Biorąc pod uwagę RSA, dlaczego nie wiemy, czy możliwa jest kryptografia klucza publicznego?

Byłem na wikipedii na liście nierozwiązanych problemów informatycznych i znalazłem to: Czy możliwa jest kryptografia klucza publicznego?

Myślałem, że szyfrowanie RSA było formą kryptografii klucza publicznego? Dlaczego to jest problem?

Nie wiemy na pewno, że RSA jest bezpieczny. Może się zdarzyć, że RSA może zostać zerwane w czasie wielomianowym, na przykład, jeśli faktoring można wykonać skutecznie. Otwarte jest istnienie wiarygodnego kryptosystemu klucza publicznego. Nie wiemy na pewno, że taki kryptosystem w ogóle istnieje; z tego co wiemy, każdy kryptosystem może zostać skutecznie uszkodzony.

Innym, niezwiązanym z RSA problemem jest to, że może on zostać złamany przez komputery kwantowe. Jest to niepowiązany problem, ponieważ definicja bezpiecznego kryptosystemu z kluczem publicznym wymaga jedynie, aby kryptosystem nie był łamalny przez klasyczne (nie kwantowe) komputery.

Praktycznie rzecz biorąc, RSA wydaje się bezpieczny i jest używany przez cały czas. Wynika to z luki między teorią a praktyką. Chociaż teoretycznie nie wiemy na pewno, że RSA jest bezpieczny, praktycznie mówiąc, musimy użyć jakiegoś kryptosystemu z kluczem publicznym, a RSA jest dobrym wyborem, ponieważ ludzie próbowali go złamać i ponieśli porażkę. Ogólnie rzecz biorąc, znany kryptosystem, na którym ludzie się troszczą, jest bezpieczniejszy niż nieznany, ponieważ oparł się próbom kryptografów. Nie świadczy to o tym, że jest bezpieczny - może nie być - ale to najlepsze, co możemy zrobić.

Oto inne punkty widzenia / szczegóły tego pytania, bardziej szczegółowe i ogólnie. Jak pisze YF w komentarzu, wbrew pozorom, RSA nie jest co najmniej tak trudne jak faktoring. Złamanie RSA wiąże się z problemem dyskretnego dziennika, który oczywiście jest ściśle związany z faktoringiem złożoności, ale nie udowodniono, że ma taką samą złożoność. Ale (jak wskazano) nawet faktoring nie okazał się trudny.

YF wspomina także o obliczeniach kwantowych. Jak dobrze znane są osoby z wewnątrz , RSA nie jest zabezpieczone przed obliczeniami kwantowymi, o których udowodniono, że są w stanie uwzględnić czas P przy użyciu algorytmu Shorsa . Algorytm Shorsa był wówczas uważany za przełom. Kolejnym przełomem, o którym należy wspomnieć w „pobliskim” obszarze, jest algorytm pierwotności AKS, który udowodnił, że testowanie pierwotności odbywa się w P. Teoretyczne przełomy w teorii złożoności są rzadkie, ale nie są niespotykane.

YF nie wspomina, ale zawsze czai się w tle tych pytań, „duże pytanie” P =? NP jest nadal otwarte. Powszechnie uważa się, że „kryptografia algorytmiczna może być niemożliwa” (z wyjątkiem padów jednorazowych), jeśli P = NP, na co eksperci nie wierzą.

Doskonały sposób na naukową koncepcję tego to światy Impagliazzos 5 , przegląd autorstwa Kabanets . Co zaskakujące, teoretycy złożoności nie wiedzą „w którym z 5 światów żyjemy”, chociaż istnieją dowody poszlakowe. To, w jakim świecie żyjemy, zależy od otwartej teorii teorii złożoności. Dotyczą one również otwartych problemów dotyczących istnienia funkcji zapadni i funkcji jednokierunkowych . ( Przypuszcza się, że RSA jest jednym i drugim .) W 2009 r. Odbyła się konferencja badawcza na temat światów Impagliazzos z najnowszymi doniesieniami.

Jedną rzeczą, którą należy tu zdefiniować, jest definicja możliwego. Istnieją dwa sposoby na rozwiązanie tego problemu. Po pierwsze, czy kryptosystem klucza publicznego można uznać za teoretycznie bezpieczny? W najszerszym znaczeniu wymaga to, aby algorytm był bezpieczny nawet w przypadku ataku z nieskończoną mocą obliczeniową. Jest jeden znany system, który to osiągnął, jednorazowa podkładka, jednak jest to tylko teoretycznie, ponieważ nie możemy stworzyć wymaganych liczb naprawdę losowych i jest to klucz prywatny. Drugim sposobem, w jaki można spojrzeć na to pytanie, jest to, czy kryptosystem klucza publicznego można uznać za bezwarunkowo bezpieczny ?. Ta druga definicja jest luźniejsza. W przypadku RSA, jeśli ktoś miałby udowodnić, że rozkład liczb całkowitych był tak trudny, jak nam się obecnie wydaje, i udowodnić, że nie ma innych założeń ani wad w systemie, wtedy RSA byłby bezwarunkowo bezpieczny. Bezwarunkowe bezpieczeństwo usuwa wymóg nieskończonej mocy obliczeniowej i rozluźnia ją do niemożliwości we wszechświecie fizycznym. Ponieważ wszystkie nasze algorytmy klucza publicznego opierają się na ogromnych założeniach dotyczących obliczalności, nie spełniają drugiej definicji.