Атака на теорему Ферма с помощью криптocистeмы RSА

[ananova]

ananova в сообщении #314448 писал(а):

Поясню почему... $x$ ≢ $y \mod (z)$. Только в этом случае основное уравнение Ферма не имеет решений.

Нечётко выразился. Правильно так:
... Поясню почему... $x$ ≢ $y \mod (z)$. Только в этом случае основное уравнение Ферма может иметь "гипотетическое решение" и далее по тексту.

[sceptic]

ananova в сообщении #314448 писал(а):

Не спешите с выводами...

sceptic в сообщении #314401 писал(а):

Поэтому, при $z>N$ RSA не обещает выполнения $x^e \neq z^e (mod\verb

Если, при этом $N \neq x$ или $N \neq y$. Вернёмся к этому чуть позже.

Нет, коли $z>N$, то не имеет значение, $N=x$ или $N \neq x$ – после шифрования сообщений $y$ и $z$ вполне может случиться равенство $y^e=z^e (mod\verb. И как Вы будете переходить к противоречию с $x^e+y^e=z^e$ в этом случае?
То же самое справедливо и для равенства/неравенства $N$ и $y$.
Вы обещаете вернуться к этому позже. Что ж, ждем-с.

ananova в сообщении #314448 писал(а):

Так что RSA помогло понять, что из исходных сообщений невозможно получить:
$x^e \equiv z^e$ \mod (y), которое "обещает" решение уравнения.

В Ваших статьях не нашел доказательства невозможности получения $x^e \equiv z^e (mod\verb. Может быть, представите здесь?

[ananova]

sceptic

sceptic в сообщении #314627 писал(а):

Нет, коли $z>N$, то не имеет значение, $N=x$ или $N \neq x$ – после шифрования сообщений $y$ и $z$ вполне может случиться равенство $y^e=z^e (mod\verb. И как Вы будете переходить к противоречию с $x^e+y^e=z^e$ в этом случае?

Я не рассматриваю в статье случая $z>N$, но, если N=x, то y + N > z. Согласны?

$y$ ≢ $z \mod (N)$. Согласны?

sceptic в сообщении #314627 писал(а):

В Ваших статьях не нашел доказательства невозможности получения $x^e \equiv z^e (mod\verb. Может быть, представите здесь?

На самом деле - это нужно делать? Ведь в основном сравнении $x^e+y^e+z^e \equiv 0 \mod (y)$ все переменные равноправны.

[sceptic]

ananova в сообщении #314708 писал(а):

Я не рассматриваю в статье случая $z>N$, но, если N=x, то y + N > z. Согласны?

$y$ ≢ $z \mod (N)$. Согласны?

Согласен. Но что дальше? Отсюда вовсе не следует, что $y^e \neq z^e (mod\verb (точнее, шифрование RSA не гарантирует этого), к чему Вы стремитесь.

ananova в сообщении #314708 писал(а):

sceptic в сообщении #314627 писал(а):

В Ваших статьях не нашел доказательства невозможности получения $x^e \equiv z^e (mod\verb. Может быть, представите здесь?

На самом деле - это нужно делать? Ведь в основном сравнении $x^e+y^e+z^e \equiv 0 \mod (y)$ все переменные равноправны.

Нет, не равноправны. Вы же ввели упорядочивание переменных $6<x<y<z$ (тем самым неявно перейдя к классической форме уравнения Ферма).

[ananova]

sceptic в сообщении #314817 писал(а):

Согласен. Но что дальше? Отсюда вовсе не следует, что $y^e \neq z^e $ (точнее, шифрование RSA не гарантирует этого), к чему Вы стремитесь.

Представьте, что у Вас два текста - не важно больших или маленьких. Они разные. Если Вы или кто-то другой используете один и тот же ключ шифрования, то Вы или (кто бы то нибыл)- никогда, повторяю никогда-никогда, не получите два одинаковых текста, какой бы ключ RSA не был маленьким или каким бы он бы не был очень большим.

И наоборот, если у Вас есть только один зашифрованный текст, и Вы используете пару чисел ($d,N$) в качестве ключа-расшифрования, то Вы и никто другой никогда, повторяю - никогда-никогда не получите два разных исходных сообщения из одного и того же зашифрованного текста. При этом неважно - сверх большие ключи или крохотные.

У нас с Вами, точнее у всех нас - два разных сообщения $z$ и $x$. ключ ($e, N=y$). Этого достаточно, чтобы система RSA работала. Одно тут важно... она будет работать, если НОД ($e$, функция Эйлера от $N=y$)=1. Об этом в статье написано. Кроме того, $x$ и $z$ должны быть взаимно просты с $N=y$. Об этом тоже написано.

Поэтому RSA, а точнее - функция Эйлера, которая является базисом RSA гарантирует то, что написано.

[ananova]

Можно добавить, что исходным является поле целых чисел $S_N$. Каждый элемент этого поля взаимно прост с числом, образующим это поле - $N$.

НОД ($x,y,z$)=1 в ВТФ, поэтому если $x=N$, то $y$ и $z$ будут элементами поля $S_N$.

Количество элементов $S_N$ соответствует значению функции Эйлера ($N$). Количество элементов поля $S_N$ равно количеству элементов поля $S_{N^E}$, образованного операцией возведения каждого элемента поля $S_N$ в степень $e$ по модулю $N$. Все элементы поля $S_{N^E}$, являются перестановкой элементов поля $S_N$, то есть не равны друг-другу.

Поэтому, если два элемента поля $S_N$ не равны между собой, то соответствующие этим элементам члены поля $S_{N^E}$ тоже никогда не будут равны между собой. Т.к. эти два поля целых чисел отличаются только перестановкой элементов.

С помощью числа $d$ можно восстановить первоначальную перестановку.

[sceptic]

ananova в сообщении #314835 писал(а):

Представьте, что у Вас два текста - не важно больших или маленьких. Они разные. Если Вы или кто-то другой используете один и тот же ключ шифрования, то Вы или (кто бы то ни был)- никогда, повторяю никогда-никогда, не получите два одинаковых текста, какой бы ключ RSA не был маленьким или каким бы он бы не был очень большим.

И наоборот, если у Вас есть только один зашифрованный текст, и Вы используете пару чисел ($d,N$) в качестве ключа-расшифрования, то Вы и никто другой никогда, повторяю - никогда-никогда не получите два разных исходных сообщения из одного и того же зашифрованного текста. При этом неважно - сверх большие ключи или крохотные.

Благодарю за приведенные азы, но здесь они излишни: с RSА я познакомился еще в 1978 г. по известной статье Диффи и Хеллмана. Позвольте и мне напомнить Вам некоторые важные детали шифрования RSА, поскольку Вы, по-видимому, невнимательно читали описание этой криптocистeмы. При шифровании RSА с открытым ключем $(e,N)$ текст $t$ зашифровывается в $t^e(mod\verb лишь при $t<N$. В случае $t>N$ текст $t$ разбивается на блоки $t_1,...,t_k$, для каждого из которых справедливо $t_i<N$; затем каждый блок зашифровывается: $t_i \to t_i^e(mod\verb - обозначим их, скажем, как $s_i$; окончательно, в качестве результата зашифровывания текста $t$ предъявляется конкатенация $s_1...s_k$. Надеюсь, Вы замечаете, что $s_1...s_k$ весьма далека от $t^e(mod\verb?
Поэтому, когда вы утверждаете, что $x^e \neq z^e (mod\verb или $y^e \neq z^e (mod\verb (при $z>N$), то не ссылайтесь на RSА, а предъявляйте доказательство!

[ananova]

sceptic
Раз всё Вам понятно, тогда ещё раз хочу подчеркнуть, что 2-сообщения у нас таковы, что они меньше чем ключ, т.к. оба являются элементами поля, порождаемым третьим числом. Поэтому на блоки нам не надо ничего делить.

Приведу пример. Пусть у нас три числа: $x$ -нечётное, $y$- чётное и 2.

имеем $x$ ≢ $y \mod (2)$.

$x$ и $y$ принадлежат полю, порождённому числом 2:

НОД ($e$, Функция Эйлера (2))=1

Тогда $x^e$ ≢ $y^e \mod (2)$.

Как видим, нам не пришлось делить числа $x$ и $y$ на блоки, чтобы доказать, что в степени $e$, числа несравнимы между собой (хотя и $x$ и $y$ больше 2).

Не будем использовать топор, чтобы открыть бутылку "Кока-колы".

Более того, я ничего не хочу доказывать, я просто сделал вывод, что, если тройка Ферма такова, что является аналогом ключевой системы RSA, то из этого вытает, что все свойства RSA распространяются на неё. Что тройка чисел является аналогом системы RSA многого доказывать не надо. - Первое - это то, что сообщения являются взаимнопростыми со вторым числом ключа (которое используется в качестве модуля, первое число - показатель степени), второе - это то, что числа несравнимы между собой по модулю ключа, т.е. сообщения - разные. Третье, - чтобы функция Эйлера одного из чисел и показатель степени не имели общих множителей. Всё.

Общее условие можно записать так: Если НОД ($\psi (x), \psi (y), \psi (z), e$)=1, то основное уравнение Ферма не имеет решений.

Задача доказывать работу RSA выходит за эти рамки. А у меня создалось такое впечатление, что Вы ставите передо мной именно эту задачу. Не думаю, что среди посетителей форума найдутся такие, которые не смогут отыскать в Интернет теоретические основы работы RSA, а если необходимо и доказательство всех его свойств.

Честно говоря, эти прописные истины я не Вам пишу, а только тем, кто сталкивается с этим впервые, чтобы им было всё понятно, что к чему.

Могу добавить, в качестве оффтопика, что в 2008 году (на уровне подсознания) пришло понимание этого поведения чисел ($x,y,z$) в сравнениях. Затем несколько месяцев был занят поиском системы, которая бы это поведение чисел описывала. Так поиск привёл к RSA. Именно так, а не наоборот, появился этот результат. Хотя, с RSA и статьей Диффи-Хеллмана я был знаком значительно раньше.

[sceptic]

ananova в сообщении #314999 писал(а):

Раз всё Вам понятно, тогда ещё раз хочу подчеркнуть, что 2-сообщения у нас таковы, что они меньше чем ключ, т.к. оба являются элементами поля, порождаемым третьим числом. Поэтому на блоки нам не надо ничего делить.

Мягко говоря, Вы вводите публику в заблуждение. В своей первой статье Вы прямо пишете:

"Сначала рассмотрим результаты шифрования ключа $(e,mod\verb.
Числа-сообщения: $y\verb и $-z\verb. Напомним, что, согласно исходных арифметических ограничений ВТФ: $y\neq z\verb. НОД$(x,y,z)=1$, $x>6$.
Криптограммы: $y^e mod\verb и $(-z)^e mod\verb.
Противоречие с арифметическими ограничениями ВТФ. Разные сообщения: $y\verb и $-z\verb, зашифрованные одним и тем же ключом, дают разные криптограммы: $y^e mod\verb и $(-z)^e mod\verb: $y^e \neq (-z)^e mod\verb. Сравнимость невозможна. (В общем-то, для криптосистемы было бы абсурдно, если бы два разных сообщения, зашифрованных одним и тем же ключом, давали бы одинаковые криптограммы.)"

Абзацем выше в статье Вы зафиксировали упорядочивание $x<y<z$. Т.е. открытый ключ шифрования ($N=x$) меньше сообщений ($y, z$). Итак, налицо фальсификация: в качестве зашифрованных сообщений $E(y), E(z)$ Вы "подсовываете" $y^e mod\verb и $(-z)^e mod\verb. Нехорошо!
Аналогичная картина при выборе ($N=y$): здесь неправомерно считать $E(z) = (-z)^e mod\verb. Лишь при $N=z$ Вы шифруете корректно: $E(x) = x^e mod\verb и $E(y) = y^e mod\verb. И верно $x^e \neq y^e mod\verb. Но как это противоречит уравнению Ферма, не ясно. Ведь из него следует всего лишь сравнение $x^e+y^e=0\verb.

ananova в сообщении #314999 писал(а):

Приведу пример. Пусть у нас три числа: $x$ -нечётное, $y$- чётное и 2.
имеем $x$ ≢ $y \mod (2)$.
$x$ и $y$ принадлежат полю, порождённому числом 2:
НОД ($e$, Функция Эйлера (2))=1
Тогда $x^e$ ≢ $y^e \mod (2)$.
Как видим, нам не пришлось делить числа $x$ и $y$ на блоки, чтобы доказать, что в степени $e$, числа несравнимы между собой (хотя и $x$ и $y$ больше 2).

А это обнадеживает. Наконец-то Вы вняли моему призыву доказывать что-то без отсылки к RSA. Жаль только, пример не имеет отношения к ВТФ (приведенная тройка$x,y,2$ не является решением уравнения Ферма ни при каком $e>2$).

ananova в сообщении #314999 писал(а):

Более того, я ничего не хочу доказывать, я просто сделал вывод, что, если тройка Ферма такова, что является аналогом ключевой системы RSA, то из этого вытает, что все свойства RSA распространяются на неё. Что тройка чисел является аналогом системы RSA многого доказывать не надо. - Первое - это то, что сообщения являются взаимнопростыми со вторым числом ключа (которое используется в качестве модуля, первое число - показатель степени), второе - это то, что числа несравнимы между собой по модулю ключа, т.е. сообщения - разные. Третье, - чтобы функция Эйлера одного из чисел и показатель степени не имели общих множителей. Всё.

Опять у Вас путаница в терминологии. Криптосистема RSA определяется числами $e,N,d$ ($e,N$ - открытый ключ шифрования, $d$ - секретный ключ расшифрования), с условиями $(e, \varphi(N))=1, ed = 1\verb. Tройка чисел гипотетического решения уравнения ферма $x^e+y^e = z^e$ может лишь рассматриваться в качестве сообщений, шифруемых в рамках этой системы (а не "аналогом" параметров криптосистемы). И чтобы не потерять информацию (содержащуюся в уравнении Ферма) при шифровании чисел тройки, на криптосистему RSA накладываются ограничения: $N>x, N>y, N>z, (xyz,N)=1$. А дальше - полный вперед! Исследуйте полученные сравнения, используя соотношения Барлоу, технику Софи Жермен, Лежандра и т.д. Сомневаюсь, что Вы найдете в этой трясине что-то новенькое, но - "надежды юношей питают"!
А Вы - "более того, я ничего не хочу доказывать". А для чего Вы тогда накропали эти свои статьи? Ведь привлечение криптосистемы RSA к ВТФ - это всего лишь своеобразный фантик для конфеты. Вы и завернули конфету криво, и конфету не обещаете! Я огорчен .

ananova в сообщении #314999 писал(а):

Задача доказывать работу RSA выходит за эти рамки. А у меня создалось такое впечатление, что Вы ставите передо мной именно эту задачу. Не думаю, что среди посетителей форума найдутся такие, которые не смогут отыскать в Интернет теоретические основы работы RSA, а если необходимо и доказательство всех его свойств.

Это только впечатление. Никто не требует от Вас объяснять, как работает RSA. Я хотел лишь, чтобы Вы, коли привлекаете криптосистему RSA к ВТФ, использовали ее корректно.

[ananova]

С каждым Вашим постом, Вы подтверждаете, что никогда не согласитесь со мной, даже если я напишу, что белое - это белое, а чёрное - это чёрное? Ну или согласитесь, но через раз, но всё равно не полностью. Ну хорошо. Давайте продолжим дискуссию вокруг точек и запятых.

Образно о доказательстве можно написать так: если у некоторой системы, при показателе 1, выполняется сравнение белое - белое, и есть однозначно определяющая операция, которая переводит путём возведения в степени $e$ - белое - в чёрное, то вы получите сравнение: чёрное-чёрное и никаких других вариантов. Если у Вас в первой степени - белое-черное, то получите в степени $e$: черное-белое.

sceptic в сообщении #315500 писал(а):

Абзацем выше в статье Вы зафиксировали упорядочивание $x<y<z$. Т.е. открытый ключ шифрования ($N=x$) меньше сообщений ($y, z$).

Если я так написал, то значит это правильно. Действительно ключ шифрования меньше сообщений y и z. Но для моего доказательства это неважно. Могу ещё раз повторить - неважно. Вы когда доказываете - число чётно или нечётно, используете сравнения насколько больше или меньше двух Ваши числа? Уверен, что не используете. Вы используете только свойство - кратно или не кратно. И только этим можете доказать отсутствие решений в определенных уравнениях. Именно так и строится критикуемое Вами доказательство. Т.е. я хочу сказать, что Вы используете политику двойных стандартов. Т.е. Вам можно использовать проверку на чётность, а мне нельзя использовать сравнимость по свойствам модуля. Именно не по модулю, а по свойствам числа, используемого в качестве модуля.
Если глубоко копнуть, то проверка на чётность вытекает из этих же свойств числа 2 и была попытка донести до Вас подобность операции.

Если Вы мне поможете правильно внести формулировку, чтобы было не только понятно Вам, но и другим, потенциальным читателям, то буду весьма признателен. Надеюсь, что Вы поймёте и поможете мне сформулировать, если я написал непонятно. Моя мысль такова - "$y$ и $z$" - не сами, а их вычеты (это уточнение для Вас), принадлежат полю, которое создано числом $x$. Я полагал, что это без объяснений понятно. Но раз Вам непонятно, то это, вероятно ещё кому-то непонятно, поэтому требует правильной переформулировки, понятной для всех именно в таком смысле который я сейчас Вам подробно расписал.

sceptic в сообщении #315500 писал(а):

Итак, налицо фальсификация: в качестве зашифрованных сообщений $E(y), E(z)$ Вы "подсовываете" $y^e mod\verb и $(-z)^e mod\verb. Нехорошо!

Ну вот, опять не разбобравшись обвиняете в чём? Мы имеем дело с вычетами, которые принадлежат полю, созданному числом $x$. Если написано у меня, что $y^e \mod x$ - является зашифрованным сообщением, то для Вас глубоко понимающим математику должно быть понятно, что здесь имеется ввиду трактовка - "шифрование" вычета сообщения. Так как извините,.... понятно, что здесь имеется ввиду не само число y, а его вычет. Именно оно подается в статье не как само число, а как вычет, т.к. связано знаком сравнения, а не равенства. Т.к. $x$ меньше $y$ и сообщение, в том виде в котором оно существует - не может быть однозначно зашифровано и восстановлено. Я понял, что это Вас серьёзно тревожит и Вы воспринимаете это, как существенный пробел в доказательстве. На самом деле, это не так. Достаточно уточнить, что автор имеет ввиду значения вычетов, а не целиком сообщений. Эти вычеты, выступают в роли лакмусовых бумажек, которые проверяют при их шифровании и расшифровании, поведение чисел в поле, созданном возведением в степень $e$. Если я пишу про целиком сообщения и понимаю, что все понимают, что это лакмусовые бумажки, а не целиком сообщения, то это дело такое - авторское. Если надо я уточню. Т.к. доказательство сути этого не меняет абсолютно. Мы же доказываем не взаимо однозначное соответствие, а свойства параметров.

Постарайтесь не зацикливаться на этом. Я понял Вашу мысль, но она тут не является ключевой в доказательстве, хотя замечание я постараюсь обдумать и внести более понятную для всех терминологию, если посчитаю это нужным и не получу какие-то дополнительные рекомендации от других форумчан. Кто его знает - может всем всё понятно без комментариев.

sceptic в сообщении #315500 писал(а):

И верно $x^e \neq y^e mod\verb. Но как это противоречит уравнению Ферма, не ясно. Ведь из него следует всего лишь сравнение $x^e+y^e=0\verb.

Прошу Вас считать это ключевым моментом доказательства. Вы ведь знаете, что если существует гипотетическое решение в уравнении Ферма, то выполняется последнее написанное Вами сравнение. Так? В тоже время, мы знаем, что в первой степени мы имеем несравнимые аргументы уравнения. Между этими фактами существует прямая связь.
Вернитесь к началу этого поста - про белое-чёрное. Это об этом. Если Вы считаете что существует гипотетическое решение в уравнении, то в сравнении будет равенство, Вы правы. Но тогда и я прав, что это сравнение было получено из сравнимых между собой чисел. А это невозможно, т.к. нарушается основные арифметические ограничения ВТФ. Если Вы имеете математические операции и теорию, которые однозначно показывают, что прийти к сравнимости в поле чисел в степени $e$, используя их, нет возможности, то почему их не использовать в доказательстве?

Ваш совет использовать $N$ > тройки чисел тривиален для меня, т.к. я сам призывал это делать Вас пару постов назад, но Ваш совет, возможно, заинтересует кого-то из читателей. Это Вам в плюс!

Доказательство, которое Вы раскритиковали, действительно строится на фундаментальных основах, которые использует система RSA и эти фундаментальные основы позволяют однозначно утверждать, что несравнимые числа по модулю числа, имеющие функцию Эйлера не кратную степени, будут несравнимы и в этой степени. Вы можете считать это глумлением над чистотой фразеологии RSA, но это уж Ваше право. Я, право, не считаю это глумлением, а дополнительным плюсом её возможностей.

[ananova]

ananova в сообщении #315585 писал(а):

эти фундаментальные основы позволяют однозначно утверждать, что несравнимые числа по модулю числа, имеющие функцию Эйлера не кратную степени, будут несравнимы и в этой степени

Правильно читать:

эти фундаментальные основы позволяют однозначно утверждать, что несравнимые числа по модулю числа, имеющие функцию Эйлера взаимно простую со степенью, будут несравнимы и в этой степени

[ananova]

Вношу правки в статью, основанные на замечаниях sceptic.

1) заменяю фразу - "для доказательства впервые используется криптографическая система RSA"

на фразу: "впервые используются фундаментальные основы криптографической системы RSA"

2) $6 < x < y < z$
заменяю на
$6$ < ($x$ or $y$ or $z$)

3) ключи шифрования $e$, mod $x$,...
на
ключи шифрования ($e,x$)

4) Числа-сообщения: $y$ mod ($x$) и $-z$ mod ($x$).

меняю на

Числа-сообщения - математические вычеты: $y$ mod ($x$) и $-z$ mod ($x$).
...

5) добавление знака минус в сравнения:
По ключам ($e, y$) и ($e, z$), для сообщений: $x \mod (y)$ ≢ $-z \mod (y)$ и $x \mod (z)$ ≢ $-y \mod (z)$, также получаются различные криптограммы.

6) Добавляю слово "вычетов":
В таком случае возможно создание криптосистемы RSA, хотя бы по одному числу из тройки $x, y, z$, когда абсолютно все результаты шифрования вычетов противоречат известным арифметическим ограничениям ВТФ.

7) Уточняю вывод доказательства:

Если хоть одно из чисел $x, y, z$ не имеет значение функции Эйлера, которое не взаимно просто с $e$, то теорема Ферма справедлива для всей тройки чисел, т.е. основное уравнение Ферма не имеет решений. Например, если одного из чисел $x,y,z$ является простым вида $2^e+1$, то его функция Эйлера не кратна никаким значениям $e$ [4].

Пока всё.

[ananova]

В последнем пункте переборщил с отрицаниями не (сам себя запутал). Правильно их убрать совсем, т.е.: "имеет значение функции Эйлера, которое взаимно просто с e"

[sceptic]

Вся моя критика основывалась на мнении, что Вы при шифровании RSA в качестве сообщений берете числа $x, y, z$ (при различных открытых ключах $N$) из гипотетического нетривиального решения уравнения ферма $x^e+y^e=z^e$. Из текста статьи не было видно, что сообщениями являются не сами числа, а их вычеты по модулю $N$. Спасибо, ananova, теперь разъяснили. Вижу, вы вносите поправки в статью. Тогда сразу предлагаю обозначать вычеты иначе, чем целые числа. Например так: $\bar x$ (модуль можно не указывать, если из контекста ясно, по какому модулю берется вычет). И, если не трудно, перейдите на общепринятое обозначение $(mod\verb вместо вашего $mod\verb.
В свете нового взгляда на текст статьи ananova беру паузу до вечера.

[ananova]

ananova в сообщении #315778 писал(а):

Вся моя критика основывалась на мнении,

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