Dlaczego większość kryptografii zależy od dużych par liczb pierwszych, a nie innych problemów?

Większość obecnych metod kryptograficznych zależy od trudności faktorowania liczb, które są iloczynem dwóch dużych liczb pierwszych. Jak rozumiem, jest to trudne tylko tak długo, jak długo metoda zastosowana do wygenerowania dużych liczb pierwszych nie może być użyta jako skrót do faktoryzacji wynikowej liczby złożonej (a samo faktoring dużych liczb jest trudne).

Wygląda na to, że matematycy od czasu do czasu znajdują lepsze skróty, w wyniku czego systemy szyfrowania muszą być okresowo aktualizowane. (Istnieje również możliwość, że obliczenia kwantowe sprawią, że faktoryzacja stanie się o wiele łatwiejszym problemem, ale nie zaskoczy nikogo, jeśli technologia dogoni teorię.)

Niektóre inne problemy okazały się trudne. Dwa przykłady, które przychodzą na myśl, to odmiany problemu plecaka i problemu podróżnego sprzedawcy.

Wiem, że Merkle – Hellman został złamany, że Nasako – Murakami pozostaje bezpieczny, a problemy z plecakiem mogą być odporne na obliczenia kwantowe. (Dzięki, Wikipedia.) Nie znalazłem nic na temat wykorzystania problemu podróżnego sprzedawcy w kryptografii.

Dlaczego więc pary dużych liczb pierwszych rządzą kryptografią?

• Czy to po prostu dlatego, że obecnie łatwo jest wygenerować pary dużych liczb pierwszych, które są łatwe do pomnożenia, ale trudne do uwzględnienia?
• Czy to dlatego, że faktoring par dużych liczb pierwszych okazuje się trudny w przewidywalnym stopniu, który jest wystarczająco dobry?
• Czy pary dużych liczb pierwszych są przydatne w inny sposób niż trudności, takie jak właściwość pracy zarówno w przypadku szyfrowania, jak i podpisywania kryptograficznego?
• Czy problem generowania zestawów problemów dla każdego z pozostałych typów problemów, które są wystarczająco trudne dla samego celu kryptograficznego, jest zbyt trudny, aby był praktyczny?
• Czy właściwości innych typów problemów nie są wystarczająco zbadane, aby można było im zaufać?
• Inny.

Boaz Barak zajął się tym w poście na blogu

Z mojego postu (z grubsza rzecz biorąc) wynika, że ​​wiemy tylko, jak projektować prymitywy kryptograficzne przy użyciu problemów obliczeniowych o pewnej strukturze, które wykorzystujemy. Bez struktury nie wiemy, co robić. Przy zbyt dużej strukturze problem staje się wydajnie obliczalny (a więc bezużyteczny do celów kryptograficznych). Wygląda na to, że ilość struktury musi być odpowiednia.

Wszystko, co powiem, jest dobrze znane (wszystkie linki prowadzą do Wikipedii), ale oto:

1. Podejście zastosowane w RSA przy użyciu par liczb pierwszych można również zastosować w bardziej ogólnym układzie grup cyklicznych, w szczególności w protokole Diffie-Helmanna , który uogólnia$\left(\mathbb{Z}/pq\mathbb{Z}\right)^{\times}$do dowolnej grupy, w szczególności krzywych eliptycznych, które są mniej podatne na ataki działające na liczby całkowite. Inne struktury grupy zostały uznane , które mogą nie być przemienne, ale nikt nie jest w powszechnym użyciu AFAIK.

2. Istnieją inne podejścia do kryptografii, w szczególności kryptografia oparta na sieci, która polega na pewnych trudnych problemach z sieciami (np. Znajdowanie punktów z małą normą w sieci) w celu wdrożenia kryptografii z kluczem publicznym. Co ciekawe, niektóre z tych systemów są trudne do udowodnienia , tzn. Mogą zostać zerwane tylko wtedy, gdy można rozwiązać odpowiedni trudny problem w teorii sieci. Jest to sprzeczne z, powiedzmy, RSA, która nie oferuje tej samej gwarancji . Zauważ, że podejście oparte na sieci nie jest trudne do NP (ale wydaje się trudniejsze niż faktoring całkowity).

3. Istnieje osobna obawa związana z udostępnianiem kluczy, a mianowicie ujawnianie sekretów , które ma bardzo interesujące właściwości teorii złożoności. Nie znam szczegółów, ale teoria protokołów zerowej wiedzy pozwala Alice ujawnić Bobowi swoją wiedzę na temat tajemnicy, którą NP trudno jest obliczyć (wykres Hamiltonian) bez ujawnienia samej tajemnicy (w tym przypadku ścieżki).

Na koniec możesz zajrzeć na stronę kryptografii post kwantowej, aby zobaczyć alternatywne podejścia do kryptosystemów z kluczem publicznym, które opierają się na trudnych problemach.