mGz developer blog

Implementacja algorytmu RSA w C++

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:

1. 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).
2. Następnie obliczamy (ponieważ wybraliśmy względnie pierwsze e, ma ono odwrotność i obliczyć ją możemy szybko rozszerzonym algorytmem Euklidesa)
3. W kolejnym kroku obliczamy n która jest iloczynem p i q
4. Klucz publiczny to para (e,n), klucz prywatny zaś to para (d,n). Liczby p i q należy zniszczyć.
5. Szyfrujemy wiadomość M za pomocą: c=m^e mod n (c- kryptogram, wiadomość zaszyfrowana = wiadomość m do potęgi e modulo n)
6. Ż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) )