Прогресс в теории простых чисел

[wrest]

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

Предположим, у нас есть текст на русском языке, который нам надо зашифровать. Мы можем перевести все буквы текста в другие буквы по любому алгоритму; но дешифратор всё равно сможет наш текст расшифровать, зная словарь русского языка.

Это вы Конан Дойля начитались Что похвально, но методы немного устарели.

[Dmitriy40]

mihaild
warlock66613
Вы оба не упомянули критическое требование к блокноту - его размер не меньше шифруемого текста. А ТС мог подразумевать именно длину блокнота в 34 символа - тупо замена букв 1-в-1, с которым неплохо справляется частотный анализ (даже знание целевого языка для достаточно больших шифровок не всегда обязательно). Как и с развитием этого метода 1-в-многие (многовариантная замена), вскрываемого чуть более сложным частотным анализом.
А про принципиально не вскрываемый метод "одноразового блокнота", подразумеваемый Вами, он видимо просто не знал. Как и вообще про более-менее современные (с середины прошлого века) методы шифрования.

-- 28.12.2023, 19:36 --

mihaild в сообщении #1624114 писал(а):

Вообще вопрос о существовании односторонней функции открыт.

Кстати спасибо за уточнение, не был в этом (и обратном) уверен, в чём сразу и признался.

[EUgeneUS]

mihaild в сообщении #1624216 писал(а):

А каким алгоритмам шифрования это важно?

Вроде бы для DES рекомендовалось. Но это не точно

[mihaild]

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

Вы оба не упомянули критическое требование к блокноту - его размер не меньше шифруемого текста

Это обычно входит в определение.

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

Кстати спасибо за уточнение, не был в этом (и обратном) уверен

В одну сторону это просто: из существования односторонней функции следует что $P \neq NP$.

EUgeneUS в сообщении #1624224 писал(а):

Вроде бы для DES рекомендовалось. Но это не точно

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

[B3LYP]

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

Вы оба не упомянули критическое требование к блокноту - его размер не меньше шифруемого текста. А ТС мог подразумевать именно длину блокнота в 34 символа - тупо замена букв 1-в-1, с которым неплохо справляется частотный анализ (даже знание целевого языка для достаточно больших шифровок не всегда обязательно).

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

[Dmitriy40]

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

Но с закрытым ключом главная проблема - его же тоже надо передавать.

Это давно решено: его вовсе не обязательно именно передавать, можно брать из общеизвестного источника и реально передавать лишь ссылку (в том или ином виде) на источник. Обычно в качестве примера приводят какую-нибудь классическую книгу, но можно брать и совсем иные источники, например старшие 13-16 битов (чтобы не попадать ни на собственное движение, ни на прецессию земной оси, ни на остальные погрешности) угловых координат звёзд из какого-нибудь более-менее большого каталога (в некоторых больше миллиарда звёзд). А чтобы дополнительно запутать, использовать какую-нибудь априори известную абонентам замороченную перестановку групп битов (или самих объектов), кодируемую малым количеством битов в самой ссылке. И так далее.

-- 29.12.2023, 09:55 --

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

[warlock66613]

Речь о том, что сжатие не при чём.

[B3LYP]

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

Это давно решено: его вовсе не обязательно именно передавать, можно брать из общеизвестного источника и реально передавать лишь ссылку (в том или ином виде) на источник. Обычно в качестве примера приводят какую-нибудь классическую книгу

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

Вот так стало чуть понятнее:

https://ru.wikipedia.org/wiki/Протокол_Диффи_—_Хеллмана

Алиса и Боб договариваются об открытых числах p=23 и g=5, обмениваются этими числами, Ева их тоже знает. Алиса загадывает число a=6, Боб число b=15, ими они не обмениваются. Далее Алиса считает $A=(g^a) \mod p = (5^6) \mod 23 = 8$, а Боб считает $B=(g^b) \mod p = (5^15) \mod 23 = 19$. Этими числами они обмениваются и Ева их тоже знает. Тут вопрос: сколько вариантов a и b есть у Евы? Как она может вычислять a и b? Подскажите по математической стороне вопроса.
Далее Алиса считает $s=g^{ab} \mod p = (B^a) \mod p$. Боб считает $s=g^{ab} \mod p = (A^b) \mod p$. Тут тоже не до конца ясна математическая часть, почему выполняются эти два равенства, поясните. Ну то есть интуитивно вроде ясно, хочется пару примеров чтобы закрепить.

[mihaild]

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

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

Тут вопрос: сколько вариантов a и b есть у Евы?

Ключевое заклинание: мультипликативная группа конечного поля циклическая.

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

Как она может вычислять a и b?

Вычисление $a$ по $g^a$ - это задача дискретного логарифмирования. Все надеются, что быстро она не решается.

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

почему выполняются эти два равенства

Потому что это взятие модуля коммутирует с умножением.

[B3LYP]

Вот тут Дерек Муллер (Veritasium) рассказывает про алгоритм постквантового шифрования:

https://youtu.be/f5slLeCz7p8?t=1108

Берётся базис (не ортонормированный) в n-мерном пространстве, берётся случайная точка, и подбирается вектор в этом базисе, совпадающий с этой точкой. В современных алгоритмах размерность предполагается около тысячи. Правильно ли я понял, что ни классические, ни квантовые компьютеры не могут решить эту задачу? Это доказано теоретически?

[mihaild]

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

Берётся базис (не ортонормированный) в n-мерном пространстве, берётся случайная точка, и подбирается вектор в этом базисе, совпадающий с этой точкой

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

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

Полного (не опирающегося на недоказанные гипотезы) доказательства надежности криптографического протокола нет ни одного (кроме тривиальных штук, вроде одноразового блокнота). Всё еще может оказаться, что P = NP (или хотя бы $\text{NP} \subseteq \text{BPP}$), и тогда хороших криптографических протоколов нет вообще.

[B3LYP]

mihaild в сообщении #1626006 писал(а):

Ищется целочисленная линейная комбинация векторов базиса, ближайшая к точке (среди всех целочисленных линейных комбинаций).

Я пока это не очень понимаю. Если базис ортогональный, то эта задача элементарная, так ведь? А если не ортогональный, разве нельзя линейным преобразованием перевести точку в ортогональный базис?

[mihaild]

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

А если не ортогональный, разве нельзя линейным преобразованием перевести точку в ортогональный базис?

Нужно найти не произвольное линейное преобразование, а сохраняющее целочисленность коэффициентов. А это сложно.