Занимательная криптография

[Bhudh]

Сдвиг - изначально никуда не годный метод.

Смотря какой . Расшифруйте:
Тёемз - ссшлднълюа бэайыш за амгньл рйшхл.

[TestamentumTartarum]

Сдвиг - изначально никуда не годный метод.

Смотря какой . Расшифруйте:
Тёемз - ссшлднълюа бэайыш за амгньл рйшхл.

> +1+2+3+4+5 - +9+10+11+12+13+14+15+16+17 +19+20+21+22+23+24 +26+27 +29+30 +32+33+34+35+36+37 +39+40+41+42+43 >

[Bhudh]

Вот. А если бы ключ был посложнее? Не N = номер символа, а перемешанный?

[Солохин]

Самый мощный из классических шифров - это, конечно, книжный шифр.

Каждое слово заменяется на три числа: номер страницы, номер строки и номер слова в данной строке.

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

Зашифрованный текст выглядит как белый шум.

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

Белый шум. Нет другого способа расшифровки кроме как знать, какой файл взят за основу. ВСЁ.

И скорость шифровки-дешифровки максимальная. Минимум операций.

[zwh]

Самый мощный из классических шифров - это, конечно, книжный шифр.

Каждое слово заменяется на три числа: номер страницы, номер строки и номер слова в данной строке.

Достаточно старая моя мысль: а что если зашифровать файл обычным образом, а потом заняться инвертированием бит -- например, каждый 3-й, 5-й, 7-й, 11-й и 31-й? Разве не белошумоподобный потом бит получится в результате?

[Солохин]

а что если зашифровать файл обычным образом, а потом заняться инвертированием бит -- например, каждый 3-й, 5-й, 7-й, 11-й и 31-й? Разве не белошумоподобный потом бит получится в результате?

Сходу не могу сообразить. Первая мысль: вроде бы должно работать. Вторая мысль: а зачем предварительно "шифровать обычным способом"? А если сразу начать инвертировать?

[Солохин]

Ага, сообразил.

Это Вы немного модифицировали XOR-шифрование: http://kriptografea.narod.ru/XOR.html

[Солохин]

Главное - что предложенная Вами операция явно коммутативна, а значит, её можно использовать в режиме "Волк, коза и капуста"!

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

[Солохин]

На примере метода zwh можно проиллюстрировать работу протокола "волк, коза и капуста".

У меня есть секретный файл-ключ для шифровки. Я накладываю его на файл-объект, который надо зашифровать. И бит за битом смотрю: если в файле-ключе какой-то бит 1, то в файле-объекте я соответствующий бит заменяю на обратный (инвертирую). Ноль на 1, а 1 на 0. Если же в ключе данный бит 0, тов объектом файле оставляю соответствующий бит как он есть, без изменения.
Зашифрованный таким образом файл высылаю тебе. У тебя есть свой секретный файл-ключ. Ты накладываешь его и инвертируешь так же точно.
Дважды зашифрованный файл высылаешь мне. Я своим ключом инвертирую все обратно и высылаю тебе. Ты тоже инвертируешь все обратно - и читаешь, что я тебе послал.

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

Но! у этого метода есть страшный недостаток: сравнивая полученный мною файл с тем, что я отправляю затем тебе, посредник заметит, какие именно биты я поменял, а какие оставил как есть. И узнает мой секретный файл. А потом возьмет копию первого высланного мной файла и расшифрует её.

Так что это годится только как иллюстрация.

[zwh]

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

[Hellerick]

Согласен.

ФСБ халутрит, пытаясь нарушить тайну переписки. У них более чем достаточно средств для установления истины и без этого нарушения. Нет никакой нужды получать права на вторжение в частную жизнь для того, чтобы обеспечить безопасность государства.

С чего вы взяли?

До Телеграма потому и докопались, что ФСБ может установить факт обращения к Телеграму, но не имеет возможности определить, кто с кем в нем общался.

[Hellerick]

XOR-шифр не обязательно должен восприниматься наличие ключа и зашифрованного сообщения. Его можно рассматривать как разделение одного текста на два зашифрованных сообщения, причем оба могут быть практически идеальным белым шумом.
Если я знаю одного человека на двух разных ресурсах под разными никами, например, на Лингвофоруме и в ВК, я оставлю на каждом ресурсе по одной 'половине' шифровки.
А можно и стеганографией баловаться. Условно говоря, на одном ресурсе я выкладываю фотографии голых тёть, а на другом битовые карты, наложение которых превращает их в нужные сообщения.
То есть задача сводится к тому, чтобы договориться о шифровке дважды. Оба раза могут быть открытыми. Секретным должен оставаться только факт идентификации пользователей разных ресурсов друг с другом.

[Солохин]

Я-то предлагал инвертировать биты не для волка с козой, а просто для обычной шифровки.

Да, я понял Вас сразу. Использовать этот метод для иллюстрации "козы и капусты" - это моя идея, а не Ваша.

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

Так ведь и пользуются (чуть-чуть другой вариант). Я дал ссылку выше. Ещё раз:  http://kriptografea.narod.ru/XOR.html

[Солохин]

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

Красивая идея! Спасибо.

[zwh]

Я-то предлагал инвертировать биты не для волка с козой, а просто для обычной шифровки.

Да, я понял Вас сразу. Использовать этот метод для иллюстрации "козы и капусты" - это моя идея, а не Ваша.

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

Так ведь и пользуются (чуть-чуть другой вариант). Я дал ссылку выше. Ещё раз:  http://kriptografea.narod.ru/XOR.html

В тексте по ссылке предлагается накладывать эту маску на каждый символ, тогда и в самом деле можно будет применить частотный анализ. Я же предлагал инвертировать никие n-ый, m-ый (и еще какие-нить биты) просто в потоке битов.

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

[Upliner]

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

Маска не обязательно должна быть однобайтной, можно генерировать её по сложной формуле. Скажем, сначала sha-512 хеш от пароля, потом sha-512 от пароля+предыдущего хеша и т.д. Тогда маска будет неотличима от белого шума (по крайней мере пока не взломают sha) и результат шифрования соответствнно тоже.

[Солохин]

В тексте по ссылке предлагается накладывать эту маску на каждый символ, тогда и в самом деле можно будет применить частотный анализ. Я же предлагал инвертировать никие n-ый, m-ый (и еще какие-нить биты) просто в потоке битов.

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

А Hellerick выше высказал ещё более мощную идею: что сам файл-маску тоже можно передавать по открытому каналу!

Более того:

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

А можно в качестве файла маски использовать что-то общедоступное, чтобы  спецслужба не догадалась связать один файл с другим:

на одном ресурсе я выкладываю фотографии голых тёть, а на другом битовые карты, наложение которых превращает их в нужные сообщения.

"Голые тёти" играют роль файла-маски. Поди догадайся, что они выложены именно для этого.

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

Недостатком этого метода ("стеганографии") является необходимость как-то передать ссылку на "голую тётю". Если эту ссылку перехватят - файл будет тут же дешифрован.

Но сама по себе идея - мощная.

[Hellerick]

Опишу его на таком примере.
Вот я высылаю тебе письмо в ящичке, который закрыт на ключ. Ключ - это шифр.
Ключа у тебя нет, открыть мое письмо ты не можешь.
Тогда ты закрываешь ящичек на второй ключ, который остается у тебя, и высылаешь его обратно мне. Твой ключ остается у тебя, и открыть ящик теперь я не могу. Собственно, мы оба теперь не могли бы его открыть.
Получив назад свой ящичек, закрытый на два ключа, я отпираю свой ключ и снова высылаю его тебе. Ящик теперь закрыт твоим ключом, и отпереть его никто не может кроме тебя.
Получив мое послание второй раз, ты отпираешь замок и читаешь мое послание.

Обнаружил это дело в 727-й серии "Детектива Конана". Там так фрукты переправляли:

(Надеюсь, копирасты меня не повесят за публикацию этого фрагмента.)

[Солохин]

Обнаружил это дело в 727-й серии "Детектива Конана"

Спасибо!

А я тем временем разовью тему, изложив суть другой столь же мощной (а на самом деле даже более мощной) идеи.

Задача почти та же: у всех на глазах договориться о ключе для шифра. Так, чтобы никто ничего не понял, кроме меня и тебя.

Делаем так.
Мы у всех на глазах договариваемся о некотором числе A, которое ляжет в основу нашего шифрования. Это число будет всем известным.

Далее.

Я придумываю секретную функцию F. И высылаю тебе у всех на глазах только результат действия этой функции F(A), оставляя саму функцию в секрете.
Ты придумываешь секретную функцию G. И высылаешь мне у всех на глазах только результат действия этой функции G(A), оставляя саму функцию в секрете.

После этого я применяю свою секретную функцию к высланному тобой результату, а ты применяешь свою функцию к моему результату.
У тебя получается G(F(A)), а у меня F(G(A)).

А что, если подобрать наши функции таким образом, чтобы G(F(A)) всегда совпадало с F(G(A))?


Например, мы можем просто возводить в степень наше число A. Это не будет секретом. Секретом будет - в какую именно степень!

Итак.

Я беру произвольное секретное число F, вычисляю A^F и высылаю результат тебе. Число F секретное, но A^F секретом теперь не является.
Ты берешь произвольное секретное число G, вычисляешь  A^G и высылаешь мне. Число G секретное, но A^G тоже секретом не является.

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

Но! барабанная дробь (A^F)^G=(A^G)^F !!!
Следовательно, мы оба получили одно и то же число.
Моё секретное число осталось известным только мне. Твоё - только тебе.
Однако число (A^F)^G=(A^G)^F теперь известно нам обоим! Но кроме нас неизвестно никому. И потому может работать как общий ключ для шифра, неизвестный никому кроме нас.

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

Это фокус-покус именуется (wiki/ru) Протокол_Диффи_—_Хеллмана и он используется, когда мы обмениваемся информацией с сайтами, в адрес которых добавлена буквочка s  (https://...) - например, в приведенном выше адресе Википедии.

Такова суть метода.

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

Если всем известно наше число A и всем известно A^F, то что может помешать вычислить моё F при помощи банального логарифма? Ничто не помешает!

И потому наши функции должны быть чуть-чуть хитрее устроены.

Давайте при возведении в степень брать не весь результат вычисления, а только остаток от деления этого результата на некоторые число B. Это число B тоже не является секретом. Однако при отбрасывании всего кроме остатка теряется информация, необходимая для вычисления логарифма! И узнать F и B можно только путем тупого перебора всех вариантов. И если мы будем использовать для вычислений по-настоящему большие числа, то этот перебор потребует астрономического времени (миллиардов лет). А если компьютеры станут более быстродействующими, мы просто-напросто увеличим размеры наших секретных чисел.

(Замечу, что когда при всех расчетах мы берем только остаток, то какие бы большие числа мы ни брали, результат расчета не может быть больше чем B.)

[Солохин]

В чём суть, в чём фишка идеи Диффи и Хеллмана?

Он очень мудро переформулируют задачу.
Все люди всю жизнь думали: как передать собеседнику секретный ключ?

А Диффи и Хеллмана осенило: а зачем его передавать, если его можно просто-напросто получить в результате совместной работы?! Если ключ рождается в процессе работы, то и обладают этим ключом лишь те, кто в этой работе участвовали. Случайные свидетели обмена информацией, необходимого для этой работы, остаются в неведении о её результатах.

[Солохин]

А теперь увлекательная задача для участников.

ФСБ при желании с легкостью взламывает протокол https! Причем для этого используется отнюдь не грубый терморектальный криптоанализ, но глубоко деликатный прием, при применении которого оба участника общения остаются в полном неведении о том, что кто-то третий молча участвовал в их общении.

Вопрос: что это за метод и как он работает?

[Upliner]

Вопрос: что это за метод и как он работает?

Считать ли обязательство сертификационных центров предоставлять ключи для изготовления фальшивых сертификатов терморектальным криптоанализом?
Если ваш метод работает без замен и краж сертификатов -- то я наконец-то узнаю тут нечто новое.

[Солохин]

Если ваш метод работает без замен и краж сертификатов -- то я наконец-то узнаю тут нечто новое.

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

[Upliner]

Ну тогда всё элементарно.

Есть клиент A и сервер B, а между ними на канале вклинился C.
А посылает B число E^F, C его перехватиывает и подменяет на E^U;
потом B отвечает A числом E^G, C подменяет его на E^V.

Получается, что A и B общаются не между собой, а оба они общаются с C, причём A уверен, что C -- это B, а B уверен, что C -- это A.
Соединение A с C шифруется ключом (E^F)^V, а соединение C с B -- ключом (E^G)^U.
C знает оба этих ключа и поэтому может полностью расшифровать переписку.
Обычно цель стоит только в прослушивании, а не во вмешательстве, поэтому C честно передаёт B сообщения, полученные от A, а A соотвественно передаются сообщения, полученные от B.

Но если этим делом будет заниматься не ФСБ, а какой-нибудь рядовой провайдер, то у него возникнет несколько проблем, одна из которых -- это то, что число E^G обычно заверено (об этом отдельная тема) сторонним сертификационным центром, и если его заменить на другое, то браузер клиента покажет большое красное предупреждение о том, что сайт не безопасен. Некоторые наверное уже видели такое.

Но если ФСБ подконтролен хотя бы один такой центр, имеющий право подписывать все домены, то он может сделать так, что число E^V также будет заверенным, и клиент ничего не заподозрит.

[Солохин]

Всё правильно!



(Не в нравственном плане, конечно, а чисто в техническом.)

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

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

Как этим воспользоваться, чтобы проверить, не сидит ли между ними посредник?