Esiste un formalismo matematico per classificare la durezza dei problemi difficili?
In particolare mi riferisco al tipo di problemi difficili che sono tipicamente usati nel sistema cypher; come la fattorizzazione per RSA o il metodo teorico numerico utilizzato in AES.
Si noti che con un sistema di classificazione non mi riferisco alla convinzione che un problema sia più difficile dell'altro perché è stato più lungo, sto chiedendo un po 'di formalismo.
Sì. E no.
I one-time-pads sono probabilmente non bloccabili perché ogni soluzione è ugualmente probabile. Sono anche totalmente inutili in tutti i casi tranne alcuni.
RSA e AES sono così diversi da non essere comparabili. RSA si basa sulla difficoltà di alcuni calcoli, mentre AES non usa la matematica nel senso tradizionale. Esso rimescola i bit molto direttamente, quindi il miglior attacco che abbiamo è una forza bruta diretta sulla chiave stessa. Un attacco "ideale" implicherebbe la ricerca di una debolezza nel modo i bit sono stati codificati, in modo tale da poter trovare qualche pregiudizio statistico che potrebbe essere sfruttato. Ma non è matematica nel senso dei primati del factoring. Non stai attaccando il problema a testa alta, stai cercando degli errori impercettibili.
Anche DES, il primo cifrario "strong" che abbiamo mai avuto, è ininterrotto nel senso che l'attacco più semplice è quello a forza bruta. È solo paralizzato dal fatto che le dimensioni della chiave rendono la forza bruta relativamente facile.
Trovare una forma di crittografia simmetrica "indistruttibile" non è proprio il problema.
Leggi altre domande sui tag encryption