Przeczytaj

Tworzenie klucza publicznego i prywatnego

Specyfikacja:

Dane:

p – liczba naturalna pierwsza
q – liczba naturalna pierwsza

Wynik:

klucz_prywatny – para liczb naturalnych; klucz prywatny algorytmu RSA
klucz_publiczny – para liczb naturalnych; klucz publiczny algorytmu RSA

Rozpoczynając szyfrowanie, musimy najpierw wybrać klucz publiczny oraz prywatny. Pierwszym krokiem, który należy wykonać w tym kierunku, jest wybranie dwóch liczb pierwszych – p oraz q.

Po wybraniu liczb pierwszych, należy obliczyć ich iloczyn – liczbę tę, zwaną modułem, w programie nazwiemy n. Potrzebna będzie również wartość funkcji Eulerafunkcja Eulerafunkcji Eulera liczby n. Dysponując rozkładem tej liczby na czynniki pierwszeD14Gk0Xunrozkładem tej liczby na czynniki pierwsze, p ∙ q, wartość funkcji Eulera możemy obliczyć następująco: fi(n) = (p‑1) ∙ (q‑1).

Zapiszmy te kroki w postaci programu, który następnie będziemy uzupełniać w kolejnych etapach tworzenia klucza publicznego i prywatnego. Na potrzeby e‑materiału posłużymy się liczbami całkowitymi typu int oraz małymi liczbami pierwszymi p i q – program przetestujemy dla liczb 13 i 11. W przyszłości pamiętajmy jednak, aby używać znacznie większych liczb.

int p = 13, q = 11;
int n = p * q;			// dla przykładowych wartości p i q, n = 143
int fi = (p-1) * (q-1);	// dla przykładowych wartości p i q, fi = 120

Teraz możemy wybrać tzw. wykładnik publiczny. Jest to liczba, która zostanie częścią klucza publicznego – oznaczymy ją jako e. Musi ona być względnie pierwsza z liczbą fi. Na tym etapie nie zajmujemy się wyborem odpowiednio dużej liczby. Często używa się liczb 257 lub 65537. W naszym przypadku wybierzemy liczbę 7.

Aby sprawdzić, czy wybrana liczba jest względnie pierwsza z fi, posłużmy się algorytmem EuklidesaP7OAFYVSialgorytmem Euklidesa. Jeśli NWD(e, fi) jest równy 1, liczbę e wybrano poprawnie. Para liczb (e, n) będzie stanowiła klucz publiczny. Ważne jest także, aby po obliczeniu klucza prywatnego sprawdzić, czy nie jest taki sam, jak klucz publiczny. Jeśli jest, trzeba zmienić liczbę e.

Funkcja sprawdz_e() weryfikuje, czy wybrana liczba jest względnie pierwsza z fi. W tym celu napisana została także funkcja nwd().

static int nwd(int a, int b) {
	if (b == 0) {
		return a;
	}
	return nwd(b, a % b);
}

static boolean sprawdz_e(int e, int fi) {
	return nwd(e, fi) == 1;
}

Utworzyliśmy już klucz publiczny, przejdźmy do utworzenia klucza prywatnego.

W tym celu musimy znaleźć dla liczby e odwrotność moduloodwrotność moduloodwrotność modulo fi – czyli taką liczbę d, dla której wartość wyrażenia (d ∙ e) % fi == 1 jest prawdziwa. Wówczas kluczem prywatnym będzie para liczb (d, n).

Możemy posłużyć się tutaj metodą naiwną – sprawdzić wszystkie liczby od 1 do fi - 1 lub zrealizować rozszerzony algorytm Euklidesa. Druga metoda jest optymalna.

Linia 1. prawy ukośnik prawy ukośnik znalezienie odwrotności modulo metodą naiwną. Linia 2. static int odwrotnosc podkreślnik modulo podkreślnik naiwnie otwórz nawias okrągły int a przecinek int n zamknij nawias okrągły otwórz nawias klamrowy. Linia 3. a znak równości a procent n średnik. Linia 4. for otwórz nawias okrągły int x znak równości 1 średnik x otwórz nawias ostrokątny znak równości n minus 1 średnik x plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. if otwórz nawias okrągły otwórz nawias okrągły a asterysk x zamknij nawias okrągły procent n znak równości znak równości 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. return x średnik. Linia 7. zamknij nawias klamrowy. Linia 8. zamknij nawias klamrowy. Linia 9. return 1 średnik. Linia 10. zamknij nawias klamrowy. Linia 12. prawy ukośnik prawy ukośnik znalezienie odwrotności modulo algorytmem Euklidesa. Linia 13. static int odwrotnosc podkreślnik modulo podkreślnik euklides otwórz nawias okrągły int a przecinek int n zamknij nawias okrągły otwórz nawias klamrowy. Linia 14. int n0 znak równości n średnik. Linia 15. int y znak równości 0 przecinek x znak równości 1 średnik. Linia 17. while otwórz nawias okrągły a zamknij nawias ostrokątny 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. int q znak równości a prawy ukośnik n średnik. Linia 19. int t znak równości n średnik. Linia 21. n znak równości a procent n średnik. Linia 22. a znak równości t średnik. Linia 23. t znak równości y średnik. Linia 25. y znak równości x minus q asterysk y średnik. Linia 26. x znak równości t średnik. Linia 27. zamknij nawias klamrowy. Linia 29. prawy ukośnik prawy ukośnik x musi być dodatnie. Linia 30. if otwórz nawias okrągły x otwórz nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 31. x plus znak równości n0 średnik. Linia 32. zamknij nawias klamrowy. Linia 34. return x średnik. Linia 35. zamknij nawias klamrowy.

// znalezienie odwrotności modulo metodą naiwną
static int odwrotnosc_modulo_naiwnie(int a, int n) {
	a = a % n;
	for (int x = 1; x <= n - 1; x++) {
		if ((a * x) % n == 1) {
			return x;
		}
	}
    return 1;
}

// znalezienie odwrotności modulo algorytmem Euklidesa
static int odwrotnosc_modulo_euklides(int a, int n) {
	int n0 = n;
	int y = 0, x = 1;

	while (a > 1) {
		int q = a / n;
		int t = n;

		n = a % n;
		a = t;
		t = y;

		y = x - q * y;
		x = t;
	}

	// x musi być dodatnie
	if (x < 0) {
		x += n0;
	}

	return x;
}

Po wyznaczeniu wartości liczby d, należy jeszcze sprawdzić, czy różni się ona od liczby e. Nie powinniśmy dopuścić do sytuacji, gdy klucz publiczny będzie taki sam jak prywatny. Aby kod zachował spójność, napiszmy funkcję sprawdz_d(), która zweryfikuje, czy d != e.

static boolean sprawdz_d(int d, int e) {
	return d != e;
}

Utwórzmy funkcję główną programu, w której zainicjujemy zmienne p oraz q, obliczymy ich iloczyn, wartość funkcji Eulerafunkcja Eulerafunkcji Eulera, a także wybierzemy wykładnik publiczny oraz utworzymy klucz publiczny i prywatny.

Linia 1. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 2. int p znak równości 13 przecinek q znak równości 11 średnik. Linia 3. int n znak równości p asterysk q średnik. Linia 4. int fi znak równości otwórz nawias okrągły p minus 1 zamknij nawias okrągły asterysk otwórz nawias okrągły q minus 1 zamknij nawias okrągły średnik prawy ukośnik prawy ukośnik obliczamy funkcję Eulera. Linia 6. int e znak równości 7 średnik. Linia 7. if otwórz nawias okrągły wykrzyknik sprawdz podkreślnik e otwórz nawias okrągły e przecinek fi zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy prawy ukośnik prawy ukośnik sprawdzenie czy e jest względnie pierwsza z fi. Linia 8. System kropka out kropka println otwórz nawias okrągły cudzysłów Nieprawidłowy wykładnik publiczny cudzysłów zamknij nawias okrągły średnik. Linia 9. System kropka exit otwórz nawias okrągły 0 zamknij nawias okrągły średnik. Linia 10. zamknij nawias klamrowy. Linia 11. prawy ukośnik prawy ukośnik klucz publiczny to para liczb otwórz nawias okrągły e przecinek n zamknij nawias okrągły. Linia 12. int otwórz nawias kwadratowy zamknij nawias kwadratowy klucz podkreślnik publiczny znak równości otwórz nawias klamrowy e przecinek n zamknij nawias klamrowy średnik. Linia 13. System kropka out kropka println otwórz nawias okrągły cudzysłów klucz publiczny dwukropek otwórz nawias okrągły cudzysłów plus e plus cudzysłów przecinek cudzysłów plus n plus cudzysłów zamknij nawias okrągły cudzysłów zamknij nawias okrągły średnik. Linia 15. int d znak równości odwrotnosc podkreślnik modulo otwórz nawias okrągły e przecinek fi zamknij nawias okrągły średnik. Linia 16. if otwórz nawias okrągły wykrzyknik sprawdz podkreślnik d otwórz nawias okrągły d przecinek e zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy prawy ukośnik prawy ukośnik sprawdzenie czy d jest różne od e. Linia 17. System kropka out kropka println otwórz nawias okrągły cudzysłów Wykładnik publiczny jest taki sam jak prywatny cudzysłów zamknij nawias okrągły średnik. Linia 18. System kropka exit otwórz nawias okrągły 0 zamknij nawias okrągły średnik. Linia 19. zamknij nawias klamrowy. Linia 20. prawy ukośnik prawy ukośnik klucz prywatny to para liczb otwórz nawias okrągły d przecinek n zamknij nawias okrągły średnik. Linia 21. int otwórz nawias kwadratowy zamknij nawias kwadratowy klucz podkreślnik prywatny znak równości otwórz nawias klamrowy d przecinek n zamknij nawias klamrowy średnik. Linia 22. System kropka out kropka println otwórz nawias okrągły cudzysłów klucz prywatny dwukropek otwórz nawias okrągły cudzysłów plus d plus cudzysłów przecinek cudzysłów plus n plus cudzysłów zamknij nawias okrągły cudzysłów zamknij nawias okrągły średnik. Linia 23. zamknij nawias klamrowy.

public static void main(String[] args) {
	int p = 13, q = 11;
	int n = p * q;
	int fi = (p - 1) * (q - 1); // obliczamy funkcję Eulera

	int e = 7;
	if (!sprawdz_e(e, fi)) { // sprawdzenie czy e jest względnie pierwsza z fi
		System.out.println("Nieprawidłowy wykładnik publiczny");
		System.exit(0);
	}
	// klucz publiczny to para liczb (e, n)
	int[] klucz_publiczny = {e, n};
	System.out.println("klucz publiczny: (" + e + ", " + n + ")");

	int d = odwrotnosc_modulo(e, fi);
	if (!sprawdz_d(d, e)) { // sprawdzenie czy d jest różne od e
		System.out.println("Wykładnik publiczny jest taki sam jak prywatny");
		System.exit(0);
	}
	// klucz prywatny to para liczb (d, n);
	int[] klucz_prywatny = {d, n};
	System.out.println("klucz prywatny: (" + d + ", " + n + ")");
}

Całość kodu prezentuje się następująco:

Linia 1. public class Main otwórz nawias klamrowy. Linia 2. prawy ukośnik prawy ukośnik znalezienie odwrotności modulo algorytmem Euklidesa. Linia 3. static int odwrotnosc podkreślnik modulo otwórz nawias okrągły int a przecinek int n zamknij nawias okrągły otwórz nawias klamrowy. Linia 4. int n0 znak równości n średnik. Linia 5. int y znak równości 0 przecinek x znak równości 1 średnik. Linia 7. while otwórz nawias okrągły a zamknij nawias ostrokątny 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. int q znak równości a prawy ukośnik n średnik. Linia 9. int t znak równości n średnik. Linia 11. n znak równości a procent n średnik. Linia 12. a znak równości t średnik. Linia 13. t znak równości y średnik. Linia 15. y znak równości x minus q asterysk y średnik. Linia 16. x znak równości t średnik. Linia 17. zamknij nawias klamrowy. Linia 19. prawy ukośnik prawy ukośnik x musi być dodatnie. Linia 20. if otwórz nawias okrągły x otwórz nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. x plus znak równości n0 średnik. Linia 22. zamknij nawias klamrowy. Linia 24. return x średnik. Linia 25. zamknij nawias klamrowy. Linia 27. static int nwd otwórz nawias okrągły int a przecinek int b zamknij nawias okrągły otwórz nawias klamrowy. Linia 28. if otwórz nawias okrągły b znak równości znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 29. return a średnik. Linia 30. zamknij nawias klamrowy. Linia 31. return nwd otwórz nawias okrągły b przecinek a procent b zamknij nawias okrągły średnik. Linia 32. zamknij nawias klamrowy. Linia 34. static boolean sprawdz podkreślnik e otwórz nawias okrągły int e przecinek int fi zamknij nawias okrągły otwórz nawias klamrowy. Linia 35. return nwd otwórz nawias okrągły e przecinek fi zamknij nawias okrągły znak równości znak równości 1 średnik. Linia 36. zamknij nawias klamrowy. Linia 38. static boolean sprawdz podkreślnik d otwórz nawias okrągły int d przecinek int e zamknij nawias okrągły otwórz nawias klamrowy. Linia 39. return d wykrzyknik znak równości e średnik. Linia 40. zamknij nawias klamrowy. Linia 42. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 43. int p znak równości 13 przecinek q znak równości 11 średnik. Linia 44. int n znak równości p asterysk q średnik. Linia 45. int fi znak równości otwórz nawias okrągły p minus 1 zamknij nawias okrągły asterysk otwórz nawias okrągły q minus 1 zamknij nawias okrągły średnik prawy ukośnik prawy ukośnik obliczamy funkcję Eulera. Linia 47. int e znak równości 7 średnik. Linia 48. if otwórz nawias okrągły wykrzyknik sprawdz podkreślnik e otwórz nawias okrągły e przecinek fi zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy prawy ukośnik prawy ukośnik sprawdzenie czy e jest względnie pierwsza z fi. Linia 49. System kropka out kropka println otwórz nawias okrągły cudzysłów Nieprawidłowy wykładnik publiczny cudzysłów zamknij nawias okrągły średnik. Linia 50. System kropka exit otwórz nawias okrągły 0 zamknij nawias okrągły średnik. Linia 51. zamknij nawias klamrowy. Linia 52. prawy ukośnik prawy ukośnik klucz publiczny to para liczb otwórz nawias okrągły e przecinek n zamknij nawias okrągły. Linia 53. int otwórz nawias kwadratowy zamknij nawias kwadratowy klucz podkreślnik publiczny znak równości otwórz nawias klamrowy e przecinek n zamknij nawias klamrowy średnik. Linia 54. System kropka out kropka println otwórz nawias okrągły cudzysłów klucz publiczny dwukropek otwórz nawias okrągły cudzysłów plus e plus cudzysłów przecinek cudzysłów plus n plus cudzysłów zamknij nawias okrągły cudzysłów zamknij nawias okrągły średnik. Linia 56. int d znak równości odwrotnosc podkreślnik modulo otwórz nawias okrągły e przecinek fi zamknij nawias okrągły średnik. Linia 57. if otwórz nawias okrągły wykrzyknik sprawdz podkreślnik d otwórz nawias okrągły d przecinek e zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy prawy ukośnik prawy ukośnik sprawdzenie czy d jest różne od e. Linia 58. System kropka out kropka println otwórz nawias okrągły cudzysłów Wykładnik publiczny jest taki sam jak prywatny cudzysłów zamknij nawias okrągły średnik. Linia 59. System kropka exit otwórz nawias okrągły 0 zamknij nawias okrągły średnik. Linia 60. zamknij nawias klamrowy. Linia 61. prawy ukośnik prawy ukośnik klucz prywatny to para liczb otwórz nawias okrągły d przecinek n zamknij nawias okrągły średnik. Linia 62. int otwórz nawias kwadratowy zamknij nawias kwadratowy klucz podkreślnik prywatny znak równości otwórz nawias klamrowy d przecinek n zamknij nawias klamrowy średnik. Linia 63. System kropka out kropka println otwórz nawias okrągły cudzysłów klucz prywatny dwukropek otwórz nawias okrągły cudzysłów plus d plus cudzysłów przecinek cudzysłów plus n plus cudzysłów zamknij nawias okrągły cudzysłów zamknij nawias okrągły średnik. Linia 64. zamknij nawias klamrowy. Linia 65. zamknij nawias klamrowy.

public class Main {
	// znalezienie odwrotności modulo algorytmem Euklidesa
	static int odwrotnosc_modulo(int a, int n) {
		int n0 = n;
		int y = 0, x = 1;

		while (a > 1) {
			int q = a / n;
			int t = n;

			n = a % n;
			a = t;
			t = y;

			y = x - q * y;
			x = t;
		}

		// x musi być dodatnie
		if (x < 0) {
			x += n0;
		}

		return x;
	}

	static int nwd(int a, int b) {
		if (b == 0) {
			return a;
		}
		return nwd(b, a % b);
	}

	static boolean sprawdz_e(int e, int fi) {
		return nwd(e, fi) == 1;
	}

	static boolean sprawdz_d(int d, int e) {
		return d != e;
	}

	public static void main(String[] args) {
		int p = 13, q = 11;
		int n = p * q;
		int fi = (p - 1) * (q - 1); // obliczamy funkcję Eulera

		int e = 7;
		if (!sprawdz_e(e, fi)) { // sprawdzenie czy e jest względnie pierwsza z fi
			System.out.println("Nieprawidłowy wykładnik publiczny");
			System.exit(0);
		}
		// klucz publiczny to para liczb (e, n)
		int[] klucz_publiczny = {e, n};
		System.out.println("klucz publiczny: (" + e + ", " + n + ")");

		int d = odwrotnosc_modulo(e, fi);
		if (!sprawdz_d(d, e)) { // sprawdzenie czy d jest różne od e
			System.out.println("Wykładnik publiczny jest taki sam jak prywatny");
			System.exit(0);
		}
		// klucz prywatny to para liczb (d, n);
		int[] klucz_prywatny = {d, n};
		System.out.println("klucz prywatny: (" + d + ", " + n + ")");
	}
}

Uruchomienie programu skutkuje wypisaniem na ekran następujących wyników:

klucz publiczny: (7, 143)
klucz prywatny: (103, 143)

Szyfrowanie i odszyfrowywanie

Przejdźmy do szyfrowania przykładowej wiadomości. Przekształcanie niezaszyfrowanej liczby t do postaci zaszyfrowanej liczby c wymaga użycia klucza publicznego (e, n). Obowiązuje zasada:

c = t^{e} mod n

Chcąc odszyfrować liczbę c do postaci niezaszyfrowanej liczby t, należy użyć klucza prywatnego (d, n) oraz wzoru:

t = c^{d} mod n

W obu sytuacjach przyda nam się funkcja realizująca potęgowanie modulo. W tym przypadku możemy posłużyć się metodą naiwną lub optymalnym algorytmem szybkiego potęgowaniapotęgowanie szybkieszybkiego potęgowania. Zaimplementuj wybraną przez siebie opcję.

Linia 1. prawy ukośnik prawy ukośnik funkcja obliczająca potęgowanie modulo metodą naiwną. Linia 2. static int potegowanie podkreślnik modulo podkreślnik naiwne otwórz nawias okrągły int a przecinek int b przecinek int n zamknij nawias okrągły otwórz nawias klamrowy. Linia 3. int wynik znak równości 1 średnik. Linia 4. a znak równości a procent n średnik. Linia 6. if otwórz nawias okrągły a znak równości znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. return 0 średnik. Linia 8. zamknij nawias klamrowy. Linia 10. while otwórz nawias okrągły b zamknij nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 11. wynik znak równości otwórz nawias okrągły wynik asterysk a zamknij nawias okrągły procent n średnik. Linia 12. minus minus b średnik. Linia 13. zamknij nawias klamrowy. Linia 15. return wynik średnik. Linia 16. zamknij nawias klamrowy. Linia 18. prawy ukośnik prawy ukośnik funkcja obliczająca potęgowanie modulo algorytmem szybkiego potęgowania. Linia 19. static int potegowanie podkreślnik modulo podkreślnik szybkie otwórz nawias okrągły int a przecinek int b przecinek int n zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. int wynik znak równości 1 średnik. Linia 21. a znak równości a procent n średnik. Linia 23. if otwórz nawias okrągły a znak równości znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 24. return 0 średnik. Linia 25. zamknij nawias klamrowy. Linia 27. while otwórz nawias okrągły b zamknij nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 28. if otwórz nawias okrągły b procent 2 znak równości znak równości 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 29. wynik znak równości wynik asterysk a procent n średnik. Linia 30. zamknij nawias klamrowy. Linia 32. b prawy ukośnik znak równości 2 średnik. Linia 33. a znak równości otwórz nawias okrągły a asterysk a zamknij nawias okrągły procent n średnik. Linia 34. zamknij nawias klamrowy. Linia 36. return wynik średnik. Linia 37. zamknij nawias klamrowy.

// funkcja obliczająca potęgowanie modulo metodą naiwną
static int potegowanie_modulo_naiwne(int a, int b, int n) {
	int wynik = 1;
	a = a % n;

	if (a == 0) {
		return 0;
	}

	while (b > 0) {
		wynik = (wynik * a) % n;
		--b;
	}

	return wynik;
}

// funkcja obliczająca potęgowanie modulo algorytmem szybkiego potęgowania
static int potegowanie_modulo_szybkie(int a, int b, int n) {
	int wynik = 1;
	a = a % n;

	if (a == 0) {
		return 0;
	}

	while (b > 0) {
		if (b % 2 == 1) {
			wynik = wynik * a % n;
		}

		b /= 2;
		a = (a * a) % n;
	}

	return wynik;
}

Po zaimplementowaniu potęgowania modulo możemy już zrealizować szyfrowanie oraz deszyfrowanie liczby za pomocą dwóch funkcji:

static int szyfruj(int t, int[] klucz_publiczny) {
	return potegowanie_modulo(t, klucz_publiczny[0], klucz_publiczny[1]);
}

static int deszyfruj(int c, int[] klucz_prywatny) {
	return potegowanie_modulo(c, klucz_prywatny[0], klucz_prywatny[1]);
}

Zwróćmy uwagę, że szyfrowana liczba nie może być większa od n, ponieważ wówczas przy odszyfrowywaniu otrzymamy jej resztę z dzielenia przez n, a nie pierwotną wartość.

Oto przykład szyfrowania oraz deszyfrowania liczby 123 za pomocą utworzonych wcześniej kluczy:

Linia 1. public class Main otwórz nawias klamrowy. Linia 2. static int odwrotnosc podkreślnik modulo otwórz nawias okrągły int a przecinek int n zamknij nawias okrągły otwórz nawias klamrowy. Linia 3. int n0 znak równości n średnik. Linia 4. int y znak równości 0 przecinek x znak równości 1 średnik. Linia 6. while otwórz nawias okrągły a zamknij nawias ostrokątny 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. int q znak równości a prawy ukośnik n średnik. Linia 8. int t znak równości n średnik. Linia 10. n znak równości a procent n średnik. Linia 11. a znak równości t średnik. Linia 12. t znak równości y średnik. Linia 14. y znak równości x minus q asterysk y średnik. Linia 15. x znak równości t średnik. Linia 16. zamknij nawias klamrowy. Linia 18. prawy ukośnik prawy ukośnik x musi być dodatnie. Linia 19. if otwórz nawias okrągły x otwórz nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. x plus znak równości n0 średnik. Linia 21. zamknij nawias klamrowy. Linia 23. return x średnik. Linia 24. zamknij nawias klamrowy. Linia 26. static int nwd otwórz nawias okrągły int a przecinek int b zamknij nawias okrągły otwórz nawias klamrowy. Linia 27. if otwórz nawias okrągły b znak równości znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 28. return a średnik. Linia 29. zamknij nawias klamrowy. Linia 30. return nwd otwórz nawias okrągły b przecinek a procent b zamknij nawias okrągły średnik. Linia 31. zamknij nawias klamrowy. Linia 33. static boolean sprawdz podkreślnik e otwórz nawias okrągły int e przecinek int fi zamknij nawias okrągły otwórz nawias klamrowy. Linia 34. return nwd otwórz nawias okrągły e przecinek fi zamknij nawias okrągły znak równości znak równości 1 średnik. Linia 35. zamknij nawias klamrowy. Linia 37. static boolean sprawdz podkreślnik d otwórz nawias okrągły int d przecinek int e zamknij nawias okrągły otwórz nawias klamrowy. Linia 38. return d wykrzyknik znak równości e średnik. Linia 39. zamknij nawias klamrowy. Linia 41. prawy ukośnik prawy ukośnik funkcja obliczająca potęgowanie modulo algorytmem szybkiego potęgowania. Linia 42. static int potegowanie podkreślnik modulo otwórz nawias okrągły int a przecinek int b przecinek int n zamknij nawias okrągły otwórz nawias klamrowy. Linia 43. int wynik znak równości 1 średnik. Linia 44. a znak równości a procent n średnik. Linia 46. if otwórz nawias okrągły a znak równości znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 47. return 0 średnik. Linia 48. zamknij nawias klamrowy. Linia 50. while otwórz nawias okrągły b zamknij nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 51. if otwórz nawias okrągły b procent 2 znak równości znak równości 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 52. wynik znak równości wynik asterysk a procent n średnik. Linia 53. zamknij nawias klamrowy. Linia 55. b prawy ukośnik znak równości 2 średnik. Linia 56. a znak równości otwórz nawias okrągły a asterysk a zamknij nawias okrągły procent n średnik. Linia 57. zamknij nawias klamrowy. Linia 59. return wynik średnik. Linia 60. zamknij nawias klamrowy. Linia 62. static int szyfruj otwórz nawias okrągły int t przecinek int otwórz nawias kwadratowy zamknij nawias kwadratowy klucz podkreślnik publiczny zamknij nawias okrągły otwórz nawias klamrowy. Linia 63. return potegowanie podkreślnik modulo otwórz nawias okrągły t przecinek klucz podkreślnik publiczny otwórz nawias kwadratowy 0 zamknij nawias kwadratowy przecinek klucz podkreślnik publiczny otwórz nawias kwadratowy 1 zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 64. zamknij nawias klamrowy. Linia 66. static int deszyfruj otwórz nawias okrągły int c przecinek int otwórz nawias kwadratowy zamknij nawias kwadratowy klucz podkreślnik prywatny zamknij nawias okrągły otwórz nawias klamrowy. Linia 67. return potegowanie podkreślnik modulo otwórz nawias okrągły c przecinek klucz podkreślnik prywatny otwórz nawias kwadratowy 0 zamknij nawias kwadratowy przecinek klucz podkreślnik prywatny otwórz nawias kwadratowy 1 zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 68. zamknij nawias klamrowy. Linia 70. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 71. int p znak równości 13 przecinek q znak równości 11 średnik. Linia 72. int n znak równości p asterysk q średnik. Linia 73. int fi znak równości otwórz nawias okrągły p minus 1 zamknij nawias okrągły asterysk otwórz nawias okrągły q minus 1 zamknij nawias okrągły średnik prawy ukośnik prawy ukośnik obliczamy funkcję Eulera. Linia 75. int e znak równości 7 średnik. Linia 76. if otwórz nawias okrągły wykrzyknik sprawdz podkreślnik e otwórz nawias okrągły e przecinek fi zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy prawy ukośnik prawy ukośnik sprawdzenie czy e jest względnie pierwsza z fi. Linia 77. System kropka out kropka println otwórz nawias okrągły cudzysłów Nieprawidłowy wykładnik publiczny cudzysłów zamknij nawias okrągły średnik. Linia 78. System kropka exit otwórz nawias okrągły 0 zamknij nawias okrągły średnik. Linia 79. zamknij nawias klamrowy. Linia 80. prawy ukośnik prawy ukośnik klucz publiczny to para liczb otwórz nawias okrągły e przecinek n zamknij nawias okrągły. Linia 81. int otwórz nawias kwadratowy zamknij nawias kwadratowy klucz podkreślnik publiczny znak równości otwórz nawias klamrowy e przecinek n zamknij nawias klamrowy średnik. Linia 82. System kropka out kropka println otwórz nawias okrągły cudzysłów klucz publiczny dwukropek otwórz nawias okrągły cudzysłów plus e plus cudzysłów przecinek cudzysłów plus n plus cudzysłów zamknij nawias okrągły cudzysłów zamknij nawias okrągły średnik. Linia 84. int d znak równości odwrotnosc podkreślnik modulo otwórz nawias okrągły e przecinek fi zamknij nawias okrągły średnik. Linia 85. if otwórz nawias okrągły wykrzyknik sprawdz podkreślnik d otwórz nawias okrągły d przecinek e zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy prawy ukośnik prawy ukośnik sprawdzenie czy d jest różne od e. Linia 86. System kropka out kropka println otwórz nawias okrągły cudzysłów Wykładnik publiczny jest taki sam jak prywatny cudzysłów zamknij nawias okrągły średnik. Linia 87. System kropka exit otwórz nawias okrągły 0 zamknij nawias okrągły średnik. Linia 88. zamknij nawias klamrowy. Linia 89. prawy ukośnik prawy ukośnik klucz prywatny to para liczb otwórz nawias okrągły d przecinek n zamknij nawias okrągły średnik. Linia 90. int otwórz nawias kwadratowy zamknij nawias kwadratowy klucz podkreślnik prywatny znak równości otwórz nawias klamrowy d przecinek n zamknij nawias klamrowy średnik. Linia 91. System kropka out kropka println otwórz nawias okrągły cudzysłów klucz prywatny dwukropek otwórz nawias okrągły cudzysłów plus d plus cudzysłów przecinek cudzysłów plus n plus cudzysłów zamknij nawias okrągły cudzysłów zamknij nawias okrągły średnik. Linia 93. int t znak równości 123 średnik. Linia 94. int c znak równości szyfruj otwórz nawias okrągły t przecinek klucz podkreślnik publiczny zamknij nawias okrągły średnik. Linia 95. int t2 znak równości deszyfruj otwórz nawias okrągły c przecinek klucz podkreślnik prywatny zamknij nawias okrągły średnik. Linia 97. System kropka out kropka println otwórz nawias okrągły cudzysłów Wiadomość przed zaszyfrowaniem dwukropek cudzysłów plus t zamknij nawias okrągły średnik. Linia 98. System kropka out kropka println otwórz nawias okrągły cudzysłów Wiadomość po zaszyfrowaniu dwukropek cudzysłów plus c zamknij nawias okrągły średnik. Linia 99. System kropka out kropka println otwórz nawias okrągły cudzysłów Wiadomość po deszyfrowaniu dwukropek cudzysłów plus t2 zamknij nawias okrągły średnik. Linia 100. zamknij nawias klamrowy. Linia 101. zamknij nawias klamrowy.

public class Main {
	static int odwrotnosc_modulo(int a, int n) {
		int n0 = n;
		int y = 0, x = 1;

		while (a > 1) {
			int q = a / n;
			int t = n;

			n = a % n;
			a = t;
			t = y;

			y = x - q * y;
			x = t;
		}

		// x musi być dodatnie
		if (x < 0) {
			x += n0;
		}

		return x;
	}

	static int nwd(int a, int b) {
		if (b == 0) {
			return a;
		}
		return nwd(b, a % b);
	}

	static boolean sprawdz_e(int e, int fi) {
		return nwd(e, fi) == 1;
	}

	static boolean sprawdz_d(int d, int e) {
		return d != e;
	}

	// funkcja obliczająca potęgowanie modulo algorytmem szybkiego potęgowania
	static int potegowanie_modulo(int a, int b, int n) {
		int wynik = 1;
		a = a % n;

		if (a == 0) {
			return 0;
		}

		while (b > 0) {
			if (b % 2 == 1) {
				wynik = wynik * a % n;
			}

			b /= 2;
			a = (a * a) % n;
		}

		return wynik;
	}

	static int szyfruj(int t, int[] klucz_publiczny) {
		return potegowanie_modulo(t, klucz_publiczny[0], klucz_publiczny[1]);
	}

	static int deszyfruj(int c, int[] klucz_prywatny) {
		return potegowanie_modulo(c, klucz_prywatny[0], klucz_prywatny[1]);
	}

	public static void main(String[] args) {
		int p = 13, q = 11;
		int n = p * q;
		int fi = (p - 1) * (q - 1); // obliczamy funkcję Eulera

		int e = 7;
		if (!sprawdz_e(e, fi)) { // sprawdzenie czy e jest względnie pierwsza z fi
			System.out.println("Nieprawidłowy wykładnik publiczny");
			System.exit(0);
		}
		// klucz publiczny to para liczb (e, n)
		int[] klucz_publiczny = {e, n};
		System.out.println("klucz publiczny: (" + e + ", " + n + ")");

		int d = odwrotnosc_modulo(e, fi);
		if (!sprawdz_d(d, e)) { // sprawdzenie czy d jest różne od e
			System.out.println("Wykładnik publiczny jest taki sam jak prywatny");
			System.exit(0);
		}
		// klucz prywatny to para liczb (d, n);
		int[] klucz_prywatny = {d, n};
		System.out.println("klucz prywatny: (" + d + ", " + n + ")");
    
		int t = 123;
		int c = szyfruj(t, klucz_publiczny);
		int t2 = deszyfruj(c, klucz_prywatny);

		System.out.println("Wiadomość przed zaszyfrowaniem: " + t);
		System.out.println("Wiadomość po zaszyfrowaniu: " + c);
		System.out.println("Wiadomość po deszyfrowaniu: " + t2);
	}
}

Oto rezultat działania przedstawionego programu:

klucz publiczny: (7, 143)
klucz prywatny: (103, 143)
Wiadomość przez zaszyfrowaniem: 123
Wiadomość po zaszyfrowaniu: 7
Wiadomość po deszyfrowaniu: 123

Dla zainteresowanych

W języku Java mamy do dyspozycji klasę BigInteger, dzięki której możemy przeprowadzać obliczenia, wykorzystując liczby przekraczające zakres standardowych zmiennych typu int oraz long.

Dlaczego algorytm RSA jest bezpieczny?

W celu złamania szyfru moglibyśmy posłużyć się rozkładem liczby n na czynniki pierwsze. W tej części e‑materiału udowodnimy, że mając klucz publiczny, możemy bez problemu opracować algorytm, który obliczy klucz prywatny. Algorytm, który rozkłada liczbę na czynniki pierwsze, w języku Java wygląda następująco:

static void rozklad(int n) {
	for (int i = 2; i <= Math.sqrt(n); ++i) {
		while (n % i == 0) {
			System.out.println(i);
			n = n / i;
			if (n == 1) {
				break;
			}
		}
	}
	if (n > 1) {
		System.out.println(n);
	}
}

Polecenie 1

Używając przedstawionej funkcji, sprawdź, czy jesteś w stanie rozłożyć na czynniki pierwsze drugą część klucza publicznego – liczbę n.

Jak się przekonaliśmy, przedstawiony algorytm jest w stanie rozłożyć dowolną liczbę na czynniki pierwsze. Ma on jednak dużą złożoność czasową. Z tego powodu należy wybierać liczby pierwsze odpowiednio duże, aby rozkład ich iloczynu na czynniki pierwsze trwał bardzo długo.

Bezpieczeństwo metody kryptograficznej RSA opiera się zatem na przemnożeniu dwóch tajnych liczb pierwszych, co dla komputerów jest działaniem stosunkowo prostym do wykonania (nawet przy bardzo dużych liczbach), ale praktycznie niemożliwym do odwrócenia w odpowiednio krótkim czasie.

Ważne!

Przy tworzeniu kluczy publicznych oraz prywatnych, a także odszyfrowywaniu wiadomości należy zachować odpowiednią ostrożność. Jeśli mamy dostęp do danych wrażliwych, o których wiemy, że mogą stanowić wartość dla osób trzecich, nie możemy mieć pewności, że nikt nie spróbuje się do nich dostać. W takiej sytuacji należy rozważyć odłączenie komputera od internetu.

Ciekawostka

Niektóre ataki hakerskie nie opierają się na dostępie komputera ofiary do internetu. W $2013$ r. izraelskim naukowcom udało się odczytać wartość klucza prywatnego z komputera, który w danym momencie odszyfrowywał wiadomość zaszyfrowaną metodą RSA, stosując $4096$ -bitowy klucz. Wykorzystano do tego celu mikrofon umieszczony obok komputera. Na podstawie dźwięków generowanych przez procesor hakerzy ustalili wartość klucza prywatnego.

Słownik

funkcja Eulera

funkcja, która do każdej liczby naturalnej przypisuje liczbę liczb, które spełniają dwa warunki: są z nią względnie pierwsze i nie są od niej większe.

odwrotność modulo

liczbę $b$ nazywamy odwrotnością modulo $n$ liczby $a$ , jeżeli spełniona jest zależność:

a \cdot b mod n \equiv 1 mod n

potęgowanie szybkie

algorytm potęgowania o wykładniku naturalnym, o złożoności logarytmicznej

Wprowadzenie

Symulacja interaktywna

Tworzenie klucza publicznego i prywatnego

Szyfrowanie i odszyfrowywanie

Dlaczego algorytm RSA jest bezpieczny?

Słownik