RSA (kryptografia)

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Algorytm Rivesta-Shamira-Adlemana (RSA) – jeden z pierwszych i obecnie najpopularniejszych asymetrycznych algorytmów kryptograficznych z kluczem publicznym, zaprojektowany w 1977 przez Rona Rivesta, Adiego Shamira oraz Leonarda Adlemana. Pierwszy algorytm, który może być stosowany zarówno do szyfrowania, jak i do podpisów cyfrowych. Bezpieczeństwo szyfrowania opiera się na trudności faktoryzacji dużych liczb złożonych. Jego nazwa pochodzi od pierwszych liter nazwisk jego twórców.

Liczba pierwsza – liczba naturalna większa od 1, która ma dokładnie dwa dzielniki naturalne: jedynkę i siebie samą, np.Stany Zjednoczone, Stany Zjednoczone Ameryki (ang. United States, US, United States of America, USA) – federacyjne państwo w Ameryce Północnej graniczące z Kanadą od północy, Meksykiem od południa, Oceanem Spokojnym od zachodu, Oceanem Arktycznym od północnego zachodu i Oceanem Atlantyckim od wschodu.

Opis algorytmu[ | edytuj kod]

Generowanie kluczy[ | edytuj kod]

W celu wygenerowania pary kluczy (prywatnego i publicznego) należy posłużyć się algorytmem:

Funkcja skrótu, inaczej: funkcja mieszająca lub funkcja haszująca – jest to funkcja, która przyporządkowuje dowolnie dużej liczbie krótką, zwykle posiadającą stały rozmiar, nie specyficzną, quasi-losową wartość, tzw. skrót nieodwracalny.Komputer kwantowy – układ fizyczny do opisu którego wymagana jest mechanika kwantowa, zaprojektowany tak, aby wynik ewolucji tego układu reprezentował rozwiązanie określonego problemu obliczeniowego.
  • Wybieramy losowo dwie duże liczby pierwsze p i q (najlepiej w taki sposób, aby obie miały zbliżoną długość w bitach, ale jednocześnie były od siebie odległe wartościami – istnieją lepsze mechanizmy faktoryzacji, jeżeli liczba ma dzielnik o wartości bliskiej ).
  • Obliczamy wartość n = pq.
  • Obliczamy wartość funkcji Eulera dla n:
  • Wybieramy liczbę e (1 < e < φ(n)) względnie pierwszą z φ(n).
  • Znajdujemy liczbę d, gdzie jej różnica z odwrotnością modularną liczby e jest podzielna przez φ(n):
  • d ≡ e (mod φ(n)).
    Ta liczba może być też prościej określona wzorem:
    d⋅e ≡ 1 (mod φ(n)).

    Leonard Adleman (ur. 31 grudnia 1945 r.) - amerykański profesor nauk informatycznych oraz biologii molekularnej na Uniwersytecie Południowej Kalifornii.Liczby względnie pierwsze – liczby całkowite, które nie mają innych poza jedynką wspólnych dzielników w rozkładzie na czynniki pierwsze lub, równoważnie, ich największym wspólnym dzielnikiem jest jedność; te, w których żadna para nie ma wspólnych dzielników w rozkładzie poza jedynką lub, równoważnie, których największy wspólny dzielnik dla dowolnej pary wynosi jeden, nazywa się parami względnie pierwszymi.

    Klucz publiczny jest definiowany jako para liczb (n, e), natomiast kluczem prywatnym jest para (n, d).

    Szyfrowanie i deszyfrowanie[ | edytuj kod]

    Zanim zaszyfrujemy wiadomość, dzielimy ją na bloki o wartości liczbowej nie większej niż n, a następnie każdy z bloków szyfrujemy według poniższego wzoru:

    Zaszyfrowana wiadomość będzie się składać z kolejnych bloków Tak stworzony szyfrogram przekształcamy na tekst jawny, odszyfrowując kolejne bloki według wzoru:

    Kryptografia klucza publicznego (nazywana również kryptografią asymetryczną) to rodzaj kryptografii, w którym używa się zestawów dwu lub więcej powiązanych ze sobą kluczy, umożliwiających wykonywanie różnych czynności kryptograficznych. Jeden z kluczy może być udostępniony publicznie bez utraty bezpieczeństwa danych zabezpieczanych tym kryptosystemem.Szyfr (inaczej kryptograficzny algorytm szyfrujący) – jest to funkcja matematyczna wykorzystywana do szyfrowania tekstu jawnego lub jego deszyfrowania. Zazwyczaj jedna funkcja wykorzystywana jest do szyfrowania, a inna do deszyfrowania wiadomości. Wiadomość przed zaszyfrowaniem nazywana jest tekstem jawnym, zaś wiadomość zaszyfrowaną nazywamy szyfrogramem. Proces zamiany tekstu jawnego na szyfrogram nazywamy szyfrowaniem.

    Własności operacji szyfrowania i deszyfrowania[ | edytuj kod]

    Niech będą kolejno szyfrowaniem i deszyfrowaniem kluczami K1 i K2. Wtedy zachodzi:

    Tekst jawny (lub inaczej tekst otwarty) – w kryptografii wiadomość, która nie została jeszcze zaszyfrowana (lub została odszyfrowana).Podpis cyfrowy - matematyczny sposób potwierdzania autentyczności cyfrowego dokumentu. Istnieje wiele schematów podpisów cyfrowych, obecnie jednak najpopularniejszym jest schemat podpisu dokumentów cyfrowych w systemach kryptograficznych z kluczem publicznym i jednokierunkową funkcją skrótu - w systemie tym do oryginalnej wiadomości dołączany jest skrót dokumentu, zaszyfrowany prywatnym kluczem nadawcy. Potwierdzenie autentyczności wiadomości jest możliwe po odszyfrowaniu skrótu kluczem publicznym nadawcy i porównaniu go z wytworzonym skrótem odebranego dokumentu.
  • – przemienność operacji szyfrowania,
  • – przemienność operacji deszyfrowania.
  • Ze względów bezpieczeństwa nie powinno się stosować więcej niż 2 zagnieżdżone szyfrowania ze względu na ataki oparte na chińskim twierdzeniu o resztach.

    21 września jest 264. (w latach przestępnych 265.) dniem w kalendarzu gregoriańskim. Do końca roku pozostaje 101 dni.Massachusetts Institute of Technology (MIT) – Instytut Technologiczny w Massachusetts położony w regionie Nowa Anglia w Stanach Zjednoczonych, założony w 1861 roku z inicjatywy kilkudziesięciu przedsiębiorców z okolic Nowego Jorku i Bostonu. Jego celem jest jednoczesne kształcenie studentów i prowadzenie badań podstawowych – jednak silnie zorientowanych na praktyczne potrzeby społeczne. MIT jest uczelnią całkowicie prywatną. Z punktu widzenia prawa jest spółką akcyjną, której akcje posiada obecnie kilkaset osób – głównie członków rodzin założycieli MIT oraz niektórych jego absolwentów.

    Podpisywanie i weryfikacja podpisu[ | edytuj kod]

    Analogicznie, RSA może zostać użyte do przeprowadzenia operacji podpisu. W takim przypadku szyfruje się zazwyczaj skrót wiadomości za pomocą klucza prywatnego i propaguje taki szyfrogram wraz z oryginalną wiadomością. Odbiorca posiadający klucz publiczny deszyfruje - otrzymaną z wiadomością - zaszyfrowaną wartość funkcji skrótu, następnie oblicza wartość tejże funkcji z otrzymanej wiadomości. Jeśli obie wartości się zgadzają, przyjmuje się, że wiadomość została podpisana poprawnie.

    Adi Szamir (hebr.: עדי שמיר, ur. w 6 czerwca 1952 w Tel Awiwie) – izraelski informatyk i kryptograf. Profesor informatyki.Funkcja φ (Eulera) lub tocjent – funkcja nosząca nazwisko Eulera przypisująca każdej liczbie naturalnej liczbę liczb względnie z nią pierwszych nie większych od niej samej.


    Podstrony: 1 [2] [3] [4]




    Reklama