Algorytm szyfrujący RSA...

RSA to algorytm kryptograficzny, który został wymyślony w roku 1977 przez Rona Rivesta, Adi Shamira oraz Leonarda Adlemana.
Bezpieczeństwo szyfru polega na trudności rozłożenia na czynniki pierwsze dużych liczb złożonych, a jego działanie oparto o zastosowanie klucza publicznego i prywatnego. 

 RSA jest bardzo bezpiecznym algorytmem szyfrowania. Wykorzystano w nim fakt, że można bardzo szybko mnożyć przez siebie 2 duże liczby pierwsze, natomiast nie ma algorytmu rozkładania w krótkim czasie otrzymanych iloczynów na czynniki pierwsze.

Algorytm RSA składa się z trzech podstawowych kroków: 

• Generacja klucza publicznego i prywatnego. Klucz publiczny jest przekazywany wszystkim zainteresowanym i umożliwia zaszyfrowanie danych. Klucz prywatny umożliwia rozszyfrowanie danych zakodowanych kluczem publicznym. Jest trzymany w tajemnicy.

• Osoba po otrzymaniu klucza publicznego koduje za jego pomocą swoje dane i przesyła je w postaci szyfru RSA do adresata dysponującego kluczem prywatnym.Klucz publiczny nie musi być chroniony, ponieważ nie umożliwia on rozszyfrowania informacji - proces szyfrowania nie jest odwracalny przy pomocy tego klucza. Zatem nie ma potrzeby jego ochrony i może on być powierzany wszystkim zainteresowanym bez ryzyka złamania kodu. 

• Adresat po otrzymaniu zaszyfrowanej wiadomości rozszyfrowuje ją za pomocą klucza prywatnego.

Struktura algorytmu:

• Najpierw generujemy klucz publiczny oraz klucz prywatny:

  • wybieramy losowo dwie liczby pierwsze p i q.

  • obliczamy iloczyn tych liczb n=p*q

  • obliczamy wrtość funkcji Eulera dla n : φ(n)=(p-1)*(q-1)

  • wybieramy liczbę e z przedziału [1,n] względnie pierwszą z φ(n)
    

  • znajdujemy liczbę d taką, że d*e=1 mod φ(n)
    

  • klucz publiczny to para liczb (n,e)

  • klucz prywatny to para liczb (n,d)

• Szyfrowanie i deszyfrowanie

  • Aby zaszyfrować wiadomość dzielimy ją na bloki m_i o wartości nie większej niż n

  • Teraz każdy z bloków szyfrujemy według wzoru : c_i = m_i^e mod n

  • Natomiast aby odszyfrować wiadomość musimy każdy z bloków c_i odszyfrować według wzoru : m_i = c_i^d mod n
   

Oto przykład:

• Wybieramy dwie liczby. p=13 oraz q=11
• Obliczamy n=13*11 . Zatem n=143
  
• Obliczamy wartość funkcji eulera Ø(n) = (p-1)*(q-1)  = ( 13 - 1 )*( 11 - 1 ) = 12*10 = 120
•   Wyznaczamy wykładnik publiczny e. Ma on być względnie pierwszy z Ø(n) czyli z liczbą 120. Warunek ten spełnia, np. liczba 7. 
• Wyznaczamy liczbę d taką, że d*e=1 mod φ(n) . Więc mamy d*7=1 mod 120. Warunek ten spełnia liczba 103
• Zatem mamy klucz publiczny (n,e) czyli (120,7) oraz klucz prywatny (d,e) czyli (103,7)
• Teraz dzielimy wiadomość na bloki m_i o wartości nie większej niż n i możemy zaszyfrować wiadomość za pomocą wzoru c_i = m_i^e mod n
• Oraz odszyfrować wiadomość za pomocą wzoru m_i = c_i^d mod n