КОММЕНТАРИИ, КРИТИКА И ЗАМЕЧАНИЯ

ПО СТАТЬЕ

“КРИПТОСИСТЕМА RSA ПРОТИВ ВТФ”

 

 

Автор весьма признателен всем, кто помог  уточнить формулировки и дать полезные замечания.

 

Актуальная версия статьи размещена по адресу:

http://www.2000.ru/fermats/2000ru_vsm_rsa1a_01_04_2010.htm

        

Форум: dxdy.ru

Замечание по сути,  - критический пересмотр доказательной части статьи с более строгим (детальным) выводом полученного результата. (Наибольший общий делитель обозначается только скобками) .

===== 14.05.2010 г. =====

Пусть для простого e  > 2

+ =   (1),

 z > y > x > 0 (2),

(x, y) = (x, z) = (y, z) = 1 (3)

Пусть (e, φ(x)) = 1 (4).

Рассмотрим сравнения по (mod x).

Введём обозначения  = y (mod x),  = z (mod x).

Из (1) и (2) ⇒ x+y > z (5) ⇒  ≠ .

Если  = , то  x|(z–y), т.е. (z–y) = kx для некоторого целого k;

т.к. z > y, то k ≥ 1 ⇒ z – y ≥ x, что противоречит (5).

Следовательно и   ≢   (mod x), принимая во внимание (4) и фундаментальные основы RSA на базе функции Эйлера, можно условно считать, что  и  – (математические вычеты) являются исходными сообщениями для последующего шифрования, а  и  (вычеты степени e по модулю x) – криптограммы. Результатом шифрования двух разных сообщений (с использованием одного и того же ключа шифрования) будут разные криптограммы.

  =  (mod x),  =  (mod x), а исходя из уравнения (1) ⇒

 ≡   (mod x). Налицо противоречие. Следовательно, невозможно выполнение (4) (в предположении существования примитивного решения уравнения Ферма). Т.е. доказано: (e, φ(x)) = e.

Аналогично доказывается (e, φ(y)) = e (все выкладки проводятся с  (mod y).

Пусть (e, φ(z)) = 1 (6). Переходим к вычислениям по (mod z).

Из (2) ⇒ 2z > x+y > z. Т.е.  +  ≢ 0 (mod z) ⇒  ≢ z –  (mod z).

(z –  – это вычет (–y) по (mod z); приходится следить за знаками, поскольку работаем с приведённой системой вычетов: 0 ≤   < z). Вновь мы вправе рассчитывать на сохранение неравенства при возведении в степень е (mod z). Помним, что мы предположили (6), тогда по подобию RSA:

 ≢  (z–  (mod z), а это означает  ≢ – (mod z), (помним, что e – нечётно). Опять приходим к противоречию с + (mod ), вытекающему из (1). Следовательно доказано: (e, φ(z)) = e.

 

Contact:

S.M. Vakhterov,  student, Moscow State Technical University n.a. N.E. Bauman

M.I. Vakhterov, editor

http:// www.2000.ru/fermats/fermats_rsa_comments_vakhterov.htm

 

Last Modified: May, 14, 2010