RSA algoritmas yra asimetrinis kriptografijos algoritmas. Asimetriškas iš tikrųjų reiškia, kad jis veikia dviem skirtingais klavišais t.y. Viešasis raktas ir Privatus raktas. Kaip nurodo pavadinimas, viešasis raktas suteikiamas visiems, o privatus raktas yra privatus.
cout
Asimetrinės kriptografijos pavyzdys:
- Klientas (pavyzdžiui, naršyklė) siunčia savo viešąjį raktą į serverį ir prašo tam tikrų duomenų.
- Serveris užšifruoja duomenis naudodamas kliento viešąjį raktą ir siunčia užšifruotus duomenis.
- Klientas gauna šiuos duomenis ir juos iššifruoja.
Kadangi tai yra asimetriška, niekas kitas, išskyrus naršyklę, negali iššifruoti duomenų, net jei trečioji šalis turi viešąjį naršyklės raktą.
Idėja! RSA idėja grindžiama tuo, kad sunku apskaičiuoti didelį sveikąjį skaičių. Viešąjį raktą sudaro du skaičiai, kur vienas skaičius yra dviejų didelių pirminių skaičių padauginimas. Ir privatus raktas taip pat gaunamas iš tų pačių dviejų pirminių skaičių. Taigi, jei kas nors gali suskaidyti didelį skaičių, privatus raktas yra pažeistas. Todėl šifravimo stiprumas visiškai priklauso nuo rakto dydžio, o jei rakto dydį padidiname dvigubai arba trigubai, šifravimo stiprumas didėja eksponentiškai. RSA raktai paprastai gali būti 1024 arba 2048 bitų ilgio, tačiau ekspertai mano, kad artimiausiu metu 1024 bitų raktai gali būti sugadinti. Tačiau iki šiol tai atrodo neįgyvendinama užduotis.
Sužinokime RSA algoritmo mechanizmą:>> Viešojo rakto generavimas:
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],>> Privataus rakto generavimas: Turime apskaičiuoti Φ(n) : Taip, kad Φ(n) = (P-1)(Q-1) taigi, Φ(n) = 3016 Dabar apskaičiuokite privatų raktą, d : d = (k *Φ(n) + 1) / e tam tikram sveikajam skaičiui k Jei k = 2, d reikšmė yra 2011. Dabar mes pasiruošę naudoti viešąjį raktą (n = 3127 ir e = 3) ir privatųjį raktą (d = 2011). ) Dabar mes užšifruosime HI : Konvertuosime raides į skaičius : H = 8 ir I = 9 Taigi užšifruoti duomenys c = (89 e )mod n Taigi mūsų užšifruoti duomenys bus 1394 Dabar iššifruosime 1394 : iššifruoti duomenys = (c d )mod n Taigi mūsų užšifruoti duomenys yra 89 8 = H ir I = 9, ty 'HI'. Žemiau pateikiamas RSA algoritmo įgyvendinimas 1 metodui: Mažų skaitinių reikšmių šifravimas ir iššifravimas: C++ // C programa RSA asimetriniam kriptografiniam // algoritmui. Demonstracinės reikšmės yra // santykinai mažos, palyginti su praktine // programa #include naudojant vardų erdvę std; // Grąžina a ir b gcd int gcd(int a, int h) { int temp; o (1) { temp = a % h; if (temp == 0) return h; a = h; h = temp; } } // Kodas, rodantis RSA algoritmą int main() { // Du atsitiktiniai pirminiai skaičiai double p = 3; dvigubas q = 7; // Pirmoji viešojo rakto dalis: dvigubas n = p * q; // Kitos viešojo rakto dalies radimas. // e reiškia šifruoti dvigubą e = 2; dvigubas phi = (p - 1) * (q - 1); while (e // e turi būti bendras pirminis su phi ir // mažesnis nei phi. if (gcd(e, phi) == 1) break; else e++; } // Privatus raktas (d reiškia iššifruoti) // pasirenkant d taip, kad atitiktų // d*e = 1 + k * totient k = 2 // Pastovi reikšmė double d = (1 + (k * phi)) // Šifruotinas pranešimas dvigubas pranešimas; = 12 printf('Pranešimo duomenys = %lf', msg // Šifravimas c = (msg ^ e) % n double c = pow(msg, n); ('
Šifruoti duomenys = %lf', c // Iššifravimas m = (c ^ d) % n double m = pow(c, d) m = fmod(m, n);
Original Message Sent = %lf', m); grąžina 0 java.math.*; importuoti java.util.*; , double h) { /* * Ši funkcija grąžina gcd arba didžiausią bendrą * daliklį */ double temp; while (true) { temp = a % h; if (temp == 0) return h; a = h; h = temp; } } public static void main(String[] args) { double p = 3; dvigubas q = 7; // Išsaugoma pirmoji viešojo rakto dalis: double n = p * q; // Kitos viešojo rakto dalies radimas. // double e reiškia šifruoti double e = 2; dvigubas phi = (p - 1) * (q - 1); while (e /* * e turi būti bendras pirminis su phi ir * mažesnis už phi. */ if (gcd(e, phi) == 1) break; else e++; } int k = 2; // Pastovi reikšmė double d = (1 + (k * phi)) / e // Šifruojamas pranešimas System.out.println('Pranešimo duomenys = ' + msg; ^ e) % n double c = Math.pow(msg, e = c % n;'Šifruoti duomenys = ' + c); % n double m = Math.pow(c, d) m = m % n; Python3 # Python, skirtas RSA asimetriniam kriptografiniam algoritmui. 0): grąžinimas h a = h h = temp p = 3 q = 7 n = p*q e = 2 phi = (p-1)*(q-1), tuo tarpu (e # e turi būti bendras pirminis su phi ir # mažesnis nei phi if(gcd(e, phi) == 1): break else: e = e+1 # Privatus raktas (d reiškia iššifruoti) # pasirenkant d taip, kad jis atitiktų # d*e = 1 + k * totient. k = 2 d = (1 + (k*phi))/e # Šifruotinas pranešimas msg = 12.0 print('Pranešimo duomenys = ', msg) # Šifravimas c = (msg ^ e) % n c = pow( msg, e) c = math.fmod(c, n) print('Šifruoti duomenys = ', c) # Iššifravimas m = (c ^ d) % n m = pow(c, d) m = math.fmod( m, n) print('Original Message Sent = ', m) # Šį kodą pateikė Pranay Arora. C# /* * C# programa, skirta RSA asimetriniam kriptografiniam algoritmui. * Demonstravimui reikšmės yra santykinai mažos, palyginti su praktiniu pritaikymu */ naudojant sistemą; public class GFG { public static double gcd(double a, double h) { /* * Ši funkcija grąžina gcd arba didžiausią bendrąjį * daliklį */ double temp; while (true) { temp = a % h; if (temp == 0) return h; a = h; h = temp; } } static void Main() { double p = 3; dvigubas q = 7; // Išsaugoma pirmoji viešojo rakto dalis: double n = p * q; // Kitos viešojo rakto dalies radimas. // double e reiškia šifruoti double e = 2; dvigubas phi = (p - 1) * (q - 1); while (e /* * e turi būti bendras pirminis su phi ir * mažesnis už phi. */ if (gcd(e, phi) == 1) break; else e++; } int k = 2; // Pastovi reikšmė double d = (1 + (k * phi)) / e // Šifruojamas pranešimas double msg = 12 ('Message data = ' + String.Format('{0:F6}); ', msg)); // Šifravimas c = (msg ^ e) % n double c = Math.Pow(msg, e = c % n); Formatas ('{0:F6}', c)); // Iššifravimas m = (c ^ d) % n double m = Math.Pow(c, d) 'Original Message Sent = ' + String.Format('{0:F6}', m)); function gcd(a, h) { /* * Ši funkcija grąžina gcd arba didžiausią daliklį */ tegul temp while (true) { temp = a % h; h = temp } tegul p = 7 // Išsaugoma pirmoji viešojo rakto dalis: tegul n = p * q; // Kitos viešojo rakto dalies radimas. // e reiškia šifruoti, tegul e = 2; tegul phi = (p - 1) * (q - 1); while (e /* * e turi būti bendras pirminis su phi ir * mažesnis už phi. */ if (gcd(e, phi) == 1) break; else e++; } tegul k = 2; // Pastovi reikšmė tegul d = (1 + (k * phi)) / e // Šifruojamas pranešimas tegul msg = 12 ('Pranešimo duomenys = ' + msg; šifravimas c = (msg ^ e; ) % n tegul c = Math.pow(msg, e = c % n; 'Šifruoti duomenys = ' + c) = Math.pow(c, d) = m % n; Išsiųstas pranešimas = 12,000000 2 metodas: paprastų tekstinių pranešimų, kuriuose yra abėcėlės ir skaičiai, šifravimas ir iššifravimas naudojant jų ASCII reikšmę: C++ #include naudojant vardų sritį std pirminis; // rinkinys bus pirminių skaičių rinkinys, // kur galime pasirinkti atsitiktinius pirminius p ir q int public_key; int privatus_raktas; int n; // funkciją vykdysime tik vieną kartą, kad užpildytume pirminių skaičių aibę // void primefiller() { // metodas naudojamas pirminių skaičių rinkiniui užpildyti yra seive of // eratosthenes(metodas pirminiams skaičiams rinkti) vektorius seive(250, tiesa); seive[0] = klaidinga; seive[1] = klaidinga; už (int i = 2; i<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 encoder(styling message) { vektorius forma; // šifravimo funkcijos iškvietimas kodavimo funkcijoje for (auto& raidė : pranešimas) form.push_back(encrypt((int)letter)); grąžinimo forma; } eilutės dekoderis(vektorius encoded) { string s; // iškviečiama iššifravimo funkcija dekodavimo funkcija, skirta (auto& num : encoded) s += decrypt(num); grąžinti s; } int main() { pirminis užpildas(); setkeys (); string message = 'Test žinutė'; // toliau panaikinkite komentarą rankiniam įvedimui // cout<<'enter the message
';getline(cin,message); // calling the encoding function vector užkoduotas = koduotuvas(pranešimas); 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) { šifruotas_tekstas *= pranešimas; šifruotas_tekstas %= n; e = 1; } grąžinti šifruotą_tekstą; } public static int decrypt(int šifruotas_tekstas) { int d = privatus_raktas; int iššifruota = 1; while (d> 0) { iššifruotas *= šifruotas_tekstas; iššifruota %= n; d = 1; } return iššifruotas; } public static int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); } public static List encoder(String message) { Sąrašas užkoduotas = new ArrayList(); for (char raidė : pranešimas.toCharArray()) { encoded.add(šifruoti((int) raidė)); } grįžti užkoduotas; } public static String decoder(Sąrašas užkoduotas) { StringBuilder s = new StringBuilder(); for (int num : encoded) { s.append((char)decrypt(num)); } return s.toString(); } } Python3 import atsitiktinio importo matematika # Rinkinys bus pirminių skaičių rinkinys, # kur galime pasirinkti atsitiktinius pirminius skaičius p ir q prime = set() public_key = Nėra private_key = Nėra n = Nėra # Funkciją vykdysime tik vieną kartą užpildyti # pirminių skaičių aibę def primefiller(): # Pirminių skaičių aibei užpildyti naudojamas metodas yra # Eratosthenes sietas (pirminių skaičių rinkimo metodas) seive = [Tiesa] * 250 seive[0] = klaidingas seive[1 ] = Klaidinga i diapazone (2, 250): j diapazone (i * 2, 250, i): seive[j] = klaidinga # Pirminių i skaičių užpildymas diapazone (len(seive)): jei seive[i]: prime.add(i) # Atsitiktinio pirminio skaičiaus pasirinkimas ir šio pirminio # skaičiaus ištrynimas iš sąrašo, nes p!=q def pickrandomprime(): visuotinis pirminis k = random.randint(0, len(prime) - 1) it = iter(prime) for _ diapazone(k): next(it) ret = next(it) prime.remove(ret) return ret def setkeys(): global public_key, private_key, n prime1 = pickrandomprime() # Pirmasis pirminis skaičius pirminis2 = pickrandomprime() # Antrasis pirminis skaičius n = pirminis1 * pirminis2 fi = (pirminis1 - 1) * (pirminis2 - 1) e = 2, o tiesa: jei math.gcd(e, fi) == 1: pertrauka e += 1 # d = (k*Φ(n) + 1) / e tam tikram sveikajam skaičiui k viešasis_raktas = e d = 2, o True: if (d * e) % fi == 1: pertrauka d += 1 privatus_raktas = d # Norėdami užšifruoti nurodytą skaičių, def encrypt(pranešimas): visuotinis viešasis_raktas, n e = viešasis_raktas šifruotas_tekstas = 1, o e> 0: šifruotas_tekstas *= pranešimas šifruotas_tekstas %= n e -= 1 return encrypted_text # Norėdami iššifruoti nurodytą skaičių def decrypt( šifruotas_tekstas): pasaulinis privatus_raktas, n d = privatus_raktas iššifruotas = 1, o d> 0: iššifruotas *= šifruotas_tekstas iššifruotas %= n d -= 1 grąžinamas iššifruotas # Pirmiausia kiekvieną simbolį konvertuoja į jo ASCII reikšmę ir #, tada užkoduoja, tada dekoduoja skaičių, kad gautų # ASCII ir konvertuoti jį į simbolių def koduotoją (pranešimą): encoded = [] # Šifravimo funkcijos iškvietimas žinutėje esančios raidės kodavimo funkcijoje: encoded.append(encrypt(ord(letter))) return encoded def decoder(encoded) : s = '' # Iškviečiama iššifravimo funkcijos dekodavimo funkcija num in encoded: s += chr(decrypt(num)) return s if __name__ == '__main__': primefiller() setkeys() message = 'Test Message' # Atšaukti komentarą rankiniam įvedimui # pranešimas = input('Įveskite pranešimą
') # Kodavimo funkcijos iškvietimas coded = encoder(message) print('Pradinis pranešimas:') print(message ) print('
Užkoduotas pranešimas (šifruotas viešuoju raktu)
') print(''.join(str(p) for p in coded)) print('
Iškoduotas pranešimas(iššifruotas viešuoju raktu)
') print(''.join(str(p) for p in decoder(coded))) C# naudojant sistemą; naudojant System.Collections.Generic; public class GFG { private static HashSet pirminis = naujas maišos rinkinys (); privatus statinis tarpt? viešasis_raktas = null; privatus statinis tarpt? privatus_raktas = null; privatus statinis tarpt? n = nulis; private static Atsitiktinis atsitiktinis = new Atsitiktinis(); public static void Main() { PrimeFiller(); SetKeys(); string message = 'Test žinutė'; // Toliau panaikinkite komentarą rankiniam įvedimui // Console.WriteLine('Įveskite pranešimą:'); // pranešimas = Console.ReadLine(); Sąrašas užkoduotas = Encoder(pranešimas); Console.WriteLine('Pradinis pranešimas:'); Console.WriteLine(pranešimas); Console.WriteLine('
Užkoduotas pranešimas (užšifruotas viešuoju raktu)
'); Console.WriteLine(string.Join('', coded)); Console.WriteLine('
Iššifruotas pranešimas (iššifruotas viešuoju raktu)
'); Console.WriteLine(Dekoderis(koduotas)); } public static void PrimeFiller() { bool[] sieve = new bool[250]; už (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.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) { šifruotas_tekstas *= pranešimas; šifruotas_tekstas %= n.Vertė; e = 1; } grąžinti šifruotą_tekstą; } public static int Iššifruoti(int šifruotas_tekstas) { int d = privatus_raktas.Vertė; int iššifruota = 1; while (d> 0) { iššifruotas *= šifruotas_tekstas; iššifruota %= n.Value; d = 1; } return iššifruotas; } public static int GCD(int a, int b) { if (b == 0) { return a; } return GCD(b, a % b); } viešas statinis sąrašas Encoder(styling message) { Sąrašas užkoduotas = naujas sąrašas (); foreach (char raidė žinutėje) { encoded.Add(Encrypt((int)letter)); } grįžti užkoduotas; } vieša statinė eilutė Dekoderis(List užkoduota) { string s = ''; foreach (int num in encoded) { s += (char)Decrypt(num); } return s; } } Išvesties pradinis pranešimas: Bandomasis pranešimas Užkoduotas pranešimas (šifruotas viešuoju raktu) 863312887135951593413927434912887135951359583051879012887 Iššifruotas pranešimas, naudojant RSA Impototlement raktą, naudojant RSA įdiegsime paprastą RSA versiją naudodami primityvias šaknis. 1 veiksmas: raktų generavimas Norėdami pradėti, turime sugeneruoti du didelius pirminius skaičius, p ir q. Šie pirminiai skaičiai turėtų būti maždaug vienodo ilgio, o jų sandauga turėtų būti daug didesnė už pranešimą, kurį norime užšifruoti. Galime generuoti pirminius duomenis naudodami bet kurį pirmumo testavimo algoritmą, pvz., Miller-Rabin testą. Kai turėsime du pirminius duomenis, galime apskaičiuoti jų sandaugą n = p*q, kuri bus mūsų RSA sistemos modulis. Toliau turime pasirinkti sveikąjį skaičių e, kad būtų 1 Norėdami apskaičiuoti privataus rakto eksponentą d, turime rasti sveikąjį skaičių d, kad d*e = 1 (mod phi(n)). Tai galima padaryti naudojant išplėstinį Euklido algoritmą. Mūsų viešasis raktas yra (n, e), o privatus raktas yra (n, d). 2 veiksmas: šifravimas Norėdami užšifruoti pranešimą m, turime jį konvertuoti į sveikąjį skaičių nuo 0 iki n-1. Tai galima padaryti naudojant grįžtamąją kodavimo schemą, pvz., ASCII arba UTF-8. Kai gauname sveikąjį pranešimo atvaizdavimą, apskaičiuojame šifruotą tekstą c kaip c = m^e (mod n). Tai galima efektyviai padaryti naudojant modulinius eksponencijos algoritmus, tokius kaip dvejetainis eksponentas. 3 veiksmas: iššifravimas Norėdami iššifruoti šifruotą tekstą c, apskaičiuojame paprastą tekstą m kaip m = c^d (mod n). Vėlgi, galime naudoti modulinius eksponencijos algoritmus, kad tai padarytume efektyviai. 4 veiksmas: pavyzdys Peržiūrėkime pavyzdį naudodami mažas reikšmes, kad parodytume, kaip veikia RSA kriptosistema. Tarkime, kad pasirenkame p = 11 ir q = 13, gaudami n = 143 ir phi(n) = 120. Galime pasirinkti e = 7, nes gcd(7, 120) = 1. Naudodami išplėstinį Euklido algoritmą galime apskaičiuoti d = 103, nes 7*103 = 1 (mod. 120). Mūsų viešasis raktas yra (143, 7), o privatus raktas yra (143, 103). Tarkime, kad norime užšifruoti pranešimą HELLO. Naudodami ASCII kodavimą galime tai konvertuoti į sveikąjį skaičių 726564766. Naudodami viešąjį raktą, apskaičiuojame šifruotą tekstą kaip c = 726564766^7 (mod 143) = 32. Norėdami iššifruoti šifruotą tekstą, naudojame privatų raktą, kad apskaičiuotume m = 32^103 (mod 143) = 726564766, kuris yra originalas. žinutę. Kodo pavyzdys: C++ #include #include naudojant vardų erdvę std; // apskaičiuoti phi(n) duotam skaičiui n int phi(int n) { int rezultatas = n; už (int i = 2; i<= sqrt(n); i++) { if (n % i == 0) { while (n % i == 0) { n /= i; } result -= result / i; } } if (n>1) { rezultatas -= rezultatas / n; } grąžinti rezultatą; } // apskaičiuokite gcd(a, b) naudodami Euklido algoritmą int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); } // apskaičiuokite a^b mod m naudodami modulinį eksponenciją int modpow(int a, int b, int m) { int rezultatas = 1; while (b> 0) { if (b & 1) { rezultatas = (rezultatas * a) % m; } a = (a * a) % m; b>>= 1; } grąžinti rezultatą; } // generuoti atsitiktinę primityviąją šaknį modulo n int generuotiPrimitiveRoot(int n) { int phiN = phi(n); int faktoriai[phiN], skaičiusFactors = 0; int temp = phN; // gauti visus pirminius phi(n) koeficientus (int i = 2; i<= sqrt(temp); i++) { if (temp % i == 0) { factors[numFactors++] = i; while (temp % i == 0) { temp /= i; } } } if (temp>1) { faktoriai[skaičiusFactors++] = temp; } // patikrinkite galimas primityvias šaknis (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.>