Конкурсы по выбору симметричных функций в криптографии. AES. NESSIE. CRYPTREC

17

Міністерство освіти і науки, молоді та спорту України

Запорізький національний технічний університет

кафедра ПЗ               

РЕФЕРАТ

на тему: «Конкурсы по выбору симметричных функций в криптографии.

AES. NESSIE. CRYPTREC »

Виполнила:

ст. гр. ИВТ-717                                                                                                                                            Е.А.Фандеева

Прийняла:                                                                                                                                            А.В.Неласая

2011

Содержание

1.              Выбор криптостандартов

2.              NESSIE – конкурс

2.1.              Конкурс AES

2.2.              Организаторы и участники NESSIE

2.3.              Победители конкурса

2.4.              MISTY1

2.5.              Camellia

2.6.              SHACAL-2

2.7.              Политика

3.              CRYPTREC – проект по выбору криптостандартов Японии

3.1.              Цели и этапы CRYPTREC

3.2.              Технологии и алгоритмы, рассматриваемые в рамках проекта

3.3.              Сравнение CRYPTREC с конкурсом NESSIE

4.              AES — конкурс

4.1.              Начало конкурса

4.2.              Конкурс AES

4.3.              Первый раунд AES

4.4.              Второй раунд AES

4.5.              Голосование

4.6.              Третья конференция AES

4.7.              Выбор победителя

5.              Классификация критериев и показателей эффективности функционирования схем ПШ

Литература

1.      Выбор криптостандартов

В большинстве развитых стран использование различных средств защиты информации регулируется государством, а алгоритмы защиты стандартизованы. В России из перечисленных выше типов алгоритмов есть стандарты на симметричное шифрование (ГОСТ 28147—89), ЭЦП (ГОСТ Р 34.10—94 и ГОСТ Р 34.10—2001) и хэширование (ГОСТ Р 34.11—94).

Отечественные криптостандарты разрабатывались в недрах соответствующих спецслужб. Особенно показательна в этом смысле история алгоритма шифрования ГОСТ 28147—89, который разрабатывался еще в Советском Союзе. Несколько лет после разработки этот алгоритм имел статус секретного и только в начале 90-х годов был рассекречен и опубликован в открытой печати.

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

Организаторы объявляют конкурс на выбор стандартов защиты информации, публикуют требования к алгоритмам-претендентам. В течение определенного срока математики и криптологи присылают свои алгоритмы для участия в конкурсе.

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

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

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

2.      NESSIE – конкурс

В январе 2000 года в Бельгии начался трехлетний европейский криптопроект NESSIE (New European Schemes for Signatures, Integrity, and Encryption), целью которого являлся отбор криптографических алгоритмов, на базе которых, теоретически, должны формироваться будущие криптостандарты Европы.

2.1. Конкурс AES

За три года до старта NESSIE в США состоялся весьма похожий конкурс AES (Advanced Encryption Standard). «Конкурсантами» являлись алгоритмы блочного шифрования, присланные различными организациями и частными лицами, из которых специалисты Института стандартов и технологий США (NIST – National Institute of Standards and Technologies) должны были выбрать новый стандарт блочного шифрования США.

Из 15 алгоритмов, присланных на конкурс, NIST выбрал на первом этапе те 5 из них, в которых не обнаружилось уязвимостей и различных недостатков (недостатками считались, например, низкая скорость шифрования или высокие требования к оперативной и/или энергонезависимой памяти). На втором этапе эксперты отдали предпочтение алгоритму Rijndael (его авторы – криптографы из Бельгии Joan Daemen и Vincent Rijmen), который и стал новейшим стандартом блочного шифрования США.

2.2. Организаторы и участники NESSIE

Конкурс NESSIE был организован рядом научных организаций из Бельгии, Германии, Великобритании, Франции, Норвегии и Израиля. Как и в конкурсе AES, участниками могли стать любые организации и частные лица со всего мира, для чего следовало прислать алгоритм собственной разработки, предназначенный для выполнения одной из следующих криптографических операций:

 блочное шифрование данных (для 64-, 128- и 160-битных блоков, а также блоков, размер которых является параметром алгоритма; всего прислано 17 алгоритмов);

 потоковое шифрование (6 алгоритмов),

 хэширование (3),

 асимметричное шифрование (5),

 электронная цифровая подпись (7).

Кроме того, на конкурс были присланы алгоритм асимметричной идентификации и криптоаналитический алгоритм.
Как видно, NESSIE был задуман как существенно более широкий, чем AES, проект – шутка ли, его устроители замахнулись, фактически, на выбор криптостандартов для большинства криптографических применений! Впрочем, к этой теме мы еще вернемся несколько позже.
Еще одно техническое отличие NESSIE от AES – более подробные технические требования к алгоритмам: если описание блочного шифра – потенциального криптостандарта США – можно было уложить в несколько строк, то организаторы NESSIE установили строгий интерфейс к реализациям алгоритмов в виде описания экспортируемых функций на «portable C».
Выбор оптимальных алгоритмов проходил в 3 этапа:

1.                       Первичное изучение алгоритма.

2.                       Криптоаналитические исследования, на основании которых делался вывод о возможных уязвимостях конкретного алгоритма.

3.                       Сравнение алгоритмов, прошедших предыдущий этап, по ряду критериев: быстродействие, минимальные требования к вычислительным ресурсам и т. д.

Как и на конкурс AES, алгоритмы были присланы буквально со всего мира. Стоит отметить, что в конкурсе принимал участие и алгоритм из России – алгоритм блочного шифрования NUSH, который, к сожалению, был отвергнут на достаточно раннем этапе по причине отсутствия в нем табличных замен или других нелинейных операций, что доказанно делало этот алгоритм уязвимым к линейному криптоанализу (линейный криптоанализ основан на поиске зависимостей между символами открытого и зашифрованного текста).
Среди остальных претендентов стоит отметить алгоритмы, участвовавшие в конкурсе AES: RC6 (представлен компанией RSA Laboratories) и SAFER++ (разработчики – фирма ETH Zurich, Швейцария в сотрудничестве с Академией Наук Армении), последний из них – незначительно измененный SAFER+, который был отклонен на первом этапе конкурса AES. Кроме того, претендентами в конкурсе NESSIE были широко используемый алгоритм блочного шифрования IDEA и известная схема электронной подписи на эллиптических кривых ECDSA. Часть участвовавших алгоритмов была разработана специально в надежде победить в конкурсе NESSIE.

2.3. Победители конкурса

На первом этапе исследований алгоритмов эксперты выбрали 24, из которых впоследствии было выбрано 12 алгоритмов, не содержащих уязвимостей. Здесь организаторы конкурса дополнили список несколькими известными или стандартизованными алгоритмами (например, алгоритмом блочного шифрования Rijndael, алгоритмом хэширования SHA, являющимся стандартом хэширования США, и т.д.), не представленными на конкурс. Выбор победителей конкурса проводился из этого расширенного списка претендентов, состоящего из 17 криптографических алгоритмов. Причем, что интересно, в данном списке «финалистов» конкурса оказалось (с учетом добавлений) целых шесть хэш-функций, но ни одного потокового шифра, поскольку ни один из них не удовлетворил экспертов конкурса по криптостойкости.
Рассмотрим подробно алгоритмы, которые победили в наиболее интересной, на мой взгляд, категории блочных шифров, а именно следующие:

1.                       MISTY1 для шифрования 64-битных блоков,

2.                       AES (т.е. Rijndael) и Camellia (128 бит),

3.                       SHACAL-2 (256 бит).

2.4. MISTY1

Алгоритм MISTY1 был разработан в 1996 году японской корпорацией Mitsubishi Electric.
Структурная схема алгоритма представлена на рис. 1.

Рисунок 1.

Как видно из схемы, данный алгоритм является сетью Фейстеля (т.е. разбивает входной поток на два субблока, результат обработки одного из которых накладывается на другой субблок, затем субблоки меняются местами, см. рис. 2), причем, обработка субблоков в алгоритме различается для четных и нечетных раундов. Количество раундов алгоритма не ограничено, однако, рекомендовано выполнять 8 раундов преобразований.

Рисунок 2.

Помимо значения обрабатываемого субблока, операции FL и FO (см. рис. 1) используют в качестве параметра и значение определенного подключа, вычисляемое на этапе расширения 128-битного ключа шифрования данного алгоритма. Операция FL выполняет несложные преобразования входных данных с участием ключа, тогда как операция FO является, фактически, еще одной 4-раундовой сетью Фейстеля: в ней обрабатываемый 32-битный субблок разбивается еще на две части по 16 бит, одна из которых складывается с фрагментом ключа, после чего к ней применяется операция FI, результат накладывается на другую часть, после чего 16-битные части меняются местами. В свою очередь, операция FI является еще более интересной (см. рис. 3): 16-битное входное значение после разбиения на 7- и 9-битные блоки «прогоняется» через таблицы замен S7 (для 7 бит) и S9 (для 9 бит), которые обеспечивают, таким образом, перемешивающую часть криптопреобразований.

Рисунок 3.

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

2.5. Camellia

Шифр Camellia был также разработан компанией Mitsubishi Electric в сотрудничестве с еще одной известной японской корпорацией – Nippon Telegraph and Telephone (NTT). Для последней это был не первый опыт участия в международных криптоконкурсах – на конкурс AES корпорация NTT выдвигала алгоритм E2, который не прошел в финал конкурса.
Именно от E2 унаследовал алгоритм Camellia большую часть выполняемых операций. Camellia представляет собой сеть Фейстеля, в каждом раунде которой выполняется основное преобразование, показанное на рис. 4. В зависимости от длины ключа (алгоритм допускает использование 128-, 192- и 256-битных ключей) выполняется 18 или 24 раундов, причем после каждого шестого раунда, исключая последний, выполняется преобразование FL, практически не измененное по сравнению с аналогичной операцией алгоритма MISTY1.

Рисунок  4.

Как видно на рис. 4, содержимое 64-битного субблока обрабатывается побайтно применением следующих операций:

1.                       сложение по модулю 2 с соответствующим байтом ключа раунда;

2.                       табличная замена (с помощью четырех таблиц s1 … s4);

3.                       сложение по модулю два с конкретными байтами субблока;

4.                       байтовая перестановка.

Алгоритм Camillia был признан алгоритмом без уязвимостей, причем, достаточно быстрым и не требовательным к ресурсам.

2.6. SHACAL-2

Алгоритм SHACAL-2 был представлен на конкурс французской компанией Gemplus, которая является широко известным производителем смарт-карт и оборудования для работы с ними.
SHACAL-2 шифрует блоками по 256 бит, используя 512-битный ключ шифрования. Данный алгоритм можно описать следующим образом:

1.                        256-битный блок открытого текста разбивается на 8 частей и записывается в 8 32-битных регистров, обозначаемых латинскими буквами A … H.

2.                        Выполняется 64 раунда преобразований над регистрами A … H согласно рис. 5, где:

Рисунок 5.

3.                        Шифртекстом является конкатенация восьми 32-битных фрагментов, находящихся в регистрах A … H.