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

30

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?

Charlie Parker
źródło
3
Może to oznaczać, że złamanie RSA jest trudne, ale nie zostało to udowodnione .
Tom van der Zanden,
2
dyskretny logarytm problemem w sercu złamanie RSA natomiast „bardzo podobne” nie okazał się być równoważne do faktoringu, jego główną kwestią otwartą pola (zarówno kryptografii i TCS)
vzn
1
Czy drugi nie powinien używać myślnika zamiast przecinków? Czy myślnik nie jest używany, gdy w klauzuli zależnej znajdują się przecinki? The converse statement -- that if factoring large integers is hard, then breaking RSA is hard -- is unproven.
Czipperz
@ruakh: Ups, tak ... Nawet sprawdziłem to dwukrotnie, ale nadal się mylę. Ciągle zapominam, że powinieneś sprowadzić się do problemu, o którym wiesz, że jest łatwy, a nie do problemu, o którym wiesz, że jest co najmniej tak trudny jak twój obecny. :-) Dzięki za to usunąłem go.
Mehrdad
Argument matematyczny: „jeśli , to B ” oznacza to samo co „jeśli nie B , to nie A ”. Nie możesz powiedzieć nic o „jeśli nie A , to nie B ”. ABBAAB
drzbir

Odpowiedzi:

50

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.

jmite
źródło
10
„co najmniej tak samo łatwe” - to sposób interpretacji redukcji, których należy uczyć jaśniej, a także na odwrót.
G. Bach,
Możesz to zrobić w każdy sposób, jeśli X jest co najmniej tak samo twardy jak Y, Y jest co najmniej tak łatwy jak X.
jmite
2
Właśnie to miałem na myśli - prawie wszyscy prawdopodobnie słyszeli, że „X jest co najmniej tak trudne jak Y”, ale „Y jest co najmniej tak łatwe, jak X” bardzo rzadko jest wyjaśniane - chociaż jest tak samo przydatne.
G. Bach,
1
Wydaje mi się, że niejasno pamiętam, że Donald Knuth wspominał o algorytmie, który w przypadku maszyny, która potrafi magicznie złamać dowolne wiadomości zaszyfrowane RSA, byłby w stanie uwzględnić produkty dwóch dużych liczb pierwszych. Mogę mieć to źle :-(
gnasher729
31

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.

Rainer P.
źródło
1
Moglibyśmy udowodnić, że RSA i faktoring są równie trudne, gdybyśmy mogli stworzyć algorytm, który może uwzględniać produkty dwóch dużych liczb pierwszych, generując niektóre specjalne zaszyfrowane wiadomości RSA, łamiąc je, a następnie wykonując więcej obliczeń. Oznaczałoby to, że RSA nie jest łatwiejsze niż faktoring. To nie znaczy, że albo jest łatwe, albo trudne.
gnasher729
@ gnasher729 Czy to wystarczy? Czy algorytm mógłby uwzględniać produkty dwóch dużych liczb pierwszych, ale nie produktów obejmujących więcej niż 2 liczby pierwsze lub produktów zawierających małe liczby pierwsze?
otakucode
@Myślę, że RSA zależy tylko od czynników chronionych prawem autorskim. Tak więc obejście produktów złożonych z wielu czynników byłoby proste.
Taemyr
10

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

Ran G.
źródło
7

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

pqe,v,mvmemodpq

pq,pq

dmvd

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.

CR Drost
źródło
@Gilles właściwie myślę, że masz rację, więc odpowiednio poprawiłem swoją odpowiedź.
CR Drost
3

logeCZmemC

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.

zwol
źródło
mm