RSA

Modell:MILCLASS Modell:Nota desambiguazion Modell:F El RSA a l'è on sistema de crittografia asimmetrega inventaa in del 1977 da Ron Rivest, Adi Shamir e Len Adleman al MIT. A l'è staa vun di primm algoritm a ciav publega e 'l primm bon de firmà oltra che cifrà. Brevettaa in del 1983, a l'è staa desecretaa in del 1997.

Operazion

RSA a l'è fondaa in su la complessità de fà la fattorizzazion di numer primm assee grand, e donca se fa inscì:

1. Se scernissen a cas du numer primm $p$ e $q$, assee grand de permett 'na cifratura segura.
2. Se calcola el prodott $n=pq$ e $\phi (n)=(p-1)(q-1)$
3. Se considera che la fattorizzazion de n a l'è secreta, foeura per quej che scernissen p e q
4. Se troeuva on esponent publich, $e$, coprimm de$\phi (n)$ e pussee piscininn de $\phi (n)$.
5. Se calcola el numer $d$ (esponent privaa) inscì che 'l sò prodott con$e$ l'è congrov a $1$ modul $\phi (n)$ ossia che $ed\equiv 1(\mathrm{mod}\phi (n))$

La ciav publega l'è $(n,e)$, la ciav privada è $(n,d)$.

Fondament de matematica

A garantì la decifratura del messagg a gh'è di teorema matematich. De facc del calcol sortiss foeura: $c^d(\mathrm{mod}n)=(m^e{)}^d(\mathrm{mod}n)=m^{ed}(\mathrm{mod}n)$

Ma savemm che: $ed\equiv 1(\mathrm{mod}(p-1)(q-1))$

E donca: $ed\equiv 1(\mathrm{mod}p-1)$ e che $ed\equiv 1(\mathrm{mod}q-1)$.

Donca, per el teorema piscininn de Fermat:

$m^{ed}\equiv m(\mathrm{mod}p)$ e $m^{ed}\equiv m(\mathrm{mod}q)$

Vist che $p$ e $q$ a hinn numer primm different se pò applicà el teorema cines del rest e ottegnì:

$m^{ed}\equiv m(\mathrm{mod}pq)$

e donca che

$c^d\equiv m(\mathrm{mod}n)$

Vos correlaa

• Algoritm Blum-Goldwasser
• Numer RSA