RSA-kubisa. Kufotokozera ndi kugwiritsa ntchito RSA aligorivimu

RSA-kubisa ndi oyamba cryptosystems zothandiza anthu, omwe chimagwiritsidwa ntchito kufala deta otetezeka. kusiyana Aika ku ntchito zofanana ndi kiyi kubisa ndi lotseguka ndi osiyana ndi kiyi decryption, amene zobisika. Kagwiridwe RSA , asymmetry izi zachokera movutikira yeniyeni ya factoring ndi kubwezeretsa awiri ambiri yaikulu (vuto la factoring).

Mbiri ya chilengedwe

RSA dzina imakhala makalata woyambirira wa mayina Rivest, Shamir ndi Adleman - asayansi amene poyamba poyera anafotokoza awa ma aligorivimu kubisa mu 1977. Klifford Koks, ndi English masamu, yemwe ankagwira ntchito British nzeru, woyamba kukhala dongosolo lofanana mu 1973, koma declassified mpaka 1997

RSA wosuta amalenga kenako limafalitsa chinsinsi anthu zochokera manambala awiri akuluakulu yaikulu pamodzi ndi mtengo wothandiza. manambala Yaikulu ayenera zobisika. Aliyense akhoza kugwiritsa ntchito kiyi anthu chitetezo uthenga, koma ngati ziri zazikulu mokwanira, ndiye kokha munthu wodziwa manambala yaikulu akhoza decode uthenga. RSA kubisa Kuwulura chikudziwika ngati vuto waukulu lero ndi kukambirana momasuka za mmene limagwirira odalirika.

RSA aligorivimu zimakhalanso pang'onopang'ono, chifukwa omwe si monga chimagwiritsidwa ntchito kuti mwachindunji chitetezo wosuta. Nthawi zambiri, njira imeneyi ntchito kufala mu kiyi nawo encrypted kwa ofananira kiyi kubisa, womwe tikhoza kuchita ntchito kubisa chochuluka ndi decryption pa liwiro apamwamba.

Pamene panali cryptosystem maonekedwe?

Ganizo cryptographic kiyi asymmetric zimachitika Diffie ndi Hellman, amene lofalitsidwa chiphunzitso cha mu 1976, kuyambitsa anasaina digito, ndipo tikuyesetsa kutsatira chiphunzitso cha manambala. chiphunzitso awo amagwiritsa limodzi chinsinsi kiyi opangidwa kuchokera wina chiwerengero cha exponentiation modulo nambala yaikulu. Komabe, anasiya kutsegula nkhani ya kukwaniritsidwa kwa nchito imeneyi, popeza mfundo za factoring sanali bwinobwino pa nthawi.

Rivest, Adi Shamir, ndi Adleman pa MIT kuti ankafuna angapo zaka kulenga njira ya ntchito kuti n'zovuta decode. Rivest ndi Shamir (monga asayansi kompyuta) akhala akuganizira ntchito ambiri ofuna, pamene Adleman (ngati masamu) kufunafuna "zofooka" wa aligorivimu ndi. Iwo ntchito zambiri likuyandikira ndipo m'kupita kupangika komaliza, lomwe pano RSA mu April 1977.

Pakompyuta siginecha ndi kiyi anthu

Intaneti siginecha kapena siginecha zamagetsi, ndi mbali yofunika ya mitundu chikalata amagetsi. Iwo apangidwa pa ena kusintha cryptographic deta. Ndi wamphamvu zotheka kuonanso kukhulupirika kwa bukuli, chinsinsi chake, komanso kudziwa amene mwini. Ndipotu njira ina wamba muyezo siginecha.

cryptosystem izi (RSA-encrypted) amapereka chinsinsi anthu, mosiyana ofananira. mfundo zake ntchito ndi mafungulo awiri osiyana ntchito - anatseka (encrypted) ndipo panja. Woyamba ntchito kupanga siginecha digito kenako athe decrypt lembalo. Chachiwiri - kwa kubisa yeniyeni siginecha amagetsi.

Kugwiritsa anasaina bwino kumvetsa kubisa RSA, chitsanzo cha zomwe angathe kuchepetsedwa ngati chinsinsi yachibadwa "anatseka m'maso kuwafunsa mafunso ochititsa manyazi," mpukutuwu.

Kodi aligorivimu?

RSA aligorivimu imakhala njira zinayi: kiyi m'badwo, kugawa, kubisa ndi decryption. Monga tanenera kale, RSA-kubisa zikuphatikizapo chinsinsi anthu ndi kiyi wapadera. Panja angadziwike kuti zonse ndi ntchito chitetezo mauthenga. Kwenikweni ake kwagona kuti mauthenga encrypted ndi kiyi anthu akhoza decrypted mu nthaŵi ntchito kiyi chinsinsi.

Zifukwa chitetezo cha integers ifunika mwachisawawa ndi kukhala zofanana kukula, koma amasiyana kutalika ndi manambala angapo kuti factoring kovuta. Chomwecho nambalayi ungagwire anapezeka ndi mayeso osavuta kumva, kotero kubisa wa mudziwe ayenera kukhala zovuta.

Kiyi anthu imakhala ya modulus ndipo amalimbikitsa anthu. M'nyumba wagawo ndi imakhala ndi chithunzi payekha, zimene ziyenera zobisika.

RSA kubisa owona ndi zofooka

Komabe, pali angapo ophweka kuwakhadzula RSA njira. Pamene encrypting ndi mfundo otsika ndi ka manambala malamulo mosavuta anatsegula, ngati Sankhapo muzu ciphertext pa integers lapansi.

Popeza RSA-kubisa ndi aligorivimu deterministic (ie, alibe chigawo mwachisawawa), ndi tizilomboto angathe kufalitsa anasankha malemba lotseguka adzaukira cryptosystem ndi encrypting plaintexts mwina pansi kiyi anthu ndi macheke ngati ali ofanana ciphertext. Semantically cryptosystem otetezeka amatchedwa kukachitika kuti tizilomboto sangathe kusiyanitsa kubisa awiri ndi mzake, ngakhale amadziwa malemba zogwirizana mu mawonekedwe kukodzedwa. Monga tafotokozazi, RSA zina popanda padding si semantically otetezeka.

ma aligorivimu zoonjezera kubisa ndi chitetezo

Kuti mupewe mavuto pamwamba, mu kukhazikitsa ntchito RSA zambiri anaikapo mu mawonekedwe ena kusasintha, osapanganika kudzazidwa pamaso kubisa. Izi zipangitsa kuti zili asagwe mkati osiyanasiyana plaintexts osatetezeka, ndi kuti uthenga uwu sungakhoze anathana ndi osankhidwa mwachisawawa.

Security RSA cryptosystem ndi kubisa zochokera mavuto awiri masamu: vuto la factoring ambiri ndi leni RSA vuto. Full Kuwulura wa ciphertext ndi siginecha mu RSA imatengedwa inadmissible pa kopanda kuti mavuto amenewa sangathe pamodzi.

Komabe, ndi luso achire zinthu zazikulu, ndi tizilomboto mukhoza kuwerengera amalimbikitsa chinsinsi cha fungulo onse ndiponso decrypt lemba ntchito ndondomeko muyezo. Ngakhale kuti masiku ano palibe njira zilipo kwa factoring integers lalikulu pa kompyuta chakale sichingapezeke, sizinapezekebe kutsimikiziridwa kuti iye kulibe.

automation

The chida, wotchedwa Yafu, angagwiritsidwe ntchito konza ndondomekoyi. Zokha mu YAFU ndi chinthu zapamwamba kuti Chili factorization ma aligorivimu mu njira ozindikira ndipo dziphunzitsiranso kuti minimizes nthawi kupeza zinthu za manambala athandizira umasinthasintha. implementations kwambiri multithreaded aligorivimu kulola Yafu ntchito mokwanira multi- kapena ambiri mapurosesa Mipikisano pachimake (kuphatikizapo SNFS, SIQS ndi ECM). Choyamba, iwo ukulamuliridwa ndi lamulo mzere chida. nthawi imene kufunafuna kubisa Yafu Chinthu ntchito kompyuta ochiritsira, angathe kusanduka masekondi 103,1746. Chida njira bayinare mphamvu Akamva 320 kapena kuposa. Izi ndi mapulogalamu zovuta kuti amafuna wina kuchuluka kwa luso luso kukhazikitsa ndi sintha. Choncho, RSA-kubisa akhale osatetezeka C.

Kuwakhadzula zoyesayesa posachedwapa

Mu 2009, Bendzhamin Mudi ntchito RSA-512 pang'ono Chinsinsi ntchito pa chinawathandiza kumvetsa n'chakuti kriptoteksta kwa masiku 73, ntchito pulogalamu yekha odziwika (GGNFS) ndi kompyuta pafupifupi (wapawiri-pachimake Athlon64 pa 1900 MHz). Malinga ndi zochitika, chofunika pang'ono osachepera 5 GB wa litayamba ndi za 2.5 gigabytes kukumbukira kuti ndondomeko ya "sifting."

Monga cha 2010, chiwerengero chachikulu kwambiri anali factored RSA 768 Akamva yaitali (232 decimal manambala, kapena RSA-768). Kuwulura wake unatha zaka ziwiri pa kompyuta mazana angapo nthawi imodzi.

Zochita mafungulo RSA yaitali - ambiri kuchokera 1024 mpaka 4096 Akamva. Akatswiri ena amakhulupirira kuti makiyi 1024-bit akhale wosadalirika posachedwapa kapena kuposerapo akhoza losweka nkhondo kwambiri bwino akusukulu yapansi ulele. Komabe, pang'ono anganene kuti makiyi 4096-bit Angagwiritsidwenso kuwuluridwa posachedwapa.

ziyembekezo

Choncho, monga ulamuliro, amaganiza kuti RSA ndi otetezeka ngati manambala ndi okwanira. Ngati m'munsi chiwerengero cha Akamva 300 kapena aafupi, ndi ciphertext digito siginecha akhoza decomposed patangotha maola ochepa pa kompyuta munthu pogwiritsa ntchito pulogalamu kale likupezeka mu ankalamulira. Mfundo kutalika 512 Akamva, monga tikuonera, akhoza anatsegula mwamsanga 1999, ntchito makompyuta mazana angapo. Masiku ano n'zotheka mu masabata angapo ntchito hardware zilipo poyera. Choncho, n'zotheka kuti buduschembudet mosavuta kuwuluridwa RSA-encrypted pa zala, ndi dongosolo adzakhala kwadzaoneni chakale.

Mwalamulo mu 2003, unakaikiridwa chitetezo cha mafungulo 1024-bit. Panopa, izo tikulimbikitsidwa kuti kutalika osachepera 2048 Akamva.