19.10 Криптосистемы с открытым ключом на базе конечных автоматов

Китайский криптограф Тао Ренжи разработал алгоритм с открытым ключом, основанный на использовании конечных автоматов [1301, 1302, 1303, 1300, 1304, 666]. Такой же сложной задачей, как и разложение на множители произведения двух больших простых чисел, является задача разложения на составляющие произведения двух конечных автоматов. Это тем более верно, если один из автоматов нелинеен.

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

О производительности таких систем вкратце можно сказать следующее: они, как и система McEliece, намного быстрее RSA, но требуют использования более длинных ключей. Длина ключа, обеспечивающая, как думают, безопасность, аналогичную 512-битовому RSA, равна 2792 битам, а 1024-битовому RSA - 4152 битам. В первом случае система шифрует данные со скоростью 20869 байт/ñ и дешифрирует данные со скоростью17117 байт/ñ, работая на 80486/33 МГц.

Ренжи опубликовал три алгоритма. Первым был FAPKC0. Эта слабая система использует линейные компоненты и, главным образом, является иллюстративной. Каждая из двух серьезных систем, FAPKC1 и FAPKC2, использует один линейный и один нелинейный компонент. Последняя сложнее, она была разработана для поддержки операции проверки подлинности.

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

Привлекательной особенностью FAPKC1 и FAPKC2 является то, что они не ограждены никакими патентами США. Следовательно, так как срок действия патента на алгоритм Diffie-Hellman истекает в 1997 году, эти алгоритмы несомненно являются очень интересными.

Алгоритмы цифровой подписи с открытым ключом

20.1 Алгоритм цифровой подписи (digital signature algorithm, dsa)

В августе 19991 года Национальный институт стандартов и техники (National Institute of Standards and Technology, NIST) предложил для использования в своем Стандарте цифровой подписи (Digital Signature Standard, DSS) Алгоритм цифровой подписи (Digital Signature Algorithm, DSA). Согласно Federal Register [538]:

Предлагается Федеральный стандарт обработки информации (Federal Information Processing Standard, FIPS) для Стандарта цифровой подписи (Digital Signature Standard, DSS). В этом стандарте определяется алгоритм цифровой подписи с открытым ключом (DSA), пригодный для федеральных применений, требующих цифровой подписи. Предложенный DSS использует открытый ключ для проверки получателем целостности полученных данных и личности отправителя. DSS также может быть использован третьей стороной для проверки правильности подписи и связанных с ней данных.

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

И:

Предложенный стандарт представляет собой результат оценки различных методик цифровой подписи. Принимая решение, NIST следовал положению раздела 2 Акта о компьютерной безопасности (Computer Security Act) 1987 года о том, что NIST разрабатывает стандарты," . . . обеспечивающие рентабельные безопасность и секретность Федеральной информации, выбирая из технологий, предлагающих сравнимую степень защиты, ту, которая обладает наиболее подходящими рабочими и эксплуатационными характеристиками".

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

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

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

Прежде, чем все совсем запутается, позвольте мне разобраться с названиями: DSA - это алгоритм, а DSS стандарт. Стандарт использует алгоритм. Алгоритм является частью стандарта.