Rabins kryptosystem

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 17 augusti 2021; verifiering kräver 1 redigering .

Rabins kryptosystem  är ett kryptografiskt system med offentlig nyckel vars säkerhet säkerställs av svårigheten att hitta kvadratrötter i ringen av rester modulo ett sammansatt nummer . Säkerheten i systemet, liksom säkerheten för RSA- metoden , beror på svårigheten att faktorisera stora siffror. Ett krypterat meddelande kan dekrypteras på fyra sätt. Nackdelen med systemet är behovet av att välja ett sant meddelande bland fyra möjliga.

Historik

I januari 1979 publicerade Michael O. Rabin en beskrivning av sitt system. Det har bevisats att det är lika svårt att återställa klartext från chiffertext som att faktorisera stora siffror. Rabins system blev det första asymmetriska kryptosystemet för vilket ett sådant bevis utfördes. Komplexiteten i återhämtningen är relaterad till svårigheten att extrahera kvadratroten modulo ett sammansatt tal N = p · q . Faktoriseringsproblemet och kvadratrotsproblemet är likvärdiga, det vill säga:

• genom att känna till primtalsdivisorerna för talet N , kan du extrahera kvadratrötterna modulo N ;
• genom att veta hur man extraherar kvadratrötter modulo N , kan man faktorisera N till primtalsfaktorer.

Nyckelgenerering

Rabin-systemet, som alla asymmetriska kryptosystem , använder en offentlig och en privat nyckel. Den publika nyckeln används för att kryptera meddelanden och kan släppas till allmänheten. Den privata nyckeln krävs för dekryptering och bör endast vara känd för mottagarna av krypterade meddelanden.

Nyckelgenereringsprocessen är som följer:

• två slumpmässiga tal p och q väljs med hänsyn till följande krav:
  • siffror måste vara stora (se bitdjup );
  • tal måste vara primtal ;
  • följande villkor måste vara uppfyllt: p ≡ q ≡ 3 mod 4 .

Uppfyllelsen av dessa krav påskyndar avsevärt proceduren för att extrahera rötter modulo p och q ;

• antalet n = p · q beräknas ;
• talet n  är den publika nyckeln; talen p och q  är stängda.

Exempel. Låt p = 7 och q = 11 . Då är n = p · q = 7 · 11 = 77 . Talet n = 77  är den offentliga nyckeln, och siffrorna p = 7 och q = 11  är den privata nyckeln. Mottagaren berättar för avsändarna numret 77. Avsändarna krypterar meddelandet med numret 77 och skickar det till mottagaren. Mottagaren dekrypterar meddelandet med hjälp av siffrorna 7 och 11. De givna nycklarna är dåliga för praktisk användning, eftersom siffran 77 lätt kan delas upp i primtal (7 och 11).

Kryptering

Det ursprungliga meddelandet m (text) krypteras med den offentliga nyckeln - numret n enligt följande formel:

c = m² mod n .

På grund av användningen av modulo multiplikation är krypteringshastigheten för Rabin-systemet högre än krypteringshastigheten för RSA- metoden , även om i det senare fallet ett litet exponentvärde väljs.

Exempel (fortsättning). Låt källtexten vara m = 20 . Då blir chiffertexten : c = m² mod n = 20² mod 77 = 400 mod 77 = 15 .

Dekryptering

För att dekryptera meddelandet behöver du en privat nyckel - siffrorna p och q . Dekrypteringsprocessen är som följer:

• först, med hjälp av Euklids algoritm , siffror och hittas från ekvationen ;
• sedan, med hjälp av den kinesiska restsatsen , beräknas fyra tal:

Ett av dessa nummer är den sanna klartexten m .

Exempel (slut). Som ett resultat av avkodningen får vi: . Vi ser att en av rötterna är originaltexten m .

Algoritm utvärdering

Effektivitet

Att dechiffrera texten, förutom den korrekta, leder till ytterligare tre falska resultat. Detta är den största nackdelen med Rabins kryptosystem och en av faktorerna som hindrade det från att få bred praktisk användning.

Om källtexten är ett textmeddelande är det inte svårt att bestämma rätt text. Men om meddelandet är en ström av slumpmässiga bitar (till exempel för att generera nycklar eller en digital signatur ) blir det ett verkligt problem att bestämma rätt text. Ett sätt att lösa detta problem är att lägga till en känd rubrik eller någon form av etikett till meddelandet före kryptering.

Beräkningshastighet

Rabin-algoritmen liknar RSA-kodning, men istället för att höja meddelandet till styrkan e , använder krypteringen operationen att kvadrera meddelandeblocket, vilket positivt påverkar algoritmens hastighet utan att offra kryptografisk styrka.

För avkodning tillämpas den kinesiska restsatsen tillsammans med två exponentieringar modulo. Här är effektiviteten jämförbar med RSA.

Att välja önskad text bland de fyra leder till ytterligare beräkningskostnader. Och detta tjänade till att säkerställa att Rabins kryptosystem inte fick stor praktisk användning.

Säkerhet

Den stora fördelen med Rabins kryptosystem är att den slumpmässiga texten kan återställas helt och hållet från chiffertexten endast om dekryptören kan effektivt faktorisera den publika nyckeln n.

Ett Rabin-kryptosystem är bevisligen motståndskraftigt mot en allt-eller-inget- attack baserat på en utvald chiffertextattack om och bara om problemet med att faktorisera ett heltal i primtalsfaktorer är svårlöst.

Allt-eller-inget-säkerhet innebär att, med en text krypterad med en viss algoritm, måste en angripare återställa ett block av originaltexten, vars storlek vanligtvis bestäms av säkerhetsparametern för kryptosystemet. Med tanke på originalet och chiffertexten måste angriparen återställa hela den privata nyckelblocket . I det här fallet uppnår angriparen antingen fullständig framgång eller får ingenting. Ordet "ingenting" betyder att angriparen inte har någon hemlig information vare sig före eller efter en misslyckad attack.

Rabins kryptosystem är helt försvarslöst mot attacker baserat på den valda chiffertexten . Som regel använder angriparen alla möjligheter han har. Han tar kontakt med den attackerade användaren, skickar chiffertexten till honom för efterföljande dekryptering och kräver att originaltexten ska återlämnas.

Till exempel kan lägga till redundans, som att upprepa de senaste 64 bitarna, göra roten unik. Dekrypteringsalgoritmen i detta fall producerar en enda rot, som redan är känd för angriparen.

Processen är dessutom sårbar eftersom endast kvadratiska rester används vid kodning. I exemplet med n = 77 används endast 23 av 76 möjliga tillstånd.

Se även

• Merkle-Hellman ryggsäckskryptosystem

Litteratur

• Mao V. Kryptering - asymmetriska metoder // Modern kryptografi : Teori och praktik / transl. D. A. Klyushina - M . : Williams , 2005. - 768 sid. — ISBN 978-5-8459-0847-6
• Schneier B. Tillämpad kryptografi. Protokoll, algoritmer, källkod i C-språk = Applied Cryptography. Protocols, Algoritms and Source Code in C. - M. : Triumph, 2002. - 816 sid. - 3000 exemplar.  - ISBN 5-89392-055-4 .

Public key kryptosystem
Algoritmer	Faktorisering av heltal Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalare Rabin RSA Okamoto - Uchiyama Schmidt-Samoa Diskret logaritm BLS Cramer - Shoup Diffie-Hellman-protokollet DSA ECDH Kurva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypterad nyckelutbyte Schema för ElGamal signaturschema MQV Schnorr-schema SPEKE SRP STS Kryptografi på galler NTRUEncrypt NTRUSign Inlärningsbaserat nyckelutbyte med fel Signaturbaserad träning med fel i ringen SALIGHET Nytt hopp Övrig AE CEILIDH EPOC Dolda fältekvationer IES Lamports signatur McEliece Merkle-Hellman ryggsäckskryptosystem Naccache–Stern ryggsäckskryptosystem Trestegsprotokoll XTR
Teori	Diskret logaritm på en elliptisk kurva Elliptisk kryptografi Hash-baserad kryptografi Icke-kommutativ kryptografi RSA problem Enkelriktad funktion med hemlig entré
Standarder	CRYPTREC IEEE P1363 NESSIE NSA Suite B Postkvantkryptering
Ämnen	Elektronisk signatur OAEP Fingeravtryck PKI nät av förtroende Nyckelstorlek Identitetsbaserad kryptografi Postkvantkryptografi OpenPGP-kort