Perché la crittografia con lo stesso non one-time-pad buona?

Question

Per crittografare un messaggio $ m_1 $ con un one-time-pad chiave $ k $ si fa $ Enc (m_1, k) = m_1 \ oplus k $.

Se si utilizza la stessa $ k $ per crittografare un messaggio diverso $ m_2 $ si ottiene $ Enc (m_2, k) = m_2 \ oplus k $, e se si esegue XOR dei due testo cifrato si ottiene $$ (m_1 \ oplus k) \ oplus (m_2 \ oplus k) = m_1 \ oplus m_2 $$

così, OK, v'è una certa perdita di informazioni becuse si impara $ m_1 \ oplus m_2 $, ma perché è non è sicuro? Non ho modo di imparare (diciamo) $ m_1 $ se non so $ m_2 $. Così perché è sbagliato usare $ k $ due volte ??

Answer 1

Non ho modo di imparare (diciamo) $ m_1 $ se non so $ m_2 $.

Questo è esattamente il problema - se si ri-utilizzare la stessa chiave, e qualcuno ha accesso a un messaggio crittografati nella sia chiaro e forma criptata, possono utilizzare che per trovare la chiave: $$ (M_2 \ oplus k) \ oplus m_2 = k $$

In uno scenario alternativo, se si utilizza la stessa chiave più e più volte, gli attaccanti possono essere in grado di indovinare solo pezzi di vari messaggio cifrato, e ogni ipotesi di successo rivela una parte della chiave $ k $, in modo che nel corso del tempo sempre di più la chiave è rivelato.

Questa strategia generale per rompere un sistema di crittografia è conosciuto come un noto attacco plaintext . Molti sistemi, come AES e RSA, si crede di essere al sicuro da questi attacchi. Ma un one-time pad diventa completamente insicura contro di loro a meno che un nuovo pad viene utilizzato per ogni crittografia, che è il motivo per cui sono chiamati "one-time pad".

Answer 2

E 'insicuro proprio per la ragione si parla -. V'è una certa perdita di informazioni

In sostanza, se avete qualsiasi ipotesi su testi in chiaro (testo in inglese, i file con struttura nota, ecc), che porta ad un'analisi statistiche facile. Probabilmente usando due volte non cambia la praticità dell'attacco in modo significativo, ma usando molte volte con un testo in chiaro non casuale, alla fine rivela informazioni sufficienti per recuperare la chiave.

Infine, se avete la possibilità di usarlo solo per due volte , si ha anche la possibilità di utilizzare solo una volta - la restrizione è che questi uno-tempo- elettrodi non devono essere utilizzati potenzialmente sconosciuto e nel corso del tempo, il numero di volte danneggiare.

A un estremo, se si è a conoscenza (noto testo in chiaro) che il $ m_1 $ è solo un null-string della lunghezza del pad, ti hanno consegnato l'attaccante la chiave prima del calcolo $ m_2 $.

noti attacchi di solo testo sono abbastanza comuni, è ragionevolmente facile di costringere un meccanismo di crittografia per cifrare qualcosa che si conosce a priori. In caso contrario, di solito si può fare assunzioni statistiche ragionevoli.

Answer 3

Si supponga di utilizzare un one-time pad con testo inglese, e si utilizza due volte. Ora, è possibile ottenere $ (M_1 \ oplus k) \ oplus (m_2 \ oplus k) = m_1 \ oplus m_2 $.

testo inglese ha un entropia di qualcosa come 1,3 bit per lettera. La XOR di due messaggi ha 2,6 bit per lettera. Ci sono 26 lettere nell'alfabeto, quindi questo dà $ \ log_2 26 = 4,7 $ bit per lettera. Ciò significa che, anche se si prende lo XOR di due testi in lingua inglese, non v'è ancora abbastanza teoricamente informazioni per decodificare entrambi questi testi. Inoltre, sono abbastanza sicuro che ho letto che criptoanalisti sono in grado di farlo in pratica.

Se si desidera utilizzare un one-time pad due volte, è necessario comprimere il messaggio prima. E anche allora, se non si utilizza un algoritmo di compressione quasi-perfetto, e si utilizza l'one-time pad più volte, ci sarà abbastanza entropia a sinistra per recuperare teoricamente i messaggi. Non so quanto sia difficile sarebbe in pratica.

Answer 4

Il fatto è che, anche se non si sa nulla circa $ m_1 $ e $ m_2 $, si potrebbe essere in grado di recuperare tutti e due da $ m_1 \ oplus m_2 $.

In realtà, per molti casi, è molto semplice. Ecco una semplice visualizzazione.

Answer 5

Ecco un modo intuitivo di rappresentare l'approccio senza ricorrere alla matematica. Diciamo che si dispone di due messaggi cifrati che sono stati criptati con lo stesso pad tempo uno.

1. Fare un indovinare una parola o una frase che può essere contenuta in uno dei messaggi. Diciamo che la frase "Bollettino"
2. A partire con il messaggio 1, si supponga che "Weather Report" si verifica nella prima posizione lettera.
3. Back-calcolare i primi 14 caratteri del pad una volta.
4. decifrare i primi 14 caratteri del messaggio utilizzando il 2 OTP back-calcolato.
5. Se gli sguardi in chiaro come trangugiare-di-gook, poi tornare al punto 2 e ripetere alla posizione 2 ° lettera. Tuttavia, se si ottiene testo significativo (ad esempio "Good Morning I" allora congratulazioni, hai lavorato fuori i primi 14 caratteri del OTP (ed i primi 14 caratteri di ogni lettera)
6. Se si arriva alla fine del messaggio 1 senza vomitare qualcosa di diverso da lettere casuali, allora si può concludere che la frase "Weather Report" non si verifica in un messaggio 1. tornare al punto 1 con una frase diversa, come "Caro colonnello"