05.08 // Новые направления в ассиметричной криптографии

//Новые направления в ассиметричной криптографии

Криптография с открытым (или публично доступным) ключём (Public Key Crypto – PKC) стала известна в семидесятые годы прошлого века. Рассекреченые позднее документы свидетельствуют об открытии её в секретных службах примерно на десять лет раньше.

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

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

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

Первый асимметричный алгоритм совместной генерации сеансового симметричного ключа был опубликован Диффи и Хелманом в 1976 году (DH).
Он основан на трудности нахождения дискретных логарифмов. Его идея была адаптирована для создания алгоритма шифрования с открытым ключём Эль-Гамаля и алгоритма подписи Эль-Гамаля (1984 год), вариант которой, предложеный американским Агенством Национальной Безопасности вошёл в стандарт под названием алгоритма DSA.

Другой известный алгоритм для шифрования и подписи был изобретён Райвистом, Шамиром и Адлеманом (RSA) и опубликован в 1978 году. Он основан на другой проблеме – трудности нахождения множителей произведения двух простых чисел (целочисленной факторизации). Система шифрования Рабина также полагается на трудность этой проблемы.

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

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

В 1985-1987 Коблитц и Миллер дали начало идее криптографии на эллиптических кривых (Elliptic Curve Cryptography – ECC), которая позволила перенести все алгоритмы, основанные на проблеме Диффи-Хеллмана в группы точек на эллиптических кривых. Если в традиционных DH-алгоритмах используются мультипликативные группы, то здесь применяются аддитивные группы точек эллиптических кривых над конечными полями. Это позволило убрать возможность применения ненужных операций, которые только способствуют ускоренному взлому и несмотря на повышенный объём вычислений в процессе работы криптоалгоритмов, увеличить относительную стойкость. Соответственно длина ключа становится значительно меньше, и при такой длине ключа абсолютная скорость возрастает.
Многие системы, где происходит или обработка очень большого числа запросов (электронное голосование) или используется очень слабый процессор для операций (смарт-карты) проектируются на основе ECC-алгоритмов.

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

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

Более общая задача состоит в исследовании возможностей создания ассиметричных алгоритов на основе новых принципов.

Задачи на основе укладки рюкзака и теории конечных автоматов не привели к созданию стойких схем.

Интерес продолжают вызывать система МакЭлиса (1978 год) на основе кодов коррекции ошибок (серьёзных методов взлома продемонстрировано не было, предполагается устойчивость к квантовому криптоанализу), однако она практически не применяется из-за большой длины ключа (несколько сотен тысяч бит).
Система Ajtai-Dwork (AD) – (1997 год) – первая, основанная на использовании таких математических объектов как решётки. Она также непрактична из медленного побитового шифрования, значительного увеличения шифртекста по сравнению с открытм текстом и больших размеров ключей. Другие схемы на основе решёток (Goldreich-Goldwasser-Halevi – GGH97) также не получили распространения. Они также считаются трудными для квантового криптоанализа, однако методы обычного криптоанализа против них более эффективны.

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

Boaz Barak и Avi Wigderson в работе
Public Key Cryptography from Different Assumptions
недавно предложили подход, основанный на использовании псевдослучайных генераторов и теории графов, однако о практическом построения алгоритма говорить пока рано.

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

Chris J. Mitchel в 2003 году в работе "Public key encryptions using block ciphers" предложил усовершенствовать идею головоломок Меркла. Для построения ассиметричного алгоритма используются любые блочные шифры. К сожалению, для обеспечения 64-битного уровня безопасности (аналогичного симметричным шифрам, что явно недостаточно), требуется закрытый ключ размером 30 гигабайт и открытый размером 60 гигабайт, увеличение стойкости схемы делает её еще более непрактичной.

Попытки создания ассиметричных алгоритмов на основе блочных шифров с секретными параметрами S-блоков (Patarin's 2-Round Public Key System with S-boxes) не увенчались созданием стойких схем.

Тем интереснее выглядит работа Public Key Block Cipher Based on Multivariate Quadratic Quasigroups
Danilo Gligoroski and Smile Markovski and Svein J. Knapskog, в которой авторы соединяют теорию многовариантых квадратичных многочленов и использование квазигруп. Им уже удалось относительно упешно продемонстрировать потоковый шифр Edon 80 на конкурсе eStream, где он хотя и не стал победителем, но был отмечен за перспективный дизайн на основе квазигрупп.

Теория квазигрупп изучается уже давно (в середине 50-х годов XX века одним из ведущих мировых учёных, занимавшихся этой проблемой, был советский математик Белоусов).

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

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

Исследователи описали новый тип объектов – мультивариантные квазигруппы и добились неожиданно высоких результатов в плане практической реализации алгоритма:

1) Алгоритм является детерминистским (не требует ввода случайных параметров) и является однозначным отображением.
2) Алгоритм не увеличивает размер сообщения после шифрования
3) Алгоритм имеет один параметр n=(140,160,180,200) – длина шифрованного блока в битах.
4) Предполагаемый уровень стойкости алгоитма 2^^ (n/2)^^
5) Скорость шифрования сопоставима с алгоритмами на многовариантых квадратичных многочленах.
6) Скорость расшифрования и подписи сопостоваима со скоростью работы обычных блочных шифров (в 500-1000 раз быстрее традиционных ассиметричных алгоритмов).
7) Алгоритм подходит для создания коротких подписей.

Таким образом, авторам удалось создать ассиметричный алгоритм с коротким ключём, который в 10000 раз быстрее RSA и если он окажется стойким и обладает свойствами блочного шифра, то он может изменить многие криптографические протоколы.

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

И хотя стойкость алгоритма может вызывать сомнения (неудачные случаи использования квазигрупп в криптографии тоже встречались), на всякий случай стоит запомнить название новой, необычной криптосистемы – Multivariate Quadratic Quasigroups (MQQ).

Источник: Cryptology ePrint Archive