Указатель — Разделы — Обозначения — Автор — О проекте
Вспомогательный раздел к разделу КРИПТОГРАФИЯ.
Криптоанализом называется совокупность действий потенциального противника, направленных на достижение какой-либо из следующих целей:
Будем также считать, что противник (криптоаналитик) не имеет непосредственного доступа к генератору шифра, но в то же время:
Я не буду касаться различных технических аспектов и роли человеческого фактора для криптоанализа (см. по этому поводу весьма перспективные разработки компании "Терморектальный криптоанализ" ). Предметом криптоанализа в настоящем разделе является исключительно алгоритм RSA.
Поллард [2] указал еще один неудачный выбор множителей. Каждое из чисел и
очевидно
составное. Пусть все простые сомножители в каноническом разложении
числа
оказываются меньшими некоторого целого
; тогда все они
содержатся в последовательности
всех простых чисел, не превосходящих . Для любого числа
из этой последовательности определим
как показатель
максимальной степени числа
, умещающейся в
:
Тогда число
очевидно делится на . Теорема Ферма утверждает,
что
Поскольку сравнения можно возводить в степень (см. ☞ ЗДЕСЬ), тогда будет
Последнее эквивалентно условию, что число делится на
.
Следовательно,
равен либо
, либо
.
На этом и основан алгоритм факторизации. Выбираем произвольное простое число
,
, проверяем условие
(в противном случае
является множителем
). Задаем предполагаемую оценку
для простых
множителей канонического представления какого-то из чисел
или
.
Выписываем все простые числа от
до
, пусть их количество равно
.
Вычисляем соответствующие показатели
.
Поскольку ( см. свойства сравнений ☞ ЗДЕСЬ)
то вычисление имеет смысл сразу проводить по модулю
,
творчески развив метод квадрирования-умножения:
Если какое-то , то выбор
признается неудачным и выбирается другое
значение1).
Если
, то мы нашли нетривиальный множитель числа
,
если
, то при
вычисляем
. Если же
,
то оценка
признается несостоятельной, т.е. каждое из чисел
или
имеет хотя бы один простой сомножитель, больший
.
Оценка
увеличивается, последовательность
простых чисел дополняется новыми и процесс вычисления
продолжается.
Пример. Факторизовать число .
Решение. В качестве рабочей гипотезы полагаем .
Выбираем произвольное простое
, например,
.
Выписываем все простые числа
, лежащие в промежутке от
до
вместе с соответствующими показателями
.
Вычисляем
по схеме
:
Итак, . Это и есть
(для полноты картины укажем, что
), а
.
♦
Понятно, что успех метода существенно зависит от величины : чем она
меньше, тем быстрее факторизуется число
. Если же
у чисел
имеются большие простые сомножители, то схема рискует работать долго:
так, при
пришлось бы рассмотреть
простых чисел, меньших
.
Эта атака будет успешной в том случае, когда хотя бы один из простых сомножителей модуля
обладает следующим свойством: число
раскладывается в произведение простых сомножителей
таких, что числа
имеют только небольшие простые сомножители.
Задав произвольное
такое, что
, криптоаналитик вычисляет последовательность
и проверяет условие .
Пример. Факторизовать модуль ключа шифрования .
Решение. Взяв , величину
получим уже при
. Проверьте, что это значение
возникает и при других выборах
. Установите значения
, соответствующие минимальному количеству итераций до факторизации.
Факторизовать модуль ключа шифрования .
Любое число , сравнимое по модулю
с
«официальным» — т.е. найденным по алгоритму RSA — ключом дешифрования
, также служит ключом дешифрования:
Можно ли, однако, утверждать единственность ключа дешифрования во множестве
Ответ отрицателен:
Теорема. При любом выборе ключа шифрования2)
существует не менее двух различных ключей дешифрования любого зашифрованного
сообщения, т.е. чисел
и
из множества
, удовлетворяющих соотношению
Всего во множестве находится ровно
ключей дешифрования с таким свойством.
Доказательство. Одно из требуемых чисел — «официальный» ключ дешифрования
—
получим как решение сравнения
:
Тогда любое число из множества
где — обобщенная функция Эйлера,
будет также ключом дешифрования:
Все числа множества различны, так как при
получим, что число
делится на
, что невозможно
ввиду равенства
♦
Пример. Установить минимальный возможный ключ дешифрования сообщения
при открытом ключе шифрования .
Решение. и
,
следовательно,
.
Решением сравнения
является число
(и именно его разработчик (владелец) принимал за «официальный» ключ
дешифрования). Однако, согласно теореме, любое число из множества
также будет ключом дешифрования. Минимально возможный ключ дешифрования
получается при и равен
. Следовательно, последовательно
возводя в степени по модулю
первый блок
шифровки:
и пытаясь декодировать получаемые блоки:
криптоаналитик уже на 10-м шаге узнает ключ дешифрования. ♦
Практическая рекомендация. Проверьте, чтобы для выбранных случайным
образом сомножителей и
число
было небольшим.
Часть сообщения может остаться незашифрованным!
Пример. ,
,
Без всякого дешифрования подчеркнутые блоки декодируются в довольно осмысленнные сочетания букв.
Неподвижной (или инвариантной) точкой отображения
называется число
, оставляемое этим
отображением неизмененным:
Очевидно, что при любом неподвижными точками будут
и
.
Пример. Неподвижными точками отображения являются
.
Геометрический смысл: если изобразить все пары
на плоскости
, то неподвижные
точки расположатся на биссектрисе первого координатного угла.
Задача. Найти неподвижные точки отображения при
числах и
, удовлетворяющих условиям алгоритма RSA.
Теорема. Если число делится на
, то любая
неподвижная точка отображения
будет неподвижной точкой
отображения
.
Доказательство. Поделим на
:
.
Тогда если
, то
При получаем утверждение теоремы.
♦
При выборе чисел и
, удовлетворяющих условиям алгоритма RSA, всегда существуют по крайней мере две неподвижные точки, отличные от
и
.
Доказательство. Действительно, упомянутые точки являются
неподвижными точками отображения ,
т.е. решениями сравнения
Эти решения легко вычисляются с помощью теоремы Ферма:
также легко устанавливается, что и что
.
Более того, поскольку выбор согласно
условиям алгоритма RSA гарантирует нечетность этого числа, то, на основании предыдущей теоремы,
и неподвижные точки отображения
именно:
также будут неподвижными точками отображения .
♦
Если — неподвижная точка отображения
,
то и любая ее степень
при
также является неподвижной точкой.
Теорема. Число неподвижных точек отображения равно
Доказательство. Действительно, сравнение эквивалентно
системе сравнений
Сравнение
имеет решений по модулю
:
и
корней
-й степени
из 1 (см. теорему Эйлера ☞ ЗДЕСЬ ). Берем всевозможные пары решений сравнений по модулям
и
, каждая из них
порождает единственное решение сравнения
,
которое может быть найдено по китайской теореме об остатках.
♦
Пример. Вычислить число инвариантных точек для ключа шифрования из предыдущего примера.
Решение. и
.
По теореме получаем число инвариантных точек: .
Насколько оно велико? Отношение этого числа к числу
,
потенциально возможных сообщений
, т.е. в среднем
каждый третий блок открытого текста рискует быть незашифрованным. Примерно это
и происходит при шифровании ключом
открытого
текста3):
А | к | р | а | й | н | я | я | з | в | е | з | д | а | в | к | о | н | ц | е | с | е | л | а | |||||||||||
01 | 00 | 11 | 17 | 01 | 10 | 14 | 32 | 32 | 00 | 08 | 03 | 06 | 08 | 05 | 01 | 00 | 03 | 00 | 11 | 15 | 14 | 23 | 06 | 00 | 18 | 06 | 12 | 01 | 00 | |||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
К | а | к | с | в | е | т | в | п | о | с | л | е | д | н | е | м | д | о | м | и | к | е | п | р | и | х | о | д | а | |||||
11 | 01 | 11 | 00 | 18 | 03 | 06 | 19 | 00 | 03 | 00 | 16 | 15 | 18 | 12 | 06 | 05 | 14 | 06 | 13 | 00 | 05 | 15 | 13 | 09 | 11 | 06 | 00 | 16 | 17 | 09 | 22 | 15 | 05 | 01 |
Здесь выделенные блоки (длины 10) при отображении
останутся неизмененными.
♦
Практическая рекомендация. Показатель шифрования из алгоритма
RSA надо выбирать так, чтобы числа
были небольшими.
В алгоритме RSA построения ключей шифрования и дешифрования, создателю предлагается сначала выбрать — почти произвольным — ключ дешифрования , а уже по
нему вычислять ключ шифрования
как решение сравнения
. Ввиду симметричности последнего сравнения относительно чисел
и
, указанная
последовательность выбора допускает обращение: ничто не мешает выбирать
сначала
,
а уже по нему устанавливать
. Такая возможность иногда оправдана
тем, что выбор небольшого показателя
может облегчить процедуру
шифрования для корреспондентов. Действительно, выбор в качестве
показателя шифрования
с точки зрения стойкости для криптоанализа для модулей
совершенно равнотруден. С другой стороны, если можно взять
или
, то процедура шифрования
,
проводимая по алгоритму квадрирования-умножения, становится особенно легкой. Вдобавок при выборе
самому создателю облегчается
вычисление ключа
: он найдется по формуле
Тем не менее выбор в качестве показателя шифрования числа
одновременно несколькими — конкретно, тремя —
владельцами, может привести к успеху следующей атаки. Предположим, что
один и тот же открытый текст
должен быть секретно
переслан трем корреспондентам, ключи шифрования которых соответственно
и
. Криптоаналитик, перехвативший
шифровки
может восстановить открытый текст .
Действительно, криптоаналитик знает остатки
от деления (неизвестного ему)
числа
на числа
, ему также известно, что
Тогда по китайской теореме об остатках число
однозначно восстанавливается4), а уж извлечь из него кубический
корень можно по алгоритму, изложенному ☞ ЗДЕСЬ. Итог: сами шифры не
взламываются, но зашифрованное ими сообщение прочитывается!
Пример. Восстановить открытый текст по шифровкам
Решение. Действуя по алгоритму
1
китайской теоремы об остатках, вычисляем
сначала и
как решения сравнений:
Тогда
и после вычисления остатка от деления последнего числа на получаем
Извлечем из правой части корень кубический с помощью алгоритма теоремы, приведенной ☞ ЗДЕСЬ: если начать с числа ,
то итерационная последовательность
за 9 шагов сойдется к значению
.
С теоретической точки зрения подобная атака возможна и для других
выборов показателя ; однако же — по здравому размышлению о
свойствах человеческой натуры — немыслимо вообразить ситуацию, когда
некий секрет, одновременно доверенный, скажем,
людям,
не станет немедленным достоянием всего информационно озабоченного
человечества…
[2]. Pollard J.M. Theorems on factorization and primality testing. Proc. Cambridge Phil.Soc. 1974. Vol. 76. P. 521–528.