УказательРазделыОбозначенияАвторО проекте


§

Вспомогательный раздел к разделу КРИПТОГРАФИЯ.


Криптоанализ

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

  • установления ключа дешифрования;
  • дешифрования конкретного пересылаемого сообщения;
  • искажения содержания конкретного пересылаемого сообщения.

Будем также считать, что противник (криптоаналитик) не имеет непосредственного доступа к генератору шифра, но в то же время:

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

Я не буду касаться различных технических аспектов и роли человеческого фактора для криптоанализа (см. по этому поводу весьма перспективные разработки компании "Терморектальный криптоанализ" ). Предметом криптоанализа в настоящем разделе является исключительно алгоритм RSA.

Факторизация модуля

Метод Полларда

Поллард [2] указал еще один неудачный выбор множителей. Каждое из чисел p_1-1 и p_2-1 очевидно составное. Пусть все простые сомножители в каноническом разложении числа p_1-1 оказываются меньшими некоторого целого B_{}; тогда все они содержатся в последовательности

{\mathfrak p}_1=2,{\mathfrak p}_2=3,\dots, {\mathfrak p}_K

всех простых чисел, не превосходящих B_{}. Для любого числа {\mathfrak p} из этой последовательности определим {\mathfrak m}({\mathfrak p}) как показатель максимальной степени числа {\mathfrak p}, умещающейся в M_{}:

{\mathfrak p}^{{\mathfrak m}({\mathfrak p})} \le M < {\mathfrak p}^{{\mathfrak m}({\mathfrak p})+1} \ ; очевидно , \ {\mathfrak m}({\mathfrak p}) = \lfloor \log_{{\mathfrak p}} M \rfloor \ .

Тогда число

Q = 2^{{\mathfrak m}(2)} 3^{{\mathfrak m}(3)} \times \dots \times {\mathfrak p}_K^{{\mathfrak m}({\mathfrak p}_K)}

очевидно делится на p_1-1. Теорема Ферма утверждает, что

A^{p_1-1} \equiv 1 \pmod{p_1} \quad npu \quad \forall A\in \mathbb N,\ \operatorname{HOD} (A,p_1)=1 \ .

Поскольку сравнения можно возводить в степень (см. ☞ ЗДЕСЬ), тогда будет

A^Q \equiv 1 \pmod{p_1} \ .

Последнее эквивалентно условию, что число A^Q - 1 делится на p_{1}. Следовательно, \operatorname{HOD} \left(A^Q - 1,\ M \right) равен либо M_{}, либо p_1.

На этом и основан алгоритм факторизации. Выбираем произвольное простое число A_{}, A<M, проверяем условие \operatorname{HOD} (A,M)=1 (в противном случае A_{} является множителем M_{}). Задаем предполагаемую оценку B_{} для простых множителей канонического представления какого-то из чисел p_1-1 или p_2-1. Выписываем все простые числа от 2_{} до B_{}, пусть их количество равно K_{}. Вычисляем соответствующие показатели {\mathfrak m}. Поскольку ( см. свойства сравнений ☞ ЗДЕСЬ)

\operatorname{HOD} (A^Q-1,M) = \operatorname{HOD} \left(A^Q \pmod{M} -1 \ , M \right) \ ,

то вычисление A^{Q} имеет смысл сразу проводить по модулю M_{}, творчески развив метод квадрирования-умножения:

A_1= A^{\left(2^{{\mathfrak m}(2)}\right)} \pmod{M} , \ A_j = A_{j-1}^{\left({\mathfrak p}_j^{{\mathfrak m}({\mathfrak p}_j)} \right)} \pmod{M} \ npu \ j\in \{2,\dots, K\} \ .

Если какое-то A_j=1, то выбор A_{} признается неудачным и выбирается другое значение1). Если \operatorname{HOD} (A_j -1,M)>1, то мы нашли нетривиальный множитель числа M=p_1p_2, если \operatorname{HOD} (A_j -1,M)=1, то при j<K вычисляем A_{j+1}. Если же j=K, то оценка B_{} признается несостоятельной, т.е. каждое из чисел p_1-1 или p_2-1 имеет хотя бы один простой сомножитель, больший B_{}. Оценка B_{} увеличивается, последовательность {\mathfrak p}_1,{\mathfrak p}_2,\dots, {\mathfrak p}_K простых чисел дополняется новыми и процесс вычисления A_{j} продолжается.

П

Пример. Факторизовать число M=5621600403315503.

Решение. В качестве рабочей гипотезы полагаем B=35. Выбираем произвольное простое A_{}, например, A=3. Выписываем все простые числа {\mathfrak p}_j, лежащие в промежутке от 2_{} до 35_{} вместе с соответствующими показателями {\mathfrak m}({\mathfrak p}_j). Вычисляем A^Q \pmod{M} по схеме A_j = A_{j-1}^{\left({\mathfrak p}_j^{{\mathfrak m}({\mathfrak p}_j)} \right)} \pmod{M}:

\begin{array}{|r|r|c|c|c|} \hline j & {\mathfrak p}_j & {\mathfrak m}({\mathfrak p}_j) & A_j & \operatorname{HOD} (A_{j}-1, M) \\ \hline 1 & 2 & 52 & 4705151289181804 & 1 \\ 2 & 3 & 33 & 235135391155109 & 1 \\ 3 & 5 & 22 &1270000020906355 & 1 \\ 4 & 7 & 18 &1868121599217127 & 1 \\ 5 & 11 & 15 &3654732747996024 & 1 \\ 6 & 13 & 14 &1796657525463168 & 1 \\ 7 & 17 & 12 &666082236477340 & 1 \\ 8 & 19 & 12 &607395078985896 & 1 \\ 9 & 23 & 11 &4085605503110574 & 1 \\ 10& 29 & 10 &283149979946519 & 1 \\ 11& 31 & 10 &2028866771759143 & 60871663 \\ \hline \end{array}

Итак, \operatorname{HOD} (A_{11}-1, M)=60871663. Это и есть p_{1} (для полноты картины укажем, что p_1 = 2\cdot 3^4\cdot 17 \cdot 23 \cdot 31^2 +1), а p_2=M/p_1=92351681.

Понятно, что успех метода существенно зависит от величины B_{}: чем она меньше, тем быстрее факторизуется число M_{}. Если же у чисел p_j-1 имеются большие простые сомножители, то схема рискует работать долго: так, при B=7040 пришлось бы рассмотреть K=905 простых чисел, меньших B_{}.

Циклическая атака

Эта атака будет успешной в том случае, когда хотя бы один из простых сомножителей p_{j} модуля M_{} обладает следующим свойством: число p_j-1 раскладывается в произведение простых сомножителей p_{j\ell} таких, что числа p_{j\ell}-1 имеют только небольшие простые сомножители. Задав произвольное A_{0} такое, что \operatorname{HOD}(A_0,M)=1, криптоаналитик вычисляет последовательность

A_j=A_{j-1}^{\mathbf E} \pmod{M} \quad npu \ j\in \{1,2,\dots \}

и проверяет условие \operatorname{HOD}(A_j-A_0,M)>1.

П

Пример. Факторизовать модуль ключа шифрования M=2319201790063859,\ {\mathbf E}=11.

Решение. Взяв A_{0}=2, величину p_{1}=98771191 получим уже при j=432. Проверьте, что это значение j_{} возникает и при других выборах A_{0}. Установите значения A_{0}, соответствующие минимальному количеству итераций до факторизации.

?

Факторизовать модуль ключа шифрования M=1315782370787146343,\ {\mathbf E}=7.

Ключ дешифрования неединствен

Любое число \tilde{\mathbf D}, сравнимое по модулю \phi(M) с «официальным» — т.е. найденным по алгоритму RSA — ключом дешифрования \mathbf D, также служит ключом дешифрования:

{\mathbf D} \equiv \tilde{{\mathbf D}} \pmod{\phi(M)} \ \Rightarrow \ \left(x^{{\mathbf E}} \right)^{\tilde{\mathbf D}} \equiv x \pmod{M} \quad для \ \forall x\in \{0,1,\dots,M-1 \} \ .

Можно ли, однако, утверждать единственность ключа дешифрования во множестве

\left\{0,1,\dots, \phi(M)-1 \right\} \ ?

Ответ отрицателен:

Т

Теорема. При любом выборе ключа шифрования2) {\mathbf E} существует не менее двух различных ключей дешифрования любого зашифрованного сообщения, т.е. чисел {\mathbf D} и \tilde{{\mathbf D}} из множества \{0,1,\dots, \phi(M)-1 \}, удовлетворяющих соотношению

\left(x^{\mathbf E}\right)^{{\mathbf D}}\equiv_{_M} \left(x^{\mathbf E}\right)^{\tilde{{\mathbf D}}}\equiv_{_M}x \quad для \ \forall x\in \{0,1,2,\dots, M-1\} \ .

Всего во множестве \{0,1,\dots, \phi(M)-1 \} находится ровно

\tilde d = \operatorname{HOD} (p_1-1,\, p_2-1)

ключей дешифрования с таким свойством.

Доказательство. Одно из требуемых чисел — «официальный» ключ дешифрования {\mathbf D} — получим как решение сравнения {\mathbf E} \cdot {\mathbf D} \equiv 1 \pmod{\phi(M)}:

x^{\mathbf E} \equiv c \pmod{M} \quad \Rightarrow \quad c^{\mathbf D} \equiv x \pmod{M} \ .

Тогда любое число {\tilde{{\mathbf D}}} из множества

\left\{ {\mathbf D}+k L(M) \pmod{\phi (M)} \ \big| \ k \in \{ 0,1, \dots , \tilde d -1 \} \right\} \ ,

где L(M)= \operatorname{HOK} (p_1-1,\, p_2-1)обобщенная функция Эйлера, будет также ключом дешифрования:

c^{\tilde{\mathbf D}} = c^{{\mathbf D}+k L(M)} = c^{\mathbf D} \left(c^{L(M)}\right)^k \ \ \equiv_{_M} \ \ c^{\mathbf D} \equiv_{_M} x \ .

Все числа множества различны, так как при

{\mathbf D}+k_1 L(M)\equiv {\mathbf D}+k_2 L(M) \pmod{\phi (M)} \ , \quad 0\le k_1 < k_2 \le \tilde d -1 \ ,

получим, что число (k_2-k_1) L(M) делится на \phi (M), что невозможно ввиду равенства

\underbrace{\operatorname{HOD} (p_1-1,\, p_2-1)}_{\tilde d} \cdot \underbrace{\operatorname{HOK} (p_1-1,\, p_2-1)}_{L(M)} =\underbrace{(p_1-1)(p_2-1)}_{\phi(M)} \ .

П

Пример. Установить минимальный возможный ключ дешифрования сообщения

325172590473\ 343958407857\ 181997910876\ 256274850311\ 012909887764

при открытом ключе шифрования M=357106915621, {\mathbf E}=182979752741.

Решение. M=505051 \times 707071 и \tilde d=101010, следовательно, L(M)=\, 505050 \times 707070/101010=3535350. Решением сравнения {\mathbf E} \cdot {\mathbf D} \equiv 1 \pmod{\phi(M)} является число {\mathbf D}=3535361 (и именно его разработчик (владелец) принимал за «официальный» ключ дешифрования). Однако, согласно теореме, любое число из множества

\big\{3535361+ k\, 3535350 \ \big| \ k \in \{ -1,0,1,\dots , 101008 \} \big\}

также будет ключом дешифрования. Минимально возможный ключ дешифрования получается при k=-1 и равен 11_{}. Следовательно, последовательно возводя в степени по модулю M_{} первый блок c_1=325172590473 шифровки:

c_1^2 \pmod{M},\ c_1^3 \pmod{M}, \dots,\ c_1^{11} \pmod{M} \ ,

и пытаясь декодировать получаемые блоки:

173840865911,\ 058667684818,\dots, 320008140131 \ ,

криптоаналитик уже на 10-м шаге узнает ключ дешифрования.

Практическая рекомендация. Проверьте, чтобы для выбранных случайным образом сомножителей p_{1} и p_{2} число \operatorname{HOD} (p_1-1,\, p_2-1) было небольшим.

Незашифрованные блоки

Часть сообщения может остаться незашифрованным!

П

Пример. M=3601800221, {\mathbf E}=300140017,

\begin{array}{l} \underline{0100111701}\ 2753015690\ 2201516922\ 3363274335\ 1518851909\ \underline{1806120100}\ \\ 3573090214\ \underline{0306190003}\ 0954217522\ 3363101814\ 1887404463\ \underline{1106001617}\ 2744326638 \end{array}

Без всякого дешифрования подчеркнутые блоки декодируются в довольно осмысленнные сочетания букв.

Неподвижной (или инвариантной) точкой отображения {x^{\mathbf E} \pmod{M}} называется число x\in \{0,1,\dots,M-1\}, оставляемое этим отображением неизмененным:

x^{\mathbf E} \equiv x \pmod{M} \ .

Очевидно, что при любом {\mathbf E} неподвижными точками будут 0_{} и 1_{}.

П

Пример. Неподвижными точками отображения x^7 \pmod{187} являются 0,\, 1,\, 33,\, 34,\,67,\, 120,\, 153,\, 154,\, 186. Геометрический смысл: если изобразить все пары (x, x^{\mathbf E} \pmod{M}) на плоскости (x,y_{}), то неподвижные точки расположатся на биссектрисе первого координатного угла.

Задача. Найти неподвижные точки отображения при числах M_{} и {\mathbf E}, удовлетворяющих условиям алгоритма RSA.

Т

Теорема. Если число {\mathbf E}-1 делится на \ell-1, то любая неподвижная точка отображения x^{\ell} \pmod{M} будет неподвижной точкой отображения x^{\mathbf E} \pmod{M}.

Доказательство. Поделим {\mathbf E} на \ell-1: {\mathbf E}=q(\ell-1)+r, 0\le r<\ell-1. Тогда если x^{\ell} \equiv x \pmod{M}, то

x^{\mathbf E} =\left(x^{\ell} \right)^q x^{r-q} \equiv x^{r} \pmod{M} \ .

При r_{}=1 получаем утверждение теоремы.

=>

При выборе чисел M_{} и {\mathbf E}, удовлетворяющих условиям алгоритма RSA, всегда существуют по крайней мере две неподвижные точки, отличные от 0_{} и 1_{}.

Доказательство. Действительно, упомянутые точки являются неподвижными точками отображения x^{2} \pmod{M}, т.е. решениями сравнения

x^2 \equiv x \pmod{M} \ .

Эти решения легко вычисляются с помощью теоремы Ферма:

X_1= p_1^{p_2-1} \pmod{M} ,\quad X_2= p_2^{p_1-1} \pmod{M} \ ;

также легко устанавливается, что X_2=M+1-X_1 и что X_1\ne X_2.

Более того, поскольку выбор {\mathbf E} согласно условиям алгоритма RSA гарантирует нечетность этого числа, то, на основании предыдущей теоремы, и неподвижные точки отображения x^{3} \pmod{M} именно:

X_1,\, X_2,\, X_1-1,\, X_2-1,\, \left| X_2-X_1 \right|,\, M-\left|X_2-X_1\right|,\, M-1 \ ,

также будут неподвижными точками отображения x^{\mathbf E} \pmod{M}.

?

Если x_{0} — неподвижная точка отображения x^{\mathbf E} \pmod{M}, то и любая ее степень x_0^k \pmod{M} при k \in \mathbb N также является неподвижной точкой.

Т

Теорема. Число неподвижных точек отображения x^{\mathbf E} \pmod{M} равно

(d_1+1)(d_2+1) \ npu \ d_1 = \operatorname{HOD}(E-1,p_1-1),\ d_2 = \operatorname{HOD}(E-1,p_2-1)\ .

Доказательство. Действительно, сравнение x^{\mathbf E} - x \equiv 0 \pmod{M} эквивалентно системе сравнений

x^{\mathbf E} - x \equiv 0 \pmod{p_1} \quad u \quad x^{\mathbf E} - x \equiv 0 \pmod{p_2} \ .

Сравнение

x^{\mathbf E} - x =x \left(x^{{\mathbf E}-1} -1 \right) \equiv 0 \pmod{p_j}

имеет d_{j}+1 решений по модулю p_j: x_{}=0 и d_{j} корней (E-1)-й степени из 1 (см. теорему Эйлера ☞ ЗДЕСЬ ). Берем всевозможные пары решений сравнений по модулям p_{1} и p_{2}, каждая из них порождает единственное решение сравнения x^{\mathbf E} - x \equiv 0 \pmod{M}, которое может быть найдено по китайской теореме об остатках.

П

Пример. Вычислить число инвариантных точек для ключа шифрования из предыдущего примера.

Решение. M=3601800221=60013\times 60017 и {\mathbf E}=300140017.

По теореме получаем число инвариантных точек: (d_1+1)(d_2+1) =1200640085. Насколько оно велико? Отношение этого числа к числу M_{}, потенциально возможных сообщений \approx 0.3333, т.е. в среднем каждый третий блок открытого текста рискует быть незашифрованным. Примерно это и происходит при шифровании ключом ({\mathbf E},M) открытого текста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

Здесь выделенные блоки x_{j} (длины 10) при отображении x_j^{\mathbf E} \pmod{M} останутся неизмененными.

Практическая рекомендация. Показатель шифрования {\mathbf E} из алгоритма RSA надо выбирать так, чтобы числа d_j = \operatorname{HOD}(E-1,p_j-1) были небольшими.

Атака "малых показателей"

В алгоритме RSA построения ключей шифрования и дешифрования, создателю предлагается сначала выбрать — почти произвольным — ключ дешифрования \mathbf D, а уже по нему вычислять ключ шифрования \mathbf E как решение сравнения \mathbf E \cdot \mathbf D \equiv 1 \pmod{\phi(M)}. Ввиду симметричности последнего сравнения относительно чисел \mathbf E и \mathbf D, указанная последовательность выбора допускает обращение: ничто не мешает выбирать сначала \mathbf E, а уже по нему устанавливать \mathbf D. Такая возможность иногда оправдана тем, что выбор небольшого показателя \mathbf E может облегчить процедуру шифрования для корреспондентов. Действительно, выбор в качестве показателя шифрования

\mathbf E= 3 \quad или \quad \mathbf E=2^{16}+1=65537 \quad или \quad \mathbf E=876125345816781182489

с точки зрения стойкости для криптоанализа для модулей M\ge 10^{155} совершенно равнотруден. С другой стороны, если можно взять \mathbf E= 3 или \mathbf E=2^{16}+1, то процедура шифрования x^{\mathbf E} \pmod{M}, проводимая по алгоритму квадрирования-умножения, становится особенно легкой. Вдобавок при выборе \mathbf E= 3 самому создателю облегчается вычисление ключа \mathbf D: он найдется по формуле

{\mathbf D}=\phi (M)-\frac{1}{3}\left(\phi (M)-1 \right)\ .

Тем не менее выбор в качестве показателя шифрования числа \mathbf E= 3 одновременно несколькими — конкретно, тремя — владельцами, может привести к успеху следующей атаки. Предположим, что один и тот же открытый текст x_{} должен быть секретно переслан трем корреспондентам, ключи шифрования которых соответственно (3,M_1),\, (3,M_2) и (3,M_3). Криптоаналитик, перехвативший шифровки

c_1 = x^3 \pmod{M_1}, \ c_2 = x^3 \pmod{M_2},\ c_3 = x^3 \pmod{M_3} \ ,

может восстановить открытый текст x_{}. Действительно, криптоаналитик знает остатки c_{j} от деления (неизвестного ему) числа x^{3} на числа M_{j}, ему также известно, что

0<x^3 < \left( \min_{j=1,2,3} M_j \right)^3 \ .

Тогда по китайской теореме об остатках число x^{3} однозначно восстанавливается4), а уж извлечь из него кубический корень можно по алгоритму, изложенному ☞ ЗДЕСЬ. Итог: сами шифры не взламываются, но зашифрованное ими сообщение прочитывается!

П

Пример. Восстановить открытый текст x_{} по шифровкам

\begin{array}{ccl} c_1 &=&157376600452 \quad (M_1=375208626847,\, \mathbf E=3) \ ,\\ c_2 &=&169331183823 \quad (M_2=477056755369,\, \mathbf E=3) \ , \\ c_3 &=&347858820902 \quad (M_3=497269576663,\, \mathbf E=3) \ . \end{array}

Решение. Действуя по алгоритму 1 китайской теоремы об остатках, вычисляем сначала y_1,y_2 и y_{3} как решения сравнений:

\left(M_2M_3 \right)\cdot y_1 \equiv 1 \pmod{M_1}, \quad \left(M_1M_3 \right)\cdot y_2 \equiv 1 \pmod{M_2} \ , \quad \left(M_1M_2 \right)\cdot y_3 \equiv 1 \pmod{M_3} \ :
y_1=51916289816, \ y_2=76550650588,\ y_3=348670055330 \ .

Тогда

x^3 \equiv c_1y_1M_2M_3+c_2y_2M_1M_3+c_3y_3M_1M_2 \pmod{M_1M_2M_3} =
= 26066792334863472721295708043803736842001045048

и после вычисления остатка от деления последнего числа на M_1M_2M_3 получаем

x^3=5891607718400856907546317062286659 \ .

Извлечем из правой части корень кубический с помощью алгоритма теоремы, приведенной ☞ ЗДЕСЬ: если начать с числа B_0=10^{12}, то итерационная последовательность

B_j = \left\lfloor \frac{2}{3}B_{j-1} + \frac{B}{3B_{j-1}^2} \right\rfloor \ ,

за 9 шагов j_{} сойдется к значению x=180611170619.

§

С теоретической точки зрения подобная атака возможна и для других выборов показателя \mathbf E; однако же — по здравому размышлению о свойствах человеческой натуры — немыслимо вообразить ситуацию, когда некий секрет, одновременно доверенный, скажем, \mathbf E=65\,537 людям, не станет немедленным достоянием всего информационно озабоченного человечества…

Источники

[2]. Pollard J.M. Theorems on factorization and primality testing. Proc. Cambridge Phil.Soc. 1974. Vol. 76. P. 521–528.

1) Но, как правило, этого не происходит.
2) Cреди чисел множества \{0,1,\dots, \phi(M)-1 \}, удовлетворяющих условию алгоритма RSA
3) Отрывок из стихотворения «Der Lesende» Р.М.Рильке («За книгой», перевод Б.Пастернака).
4) Для применения теоремы числа M_1,M_2,M_3, разумеется, должны быть попарно взаимно простыми; однако при их построении как произведений пар случайно выбранных простых множителей вероятность нарушения этого условия пренебрежимо мала.

2013/12/09 21:44