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)).

    Kryptosystem – system, którego podstawowym celem jest dokonywanie operacji kryptograficznych. Jest to zbiór współdziałających ze sobą szyfrów, procedur ich użycia, protokołów zapisu danych, urządzeń.Leonard Adleman (ur. 31 grudnia 1945 r.) - amerykański profesor nauk informatycznych oraz biologii molekularnej na Uniwersytecie Południowej Kalifornii.

    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:

    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.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.

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

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

    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.Tekst jawny (lub inaczej tekst otwarty) – w kryptografii wiadomość, która nie została jeszcze zaszyfrowana (lub została odszyfrowana).
  • – 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.

    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.21 września jest 264. (w latach przestępnych 265.) dniem w kalendarzu gregoriańskim. Do końca roku pozostaje 101 dni.

    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.

    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.Adi Szamir (hebr.: עדי שמיר, ur. w 6 czerwca 1952 w Tel Awiwie) – izraelski informatyk i kryptograf. Profesor informatyki.


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




    Warto wiedzieć że... beta

    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.

    Reklama