Министерство образования и науки Российской Федерации

Г С Д Р Т Е Н ЕО Р З В Т Л Н ЕУ Р Ж Е И

О УАСВНО БАОАЕЬО Ч Е Д Н Е

В С Е ОП О Е С О А Ь О ОО Р З В Н Я

Ы Ш Г Р Ф СИНЛНГ БАОАИ

Р С И С И Г С Д Р Т Е Н ЙГ Д О Е Е Р Л Г Ч С И У И Е С Т Т

О С Й К Й ОУ А С В Н Ы ИРМТОООИЕКЙ НВРИЕ

П.П. Б е с к и д, Т.М. Т а т а р н и к о в а

КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ

ЗАЩИТЫ ИНФОРМАЦИИ

Часть 2

А Л Г О Р И Т М Ы, М Е Т О Д Ы И С Р Е Д С Т В А О БЕ С П Е Ч Е Н И Я

КОНФ ИДЕНЦИАЛЬНОСТИ, ПОДЛИННОСТИ И

ЦЕЛОСТНОСТИ И Н Ф ОРМ АЦИИ

Учебное пособие РГГМУ Санкт-Петербург УДК 621.391.037. Бескид П.П., Татарникова Т.М. Криптографические методы защи­ ты информации. Часть 2. Алгоритмы, методы и средства обеспе­ чения конфиденциальности, подлинности и целостности информа­ ции. Учебное пособие. СПб., изд. РГГМУ, 2010. - 104 с.

Рецензент: Молдовян Н.А., д-р техн. наук, проф., зав. лаборато­ рией криптологии СПИИРАН.

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

Предназначено для подготовки специалистов по специальности 090106 - информационная безопасность телекоммуникационных систем.

Может быть полезно при выполнении курсового проектирования, а также при выполнении лабораторных работ и практических занятий.

Beskid P.P., Tatamikova Т.М. Cryptographic methods of information protection. Part 2. Algorithms, methods and means of ensuring confidentiality, authenticity and integrity of information. A manual. St.

Petersburg, RSHU Publishers, 2010. - 104 pp.

(г.

* The manual presents the practical part of the discipline "Cryptographic S Methods of Information Protection: description of modem cryptographic algorithms, methods and means to ensure authenticity of information through electronic signature and algorithms ensuring integrity of information - the hash functions.

Intended for training experts in Speciality 090106 ‘Information Security of Telecommunication Systems’.

The book may be useful for preparing course projects and doing laboratory work and practicals.

© Бескид П.П., Татарникова T.M., О Российский государственный гидрометеорологический гидрометеорологический дамрвии»!

би бл и о тека 196J96, С б, М П алоохтяиский пр.,

ВВЕД ЕН И Е

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

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

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

В математической или теоретической криптографии стремят­ ся показать, что задача взламывания шифра является задачей со строго доказуемыми свойствами, в частности, ее решение имеет определенную «сложность» в рамках той или иной математиче­ ской модели, например, в рамках теоретико-информационного или теоретико-сложностного подхода.

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

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

Обычно усилия направляются на вычисление ключа.

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

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

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

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

1. КЛАССИФИКАЦИЯ ШИФРОВ ПО КЛЮЧЕВОЙ

ИНФОРМАЦИИ

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

Однако побитовая обработка информации является очень медленной в тех случаях, когда вычислительная техника имеет возможности для параллельной обработки, т.е. в программной реализации. Разрядность основной массы современных процессо­ ров равна 32 битам, существуют 64- и 80-разрядные аппаратные платформы. В этих условиях, особенно тогда, когда информация все равно переносится в буфер в том или ином объеме (пакеты в компьютерных сетях, файлы на носителях), гораздо выгоднее применять совершенно другие принципы криптографических пре­ образований, называемые блочными шифрами.

Основным законом блочного шифрования является «или блок, или ничего». То есть преобразования могут применяться только над информацией строго определенного объема. Размер блока на сегодняшний день равен 64, 128 или 256 битам. Частичное шифро­ вание (скажем, попытка обработать 177 бит) невозможно. Блочное шифрование получило гораздо более широкое распространение изза развития современной электронно-вычислительной техники, и если поточные шифры одинаково часто реализуются как про­ граммно, так и аппаратно, то блочные шифры в подавляющем большинстве имеют программную реализацию.

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

Поточный шифратор представляет собой автомат Ац, который вырабатывает псевдослучайную последовательность g-{go,.gn,..) обычно двоичную. В качестве шифрованной информации высту­ пает последовательность w = (wo,..,,w„,...), w„=J(m„,g„), где т = (то,...,т„,...) - открытый текст. Обычно в качестве функции наложения / используется функция сложения в каком либо конеч­ ном поле или кольце, в частности, в двоичном случае w„ = mn ®g„.

Здесь обратное преобразование (дешифрование) осуществляется точно так же: m„ = w„®g„, что позволяет на обоих концах канала связи иметь шифраторы с одинаковыми ключами.

Рис. 1. Общая схема классификации шифров Блочный шифратор представляет собой автомат Ак, входами которого является последовательность т и выходами - последова­ тельность w= Ак(т) длины п. Входная последовательность разби­ вается на блоки длины п и каждый блок шифруется независимо один от другого на одном ключе К. Блочный шифратор реализует перестановку элементов пространства А”, где А - используемый алфавит. Самым известными блочными шифраторами являются американский шифратор DES (data encryption standard) и отечест­ венный стандарт ГОСТ 28147-89, у которых длина блока п равна 64 и 256 соответственно. Имеются и другие типы шифраторов, от­ личные от этих, которые будут рассмотрены далее.

2. СИМЕТРИЧНАЯКРИПТОГРАФИЯ.

СТАНДАРТЫБЛОЧНОГО ШИФРОВАНИЯ

Взлет производительности вычислительной техники внес сильные коррективы в развитие криптографии. Первыми «пострадали» прими­ тивные операции, которые неприемлемо долго исполнялись в про­ граммной реализации. К таковым относятся, например, перестановки бит. Если в аппаратной схеме перестановка реализуется всего лишь распайкой контактов и дорожек и выполняется за один условный такт, то в универсальных программных модулях типа микропроцессора си­ туация гораздо сложнее. В Общем случае на перестановку или выборку каждого бита требуется одна или две команды процессора, что требует, например, для перестановки 32 бит исполнения 64 операций. Тщатель­ ная оптимизация может позволить сократить их количество за счет параллельной обработай нескольких бит в 2-3 раза, но не более того.

Следующим параметром, величина которого намного быстрее, чем ожидалось, стала неприемлемо мала, оказалась длина ключа.

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

Безальтернативная тенденция к более универсальной про­ граммной реализации вынудила создателей криптоалгоритмов считаться с законами этого направления. Во-первых, для улучше­ ния основной характеристики «скорость шифрования/стойкость»

требовались не только быстрые в программном исполнении опе­ рации, но и оптимизация их разрядности цод разрядность микро­ процессора. За довольно продолжительным периодом 8-битных операций последовал короткий 16-битный и уступил свое место нынешней повсеместной 32-разрядной оптимизации.

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

Еще одной неожиданной задачей в развитии криптографиче­ ских алгоритмах оказалась их оптимизация под параллельные ар­ хитектуры ЭВМ. Все чаще в специализированных системах и сер­ верных станциях можно встретить многопроцессорные платфор­ мы. Основным ресурсом, потребляемым криптопреобразованиями, является как раз процессорное время. Количественным критерием, характеризующим способность алгоритма к распараллеливанию, является среднее количество потоков (процессоров), на которые можно разделить данную задачу. Естественно, что во многих точ­ ках алгоритма обрабатываемые данные должны сходиться вместе на одном процессоре для перемешивания, так необходимого в криптопреобразованиях. Однако количество подобных точек не­ обходимо уменьшать в разумных пределах, а количество незави­ симых потоков, на которые можно разделить процесс между таки­ ми точками, устремить хотя бы к четырем-шести-восьми. В целом снова получается проблема поиска золотой середины между стой­ костью шифра и скоростью его работы.

2.1. Аппаратное шифрование DES Структура DES Традиционно первой знаменательной вехой в истории блочно­ го шифрования считается опубликование в 1977 г. и принятие в 1980 г. в США национального Стандарта шифрования данных DES (Data Encryption Standart). Параметры алгоритма таковы: разряд­ ность блока - 64 бита, размер ключа - 56 бит. Алгоритм представ­ ляет собой классическую сеть Файстеля из 16 раундов с добавле­ нием входной и выходной перестановок бит. Общая структура ал­ горитма представлена на рис. 2.

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

57, 49, 41, 33, 25,17, 9, 1, 59, 51, 43, 35, 27, 19, II, 3, Общая формула для вычисления индексов в псевдокоде имеет вид:

где запись ir обозначает г-й бит в записи числа г, символ | - конкатенацию цифр в двоичной записи числа.

Выходная перестановка бит является обратной к входной, правило перестановки бит в ней имеет вид:

40, 8,48,16, 56, 24, 64, 32, 39, 7,47,15, 55, 23, 63, 31, 38,6,46, 14, 54, 22, 62, 3 0,3 1,5,4 5, 13, 53,21,61,29, 36, 4, 44,12, 52, 20, 60,28, 35, 3, 3, И, 51, 19, 59, 27, 34, 2,42, 10, 50, 18, 58, 26, 33, 1,4 1,9,4 9, 11,57,25.

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

Разрядность ключей раундов, применяемых в DES равна битам. Для симметричности алгоритма шифрования/дешифро­ вания в DES, как и в классической сети Файстеля, производится дополнительно размен последнего обмена ветвей. Это позволяет производить шифрование и дешифрование одним и тем же про­ граммным кодом, передавая ему в первом случае ключи раундов в прямом порядке (ко, к\$), а во втором случае - в обратном (&15, & 4,... До). Общий вид сети Файстеля алгоритма DES приведен на рис. 3.

Образующая функция сети в алгоритме DES состоит из 4 опе­ раций:

1. Перестановка бит/расширение блока с помощью повторов по определенной схеме.

2. Наложение ключа раунда операций XOR.

3. Табличные подстановки.

4. Перестановка бит.

Расширение входных данных производится на уровне бит за­ писью некоторых из них в выходной поток дважды. В результате из 32 бит получается 48-битный блок информации, совпадающий по размеру с ключом раунда. Закон расширения выглядит сле­ дующим образом (приведены порядковые номера битов исходного блока, считая с «1»):

12, 13, 12, 13, 14, 15, 16, 17, 16, 17, 18, 19, 20, 21, 20, 22, 23, 24, 25, 24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32, Наложение ключа раунда производится операцией XOR, раз­ рядность операции - 48 бит. Правило генерации ключей раунда рассмотрим позднее.

Табличные подстановки, применяемые в DES, имеют разряд­ ность 6x4 бита, 48-битный блок данных после наложения ключа разбивается на 8 блоков по 6 бит. Каждый блок пропускается через свою табличную подстановку, обозначаемую 50, Si и т д. В резуль­ тате получаются 8 блоков по 4 бита в каждом: итого 32 бита - пер­ воначальная разрядность обрабатываемой ветви.

Заключительной операцией образующей функции является перестановка бит внутри 32-битного блока, отвечающая за пере­ мешивание информации. Правило перестановки выглядит сле­ дующим образом (приведены порядковые номера битов из 32разрядного блока - результата табличных подстановок, считая с «1»):

16, 7, 20, 21, 29 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10, 2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25.

Общий вид одного раунда сети Файстеля алгоритма DES при­ веден на рис.4.

DES: расширение клю ча Расширение ключа (создание ключей раунда) производится в DES по следующей схеме. На основе 56 значащих бит из ключа на начальном этапе создаются два 28-битных вектора Со и Do путем выбора бит из ключа в определенной последовательности.

Закон выбора бит из ключа для Со:

57,49,41, 33, 25,17, 9, 1, 58, 50, 42, 34, 26, 18, 10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, Закон выбора выбора бит из ключа для D0\ 63, 55, 47, 39 31, 23,15, 7, 62, 54,46, 38, 30, 22, Институтом стандартизации рекомендовано при хранении ключа для DES пользоваться помехоустойчивым кодированием проверкой четности. Поэтому в каждом байте значащими являют­ ся только первые 7 бит, а восьмой добавляется при записи, исходя из правила «количество единиц в двоичной записи каждого байта нечетно». Таким образом, при истинной разрядности ключа в бит хранится он в 64-битной структуре. Именно этим объясняется появление в законах выбора бит для Со и D0 номеров больших 56 и отсутствие бит с номерами 8, 16, 24, 32, 40, 48, 56 64 (они являют­ ся контрольными - незначащими).

Для генерации каждого очередного ключа раунда к, векторы С0 и D0 циклически сдвигаются влево на количество разрядов, ука­ занное в табл. 1.

Величины циклических сдвигов векторов С0 и D0 при генерации ключа ROL н а... разрядов Для выбора 48 бит ключа г-го раунда, получившиеся после циклических сдвигов векторы С,Д объединяются, и из 56 бит по­ лучившегося массива отбираются 48 по следующему закону:

26, 8, 16, 7, 27, 20, 13, 2, 41, 52, 31, 37, 47, 55, 30, 40, 51,45,33,48,44, 49, 39,56,34, 53,46,42, 50, 36, 29, 32.

Des: анализ Первое, что бросается в глаза, - это огромное количество би­ товых перестановок и выборок в алгоритме. Это связано с тем, что основной схемой разработчиками планировалось только аппарат­ ная реализация. Этому подчинено и наложение ключа именно опе­ рацией XOR, реализуемой в этом случае наиболее просто и распа­ раллелено, и небольшой размер, и минимальное количество таб­ личных подстановок. Аппаратная реализация алгоритма на от­ дельной или встроенной микросхеме позволяет достичь высокой скорости шифрования при очень небольшом объеме устройства.

Единственным нелинейным элементом алгоритма является этап табличной подстановки в образующей функции Создатели алгоритма не объяснили принцип выбора используемых таблиц, однако привели несколько правил, которым удовлетворяют вы­ бранные таблицы с целью защиты от некоторых видов криптоана­ лиза.

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

еслиY = EnCrypt(X, KEY), то Y ’ = EnCrypt(X’, K EY’), где X ’ - побитная инверсия X, Y' - побитная инверсия Y, K E Y’ - побитная инверсия KEY.

Вторым свойством является наличие среди множества ключей четырех слабых ключей. Это следующие числа в шестна­ дцатиричной записи (с контрольным 8-м битом в каждом байте):

При шифровании данных любым из этих ключей среди 2м ва­ риантов входных данных существует 232 блоков, которые в резуль­ тате шифрования преобразуются сами в себя, то есть EnCrypt(X, KEY)=X. Несмотря на то что вероятность подобного «бесполезно­ го» шифрования очень велика (1/232 - это высокий риск для крип­ тографии), вероятность того, что сам ключ окажется слабым, очень мала (1/254). Это позволяет считать наличие слабых ключей у DES, скорее, оригинальной особенностью, чем реальной уязвимостью.

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

2.2. Криптоалгоритм TEA Структура TEA Одним из самых простых представителей семейства про­ граммно ориентированных надежных блочных шифров является TEA (Tiny Encryption Algorithm). Дословно его название перево­ дится на русский язык как “крошечный криптоалгоритм». Разрабо­ тан он был в исследовательском центре защиты информации Кем­ бриджского университета и представляет собой классическую сеть Файстеля из 64 раундов. Схема алгоритма приведена на рис. 5. Ал­ горитм оптимизирован под 32-разрядные микропроцессоры, раз­ мер блока - 64 бита.

Результат образующей функции накладывается на независи­ мую ветвь операцией «сложение», поэтому восстановить исход­ ный текст простым обращением порядка ключей раунда невоз­ можно. Алгоритм TEA является примером несимметричной сети Файстеля: для дешифрования приходится реализовывать отдель­ ную процедуру, хотя, как и шифрование, очень простую.

ТЕЛ: расширение клю ча Алгоритм использует 128-битный ключ, который превращается в ключи раунда по очень простой схеме. Ключ разбивается на четыре 32разрядных машинных слова К0, К2, Ку Во всех четных (считая с 0) раундах в качестве 64-битного ключа раунда используется пара (К0, Кi) в нечетных - пара (К2, #з). В общепринятой схеме номер ра­ унда обозначается переменной /; раундов - г, компоненты ключа раун­ да - как массив k[i] (он использует сквозную нумерацию по машинным словам - в нулевом раунде используются &[0] и k\Y], в первом - к[2] и к[3] и т. д.). В таких обозначениях общая формула создания 128 ком­ понент материала ключа для TEA выглядит следующим образом:

k \l\ Анализ TEA В образующей функции TEA используются только битовые сдвиги, сложение и исключающее ИЛИ. Это приводит к тому, что в алгоритме полностью отсутствуют нелинейные преобразования.

Стойкость к линейному криптоанализу обеспечивается большим не свойственным для сети Файстеля числом раундов. Согласно исследованиям разработчиков, TEA стоек ко всем опубликован­ ным на сегодняшний день видам криптоатак. Однако из-за своей предельной простоты, которая может вызвать подозрение на нали­ чие уязвимостей к какому-либо специфическому виду криптоана­ лиза, алгоритм все-таки не получил широкого применения на практике.

2.3. Криптоалгоритм IDEA Струтктура IDEA Алгоритм IDEA (International Data Encryption algirithm) разработан специально на смену DES, удовлетворяет почти всем требованиям ново­ го криптопоколения и в отличие от TEA получил широкое применение.

IDEA построен по схеме, очень напоминающей сеть Файсте­ ля. Подобный принцип проектирования блочных шифров в клас­ сификации получил название обобщенной сети Файстеля. Исход­ ный блок данных длиной в 64 бита разбивается на 4 ветви - все операции в IDEA выполняются в 16-битной арифметике. Затем в каждом из 8 раундов над ветвями и материалом ключа выполня­ ются в специально подобранной очередности три операции: «сло­ жение», «исключающее ИЛИ» и «модифицированное умножение».

Схема одного раунда IDEA приведена на рис. 6. Модифицирован­ ное умножение изображено на схеме символом *. Длина ключа алгоритма составляет 128 бит.

Модифицированное умножение представляет собой обычное умножение по модулю 65537 (21 +1) с двумя условностями. Вопервых, если какой-либо из сомножителей равен 0, то перед умноже­ нием он заменяется на 216. Во-вторых, если получившееся после взя­ тия модуля число равно 21 то оно заменяется на 0. Определенная подобным образом операция обладает следующими свойствами:

- отображает пару 16-разрядных чисел на 16-разрядное число;

- обратима (по известному результату и одному из сомножи­ телей возможно однозначно определить второй сомножитель).

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

IDEA: расширение клю ча Получение из 128-битного ключа материала ключа в IDEA предельно просто. Первые 8 16-битных компонент &[0]...А:[7] мате­ риала ключа получаются непосредственно разбиением 128 бит ключа на блоки без каких-либо преобразований. Затем 6 раз по­ вторяется следующая операция: ключ сдвигается циклически вле­ во на 25 бит и очередные 8 компонент получаются таким же раз­ биением уже сдвинутого ключа на 16-битные блоки.

В псевдокоде расширение ключа выглядит следующим обра­ зом:

k[Q]...k[7] = key k[8]...k[15] = key Для дешифрования в IDEA можно использовать тот же самый основной алгоритм, но предварительно специальным образом не­ обходимо подготовить материал ключа. Если обозначим 52 ком­ поненты материала ключа, используемые для шифрования через е[0]...е[51], а материал для дешифрования J[0]...

ричной.

тектур ы Э В М.

сч и та е тся д ля это й ц ели н ед о стато чн о й ;

б и та;

м етр а.

реком енд ац и й для A E S :

стел я.

TwoFish: структура д ена н а р и с. 26.

р ы расш и р ен и я клю ча.

TwoFish: анализ ц ед уры р асш и р ен и я кл ю ча.

ва те л ь ски х ц ентров м ира.

Serpent: структура м еров в 128 б и т.