• Конференция
  • Поиск
    • Обзоры
    • Новости
    • Блоги
    Статьи Новости

    Алгоритмы шифрования ? финалисты конкурса AES. Часть 1.


    Стандарт DES и конкурс AES

    Алгоритм шифрования DES (Data Encryption Standard) [9] c 1977 года является стандартом симметричного шифрования США (кроме информации повышенной степени секретности). В течение последующих 20 лет «DES стойко выдержал 20 лет массового всемирного криптоанализа» [7] — десятилетия криптоанализа (т.е. науки, посвященной поиску уязвимостей и, соответственно, взлому криптографических алгоритмов защиты информации) не привели к обнаружению серьезных уязвимостей в алгоритме (подробно о криптоанализе DES см. [18]).

    Фактически, DES дал невиданный доселе толчок развитию криптоанализа. Вышли сотни трудов, посвященных различным методам криптоанализа именно в приложении к алгоритму DES, а также деталям самого алгоритма и их влиянию на криптостойкость DES. Можно утверждать, что именно благодаря DES появились целые направления криптоанализа. DES до сих пор считается сильным алгоритмом шифрования во всем, кроме размера ключа шифрования. 56-битный ключ DES явно недостаточен и при современных вычислительных ресурсах может быть вскрыт методом «грубой силы», т.е. перебором всех возможных вариантов ключа шифрования. Причем многие криптографы понимали это еще до принятия DES в качестве стандарта [22], а первые попытки увеличения размера ключа DES без изменения самого алгоритма начались уже в 1978 году (см. [18]). Однако, DES продолжал активно использоваться в качестве стандарта США.

    Фактически, первые реальные шаги по замене стандарта шифрования были сделаны в 1997 году, когда Институт стандартов и технологий США NIST (National Institute of Standards and Technology, http://www.nist.gov) объявил о проведении открытого конкурса алгоритмов шифрования, победитель которого должен был стать новым стандартом симметричного шифрования США. В конкурсе могли принять участие любые организации или частные лица, в том числе находящиеся за пределами США. И действительно, список участников конкурса оказался весьма разнообразен; среди авторов алгоритмов-претендентов были:

    • всемирно известные криптологи, например, интернациональный коллектив авторов алгоритма Serpent — Росс Андерсон (Ross Anderson), Эли Бихам (Eli Biham) и Ларс Кнудсен (Lars Knudsen);
    • организации, давно работающие в данной области и обладающие как богатым опытом разработки криптоалгоритмов, так и сильнейшими специалистами в данной области, например, американская фирма Counterpane — автор алгоритма Twofish;
    • всемирно известные корпорации, обладающие большим научным потенциалом, например немецкий телекоммуникационный гигант Deutsche Telekom с алгоритмом Magenta;
    • образовательные учреждения, известные своими достижениями в области криптографии, например Католический Университет г. Лювен (Katholieke Universiteit Leuven), Бельгия, с алгоритмом Rijndael;
    • и наоборот, организации, весьма малоизвестные до проведения конкурса AES, например, фирма Tecnologia Apropriada (автор алгоритма FROG) из латиноамериканского государства Коста-Рика.

    NIST установил всего два обязательных требования к алгоритмам-участникам конкурса [4]:

    • 128-битный размер блока шифруемых данных,
    • не менее трех поддерживаемых алгоритмом размеров ключей шифрования: 128, 192 и 256 бит.

    Однако, несравнимо больше было «рекомендательных» требований к будущему стандарту шифрования США. Поскольку соответствовать обязательным требованиям было достаточно просто, анализ алгоритмов и выбор из них лучшего производился именно по его соответствию «необязательным» характеристикам. «Пожелания» института NIST были, в частности, таковы [4]:

    1. Алгоритм должен быть стойким против криптоаналитических атак, известных на время проведения конкурса.
    2. Структура алгоритма должна быть ясной, простой и обоснованной, что, во-первых, облегчало бы изучение алгоритма специалистами, а во-вторых, гарантировало бы отсутствие внедренных авторами алгоритма «закладок» (т.е. в данном случае, особенностей архитектуры алгоритма, которыми теоретически могли бы воспользоваться его авторы в злоумышленных целях).
    3. Должны отсутствовать слабые и эквивалентные ключи (т.е. ключи, являющиеся различными, но приводящие к одному и тому же результату шифрования).
    4. Скорость шифрования данных должна быть высокой на всех потенциальных аппаратных платформах — от 8-битных до 64-битных.
    5. Структура алгоритма должна позволять распараллеливание операций в многопроцессорных системах и аппаратных реализациях.
    6. Алгоритм должен предъявлять минимальные требования к оперативной и энергонезависимой памяти.
    7. Не должно быть ограничений для использования алгоритма; в частности, алгоритм не должен ограничивать свое использование в различных стандартных режимах работы (см. [10]), в качестве основы для построения хэш-функций (см. статью «Назначение и структура алгоритмов шифрования», содержащую классификацию криптографических алгоритмов и описание наиболее часто встречающихся структур алгоритмов шифрования), генераторов псевдослучайных последовательностей и т.д.

    Эти требования оказались достаточно жесткими и частично противоречащими друг другу; каждый конкретный алгоритм из участвовавших в конкурсе представлял собой некий найденный авторами компромисс между соответствиями данным требованиям.

    Заявки от участников конкурса NIST принимал в течение полутора лет, после чего все присланные на конкурс алгоритмы изучались и обсуждались как в самом институте NIST, так и всеми желающими. Стоит сказать, что в NIST пришло немало отзывов, все они находятся в открытом доступе и их можно посмотреть на web-сайте института (см. выше).

    Всего в конкурсе приняли участие 15 алгоритмов шифрования [1, 13]:

    АлгоритмыАвторы или организацияОсновные результаты анализа
    CAST-256Entrust Technologies, Inc.В алгоритме не обнаружено уязвимостей. Однако, скорость шифрования у данного алгоритма невысока; кроме того, у него высокие требования к оперативной и энергонезависимой памяти.
    CryptonFuture Systems, Inc.Алгоритм без явных недостатков. Однако, Crypton уступает по всем характеристикам похожему на него алгоритму Rijndael. Эксперты конкурса сочли, что в финале конкурса Crypton однозначно проиграет Rijndael, поэтому не выбрали его во второй раунд конкурса.
    DEALRichard Outerbridge, Lars KnudsenМножество недостатков: наличие подмножеств слабых ключей, подверженность дифференциальному криптоанализу1 , отсутствие усиления при использовании 192-битных ключей по сравнению с 128-битными.
    DFCCNRS — Centre National pour la Recherche Scientifique — Ecole Normale SuperieureДостоинство алгоритма: очень высокая скорость шифрования на 64-битных платформах. При этом алгоритм весьма медленно шифрует на остальных платформах, а также имеет классы слабых ключей.
    E2NTT — Nippon Telegraph and Telephone CorporationАналогично алгоритму CAST-256, в E2 не найдено уязвимостей, но требования к энергонезависимой памяти слишком высоки.
    FROGTecApro Internacional S.A.Алгоритм с наиболее оригинальной структурой и с наибольшим количеством недостатков: наличие уязвимостей, низкая скорость шифрования и высокие требования к ресурсам.
    HPCRichard SchroeppelАналогично алгоритму DFC, HPC очень быстро шифрует на 64-битных платформах, но весьма медленно на остальных. Кроме того, сложная и медленная процедура расширения ключа ограничивает возможные применения алгоритма, а наиболее сложная из всех представленных на конкурс алгоритмов структура раунда усложняет анализ алгоритма и делает недоказуемым отсутствие закладок.
    LOKI97Lawrie Brown, Josef Pieprzyk, Jennifer SeberryНизкая скорость шифрования, высокие требования к ресурсам, наличие уязвимостей.
    MagentaDeutsche Telekom AGАлгоритм подвержен атакам методами линейного2 и дифференциального криптоанализа; медленная скорость шифрования.
    MARSIBMУ алгоритма отсутствуют серьезные недостатки, за исключением низкой скорости шифрования на ряде платформ, не имеющих аппаратной поддержки требуемых операций и некоторых других незначительных недостатков. Алгоритм был незначительно модифицирован в течение первого раунда; измененный вариант вышел в финал конкурса.
    RC6RSA LaboratoriesRC6 имеет весьма похожие на MARS проблемы с реализацией на некоторых платформах. Эксперты посчитали это незначительным недостатком — алгоритм вышел в финал конкурса.
    RijndaelJoan Daemen, Vincent RijmenКаких-либо недостатков у алгоритма не обнаружено; алгоритм вышел в финал конкурса.
    SAFER+Cylink CorporationАлгоритм подвержен ряду атак и имеет низкую скорость выполнения.
    SerpentRoss Anderson, Eli Biham, Lars KnudsenВыявлены некоторые незначительные недостатки, алгоритм вышел в финал конкурса.
    TwofishBruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, Niels FergusonИз недостатков эксперты отметили сложность алгоритма, затрудняющую его анализ. Алгоритм вышел в финал конкурса.

    В результате первого этапа конкурса были выбраны 5 алгоритмов без явно выраженных недостатков: MARS, RC6, Rijndael, Serpent и Twofish. Началось детальное изучение именно этих алгоритмов (что называлось «вторым этапом» или «финалом» конкурса AES), продолжавшееся еще год с небольшим. В результате победителем конкурса стал алгоритм Rijndael; ему было присвоено название AES, под именем которого он уже достаточно широко реализован и, видимо, по широте распространения обойдет своего предшественника — алгоритм DES.

    Стоит сказать, что алгоритму Rijndael посвящено уже множество статей и разделов книг (например, [20, 21]), поэтому рассмотрим здесь подробно другие алгоритмы, вышедшие в финал, а к алгоритму Rijndael, возможно, вернемся в одной из следующих статей.Алгоритм Serpent

    Как было сказано выше, алгоритм Serpent разработан тремя известнейшими криптологами: Россом Андерсоном, Эли Бихамом и Ларсом Кнудсеном. Каждый из них знаменит своими криптоаналитическими работами, а также разработанными ранее алгоритмами шифрования (например, широкую известность получили алгоритмы Bear и Leon, разработанные Андерсоном и Бихамом [2]; не менее известен алгоритм Square, разработанный авторами алгоритма Rijndael Джоан Деймен (Joan Daemen) и Винсентом Риджменом (Vincent Rijmen) при участии Ларса Кнудсена [8]). Именно Эли Бихама без преувеличения можно назвать величайшим криптоаналитиком современности — его авторству (часто в соавторстве с другими специалистами) принадлежит множество работ, посвященных методам вскрытия различных известных алгоритмов шифрования.

    Еще до конкурса AES появился алгоритм Serpent-0, отличающийся от присланного на конкурс алгоритма Serpent-1 (или просто Serpent) только тем, что в нем были использованы таблицы замен алгоритма DES (в незначительно модифицированном виде). В Serpent используются уже оригинальные таблицы замен, которые, по словам авторов [3], вкупе с незначительным изменением процедуры расширения ключа усилили алгоритм против дифференциального и линейного криптоанализа.

    Рассмотрим здесь именно тот алгоритм Serpent, который был прислан на конкурс AES и стал одним из его финалистов.

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

    Serpent представляет собой SP-сеть, в которой блок данных в процессе шифрования разбивается на 4 субблока по 32 бита (см. рис. 1) [3].Структура алгоритма Serpent

    Рис. 1. Структура алгоритма Serpent.

    Алгоритм выполняет 32 раунда преобразований; перед первым раундом выполняется начальная перестановка IP, после заключительного раунда — финальная перестановка FP. Начальная перестановка определена следующим образом:

    0326496133659723466983356799
    43668100537691016387010273971103
    8407210494173105104274106114375107
    124476108134577109144678110154779111
    164880112174981113185082114195183115
    205284116215385117225486118235587119
    245688120255789121265890122275991123
    286092124296193125306294126316395127

    Это означает, что бит 0 остается на своем месте, бит 32 входного значения становится битом 1, бит 64 — битом 2 и т.д.

    Финальная перестановка является инверсной начальной перестановке и выглядит так:

    04812162024283236404448525660
    646872768084889296100104108112116120124
    15913172125293337414549535761
    656973778185899397101105109113117121125
    261014182226303438424650545862
    667074788286909498102106110114118122126
    371115192327313539434751555963
    677175798387919599103107111115119123127

    Функция раунда весьма проста и состоит из следующих операций:

    1. Наложение 128-битного ключа раунда побитовой логической операцией «исключающее или» (XOR).
    2. Табличная замена. Обрабатываемый 128-битный блок данных разбивается на 32 фрагмента по 4 бита, над каждым из которых выполняется табличная замена 4 * 4 бит. Полученный результат объединяется обратно в 128-битный блок.

      В каждом раунде используется одна и та же таблица; всего же в алгоритме определены 8 таблиц замен S0...S7, которые циклически используются в 32 раундах шифрования:

      S03815110651114134270912
      S11512279051011114861334
      S28679312101513114401152
      S30151181296313124107514
      S41158312011625410914713
      S51552114109120314813671
      S67212584611149115133100
      S71131501482117412109356

      Ячейки таблицы содержат выходные значения; входное значение определяет требуемый номер столбца. Например, таблица S0 меняет 0 на 3, 1 на 8 и т.д.

      Таблицы замен алгоритма Serpent определенным образом сгенерированы из таблиц алгоритма DES. В спецификации алгоритма [3] приведен псевдокод, использованный для генерации таблиц S0...S7.

    3. Линейное преобразование блока данных, которое определяется следующей таблицей:
    16, 52, 56, 70, 83, 94, 10572, 114, 1252, 9, 15, 30, 76, 84, 12636, 90, 103
    20, 56, 60, 74, 87, 98, 1091, 76, 1182, 6, 13, 19, 34, 80, 8840, 94, 107
    24, 60, 64, 78, 91, 102, 1135, 80, 1226, 10, 17, 23, 38, 84, 9244, 98, 111
    28, 64, 68, 82, 95, 106, 1179, 84, 12610, 14, 21, 27, 42, 88, 9648, 102, 115
    32, 68, 72, 86, 99, 110, 1212, 13, 8814, 18, 25, 31, 46, 92, 10052, 106, 119
    36, 72, 76, 90, 103, 114, 1256, 17, 9218, 22, 29, 35, 50, 96, 10456, 110, 123
    1, 40, 76, 80, 94, 107, 11810, 21, 9622, 26, 33, 39, 54, 100, 10860, 114, 127
    5, 44, 80, 84, 98, 111, 12214, 25, 10026, 30, 37, 43, 58, 104, 1123, 118
    9, 48, 84, 88, 102, 115, 12618, 29, 10430, 34, 41, 47, 62, 108, 1167, 122
    2, 13, 52, 88, 92, 106, 11922, 33, 10834, 38, 45, 51, 66, 112, 12011, 126
    6, 17, 56, 92, 96, 110, 12326, 37, 11238, 42, 49, 55, 70, 116, 1242, 15, 76
    10, 21, 60, 96, 100, 114, 12730, 41, 1160, 42, 46, 53, 59, 74, 1206, 19, 80
    3, 14, 25, 100, 104, 11834, 45, 1204, 46, 50, 57, 63, 78, 12410, 23, 84
    7, 18, 29, 104, 108, 12238, 49, 1240, 8, 50, 54, 61, 67, 8214, 27, 88
    11, 22, 33, 108, 112, 1260, 42, 534, 12, 54, 58, 65, 71, 8618, 31, 92
    2, 15, 26, 37, 76, 112, 1164, 46, 578, 16, 58, 62, 69, 75, 9022, 35, 96
    6, 19, 30, 41, 80, 116, 1208, 50, 6112, 20, 62, 66, 73, 79, 9426, 39, 100
    10, 23, 34, 45, 84, 120, 12412, 54, 6516, 24, 66, 70, 77, 83, 9830, 43, 104
    0, 14, 27, 38, 49, 88, 12416, 58, 6920, 28, 70, 74, 81, 87, 10234, 47, 108
    0, 4, 18, 31, 42, 53, 9220, 62, 7324, 32, 74, 78, 85, 91, 10638, 51, 112
    4, 8, 22, 35, 46, 57, 9624, 66, 7728, 36, 78, 82, 89, 95, 11042, 55, 116
    8, 12, 26, 39, 50, 61, 10028, 70, 8132, 40, 82, 86, 93, 99, 11446, 59, 120
    12, 16, 30, 43, 54, 65, 10432, 74, 8536, 90, 103, 11850, 63, 124
    16, 20, 34, 47, 58, 69, 10836, 78, 8940, 94, 107, 1220, 54, 67
    20, 24, 38, 51, 62, 73, 11240, 82, 9344, 98, 111, 1264, 58, 71
    24, 28, 42, 55, 66, 77, 11644, 86, 972, 48, 102, 1158, 62, 75
    28, 32, 46, 59, 70, 81, 12048, 90, 1016, 52, 106, 11912, 66, 79
    32, 36, 50, 63, 74, 85, 12452, 94, 10510, 56, 110, 12316, 70, 83
    0, 36, 40, 54, 67, 78, 8956, 98, 10914, 60, 114, 12720, 74, 87
    4, 40, 44, 58, 71, 82, 9360, 102, 1133, 18, 72, 114, 118, 12524, 78, 91
    8, 44, 48, 62, 75, 86, 9764, 106, 1171, 7, 22, 76, 118, 12228, 82, 95
    12, 48, 52, 66, 79, 90, 10168, 110, 1215, 11, 26, 80, 122, 12632, 86, 99

    Каждая ячейка таблицы соответствует биту выходного значения (от 0 до 127); в ячейке перечислены входные биты, XOR которых дает выходное значение. Например:

    Y0 = X16 Å X52 Å X56 Å X70 Å X83 Å X94 Å X105,
    Y1 = X72 Å X114 Å X125     и т.д.,
    где Xn и Yn — соответственно, n-й бит входного и выходного значения.Линейное преобразование в алгоритме Serpent
    Рис. 2. Линейное преобразование в алгоритме Serpent.

    Линейное преобразование может быть реализовано как в виде приведенной таблицы, так и с помощью следующих вычислений (см. рис. 2):

    W0 = W0 <<< 13,
    W2 = W2 <<< 3,
    W1 = W1 Å W0 Å W2,
    W3 = W3 Å W2 Å (W0 << 3),
    W1 = W1 <<< 1,
    W3 = W3 <<< 7,
    W0 = W0 Å W1 Å W3,
    W2 = W2 Å W3 Å (W1 << 7),
    W0 = W0 <<< 5,
    W2 = W2 <<< 22,

    где Wn — n-е 32-битное слово обрабатываемого блока,
    << и <<< — соответственно, операции сдвига и циклического сдвига влево на указанное число бит. Основным критерием при разработке линейного преобразования было максимальное ускорение влияния каждого бита входного значения и ключа шифрования на каждый бит шифртекста. Как пишут авторы алгоритма [3], такое влияние достигается уже после трех раундов алгоритма Serpent.

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

    Y = L(S’(i mod 8)(X Å Ki)),
    где X и Y — соответственно, входное и выходное значения обрабатываемого блока,
    i — номер раунда (от 0 до 31),
    Ki — ключ i-го раунда,
    L — линейное преобразование,
    а символом S’ обозначено параллельное использование 32 соответствующих таблиц замен.

    Последний раунд отличается от предыдущих тем, что вместо линейного преобразования в нем выполняется дополнительное наложение ключа; здесь используется 33-й фрагмент расширенного ключа K32:

    Y = S’7(X Å K31) Å K32

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

    Расшифрование производится выполнением обратных операций в обратной последовательности. В частности, вместо таблиц замен S0...S7 применяются в обратной последовательности инверсные таблицы замен InvS0...InvS7:

    InvS01331101065121144715982
    InvS15821415612311479113100
    InvS21291541114120361358107
    InvS30910711146133512248151
    InvS45083109714212116415131
    InvS58152941131411653712100
    InvS61510113536049147212811
    InvS73061391415851211710142

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

    53, 55, 721, 5, 20, 9015, 1023, 31, 90
    57, 59, 765, 9, 24, 9419, 1067, 35, 94
    61, 63, 809, 13, 28, 9823, 11011, 39, 98
    65, 67, 8413, 17, 32, 10227, 1141, 3, 15, 20, 43, 102
    69, 71, 8817, 21, 36, 1061, 31, 1185, 7, 19, 24, 47, 106
    73, 75, 9221, 25, 40, 1105, 35, 1229, 11, 23, 28, 51, 110
    77, 79, 9625, 29, 44, 1149, 39, 12613, 15, 27, 32, 55, 114
    81, 83, 1001, 29, 33, 48, 1182, 13, 431, 17, 19, 31, 36, 59, 118
    85, 87, 1045, 33, 37, 52, 1226, 17, 475, 21, 23, 35, 40, 63, 122
    89, 91, 1089, 37, 41, 56, 12610, 21, 519, 25, 27, 39, 44, 67, 126
    93, 95, 1122, 13, 41, 45, 6014, 25, 552, 13, 29, 31, 43, 48, 71
    97, 99, 1166, 17, 45, 49, 6418, 29, 596, 17, 33, 35, 47, 52, 75
    101, 103, 12010, 21, 49, 53, 6822, 33, 6310, 21, 37, 39, 51, 56, 79
    105, 107, 12414, 25, 53, 57, 7226, 37, 6714, 25, 41, 43, 55, 60, 83
    0, 109, 11118, 29, 57, 61, 7630, 41, 7118, 29, 45, 47, 59, 64, 87
    4, 113, 11522, 33, 61, 65, 8034, 45, 7522, 33, 49, 51, 63, 68, 91
    8, 117, 11926, 37, 65, 69, 8438, 49, 7926, 37, 53, 55, 67, 72, 95
    12, 121, 12330, 41, 69, 73, 8842, 53, 8330, 41, 57, 59, 71, 76, 99
    16, 125, 12734, 45, 73, 77, 9246, 57, 8734, 45, 61, 63, 75, 80, 103
    1, 3, 2038, 49, 77, 81, 9650, 61, 9138, 49, 65, 67, 79, 84, 107
    5, 7, 2442, 53, 81, 85, 10054, 65, 9542, 53, 69, 71, 83, 88, 111
    9, 11, 2846, 57, 85, 89, 10458, 69, 9946, 57, 73, 75, 87, 92, 115
    13, 15, 3250, 61, 89, 93, 10862, 73, 10350, 61, 77, 79, 91, 96, 119
    17, 19, 3654, 65, 93, 97, 11266, 77, 10754, 65, 81, 83, 95, 100, 123
    21, 23, 4058, 69, 97, 101, 11670, 81, 11158, 69, 85, 87, 99, 104, 127
    25, 27, 4462, 73, 101, 105, 12074, 85, 1153, 62, 73, 89, 91, 103, 108
    29, 31, 4866, 77, 105, 109, 12478, 89, 1197, 66, 77, 93, 95, 107, 112
    33, 35, 520, 70, 81, 109, 11382, 93, 12311, 70, 81, 97, 99, 111, 116
    37, 39, 564, 74, 85, 113, 11786, 97, 12715, 74, 85, 101, 103, 115, 120
    41, 43, 608, 78, 89, 117, 1213, 9019, 78, 89, 105, 107, 119, 124
    45, 47, 6412, 82, 93, 121, 1257, 940, 23, 82, 93, 109, 111, 123
    49, 51, 681, 16, 86, 97, 12511, 984, 27, 86, 97, 113, 115, 127

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

    Согласно требованиям конкурса AES, Serpent поддерживает три размера ключа шифрования: 128, 192 и 256 бит. Однако, фактически, ключ алгоритма Serpent может иметь произвольный размер, меньший 256. Такой «неполный» ключ перед выполнением его расширения дополняется по следующему правилу:

    1. Ключ дополняется одним единичным битом справа.
    2. Затем ключ дополняется справа нулевыми битами до достижения 256-битного размера.

    Только после этого производится процедура расширения ключа, состоящая из следующих шагов:

    1. 256-битный дополненный (при необходимости) ключ шифрования представляется в виде 8 32-битных слов, обозначаемых w-8...w-1.
    2. Данные слова используются в качестве исходных значений для вычисления промежуточного ключа — последовательности w0...w131:
      wi = (wi-8 Å wi-5 Å wi-3 Å wi-1 Å f Å i) <<< 11,
      где f — округленная дробная часть золотого сечения (√5 + 1) / 2, т.е. 9E3779B9 в шестнадцатеричной записи.
    3. Вычисляются ключи раунда с использованием таблиц замен S0...S7 (аналогично описанному выше их использованию в алгоритме Serpent):

      K0 = S3({w0, w1, w2, w3}),
      K1 = S2({w4, w5, w6, w7}),
      K2 = S1({w8, w9, w10, w11}),
      K3 = S0({w12, w13, w14, w15}),
      K4 = S7({w16, w17, w18, w19}),
      K5 = S6({w20, w21, w22, w23}),
      K6 = S5({w24, w25, w26, w27}),
      K7 = S4({w28, w29, w30, w31}),
      ...
      K31 = S4({w124, w125, w126, w127}),
      K32 = S3({w128, w129, w130, w131}).

    Криптостойкость алгоритма

    В процессе исследований эксперты не обнаружили каких-либо криптоаналитических атак на полнораундовую версию алгоритма Serpent. Это справедливо и в отношении остальных алгоритмов-финалистов. Однако, данные алгоритмы значительно различаются по своим характеристикам — см. раздел «Достоинства и недостатки алгоритмов-финалистов» во второй части этой статьи.Алгоритм Twofish

    Аналогично алгоритму Serpent, Twofish разработан коллективом известных криптологов под руководством Брюса Шнайера (Bruce Schneier) — автора множества работ в области криптологии (в т. ч. известнейшей книги [22]), разработчика известного алгоритма шифрования Blowfish [15] и основателя американской компании Counterpane Systems, являющейся одним из мировых лидеров в области разработки средств криптографической защиты информации. Кроме него, в разработке алгоритма принимали участие Джон Келси (John Kelsey), Крис Холл (Chris Hall) и Нильс Фергюсон (Niels Ferguson) из той же компании Counterpane Systems, а также Дуг Уайтинг (Doug Whiting) из Hifn Incorporated (разработка аппаратных средств защиты Internet-коммуникаций) и Дэвид Вагнер (David Wagner) из Университета штата Калифорния.

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

    Twofish разбивает шифруемые данные на четыре 32-битных субблока (обозначим их A, B, C, D), над которыми производится 16 раундов преобразований, в каждом из которых выполняются следующие операции (см. рис. 3) [16]:Структура алгоритма Twofish

    Рис. 3. Структура алгоритма Twofish.
    Щёлкните по картинке чтобы увеличить.
    1. Содержимое субблока B циклически сдвигается влево на 8 бит.
    2. Субблок A обрабатывается операцией g(), которая будет подробно описана ниже.
    3. Субблок B также обрабатывается операцией g().
    4. Субблок B накладывается на A с помощью сложения по модулю 232, после чего аналогичным образом выполняется наложение субблока A на субблок B.
    5. Фрагмент расширенного ключа K2r+8 (где r — номер текущего раунда, начиная с 0) складывается с субблоком A по модулю 232.
    6. Аналогично предыдущему шагу, K2r+9 накладывается на субблок B.
    7. Субблок A накладывается на C операцией XOR.
    8. Содержимое субблока D циклически сдвигается влево на 1 бит.
    9. Субблок B накладывается на D операцией XOR.
    10. Содержимое субблока C циклически сдвигается вправо на 1 бит.

    B = B <<< 8,
    A = g(A),
    B = g(B),
    A = A + B mod 232,
    B = A + B mod 232,
    A = A + K2r+8 mod 232,
    B = B + K2r+9 mod 232,
    C = C Å A,
    D = D <<< 1,
    D = D Å B,
    C = C >>> 1.

    Операция g() обрабатывает 32-битных входной субблок выполнением перечисленных ниже шагов (см. рис. 4):Функция g() алгоритма Twofish

    Рис. 4. Функция g() алгоритма Twofish.
    1. Субблок делится на 4 фрагмента по 8 бит каждый.
    2. Фрагменты прогоняются через таблицы замен 8 * 8 бит S0...S3. Таблицы замен вычисляются динамически и зависят от ключа шифрования; алгоритм построения таблиц замен будет подробно описан ниже.
    3. Результат замен (обозначим его s0...s3) умножается на фиксированную матрицу M1:

      где g0...g3 — байты выходного значения функции g().
      Умножение выполняется в конечном поле GF(28) с образующим полиномом x8 + x6 + x5 + x3 + 1.
      Матрица M1 определена следующим образом (здесь и далее в таблицах указаны шестнадцатеричные значения):

      01EF5B5B
      5BEFEF01
      EF5B01EF
      EF01EF5B

    В конце каждого раунда, за исключением последнего, субблоки A (значение до описанной выше обработки) и C меняются местами; субблоки B (значение до обработки) и D также меняются местами.

    Перед первым раундом выполняется входное отбеливание — наложение операцией XOR на обрабатываемые субблоки четырех фрагментов расширенного ключа K0...K3. Аналогично выполняется выходное отбеливание — после последнего раунда с использованием подключей K4...K7.

    Как видно, алгоритм Twofish имеет существенно более сложную структуру, чем Serpent, что компенсируется вдвое меньшим количеством раундов.

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

    Процедура расширения ключа формирует 40 32-битных подключей для использования в 16 раундах алгоритма и для выполнения операций отбеливания. Кроме того, на основе ключа шифрования вычисляются таблицы замен S0...S3.

    Аналогично алгоритму Serpent, Twofish использует ключи шифрования любого размера до 256 бит включительно. Однако, дополнение ключа выполняется несколько иначе: исходный ключ, при необходимости, дополняется нулевыми битами до ближайшего стандартного размера, т.е. до 128, 192 или 256 бит. Процедура расширения ключа обрабатывает дополненный таким образом ключ.

    Сначала выполняется предварительная обработка ключа, включающая в себя следующие шаги:

    1. Выполняется инициализация переменных, участвующих в дальнейших расчетах:
      k = N / 64,
      где N — размер дополненного ключа шифрования в битах, т.е. k принимает значение 2, 3 или 4. Ключ шифрования представляется в виде 8k байт m0...m8k-1 или в виде 2k 32-битных слов, обозначаемых как M0...M2k-1.
    2. Формируются 3 массива, каждый из которых состоит из k 32-битных слов:

      Me = (M0, M2, ..., M2k-2),
      Mo = (M1, M3, ..., M2k-1),
      V = (Vk-1, Vk-2, ..., V0),

      где:

      Матрица M2 определена следующим образом:

      01A455875A58DB9E
      A45682F31EC668E5
      02A1FCC147AE3D19
      A455875A58DB9E03

    Генерация подключей k0...k39 производится на основе вычисленных на предварительном этапе массивов Me и Mo следующим образом:

    k2i = Ai + Bi mod 232,
    k2i+1 = (Ai + 2Bi mod 232) <<< 9,

    где i = 0...19, а Ai и Bi — промежуточные величины, вычисляемые так:

    Ai = h(2iρ, Me),
    Bi = h((2i + 1)ρ, Mo) <<< 8.

    Константа ρ определена следующим образом:

    ρ = 224 + 216 + 28 + 1,

    а функция h() заслуживает подробного описания.

    Данная функция схематично представлена на рис. 5.Функция h() алгоритма Twofish.

    Рис. 5. Функция h() алгоритма Twofish.

    Она выполняется в несколько шагов, состав которых зависит от размера дополненного ключа в 64-битных фрагментах, т.е. от описанного выше значения k. В качестве параметров функция h() принимает 32-битное слово и массив 32-битных слов размерностью k. Последовательность выполнения такова:

    1. Входное слово делится на 4 8-битных фрагмента, которые прогоняются через специфические операции замены q0 и q1 (как показано на рис. 5). Результат замены объединяется в 32-битное слово, которое складывается с третьим словом входного массива (на рис. 5 в качестве входного массива показан массив Me). Данный шаг не выполняется, если k < 4 (т.е. k = 2 или k = 3). На рис. 5 показаны все возможные шаги функции h().
    2. Результат предыдущего шага или входное слово обрабатывается аналогичным образом (с другой последовательностью применения q0 и q1, которая является различной для каждого шага — см. рис. 5), но складывается со вторым словом входного массива. Шаг 2 не выполняется, если k = 2.
    3. и
    4. выполняются всегда и подразумевают обработку результата предыдущего шага (или входного слова — для шага 3 и k = 2), аналогичную предыдущим шагам с использованием, соответственно, первого и нулевого слов входного массива.
    5. Как и на предыдущих шагах, применяются замены q0 и q1, после чего выполняется следующее преобразование:

      где y0...y3 — байты результата выполнения замен на шаге 5, а матрица M1 была описана выше; H — выходное значение функции h().

    Операции q0 и q1 представляют собой не табличные замены 8 * 8 бит, а вычисляют выходные значения с использованием нескольких таблиц замен 4 * 4 следующим образом:

    a0 = ëx / 16û,
    b0 = x mod 16,
    a1 = a0 Å b0,
    b1 = a0 Å (b0 >>>41) Å 8a0 mod 16,
    a2 = t0(a1),
    b2 = t1(b1),
    a3 = a2 Å b2,
    b3 = a2 Å (b2 >>>41) Å 8a2 mod 16,
    a4 = t2(a3),
    b4 = t3(b3),
    y = 16b4 + a4,

    где x — входное значение,
    y — выходное значение,
    >>>4 — операция циклического вращения вправо 4-битных величин, т.е. раздельное вращение каждого нибла обрабатываемого байта;
    ti — табличные замены, различные для q0 и q1; для q0 таблицы выглядят так:

    t0817D6F320B59ECA4
    t1ECB81235F4A6709D
    t2BA5E6D90C8F32471
    t3D7F4126E9B3085CA

    Выходное значение таблицы берется из позиции, соответствующей входному значению; например, t1 заменяет 0 на E, 1 на C и т.д.

    Таблицы для q1 определены следующим образом:

    t028BDF76E31940AC5
    t11E2B4C376DA5F908
    t24C75169A0ED82B3F
    t3B951C3DE647F208A

    Осталось описать зависимость от ключа таблиц замен S0...S3. Фактически, в алгоритме шифрования вместо описанной выше функции g() используется функция h(), использующая в качестве входного значения 32-битный субблок A или B, а в качестве входного массива — описанный ранее массив V. Таким образом, замена выполняется на основе тех же таблиц t0...t3, которые используются в процедуре расширения ключа.

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

    • доступных объемов энергонезависимой и оперативной памяти,
    • предполагаемой частоты смены ключа при шифровании данных,
    • требований к скорости шифрования блоков данных.

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

    Twofish-FK

    Помимо описанного выше «стандартного» варианта алгоритма Twofish, авторы предложили еще и Twofish Family Key (или Twofish-FK) — шаблон для формирования на основе Twofish вариантов алгоритма, несовместимых между собой и предназначенных, таким образом, для ограниченных применений, например, в рамках конкретных организаций для защиты внутреннего документооборота.

    Несовместимость вариантов достигается путем применения дополнительного ключа (FK), константного для всех субъектов, применяющих конкретный из вариантов алгоритма Twofish-FK. Т.е. конкретное значение используемого FK формирует некий «контур совместимости» криптосредств, реализующих Twofish-FK.

    Дополнительный ключ FK «подмешивается» на этапе расширения ключа следующим образом:

    1. Инициализируются переменные, используемые в дальнейших операциях (данный шаг выполняется однократно для конкретного FK):
      T0 = FK,
      T1 = (EFK(0) | EFK(1)) Å FK,
      T2 = EFK(2),
      T3 = EFK(3),
      T4 = EFK(4) mod 264,

      где EFK(N) — результат зашифрования алгоритмом Twofish на ключе FK 128-битного блока, первый байт которого содержит значение N, а остальные байты обнулены,
      | — операция конкатенации.

      Стоит отметить, что переменные T0 и T1 имеют размерность 256 бит, T2 и T3 — по 128 бит, а T4 — 64 бита.

    2. Наложение ключа FK, выполняется однократно для каждого ключа шифрования, используемого совместно с данным FK:
      • Перед выполнением процедуры расширения ключа шифрования выполняется наложение T0 на ключ шифрования операцией XOR. Если ключ шифрования имеет размер, меньший 256 бит, то используется необходимое количество бит T0.
      • После выполнения процедуры расширения ключа операциями XOR T2 накладывается на подключи K0...K3, T3 — на подключи K4...K7, а T4 — на каждую пару подключей, используемых в раундах шифрования.
      • Перед использованием табличных замен выполняется наложение операцией XOR требуемого количества бит T1 на ключ шифрования.

    Криптостойкость алгоритмов, построенных на основе Twofish-FK, по словам авторов алгоритма, полностью эквивалентна криптостойкости стандартного Twofish, поскольку подобное наложение дополнительного ключа никак не влияет на основные параметры алгоритма [16].Литература, источники

    1. AES Round 1 Information. // http://csrc.nist.gov — January 26, 2001.
    2. Anderson R., Biham E. Two Practical and Provably Secure Block Ciphers: BEAR and LION. // http://citeseer.ist.psu.edu — 1995.
    3. Anderson R., Biham E., Knudsen L. Serpent: A Proposal for the Advanced Encryption Standard. // http://csrc.nist.gov.
    4. Announcing Request for Candidate Algorithm Nominations for the Advanced Encryption Standard (AES). // http://csrc.nist.gov — Department of Commerce — National Institute of Standards and Technology — Federal Register: September 12, 1997.
    5. Biham E., Dunkelman O., Keller N. Differential-Linear Cryptanalysis of Serpent. // http://citeseer.ist.psu.edu — Technion, Haifa, Israel.
    6. Burwick C., Coppersmith D., D’Avignon E., Gennaro R., Halevi S., Jutla C., Matyas S.M.Jr., O’Connor L., Peyravian M., Safford D., Zunic N. MARS — a candidate cipher for AES. // http://www.ibm.com — IBM Corporation — Revised, September, 22 1999.
    7. Courtois N., Castagnos G., Goubin L. What do DES S-boxes Say to Each Other? // http://eprint.iacr.org — Axalto Cryptographic Research & Advanced Security, Cedex, France.
    8. Daemen J., Knudsen L., Rijmen V. The Block Cipher Square. // http://www.esat.kuleuven.ac.be.
    9. FIPS 46-3. Data Encryption Standard (DES). // http://csrc.nist.gov — Reaffirmed 1999 October 25.
    10. FIPS 81. DES Modes of Operation. // http://csrc.nist.gov — 1980 December 2.
    11. Kocher P.C. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. // http://citeseer.ist.psu.edu — Cryptography Research, Inc., San Francisco, USA.
    12. Nechvatal J., Barker E., Bassham L., Burr W., Dworkin M., Foti J., Roback E. Report on the Development of the Advanced Encryption Standard (AES). // http://csrc.nist.gov — National Institute of Standards and Technology.
    13. Nechvatal J., Barker E., Dodson D., Dworkin M., Foti J., Roback E. Status report on the first round of the development of the advanced encryption standard. // http://csrc.nist.gov — National Institute of Standards and Technology.
    14. Rivest R.L., Robshaw M.J.B., Sidney R., Lin Y.L. The RC6 Block Cipher. // http://www.rsasecurity.com — Version 1.1 — August 20, 1998.
    15. Schneier B. Description of a new variable-length key 64-bit block cipher (blowfish). // http://www.schneier.com.
    16. Schneier B., Kelsey J., Whiting D., Wagner D., Hall C., Ferguson N. Twofish: A 128-bit Block Cipher. // http://www.schneier.com — 15 June 1998.
    17. What are RC5 and RC6? // http://www.rsasecurity.com.
    18. Панасенко С. Алгоритм шифрования DES и его варианты. // Connect! Мир связи. — 2006 — №№ 3-6.
    19. Панасенко С. Интересные алгоритмы шифрования, часть 2. // BYTE/Россия. — 2006 — № 5 — с. 74-79.
    20. Панасенко С.П., Батура В.П. Основы криптографии для экономистов: учебное пособие. Под ред. Л.Г. Гагариной. — М.: Финансы и статистика, 2005 — 176 с.
    21. Соколов А.В., Шаньгин В.Ф. Защита информации в распределенных корпоративных сетях и системах. — М.: ДМК Пресс, 2002 — 656 с.
    22. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. — Пер. с англ.: М.: Издательство ТРИУМФ, 2002 — 816 с.

    [ Читайте далее: алгоритмы MARS и RC6; достоинства и недостатки ]



    24 августа 2006 Г.

    AES. 1.

    — AES. 1.

    DES AES

    DES (Data Encryption Standard) [9] c 1977 ( ). 20 DES 20 [7] — (.. , , , ) ( DES . [18]).

    , DES . , DES, DES. , DES . DES , . 56- DES , .. . DES [22], DES 1978 (. [18]). , DES .

    , 1997 , NIST (National Institute of Standards and Technology, http://www.nist.gov) , . , . , ; - :

    • , , Serpent — (Ross Anderson), (Eli Biham) (Lars Knudsen);
    • , , , , Counterpane — Twofish;
    • , , Deutsche Telekom Magenta;
    • , , . (Katholieke Universiteit Leuven), , Rijndael;
    • , , AES, , Tecnologia Apropriada ( FROG) -.

    NIST - [4]:

    • 128- ,
    • : 128, 192 256 .

    , . , . NIST , , [4]:

    1. , .
    2. , , , -, , -, (.. , , ).
    3. (.. , , ).
    4. — 8- 64-.
    5. .
    6. .
    7. ; , (. [10]), - (. , ), ..

    ; .

    NIST , NIST, . , NIST , web- (. ).

    15 [1, 13]:

    CAST-256Entrust Technologies, Inc. . , ; , .
    CryptonFuture Systems, Inc. . , Crypton Rijndael. , Crypton Rijndael, .
    DEALRichard Outerbridge, Lars Knudsen : , 1 , 192- 128-.
    DFCCNRS — Centre National pour la Recherche Scientifique — Ecole Normale Superieure : 64- . , .
    E2NTT — Nippon Telegraph and Telephone Corporation CAST-256, E2 , .
    FROGTecApro Internacional S.A. : , .
    HPCRichard Schroeppel DFC, HPC 64- , . , , .
    LOKI97Lawrie Brown, Josef Pieprzyk, Jennifer Seberry , , .
    MagentaDeutsche Telekom AG 2 ; .
    MARSIBM , , . ; .
    RC6RSA LaboratoriesRC6 MARS . — .
    RijndaelJoan Daemen, Vincent Rijmen- ; .
    SAFER+Cylink Corporation .
    SerpentRoss Anderson, Eli Biham, Lars Knudsen , .
    TwofishBruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, Niels Ferguson , . .

    5 : MARS, RC6, Rijndael, Serpent Twofish. ( AES), . Rijndael; AES, , , — DES.

    , Rijndael (, [20, 21]), , , Rijndael, , .

    Serpent

    , Serpent : , . , (, Bear Leon, [2]; Square, Rijndael (Joan Daemen) (Vincent Rijmen) [8]). — ( ) , .

    AES Serpent-0, Serpent-1 ( Serpent) , DES ( ). Serpent , , [3], .

    Serpent, AES .

    Serpent SP-, 4 32 (. . 1) [3].

    Serpent
    . 1. Serpent.

    32 ; IP, — FP. :

    0326496133659723466983356799
    43668100537691016387010273971103
    8407210494173105104274106114375107
    124476108134577109144678110154779111
    164880112174981113185082114195183115
    205284116215385117225486118235587119
    245688120255789121265890122275991123
    286092124296193125306294126316395127

    , 0 , 32 1, 64 — 2 ..

    :

    04812162024283236404448525660
    646872768084889296100104108112116120124
    15913172125293337414549535761
    656973778185899397101105109113117121125
    261014182226303438424650545862
    667074788286909498102106110114118122126
    371115192327313539434751555963
    677175798387919599103107111115119123127

    :

    1. 128- (XOR).
    2. . 128- 32 4 , 4 * 4 . 128- .

      ; 8 S0...S7, 32 :

      S03815110651114134270912
      S11512279051011114861334
      S28679312101513114401152
      S30151181296313124107514
      S41158312011625410914713
      S51552114109120314813671
      S67212584611149115133100
      S71131501482117412109356

      ; . , S0 0 3, 1 8 ..

      Serpent DES. [3] , S0...S7.

    3. , :
    16, 52, 56, 70, 83, 94, 10572, 114, 1252, 9, 15, 30, 76, 84, 12636, 90, 103
    20, 56, 60, 74, 87, 98, 1091, 76, 1182, 6, 13, 19, 34, 80, 8840, 94, 107
    24, 60, 64, 78, 91, 102, 1135, 80, 1226, 10, 17, 23, 38, 84, 9244, 98, 111
    28, 64, 68, 82, 95, 106, 1179, 84, 12610, 14, 21, 27, 42, 88, 9648, 102, 115
    32, 68, 72, 86, 99, 110, 1212, 13, 8814, 18, 25, 31, 46, 92, 10052, 106, 119
    36, 72, 76, 90, 103, 114, 1256, 17, 9218, 22, 29, 35, 50, 96, 10456, 110, 123
    1, 40, 76, 80, 94, 107, 11810, 21, 9622, 26, 33, 39, 54, 100, 10860, 114, 127
    5, 44, 80, 84, 98, 111, 12214, 25, 10026, 30, 37, 43, 58, 104, 1123, 118
    9, 48, 84, 88, 102, 115, 12618, 29, 10430, 34, 41, 47, 62, 108, 1167, 122
    2, 13, 52, 88, 92, 106, 11922, 33, 10834, 38, 45, 51, 66, 112, 12011, 126
    6, 17, 56, 92, 96, 110, 12326, 37, 11238, 42, 49, 55, 70, 116, 1242, 15, 76
    10, 21, 60, 96, 100, 114, 12730, 41, 1160, 42, 46, 53, 59, 74, 1206, 19, 80
    3, 14, 25, 100, 104, 11834, 45, 1204, 46, 50, 57, 63, 78, 12410, 23, 84
    7, 18, 29, 104, 108, 12238, 49, 1240, 8, 50, 54, 61, 67, 8214, 27, 88
    11, 22, 33, 108, 112, 1260, 42, 534, 12, 54, 58, 65, 71, 8618, 31, 92
    2, 15, 26, 37, 76, 112, 1164, 46, 578, 16, 58, 62, 69, 75, 9022, 35, 96
    6, 19, 30, 41, 80, 116, 1208, 50, 6112, 20, 62, 66, 73, 79, 9426, 39, 100
    10, 23, 34, 45, 84, 120, 12412, 54, 6516, 24, 66, 70, 77, 83, 9830, 43, 104
    0, 14, 27, 38, 49, 88, 12416, 58, 6920, 28, 70, 74, 81, 87, 10234, 47, 108
    0, 4, 18, 31, 42, 53, 9220, 62, 7324, 32, 74, 78, 85, 91, 10638, 51, 112
    4, 8, 22, 35, 46, 57, 9624, 66, 7728, 36, 78, 82, 89, 95, 11042, 55, 116
    8, 12, 26, 39, 50, 61, 10028, 70, 8132, 40, 82, 86, 93, 99, 11446, 59, 120
    12, 16, 30, 43, 54, 65, 10432, 74, 8536, 90, 103, 11850, 63, 124
    16, 20, 34, 47, 58, 69, 10836, 78, 8940, 94, 107, 1220, 54, 67
    20, 24, 38, 51, 62, 73, 11240, 82, 9344, 98, 111, 1264, 58, 71
    24, 28, 42, 55, 66, 77, 11644, 86, 972, 48, 102, 1158, 62, 75
    28, 32, 46, 59, 70, 81, 12048, 90, 1016, 52, 106, 11912, 66, 79
    32, 36, 50, 63, 74, 85, 12452, 94, 10510, 56, 110, 12316, 70, 83
    0, 36, 40, 54, 67, 78, 8956, 98, 10914, 60, 114, 12720, 74, 87
    4, 40, 44, 58, 71, 82, 9360, 102, 1133, 18, 72, 114, 118, 12524, 78, 91
    8, 44, 48, 62, 75, 86, 9764, 106, 1171, 7, 22, 76, 118, 12228, 82, 95
    12, 48, 52, 66, 79, 90, 10168, 110, 1215, 11, 26, 80, 122, 12632, 86, 99

    ( 0 127); , XOR . :

    Y0 = X16 Å X52 Å X56 Å X70 Å X83 Å X94 Å X105,
    Y1 = X72 Å X114 Å X125     ..,
    Xn Yn — , n- .

    Serpent
    . 2. Serpent.

    , (. . 2):

    W0 = W0 <<< 13,
    W2 = W2 <<< 3,
    W1 = W1 Å W0 Å W2,
    W3 = W3 Å W2 Å (W0 << 3),
    W1 = W1 <<< 1,
    W3 = W3 <<< 7,
    W0 = W0 Å W1 Å W3,
    W2 = W2 Å W3 Å (W1 << 7),
    W0 = W0 <<< 5,
    W2 = W2 <<< 22,

    Wn — n- 32- ,
    << <<< — , . . [3], Serpent.

    , , , :

    Y = L(S(i mod 8)(X Å Ki)),
    X Y — , ,
    i — ( 0 31),
    Ki — i- ,
    L — ,
    S 32 .

    , ; 33- K32:

    Y = S7(X Å K31) Å K32

    . , S0...S7 InvS0...InvS7:

    InvS01331101065121144715982
    InvS15821415612311479113100
    InvS21291541114120361358107
    InvS30910711146133512248151
    InvS45083109714212116415131
    InvS58152941131411653712100
    InvS61510113536049147212811
    InvS73061391415851211710142

    , ( ):

    53, 55, 721, 5, 20, 9015, 1023, 31, 90
    57, 59, 765, 9, 24, 9419, 1067, 35, 94
    61, 63, 809, 13, 28, 9823, 11011, 39, 98
    65, 67, 8413, 17, 32, 10227, 1141, 3, 15, 20, 43, 102
    69, 71, 8817, 21, 36, 1061, 31, 1185, 7, 19, 24, 47, 106
    73, 75, 9221, 25, 40, 1105, 35, 1229, 11, 23, 28, 51, 110
    77, 79, 9625, 29, 44, 1149, 39, 12613, 15, 27, 32, 55, 114
    81, 83, 1001, 29, 33, 48, 1182, 13, 431, 17, 19, 31, 36, 59, 118
    85, 87, 1045, 33, 37, 52, 1226, 17, 475, 21, 23, 35, 40, 63, 122
    89, 91, 1089, 37, 41, 56, 12610, 21, 519, 25, 27, 39, 44, 67, 126
    93, 95, 1122, 13, 41, 45, 6014, 25, 552, 13, 29, 31, 43, 48, 71
    97, 99, 1166, 17, 45, 49, 6418, 29, 596, 17, 33, 35, 47, 52, 75
    101, 103, 12010, 21, 49, 53, 6822, 33, 6310, 21, 37, 39, 51, 56, 79
    105, 107, 12414, 25, 53, 57, 7226, 37, 6714, 25, 41, 43, 55, 60, 83
    0, 109, 11118, 29, 57, 61, 7630, 41, 7118, 29, 45, 47, 59, 64, 87
    4, 113, 11522, 33, 61, 65, 8034, 45, 7522, 33, 49, 51, 63, 68, 91
    8, 117, 11926, 37, 65, 69, 8438, 49, 7926, 37, 53, 55, 67, 72, 95
    12, 121, 12330, 41, 69, 73, 8842, 53, 8330, 41, 57, 59, 71, 76, 99
    16, 125, 12734, 45, 73, 77, 9246, 57, 8734, 45, 61, 63, 75, 80, 103
    1, 3, 2038, 49, 77, 81, 9650, 61, 9138, 49, 65, 67, 79, 84, 107
    5, 7, 2442, 53, 81, 85, 10054, 65, 9542, 53, 69, 71, 83, 88, 111
    9, 11, 2846, 57, 85, 89, 10458, 69, 9946, 57, 73, 75, 87, 92, 115
    13, 15, 3250, 61, 89, 93, 10862, 73, 10350, 61, 77, 79, 91, 96, 119
    17, 19, 3654, 65, 93, 97, 11266, 77, 10754, 65, 81, 83, 95, 100, 123
    21, 23, 4058, 69, 97, 101, 11670, 81, 11158, 69, 85, 87, 99, 104, 127
    25, 27, 4462, 73, 101, 105, 12074, 85, 1153, 62, 73, 89, 91, 103, 108
    29, 31, 4866, 77, 105, 109, 12478, 89, 1197, 66, 77, 93, 95, 107, 112
    33, 35, 520, 70, 81, 109, 11382, 93, 12311, 70, 81, 97, 99, 111, 116
    37, 39, 564, 74, 85, 113, 11786, 97, 12715, 74, 85, 101, 103, 115, 120
    41, 43, 608, 78, 89, 117, 1213, 9019, 78, 89, 105, 107, 119, 124
    45, 47, 6412, 82, 93, 121, 1257, 940, 23, 82, 93, 109, 111, 123
    49, 51, 681, 16, 86, 97, 12511, 984, 27, 86, 97, 113, 115, 127

    AES, Serpent : 128, 192 256 . , , Serpent , 256. «» :

    1. .
    2. 256- .

    , :

    1. 256- ( ) 8 32- , w-8...w-1.
    2. — w0...w131:
      wi = (wi-8 Å wi-5 Å wi-3 Å wi-1 Å f Å i) <<< 11,
      f — (√5 + 1) / 2, .. 9E3779B9 .
    3. S0...S7 ( Serpent):

      K0 = S3({w0, w1, w2, w3}),
      K1 = S2({w4, w5, w6, w7}),
      K2 = S1({w8, w9, w10, w11}),
      K3 = S0({w12, w13, w14, w15}),
      K4 = S7({w16, w17, w18, w19}),
      K5 = S6({w20, w21, w22, w23}),
      K6 = S5({w24, w25, w26, w27}),
      K7 = S4({w28, w29, w30, w31}),
      ...
      K31 = S4({w124, w125, w126, w127}),
      K32 = S3({w128, w129, w130, w131}).

    - Serpent. -. , — . - .

    Twofish

    Serpent, Twofish (Bruce Schneier) — ( . . [22]), Blowfish [15] Counterpane Systems, . , (John Kelsey), (Chris Hall) (Niels Ferguson) Counterpane Systems, (Doug Whiting) Hifn Incorporated ( Internet-) (David Wagner) .

    Twofish 32- ( A, B, C, D), 16 , (. . 3) [16]:

    Twofish
    . 3. Twofish.
    ٸ .
    1. B 8 .
    2. A g(), .
    3. B g().
    4. B A 232, A B.
    5. K2r+8 ( r — , 0) A 232.
    6. , K2r+9 B.
    7. A C XOR.
    8. D 1 .
    9. B D XOR.
    10. C 1 .

    B = B <<< 8,
    A = g(A),
    B = g(B),
    A = A + B mod 232,
    B = A + B mod 232,
    A = A + K2r+8 mod 232,
    B = B + K2r+9 mod 232,
    C = C Å A,
    D = D <<< 1,
    D = D Å B,
    C = C >>> 1.

    g() 32- (. . 4):

    g() Twofish
    . 4. g() Twofish.
    1. 4 8 .
    2. 8 * 8 S0...S3. ; .
    3. ( s0...s3) M1:

      g0...g3 — g().
      GF(28) x8 + x6 + x5 + x3 + 1.
      M1 ( ):

      01EF5B5B
      5BEFEF01
      EF5B01EF
      EF01EF5B

    , , A ( ) C ; B ( ) D .

    — XOR K0...K3. — K4...K7.

    , Twofish , Serpent, .

    40 32- 16 . , S0...S3.

    Serpent, Twofish 256 . , : , , , .. 128, 192 256 . .

    , :

    1. , :
      k = N / 64,
      N — , .. k 2, 3 4. 8k m0...m8k-1 2k 32- , M0...M2k-1.
    2. 3 , k 32- :

      Me = (M0, M2, ..., M2k-2),
      Mo = (M1, M3, ..., M2k-1),
      V = (Vk-1, Vk-2, ..., V0),

      :

      M2 :

      01A455875A58DB9E
      A45682F31EC668E5
      02A1FCC147AE3D19
      A455875A58DB9E03

    k0...k39 Me Mo :

    k2i = Ai + Bi mod 232,
    k2i+1 = (Ai + 2Bi mod 232) <<< 9,

    i = 0...19, Ai Bi — , :

    Ai = h(2iρ, Me),
    Bi = h((2i + 1)ρ, Mo) <<< 8.

    ρ :

    ρ = 224 + 216 + 28 + 1,

    h() .

    . 5.

    h() Twofish.
    . 5. h() Twofish.

    , 64- , .. k. h() 32- 32- k. :

    1. 4 8- , q0 q1 ( . 5). 32- , ( . 5 Me). , k < 4 (.. k = 2 k = 3). . 5 h().
    2. ( q0 q1, — . . 5), . 2 , k = 2.
    4. ( — 3 k = 2), , , .
    5. , q0 q1, :

      y0...y3 — 5, M1 ; H — h().

    q0 q1 8 * 8 , 4 * 4 :

    a0 = ëx / 16û,
    b0 = x mod 16,
    a1 = a0 Å b0,
    b1 = a0 Å (b0 >>>41) Å 8a0 mod 16,
    a2 = t0(a1),
    b2 = t1(b1),
    a3 = a2 Å b2,
    b3 = a2 Å (b2 >>>41) Å 8a2 mod 16,
    a4 = t2(a3),
    b4 = t3(b3),
    y = 16b4 + a4,

    x — ,
    y — ,
    >>>4 — 4- , .. ;
    ti — , q0 q1; q0 :

    t0817D6F320B59ECA4
    t1ECB81235F4A6709D
    t2BA5E6D90C8F32471
    t3D7F4126E9B3085CA

    , ; , t1 0 E, 1 C ..

    q1 :

    t028BDF76E31940AC5
    t11E2B4C376DA5F908
    t24C75169A0ED82B3F
    t3B951C3DE647F208A

    S0...S3. , g() h(), 32- A B, — V. , t0...t3, .

    , , . [16] , , :

    • ,
    • ,
    • .

    : , , .

    Twofish-FK

    Twofish, Twofish Family Key ( Twofish-FK) — Twofish , , , , , .

    (FK), , Twofish-FK. .. FK , Twofish-FK.

    FK :

    1. , ( FK):
      T0 = FK,
      T1 = (EFK(0) | EFK(1)) Å FK,
      T2 = EFK(2),
      T3 = EFK(3),
      T4 = EFK(4) mod 264,

      EFK(N) — Twofish FK 128- , N, ,
      | — .

      , T0 T1 256 , T2 T3 — 128 , T4 — 64 .

    2. FK, , FK:
      • T0 XOR. , 256 , T0.
      • XOR T2 K0...K3, T3 — K4...K7, T4 — , .
      • XOR T1 .

    , Twofish-FK, , Twofish, [16].

    ,

    1. AES Round 1 Information. // http://csrc.nist.gov — January 26, 2001.
    2. Anderson R., Biham E. Two Practical and Provably Secure Block Ciphers: BEAR and LION. // http://citeseer.ist.psu.edu — 1995.
    3. Anderson R., Biham E., Knudsen L. Serpent: A Proposal for the Advanced Encryption Standard. // http://csrc.nist.gov.
    4. Announcing Request for Candidate Algorithm Nominations for the Advanced Encryption Standard (AES). // http://csrc.nist.gov — Department of Commerce — National Institute of Standards and Technology — Federal Register: September 12, 1997.
    5. Biham E., Dunkelman O., Keller N. Differential-Linear Cryptanalysis of Serpent. // http://citeseer.ist.psu.edu — Technion, Haifa, Israel.
    6. Burwick C., Coppersmith D., DAvignon E., Gennaro R., Halevi S., Jutla C., Matyas S.M.Jr., OConnor L., Peyravian M., Safford D., Zunic N. MARS — a candidate cipher for AES. // http://www.ibm.com — IBM Corporation — Revised, September, 22 1999.
    7. Courtois N., Castagnos G., Goubin L. What do DES S-boxes Say to Each Other? // http://eprint.iacr.org — Axalto Cryptographic Research & Advanced Security, Cedex, France.
    8. Daemen J., Knudsen L., Rijmen V. The Block Cipher Square. // http://www.esat.kuleuven.ac.be.
    9. FIPS 46-3. Data Encryption Standard (DES). // http://csrc.nist.gov — Reaffirmed 1999 October 25.
    10. FIPS 81. DES Modes of Operation. // http://csrc.nist.gov — 1980 December 2.
    11. Kocher P.C. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. // http://citeseer.ist.psu.edu — Cryptography Research, Inc., San Francisco, USA.
    12. Nechvatal J., Barker E., Bassham L., Burr W., Dworkin M., Foti J., Roback E. Report on the Development of the Advanced Encryption Standard (AES). // http://csrc.nist.gov — National Institute of Standards and Technology.
    13. Nechvatal J., Barker E., Dodson D., Dworkin M., Foti J., Roback E. Status report on the first round of the development of the advanced encryption standard. // http://csrc.nist.gov — National Institute of Standards and Technology.
    14. Rivest R.L., Robshaw M.J.B., Sidney R., Lin Y.L. The RC6 Block Cipher. // http://www.rsasecurity.com — Version 1.1 — August 20, 1998.
    15. Schneier B. Description of a new variable-length key 64-bit block cipher (blowfish). // http://www.schneier.com.
    16. Schneier B., Kelsey J., Whiting D., Wagner D., Hall C., Ferguson N. Twofish: A 128-bit Block Cipher. // http://www.schneier.com — 15 June 1998.
    17. What are RC5 and RC6? // http://www.rsasecurity.com.
    18. . DES . // Connect! . — 2006 — 3-6.
    19. . , 2. // BYTE/. — 2006 — 5 — . 74-79.
    20. .., .. : . . .. . — .: , 2005 — 176 .
    21. .., .. . — .: , 2002 — 656 .
    22. . . , , . — . .: .: , 2002 — 816 .

    [ : MARS RC6; ]



    24 2006 , http://www.panasenko.ru

    Новости

    Раздел новостей >
    Попробовать новый дизайн       Подробнее

    Copyright © 1997—2024.

    О сайте

    Адрес для связи info@ixbt.com

    Наши проекты
    Полезные ссылки
    Связь с администрацией

    Нашли ошибку? Выделите текст и нажмите Shift+Enter.

    Copyright © 1997-2024