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

[ananova]

Добрый день!

Как и обещал, выкладываю статью, которая является завязкой для общего доказательства.

Суть перескажу лучше "на пальцах".

Если у Вас есть 1 ключ шифрования, а сообщения разные, то в результате Вы получите две криптограммы. И они будут разные. Соответственно, если исходный текст одинаков, то криптограммы одинаковые. Если зашифровать разные числа одним ключом, то получим два числа, которые будут не равны друг-другу.

Числа $x, y, z$ взаимнопростые, как это доказано другими авторами,
а $z>y>x>6$, как это было доказано в этой теме:
http://dxdy.ru/topic30942.html

Можно создавать на этой базе "криптографическую систему". В качестве ключей для шифрования будут выступать числа $x,y,z$ вместе с показателем степени

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

Случай, когда криптосистему создать невозможно, рассмотрен в этой теме на форуме:

http://dxdy.ru/topic31438.html

Обе статьи направил в журнал для публикации. Пока же их разместил на сайте http://www.2000.ru. Сейчас занимаюсь поиском переводчика со знанием теоремы Ферма .

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

Благодарю всех, кто помогал.

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

[ananova]

..
GCD (φ (x), e)=1
..

[Виктор Ширшов]

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

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

[ananova]

Виктор Ширшов в сообщении #306107 писал(а):

ananova в сообщении #305584 писал(а):
Пока о доказательстве лучше не говорить, но новая неочевидная атака на теорему выполнена. Проверим на стойкость.

Атака до конца не прошла... Пришлось добавить условие - ВТФ справедлива, т.е. основное уравнение Ферма не имеет решениий, если выполняется хоть одно из условий, для cтепени p:

1) $p^{\frac {\psi (x)}{p}}$ ≢ $1 \mod (x)$ и $x$ не кратно $p$
2) $p^{\frac {\psi (y)}{p}}$ ≢ $1 \mod (y)$ и $y$ не кратно $p$
3) $p^{\frac {\psi (z)}{p}}$ ≢ $1 \mod (z)$ и $z$ не кратно $p$

Где $\psi$ - функция Эйлера

Сколько может быть чисел ??? - бесконечно или конечно, одно или несколько?: $p^{\frac {\psi (x)}{p}} \equiv 1 \mod (x)$ надо будет разобраться.

Условие эквивалентное данному: ${\frac {\psi (x)}{p}}^{\frac {\psi (x)}{p}} \equiv 1 \mod (x)$

[Gem]

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

, как это было доказано в этой теме:

$3^2+4^2=5^2$
Вроде бы
5<6$
Нет?

[ananova]

Gem в сообщении #314286 писал(а):

$3^2+4^2=5^2$
Вроде бы
5<6$
Нет?

Тут обстоятельства складываются так. Если n - чётное, то всё уравнение на x+y не делится, а если нечётное число, то делится на x+y.

Вы выбрали чётную степень и получили не тот пример, который мог бы противоречить условию.

[Gem]

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

Вы выбрали чётную степень и получили не тот пример, который мог бы противоречить условию.

Я виновать в том, что $5<6$?

[ananova]

Gem в сообщении #314300 писал(а):

Я виновать в том, что $5<6$?

Нет, я просто не могу уловить Вашу мысль.

К теореме Пифагора это условие никакого отношения не имеет. Если Вы это имели ввиду.

[Gem]

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

К теореме Пифагора это условие никакого отношения не имеет.

К какой именно теореме Пифагора и вообще о чём Вы говорите?
Повторите ясно, плз.

[sceptic]

Что означает выражение "числа $(e, mod\verb" в первой статье? Я понимаю, что это пара чисел: $e$ и ... что? $x$? или что-то иное?

[ananova]

(Оффтоп)

Пишите мне письма в личную почту, если Вам что-то надобно... там можем обсудить про Ваши 5<6, здесь я отвечать не буду

-- Пт апр 30, 2010 13:55:04 --

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

Что означает выражение "числа $(e, mod\verbe$ и ... что? $x$? или что-то иное?

На самом деле - два числа: $e$ и $x$, $x$ - используется в качестве модуля для шифрования...

(Оффтоп)

Вы можете скачать pdf файлы, если браузер плохо воспринимает формулы (opera этим страдает).

Например $e=3, x =7, y=5 $
Тогда криптограммой по паре (3,7) будет $5^3 \mod (x=7)$

Буква $e$ cюда "перебралась" из теории по RSA - обозначение степени - e(ncrypted). На самом, деле всякие варианты на эту тему доставляют много удовольствия - попробуйте поэкспериментировать со сравнениями:
$(x^e+y^e)^d \equiv z^{ed} \equiv z \mod (q)$,
$q$: $\psi (q)+1 =ed$

или такими:

$(x^e+y^e)^d \equiv (z^e+s^e)^d \mod (q)$

и многими другими... . Уверяю, занимательное дело...

[sceptic]

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

(Оффтоп)

Пишите мне письма в личную почту, если Вам что-то надобно... там можем обсудить про Ваши 5<6, здесь я отвечать не буду

1. Это не мне надобно, а Вам потребовалось "проверить на стойкость" (как Вы выразились в стартовом посте) свою "атаку" на ВФТ. Я же (исходя из своего опыта общения с ферматистами), прежде чем начать разбор работы по существу, уточняю терминологию, используемую автором - часто авторы вкладывают в обычные мат. понятия свой "сакральный" смысл.
2. Вы не спутали меня с Gem'ом? "5<6" - это его.

(Оффтоп)

Я опоздал с репликой . Вы уже ответили...

[ananova]

(Оффтоп)

Да, сначала я ответил Gem, потом Вам.... Но ответы склеились, поэтому получилось так как получилось..

-- Пт апр 30, 2010 14:30:33 --

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

свою "атаку" на ВФТ

На самом деле, начальный "раздел", где значение функции Эйлера хоть одного из чисел - $x,y,z $ не кратно степени - проверять не надо. Он абсолютно верен и я в нём нисколько не сомневаюсь. Если интересно, то почитайте. А вот там, где используются приём Лежандра, там ещё есть что доработать...

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

ВТФ справедлива, т.е. основное уравнение Ферма не имеет решениий, если выполняется хоть одно из условий, для cтепени p:

1) $p^{\frac {\psi (x)}{p}}$ ≢ $1 \mod (x)$ и $x$ не кратно $p$
2) $p^{\frac {\psi (y)}{p}}$ ≢ $1 \mod (y)$ и $y$ не кратно $p$
3) $p^{\frac {\psi (z)}{p}}$ ≢ $1 \mod (z)$ и $z$ не кратно $p$

Где $\psi$ - функция Эйлера

Сколько может быть чисел для выполнения следующего условия ??? - бесконечно или конечно, одно ?: $p^{\frac {\psi (x)}{p}} \equiv 1 \mod (x)$ надо будет разобраться.

Условие эквивалентное данному: ${\frac {\psi (x)}{p}}^{\frac {\psi (x)}{p}} \equiv 1 \mod (x)$

[sceptic]

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

На самом деле - два числа: $e$ и $x$, $x$ - используется в качестве модуля для шифрования...

Ну так и пишите "ключ шифрования $(e,x)$" а не "ключ шифрования $(e, mod\verb". Впрочем, можете это рассматривать как редакторскую придирку (но ни один приличный журнал статью с такой неряшливостью в обозначениях не примет).

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

На самом деле, начальный "раздел", где значение функции Эйлера хоть одного из чисел - $x,y,z $ не кратно степени - проверять не надо. Он абсолютно верен и я в нём нисколько не сомневаюсь.

Я сомневаюсь. Позвольте мне самому решать, что нуждается в проверке.

Перейду к статье. Вводя ограничение $6<x<y<z$ (возражений нет никаких) для гипотетического решения уравнения $x^e+y^e=z^e$(надеюсь, Вы не будете возражать против перехода к классической форме уравнения Ферма от вашего $x^e+y^e+z^e=0$), Вы не вправе использовать криптосистему RSA с ключами $(e,x)$ и $(e,y)$. Если Вы помните определение криптосистемы RSA, функция шифрования $E(e,N)$гарантирует инъективность (а только она и нужна Вам в вашей "атаке") лишь на сообщениях из интервала $(0,N)$. Поэтому, при $z>N$ RSA не обещает выполнения $x^e \neq z^e (mod\verb или $y^e \neq z^e (mod\verb. Это может произойти при определенных условиях на $x,y,z,e,N$, но где анализ (и даже формулировка!) этих условий? Увы, такая задача Вами даже и не рассматривалась.
Рассмотрим шифрование RSA с $N=z$. Да, здесь гарантируется $x^e \neq y^e (mod\verb, но не это Вам надо, не так ли? А $x^e+y^e \neq 0 (mod\verb RSA не обещала .
Итак, что осталось от основной Вашей идеи привлечь RSA к атаке на ВТФ? Остался один нерассмотренный вариант выбора секретного ключа $N$: $N>z$. Какая малость ! Как говаривал классик: "Пилите, Шура, пилите!".

[ananova]

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

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

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

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

Поэтому интересней рассматривать случай $N>z$.

Такой случай я рассматривал не достаточно много, но рассматривал. - Причём $N$ (или в моём случае - $q$) в самых разных вариантах: и как просто $N$, и как $N=z^n+1$, и как многое чего другого...
Действительно, там есть где "пошевелить"... Пока получены самые разные соотношения, но нет ясного и чёткого результата. Потом, мне в этом интересно самому копаться, пока не будет получен результат интересный для других. Как будет, так и поделюсь. Но в какой-то момент я понял, что на форуме есть математики-профессионалы и они гораздо быстрей получат результаты, если заметят в этом какой-то смысл. А пока Вы правы - пилю, пилю ... и атакую

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

где анализ (и даже формулировка!) этих условий? Увы, такая задача Вами даже и не рассматривалась.

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

Возвращаюсь к $N=z$.

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

Да, здесь гарантируется $x^e \neq y^e (\mod (z)$, но не это Вам надо, не так ли?

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

Раз вы ушли от cравнения $x^e+y^e+z^e \equiv 0 \mod (z)$

Поясню почему... $x$ ≢ $y \mod (z)$. Только в этом случае основное уравнение Ферма не имеет решений. RSA из такой ситуации, когда два разных сообщения зашифровываются одним и тем же ключом, может привести только к тому, что Вы указали.


Не вижу проблем и в таких сравнениях:
$x^e$ ≢ $z^e$ \mod (y)
$x^{2e}$ ≢ $y^{2e}$ \mod (z)

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

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