Algorytm RSA jest algorytmem kryptografii asymetrycznej. Asymetryczny faktycznie oznacza, że działa na dwóch różnych klawiszach, tj. Klucz publiczny I Prywatny klucz. Jak sama nazwa wskazuje, klucz publiczny jest nadawany każdemu, a klucz prywatny jest prywatny.
nazwa użytkownika
Przykład kryptografii asymetrycznej:
- Klient (na przykład przeglądarka) wysyła swój klucz publiczny do serwera i żąda pewnych danych.
- Serwer szyfruje dane za pomocą klucza publicznego klienta i wysyła zaszyfrowane dane.
- Klient otrzymuje te dane i odszyfrowuje je.
Ponieważ jest to asymetryczne, nikt inny poza przeglądarką nie może odszyfrować danych, nawet jeśli osoba trzecia posiada klucz publiczny przeglądarki.
Pomysł! Idea RSA opiera się na fakcie, że dużą liczbę całkowitą trudno jest rozłożyć na czynniki. Klucz publiczny składa się z dwóch liczb, z których jedna jest mnożeniem dwóch dużych liczb pierwszych. Klucz prywatny również pochodzi z tych samych dwóch liczb pierwszych. Jeśli więc ktoś może rozłożyć na czynniki dużą liczbę, klucz prywatny zostanie naruszony. Dlatego siła szyfrowania całkowicie zależy od rozmiaru klucza, a jeśli podwoimy lub potroimy rozmiar klucza, siła szyfrowania wzrośnie wykładniczo. Klucze RSA mogą mieć zazwyczaj długość 1024 lub 2048 bitów, ale eksperci uważają, że klucze 1024-bitowe mogą w najbliższej przyszłości zostać złamane. Jednak na razie wydaje się to zadaniem niewykonalnym.
Poznajmy mechanizm algorytmu RSA:>> Generowanie klucza publicznego:
Select two prime no's. Suppose P = 53 and Q = 59. Now First part of the Public key : n = P*Q = 3127. We also need a small exponent say e : But e Must be An integer. Not be a factor of Φ(n). 1 Φ(n) [Φ(n) is discussed below],>> Generowanie klucza prywatnego: Musimy obliczyć Φ(n): Tak, że Φ(n) = (P-1)(Q-1) więc, Φ(n) = 3016 Teraz obliczmy klucz prywatny, d : d = (k *Φ(n) + 1) / e dla pewnej liczby całkowitej k Dla k = 2 wartość d wynosi 2011. Teraz jesteśmy gotowi z naszym – Kluczem Publicznym ( n = 3127 i e = 3) i Kluczem Prywatnym (d = 2011 ) Teraz zaszyfrujemy HI : Zamień litery na liczby : H = 8 i I = 9 W ten sposób zaszyfrowane dane c = (89 e )mod n W ten sposób nasze zaszyfrowane dane wyniosą 1394 Teraz odszyfrujemy 1394 : Odszyfrowane dane = (c d )mod n Zatem nasze zaszyfrowane dane wynoszą 89 8 = H i I = 9, tj. 'HI'. Poniżej znajduje się implementacja algorytmu RSA dla Metody 1: Szyfrowanie i deszyfrowanie małych wartości liczbowych: C++ // Program C dla algorytmu asymetrycznego kryptograficznego // RSA. W celach demonstracyjnych wartości są // stosunkowo małe w porównaniu z praktycznym // zastosowaniem #include using namespace std; // Zwraca gcd z a i b int gcd(int a, int h) { int temp; podczas gdy (1) { temp = a % h; if (temp == 0) zwróć h; za = godz; h = temperatura; } } // Kod demonstrujący algorytm RSA int main() { // Dwie losowe liczby pierwsze double p = 3; podwójne q = 7; // Pierwsza część klucza publicznego: double n = p * q; // Znalezienie innej części klucza publicznego. // e oznacza szyfrowanie podwójne e = 2; podwójne phi = (p - 1) * (q - 1); while (e // e musi być liczbą pierwszą phi i // mniejszą niż phi. if (gcd(e, phi) == 1) break; else e++; } // Klucz prywatny (d oznacza deszyfrowanie) // wybierając d tak, aby spełniało // d*e = 1 + k * totient int k = 2; // Wartość stała double d = (1 + (k * phi)) / e // Wiadomość do zaszyfrowania double msg = 12; printf('Dane wiadomości = %lf', msg); // Szyfrowanie c = (msg ^ e) % n double c = pow(msg, e); c = fmod(c, n); ('
Zaszyfrowane dane = %lf', c); // Odszyfrowanie m = (c ^ d) % n double m = pow(c, d); m = fmod(m, n);
Wysłano oryginalną wiadomość = %lf', m); return 0 } // Ten kod został napisany przez Akash Sharan. Java /*pakiet dowolny //nie wpisuj tutaj nazwy pakietu */ import java.io.*; java.math.*; import java.util.*; /* * Program Java dla asymetrycznego algorytmu kryptograficznego RSA * W celach demonstracyjnych wartości są * stosunkowo małe w porównaniu z praktycznym zastosowaniem */ public class GFG { public static double gcd(double a). , double h) { /* * Ta funkcja zwraca gcd lub największy wspólny * dzielnik */ double temp; while (true) { temp = a % h; if (temp == 0) zwróć h; za = godz; h = temperatura; } } public static void main(String[] args) { double p = 3; podwójne q = 7; // Przechowuje pierwszą część klucza publicznego: double n = p * q; // Znalezienie drugiej części klucza publicznego. // double e oznacza szyfrowanie double e = 2; podwójne phi = (p - 1) * (q - 1); while (e /* * e musi być liczbą pierwszą phi i * mniejszą niż phi. */ if (gcd(e, phi) == 1) break; else e++; } int k = 2; // Wartość stała double d = (1 + (k * phi)) / e; // Wiadomość do zaszyfrowania double msg = 12; System.out.println('Dane wiadomości = ' + msg); ^ e) % n double c = Math.pow(msg, e); c = c % n; System.out.println('Zaszyfrowane dane = ' + c); % n double m = Math.pow(c, d); m = m % n; System.out.println('Wysłano oryginalną wiadomość = ' + m } } // Ten kod został napisany przez Pranay Arora. Python3 # Python dla asymetrycznego algorytmu kryptograficznego RSA # Dla demonstracji wartości są # stosunkowo małe w porównaniu z praktyczną aplikacją import math def gcd(a, h): temp = 0 while(1): temp = a % h if (temp == 0): powrót h a = h h = temp p = 3 q = 7 n = p*q e = 2 phi = (p-1)*(q-1) while (e # e musi być liczbą pierwszą współrzędną phi i # mniejszą niż phi. if(gcd(e, phi) == 1): break else: e = e+1 # Klucz prywatny (d oznacza deszyfrowanie) # wybieranie d w taki sposób, aby spełniało # d*e = 1 + k * totient k = 2 d = (1 + (k*phi))/e # Wiadomość do zaszyfrowania msg = 12.0 print('Dane wiadomości = ', msg) # Szyfrowanie c = (msg ^ e) % n c = pow( msg, e) c = math.fmod(c, n) print('Zaszyfrowane dane = ', c) # Deszyfrowanie m = (c ^ d) % n m = pow(c, d) m = math.fmod( m, n) print('Wysłano oryginalną wiadomość = ', m) # Ten kod został napisany przez Pranay Arora. C# /* * Program w C# dla asymetrycznego algorytmu kryptograficznego RSA. * W celach demonstracyjnych wartości są * stosunkowo małe w porównaniu z praktycznym zastosowaniem */ przy użyciu systemu; public class GFG { public static double gcd(double a, double h) { /* * Ta funkcja zwraca gcd lub największy wspólny * dzielnik */ double temp; while (true) { temp = a % h; if (temp == 0) zwróć h; za = godz; h = temperatura; } } statyczny void Main() { double p = 3; podwójne q = 7; // Przechowuje pierwszą część klucza publicznego: double n = p * q; // Znalezienie drugiej części klucza publicznego. // double e oznacza szyfrowanie double e = 2; podwójne phi = (p - 1) * (q - 1); while (e /* * e musi być liczbą pierwszą phi i * mniejszą niż phi. */ if (gcd(e, phi) == 1) break; else e++; } int k = 2; // Wartość stała double d = (1 + (k * phi)) / e; // Wiadomość do zaszyfrowania double msg = 12; Console.WriteLine('Dane wiadomości = ' + String.Format('{0:F6} ', msg)); // Szyfrowanie c = (msg ^ e) % n double c = Math.Pow(msg, e); c = c % n; Console.WriteLine('Zaszyfrowane dane = ' + String. Format('{0:F6}', c)); // Deszyfrowanie m = (c ^ d) % n double m = Math.Pow(c, d); 'Oryginalna wiadomość wysłana = ' + String.Format('{0:F6}', m)); } } // Ten kod został napisany przez Pranay Arora w języku JavaScript //GFG //Kod JavaScript dla tego podejścia funkcja gcd(a, h) { /* * Ta funkcja zwraca gcd lub największy wspólny * dzielnik */ let temp; while (true) { temp = a % h; if (temp == 0) return h; ; h = temp; } } niech p = 3; niech q = 7; // Przechowuje pierwszą część klucza publicznego: niech n = p * q; // Znalezienie drugiej części klucza publicznego. // e oznacza szyfrowanie let e = 2; niech phi = (p - 1) * (q - 1); while (e /* * e musi być liczbą pierwszą phi i * mniejszą niż phi. */ if (gcd(e, phi) == 1) break; else e++; } let k = 2; // Wartość stała let d = (1 + (k * phi)) / e; // Wiadomość do zaszyfrowania let msg = 12; console.log('Dane wiadomości = ' + msg); // Szyfrowanie c = (msg ^ e ) % n let c = Math.pow(msg, e); c = c % n; console.log('Zaszyfrowane dane = ' + c); // Deszyfrowanie m = (c ^ d) % n let m = Math.pow(c, d); m = m % n; console.log('Wysłano oryginalną wiadomość = ' + m); //Ten kod jest zapisywany przez komunikat wyjściowy Sundaram data = 12,000000 Zaszyfrowane dane = 3,000000 Oryginał Wysłana wiadomość = 12,000000 Metoda 2: Szyfrowanie i deszyfrowanie wiadomości tekstowych zawierających litery i cyfry przy użyciu ich wartości ASCII: C++ #include przy użyciu zestawu przestrzeni nazw std; główny; // zbiór będzie zbiorem liczb pierwszych, // gdzie możemy wybrać losowe liczby pierwsze p i q int public_key; int klucz_prywatny; int n; // uruchomimy funkcję tylko raz, aby wypełnić zbiór // liczb pierwszych void primefiller() { // metoda użyta do wypełnienia zbioru liczb pierwszych to seive of // eratostenes (metoda zbierania liczb pierwszych) wektor seive(250, prawda); seive[0] = fałsz; seive[1] = fałsz; for (int i = 2; tj<250; i++) { for (int j = i * 2; j <250; j += i) { seive[j] = false; } } // filling the prime numbers for (int i = 0; i if (seive[i]) prime.insert(i); } } // picking a random prime number and erasing that prime // number from list because p!=q int pickrandomprime() { int k = rand() % prime.size(); auto it = prime.begin(); while (k--) it++; int ret = *it; prime.erase(it); return ret; } void setkeys() { int prime1 = pickrandomprime(); // first prime number int prime2 = pickrandomprime(); // second prime number // to check the prime numbers selected // cout< n = prime1 * prime2; int fi = (prime1 - 1) * (prime2 - 1); int e = 2; while (1) { if (__gcd(e, fi) == 1) break; e++; } // d = (k*Φ(n) + 1) / e for some integer k public_key = e; int d = 2; while (1) { if ((d * e) % fi == 1) break; d++; } private_key = d; } // to encrypt the given number long long int encrypt(double message) { int e = public_key; long long int encrpyted_text = 1; while (e--) { encrpyted_text *= message; encrpyted_text %= n; } return encrpyted_text; } // to decrypt the given number long long int decrypt(int encrpyted_text) { int d = private_key; long long int decrypted = 1; while (d--) { decrypted *= encrpyted_text; decrypted %= n; } return decrypted; } // first converting each character to its ASCII value and // then encoding it then decoding the number to get the // ASCII and converting it to character vector koder(wiadomość ciągu) {wektor formularz; // wywołanie funkcji szyfrującej w funkcji kodowania dla (auto& letter : Message) form.push_back(encrypt((int)letter)); formularz zwrotu; } dekoder ciągów (vector zakodowane) { ciąg s; // wywołanie funkcji deszyfrującej funkcja dekodowania for (auto& num : encoded) s += decrypt(num); zwroty; } int main() { wypełniacz(); setkeys(); string message = 'Wiadomość testowa'; // usuń komentarz poniżej, aby wprowadzić dane ręcznie // cout<<'enter the message
';getline(cin,message); // calling the encoding function vector coded = koder(wiadomość); cout<< 'Initial message:
' << message; cout << '
The encoded message(encrypted by public ' 'key)
'; for (auto& p : coded) cout << p; cout << '
The decoded message(decrypted by private ' 'key)
'; cout << decoder(coded) << endl; return 0; } Java import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Random; public class GFG { private static HashSet prime = new HashSet(); private static Integer public_key = null; private static Integer private_key = null; private static Integer n = null; private static Random random = new Random(); public static void main(String[] args) { primeFiller(); setKeys(); String message = 'Test Message'; // Uncomment below for manual input // System.out.println('Enter the message:'); // message = new Scanner(System.in).nextLine(); List coded = encoder(message); System.out.println('Initial message:'); System.out.println(message); System.out.println( '
The encoded message (encrypted by public key)
'); System.out.println( String.join('', coded.stream() .map(Object::toString) .toArray(String[] ::new))); System.out.println( '
The decoded message (decrypted by public key)
'); System.out.println(decoder(coded)); } public static void primeFiller() { boolean[] sieve = new boolean[250]; for (int i = 0; i <250; i++) { sieve[i] = true; } sieve[0] = false; sieve[1] = false; for (int i = 2; i <250; i++) { for (int j = i * 2; j <250; j += i) { sieve[j] = false; } } for (int i = 0; i if (sieve[i]) { prime.add(i); } } } public static int pickRandomPrime() { int k = random.nextInt(prime.size()); List primeList = new ArrayList(prime); int ret = primeList.get(k); prime.remove(ret); return ret; } public static void setKeys() { int prime1 = pickRandomPrime(); int prime2 = pickRandomPrime(); n = prime1 * prime2; int fi = (prime1 - 1) * (prime2 - 1); int e = 2; while (true) { if (gcd(e, fi) == 1) { break; } e += 1; } public_key = e; int d = 2; while (true) { if ((d * e) % fi == 1) { break; } d += 1; } private_key = d; } public static int encrypt(int message) { int e = public_key; int encrypted_text = 1; while (e>0) { zaszyfrowany_tekst *= wiadomość; zaszyfrowany_tekst %= n; mi -= 1; } zwróć zaszyfrowany_tekst; } public static int deszyfrowanie(int szyfrowany_tekst) { int d = klucz_prywatny; int odszyfrowany = 1; while (d> 0) { odszyfrowany *= zaszyfrowany_tekst; odszyfrowane%= n; d -= 1; } powrót odszyfrowany; } public static int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); } public static List encoder(String Message) { Lista zakodowana = nowa ArrayList(); for (litera znakowa: wiadomość.toCharArray()) { encoded.add(encrypt((int)letter)); } powrót zakodowany; } publiczny statyczny dekoder ciągów (lista zakodowana) { StringBuilder s = nowy StringBuilder(); for (int num: zakodowane) { s.append((char)decrypt(num)); } zwróć s.toString(); } } Python3 import random import math # Zbiór będzie zbiorem liczb pierwszych, # gdzie możemy wybrać losowe liczby pierwsze p i q prime = set() public_key = Brak private_key = Brak n = Brak # Funkcję uruchomimy tylko raz aby wypełnić zestaw # liczb pierwszych def primefiller(): # Metoda używana do wypełniania zestawu liczb pierwszych to Sito # Eratostenesa (metoda zbierania liczb pierwszych) seive = [True] * 250 seive[0] = False seive[1 ] = Fałsz dla i w zakresie (2, 250): dla j w zakresie (i * 2, 250, i): seive[j] = Fałsz # Wypełnianie liczb pierwszych dla i w zakresie (len(seive)): if seive[i]: prime.add(i) # Wybieranie losowej liczby pierwszej i usuwanie jej z listy, ponieważ p!=q def pickrandomprime(): global prime k = random.randint(0, len(prime) - 1) it = iter(prime) dla _ w zakresie(k): next(it) ret = next(it) prime.remove(ret) return ret def setkeys(): globalny klucz publiczny, klucz_prywatny, n prime1 = pickrandomprime() # Pierwsza liczba pierwsza prime2 = pickrandomprime() # Druga liczba pierwsza n = liczba pierwsza1 * liczba pierwsza2 fi = (pierwsza1 - 1) * (pierwsza2 - 1) e = 2 while True: if math.gcd(e, fi) == 1: break e += 1 # d = (k*Φ(n) + 1) / e dla pewnej liczby całkowitej k klucz_publiczny = e d = 2 while True: if (d * e) % fi == 1: break d += 1 klucz_prywatny = d # Aby zaszyfrować podany numer def encrypt(wiadomość): global klucz_publiczny, n e = klucz_publiczny zaszyfrowany_tekst = 1 while e> 0: zaszyfrowany_tekst *= wiadomość zaszyfrowany_tekst %= n e -= 1 return zaszyfrowany_tekst # Aby odszyfrować podany numer def deszyfruj( zaszyfrowany_tekst): globalny klucz prywatny, n d = klucz_prywatny odszyfrowany = 1 podczas d> 0: odszyfrowany *= zaszyfrowany_tekst odszyfrowany %= n d -= 1 return odszyfrowany # Najpierw konwertuje każdy znak na jego wartość ASCII i # następnie go koduje, a następnie dekoduje liczbę, aby otrzymać # ASCII i konwertowanie go na znak def encoder(wiadomość): encoded = [] # Wywołanie funkcji szyfrującej w funkcji kodowania dla litery w wiadomości: encoded.append(encrypt(ord(letter))) return encoded def dekoder(encoded) : s = '' # Wywołanie funkcji deszyfrującej funkcja dekodowania dla num w zakodowanym: s += chr(decrypt(num)) return s if __name__ == '__main__': primefiller() setkeys() message = 'Wiadomość testowa' # Odkomentuj poniżej, aby wprowadzić ręcznie # wiadomość = wejście('Wprowadź wiadomość
') # Wywołanie funkcji kodowania coded = encoder(wiadomość) print('Wiadomość początkowa:') print(wiadomość ) print('
Zaszyfrowana wiadomość (zaszyfrowana kluczem publicznym)
') print(''.join(str(p) dla p w zakodowaniu)) print('
Odkodowana wiadomość (odszyfrowana kluczem publicznym)
') print(''.join(str(p) for p w dekoderze(kodowane))) C# using System; przy użyciu System.Collections.Generic; klasa publiczna GFG {prywatny statyczny HashSet prime = nowy HashSet (); prywatny statyczny int? klucz_publiczny = null; prywatny statyczny int? klucz_prywatny = null; prywatny statyczny int? n = zero; prywatny statyczny Losowy losowy = nowy Losowy(); public static void Main() { PrimeFiller(); UstawKlucze(); string message = 'Wiadomość testowa'; // Odkomentuj poniżej, aby ręcznie wprowadzić dane // Console.WriteLine('Wpisz wiadomość:'); // wiadomość = Console.ReadLine(); Lista coded = Koder(wiadomość); Console.WriteLine('Komunikat początkowy:'); Console.WriteLine(wiadomość); Console.WriteLine('
Zaszyfrowana wiadomość (zaszyfrowana kluczem publicznym)
'); Console.WriteLine(string.Join('', kodowany)); Console.WriteLine('
Odszyfrowana wiadomość (odszyfrowana kluczem publicznym)
'); Console.WriteLine(Dekoder (kodowany)); } public static void PrimeFiller() { bool[] site = new bool[250]; for (int i = 0; tj<250; i++) { sieve[i] = true; } sieve[0] = false; sieve[1] = false; for (int i = 2; i <250; i++) { for (int j = i * 2; j <250; j += i) { sieve[j] = false; } } for (int i = 0; i { if (sieve[i]) { prime.Add(i); } } } public static int PickRandomPrime() { int k = random.Next(0, prime.Count - 1); var enumerator = prime.GetEnumerator(); for (int i = 0; i <= k; i++) { enumerator.MoveNext(); } int ret = enumerator.Current; prime.Remove(ret); return ret; } public static void SetKeys() { int prime1 = PickRandomPrime(); int prime2 = PickRandomPrime(); n = prime1 * prime2; int fi = (prime1 - 1) * (prime2 - 1); int e = 2; while (true) { if (GCD(e, fi) == 1) { break; } e += 1; } public_key = e; int d = 2; while (true) { if ((d * e) % fi == 1) { break; } d += 1; } private_key = d; } public static int Encrypt(int message) { int e = public_key.Value; int encrypted_text = 1; while (e>0) { zaszyfrowany_tekst *= wiadomość; zaszyfrowany_tekst %= n.Wartość; mi -= 1; } zwróć zaszyfrowany_tekst; } public static int Deszyfruj(int szyfrowany_tekst) { int d = klucz_prywatny.Wartość; int odszyfrowany = 1; while (d> 0) { odszyfrowany *= zaszyfrowany_tekst; odszyfrowany %= n.Wartość; d -= 1; } powrót odszyfrowany; } public static int NWD(int a, int b) { if (b == 0) { return a; } zwróć GCD(b, a % b); } publiczna lista statyczna Koder (wiadomość tekstowa) { Lista zakodowane = nowa lista (); foreach (znak w wiadomości) { encoded.Add(Encrypt((int)letter)); } powrót zakodowany; } publiczny ciąg statyczny Dekoder (List zakodowane) { ciąg s = ''; foreach (int num w zakodowaniu) { s += (char)Deszyfruj (liczba); } zwroty; } } Wyjście Wiadomość początkowa: Wiadomość testowa Zaszyfrowana wiadomość (zaszyfrowana kluczem publicznym) 863312887135951593413927434912887135951359583051879012887 Wiadomość zdekodowana (odszyfrowana kluczem prywatnym) Wiadomość testowa Implementacja RSA Cryptosystem przy użyciu prymitywnych korzeni w C++ zaimplementujemy prostą wersję RSA używając prymitywnych korzeni. Krok 1: Generowanie kluczy Na początek musimy wygenerować dwie duże liczby pierwsze, p i q. Te liczby pierwsze powinny być mniej więcej równej długości, a ich iloczyn powinien być znacznie większy niż wiadomość, którą chcemy zaszyfrować. Liczby pierwsze możemy wygenerować za pomocą dowolnego algorytmu testowania pierwszości, takiego jak test Millera-Rabina. Gdy mamy już dwie liczby pierwsze, możemy obliczyć ich iloczyn n = p*q, który będzie modułem naszego systemu RSA. Następnie musimy wybrać liczbę całkowitą e taką, że 1 Aby obliczyć wykładnik klucza prywatnego d, musimy znaleźć liczbę całkowitą d taką, że d*e = 1 (mod phi(n)). Można to zrobić za pomocą rozszerzonego algorytmu Euklidesa. Nasz klucz publiczny to (n, e), a nasz klucz prywatny to (n, d). Krok 2: Szyfrowanie Aby zaszyfrować wiadomość m, musimy ją przekonwertować na liczbę całkowitą z zakresu od 0 do n-1. Można to zrobić za pomocą odwracalnego schematu kodowania, takiego jak ASCII lub UTF-8. Kiedy mamy już całkowitą reprezentację wiadomości, obliczamy zaszyfrowany tekst c jako c = m^e (mod n). Można to skutecznie zrobić, stosując modułowe algorytmy potęgowania, takie jak potęgowanie binarne. Krok 3: Deszyfrowanie Aby odszyfrować zaszyfrowany tekst c, obliczamy tekst jawny m jako m = c^d (mod n). Ponownie możemy użyć modułowych algorytmów potęgowania, aby zrobić to efektywnie. Krok 4: Przykład Przeanalizujmy przykład, używając małych wartości, aby zilustrować działanie kryptosystemu RSA. Załóżmy, że wybierzemy p = 11 i q = 13, co da nam n = 143 i phi(n) = 120. Możemy wybrać e = 7, ponieważ gcd(7, 120) = 1. Korzystając z rozszerzonego algorytmu Euklidesa, możemy obliczyć d = 103, ponieważ 7*103 = 1 (mod 120). Nasz klucz publiczny to (143, 7), a nasz klucz prywatny to (143, 103). Załóżmy, że chcemy zaszyfrować wiadomość HELLO. Możemy przekonwertować tę liczbę na liczbę całkowitą 726564766, używając kodowania ASCII. Używając klucza publicznego, obliczamy zaszyfrowany tekst jako c = 726564766^7 (mod 143) = 32. Aby odszyfrować zaszyfrowany tekst, używamy klucza prywatnego do obliczenia m = 32^103 (mod 143) = 726564766, który jest oryginałem wiadomość. Przykładowy kod: C++ #include #include using namespace std; // oblicz phi(n) dla danej liczby n int phi(int n) { int wynik = n; for (int i = 2; tj<= sqrt(n); i++) { if (n % i == 0) { while (n % i == 0) { n /= i; } result -= result / i; } } if (n>1) { wynik -= wynik / n; } zwróć wynik; } // oblicz gcd(a, b) za pomocą algorytmu euklidesowego int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); } // oblicz a^b mod m za pomocą potęgowania modułowego int modpow(int a, int b, int m) { int wynik = 1; póki (b> 0) { if (b i 1) { wynik = (wynik * a) % m; } za = (a * a) % m; b>>= 1; } zwróć wynik; } // wygeneruj losowy pierwiastek pierwotny modulo n int generatePrimitiveRoot(int n) { int phiN = phi(n); int współczynniki[phiN], numFactors = 0; int temp = phiN; // pobierz wszystkie czynniki pierwsze phi(n) for (int i = 2; i<= sqrt(temp); i++) { if (temp % i == 0) { factors[numFactors++] = i; while (temp % i == 0) { temp /= i; } } } if (temp>1) {czynniki[liczbaCzynników++] = temp; } // sprawdź możliwe pierwiastki pierwotne dla (int i = 2; i<= n; i++) { bool isRoot = true; for (int j = 0; j if (modpow(i, phiN / factors[j], n) == 1) { isRoot = false; break; } } if (isRoot) { return i; } } return -1; } int main() { int p = 61; int q = 53; int n = p * q; int phiN = (p - 1) * (q - 1); int e = generatePrimitiveRoot(phiN); int d = 0; while ((d * e) % phiN != 1) { d++; } cout << 'Public key: {' << e << ', ' << n << '}' << endl; cout << 'Private key: {' << d << ', ' << n << '}' << endl; int m = 123456; int c = modpow(m, e, n); int decrypted = modpow(c, d, n); cout << 'Original message: ' << m << endl; cout << 'Encrypted message: ' << c << endl; cout << 'Decrypted message: ' << decrypted << endl; return 0; } Output: Public key: {3, 3233} Private key: {2011, 3233} Original message: 123456 Encrypted message: 855 Decrypted message: 123456 Advantages: Security: RSA algorithm is considered to be very secure and is widely used for secure data transmission. Public-key cryptography: RSA algorithm is a public-key cryptography algorithm, which means that it uses two different keys for encryption and decryption. The public key is used to encrypt the data, while the private key is used to decrypt the data. Key exchange: RSA algorithm can be used for secure key exchange, which means that two parties can exchange a secret key without actually sending the key over the network. Digital signatures: RSA algorithm can be used for digital signatures, which means that a sender can sign a message using their private key, and the receiver can verify the signature using the sender’s public key. Speed: The RSA technique is suited for usage in real-time applications since it is quite quick and effective. Widely used: Online banking, e-commerce, and secure communications are just a few fields and applications where the RSA algorithm is extensively developed. Disadvantages: Slow processing speed: RSA algorithm is slower than other encryption algorithms, especially when dealing with large amounts of data. Large key size: RSA algorithm requires large key sizes to be secure, which means that it requires more computational resources and storage space. Vulnerability to side-channel attacks: RSA algorithm is vulnerable to side-channel attacks, which means an attacker can use information leaked through side channels such as power consumption, electromagnetic radiation, and timing analysis to extract the private key. Limited use in some applications: RSA algorithm is not suitable for some applications, such as those that require constant encryption and decryption of large amounts of data, due to its slow processing speed. Complexity: The RSA algorithm is a sophisticated mathematical technique that some individuals may find challenging to comprehend and use. Key Management: The secure administration of the private key is necessary for the RSA algorithm, although in some cases this can be difficult. Vulnerability to Quantum Computing: Quantum computers have the ability to attack the RSA algorithm, potentially decrypting the data.>