Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek,  wersja1.0

©2010 mgr Jerzy Wałaszek I LO w Tarnowie

Szyfrowanie tekstów - szyfr RSA

Symetryczny system szyfrowania to taki, w którym klucz szyfrujący pozwala zarówno szyfrować dane, jak również odszyfrowywać je. Opisane w poprzednich rozdziałach systemy były systemami symetrycznymi. Podstawową wadą systemów symetrycznych jest ścisła konieczność ochrony klucza. Z tego powodu mozna je było stosować tylko w ograniczonych grupach użytkowników.

R.L.Rivest	A. Shamir	L. Adleman
Twórcy algorytmu RSA

W roku 1977 trzej profesorowie z MIT w USA, Ronald L. Rivest, Adi Shamir i Leonard Adleman, opublikowali nowy rodzaj szyfrowania danych, który nazwano od pierwszych liter ich nazwisk systemem RSA.  Jest to niesymetryczny algorytm szyfrujący, którego zasadniczą cechą są dwa klucze: publiczny do kodowania informacji oraz prywatny do jej odczytywania. Klucz publiczny (można go udostępniać wszystkim zainteresowanym) umożliwia jedynie zaszyfrowanie danych i w żaden sposób nie ułatwia ich odczytania, nie musi więc być chroniony. Dzięki temu firmy dokonujące transakcji poprzez sieć Internet mogą zapewnić swoim klientom poufność i bezpieczeństwo. Drugi klucz (prywatny, przechowywany pod nadzorem) służy do odczytywania informacji zakodowanych przy pomocy pierwszego klucza. Klucz ten nie jest udostępniany publicznie. System RSA umożliwia bezpieczne przesyłanie danych w środowisku, w którym może dochodzić do różnych nadużyć. Bezpieczeństwo oparte jest na trudności rozkładu dużych liczb na czynniki pierwsze.

Przykład:

Załóżmy, iż dysponujemy superszybkim komputerem, który jest w stanie sprawdzić podzielność miliarda dużych liczb w ciągu jednej sekundy. Aby złamać szyfr RSA należy rozbić klucz publiczny na dwie liczby pierwsze będące jego dzielnikami. Znajomość tych liczb pozwala rozszyfrować każdą informację zakodowaną kluczem prywatnym i publicznym.

Brzmi dosyć prosto. Jednakże nie ma prostej metody rozbijania dużych liczb na czynniki pierwsze. Nie istnieje żaden wzór, do którego podstawiamy daną liczbę i w wyniku otrzymujemy wartości jej czynników pierwszych. Należy je znaleźć testując podzielność kolejnych liczb.

Z rozważań o liczbach pierwszych wynika, iż w przypadku dwóch różnych dzielników pierwszych jeden musi leżeć poniżej wartości pierwiastka z danej liczby, a drugi powyżej (dlaczego?). Zatem, aby go znaleźć musimy wyliczyć pierwiastek z rozkładanej liczby, a następnie testować podzielność przez liczby nieparzyste leżące poniżej tego pierwiastka.

Statystycznie poszukiwany czynnik pierwszy powinien znajdować się w górnej połówce zakresu od 2 do pierwiastka z n. Ile działań musimy wykonać? Policzmy.

Klucz 128 bitowy. Pierwiastek jest liczbą 64 bitową. W zakresie od 2 do 2⁶⁴ co druga liczba jest nieparzysta, zatem jest ich około 2⁶⁴ / 2 = 2⁶³. Ponieważ interesuje nas tylko górna połówka, to ilość liczb do sprawdzenia jest dwa razy mniejsza, czyli wynosi 2⁶³ / 2 = 2⁶². Ile czasu zajmie naszemu superkomputerowi sprawdzenie podzielności przez około 2⁶² liczb, jeśli w ciągu 1 sekundy wykonuje on miliard sprawdzeń? Odpowiedź brzmi:

Czy sądzisz, że ktoś będzie czekał przez prawie dwa życia na złamanie szyfru? Zatem można podać do publicznej wiadomości liczbę będącą iloczynem dwóch dużych liczb pierwszych i mieć prawie pewność, iż nikt jej nie rozbije na czynniki pierwsze w rozsądnym czasie. Ostatecznie zamiast 128 bitów możemy zwiększyć klucz do np. 1024 bitów, a wtedy czas łamania szyfru liczy się miliardami miliardów... miliardów lat.

Fazy algorytmu RSA

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

Tworzenie kluczy RSA

Przykład:

Szyfrowanie kluczem publicznym RSA

Przykład:

Rozszyfrowywanie kluczem prywatnym RSA

Przykład:

d = 103 n = 143 c = 7

Otrzymaliśmy zakodowaną wiadomość o wartości 7. Jesteśmy w posiadaniu klucza prywatnego, który służy do rozszyfrowywania wiadomości zakodowanych kluczem publicznym.

t = 123

Wykonujemy następujące operacje:    t = 7103 mod 143 Potęga jest zbyt duża, aby można ją było w normalny sposób obliczyć (języki programowania mają zwykle ograniczenia co do wielkości liczb całkowitych). Jednakże nas nie interesuje wartość liczbowa potęgi, a jedynie reszta z dzielenia jej przez 143. Możemy więc rozłożyć potęgę na iloczyn składników o wykładnikach równych kolejnym potęgom liczby dwa: 7103 mod 143 = 764 + 32 + 4 + 2 + 1 mod 143 = (764 mod 143) × (732 mod 143) × (74 mod 143) × (72 mod 143) × 7 mod 143 71 mod 143 = 7 72 mod 143 = (71 mod 143)2 mod 143 = 49 mod 143 = 49 74 mod 143 = (72 mod 143)2 mod 143 = 492 mod 143 = 113 78 mod 143 = (74 mod 143)2 mod 143 = 1132 mod 143 = 42 716 mod 143 = (78 mod 143)2 mod 143 = 422 mod 143 = 48 732 mod 143 = (716 mod 143)2 mod 143 = 482 mod 143 = 16 764 mod 143 = (732 mod 143)2 mod 143 = 162 mod 143 = 113 Do wyliczenia potęgi bierzemy tylko te reszty, które występują w sumie potęg 2: (jeśli byłoby ich bardzo dużo, to każde mnożenie można wykonać z operacją modulo, dzięki czemu wynik nigdy nie wyjdzie poza wartość modułu) t = 7103 mod 143 = 113 × 16 × 113 × 49 × 7 mod 143 = 123

 

Program RSA

Program

Na podstawie podanych informacji napiszemy prostą aplikację, która pełnić będzie rolę kompletnego systemu szyfrowania RSA. Proces szyfrowania i rozszyfrowywania jest identyczny, różni się tylko rodzajem zastosowanego klucza. Dlatego w aplikacji występują jedynie dwie opcje: tworzenie kluczy RSA oraz szyfrowanie RSA. W pierwszym przypadku program generuje dwa klucze, publiczny oraz prywatny. Należy zapamiętać te dane, gdyż będą one potrzebne w drugiej opcji do szyfrowania lub rozszyfrowywania. Proponujemy zastosowanie tej aplikacji do prostej zabawy w klasie. Tworzymy jedną grupę uczniów, która utworzy klucz publiczny oraz prywatny. Klucz publiczny przekaże reszcie klasy, klucz prywatny zachowa dla siebie. Następnie pozostali uczniowie na podstawie otrzymanych kluczy publicznych mogą kodować swoje dane i przekazywać je pierwszej grupie, która za pomocą klucza prywatnego dokona rozszyfrowania wiadomości.

Życzymy dobrej zabawy.

/*
 *******************************************************
 ** Przykładowa aplikacja obrazująca sposób działania **
 ** asymetrycznego systemu kodowania informacji RSA.  **
 ** ------------------------------------------------- **
 **           (C)2009 mgr Jerzy Wałaszek              **
 **            I Liceum Ogólnokształcące              **
 **          im. Kazimierza Brodzińskiego             **
 **                   w Tarnowie                      **
 *******************************************************
*/

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

// Funkcja czeka na dowolny klawisz i czyści ekran
//------------------------------------------------

void czekaj(void)
{
  char c[1];

  cout << "\nZapisz te dane\n\n";
  cin.getline(c,1);
  cin.getline(c,1);	
  for(int i = 1; i < 500; i++) cout << endl;
}

// Funkcja obliczająca NWD dla dwóch liczb
//----------------------------------------

int nwd(int a, int b)
{
  int t;

  while(b != 0)
  {
    t = b;
    b = a % b;
    a = t;
  };
  return a;
}

// Funkcja obliczania odwrotności modulo n
//----------------------------------------

int odwr_mod(int a, int n)
{
  int a0,n0,p0,p1,q,r,t;

  p0 = 0; p1 = 1; a0 = a; n0 = n;
  q  = n0 / a0;
  r  = n0 % a0;
  while(r > 0)
  {
    t = p0 - q * p1;
    if(t >= 0)
      t = t % n;
    else
      t = n - ((-t) % n);
    p0 = p1; p1 = t;
    n0 = a0; a0 = r;
    q  = n0 / a0;
    r  = n0 % a0;
  }
  return p1;
}

// Procedura generowania kluczy RSA
//---------------------------------

void klucze_RSA()
{
  const int tp[10] = {11,13,17,19,23,29,31,37,41,43};
  int p,q,phi,n,e,d;

  cout << "Generowanie kluczy RSA\n"
          "----------------------\n\n";

// generujemy dwie różne, losowe liczby pierwsze

  do
  {
    p = tp[rand() % 10];
    q = tp[rand() % 10];
  } while (p == q);

  phi = (p - 1) * (q - 1);
  n   = p * q;

// wyznaczamy wykładniki e i d

  for(e = 3; nwd(e,phi) != 1; e += 2);
  d = odwr_mod(e,phi);

// gotowe, wypisujemy klucze

  cout << "KLUCZ PUBLICZNY\n"
          "wykladnik e = " << e
       << "\n    modul n = " << n
       << "\n\nKLUCZ PRYWATNY\n"
          "wykladnik d = " << d << endl;
  czekaj();
}

// Funkcja oblicza modulo potęgę podanej liczby
//---------------------------------------------

int pot_mod(int a, int w, int n)
{
  int pot,wyn,q;

// wykładnik w rozbieramy na sumę potęg 2
// przy pomocy algorytmu Hornera. Dla reszt
// niezerowych tworzymy iloczyn potęg a modulo n.

  pot = a; wyn = 1;
  for(q = w; q > 0; q /= 2)
  {
    if(q % 2) wyn = (wyn * pot) % n;
    pot = (pot * pot) % n; // kolejna potęga
  }
  return wyn;
}

// Procedura kodowania danych RSA
//-------------------------------

void kodowanie_RSA()
{
  int e,n,t;

  cout << "Kodowanie danych RSA\n"
          "--------------------\n\n"
          "Podaj wykladnik = "; cin  >> e;
  cout << "    Podaj modul = "; cin  >> n;
  cout << "----------------------------------\n\n"
          "Podaj kod RSA   = "; cin  >> t;
  cout << "\nWynik kodowania = " << pot_mod(t,e,n) << endl;

  czekaj();
}

// ********************
// ** Program główny **
// ********************

int main()
{
  int w;

  srand((unsigned)time(NULL));

  do
  {
    cout << "System szyfrowania danych RSA\n"
            "-----------------------------\n"
            " (C)2009  mgr Jerzy Walaszek\n\n"
            "MENU\n"
            "====\n"
            "[ 0 ] - Koniec pracy programu\n"
            "[ 1 ] - Generowanie kluczy RSA\n"
            "[ 2 ] - Kodowanie RSA\n\n"
            "Jaki jest twoj wybor? (0, 1 lub 2) : ";
    cin  >> w;
    cout << "\n\n\n";
    switch (w)
    {  
      case 1 : klucze_RSA(); break;
      case 2 : kodowanie_RSA(); break;
    }
    cout << "\n\n\n";
  } while(w != 0);

  return 0;
}

System szyfrowania danych RSA
-----------------------------
 (C)2009  mgr Jerzy Wałaszek

MENU
====
[ 0 ] - Koniec pracy programu
[ 1 ] - Generowanie kluczy RSA
[ 2 ] - Kodowanie RSA

Jaki jest twój wybór? (0, 1 lub 2) :

Generowanie kluczy RSA
----------------------

KLUCZ PUBLICZNY
wykładnik e =    3
    moduł n =  391

KLUCZ PRYWATNY
wykładnik d =  235

Zapisz te dane i naciśnij Enter

Kodowanie danych RSA
--------------------

Podaj wykładnik = 3
    Podaj moduł = 391
----------------------------------

Podaj kod RSA   = 123

Wynik kodowania = 98

Zapisz te dane i naciśnij Enter

Kodowanie danych RSA
--------------------

Podaj wykładnik = 235
    Podaj moduł = 391
----------------------------------

Podaj kod RSA   = 98

Wynik kodowania = 123

Zapisz te dane i naciśnij Enter

Przykładowe zastosowania RSA

Bezpieczne połączenie internetowe

Sieć komputerowa Internet jest środowiskiem o niskim bezpieczeństwie poufności przesyłanych danych. Pakiety danych podróżujące pomiędzy różnymi węzłami sieci mogą być podglądane przez osoby nieupoważnione. Szyfrowanie danych zapewni nam bezpieczeństwo. Nawiązanie bezpiecznego połączenia wykorzystującego szyfrowanie RSA składa się z następujących etapów:

1. Obie stacje generują zestaw kluczy RSA.

2. Stacje wymieniają się kluczami publicznymi, które posłużą do szyfrowania przesyłanych wiadomości. Operacja ta jest bezpieczna, ponieważ klucze publiczne nie pozwalają odczytać zaszyfrowanych przy ich pomocy wiadomości. Zatem przechwycenie klucza publicznego przez osobę nieupoważnioną nie da jej żadnych korzyści.

3. Wysyłane wiadomości stacje szyfrują przy pomocy otrzymanego klucza publicznego.

4. Odebrane wiadomości stacje rozszyfrowują przy pomocy swojego klucza prywatnego, który nie był ujawniany. Dzięki temu przechwycenie szyfrogramu w drodze do odbiorcy nie przyniesie osobie nieupoważnionej żadnych korzyści.

Bezpieczne połączenia internetowe są dzisiaj szeroko wykorzystywane w sieci do prowadzenia działalności handlowej. Dzięki nim klienci banków mogą bezpiecznie zarządzać swoimi kontami oraz dokonywać zakupów w sieci z wykorzystaniem kart płatniczych.

Podpis cyfrowy

Załóżmy, iż stacja A chce wysłać do stacji B wiadomość W podpisaną cyfrowo.

1. W tym celu stacja A szyfruje wiadomość W za pomocą swojego klucza tajnego i szyfr dołącza do tej wiadomości. Klucz tajny stacja A otrzymuje od instytucji zajmującej się przydzielaniem certyfikatów - jest to tzw. podpis elektroniczny, który jednoznacznie identyfikuje nadawcę wiadomości. W efekcie nowa wiadomość W' składa się z oryginalnej wiadomości W oraz jej zaszyfrowanej kopii.

2. W takiej postaci wiadomość W' zostaje przesłana do stacji B.

3. Stacja B rozszyfrowuje kopię kluczem publicznym stacji A. Klucz publiczny stacji A może być pobrany z serwera instytucji przydzielającej certyfikaty lub otrzymany od stacji A i potwierdzony przez instytucję przydzielającą certyfikaty. W ten sposób stacja B ma pewność, iż klucz publiczny na pewno dotyczy stacji A.

4. Stacja B porównuje obie części wiadomości W'. Jeśli są takie same, to oznacza to, iż pochodzą rzeczywiście od stacji A.

Jeśli przesyłana wiadomość jest poufna, to do jej przekazania można dodatkowo wykorzystać bezpieczne połączenie internetowe.

---

I Liceum Ogólnokształcące    im. Kazimierza Brodzińskiego w Tarnowie ©2024 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe