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

[B3LYP]

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

А давайте Алиса не будет загадывать столь удобные числа, а?

В чём проблема? А если Алиса загадывает число от 100000000000 до 100999999999?

И я прокомментирую ваш предыдущий ответ:

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

А давайте Алиса задумает число 13, а не 4. Тогда она вернёт Бобу число 325, которое Ева уже не сможет сдвинуть вправо. И?
Боб же, умножив 325 на 40 получит 13000 и сможет сдвинуть вправо на три цифры получив задуманное Алисой 13.

А ещё Боб может передать Алисе не 25, а например 512, оставив у себя 1953125. Тогда Еве ещё сложнее будет сдвигать числа Алисы вправо, слишком мало их будет оканчиваться нулями.

Когда Боб пришлёт Алисе число 25, Ева будет знать что тысяча делится на это число, поэтому ей разделить 100 на 25 будет заведомо легко.
Т.е. Ева знает что число 25 от Боба - это произведение пятёрок и двоек, по десятеричной записи этого числа видимо легко разложить его на множители.

[Dmitriy40]

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

И я прокомментирую ваш предыдущий ответ:

Тогда уж посмотрите и одно сообщение выше, там цитата моих слов про выбор 100 и 1000.

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

В чём проблема? А если Алиса загадывает число от 100000000000 до 100999999999?

Проблема в том что если Ева в курсе про диапазон загадываемых Алисой чисел, то увидев в канале число $77$ сразу может восстановить задуманное Алисой число $1001$ - только оно в указанном диапазоне $[1001 \ldots 1009]$ делится на $77$ (проверяется умножением на натуральный ряд, без затратного деления) - и всё, секрета больше нет.
С большим диапазоном уже лучше, но Алиса должна передавать Бобу достаточно малый делитель задуманного числа, чтобы в разрешённом диапазоне было несколько чисел с данным делителем - тогда Еве уже не удастся однозначно восстановить задуманное Алисой число по его делителю в канале. Но этот делитель должен быть достаточно большим чтобы Ева не могла просто разделить (методом подбора частного) число от Боба на этот делитель. Плюс Боб не должен загадывать достаточно малых чисел - тоже чтобы Ева не могла поделить число от Боба на известный делитель.
Мне понравилось число $100399999999=128203\cdot783133$, можно Бобу передать $128203$. А он пусть задумывает только числа например $[200 \ldots 250]$.
Но как видите Еве всего лишь в ~250 раз сложнее Алисы восстановить число Боба методом подбора.

[B3LYP]

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

Но как видите Еве всего лишь в ~250 раз сложнее Алисы восстановить число Боба методом подбора.

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

(Оффтоп)

Шифрование будет вечным противостоянием брони и снаряда. Скоро RSA шифрование, возможно, сможет перестать работать, не только из-за квантовых компьютеров, но и потому что кто-то научится таки раскладывать простые числа на множители. Мне попадаются иногда новости, что раз за разом делаются какие-то мелкие открытия, связанные с простыми числами.
Если RSA перестанет работать, все перейдут на более продвинутые варианты, например Дерек Миллер (Veritassium) рассказывал про алгоритм с подбором векторов в многомерном пространстве. Но и для этого алгоритма, возможно, когда-то найдут ключик. И если окажется, что в этом противостоянии расшифровка победит - любая расшифровка будет занимать не намного больше машинного времени, чем шифровка - останется ещё один подход: провести вычисления заранее. Вы ставите на ночь смартфон в беззвучный режим и подсоединяете к зарядке, и он всю ночь делает какие-то вычисления, типа находит несколько очень больших простых чисел. К утру он накапливает массив чисел (которых на сутки хватит), и с утра, когда вы с кем-то переписываетесь, он их расходует. Чтобы эту переписку расшифровать, нужно как минимум ещё одну ночь на другом устройстве делать другие вычисления. Что скажете?
У меня вопросы:
1) Правильно ли я понимаю, что по алгоритму Миллера-Рабина можно быстро определить, является ли любое число (большое) простым? Только не совсем со стопроцентной надёжностью, а почти стопроцентной.
2) Выходит, если взять случайное число размером тысячу байт, то разложить его на простые множители займёт миллион лет, а просто определить является ли оно простым - долю секунды?
3) Сколько времени на современном компьютере займёт деление одного числа размером 1 гб на число размером 0.5 гб?
4) Насколько это время будет больше, чем перемножить два числа размером 0.5 гб?

[wrest]

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

3) Сколько времени на современном компьютере займёт деление одного числа размером 1 гб на число размером 0.5 гб?

На планшете 40с (на всякий случай я понял "б" как байт)

? x=random(10^1000000000);
  *** _^s: Warning: increasing stack size to 800000000.
  *** _^s: Warning: increasing stack size to 1600000000.
time = 18,713 ms.
? y=random(5*10^100000000);
time = 1,491 ms.
? z=x\y;
  *** _\_: Warning: increasing stack size to 800000000.
time = 41,149 ms.
?

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

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

4) Насколько это время будет больше, чем перемножить два числа размером 0.5 гб?

В 20 раз

? x=random(5*10^100000000);
time = 1,502 ms.
? y=random(5*10^100000000);
time = 1,453 ms.
? z=x*y;
time = 2,268 ms.
?

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

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

1) Правильно ли я понимаю, что по алгоритму Миллера-Рабина можно быстро определить, является ли любое число (большое) простым? Только не совсем со стопроцентной надёжностью, а почти стопроцентной.

Вопрос в "почти". Но не любое. На простом или полупростом тест будет очень долго задумываться. А на если есть мелкие делители - очень быстро, да.

? x=random(5*10^100000000);
time = 1,484 ms.
? ispseudoprime(x)
time = 21 ms.
0
?

Но тест, если он вернул что число составное - это практически гарантия, а вот если вернул что псевдопростое -- тут уже гарантии нет.

[B3LYP]

wrest в сообщении #1732049 писал(а):

на всякий случай я понял "б" как байт

Да, мне надо было уточнить. Имел в виду 1 гигабайт.

wrest в сообщении #1732049 писал(а):

В 20 раз

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

[wrest]

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

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

Да - тест на составность работает обычно быстро (для случайного числа, т.к. в нём практически наверняка будут мелкие множители).

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

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

А какие есть ещё задачи, где всё-таки больше разница? И какие есть задачи, где для чисел в гбайт расчёт займёт например неделю?

Вопрос сформулируйте.

[Dmitriy40]

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

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

Не простым, а составным. Чтобы убедиться что оно простое понадобятся месяцы (сильно быстрее разложения на множители, но всё равно сильно медленнее теста Миллера-Рабина). Быстро можно убедиться что оно лишь вероятно простое (или псевдопростое).
Вот вчера был пример доказательства про длинное число, почитайте, число из 9371 цифры проверялось 4.5 месяца.

[wrest]

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

Да, мне надо было уточнить. Имел в виду 1 гигабайт.

Я так и подумал, да. Заглавная Б - байт. Строчная б - бит. Приставка гига - с заглавной. Гигабайт - ГБ.
гб - гектобит. Не путайте.

[B3LYP]

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

Не простым, а составным. Чтобы убедиться что оно простое понадобятся месяцы (сильно быстрее разложения на множители, но всё равно сильно медленнее теста Миллера-Рабина). Быстро можно убедиться что оно лишь вероятно простое (или псевдопростое).
Вот вчера был пример доказательства про длинное число
, почитайте, число из 9371 цифры проверялось 4.5 месяца.

Уф, а я уж испугался до отторопи...
Но мне сейчас по-прежнему кое что сильно непонятно и смущает:

(Оффтоп)

Вот в методе rsa Алиса придумывает случайные числа p и q, из них рассчитывает n, потом случайно выбирает e, и потом алгоритмом Евклида из p, q и e считает d. Вопрос: p и q это любые простые числа, или только любые взаимно-простые?
Явно же что именно взаимно-простые, иначе снова испугаюсь. Выходит я нашёл способ быстро узнать, являются ли два числа взаимно-простыми. Алиса выбирает случайно p и q и сама себе тысячу раз по алгоритму rsa пересылает разные сообщения. Если хоть раз сообщение исказилось при пересылке - значит p и q не являются взаимно простыми, надо выбрать следующие (и поскольку вероятность взаимной простоты чисел около половины, подобрать правильные p и q можно быстро). Всё верно?

[Dmitriy40]

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

Выходит я нашёл способ быстро узнать, являются ли два числа взаимно-простыми. Алиса выбирает случайно p и q и сама себе тысячу раз по алгоритму rsa пересылает разные сообщения. Если хоть раз сообщение исказилось при пересылке - значит p и q не являются взаимно простыми, надо выбрать следующие (и поскольку вероятность взаимной простоты чисел около половины, подобрать правильные p и q можно быстро). Всё верно?

Где оценка что шифрование и дешифрование 1000 сообщений (и каких кстати, одинаковых или коротких или случайных, и насколько именно случайных) будет быстрее вычисления GCD(p,q) (например двоичным методом без делений)?
И почему именно 1000?! Где оценка вероятности ошибки для 1000 и соответственно обоснования выбора именно 1000?
И где собственно обоснование что будет искажение сообщения и именно по причине не взаимной простоты p и q? Насколько я понимаю при правильной реализации (без упрощений) вместо искажения будет лишь облегчение взлома пароля.

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

Вопрос: p и q это любые простые числа, или только любые взаимно-простые?
Явно же что именно взаимно-простые, иначе снова испугаюсь.

Нет, p и q должны быть простыми (и кстати не любыми!) - иначе в p*q появятся лишние делители что значительно облегчит его разложение на множители, а на трудности этой операции и основан RSA.

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

B3LYP
Вас что, и гугл и чатжпт и вики забанили?! Есть же полно информации по вашим вопросам, во вполне доступной форме, вот например вики прямо говорит:

вики про криптостойкость RSA писал(а):

Вычисление обратного элемента по модулю не является сложной задачей, однако злоумышленнику неизвестно значение $\varphi (n)$. Для вычисления функции Эйлера от известного числа $n$ необходимо знать разложение этого числа на простые множители. Нахождение таких множителей и является сложной задачей, а знание этих множителей — «потайной дверцей» (англ. backdoor), которая используется для вычисления $d$ владельцем ключа.

Так что наличие других множителей/делителей у $n=pq$ кроме $p,q$ сразу же облегчит взлом.

[B3LYP]

Вначале я подумал, что может быть всё неправильно понял - p и q у Алисы могут быть любыми, передача числа m от Боба в любом случае состоится, просто если эти числа составные, то Еве легче провести расшифровку. Но нет же, вроде если p или q составные, то просто сообщение не всегда сможет правильно передаться.
Разобрался с алгоритмом определения НОД, спасибо. Круто: если взять случайное число размером в тысячу байт, то разложить его на простые множители займёт миллионы лет, а вот найти НОД у двух таких чисел можно за долю секунды.
Может быть, я всё-таки в принципе верно сформулировал выше, как работает реальное rsa? Я описал метод определения, являются ли два числа p и q простыми (точнее псевдопростыми), и соответственно нахождения подходящих простых p и q перебором. Возможно мой метод очень мало отличается от алгоритма Миллера-Рабина? То как я написал, годится опять же скорее для популяризации и объяснятельства.
У меня вопрос: если брать случайные числа размером 300 байт, сколько в среднем у каждого из них простых делителей? Далее вопрос - правильно ли я понимаю, что псевдопростое число это такое, в котором делителей мало? Сколько их должно быть для числа размером 300 байт, чтобы оно называлось псевдопростым?
Правильно ли я понял следующее: если в rsa методе Алиса загадала числа p и q размером 300 байт, которые являются не простыми а псевдопростыми, то будет маленькая вероятность что число от Боба ей передастся неправильно, и этот риск, хотя и очень маленький, есть для любых современных мессенджеров?

[wrest]

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

У меня вопрос: если брать случайные числа размером 300 байт, сколько в среднем у каждого из них простых делителей?

В среднем около 8

[Dmitriy40]

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

Далее вопрос - правильно ли я понимаю, что псевдопростое число это такое, в котором делителей мало?

Неправильно: "Псевдопростое число — натуральное число, обладающее некоторыми свойствами простых чисел, являясь тем не менее составным. В зависимости от рассматриваемых свойств существует несколько различных типов псевдопростых чисел."(с)рувики.
В узком смысле, это число, про которое (выбранный) тест простоты говорит что оно якобы простое, но которое на самом деле может (очень маловероятно) оказаться и составным.

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

Правильно ли я понял следующее: если в rsa методе Алиса загадала числа p и q размером 300 байт, которые являются не простыми а псевдопростыми, то будет маленькая вероятность что число от Боба ей передастся неправильно, и этот риск, хотя и очень маленький, есть для любых современных мессенджеров?

Неправильно, см. далее.

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

Вначале я подумал, что может быть всё неправильно понял - p и q у Алисы могут быть любыми, передача числа m от Боба в любом случае состоится, просто если эти числа составные, то Еве легче провести расшифровку. Но нет же, вроде если p или q составные, то просто сообщение не всегда сможет правильно передаться.

Продемонстрируйте как скажем три делителя в n (можете взять то самое своё n=1001 и e=17, d=593) испортят передачу некоего сообщения. Не словами, а формулами и числами. Алгоритм RSA подробно описан даже в рувики, калькулятор есть в винде (или онлайн калькуляторы сразу RSA, например этот). Я вот при таких условиях (n=1001,e=17,d=593 или n=1001,e=41,d=281 или n=1001,e=1051,d=211) не нашёл какое сообщение короче/меньше n будет передано с ошибкой. Жду от Вас или примера такого сообщения, или формулы с ошибкой, или признания что для правильной передачи n может иметь сколько угодно делителей (и прекращения повтора процитированной глупости).

[Someone]

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

правильно ли я понимаю, что псевдопростое число это такое, в котором делителей мало?

Dmitriy40 уже ответил, я просто немного добавлю.
Есть так называемая малая теорема Ферма: если $p$ — простое число, то для любого натурального $a$ число $a^p-a$ делится на $p$.
Если здесь $a$ не делится на $p$, то $a^{p-1}-1$ делится на $p$.
Однако оказалось, что такая делимость возможна не только для простых чисел, и составное натуральное число $n$ стали называть псевдопростым по основанию $a$, если $a^{n-1}-1$ делится на $n$.
Потом обнаружили, что существуют такие составные числа $n$, что $a^{n-1}-1$ делится на $n$ для любого натурального $a$, взаимно простого с $n$. Такие числа называются числами Кармайкла (иногда — абсолютно псевдопростыми).
Ну а позже появились и другие виды псевдопростых чисел.

[B3LYP]

Dmitriy40

p=20, q=25
n=500 f=456
e=11 d=83 (11*83=913 912/2=456)

m=2
2^11=2048

2048 mod 500 = 48

48^83=
34915856680712522813600742674032577179188644582925720447209298744786935376971855410564958912947279295444708401888246362274806880414772232192


34915856680712522813600742674032577179188644582925720447209298744786935376971855410564958912947279295444708401888246362274806880414772232192

mod 500 = 192


Ничего что без латеха пишу, оно же могло не влезть плюс всем надо будет скопировать?