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

§

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

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

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

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

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

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

!

Я не буду касаться различных технических аспектов и роли человеческого фактора для криптоанализа (см. по этому поводу весьма перспективные разработки компании "Терморектальный криптоанализ" ). Предметом криптоанализа в настоящем разделе является исключительно алгоритм 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$ , разумеется, должны быть попарно взаимно простыми; однако при их построении как произведений пар случайно выбранных простых множителей вероятность нарушения этого условия пренебрежимо мала.

А		к	р	а	й	н	я	я		з	в	е	з	д	а		в		к	о	н	ц	е		с	е	л	а
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

А		к	р	а	й	н	я	я		з	в	е	з	д	а		в		к	о	н	ц	е		с	е	л	а
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

А		к	р	а	й	н	я	я		з	в	е	з	д	а		в		к	о	н	ц	е		с	е	л	а
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