!!§!! Вспомогательный раздел к разделу ((:crypto#криптография_с_открытым_ключом КРИПТОГРАФИЯ)).

----


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


~~TOC~~


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


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

<note warn>
Я не буду касаться различных технических аспектов и роли человеческого фактора для криптоанализа  (см. по этому поводу весьма перспективные разработки компании ((http://termorect.narod.ru/index.html "Терморектальный криптоанализ")) ). Предметом криптоанализа  в настоящем разделе является исключительно ((:crypto#алгоритм_rsa алгоритм RSA)).
</note>




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












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

Поллард ((#источники [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 $. ((:modular#теорема_ферма Теорема Ферма)) утверждает,
что 
$$ A^{p_1-1} \equiv 1 \pmod{p_1} \quad npu \quad \forall A\in \mathbb N,\ \operatorname{HOD} (A,p_1)=1 
\ .$$
Поскольку сравнения можно возводить в степень (см. ☞ ((:modular#сравнения ЗДЕСЬ))), тогда будет
$$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} $. 
Поскольку ( см. свойства сравнений ☞ ((:modular#сравнения ЗДЕСЬ))) 
$$ \operatorname{HOD} (A^Q-1,M) = \operatorname{HOD} \left(A^Q \pmod{M} -1 \ , M \right)
\ , $$
то вычисление $ A^{Q} $ имеет смысл сразу проводить по модулю $ M_{} $, 
творчески развив ((:modular#вычисление_остатков_степенных_выражений метод квадрирования-умножения)):
$$
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 $. <html>
  <font face="Times">
        <font color="#ff00ff" size="+1">♦</font>
  </font>
</html>

Понятно, что успех метода существенно зависит от величины $ 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\} \ ?
$$
Ответ отрицателен:

!!Т!!** Теорема.** //При любом выборе ключа шифрования//[[Cреди чисел множества $ \{0,1,\dots, \phi(M)-1 \} $, удовлетворяющих условию 
алгоритма **RSA**]]  $ {\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) $ --- ((:modular#теорема_эйлера обобщенная функция Эйлера)), 
будет также ключом дешифрования:
$$ 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)} \ . $$
<html>
  <font face="Times">
        <font color="#ff00ff" size="+2">♦</font>
  </font>
</html>




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

$$ 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-м шаге узнает ключ дешифрования. <html>
  <font face="Times">
        <font color="#ff00ff" size="+1">♦</font>
  </font>
</html>



**Практическая рекомендация.** Проверьте, чтобы для выбранных случайным
образом сомножителей $ 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_{} $. 

{{ crypto:nebo2.gif|}}
!!П!! **Пример.** Неподвижными точками отображения $ 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 $ получаем утверждение теоремы. <html>
  <font face="Times">
        <font color="#ff00ff" size="+1">♦</font>
  </font>
</html>






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


**Доказательство.**  Действительно, упомянутые точки являются
неподвижными точками отображения $ x^{2} \pmod{M} $,
т.е. решениями сравнения 
$$
x^2 \equiv x \pmod{M} \ .
$$
Эти решения легко вычисляются с помощью ((:numtheory#теорема_ферма теоремы Ферма)):
$$
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} $. <html>
  <font face="Times">
        <font color="#ff00ff" size="+1">♦</font>
  </font>
</html>

!!?!! Если $ 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 (см. теорему Эйлера <html>
  <font face="Times">
        <font color="#ff00ff" size="+2"> ☞

</font>
  </font>
</html>  ((:modular#двучленные_сравнения ЗДЕСЬ)) ). Берем всевозможные пары решений сравнений по модулям $ p_{1} $ и $ p_{2} $, каждая из них 
порождает единственное решение сравнения $ x^{\mathbf E} - x \equiv 0 \pmod{M} $,
которое может быть найдено по ((:modular:crt китайской теореме об остатках)). <html>
  <font face="Times">
        <font color="#ff00ff" size="+1">♦</font>
  </font>
</html>

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

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

По теореме получаем число инвариантных точек: $ (d_1+1)(d_2+1) =1200640085 $.                         
Насколько  оно велико? Отношение этого числа к числу $ M_{} $,
 потенциально возможных сообщений  $ \approx 0.3333 $, т.е. в среднем 
каждый третий блок открытого текста рискует быть незашифрованным. Примерно это 
и происходит при шифровании ключом $ ({\mathbf E},M) $ открытого 
текста[[Отрывок из стихотворения "Der Lesende" Р.М.Рильке ("За книгой", перевод Б.Пастернака).]]:

| А |  | к | р | а | й | н | я | я | | з | в | е | з | д | а | | в | | к | о | н | ц | е | | с | е | л | а | |
^ 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} $ останутся неизмененными. <html>
  <font face="Times">
        <font color="#ff00ff" size="+1">♦</font>
  </font>
</html>


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





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

В алгоритме **RSA** построения ключей шифрования и дешифрования, создателю ((:crypto#алгоритм_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} $,
проводимая по ((:modular#вычисление_остатков_степенных_выражений алгоритму квадрирования-умножения)), становится особенно легкой. Вдобавок при выборе $ \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 \ .$$
Тогда по ((:modular#китайская_теорема_об_остатках китайской теореме об остатках)) число $ x^{3} $ 
однозначно восстанавливается[[Для применения теоремы числа
$ M_1,M_2,M_3 $, разумеется, должны быть попарно взаимно простыми; однако при их построении как произведений пар __случайно__ выбранных простых множителей вероятность нарушения этого условия
пренебрежимо мала.]], а уж извлечь из него кубический
корень можно по алгоритму, изложенному <html>
  <font face="Times">
        <font color="#ff00ff" size="+2"> ☞

</font>
  </font>
</html>  ((:numtheory:issquare ЗДЕСЬ)). Итог: сами шифры не 
взламываются, но зашифрованное ими сообщение прочитывается!

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

**Решение.** Действуя по алгоритму <html>
  <font face="Times">
        <font color="#0000ff" size="+1">1</font>
    </font>
</html>
 ((:modular#китайская_теорема_об_остатках китайской теоремы об остатках)), вычисляем
сначала $ 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 \ .$$
Извлечем из правой части корень кубический с помощью алгоритма теоремы, приведенной <html>
  <font face="Times">
        <font color="#ff00ff" size="+2"> ☞

</font>
  </font>
</html>  ((:numtheory:issquare ЗДЕСЬ)): если начать с числа $ 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 $.

<note cert>
С теоретической точки зрения подобная атака возможна и для других
выборов показателя $ \mathbf E $; однако же --- по здравому размышлению о
свойствах человеческой натуры --- немыслимо вообразить ситуацию, когда
некий секрет, одновременно доверенный, скажем, $ \mathbf E=65\,537 $ людям,
не станет немедленным достоянием всего //информационно озабоченного// 
человечества...
</note>

==Источники==

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