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

Аналогично процессу в линейном решете, с помощью линейной алгебры мы строим множество S так, чтобы разности

и

были «гладкими». Необходимо уточнить, что в данной ситуации называть гладкими объектами. Для этого придется привлечь теорию числовых полей. Обобщая старое определение гладких целых чисел на случай алгебраических целых, мы получаем следующее определение:

Эта часть метода решета в числовом поле на сегодняшний день больше смахивает на черную магию. Мы требуем выполнения только одного условия:

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

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

Такое наблюдение было сделано Полигом и Хеллманом и справедливо в любой конечной абелевой группе. Вот его обоснование.

Представляем его в виде многочлена:

с коэффициентами{0,1,2}. Как Вы помните, мы решаем уравнение

#' = 286 =

Здесь задача

273=(mod 397)

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

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

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

Пусть ƒ : S → S — случайная функция на множестве S и #S = n.

Выбираем произвольный элементS и последовательно вычисляем

при i ≥ 0.

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

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

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

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

Как уже было отмечено в предыдущих главах, часто применяются достаточно небольшие открытые (шифрующие) экспоненты, например, Е = 3, 17 или 65 537. Причина, по которой выбираются такие значения, состоит в том, что эти числа имеют небольшой вес Хем-минга, фактически наименьший из возможных для открытых RSA-ключей, а именно, 2. Поэтому двоичный метод или любой другой разумный алгоритм потенцирования будет использовать лишь одно общее умножение и к возведений в квадрат, где k — число двоичных знаков открытой экспоненты. Например,

В случае расшифрования или подписывания сообщения в алгоритме RSA показатель вычисляемой степени будет общим 1000-битовым числом. Следовательно, нам нужен какой-нибудь путь сокращения числа операций. К счастью, мы знаем секретный ключ,а значит и разложение модуля алгоритма на множители: N = pq. При расшифровывании сообщения приходится вычислить

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

Криптографическая хэш-функция h — это функция, определенная на битовых строках произвольной длины со значениями в строках битов фиксированной длины. Ее значение часто называют хэш-кодом или хэш-значением. В информатике тоже используются своего рода хэш-функции, но важное отличие криптографических хэш-функций от стандартных состоит в том, что первые должны быть односторонними. Другими словами, должно быть невозможно в вычислительном отношении по элементу Y из множества значений хэш-функции подобрать такой х из области определения, при котором h(x) = Y. Другая характеризация односторонних хэш-функций — сказать о них, что они защищены от восстановления прообразов. Применение криптографических хэш-функций позволяет создать схему подписи RSA без восстановления сообщения, что намного эффективней для длинных сообщений.

Мы уже рассказывали об одной из схем цифровой подписи, а именно о схеме RSA. Можно спросить: зачем нужны еще какие-то схемы подписей? Ответ разобьем на несколько утверждений:

- Что если кто-то вскроет алгоритм RSA или решит задачу разложения на множители?

- Алгоритм RSA неприменим в некоторых приложениях, поскольку генерирование подписи с его помощью — слишком дорогостоящая операция.

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

Может оказаться, что подпись на коротком сообщении будет более длинной, чем его основное содержание. Напомним, что RSA можно использовать и как схему подписи с приложением, и как схему подписи с восстановлением сообщения. Пока ни один из описанных нами алгоритмов подписи, основанный на дискретном логарифмировании, нельзя использовать в виде схемы с восстановлением сообщения. Сейчас мы приведем пример схемы подписи с восстановлением сообщения, называемый алгоритмом подписи Ниберга-Руппеля, основанный на вычислении логарифмов в открытой конечной абе-левой группе А.

Цели главы

• Показать, как работают алгоритмы возведения в степень.

• Объяснить, как эффективно реализовать арифметические операции в кольцах вычетов.

• Перечислить приемы, ускоряющие операции в алгоритмах RSA и DSA.

• Объяснить, как эффективно реализовать конечные поля характеристики 2.