Dimostrazione cifrario di vernam

[andrew low]

Ho letto che è Matematicamente Dimostrato che il cifrario di vernam è indecriptabile. Dove è possibile vedere la dimostrazione???

[dAb]

Io non ci riesco.

fatto

[andrew low]

Mi interessa saperlo perchè dicono (varie fonti) che è dimostrato matematicamente, ma esiste veramente questa dimostrazione o viene definito semplicemente sicuro ma non è provato? Perchè se così fosse, probabilmente esisterà un modo per decriptarlo.

[albgen]

One time pad:

Constructing an unbreakable cipher is actually quite easy; the technique has been known for decades. First choose a random bit string as the key. Then convert the plaintext into a bit string, for example by using its ASCII representation. Finally, compute the XOR (eXclusive OR) of these two strings, bit by bit.

perchè è sicuro:

The resulting ciphertext cannot be broken, because in a sufficiently large sample of ciphertext, each letter will occur equally often, as will every digram, every trigram, and so on. This method, known as the one-time pad, is immune to all present and future attacks no matter how much computational power the intruder has. The reason derives from information theory: there is simply no information in the message because all possible plaintexts of the given length are equally likely.

[MItaly]

http://www.cs.bu.edu/~reyzin/teachin...es/notes-1.pdf
Un tizio sostiene che la dimostrazione in questione è fallata, ma non ho le conoscenze per dirti se abbia ragione o meno.

D'altra parte anche se è provato che è sicuro, il fatto che la chiave deve essere assolutamente casuale e della stessa lunghezza dei dati da cifrare lo rende inutile per la maggior parte degli utilizzi pratici.

[andrew low]

Originariamente inviato da albgen
The resulting ciphertext cannot be broken, because in a sufficiently large sample of ciphertext, each letter will occur equally often, as will every digram, every trigram, and so on. This method, known as the one-time pad, is immune to all present and future attacks no matter how much computational power the intruder has. The reason derives from information theory: there is simply no information in the message because all possible plaintexts of the given length are equally likely.

HO dovuto pure tradurla faticosamente! Comuqnue non è la dimostrazione, perchè da quanto ne ho capito c'è scritto perchè non ci sono "appigli" a cui aggrapparsi per decriptarlo, ma questo non è provato (almeno da quello che hai scritto te). E sarebbe la stessa cosa che pensavano tempi addietro quando dovevano decriptare la criptazione monoalfabetica.

Mitaly domani guardo i 2 link (con dizionario, google e una scarsa conoscenza dell'inglese)

Nel frattempo, grazie a tutti e 2!

[albgen]

Quello che ho postato prima, l'ho preso dal libro "computer network capitolo 8.1.4".
Posto anche l'esempio che segue subito dopo il paragrafo del post precedente...è molto semplice e ti fa capire perchè questo cifrario è sicuro

An example of how one-time pads are used is given in Fig. 8-4. First, message 1, ''I love you.'' is converted to 7-bit ASCII. Then a one-time pad, pad 1, is chosen and XORed with the message to get the ciphertext. A cryptanalyst could try all possible one-time pads to see what plaintext came out for each one. For example, the one-time pad listed as pad 2 in the figure could be tried, resulting in plaintext 2, ''Elvis lives'', which may or may not be plausible (a subject beyond the scope of this book). In fact, for every 11-character ASCII plaintext, there is a one-time pad that generates it. That is what we mean by saying there is no information in the ciphertext: you can get any message of the correct length out of it.

[tia86]

Originariamente inviato da andrew low
Perchè se così fosse, probabilmente esisterà un modo per decriptarlo.

x + y = 1
Dove x e y sono numeri relativi, x è il numero da trovare, y è un numero casuale (a te sconosciuto) e 1 è il risultato della cifratura. Trovami *univocamente* il numero x che ho cifrato.

[Reiuky]

Originariamente inviato da tia86
x + y = 1
Dove x e y sono numeri relativi, x è il numero da trovare, y è un numero casuale (a te sconosciuto) e 1 è il risultato della cifratura. Trovami *univocamente* il numero x che ho cifrato.

Ok....

X + Y = 1

Z + Y = 2

W + Y = 3

e così via....
Dando per scontato che questo sia un messaggio in cui X, W, Z, etc siano i simboli di un messaggio, è impossibile intuire il valore di Y e quindi tradurre il messaggio.

[ilgiovo]

non è vero che è indecifrabile: con una immensa botta di culo, tutto è possibile.