Размещено на http://www.allbest.ru/

Современная прикладная криптография

Содержание

Введение

Раздел 1. Введение в криптологию(криптографию)

1.1 Первые понятия криптологии. Этапы развития

1.2 Некоторые поясняющие примеры из истории

1.3 Теория информации в криптологии

1.4 Теория сложности и криптология

1.5 Некоторые необходимые сведения из теории чисел

Раздел 2. Основные понятия и методы современной криптологии

2.1 Криптографические протоколы

2.2 Однонаправленная функция

2.3 Открытое распределение ключей. Схема Диффи-Хеллмана

2.4 Односторонняя функция с секретом

2.5 Открытое шифрование, криптосистема с открытым ключом

2.6 Криптосистема RSA

2.7 Цифровая подпись

2.8 Схема цифровой подписи Эль Гамаля

2 9 Управление ключами

2.10 Криптографические хэш-функции. Аутентификация

Раздел 3. Стандартизация криптографических методов

3.1 Организации, разрабатывающие стандарты по криптологии

3.2 Первые варианты стандартов цифровой подписи США и России

3.3 Развитие американских стандартов хэш-функции

3.4 Российский стандарт хэш-функции ГОСТ Р 34.11-94

3.5 Использование эллиптических кривых в криптологии. Новые стандарты цифровой подписи

Литература

Введение

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

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

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

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

Основная масса литературы по данным вопросам опубликована на английском языке, для многих еще нет общепринятых отечественных эквивалентов, к некоторым трудно найти подходящий удобный перевод.

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

криптология информация протокол эллиптический

Раздел 1. Введение в криптологию

1.1 Первые понятия криптологии. Этапы развития

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

Криптологию принято делить на две части: криптографию и криптоанализ, в соответствии с аспектами синтеза и анализа. Криптография - наука о методах обеспечения безопасности, то есть более занимается вопросами синтеза систем. Криптоанализ - наука о методах атак на безопасность данных. У нас в стране имеет место и другая терминология, когда термин "криптография" использовался для названия всей науки, а криптоанализ назывался дешифрованием.

Цели криптографии менялись на протяжении всей ее истории. Сначала она служила больше для обеспечения секретности, чтобы препятствовать несанкционированному раскрытию информации, передаваемой по открытой связи. С началом информационного века обнаружилась потребность применения криптографии и в частном секторе. Количество конфиденциальной информации огромно - истории болезней, юридические, финансовые документы и т.д. Последние достижения криптографии позволили использовать ее не только для защиты информации от несанкционированного раскрытия, но и для обеспечения подлинности, целостности информации.

Для сохранения тайны сообщения помимо криптографических способов применяются физическая защита и стеганография. Стеганография (от греческих слов stege - "крыша" и grapho -"пишу") занимается методами сокрытия самого факта передачи сообщения. Например, можно писать скрытое сообщение (на свободном месте фактического сообщения) молоком, специальными чернилами и т.п. К методам стеганографии можно отнести шумоподобные методы радиопередачи. В настоящее время получила развитие компьютерная стеганография, но это отдельная наука.

Как показала практика, наиболее эффективная защита информации обеспечивается на основе криптографических способов и, как правило, в сочетании с другими способами.

Исходное сообщение, которое должен защищать криптограф, называется открытым текстом.

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

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

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

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

Можно выделить следующие периоды развития криптологии. Первый период - эра донаучной криптологии, являвшейся ремеслом, уделом узкого круга искусных умельцев. Началом второго периода можно считать 1949 год, когда появилась работа К.Шеннона "Теория связи в секретных системах", в которой проведено фундаментальное научное исследование шифров и важнейших вопросов их стойкости. Благодаря этому труду, криптология оформилась как прикладная математическая наука. И, наконец, начало третьему периоду было положено появлением в 1976 г., работы У. Диффи, М. Хеллмана "Новые направления в криптографии", где показано, что секретная связь возможна без предварительной передачи секретного ключа. Так началось и продолжается до настоящего времени бурное развитие наряду с обычной классической криптографией и криптографии с открытым ключом.

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

1.2 Некоторые поясняющие примеры из истории

Приводимые далее примеры тайнописи служат для пояснения введенных понятий и для введения новых. Большинство из них можно найти в работах [3.75.100]. Несмотря на древность примеров, многие методы, примененные в далекие времена, используются до сих пор (например, перешифрование, рандомизация, …).

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

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

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

56 г. н.э. Во время войны с галлами Ю.Цезарь использует другую разновидность шифра - шифр замены. Под алфавитом открытого текста писался тот же алфавит со сдвигом (у Цезаря на три позиции) по циклу. При шифровании буквы открытого текста из верхнего алфавита заменялись на буквы нижнего алфавита. Хотя этот шифр был известен до Ю.Цезаря, тем не менее, шифр был назван его именем.

Другим более сложным шифром замены является греческий шифр - ” квадрат Полибия ”. Алфавит записывается в виде квадратной таблицы 5х5. При шифровании буквы открытого текста заменялись на пару чисел - номера столбца и строки этой буквы в таблице. При произвольном расписывании алфавита по таблице и шифровании такой таблицей короткого сообщения, этот шифр является стойким даже по современным понятиям. Идея была реализована в более сложных шифрах, применявшихся во время первой мировой войны.

	1	2	3	4	5
1	A	B	C	D	T
2	F	G	H	I,J	K
3	L	M	N	O	P
4	Q	R	S	T	U
5	V	W	X	Y	Z

Квадрат Полибия для английского языка.

Крах Римской империи в V в. н.э. сопровождался закатом искусства и наук, в том числе и криптографии. Церковь в те времена преследовала тайнопись, которую она считала чернокнижием и колдовством. Сокрытие мыслей за шифрами не позволяло церкви контролировать эти мысли.

Р.Бэкон (1214-1294) - францисканский монах и философ - описал семь систем секретного письма. Большинство шифров в те времена применялись для закрытия научных записей.

Середина XV в. И. Гутенберг изобрел книгопечатание. Это привело к росту грамотности и увеличению число людей, которые могли вести переписку. Развиваются межгосударственные отношения, тайнопись становится крайне необходимой.

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

Интересен факт, что король Франции Франциск I в 1546 году издал указ, запрещающий подданным использование шифров. Хотя шифры того времени были исключительно простыми, они считались нераскрываемыми. В настоящее время в разных странах существуют ограничения на использование шифров.

Франсуа Виет (1540-1630) - французский математик. Всем известна со школьной скамьи теорема его имени. Он же был искусным дешифровальщиком или криптоаналитиком, находясь при дворе короля Генриха IV.

Иоганн Тритемий (1462-1516). Монах-бенедиктинец, живший в Германии. Написал один из первых учебников по криптографии. Предложил оригинальный шифр многозначной замены под названием "Ave Maria". Каждая буква открытого текста имела не одну замену, а несколько, по выбору шифровальщика. Причем буквы заменялись буквами или словами так, что получался некоторый псевдооткрытый текст, тем самым скрывался сам факт передачи секретного сообщения. То есть применялась стеганография вместе с криптографической защитой. Разновидность шифра многозначной замены применяется до сих пор.

Джироламо Кардано - итальянский математик, механик, врач, изобрел систему шифрования, так называемую решетку Кардано. В куске картона с размеченной решеткой определенным образцом прорезались отверстия, нумерованные в произвольном порядке. Чтобы получить шифртекст, нужно положить этот кусок картона на бумагу и начинать вписывать в отверстия буквы в выбранном порядке. После снятия картона промежутки бессмысленного набора букв дописывались до псевдоосмысловых фраз, так что можно было скрыть факт передачи секретного сообщения. Скрытие легко достигается, если промежутки эти большие, и если слова открытого текста имеют небольшую длину. Неудобство шифра в том, что кусок картона надо хранить в тайне.

XVI в. Шифры замены получили развитие в работах итальянца Джованни Батиста Порты и француза Блеза де Вижинера. Рассмотрим систему шифрования последнего подробно в виду ее важности для дальнейшего изложения.

Система Вижинера требует для зашифрования ключ - в виде ключевого слова, которое подписывается сверху над открытым текстом периодически. Каждая буква открытого текста заменяется на букву, стоящую в алфавите далее ее (по циклу) на число позиций, определяемое номером в алфавите стоящей сверху буквы ключевого слова (минус 1). Для сравнения заметим, что в "шифре Цезаря" это ключевое слово состоит из одной буквы, стоящей на третьем месте в алфавите. Для удобства пользования изготовлялась легко запоминающаяся таблица.

Буквы ключевого слова

		A	B	C	D	. . . . .	X	Y	Z
A		A	B	C	D	. . . . .	X	Y	Z
B		B	C	D	E	. . . . .	Y	Z	A
C		C	D	E	G	. . . . .	Z	A	B
X		X	Y	Z	A	. . . . .	U	V	W
Y		Y	Z	A	B	. . . . .	V	W	X
Z		Z	A	B	C	. . . . .	W	X	Y

Буквы открытого текста A, B, C, …, Z.

Таблица Вижинера относительно английского алфавита.

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

XVII в. Кардинал Ришелье (министр при короле Франции Людовике XIII) создал первую в мире шифрслужбу. Эту службу возглавлял Антуан Россиньоль (1590-1673).

Лорд Френсис Бэкон (1562-1626) был первым, кто обозначил буквы 5-значным двоичным кодом : а = 00001. B = 00010, .. и т.д. Правда, Бэкон никак не обрабатывал этот код, поэтому такое закрытие было совсем нестойким. Тут уместно вспомнить коды Морзе, Бодо, международный телеграфный код № 2, код ascii, также представляющие собой простую замену.

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

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

К.Гаусс (1777-185S) - великий математик, тоже не обошел своим вниманием криптологию. Он создал шифр, который ошибочно считал нераскрываемым. При его создании использовался интересный прием - рандомизация (random - случайный) открытого текста. Открытый текст можно преобразовать в другой текст, содержащий символы большего алфавита, путем замены часто встречающихся букв случайными символами из соответствующих определенных им групп. В получающемся тексте все символы большого алфавита встречаются с примерно одинаковой частотой. Зашифрование такого текста противостоит методам дешифрования на основе анализа частот отдельных символов. После расшифрования законный получатель легко снимает рандомизацию. Такие шифры называют "шифрами с многократной подстановкой" или "равночастотными шифрами".

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

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

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

1. Методы дешифрования на основе знания только шифртекстов.

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

3. Методы дешифрования по выбираемым открытым и соответствующим шифртекстам - методы тестирования (chosen plaintext attack).

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

4. Для полноты картины укажем и на методы, появляющиеся на третьем этапе развития криптологии - криптологии с открытым ключом, о котором уже говорилось в связи с работой У.Диффи и М.Хеллмана. Это методы дешифрования по выбранным шифртекстам и соответствующим открытым текстам (chosen cipher text attack).

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

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

Вместе с тем, имеются примеры и другого рода. В 1917 году инженер американской компании ат&т Г.С. Вернам опубликовал замечательную систему побитового шифрования открытого текста, представленного в коде Бодо, когда каждый бит преобразуется с использованием соответствующего ему бита ключа по следующему алгоритму:

, , , .

Это так называемое сложение по модулю два ("XOR"). Расшифрование осуществляется той же операцией, что очень удобно для реализации. Вернам предлагал использовать ключ только один раз (one - time pad), несмотря на трудности передачи по секретному каналу этого ключа, длина которого равна длине шифруемого открытого текста. Однако это дает, как показал впоследствии К.Шеннон, действительно нераскрываемый шифр. Сам Вернам, хотя и считал, что его шифр нераскрываем, не представил доказательств этого. Казалось бы, что после создания такого шифра, все проблемы для криптографов решены. Но это не так. Как показала дальнейшая практика, использование шифра Вернама требует решения проблем выработки длинных двоичных последовательностей ключей, контроля за их качеством, проблем хранения, уничтожения и транспортировки. На каждом из этапов существования ключей (жизненного цикла) есть угроза их безопасности. Все это делает систему Вернама непрактичной, дорогостоящей, и она применяется в исключительных случаях.

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

При шифровании на один из контактов первого диска подается напряжение, которое последовательно передается на связанный контакт последнего диска, соответствующий некоторой букве шифртекста. Если бы все диски были неподвижными, то эта система представляла бы собой простую замену, эквивалентную замене, реализуемой одним диском. При большом количестве дисков (5-10) и правильно выбранном законе псевдослучайного движения дисков система обеспечивала весьма высокую стойкость.

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

Принцип работы дисков был почти одновременно открыт четырьмя изобретателями из разных стран. Это американец Эдвард Хеберн (1918 г.), голландец Хуго Кох (1919), швед Арвид Дамм (1919), немец Артур Шербиус (1927). Последний сконструировал известную немецкую дисковую машину "Энигма" ("Загадка"). Из четырех изобретателей только А.Дамму удалось добиться коммерческого успеха. Его фирма - "Криптография", под управлением Бориса Хагелина, выпустила весьма компактную и простую в работе шифрмашину. известную под названием "Хагелин". Шифрмашины этой фирмы и их модификации были изготовлены в огромном количестве. Так, только США в период второй мировой войны заказали несколько тысяч таких машин под наименованием "Конвертер М-209". Далее после войны Б. Хагелин перенес штабквартиру фирмы в Швейцарию, где она успешно функционирует до сих пор в г Цуг, правда под другим названием - "Сrypto ag". История криптологии исключительно интересна. Она насыщена многочисленными фактами противоборства криптографов и криптоаналитиков (дешифровальщиков). Причем, чем дальше от наших дней рассматриваемый отрезок времени, тем больше этих фактов опубликовано и известно. Такова деликатная природа этой науки. Для более детального ознакомления с историей криптологии можно порекомендовать книги Д.Кана [3] , Г Фролова [75], или [].

В настоящее время вместо понятия шифра часто используется понятие криптографической системы с секретным ключом (secret key cryptosystem), [24], которая задается следующими пятью компонентами:

пространством открытых текстов, м;

пространством шифрованных текстов, с,

пространством ключей, к;

множеством преобразований зашифрования {е , } ;

е : м с, где;

множеством преобразований расшифрования {, };

D: с м, где

Преобразования и для всех и любого открытого текста должны удовлетворять следующему условию:

Согласно основному правилу Керкхоффса, множества

преобразований {} и {} могут быть известны не только криптографу, но и криптоаналитику. Секретность же сообщения обеспечивается сокрытием того, какое именно преобразование из известного множества преобразований использовалось для зашифрования. Заметим также, что знание ключа K дает возможность легко указать соответствующие ему преобразования и , однако обратное не всегда верно.

Криптосистемы с секретным ключом подразделяются на два вида:

блочные (block) и поточные (stream) криптосистемы.

Блочная криптосистема (блочный шифр) разбивает открытый текст M на последовательные блоки .... и зашифровывает каждый блок с помощью одного и того же обратимого преобразования , выбранного в соответствии с ключом k

Примерами блочных систем являются: des (режим электронной кодовой книги - есв), ГОСТ 28147-89 (режим простой замены [20,76]. Размер блоков открытого и шифрованного текста в этих криптосистемах равен 64 битам. В американском стандарте шифрования AES размер блока равен 128. В настоящее время такой размер блоков более актуален.

ГОСТ 28147-89

Рассмотрим подробнее отечественный стандарт ГОСТ 28147-89, используемый с 1989 года до настоящего времени.

Всего у стандарта четыре режима использования:

1. Режим простой замены;

2. Режим гаммирования;

3. Режим гаммирования с обратной связью;

4. Режим имитовставки.

Начнем изложение с режима простой замены. Отечественный ГОСТ менее известен, чем американский DES, но они имеют много общего, а именно принцип построения в соответствии со схемой Фейстеля. Описываемый режим работы соответствует режиму электронной кодовой книги есв (Electronic Codebook) для алгоритма des по стандарту fips pub 81 (I980).

Введем необходимые понятия и обозначения.

Ключом (сеансовым, разовым) является 256-битная последовательность W = [****], которая разбивается на восемь 32-битных блока следующим образом:

,

,

Эти блоки используются в процедуре размножения ключа (key shedule) для получения тридцати двух 32-битных блоков по правилу

=.

Долговременным ключом К является набор из восьми таблиц замены 4-х битных двоичных векторов, которые разбиваются на восемь последовательно идущих 4-битных векторов, каждый из которых преобразуется в 4-битный вектор по соответствующей таблице замены из . Наконец, через T обозначим преобразование циклического сдвига на 11 разрядов 32-битных двоичных векторов в сторону старшего разряда.

Каждый 64-битный блок открытого текста ( i = 1,2,…) разбивается на две равные части

которые определяют начальные векторы и рекурренты второго порядка вида

, j = 0,1

следующим образом

=,

=,

Через "®" и "+" обозначены соответственно операции побитового сложения двоичных векторов по модулю два и сложения целых чисел по модулю 2³². Здесь и далее не различаем целые числа и их двоичное представление, все определяется операциями, которые к ним применяются.

В приведенных обозначениях 64-битный блок шифртекста получается из значений

и ,

описанной выше рекурренты, следующей перестановкой бит

.

Расшифрование производится в обратном порядке.

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

Режим сцепления блоков шифра (Cipher Block Chaining - CBC). Этот режим использования блочного шифра, как показал Фейстель (H. Feistel), предпочтителен для шифрования открытых текстов и является более устойчивым к атакам криптоаналитиков.

Если обозначить через (), преобразование зашифрования (расшифрования) , то получение блоков шифрованного текста , .... из блоков , открытого текста описывается соотношением

, i=1,2,…

Начальное значение является несекретным и передается вместе с шифртекстом.

Соответственно процесс расшифрования определяется соотношением

, i=1,2,

Иногда используются подобные CBC режимы, например, режим рсвс (Propagating Cipher Block Chaning) и режим РВС (Plaintext Block Chaning),соотношения зашифрования и расшифрования, для которых имеют соответственно вид

Например, режим рсвс используется в системе Kerberos [48].

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

В отечественной литературе (см. например, ГОСТ 28147-89) такие системы называются системами гаммирования, а последовательность ,,… называется гаммой.

Примерами поточных криптосистем являются:

- система Вернама (где()=() XOR ,, ),

- ГОСТ 28147-89 (режимы гаммирования и гаммирования с обратной связью),

- des (режимы CFB и OFB).

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

Алгоритм, который вырабатывает ключевой поток (гамму), должен быть либо детерминистическим, чтобы воспроизвести одинаковые потоки на приемном и передающем концах связи, либо случайным, что часто непрактично в силу необходимости передачи и хранения ключевой информации большого объема. Этот алгоритм называют генератором ключевого потока (running key generator-RKG, key stream generator). Если генератор детерминистический, то он должен зависеть от секретного ключа.

Для описания работы генераторов удобно использовать язык теории автоматов [40]. Если обозначить через состояние генератора в 1-тый момент времени, то работу синхронной поточной системы можно описать двумя соотношениями

,

где функции F и f называются соответственно функцией переходов и функцией выхода. Начальное состояние может быть функцией от ключа k.

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

Режим обратной связи по входу (Output Feedback - OFB).

Этот режим характеризует независимость функции выхода I от ключа. Поэтому его также называют режимом с внутренней обратной связью (Internal Feedback).

Если обозначить через - преобразование зашифрования блочного шифра на ключе k, то уравнение переходов в этом режиме принимает вид, а в качестве знаков ключевого потока могут использоваться какие-нибудь (чаще всего старшие) биты вектора состояния (Режим ofb для des).

Иногда рассматривают вариант режима ofb, где ключ k определяет только начальное состояние генератора ключевого потока и = , k = f.

Счетчиковый метод (Counter method) .

Метод предложен Диффи и Хеллманом [14]. В общем случае работа генератора ключей описывается соотношениями

Функция переходов F не зависит от ключа, но преобразование F выбирается так, что гарантирует перебор всех или почти всех возможных состояний генератора при изменении времени i ⁼ 0,1,... В качестве f часто используются преобразования регистров сдвига с линейно обратной связью, вырабатывающие последовательности максимального периода [23], или просто счетчики, состояния которых меняется прибавлением единицы по некоторому модулю (периоду состояний счетчика). В качестве функции выхода используется преобразование зашифрования блочного шифра.

Примером счетчикового метода является режим гаммирования в ГОСТ 28147-89.

Достоинство счетчикового метода в том, что можно получить произвольный знак ключевой последовательности без получения предыдущих значений этой последовательности (в отличие от режима OFB, например).

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

=

= , i = 1,2

Заметим, что в этих системах вход (знаки шифртекста) и выход (ключевой поток) могут быть известны криптоаналитику как при атаке с известным открытым текстом (known plaintext attack).

Примером таких поточных систем является режим гаммирования с обратной связью в ГОСТ 28147-89.

Режим обратной связи по шифртексту (Cipher Feedback - СFВ).

Приведенные выше соотношения при использовании блочного шифра и проходного регистра сдвига принимают следующий вид

=

=

где n - размер преобразованного блока и v номер какой-нибудь (чаще младшей) координаты выходного блока [= ]. (Так делается в режиме CFB стандарта des).

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

Блочные и поточные криптосистемы имеют ряд достоинств и недостатков друг перед другом, некоторые из которых приведены в работах [12,85].

Описание тройного DES алгоритма (3DES, Triple DES, TDEA)

В американских стандартах различают понятия алгоритма и стандарта. На слуху все же больше звучит DES, чем DEA. В настоящее время и до принятия стандарта AES использовался тройной DES - 3DES. Обычно производители средств защиты указывают на реализацию 3DES, не уточняя деталей, которые весьма существенны. Далее описание дается по FIPS PUB 46-3, Reaffirmed, 1999 October 25.

Пусть EK(I) и DK(I) обозначают соответственно преобразование зашифрования и расшифрования блока I алгоритмом DES на ключе K . Преобразование зашифрования/расшифрования по алгоритму TDEA (как определено в ANSI X9.52) является композицией из преобразований зашифрования/расшифрования по алгоритму DES следующим образом.

1. преобразование зашифрования по алгоритму TDEA: преобразование 64-битового блока I в 64-битовый блок O следующим образом:

O = EK3(DK2(EK1(I))).

2. преобразование расшифрования по алгоритму TDEA: преобразование 64-битового блока I в 64-битовый блок O следующим образом :

O = DK1(EK2(DK3(I)))

Стандарт определяет следующие возможности для выбора ключей (K1, K2, K3)

1. Выбор 1: K1, K2 и K3 являются независимыми ключами;

2. Выбор 2: K1 и K2 - независимые ключи и K3 = K1;

3. Выбор 3: K1 = K2 = K3.

Когда используется Выбор ключей 3 (K1 = K2 = K3), то режимы шифрования для TECB, TCBC, TCFB и TOFB совпадают с режимами ECB, CBC, CFB, OFB обычного DES соответственно.

От Rijndael до AES. Новый американский стандарт шифрования AES

В конце ноября 2001 г. NIST принял новый стандарт симметричного шифрования Advanced Encryption Standard (AES) (FIPS PUB 197). Этим завершилась процедура выбора нового перспективного стандарта шифрования на смену устаревшего стандарта DES (DES-1997), начатая в сентябре 1997 г. после опубликования требований к участникам конкурса.

Алгоритм стандарта DES считается многими устаревшим по следующим причинам:

· малая длина ключа в 56 бит,

· неудобство реализации на современных процессорах,

· относительно малое быстродействие.

· относительно малый размер блока в 64 бита.

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

Минимальные требованиями к новому алгоритму шифрования были следующие:

· алгоритм должен реализовывать криптографию с симметричным(секретным) ключом,

· алгоритм должен быть блочным шифром,

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

Кроме того, предполагалось, что:

· алгоритм должен быть открыто опубликован;

· алгоритм должен быть удобен как для аппаратной, так и для программной реализации;

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

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

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

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

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

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

Всего к конкурсу AES были допущены 15 алгоритмов, разработанных криптографами из 12 стран - Австралии, Бельгии, Великобритании, Германии, Израиля, Канады, Коста-Рики, Норвегии, США, Франции, Южной Кореи и Японии.

В финал конкурса вышли следующие алгоритмы:

· MARS (США),

· RC6 (США),

· RIJNDAEL (Бельгия),

· SERPENT (Великобритания, Израиль, Норвегия),

· TWOFISH (США).

Победителем конкурса стал криптоалгоритм RIJNDAEL.

Материалы конкурса AES, в том числе документацию по алгоритмам - финалистам конкурса, можно найти на странице http://www.nist.gov/aes/ .

Важно заметить, что алгоритм RIJNDAEL допускает различные размеры пар блока-ключа в битах, но в стандарте FIPS PUB 197 приняты только следующие: 128-128, 192-128, 256-128. Далее будет в основном излагаться описание в терминах RIJNDAEL.

Для понимания работы алгоритма RIJNDAEL напомним некоторые математические основы. В RIJNDAEL операции выполняются над байтами, которые рассматриваются как элементы поля Элементами являются двоичные многочлены степени N < 8, которые могут быть заданы строкой своих коэффициентов. Так, например, байту 01010111 (`57h' в шестнадцатеричной форме) соответствует многочлен

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

В алгоритме RIJNDAEL авторы вводят операцию . - это операция умножения элемента поля на x. Тогда умножение на можно осуществить путем n-кратного повторения операции , а умножение на произвольный элемент поля можно осуществить, складывая результаты операций .

Структура шифра

Общие сведения

RIJNDAEL - это итерационный блочный шифр, имеющий следующие варьируемые параметры: длина блоков, длина ключа. Длина ключа и длина блока могут быть равны независимо друг от друга 128, 192 или 256 битам.(В AES не так).

Промежуточные результаты преобразований, выполняемых в рамках алгоритма, называются состояниями. Состояние (рис.) можно представить в виде прямоугольного массива байтов. Этот массив имеет 4 строки, а число столбцов равно длине блока, деленной на 32.

Ключ шифрования также представлен в виде прямоугольного массива с четырьмя строками. Число столбцов равно длине ключа, деленной на 32.

рис. Пример представления состояния () и ключа шифрования ()

Входные данные для шифра обозначаются как байты состояния в порядке a₀₀, a₁₀, a₂₀, a₃₀, a₀₁, a₁₁, a₂₁, a₃₁, a₄₁ ... После завершения действия шифра выходные данные получаются из байтов состояния в том же порядке.

Число циклов зависит от значений и - числа 32-битных слов в информационном блоке и, соответственно, основном ключе алгоритма:

Зависимость числа циклов от числа столбцов в таблице состояний и длины ключа шифрования
	10	12	14
	12	12	14
	14	14	14

Цикловое преобразование

Любой цикл шифрования, кроме последнего, состоит из четырех различных преобразований. На псевдо-Си это выглядит следующим образом:

Round (State, RoundKey)

{

ByteSub(State); // замена байтов

ShiftRow(State); // сдвиг строк

MixColumn(State); // перемешивание столбцов

AddRoundKey(State, RoundKey); // добавление циклового ключа

}

Последний цикл шифрования немного отличается от остальных. Вот как он выглядит:

FinalRound(State, RoundKey)

{

ByteSub(State); // замена байтов

ShiftRow(State); // сдвиг строк

AddRoundKey(State, RoundKey); // добавление циклового ключа

}

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

Замена байтов (ByteSub).

Заметим, что в AES употребляются несколько видоизмененные названия для этого и других преобразований, что можно рассматривать как еще одно различие в описании (Именно, SubBytes, ShiftRows, MixColumns, …). Излагать будем как в описании Rijndael.

Преобразование ByteSub является S-блоком и представляет собой нелинейную замену байтов, выполняемую независимо для каждого байта состояния. Таблицы замены S-блока являются инвертируемыми и построены как композиция двух преобразований:

переход к обратному элементу относительно умножения в поле GF(2⁸), при этом нулевой элемент '00h' переходит сам в себя;

применение аффинного преобразования над 8-ми мерным двоичным вектором:



Применение описанного выше S-блока ко всем байтам состояния обозначено как ByteSub(State).

Операция обратная к ByteSub - это замена байтов с использованием инвертированной таблицы. Обратимость операции ByteSub следует из обратимости аффинного преобразования и наличия у каждого элемента поля обратного элемента.

Преобразование сдвига строк (ShiftRow)

Строки матрицы состояния (кроме нулевой строки) циклически сдвигаются на различное число байт. Строка 1 сдвигается на С1 байт, строка 2 - на С2 байт и строка 3 - на С3 байт. Значения сдвигов С1, С2 и С3 зависят от длины блока . Их величины приведены ниже в таблице.

Величина сдвига для разной длины блоков
	C1	C2	C3
4	1	2	3
6	1	2	3
8	1	3	4

Операция сдвига последних 3 строк состояния на определенную величину обозначена как ShiftRow (State).

Преобразование перемешивания столбцов (MixColumn)

В этом преобразовании столбцы состояния рассматриваются как многочлены над GF(2⁸) и умножаются по модулю на многочлен

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

Это может быть представлено в матричном виде следующим образом

Применение этой операции ко всем четырем столбцам состояния обозначено как

Для обращения операции MixColumn необходимо умножить столбец, к которому применялась эта операция, на многочлен обратный к по модулю , т.е. на многочлен ().

Добавление циклового ключа (AddRoundKey).

В данной операции цикловой ключ добавляется к матрице состояния посредством простого поразрядного XOR. Цикловой ключ вырабатывается из ключа шифрования посредством алгоритма выработки ключей (key schedule). Длина циклового ключа должна быть равна длине блокаПреобразование, состоящее в добавлении посредством XOR циклового ключа к матрице состояния (Ошибка! Источник ссылки не найден.), обозначено как AddRoundKey(State, RoundKey).

При добавлении ключа, цикловой ключ складывается посредством операции XOR с матрицей состояния. Эта операция, очевидным образом, обратима.

Алгоритм выработки ключей (Key Schedule)

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

· расширение ключа (Key Expansion)

· выбор циклового ключа (Round Key Selection).

Основные принципы алгоритма выглядят следующим образом:

· общее число бит цикловых ключей равно длине блока, умноженной на число циклов шифрования плюс 1 (например, для длины блока 128 бит и 10 циклов требуется 1408 бит циклового ключа);

· ключ шифрования расширяется в расширенный ключ (Expanded Key);

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

Расширение ключа (Key Expansion)

Расширенный ключ представляет собой линейный массив 4-байтовых слов и обозначен как .

Первые слов содержат ключ шифрования. Все остальные слова определяются рекурсивно из слов с меньшими индексами. Алгоритм выработки ключей зависит от величины Ниже приведена версия для меньшего или равного 6 и версия для большего 6.

...