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

[Anton_Peplov]

B3LYP
Я бы объяснил так. Давайте отвлечемся от специального термина "закрытые и открытые ключи" и обратимся к понятной аналогии. Есть замок, которым запирают секретную информацию, и есть ключ к замку. Замок можно закрыть без ключа (нажал и щелкнуло), но нельзя открыть без ключа. Зашифровать = закрыть замок, расшифровать = открыть замок ключом. Банк выдает клиентам замки, ключи от которых есть только у него. Даже если хакер перехватит замок, он не сможет им ничего открыть, только закрыть, поэтому перехватывать замок бессмысленно. А ключ никому не выдается, лежит себе в банке под охраной дракона.
Произведение двух больших простых чисел - это замок. Сами множители - это ключ.

Если хотите детально разобраться в работе RSA, она хорошо разобрана, например, в книге: С. Дасгупта, Х. Пападимитриу, У. Вазирани. Алгоритмы. М.: МЦНМО, 2014.

[Ende]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Криптография и Защита Информации»
Причина переноса: тематика.

[B3LYP]

Можно пока мысли вслух.
1) Первый момент: можно ли поставить эксперимент так, что Алиса и Боб разговаривают по телефону, а Ева их прослушивает; или скажем Алиса, Боб и Ева сидят в чате на троих, но Ева не может ничего писать, только читает.
2) Алиса загадывает число 5, Боб загадывает число 7. Или правильнее так - Алиса загадывает оба числа, но только число 7 она сообщает Бобу?
3) Алиса производит какую-то операцию над своим текстом с помощью числа 5, присылает результат Бобу, тот обрабатывает результат с помощью числа 7, и возвращает что-то Алисе. Так? Вроде логично что главное преимущество Боба перед Евой - это то, что он может что-то передать Алисе, а Ева не может. Алиса и Боб производят какую-то "взаимную постройку" друг под друга. Верно?

[mihaild]

Я бы советовал сначала разобраться со стандартным протоколом, а потом уже придумывать что-то своё.
Базовая идея же очень простая, и хорошая аналогия написана выше.

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

[B3LYP]

topic161621.html

[B3LYP]

Я часто думаю над таким вопросом: а вдруг мы сможем открыть алгоритм, с которым можно будет на обычном компьютере быстро разложить любое число на простые множители?
Ожидаю что тут всем типа смешно, а мне скорее страшно... Ну ладно, пока у меня два вопроса:
1) Я написал программу для вычислений с целыми числами любого размера. С этой программой, вычисление два в степени тысяча на моём компьютере заняло около четверти секунды, что достаточно много. А ведь если писать числа не в десятичной а в двоичной системе списания, то по определению считать вообще не надо будет. Наверно, такое число как $2^{1000}$ действительно куда как быстрее сначала записать в двоичной системе, а потом перевести в десятичную? Как будет выглядеть хороший алгоритм перевода? И как вообще с целыми числами быстро возвести число в степень?
2) Если мы запишем любое число в десятичных цифрах, то по последней цифры записи сразу видно, делится ли число на 2 и 5. Если мы запишем число в 21-ричных цифрах, то по последней цифре, сразу видно, делится ли это число на 3 и 7. Никто не пробовал применять этот подход на практике для быстрого разложения чисел на простые множители? Вроде того что, скажем, можно записать число в такой системе счисления, основание которой является произведением первых тысячи простых чисел.

[mihaild]

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

вычисление два в степени тысяча на моём компьютере заняло около четверти секунды

Это и в десятичной системе как-то совсем плохо. Очень неоптимальная реализация, видимо.

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

Наверно, такое число как $2^{1000}$ действительно куда как быстрее сначала записать в двоичной системе, а потом перевести в десятичную?

Это как раз очень долгий процесс. Есть разные алгоритмы, описаны в учебниках.

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

И как вообще с целыми числами быстро возвести число в степень?

https://en.wikipedia.org/wiki/Exponenti ... y_squaring

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

Никто не пробовал применять этот подход на практике для быстрого разложения чисел на простые множители? Вроде того что, скажем, можно записать число в такой системе счисления, основание которой является произведением первых тысячи простых чисел

Проверить, делится ли число из нескольких сотен тысяч бит на число из пары десятков бит - элементарно, и никая оптимизация не нужна.
Для некоторых задач числа хранятся в виде кортежа остатков от деления на разные простые. Но это довольно специфическое представление.

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

Никто не пробовал

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

[Dmitriy40]

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

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

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

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

Наверно, такое число как $2^{1000}$ действительно куда как быстрее сначала записать в двоичной системе, а потом перевести в десятичную?

А зачем переводить? Программе для работы с этим числом перевод его в десятичную форум не нужен, компьютеры и с двоичными работают, даже намного лучше чем с десятичными. Десятичная форма нужна фактически исключительно человеку, а ему можно и относительно долго переводить, он всё равно не успеет обработать более 1 числа в секунду. Для обмена между программами достаточно восьмеричной или шестнадцатиричной системы, перевод в которую из двоичной и обратно тривиален (и делается в уме если вдруг надо руками).

[B3LYP]

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

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

Дискретный логарифм это ещё одна разновидность постквантового шифрования?

[Dmitriy40]

(Оффтоп)

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

Дискретный логарифм это ещё одна разновидность постквантового шифрования?

Вроде бы нет:

Цитата:

Изначально это была задача дискретного логарифмирования в мультипликативной группе конечного поля (Discrete Logarithm Problem, сокр. — DLP), сейчас на практике широко используется задача дискретного логарифмирования в группе точек эллиптической кривой (Elliptic Curve DLP — ECDLP). В будущем (не таком уж далеком) предполагается использовать другие “сложные” задачи, которые будет иметь экспоненциальную сложность не только на классическом, но и на квантовом компьютере. Они называются постквантовыми. Одной из таких задач является задача нахождения изогении между эллиптическими кривыми
[...]
Для симметричных шифров все пока не так ужасно – их будут атаковать квантовым алгоритмом Гровера, который имеет сложность квадратный корень из мощности множества ключа. К примеру, если вы использовали AES c длиной ключа 128 бит, то чтобы сохранить тот же уровень безопасности нужен тот же AES, но c 256 битным ключом (а AES-128 падает до 64 битного уровня, т.е. атакующему нужно будет выполнить $2^{64}$ операций на квантовом компьютере).

Но это хабр, так что лучше бы проверить по более надёжным источникам.

UPD. Убрал под тег, ответ mihaild ниже гораздо более полный.

[mihaild]

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

Дискретный логарифм это ещё одна разновидность постквантового шифрования?

Дискретный логарифм - это решение уравнения $x^n \equiv y \pmod p$. И основанное на нём шифрование не постквантовое, для нахождения дискретного логарифма есть эффективный квантовый алгоритм.

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

[Dan B-Yallay]

Насчёт частотного анализа: допустим есть двухбуквенный алфавит $\{a, b \}$ и язык, в котором буква $b$ встречается в ровно два раза чаще, чем буква $a$.
берем 3 символа $\{ \omega, \varphi, \psi \}$ и делаем такую замену:

$ a \rightarrow \omega $

$ b \rightarrow $ случайным образом $ \rightarrow \{\varphi , \psi \}$

(Оффтоп)

Соответственнo расширяется на русский алфавит/язык (и другие естественные языки)

Вроде такой шифр должен быть известен. Kакими методами он может ломаться?

[mihaild]

Dan B-Yallay
Не очень понял, в чем, собственно, шифр. Что является ключом? Шифрование - это функция, которая из входа и ключа делает выход.

[Dmitriy40]

mihaild
В данном случае ключом служат правила замен (из трёх утверждений, включая случайность выбора из двух символов).
Функция шифрования принимает исходный текст и правила замен (как ключ), выдаёт шифрованный текст.
Функция расшифровки принимает шифрованный текст и правила замен (как ключ), выдаёт исходный текст.
Указанное преобразование очевидно обратимо, так что всё в порядке.

Dan B-Yallay в сообщении #1721946 писал(а):

Kакими методами он может ломаться?

Словарными: не все возможные комбинации символов используются в словах. Тут есть три варианта расшифровки, смотря какой символ берём за $a$, пробуем каждый вариант и если натыкаемся на несуществующее слово - считаем вариант ошибочным. Для реальных текстов и слов недопустимые комбинации появляются довольно быстро (число допустимых комбинаций много меньше всех возможных).
Вот если так передавать двоичные числа, то взломать может и не получиться (вероятности всех комбинаций одной длины примерно одинаковы), смотря какие числа передаются и как разделяются.

-- 10.04.2026, 02:37 --

Dan B-Yallay
Вот здесь такой шифр называют шифром омофонной замены. Про взлом там вроде ничего не сказано.

[Dan B-Yallay]

Dmitriy40
Спасибо за информацию.

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

Словарными: не все возможные комбинации символов используются в словах.

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

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

Про взлом там вроде ничего не сказано

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

При этом есть примеры (не простейших?) омофонных шифровок, которые не расшифрованы.