Представляю вам очередную вылазку в мир криптографии. На этот раз в роли жертвы выступает шифр гаммирования. Он не из легких, но поддался явно легче, чем перестановочный. Хотя идея самого шифра мне кажется гораздо проще — всего одна операция и никаких премудростей. Шифровать данные этим алгоритмом очень просто, но давайте посмотрим, просто ли будет его взломать?
Прежде чем продолжить чтение, обратите внимание на реализации других шифров
- Реализация и взлом шифра Цезаря;
- Реализация и взлом шифра простой перестановки;
- Реализация и взлом шифра гаммирования;
- Реализация и взлом шифра простой замены.
Шифр гаммирования
Вся суть шифра описывается красивым схематичным изображением, которое я позаимствовал у википедии.
Для того, чтобы получить зашифрованный текст достаточно сложить каждый символ открытого текста с символом гаммы. В качестве гаммы будет выступать символьная последовательность произвольной длины. В случае, если ее длина меньше длины текста, мы просто повторим последовательность нужное количество раз, чтобы хватило на зашифровку всего текста.
Расшифровка выполняется аналогичным образом. Складываем символы зашифрованного текста с символами гаммы и получаем открытый текст.
Реализация шифра гаммирования на Python
В качестве языка программирования по прежнему выступает скриптовый Python. Так как мы будем шифровать не двоичную последовательность, а текст на английском языке, то и сложение будем выполнять не по модулю 2, как на схеме, а по модулю 26.
Функция шифрования
На вход поступает открытый текст без пробелов, в виде массива символов, и ключ — гамму. Анализируем длину текста, «растягиваем» гамму до нужного размера и выполняем посимвольное сложение.
def encrypt(text, gamma): textLen = len(text) gammaLen = len(gamma) #Формируем ключевое слово(растягиваем гамму на длину текста) keyText = [] for i in range(textLen // gammaLen): for symb in gamma: keyText.append(symb) for i in range(textLen % gammaLen): keyText.append(gamma[i]) #Шифрование code = [] for i in range(textLen): code.append(alphabeth[(alphabeth.index(text[i]) + alphabeth.index(keyText[i])) % 26]) return code
Функция расшифрования
Работает аналогично. «Растягиваем» гамму и выполняем посимвольное вычитание ее из текста.
def decrypt(code, gamma): codeLen = len(code) gammaLen = len(gamma) #Формируем ключевое слово(растягиваем гамму на длину текста) keyText = [] for i in range(codeLen // gammaLen): for symb in gamma: keyText.append(symb) for i in range(codeLen % gammaLen): keyText.append(gamma[i]) #Расшифровка text = [] for i in range(codeLen): text.append(alphabeth[(alphabeth.index(code[i]) - alphabeth.index(keyText[i]) + 26) % 26]) return text
Реализация взлома шифра гаммирования
С шифрованием и дешифровкой быстро разобрались, там нет ничего сложного и необычного, самое время начать криптоанализ шифра гаммирования.
По традиции можно выделить два основных этапа.
- получение длины гаммы.
- получение значения гаммы.
Первая часть задачи решается с помощью параметра, называемого индексом совпадений. Он определяется как вероятность совпадения двух произвольных символов в строке. Считается по этой формуле.
Где n — длина текста, f_i — количество появлений в тексте i-го символа алфавита.
Мы будем перебирать длину гаммы и разбивать шифр на столбцы до тех пор, пока индекс совпадений первого столбца не будет максимально близок к 0.066 — это табличное значение индекса совпадений для литературного текста на английском языке.
На практике я заметил, что если длина подходящая, то индекс первого столбца будет гарантированно превышать значение 0.053. А когда длина плохая, он будет колебаться от 0.03 до 0.044.
На втором этапе будет использоваться уже взаимный индекс совпадений двух столбцов. Он считается по такой формуле.
Где f_i — количество появлений i-го символа в первом столбце, g_i — во втором, n — длина первого столбца, n - длина второго. В нашем случае n = n`, столбцы одинаковой длины.
Мы разбиваем код на столбцы по длине гаммы, которую нашли на прошлом этапе, и перебираем все их пары, начиная с первого. У второго столбца в паре перебираем все сдвиги(от 1 до 26) и считаем для каждого взаимный индекс совпадений. В тот момент, когда индекс будет близок к 0.066, запоминаем смещение и переходим к следующей паре столбцов.
После этой процедуры мы получим относительные сдвиги второго столбца относительно первого, третьего относительно второго, четвертого относительно третьего и так далее для всех столбиков.
Следующим шагом будет вычисление правильного сдвига для первого столбца, чтобы затем применить все относительные сдвиги и получить наконец открытый текст. Сдвиг будем искать с помощью частотного анализа, в точности как в шифре Цезаря. Подробнее об этой процедуре я написал в комментариях к коду. После того, как мы нашли сдвиг первого столбика, сдвигаем все столбцы относительно своих соседей и получаем значение гаммы.
На этом описание алгоритма взлома завершено, я постарался максимально подробно его описать, но как всегда, лучше один раз глянуть код, чем сотню раз прочитать алгоритм. Комментарии писал везде, где только можно.
Исходный код функции взлома на Python
#Функция взлома шифра гаммирования
def hack(code):
codeLen = len(code)
#Подобрать длину гаммы
gammaLen = -1
for n in range(2, codeLen // 2):
#Формируем столбец
col = []
for i in range(0, codeLen, n):
col.append(code[i])
#Посчитать индекс Фридмана для каждого нулевого столбика для всех длин,
#взять за эталонную первую, при которой индекс будет максимально близок к 0.066
symbolsCount = [0 for i in range(26)]
for symb in col:
symbolsCount[alphabeth.index(symb)] += 1
FriedmanIndex = 0
for i in range(len(symbolsCount)):
FriedmanIndex += (symbolsCount[i] * (symbolsCount[i] - 1)) / (len(col) * (len(col) - 1))
#Проверить индекс на попадание в диапазон
#if abs(FriedmanIndex - 0.066) < 0.006:
if FriedmanIndex > 0.053:
#Если попал, берем n за эталон и уходим
gammaLen = n
break
print('gamma len = ', gammaLen)
#Теперь можно определить саму гамму
#Разбиваем текст на столбцы по этой длине гаммы
#формируем подстроки
rows = [] #блоки(строки)
for i in range(0, codeLen - gammaLen, gammaLen): #без последнего блока
row = [ code[i + j] for j in range(gammaLen)]
rows.append(row)
#формируем столбцы
collumns = []
for k in range(n): #выбираем номер столбца
collumn = []
for i in range(len(rows)): #выбираем строку
collumn.append(rows[i][k])
collumns.append(collumn)
#Находим относительные сдвиги столбцов с помощью взаимного индекса Фридмана(совпадений)
slides = []
for n in range(1, gammaLen):
#Находим встречаемость каждого символа в первом столбике
firstSymbolsCount = [0 for i in range(26)]
for symb in collumns[n - 1]:
firstSymbolsCount[alphabeth.index(symb)] += 1
#Ищем сдвиг для второго столбца такой, чтобы взаимный индекс Фридмана был близок к 0.066
for m in range(26):
#сдвинуть второй столбец
slideSecondCol = []
for symb in collumns[n]:
slideSecondCol.append(alphabeth[(alphabeth.index(symb) + m) % 26])
#Находим встречаемость каждого символа во втором столбике
secondSymbolsCount = [0 for i in range(26)]
for symb in slideSecondCol:
secondSymbolsCount[alphabeth.index(symb)] += 1
#Находим взаимный индекс Фридмана
FriedmanIndex = 0
for i in range(len(firstSymbolsCount)):
FriedmanIndex = FriedmanIndex + ((firstSymbolsCount[i] * secondSymbolsCount[i]) / (len(collumns[n])**2))
#Проверяем диапазон
#if abs(FriedmanIndex - 0.066) < 0.006:
if FriedmanIndex > 0.053:
#Если попали, запоминаем это смещение и останавливаем перебор
slides.append((26 - m) % 26)
break
#У нас есть взаимные сдвиги всех столбцов, теперь нужно найти сдвиг первого
#искать будем с помощью частотного анализа символов(как в шифре Цезаря)
currentSymbolsFreq = [0 for i in range(26)]
for symb in collumns[0]:
currentSymbolsFreq[alphabeth.index(symb)] += 1
for i in range(len(currentSymbolsFreq)):
currentSymbolsFreq[i] = currentSymbolsFreq[i] / len(collumns[0]) * 100
#Находим все возможные сдвиги для первого столбца
slidesOfFirstCol = []
for i in range(len(currentSymbolsFreq)):
for j in range(len(symbolsFreq)):
if abs(currentSymbolsFreq[i] - symbolsFreq[j]) < 0.12: #0.25
slidesOfFirstCol.append(i - j)
#Берем за эталонное такое смещение, которое встречалось чаще всего
finalSlide = slidesOfFirstCol[0]
maximum = slidesOfFirstCol.count(slidesOfFirstCol[0])
for slide in slidesOfFirstCol:
if slidesOfFirstCol.count(slide) > maximum:
maximum = slidesOfFirstCol.count(slide)
finalSlide = slide
#Посчитать сдвиги для столбиков, зная сдвиг первого
finalSlides = []
finalSlides.append(finalSlide)
for slide in slides:
finalSlides.append(slide)
#считаем сдвиги столбиков
for i in range(1, len(finalSlides)):
finalSlides[i] = (finalSlides[i-1] + finalSlides[i]) % 26
#Мы нашли гамму в виде сдвигов, осталось преобразовать ее в слово
gamma = []
for slide in finalSlides:
gamma.append(alphabeth[slide])
return ''.join(gamma)
Заключение
Вот уже четыре взломанных шифра на моем счету. На очереди стоит шифр простой замены, этот экспонат уже совсем непрост, но мне все равно придется его взломать, чтобы получить зачет по предмету. Так что статья про его взлом обязательно появится! А на сегодня все, спасибо за внимание!