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

13

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?

cryptography encryption

— S.LAKSHMINARAYAN
źródło

6

To pytanie wydaje się być kopiowane słowo po słowie z Quory , aż do błędu gramatycznego („możliwy projekt”). Sprowadza się to do plagiatu, który nie jest fajny i nie jest mile widziany na tej stronie. Pamiętaj, aby zawsze dodawać wyraźne atrybucje podczas korzystania z innych źródeł.

— DW

1

Szukamy również pytań napisanych własnymi słowami - powinny one być czymś więcej niż tylko kopiowaniem i wklejaniem materiałów dostępnych gdzie indziej. Nie chcemy po prostu być miejscem, które kopiuje i wkleja całe pytania lub odpowiedzi z Quory. Można używać małych cytatów z innych źródeł, jeśli wyraźnie wskażesz, która część jest cytatem i link do źródła i podasz źródło, ale większość musi być twoją własną treścią. Zobacz także cs.stackexchange.com/help/referencing i stackexchange.com/legal .

— DW

n ^ 2 jest w P. Więc P = NP nie wpływa na odpowiedź na pytanie.

— Taemyr

14

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.

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ść). $n$ $I_i$ $K_i$ $n$ $O(n)$ $O(1)$
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). $I_i$ $K_i$ $O(n)$ $O(1)$ $n$
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. $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 ,…

— Gilles „SO- przestań być zły”
źródło

Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .

— DW

1

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.

— jmite
źródło

3

Nie ma algorytmu kryptoanalizy dla OTP, nie mówiąc już o optymalnym. Pytanie dotyczyło konkretnie tego, a nie tego, czy możliwe byłoby bezpieczne szyfrowanie.

— OrangeDog