ИСПОЛЬЗОВАНИЕ ШИФРА ХИЛЛА В СОВРЕМЕННЫХ ИНФОРМАЦИОННЫХ СИСТЕМАХ

История и описание шифра

Шифр Хилла является основанным на модульной арифметике и линейной алгебре полиграммным шифром. Он был изобретен американским математиком Лестером Хиллом в конце 20-х годов прошлого века. И хотя практического применения ему найти не удалось, данный шифр считают первым шифром, заложившим в криптографию базовые математические методы.

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

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

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

Недостатками данного шифра являются:

• Высокая линейность (неустойчивость к взлому);
• Неприменимость к современным информационным системам;
• Избыточно большой по сравнению с блоком текста ключ.

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

Проблемы применимости шифра Хилла в современных информационных системах

Рассмотрим поставленные проблемы подробнее:

• Неприменимость.

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

• Избыточность ключа.

Использование матриц-столбцов в качестве матриц сообщений приводит к очень неудобному соотношению длин, а именно:

где  – длина ключа, а  – длина блока сообщения. Имеет смысл пересмотреть размеры матриц с целью достижения лучшего соотношения.

• Линейность.

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

Предлагаемые улучшения алгоритма

• Неприменимость.

Как было написано выше, модуль 26 является неприменимым для данного способа шифрования. Изначально Хиллом задумывалось шифровать только английские буквы, поэтому модуль был равен количеству букв в английском алфавите. Но с развитием информационных систем появились и другие способы представления информации, с многими из которых мы имеем дело в повседневности. Хорошим решением в общем случае было бы использование модуля, равного 256. Именно столькими комбинациями битов может представляться байт - неразделимая часть любого файла.

• Избыточность ключа.

В силу необходимости обратимости матрицы ключа можно утверждать, что только матрица ключа обязана быть квадратной, в то время как матрицам С и М быть квадратными и не нужно, а достаточно только, чтобы количество строк или столбцов было равно количеству строк ключа для умножения на ключ справа или слева соответственно. Однако оптимальным вариантом будет использование квадратных матриц в качестве С и М, ведь в таком случае длина ключа будет равна длине сообщения, а использовать ключ, который короче сообщения, считается нецелесообразным в криптографии. Плюс ко всему, при использовании квадратных С и М мы сможем умножать ключ как справа, так и слева без дополнительных транспонирований. Таким образом, длина ключа в большинстве случаев станет равной длине блока сообщения. Однако возникает другая проблема: что делать, если длина блока сообщения меньше, чем количество элементов матрицы? А здесь можно применить криптографическое дополнение, например, в недостающие элементы матрицы записать число, равное количеству недостающих элементов. Этот подход достаточно распространен и описан в спецификации PKCS.

• Линейность.

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

Таблица 1.

Блок перестановок 16х16

Реализация улучшенного алгоритма

Рисунок 1. Блок-схема шифра

Процесс шифрования можно разделить на пять этапов. Для начала шифротекст разбивается на блоки по 16 байт, где каждый блок будет представлять собой матрицу 4х4. Если в последнем блоке не достает байтов до 16, пустые места заполнятся значениями, равными их количеству. Вторым шагом к каждому блоку применяются S-блоки, целью которых является понижение уязвимости алгоритма к криптоанализу путем повышения нелинейности. Следующим шагом каждый из блоков представляется матрицей и умножается на ключ. Ключ генерируется таким образом, чтобы удовлетворять критерию обратимости:

По найденному ключу находится обратная матрица, которая будет использоваться в процессе дешифрования:

Затем результирующее произведение перемешивается снова, но уже по обратному правилу. Наконец, все блоки соединяются в один шифротекст в прямом порядке, на этом этапе шифр закончил свою работу.

Процесс дешифрования отличается от шифрования лишь тем, что в качестве ключа используется матрица, обратная к ключу шифрования.

Рисунок 2. Пример работы алгоритма

Вывод

В данной работе мы изучили и описали алгоритм шифрования, предложенный Хиллом, остановились на рассмотрении основных недостатков шифра, наличие которых делало шифр непригодным в современности, предложили свои способы и возможности решения проблем применимости и линейности и реализовали улучшенный алгоритм на языке программирования Python, код которого указан в Приложении.

Список литературы:

1. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черёмушкин А.В. Основы криптографии. Гелиос АРВ, 2002. — 480 с.
2. Брюс Шнайер. Прикладная криптография. Триумф, 2002. — 816 с.
3. Mark Stamp, Richard M. Low. Applied Cryptanalysis: Breaking Ciphers in the Real World. Wiley-IEEE Press, 2007.— 424 с.

Приложение.

Код программы, реализующей алгоритм.

import numpy

import random

class HillCipher:

    n = 4

    modulus = 256

    sBox = [

         5, 14,  7, 10,

        15,  3,  9,  2,

        11,  0, 13,  4,

        6, 12,  1,  8

    ]

    invSBox = [

         9, 14,  7,  5,

        11,  0, 12,  2,

        15,  6,  3,  8,

        13, 10,  1,  4

    ]

    def __GetDeterminant(self, matrix):

        determinant = int(round(numpy.linalg.det(matrix)))

        return determinant % self.modulus

    def __GetReverseDeterminantModulo(self, determinant):

        m = self.modulus

        d = determinant

        qList = []

        while (m % d != 0):

            qList.append(m // d)

            m, d = d, m % d

        qList.append(m // d)

        PList = []

        PList.append(qList[0])

        PList.append(1 + qList[1] * PList[0])

        for i in range(2, len(qList)):

            PList.append(PList[-1] * qList[i] + PList[-2])

        reverseDeterminant = (-1) ** (len(qList) - 1) * PList[-2]

        while (reverseDeterminant < 0):

            reverseDeterminant += 256

        return reverseDeterminant

    def __MatrixGeneration(self):

        matrix = numpy.empty([self.n, self.n])

        while True:

            for i in range(self.n):

                for j in range(self.n):

                    matrix[i][j] = random.randint(0, self.modulus - 1)

            if (self.__GetDeterminant(matrix) % 2 != 0):

                break

        return matrix

    def __MatrixProduct(self, matrix, keyMatrix):

        result = numpy.matmul(matrix, keyMatrix)

        for i in range(self.n):

            for j in range(self.n):

                result[i][j] %= self.modulus

        return result

    def __GetInverseMatrix(self, matrix):

        invmtr = numpy.linalg.inv(matrix)

        invmtr *= numpy.linalg.det(matrix)

        determinant = 0

        determinant = self.__GetDeterminant(matrix)

        reverseDeterminant = self.__GetReverseDeterminantModulo(determinant)

        invmtr *= reverseDeterminant

        for i in range(self.n):

            for j in range(self.n):

                invmtr[i][j] = round(invmtr[i][j]) % self.modulus

        return invmtr

    def __ShuffleText(self, block):

        newBlock = ['0'] * len(block)

        for i in range(len(block)):

                newBlock[self.sBox[i]] = block[i]

        result = ''.join(newBlock)

        return result

    def __DeshuffleText(self, block):

        newBlock = ['0'] * len(block)

        for i in range(len(block)):

                newBlock[self.invSBox[i]] = block[i]

        result = ''.join(newBlock)

        return result

    def __SplittingText(self, text):

        listOfBlocks = []

        lengthOfListOfBlocks = 0

        if (len(text) % (self.n ** 2) != 0):

            lengthOfListOfBlocks = len(text) / (self.n ** 2) + 1

            text += chr((self.n ** 2) - (len(text) % (self.n ** 2))) * ((self.n ** 2) - (len(text) % (self.n ** 2)))

        else:

            lengthOfListOfBlocks = len(text) / (self.n ** 2)

        for i in range(lengthOfListOfBlocks):

            listOfBlocks.append(text[i * (self.n ** 2): (self.n ** 2) + i * (self.n ** 2)])

        return listOfBlocks

    def __RemovePaddig(self, block):

        bt = ord(block[-1])

        flag = True

        for i in range(bt):

            if (ord(block[-1-i]) != bt):

                flag = False

                break

        if not flag:

            return block

        else:

            return block[:-bt]

    def __ConcatBlocks(self, blocks):

        return ''.join(blocks)

    def __GetMatrix(self, block):

        matrix = numpy.empty([self.n, self.n])

        for i in range(self.n):

            for j in range(self.n):

                matrix[i][j] = ord(block[self.n * i + j])

        return matrix

    def __GetBlock(self, matrix):

        block = ''

        for i in range(self.n):

            for j in range(self.n):

                block += chr(int(round(matrix[i][j])))

        return block

    def Encrypt(self, text):

        keyMatrix = self.__MatrixGeneration()

        invKeyMatrix = self.__GetInverseMatrix(keyMatrix)

        blocks = self.__SplittingText(text)

        cipherBlocks = []

        for i in range(len(blocks)):

            blocks[i] = self.__ShuffleText(blocks[i])

            matrix = self.__GetMatrix(blocks[i])

            cipherMatrix = self.__MatrixProduct(matrix, keyMatrix)

            cipherBlocks.append(self.__DeshuffleText(

self.__GetBlock(cipherMatrix)))

        cipherText = self.__ConcatBlocks(cipherBlocks)

        return cipherText, invKeyMatrix

    def Decrypt(self, cipherText, invKeyMatrix):

        blocks = self.__SplittingText(cipherText)

        plainBlocks = []

        for i in range(len(blocks)):

            blocks[i] = self.__ShuffleText(blocks[i])

            matrix = self.__GetMatrix(blocks[i])

            plainMatrix = self.__MatrixProduct(matrix, invKeyMatrix)

            plainBlocks.append(self.__DeshuffleText(self.__GetBlock(plainMatrix)))

        plainBlocks[-1] = self.__RemovePaddig(plainBlocks[-1])

        plainText = self.__ConcatBlocks(plainBlocks)

        return plainText

if __name__ == "__main__":

    hill = HillCipher()

    while True:

        cipher, invKey =  hill.Encrypt(raw_input(">> "))

        print "Ciphertext: %s" % cipher

        print "Matrix inverse key:\n", invKey

        print "Plaintext: %s" % hill.Decrypt(cipher, invKey)