Реферат: Научные проблемы Интернета

или, что эквивалентно:

, .

(1.8)

В неравенстве с положительной правой частью выделим член с минимальным по модулю коэффициентом и разрешим неравенство относительно этого члена:

, .

Отсюда легко получить отсекающее неравенство:

(a) , (b) , (c) .

(1.9)

Здесь z – новая целочисленная переменная. Заметим, что переход от (a) к (b) в (1.9) правомерен, так как r , d , z – целочисленны.

Выполним подстановку (3.9) в систему (1.8). Получим новую систему:

, .

(1.10)

Обратим внимание на следующее принципиальное обстоятельство. В сравнении с (1.8) значение минимального коэффициента понизилось. Этот факт можно строго обосновать. Следовательно, весь процесс должен закончиться рано или поздно одним из двух результатов:

1) минимальный коэффициент по модулю станет равным 1 (как в (1.10)); будет получена система вида

,

,

где a и b – взаимно просты (в этом случае нет решения в целых числах).

В первом случае процесс решения завершен. Получаем из (1.10) подстановку для d :

.

(1.11)

Тогда из (1.9) найдем:

.

(1.12)

Итак, формулы (1.11) и (1.12) и дают нам итоговые подстановки для d и r из (1.7). Например, пусть . Тогда , . Возьмем именно это значение для минимального d .

Итак, мы подошли к решающему моменту: наш секретный ключ . Получили число , , .Восстанавливаем x по формуле:

.

(1.13)

Итак, .

Все сошлось. Возьмем, например, . Тогда , :

(ответ тот же).

Таким образом, не имеет значения, какое z брать для получения d .

Метод RSA мы завершим следующим замечанием.

Метод RSA вообще говоря требует, чтобы m было большим простым числом. Для установления факта, что m – простое, можно использовать малую теорему Ферма:

.

(1.14)

В (1.14) a и p должны быть взаимно просты, а p – простое число.