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

[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), но не сказать чтобы так уж сильно, всего вдвое-вчетверо), непонятно почему Вам это не очевидно и почему Вы не можете сразу (в уме или короткой прогой) это прикинуть.

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