Всем привет! Продолжается погружение в увлекательный и местами запутанный мир криптографии. Шифр простой перестановки самый легкий из перестановочных, но даже его взлом занял у меня в два раза больше времени и сил, чем шифр Цезаря. Пришлось попотеть с выбором алгоритма криптоанализа. Сначала я пробовал частотный анализ биграмм, но для этого метода нужен очень большой литературный текст, иначе частоты никогда не совпадут с эталонными. Поэтому окончательный выбор пал на метод запрещенных биграмм. Я расскажу о нем подробнее, но сначала пара слов о самом шифре, поехали!
Прежде чем продолжить чтение, обратите внимание на реализации других шифров
- Реализация и взлом шифра Цезаря;
- Реализация и взлом шифра простой перестановки;
- Реализация и взлом шифра гаммирования;
- Реализация и взлом шифра простой замены.
Шифр простой перестановки
Определение перестановки(подстановки, расстановки) приводить не буду, о каком шифре может идти речь, если не знать базовых определений?
Шифр перестановки называется простым, если элементы открытого текста меняют свои позиции только один раз. Существуют шифры множественной перестановки, в которых первым делом меняются символы в каждом блоке, а потом, например, меняются местами сами блоки. Этих крутых ребят мы сейчас трогать не будем и заострим свое внимание исключительно на первой разновидности шифра.
Итак, суть. Дан ключ — перестановка длины N, не большей, чем длина открытого текста. Во время шифрования текст делится на блоки длины N и в каждом блоке символы меняются местами в соответствии с перестановкой. Расшифровка выполняется аналогично.
В шифровании и расшифровании ничего сверхсложного и необычного нет. Все самое интересное сосредоточено во взломе. Поэтому предлагаю перейти сразу к реализации и разобрать метод запрещенных биграмм с ее помощью.
Реализация шифра перестановки на Python
Функция шифрования
Естественно, если текст не делится на длину перестановки, его нужно добить. Иногда добивают нулями, но это визуально просматривается, поэтому я добавлял случайные символы из алфавита.
На вход функция получает текст в виде массива символов и саму перестановку. Объектов для перестановки мы вводить не будем, воспользуемся обычным массивом. Пусть значение каждого индекса будет позицией, в которую перейдет символ. Например, перестановка (012) в виде массива это [1,2,0].
Исходный код функции на Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#Функция шифрования текстом с помощью перестановки permutation def encrypt(text, permutation): blockSize = len(permutation) textSize = len(text) #Выравнивание текста difference = (textSize) % blockSize if difference != 0: #добить нужным количеством символов for i in range(blockSize - difference): text.append(chr(random.randrange(ord('a'), ord('z'), 1))) #взять новый размер строки textSize = len(text) #Шифрование for i in range(0, textSize, blockSize): string = [ text[i+j] for j in range(blockSize)] for j in range(blockSize): text[i + j] = string[permutation[j]] return |
Функция расшифровки
Работает аналогично шифрованию, но ничего добивать не нужно.
Исходный код функции на Python
|
1 2 3 4 5 6 7 8 9 10 11 12 |
#Функция дешифрования кода с помощью перестановки permutation def decrypt(code, permutation): blockSize = len(permutation) codeSize = len(code) #Дешифрование for i in range(0, codeSize, blockSize): string = [ code[i+j] for j in range(blockSize)] for j in range(blockSize): code[i + j] = string[permutation[j]] return |
Криптоанализ шифра перестановки методом запрещенных биграмм
Наконец мы добрались до взлома! Естественно, раз используется метод запрещенных биграмм, нам нужен их список. Я его получил с помощь скрипта, о котором писал ранее. Могу с уверенностью сказать, что наиболее полный список получается при анализе набора сочинений Артура Конана Дойля о Шерлоке Холмсе. Единственное, что нужно учитывать — это наличие имен собственных. Для решения этой проблемы можно исключить из текста все слова, содержащие заглавную букву.
Взлом методом запрещенных биграмм можно разделить на два этапа.
— определение длины перестановки;
— нахождение самой перестановки.
На первом этапе мы должны найти все целые делители шифра. Для каждого из них разбить шифр на столбцы.
Что такое столбец. Допустим, что n равно 5, а длина шифра 10. Шифр делится ровно на два блока по пять символов и на пять столбцов по два символа. Нулевой столбец это нулевые символы из каждого блока, первый столбец — первые символы и так далее.
Разбили, теперь нужно «склеивать» столбики, то есть подставлять новый столбец справа и слева к текущему и смотреть на образующиеся биграммы. Попробовать совместить нужно все столбцы. Нам подойдет такая длина n, при которой найдется хотя бы одна склейка столбцов, не образующая запрещенных биграмм. Важная особенность, кроме такой n подойдут так же все длины, кратные ей. Это происходит потому что биграммы сохраняются, просто становится больше столбиков. Так вот, мы должны взять наименьшую такую n. На этом первый этап подошел к концу.
На очереди второй этап. У нас есть длина перестановки, делим текст на столбики. И склеиваем их. При этом заводим массив для верных позиций столбиков. Он формируется следующим образом. Допустим, что мы смогли подставить столбец с индексом 4 справа к столбцу под номером 2 так, чтобы не образовалось запрещенных биграмм. Тогда в массиве появятся такие элементы [2, 4]. Если к этим двум столбцам мы подставили 0-ой слева, массив будет выглядеть так: [0, 2, 4]. Наша задача найти место для каждого столбца. При этом нужно не забыть вести список уже использованных столбиков, чтобы каждый подставить ровно один раз. В итоге у нас получится массив длины n. Для того, чтобы получить открытый текст, достаточно просто вывести символы в соответствии с этой расстановкой.
Описание алгоритма завершено, для того, чтобы лучше его понять, нужно посмотреть и потрогать реализацию. Попробовать выводить столбики на разных итерациях и следить за тем, что происходит. Я постарался максимально подробно комментировать каждый шаг алгоритма.
Исходный код функции на Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 |
#Источник - моя программа из статьи про запрещенные биграмы. Построено на основе повестей о Шерлоке Холмсе #url - //mindhalls.ru/bad-bigram-table/ #Функция взлома шифра перестановки def hack(codeFileName): #Считываем код из файла file = open(codeFileName, 'r') code = list(file.read()) file.close() codeSize = len(code) #Найти все возможные делители длины текста dividers = [] for n in range(2, codeSize, 1): if codeSize % n == 0: dividers.append(n) #Формируем блоки длины n, не берем в рассчет последний, потому что там рандомные добитки currentPermutationSize = 0 for n in dividers: #формируем подстроки rows = [] #блоки(строки) for i in range(0, codeSize-n, n): #codeSize-n без последнего блока row = [ code[i+j] for j in range(n)] rows.append(row) #формируем столбцы collums = [] for k in range(n): #выбираем номер столбца collum = [] for i in range(len(rows)): #выбираем строку collum.append(rows[i][k]) collums.append(collum) ''' Подставлять столбцы справа и слева, если появилась запрещенная биграмма подставить другой, если запретных биграмм нет хотя бы в одной подстановке столбцов, берем эту длину перестановки за эталонную. БЕРЕМ ПЕРВУЮ ТАКУЮ ДЛИНУ, потому что дальше будут подходить ее множители (если эталонная 12, то и 24 тоже подойдет) ''' findGoodBigrammFlag = False #Флаг, что нашлась подстановка без плохих биграмм for i in range(len(collums)): #i - номер столбца, к которому подставляем for j in range(len(collums)): #j - номер столбца, который подставляем if i == j: #так мы переберем все подстановки столбцов continue #Составляем список всех биграмм с текущими столбиками bigramms = [ collums[i][k] + collums[j][k] for k in range(len(collums[i]))] ''' Теперь нужно проверить, есть ли запретные биграммы в такой подстановке столбцов если хотя бы в одной подстановке столбцов нет запрещенных биграмм, то скорее всего такая длинна эталонная ''' findBadBigrammFlag = False for bigramm in bigramms: if bigramm in badBigramms: #Нашли плохую биграмму в такой подстановке столбцов findBadBigrammFlag = True #Если в такой подстановке столбцов для этой n НЕ БЫЛО плохих биграмм, то #эта n наща эталонная if findBadBigrammFlag == False: findGoodBigrammFlag = True #забираем нашу n и уходим из беребора делителей if findGoodBigrammFlag == True: currentPermutationSize = n break print('currentPermutationSize: ', currentPermutationSize) ''' Есть длина, теперь можно найти саму перестановку. Будем подставлять столбцы слева и справа. Тем самым формируя текст. Гарантированно, что для каждого i-го столбика к нему справа или слева можно подставить ВСЕГО один какой-нибудь столбец ''' #формируем блоки для данной длины перестановки rows = [] #блоки(строки) for i in range(0, codeSize-currentPermutationSize, currentPermutationSize): row = [ code[i+j] for j in range(currentPermutationSize)] rows.append(row) #формируем столбцы collums = [] for k in range(currentPermutationSize): #выбираем номер столбца collum = [] for i in range(len(rows)): #выбираем строку collum.append(rows[i][k]) collums.append(collum) #задача: подставлять столбцы справа и слева к нулевому #Если подставить удалось, запомнили это и подставляем к получившемуся еще один справа или слева и так далее collumsPositions = [0] #Массив позици столбцов. В начале [0] это стоит только нулевой столбец #Если массив [1,0,2] - это значит что мы смогли к нулевому столбцу слева подставить 1, а справа 2 usedIndexes = [0] #индексы уже подставленных столбцов, их мы больше не подставляем while len(collumsPositions) != currentPermutationSize: #вайл до тех пор, пока не подставим все столбцы for i in range(len(collums)): #берем какой-то столбец if i in usedIndexes: #Проверяем, что еще его не брали continue #подставляем справа bigramms = [ collums[collumsPositions[len(collumsPositions)-1]][k] + collums[i][k] for k in range(len(collums[i]))] findBadBigrammFlag = False for bigramm in bigramms: if bigramm in badBigramms: findBadBigrammFlag = True #Если смогли подставить столбец i справа без плохих биграмм if findBadBigrammFlag == False: #Формируем правильный список. Добавили справа collumsPositions.append(i) usedIndexes.append(i) #подставляем слева bigramms = [ collums[i][k] + collums[collumsPositions[0]][k] for k in range(len(collums[i]))] findBadBigrammFlag = False for bigramm in bigramms: if bigramm in badBigramms: findBadBigrammFlag = True #Если смогли подставить столбец i слева без плохих биграмм if findBadBigrammFlag == False: #Формируем правильный список. Добавили слева #Вставки в начало листа нет, поэтому создаем новый и пишем туда, что было temp = [i] #i-ый столбец ставим слева for k in collumsPositions: temp.append(k) collumsPositions = temp usedIndexes.append(i) #Выводим на экран позиции, согласно которым нужно слепить столбики print(collumsPositions) #Получили позиции столбцов, осталось вывести текст в этом порядке и все! text = [] for i in range(len(collums[0])): for j in range(len(collumsPositions)): text.append(collums[collumsPositions[j]][i]) print('text:') print(''.join(text)) return text |
Заключение
Дело сделано, перестановочный шифр реализован и взломан. Следующий подопытный — шифр гаммирования, статья о нем выйдет через некоторое время. Справедливости ради стоит заметить, что взлом гаммирования проще в понимании и реализации. Поэтому я надеюсь не затягивать с ним. На этом все, спасибо за внимание!