Dlaczego liczby pierwsze są ważne w kryptografii?


191

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


Kilka spostrzeżeń: 1. Ludzie poniżej wspominają, że „pierwszeństwo dużych liczb zajmuje dużo czasu”. To samo dotyczy każdej faktoryzacji. Ważne jest to, że każda liczba całkowita! = 0 ma unikalny rozkład na czynniki jako iloczyn liczb pierwszych (w tym 1, która ma rozkład o długości 0).
TT_

1
2. Proszę sprawdzić moje wyjaśnienie, dlaczego liczby pierwsze są ważne dla funkcji mieszających: stackoverflow.com/questions/1145217/… Jest to związane z właściwością wielomianów o współczynnikach należących do pola (co prawdopodobnie nie jest krótkim wyjaśnieniem).
TT_

2
Zbyt proste krótkie wyjaśnienie → Rozwiąż: a * b = 91. Teraz rozwiązać: 13 * 7 = x. Drugie równanie jest znacznie szybsze do rozwiązania (dla człowieka lub komputera).
Dem Pilafian

Odpowiedzi:


204

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.


7
Gdy wchodzimy w erę obliczeń kwantowych, wydaje się właściwe, aby zauważyć, że rozkład liczb pierwszych za pomocą komputera kwantowego można osiągnąć w czasie wielomianowym za pomocą algorytmu Shora en.wikipedia.org/wiki/Shor%27s_alnodm Prawdopodobnie istnieją już komputery, które mogą odszyfrować szyfrowanie klucza publicznego, takie jak RSA
stujo,

16
@stujo: masowo przeceniasz stan obliczeń kwantowych. W rzeczywistości jest pewne, że taki komputer nie istnieje. Największa liczba, która została uwzględniona przy użyciu algorytmu Shora i najnowocześniejszych badań w sprzęcie kwantowym, wynosi 21. To nie jest 21 bitów, ale liczba 21, czynniki pierwsze 3 i 7.
Michael Borgwardt

1
Nie jestem pewien, jakie dane są aktualne, trudno jest uzyskać informacje o najnowszej pracy, myślę, że to było w 2012 roku, ten artykuł pochodzi z 2014 roku ( m.phys.org/news/2014-11-largest-factored- quantum-device.html ) Czy widzieliśmy jakieś dane publiczne z 2016 roku? Nie wykluczać tego, co może być sklasyfikowane. Chociaż nie można uruchomić algorytmu Shorsa, D-Wave ma teraz ponad 1000 qbitów
stujo

1
@stujo: te same zasady będą obowiązywać, gdy wszyscy będziemy używać procesorów kwantowych, ponieważ liczby pierwsze mogą nadal rosnąć, chodzi o znalezienie większych, niepraktycznych dla procesorów kwantowych, problem istnieje, jeśli niektórzy używają regularnego CPUS do tworzenia kluczy, a niektórzy używają procesorów kwantowych do przełam je. Moc procesorów kwantowych, jak rozumiem, polega na tym, że wykorzystuje qbity, każdy qbit może mieć 3 wartości, a zatem nową technologią jest baza 3, a nie podstawa 2. Procesor 64 qbits miałby 3 ^ 64 kombinacji w jednym słowie. Nie wiem, jak wpływa to na wydajność.
juanmf

5
@juanmf: twoje rozumienie obliczeń kwantowych jest całkowicie błędne. Nie ma to absolutnie nic wspólnego z posiadaniem 3 wartości, co byłoby całkowicie nieciekawe. Szczegóły są bardzo złożone, ale efektem jest to, że niektóre algorytmy kwantowe mogą rozwiązać problemy o niższej złożoności Big-O niż „normalne” algorytmy na sprzęcie nie kwantowym.
Michael Borgwardt,

137

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.


2
Warto również zauważyć, że oprócz problemu faktoryzacji wiele współczesnych kryptografii również (lub zamiast tego) opiera się na problemie z dyskretnym logarytmem. Obie są funkcjami „jednokierunkowymi”: łatwo jest wziąć znane dane wejściowe i obliczyć odpowiedź, ale trudno jest uzyskać odpowiedź i obliczyć te dane wejściowe.
nezroy

4
Pomocne byłoby powiązanie tego wyjaśnienia z terminem „funkcja jednokierunkowa”: en.wikipedia.org/wiki/One-way_function
Chris Conway

Ale jeśli można użyć klucza publicznego do szyfrowania, dlaczego nie można go użyć do odwrotnej sytuacji?
jayarjo,

45

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.


30
Po prostu FYI, liczba uzyskana z pomnożenia dwóch liczb pierwszych nazywa się półpierwszą.
Matthew Brubaker

15

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


10
W rzeczywistości musisz tylko przetestować liczby pierwsze do pierwiastka kwadratowego z liczby, którą próbujesz uwzględnić.
Matthew Brubaker

3
Wiem. Był to szczegół, który „przeoczyłem” w imię prostoty.
Barry Brown

@MatthewBrubaker Czy mógłbyś wyjaśnić, dlaczego tak jest? Naprawdę nie rozumiem.
Kartik Chugh,

4
@KartikChugh ヅ powiedzieć, że nnie jest liczbą pierwszą n = a * b. Jeśli a > sqrt(n), bmusi być mniejszy i odwrotnie, inaczej a * b > nsamo, co zaprzeczyłoby naszemu pierwotnemu twierdzeniu. Aby sprawdzić liczbę pierwszą, sprawdzamy tylko do sqrt.
Abhinav Gauniyal

13

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


1
Co ciekawe, już teraz można szybko dowiedzieć się, JEŻELI liczba jest liczbą pierwszą.
nes1983,

Brakuje tutaj „jeśli czynniki pierwsze są duże”.
Ben Voigt

@Ben: Nie brakuje. Problem jest ogólnie trudny. Należy pamiętać, że problemy, które są na ogół trudne, mogą mieć łatwe przypadki. W tym przypadku małe liczby pierwsze nie są wcale łatwymi przypadkami.
nes1983

2
Nikt nie wie „publicznie”. Możliwe, że agencje wywiadowcze różnych światowych rządów stosują techniki, których nie udostępniają. Zatrudniają ogromną liczbę absolwentów matematyki. Na przykład NSA potajemnie promowała losowe generowanie liczb pierwszych przez „Dual EC_DRBG”, które, jak wiedzieli, było słabe, jako część standardowego schematu kryptograficznego do użytku publicznego. bits.blogs.nytimes.com/2013/09/10/…
don jasne

don: zaspane dokumenty wydają się ujawniać, że tak nie jest. narysowali całkiem rozstrzygający obraz, który (ogólnie rzecz biorąc, mogą istnieć rogi), NSA nie może odszyfrować zaszyfrowanych danych za pomocą specjalnej magii matematycznej, którą tylko oni znają. Schneier szczegółowo omówił tę kwestię.
nes1983,

12

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

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


9

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.


7

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.



6

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.


3
Tylko ostatni akapit jest naprawdę ważny. Argument sum można również powiedzieć dla dowolnej liczby złożonej (istnieje duży zakres [technicznie nieskończenie duży], przechowywanie wszystkich sum jest niemożliwe / głupie). Również sumy liczb pierwszych nie mają tak dużego znaczenia w kryptografii, ważniejsze (zwykle, jak w przypadku RSA) jest ich produkt. Ponadto, przez obliczenia odwrotne prawdopodobnie masz na myśli faktoring . To prawdopodobnie pomoże ci w tym, co masz na myśli.
initramfs

4

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.


4

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


3

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.


To dla mnie trochę zbędne. Część ze słabszej części kluczowej, którą można skomentować do najwyższej odpowiedzi :)
Ulysse BN

-1

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


7
Ustalenie, czy liczba jest liczbą pierwszą, jest tanie i musimy być tanie. Skąd inaczej mielibyśmy wiedzieć, że wybraliśmy liczby pierwsze jako nasze czynniki pierwsze w RSA lub liczbę pierwszą jako moduł w krypto pola skończonego? Kosztowne jest uwzględnienie dużej liczby złożonej w jej dużych czynnikach głównych.
CodesInChaos
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.