RSA-encryption. Maelezo na utekelezaji wa RSA algorithm

RSA-encryption ni moja ya kwanza cryptosystems vitendo umma muhimu ambayo ni sana kutumika kwa ajili ya maambukizi ya data salama. tofauti yake kuu na huduma kama hiyo ni kwamba ufunguo encryption ni wazi na tofauti na muhimu decryption, ambayo ni siri. teknolojia RSA , asymmetry hii ni misingi ya ugumu vitendo ya factoring uchezaji wa mbili idadi kubwa mkuu (tatizo la factoring).

Historia ya viumbe

RSA jina lina barua ya awali ya majina Rivest, Shamiri na Adleman - wanasayansi ambao kwanza hadharani alielezea haya algorithms encryption mwaka 1977. Klifford Koks, Kiingereza mwanahisabati, ambaye alifanya kazi kwa ajili ya huduma ya Uingereza akili, kwanza ili kuunda mfumo sawa katika 1973, lakini haikuwa declassified hadi 1997

RSA user inajenga na kisha kuchapisha ufunguo wa umma kulingana na namba mbili kubwa mkuu pamoja na thamani ya msaidizi. namba Mkuu kuhifadhiwa siri. Mtu yeyote anaweza kutumia ufunguo wa umma encrypt ujumbe, lakini kama ni kubwa ya kutosha, basi tu mtu aliye na ujuzi wa idadi mkuu unaweza Decode ujumbe. RSA encryption kutoa taarifa inajulikana kama tatizo kubwa leo ni mjadala wa wazi juu ya namna ya utaratibu wa kuaminika.

RSA algorithm ni kiasi polepole, kwa sababu ambayo ni haitumiki kwa upana kwa moja kuficha user. Katika hali nyingi, njia hii ni kutumika kwa ajili ya maambukizi katika ufunguo pamoja fiche kwa linganifu muhimu kuficha, ambayo kwa upande unaweza kufanya shughuli encryption wingi na decryption kwa kasi kubwa zaidi.

Wakati kulikuwa na cryptosystem katika hali yake ya sasa?

wazo la Kriptografia muhimu zisopacha kuhusishwa na Diffie na Hellman, ambaye kuchapishwa dhana mwaka 1976, kuanzisha saini digital, na kujaribu kutumia nadharia ya idadi. uundaji yao inatumia pamoja siri muhimu yanayotokana na baadhi ya idadi ya exponentiation modulo idadi ya waziri mkuu. Hata hivyo, kushoto kufungua suala la utambuzi wa kazi hii, tangu kanuni za factoring hakuwa vizuri kwa wakati.

Rivest, Adi Shamir, na Adleman katika MIT kuwa alifanya majaribio kadhaa katika kipindi cha miaka ya kujenga njia moja ya kazi ambao ni mgumu kusimbua. Rivest na Shamir (kama wanasayansi kompyuta) wamependekeza kazi nyingi uwezo, wakati Adleman (kama hisabati) na kutafuta "pointi dhaifu" ya algorithm. Walizotumia mengi ya mbinu na hatimaye kuunda mfumo wa mwisho, sasa inajulikana kama RSA katika Aprili 1977.

Electronic sahihi na ufunguo wa umma

Digital saini au saini za elektroniki, ni sehemu muhimu ya aina hati elektroniki. Ni sumu kwa baadhi ya mabadiliko Kriptografia data. Pamoja na sifa hii inawezekana kuangalia uadilifu wa hati, usiri wake, pamoja na kuamua ambaye anamiliki yake. Kwa kweli, mbadala kwa kawaida kiwango sahihi.

cryptosystem hii (RSA-encrypted) inatoa ufunguo wa umma, tofauti na linganifu. Kanuni yake ya kazi ni kwamba funguo mbili tofauti hutumika - imefungwa (encrypted) na nje. kwanza ni kutumika kuzalisha sahihi digital na kisha kuwa na uwezo ili kusimbua maandishi. Pili - kwa ajili ya encryption halisi na sahihi ya elektroniki.

Kwa kutumia saini ili kuelewa encryption RSA, ni mfano wa mambo ambayo yaweza kupunguzwa kama siri kawaida "kufungwa kutoka machoni mwa watu," hati.

Ni nini algorithm?

RSA algorithm lina hatua nne: ufunguo wa kizazi, usambazaji, encryption na decryption. Kama tayari kutajwa, RSA-encryption ni pamoja ufunguo wa umma na ufunguo binafsi. Outdoor wanaweza kujulikana kwa wote na hutumiwa kutia fumbo ujumbe. Asili yake liko katika ukweli kwamba ujumbe kwa njia fiche kwa ufunguo wa umma inaweza tu decrypted katika kipindi fulani cha muda kwa kutumia ufunguo wa siri.

Kwa sababu za usalama, nambari halisi ya kuchaguliwa katika random na kuwa sawa katika ukubwa, lakini tofauti katika urefu na idadi chache ya kufanya factoring magumu zaidi. Same idadi sawa inaweza kufanywa kupatikana kwa mtihani katika ujinga wao, hivyo encryption wa habari lazima lazima kuwa ngumu.

ufunguo wa umma lina modulus na exponent ya umma. Indoor kitengo na lina takwimu binafsi, ambayo lazima iwekwe siri.

RSA encryption ya mafaili na udhaifu

Hata hivyo, kuna idadi ya rahisi Hacking RSA taratibu. Wakati encrypting na maadili ya chini na ndogo ya namba code inaweza kwa urahisi kufunguliwa, kama pick mizizi nakala ya siri juu ya integers.

Tangu RSA-encryption ni algorithm la kuonyesha (yaani, hana sehemu random), mshambulizi anaweza kufanikiwa kuzindua kuchaguliwa Nakala wazi mashambulizi dhidi cryptosystem na encrypting plaintexts uwezekano chini ya muhimu ya umma na hundi na kama wao ni sawa nakala ya siri. Semantically cryptosystem salama inaitwa ikitokea kwamba mshambuliaji hawezi kutofautisha kati ya encryption mbili kutoka kwa kila mmoja, hata kama anajua maandiko muhimu katika mfumo kupanua. Kama ilivyoelezwa hapo juu, RSA huduma nyingine bila padding si yasiyokuwa salama.

mipangilio ya ziada kwa ajili encryption na ulinzi

Ili kuepuka matatizo hapo juu, katika utekelezaji wa vitendo wa RSA ni kawaida kuingizwa katika baadhi ya fomu ya muundo, randomized kujaza kabla encryption. Hii kuhakikisha kwamba maudhui hayako katika aina mbalimbali ya plaintexts salama, na kwamba ujumbe huu hauwezi kutatuliwa kwa uteuzi maalum.

Usalama RSA cryptosystem na encryption kulingana na matatizo mawili hisabati: tatizo la factoring idadi kubwa na ya kweli RSA tatizo. Full kutoa taarifa ya nakala ya siri na saini katika RSA ni kuchukuliwa haikubaliki katika dhana kwamba ile vizuri haliwezi kutatuliwa kwa pamoja.

Hata hivyo, pamoja na uwezo wa kuokoa mambo mkuu, mshambulizi anaweza mahesabu exponent siri ya ufunguo wa umma na kisha decrypt maandishi kwa kutumia utaratibu kiwango. Licha ya ukweli kwamba leo hakuna njia zilizopo kwa factoring nambari halisi kubwa kwenye kompyuta classical hawezi kupatikana, ni haijawahi kuthibitika kuwa haipo.

automation

chombo, inaitwa Yafu, inaweza kutumika kuongeza mchakato. Automation katika YAFU ni hulka ya juu ambayo inaunganisha factorization mipangilio katika mbinu miliki na adaptive kwamba itapunguza muda wa kupata mambo ya idadi ya pembejeo kiholela. utekelezaji Wengi multithreaded algorithm kuruhusu Yafu kutumia kikamilifu mbalimbali au wengi wasindikaji mbalimbali ya msingi (ikiwa ni pamoja SNFS, SIQS na ECM). Kwanza kabisa, ni kudhibitiwa na chombo amri ya mstari. muda unaotumika kutafuta encryption Yafu sababu kwa kutumia kompyuta za kawaida, inaweza kuwa kupunguzwa kwa sekunde 103.1746. chombo michakato binary uwezo wa bits 320 au zaidi. Hii ni programu ngumu sana ambayo inahitaji kiasi fulani cha ujuzi wa kiufundi kwa kufunga na configure. Hivyo, RSA-encryption inaweza kuwa katika mazingira magumu C.

Hacking majaribio katika miaka ya hivi karibuni

Mwaka 2009, Bendzhamin Mudi kutumia RSA-512 bit ufunguo alikuwa akifanya kazi kwenye deciphering kriptoteksta kwa siku 73, kwa kutumia programu tu maalumu (GGNFS) na desktop wastani (dual-msingi Athlon64 katika 1900 MHz). Kama inavyoonekana kwa uzoefu, required kidogo chini ya 5 GB ya disk na 2.5 gigabytes ya kumbukumbu kwa ajili ya mchakato wa "sifting."

Kama ya 2010, idadi kubwa mara factored RSA 768 bits kwa muda mrefu (232 decimal ya tarakimu, au RSA-768). kutoa taarifa yake ilidumu miaka miwili kwenye kompyuta mia kadhaa kwa mara moja.

Katika mazoezi, funguo RSA ni ndefu - kawaida 1024-4096 bits. Baadhi ya wataalamu wanaamini kwamba funguo 1024-bit inaweza kuwa uhakika katika siku chache zijazo au hata tena inaweza kupasuka washambuliaji sana vizuri unaofadhiliwa. Hata hivyo, wachache wanasema kuwa funguo 4096-bit pia kuwa wazi hivi karibuni.

matarajio

Kwa hiyo, kama sheria, ni kudhani kwamba RSA ni salama kama idadi ni kubwa ya kutosha. Kama msingi idadi ya bits 300 au mfupi, na nakala ya siri digital saini inaweza iliyooza baada ya saa chache juu ya kompyuta binafsi kwa kutumia programu tayari inapatikana katika miliki ya umma. ufunguo urefu 512 bits, kama inavyoonekana, inaweza kufunguliwa mapema mwaka 1999, pamoja na matumizi ya kompyuta mia kadhaa. Siku hizi inawezekana katika wiki chache kutumia vifaa kwa umma. Hivyo, inawezekana kwamba katika buduschembudet urahisi wazi RSA-encrypted kwenye vidole, na mfumo wa kuwa hopelessly imepitwa na wakati.

Rasmi mwaka 2003, aliitwa katika swali usalama wa funguo 1024-bit. Hivi sasa, inashauriwa kuwa muda wa matumizi ya 2048 bits.