Znaczenie: „Jeśli faktoring dużych liczb całkowitych jest trudny, to złamanie RSA jest trudne,” nie jest udowodnione ”

Czytałem CLRS i powiedziano:

Jeśli faktoring dużych liczb całkowitych jest łatwy, to złamanie kryptosystemu RSA jest łatwe.

Ma to dla mnie sens, ponieważ dzięki znajomości $p$ i $q$ łatwo jest stworzyć tajny klucz, który jest znajomością klucza publicznego. Wyjaśnia jednak odwrotne stwierdzenie, którego nie do końca rozumiem:

Przeciwnie, stwierdzenie, że jeśli uwzględnienie dużych liczb całkowitych jest trudne, to złamanie RSA jest trudne, nie jest udowodnione.

Co formalnie oznacza powyższe stwierdzenie? Jeśli założymy, że faktoring jest trudny (w jakiś formalny sposób), dlaczego nie oznacza to, że złamanie systemu kryptograficznego RSA jest trudne?

Rozważmy teraz, że jeśli założymy, że faktoring jest trudny ... i odkryliśmy, że oznacza to, że kryptosystem RSA jest trudny do złamania. Co to by formalnie oznaczało?

Najłatwiejszym sposobem myślenia o tym jest myślenie przeciwne.

Wyrok:

jeśli faktoring dużych liczb całkowitych jest trudny, wówczas złamanie RSA jest trudne

odpowiada następującemu:

jeśli przełamanie RSA jest łatwe, to faktoring dużych liczb całkowitych jest łatwy

To stwierdzenie nie zostało udowodnione.

Mówią, załóżmy, że mamy algorytm, który rozwiązuje faktoring w czasie wielomianowym. Następnie możemy go użyć do skonstruowania algorytmu, który rozwiązuje RSA w czasie wielomianowym.

Ale może istnieć inny sposób na złamanie RSA, który nie wymaga uwzględnienia liczb całkowitych. Możliwe, że okaże się, że możemy złamać RSA w sposób, który nie pozwala na uwzględnienie liczb całkowitych w czasie wielomianowym.

Krótko mówiąc, wiemy, że RSA jest co najmniej tak łatwe jak faktoring. Istnieją dwa możliwe wyniki: RSA i faktoring mają równoważną trudność lub RSA jest problemem o wiele łatwiejszym niż faktoring. Nie wiemy, co się dzieje.

Istnienie trudnej drogi nie oznacza, że ​​nie ma łatwej drogi.

Istnieje wiele sposobów na złamanie RSA i musimy tylko znaleźć jeden z nich.

Jednym z tych sposobów jest faktoring dużej liczby całkowitej, więc jeśli jest to łatwe, możemy to zrobić w ten sposób, a RSA jest zepsuty. To także jedyny znany nam sposób. Jeśli jest to niewykonalne, wciąż możemy znaleźć inny, mniej wymagający obliczeniowo sposób wykonywania naszego zadania bez potrzeby jawnego obliczania p i q od n .

Aby udowodnić, że RSA jest zepsuty, musimy udowodnić, że jeden sposób jest prosty.

Aby udowodnić, że RSA jest bezpieczny, musimy udowodnić, że wszystkie sposoby na to są trudne.

Wreszcie, twoje oświadczenie nie jest udowodnione, ponieważ nie jest udowodnione, że nie istnieje żadna inna, łatwiejsza metoda, która wyodrębnia informacje z szyfrogramu.

Jednym dodatkowym sposobem spojrzenia na to jest to, że złamanie RSA wymaga tylko specjalnego przypadku faktoringu, który może, ale nie musi być łatwy, niezależnie od ogólnej kwestii faktoringu.

$3$

Oznacza to, że problem RSA wydaje się (w tym momencie) bardziej konkretny niż faktoring.

$pq$$e,$$v,$$m$$v \equiv m^e \mod pq$

$pq,$$p$$q$

$d$$m \equiv v^d$

$m$

W rzeczywistości w 1998 roku Boneh i Venkatesan opublikowali dowód, że pewna prosta klasa algorytmów (plus, czasy, wykładniki, brak elementów typu XOR / NAND) nie może zostać użyta do przekształcenia rozwiązania problemu RSA w algorytm faktoringu. Argument miał prostą pomysłowość: manipulując matematycznie tymi operacjami arytmetycznymi, możemy dowiedzieć się, że „algorytm redukcji” (dla precyzji: jest to algorytm, który używa „wyroczni” RSA dla semiprime do uwzględnienia tego semiprime) być samodzielnym algorytmem faktoringowym, abyśmy mogli go zmodyfikować do wariantu, który nie wywołuje żadnej wyroczni. Mamy więc trikotomię: albo (a) nie ma takiego algorytmu redukcji, albo (b) algorytm redukcji nie ma dobrej interpretacji arytmetycznej lub (c) faktoring jest czasem wielomianowym, tak jak algorytm redukcji.

$\log_e C$$\mathbb{Z}_{m}$$e$$m$$C$

Te dwa zadania matematyczne są powiązane, ale (o ile dobrze pamiętam) uważa się, że rozwiązanie jednego nie oznaczałoby rozwiązania drugiego. Nie wiem, czy są to jedyne dwa sposoby matematycznego złamania RSA.