Loading AI tools
algorytm kryptograficzny Z Wikipedii, wolnej encyklopedii
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[1]. Jego nazwa pochodzi od pierwszych liter nazwisk jego twórców[2].
W celu wygenerowania pary kluczy (prywatnego i publicznego) należy posłużyć się algorytmem:
d⋅e ≡ 1 (mod φ(n)).
Klucz publiczny jest definiowany jako para liczb (n, e), natomiast kluczem prywatnym jest para (n, d).
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:
Niech będą kolejno szyfrowaniem i deszyfrowaniem kluczami K1 i K2. Wtedy zachodzi:
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.
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.
Pierwszą udaną faktoryzację RSA zakończono 2 grudnia 1999 roku w ramach konkursu The RSA Factoring Challenge[3].
Dotychczas największym kluczem RSA, jaki rozłożono na czynniki pierwsze, jest klucz 768-bitowy. Liczby pierwsze zostały znalezione 12 grudnia 2009, a informacje o przeprowadzonej faktoryzacji opublikowano 7 stycznia 2010 roku[4]. Wykorzystano do tego klaster komputerów; czas zużyty na obliczenia był o 2 rzędy wielkości krótszy od prognozowanego.
Istnieje także szereg ataków na implementacje RSA[5][6]. Ochrona przed nimi polega na stosowaniu probabilistycznych trybów szyfrowania (OAEP) oraz konstruowania implementacji sprzętowych i programowych w taki sposób, by nie były podatne na ataki czasowe lub manipulacje zasilaniem (sprzętowe).
Potencjalnym zagrożeniem dla RSA jest skonstruowanie komputera kwantowego.
Claus Peter Schnorr w opublikowanym 1 marca 2021[7] (i poprawionym 9 lipca 2021[8]) opisie wykorzystania szybkiej faktoryzacji liczb całkowitych za pomocą algorytmów SVP twierdzi, że takie podejście łamie całkowicie kryptografię RSA.
W Stanach Zjednoczonych algorytm RSA był opatentowany. Patent o numerze 4.405.829 został przyznany Massachusetts Institute of Technology (które było w tym czasie pracodawcą autorów) we wrześniu 1983 roku, następnie wszystkie prawa do tego patentu zostały odsprzedane firmie RSA Data Security (za kwotę 150 000 USD)[9]. Patent wygasł 21 września 2000 roku.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.