Funcția trapă

Criptarea modernă, asimetrică, se bazează pe două probleme greu de rezolvat: Găsirea Factorilor Primi și Problema Logaritmului Discret

Să discutăm despre găsirea factorilor primi și rolul ei îm criptarea cu cheie publică | privată.

Pare nenatural să închizi ceva cu o cheie și să nu o mai poți deschide cu aceeasi cheie. Ca să complică, lucrurile și mai mult, poti deschide doar cu o cheie diferită. Asta este esența RSA

Ca să reușim cele discutate mai sus, avem nevoie de o funcție „trapă”, adică poate fi calculată într-o direcție, dar este aproape imposibil să refaci pașii invers, fără a doua cheie.

Este un concept matematic, o funcție (aproape) unidirecțională, ușor de calculat într-o directie, foarte costisitor ca resurse informatice să o inversezi.

Trecând prin pașii de mai jos, vom folosi numere mici, dar în practică, numerele folosite sunt foarte mari. Pentru RSA cu 2084 biți cele doua numere prime au 1024 biți fiecare, în jur de 300 de cifre

Alege două numere prime

$p = 5$ , $q = 11$

Aceste numere prime sunt aproape valoric unu de celalalt și foarte lungi, 300 de cifre

Calculează $n$ și $\phi(n)$

$n = p \cdot q = 5 \cdot 11 = 55$

$\phi(n) = (p - 1)(q - 1) = 4 \cdot 10 = 40$

$\phi$(n) întoarce câte numere prime sunt relative până la valoarea lui n, adică toate numerele cuprinse între 1 și n, care nu sunt divizibile la n. Formmula este $(p - 1)(q - 1),$ numai când $p,q$ sunt numere prime.

Alege un exponent public $e$

Alege $e$ în așa fel încât $1 < e < \phi(n)$ și $\gcd(e, \phi(n)) = 1$, gcd este cel mai mare divizor comun

Alegem pe $e = 3$

Calculeaza cheia privată $d$

Avem $d$ astfel încât:

$e \cdot d \equiv 1 \pmod{\phi(n)}$

$3 \cdot d \equiv 1 \pmod{40} \Rightarrow d=27$

Cheia privata este inversul modulo Aritmetica modulară este un alt element esențial în criptare, pentru că fără modulo nu putem inversa procesul de criptare.

---

Cheile

Cheia publică: ($e = 3, n = 55$)

Cheia privată: ($d = 27, n = 55$)

---

Cum criptăm mesajul

Formula pentru a crea mesajul criptat:

$c = m^{e}$, $c = m^e \bmod n$, $c = 7^3 \bmod 55$, $c = 343 \bmod 55$, $c = 13$

Mesajul criptat este 13.

---

Decriptarea mesajului criptat

$m = c^d \bmod n$, $m = 13^{27} \bmod 55$, $m = 7$

Mesajul original este 7

---

Revenind la spoiler-ul articolului, s-a dovedit foarte utilă această funcție, ea permițând semnarea mesajelor cu cheia privată pentru a dovedi autenticitatea autorului. Sau semnarea cu cheia publică pentru a trimite un mesaj pe care doar deținătorul cheiei private îl poate descifra.

---

English article