Sprawdź się

Pokaż ćwiczenia:

Ćwiczenie 1

Napisz program obliczający odwrotność modulo z wykorzystaniem rozszerzonego algorytmu Euklidesa. Program ma obliczyć $e \mod euler$ , gdzie $e$ to pierwsza wyznaczona liczba względnie pierwsza z wartością $euler$ , a $euler$ jest równe wartości funkcji Eulera dla dwóch liczb pierwszych: $p$ i $q$ . Program ma zwrócić liczbę będącą wynikiem odwrotności modulo. Wartość $e$ ma spełniać warunek $1 < e < euler$ .

Informacje na temat funkcji Eulera znajdziesz w sekcji „Przeczytaj”.

Program przetestuj dla wartości $p = 17$ i $q = 13$ .

Specyfikacja problemu:

Dane:

p – liczba całkowita dodatnia; wartość jednej z liczb pierwszych potrzebnych do obliczenia odwrotności modulo
q – liczba całkowita dodatnia; wartość drugiej z liczb pierwszych potrzebnych do obliczenia odwrotności modulo

Wynik:

odwrotnosc – liczba naturalna; wyznaczona wartość odwrotności modulo

RLT1tCGLQTOyc

Przykładowe rozwiązanie zadania:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 3. using namespace std średnik. Linia 5. int RozszerzonyEuklides otwórz nawias okrągły int a przecinek int b przecinek int asterysk x przecinek int asterysk y zamknij nawias okrągły. Linia 6. otwórz nawias klamrowy. Linia 7. if otwórz nawias okrągły a znak równości znak równości 0 zamknij nawias okrągły. Linia 8. otwórz nawias klamrowy. Linia 9. asterysk x znak równości 0 przecinek asterysk y znak równości 1 średnik. Linia 10. return b średnik. Linia 11. zamknij nawias klamrowy. Linia 12. int x1 przecinek y1 średnik. Linia 13. int NWD znak równości RozszerzonyEuklides otwórz nawias okrągły b procent a przecinek a przecinek ampersant x1 przecinek ampersant y1 zamknij nawias okrągły średnik. Linia 14. asterysk x znak równości y1 minus otwórz nawias okrągły b prawy ukośnik a zamknij nawias okrągły asterysk x1 średnik. Linia 15. asterysk y znak równości x1 średnik. Linia 16. return NWD średnik. Linia 17. zamknij nawias klamrowy. Linia 19. int odwrotnoscMod otwórz nawias okrągły int a przecinek int b zamknij nawias okrągły. Linia 20. otwórz nawias klamrowy. Linia 21. int x przecinek y średnik. Linia 22. int g znak równości RozszerzonyEuklides otwórz nawias okrągły a przecinek b przecinek ampersant x przecinek ampersant y zamknij nawias okrągły średnik. Linia 23. if otwórz nawias okrągły g wykrzyknik znak równości 1 zamknij nawias okrągły. Linia 24. return minus 1 średnik. Linia 25. else. Linia 26. otwórz nawias klamrowy. Linia 27. int odwrotnosc znak równości otwórz nawias okrągły x procent b plus b zamknij nawias okrągły procent b średnik. Linia 28. return odwrotnosc średnik. Linia 29. zamknij nawias klamrowy. Linia 30. zamknij nawias klamrowy. Linia 32. int main otwórz nawias okrągły zamknij nawias okrągły. Linia 33. otwórz nawias klamrowy. Linia 34. int p znak równości 17 średnik. Linia 35. int q znak równości 13 średnik. Linia 36. int euler 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. Linia 37. int x przecinek y średnik. Linia 38. int e znak równości 1 średnik. Linia 39. do. Linia 40. otwórz nawias klamrowy. Linia 41. e plus plus średnik. Linia 42. zamknij nawias klamrowy while otwórz nawias okrągły RozszerzonyEuklides otwórz nawias okrągły e przecinek euler przecinek ampersant x przecinek ampersant y zamknij nawias okrągły wykrzyknik znak równości 1 zamknij nawias okrągły średnik. Linia 43. int odwrotnosc znak równości odwrotnoscMod otwórz nawias okrągły e przecinek euler zamknij nawias okrągły średnik. Linia 44. cout otwórz nawias ostrokątny otwórz nawias ostrokątny odwrotnosc średnik. Linia 46. return 0 średnik. Linia 47. zamknij nawias klamrowy.

#include <iostream>

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)
		return -1;
	else
	{
		int odwrotnosc = (x % b + b) % b;
		return odwrotnosc;
	}
}

int main()
{
	int p = 17;
	int q = 13;
    int euler = (p-1)*(q-1);
    int x,y;
    int e = 1;
    do
	{
		e++;
	} while (RozszerzonyEuklides(e, euler, &x, &y) != 1);
	int odwrotnosc = odwrotnoscMod(e, euler);
	cout << odwrotnosc;
    
	return 0;
}

Ćwiczenie 2

Napisz program wyznaczający klucz publiczny i klucz prywatny na podstawie podanej pary liczb pierwszych $p$ i $q$ . Uzyskane klucze podaj w formie par $(e, n)$ i $(d, n)$ oddzielonych znakiem nowej linii.

Program przetestuj dla wartości $p = 23$ i $q = 11$ .

Specyfikacja problemu:

Dane:

p – liczba całkowita dodatnia; wartość jednej z liczb pierwszych potrzebnych do wyznaczenia wartości kluczy
q – liczba całkowita dodatnia; wartość drugiej z liczb pierwszych potrzebnych do wyznaczenia wartości kluczy

Wynik:

klucz publiczny i klucz prywatny

R1WckWZs9tkfc

Przykładowe rozwiązanie zadania:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 3. using namespace std średnik. Linia 5. int RozszerzonyEuklides otwórz nawias okrągły int a przecinek int b przecinek int asterysk x przecinek int asterysk y zamknij nawias okrągły. Linia 6. otwórz nawias klamrowy. Linia 7. if otwórz nawias okrągły a znak równości znak równości 0 zamknij nawias okrągły. Linia 8. otwórz nawias klamrowy. Linia 9. asterysk x znak równości 0 przecinek asterysk y znak równości 1 średnik. Linia 10. return b średnik. Linia 11. zamknij nawias klamrowy. Linia 12. int x1 przecinek y1 średnik. Linia 13. int NWD znak równości RozszerzonyEuklides otwórz nawias okrągły b procent a przecinek a przecinek ampersant x1 przecinek ampersant y1 zamknij nawias okrągły średnik. Linia 14. asterysk x znak równości y1 minus otwórz nawias okrągły b prawy ukośnik a zamknij nawias okrągły asterysk x1 średnik. Linia 15. asterysk y znak równości x1 średnik. Linia 16. return NWD średnik. Linia 17. zamknij nawias klamrowy. Linia 19. int odwrotnoscMod otwórz nawias okrągły int a przecinek int b zamknij nawias okrągły. Linia 20. otwórz nawias klamrowy. Linia 21. int x przecinek y średnik. Linia 22. int g znak równości RozszerzonyEuklides otwórz nawias okrągły a przecinek b przecinek ampersant x przecinek ampersant y zamknij nawias okrągły średnik. Linia 23. if otwórz nawias okrągły g wykrzyknik znak równości 1 zamknij nawias okrągły. Linia 24. return minus 1 średnik. Linia 25. else. Linia 26. otwórz nawias klamrowy. Linia 27. int odwrotnosc znak równości otwórz nawias okrągły x procent b plus b zamknij nawias okrągły procent b średnik. Linia 28. return odwrotnosc średnik. Linia 29. zamknij nawias klamrowy. Linia 30. zamknij nawias klamrowy. Linia 32. int main otwórz nawias okrągły zamknij nawias okrągły. Linia 33. otwórz nawias klamrowy. Linia 34. int p znak równości 23 średnik. Linia 35. int q znak równości 11 średnik. Linia 36. int euler 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. Linia 37. int n znak równości p asterysk q średnik. Linia 38. int x przecinek y średnik. Linia 39. int e znak równości 1 średnik. Linia 40. do. Linia 41. otwórz nawias klamrowy. Linia 42. e plus plus średnik. Linia 43. zamknij nawias klamrowy while otwórz nawias okrągły RozszerzonyEuklides otwórz nawias okrągły e przecinek euler przecinek ampersant x przecinek ampersant y zamknij nawias okrągły wykrzyknik znak równości 1 zamknij nawias okrągły średnik. Linia 44. int d znak równości odwrotnoscMod otwórz nawias okrągły e przecinek euler zamknij nawias okrągły średnik. Linia 45. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów otwórz nawias okrągły cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny e otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów przecinek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny n otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów zamknij nawias okrągły cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 46. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów otwórz nawias okrągły cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny d otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów przecinek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny n otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów zamknij nawias okrągły cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 48. return 0 średnik. Linia 49. zamknij nawias klamrowy.

#include <iostream>

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)
		return -1;
	else
	{
		int odwrotnosc = (x % b + b) % b;
		return odwrotnosc;
	}
}

int main()
{
	int p = 23;
	int q = 11;
    int euler = (p-1)*(q-1);
    int n = p * q;
    int x,y;
    int e = 1;
    do
	{
		e++;
	} while (RozszerzonyEuklides(e, euler, &x, &y) != 1);
	int d = odwrotnoscMod(e, euler);
	cout << "(" << e << ", " << n << ")" << endl;
    cout << "(" << d << ", " << n << ")" << endl;
    
    return 0;
}

Ćwiczenie 3

Napisz program pozwalający na zaszyfrowanie i odszyfrowanie podanych wartości liczbowych szyfrem RSA, na podstawie podanych liczb pierwszych $p$ i $q$ . W zadaniu nie używaj funkcji pow().

Program przetestuj dla wartości $p = 23$ i $q = 13$ . Otrzymanymi kluczami zaszyfruj liczbę $72$ i odszyfruj liczbę, której szyfrogram ma postać liczby $75$ .

Specyfikacja problemu:

Dane:

p – liczba całkowita dodatnia; wartość jednej z liczb pierwszych potrzebnych do wyznaczenia wartości kluczy
q – liczba całkowita dodatnia; wartość drugiej z liczb pierwszych potrzebnych do wyznaczenia wartości kluczy
liczbaDoZaszyfrowania – liczba naturalna; liczba do zaszyfrowania kluczem publicznym
szyfrogram – liczba naturalna; wiadomość do odszyfrowania kluczem prywatnym

Wynik:

zaszyfrowana postać liczby liczbaDoZaszyfrowania
odszyfrowana postać szyfrogramu szyfrogram

RZYElRkLaEqeX

Przykładowe rozwiązanie zadania:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. kratka include otwórz nawias ostrokątny cmath zamknij nawias ostrokątny. Linia 4. using namespace std średnik. Linia 6. int RozszerzonyEuklides otwórz nawias okrągły int a przecinek int b przecinek int asterysk x przecinek int asterysk y zamknij nawias okrągły. Linia 7. otwórz nawias klamrowy. Linia 8. if otwórz nawias okrągły a znak równości znak równości 0 zamknij nawias okrągły. Linia 9. otwórz nawias klamrowy. Linia 10. asterysk x znak równości 0 przecinek asterysk y znak równości 1 średnik. Linia 11. return b średnik. Linia 12. zamknij nawias klamrowy. Linia 13. int x1 przecinek y1 średnik. Linia 14. int NWD znak równości RozszerzonyEuklides otwórz nawias okrągły b procent a przecinek a przecinek ampersant x1 przecinek ampersant y1 zamknij nawias okrągły średnik. Linia 15. asterysk x znak równości y1 minus otwórz nawias okrągły b prawy ukośnik a zamknij nawias okrągły asterysk x1 średnik. Linia 16. asterysk y znak równości x1 średnik. Linia 18. return NWD średnik. Linia 19. zamknij nawias klamrowy. Linia 21. int odwrotnoscMod otwórz nawias okrągły int a przecinek int b zamknij nawias okrągły. Linia 22. otwórz nawias klamrowy. Linia 23. int x przecinek y średnik. Linia 24. int g znak równości RozszerzonyEuklides otwórz nawias okrągły a przecinek b przecinek ampersant x przecinek ampersant y zamknij nawias okrągły średnik. Linia 25. if otwórz nawias okrągły g wykrzyknik znak równości 1 zamknij nawias okrągły. Linia 26. return minus 1 średnik. Linia 27. else. Linia 28. otwórz nawias klamrowy. Linia 29. int odwrotnosc znak równości otwórz nawias okrągły x procent b plus b zamknij nawias okrągły procent b średnik. Linia 30. return odwrotnosc średnik. Linia 31. zamknij nawias klamrowy. Linia 32. zamknij nawias klamrowy. Linia 35. unsigned long long szyfrowanieRSA otwórz nawias okrągły int wiadomosc przecinek int e przecinek int n zamknij nawias okrągły. Linia 36. otwórz nawias klamrowy. Linia 37. unsigned long long rezultat znak równości wiadomosc średnik. Linia 38. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny e średnik i plus plus zamknij nawias okrągły. Linia 39. otwórz nawias klamrowy. Linia 40. rezultat znak równości otwórz nawias okrągły rezultat asterysk wiadomosc zamknij nawias okrągły procent n średnik. Linia 41. zamknij nawias klamrowy. Linia 42. return rezultat średnik. Linia 43. zamknij nawias klamrowy. Linia 45. unsigned long long deszyfrowanieRSA otwórz nawias okrągły int szyfrogram przecinek int d przecinek int n zamknij nawias okrągły. Linia 46. otwórz nawias klamrowy. Linia 47. unsigned long long rezultat znak równości szyfrogram średnik. Linia 48. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny d średnik i plus plus zamknij nawias okrągły. Linia 49. otwórz nawias klamrowy. Linia 50. rezultat znak równości otwórz nawias okrągły rezultat asterysk szyfrogram zamknij nawias okrągły procent n średnik. Linia 51. zamknij nawias klamrowy. Linia 52. return rezultat średnik. Linia 53. zamknij nawias klamrowy. Linia 55. int main otwórz nawias okrągły zamknij nawias okrągły. Linia 56. otwórz nawias klamrowy. Linia 57. int p znak równości 23 średnik. Linia 58. int q znak równości 13 średnik. Linia 59. int liczbaDoZaszyfrowania znak równości 72 średnik. Linia 60. int szyfrogram znak równości 75 średnik. Linia 61. int n znak równości p asterysk q średnik. Linia 62. int euler 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. Linia 63. int e znak równości 1 średnik. Linia 64. int pom1 średnik. Linia 65. int pom2 średnik. Linia 66. do. Linia 67. otwórz nawias klamrowy. Linia 68. e plus plus średnik. Linia 69. zamknij nawias klamrowy while otwórz nawias okrągły RozszerzonyEuklides otwórz nawias okrągły e przecinek euler przecinek ampersant pom1 przecinek ampersant pom2 zamknij nawias okrągły wykrzyknik znak równości 1 zamknij nawias okrągły średnik. Linia 70. int d znak równości odwrotnoscMod otwórz nawias okrągły e przecinek euler zamknij nawias okrągły średnik. Linia 71. int zaszyfrowanaWiadomosc znak równości szyfrowanieRSA otwórz nawias okrągły liczbaDoZaszyfrowania przecinek e przecinek n zamknij nawias okrągły średnik. Linia 72. int odszyfrowanaWiadomosc znak równości deszyfrowanieRSA otwórz nawias okrągły szyfrogram przecinek d przecinek n zamknij nawias okrągły średnik. Linia 73. cout otwórz nawias ostrokątny otwórz nawias ostrokątny zaszyfrowanaWiadomosc otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 74. cout otwórz nawias ostrokątny otwórz nawias ostrokątny odszyfrowanaWiadomosc otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 76. return 0 średnik. Linia 77. zamknij nawias klamrowy.

#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)
		return -1;
	else
	{
		int odwrotnosc = (x % b + b) % b;
		return odwrotnosc;
	}
}


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;
}

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;
}

int main()
{
	int p = 23;
	int q = 13;
	int liczbaDoZaszyfrowania = 72;
	int szyfrogram = 75;
	int n = p * q;
	int euler =  (p - 1) * (q - 1);
	int e = 1;
	int pom1;
	int pom2;
	do 
	{
		e++;
	} while (RozszerzonyEuklides(e, euler, &pom1, &pom2) != 1);
	int d = odwrotnoscMod(e, euler);
	int zaszyfrowanaWiadomosc = szyfrowanieRSA(liczbaDoZaszyfrowania, e, n);
    int odszyfrowanaWiadomosc = deszyfrowanieRSA(szyfrogram, d, n);
    cout << zaszyfrowanaWiadomosc << endl;
	cout << odszyfrowanaWiadomosc << endl;
    
	return 0;
}

Przeczytaj

Dla nauczyciela