Гаммирование: различия между версиями

[отпатрулированная версия]

[непроверенная версия]

Содержимое удалено Содержимое добавлено

Линейный

Версия от 05:40, 30 марта 2015

Гамми́рование — метод симметричного шифрования, заключающийся в «наложении» последовательности, состоящей из случайных чисел, на открытый текст. Последовательность случайных чисел называется гамма-последовательностью и используется для зашифровывания и расшифровывания данных. Суммирование, обычно, выполняется в каком-либо конечном поле. Например, в поле Галуа GF(2) суммирование принимает вид операции «исключающее ИЛИ (xor)».

Визуальное представление

Схема передатчика.

Схема приёмника.

Стойкость

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

Доказательство Шеннона.

Пусть X, Y и Z — дискретные случайные величины.

Пусть:

X — значение бита открытого текста; то есть, переменная X (бит) способна принимать два значения: 0 и 1;
p — вероятность события, заключающегося в том, что переменная X примет значение 0;
(1-p) — вероятность протовоположного события (то есть, вероятность того, что переменная X примет значение 1).

Запишем закон распределения значений X:

X	0	1
Pi	p	1-p

Используем p и 1-p, так как вероятность встретить одну букву в разных словах различна.

Пусть:

Y — бит псевдослучайной последовательности (гаммы); то есть, переменная Y (бит) способна принимать два значения: 0 и 1;
каждое из значений Y равновероятно; то есть, вероятности получить 0 или 1 равны 1/2.

Запишем закон распределения значений Y:

Y	0	1
Pi	1/2	1/2

Иными словами, в качестве гаммы (Y) подаётся одинаковое количество нулей и единиц, или значения переменной Y имеют симметричный закон распределения.

Пусть:

Z — бит закрытого текста; то есть, переменная Z (бит) способна принимать два значения: 0 и 1;
значение Z вычисляется на основе значений X и Y по формуле:

Z = X+Y (mod 2)

или

Z = xor( X, Y )

или

Z = X ⊕ Y

Найдём следующие вероятности:

P(Z=0) — вероятность события, заключающегося в том, что переменная Z принимает значение 0;
P(Z=1) — вероятность события, заключающегося в том, что переменная Z принимает значение 1.

Используем формулы:

сложения вероятностей несовместных событий:

P(A+B) = P(A) + P(B);

умножения вероятностей независимых событий:

P(A*B) = P(A) * P(B).

Вероятность того, что переменная Z примет значение 0:

P(Z=0) = P( X=0, Y=0 ) + P( X=1, Y=1 ) =
= P(X=0) * P(Y=0) + P(X=1) * P(Y=1) =
p * 1/2 + (1-p) * 1/2 = 1/2.

Вероятность того, что переменная Z примет значение 1:

P(Z=1) = 1 - P(Z=0) = 1/2

То есть, так как P(Z=0) и P(Z=1) не зависят от p, p может принимать любое значение.

Запишем закон распределения значений переменной Z:

Z	0	1
Pi	1/2

Закон распределения Z оказался симметричным, как и закон распределения гамма (Y) или шум. То есть, Z не содержит никакую информацию из X (в Z нет p). Это доказывает, что шифр является абсолютно стойким.

Требования к гамме

Для каждого сообщения использовать новую гамму (повторное использование гаммы недопустимо).

Для формирования гаммы использовать аппаратные генераторы случайных чисел на основе физических процессов.

Длина гаммы должна быть не меньше длины защищаемого сообщения.

Примечания

Литература

Ященко В. В. Введение в криптографию.

Ссылки

См. также

Псевдослучайная последовательность

@@ Строка 37: / Строка 37: @@
 [[Шеннон, Клод Элвуд|Клод Шеннон]] доказал, что при определённых свойствах гаммы этот метод шифрования является абсолютно стойким (то есть, не поддающимся взлому).
-''Доказательство Шеннона''.
+'''Доказательство Шеннона'''.
+Пусть X, Y и Z — дискретные [[случайная величина|случайные величины]].
 Пусть:
+* X — значение [[бит]]а [[открытый текст|открытого текста]]; то есть, переменная X (бит) способна принимать два значения: 0 и 1;
-* X и Y — [[случайная величина|случайные величины]] дискретного типа;
+* p — вероятность события, заключающегося в том, что переменная X примет значение 0;
-* X — случайная величина для
+* (1-p) — вероятность протовоположного события (то есть, вероятность того, что переменная X примет значение 1).
-открытого текста;
-* Y — случайная величина для гаммы,
-тогда [[функция распределения|закон распределения]] X будет выглядеть так:
+Запишем [[функция распределения|закон распределения]] значений X:
-{| border=1
- !X
+{| class="wikitable"
- !0
- !1
+ ! X || 0 || 1
  |-
- !Pi
+ ! Pi
- |p
+ | p || 1-p
- |1-p
  |}
-Используем p и 1-p, так как [[вероятность]] встречаемости букв в разных словах различна. Закон распределения Y:
+Используем p и 1-p, так как [[вероятность]] встретить одну букву в разных словах различна.
+Пусть:
-{| border=1
+* Y — бит псевдослучайной последовательности (гаммы); то есть, переменная Y (бит) способна принимать два значения: 0 и 1;
- !Y
+* каждое из значений Y равновероятно; то есть, вероятности получить 0 или 1 равны 1/2.
- !0
- !1
+Запишем [[функция распределения|закон распределения]] значений Y:
+{| class="wikitable"
+ ! Y || 0 || 1
  |-
- !Pi
+ ! Pi
- |1/2
+ | 1/2 || 1/2
- |1/2
  |}
-То есть в качестве гаммы подаётся одинаковое количество единиц и
+Иными словами, в качестве гаммы (Y) подаётся одинаковое количество нулей и единиц, или значения переменной Y имеют симметричный закон распределения.
-нулей (у Y симметричный закон распределения).
+Пусть:
-Z — случайная величина дискретного типа для закрытого текста. Из картинки выше
+* Z — бит закрытого текста; то есть, переменная Z (бит) способна принимать два значения: 0 и 1;
-видно, что Z=X+Y(mod 2).
+* значение Z вычисляется на основе значений X и Y по формуле:
-Вычислим вероятности встречаемости нулей и единиц в законе распределения Z:
+: Z = X+Y (mod 2)
+: или
+: Z = [[Сложение по модулю 2|xor]]( X, Y )
+: или
+: Z = X [[Сложение по модулю 2|⊕]] Y
+Найдём следующие вероятности:
-Используя:
+* P(Z=0) — вероятность события, заключающегося в том, что переменная Z принимает значение 0;
+* P(Z=1) — вероятность события, заключающегося в том, что переменная Z принимает значение 1.
+Используем формулы:
-. P(A+B)=P(A)+P(B), если A и B не совместны.
+* сложения вероятностей [[Несовместные события|несовместных событий]]:
+: P(A+B) = P(A) + P(B);
+* умножения вероятностей [[Независимость (теория вероятностей)|независимых]] событий:
+: P(A*B) = P(A) * P(B).
+Вероятность того, что переменная Z примет значение 0:
-. P(A*B)=P(A)*P(B), если A и B независимы.
+ P(Z=0) = P( X=0, Y=0 ) + P( X=1, Y=1 ) =
-Имеем:
+ = P(X=0) * P(Y=0) + P(X=1) * P(Y=1) =
+ p * 1/2 + (1-p) * 1/2 = 1/2.
+Вероятность того, что переменная Z примет значение 1:
-P(Z=0) = P(X=0,Y=0)+P(X=1,Y=1) = P(X=0)*P(Y=0)+P(X=1)*P(Y=1) =
-p*1/2+(1-p)*1/2 = 1/2 (для любого p!)
+ P(Z=1) = 1 - P(Z=0) = 1/2
+То есть, так как P(Z=0) и P(Z=1) не зависят от p, p может принимать любое значение.
-P(Z=1) = 1-P(Z=0) = 1/2
-То есть закон распределения Z:
+Запишем [[функция распределения|закон распределения]] значений переменной Z:
+{| class="wikitable"
-{| border=1
- !Z
+ ! Z || 0 || 1
- !0
- !1
  |-
- !Pi
+ ! Pi
- |1/2
+ | 1/2 | 1/2
- |1/2
  |}
+Закон распределения Z оказался симметричным, как и закон распределения гамма (Y) или шум. То есть, Z не содержит никакую информацию из X (в Z нет p). Это доказывает, что шифр является абсолютно стойким.
-Таким образом, закон распределения Z оказывается симметричным, то есть получается
-та же гамма или шум (Z не содержит никакую информацию из X, то есть в Z нет p).
-Это доказывает что шифр является абсолютно стойким.
 == Требования к гамме ==

Гаммирование: различия между версиями

Версия от 05:40, 30 марта 2015

Содержание

Визуальное представление

Стойкость

Требования к гамме

Примечания

Литература

Ссылки

См. также

Навигация

Гаммирование: различия между версиями

Версия от 05:40, 30 марта 2015

Визуальное представление

Стойкость

Требования к гамме

Примечания

Литература

Ссылки

См. также

Навигация

Поиск