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


Криптография с открытым (или публично доступным) ключом (Public Key Crypto – PKC) стала известна в семидесятые годы прошлого века. Рассекреченые позднее документы, относящиеся к 1970 году, свидетельствуют об открытии её в секретных службах Великобритании исследователями James H. Ellis, Clifford Cocks, и Malcolm Williamson.

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

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

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

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

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

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

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

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

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

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

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

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

Интерес продолжают вызывать система МакЭлиса (1978 год) и система Нидеррайтера на основе кодов коррекции ошибок (серьёзных методов взлома продемонстрировано не было (известны атаки Штерна, Сидельникова, Canteaut-Sendrier-Chabaud), и эти системы являются одними из основных кандидатов на алгоритмы, устойчивые к квантовому криптоанализу), однако практически не применяются из-за большой длины ключа (несколько сотен тысяч бит).

Недавние исследования, изложенные в работе Daniel J. Bernstein, Tanja Lange Christiane Peters Attacking and defending the McEliece cryptosystem[link1] привели к созданию улучшенного метода атаки на систему МакЭлиса и Нидеррайтера.

Используя компьютер с процессором Core 2 Quad 6600 на проведение атаки на систему МакЭлиса с предполагавшимися ранее параметрами безопасности потребовалось бы 1400 дней (или 258 процессорных циклов). Используя кластер из двухсот компьютеров стоимостью $200000 можно уменьшить время вскрытия до одной недели. При этом коммуникации между узлами кластера практически не требуется.

Данный пример отражает прогресс в области вычислительных технологий – аналогичная атака, проводимая в 1998 году на процессорах 433MHz DEC Alpha потребовала бы 7400000 дней (268 процессорных циклов).

Уменьшение времени атаки с 7400000 до 1400 дней за десять лет выглядит впечатляюще.
Дешёвые процессоры Core 2 Quad работают в 5.54 раз быстрее по тактовой частоте, чем процессор Alpha 21164, имеют 4 параллельных ядра вместо одного и способны выполнять три арифметические инструкции за один цикл (в отличие от двух).

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

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

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

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

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

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

К сожаление этот метод нельзя использовать для асимметричного шифрования.

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

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

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

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

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

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

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

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

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

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

Алгоритм протестирован как на быстрых процессорах (скорость работы 160-битной C-реализации на Intel Core 2 Duo составляет 11000 циклов за такт на одном ядре и 6000 циклов на двух ядрах, что говорит о хорошем распараллеливании), так и на медленных программируемых микросхемах FPGA (Xilinx Virtex-5: 249.4 Mhz – скорость расшифрования 399 Mbps, зашифрование при частоте 276.7 Mhz – скорость зашифрования 44.27 Gbps)

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

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

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

Ссылки
[link1] http://eprint.iacr.org/2008/318

[link2] http://eprint.iacr.org/2008/335

[link3] http://www.ma.rhul.ac.uk/static/techrep/2003/RHUL-MA-2003-6.pdf

[link4] http://eprint.iacr.org/2008/320

[link5] http://www.ecrypt.eu.org/stream/edon80p3.html