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

[Солохин]

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

Вот задача, с которой всё началось.

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

Эту задачу никто не мог решить тысячелетиями. Во время войны британцы читали немецкие шифровки, потому что как-то узнали ключ к шифру. (Считается, что раскрыли с помощью протокомпьютера, но скорее всего просто нашпионили, как и подобает пиратам.) Если бы немцы умели делать то, что сейчас расскажу, то Вторая мировая война могла бы пойти по-другому. (Хотя кончилась бы так же; шансов на победу против Британии+США+России у Гитлера не было.)

Представьте себе: тысячу лет никто никому не приходило в голову, как это сделать. А в XX веке, в 60-е годы, математики придумали! Я считаю, это одно из главных достижений человечества в XX веке, наряду с атомной бомбой и полетом в космос.
Если бы этого не было, то не было бы и Интернета, потому что в Сети все происходит у всех на глазах, и если без шифров тут можно было бы говорить только о погоде.

Решение задачи, как и все гениальное, просто.
Помните задачу про волка, козу и капусту? Как их перевести на другой берег, если лодка не вмещает сразу всех?

Так вот, решение Проблемы шифра очень похоже на решение это

[Солохин]

Решение задачи, как и все гениальное, просто.
Помните задачу про волка, козу и капусту? Как их перевести на другой берег, если в лодке только есть место лишь для чего-то одного? при этом волк съест козу, а коза - капусту, если оставить их без присмотра.
Решение знают все!
Сначала везем козу, потом везем капусту, потом забираем козу назад (чтобы она не съела капусту), потом везем волка, потом наконец везем козу. Пять раз придется переплыть реку,

Так вот, решение Проблемы шифра очень похоже на решение этой задачки!

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

Профит!

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

Примерно так и работает современный интернет.

Понравилось?

Расскажите, кто что ещё знает на эту тему!

[BormoGlott]

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

[Солохин]

Согласен.

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

Впрочем, я знаю, как решить и вот эту задачу:

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

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

Я придумал, как.
Но пока не публиковал идею.
Из гуманитарных соображений. Чтобы шпионам жизнь мёдом не казалась.

[Солохин]

Кстати, вчера я задумался: а сделать так, чтобы переписка оставалась секретной, но в то же время была доступна с любого (нового) устройства?
Очевидно, для этого она должна храниться "на облаке" в зашифрованном виде. Но добиться того, чтобы ключ от шифра был лишь у участников переписки и более ни у кого?

Проснувшись наутро сегодня, я обнаружил у себя голове готовую схему, как можно это сделать.

Как сделать ВСЕ чаты секретными и в то же время переносимыми с одного устройства на другое.

А именно.

Каждый публичный чат хранится на сервере в зашифрованном виде. Чтобы его прочитать, надо быть участником чата - то есть, иметь доступ к ключу, которым он зашифрован. Не знаешь ключа - можешь читать сколько угодно: ничего понять невозможно. К тебе на устройство история чата передается в зашифрованном виде, расшифровывается только у тебя на устройстве.
А где хранится этот ключ? (Особый для каждого чата.)
Ключ хранится на сервере, но тоже в зашифрованном виде, в моем индивидуальном списке - списке ключей ко всем моим чатам и каналам. Этот список зашифрован моим индивидуальным ключом, и он передается мне сразу после того, когда я вхожу в свой аккаунт. Передается тоже в зашифрованном виде, причем никому не известен мой индивидуальный ключ, пользуясь которым можно этот список прочесть.
Хорошо, а где же хранится мой индивидуальный ключ?
А он тоже хранится на сервере, и зашифрован! И передается мне в тот момент, когда я вхожу в свой аккаунт в зашифрованном виде. Чтобы его расшифровать, нужно знать мой пароль, который я должен хранить в тайне, это уже моя забота.

Итак.

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

Профит!

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

[Солохин]

Ну, и в итоге.

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

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

Вуаля. ФСБ ничего сделать не может. Система взламывается только при помощи терморектального анализа.

[zwh]

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

Т.е. сообщение зашифровано дважды. Но можно ли расшифровать его по первому ключу, оставив зашифрованным по второму? Ну, наверно, как-то можно, это ж не просто так, что, допустим, я загнал файл в RAR-архив (или там ZIP-, ARJ-... без разницы) без сжатия, но с паролем, потом так же загнал в следующий запароленный архив, а теперь хочу распаролить его по первому ключу, не зная второй... На архивах это не получится, а на сообщениях -- если разработать соответствующую технологию -- ХЗ, наверно можно.

[BormoGlott]

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

[Солохин]

Но можно ли расшифровать его по первому ключу, оставив зашифрованным по второму

Хороший вопрос! Зрите в корень.

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

Например, Вы хотите передать мне число А. Вы передаете мне А*В (В - Ваш ключ!). Я передаю Вам обратно А*В*С (С - мой ключ!), Вы делите это на В и получаете А*С, пересылаете мне. Я делю это на С и получаю А. Что и требовалось.

Конечно, умножение - слишком простая операция. Надо похитрее - что угодно, лишь бы результат последовательного применения двух таких операций не зависел от их порядка. Как в умножении А*В*С=А*С*В.
Таким же свойством обладает, например, возведение в степень.

(А^В)^С = (А^С)^В

Если Вы знаете x и y и знаете, что x=f(y) - достаточно ли это чтобы понять, что такое f?
Если речь идет всего лишь об умножении на число, f(x)=a*x, то достаточно.
Но бывают же и более хитрые функции, для определения которых ничего не даст ни знание пары примеров её действия, ни даже даже сотни таких примеров.

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

[Солохин]

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

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

Я не склонен относиться к этому слишком уж легкомысленно.

Бывают такие идеи, которыми можно разрушить этот скорбный мир.

[Солохин]

Возведение в степень на циклической группе

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

Например: 9*9=81~1
5*5=25~5

При этом возведение в степень числа 7 выглядит так:

7¹=7
7²=7*7=49~9
7³=7*7*7=9*7=63~3
7⁴=7*7*7*7=3*7=21~1
7⁵=1*7~7
7⁶=1*7~9
Далее начинается повтор.

Если теперь использовать не десятичное исчисление, а положить в основание простое число N (сколько угодно большое), то цикл возникает лишь после того, как будут перебраны все варианты (а их N штук).

К слову, малая теорема Ферма как раз устанавливает момент, когда начинается повтор: (wiki/ru) Малая_теорема_Ферма

[Солохин]

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

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

[zwh]

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

[Rusiok]

ящичек, закрытый на два ключа

Я было вначале обрадовался Вашему объяснению. Но потом понял, что аналогия не работает.

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

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

[Bhudh]

Если теперь использовать не десятичное исчисление, а положить в основание простое число N (сколько угодно большое), то цикл возникает лишь после того, как будут перебраны все варианты (а их N штук).

А можно договориться брать не последнее число, а число num( n ). Или несколько чисел/цифр. Интересно, будет ли это обратно восстановимо?
Скажем, берём число 17, проводим операции с числами, записанными в 36-ичной системе счисления, берём от результата 2 последних знака.

17¹ = h
17² = ‹h*h› = 81
17³ = ‹h*h*h› = ‹81*h› = 3sh ~ sh
17⁴ = ‹h*h*h*h› = ‹sh*h› = dg1 ~ g1
17⁵ = ‹g1*h› = 7kh ~ kh
17⁶ = ‹kh*h› = 9o1 ~ o1

Ряд [h, 81, sh, g1, kh, o1], как видим, цикличен в отношении последней цифры, но можно брать от уже полученной предпоследнюю: ряд [h, 8, s, g, k, o] уже вполне удовлетворяет случайному.

[Bhudh]

Умножение матриц не коммуникативно.

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

[Солохин]

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

Я этот вопрос уже рассмотрел выше. Вот ссылка:

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

[Солохин]

А можно договориться брать не последнее число, а число num( n ). Или несколько чисел/цифр. Интересно, будет ли это обратно восстановимо?

Вот смотрите!

На самом деле лучше вообще брать не "последнюю цифру или несколько", а подумать, как наш комп вычисляет эти цифры.
Он же считает в двоичной системе, однако ответ выдает в десятичной. Как он это делает?

А очень просто: чтобы перевести число в систему исчисления с основанием N, надо просто поделить это число на N и взять остаток от деления. Это и будет последняя цифра.
Затем (отбросив остаток) поделить результат предыдущего деления снова на N и опять взять остаток. Это будет предпоследняя цифра.
И так далее.

То есть, например, он хочет перевести 654 (записанное нулями и единицами) в 10-ю систему.
Он считает в двоичной системе, а я запишу в десятичной, что он делает:
654:10= 65 и в остатке 4
65:10=6 и в остатке 5
6:10=0 и в остатке 6.

Эти-то три числа (4, 5, 6) он и выдает на экран справа налево, изображая их в виде привычных нам арабских загогулин: 6 5 4.

То есть, когда я говорю про "последнюю цифру", на самом деле я имею в виду "остаток от деления на N". Что мы используем именно десятичную систему - это как бы случайность (десять пальцев на руках). Можно брать любое N и делать так же точно.

А если Вы берете несколько (k) цифр - это то же самое, что использовать систему с основанием N^k и брать одну цифру.
Например, для десятичной системы брать две последние цифры - это то же самое, что использовать 100-ичную систему счисления.

В Вашем примере Вы де-факто использовали 36*36=1296-ичную систему. И это не очень хорошая идея, потому что у числа 1296 очень много делителей. Потому ряд так быстро и зацикливается. Лучше всего брать простые числа - то есть, те, которые не делятся ни на что. Тогда цикл получается максимально длинный (длиной N) и результат больше всего похож на генератор случайных чисел.

[Alexandra A]

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

Я этот вопрос уже рассмотрел выше. Вот ссылка:

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

А как ты не будешь знать ключ твоего собеседника?

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

Если я хочу передать слово ИСПАНИЯ, я его зашифровываю как КТРБОКА (прибавляя к каждой букве единицу). Я передаю собеседнику  КТРБОКА. Он перешифровывает это слово как МФТГРМВ (прибавляя к каждой букве двойку). И возвращает мне его назад.

Ну так теперь у меня есть два слова: КТРБОКА зашифровано как МФТГРМВ. Если есть исходный вариант, и есть зашифрованное слово - я не могу расшифровать шифр?

[Awwal12]

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

Если текст достаточно длинный - безусловно.

Если я хочу передать слово ИСПАНИЯ, я его зашифровываю как КТРБОКА (прибавляя к каждой букве единицу). Я передаю собеседнику  КТРБОКА. Он перешифровывает это слово как МФТГРМВ (прибавляя к каждой букве двойку). И возвращает мне его назад.

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

[Солохин]

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

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

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

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

А, например, 100=2*2*2*2*5*5

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

В двоичной системе исчисления получается ещё симпатичнее. Если хотите, объясню. Хотя это уже совсем мелкие технические детали, но мне не жалко
Лишь бы было интересно.

[Upliner]

А как ты не будешь знать ключ твоего собеседника?

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

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

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

[Солохин]

А как ты не будешь знать ключ твоего собеседника?

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

А предложенный Вами метод шифровки - это очень простой метод при очень простом ключе. Так, конечно, ничего не выйдет!

[Awwal12]

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

Если текст достаточно длинный - безусловно.

P.S.: Кроме того, это не имеет значения. Задача-то исходная какая? Передать ключ (т.е. некое сообщение) зашифрованным для стороннего наблюдателя образом в отсутствие общего шифра.

[Солохин]

Передать ключ (т.е. некое сообщение) зашифрованным для стороннего наблюдателя образом в отсутствие общего шифра.

Именно! Шифра нет, и договариваться о шифре мы должны у всех на глазах.
Как же тогда?!
С первого взгляда эта задача кажется настолько неразрешимой, что когда мне впервые сказали, что решение существует, я просто не поверил.

Как с волком, козой и капустой.