RSA (Rivest–Shamir–Adleman): avaliku võtme krüptograafia selgitus

RSA: selge juhend avaliku võtme krüptograafiast — kuidas toimib RSA, miks see turvaline on, võtmete genereerimine ja praktilised kasutusjuhtumid.

Autor: Leandro Alegsa

RSA (Rivest–Shamir–Adleman) on algoritm, mida kaasaegsed arvutid kasutavad sõnumite krüpteerimiseks ja dekrüpteerimiseks. See on asümmeetriline krüptograafiline algoritm. Asümmeetriline tähendab, et kasutatakse kahte erinevat võtit. Seda nimetatakse ka avaliku võtme krüptograafiaks, sest ühe võtme (avaliku võtme) võib jagada kõigiga, samas kui teine võti peab jääma privaatseks. RSA turvalisus põhineb asjaolul, et väga suure liitarvu tegurite leidmine on arvuliselt keeruline: kui tegurid on algarvud, nimetatakse seda probleemi primaarfaktoreerimiseks.

Kuidas RSA töötab (lühike ülevaade)

Peamised sammud võtme genereerimiseks ja sõnumi krüpteerimiseks on järgmised:

  • Vali kaks suurt juhuslikku eri alg­arvu p ja q.
  • Arvuta n = p × q. Mõlemad p ja q peavad jääma salajas — n on osa avalikust võtmeparist.
  • Arvuta φ(n) = (p − 1) × (q − 1) (Euler'i totientfunktsioon).
  • Vali avalik eksponent e, kus 1 < e < φ(n) ja gcd(e, φ(n)) = 1 (ehk e on φ(n)-ga ühismittea).
  • Leia privaatne eksponent d, mis on e modulaarne pöördarv suhtes φ(n); s.t. d × e ≡ 1 (mod φ(n)).
  • Avalik võti on paar (n, e); privaatvõti on (n, d) või tihti hoopis p, q, d koos optimeerimiseks vajalike lisaväärtustega.

Krüpteerimine ja dekrüpteerimine matemaatiliselt:

  • Krüpteerimine: c = me mod n (kus m on sõnumi arvuline esitus, väiksem kui n).
  • Dekrüpteerimine: m = cd mod n.

Kasutusalad

  • Andmete konfidentsiaalsus: RSA-d kasutatakse sageli võtmevahetuseks — genereeritakse juhuslik sümmeetriline võti, mis krüpteeritakse RSA abil ja saadetakse turvaliselt. Sõnumite tegelik krüptimine toimub tavaliselt kiiremate sümmeetriliste algoritmidega (nt AES).
  • Digitaalsed allkirjad: RSA võimaldab allkirjastada sõnumeid või dokumente privaatvõtmega, et vastuvõtja saaks avaliku võtmega allkirja kontrollida.
  • Transporti- ja protokollid: RSA on olnud laialdaselt kasutuses TLS/SSL, e-posti krüpteerimisel (PGP) ja muudes turvaprotokollides.

Turvalisus ja piirangud

RSA turvalisus tugineb faktoreerimisraskusele. Kui keegi suudab n-i faktoriseerida (leida p ja q), saab ta arvutada φ(n) ja sellest d — seega murda võtme. Peamised ohud ja kaalutlused:

  • Faktoreerimisrünnakud: suuremate n-de faktoreerimine on arvuliselt kallis. Tänapäeval peetakse 2048-bitiseid võtmeid üldiselt turvaliseks paljude rakenduste jaoks; kõrgema turvalisuse puhul soovitatakse 3072 või 4096 bitti. Soovituslik võtme pikkus sõltub oodatavast ohutasemest ja aeghorizonist.
  • Paddinõuded: RSA ei ole turvaline ilma sobiva täiendava täitmisrežiimita (padding). Ilma sellele lisamata (nt "textbook RSA") on võimalik sõnumeid mõne lihtsa rünnakuga taastada. Levinud täitmisstandardid on PKCS#1 v1.5 (vana, mõningad haavatavused) ja kaasaegsem OAEP (Optimal Asymmetric Encryption Padding) krüpteerimiseks ning PSS allkirjade jaoks.
  • Külgkanalirünnakud: RSA on haavatav füüsilistele rakendustele (nt ajastusanalüüs, elektrivoolu mõõtmine). Leevendused hõlmavad blindimist (blinding) ja CRT-põhiste dekrüpteerimiste turvalist implmentatsiooni.
  • Kvantarünnakud: teoreetilise kvantarvuti olemasolu korral võib Shori algoritm primaarfaktoreerimise teha polürütmiliselt kiirelt, mis muudaks RSA kiirelt ebaturvaliseks. Sellepärast uuritakse uut "postkvant" krüptograafiat.

Headempraktikad ja optimeerimine

  • Kasuta alati sobivat täitmist (nt OAEP krüpteerimiseks, PSS allkirjadeks).
  • Võtme pikkus: vali riskitundlikusest sõltuvalt vähemalt 2048 bitti (paljud organisatsioonid eelistavad 3072+ bitti pikaajaliseks konfidentsiaalsuseks).
  • Ära kasuta RSA-d otse pikemate sõnumite krüpteerimiseks — kasuta hübriidset lähenemist: RSA krüpteerib sümmeetrilise võtme, millest järgneb sõnumi AES-iga krüpteerimine.
  • Haldus: hoia privaatvõti turvaliselt (riistvarakaitstud võtmehoidjad, HSM-id) ja tagasta/kehtetu tava korral võtme muutmine (rotatsioon).
  • Implmentatsioonis kasuta kaitsemeetmeid külgkanalirünnakute ja valesisendite vastu ning kasuta usaldusväärseid krüptograafilisi teeke.

Tõhusus

RSA põhitegevused (eksponentsiaalsed teisendused suurtel arvudel) on suhteliselt aeglased võrreldes sümmeetriliste algoritmidega. Sellepärast kasutatakse RSA-t peamiselt võtmevahetuseks ja allkirjastamiseks, mitte suure mahu otse krüpteerimiseks. Dekrüpteerimisel ja allkirjade tegemisel kasutatakse sageli CRT-tehnikaid (Chinese Remainder Theorem), mis kiirendavad arvutusi, kuid nõuavad hoolikat teostust turvalisuse säilitamiseks.

Ajaloost ja patenteerimisest

RSA avalikustati 1977. aastal Ronald Rivest, Adi Shamir ja Leonard Adlemani poolt. Algusaegadel oli RSA-le seotud patent (USA-s), mis aegus 2000. aastal; sellest ajast alates on algoritmi kasutamine olnud laiemalt vabalt kättesaadav. Hoolimata vanusest on RSA endiselt üks tuntumaid avaliku võtme skeeme maailmas, kuigi kasvav huvi postkvantlahenduste vastu võib tulevikus muuta selle positsiooni.

Kokkuvõte

RSA on oluline ja laialdaselt kasutatav avaliku võtme krüptograafia meetod, mis põhineb suurte arvude primaarfaktoreerimise raskusel. See pakub nii konfidentsiaalsust kui ka autentimist/allkirjastamist, kuid nõuab õigeid täitmisstandardeid, piisavat võtme pikkust ja ettevaatusabinõusid külgkanalirünnakute ning tulevaste kvantohtude vastu. Praktikas kasutatakse RSA-d tihti koos sümmeetriliste algoritmidega, et kombineerida turvalisust ja jõudlust.

Sõnumi krüpteerimine

Alice annab oma avaliku võtme ( n {\displaystyle n\,}{\displaystyle n\,} & e {\displaystyle e\,}{\displaystyle e\,} ) Bobile ja hoiab oma isikliku võtme salajas. Bob soovib saata Alice'ile sõnumi M.

Kõigepealt muudab ta M arvuks m {\displaystyle m}m , mis on väiksem kui n {\displaystyle n}n , kasutades selleks kokkulepitud pöörduvat protokolli, mida nimetatakse polsterdusskeemiks. Seejärel arvutab ta salakirja c {\displaystyle c\,}{\displaystyle c\,} , mis vastab:

c = m e mod n {\displaystyle c=m^{e}\mod {n}} {\displaystyle c=m^{e}\mod {n}}

Seda saab kiiresti teha, kasutades ruutkeskmise meetodit. Seejärel saadab Bob Alice'ile c \displaystyle c\,} . {\displaystyle c\,}

Sõnumi dekrüpteerimine

Alice saab m {\displaystyle m\,}{\displaystyle m\,} taastada c {\displaystyle c\,}{\displaystyle c\,} , kasutades oma isiklikku võtit d {\displaystyle d\,}{\displaystyle d\,} järgmises menetluses:

m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}} {\displaystyle m=c^{d}{\bmod {n}}}

Arvestades m {\displaystyle m\,}{\displaystyle m\,} , saab ta taastada algsed erinevad algsed algarvud, kohaldades Hiina jäägite teoreemi nende kahe kongruentsuse suhtes, saadakse

m e d ≡ m mod p q {\displaystyle m^{ed}\equiv m{\bmod {pq}}} .{\displaystyle m^{ed}\equiv m{\bmod {pq}}}

Seega,

c d ≡ m mod n {\displaystyle c^{d}\equiv m{\bmod {n}}} .{\displaystyle c^{d}\equiv m{\bmod {n}}}

Töötav näide

Siin on näide RSA krüpteerimise ja dekrüpteerimise kohta. Siin kasutatud parameetrid on kunstlikult väikesed, kuid te võite kasutada OpenSSL-i ka tõelise võtmepaari genereerimiseks ja uurimiseks.

  1. Valige kaks juhuslikku algarvu.
  2.  : p = 61 {\displaystyle p=61}{\displaystyle p=61} ja q = 53 ; {\displaystyle q=53;} {\displaystyle q=53;}Arvuta n = p q {\displaystyle n=pq\,} {\displaystyle n=pq\,}
  3.  : n = 61 ∗ 53 = 3233 {\displaystyle n=61*53=3233} {\displaystyle n=61*53=3233}
  4. Arvutatakse totient ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)\,} {\displaystyle \phi (n)=(p-1)(q-1)\,}
  5.  : ϕ ( n ) = ( 61 - 1 ) ( 53 - 1 ) = 3120 {\displaystyle \phi (n)=(61-1)(53-1)=3120} {\displaystyle \phi (n)=(61-1)(53-1)=3120}
  6. Vali e > 1 {\displaystyle e>1}{\displaystyle e>1} coprime to 3120
  7.  : e = 17 {\displaystyle e=17} {\displaystyle e=17}
  8. Valige d {\displaystyle d\,}{\displaystyle d\,} nii, et d e mod ϕ ( n ) ≡ 1 {\displaystyle de{\bmod {\phi (n)}\equiv 1\,} rahuldab.} {\displaystyle de{\bmod {\phi (n)}}\equiv 1\,}
  9.  : d = 2753 {\displaystyle d=2753} {\displaystyle d=2753}
  10.  : 17 ∗ 2753 = 46801 = 1 + 15 ∗ 3120 {\displaystyle 17*2753=46801=1+15*3120} .{\displaystyle 17*2753=46801=1+15*3120}

Avalik võti on ( n = 3233 {\displaystyle n=3233}{\displaystyle n=3233} , e = 17 {\displaystyle e=17}{\displaystyle e=17} ). Täidetud sõnumi m {\displaystyle m\,}{\displaystyle m\,} puhul saab krüpteerimisfunktsioon c = m e mod n {\displaystyle c=m^{e}{\bmod {n}}}{\displaystyle c=m^{e}{\bmod {n}}} :

c = m 17 mod 3 233 {\displaystyle c=m^{17}{\bmod {3}}233\,} {\displaystyle c=m^{17}{\bmod {3}}233\,}

Privaatne võti on ( n = 3233 {\displaystyle n=3233}{\displaystyle n=3233} , d = 2753 {\displaystyle d=2753}{\displaystyle d=2753} ). Dekrüpteerimisfunktsioon m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}}{\displaystyle m=c^{d}{\bmod {n}}} saab:

m = c 2753 mod 3 233 {\displaystyle m=c^{2753}{\bmod {3}}233\,} {\displaystyle m=c^{2753}{\bmod {3}}233\,}

Näiteks, et krüpteerida m = 123 {\displaystyle m=123} {\displaystyle m=123}arvutame

c = 123 17 mod 3 233 = 855 {\displaystyle c=123^{17}{\bmod {3}}233=855}} {\displaystyle c=123^{17}{\bmod {3}}233=855}

C = 855 {\displaystyle c=855} dekrüpteerimiseks. {\displaystyle c=855}arvutame

m = 855 2753 mod 3 233 = 123 {\displaystyle m=855^{2753}{\bmod {3}}233=123} {\displaystyle m=855^{2753}{\bmod {3}}233=123}

Mõlemaid arvutusi saab tõhusalt arvutada, kasutades modulaarse korrutamise ruut- ja korrutamisalgoritmi [en].

RSA võrrandi tuletamine Euleri teoreemi põhjal

RSA saab hõlpsasti tuletada Euleri teoreemi ja Euleri totaalfunktsiooni abil.

Alustades Euleri teoreemiast,

m ϕ ( n ) ≡ 1 ( mod n ) {\displaystyle m^{\phi (n)}\equiv 1{\pmod {n}}} {\displaystyle m^{\phi (n)}\equiv 1{\pmod {n}}}

peame näitama, et krüpteeritud sõnumi dekrüpteerimine õige võtmega annab algse sõnumi. Kui on antud täiendatud sõnum m, siis arvutatakse salastatud tekst c järgmiselt.

c ≡ m e ( mod n ) {\displaystyle c\equiv m^{e}{\pmod {n}}} {\displaystyle c\equiv m^{e}{\pmod {n}}}

Asendades dekrüpteerimisalgoritmi, saame järgmise tulemuse

c d ≡ ( m e ) d ≡ m e d ( mod n ) {\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}} {\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}}

Tahame näidata, et see väärtus on samuti kongruentne m-ga. e ja d väärtused valiti nii, et need rahuldaksid,

e d ≡ 1 ( mod ϕ ( n ) ) {\displaystyle ed\equiv 1{\pmod {\phi (n)}}} {\displaystyle ed\equiv 1{\pmod {\phi (n)}}}

See tähendab, et on olemas mingi täisarv k, mis on selline, et

e d = k × ϕ ( n ) + 1 {\displaystyle ed=k\times \phi (n)+1} {\displaystyle ed=k\times \phi (n)+1}

Nüüd asendame krüpteeritud ja seejärel dekrüpteeritud sõnumi,

m e d ≡ m k ϕ ( n ) + 1 ≡ m × m k ϕ ( n ) ≡ m × ( m ϕ ( n ) ) k ( mod n ) {\displaystyle {\begin{aligned}m^{ed}&\equiv m^{k\phi (n)+1}\\&\equiv m\times m^{k\phi (n)}\\&\equiv m\times \left(m^{\phi (n)}\right)^{k}{\pmod {n}}\end{aligned}}}} {\displaystyle {\begin{aligned}m^{ed}&\equiv m^{k\phi (n)+1}\\&\equiv m\times m^{k\phi (n)}\\&\equiv m\times \left(m^{\phi (n)}\right)^{k}{\pmod {n}}\end{aligned}}}

Rakendame Euleri teoreemi ja saavutame tulemuse.

m × ( 1 ) k ≡ m ( mod n ) {\displaystyle m\times (1)^{k}\equiv m{\pmod {n}}} {\displaystyle m\times (1)^{k}\equiv m{\pmod {n}}}

Padding skeemid

Kui RSA-d kasutatakse praktikas, tuleb seda kombineerida mingisuguse polsterdusskeemiga, nii et M-i väärtused ei annaks ebaturvalist salastusteksti. Ilma polsterduseta kasutataval RSA-l võib olla mõningaid probleeme:

  • Väärtused m = 0 või m = 1 annavad alati vastavalt 0 või 1 väärtusega šifreeritud tekstid, mis tulenevad eksponentsuse omadustest.
  • Kui krüpteeritakse väikeste krüpteerimiseksponentidega (nt e = 3) ja väikeste m väärtustega, võib m e {\displaystyle m^{e}}{\displaystyle m^{e}} (mittemodulaarne) tulemus olla rangelt väiksem kui moodul n. Sellisel juhul võib salakirju kergesti dekrüpteerida, võttes salakirju eetrijuure, võtmata arvesse moodulit.
  • RSA krüpteerimine on deterministlik krüpteerimisalgoritm. Sellel puudub juhuslik komponent. Seetõttu saab ründaja edukalt käivitada valitud lihtteksti rünnaku krüptosüsteemi vastu. Nad võivad koostada sõnastiku, krüpteerides tõenäolisi lihtsaid tekste avaliku võtme all ja salvestades saadud šifreeritud tekstid. Seejärel saab ründaja jälgida sidekanalit. Niipea kui nad näevad salakirjatekste, mis vastavad nende sõnastikus olevatele tekstidele, saavad ründajad kasutada seda sõnastikku, et teada saada sõnumi sisu.

Praktikas võivad lühikeste ASCII-sõnumite saatmisel tekkida kaks esimest probleemi. Sellistes sõnumites võib m olla ühe või mitme ASCII-kodeeritud tähemärgi aheldamine. Sõnum, mis koosneb ühest ASCII-märgist NUL (mille numbriline väärtus on 0), kodeeritakse m = 0, mis annab salakirjasõnumi 0, olenemata sellest, milliseid e ja N väärtusi kasutatakse. Samamoodi annab üks ASCII SOH (mille numbriline väärtus on 1) alati salakirjateksti väärtusega 1. Süsteemides, kus tavapäraselt kasutatakse väikeseid e väärtusi, näiteks 3, oleksid kõik selle skeemi abil kodeeritud ühe tähemärgiga ASCII-sõnumid ebaturvalised, sest suurima m väärtus oleks 255 ja 2553 on väiksem kui mis tahes mõistlik moodul. Selliseid salakirju saaks taastada, võttes lihtsalt salakirjastusteksti kuupjuurt.

Nende probleemide vältimiseks on praktilised RSA rakendused tavaliselt enne krüpteerimist väärtusele m mingi struktureeritud, randomiseeritud polsterdus. See täitmine tagab, et m ei kuulu ebaturvaliste algtekstide hulka ja et antud sõnum, kui see on täidetud, krüpteeritakse üheks paljudest erinevatest võimalikest salakirjadest. Viimane omadus võib suurendada sõnastikurünnaku maksumust üle mõistliku ründaja võimete.

Sellised standardid nagu PKCS on hoolikalt kavandatud sõnumite turvaliseks polsterdamiseks enne RSA-krüpteerimist. Kuna need skeemid täidavad lihtteksti m teatud arvu lisabittidega, peab täiendamata sõnumi M suurus olema mõnevõrra väiksem. RSA-skeemid peavad olema hoolikalt kavandatud, et vältida keerulisi rünnakuid. Seda võib lihtsustada prognoositav sõnumite struktuur. PKCS-standardi varajased versioonid kasutasid ad-hoc-konstruktsioone, mis hiljem leiti, et need on haavatavad praktilise adaptiivse valitud salastusteksti rünnaku suhtes. Kaasaegsed konstruktsioonid kasutavad sõnumite kaitsmiseks turvalisi tehnikaid, nagu optimaalne asümmeetriline krüpteerimine (Optimal Asymmetric Encryption Padding, OAEP), mis takistab selliseid rünnakuid. PKCS-standardis on ka töötlemisskeemid, mis on mõeldud RSA allkirjade täiendava turvalisuse tagamiseks, nt RSA-pSS (Probabilistic Signature Scheme for RSA).

Sõnumite allkirjastamine

Oletame, et Alice kasutab Bobi avalikku võtit, et saata talle krüpteeritud sõnum. Sõnumis võib ta väita, et ta on Alice, kuid Bobil ei ole võimalik kontrollida, kas sõnum on tegelikult Alice'ilt, sest igaüks võib kasutada Bobi avalikku võtit, et saata talle krüpteeritud sõnumeid. Seega saab sõnumi päritolu kontrollimiseks kasutada RSA-d ka sõnumi allkirjastamiseks.

Oletame, et Alice soovib saata allkirjastatud sõnumi Bobile. Ta koostab sõnumi hash-väärtuse, tõstab selle d mod n-i potentsile (nagu sõnumi dekrüpteerimisel) ja lisab selle sõnumi "allkirjaks". Kui Bob saab allkirjastatud sõnumi, tõstab ta allkirja potentsile e mod n (nagu sõnumi krüpteerimisel) ja võrdleb saadud riivimisväärtust sõnumi tegeliku riivimisväärtusega. Kui need langevad kokku, teab ta, et sõnumi autoril oli Alice'i salajane võti ja et sõnumit ei ole pärast seda muudetud.

Pange tähele, et turvalised polsterdusskeemid, nagu RSA-PSS, on sõnumi allkirjastamise turvalisuse seisukohalt sama olulised kui sõnumi krüpteerimisel, ning et sama võtit ei tohiks kunagi kasutada nii krüpteerimiseks kui ka allkirjastamiseks.

Küsimused ja vastused

K: Mis on RSA?


V: RSA (Rivest-Shamir-Adleman) on algoritm, mida kaasaegsed arvutid kasutavad sõnumite krüpteerimiseks ja dekrüpteerimiseks. See on asümmeetriline krüptograafiline algoritm.

K: Mida tähendab asümmeetriline?


V: Asümmeetriline tähendab, et on kaks erinevat võtit - avalik ja privaatne võti.

K: Mis on RSA algoritmi alus?


V: Algoritm põhineb asjaolul, et suure liitarvu tegurite leidmine on keeruline - kui tegurid on algarvud, nimetatakse seda probleemi algarvude faktoriseerimiseks.

K: Kuidas RSA töötab?


V: RSA hõlmab avalikku võtit ja privaatvõtit. Avalik võti võib olla kõigile teada - seda kasutatakse sõnumite krüpteerimiseks. Avaliku võtmega krüpteeritud sõnumeid saab dekrüpteerida ainult privaatvõtmega, mida tuleb hoida salajas. Avaliku võtme põhjal on väga raske arvutada privaatvõtit.

Küsimus: Kas seda tüüpi krüptograafiat nimetatakse ka teisiti?


V: Seda krüptograafiatüüpi nimetatakse ka avaliku võtme krüptograafiaks, sest ühe võtme võib anda kellelegi, kuid teise võtme võib hoida privaatsena.

K: Kas RSA genereerib võtmepaari?


V: Jah, RSA genereerib võtmepaari - avaliku ja privaatvõtme - mida kasutatakse vastavalt krüpteerimiseks ja dekrüpteerimiseks.


Otsige
AlegsaOnline.com - 2020 / 2025 - License CC3