Rabins kryptosystem
Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 17. august 2021; verifikation kræver 1 redigering .Rabin-kryptosystemet er et kryptografisk system med offentlig nøgle, hvis sikkerhed er sikret af vanskeligheden ved at finde kvadratrødder i ringen af rester modulo et sammensat tal . Systemets sikkerhed, ligesom sikkerheden ved RSA -metoden , skyldes vanskeligheden ved at faktorisere store tal. En krypteret besked kan dekrypteres på 4 måder. Ulempen ved systemet er behovet for at vælge en sand besked blandt 4 mulige.
Historie
I januar 1979 offentliggjorde Michael O. Rabin en beskrivelse af sit system. Det er blevet bevist, at gendannelse af almindelig tekst fra chiffertekst er lige så vanskelig som at faktorisere store tal. Rabins system blev det første asymmetriske kryptosystem, som et sådant bevis blev udført for. Kompleksiteten af genopretning er relateret til vanskeligheden ved at udtrække kvadratroden modulo et sammensat tal N = p · q . Faktoriseringsproblemet og kvadratrodsproblemet er ækvivalente, det vil sige:
- ved at kende primdivisorerne for tallet N , kan du udtrække kvadratrødderne modulo N ;
- ved at udtrække kvadratrødder modulo N , kan man faktorisere N til primfaktorer.
Nøglegenerering
Rabin-systemet, som ethvert asymmetrisk kryptosystem , bruger en offentlig og en privat nøgle. Den offentlige nøgle bruges til at kryptere meddelelser og kan frigives til offentligheden. Den private nøgle er påkrævet til dekryptering og bør kun være kendt af modtagerne af krypterede beskeder.
Nøglegenereringsprocessen er som følger:
- to tilfældige tal p og q er valgt under hensyntagen til følgende krav:
- tallet n = p · q beregnes ;
- tallet n er den offentlige nøgle; tallene p og q er lukkede.
Eksempel. Lad p = 7 og q = 11 . Så er n = p · q = 7 · 11 = 77 . Tallet n = 77 er den offentlige nøgle, og tallene p = 7 og q = 11 er den private nøgle. Modtageren fortæller afsenderne nummeret 77. Afsenderne krypterer beskeden ved hjælp af nummeret 77 og sender den til modtageren. Modtageren dekrypterer beskeden ved hjælp af tallene 7 og 11. De givne nøgler er dårlige til praktisk brug, da tallet 77 let kan dekomponeres i primtal (7 og 11).
Kryptering
Den oprindelige besked m (tekst) er krypteret ved hjælp af den offentlige nøgle - tallet n i henhold til følgende formel:
c = m² mod n .På grund af brugen af modulo multiplikation er Rabin-systemets krypteringshastighed større end krypteringshastigheden for RSA -metoden , selvom der i sidstnævnte tilfælde er valgt en lille eksponentværdi.
Eksempel (fortsat). Lad kildeteksten være m = 20 . Så ville chifferteksten være: c = m² mod n = 20² mod 77 = 400 mod 77 = 15 .
Dekryptering
For at dekryptere beskeden skal du bruge en privat nøgle - tallene p og q . Dekrypteringsprocessen er som følger:
- først, ved hjælp af Euklids algoritme , tal og findes fra ligningen ;
- derefter, ved hjælp af den kinesiske restsætning , beregnes fire tal:
Eksempel (slut). Som et resultat af afkodning får vi: . Vi ser, at en af rødderne er den oprindelige tekst m .
Algoritme-evaluering
Effektivitet
Dechifrering af teksten, ud over den korrekte, fører til yderligere tre falske resultater. Dette er den største ulempe ved Rabins kryptosystem og en af de faktorer, der forhindrede det i at finde bred praktisk brug.
Hvis kildeteksten er en tekstbesked, så er det ikke svært at bestemme den korrekte tekst. Men hvis meddelelsen er en strøm af tilfældige bits (for eksempel for at generere nøgler eller en digital signatur ), bliver det et reelt problem at bestemme den rigtige tekst. En måde at løse dette problem på er at tilføje en kendt header eller en slags etiket til beskeden før kryptering.
Beregningshastighed
Rabin-algoritmen ligner RSA-kodning, men i stedet for at hæve beskeden til magten e , bruger krypteringen operationen med at kvadrere beskedblokken, hvilket positivt påvirker algoritmens hastighed uden at ofre kryptografisk styrke.
Til afkodning anvendes den kinesiske restsætning sammen med to eksponentiationer modulo. Her er effektiviteten sammenlignelig med RSA.
Valg af den ønskede tekst blandt de fire fører til yderligere beregningsomkostninger. Og dette tjente til at sikre, at Rabins kryptosystem ikke fik stor praktisk brug.
Sikkerhed
Den store fordel ved Rabin-kryptosystemet er, at den tilfældige tekst kun kan gendannes helt fra chifferteksten, hvis dekrypteringsværktøjet er i stand til effektivt at faktorisere den offentlige nøgle n.
Et Rabin-kryptosystem er beviseligt modstandsdygtigt over for et alt-eller-intet- angreb baseret på et valgt almindeligt chiffertekstangreb, hvis og kun hvis problemet med at indregne et heltal i primfaktorer er uoverskueligt.
Alt-eller-intet-sikkerhed betyder, at når en tekst er krypteret med en bestemt algoritme, skal en angriber gendanne en blok af den originale tekst, hvis størrelse normalt bestemmes af kryptosystemets sikkerhedsparameter. I betragtning af originalen og chifferteksten skal angriberen gendanne hele blokken med private nøgler . I dette tilfælde opnår angriberen enten fuldstændig succes eller modtager intet. Ordet "ingenting" betyder, at angriberen ikke har nogen hemmelig information hverken før eller efter et mislykket angreb.
Rabins kryptosystem er fuldstændig forsvarsløst mod angreb baseret på den valgte chiffertekst . Som regel bruger angriberen alle de muligheder, han har. Han tager kontakt med den angrebne bruger, sender ham chifferteksten til efterfølgende dekryptering og kræver returnering af den originale tekst.
For eksempel kan tilføjelse af redundans, såsom gentagelse af de sidste 64 bit, gøre roden unik. Dekrypteringsalgoritmen i dette tilfælde producerer en enkelt rod, som allerede er kendt af angriberen.
Processen er yderligere sårbar, fordi der kun bruges kvadratiske rester til kodning. I eksemplet med n = 77 bruges kun 23 ud af 76 mulige tilstande.
Se også
Litteratur
- Mao V. Kryptering - asymmetriske metoder // Moderne kryptografi : Teori og praksis / overs. D. A. Klyushina - M. : Williams , 2005. - 768 s. — ISBN 978-5-8459-0847-6
- Schneier B. Anvendt kryptografi. Protokoller, algoritmer, kildekode i C-sprog = Applied Cryptography. Protocols, Algoritms and Source Code in C. - M. : Triumph, 2002. - 816 s. - 3000 eksemplarer. - ISBN 5-89392-055-4 .