Система сравнений, теорема об остатках

[Nurzery[Rhymes]]

Захотелось реализовать криптосистему RSA для экспериментов с атакой Винера, готово почти все, кроме функции дешифрования. Для ускорения дешифрования использую теорему об остатках - представляю одно число по модулю pq, которое получится в результате декодирования, в виде системы двух сравнений по модулям p и q.

Система сравнений получилась такая:

$\left\{ \begin{array}{rcl} &D_p={C^d} \mod p = C^{d \mod p-1} \mod p& \\ &D_q ={C^d} \mod q = C^{d \mod q-1} \mod q& \\ \end{array} \right.$

Здесь $C$ - зашифрованное сообщение, $d$ - ключ дешифрования, $p,q$ - множители модуля, по которому производятся вычисления.

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

$\left\{ \begin{array}{rcl} &x\equiv a (\mod p)& \\ &x \equiv b (\mod q)& \\ \end{array} \right.$
Из первого сравнения выражаю $x$: $x = a+tp$
Подставляю во второе сравнение: $a+tp \equiv b+nq$ и дальше не могу ничего придумать. Подскажите, как вывести общее решение для любой подобной системы.

[Cash]

Посмотрите китайскую теорему об остатках

[Nurzery[Rhymes]]

Cash в сообщении #938196 писал(а):

Посмотрите китайскую теорему об остатках

Я помню, как решал системы сравнений по этой теореме, но я не могу вывести формулу, когда вместо чисел буквы. Я так понимаю эту теорему, если не углубляться в ее значение из теории колец: система сравнений по модулям $p, q$ имеет решение по одному модулю $pq$. Но как свести систему к одному сравнению, которое можно легко решить?

[provincialka]

Что-то вроде алгоритма Евклида
Явной формулы не получится, разве что итерационный процесс.

[Nurzery[Rhymes]]

Вчера я пытался вывести формулу, по которой можно восстановить число по его остаткам от деления на числа $p$ и $q$, вот что получилось:

$\left\{ \begin{array}{rcl} &x \equiv a_1 (\mod m_1)& \\ &x \equiv a_2 (\mod m_2)& \\ \end{array} \right.$

Общий модуль: $M=m_1 m_2$
Частные модули:
$M_1 = M/m_1=m_2$
$M_2=M/m_2=m_1$

Дальше понадобятся решения сравнений $M_i N_i \equiv 1 (\mod m_i)$

Для системы $\left\{ \begin{array}{rcl} &x \equiv a_1 (\mod p)& \\ &x \equiv a_2 (\mod q)& \\ \end{array} \right.$
Имеем: $M=pq, M_1=q, M_2=p$

1) $q N_1 \equiv 1 (\mod p)$, $N_1 = q^{-1} \mod p$
2) $p N_2 \equiv 1 (\mod q)$, $N_2 = p^{-1} \mod p$

Решение системы получается как сумма $x=a_1 N_1 M_1 + a_2 N_2 M_2 (\mod pq)$
В чем ошибка?

[provincialka]

А у вас $p$ простое? Если нет, то не у каждого $q$ есть обратный элемент. Если да - дело за малым -- найти эти обратные элементы.

[Nurzery[Rhymes]]

provincialka в сообщении #938231 писал(а):

А у вас $p$ простое? Если нет, то не у каждого $q$ есть обратный элемент. Если да - дело за малым -- найти эти обратные элементы.

Да, я брал $p$ и $q$ из списка простых чисел. Функция нахождения обратного элемента у меня работает верно для тех чисел, которые я проверял, должно и для других чисел правильно вычислять обратные.

[provincialka]

Хм... А почему вы для проверки вычисления обратных используете тест? А не проверяете сам алгоритм?

[Nurzery[Rhymes]]

Меня еще очень заинтересовала функция дешифрования в быстрой реализации RSA. В статье, которую я читал, были такие вычисления:

$\left\{ \begin{array}{rcl} &x={C^d} \mod p = C^{d \mod p-1} \mod p& \\ &y ={C^d} \mod q = C^{d \mod q-1} \mod q& \\ \end{array} \right.$

Вычисляем обратный элемент для $q$ по модулю $p$: $q_{inv} = q^{-1} \mod p$
$h = ((x-y)\cdot q_{inv}) \mod p$

Дешифрованный блок получается по формуле $y+hq$
Что это за магия? Это так решается система сравнений, или здесь использована какая-то другая теория?

-- 30.11.2014, 12:42 --

provincialka в сообщении #938235 писал(а):

Хм... А почему вы для проверки вычисления обратных используете тест? А не проверяете сам алгоритм?

Я его реализовывал по словесному описанию из учебника, там должно быть все верно. Не так сложно реализовать расширенный алгоритм Евклида, у меня он даже в матричной форме где-то есть.

[provincialka]

Че-то не поняла. Вам даны $x,y,d$, а найти надо $C$? Почему же к ответе вида $y+hq$ не участвует $d$? Или это еще не $C$, а какой-то промежуточный результат?

[Nurzery[Rhymes]]

provincialka в сообщении #938242 писал(а):

Че-то не поняла. Вам даны $x,y,d$, а найти надо $C$? Почему же к ответе вида $y+hq$ не участвует $d$? Или это еще не $C$, а какой-то промежуточный результат?

Не совсем. Дано $C$ и $d$ - дешифрующая экспонента. Можно просто вычислить $C^d=(P^e)^d=P^1=P$ (т.к. $e$ и $d$ взаимно обратны в кольце), но для ускорения дешифровки мы разлагаем шифротекст на два числа (та самая система) и из этой системы каким-то образом получаем открытый текст P.
$C$ - зашифрованный блок. Надо найти исходный, он оказывается равен $y+hq$. Число $d$ участвует в вычислении $x$ и $y$, которые используются дальше.

[provincialka]

А! Вам бы стоило сказать это сразу, вряд ли много участников работали с проблемой именно в такой постановке.
Если так, в чем же дело? Проверьте является ли выписанная сумма решением системы сравнений.

[Nurzery[Rhymes]]

provincialka в сообщении #938270 писал(а):

А! Вам бы стоило сказать это сразу, вряд ли много участников работали с проблемой именно в такой постановке.
Если так, в чем же дело? Проверьте является ли выписанная сумма решением системы сравнений.

Не является :(
Может, я неправильно понял, как восстанавливается сообщение из системы в пункте "Использование китайской теоремы об остатках для ускорения расшифрования"? http://ru.wiki2.org/wiki/RSA
Предполагаю, что $m_p$ и $m_q$ - это вовсе не обозначения для двух разных чисел, а некоторое число $m$, взятое по модулям $p$ и $q$. Остается только решить эту систему относительно $m$...

[Cash]

Вы все правильно поняли. $2n$-битовое число можно однозначно задать с помощью 2-х $n$-битовых взаимно простых чисел. Соответственно для операций с числами в два раза короче (в данном случае возведение в квадрат) мы получаем существенный прирост скорости.

-- Вс ноя 30, 2014 14:34:38 --

Cash в сообщении #938284 писал(а):

Предполагаю, что $m_p$ и $m_q$ - это вовсе не обозначения для двух разных чисел, а некоторое число $m$, взятое по модулям $p$ и $q$. Остается только решить эту систему относительно $m$...

Не пойму, у Вас остались вопросы по восстановлению?

Upd.
хотя насчет существенного я поторопился. Грубо прикидывая, для возведения в квадрат $2n$ битового числа требуется $2n\ln{2n}$ против $2n\ln n$ операций во втором случае. Прирост если и есть, то небольшой.

[Nurzery[Rhymes]]

Cash в сообщении #938284 писал(а):

Не пойму, у Вас остались вопросы по восстановлению?

Да, формула, которую я записал для решения системы в самом начале, не дает исходное число. Там же все верно? Может быть, ошибка у меня в коде, а не в формулах?