Гаммирование

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

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

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

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

Стойкость

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

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

Пусть:

• X и Y — случайные величины дискретного типа;
• X — случайная величина для

открытого текста;

• Y — случайная величина для гаммы,

тогда закон распределения X будет выглядеть так:

X	0	1
Pi	p	1-p

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

Y	0	1
Pi	1/2	1/2

То есть в качестве гаммы подаётся одинаковое количество единиц и нулей (у Y симметричный закон распределения). Z — случайная величина дискретного типа для закрытого текста. Из картинки выше видно, что Z=X+Y(mod 2). Вычислим вероятности встречаемости нулей и единиц в законе распределения Z:

Используя:

1. P(A+B)=P(A)+P(B), если A и B не совместны.

2. 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 (для любого p!)

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

То есть закон распределения Z:

Z	0	1
Pi	1/2	1/2

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

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

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

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

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

Литература

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

См. также

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