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

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

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

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

Поллард [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} \ ; \ \mbox{ очевидно }, \ {\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_{} $ признается неудачным и выбирается другое значение¹⁾. Если $ \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 \mbox{ для }\ \forall x\in \{0,1,\dots,M-1 \} \ .$$ Можно ли, однако, утверждать единственность ключа дешифрования во множестве $$ \left\{0,1,\dots, \phi(M)-1 \right\} \ ? $$ Ответ отрицателен:

Теорема. При любом выборе ключа шифрования²⁾ $ {\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 \mbox{ для }\ \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) $ открытого текста³⁾:

Здесь выделенные блоки $ 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 \mbox{ или } \quad \mathbf E=2^{16}+1=65537 \quad \mbox{ или } \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} $ однозначно восстанавливается⁴⁾, а уж извлечь из него кубический корень можно по алгоритму, изложенному ☞ ЗДЕСЬ. Итог: сами шифры не взламываются, но зашифрованное ими сообщение прочитывается!

Пример. Восстановить открытый текст $ 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 $.

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