Crypto basics: гаммирование
===========================
Настоящий текст является логическим продолжением серии статей по
основам криптографии в журнале FDS (y0 m0w1 :)). Речь в данном случае
пойдет о технике "гаммирования" (симметричный алгоритм), основанной на
использовании конгруэнтного датчика псевдослучайных чисел (ДПЧ) и
некоторого ключа. Методика крайне проста,поэтому сразу перейдем к делу.
У нас есть некоторое исходное сообщение,состоящее из последовательности
цифр в диапазоне 0-7 (состоять оно, конечно же, может из любого словаря
символов - мы рассмотрим частный случай для упрощения задачи).
Прежде всего, исходную десятичную последовательность нужно перевести в
двоичные символы. Для этого воспользуемся следующего вида функцией:
def dectobin(decimal):
""" Decimal -> binary """
binary = []
while decimal != 0:
binary.append(decimal%2)
decimal = decimal/2
if len(binary) < 3: # Выравниваем
while len(binary) < 3: # до трех
binary.append(0) # символов
binary.reverse()
return binary
И так, в цикле, для каждого из символов исходного сообщения. Стоит
отметить, что для кодирования нечисловых значений нужно воспользоваться
функцией ord(),которая возвращает ASCII-код указанного символа. В итоге
у нас должен получиться список триад binary_message.
Теперь, собственно, само шифрование. Однако тут необходимо
некоторое теоретическое введение, чтобы все было понятно.
+-------------->>-------------+--------+
| ____ ____ ____ ____ | ____ |
| | | | | | | | | | | | |
G <--|-| s0 |-| s1 |-| s2 |-| s3 |-|-| s4 |-|
| |____| |____| |____| |____| | |____| |
| | |
| 1 1 1 0 | 0 |
+--------------<<-----------( + )------+
Представим себе простое устройство, состоящее из регистров s[0-4] и
сумматора (на схеме изображен как ( + )). Начальное заполнение
регистров произвольно, в данном случае - 11100. Как работает
устройство: в цикле происходит сдвиг значений регистров влево, при том,
что за каждый проход значение s0 суммируется (сложение по модулю 2) со
значением регистра s4 (это значит, что используется ключ "x5=x0 ^ x4").
Гамма генерируется до нужного размера (пока ее длина не станет равной
длине кодируемого сообщения) взятием значения s0 при каждой итерации.
Вот и все. Поясню на примере. Возьмем начальное заполнение регистров
(N), равное 11100:
N: 1 1 1 0 0
------------
1: 1 1 0 0 1
2: 1 0 0 1 0
3: 0 0 1 0 1
4: 0 1 0 1 1
5: 1 0 1 1 1
6: 0 1 1 1 0
7: 1 1 1 0 0
Как вы видите, на 7 итерации начальное заполнение вновь стало равным
N. Это называется периодом повторения гаммы (в данном случае период
равен 7). Чем больше период, тем сильнее будет считаться
используемый шифр. Максимальное значение периода можно узнать
математически, для этого используется формула: 2 в степени
число_регистров. В нашем с вами случае - 2**5 = 32. Величина периода
зависит от начального заполнения и ключа. Сам по себе, ключ задает
количество регистров и расположение сумматора.
Вот еще пара примеров:
+----------------+--------------+--------+
Нач. заполнение | Ключ | Период
+----------------+--------------+--------+
1 0 1 0 1 x5 = x0 ^ x4 21
1 0 0 0 0 x5 = x0 ^ x3 31
1 0 0 0 0 x5 = x0 ^ x4 21
1 0 0 1 1 x5 = x0 ^ x4 21
А теперь представьте, что, например, регистров не 5, а 10, да еще и
сумматоров несколько.
На всякий случай напомню, как выполняется операция сложения по модулю 2
(также известная как Побитовое Исключающее ИЛИ или XOR):
>>> 1 ^ 0
1
>>> 0 ^ 1
1
>>> 0 ^ 0
0
>>> 1 ^ 1
0
То есть 1 получается в результате сложения 1 и 0, во всех остальных
случаях - 0.
Для реализации алгоритма мы будем использовать две функции. Одна
(gammaRoll()) будет сохранять значение s0 в каждой итерации цикла и
сдвигать значения регистров нужное число раз, вторая (gammaAll())
будет складывать по модулю 2 нужные регистры и возвратит саму гамму.
Payload = [1,1,1,0,0] # начальное заполнение
TempPayload = Payload[:] # копия нач. заполнения
def gammaRoll():
""" Get s0 value """
toGamma = Payload[0] # берем первый символ от нач. заполнения
# сдвигаем значения регистров влево
for i in range(0,len(Payload)-1): TemPayload[i] = TemPayload[i+1]
return toGamma
def gammaAll(NotCodedWord):
""" Get the whole gamma """
Period = 0 # счетчик периода (для красоты)
Gamma = []
# пока длина гаммы не равна длине кодируемого слова
while len(Gamma) != len(NotCodedWord):
first = gammaRoll() # получаем значение первого символа
# побитово складываем s0 и "старый" s4
TemPayload[len(Payload)-1] = (first ^ TemPayload[len(Payload)-2])
Period += 1 # увеличиваем значение периода
Gamma.append(first) # добавляем первый символ к гамме
return Gamma, Period
В результате выполнения функции gammaAll() мы получим гамму нужного
размера. Теперь осталось зашифровать при ее помощи исходное сообщение.
Шифрование выполняется опять же побитовым сложением гаммы с исходным
сообщением. Вот функция наложения гаммы:
def gammaApply(Gamma,NotCodedWord):
""" Applyes gamma to plain message """
i = 0
CodedWord = []
# тут вроде все просто, комментарии не нужны :).
while i != len(Gamma):
# поэлементное сложение гаммы и исх. сообщения
CodedWord.append(int(Gamma[i])^NotCodedWord[i])
i += 1
return CodedWord
При выполнении gammaApply() мы получим собственно закодированное
сообщение. Теперь самое интересное. Для расшифровки этого
сообщения нам нужно снова сгенерировать гамму (с использованием тех
же начального заполнения и ключа), а затем наложить ее на зашифрованное
сообщение.
Полученную двоичную последовательность нам нужно перевести в десятичные
числа. Для этого будем использовать следующую функцию (алгоритм
позаимствован из FDS#5):
def bintodec(binary):
""" Binary -> decimal """
Tmp = ''
decimal = 0
binLen = len(binary)
while binLen > 0:
Tmp += binary[binLen-1]
binLen -= 1
for i in range(0,len(Tmp)):
decimal += int(Tmp[i])*(2**i)
return decimal
Полный листинг программы вы найдете в /include/gamma/Gamma.py
Работает она так:
> python Gamma.py -e plain := зашифровать
> python Gamma.py -d crypted := расшифровать
Спасибо S**** за помощь в составлении алгоритма.
В программе допущено несколько досадных ошибок, которые рекомендуется
исправить перед использованием.
--
..np: Abruptum - Obscuratatem advoco amplectere me (part 2).mp3
