Молодогвардейцев 454015 Россия, Челябинская область, город Челябинск 89085842764
MindHalls logo

Реализация и криптоанализ шифра простой перестановки

Всем привет! Продолжается погружение в увлекательный и местами запутанный мир криптографии. Шифр простой перестановки самый легкий из перестановочных, но даже его взлом занял у меня в два раза больше времени и сил, чем шифр Цезаря. Пришлось попотеть с выбором алгоритма криптоанализа. Сначала я пробовал частотный анализ биграмм, но для этого метода нужен очень большой литературный текст, иначе частоты никогда не совпадут с эталонными. Поэтому окончательный выбор пал на метод запрещенных биграмм. Я расскажу о нем подробнее, но сначала пара слов о самом шифре, поехали!

Прежде чем продолжить чтение, обратите внимание на реализации других шифров

Шифр простой перестановки

Определение перестановки(подстановки, расстановки) приводить не буду, о каком шифре может идти речь, если не знать базовых определений?

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

Итак, суть. Дан ключ — перестановка длины N, не большей, чем длина открытого текста. Во время шифрования текст делится на блоки длины N и в каждом блоке символы меняются местами в соответствии с перестановкой. Расшифровка выполняется аналогично.

В шифровании и расшифровании ничего сверхсложного и необычного нет. Все самое интересное сосредоточено во взломе. Поэтому предлагаю перейти сразу к реализации и разобрать метод запрещенных биграмм с ее помощью.

Реализация шифра перестановки на Python

Функция шифрования

Естественно, если текст не делится на длину перестановки, его нужно добить. Иногда добивают нулями, но это визуально просматривается, поэтому я добавлял случайные символы из алфавита.

На вход функция получает текст в виде массива символов и саму перестановку. Объектов для перестановки мы вводить не будем, воспользуемся обычным массивом. Пусть значение каждого индекса будет позицией, в которую перейдет символ. Например, перестановка (012) в виде массива это [1,2,0].

Исходный код функции на Python

#Функция шифрования текста с помощью перестановки '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 =  for j in range(blockSize)]
        for j in range(blockSize):
            text[i + j] = string[permutation[j]]

    return

Функция расшифровки

Работает аналогично шифрованию, но ничего добивать не нужно.

Исходный код функции на Python

#Функция дешифрования кода с помощью перестановки permutation
def decrypt(code, permutation):
    blockSize = len(permutation)
    codeSize = len(code)

    #Дешифрование
    for i in range(0, codeSize, blockSize):
        string =  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

#Источник - моя программа из статьи про запрещенные биграмы. Построено на основе повестей о Шерлоке Холмсе
#url - http://mindhalls.ru/bad-bigram-table/
badBigramms = ['bg', 'bk', 'bq', 'bx', 'bz', 'cj', 'cv', 'cw', 'cx', 'cz', 'dx', 'dz', 'fq', 'fv', 'fx', 'fz', 'gq', 'gx', 'hq', 'hv', 'hx', 'hz', 'iy', 'jb', 'jc', 'jd', 'jf', 'jg', 'jj', 'jk', 'jl', 'jm', 'jn', 'jq', 'jr', 'js', 'jt', 'jv', 'jw', 'jx', 'jy', 'jz', 'kj', 'kq', 'kv', 'kx', 'kz', 'lq', 'lx', 'mk', 'mq', 'mv', 'mx', 'mz', 'pj', 'pq', 'pv', 'px', 'pz', 'qa', 'qb', 'qc', 'qd', 'qe', 'qf', 'qg', 'qh', 'qi', 'qj', 'qk', 'ql', 'qm', 'qn', 'qo', 'qp', 'qq', 'qr', 'qs', 'qt', 'qv', 'qw', 'qx', 'qy', 'qz', 'sx', 'tq', 'tx', 'uu', 'vb', 'vc', 'vd', 'vf', 'vg', 'vh', 'vj', 'vk', 'vl', 'vm', 'vn', 'vp', 'vq', 'vt', 'vv', 'vw', 'vx', 'vz', 'wj', 'wq', 'wv', 'wx', 'wz', 'xd', 'xg', 'xj', 'xk', 'xn', 'xz', 'yk', 'yq', 'zb', 'zc', 'zd', 'zf', 'zg', 'zj', 'zm', 'zn', 'zp', 'zq', 'zs', 'zt', 'zw', 'zx']

#Функция взлома шифра перестановки
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:
        #формируем подстроки(блоки шифра длины n)
        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)
        
        '''
        Подставлять столбцы справа и слева, если появилась запрещенная биграмма
        подставить другой. Если запретных биграмм нет ХОТЯ БЫ В ОДНОЙ подстановке столбцов,
        берем этот делитель за длину перестановки
        '''
        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

                if findBadBigrammFlag == False:
                    findGoodBigrammFlag = True


        if findGoodBigrammFlag == True:
            #Нашли длину, останавливаем перебор
            currentPermutationSize = n
            break

    print('currentPermutationSize: ', currentPermutationSize)

    '''
    Есть длина, теперь можно найти саму перестановку.
    Будем подставлять столбцы слева и справа и формировать текст так,
    чтобы не встречалось запрещенных биграмм
    '''

    #формируем блоки для данной длины перестановки
    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]
    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

Заключение

Дело сделано, перестановочный шифр реализован и взломан. Следующий подопытный —  шифр гаммирования, статья о нем выйдет через некоторое время. Справедливости ради стоит заметить, что взлом гаммирования проще в понимании и реализации. Поэтому я надеюсь не затягивать с ним. На этом все, спасибо за внимание!

  • Игорь

    Несколько issues
    У вас код неверный. Много очепяток в коде. + Избыточность в коде…
    Для простоты, при создании матрицы, можно было использовать numpy
    import numpy as np
    print(np.reshape(list(text[:144]), (-1, 12)))
    P.S. Но в общем — интересно!

    • Кузьминых Кирилл

      Избыточность есть, чтобы не терять суть и сохранить понимание алгоритма. А по поводу опечаток, я буду рад, если вы мне на них укажете. И о какой именно матрице идет речь?

      • Игорь

        Сделайте ревью кода. Вот например ошибки: стр 26, 77
        А первые функции, которые шифруют/дешифруют — вообще ничего не возвращают 😉
        Ну и на сайте у вас не видно весь код, т.к. он не flexible. Даже уменьшая картинку, весь код не увидеть, пока css не подправишь.
        По поводу матриц. — Я нашел длину. Нашел делители из 5316 символов. [2, 3, 4, 6, 12, 443, 886, 1329, 1772, 2658] — Разумно предположить, что длина ключа не будет более 12 символов. Далее я сделал матрицу из 144 символов (12 строк и 12 колонок),
        mtx = np.reshape(list(text[:144]), (-1, 12)) # Создание матрицы 12 на 12
        чего вполне хватает для поиска биграмм, триграмми квадграмм. Далее сделал 132 уникальных комбинации столбиков для проверки на вхождение запрещенных биграмм
        lst = [‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’, ‘h’, ‘i’, ‘j’, ‘k’, ‘l’]
        itertools.permutations(lst, 2) # Создал сет из 132 уникальных кортежа (варианты столбиков)
        далее проверяю, есть запрещенная биграмма в list(zip(a, b))
        рулить столбиками можно так
        a = mtx[:, 0] — нулевой столбик целиком (https://pythonworld.ru/numpy/2.html)
        и т.д.

        • Кузьминых Кирилл

          Ошибки в строках 26 и 77 были связаны с тем, что текстовый редактор WP находил подстроку ‘[code’ и пытался начинать оттуда форматировать, поэтому подстрока просто исчезла из кода. Спасибо, исправил и взял на заметку.
          Функции шифрования и дешифрования ничего и не должны возвращать. Я работаю с одной копией текста, переделать, как душе угодно может каждый лично для себя.
          Весь код прекрасно видно с горизонтальной прокруткой, это осознанный шаг чтобы строки не переносились.

          • Игорь

            PEP8, 257 не зря писали… 80 для кода, 72 для комментариев.
            Горизонтальная прокрутка это костыль, без которого стоит обходится. Юзабилити очень понижается.
            Мне, к примеру, для быстрого понимания кода нужно видеть, по-возможности, весь код целиком.
            Если функция ничего не должна возвращать, то return писать не следует. Или же стоит возвратить ответ, что функция отработала хорошо и закончила свою работу. — Так будет правильней.
            Еще ускорило бы работу программы использование кортежей, словарей и множества, вместо списков. Например:
            someSet.isdisjoint(badBigramms) # Если нет совпадений, то True
            это быстрее, чем for iteration in badBigramms, т.к. сравниваются хеши, а не сущность.
            Да.. Хотел спросить, почему сайт на WP, а не Django? И думаете ли делать разбор полетов шифра с двойной перестановкой?

          • Кузьминых Кирилл

            Костыль — это уменьшать размер шрифта ради того, чтобы все влезло. Сайт на WP, а не на джанго потому что я так захотел.
            Return писать стоит в том месте, в котором происходит логический выход из функции, а возвращать признак успешного выполнения функции не принято с тех пор, как появились исключения. Конкретно в этих функциях оставить пустой return я посчитал необходимым именно для того, чтобы подчеркнуть тот факт, что функции форматируют исходный текст, а не создают копию.
            Про стиль комментариев тут вообще неуместно говорить, ибо код несет исключительно учебный характер. В реальных проектах комментарии ограничиваются лишь документацией функций.
            Все отступления от код стайла необходимы для понимания алгоритма. Не забывайте, что это учебный проект. Суть этой статьи в реализации алгоритма. Я считаю, что проект имеет право на существование. И может послужить свою службу и помочь разобраться в алгоритме.
            По поводу шифра с двойной перестановкой. Даже если и будет его разбор, то очень и очень нескоро

  • Игорь

    Все-равно, спасибо! Очень хорошая статья получилась!

    • Кузьминых Кирилл

      Это вам спасибо за критику и внимательный взгляд, благодаря им материал на сайте будет становится все лучше и лучше