Шифр Вернама (одноразовый блокнот) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Шифр Вернама (одноразовый блокнот) - единственный известный абсолютно секретный шифр. Он о…»)
 
м (rollbackEdits.php mass rollback)
 
(не показано 9 промежуточных версий 3 участников)
Строка 1: Строка 1:
Шифр Вернама (одноразовый блокнот) - единственный известный абсолютно секретный шифр. Он основан на том, что сообщение кодируется побитовым ''xor'' с одноразовым ключом.  
+
Шифр Вернама (одноразовый блокнот) - единственный известный абсолютно секретный шифр. Он основан на том, что сообщение кодируется побитовым ''xor'' с одноразовым ключом, длина которого не меньше длины передаваемого сообщения.  
 +
 
 +
<tex>E_k(x_1) = x_1 \oplus k</tex>
 +
 
 +
<tex>D_k(x_1 \oplus k \oplus k) = x_1</tex>
  
 
Шифр назван в честь телеграфиста Гильберта Вернама, который сконструировал телеграфный аппарат, автоматически кодирующий сообщения таким методом (ключ подавался на отдельной ленте).  
 
Шифр назван в честь телеграфиста Гильберта Вернама, который сконструировал телеграфный аппарат, автоматически кодирующий сообщения таким методом (ключ подавался на отдельной ленте).  
Легко заметить, что нельзя использовать один и тот же ключ несколько раз - при кодировании одинаковых сообщений в такой ситуации, полученные сообщения также будут одинаковыми, что позволит анализировать передаваемые сообщения.
+
 
Технология одноразового блокнота использовалась во времена Второй Мировой войны, при этом как генератор случайных ключей на стороне СССР использовалась машинистка, которая произвольным образом била по клавишам печатной машинки.
+
Легко заметить, что нельзя использовать один и тот же ключ несколько раз - при кодировании одинаковых сообщений с одинаковым ключом, полученные сообщения также будут одинаковыми, что позволит анализировать передаваемые сообщения.
 +
 
 +
Доказательство абсолютной секретности:
 +
 
 +
Пусть кодируемое слово &mdash; <tex>x</tex>, ключ <tex>k</tex>, результат кодирования <tex> y = x \oplus k </tex>. Таким образом <tex>P(y=y_0) = P(k = y_o \oplus x)</tex>.
 +
Заметим, что при фиксированном <tex>x</tex>, каждому случайному <tex>k</tex> соответствует ровно один <tex>y</tex>, а значит и распределение <tex>y</tex> будет совпадать с распределением ключа, из чего следует, что <tex>\forall x_1 \neq x_2</tex>  <tex> f(y_1 \oplus k) =  f(y_2 \oplus k)</tex>, что и требовалось доказать.

Текущая версия на 19:33, 4 сентября 2022

Шифр Вернама (одноразовый блокнот) - единственный известный абсолютно секретный шифр. Он основан на том, что сообщение кодируется побитовым xor с одноразовым ключом, длина которого не меньше длины передаваемого сообщения.

[math]E_k(x_1) = x_1 \oplus k[/math]

[math]D_k(x_1 \oplus k \oplus k) = x_1[/math]

Шифр назван в честь телеграфиста Гильберта Вернама, который сконструировал телеграфный аппарат, автоматически кодирующий сообщения таким методом (ключ подавался на отдельной ленте).

Легко заметить, что нельзя использовать один и тот же ключ несколько раз - при кодировании одинаковых сообщений с одинаковым ключом, полученные сообщения также будут одинаковыми, что позволит анализировать передаваемые сообщения.

Доказательство абсолютной секретности:

Пусть кодируемое слово — [math]x[/math], ключ [math]k[/math], результат кодирования [math] y = x \oplus k [/math]. Таким образом [math]P(y=y_0) = P(k = y_o \oplus x)[/math]. Заметим, что при фиксированном [math]x[/math], каждому случайному [math]k[/math] соответствует ровно один [math]y[/math], а значит и распределение [math]y[/math] будет совпадать с распределением ключа, из чего следует, что [math]\forall x_1 \neq x_2[/math] [math] f(y_1 \oplus k) = f(y_2 \oplus k)[/math], что и требовалось доказать.