Jeśli P = NP, czy istnieją kryptosystemy, które wymagałyby n ^ 2 czasu, aby się złamać?

Jeśli P równa się NP, czy nadal będzie możliwe zaprojektowanie kryptosystemu, w którym optymalny algorytm kryptoanalizy zajmuje, powiedzmy, kwadrat czasu zajmowanego przez legalne algorytmy szyfrowania i deszyfrowania? Czy istnieją już takie algorytmy?

Tak - tak naprawdę działał pierwszy algorytm klucza publicznego wynaleziony poza agencją wywiadu! Pierwsza publikacja, która proponuje kryptografii klucza publicznego był „bezpiecznej komunikacji ponad niepewny kanały” przez Ralpha Merkle , gdzie proponuje się wykorzystać „zagadki” . Jest to kluczowy protokół umowy.

1. Alice wysyła zaszyfrowanych wiadomości (zwanych puzzlami), każda zawierająca unikalny identyfikator i klucz sesji , z kluczami dla każdej wiadomości wybranymi spośród zestawu kluczy. Zajmuje to czas ( na wiadomość).I i K i n O ( n ) O ( 1 $n$$I_i$$K_i$$n$$O(n)$$O(1)$
2. Bob odszyfrowuje jedną z wiadomości za pomocą brutalnej siły i odsyła zaszyfrowane za pomocą . Zajmuje to czas ( na klawisz, razy możliwych kluczy).K i O ( n ) O ( 1 ) $I_i$$K_i$$O(n)$$O(1)$$n$
3. Alicja próbuje wszystkich kluczy, aby odszyfrować wiadomość. Ponownie zajmuje to czas .$O(n)$

Każda ze stron wymaga tylko obliczenia , ale podsłuchujący, który chce znaleźć musi wypróbować średnio połowę zagadek, aby obliczyć właściwy klucz (podsłuchujący nie wie, którą wiadomość Bob odszyfrował), więc podsłuchujący wymaga Obliczenia średnio.K i Θ ( n 2$O(n)$$K_i$$\Theta(n^2)$

Po tym, jak Merkle wynalazł swoje łamigłówki, Diffie i Hellman opublikowali kluczowy protokół umowy oparty na dyskretnym logarytmie . Ten protokół jest nadal używany.

Problem z łamigłówkami Merkle lub cokolwiek, w którym ilość pracy, którą musi wykonać atakujący, wzrasta tylko jako kwadrat legalnej partii, polega na tym, że do uzyskania przyzwoitego marginesu bezpieczeństwa potrzeba ogromnych rozmiarów kluczy i obliczeń.

W każdym razie nie jest jasne, że samo udowodnienie, że P = NP unieważni istniejące algorytmy kryptograficzne. Jeśli wzrost wielomianu jest wystarczająco wysoką mocą, może nie mieć tak wielkiego znaczenia w praktyce. Zobacz Jak trzeba zmienić zabezpieczenia, jeśli P = NP? , Czy możemy powiedzieć, że jeśli P = NPP = NP, nie ma bezpiecznego szyfrowania kluczem publicznym CPA? , P = NP i obecne systemy kryptograficzne ,…

https://en.m.wikipedia.org/wiki/One-time_pad

Jednorazowa podkładka jest bezpieczna niezależnie od złożoności, o ile twoje liczby są naprawdę losowe.

Nawet jeśli możesz szybko wypróbować każdy klucz, jest to bezużyteczne, ponieważ ujawni każdą możliwą wiadomość i nie ma sposobu, aby dowiedzieć się, który był pożądany.

Jeśli chodzi o to, co opisujesz, jeśli analiza zajmowałaby tylko tyle czasu, co szyfrowanie, według współczesnych standardów byłaby niepewna. Szyfrowanie musi nastąpić w ciągu kilku sekund lub nawet krócej, więc kwadratowy wzrost pozwoliłby na dekodowanie wiadomości w ciągu kilku godzin.