ElGamal

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

ElGamal to jeden z dwóch najważniejszych algorytmów kryptografii asymetrycznej (obok RSA). System jest oparty na trudności problemu logarytmu dyskretnego w ciele liczb całkowitych modulo duża liczba pierwsza. Algorytm w połowie lat 80. XX wieku przedstawił Egipcjanin Taher Elgamal.

RSA – jeden z pierwszych i obecnie najpopularniejszych asymetrycznych algorytmów kryptograficznych z kluczem publicznym, zaprojektowany w 1977 przez Rona Rivesta, Adi 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.Egipt (arab. مصر Miṣr; dialekt egipski: Máṣr (/masˤɾ/); łac. Aegyptus, gr. Αίγυπτος Aígyptos), nazwa oficjalna Arabska Republika Egiptu (arab. جمهوريّة مصر العربيّة Dżumhurijjat Misr Al-Arabijja) – państwo położone w północno-wschodniej Afryce z półwyspem Synaj w zachodniej Azji. Egipt graniczy z Izraelem i Strefą Gazy na północnym wschodzie, Sudanem na południu i Libią na zachodzie. Od północy rozpościera się Morze Śródziemne, a na wschodzie Morze Czerwone.

Algorytm ElGamala umożliwia szyfrowanie oraz obsługę podpisów cyfrowych. Setki modyfikacji algorytmu ElGamala (podobnie jak modyfikacje algorytmu RSA) mają różne inne zastosowania.

Na koncepcji algorytmu ElGamala jest też oparta kryptografia krzywych eliptycznych – w tym przypadku zamiast grupy multiplikatywnej ciała używamy grupy punktów na krzywej eliptycznej.

Szyfrowanie[ | edytuj kod]

Generowanie klucza: wybieramy dowolną liczbę pierwszą dowolny generator podgrupy multiplikatywnej, tzn. taki element, którego rząd jest równy oraz dowolne takie, że: Liczymy

Rząd – w teorii grup pojęcie oddające intuicję „rozmiaru” (w sensie „rzędu wielkości”) danej grupy i ułatwiające przy tym opis jej podgrup; w szczególności rzędem elementu nazywa się rząd („rozmiar”) najmniejszej (pod)grupy zawierającej ten element.Logarytm dyskretny elementu b {displaystyle b} przy podstawie a {displaystyle a} w danej grupie skończonej – liczba całkowita c {displaystyle c} , dla której zachodzi równość (w notacji multiplikatywnej):

co potrafimy zrobić szybko za pomocą potęgowania przez podnoszenie do kwadratu.

Gdyby było dowolne to przykładowo dla:

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.Krzywa eliptyczna – pojęcie z zakresu geometrii algebraicznej, oznaczające według współczesnej definicji gładką krzywą algebraiczną (czyli rozmaitość algebraiczną wymiaru 1) o genusie równym 1 wraz z wyróżnionym punktem O, zwanym "punktem w nieskończoności". Elementy krzywej rozumianej jako zbiór nazywa się, zgodnie z terminologią geometryczną, punktami.
otrzymalibyśmy:

co spowodowałoby, że kryptosystem byłby bezużyteczny (gdyż przy szyfrowaniu zawsze otrzymywalibyśmy 1).

Elliptic Curve Cryptography (ECC) – grupa technik kryptografii asymetrycznej, wykorzystująca jako podstawową technikę matematyczną krzywe eliptyczne. Użycie krzywych eliptycznych w celach kryptograficznych zostało zasugerowane niezależnie przez dwójkę badaczy, Neal Koblitza oraz Victora S. Millera w roku 1985.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.

Następnie publikujemy jako klucz publiczny i zachowujemy jako klucz prywatny.

Algorytm Euklidesa – pierwszy znany algorytm wyznaczania największego wspólnego dzielnika dwóch liczb naturalnych. Został opisany przez greckiego matematyka, Euklidesa w jego dziele "Elementy", w księgach siódmej oraz dziesiątej.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.

Szyfrowanie: mając do zaszyfrowania wiadomość przedstawiamy ją jako element grupy [] wybieramy losowo liczbę i liczymy (modulo )

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.Redukcja Pohliga-Hellmana jest metodą obliczania logarytmu dyskretnego w ciele skończonym GF(p) wymyśloną przez Stephena Pohliga i Martina Hellmana.

Deszyfrowanie: podnosimy otrzymane do potęgi

Następnie znajdujemy odwrotność (nadal modulo ) rozszerzonym algorytmem Euklidesa:

W końcu dzielimy przez czyli mnożymy przez jej odwrotność –

Podstrony: 1 [2] [3]




Reklama