Se P = NP, cosa è ancora crittograficamente sicuro? [duplicare]

Question

Se P = NP, cosa è ancora crittograficamente sicuro? [duplicare]

#1 da (0 voti)
#2 da (0 voti)

0

Lo so, lo so - "Se P = NP" è un'ipotesi molto ampia e di grande impatto.

Ma questa è un'ipotetica.

Voglio dire, chiaramente RSA (e metodi simili di offuscamento) diventerebbero probabilmente del tutto irrilevanti - o sarebbe? Essere risolvibili in polinomio rispetto al tempo esponenziale sarebbe un duro colpo per il loro funzionamento, ma potrebbero usare chiavi pubbliche / private così grandi (se P = NP, quindi i localizzatori di numeri primi più efficienti sembrano probabili) che spaccandoli è ancora qualcosa di "difficile?"

Questi sono per lo più solo dei punti di discussione. In termini di domanda grezza: quali metodi di crittografia non si basano in definitiva su P! = NP?

cryptography encryption passwords

posta Curious 15.03.2014 - 13:43

fonte

2 risposte

Leggi altre domande sui tag cryptography encryption passwords

Email hacking / prevenzione mascheramento In che modo il toolkit Subterfuge ignora SSL? [chiuso]

score 0 · Answer 1

Qualsiasi schema di crittografia classica è di natura algoritmica, cioè qualsiasi schema di crittografia classica può essere rotto (in linea di principio). Il prossimo campo delle informazioni quantistiche credo che un giorno sia in grado di rendere sicura la comunicazione. Se vuoi saperne di più sui protocolli di distribuzione delle chiavi quantistiche, prova a cercare: protocollo BB84, protocollo B92 e protocollo eckert.

score 0 · Answer 2

Dipende. Se P = NP, ma il miglior algoritmo per risolvere un NP generale completo come SAT è dire O (N ^ 10) con costanti opportunamente grandi, quindi nonostante sia polinomiale, la nostra crittografia convenzionale per i valori di N usati oggi rimarrà valida. Se P = NP con soluzioni per un problema generale NP completo che è O (N ^ 3) con costanti opportunamente piccole, allora un sacco di crittografia diventerà piuttosto debole.

Il controllo della primalità è già abbastanza efficiente (non il tempo esponenziale), quindi una riduzione di SAT a P non necessariamente accelera le ricerche dei numeri primi in alcun modo significativo.