Come sarà necessario modificare la sicurezza se P = NP?

Question

Come sarà necessario modificare la sicurezza se P = NP?

#1 da (23 voti)

19

Se supponiamo che si trovi P = NP, come dovranno essere cambiate le misure di sicurezza?

Mi piacerebbe conoscere le principali misure di sicurezza che sono interessate e come dovrebbero essere modificate. Possiamo supporre che le password possano essere violate nel tempo O (n ^ 4), per amor di discussione.

Come esempio di ciò che sto cercando in parte, potremmo avere una risposta come le password RSA di 1.024 bit che dovrebbero essere estese a 5 milioni di bit, o SSH sarebbe reso non sicuro. Credo che sto tentando di ottenere una misura scientifica dei cambiamenti che dovrebbero avvenire senza entrare nel regno della speculazione. Quindi, probabilmente dovremmo prima determinare quale livello di sicurezza è adeguato e quindi confrontare i cambiamenti necessari. Quindi per avere questo livello come parte della domanda, possiamo semplicemente usare le pratiche di sicurezza comuni in vigore oggi.

Sono un po 'novizio nel campo della sicurezza IT, quindi spero che qualcuno possa aiutare a sottolineare ciò che è importante sapere in questo scenario.

authentication cryptography passwords exploit

posta Matt Groff 16.03.2012 - 17:17

fonte

1 risposta

Leggi altre domande sui tag authentication cryptography passwords exploit

exploit di caratteri multibyte - PHP / MySQL ESET avverte: Skype tenta di comunicare con un computer remoto sconosciuto

score 23 · Answer 1

La risposta è: dipende.

Supponiamo di aver trovato un algoritmo di tempo O (n ^ 4) per un problema NP completo come SAT, dove la costante nascosta dalla notazione O grande non è troppo grande. Ciò ucciderebbe quasi tutta la crittografia moderna, compresa la crittografia a chiave simmetrica e la crittografia a chiave pubblica. Le uniche cose rimaste in piedi sarebbero i crittosistemi, teoricamente sicuri, come il one-time pad e l'autenticazione dei messaggi in stile Carter-Wegman.

In tal caso, si potrebbe essere in grado di rispondere progettando cryptosystems con una chiave da 10 milioni di bit o giù di lì, ma, ragazzo, la vita farebbe schifo. Sarebbe piuttosto difficile trasferire le chiavi così grandi. E sarebbe terribilmente difficile fidarsi del crittosistema risultante per qualsiasi tipo di sicurezza duratura. Se oggi qualcuno presenta un algoritmo O (n ^ 4) per SAT, devi presumere che forse l'anno prossimo qualcuno capirà come migliorarlo a O (n ^ 3 log n) o qualcosa del genere. Quindi, in pratica, se qualcuno trova un algoritmo di tempo pratico O (n ^ 4) per SAT, un sacco di crittografia poggia su un fondamento di sabbia, e dovremmo ripensare a tutto.
In alternativa, supponiamo che qualcuno abbia trovato un algoritmo di tempo O (n ^ 100) per un problema NP completo come SAT. In termini di impatto immediato, tale algoritmo sarebbe totalmente inutile per crackare la crittografia. Tuttavia, in molti modi ci troveremmo nella situazione dell'ultimo paragrafo: tutti si chiederebbero se l'anno prossimo un genio migliorerà questo a O (n ^ 10), e poi l'anno dopo O (n ^ 4), e presto. Questo potrebbe facilmente essere un duro colpo per la fiducia della gente nella sicurezza della crittografia moderna. Quindi anche questa sarebbe una scoperta abbastanza sconvolgente, anche se non ha un impatto immediato diretto.
Oppure, supponiamo che qualcuno trovi una prova non costruttiva che esiste un algoritmo tempo-polinomiale per qualche problema NP-completo, ma senza alcuna indicazione su come trasformarlo in un vero algoritmo e nessuna prova che il risultante l'algoritmo sarà efficiente nella pratica. Allora saremmo in uno stato di confusione. Nessuno saprebbe se siamo forse nel mondo del proiettile 1 sopra, o nel mondo di bullet 2, o qualcos'altro interamente.

Tutto ciò che ho detto, non penso che nessuno di questi scenari sia molto probabile nel prossimo futuro. In effetti, andrei così lontano da indovinare che sono molto improbabili. Potremmo anche parlare di quale sarebbe l'effetto sulla crittografia se un grande asteroide colpisse la terra l'anno prossimo. Bene, l'impatto sarebbe piuttosto devastante - ma la probabilità è piuttosto piccola. Penso che ci siano cose molto più rilevanti, probabilmente di cui preoccuparsi.

Quindi, se ti stai chiedendo se dovresti prendere dei provvedimenti per proteggerti dalla possibilità che qualcuno dimostri P = NP: non preoccuparti. Questa è una perdita di tempo. Spendi le tue energie su minacce più realistiche.