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

[Dmitriy40]

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

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

Нет, это не принципиально. В русском языке нет случаев "ййй" ни в одном правильном слове любой длины. Обнаружив при попытке расшифровки такую комбинацию можно сделать вывод что ключ (правила замен) некорректен и проверять другой. И не просто другой, а можно сразу исключить что эти три (в общем случае разных) символа шифротекста кодируют один символ "й" и значит минимум один из них должен кодировать какой-то другой символ - можно сразу отбросить все варианты ключа где три шифрованным символа все кодируют "й". Пробелы и равновероятность на это не влияют. Хотя и могут помогать: не все символы или их комбинации допустимы в начале или конце слова (если мы уже можем выделить границы слов в исходном тексте), это тоже даёт причину отбросить ключ и перейти к следующему. И например нет слов длиннее какого-то порога (для русского не помню, символов 30 или 40), значит среди любых последовательных 40 шифрованных символов есть знак препинания (или пробел) и обнаружив слово длиннее порога можно тоже отбросить вариант ключа. Знаков препинания не бывает много подряд. И так далее, критериев может быть много, но они почти все специфичны для каждого языка и даже для типа исходного текста (например немало типов текстов примерно одинаково начинаются или заканчиваются, скажем письма приветствием и подписью).
Правда в таком виде это чувствительно к опечаткам, но и это лечится если отбрасывать ключ не по первой же ошибке, а по накоплению скольких-то ошибок.
Кстати частотный анализ здесь всё равно можно применять, только считать частоты не отдельных символов, а комбинаций символов, про их равночастоность в условии не сказано. А, это и в вики сказано.
И да, чем короче текст и его повторяемость (например сколько отдельных email перехвачено) тем меньше вероятность его взлома. Наверное поэтому и остаются нерасшифрованными криптограммы.
Впрочем я в шифровании ни бум-бум.

[Dan B-Yallay]

Dmitriy40
Я не совсем понимаю выражение "сразу отбросить все варианты ключа где три шифрованным символа все кодируют "й"."

Допустим, я использую такой ключ, в котором русской букве "А" можно произвольно поставить один из десяти тысяч уникальных символов. Соответственно букве "Б" тоже один из 10 000 других символов. И т.д. включая пробелы, переносы строки, препинания и всё остальное. Тогда зашифрованное сообщение в, скажем, 5 000 знаков практически гарантированно будет последовательностью ни разу не повторяющихся знаков. Каким образом будут перебираться ключи в этом случае?
Даже если перехватить несколько десятков зашифрованных сообщений подобной длины.

ЗЫ. В рамках примера правильней, конечно, если количество возможных сопоставляемых символов каждой букве будет пропорционально соответствовать статистике частот этих букв в языке х 1000..

[B3LYP]

Я не до конца понял последнюю дискуссию про омофоны, но у меня есть возможно похожий вопрос. Дешифровать текст можно на основании того, что он пишется на каком-то конкретном языке, с высокой вероятностью там встречается слово "привет" и т.д. Чтобы избежать такого дешифрования, хорошим решением будет обозначить кодами все слова. Т.е. если в русском языке есть например миллион слов, то каждому слову будет соответствовать число от одного до миллиона. А для слов, не входящих в словарь, можно оставить побуквенную запись, но такое будет очень редко. Возможно, обычный zip делает именно это, когда архивирует текстовые файлы? Есть мессенджеры, которые зипуют любое текстовое сообщение перед отправкой?

[Dig386]

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

Я не до конца понял последнюю дискуссию про омофоны, но у меня есть возможно похожий вопрос. Дешифровать текст можно на основании того, что он пишется на каком-то конкретном языке, с высокой вероятностью там встречается слово "привет" и т.д. Чтобы избежать такого дешифрования, хорошим решением будет обозначить кодами все слова. Т.е. если в русском языке есть например миллион слов, то каждому слову будет соответствовать число от одного до миллиона. А для слов, не входящих в словарь, можно оставить побуквенную запись, но такое будет очень редко. Возможно, обычный zip делает именно это, когда архивирует текстовые файлы? Есть мессенджеры, которые зипуют любое текстовое сообщение перед отправкой?

Если взять современный симметричный шифр (т.е. там, где один ключ и для шифрования, и для дешифрования), то никаких частотных закономерностей не должно остаться даже если им одни пробелы шифровать. И нам не должен быть известен способ по такой шифровке восстановить ключ без брутфорса (и даже если мы знаем начальный килобайт текста в сообщении, мы не должны быть способны "расковырять" ключ). Более того, шифр, шифрующий одни пробелы, должен быть пригоден как образцовый ГПСЧ для метода Монте-Карло.

Цитата:

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

В симметричном поточном шифре нет никаких словарей естественных языков, его можно представить себе как некую функцию с целочисленным параметром (ключом), выдающую поток бит, который должен быть неотличим от случайного известными методами. Поэтом его побитово XORят с сообщением. Т.е. он представляет собой скорее "ГПСЧ, сделанный как надо", чем классическую кодовую книгу.

-- 10.04.2026, 10:02 --

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

Dmitriy40Допустим, я использую такой ключ, в котором русской букве "А" можно произвольно поставить один из десяти тысяч уникальных символов. Соответственно букве "Б" тоже один из 10 000 других символов. И т.д. включая пробелы, переносы строки, препинания и всё остальное. Тогда зашифрованное сообщение в, скажем, 5 000 знаков практически гарантированно будет последовательностью ни разу не повторяющихся знаков. Каким образом будут перебираться ключи в этом случае?
Даже если перехватить несколько десятков зашифрованных сообщений подобной длины.

1) В схеме получается очень длинный ключ, на порядки длиннее, чем в AES или ChaCha при сомнительной криптостойкости.
2) Пробовали ли Вы сделать двоичный аналог Вашей схемы, зашифровать 32 ТиБ одних пробелов и прогнать через PractRand? Без подобных грубых проверок криптоанализ даже обычно не начинают.
3) Само по себе "произвольно" - это уже проблема, на машине будет нужен системный криптогенератор, а живому оператору с кодовой книгой потребуется 10-15 бросков монетки на букву с последующими манипуляциями с двоичной системой счисления. Сам по себе человек как датчик случайных чисел не годится.

Вообще шифр скорее всего несколько уязвим перед Plain Text Attack, т.е. по накопленным парам "оригинал - шифровка" можно начать восстанавливать кодовую книгу, чего стойкий шифр позволять не должен. Возможно, можно ещё какие-то закономерности найти. Да, он более стоек, чем шифры Цезаря и Виженера, но если есть компьютер - то есть AES или ChaCha, а если нет - то одноразовые блокноты. Если монетку всё равно надо бросать, то чего бы заранее не наделать именно что случайных последовательностей?

[mihaild]

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

Тогда зашифрованное сообщение в, скажем, 5 000 знаков практически гарантированно будет последовательностью ни разу не повторяющихся знаков. Каким образом будут перебираться ключи в этом случае?

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

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

Даже если перехватить несколько десятков зашифрованных сообщений подобной длины

А вот если текстов достаточно много, чтобы хотя бы оценить частоты биграмм - то уже можно.

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

Чтобы избежать такого дешифрования, хорошим решением будет обозначить кодами все слова

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

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

Возможно, обычный zip делает именно это, когда архивирует текстовые файлы?

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

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

Есть мессенджеры, которые зипуют любое текстовое сообщение перед отправкой?

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

Dig386 в сообщении #1721974 писал(а):

Вообще шифр скорее всего несколько уязвим перед Plain Text Attack

Не скорее всего, а точно. Если буква имеет $n$ замен, то после примерно $n \cdot (\ln n + 1)$ повторов мы весьма вероятно увидим все возможные замены.

[Dmitriy40]

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

Я не совсем понимаю выражение "сразу отбросить все варианты ключа где три шифрованным символа все кодируют "й"."

Предположим у нас есть 33 буквы русского языка и каждая кодируется в один из 10 символов шифротекста. Тогда всего есть $C_{330}^{33}$ (количество размещений 330 возможных шифросимволов по 33 буквам) вариантов ключа. Обнаружив в шифротексте для некоторого ключа расшифровку трёх последовательных шифросимволов как "ййй" помечаем все варианты ключей с этими тремя шифросимволами для "й" независимо от размещения по буквам остальных 227 шифросимволов некорректными и больше их не проверяем. Т.е. можно исключить не один вариант ключа из $C_{330}^{33}$, а сразу много, все в которых данные три шифросимвола кодируют букву "й".

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

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

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

[Dan B-Yallay]

Dig386
mihaild
Dmitriy40

Мне стало понятней, спасибо за разъяснения.

[B3LYP]

Мне хочется понять так сказать "философскую суть" шифрования с открытым ключом, например RSA. Полагаю, для понимания надо находить по возможности побольше простых аналогий. Вот моя аналогия, подскажите насколько она верна или неверна:
Алиса должна передать Бобу число 4. Боб загадывает два числа, которые в произведении дают тысячу, например 25 и 40. Число 25 он передаёт Алисе. Алиса умножает 4 на 25, получает 100 передаёт 100 Бобу. Ева (перехватчик) знает числа 100 и 25, и чтобы получить сообщение Алисы (4), она должна разделить 100 на 25. Бобу же вроде как немного проще: он может умножить 100 на 40, получит 4000, и далее просто отрежет три ноля от этого числа.
На самом деле я понимаю что эта аналогия неверна по одной или двум причинам, но порассуждать можно.

[Dmitriy40]

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

Алиса умножает 4 на 25, получает 100 передаёт 100 Бобу. Ева (перехватчик) знает числа 100 и 25, и чтобы получить сообщение Алисы (4), она должна разделить 100 на 25.

Вот этим и плоха операция умножения, что её можно быстро обратить зная один аргумент и результат. И потому такая аналогия, с простым умножением - некорректна. Вроде бы с нормальной операцией (возведение в степень по модулю) не столь уж сложнее в понимании ...
Но если не думать про Еву (перехват сообщений), то для начала да, можно пользоваться. Только это не RSA, там ведь подразумевается что числа 25 и 100 - общедоступны/опубликованы и они не должны позволять быстро/легко получить число 4 и это принципиальное отличие RSA от известных ранее симметричных шифров, что почти всё общедоступно (кроме закрытой части ключа), а расшифровать нельзя.

-- 11.04.2026, 18:09 --

B3LYP
Ну или представьте что никто в мире не умеет делить два числа. Только складывать/вычитать и умножать, но не делить, вот невозможно посчитать частное кроме как подбором через умножение (и каждое умножение занимает скажем минуту, не меньше). И числа возьмите побольше, уж до 4 перебрать несложно, а вот до 4000000 уже не так просто (тем более по минуте на каждое). Тогда аналогия с умножением будет похожа на RSA.

[B3LYP]

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

Ну или представьте что никто в мире не умеет делить два числа. Только складывать/вычитать и умножать, но не делить, вот невозможно посчитать частное кроме как подбором через умножение (и каждое умножение занимает скажем минуту, не меньше). И числа возьмите побольше, уж до 4 перебрать несложно, а вот до 4000000 уже не так просто (тем более по минуте на каждое). Тогда аналогия с умножением будет похожа на RSA.

Честно говоря я сам сейчас считаю, что моя аналогия уж очень далёкая, т.е. скорее неправильная. Дело в том что Еве легче делить на 25, если она знает что 25 кратно тысяче. Это ещё более очевидно, если перейти от десятичных цифр к двоичным: ясно что умножение и деление таких чисел будет банальным shl и shr.
Но может можно придумать более хорошую аналогию? Общий принцип - в математике есть много задач, с которыми решение прямой задачи легче решения обратной, т.е. легче найти y зная x, чем найти x зная y.

[Dmitriy40]

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

Дело в том что Еве легче делить на 25, если она знает что 25 кратно тысяче.

А откуда она это знает про любое подсмотренное в канале число? Ведь 25 она не сама придумывает, а видит в канале и его придумывает Боб. И Только Боб может знать про его соотношение с 1000 - он может именно так придумывать свои числа. А Ева не знает даже что именно тысяче, а не миллиарду или любому другому числу. И даже если пробовать все степени 10, то непонятно как выбрать нужную (100 или 1000 или 1000000 или 10^931). Ева по идее даже про то что система счисления десятичная может не знать, вдруг она 13-ричная, просто цифр больше 9 случайно (или не случайно) не попалось.
И да, 25 не кратно 1000, наоборот, это 1000 кратно 25. А 25 делит 1000.

[B3LYP]

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

А откуда она это знает про любое подсмотренное в канале число? Ведь 25 она не сама придумывает, а видит в канале и его придумывает Боб. И Только Боб может знать про его соотношение с 1000 - он может именно так придумывать свои числа. А Ева не знает даже что именно тысяче, а не миллиарду или любому другому числу. И даже если пробовать все степени 10, то непонятно как выбрать нужную (100 или 1000 или 1000000 или 10^931). Ева по идее даже про то что система счисления десятичная может не знать, вдруг она 13-ричная, просто цифр больше 9 случайно (или не случайно) не попалось.

Немного неудобно что я типа сам себя опровергаю/разоблачаю, но тем не менее: то что я написал в предыдущем посте, понятно если система счисления сугубо двоичная. Алиса передаёт Бобу число 100, Боб должен его умножить на 10 (сделать shl 1) и получит 1000, и отнимет три ноля, а Ева поделит число на 100 (сделает shr 2), сразу получит 1. Нет, эта аналогия плохая. Может если в качестве основания системы счисления взять число, являющееся произведением первой тысячи простых чисел - выйдет чуть получше? Но сомневаюсь.
Я немного знаю про RSA: там "магия" основана на каком-то объединении двух чисел на базе двух принципов, или может я неправильно написал, но мне хочется сослаться что вся "магия" квантовой механики тоже возникает при переходе от одномерного базиса к двумерному (неравенства Белла вместо ЭПР, квантовая криптография, квантовая псевдотелепатия). Это неспроста.

[Dmitriy40]

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

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