Witam,
Dzisiaj chciałbym przedstawić wam implementacje algorytmu RSA( Ronald Rivest, Adi Shamir, Leonard Adleman). Wykorzystując potężną bibliotekę LiDIA (strona domowa biblioteki: http://www.cdc.informatik.tu-darmstadt.de/TI/LiDIA/)
Najpierw przedstawie algorytm:
- Losujemy dwie duże(ok 1024 bity tj. Liczba składająca się z 300 cyfr) liczby pierwsze p i q, oraz liczbę e = (p − 1)(q − 1).
- Następnie obliczamy
(ponieważ wybraliśmy względnie pierwsze e, ma ono odwrotność i obliczyć ją możemy szybko rozszerzonym algorytmem Euklidesa)
- W kolejnym kroku obliczamy n która jest iloczynem p i q
- Klucz publiczny to para (e,n), klucz prywatny zaś to para (d,n). Liczby p i q należy zniszczyć.
- Szyfrujemy wiadomość M za pomocą: c=m^e mod n (c- kryptogram, wiadomość zaszyfrowana = wiadomość m do potęgi e modulo n)
- Żeby M zdeszyfrować podnosimy zaszyfrowaną wiadomość do potęgi d. Zgodnie z twierdzeniem Eulera dostaniemy oryginalną wiadomość (o ile m nie jest wielokrotnością p lub q): c^d = m^(ed) = m mod n
Implementacja:
#include <LiDIA/bigint.h>
#include <iostream>using namespace std;
using namespace LiDIA;
bigint get_liczba() {
bigint rand_liczba;
bigint max = 1;
shift_left(max, max, 1024); // powiększamy liczbę do 1024 bajtów wielkości
do {
rand_liczba.randomize(max);
}while(!is_prime(rand_liczba));
return rand_liczba;
}
int main(){
bigint p, q;
// losowanie p i q
do{
p = get_liczba();
q = get_liczba();
}
while(p==q);
//licznie n
bigint n;
n = p * q;
bigint fi;
fi = (p-1)*(q-1);
bigint u,v,e;
do {
e.randomize(fi);
e++;
}while(xgcd(u,v,e,fi)!=1);
bigint m,c,de;
m=50000; // nasza wiadomość
cout<<"message: "<<m<<endl;
if (u<0){
u=u%fi;
}
power_mod(c,m,e,n);
cout<<"zaszyfrowane = "<<c<<endl<<endl;
power_mod(de,c,u,n);
cout<<"odszyfrowane = "<<de<<endl<<endl;
}
Kompilacja:
g++ -O test.cc -I/usr/local/include -L/usr/local/lib -o test -lLiDIA -lgmp -lm
Opis Funkcji:
- bigint xgcd(bigint & u, bigint & v, const bigint & a, const bigint & b) – funkcja oblicza (a, b) = au + vb)
- void power_mod (bigint & res, const bigint & a, const bigint & n, const bigint m, int err = 0) – funkcja oblicza res = a^n (mod m)
- void div_rem (bigint & q, bigint & r, const bigint & a, const bigint & b) – funkcja oblicza: q i r takie, że a = qb + r
- bool is_prime (const bigint & a, int n = 10) – funkcja zwraca wartość true jeśli a jest liczbą pierwszą(Prawdopodobieństwo tego, że a jest liczbą pierwszą jest nie mniejsze niż 1 – 1/(4^n) )