Прогресс в теории простых чисел и методы шифрования

[wrest]

B3LYP в сообщении #1732725 писал(а):

А не может быть такого,

Нет, не может.

[Dmitriy40]

B3LYP в сообщении #1732725 писал(а):

будет уже не восемь а восемьдесят?

Не будет, порядок роста в общем тот же.

[B3LYP]

Я пока не разобрался толком в RSA, но хотелось бы снова порассуждать на эту тему. Мне вроде понятно, как бы работала RSA, если бы можно случайно выбрать числа p и q, которые имеют размер в триста байт и при этом являются простыми. Но если выбрать просто случайное число размером в триста байт, то будет не так просто проверить, является ли оно простым. И вот как мог бы я запрограммировать шифрование: Алиса выбирает случайные числа p и q и с ними сама себе методом RSA тысячу раз пересылает случайные числа. Если хоть раз не переслалось - значит p или q были неправильные, надо выбрать другие. И можно много раз подбирать случайные p и q, пока не получится что с ними всё вроде ок. Это и будут псевдослучайные p и q в реальном RSA? Или вот другой вопрос, более конкретный - в реальном RSA, которое используется сейчас в мессенджерах, есть очень маленькая вероятность что сообщение передастся с ошибкой (эту вероятность можно делать сколь угодно малой, пересылая с выбранными p и q самому себе всё больше случайных чисел в моём примере), или эта вероятность строго нулевая? С моим доморощенным алгоритмом она ненулевая.

[Dmitriy40]

B3LYP в сообщении #1733046 писал(а):

Алиса выбирает случайные числа p и q и с ними сама себе методом RSA тысячу раз пересылает случайные числа. Если хоть раз не переслалось - значит p или q были неправильные, надо выбрать другие. И можно много раз подбирать случайные p и q, пока не получится что с ними всё вроде ок. Это и будут псевдослучайные p и q в реальном RSA?

Я повторю свои вопросы:
Где оценка скорости шифрования по сравнению со скоростью gcd(p,q)?
И по сравнению с тестом простоты?
Где оценка вероятности для тысячи раундов и обоснование почему выбрана именно тысяча?
Без ответа на них похоже что Вы хотите микроскопом забивать гвозди.

B3LYP в сообщении #1733046 писал(а):

Или вот другой вопрос, более конкретный - в реальном RSA, которое используется сейчас в мессенджерах, есть очень маленькая вероятность что сообщение передастся с ошибкой (эту вероятность можно делать сколь угодно малой, пересылая с выбранными p и q самому себе всё больше случайных чисел в моём примере), или эта вероятность строго нулевая?

Строго нулевая: числа как минимум взаимно простые (уж надеюсь эта быстрая проверка обязательно встроена перед более медленной проверкой на простоту чисел), а значит ошибок не будет. Если они не простые, что в принципе может оказаться, то всего лишь облегчится взлом шифра. И этот вопрос уже поднимался выше и был решён, зачем повторять, или Вы его решение так и не поняли ...

[B3LYP]

Dmitriy40 в сообщении #1733091 писал(а):

Я повторю свои вопросы:
Где оценка скорости шифрования по сравнению со скоростью gcd(p,q)?
И по сравнению с тестом простоты?
Где оценка вероятности для тысячи раундов и обоснование почему выбрана именно тысяча?
Без ответа на них похоже что Вы хотите микроскопом забивать гвозди.

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

Dmitriy40 в сообщении #1733091 писал(а):

Строго нулевая: числа как минимум взаимно простые (уж надеюсь эта быстрая проверка обязательно встроена перед более медленной проверкой на простоту чисел), а значит ошибок не будет. Если они не простые, что в принципе может оказаться, то всего лишь облегчится взлом шифра. И этот вопрос уже поднимался выше и был решён, зачем повторять, или Вы его решение так и не поняли ...

Вроде понятно, но остался вопрос - а как определить, что p и q не являются "квадратными" или как это называется, то есть что нельзя брать p=12 и q=25, где простые множители встречаются более одного раза?

[Dmitriy40]

B3LYP в сообщении #1733095 писал(а):

Вроде понятно, но остался вопрос - а как определить, что p и q не являются "квадратными" или как это называется, то есть что нельзя брать p=12 и q=25, где простые множители встречаются более одного раза?

Так и называются, бесквадратные (squarefree) числа.

Квадратов не должно быть в n, а не в p или q (хотя очевидно и там тоже, но только в них - недостаточно, например p=30, q=21 - не подходят) потому что для RSA нужно n, а p и q всего лишь облегчают вычисление $\varphi(n)$ и гарантируют нужные свойства n (т.е. фактически лишь облегчают выбор правильного и удобного n) и больше никак не используются.

Определить просто: квадрат (и степень выше) может появиться в n лишь при соблюдении любого из двух условий: квадрат есть в любом из чисел p или q, p и q имеют общие делители (которые и окажутся в n в степени выше первой). Первое исключается выбором простых p и q в оригинальном RSA, второе исключается тем же самым выбором или прямой проверкой взаимной простоты p и q как Вы обсуждаете в этой теме. Первое можно исключить и выбирая бесквадратные p и q, для чего требуется их разложение или проверка на простоту (что для больших чисел быстрее на много порядков).

В итоге выбором простых p и q решают сразу все проблемы: и ошибок при передаче не будет (в n не будет квадратов), и они автоматически взаимно простые (нет квадратов в n и передача без ошибок), и взлом (вычисление $\varphi(n)$) максимально затруднён, и тысячи лет раскладывать p и q (не говоря уж про миллионы лет для n) на множители для вычисления $\varphi(n)$ не надо.

-- добавлено через 22 минуты --

B3LYP в сообщении #1733095 писал(а):

я пока просто иллюстрирую как размышляю

Чтобы размышления не оставались пустым фантазёрством очень полезно сразу делать какие-то оценки. Для меня достаточно очевидно что вычислить $\gcd(p,q)$ намного быстрее вычисления тысячи (да даже и один) раз $w=(m^e)\bmod n, t=(w^d)\bmod n$, хотя бы потому что d вычисляется по e именно расширенным алгоритмом Евклида (который хоть и дольше gcd(p,q), но не сказать чтобы так уж сильно, всего вдвое-вчетверо), непонятно почему Вам это не очевидно и почему Вы не можете сразу (в уме или короткой прогой) это прикинуть.

По моему вопросы и странные утверждения уже ходят по кругу ...

[B3LYP]

Dmitriy40

Я понимаю, что для случайно выбранных p и q можно за миллисекунду найти gcd, то есть очень легко найти два взаимно простых p и q. Но как ещё убедиться, что p и q это бесквадратные числа?
Понятно что можно проверить простоту p и q вероятностными алгоритмами, вроде алгоритма Миллера-Рабина. Но ведь эти алгоритмы не абсолютно надёжные? Значит есть маленькая, но ненулевая вероятность, что p или q будут содержать квадраты, и мессенджер передаст вам сообщение с ошибкой?
Повторю ещё раз два своих вопроса, они достаточно конкретные:
1) Есть ли с современными rsa алгоритмами, используемыми в мессенджерах, очень маленькая но ненулевая вероятность, что сообщение передастся с ошибкой?
2) Можно ли назвать алгоритм, который я привёл выше, более-менее рабочим, хотя и неказистым? Он заключается в том, чтобы выбрать случайные (взаимно простые) p и q, и много раз пересылать самому себе разные случайные числа, чтобы убедиться что p и q являются бесквадратными. Стопроцентно убедиться в этом невозможно, но чем больше чисел самому себе пересылать, тем больше надёжность.

[realeugene]

B3LYP в сообщении #1733643 писал(а):

1) Есть ли с современными rsa алгоритмами, используемыми в мессенджерах, очень маленькая но ненулевая вероятность, что сообщение передастся с ошибкой?

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

[Dmitriy40]

B3LYP в сообщении #1733643 писал(а):

Но как ещё убедиться, что p и q это бесквадратные числа?

Взять их простыми. Для этого сначала убедиться что они составные (это 100% правильно). Если нет, то вероятностным тестом простоты довести вероятность ошибки до разумно малой величины (например неизвестно ни одного исключения/ошибки теста BPSW, на числах любой длины, возможно их вообще не существует). Если хочется 100% уверенности, то разложение на множители или любой детерминированный тест простоты.

B3LYP в сообщении #1733643 писал(а):

1) Есть ли с современными rsa алгоритмами, используемыми в мессенджерах, очень маленькая но ненулевая вероятность, что сообщение передастся с ошибкой?

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

B3LYP в сообщении #1733643 писал(а):

2) Можно ли назвать алгоритм, который я привёл выше, более-менее рабочим, хотя и неказистым?

Он конечно рабочий, но никому не нужный. Это примерно как проверять делимость числа на 131 разложением на множители вероятностным методом (типа ECM).

Поймите же наконец, вам по любому придётся раскладывать p и q на простые множители!! Потому что иначе $\varphi(n)$ (и соответственно d и e) не вычислить! Её легко вычислить только если разложение $n$ на простые множители уже известно. А это бывает только если известно разложение на множители чисел p и q (именно обоих). А это автоматом означает что известно простые они или бесквадратные или какие. Т.е. вам по любому придётся это проверять, иначе никак - если только не брать p и q заранее простыми, что и делается в RSA. Так что или они сразу простые, или придётся без всяких шифрований всё равно раскладывать p,q на простые множители (и этим заодно убеждаться что n бесквадратное).
Т.е. ваше предложение просто излишне, оно плохим образом дублирует то что и так обязательно нужно будет делать ещё до начала шифрования.

-- добавлено через 8 минут --

B3LYP
Не вычислив $\varphi(n)$ вы не сможете ничего зашифровать или расшифровать. Потому что не будете знать d или e (смотря какое по какому вычисляется).
А для вычисления $\varphi(n)$ надо знать разложение на простые множители числа n.
Но зная последнее не нужно ничего шифровать и никуда пересылать - по разложению легко устанавливается факт бесквадратности (и простоты).
Всё.
Не то что шифровать и расшифровывать, даже d и e вычислять не нужно, достаточно списка простых множителей n.

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