Klucze RSA w języku C++

Specyfikacja problemu:

Dane:

• p – liczba naturalna pierwsza; jedna z liczb pierwszych potrzebnych do wyznaczenia kluczy

• q – liczba naturalna pierwsza; druga z liczb pierwszych potrzebnych do wyznaczenia kluczy

Wynik:

• klucz_prywatny – para liczb naturalnych; klucz prywatny algorytmu RSA

• klucz_publiczny – para liczb naturalnych; klucz publiczny algorytmu RSA

Algorytm szyfrowania RSA wymaga zaimplementowaniu kilku funkcji pomocniczych lub zastosowania odpowiednich bibliotek. Jego tworzenie rozpoczniemy od wybrania dwóch liczb pierwszych i oznaczenia ich jako p i q. Do ich odnalezienia możemy zastosować sito Eratostenesasito Eratostenesasito Eratostenesa (jego implementacja w języku C++ została omówiona w e‑materiale: Sito Eratostenesa w języku C++PIp1MFCmXSito Eratostenesa w języku C++).

Następnie obliczamy wartość n = p ∙ q oraz wartość funkcji Eulerafunkcja Eulerafunkcji Eulera dla n (informacje o niej znajdziesz w e‑materiale Szyrf RSAPl0GrlFTpSzyrf RSA).

W kolejnym kroku należy odnaleźć liczbę e spełniającą warunek (1 < e < φphi(n)), która będzie względnie pierwszaliczby względnie pierwszewzględnie pierwsza do liczby φphi. W tym celu można posłużyć się podstawową wersją algorytmu Euklidesaalgorytm Euklidesaalgorytmu Euklidesa (jego implementacja w języku C++ została omówiona w e‑materiale: Algorytm Euklidesa w języku C++PRand33dvAlgorytm Euklidesa w języku C++).

W następnej kolejności należy obliczyć liczbę d spełniającą równanie:

Aby to osiągnąć, można posłużyć się rozszerzonym algorytmem Euklidesa, również przedstawionym we wspomnianym wyżej materiale.

Kluczem publicznym jest para liczb (e, n), a kluczem prywatnym (d, n), gdzie:

• e – liczba względnie pierwsza do liczby φphi,

• n – p ∙ q, gdzie p i q to liczby pierwsze i p != q,

• d – odwrotność modulo φphi(n) liczby e, gdzie φphi(n) to funkcja Eulera.

Przedstawiona poniżej funkcja pozwala na wyznaczenie największego wspólnego dzielnika lub sprawdzenie, czy podane liczby są względnie pierwsze.

Funkcja przyjmuje cztery argumenty: liczby, dla których szukamy największego wspólnego dzielnika, czyli a i b oraz wskaźniki na liczby, które będą miały spełniać tzw. tożsamość Bezouta, czyli x i y. Liczby a, b, x i y są liczbami całkowitymi. Tożsamość Bezouta wygląda następująco: $\mathrm{ax}+\mathrm{by}=\mathrm{NWD(a,b)}$

Przedstawiana funkcja będzie opierała się na mechanizmie rekurencji, w związku z czym wymaga ona warunku zakończenia, po którego spełnieniu zwróci wartość, co pozwoli na zakończenie rekurencji (zapobiegnie powstaniu nieskończonej pętli). Dla rozszerzonego algorytmu Euklidesa warunkiem tym jest osiągnięcie przez pierwszą z porównywanych liczb wartości 0. Wtedy jedynym liczącym się współczynnikiem w tożsamości Bezouta będzie współczynnik $\mathrm{by}$, który będzie równy wartości największego wspólnego dzielnika liczb a i b, więc wartość x ustawiamy na 0, a y na 1 (zerujemy pierwszy wyraz równania, a drugi przyjmuje wartość b).

Następnym krokiem jest stworzenie zmiennych x1 i y1, które będą wykorzystane do wyznaczenia końcowych wartości x i y po zakończeniu rekurencji, w każdym wywołaniu funkcji.

Kolejnym etapem tego algorytmu będzie rekurencyjne wywołanie funkcji ze zmienionymi argumentami. Pierwszy argument powinien przyjąć wartość b%a, a jako drugi podajemy dotychczasowy argument a. W miejsce x i y podajemy wskaźniki na x1 i y1. W ten sposób uzyskamy cykl rekurencji zakończony w momencie wystąpienia warunku zakończenia – zredukowania pierwotnych wartości porównywanych do jednej różnej od 0, będącej ich największym wspólnym dzielnikiem.

Ostatni etap to modyfikacja wartości x i y, tak by spełniały one tożsamość Bezouta, i zwrócenie wyznaczonej rekurencyjnie wartości największego wspólnego dzielnika.

int RozszerzonyEuklides(int a, int b, int* x, int* y)
{
	if (a == 0)
	{
		*x = 0, * y = 1;
		return b;
	}
	int x1, y1;
	int NWD = RozszerzonyEuklides(b % a, a, &x1, &y1);
	*x = y1 - (b / a) * x1;
	*y = x1;
	return NWD;
}

Przedstawiona poniżej funkcja pomocnicza ma na celu wyznaczenie odwrotności modulo podanych jej liczb.

Pierwszym krokiem będzie stworzenie zmiennych x i y, których adresy następnie zostaną użyte przy wywołaniu poprzednio opisanej funkcji.

Aby możliwe było wykonanie operacji odwrotności modulo, liczby, na których chcemy wykonać tę operację, muszą być względnie pierwsze. Sprawdzamy to za pomocą opisanej wcześniej funkcji realizującej rozszerzony algorytm Euklidesa.

Jeśli funkcja obliczająca największy wspólny dzielnik zwróciła wartość inną niż 1, oznacza to, że liczby, na których chcemy wykonać operację odwrotności modulo, nie są względnie pierwsze, zatem powinniśmy zakończyć wykonywanie funkcji z kodem oznaczającym błąd.

Jeżeli liczby, na których chcemy wykonać działanie, są względnie pierwsze, obliczamy odwrotność modulo z wykorzystaniem wyznaczonej przez rozszerzony algorytm Euklidesa wartości x i zwracamy wynik.

int odwrotnoscMod(int a, int b) 
{ 
    int x, y; 
    int g = RozszerzonyEuklides(a, b, &x, &y); 
    if (g != 1) //jeśli g != 1 to liczby a i b nie są względnie pierwsze
        return -1;
    else
    { 
        /*Liczba x może być ujemna, aby tego uniknąć
		dodajemy b, jeśli liczba jest dodatnia, to zewnętrzna
		operacja % gwarantuje nam poprawny wynik*/
        int odwrotnosc = (x%b + b) % b;
        return odwrotnosc;
    } 
}

W tym momencie posiadamy już wszystkie narzędzia do wyznaczania klucza publicznego, klucza prywatnego oraz do szyfrowania i deszyfrowania wiadomości.

Aby zaszyfrować wiadomość, dzielimy ją na bloki o wartości liczbowej nie większej niż n, a następnie implementujemy następującą funkcję, w której P oznacza szyfrowaną wiadomość:

Warto zwrócić uwagę, że wartości (e, n) stanowią klucz publiczny osoby, do której wysyłamy wiadomość.

Funkcje szyfrującą i deszyfrującą łatwo jest zaimplementować z wykorzystaniem funkcji pow(), dostępnej w bibliotece cmath.

unsigned long long szyfrowanieRSA(int wiadomosc, int e, int n)
{
	return (unsigned long long)pow(wiadomosc, e) % n;
}

Jeżeli nie jest możliwe użycie funkcji pow(), to funkcja szyfrująca może mieć następującą formę:

unsigned long long szyfrowanieRSA(int wiadomosc, int e, int n)
{
	unsigned long long rezultat = wiadomosc;
    for (int i = 1; i < e; i++)
    {
    	rezultat = (rezultat * wiadomosc) % n;
    }
    return rezultat;
}

Aby odszyfrować wiadomość, wykonujemy następującą funkcję, w której C oznacza szyfrogram, a para (d, n) jest kluczem prywatnym osoby, która odebrała tę wiadomość:

unsigned long long deszyfrowanieRSA(int szyfrogram, int d, int n)
{
	return (unsigned long long)pow(szyfrogram, d) % n;
}

Podobnie jak w poprzednim przypadku – jeżeli nie jest możliwe użycie funkcji pow(), to funkcja szyfrująca może przyjąć następującą postać:

unsigned long long deszyfrowanieRSA(int szyfrogram, int d, int n)
{
	unsigned long long rezultat = szyfrogram;
	for (int i = 1; i < d; i++)
	{
		rezultat = (rezultat * szyfrogram) % n;
	}
	return rezultat;
}

Problemy w implementacji szyfru RSA w języku C++

Specyfikacja problemu:

Dane:

• p – liczba naturalna pierwsza; jedna z liczb pierwszych potrzebnych do wyznaczenia kluczy

• q – liczba naturalna pierwsza; druga z liczb pierwszych potrzebnych do wyznaczenia kluczy

• wiadomoscSzyfrowana – liczba naturalna; liczba szyfrowana

Wynik:

• szyfrogram – zaszyfrowana wiadomość

Implementując szyfr RSA w języku C++, możemy napotkać problemy, wynikające z ograniczeń samego języka. Liczby pierwsze używane do generowania klucza publicznego i prywatnego powinny być „duże”. Język C++ domyślnie oferuje jedynie liczby 8‑bajtowe bez znaku (unsigned long long) – liczba taka przyjmuje wartości od 0 do 18 446 744 073 709 551 615. Nie jest ona wystarczająca dla większych wartości kluczy. Dlatego używanie tego algorytmu w języku C++ bez wprowadzania nowych typów danych bardzo ogranicza jego możliwości.

Przykładowy program:

#include <iostream>
#include <cmath>

using namespace std;

int RozszerzonyEuklides(int a, int b, int *x, int *y) 
{ 
    if (a == 0) 
    { 
        *x = 0, *y = 1; 
        return b; 
    } 
    int x1, y1;
    int NWD = RozszerzonyEuklides(b%a, a, &x1, &y1); 
    *x = y1 - (b/a) * x1; 
    *y = x1; 

    return NWD; 
}

int odwrotnoscMod(int a, int b) 
{ 
    int x, y; 
    int g = RozszerzonyEuklides(a, b, &x, &y); 
    if (g != 1) //jeśli g != 1 to liczba nie jest pierwsza
        return -1;
    else
    { 
        /*Liczba x może być ujemna, aby tego uniknąć
		dodajemy m, jeśli liczba jest dodatnia, to zewnętrzna
		operacja % gwarantuje nam poprawny wynik*/
        int odwrotnosc = (x%b + b) % b;
        return odwrotnosc;
    } 
}

unsigned long long szyfrowanieRSA(int wiadomosc, int e, int n)
{
	return (unsigned long long)pow(wiadomosc, e) % n;
}

unsigned long long deszyfrowanieRSA(int szyfrogram, int d, int n)
{
	return (unsigned long long)pow(szyfrogram, d) % n;
}

int funkcjaEulera(int p, int q)
{
	return (p-1)*(q-1);
}

int main() 
{
	//Jako osoba chcąca odbierać zaszyfrowane wiadomości generuję sobie klucz prywatny i publiczny
	int p = 5;
	int q = 7;
	int n = p * q;
	int euler = funkcjaEulera(p, q);
	int e = 1;
	int pom1; //zmienne pomocnicze
	int pom2;//Aby użyć rozszerzonego algorytmu Euklidesa jak zwykłego
	do //odnajdywanie e takiego, źe 1 < e < euler
	{
		e++;	
	}
	while(RozszerzonyEuklides(e, euler, &pom1, &pom2) != 1);
	int d = odwrotnoscMod(e, euler);
	/*e, n - klucz publiczny
	d, n - klucz prywatny*/
	int wiadomoscSzyfrowana = 32;
	int szyfrogram = szyfrowanieRSA(wiadomoscSzyfrowana, e, n);
	cout<<"Szyfrogram to: "<<szyfrogram<<" "<<endl;
	
	return 0;
}

Wynik działania programu:

Szyfrogram to: 2

Wynikiem działania programu, szyfrowania liczby naturalnej, jest inna liczba naturalna.

Słownik