Гаммирование является широко применяемым криптографическим преобразованием.
Под гаммированием понимают процесс наложения по определенному закону гаммы шифра на открытые данные. Гамма шифра — это псевдослучайная последовательность, выработанная по заданному алгоритму для шифровки открытых данных и дешифровки зашифрованных данных.
Процесс шифровки заключается в генерации гаммы шифра с помощью датчика псевдослучайных чисел и наложении полученной гаммы на исходный открытый текст обратимым образом, например с использованием операции сложения по модулю 2.
Следует отметить, что перед шифровкой открытые данные разбивают на блоки Tо(i) одинаковой длины, обычно по 64 бита. Гамма шифра вырабатывается в виде последовательности блоков Гш(i) аналогичной длины.
Уравнение шифровки можно записать в виде
Тш(i) = Гш(i) A То(i) , i = 1 … M,
где Тш(i) i-й блок шифртекста;
Гш(i) i-й блок гаммы шифра;
То(i) i-й блок открытого текста;
M количество блоков открытого текста.
Процесс дешифровки сводится к повторной генерации гаммы шифра и наложению этой гаммы на зашифрованные данные. Уравнение дешифровки имеет вид
То(i)= Гш(i)A Тш(i) , i = 1 … M.
Достоинства и недостатки метода.
Получаемый этим методом шифртекст достаточно труден для раскрытия, поскольку ключ здесь является переменным. По сути дела гамма шифра должна изменяться случайным образом для каждого шифруемого блока. Если период гаммы превышает длину всего шифруемого текста и злоумышленнику неизвестна никакая часть исходного текста, то такой шифр можно раскрыть только прямым перебором всех вариантов ключа. В этом случае криптостойкость шифра определяется длиной ключа.
Однако, метод гаммирования становится бессильным, если злоумышленник узнает фрагмент исходного текста и соответствующую ему шифрограмму. Простым вычитанием по модулю получается отрезок псевдослучайной последовательности и по нему восстанавливается вся последовательность.
Методы генерации псевдослучайных последовательностей чисел
При шифровании методом гаммирования в качестве ключа используется случайная строка битов, которая объединяется с открытым текстом, также представленным в двоичном виде, с помощью побитового сложения по модулю 2, и в результате получается шифрованный текст. Генерирование непредсказуемых двоичных последовательностей большой длины является одной из важных проблем классической криптографии. Для решения этой проблемы широко используются генераторы двоичных псевдослучайных последовательностей.
Генерируемые псевдослучайные ряды чисел часто называют гаммой шифра или просто гаммой (по названию буквы g греческого алфавита, часто используемой в математических формулах для обозначения случайных величин).
Обычно для генерации последовательности псевдослучайных чисел применяют компьютерные программы, которые, хотя и называются генераторами случайных чисел, на самом деле вырабатывают детерминированные числовые последовательности, которые по своим свойствам очень похожи на случайные.
К криптографически стойкому генератору ПСП чисел (гаммы шифра) предъявляются три основных требования:
период гаммы должен быть достаточно большим достаточно большим для шифрования сообщений различной длины;
гамма должна быть практически непредсказуемой, что означает невозможность предсказать следующий бит гаммы, даже если известны тип генератора и предшествующий кусок гаммы;
генерирование гаммы не должно вызывать больших технических сложностей;
Длина периода гаммы является самой важной характеристикой генератора ПСЧ. По окончании периода числа начнут повторяться и их можно будет предсказать.
Один из первых способов генерации ПСЧ на ЭВМ предложил в 1946 г. Джон фон Нейман. Суть этого способа состоит в том, что каждое последующее случайное число образуется возведением в квадрат предыдущего числа с отбрасыванием цифр младших и старших разрядов. Однако этот способ оказался ненадежным и от него вскоре отказались.
Из известных процедур генерации последовательности ПСЧ наиболее часто применяется так называемый линейный конгруэнтный генератор. Этот генератор вырабатывает последовательность ПСЧ Y1, Y2, …, Yi-1, Yi, …, используя соотношение
Yi = (a • Yi-1 + b) mod m,
где Yi i-е (текущее) число последовательности;
Yi-1 предыдущее число последовательности;
m – модуль;
a – множитель;
b – приращение;
а Y0 — порождающее число (исходное значение).
Текущее псевдослучайное число Yi получают из предыдущего числа Yi-1 умножением его на коэффициент а, сложением с приращением b и вычислением остатка от деления на m. Данное уравнение генерирует ПСЧ с периодом повторения, зависящим от выбранных значений a и b и может достигать значения m. Значение m обычно устанавливается равным 2n, где n — длина машинного слова в битах, либо равным простому числу, например m=231-1. Как показано Д. Кнутом, линейный конгруэнтный датчик ПСЧ имеет максимальный период тогда и только тогда, когда b — нечетное, и a mod 4 = 1.
Также для получения последовательности ПСЧ применяются аддитивные и мультипликативные генераторы.
Мультипликативный генератор вырабатывает последовательности чисел с помощью рекуррентного соотношения:
Yi = (a • Yi-1) mod m.
Требования к значениям констант a и m такие же, как и для линейного конгруэнтного генератора.
Текущее случайное число Yi аддитивного датчика получается из суммы чисел Yi-1 и Yi-2 вычислением модуля от деления этой суммы на m:
Yi = (Yi-1 + Yi-2) mod m.
Алгоритм преобразования выглядит следующим образом: проинициализировать датчик ПСЧ (1); выделить блок открытого текста; cгенерировать ГШ (2); получить блок зашифрованного текста, сложив по модулю 2 блок открытого текста с ГШ (3); в случае, если текст не закончился, перейти к пункту 2, иначе к пункту 5 (4); конец алгоритма шифровки (5).
Алгоритм обратного преобразования выполняется следующим образом: проинициализировать датчик ПСЧ; выделить блок зашифрованного текста (1); cгенерировать ГШ (2); Получить блок открытого текста, сложив по модулю 2 блок зашифрованного текста с ГШ (3); если зашифрованный текст не закончился, перейти к пункту 2, иначе к пункту 6 (4); конец алгоритма дешифровки (5).
Пример алгоритма с аддитивным генератором на Python
a = 7
m = 4096
main_str = input()
Y = [0] * 8
Y[0] = 502
for i in range(1,8):
Y[i] = (a * Y[i-1]) % m
print(Y)
gamma = ""
for i in range(len(Y)):
#print(Y[i]%26+97)
gamma += chr(Y[i]%26+97)
print(gamma)
result_str = ""
cnt = 0
for i in range(len(main_str)):
#print((ord(main_str[i]) ^ ord(gamma[cnt]))+97)
result_str += chr((ord(main_str[i]) ^ ord(gamma[cnt]))+97)
if cnt == 7:
cnt = 0
print(result_str)
Пример алгоритма с линейным конгруэнтным генератором на Python
A = 15
B = 17
M = 4096
Y0 = 4003
def Gamma(y):
gamma_list = []
for _ in range(8):
y = (A * y + B) % M
gamma_list.append(y)
return gamma_list
def Crypt():
gamma = Gamma(Y0)
with open('Sourse.txt', 'rb') as f:
while True:
temp = f.read(8)
if temp:
for i, item in enumerate(temp):
print(chr(item ^ gamma[i]))
else:
break
crypt()
Следующий пример содержит функции шифрования и расшифровки с линейным конгруэнтным генератором, текст загружается из файла Sourse.txt в кодировке utf-8, шифруется в Result.txt и заново расшифровывается Newresult.txt
Файлы создаем в блокноте или notepad++ с указанием кодировки utf-8.
A = 15
B = 17
M = 4096
Y0 = 4003
def Gamma(y):
gamma_list = []
for _ in range(8):
y = (A * y + B) % M
gamma_list.append(y)
return gamma_list
def Crypt():
gamma = Gamma(Y0)
res = open("Result.txt", "w",encoding="utf-8")
with open('Sourse.txt', 'r',encoding="utf-8") as f:
r_int = ""
r=""
while True:
temp = f.read(8)
if temp:
for i, item in enumerate(temp):
r_int = r_int + " "+str(ord(item) ^ gamma[i])
r = r +" "+chr(ord(item) ^ gamma[i])
res.write(chr(ord(item) ^ gamma[i]))
else:
break
print(r_int)
res.close()
Crypt()
def DeCrypt():
gamma = Gamma(Y0)
res = open("NewResult.txt", "w",encoding="utf-8")
with open('Result.txt', 'r',encoding="utf-8") as f:
r_int = ""
r = ""
while True:
temp = f.read(8)
if temp:
for i, item in enumerate(temp):
r_int = r_int + " " + str(ord(item) ^ gamma[i])
r = r + chr(ord(item) ^ gamma[i])
res.write(chr(ord(item) ^ gamma[i]))
else:
break
print(r_int)
res.close()
DeCrypt()