часть5
Q: А спецификация на Е2 - 128-битный блочный шифр можно о нём немного поподробнее?

A: 1. Описание алгоритма

1.1 Соглашения и обозначения

В данном документе используются следующие обозначения:

1. Обозначим Z - множество всех целых чисел.
2. Обозначим буквами A, B, C множества. Положим А*В:={(a, b)|a?A, b?B} - Декартово произведение множеств А и В. Элемент произведения А*В*С определим следующим образом: (а, b, c)=(a, (b, c))=((a, b), c). Более того, положим , для
3. У элемента ( , ,…, ) из множества будем считать самым левым элементом и - самым правым.
4. Пусть K -поле и n>1. Обозначим через K - n-мерное векторное пространство над полем K . Для двух векторов ( , ,…, ) и ( , ,…, ) из K справедливы следующие соотношения:
= ( + , + ,…, + )
( , ,…, )
5. Если K = ={0,1}, то операция ИСКЛЮЧАЮЩЕЕ-ИЛИ, , рассматривается как аддитивная операция. Операция называется просто XOR-операцией.
6. Вектор-строка ( , ,…, ) соответствует вектор-столбцу .
7. Пусть B -это векторное пространство 8-битовых элементов, т.е. B= .
8. Пусть W -это векторное пространство 32-битовых элементов, т.е. W=B .
9. Пусть H -это векторное пространство 32-битовых элементов, т.е. H=B .
10. Элемент поля определяется как многочлен p(X) из , чья степень меньше 8, при этом изоморфно и r(X)=X +X +X +X+1, являющийся неприводимым многочленом в . Таким образом, полное множество представителей есть .
11. Элемент p(X) из множества представленный как эквивалентен B.
12. Элемент B, где , сопоставим элементу
Z Z / Z,
где ( ) соответствует в канонической форме записи, т.е. -старший бит (самый левый) и - младший (самый левый) бит.

13. Элемент из W, где B, сопоставим элементу
Z Z / Z ,
где ( ) соответствует . Соответствие между и будет установлено в главе 12.


1.2. Схема алгоритма

Пусть:
М – это открытый текст ( H ),
K – секретный ключ ( H , H , H ), и
C – шифртекст ( H ).

Алгоритм шифрования E2 определяется как:
C = E (M, K)
M = D (C, K),
Где E – шифрующая функция в E2, описанная в пункте 1.3, и D – функция расшифрования в E2, описанная далее в пункте 1.4. Справедливы следующие уравнения:
M = D (E (M, K), K)
C = E (D (C, K), K)


Шифрование

Часть алгоритма, в которой осуществляется перемешивание информации, состоит из начальной перестановки IT, 12-и петель Фестеля с F-функцией, и конечной перестановки FT. До начала процесса шифрования согласно ключевому расписанию из секретного ключа K вырабатываются 16 подключей { } ( B ).
Первоначально вычисляется

где M – открытый текст. Далее, разбивается на две части и равной длины, т.е. , где H и H. Затем последовательно для от 1 до 12 вычисляются


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

Все данные приведены в шестнадцатеричном виде.

a) Длина ключа равна 128 бит
K = 00000000000000000000000000000000
M = 00000000000000000000000000000000
C = c2883490b9d9d5e5a03f216edb815fff

b) Длина ключа равна 192 бит
K = 000000000000000000000000000000000000000000000000
M = 00000000000000000000000000000000
C = 882f80269d3c146d6ebb9addc4715b4c

c) Длина ключа равна 256 бита
K = 00000000000000000000000000000000000000000000000000 00000000000000
M = 00000000000000000000000000000000
C = 5002cb8cd878f26fbab9f52e6c96501e

Q: можно повторить перечень наиболее распространенных асимметричных криптоалгоритмов?

A: Прежде всего назовем наиболее распространенные (наиболее часто обсуждаемые) алгоритмы асимметричной криптографии:
1. Схема Диффи-Хеллмана в мультипликативной группе конечного поля (статья 1976 года) и в группе точек эллиптической кривой над конечным полем Нила Коблица[9].
2. Схема открытого шифрования RSA и построенные на ее основе схемы подписи и аутентификации[10].
3. Схемы типа Фиата-Шамира [11].
4. Семейство схем подписи типа Эль-Гамаля [12].
5. Схемы на основе задачи "о рюкзаке" [13].
6. Теоретико-кодовые конструкции МакЭлиса [14].
Названные схемы достаточно известны, поэтому формально описывать их не будем (тем более что их описанию посвящены отдельные публикации). Со всемиперечисленными схемами связан ряд теоретических проблем. Ниже приведем некоторые из них.

Теоретико-сложностные проблемы:

1. Проблема эквивалентности задачи Диффи-Хеллмана и задачи логарифмирования в соответствующей группе.
Практически очевидно, что задача Диффи-Хеллмана не сложнее задачи логарифмирования (если мы умеем логарифмировать, то система открытогораспределения ключей Диффи-Хеллмана нестойкая). Хотя большинство исследователей склоняется к мнению, что эти задачи эквивалентны, вопрос о том, верно лиобратное, на сегодняшний день открыт. Эквивалентность, при некоторых дополнительных условиях, доказали Маурэр [15] и ден Бур [16]. Из отечественныхисследовател ей сильный результат по данной проблематике получен М. А. Черепневым, которому удалось построить субэкспоненциальный алгоритм сведениязадачи дискретного логарифмирования в простом конечном поле к задаче Диффи-Хеллмана. Наиболее же близки к решению проблемы швейцарские ученые [17].
2. Проблема эквивалентности задачи компрометации схемы Эль-Гамаля и задачи логарифмирования.
3. Проблема эквивалентности задачи вскрытия системы RSA и задачи факторизации целых чисел (под секретным ключом понимается экспонента e).
Задача определения секретного ключа здесь эквивалентна факторизации, тем не менее, вопрос об эквивалентности бесключевого чтения и факторизации открыт. Вто же время известны частные случаи, когда задача решается легко (случай, так называемых, "слабых ключей").
4. Проблема построения стойких (доказуемо) криптографических протоколов в предположении о существовании тех или иных криптографических примитивов.
Основная масса публикаций по теоретико-сложностным проблемам криптографии относится именно к этой тематике.

Q: можно более подробно о алгоритме DSA?

A: . Общее описание алгоритма
Алгоритм DSA основывается на двух вычислительный задачах, связанных с дискретным логарифмированием. Одной задачей является сложность вычисления логарифма в Z*p, другая задача - сложность логарифмирования в циклической подгруппе порядка q. Алгоритм является частным случаем цифровой подписи Эль-Гамаля (ElGamal) и был представлен как стандарт FIPS PUB 186-94 (DSS).
1.2 Генерация ключей DSA


1. Выбирается простое число q, такое, что 2159<q<2160.
2. Выбирается t, т.ч. 0<=t<=8 и выбирается простое число p так, что 2511+64t<p<2512+64t, причем q должно делить (p-1).
3. Находится производящий элемент a для циклической группы Z*p порядка q (для этого выбирается g ОZ*p и вычисляется a =g(p-1)/q mod p, Если a ?= 1, то пр. элемент найден).
4. Выбирается случайное целое a, т. ч. 1<=a<=q-1.
5. Вычисляется y=a a mod p.

Секретным ключом является a, открытым ключом - (p,q,a ,y)
1.2 Подпись сообщения
Имеется сообщение m. Подпись сообщения секретным ключом выглядит следующим образом.

1. Выбирается случайное секретное число k, 0<k<q (разовый секретный ключ).
2. Вычисляется r=(a k mod p) mod q.
3. Вычисляется k-1 mod q.
4. Вычисляется s=k-1{h(m)+ar} mod q, где h(m)-значение хэш-функции от сообщения m.

Подписью для сообщения m является пара (r,s).
1.3 Проверка подписи
Имеется открытый ключ (p,q,a ,y), сообщение m, подпись сообщения (r,s).

1. Проверить, что 0<r<q и 0<s<q. Если это не так, отвергнуть подпись.
2. Вычислить w=s-1 mod q и h(m).
3. Вычислить u1=wh(m) mod q и u2=rw mod q.
4. Вычислить v=(a u1yu2 mod p) mod q.
5. Подпись верна, только если v=r.

1.4 Док-во корректности подписи
Если (r,s) является корректной подписью для сообщения m, тогда должно выполняться h(m)=-ar+ks (mod q). Умножим обе части равенства на w и получим, что wh(m)+arw=k (mod q). А это есть u1+au2=k (mod q). Т.е. получаем, что (a u1a au2 mod p) mod q=(a k mod p) mod q. Или (au1yu2 mod p) mod q=(a k mod p) mod q. Это есть v=r, что и требовалось доказать.
2. Практические рекомендации
В данном алгоритме предлагается использовать простое p размером от 512 до 1024 бит. Размер в 512 бит обеспечивает минимальную защищенность. Рекомендуемый размер - не менее 768 бит. Согласно FIPS 186, алгоритм не допускает простых чисел больше 1024 бит.

Совершенно не обязательно существование уникальных p и q для каждого пользователя алгоритма. FIPS допускает использование p,q и a в качестве системных параметров для группы пользователей. Однако для повышения безопасности работы лучше использовать уникальные значения.