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

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

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

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

Пусть:

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

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

${\displaystyle X}$	${\displaystyle 0}$	${\displaystyle 1}$
${\displaystyle Pi}$	${\displaystyle p}$	${\displaystyle (1-p)}$

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

Пусть:

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

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

${\displaystyle Y}$	${\displaystyle 0}$	${\displaystyle 1}$
${\displaystyle Pi}$	${\displaystyle {\frac {1}{2}}}$	${\displaystyle {\frac {1}{2}}}$

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

Пусть:

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

${\displaystyle Z=X+Y}$ (mod 2)

или

Z = xor(X, Y)

или

Z = X ⊕ Y

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

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

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

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

${\displaystyle P(A+B)=P(A)+P(B)}$;

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

${\displaystyle P(A*B)=P(A)*P(B)}$.

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

${\displaystyle 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}$.

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

${\displaystyle P(Z=1)=1-P(Z=0)=1/2}$.

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

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

${\displaystyle Z}$	${\displaystyle 0}$	${\displaystyle 1}$
${\displaystyle Pi}$	${\displaystyle {\frac {1}{2}}}$	${\displaystyle {\frac {1}{2}}}$

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

• Для шифрования каждого нового сообщения нужно использовать новую гамму. Повторное использование гаммы недопустимо ввиду свойств операции «xor». Рассмотрим пример: с помощью одинаковой гаммы Y зашифрованы два открытых текста X₁ и X₂, получено две шифрограммы Z₁ и Z₂:

${\displaystyle Z_{1}=X_{1}\oplus Y}$

${\displaystyle Z_{2}=X_{2}\oplus Y}$

Выполним сложение двух шифрограмм, используя операцию «xor»:

${\displaystyle Z_{1}\oplus Z_{2}=(X_{1}\oplus Y)\oplus (X_{2}\oplus Y)=X_{1}\oplus X_{2}}$

Результат зависит от открытых текстов X₁ и X₂ и не зависит от гаммы Y. Ввиду избыточности естественных языков результат поддаётся частотному анализу, то есть открытые тексты можно подобрать, не зная гамму Y.

• Для формирования гаммы (последовательности псевдослучайных чисел) нужно использовать аппаратные генераторы случайных чисел, основанные на физических процессах. Если гамма не будет случайной, для получения открытого текста потребуется подобрать только начальное состояние (англ. seed) генератора псевдослучайных чисел.
• Длина гаммы должна быть не меньше длины защищаемого сообщения (открытого текста). В противном случае для получения открытого текста потребуется подобрать длину гаммы, проанализировать блоки шифротекста угаданной длины, подобрать биты гаммы.

• Введение в криптографию (рус.) / под ред. Ященко. — Litres, 2017. — 349 с. — ISBN 978-5-457-91528-2.
• Владимир Иванов (Яндекс). Видеолекция о криптографии.

• Псевдослучайная последовательность
• Потоковый шифр
• Шифр Вернама