Dlaczego liczby pierwsze są ważne w kryptografii?

Jedna rzecz, która zawsze wydaje mi się, że nie jestem kryptografem: Dlaczego tak ważne jest używanie liczb pierwszych? Co czyni je tak wyjątkowymi w kryptografii?

Czy ktoś ma proste krótkie wyjaśnienie? (Zdaję sobie sprawę, że istnieje wiele starterów i że kryptografia stosowana jest Biblią, ale jak powiedziano: nie zamierzam wdrożyć własnego algorytmu kryptograficznego, a znalezione przeze mnie rzeczy spowodowały, że mój mózg eksplodował - brak 10 stron wzorów matematycznych Proszę :))

Dziękuję za wszystkie odpowiedzi. Zaakceptowałem ten, który wyjaśnił mi rzeczywistą koncepcję.

Najbardziej podstawowe i ogólne wyjaśnienie: w kryptografii chodzi o teorię liczb , a wszystkie liczby całkowite (z wyjątkiem 0 i 1) składają się z liczb pierwszych, więc w liczbach liczbowych dużo się zajmuje.

Mówiąc ściślej, niektóre ważne algorytmy kryptograficzne, takie jak RSA, krytycznie zależą od tego, że faktoryzacja dużej liczby dużych liczb zajmuje dużo czasu. Zasadniczo masz „klucz publiczny” składający się z iloczynu dwóch dużych liczb pierwszych używanych do szyfrowania wiadomości oraz „tajny klucz” składający się z tych dwóch liczb pierwszych używanych do odszyfrowywania wiadomości. Możesz ustawić klucz publiczny jako publiczny i każdy może go używać do szyfrowania wiadomości, ale tylko Ty znasz podstawowe czynniki i możesz je odszyfrować. Wszyscy inni musieliby wziąć pod uwagę liczbę, która jest zbyt długa, aby była praktyczna, biorąc pod uwagę obecny stan teorii liczb.

Prosty? Tak.

Po pomnożeniu dwóch dużych liczb pierwszych, otrzymamy ogromną liczbę niepierwszą z tylko dwoma (dużymi) czynnikami liczbami pierwszymi.

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

Dodatek: Jeszcze trochę wyjaśnienia. Iloczyn dwóch liczb pierwszych można użyć jako klucza publicznego, a same liczby pierwsze jako klucza prywatnego. Każda operacja wykonana na danych, którą można cofnąć tylko poprzez znajomość jednego z dwóch czynników, nie będzie trywialna do odszyfrowania.

Oto bardzo prosty i powszechny przykład.

Algorytm szyfrowania RSA , który jest powszechnie stosowany w bezpieczny commerce stron internetowych opiera się na fakcie, że łatwo jest wykonać dwa (bardzo duże) liczby pierwsze i pomnożyć je, a to jest bardzo trudne do zrobienia, przeciwnie - oznacza: wziąć bardzo duża liczba, biorąc pod uwagę, że ma tylko dwa czynniki pierwsze, i znajdź je.

Ważne są nie same liczby pierwsze, ale 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ą unikalną właściwość, ponieważ mają dokładnie dwa czynniki: 1 i siebie.

Faktoring jest tak ważny, ponieważ matematycy i informatycy nie wiedzą, jak uwzględnić liczbę, nie wypróbowując każdej możliwej kombinacji. To znaczy, najpierw spróbuj podzielić przez 2, następnie przez 3, następnie przez 4 i tak dalej. Jeśli spróbujesz uwzględnić liczbę pierwszą - szczególnie bardzo dużą - będziesz musiał (zasadniczo) wypróbować każdą możliwą liczbę między 2 a tą dużą liczbą pierwszą. Nawet na najszybszych komputerach uwzględnianie rodzajów liczb pierwszych używanych w kryptografii zajmie lata (a nawet stulecia).

Faktem jest, że nie wiemy, jak efektywnie uwzględnić dużą liczbę, która daje siłę algorytmom kryptograficznym. Jeśli pewnego dnia ktoś wymyśli, jak to zrobić, wszystkie stosowane obecnie algorytmy kryptograficzne staną się przestarzałe. Pozostaje to otwarty obszar badań.

Ponieważ nikt nie zna szybkiego algorytmu, który rozkłada liczbę całkowitą na czynniki pierwsze. Jednak bardzo łatwo jest sprawdzić, czy zbiór czynników pierwszych mnoży się przez pewną liczbę całkowitą.

Istnieje kilka dobrych zasobów do przyspieszenia szyfrowania. Tu jest jeden:

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

Z tej strony:

W najczęściej stosowanym systemie kryptografii z kluczem publicznym, wynalezionym przez Rona Rivesta, Adi Shamira i Lena Adlemana w 1977 r., Zarówno klucze publiczne, jak i prywatne pochodzą z pary dużych liczb pierwszych zgodnie ze stosunkowo prostą formułą matematyczną. Teoretycznie możliwe jest uzyskanie klucza prywatnego z klucza publicznego poprzez odwrócenie formuły. Ale tylko iloczyn dużych liczb pierwszych jest publiczny, a dzielenie liczb tego rozmiaru na liczby pierwsze jest tak trudne, że nawet najpotężniejsze superkomputery na świecie nie mogą złamać zwykłego klucza publicznego.

Książka Bruce'a Schneiera Applied Cryptography to kolejna. Bardzo polecam tę książkę; fajnie jest czytać.

Aby być bardziej konkretnym na temat tego, w jaki sposób RSA wykorzystuje właściwoś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 zgodne z 1 modułem N, gdzie e jest funkcją całkowitą Eulera dla N.

Skąd się biorą liczby pierwsze? Aby skutecznie obliczyć całkowitą funkcję Eulera N, konieczne jest poznanie faktoryzacji liczby pierwszej 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, obliczenie e jest bardzo trudne.

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

Sugerowałbym książkę A Mathematical Journey In Code . Książka ma przyjemny, przyziemny charakter, co jest zaskakujące, ponieważ dotyczy kryptografii. Książka podsumowuje podróż Sarah Flannery od nauki łamigłówek jako dziecka do stworzenia algorytmu Cayley-Purser (CP) w wieku 16 lat. Zapewnia niezwykle szczegółowe wyjaśnienie funkcji jednokierunkowych, teorii liczb i liczb pierwszych oraz ich powiązania z kryptografia.

Tym, co czyni tę książkę jeszcze bardziej konkretną dla twojego pytania, jest to, że Sarah próbowała zaimplementować nowy algorytm klucza publicznego za pomocą matryc. Było znacznie szybciej niż przy użyciu liczb pierwszych, ale znaleziono dziurę w pętli, która mogłaby ją wykorzystać. Okazuje się, że jej algorytm był lepiej wykorzystywany jako prywatny mechanizm szyfrowania. Książka jest doskonałym ś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. Bezpieczeństwo teraz! odcinek 30 (około 30 minutowy podcast, link do transkrypcji) mówi o problemach z kryptografią i wyjaśnia, dlaczego liczby pierwsze są ważne.

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

Cały ten wątek jest wypełniona wyjaśnieniami o JAK liczby pierwsze są wykorzystywane w kryptografii, trudno znaleźć kogokolwiek w tym wątku wyjaśniającym w prosty sposób DLACZEGO stosowane są liczbami pierwszymi ... najprawdopodobniej dlatego, że wszyscy wiedzą, że bierze za pewnik.

Tylko spojrzenie na problem z zewnątrz może wywołać reakcję podobną do; ale jeśli używają sum dwóch liczb pierwszych, dlaczego nie stworzyć listy wszystkich możliwych sum, które mogą wygenerować dowolne dwie liczby pierwsze?

Na tej stronie znajduje się lista 455 042 511 liczb pierwszych, przy czym najwyższe liczby pierwsze wynoszą 9 987 500 000 ( 10 cyfr).

Największa znana liczba pierwsza (na luty 2015 r.) Wynosi 2 do potęgi 257 885 161 - 1, czyli 17 425 170 znaków.

Oznacza to, że nie ma sensu prowadzić listy wszystkich znanych liczb pierwszych, a tym bardziej wszystkich ich możliwych sum. Łatwiej jest wziąć liczbę i sprawdzić, czy to liczba pierwsza.

Obliczanie dużych liczb pierwszych samo w sobie jest monumentalnym zadaniem, więc odwrotne obliczanie dwóch liczb pierwszych, które zostały pomnożone ze sobą zarówno przez kryptografów, jak i matematyków, jest wystarczająco trudne ... dzisiaj.

Algorytmy kryptograficzne zwykle polegają na swoim bezpieczeństwie na „trudnym problemie”. Większość współczesnych algorytmów wydaje się wykorzystywać faktoring bardzo dużych liczb jako swojego trudnego problemu - jeśli pomnożymy dwie duże liczby razem, obliczenie ich czynników jest „trudne” (tj. Czasochłonne). Jeśli te dwie liczby są liczbami pierwszymi, to jest tylko jedna odpowiedź, co czyni ją jeszcze trudniejszą, a także gwarantuje, że gdy znajdziesz odpowiedź, jest to właściwa, a nie jakaś inna odpowiedź, która po prostu daje taki sam wynik.

Myślę, że w kryptografii ważne są same liczby pierwsze, ale trudność związana z faktoryzacją liczb pierwszych

Załóżmy, że masz bardzo dużą liczbę całkowitą, o której wiadomo, że jest iloczynem 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.

Nawiasem mówiąc, opublikowano artykuł na temat algorytmu, który może „rozwiązać” ten problem faktoryzacji pierwotnej w akceptowalnym czasie za pomocą komputera kwantowego. Nowsze algorytmy w kryptografii mogą już nie polegać na tej „trudności” faktoryzacji pierwotnej, gdy do miasta przyjeżdża komputer kwantowy :)

Ponieważ algorytmy faktoryzacji znacznie przyspieszają z każdym znalezionym czynnikiem. Ustawienie obu kluczy prywatnych na pierwsze spowoduje, że pierwszy znaleziony czynnik będzie również ostatnim. Idealnie oba klucze prywatne będą miały prawie taką samą wartość, ponieważ liczy się tylko siła słabszych kluczy.

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