Crittografia e compressione

Qui non c'è contraddizione se si considera il problema nei termini probabilistici . Ad esempio:

The reason I'm confused is that I thought that all encryption was supposed to do is make it as difficult as brute forcing the key to go from the cipher text to the plain text. It seems to me like there could be an AES key that would produce an all 0 ciphertext given a certain plaintext.

Sì, è certamente possibile che alcune combinazioni di chiave e testo in chiaro potrebbero produrre un testo cifrato tutto-zero. Ma dal momento che le chiavi devono essere scelte a caso, se esiste una tale combinazione esiste anche la probabilità che si verifichi nella pratica è solo astronomicamente improbabile.

Una delle principali nozioni di sicurezza per le crittografie è indistinguibilità sotto chosen-plaintext attack ("IND-CPA"), che dice (approssimativamente) che un avversario non può distinguere efficacemente i testi cifrati dai bit casuali uniformi , anche se scelgono i testi in chiaro da crittografare. Più precisamente, qualsiasi algoritmo che riesce a distinguere il cifrario deve essere proibitivamente costoso (ad esempio, forzare bruto una chiave a 128 bit).

Ciò significa che possiamo trarre delle buone conclusioni sulla comprimibilità dei ciphertexts semplicemente ragionando sulla comprimibilità delle stringhe di bit casuali uniformi. E si tratta di questo: per un algoritmo di compressione fisso, se scegli una stringa n -bit a caso, la possibilità che l'algoritmo comprima la stringa che hai scelto per una lunghezza di m i bit ( m < n ) diminuiscono in modo esponenziale con m . Se si potesse scrivere un efficiente algoritmo (forza non bruta) che ha ottenuto un successo migliore di questo a comprimere i testi cifrati, allora la sicurezza del codice sarebbe sospetta.

La compressione e la crittografia producono entrambi output di alta entropia, ma con diversi mezzi e per diversi motivi.

La compressione rimuove la ridondanza (bassa entropia), aumentando così l'entropia media. Considera una sequenza come 111111111 ; poca entropia dato che ogni byte è uguale. Ora pseudo-RLE a 1x9; ; ora è metà della lunghezza e ogni byte memorizzato è diverso. Rimuovendo lo stesso, ti rimangono molte più differenze; ha senso.

La crittografia di solito non modifica la dimensione dell'output; aumentandolo se non altro Ecco perché si desidera comprimere prima che si cripta: testo normale di entropia più alta (solitamente meno probabile) e meno byte da crittografare. Per aumentare l'entropia dell'output, la crittografia miscela l'entropia nella chiave con l'entropia nel testo in chiaro. L'obiettivo è di massimizzare la distribuzione dell'output in modo che gli input strettamente correlati abbiano ancora una distribuzione dell'output variata e uniforme.

È perché le uscite "abc" sono molto diverse da "abd" e gli attaccanti non possono dire quanto sia vicina una particolare ipotesi: devono inchiodare la chiave esattamente o non funzionerà affatto. Contrastalo con un catenaccio dove l'attaccante sa di essere a "1 pin di distanza" e vale la pena di fare un piccolo sforzo in più. Senza il feedback gli attaccanti devono ricorrere alla forza bruta, e poiché quella forza bruta attualmente è dura / costosa / lenta, l'attaccante è sia disincentivato che matematicamente impedito.