RSA-encrypt. Paglalarawan at pagpapatupad ng RSA algorithm

RSA-encryption ay isa sa mga unang praktikal na pampublikong-key cryptosystems na malawak na ginagamit para sa mga secure na paghahatid ng data. Nito pangunahing pagkakaiba mula sa mga katulad na serbisyo ay na ang encryption key ay bukas at naiiba mula sa decryption key, na kung saan ay pinananatiling lihim. Ang RSA teknolohiya , ito kawalaan ng simetrya ay batay sa mga praktikal na kahirapan ng factoring ang pag-playback ng dalawang malalaking numero ng kalakasan (ang problema ng factoring).

Kasaysayan ng paglikha

RSA pangalan ko ay binubuo ng inisyal na titik ng apelyido Rivest, Shamir at Adleman - ang mga siyentipiko kung sino ang unang sa publiko na inilarawan ang mga encryption algorithm sa 1977. Klifford Koks, isang Ingles na matematiko, na nagtrabaho para sa British katalinuhan serbisyo, ang unang upang bumuo ng isang katumbas na sistema sa 1973, ngunit hindi ito ay declassified hanggang 1997

RSA user ay lumilikha at pagkatapos ay nagpa-publish ng pampublikong susi batay sa dalawang malaking kalakasan mga numero kasama ang mga auxiliary halaga. Prime numero ay dapat na pinananatiling lihim. Kahit sino ay maaaring gamitin ang pampublikong key upang i-encrypt ang isang mensahe, ngunit kung ito ay malaki sapat na, pagkatapos lamang ng isang tao na may kaalaman ng de-kalidad na mga numero ay maaaring decode ng mga mensahe. RSA encryption pagsisiwalat ay kilala bilang ang pangunahing problema sa araw na ito ay isang bukas na talakayan tungkol sa kung paano ang isang maaasahang mekanismo.

RSA algorithm ay relatibong mabagal, na kung saan dahilan ng ito ay hindi bilang malawak na ginagamit upang direktang i-encrypt ang user. Sa karamihan ng mga kaso, ang pamamaraan na ito ay ginagamit para sa paghahatid sa nakabahaging key-encrypt para sa isang proporsyonado encryption key, na kung saan maaaring magsagawa ng mga pagpapatakbo bulk encryption at decryption sa isang mas mataas na bilis.

Kapag nagkaroon ng cryptosystem sa kasalukuyang anyo nito?

Ang ideya ng tabingi cryptographic key maiugnay sa Diffie at Hellman, na-publish ang konsepto noong 1976, na nagpapakilala sa mga digital na lagda, at sinusubukan upang ilapat ang teorya ng mga numero. Kanilang pagbabalangkas ay gumagamit ng isang shared lihim na key na nabuo mula sa isang tiyak na bilang ng mga Eksponente modulo ng kalakasan numero. Gayunman, iniwan nila ang mga isyu ng pagsasakatuparan ng mga function na ito, dahil sa ang mga prinsipyo ng factoring ay hindi naunawaan nang mabuti sa oras.

Rivest, Adi Shamir, at Adleman sa MIT na ginawa ng ilang mga pagtatangka sa mga nakaraang taon upang lumikha ng isang one-way na function na ay mahirap i-decode. Rivest at Shamir (tulad ng mga siyentipiko computer) nagpanukala maraming mga potensyal na mga pag-andar, habang Adleman (tulad ng matematika) upang maghanap para sa "mahina puntos" ng algorithm. Ginamit nila ang isang pulutong ng mga approach na ito at sa huli bumuo ng isang pangwakas na sistema, na kilala ngayon bilang RSA noong Abril 1977.

Electronic signature at ang public key

Digital lagda o electronic na lagda, ay isang mahalagang bahagi ng electronic mga uri ng dokumento. Ito ay binuo sa isang tiyak na cryptographic mga pagbabago ng data. Gamit ang katangiang ito posible upang suriin ang integridad ng mga dokumento, ang pagiging lihim nito, pati na rin upang matukoy kung sino ang nagmamay-ari nito. Sa katunayan, isang alternatibo sa ordinaryong karaniwang lagda.

Ito cryptosystem (RSA-encrypt) ay nag-aalok ng pampublikong susi, hindi tulad ng simetriko. Ang prinsipyo ng operasyon ay na ang dalawang magkaibang mga susi ay ginagamit - sarado (encrypted) at panlabas. Ang una ay ginagamit upang bumuo ng mga digital na lagda at pagkatapos ay magagawang upang i-decrypt ang text. Pangalawa - para sa aktwal na pag-encrypt at electronic signature.

Ang paggamit ng mga lagda upang mas mahusay na maunawaan ang RSA encryption, isang halimbawa nito ay maaaring nabawasan bilang isang normal na lihim na "sarado mula sa prying mata," ang dokumento.

Ano ang algorithm?

RSA algorithm ay binubuo ng apat na hakbang: susi henerasyon, pamamahagi, encryption at decryption. Bilang na nabanggit, RSA-encryption ay nagsasama ng isang public key at pribadong key. Panlabas na maaaring kilala sa lahat at ay ginagamit upang i-encrypt mga mensahe. Nito kakanyahan ay namamalagi sa ang katunayan na ang mga mensahe na naka-encrypt na may mga pampublikong key ay maaari lamang decrypted sa isang naibigay na tagal ng panahon ng paggamit ng isang lihim na key.

Para sa mga kadahilanang kaligtasan, ang mga intedyer na pinili nang random at maging magkapareho sa sukat, ngunit naiiba ang haba sa pamamagitan ng ilang mga numero upang gumawa ng factoring mas mahirap. Same parehong numero ay maaaring epektibong matagpuan sa pamamagitan ng isang pagsubok sa kanilang pagiging simple, kaya ang pag-encrypt ng impormasyon ay dapat na kinakailangang maging kumplikado.

Ang public key ay binubuo ng mga modulus at pampublikong exponent. Panloob na yunit at binubuo ng isang pribadong figure, na dapat ay pinananatiling lihim.

RSA encryption ng mga file at kahinaan

Subalit, may mga isang bilang ng mga simpleng pag-hack RSA mekanismo. Kapag pag-encrypt na may mababa at maliit na mga halaga ng mga numero ng code maaaring madaling binuksan, kung ang pick-ugat ciphertext sa ibabaw ng integer.

Dahil ang RSA-encryption ay isang deterministic algorithm (ibig sabihin, ay walang mga random na mga bahagi), isang magsasalakay ay maaaring matagumpay na ilunsad ang napiling teksto open-atake laban sa mga cryptosystem sa pamamagitan ng pag-encrypt malamang plaintexts sa ilalim ng public key at mga tseke sa kung ang mga ito ay pantay-pantay ciphertext. Semantically secure na cryptosystem ay tinatawag na sa kaganapan na ang isang magsasalakay ay hindi maaaring makilala sa pagitan ng dalawang pag-encrypt mula sa bawat isa, kahit na alam niya ang may-katuturang mga teksto sa pinalawak na form. Tulad ng inilarawan sa itaas, RSA iba pang mga serbisyo nang walang padding ay hindi semantically secure.

Karagdagang mga algorithm para sa encryption at proteksyon

Upang maiwasan ang mga problema sa itaas, sa mga praktikal na pagsasakatuparan ng RSA ay karaniwang ipinasok sa ilang anyo ng istrakturang, randomized pagpuno bago encryption. Sinisiguro nito na ang nilalaman ay hindi mahulog sa loob ng hanay ng mga hindi ligtas plaintexts, at na ang mensaheng ito ay hindi maaaring malutas sa pamamagitan ng random na pagpili.

Security RSA cryptosystem at encryption batay sa dalawang mga problema sa matematika: ang problema ng factoring malalaking numero at ang aktwal na problema RSA. Buong pagsisiwalat ng ciphertext at lagda sa RSA ay itinuturing na hindi tinatagusan sa pagpapalagay na ang parehong mga problema ay hindi maaaring malutas kapag pinagsama-sama.

Gayunman, na may kakayahan na mabawi ang de-kalidad na mga kadahilanan, ang isang magsasalakay ay maaaring kalkulahin ang lihim exponent ng pampublikong key at pagkatapos ay i-decrypt teksto gamit ang standard na pamamaraan. Sa kabila ng katotohanan na ngayon walang umiiral na paraan para sa factoring malaking integer sa isang classical computer ay hindi maaaring matagpuan, ito ay hindi pa napatunayan na siya ay hindi umiiral.

pag-aautomat

Ang tool na ito, na tinatawag na Yafu, ay maaaring magamit upang i-optimize ang proseso. Automation sa YAFU ay isang advanced na tampok na pinagsasama paktorisasyon algorithm sa intelektwal na at nakakapag-agpang pamamaraan na minimizes ang oras upang mahanap ang mga kadahilanan ng mga arbitrary na numero ng input. Karamihan sa mga pagpapatupad multithreaded algorithm na nagpapahintulot Yafu buo ang mga multi- o maraming mga multi-core processors (kabilang SNFS, SIQS at ECM). Una sa lahat, ito ay kinokontrol ng command-line tool. Ang oras na ginugol naghahanap para sa pag-encrypt Yafu factor paggamit ng isang maginoo computer, maaari itong mabawasan sa ilang mga segundo 103.1746. Ang tool na maproseso ang mga binary na kapasidad ng 320 bits o higit pa. Ito ay isang napaka-komplikadong software na ay nangangailangan ng isang tiyak na halaga ng teknikal na kasanayan upang i-install at i-configure. Kaya, RSA-encryption ay maaaring maging mahina C.

Hacking pagtatangka sa kamakailang mga beses

Noong 2009, Bendzhamin Mudi gamit RSA-512 bit key ay nagtatrabaho sa deciphering kriptoteksta para sa 73 araw, gamit lamang ang mga kilalang software (GGNFS) at ang average na desktop (dual-core Athlon64 sa 1900 MHz). Tulad ng ipinapakita sa pamamagitan ng mga karanasan, kinakailangan bahagyang mas mababa sa 5 GB ng disk at tungkol sa 2.5 gigabytes ng memory para sa proseso ng "bistay."

Bilang ng 2010, ang pinakamalaking bilang ay isinasali RSA 768 bits mahaba (232 mga decimal digit, o RSA-768). Ang kanyang pagsisiwalat ay tumagal ng dalawang taon sa ilang daang mga computer sabay-sabay.

Sa pagsasanay, ang RSA keys ay matagal - karaniwang 1024-4096 bits. Ang ilang mga eksperto ay naniniwala na ang 1024-bit key ay maaaring maging hindi kapani-paniwala sa malapit na hinaharap o kahit na maaaring may lamat napaka-well-pinondohan attackers. Gayunman, ang ilang ay magtaltalan na 4096-bit key ay maaari ring isiwalat sa malapit na hinaharap.

prospects

Samakatuwid, bilang isang panuntunan, ito ay ipinapalagay na RSA ay ligtas kung ang mga numero ay malaki sapat. Kung ang batayang bilang ng 300 bits o mas maikli, at ang ciphertext pirmang digital ay maaaring decomposed sa loob ng ilang oras sa isang personal computer gamit ang software na magagamit na sa pampublikong domain. Ang isang pangunahing length 512 bits, tulad ng ipinapakita, ay maaring mabuksan kasing aga ng 1999, ang paggamit ng ilang daang mga computer. Kasalukuyan ito ay posible sa loob ng ilang linggo ng paggamit ng isang pampublikong magagamit na hardware. Kaya, ito ay posible na sa buduschembudet madaling isiwalat RSA-encrypt sa mga daliri, at ang sistema ay maging hopelessly lipas na sa panahon.

Opisyal sa 2003, ay tinatawag na sa tanong sa seguridad ng 1024-bit key. Sa kasalukuyan, ito ay inirerekomenda na magkaroon ng isang minimum na haba ng 2048 bits.