Пользователь
0,0
рейтинг
21 сентября 2015 в 11:13

Разработка → Алгоритм шифрования RC5 и его реализация на python из песочницы


Алгоритм RC5


В своём посте, я хотел бы рассказать о симметричном алгоритме шифрования RC5 и моей версии его реализации на python. Данный алгоритм разработан известнейшим криптологом Рональдом Макдональдом Ривестом — одним из разработчиков системы RSA и основателей одноименной фирмы. По количеству пользователей RC5 стоит в одном ряду с такими известными алгоритмами как IDEA и Blowfish. Аббревиатура RC обозначает, по разным источникам, либо Rivest Cipher, либо Ron's Code, что в совокупности даёт нам «шифр Рона Ривеста». Заинтересовавшихся прошу под кат.

Введение

При описании алгоритма будем использовать следующие обозначения:
  • Размер слова в битах. RC5 шифрует блоками по два слова; допустимыми значениями являются 16, 32 и 64. Данную величину рекомендуется брать равной машинному слову. Например для 32-битных машин = 32 и следовательно размер блока будет равен 64 бита
  • Количество раундов алгоритма — целое число от 0 до 255 включительно. При значении 0 шифрование выполняться не будет
  • Размер секретного ключа в байтах — целое число от 0 до 255 включительно

Для уточнения параметров, используемых в конкретном случае применяется обозначение RC5-;
например, RC5-32/12/16 обозначает алгоритм RC5 c 64-битным блоком, 12 раундами шифрования и 16-байтным ключом(данная комбинация рекомендуется Ривестом в качестве основного варианта).

Работа алгоритма состоит из двух этапов:
  • Процедура расширения ключа
  • Само шифрование

Создадим класс и конструктор инициализирующий необходимые стартовые переменные
Python listing
    def __init__(self, w, R, key):
        self.w = w
        self.R = R
        self.key = key
        self.T = 2 * (R + 1)
        self.w4 = w // 4
        self.w8 = w // 8
        self.mod = 2 ** self.w
        self.mask = self.mod - 1
        self.b = len(key)
        self.__keyAlign()
        self.__keyExtend()
        self.__shuffle()


Процедура расширения ключа

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

Выравнивание ключа

Если размер ключа(в байтах) не кратен , дополняем его нулевыми байтами до ближайшего размера кратного . После этого ключ копируется в массив , где . Проще говоря, мы копируем ключ блоками по байт (2, 4, 8 для значений 16, 32, 64 соответственно) в массив .
Например, при параметрах и значении ключа мы получим и (под 0 подразумевается нулевой байт).

Опишем необходимую функцию
Python listing
    def __keyAlign(self):
        if self.b == 0: # пустой ключ
            self.c = 1
        elif self.b % self.w8: # ключ не кратен w / 8
            self.key += b'\x00' * (self.w8 - self.b % self.w8) # дополняем ключ байтами \x00
            self.b = len(self.key)
            self.c = self.b // self.w8
        else:
            self.c = self.b // self.w8
        L = [0] * self.c
        for i in range(self.b - 1, -1, -1): # Заполняем массив L
            L[i // self.w8] = (L[i // self.w8] << 8) + self.key[i]
        self.L = L


Инициализация массива расширенных ключей

На этом шаге нам нужно сгенерировать псевдослучайные константы и по следующим формулам:

,
где
— функция округления до ближайшего нечентного
число Эйлера
золотое сечение

Так же в спецификации алгоритма приведены уже вычисленные константы для всех возможных значений :





,
все константы представлены в шестнадцатеричном виде.

Получив всё необходимое мы инициализируем массив , где



Описание функций
Python listing
    def __const(self): # функция генерации констант
        if self.W == 16:
            return (0xB7E1, 0x9E37) # Возвращает значения P и Q соответсвенно
        elif self.W == 32:
            return (0xB7E15163, 0x9E3779B9)
        elif self.W == 64:
            return (0xB7E151628AED2A6B, 0x9E3779B97F4A7C15)

    def __keyExtend(self): # Заполняем массив S
        P, Q = self.__const()
        self.S = [(P + i * Q) % self.mod for i in range(self.T)]


Перемешивание

Теперь, перед тем как приступить к шифрованию, нам осталось лишь перемешать элементы массивов L и S выполнив следующий цикл:



, где
— временные переменные, начальные значения равны 0
— массивы полученные на предыдущих шагах
Количество итераций определяется как

Python listing
    def __shuffle(self):
        i, j, A, B = 0, 0, 0, 0
        for k in range(3 * max(self.c, self.T)):
            A = self.S[i] = self.__lshift((self.S[i] + A + B), 3)
            B = self.L[j] = self.__lshift((self.L[j] + A + B), A + B)
            i = (i + 1) % self.T
            j = (j + 1) % self.c

lshift и rshift(который встретится нам чуть ниже) это операции логического сдвига влево и вправо соответственно.
Я думаю, что их комментарии будут излишними, а код можно посмотреть на github(ссылка в конце)


Структура алгоритма

Шифрование

Алгоритм представляет собой сеть Фейстеля, в каждом раунде которой(за исключением нулевого) выполняются следующие операции:

,
где
— номер текущего раунда, начиная с 1
— фрагмент расширенного ключа
— операция циклического сдвига на битов влево

В нулевом раунде выполняется операции наложения двух первых фрагментов расширенного ключа на шифруемые данные:



Стоит отметить, что под раундом подразумевается преобразования, соответствующее двум раундам обычных алгоритмов, сконструированных на основе сетей Фейстеля. За раунд RC5 обрабатывает блок целиком, в отличии от раунда сети Фейстеля обрабатывающего один подблок — чаще всего половину блока.

Соответствующий код:
Python listing
    def encryptBlock(self, data):
        A = int.from_bytes(data[:self.w8], byteorder='little')
        B = int.from_bytes(data[self.w8:], byteorder='little')
        A = (A + self.S[0]) % self.mod
        B = (B + self.S[1]) % self.mod
        for i in range(1, self.R + 1):
            A = (self.__lshift((A ^ B), B) + self.S[2 * i]) % self.mod
            B = (self.__lshift((A ^ B), A) + self.S[2 * i + 1]) % self.mod
        return (A.to_bytes(self.w8, byteorder='little')

    def encryptFile(self, inpFileName, outFileName): # в качестве параметров передаётся имя файла и открытым текстом и имя выходного файла
        with open(inpFileName, 'rb') as inp, open(outFileName, 'wb') as out:
            run = True
            while run:
                text = inp.read(self.w4)
                if not text:
                    break
                if len(text) != self.w4:
                    text = text.ljust(self.w4, b'\x00') # последняя считанная строка может быть меньше необходимого размера, что критичного для блочного шифра, поэтому мы дополняем её нулевыми байтами
                    run = False
                text = self.encryptBlock(text)
                out.write(text)


Расшифровывание

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

,
где
— операция циклического сдвига вправо
— номер раунда в обратном порядке, т.е. начиная с и заканчивая единицей.

После этого выполняются операции обратные для нулевого раунда, а именно:



Код тут:
Python listing
    def decryptBlock(self, data):
        A = int.from_bytes(data[:self.w8], byteorder='little')
        B = int.from_bytes(data[self.w8:], byteorder='little')
        for i in range(self.R, 0, -1):
            B = self.__rshift(B - self.S[2 * i + 1], A) ^ A
            A = self.__rshift(A - self.S[2 * i], B) ^ B
        B = (B - self.S[1]) % self.mod
        A = (A - self.S[0]) % self.mod
        return (A.to_bytes(self.w8, byteorder='little')
                + B.to_bytes(self.w8, byteorder='little'))

    def decryptFile(self, inpFileName, outFileName):
        with open(inpFileName, 'rb') as inp, open(outFileName, 'wb') as out:
            run = True
            while run:
                text = inp.read(self.w4)
                if not text:
                    break
                if len(text) != self.w4:
                    run = False
                text = self.decryptBlock(text)
                if not run:
                    text = text.rstrip(b'\x00') # удаляем добавленные на этапе шифрования b'\x00'
                out.write(text)


Алгоритм поразительно прост — в нем используются только операции сложения по модулю 2 и по модулю , а также сдвиги на переменное число битов. Последняя из операций представляется автором алгоритма как революционное решение, не использованное в более ранних алгоритмах шифрования (до алгоритма RC5 такие использовались только в алгоритме Madryga, не получившем широкого распространения), — сдвиг на переменное число битов является весьма просто реализуемой операцией, которая, однако, существенно усложняет дифференциальный и линейный криптоанализ алгоритма. Простота алгоритма может рассматриваться как его важное достоинство — простой алгоритм легче реализовать и легче анализировать на предмет возможных уязвимостей.

Код целиком можно посмотреть на github.
Немного криптоанализа

  • Существует класс ключей при использовании которых алгоритм можно вскрыть линейным криптоанализом. В других случаях это почти невозможно.
  • Дифференциальный криптоанализ более эффективен при атаке на данный алгоритм. Например, для алгорима RC5-32-12-16, в лучшем случае, требуется выбранных открытых текстов для успешной атаки. При использовании 18-20(и больше) раундов вместо 12 вскрыть алгоритм с помощью дифференциального криптоанализа почти невозможно.

Таким образом, наиболее реальным методом взлома алгоритма RC5 (не считая варианты с небольшим количеством раундов и с коротким ключом) является полный перебор возможных вариантов ключа шифрования. Что означает, что у алгоритма RC5 практически отсутствуют недостатки с точки зрения его стойкости. На этом и хотелось бы закончить. Всем спасибо за внимание.

UPD: Изменены операции lshift, rshift. Добавленны константы в конструктор класса. Добавлены тесты.
Спасибо mas за советы и помощь.
Дмитрий @tbb
карма
8,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (8)

  • +1
    e — экспонента
    Обычно всё-таки число e или число Эйлера в русской терминологии. А экспонента — e^x — конкретное отображение.
    • +1
      Спасибо за замечание, исправил.
  • 0
    А что у него, кстати с патентной чистотой (был US patent в 1997 на RSA Data Security) и прочей копирастией (trade mark, другие ограничения)?

    Также стоит информацию по патентну, лицензии на имплементацию и т. п. на github.
    • 0
      Все верно, правообладателем является RSA, US5835600 и US5724428. Благодарю за совет.
  • +1
    В ...self.__lshift((self.S[i] + A + B),… или в самом __lshift (и __rshift), видимо, надо ограничить агрумент модулем 2**self.W, иначе значения S и L растут за пределы «слова». Ну и через строки работать, это конечно… эээ… попробуйте что-то вроде ((val<<n)|(val>>(self.W-n))) & self.MW для сдвига, где self.TW = 2**self.W # module и self.MW = self.TW-1 # mask. Лучше было, конечно, перевести прямо из С, который есть в people.csail.mit.edu/rivest/Rivest-rc5rev.pdf, Ну а так пока дальше будут вылезать ошибки для ключа из нулей, для файлов из нулей и т.д. И ещё, такие штуки надо обязательно проверять для стандартных тестовых наборов, если такие есть в описании алгоритмов. И лучше сделать encrypt и decrypt для одиночных блоков, а потом уже, используя их, для потоков (файлов) и байтовых строк.

    Спасибо, однако, за статью. Хотя так и не понятно, рекомендуется ли RC5 и для каких применений, и насколько он распространён.
    • 0
      Спасибо большое, отличная идея использовать & (теперь я чувствую себя неловко, потому что не догадался сам) и шифровать по блокам. Если честно, у меня мало опыта в разработке(особенно на Python), на днях дочитал «Изучаем Python» (Марк Лутц) и решил, что пора попробовать свои силы. Я думаю, в течении недели перепишу код и добавлю тесты, и сделаю апдейт статьи.
  • 0
    Чем бы не заниматься, лишь бы не работой :) Довёл до какого-то рабочего состояния: С www.dropbox.com/s/52852xi7itrd6u0/RC5.c?dl=0 и Питон www.dropbox.com/s/krvs0iz4uf8x0ic/RC5.py?dl=0
  • +1
    > По количеству пользователей RC5 стоит в одном ряду с такими известными алгоритмами как IDEA и Blowfish.

    Можно какие-нибудь ссылки, откуда инфа?

    По поводу криптанализа — шифр взломан ещё в прошлом веке (с точки зрения академической криптографии), и с тех пор им почти никто не интересуется (опять же, среди криптоаналитиков). Поэтому утверждение

    > у алгоритма RC5 практически отсутствуют недостатки с точки зрения его стойкости

    слишком самоуверенно. Вы предлагаете 18-20 раундов для 32х битной версии (причем только как замечание в конце статьи), но вы не знаете какую стойкость эта версия гарантирует. 2^60? 2^70? Кроме того, «революционное решение» использовать переменные сдвиги очень сомнительное. Есть ли примеры не таких старых невзломанных шифров, использующих этот приём? А «поразительная простота» алгоритма, которая вас удивила, давно породила парадигму ARX шифров.

    Я понимаю что статья про имплементацию чего попало на питоне, но почему бы не использовать для этого современные шифры?

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