CRYPTON — алгоритм симметричного блочного шифрования (размер блока 128 бит, ключ длиной до 256 бит), разработанный южнокорейским криптологом Че Хун Лим () из южнокорейской компании Future Systems, с конца 1980-х годов работающая на рынке сетевого обеспечения и защиты информации. Алгоритм был разработан в 1998 году в качестве шифра — участника конкурса AES. Как признавался автор, конструкция алгоритма опирается на алгоритм SQUARE.
В алгоритме Crypton нет традиционных для блочных шифров сети Фейстеля. Основу данного шифра составляет так называемая SP-сеть (повторяющаяся циклическая функция из замен-перестановок, ориентированная на распараллеленную нелинейную обработку всего блока данных). Кроме высокой скорости, преимуществами таких алгоритмов является облегчение исследования стойкости шифра к методам дифференциального и линейного криптоанализа, являющимся на сегодня основными инструментами вскрытия блочных шифров.
На конкурс AES была изначально представлена версия алгоритма Crypton v0.5. Однако, как говорил Че Хун Лим, ему не хватало времени для разработки полной версии. И уже в первом этапе конкурса AES в ходе анализа алгоритмов, версия Crypton v0.5 была заменена на версию Crypton v1.0. Отличие новой версии от первоначальной заключались в изменении таблиц замен, в модификации процесса расширения ключа.
Структура алгоритма. Основные характеристики Как и другие участники конкурса AES, Crypton предназначен для шифрования 128-битовых блоков данных. При шифровании используются ключи шифрования нескольких фиксированных размеров — от 0 до 256 бит с кратностью 8 битов.
Структура алгоритма Crypton — структура «Квадрата» — во многом похожа на структуру алгоритма Square, созданного в 1997 году. Криптографические преобразования для алгоритмов с данной структурой могут быть выполнены как над целыми строками и столбцами массива, так и над отдельными его байтами. (Стоит отметить, что алгоритм Square был разработан авторами будущего победителя конкурса AES — авторами алгоритма Rijndael — Винсентом Рэйменом и Йоаном Дайменом.)
Шифрование Алгоритм Crypton представляет 128-битовый блок шифруемых данных в виде байтового массива 4×4, над которыми в процессе шифрования производится несколько раундов преобразований. В каждом раунде предполагается последовательное выполнение следующих операций: Табличная замена ; Линейное преобразование ; Байтовая перестановка ; Операция .
Табличная замена γ
Алгоритм Crypton использует 4 таблицы замен. Каждая из которых замещает 8-битовое входное значение на выходное такого же размера.
Все таблицы являются производными от основной таблицы (см. рисунок - вычисление производных таблиц замен).
Ниже представлен пример таблиц:
Таблица : 63 ec 59 aa db 8e 66 c0 37 3c 14 ff 13 44 a9 91 3b 78 8d ef c2 2a f0 d7 61 9e a5 bc 48 15 12 47 ed 42 1a 33 38 c8 17 90 a6 d5 5d 65 6a fe 8f a1 93 c2 2f 0c 68 58 df f4 45 11 a0 a7 22 96 fb 7d 1d b4 84 e0 bf 57 e9 0a 4e 83 cc 7a 71 39 c7 32 74 3d de 50 85 06 6f 53 e8 ad 82 19 e1 ba 36 cb 0e 28 f3 9b 4a 62 94 1f bd f6 67 41 d8 d1 2d a4 86 b7 01 c5 b0 75 02 f9 2c 29 6e d2 f5 8b fc 5a e4 7f dd 07 55 b1 2b 89 72 18 3a 4c b6 e3 80 ce 49 cf 6b b9 f2 0d dc 64 95 46 f7 10 9a 20 a2 3f d6 87 70 3e 21 fd 4d 7b 3c ae 09 8a 04 b3 54 f8 30 00 56 d4 e7 25 bb ac 98 73 ea c9 9d 4f 7e 03 ab 92 a8 43 0f fa 24 5c 1e 60 31 97 cd c6 79 f5 5e e5 34 76 1c 81 b2 af 0b 5d d9 e2 27 6d d0 88 c1 51 e6 9c 77 be 99 23 da eb 52 2e b5 08 05 6c b8 1b a3 69 8c d3 40 26 f1 c4 9f 35 ee 7c 4b 16
Таблица 8d b3 65 aa 6f 3a 99 03 dc f0 50 ff 4c 11 a6 46 ec e1 36 bf 0b a8 c3 5f 85 7a 96 f2 21 54 48 1d b7 09 68 cc e0 23 5c 42 9a 57 75 95 a9 fb 3e 86 4e 2b bc 30 a1 61 7f d3 15 44 82 9e 88 5a Ef f5 74 d2 12 83 fe 5d a7 28 39 0e 33 e9 c5 e4 1f c8 d1 f4 7b 41 16 18 bd 4d a3 b6 0a 64 87 ea d8 2f 38 a0 cf 6e 29 89 52 7c f6 db 9d 05 63 47 b4 92 1a de 04 17 c2 d5 08 e7 b0 a4 b9 4b 7d 2e f3 69 93 fd 77 1c 55 c6 ac 26 c9 60 e8 31 da 8f 02 3b 25 3f ad e6 cb 34 73 91 56 19 df 40 6a 80 8a fc 5b 1e c1 f8 84 f7 35 ed 0f ba 24 2a 10 ce 51 e3 c0 00 59 53 9f 94 ee b2 62 cd ab 27 76 3d f9 0c ae 4a a2 0d 3c eb 90 71 78 81 c4 5e 37 1b e5 d7 79 97 d0 d9 70 06 ca be 2c 6d 67 8b 9c b5 43 22 07 45 9b 72 dd fa 66 8c 6b af 49 b8 d6 20 14 b1 e2 6c 8e a5 32 4f 01 98 c7 13 7e d4 bb f1 2d 58
Таблица b1 72 76 bf ac ee 55 83 ed aa 47 d8 33 95 60 c4 9b 39 1e 0c 0a 1d ff 26 89 5b 22 f1 d4 40 c8 67 9d a4 3c e7 c6 b5 f7 dc 61 79 15 86 78 6e eb 32 b0 ca 4f 23 d2 fb 5e 08 24 4d 8a 10 09 51 a3 9f f6 6b 21 c3 0d 38 99 1f 1c 90 64 fe 8b a6 48 bd 53 e1 ea 57 ae 84 b2 45 35 02 7f d9 c7 2a d0 7c c9 18 65 00 97 2b 06 6a 34 f3 2c 92 ef dd 7a 56 a2 c4 88 b9 50 75 d3 e4 11 ce 4b a7 fd 3f be 81 8e d5 5a 49 42 54 70 a1 df 87 ab 7d f4 12 05 2e 27 0f c1 30 66 98 3d cb b8 e6 9c 63 e3 bc 19 fa 3a 2f 9e f2 6f 1a 28 3b c2 0e 03 c0 b7 59 a9 d7 74 85 d6 ad 41 ec 8c 71 f0 93 5d b6 1b 68 e5 44 07 e0 14 8a f9 73 cd 4e 25 bb 31 5f 4a cc 8f 91 de 6d 7b f5 b3 29 a0 17 6c da e8 04 96 82 52 36 43 5c db 8d 80 d1 e2 b4 58 46 ba e9 01 20 fc 13 16 f8 94 62 37 cf 69 9a af 77 c5 3e 7e a5 2d 0b
Таблица : b1 f6 8e 07 72 6b d5 e0 76 21 5a 14 bf c3 49 a8 ac 0d 42 f9 ee 38 54 73 55 99 70 cd 83 1f a1 4e ed 1c df 25 aa 90 87 bb 47 64 ab 31 d8 fe 7d 5f 33 8b f4 4a 95 a6 12 cc 60 48 05 8f c4 bd 2e 91 9b 53 27 de 39 e1 0f 6d 1e ea c1 7b 0c 57 30 f5 0a ae 66 b3 1d 84 98 29 ff b2 3d a0 26 45 cb 17 89 35 b8 6c 5b 02 e6 da 22 7f 9c e8 f1 d9 63 04 d4 c7 e3 96 40 2a bc 82 c8 d0 19 52 67 7c fa 36 9d c9 3a 43 a4 18 2f 5c 3c 65 9e db e7 00 f2 8d c6 97 6f 80 b5 2b 1a d1 f7 06 28 e2 dc 6a 3b b4 61 34 c2 58 79 f3 0e 46 15 2c 03 ba 86 92 c0 e9 78 ef b7 01 6e dd 59 20 eb 7a a9 fc 32 56 d7 13 b0 a2 74 16 ca 4c 85 f8 4f 88 d6 94 23 b9 ad 62 d2 50 41 37 fb 75 ec cf 5e d3 8c 69 08 e4 71 9a 24 11 f0 af 4d ce 93 77 8a 4b 5d c5 10 a7 b6 3e 09 fd 1b 7e 51 3f 68 a5 a3 be e5 2d 9f 81 44 0b
В четных раундах используется операция , в нечетных - . Эти операции и таблицы замен обладают рядом свойств, которые важны, особенно для унификации операций шифрования и расшифрования. Свойства таблиц и операций:
где — текущее значение блока шифруемых данных. Операции и можно определить следующим образом:
где: — текущее значение конкретного байта данных; — значение байта данных после выполнения операции;
Линейное преобразование π
Здесь используется 4 специальных константы, шестнадцатеричные значения которых указаны ниже:
Эти константы объединены в маскирующие последовательности, перечисленные ниже:
где — операция конкатенации.
Сама же операция — представляет собой битовую перестановку. В нечетных раундах используется операция :
где: — логическая побитовая операция «и»; и — значение i-ой строки обрабатываемых данных до и после выполнения операции соответственно.
В четных раундах используется операция :
Фактически эта операция обеспечивает наличие в каждом результирующем байте каждого столбца двух битов каждого исходного байта того же столбца.
Байтовая перестановка τ
Данная перестановка преобразует простейшим образом строку данных в столбец:
Операция σ
Данная операция является побитовым сложением всего массива данных с ключом раунда:
где: — новое значение блока шифруемых данных; — ключ текущего раунда .
Заметим, именно 12 раундов шифрования рекомендуется автором алгоритма Че Хун Лимой, однако строгое количество раундов не установлено. Кроме 12 раундов шифрования, перед первым раундом алгоритма выполняется предварительная операция , а по завершении 12 раундов выполняется выходное преобразование , состоящее из последовательно выполняемых операций , и .
Расшифрование Расшифрование выполняется применением обратных операций в обратной последовательности. Все операции, кроме и являются обратными самим себе, а сами и связаны следующими соотношениями:
поэтому при расшифровывании — используется в четных раундах, а — в нечетных.
Стоит отметить ещё одну особенность: каждый этап может быть выполняется параллельно, что важно при реализации на современных многоядерных и многопоточных системах. Алгоритм имеет структуру SP-сети, как и Rijndael (который является победителем конкурса AES) Также особенностью шифра является то, что для зашифрования и расшифрования может использоваться одна и та же процедура, но с разными подключами. Алгоритм эффективен как при программной, так и при аппаратной реализации. Шифр достаточно быстр — на конкурсе AES при использовании компилятора Borland C показал наилучшие результаты среди всех участников.
Процедура расширения ключа Алгоритм Crypton требует наличие 128 — битового ключа для каждого раунда, а также 128 битового ключа для предварительной операции σ. Расширение ключа происходит в два этапа: на первом этапе происходит формирование восьми расширенных ключей; на втором этапе происходит вычисление ключей раундов из расширенных ключей.
Формирование расширенных ключей Формирование расширенных ключей происходит так: Если ключ шифрования имеет размер, меньший 256 бит, он дополняется битовыми нулями, пока не достигнет 32-байтового исходного ключа :
Ключ K разбирается на последовательности и , первая из которых содержит только четные байты ключа, вторая — только нечетные:
Над последовательностями и выполняется один раунд шифрования алгоритма Crypton с использованием ключа раунда, состоящего из нулевых битов. Соответственно для выполняются преобразования нечетного раунда, для происходит преобразование четного раунда. Результирующие последовательности обозначаются как и . Происходит вычисление 8 расширенных ключей:
для где и — последовательности, которые определяются следующими формулами:
Вычисление ключей раундов Для вычисления из расширенных ключей — ключей раундов, используются следующие константы:
Заметим, что псевдослучайные константы A54FF53A и 3C6EF372 получаются из дробных частей от чисел и соответственно.
Сначала вычисляются ключи для предварительной операции σ и первого раунда:
где — i-ая строка ключа раунда . Как и для шифруемых данных, ключ предоставляется в виде таблицы..
Константы вычисляются путём побитового циклического сдвига каждого байта константы на 1 бит влево.
Для второго и каждого последующего четного раунда ключ вычисляется следующим образом: Выполняется модификация первых четырёх расширенных ключей:
где знаком <<< обозначена операция побитового циклического сдвига каждого байта (раздельно) расширенного ключа на указанное число битов влево, а << — побитового циклического сдвига всего ключа на указанное число битов влево. Вычисление ключа раунда с помощью модифицированных расширенных ключей:
Аналогично происходит вычисление ключей для нечетных раундов:
Процедура расширения ключа позволяет генерировать ключи раундов «на лету», то есть в процессе шифрования по мере необходимости. Это явное достоинство алгоритма, по крайней мере потому, что не требуется памяти для хранения ключей раундов. Для расшифорвания возможно и выполнение прямой процедуры расширения ключа и использование полученных ключей раундов в обратном порядке.
Безопасность
Недостатки алгоритма Crypton При анализе исходной версии алгоритма, Crypton v0.5, сразу двое экспертов независимо обнаружили класс слабых ключей: таковых оказалось 232 256-битовых ключей. Также, была обнаружена атака на шестираундовую версию алгоритма Crypton, похожая на атаку на алгоритм Square. Это было одной из причин появления новой версии алгоритма — Crypton v1.0.
Достоинства алгоритма Crypton Однако по мнению экспертов института NIST, вышеперечисленные недостатки не являются грубыми. Кроме того, плюсов у алгоритма было вполне достаточно: алгоритм эффективен на программном и аппаратном уровне благодаря высокой степени параллельности и использованию очень простых логических операций ANDS/XORS; алгоритм не подвержен атакам по времени выполнения и потребляемой мощности; хорошая стойкость к существующим атакам; возможность распараллеливания операций в процессе шифрования;