RSA-ìsekóòdù. Apejuwe ati imuse ti awọn RSA alugoridimu

RSA-ìsekóòdù jẹ ọkan ninu awọn akọkọ wulo àkọsílẹ-bọtini cryptosystems o ti wa ni o gbajumo ni lilo fun ni aabo data gbigbe. Awọn oniwe-akọkọ iyato lati iru awọn iṣẹ ni wipe awọn ìsekóòdù bọtini wa ni sisi ati ki o yatọ lati awọn decryption bọtini, eyi ti o ti pa ìkọkọ. The RSA ọna , yi asymmetry wa ni da lori asa isoro ti Factoring ṣiṣiṣẹsẹhin ti awọn meji ti o tobi nomba (awọn isoro ti Factoring).

Itan ti ẹda

RSA Awọn orukọ oriširiši ti awọn ni ibẹrẹ awọn lẹta ti awọn surnames Rivest, Ṣamiri ati Adleman - awọn sayensi ti o akọkọ gbangba ṣàpèjúwe wọnyi ìsekóòdù aligoridimu ni 1977. Klifford Koks, ohun English mathimatiki, ti o sise fun British otelemuye, akọkọ lati se agbekale ohun deede eto ni 1973, sugbon o ti a ko declassified titi 1997

RSA olumulo ṣẹda ati ki o si nkede awọn àkọsílẹ bọtini da lori nla meji ti nomba paapọ pẹlu oluranlowo iye. Nomba yẹ ki o wa ni pa ìkọkọ. Ẹnikẹni le lo awọn àkọsílẹ kiri lati encrypt a ifiranṣẹ, ṣugbọn ti o ba jẹ tobi to, ki o si nikan ẹnikan pẹlu imo ti nomba le iyipada awọn ifiranṣẹ. RSA ìsekóòdù ifihan wa ni mo bi awọn ifilelẹ ti awọn isoro loni jẹ ẹya-ìmọ fanfa nipa bi a gbẹkẹle siseto.

RSA alugoridimu jẹ jo o lọra, fun eyi ti idi ti o ti wa ni ko bi o gbajumo ni lilo to taara encrypt awọn olumulo. Ni ọpọlọpọ igba, yi ọna ti o ti lo fun gbigbe ninu awọn pín bọtini ti paroko fun a to dogba ìsekóòdù bọtini, eyi ti o ni Tan le ṣe mosi olopobobo ìsekóòdù ati decryption ni a Elo ti o ga iyara.

Nígbà tí a cryptosystem ninu awọn oniwe-bayi fọọmu?

Awọn agutan ti aibaramu cryptographic bọtini Wọn si Diffie ati Hellman, ti o atejade awọn Erongba ni 1976, ni lenu oni ibuwọlu, ati ki o gbiyanju lati waye yii ti awọn nọmba. Wọn agbese nlo a pín ìkọkọ bọtini ti ipilẹṣẹ lati kan awọn nọmba ti exponentiation ìfiwọn a nomba nọmba. Sibẹsibẹ, nwọn si fi si oro ti riri ti yi iṣẹ, niwon awọn agbekale ti Factoring ti ko daradara gbọye ni akoko.

Rivest, Adi Ṣamiri, ati Adleman ni MIT ti ṣe ọpọlọpọ awọn igbiyanju lori awọn ọdun lati ṣẹda kan ọkan-ọna iṣẹ ti o jẹ soro lati iyipada. Rivest ati Ṣamiri (bi kọmputa sayensi) ti dabaa ọpọlọpọ awọn ti o pọju awọn iṣẹ, nigba ti Adleman (bi mathimatiki) lati wa fun awọn "lagbara ojuami" ti awọn alugoridimu. Ti won ti lo kan pupo ti yonuso ati ki o bajẹ se agbekale a ik eto, bayi mo bi RSA ni April 1977.

Ẹrọ itanna Ibuwọlu ati awọn àkọsílẹ bọtini

Oni Ibuwọlu tabi ẹrọ itanna Ibuwọlu, ti wa ni ohun je ara ti awọn ẹrọ itanna iwe omiran. O ti wa ni akoso ni kan awọn cryptographic data awọn ayipada. Pẹlu yi ro pe ṣee ṣe lati ṣayẹwo awọn iyege ti awọn iwe, awọn oniwe-asiri, bi daradara bi lati mọ ti o ti o o. Ni o daju, yiyan si arinrin boṣewa Ibuwọlu.

Yi cryptosystem (RSA-paroko) nfun awọn àkọsílẹ bọtini, ko dogba. Awọn oniwe-opo ti awọn isẹ ni wipe awọn meji ti o yatọ awọn bọtini ti wa ni lilo - ni pipade (ti paroko) ati ita gbangba. Ni igba akọkọ ti a ti lo lati se ina awọn oni Ibuwọlu ati ki o ni anfani lati gbo awọn ọrọ. Keji - fun awọn gangan ìsekóòdù ati ẹrọ itanna Ibuwọlu.

Lilo ibuwọlu si dara ye awọn RSA ìsekóòdù, ohun apẹẹrẹ ti eyi ti le ti wa ni dinku bi awọn kan deede ìkọkọ "ni pipade lati prying oju," awọn iwe.

Kini ni alugoridimu?

RSA alugoridimu oriširiši mẹrin igbesẹ: bọtini iran, pinpin, ìsekóòdù ati decryption. Bi tẹlẹ darukọ, RSA-ìsekóòdù pẹlu kan àkọsílẹ bọtini ati ki o kan ikọkọ bọtini. Ita gbangba le ti wa ni a mo si gbogbo ki o si wa ni lo lati encrypt awọn ifiranṣẹ. Awọn oniwe-lodi wa da ni o daju wipe awọn ifiranṣẹ ti paroko pẹlu awọn àkọsílẹ bọtini le nikan ni decrypted ni a fi fun igba akoko ti lilo a ìkọkọ bọtini.

Fun ailewu idi, awọn odidi lati wa ni yàn ni ID ki o si wa aami ni iwọn, sugbon yato ni ipari nipa kan diẹ awọn nọmba lati ṣe Factoring nira sii. Kanna kanna nọmba le ti wa ni fe ni ri nipa a igbeyewo ni won ayedero, ki awọn ìsekóòdù ti alaye gbọdọ dandan wa ni idiju.

Awọn àkọsílẹ bọtini oriširiši awọn modulus ati gbangba agbènọmbàga. Abe ile kuro ki o oriširiši ti a ikọkọ nọmba rẹ, eyi ti o yẹ ki o wa ni pa ìkọkọ.

RSA ìsekóòdù ti awọn faili ati ailagbara

Sibẹsibẹ, nibẹ ni o wa nọmba kan ti o rọrun sakasaka RSA ise sise. Nigba ti encrypting pẹlu kekere ati kekere iye ti koodu nọmba le wa ni awọn iṣọrọ la, ti o ba ti gbe root ciphertext lori awọn odidi.

Niwon awọn RSA-ìsekóòdù ni a deterministic alugoridimu (ie, ni o ni ko ID paati), ohun attacker le ni ifijišẹ lọlẹ awọn ti a ti yan ọrọ ìmọ kolu lodi si cryptosystem nipa encrypting seese plaintexts labẹ awọn àkọsílẹ bọtini ati ki o sọwedowo lori boya ti won ba wa dogba ciphertext. Semantically ni aabo cryptosystem ni a npe ni ninu awọn iṣẹlẹ ti ohun attacker ko le se iyato laarin awọn meji ìsekóòdù lati kọọkan miiran, paapa ti o ba ti o mo awọn ti o yẹ ọrọ ninu awọn ti fẹ fọọmu. Bi a ti salaye loke, RSA awọn iṣẹ miiran lai òwú ni ko semantically ni aabo.

Afikun aligoridimu fun ìsekóòdù ati aabo

Lati yago fun awọn loke isoro, ninu awọn wulo imuse ti RSA ti wa ni maa fi sii sinu diẹ ninu awọn fọọmu ti eleto, ti aileto nkún ki o to ìsekóòdù. Eleyi idaniloju wipe awọn akoonu ko ni subu laarin awọn ibiti o ti insecure plaintexts, ati pe yi ifiranṣẹ ko le wa ni re nipa ID aṣayan.

Security RSA cryptosystem ati ìsekóòdù da lori meji mathematiki isoro: awọn isoro ti Factoring tobi awọn nọmba ati awọn gangan RSA isoro. Full sisọ awọn ciphertext ati Ibuwọlu ni RSA ti wa ni ka inadmissible lori awọn arosinu ti mejeji ti awọn wọnyi isoro ko le wa ni resolved collectively.

Sibẹsibẹ, pẹlu awọn agbara lati bọsipọ nomba ifosiwewe, ohun attacker o le ṣe iṣiro awọn ìkọkọ agbènọmbàga ti gbangba bọtini ati ki o si gbo tan ọrọ sii nipa lilo awọn boṣewa ilana. Bíótilẹ o daju wipe oni ko si tẹlẹ ọna fun Factoring tobi odidi on a kilasika kọmputa ko le ṣee ri, o ti ko a ti fihan pe o ko ni tẹlẹ.

adaṣiṣẹ

Awọn ọpa, ti a npe Yafu, a le lo lati je ki awọn ilana. Adaṣiṣẹ ni YAFU jẹ ẹya to ti ni ilọsiwaju ẹya-ara ti o daapọ factorization aligoridimu ni ọgbọn ati aláwòṣe ogbon ti o minimizes akoko lati wa awọn okunfa ti lainidii input awọn nọmba. Ọpọlọpọ awọn imuṣẹ multithreaded alugoridimu gbigba Yafu kikun lilo ti olona-tabi ọpọlọpọ awọn olona-mojuto to nse (pẹlu SNFS, SIQS ati ECM). Akọkọ ti gbogbo, ti o ti wa ni dari nipa aṣẹ-ila ọpa. Ni akoko lo wiwa fun ìsekóòdù Yafu ifosiwewe lilo a mora kọmputa, o le dinku lati aaya 103,1746. Awọn ọpa lakọkọ awọn alakomeji agbara ti 320 die tabi diẹ ẹ sii. Eleyi jẹ a gidigidi eka software ti nbeere kan awọn iye ti imọ ogbon lati fi sori ẹrọ ki o si tunto. Bayi, RSA-ìsekóòdù o le jẹ ipalara C.

Sakasaka igbiyanju ni igba to šẹšẹ

Ni 2009, Bendzhamin Mudi lilo RSA-512 bit bọtini a ti sise lori deciphering kriptoteksta fun 73 ọjọ, lilo nikan daradara-mọ software (GGNFS) ati awọn apapọ tabili (meji-mojuto Athlon64 ni 1900 MHz). Bi han nipa awọn iriri, ti a beere die-die kere ju 5 GB ti disk ati nipa 2.5 gigabytes ti iranti fun awọn ilana ti "sifting."

Bi ti 2010, awọn ti nọmba ti a factored RSA 768 die gun (232 eleemewa nọmba, tabi RSA-768). Rẹ ifihan fi opin si odun meji lori orisirisi awọn ọgọrun kọmputa ni ẹẹkan.

Ni asa, awọn RSA bọtini ni o wa gun - ojo melo lati 1024 to 4096 die. Diẹ ninu awọn amoye gbagbo wipe awọn 1024-bit awọn bọtini le di unreliable ninu awọn sunmọ iwaju tabi paapa gun le ti wa ni sisan gan daradara-agbateru attackers. Sibẹsibẹ, diẹ yoo jiyan wipe 4096-bit awọn bọtini le tun ti wa ni ti sọ ninu awọn sunmọ iwaju.

asesewa

Nitorina, bi ofin, o ti wa ni pe RSA ni aabo ti o ba ti awọn nọmba ni o wa tobi to. Ti o ba ti awọn mimọ nọmba ti 300 die tabi kikuru, ati awọn ciphertext oni Ibuwọlu le ti wa ni decomposed laarin kan diẹ wakati lori kan ti ara ẹni kọmputa nipa lilo software wa tẹlẹ ni gbangba ašẹ. A bọtini ipari 512 die, bi o han, le ti wa ni la bi tete bi 1999, pẹlu awọn lilo ti kan diẹ ọgọrun awọn kọmputa. Lasiko o jẹ ṣee ṣe ni kan diẹ ọsẹ lilo a gbangba wa hardware. Bayi, o jẹ ṣee ṣe pe ni buduschembudet awọn iṣọrọ sọ RSA-enkiripiti lori awọn ika, ati awọn eto yoo di hopelessly igba atijọ.

Ifowosi ni 2003, ti a npe ni sinu ibeere ni aabo ti awọn 1024-bit bọtini. Lọwọlọwọ, o ti wa ni niyanju lati ni a kere ipari ti 2048 die-die.