车讯:长安CS15新DCT车型上市 售7.29-7.79万元

Denna artikel handlar om krypteringsalgoritmen RSA. Se ?ven RSA (olika betydelser).

RSA

Krypteringssystem

Under­klass till	? krypteringssystem  ? asymmetrisk kryptering
Tillkomst	1977
Uppkallad efter	Ron Rivest, Adi Shamir, Leonard Adleman
Defi­nie­ran­de formel	$\left(m^{e}\right)^{d}\equiv m{\pmod {n}}$
Symbol i defi­nie­ran­de formel	$m$, $e$, $d$, $n$
Anv?nds av	Transport Layer Security, version 1.3

百度 在每个环节，只要刷一下身份证，就能做B超、抽血等体检项目，不用再拿着一摞体检表排着长队等候。

RSA-krypteringen (Rivest–Shamir–Adleman) ?r en av de mest k?nda krypteringsalgoritmerna. Det var den f?rsta allm?nt beskrivna algoritmen som anv?nder s? kallad asymmetrisk kryptering. Detta inneb?r att man anv?nder en nyckel f?r att kryptera ett meddelande och en annan f?r att dekryptera det. Denna egenskap g?r den ocks? anv?ndbar f?r att signera ett meddelande s? att mottagaren garanterat vet vem som ?r avs?ndaren. Beteckningen RSA ?r bildat av begynnelsebokst?verna i namnen p? upphovsm?nnen Ron Rivest, Adi Shamir och Len Adleman som beskrev den 1977.

Beskrivning av algoritmen

RSA anv?nder tv? nycklar, en offentlig nyckel och en hemlig nyckel. (P? engelska heter den hemliga nyckeln "private key" vilket inte ?r detsamma som det svenska "privat"). Den publika nyckeln anv?nds f?r att kryptera meddelandet. Meddelandet kan sedan bara dekrypteras med hj?lp av den hemliga nyckeln. Den som ska ta emot ett meddelande best?mmer b?de den offentliga och den hemliga nyckeln och g?r sedan den f?rstn?mnda k?nd f?r alla som ska kunna skicka meddelanden, men beh?ller den hemliga nyckeln f?r sig sj?lv. De nycklar som anv?nds av RSA ?r mycket stora primtal.

Generering av nycklarna

F?r att ta fram nycklarna som beh?vs f?r att anv?nda RSA-algoritmen g?rs f?ljande ber?kningssteg

1. V?lj f?rst slumpm?ssigt tv? olika, stora, primtal p och q.
2. Multiplicera d?refter p och q och kalla produkten f?r n.
3. V?lj sedan ett till heltal, e s? att e och (p-1)(q-1) ?r relativt prima och 1 < e < (p-1)(q-1) .
4. Ber?kna slutligen ett heltal d s?dant att ed ≡ 1 (mod (p-1)(q-1)).

Den offentliga nyckeln best?r av talen e och n och den hemliga nyckeln av talen p, q och d.

Finessen ?r att ?ven om e och n ?r k?nda, g?r det inte att r?kna ut de b?da primfaktorerna p och q, inom rimlig tid, eftersom det inte finns n?gon effektiv algoritm f?r primtalsfaktorisering. D?rmed kan man inte heller r?kna ut d. Endast den r?tte mottagaren k?nner till p, q och d och kan d?rmed avkoda meddelandet.

Kryptering

Den som vill s?nda ett meddelande omformar detta till ett tal x < n, eller en f?ljd av s?dana tal. Detta sker med en i f?rv?g ?verenskommen reversibel algoritm. F?r varje x ber?knas talet y

y = x^e mod n

Talet y eller f?ljden av s?dana tal ?r det krypterade meddelandet.

Dekryptering

F?r varje mottaget tal y kan det ursprungliga talet x ber?knas med

x = y^d mod n

och d?refter kan det ursprungliga meddelandet ?terskapas. Att s? ?r fallet f?ljer av f?ljande matematiska resonemang

y^d mod n = (x^e mod n)^d mod n = (x^e)^d mod n = x^ed mod n

Eftersom ed ≡ 1 (mod (p-1)(q-1)) s? g?ller ocks?

ed ≡ 1 (mod p-1)

och

ed ≡ 1 (mod q-1)

och av Fermats lilla sats f?ljer d?

x^ed ≡ x (mod p)

och

x^ed ≡ x (mod q)

Eftersom p och q ?r olika primtal, f?r man genom att till?mpa Kinesiska restklassatsen att

x^ed ≡ x (mod pq)

D.v.s

x^ed ≡ x (mod n)

eller

x = x^ed mod n = y^d mod n

Signering

Om avs?ndaren av ett meddelande vill kunna bevisa att han verkligen ?r den som s?nt meddelandet, och samtidigt garantera att meddelandet inte kan ha ?ndrats p? v?gen, kan han anv?nda RSA f?r att signera sitt meddelande. Detta g?r till p? f?ljande s?tt.

F?rst ber?knas ett hashv?rde h av meddelandet d?r 0 < h < n. Detta g?rs med n?gon ?verenskommen algoritm, och hashv?rdet krypteras sedan med avs?ndarens hemliga nyckel:

s = h^d mod n

Det krypterade hashv?rdet s?nds sedan som en signatur tillsammans med meddelandet till mottagaren. Mottagaren kan verifiera att avs?ndaren ?r den han utger sig vara, genom att dekryptera signaturen s med avs?ndarens publika nyckel:

h = s^e mod n

Mottagaren kontrollerar sedan den dekrypterade signaturen genom att sj?lv ber?kna hashv?rdet fr?n det mottagna meddelandet och j?mf?ra det med den dekrypterade signaturen. Om v?rdena ?verensst?mmer vet mottagaren att endast den angivna avs?ndaren kan ha producerat meddelandet.

Ett "smidigt" exempel

Primtalen 1 249 och 1 049 ger n = 1 310 201. Vi v?ljer e = 1 013 varp? d = 843 101. Utr?kningen av d g?rs genom en diofantisk ekvation, 1 013d - (p-1)(q-1)k = 1.

Ett meddelande x, som lyder 444 807 och som vi vill kryptera g?rs detta genom att r?kna ut x^e (mod n), allts? 444 807^{1 013} (mod 1 310 201). Det krypterade meddelandet blir d? 503 328.

Dekryptering av ovanst?ende meddelande y g?rs genom y^d (mod n), allts? 503 328^{843 101} (mod 1 310 201). Detta blir 444 807, vilket var v?rt ursprungliga meddelande.