Dlaczego liczby pierwsze są ważne w kryptografii?

Proste? Tak.

Jeśli pomnożysz dwie duże liczby pierwsze, otrzymasz ogromną liczbę niepierwszą z tylko dwoma (dużymi) czynnikami pierwszymi.

Faktorowanie tej liczby jest nietrywialną operacją, a fakt ten jest źródłem wielu algorytmów kryptograficznych. Zobacz funkcje jednokierunkowe aby uzyskać więcej informacji.

Dodatek: Jeszcze trochę wyjaśnienia. Iloczyn dwóch liczb pierwszych może być używany jako klucz publiczny, podczas gdy same liczby pierwsze jako klucz prywatny. Dowolne operacje wykonywane na danych, które można cofnąć tylko znając jeden z dwóch czynników, będą nietrywialne do odszyfrowania.

Oto bardzo prosty i powszechny przykład.

Algorytm szyfrowania RSA , który jest powszechnie stosowany w bezpiecznych witrynach handlowych, opiera się na fakcie, że łatwo jest wziąć dwie (bardzo duże) liczby pierwsze i pomnożyć je, podczas gdy niezwykle trudno jest zrobić coś przeciwnego - co oznacza: wziąć bardzo dużą liczbę, biorąc pod uwagę, że ma tylko dwa czynniki pierwsze, i znaleźć je.

Ponieważ nikt nie zna szybkiego algorytmu faktoryzującego liczbę całkowitą do jej czynników pierwszych. Jednak bardzo łatwo jest sprawdzić, czy zbiór czynników pierwszych mnoży się do pewnej liczby całkowitej.

Istnieje kilka dobrych zasobów do rozruchu na krypto. Oto jeden:

• http://research.microsoft.com/en-us/groups/crypto/firstcrypto.aspx

Z tej strony:

W najczęściej używanym kluczu publicznym system kryptograficzny, wymyślony przez Rona Rivest, Adi Shamir i Len Adleman w 1977, the public and the private klucze pochodzą od pary dużych liczby pierwsze według a stosunkowo proste matematyczne formuła. W teoria, to może być możliwość uzyskania klucza prywatnego z klucza publicznego poprzez pracę z formula_12 Ale tylko iloczynem dużych liczb pierwszych jest publicznych, a faktoring liczby tego wielkość do liczb pierwszych jest tak trudna, że nawet najpotężniejsze superkomputery w świat nie może złamać zwykłego klucz publiczny.

Książka Bruce ' a Schneiera Kryptografia stosowana jest inna. Gorąco polecam tę książkę; fajnie się czyta.

Ważne są nie tyle same liczby pierwsze, co algorytmy, które działają z liczbami pierwszymi. W szczególności znalezienie czynników liczby (dowolnej liczby).

Jak wiadomo, każda liczba ma co najmniej dwa czynniki. Liczby pierwsze mają tę unikalną właściwość, że mają dokładnie dwa czynniki: 1 i siebie.

Powodem, dla którego faktoring jest tak ważny, jest to, że matematycy i informatycy nie wiedzą, jak obliczyć liczbę, nie próbując po prostu wszystkich możliwych kombinacja. Oznacza to, że najpierw spróbuj podzielić przez 2, potem przez 3, potem przez 4 i tak dalej. Jeśli spróbujesz uwzględnić liczbę pierwszą-szczególnie bardzo dużą-będziesz musiał spróbować (zasadniczo) każdej możliwej liczby między 2 A tą dużą liczbą pierwszą. Nawet na najszybszych komputerach uwzględnienie rodzajów liczb pierwszych używanych w kryptografii zajmie lata (nawet wieki).

To fakt, że nie wiemy jak efektywnie obliczać dużą liczbę, nadaje algorytmom kryptograficznym ich Siła. Jeśli pewnego dnia ktoś wymyśli, jak to zrobić, wszystkie algorytmy kryptograficzne, których obecnie używamy, staną się przestarzałe. Pozostaje to otwartym obszarem badań.

Aby być nieco bardziej konkretnym o tym, jak RSA wykorzystuje własności liczb pierwszych, algorytm RSA zależy krytycznie od twierdzenia Eulera, które stwierdza, że dla względnie pierwszych liczb "a" i "N", A^e jest przystające do 1 modulo n, gdzie E jest funkcją totientową Eulera z n.

Skąd się biorą pierwsze? Aby efektywnie obliczyć funkcję tientową Eulera N, potrzebna jest znajomość faktoryzacji pierwszości N. W przypadku algorytmu RSA, gdzie N = pq dla niektórych liczb pierwszych " p " i "q", to e = (P-1) (q-1) = N - P - q + 1. Ale bez znajomości p I q obliczanie e jest bardzo trudne.

Bardziej abstrakcyjnie, wiele protokołów kryptograficznych używa różnych funkcji zapadkowych , które są łatwe do obliczenia, ale trudne do odwrócenia. Teoria liczb jest bogatym źródłem takich funkcji (jak mnożenie dużych liczb pierwszych), a liczby pierwsze są absolutnie kluczowe dla teorii liczb.

Proponuję książkę matematyczna podróż w kodzie . Książka ma przyjemny klimat, co jest zaskakujące, ponieważ dotyczy kryptografii. Książka podsumowuje podróż Sary Flannery od nauki łamigłówek jako dziecko do stworzenia algorytmu Cayley-Purser (CP) w wieku 16 lat. Daje zdumiewająco szczegółowe wyjaśnienie funkcji jednokierunkowych, teorii liczb I liczb pierwszych oraz ich związku z kryptografią.

Co sprawia, że ta książka jest jeszcze bardziej specyficzna dla twoje pytanie brzmi: Sarah próbowała zaimplementować nowy algorytm klucza publicznego przy użyciu matrycy. było to znacznie szybsze niż przy użyciu liczb pierwszych, ale znaleziono dziurę w pętli, która mogłaby go wykorzystać. Okazało się, że jej algorytm był lepiej wykorzystywany jako prywatny mechanizm szyfrujący. Książka jest świetnym świadectwem używania liczb pierwszych do szyfrowania, ponieważ przetrwała próbę czasu i wyzwania bardzo inteligentnych osób.

Jeszcze jeden zasób dla Ciebie. Ochrona! episode 30 (~30 minutowy podcast, link do transkrypcji) opowiada o zagadnieniach kryptograficznych i wyjaśnia, dlaczego liczby pierwsze są ważne.

Nie jestem matematykiem ani kryptologiem, więc oto zewnętrzna obserwacja w kategoriach laika (żadnych wymyślnych równań, przepraszam).

Cały ten wątek jest wypełniony wyjaśnieniami o Jaksą używane w kryptografii, trudno znaleźć kogoś w tym wątku wyjaśniającego w łatwy sposób Dlaczego są używane ... prawdopodobnie dlatego, że każdy bierze tę wiedzę za pewnik.

Tylko patrzenie na problem z zewnątrz może wywołać taką reakcję; ale jeśli użyj Sum dwóch liczb pierwszych, dlaczego nie utworzyć listy wszystkich możliwych Sum, które mogą wygenerować dowolne dwie liczby pierwsze?

Na tej stronie znajduje się lista 455,042,511 primes, gdzie najwyższe primes to 9,987,500,000 (10 cyfry).

Największa znana liczba pierwsza (stan na Luty 2015) to 2 do potęgi 257,885,161-1, która jest 17,425,170 cyfry.

oznacza to, że nie ma sensu trzymać listy wszystkich znanych liczb pierwszych, a tym bardziej wszystkich ich możliwe sumy. Łatwiej jest wziąć liczbę i sprawdzić, czy jest liczbą pierwszą.

Obliczanie wielkich liczb pierwszych samo w sobie jest monumentalnym zadaniem, więc obliczenie odwrotne dwie liczby pierwsze, które zostały pomnożone przez siebie, zarówno kryptografowie, jak i matematycy, powiedzieliby, że jest wystarczająco trudne ... dzisiaj.

Algorytmy kryptograficzne zazwyczaj polegają na "trudnym problemie". Większość współczesnych algorytmów zdaje się używać faktoringu bardzo dużych liczb jako trudnego problemu - jeśli pomnożymy dwie duże liczby razem, obliczanie ich czynników jest "trudne" (tj. czasochłonne). Jeśli te dwie liczby są liczbami pierwszymi, to jest tylko jedna odpowiedź, która sprawia, że jest jeszcze trudniejsza, a także gwarantuje, że kiedy znajdziesz odpowiedź, jest to właściwa, a nie jakaś inna odpowiedź, która daje taki sam wynik.

Myślę, że to, co jest ważne w kryptografii, to nie same liczby pierwsze, ale trudność problemu faktoryzacji prime

Załóżmy, że masz bardzo dużą liczbę całkowitą, która jest znana jako iloczyn dwóch liczb pierwszych m I n, nie jest łatwo znaleźć, czym są m i N. algorytm taki jak RSA zależy od tego faktu.

Przy okazji, jest opublikowany artykuł na algorytm, który może "rozwiązać" ten problem faktoryzacji prime w akceptowalnym czasie za pomocą kwantowej komputer. Tak więc nowsze algorytmy w kryptografii mogą już nie polegać na "trudnościach" faktoryzacji prime, gdy komputer kwantowy przyjeżdża do miasta:)]}

Ponieważ algorytmy faktoryzacji przyspieszają znacznie z każdym znalezionym czynnikiem. Uczynienie obu kluczy prywatnych pierwszym gwarantuje, że pierwszy znaleziony czynnik będzie również ostatnim. W idealnym przypadku oba klucze prywatne również będą prawie równe pod względem wartości, ponieważ liczy się tylko siła słabszego klucza.

Liczby pierwsze są używane głównie w kryptografii, ponieważ zajmuje dużo czasu na określenie, czy dana liczba jest liczbą pierwszą, czy nie. Dla hakerów, jeśli jakiś algorytm zajmie dużo czasu, aby złamać kod, staje się dla nich bezużyteczny