Телефон: 8-800-350-22-65
WhatsApp: 8-800-350-22-65

Статья опубликована в рамках: XXI Международной научно-практической конференции «Научное сообщество студентов: МЕЖДИСЦИПЛИНАРНЫЕ ИССЛЕДОВАНИЯ» (Россия, г. Новосибирск, 18 мая 2017 г.)

Наука: Математика

Скачать книгу(-и): Сборник статей конференции

Библиографическое описание:
Буторов В.А., Горячев В.А. ИСПОЛЬЗОВАНИЕ ШИФРА ХИЛЛА В СОВРЕМЕННЫХ ИНФОРМАЦИОННЫХ СИСТЕМАХ // Научное сообщество студентов: МЕЖДИСЦИПЛИНАРНЫЕ ИССЛЕДОВАНИЯ: сб. ст. по мат. XXI междунар. студ. науч.-практ. конф. № 10(21). URL: https://sibac.info/archive/meghdis/10(21).pdf (дата обращения: 17.10.2021)
Проголосовать за статью
Конференция завершена
Эта статья набрала 60 голосов
Дипломы участников
У данной статьи нет
дипломов

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

Буторов Владислав Андреевич

студент, факультет информатики, Самарский Национальный Исследовательский Университет имени академика С.П.Королёва

РФ, г. Самара

Горячев Вячеслав Андреевич

студент, факультет информатики, Самарский Национальный Исследовательский Университет имени академика С.П.Королёва

РФ, г. Самара

Научный руководитель Тишин Владимир Викторович

доц., кафедра прикладной математики, Самарский Национальный Исследовательский Университет имени академика С.П.Королёва

 РФ, г. Самара

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

Таблица 1.

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

 

00

01

10

11

00

0101

1100

0111

1010

01

1111

0011

1001

0010

10

1011

0000

1101

0100

11

0110

1100

0001

1000

 

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

Рисунок 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)

Проголосовать за статью
Конференция завершена
Эта статья набрала 60 голосов
Дипломы участников
У данной статьи нет
дипломов

Оставить комментарий

Форма обратной связи о взаимодействии с сайтом