stringtranslate.com

Змей (шифр)

Serpent — это симметричный блочный шифр , который стал финалистом конкурса Advanced Encryption Standard (AES) , где занял второе место после Rijndael . [2] Serpent был разработан Россом Андерсоном , Эли Бихамом и Ларсом Кнудсеном . [3]

Как и другие заявки AES , Serpent имеет размер блока 128 бит и поддерживает размер ключа 128, 192 или 256 бит. [4] Шифр ​​представляет собой 32-раундовую сеть подстановки-перестановки, работающую на блоке из четырех 32-битных слов . Каждый раунд применяет один из восьми 4-битных в 4-битных S-блоков 32 раза параллельно. Serpent был разработан таким образом, чтобы все операции могли выполняться параллельно , используя 32- битные срезы . Это максимизирует параллелизм, но также позволяет использовать обширную работу по криптоанализу, выполненную в DES .

Serpent придерживался консервативного подхода к безопасности, выбрав большой запас прочности: разработчики посчитали, что 16 раундов будет достаточно для известных типов атак, но указали 32 раунда в качестве страховки от будущих открытий в криптоанализе. [5] Официальный отчет NIST по соревнованию AES классифицировал Serpent как имеющий высокий запас прочности, как MARS и Twofish , и в отличие от адекватного запаса прочности RC6 и Rijndael (в настоящее время AES). [2] В финальном голосовании Serpent получил наименьшее количество отрицательных голосов среди финалистов, но занял второе место в общем зачете, потому что Rijndael имел существенно больше положительных голосов, решающим фактором стало то, что Rijndael допускал гораздо более эффективную программную реализацию. [ необходима цитата ]

Алгоритм шифрования Serpent находится в общественном достоянии и не запатентован . [ 6] Справочный код является программным обеспечением в общественном достоянии , а оптимизированный код лицензируется по GPL . [7] Нет никаких ограничений или обременений относительно его использования. В результате, любой может свободно включать Serpent в свое программное обеспечение (или в аппаратные реализации) без уплаты лицензионных сборов.

Расписание ключей

Расписание ключей Serpent состоит из 3 основных этапов. На первом этапе ключ инициализируется путем добавления заполнения, если необходимо. Это делается для того, чтобы короткие ключи соответствовали длинным ключам длиной 256 бит, один бит «1» добавляется в конец короткого ключа, за которым следуют биты «0», пока короткий ключ не будет сопоставлен с длинной длиной ключа. [4]

На следующем этапе «предварительные ключи» выводятся с использованием ранее инициализированного ключа. 32-битные части ключа подвергаются операции XOR, FRAC , который является дробью золотого сечения , и индекс раунда подвергаются операции XOR с частями ключа, результат операции XOR поворачивается влево на 11. FRAC и индекс раунда были добавлены для достижения равномерного распределения битов ключей во время раундов. [4]

Наконец, «подключи» выводятся из ранее сгенерированных «предключей». Это приводит к общему количеству 33 128-битных «подключей». [4]

В конце раундовый ключ или «подключ» помещается в «начальный IP-адрес перестановки», чтобы поместить биты ключа в правильный столбец. [4]

Расписание ключей в C++

#define FRAC 0x9e3779b9 // дробная часть золотого сечения #define ROTL(A, n) ((A) << n | (A) >> 32-n)uint32_t key [ 8 ]; // ключ, предоставленный пользователем uint32_t subkey [ 33 ][ 4 ]; // roundkeys const uint8_t S [ 8 ][ 16 ] = {}; // S-boxes         /* расписание ключей: получить предварительные ключи */ void get_pre ( uint32_t w [ 4 * 33 ], const uint32_t k [ 8 ]) { uint32_t x [ 4 * 33 + 8 ]; for ( int i = 0 ; i < 8 ; i ++ ) x [ i ] = k [ i ]; for ( int i = 8 ; i < 140 ; i ++ ) { x [ i ] = ROTL ( x [ i -8 ] ^ x [ i -5 ] ^ x [ i -3 ] ^ x [ i -1 ] ^ FRAC ^ ( i -8 ), 11 ); w [ i -8 ] = x [ i ]; } }                                                /* расписание ключей: получение подключаемых ключей */ void get_sk ( const uint32_t w [ 4 * 33 ], uint32_t ( * sk )[ 4 ]) {       uint8_t i , p , j , s , k ; для ( i = 0 ; i < 33 ; i ++ ) { p = 32 + 3 - i ; для ( j = 0 ; j < 4 ; j ++ ) sk [ i ][ j ] = 0 ; для ( k = 0 ; k < 32 ; k ++ ) { s = S [ p % 8 ][(( w [ 4 * i + 0 ] >> k ) & 0x1 ) << 0 | (( w [ 4 * i + 1 ] >> k ) & 0x1 ) << 1 | (( w [ 4 * i + 2 ] >> k ) & 0x1 ) << 2 | (( w [ 4 * i + 3 ] >> k ) & 0x1 ) << 3 ]; for ( j знак равно 0 ; j < 4 ; j ++ ) { sk [ i ][ j ] |= (( s >> j ) & 0x1 ) << k ; } } } }                                                                                                         void key_schedule () { uint32_t w [ 4 * 33 ]; get_pre ( w , key ); get_sk ( w , subkey ); }

S-боксы

S-блоки Serpent представляют собой 4-битные перестановки и обладают следующими свойствами:

S-boxes Serpent были построены на основе 32 строк s-boxes DES . Они были преобразованы путем обмена записями, полученные массивы с желаемыми свойствами были сохранены как s-boxes Serpent. Этот процесс повторялся до тех пор, пока не было найдено в общей сложности 8 s-boxes. В этом процессе использовался следующий ключ: "sboxesforserpent". [4]

Перестановки и преобразования

Начальная перестановка (ИП)

Первоначальная перестановка работает со 128 битами за раз, перемещая биты.

для i в диапазоне 0 .. 127 поменять местами ( бит ( i ), бит (( 32 * i ) % 127 ) )

Конечная перестановка (FP)

Окончательная перестановка работает со 128 битами за раз, перемещая биты.

для i в диапазоне 0 .. 127 поменять местами ( бит ( i ), бит (( 4 * i ) % 127 ) )

Линейное преобразование (ЛП)

Состоит из операций XOR, S-Box, битового сдвига влево и битового поворота влево. Эти операции выполняются над 4 32-битными словами.

для ( коротко i = 0 ; i < 4 ; i ++ ) { X [ i ] = S [ i ][ B [ i ] ^ K [ i ]]; } X [ 0 ] = ROTL ( X [ 0 ], 13 ); X [ 2 ] = ROTL ( X [ 2 ], 3 ); X [ 1 ] = X [ 1 ] ^ X [ 0 ] ^ X [ 2 ]; X [ 3 ] = X [ 3 ] ^ X [ 2 ] ^ ( X [ 0 ] << 3 ); X [ 1 ] = ROTL ( X [ 1 ], 1 ); X [ 3 ] = ROTL ( X [ 3 ], 7 ); X [ 0 ] = X [ 0 ] ^ X [ 1 ] ^ X [ 3 ]; X [ 2 ] = X [ 2 ] ^ X [ 3 ] ^ ( X [ 1 ] << 7 ); X [ 0 ] = ROTL ( X [ 0 ], 5 ); X [ 2 ] = ROTL ( X [ 2 ], 22 ); для ( короткое i = 0 ; i < 4 ; i ++ )                                                                         { В [ я + 1 ] = Х [ я ]; }

Рейндал против Змея

Rijndael — это сеть линейного преобразования подстановки с десятью, двенадцатью или четырнадцатью раундами в зависимости от размера ключа и с независимо указанными размерами ключа 128 бит, 192 бита или 256 бит. Serpent — это сеть подстановки-перестановки, которая имеет тридцать два раунда, а также начальную и конечную перестановку для упрощения оптимизированной реализации. Функция раунда в Rijndael состоит из трех частей: нелинейного слоя, слоя линейного смешивания и слоя ключевого смешивания XOR. Функция раунда в Serpent состоит из ключевого смешивания XOR, тридцати двух параллельных приложений одного и того же 4×4 S-box и линейного преобразования, за исключением последнего раунда, в котором другой ключевой смешивающий XOR заменяет линейное преобразование. Нелинейный слой в Rijndael использует 8×8 S-box, тогда как Serpent использует восемь различных 4×4 S-box. 32 раунда означают, что Serpent имеет более высокий запас безопасности, чем Rijndael; Однако Rijndael с 10 раундами быстрее и проще в реализации для небольших блоков. [9] Поэтому Rijndael был выбран победителем в конкурсе AES.

Змей-0 против Змея-1

Оригинальный Serpent, Serpent-0, был представлен на 5-м семинаре по быстрому программному шифрованию , но несколько измененная версия, Serpent-1, была представлена ​​на конкурс AES. В представленной на конкурс AES статье обсуждаются изменения, в том числе различия в планировании ключей.

Безопасность

Атака XSL , если она эффективна, ослабит Serpent (хотя и не так сильно, как она ослабила бы Rijndael , который стал AES ). Однако многие криптоаналитики считают, что если учесть особенности реализации, атака XSL будет более затратной, чем атака методом подбора . [ требуется цитата ]

В 2000 году в статье Коно и др. была представлена ​​атака «встреча посередине» против 6 из 32 раундов Serpent и усиленная атака «бумеранг» против 9 из 32 раундов Serpent. [10]

Атака 2001 года Эли Бихама , Орра Данкельмана и Натана Келлера представляет собой линейную криптоаналитическую атаку, которая взламывает 10 из 32 раундов Serpent-128 с 2 118 известными открытыми текстами и временем 2 89 , и 11 раундов Serpent-192/256 с 2 118 известными открытыми текстами и временем 2 187. [11]

В статье 2009 года было отмечено, что нелинейный порядок Serpent S-boxes не был равен 3, как утверждали разработчики. В частности, четыре элемента имели порядок 2. [8]

Атака 2011 года, предпринятая Хонгжуном Ву, Хуасюном Ваном и Фуонгом Ха Нгуеном, также с использованием линейного криптоанализа, взломала 11 раундов Serpent-128 с 2 116 известными открытыми текстами, 2 107,5 времени и 2 104 памяти. [1]

В той же статье описываются две атаки, которые взламывают 12 раундов Serpent-256. Первая требует 2 118 известных открытых текстов, 2 228,8 времени и 2 228 памяти. Другая атака требует 2 116 известных открытых текстов и 2 121 памяти, но также требует 2 237,5 времени.

Смотрите также

Сноски

  1. ^ ab Huaxiong Wang, Hongjun Wu & Phuong Ha Nguyen (2011). "Улучшение алгоритма 2 в многомерном линейном криптоанализе" (PDF) . Информационная безопасность и конфиденциальность . Конспект лекций по информатике. Том 6812. ACISP 2011. стр. 61–74. doi :10.1007/978-3-642-22497-3_5. ISBN 978-3-642-22496-6. Архивировано из оригинала (PDF) 14 апреля 2017 г. . Получено 25 сентября 2014 г. .
  2. ^ ab Nechvatal, J.; Barker, E.; Bassham, L.; Burr, W.; Dworkin, M.; Foti, J.; Roback, E. (май 2001 г.). «Отчет о разработке Advanced Encryption Standard (AES)». Журнал исследований Национального института стандартов и технологий . 106 (3): 511–577. doi :10.6028/jres.106.023. ISSN  1044-677X. PMC 4863838. PMID 27500035  . 
  3. ^ "Домашняя страница Serpent".
  4. ^ abcdef Росс Дж. Андерсон (23 октября 2006 г.). «Serpent: A Candidate Block Cipher for the Advanced Encryption Standard». Компьютерная лаборатория Кембриджского университета . Получено 14 января 2013 г.
  5. ^ "serpent.pdf" (PDF) . Получено 25 апреля 2022 г. .
  6. ↑ Serpent держит ключ к безопасности Интернета – объявлены финалисты всемирного конкурса по шифрованию (1999)
  7. ^ SERPENT – Кандидатный блочный шифр для расширенного стандарта шифрования «Serpent теперь полностью находится в общественном достоянии, и мы не накладываем никаких ограничений на его использование. Об этом было объявлено 21 августа на Первой конференции кандидатов AES. Оптимизированные реализации в пакете заявок теперь находятся под лицензией General Public License (GPL), хотя некоторые комментарии в коде по-прежнему говорят об обратном. Вы можете использовать Serpent для любых приложений. Если вы его используете, мы будем признательны, если вы сообщите нам об этом!» (1999)
  8. ^ abcd Бхупендра Сингх; Лекси Александр; Санджай Берман (2009). «Об алгебраических отношениях змеиных S-боксов» (PDF) . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  9. ^ Брюс Шнайер; Джон Келси; Дуг Уайтинг; Дэвид Вагнер; Крис Холл. Нильс Фергюсонк; Тадаёши Коно; Майк Стэй (2000). "The Twofish Team's Final Comments on AES Selection" (PDF) . Архивировано из оригинала (PDF) 2 января 2010 года . Получено 19 января 2015 года . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  10. ^ Тадаёси Коно; Джон Келси и Брюс Шнайер (2000). «Предварительный криптоанализ змеи с уменьшенным раундом». {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  11. ^ Эли Бихам, Орр Данкельман и Натан Келлер (2001). «Линейный криптоанализ редуцированного круглого змея». FSE 2001. CiteSeerX 10.1.1.78.6148 .  {{cite journal}}: Цитировать журнал требует |journal=( помощь )

Дальнейшее чтение

Внешние ссылки