Личностная криптография: рассказ об одной полезной уязвимости

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

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

1. Алиса проходит процедуру проверки в удостоверяющем центре(УЦ) и получает сертификат
2. Алиса посылает свой сертификат Бобу
3. Боб получает сертификат УЦ
4. С помощью полученных сертификатов Боб производит аутентификацию Алисы

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

Класс уязвимых эллиптических кривых

Эллиптическая криптография построена на предположении о сложности решения задачи дискретного логарифмирования над полем точек эллиптической кривой.
Основное преимущество «эллиптики» перед классической асимметричной криптографией заключается в гораздо меньших размерах ключей. Объясняется это тем, что для классической задачи дискретного логарифмирования существуют так называемые субэкспоненциальные алгоритмы решения, имеющие следующую вычислительную сложность . Поэтому для достижения стойкости порядка 2⁸⁰ необходимо чтобы число p имело размер в 1024 бит.
Для задачи дискретного логарифмирования над точками эллиптической кривой субэкспоненциальных алгоритмов найдено не было. Наиболее быстрые алгоритмы для данного типа задач имеют сложность . Это позволяет использовать числа размерами всего 160 бит для достижения того же самого порога стойкости в 2⁸⁰.

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

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

Спаривание Вейля

В 1983 году Менезес, Окамото и Ванстоун показали, что для суперсингулярных кривых существует эффективный способ отобразить пары точек кривой в невырожденный элемент конечного поля.
Изоморфизм использованный ими для этого называется спариванием Вейля. В соответствие двум точкам поля E(F_q^l) этот изоморфизм ставит элемент поля F_q^l. Другими словами, спаривание Вейля позволяет отразить множество точек эллиптической кривой в множество вычетов по модулю большого числа.

Пусть (G₁,+) — группа точек эллиптической кривой. И (G₂, *) — группа вычетов по модулю большого числа. И пусть две эти группы изоморфны относительно спаривания Вейля e_x. Спаривание Вейля обладает следующими свойствами:

1. Тождественность: для всех выполняется
2. Билинейность: для всех выполняется
3. Невырожденность: Для всех , таких что выполняется
4. Практическая эффективность: для всех P и R числа допускают эффективное вычисление

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

Именно спаривание Вейля делает суперсингулярные кривые бесполезными в алгоритмах ЭЦП. С другой стороны, оно же помогло реализовать идею Шамира.

Задача принятия решения Диффи-Хеллмана

Основополагающими проблемами современной асимметричной криптографии на эллиптических кривых являются:

• Задача дискретного логарифмирования. Даны две точки кривой P и Q. Необходимо найти число a, такое что Q=aP. На сложности этой задачи основан алгоритм цифровой подписи ECDSA.
• Вычислительная задача Диффи-Хеллмана. Даны три точки кривой: P, aP, bP. Необходимо вычислить элемент abP. Эта задача лежит в основе алгоритма распределения ключей ECDH.

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

Задача принятия решения Диффи-Хеллмана.
Даны четыре точки кривой P, aP, bP, cP. Необходимо определить выполняется ли равенство a=bc.
Прежде чем описать как спаривание Вейля помогает решить данную задачу, замечу что свойство тождественности для точек P и Q, таких что Q=aP, приводит к довольно неудобному результату. Согласно этому правилу отображение пары P и Q равняется единице .
Чтобы исправить этот недостаток, необходимо найти другую точку такого же порядка, что и Q, но при этом линейно независимую от P.
Существует специальный метод, называемый деформирующем отображением, обозначаемым как F(P). При использовании деформирующего отображения спаривание Вейля записывается как: .
Выражение не будет равняться единице, т.к. точка F(P) линейно независима от P. Эта операция называется модифицированным спариванием Вейля.

Рассмотрим теперь задачу принятия решения Диффи-Хеллмана. Вычислим пару и . Учитывая, что , равенство будет выполнятся только при условии, что a=bc.

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

Личностная криптография. Неинтерактивная схема разделения ключей SOK

Вернемся теперь к основной теме этого топика. А именно, к проблеме аутентификации ключей.

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

Неинтерактивный протокол SOK(в честь первых букв имен его создателей) состоит из следующих частей.

Установка параметров системы
В протоколе участвуют три стороны: Алиса, Боб и Трент(доверенный центр производящий генерацию ключей и удостоверяющий личность пользователей).

Первая часть протокола производится непосредственно Трентом. Он выполняет следующие операции.

1. Генерирует две группы (G₁,+) и (G₂,*), для которых выполняется модифицированное спаривание Вейля e. А затем выбирает произвольный порождающий элемент .
2. Случайным образом выбирает число l и устанавливает параметр P_pub=l*P. Число l является главным секретным ключом системы.
3. Выбирает стойкую криптографическую хэш функцию f. Функция f служит для отображения личной информации пользователя ID, в элемент группы G₁.
4. Оглашает системные параметры (G₁, G₂, e, P, P_pub, f).

Генерация ключей пользователя
Эта часть тоже выполняется Трентом. Пусть ID_A — некий однозначно определяемый идентификатор Алисы. Это может быть полное ее имя или паспортные данные.
Проверив личность Алисы и убедившись, что ID_A действительно принадлежит ей, Трент выполняет следующие действия.

1. Вычисляет элемент группы G₁ как P_ID = f(ID_A ).
2. Устанавливает закрытый ключ Алисы S_IDa = l* P_IDa

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

Алгоритм разделения ключа
Идентификаторы Алисы и Боба ID_A и ID_B известны обоим партнерам. Следовательно они могут вычислить элементы группы G₁ P_A=f(ID_A) и P_B=f(ID_B).
Для генерации общего ключа K_AB Алиса вычисляет .
Боб в свою очередь для получения общего ключа с Алисой вычисляет .
Учитывая свойство билинейности независимо друг от друга они получают один и тот же элемент группы G₂: .

Преимущества и недостатки личностной криптографии

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

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

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

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

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