RSA, vai tas tiešām ir tik vienkārši? RSA šifra parametru izvēle un iespējamās sekas Šifrēšana, izmantojot rsa algoritmu

Ne visi personālo datoru iekārtu lietotāji zina un saprot, kas ir RSA šifrēšana, un ir pārsteigti, izdzirdot šo terminu. Bet šajā koncepcijā nav slēpta nekā sarežģīta. RSA šifrēšana ir tikai kriptosistēma, kas ļauj droši izmantot visus elektroniskos datus, kas izveidoti, izmantojot datortehnoloģiju. Tā nav datu atšifrēšana, kad failus nevar nolasīt, nezinot noteiktu kodu. RSA šifrēšana nozīmē, ka atslēgas ir atvērtas.

RSA šifrēšana darbojas pēc faktoringa principa. Kā šis? Un tas ir faktorings
divu lielu skaitlisku datu reproducēšana.

Kas izveidoja RSA šifrēšanas sistēmu?

RSA šifrēšanas algoritms tika izveidots tālajā 1977. gadā, tā veidotāji ir zinātnieki Rivest, Shamir, Adleman, viņu uzvārdu sākuma burtu saīsinājums veido terminu RSA. Agrāku algoritmu izstrādāja Klifords Kokss, matemātiķis no Anglijas, kurš strādāja valsts izlūkdienestos. 1973. gadā viņam izdevās izveidot līdzvērtīgu sistēmu, taču to izmantoja tikai klasificētas personas, un tehnika netika izplatīta parasto personālo datoru aprīkojuma lietotāju līmenī.

Kā darbojas RSA šifrēšana?

Sistēmas lietotājs vispirms izveido un pēc tam publicē publisko atslēgu, kuras pamatā ir divi lieli skaitļi, tikai ar palīgvērtību. Vienkāršākie skaitļi tiek turēti noslēpumā. Lai, piemēram, lasītu e-pastu, jums vienkārši jāizmanto dokumenta publiskā atslēga, bet, ja atslēga ir gara, informācijai kļūst grūti piekļūt.

Mūsdienās RSA šifrēšana tiek raksturota kā ne pārāk uzticama datu šifrēšanas metode. Tas ir lēns algoritms, tāpēc parasto datoru lietotāju vidū tas nav tik izplatīts. Kāpēc tad šī sistēma tika izveidota, ja parastie datorzinātnieki to praktiski neizmanto?

Lieta ir tāda, ka tā ir atradusi savu pielietojumu simetriskas šifrēšanas atslēgas publisko atslēgu šifrētā pārraidē, kas paredzēta lielapjoma šifrēšanai un atšifrēšanai lielā ātrumā.

Mūsdienu asimetrisko atslēgu kriptosistēma radās, pateicoties Difija un Helmena darbam. Viņi izstrādāja koncepciju 1976. gadā un prezentēja to sabiedrībai kā digitālus ierakstus. Viņi varēja izveidot publisko atslēgu, pamatojoties uz principu, ka noteikta skaitļa paaugstināšana modulo pirmo skaitli. Bet viņu princips palika karājās gaisā, jo tajā laikā paši faktoringa principi vēl nebija labi izpētīti.

Rivests, Adims Šamirs, Adlemans neapstājās pie iepriekš sasniegtā un rūpīgi izstrādāja vienvirziena funkcijas mehānismu, kuru nav tik viegli atšifrēt. Rivests un Šamirs strādāja tieši pie pašām funkcijām, un Adlemans meklēja nepilnības izveidotajos algoritmos. Galu galā viņiem izdevās izveidot RSA asimetrisko atslēgu sistēmu.

Ciparparaksts un publiskās atslēgas komunikācija

Šobrīd daudzi uzņēmumi savās darba aktivitātēs izmanto šādu elektronisko elementu kā digitālo parakstu. Izveidotie elektroniskie dokumenti, kas satur tā saukto ciparparakstu, ir oficiāli likumīgā līmenī atzīti dokumenti. Elektroniskais ciparparaksts tiek izveidots, kad dati tiek kriptogrāfiski mainīti.

Šī alternatīva parastajam parakstam ļauj padarīt dokumentu konfidenciālu, nodrošināt tā integritāti un vienmēr iegūt informāciju par tā veidotāju un īpašnieku.

Elektroniskais paraksts ir cieši saistīts ar attiecīgo RSA šifrēšanu. Šī sistēma, kā minēts iepriekš, pieņem publiskās atslēgas klātbūtni. Mūsdienās praksē tiek izmantotas divas atslēgas - publiskās - visiem zināmās un privātās - šifrētas, lai nepieļautu nepilnvarotu personu piekļuvi informācijai.

Tādējādi publiskā atslēga ļauj piekļūt dokumentam ar elektronisko zīmogu, bet privātā atslēga ļauj atšifrēt parakstu un to pārbaudīt. Citiem vārdiem sakot, RSA šifrēšana ļauj paslēpt dokumentus no ziņkārīgo acīm, paturēt tos noslēpumā, bet ar iespēju tiem piekļūt īstajā laikā.

Izdomāsim, kāda ir izgudrotā algoritma būtība?

RSA šifrēšana darbojas četros posmos:
atslēgu ģenerēšana;
atslēgu izplatīšana;
atslēgas šifrēšana;
atslēgu atšifrēšana.

RSA šifrēšanas princips apvieno publisko un privāto atslēgu izveidi. Pakavēsimies pie šī vēlreiz. Atvērts – zināms visiem, var izmantot ziņojumu šifrēšanai. Šos elektroniskos datus var atšifrēt, izmantojot privāto atslēgu. Veidojot publiskās atslēgas, skaitļi tiek izvēlēti nejauši un ir vienāda izmēra, bet atšķiras pēc ieraksta ilguma, tāpēc faktorings ir grūtāks.

Identiskus skaitļus var atrast, pārbaudot to vienkāršību. Tādējādi šifrēšana pakāpeniski kļuva sarežģītāka. No kā sastāv publiskā atslēga? Un tas sastāv no parastā moduļa un tā sauktā publiskā eksponenta. Bet slēgtajā ir iekļauts modulis un privātais indikators, kas netiek nodrošināts nevienam, izņemot radītāju.

RSA šifrēšanas tehnikas nepilnības

Neskatoties uz pārdomāto šifrēšanas principu, to var viegli uzlauzt. To var izdarīt, ja atslēgu izveidošanai tika izmantoti mazi skaitļi, atslēgu var atklāt, vienkārši atlasot vienkāršus veselus skaitļus.

Pati RSA šifrēšana ir algoritms, kas novērš nejaušus komponentus, kas ļauj datortīklu krāpniekiem vieglāk uzlauzt deterministisko mehānismu, saskaņojot to ar Dos uzbrukumu atklāto tekstu, kas pārbauda, ​​vai palaistajiem tekstiem ir pastāvīgi vienāds garums ar ģenerētajām atslēgām.

Un tas, pirmkārt, izskaidro, ka RSA šifrēšana nav tā pati kriptosistēma, kas visos aspektos ir droša elektronisko datu saglabāšanai no nevēlamu personu uzbrukumiem. Ja vien tas netiek pievienots progresīvākiem serveriem, tas iegūst šādus rekvizītus.

Papildu komponenti, kas nodrošina RSA šifrēšanas lietošanas drošību

Lai novērstu iespēju uzlauzt RSA formāta šifrēšanu, programmētāji tajā iestrādā strukturētu, tā saukto randomizēto aizpildīšanas veidu, kas tiek darīts pirms faktiskās elektroniskās informācijas šifrēšanas. Šis punkts garantē, ka elektronisko dokumentu saturs netiks parādīts visiem un konfidenciāla informācija nevar tikt apskatīta, ja dokumentiem tiek piemērots nejaušas atslēgu atlases mehānisms.

RSA šifrēšana sadala matemātiskos skaitļus faktoros, taču mehānisms nekad nav ticis pilnveidots. Tāpēc šobrīd uzbrucējiem joprojām ir iespēja un daudzas nepilnības izvēlēties metodes datu šifrēšanas pārtraukšanai. Un viņiem tas izdodas precīzi, izmantojot galveno faktoru atjaunošanas mehānismu.

Krāpnieki aprēķina publiskajā atslēgā ietverto slepeno indikatoru un atšifrē dokumentāciju, izmantojot standarta metodi. Tātad darbības lauks tiem, kas patiešām vēlas kaitēt uzņēmumam, ir ievērojami liels. Teiksim tā, ka RSA šifrēšanas drošības problēma joprojām ir aktuāla un atklāta, lai gan reti kurš par to runā publiski.

Automatizēts elektronisko datu šifrēšanas process

Neskatoties uz zemo drošības pakāpi, attiecīgā RSA šifrēšana ir piemērojama daudzās nozarēs. Tas ir īpaši apsveicami, ja ir liela elektroniskās dokumentācijas aprite. Pieņemsim, ka RSA šifrēšana tiek izmantota, lai aizsargātu dokumentus vidējā atbildības līmenī.

Yafu programmatūra ļauj automātiski šifrēt elektroniskos datus. Šī programma ļauj ātri atrast datus asimetrisko atslēgu izveidei, ievērojot faktoringa uzticamības noteikumus. Tas ir savietojams ar tādiem procesoriem kā SIQS, ECM, SNFS. Tas tiek palaists, izmantojot komandrindu. Šīs komandas ievadīšana rindā ļauj vairākas reizes samazināt laiku, kas nepieciešams datu meklēšanai, lai izveidotu atslēgas.

Vidējais personālo datoru iekārtu lietotājs nevar tikt galā ar šo programmatūru. Tā uzstādīšana un konfigurēšana prasa zināmas zināšanas, un to bieži veic IT programmētāji un speciālisti.

RSA šifrēšana ir ļoti neaizsargāta, un tas neskatoties uz to, ka publisko un privāto atslēgu izveidošanai tiek izmantoti lieli skaitļi, kuru apjoms ir vairāki tūkstoši bitu diskos.

Bendžamins Mūdijs 2009. gadā pierādīja, ka publisko un privāto atslēgu uzlaušanas process ir iespējams. Lai gan tas var aizņemt divus vai vairāk gadus, joprojām pastāv fakts, ka daudzas pasaules datorsistēmas var tikt uzlauztas.

Piemēram, šim speciālistam nebija vajadzīgs nekas īpašs, lai izsijātu atslēgu skriptus - parastā lietotāja datoru un GGNFS programmatūru. Pat vairāku tūkstošdaļu bitu šifrēšanas atslēgu prakse nepasargā informāciju no tā, ka lauks tiek atstāts konfidenciāls un citiem lietotājiem nepieejams.

Protams, RSA šifrēšanas pārtraukšana prasa laiku. Daudzi hakeri pavada gadus, lai sasniegtu pozitīvu rezultātu. Tās bieži vien ir labi apmaksātas perspektīvas, kas veicina interesi turpināt meklēt īsto atslēgu. Vairumā gadījumu no garo taustiņu uzlaušanas tiek atteikties, meklējot vienkāršākas perspektīvas. Bet tas nenozīmē, ka neviens nemēģina izveidot vienkāršotu atslēgu uzlaušanas mehānismu.

Galvenā aizsardzība pret uzmācīgiem krāpnieku uzbrukumiem ir lielu un garu vairāk nekā divu tūkstošu bitu atslēgu izveide. Jau ir zināmi gadījumi, kad uzlaušanas atslēgas svārstās no simts līdz piecsimt bitiem. Tāpēc jums ir jāsaglabā asas ausis. Ja ir īso taustiņu uzlaušanas mehānisms, iespējams, kaut kur ļaundaru pusē darbs rit pilnā sparā, lai uzlauztu garākās elektroniskās datu šifrēšanas kombinācijas.

Secinājums

Pamatojoties uz iepriekš minēto, RSA šifrēšana ir droša metode elektronisko datu konfidencialitātes saglabāšanai, ja tiek izveidotas garas un ar informāciju bagātas atslēgas.

Manuāli tos atlasīt ir grūti, tāpēc tiek izmantots automatizēts programmatūras produkts Yafu. To uzstāda un konfigurē IT speciālisti. Ja to darāt pats, var tikt sabojāta datora operētājsistēma.
Šī programmatūra ir paredzēta darbam tandēmā ar modernās paaudzes daudzkodolu datoru procesoriem.

Krāpniecisko uzbrukumu galvenie mērķi ir lieli rūpniecības un finanšu uzņēmumi, tāpēc bez RSA šifrēšanas to elektroniskā dokumentu pārvaldība nedarbojas. Arī dokumentu elektroniskais paraksts ir pakļauts šifrēšanai, un uz to attiecas tie paši drošības standarti kā uz citiem informācijas datiem. Principam – jo lielāka atslēga, jo grūtāk ir uzlauzt dokumentu – būtu jāattiecina uz absolūti visiem datiem, kas nav paredzēti publiskai lietošanai.

RSA šifrēšana ir viena no pirmajām praktiskajām publiskās atslēgas kriptosistēmām un tiek plaši izmantota drošai datu pārraidei. Tā galvenā atšķirība no līdzīgiem pakalpojumiem ir tā, ka šifrēšanas atslēga ir publiska un atšķiras no atšifrēšanas atslēgas, kas tiek turēta slepenībā. RSA tehnoloģija ir balstīta uz praktiskām grūtībām, kas saistītas ar divu lielu pirmskaitļu faktorinēšanu (faktoringa problēma).

Radīšanas vēsture

Nosaukums RSA sastāv no Rivest, Shamir un Adleman uzvārdu sākuma burtiem, zinātnieku, kuri pirmo reizi tos publiski aprakstīja 1977. gadā. Klifords Kokss, angļu matemātiķis, kurš strādāja Lielbritānijas izlūkdienestos, pirmo reizi līdzvērtīgu sistēmu izstrādāja 1973. gadā, taču tā tika deklasificēta tikai 1997. gadā.

RSA lietotājs izveido un pēc tam publicē publisko atslēgu, kuras pamatā ir divi lieli pirmskaitļi kopā ar palīgvērtību. jātur noslēpumā. Ikviens var izmantot publisko atslēgu, lai šifrētu ziņojumu, bet, ja tā ir pietiekami liela, tad ziņojumu var atšifrēt tikai kāds, kurš zina pirmskaitļus. Ir zināms, ka RSA šifrēšanas pārtraukšana ir liela problēma: šodien notiek atklātas debates par šī mehānisma drošumu.

RSA ir salīdzinoši lēns algoritms, tāpēc tiešais lietotājs to plaši neizmanto. Visbiežāk izmanto šo metodi, lai pārsūtītu šifrētas koplietotās atslēgas simetriskai šifrēšanas atslēgai, kas savukārt var veikt lielapjoma šifrēšanas un atšifrēšanas darbības ar daudz lielāku ātrumu.

Kad kriptosistēma parādījās tās modernajā formā?

Asimetrisko atslēgu kriptosistēmas ideja tiek piedēvēta Difijam un Helmanam, kuri šo koncepciju publicēja 1976. gadā, ieviešot digitālos parakstus un mēģinot pielietot skaitļu teoriju. To formulējumā tiek izmantota koplietota slepenā atslēga, kas izveidota no kāda skaitļa eksponenta, kas modulo pirmo skaitli. Taču viņi atstāja atklātu šīs funkcijas īstenošanas problēmu, jo faktoringa principi tolaik nebija labi saprotami.

Rivest, Adi Shamir un Adleman no MIT gada laikā veica vairākus mēģinājumus izveidot vienvirziena funkciju, kuru ir grūti atšifrēt. Rivests un Šamirs (kā datorzinātnieki) ierosināja daudzas iespējamās funkcijas, savukārt Adlemans (kā matemātiķis) meklēja algoritma vājās vietas. Viņi izmantoja daudzas pieejas un galu galā 1977. gada aprīlī izstrādāja galīgo sistēmu, kas šodien pazīstama kā RSA.

Digitālais paraksts un publiskā atslēga

Elektroniskais ciparparaksts jeb EDS ir elektronisko dokumentu neatņemama sastāvdaļa. To veido noteiktas kriptogrāfiskas izmaiņas datos. Izmantojot šo atribūtu, ir iespējams pārbaudīt dokumenta integritāti, tā konfidencialitāti, kā arī noteikt, kas ir tā īpašnieks. Būtībā šī ir alternatīva parastajam standarta parakstam.

Šī kriptosistēma (RSA šifrēšana) piedāvā publisko atslēgu, kas to atšķir no simetriskajām. Tās darbības princips ir tāds, ka tiek izmantotas divas dažādas atslēgas - privātā (šifrētā) un publiskā. Pirmais tiek izmantots, lai ģenerētu elektronisko parakstu un pēc tam varētu atšifrēt tekstu. Otrais ir paredzēts digitālā paraksta faktiskajai šifrēšanai un pārbaudei.

Paraksta izmantošana ļauj labāk izprast RSA šifrēšanu, kuras piemēru var sniegt kā parastu klasificētu dokumentu, kas ir “slēgts no ziņkārīgo acīm”.

Kāda ir algoritma būtība?

RSA algoritms sastāv no četriem posmiem: atslēgu ģenerēšana, atslēgu izplatīšana, šifrēšana un atšifrēšana. Kā jau minēts, RSA šifrēšana ietver publisko atslēgu un privāto atslēgu. Open var būt zināms visiem un tiek izmantots ziņojumu šifrēšanai. Tās būtība ir tāda, ka ziņojumus, kas šifrēti, izmantojot publisko atslēgu, var atšifrēt tikai noteiktā laika periodā, izmantojot privāto atslēgu.

Lai būtu droši, veseli skaitļi ir jāatlasa nejauši, un tiem jābūt vienāda izmēra, taču tiem ir jāatšķiras garumā par dažiem cipariem, lai faktorings būtu grūtāks. Identiskus skaitļus var efektīvi atrast, izmantojot to primāruma pārbaudi, tāpēc informācijas šifrēšanai noteikti jākļūst sarežģītākai.

Publiskā atslēga sastāv no moduļa un publiskā eksponenta. Privātais sastāv no moduļa un privātā indikatora, kas jātur noslēpumā.

RSA failu šifrēšana un trūkumi

Tomēr ir vairāki mehānismi vienkāršas RSA pārtraukšanai. Šifrējot ar zemu ātrumu un maziem skaitļiem, šifru var viegli uzlauzt, ja atrodat šifrētā teksta sakni virs veseliem skaitļiem.

Tā kā RSA šifrēšana ir deterministisks algoritms (t.i., tai nav nejauša komponenta), uzbrucējs var veiksmīgi uzsākt izvēlētu vienkārša teksta uzbrukumu kriptosistēmai, šifrējot ticamus vienkāršus tekstus ar publisko atslēgu un pārbaudot, vai tie ir vienādi ar šifrēto tekstu. Tiek uzskatīts, ka kriptosistēma ir semantiski droša, ja uzbrucējs nevar atšķirt divus šifrējumus vienu no otra, pat ja viņš zina atbilstošos tekstus notīrītā formā. Kā aprakstīts iepriekš, RSA, nepapildinot to ar citiem pakalpojumiem, nav semantiski droša.

Papildu šifrēšanas un drošības algoritmi

Lai izvairītos no iepriekš minētajām problēmām, RSA praktiskās ieviešanas parasti pirms šifrēšanas veido kādu strukturētu, nejaušinātu pildījumu. Tas nodrošina, ka saturs neietilpst nedrošā vienkāršā teksta diapazonā un ka ziņojumu nevar nejauši apdraudēt.

RSA kriptosistēmas drošības un informācijas šifrēšanas pamatā ir divas matemātiskas problēmas: lielu skaitļu faktoringa problēma un pati RSA problēma. Pilnīga šifrēta teksta un digitālā paraksta izpaušana RSA tiek uzskatīta par nepieņemamu, pieņemot, ka abas šīs problēmas nevar atrisināt kopā.

Tomēr, pateicoties spējai atgūt galvenos faktorus, uzbrucējs var aprēķināt slepeno eksponentu no publiskās atslēgas un pēc tam atšifrēt tekstu, izmantojot standarta procedūru. Lai gan mūsdienās nav atrasta neviena esoša metode lielu skaitļu faktorinēšanai klasiskajā datorā, nav pierādīts, ka tā neeksistē.

Automatizācija

Lai racionalizētu šo procesu, var izmantot rīku Yafu. Automatizācija YAFU ir vismodernākā funkcija, kas apvieno faktorizēšanas algoritmus inteliģentā un adaptīvā metodoloģijā, kas samazina laiku, lai atrastu patvaļīgu ievades skaitļu faktorus. Lielākajai daļai algoritma implementāciju ir vairāki pavedieni, kas ļauj Yafu pilnībā izmantot vairāku vai daudzu (tostarp SNFS, SIQS un ECM) priekšrocības. Pirmkārt, tas ir pārvaldīts komandrindas rīks. Laiku, kas pavadīts, meklējot šifrēšanas faktoru, izmantojot Yafu parastā datorā, var samazināt līdz 103,1746 sekundēm. Šis rīks nodrošina apstrādes jaudu 320 bitu vai vairāk. Šī ir ļoti sarežģīta programmatūra, kuras instalēšanai un konfigurēšanai ir nepieciešamas noteiktas tehniskās prasmes. Tādējādi RSA C šifrēšana var būt neaizsargāta.

Datorurķēšanas mēģinājumi mūsdienās

2009. gadā Bendžamins Mūdijs, izmantojot RSA-512 bitu atslēgu, strādāja, lai atšifrētu kriptotekstu 73 dienas, izmantojot tikai parastu programmatūru (GGNFS) un vidējo galddatoru (divkodolu Athlon64 ar 1900 MHz). Kā parādīja šī pieredze, “sijāšanas” procesam bija nepieciešami nedaudz mazāk par 5 gigabaiti diska un aptuveni 2,5 gigabaiti RAM.

2010. gadā lielākais faktorētais RSA numurs bija 768 bitus garš (232 cipari aiz komata jeb RSA-768). Tās izvietošana ilga divus gadus vairākos simtos datoru vienlaikus.

Praksē RSA atslēgas ir garākas – parasti no 1024 līdz 4096 bitiem. Daži eksperti uzskata, ka 1024 bitu atslēgas tuvākajā nākotnē var kļūt nedrošas vai pat jau var tikt uzlauztas ar pietiekami labi finansētu uzbrucēju. Tomēr daži iebilst, ka 4096 bitu atslēgas var tikt atklātas arī pārskatāmā nākotnē.

Izredzes

Tāpēc parasti tiek pieņemts, ka RSA ir droša, ja skaitļi ir pietiekami lieli. Ja bāzes skaitlis ir 300 biti vai mazāks, šifrēto tekstu un ciparparakstu var sadalīt dažu stundu laikā personālajā datorā, izmantojot programmatūru, kas jau ir brīvi pieejama. 512 bitu atslēgas tika uzlauztas jau 1999. gadā, izmantojot vairākus simtus datoru. Mūsdienās tas ir iespējams dažu nedēļu laikā, izmantojot publiski pieejamu aparatūru. Tādējādi ir pilnīgi iespējams, ka nākotnē RSA šifrēšana tiks viegli uzlauzta uz pirkstiem, un sistēma kļūs bezcerīgi novecojusi.

Oficiāli 2003. gadā tika apšaubīta 1024 bitu atslēgu drošība. Pašlaik ieteicams būt vismaz 2048 bitu garš.

Zem griezuma ir “slikto” RSA šifra parametru izvēles piemēri.

“Jāuzsver, ka, izvēloties RSA moduli (numurs n) katram tīkla korespondentam. Šajā sakarā var teikt sekojošo. Lasītājs to var patstāvīgi pārbaudīt, zinot vienu no trim daudzumiem lpp, q vai φ(n), jūs varat viegli atrast RSA privāto atslēgu...".

Papildināsim šo tekstu. Ja RSA šifrēšanas moduļa izvēle ir neveiksmīga, kā tas tika darīts tālāk sniegtajā rokasgrāmatas piemērā, varat atšifrēt tekstu bez slepenās atslēgas klātbūtnes, t.i. nezinot nevienu no trim nosauktajiem daudzumiem.

Lai to izdarītu, pietiek ar šifrēšanas moduļa norādīto šifrēto tekstu n, publiskā atslēga ešifrēt un veikt tikai trīs bezatslēgas lasīšanas uzbrukuma darbības. Pēc ceturtā uzbrukuma posma tiek konstatēts, ka avota teksts tika iegūts iepriekšējā solī un ir lasāms. Parādīsim, cik viegli to izdarīt.

Vispirms sniegsim pašu piemēru no minētās rokasgrāmatas 313.-315. lpp.

Piemērs

Šifrēšanaīsa sākotnējā īsziņa: RSA.
Saņēmējs iestata šifru ar īpašībām n=pq=527, Kur p=17, q=31 Un φ(n)=(р –1)(q – 1)=480. Kā publiskā atslēga e tiek izvēlēts skaitlis, kas ir pirmais φ(n), e=7. Šim skaitlim tiek atrasti veseli skaitļi, izmantojot paplašināto Eiklīda algoritmu u Un v, apmierinot attiecības e∙u+φ(n)∙v=1:

480=7∙68+4,
7=4∙1+3,
4=3∙1+1,
1=4–3∙1=4–(7–4∙1)∙1=4∙2–7∙1=(480–7∙68)∙2–7∙1=480∙2–7∙137,
v=2, u=–137.

Tāpēc ka –137≡343 (mod480), Tas d=343.

Pārbaude: 7∙343=2401≡1 (mod480).

Īsziņa tiek parādīta kā ciparu secība, kas ietverta intervālā . Vēstules šim nolūkam R, S Un A tiek kodēti kā piecu bitu bināri skaitļi. Šo burtu sērijas numuri angļu alfabētā tiek izmantoti to binārajā attēlojumā:

R = 18 10 = (10010) 2, S=19 10 = (10011) 2,
A=1 10 = (00001) 2.

Tad RSA=(100101001100001) 2. Sadalot tekstu ierobežota garuma blokos, tiek iegūta divu bloku prezentācija: RSA=(100101001), (100001)=(M 1 = 297, M 2 = 33).

Avota teksta bloki tiek šifrēti secīgi M1 = 297, M2 = 33:
y 1 = E k (M 1) = M 1 e ≡ 297 7 (mod527) = 474.

Šeit mēs izmantojām faktu, ka:

297 7 =((297 2) 3)297≡(mod527)=(200 3 (mod527)297)(mod527)=474,
y 2 = E k (M 2) = M 2 e ≡ 33 7 (mod527) = 407.

Šifrēts teksts, tāpat kā oriģinālais, tiek iegūts divu bloku veidā: y 1 =474; y 2 =407.

Dekodēšanašķiet, ka tā ir darbību secība D k (y i) = (y i) d = (y i) 343 (mod 527), i=1,2.

Eksponentācijas aprēķini d to ir ērtāk veikt, vispirms attēlojot eksponentu kā skaitļa pakāpju summu 2 , proti: 343=256+64+16+4+2+1 .

Izmantojot šo eksponentu attēlojumu d=343, mēs iegūstam:

474 2 ≡174 (mod527),
474 4 ≡237 (mod527),
474 8 ≡307 (mod527),
474 16 ≡443 (mod527),
474 32 ≡205 (mod527),
474 64 ≡392 (mod527),
474 128 ≡307 (mod527),
474 256 ≡443 (mod527),
un visbeidzot 474 343 (mod527)=(443∙392∙443∙237∙174∙474) (mod527)=297.

Vērtība tiek aprēķināta līdzīgi 407 343 (mod527)=33.

Pārslēgšanās uz atšifrētā ziņojuma burtisku attēlojumu dod: RSA.

Pēc piemēra apskatīšanas rokasgrāmatā ir apskatīta RSA sistēmas robustums. Tiek uzsvērta nepieciešamība ievērot piesardzību, izvēloties RSA šifra moduli (skaitļus). n) katram tīkla korespondentam. Tiek norādīts, ka nav pieļaujams ignorēt prasības attiecībā uz izvēlētajiem šifrēšanas sistēmas raksturlielumiem. Starp šīm prasībām, kuru pārkāpums ir ilustrēts ar sniegto piemēru, diemžēl nav norādīts.

Uzbrukums RSA šifram

Apskatīsim piemēru uzbrukumam RSA šifram. Izmantosim datus no A.P. mācību grāmatas “Kriptogrāfijas pamati” 313.-315.lpp. Alferovs, A.Ju. Zubovs, A.S. Kuzmins, A.V. Čeremuškins, Maskava. "Helios ARV", 2001.

Šajā piemērā atlasīto sistēmas parametru kļūme (nepieļaujamība) ir viegli parādīta ar aprēķiniem, kas īsteno uzbrukumu bezatslēgai avota teksta lasīšanai. Šāda uzbrukuma būtība ir šāda. RSA šifra publiskā atslēga ir norādīta ( e=7, n=527) un šifrētu tekstu. Piemērā šifrētais teksts ir attēlots divos blokos
y=(y 1 = 474, y 2 = 407).

Katram šifrētajam blokam uzbrūk atsevišķi, vispirms mēs uzbrūkam y 1 =474, pēc tā atšifrēšanas mēs uzbrūkam citam blokam y 2 =407.

Tālāk tiek veidota skaitlisko vērtību secība, atkārtoti šifrējot, saglabājot divu secīgu uzbrukuma algoritma darbību rezultātus un izmantojot publisko atslēgu. y i, y 1 = y pieejams šifrēts teksts.

Šifrēta teksta uzbrukuma algoritmā tiek noteikts šāds soļa numurs: j, par kuru y i e j (mod n)=(y i e j–1 (mod n)) e (mod n)=y i, i>1. No pēdējās attiecības mēs to redzam, kad tas tiek pacelts uz spēku e vērtības (y i e j–1 (mod n)) tiek iegūts sākotnējais šifrētais teksts y i = y 1.

Bet tas nozīmē, ka šajā solī vienkāršais teksts tika šifrēts. Veicot tiešus aprēķinus (to ir ļoti maz), izmantojot ekrāna kalkulatoru, mēs atrodam šo vērtību j, kurā šifrēšanas cikls beidzas ar vērtību y 1, no kura sākās cikls.

Uzbrukums pirmajam blokam y 1 =474šifrēts teksts.
1. darbība:  474 7 (mod527)=382;
2. darbība:  382 7 (mod527)=423;
3. darbība:  423 7 (mod527)=297;
4. darbība:   šajā darbībā jau atrastais avota teksts tiek šifrēts, taču tas ir jādara, jo uzbrucējs nezina avota tekstu. Uzbrukuma pabeigšanas pazīme ir sākotnējās šifrētā teksta vērtības sakritība ( 474 ) un 4. šifrēšanas soļa rezultāts. Tā ir tieši tā sakritība, kas notiek.

297 7 (mod527) = 474 saņēma sākotnējo (pirmo) šifrētā teksta bloku. Uzbrukums pirmajam blokam tika pabeigts veiksmīgi y 1 =474. Iepriekšējais 3. darbības rezultāts ir vienāds ar vienkāršu tekstu M1 = 297.

n=527 r=297 modulo n=527. Tas ir rakstīts šādi y i = y 1 = 297. Spēka atlikumu veidošana
(((297 7 (mod527)) 7 (mod527)) 7 (mod527)) 7 = 297.

Uzbrukums otrajam blokam y 2 =407šifrēts teksts.
1. darbība:  407 7 (mod527)=16;
2. darbība:  16 7 (mod527)=101;
3. darbība:  101 7 (mod527)=33;
4. darbība:  33 7 (mod527)=407.

Trešajā solī atkal tika iegūts avota teksta bloks ( M2 = 33), taču uzbrucējs to nezina un veic nākamo (ceturto soli), kura rezultāts ir ( 407 ) atbilst sākotnējam šifrētajam tekstam y 2 =407.

Būtībā modulo atlikumu gredzenā n=527 tika ieviests īss atskaitījumu apstrādes cikls r=33 modulo n=527. Tas ir rakstīts šādi y i = y 2 =33.
Spēka atlikumu veidošana ((33 7 (mod527)) 7 (mod527)) 7 (mod527) = 33.

Uzbrukuma rezultāts (avota teksts M1 = 297, M2 = 33) tiek iegūts, trīs reizes šifrējot doto šifrēto tekstu. Grūti iedomāties lielākus panākumus šifrētā teksta uzbrucējam.

Turpinot diskusiju par moduļa un citu šifra parametru izvēli, varam piebilst, ka šifrēšanas modulis ( n=527) dažus avota tekstus vispār nevar šifrēt. Šajā gadījumā publiskās atslēgas vērtības izvēlei nav lielas nozīmes. Ir avota teksta vērtības, kuras parasti nav iespējams šifrēt ar atlasīto šifru ar moduli n=527.

Neviens no dotajiem nevar šifrēt avota tekstus, kas attēloti ar cipariem
187 , 341 , 154 Un 373 .

Piemērs (nespēja šifrēt dažu avota tekstu vērtības)

Ļaujiet avota tekstiem attēlot četrus blokus y=(y 1 = 154, y 2 = 187, y 3 = 341, y 4 = 373). Izstādes dalībnieks ešifra publiskā atslēga var būt jebkurš kopskaitlis ar Eilera funkciju φ(n)=φ(527)=480. Tomēr izskatāmajā gadījumā publiskā atslēga e var iestatīt patvaļīgi. Patiešām, ļaujiet e=2, 4, 7, 9, 17, 111 Pēc tam:

154 2 (mod527)=1;
154 4 (mod527)=1;
154 7 (mod527)=154;
154 9 (mod527)=154;
154 17 (mod527)=154;
154 111 (mod527)=154;
187 2 (mod527)=187;
187 4 (mod527)=187;
187 7 (mod527)=187;
187 9 (mod527)=187;
187 17 (mod527)=187;
187 111 (mod527)=187;
341 2 (mod527)=341;
341 4 (mod527)=1;
341 7 (mod527)=341;
341 9 (mod527)=341;
341 17 (mod527)=341;
341 111 (mod527)=341;
373 2 (mod527)=1;
373 4 (mod527)=373;
373 7 (mod527)=373;
373 9 (mod527)=373;
373 17 (mod527)=373;
373 111 (mod527)=373.

No aplūkotā piemēra izriet vienkāršs secinājums. Patiešām, šifrēšanas procesa parametru izvēle ir jāpieiet ļoti uzmanīgi un jāveic rūpīga šādu parametru iepriekšēja analīze. Kā to izdarīt, ir atsevišķs jautājums, un tas nav aplūkots šī darba ietvaros.

Visbeidzot, ir pienācis laiks sākt RSA kriptosistēmas aprakstu. Papildus paskaidrojumam, kā tas darbojas, mums ir detalizēti jāapspriež tā drošība; citiem vārdiem sakot, kāpēc ir tik grūti izjaukt ziņojumu, kas šifrēts ar RSA kriptosistēmas palīdzību?

12.1. §. Par sākumu un beigām

Lai ieviestu viena lietotāja RSA šifrēšanas sistēmu, ir jāizvēlas divi dažādi pirmskaitļi p un q un jāaprēķina to reizinājums, kamēr skaitlis kļūst par publiskās atslēgas daļu. 12.5. paragrāfā mēs detalizēti apspriežam atslēgu pirmskaitļu atlases metodi un to, kā šī izvēle ir saistīta ar sistēmas uzticamību.

Ziņojums (ko var uzskatīt par veselu skaitli) tiek šifrēts, paaugstinot to uz kādu jaudas moduli. Tāpēc vispirms ir jāatrod veids, kā attēlot ziņojuma tekstu kā moduļu klašu sarakstu šifrēšanas procesu, bet tikai sagatavo ziņojumu, lai to varētu šifrēt.

Vienkāršības labad pieņemsim, ka ziņojuma tekstā ir tikai vārdi, kas rakstīti ar lielajiem burtiem. Tātad ziņojums galu galā ir burtu un atstarpju secība. Pirmais solis ir aizstāt katru ziņojuma burtu ar ciparu, kas ir atlasīts no šīs tabulas:

(skatīt skenēšanu)

Atstarpe starp vārdiem tiek aizstāta ar skaitli 99. Veicot šo procedūru, mēs iegūsim skaitli, iespējams, ļoti lielu, ja ziņojums ir garš. Tomēr tas nav galīgais skaitlis, uz kuru mēs tiecamies, bet gan tikai moduļu klašu kopums. Un tagad mums ir jāsadala ziņojuma skaitliskais attēlojums gabalos, no kuriem katrs ir naturāls skaitlis, kas nepārsniedz Šos gabalus parasti sauc. ziņojumu bloki.

Piemēram, moto “IZZINI SEVI” skaitliskais attēlojums izskatās šādi:

Izvēloties vienkāršus, iegūstam reizinājumu, tāpēc iepriekš izrakstītā ziņojuma skaitliskais attēlojums ir jāsadala blokos, kas ir mazāki par 23 393.

Protams, bloku izvēle nav viennozīmīga, taču arī tā nav gluži patvaļīga. Piemēram, lai izvairītos no neskaidrībām uz skatuves

atšifrēšanai nevajadzētu izcelt blokus, kas sākas ar nulli.

Atšifrējot ziņojumu, kas šifrēts ar RSA šifrēšanas sistēmu, tiek iegūta bloku secība. Pēc tam tie tiek savienoti kopā, lai izveidotu ziņojuma skaitlisku attēlojumu. Un tikai pēc ciparu aizstāšanas ar burtiem saskaņā ar augstāk esošo tabulu būs iespējams izlasīt sākotnējo ziņojumu.

Lūdzu, ņemiet vērā, ka katrs burts tabulā ir kodēts ar divciparu skaitli. Tas tiek darīts, lai novērstu neskaidrības. Pieņemsim, ka mēs numurējām burtus secībā, sākot ar 1, t.i. A atbilst 1, B atbilst 2 un tā tālāk. Šajā gadījumā mēs nevarēsim precīzi pateikt, vai 12. bloks apzīmē burtu pāri vai tikai vienu burtu, alfabēta divpadsmito burtu. Protams, ziņojuma skaitliskai attēlošanai var izmantot jebkuru burtu un ciparu atbilstību viens pret vienu, piemēram, -kodējumu, kurā ziņojuma tulkošanu digitālā formā automātiski veic dators.

12.2. §. Šifrēšana un atšifrēšana

Ziņojums, kas sagatavots šifrēšanai, izmantojot 12.1. paragrāfa metodi, sastāv no bloku secības, no kuriem katrs ir par skaitli mazāks nekā Tagad apspriedīsim, kā katrs bloks tiek šifrēts. Lai to izdarītu, mums ir nepieciešams skaitlis, kas vienāds ar pirmskaitļu un naturāla skaitļa reizinājumu, modulo invertible, t.i. numurs, kas atbilst nosacījumam

Atcerēsimies, ka no zināmajiem p un q skaitli var viegli aprēķināt. Tiešām,

Pāris tiek saukts par mūsu aprakstītās RSA kriptosistēmas publisko jeb kodēšanas atslēgu. Ļaujiet ziņojuma blokam, tas ir, veselam skaitlim, kas apmierina nevienlīdzību. Mēs izmantosim simbolu, lai apzīmētu šifrētā ziņojuma bloku, kas atbilst To aprēķina saskaņā ar šādu noteikumu:

Ņemiet vērā, ka katrs ziņojumu bloks tiek šifrēts atsevišķi. Tāpēc šifrēts ziņojums faktiski sastāv no atsevišķiem šifrētiem blokiem. Turklāt mēs nevaram apvienot šos blokus vienā lielā skaitā, jo tas padarīs neiespējamu ziņojuma atšifrēšanu. Mēs drīz redzēsim iemeslu tam.

Atgriezīsimies pie piemēra, kuru sākām apsvērt pirmajā rindkopā. Mēs esam noteikuši tā, ka Tagad mums ir jāizvēlas skaitlis Atgādināt, ka tam jābūt pirmskaitļa skaitlim ar Mazākais pirmskaitlis, kas nedala 23088, ir vienāds ar 5. Iestatīsim Lai kodētu pirmo ziņojuma bloku no § 12.1, mums ir Lai noteiktu skaitļa 25245 atņemšanu modulo 23393. Izmantojot simbolisko aprēķinu programmu (vai kalkulatoru, ja jums ir pacietība), mēs iegūstam, ka nepieciešamais atskaitījums ir 22 752. Tātad šifrētais ziņojums tiek attēlots ar sekojošu bloku secību :

Apskatīsim, kā tiek atšifrēti šifrētu ziņojumu bloki. Lai sāktu atšifrēšanu, mums jāzina modulo apgrieztais elements. Pēdējais no tiem ir naturāls skaitlis, ko apzīmēsim ar Pāri sauc par RSA šifrēšanas sistēmas slepeno jeb dekodēšanas atslēgu. Ja a ir šifrēta ziņojuma bloks, tad tam atbilstošā atšifrēšana

Operācijas rezultāts ir:

Pirms atgriešanās pie piemēra, ir nepieciešami daži komentāri. Pirmkārt, to ir ļoti viegli aprēķināt, ja zināt Patiešām, slepenā atslēga tiek noteikta, izmantojot paplašināto Eiklīda algoritmu. Otrkārt, ja bloks ir sākotnējais ziņojums, tad mums ir tiesības sagaidīt vienlīdzību. Citiem vārdiem sakot, atšifrējot šifrēta ziņojuma bloku, mēs ceram noskaidrot oriģinālā ziņojuma atbilstošo bloku. Tas, ka tas tā būs, tieši neizriet no iepriekš aprakstītā algoritma, taču visu sīkāk apspriedīsim nākamajā rindkopā.

Visbeidzot, kā mēs apgalvojām ievadā un visā grāmatā, lai izjauktu RSA kriptosistēmu, tā ir jāfaktorizē, jo jums ir jāzina, kā atšifrēt ziņojumu. Tomēr, kad sistēmas darbība ir sīki aprakstīta, tas ir skaidrs pēdējais apgalvojums nav gluži precīzs. Lai nolasītu šifrēšanu, papildus pašam elementam ir jāzina tikai elementa modulo inverss. Tāpēc, lai uzlauztu sistēmu, pietiek aprēķināt ar zināmu. Izrādās, ka šis aprēķins ir līdzvērtīgs skaitļa faktorinēšanai. , kā redzēsim 12.4. §.

Apspriežamajā piemērā mēs izmantojam paplašināto Eiklīda algoritmu skaitļiem un 5, lai noteiktu.

(skatīt skenēšanu)

Tādējādi 5 moduļa apgrieztā vērtība būtu -9235 un

Mazākais naturālais skaitlis, kas salīdzināms ar -9235 modulo Tātad, lai atšifrētu šifrēta ziņojuma bloku, mums tas jāpalielina līdz 13 853 modulo 23 393. Mūsu piemērā pirmais kodētais bloks ir 22 752 75213853 modulo 23,393 , mēs saņemam Ņemiet vērā, ka pat ar tik maziem skaitļiem prasības RSA kriptosistēmas darbībai pārsniedz vairuma kabatas kalkulatoru iespējas.

12.3.§. Kāpēc tas darbojas?

Kā jau minēts iepriekš, iepriekš aprakstītās darbības noved pie funkcionējošas kriptosistēmas tikai tad, ja katra šifrētā ziņojuma bloka dekodēšana atjaunos atbilstošo sākotnējā bloka bloku. Pieņemsim, ka mums ir darīšana ar RSA sistēmu, kurai ir publiskā un privātā atslēga Izmantojot 12.2. punktu, mums jāparāda, ka jebkuram veselam skaitlim, kas atbilst nevienlīdzībai, ir spēkā identitāte.

Patiesībā pietiek ar to pierādīt

Patiešām, gan 6, gan nenegatīvi veseli skaitļi ir mazāki, tāpēc tie ir salīdzināmi absolūtā vērtībā tad un tikai tad, ja tie ir vienādi. Tas jo īpaši izskaidro, kāpēc mēs sadalām ziņojuma skaitlisko attēlojumu mazākos blokos. Turklāt no tā var redzēt, ka bloki

Kodētais ziņojums ir jāpieraksta atsevišķi: pretējā gadījumā mūsu argumentācija nedarbosies.

No šifrēšanas un atšifrēšanas receptēm izriet, ka

Tā kā elementi ir savstarpēji apgriezti modulī, ir tāds naturāls k, ka pēc nosacījuma skaitļi ir lielāki. Tāpēc, aizstājot reizinājumu vienādojumā (3.1), mēs iegūstam

Tagad izmantosim Eilera teorēmu, kas nosaka, ka Hence, t.i.

un mēs būtu pilnībā ieguvuši pierādījumu, ja tajā nebūtu iezagusies neliela kļūda.

Ja vēlreiz rūpīgi pārskatīsit mūsu argumentāciju, jūs pamanīsit, ka mēs neņēmām vērā Eilera teorēmas nosacījumus. Faktiski pirms teorēmas piemērošanas ir jāpārliecinās, ka skaitļi ir savstarpēji pirmizrādes Tas, šķiet, ir jāuzrauga, gatavojot ziņojumu šifrēšanai, t.i. Sadalot ziņojuma skaitlisko attēlojumu blokos, jums jāpārliecinās, ka visi iegūtie bloki ir vienādi, par laimi, tas nav nepieciešams, jo faktiski salīdzinājums tiek veikts jebkuram blokam. Un kļūda slēpjas nevis rezultātā, ko mēs gribam pierādīt, bet tikai pašā pierādījumā. Pareizā pieeja ir balstīta uz argumentāciju, kas izmantota Korcelta teorēmas pierādījumā 7. nodaļā.

Atcerieties, ka kur ir dažādi pirmskaitļi. Definēsim skaitļa atlikumus modulo Since

aprēķini abiem pirmskaitļiem ir līdzīgi, mēs to izskatīsim tikai sīkāk

kādam veselam skaitlim Tāpēc

Mēs tagad vēlētos piemērot Fermā teorēmu, bet mums ir tiesības to darīt tikai tad, ja tā nedala Lai šī prasība tiktu izpildīta. Tad mēs to saņemam

Aizstājot Fermā teorēmu ar Eilera teorēmu, mēs neatrisinājām radušos problēmu: salīdzinājums ir derīgs tikai dažiem, bet ne visiem blokiem. Tomēr tagad bloki, kuriem argumentācija nedarbojas, ir jāsadala ar Tālāk, ja tas dala, tad abi ir 6 un ir salīdzināmi ar 0 pēc moduļa un tāpēc ir salīdzināmi viens ar otru. Tādējādi pierādāmais salīdzinājums ir spēkā arī šajā gadījumā. Tāpēc salīdzinājums ir patiess jebkuram veselam skaitlim. varēja izmantot līdzīgu argumentāciju, piemērojot Eilera teorēmu Patiešām, nevienlīdzība nenozīmē salīdzināšanu, jo skaitlis ir salikts.

Tātad, mēs esam pierādījuši, ka salīdzinājums ir līdzīgi pierādīts. Citiem vārdiem sakot, dala gan ar, gan Bet ir atšķirīgi pirmskaitļi, tāpēc lemma no 3.6. paragrāfa mums garantē, ka dala A, jo mums ir jebkurš vesels skaitlis. mēs atzīmējām rindkopas sākumā, tas ir pietiekami, lai pierādītu vienlīdzību, jo abas tās daļas ir nenegatīvi veseli skaitļi, kas ir mazāki par Apkopojot, mēs varam teikt, ka

iepriekšējās rindkopas algoritms noved pie praktiskas kriptosistēmas. Tagad jums jāpārliecinās, vai tas ir uzticams.

12.4.§. Kāpēc sistēma ir uzticama?

Atgādinām, ka RSA ir šifrēšanas sistēma ar publisko atslēgu, kas sastāv no dažādu pirmskaitļu un modulo invertējama naturālā skaitļa reizinājuma. Uzmanīgi apskatīsim, ko var darīt, lai uzlauztu RSA, ja zināms ir tikai pāris

Lai atšifrētu bloku, kas šifrēts ar RSA, mums ir jāzina modulo k apgrieztā vērtība. Problēma ir tāda, ka praktiski vienīgais zināmais veids, kā to izdarīt, ir izmantot paplašināto Eiklīda algoritmu. Tomēr, lai aprēķinātu, izmantojot formulu no 9.4. mums ir jāzina, kas apstiprina sākotnējo apgalvojumu: RSA pārtraukšanai nepieciešama faktorizēšana. Un tā kā sadalīšanās grūtības ir būtiskas, RSA sistēma ir droša.

Var, protams, pieņemt, ka kādreiz kāds atklās algoritmu, kas aprēķina bez informācijas par skaitļa faktoriem Kas, piemēram, notiks, ja kāds izdomās efektīvu veidu, kā noteikt tieši pēc Faktiski tas ir tikai slēpta paplašināšanas metode Precīzāk, ja

ir zināmi, tad mēs varam viegli aprēķināt Patiešām,

tātad ir zināma nepieciešamo pirmskaitļu dalītāju summa. Tālāk,

tāpēc arī atšķirība ir zināma. Tagad, atrisinot vienkāršu lineāro vienādojumu sistēmu, mēs varam viegli atrast faktorizāciju.

Tas nozīmē, ka algoritms, kas aprēķina, faktiski sadala skaitli faktoros, tātad tas ir spalvu putns. Bet vēl ir pāragri nomierināties. Jūs varat iet tālāk savās fantāzijās un pieņemt, ka kāds ir izdomājis algoritmu, kas nosaka tieši pēc Bet Tātad, ja mēs zinām, tad mēs zinām skaitli, kas ir tā daudzkārtnis. Izrādās, ka šāda informācija ir pietiekama dekompozīcijai. Varbūtības algoritmu, kas noved pie šādas sadalīšanās, var atrast V. 7. uzdevums parāda līdzīgu (bet vienkāršāku) sadalīšanas algoritmu, pieņemot, ka Rabin kriptosistēma var tikt salauzta. Tas sniegs jums priekšstatu par varbūtības algoritmu no .

Paliek pēdējā uzlaušanas iespēja: mēģinājums atjaunot bloku tieši ar modulo atlikumu, ja tas ir pietiekami liels, tad sistemātiska visu iespējamo meklēšanas kandidātu meklēšana ir vienīgā izeja. Neviens vēl neko labāku nav izdomājis. Mēs esam uzskaitījuši galvenos argumentus, kas izskaidro, kāpēc RSA kriptosistēmas laušana tiek uzskatīta par līdzvērtīgu faktorizēšanai, lai gan šim apgalvojumam vēl nav stingru pierādījumu.

12.5.§. Izvēloties vienkāršus

No iepriekšējās diskusijas izriet, ka RSA kriptosistēmas drošībai ir svarīgi izvēlēties pareizos pirmskaitļus Protams, ja tie ir mazi, sistēma ir viegli uzlauzta. Tomēr nepietiek ar lielu izvēli Patiešām, pat ja p un q ir milzīgi, bet atšķirība ir maza, to reizinājumu var viegli faktorizēt, izmantojot Fermā algoritmu (sk. § 3.4).

Tā nav tukša runa. 1995. gadā divi studenti no Amerikas universitātes uzlauza RSA publisko versiju. Tas kļuva iespējams, pateicoties sliktai sistēmas galveno faktoru izvēlei.

No otras puses, RSA tiek izmantota jau ilgu laiku, un, rūpīgi izvēloties galvenos faktorus, sistēma faktiski izrādās diezgan uzticama. Tādējādi jebkuram RSA šifrēšanas programmētājam ir nepieciešama efektīva metode veiksmīgai pirmskaitļu izvēlei.

Pieņemsim, ka mēs vēlamies izveidot RSA kriptosistēmu ar publisko atslēgu, kurā veselam skaitlim ir aptuveni cipari. Vispirms izvēlēsimies pirmskaitli, kura rakstzīmju skaits atrodas starp, ņemsim to tuvu Pašlaik personīgai lietošanai ieteicamais atslēgas izmērs ir 768 biti, t.i. jābūt aptuveni 231 cipara garam. Lai izveidotu šādu skaitli, mums ir nepieciešami divi vienkārši, piemēram, 104 un 127 cipari. Lūdzu, ņemiet vērā, ka šādi izvēlētie pirmskaitļi atrodas diezgan tālu viens no otra, t.i. Fermā algoritma izmantošana sadalīšanai šajā situācijā ir nepraktiska. Turklāt mums ir jāpārliecinās, ka skaitļu iekļaušanā primārajos faktoros ir iesaistīti ne tikai mazi, bet arī lieli faktori. Patiešām, pretējā gadījumā skaitlis kļūst par vieglu laupījumu dažiem labi zināmiem sadalīšanas algoritmiem (sk.). Tagad apskatīsim metodi, ar kuras palīdzību tiek atrasti pirmskaitļi, kas atbilst uzskaitītajiem nosacījumiem.

Vispirms mums ir nepieciešams viens vienkāršs rezultāts par pirmskaitļu sadalījumu. Atcerēsimies, kas apzīmē pirmskaitļu skaitu, kas nepārsniedz x. Ņemot vērā pirmskaitļa teorēmu, mēs redzam, ka lielam x skaitlis ir aptuveni vienāds ar kur ir naturālais logaritms

pamatojoties uz (sk. 4.5. punktu). Lai tas būtu ļoti liels, kaut kāds pozitīvs skaitlis. Mēs vēlamies novērtēt pirmskaitļu skaitu, kas atrodas starp, un novērtēt starpību, pateicoties pirmskaitļu teorēmai un logaritma īpašībām, starpība ir aptuveni vienāda ar

Pieņemot, ka tas ir ļoti mazs, mēs varam pieņemt, ka vērtība ir vienāda ar 0, un iegūt saprātīgu starpības aplēsi. Tātad, starp ietverto pirmskaitļu skaits, protams, ir precīzāks, jo lielāks ir un jo mazāks Sīkāku ievadu par šādu tāmi skatīt ([D. 10]).

Pieņemsim, ka mums ir jāizvēlas pirmskaitlis vesela skaitļa x tuvumā. Precizitātes labad mēs pieņemsim, ka x ir kārtībā, un mēs meklējam pirmskaitļu intervālā no x līdz Būtu lietderīgi iepriekš zināt, cik pirmskaitļu ir šajā intervālā. Lai novērtētu pirmskaitļu skaitu, varat izmantot tikko iegūto rezultātu. Mūsu piemērā vērtība ir ļoti maza: tāpēc, izmantojot iepriekš uzrakstīto formulu, mēs secinām, ka intervāls starp ir aptuveni

pirmskaitļi. 11. nodaļas otrās rindkopas beigās mēs formulējām stratēģiju, kas izstrādāta, lai pierādītu dotā nepāra skaitļa būtību. Tā sastāv no trim soļiem.