Занимательные шифры, или Что такое «электронная подпись»
Ещё технологии информации
Необходимые пояснения о шифровании
Контроль и защита / апрель, 2018
Заметил, что многие граждане крайне превратно представляют себе современные (хотя, на самом деле, они не особо современные - им уже более полувека) алгоритмы шифрования. ©
Ключи и шифры
В частности, многие думают, будто бы при шифровании с двумя ключами собеседники тайно обмениваются своими закрытыми ключами, а потому можно куда-то там в середину вклиниться, перехватить ключ и всё расшифровывать.
Я вполне допускаю, что вам не довелось ознакомиться в детстве с книгами серии «Занимательная математика» или с интереснейшими произведениями Мартина Гарднера, которыми в советские времена зачитывался каждый второй школьник. Однако вы ведь всё-таки могли бы заглянуть хотя бы в Википедию - она открыта для всех и находится от вас на расстоянии нескольких кликов.
Так вот.
Шифрование с двумя ключами (иногда также называемое «шифрованием с открытым ключом») основано на асимметричности некоторых математических операций. Так оказывается, что некоторые операции довольно быстро вычисляются в одну сторону, но довольно медленно в другую, что делает практически невозможным подбор нужных операндов методом перебора за разумное время.
Грубо говоря, зная некое число икс, вы быстро можете вычислить значение некоторой функции f от этого икс. Но вот знание значения f(икс) не позволяет вам быстро найти сам икс, поскольку для функции f не существует простой обратной функции.
На этом свойстве и основаны крайне распространённые сейчас методы шифрования, которые используются практически вообще везде.
А именно:
- Желающий получать зашифрованные сообщения генерирует себе пару ключей.
- Один ключ, называемый «закрытым», он оставляет себе и никому никогда не показывает, если не хочет проблем. Второй ключ, называемый «открытым» он отсылает своему собеседнику.
- Собеседник шифрует свои сообщения при помощи открытого ключа и отправляет владельцу закрытого.
- Владелец закрытого расшифровывает это сообщение закрытым ключом.
Фишка тут в том, что открытого ключа недостаточно, чтобы расшифровать сообщение за разумное время. Это возможно, лишь если сами по себе ключи довольно короткие, а потому поиск закрытого ключа перебором будет всё-таки меньше времени жизни вселенной.
Именно поэтому открытый ключ адресат может разослать хоть всему человечеству: это никак и никому не поможет расшифровывать направляемые ему сообщения.
Да, всё человечество получит возможность что-то там зашифровать и послать этому адресату зашифрованное сообщение, но не расшифровать то, что ему послал кто-то ещё.
Даже если у всех имеется один и тот же открытый ключ.
На всякий случай, повторю ещё раз:
- Открытым ключом нельзя расшифровать за разумное время то сообщение, которое было зашифровано этим же открытым ключом. Для этого нужен закрытый ключ.
- Закрытый ключ ни на каком этапе никому не передаётся: ни тайно, ни явно. Его знает только сам адресат.
При переписке двух собеседников, каждый из них просто выполняет вышеописанные пункты: генерирует свой закрытый ключ и парный ему открытый, после чего передаёт открытый ключ своему собеседнику.
Оба собеседника и далее тоже делают совершенно симметричное: шифруют свои сообщения открытым ключом другого собеседника и пересылают ему. При этом расшифровать сообщения сможет только тот, кому оно адресовано, поскольку только у него есть закрытый ключ, требуемый для расшифровки сообщения.
Если, конечно, этот человек по незнанию не передал кому-то свой закрытый ключ.
Независимо от того, используется ли сервер только для установки соединения между собеседниками или через него проходят сами зашифрованные сообщения, никто, включая этот гипотетический сервер, не в состоянии узнать, что именно написано в зашифрованных сообщениях, если закрытые ключи были сгенерированы на компьютере самих собеседников и не были после этого переданы серверу или ещё кому-то.
Смысл устойчивых к взлому шифров именно в этом, а вовсе не в том, что для пересылки сообщений используются какие-то особо честные и не идущие на сделки сервера: зашифрованные таким способом сообщения можно слать даже через сервер ваших врагов и единственное, что они смогут сделать, - не переслать это сообщение адресату. Но прочитать его они не смогут, даже если они чудовищно коварны и очень сильно вас ненавидят.
Более того, небольшая модификация алгоритма не позволит им даже сымитировать сообщения от вашего собеседника, вписав в них какую-то дезу и зашифровав их вашим открытым ключом.
Для борьбы с подобного рода подлогом используется ровно та же система.
Кстати, она, по совместительству, и есть «электронная подпись».
Прежде чем зашифровать сообщение вам вашим открытым ключом, собеседник сам шифрует его, но уже своим закрытым ключом. В этом случае получается обратная ситуация: любой может открытым ключом расшифровать это сообщение, но зашифровать его может только владелец ключа.
Таким образом, у нас получается что-то вроде системы из двух вложенных друг в друга контейнеров: внешний контейнер может расшифровать только адресат, внутри же него лежит контейнер, который мог бы расшифровать кто угодно, но зашифровать мог бы только конкретный отправитель, что позволяет адресату убедиться, что сообщение пришло именно от того самого собеседника и содержит оно ровно то самое, что этот собеседник написал.
Даже если коварный недруг попытается подменить или даже слегка изменить письмо, то получатель всё равно мгновенно узнает, что письмо изменено или подменено.
В результате у недруга остаётся только один вариант. Он может сгенерировать свою пару ключей и попробовать некриптографическими методами убедить адресата, что вот такой-то открытый ключ - это и есть ключ того самого Васи Пупкина, который разговаривает с адресатом.
Однако даже так он сможет лишь имитировать письма от некоторого конкретного собеседника, но не читать те, которые посылает адресату любой его другой собеседник.
Лекс Кравецкий
«XXII ВЕК», 18 апреля 2018
Необходимые пояснения о шифровании
Контроль и защита / апрель, 2018
Заметил, что многие граждане крайне превратно представляют себе современные (хотя, на самом деле, они не особо современные - им уже более полувека) алгоритмы шифрования. ©
Ключи и шифры
В частности, многие думают, будто бы при шифровании с двумя ключами собеседники тайно обмениваются своими закрытыми ключами, а потому можно куда-то там в середину вклиниться, перехватить ключ и всё расшифровывать.
Я вполне допускаю, что вам не довелось ознакомиться в детстве с книгами серии «Занимательная математика» или с интереснейшими произведениями Мартина Гарднера, которыми в советские времена зачитывался каждый второй школьник. Однако вы ведь всё-таки могли бы заглянуть хотя бы в Википедию - она открыта для всех и находится от вас на расстоянии нескольких кликов.
Так вот.
Шифрование с двумя ключами (иногда также называемое «шифрованием с открытым ключом») основано на асимметричности некоторых математических операций. Так оказывается, что некоторые операции довольно быстро вычисляются в одну сторону, но довольно медленно в другую, что делает практически невозможным подбор нужных операндов методом перебора за разумное время.
Грубо говоря, зная некое число икс, вы быстро можете вычислить значение некоторой функции f от этого икс. Но вот знание значения f(икс) не позволяет вам быстро найти сам икс, поскольку для функции f не существует простой обратной функции.
На этом свойстве и основаны крайне распространённые сейчас методы шифрования, которые используются практически вообще везде.
А именно:
- Желающий получать зашифрованные сообщения генерирует себе пару ключей.
- Один ключ, называемый «закрытым», он оставляет себе и никому никогда не показывает, если не хочет проблем. Второй ключ, называемый «открытым» он отсылает своему собеседнику.
- Собеседник шифрует свои сообщения при помощи открытого ключа и отправляет владельцу закрытого.
- Владелец закрытого расшифровывает это сообщение закрытым ключом.
Фишка тут в том, что открытого ключа недостаточно, чтобы расшифровать сообщение за разумное время. Это возможно, лишь если сами по себе ключи довольно короткие, а потому поиск закрытого ключа перебором будет всё-таки меньше времени жизни вселенной.
Именно поэтому открытый ключ адресат может разослать хоть всему человечеству: это никак и никому не поможет расшифровывать направляемые ему сообщения.
Да, всё человечество получит возможность что-то там зашифровать и послать этому адресату зашифрованное сообщение, но не расшифровать то, что ему послал кто-то ещё.
Даже если у всех имеется один и тот же открытый ключ.
На всякий случай, повторю ещё раз:
- Открытым ключом нельзя расшифровать за разумное время то сообщение, которое было зашифровано этим же открытым ключом. Для этого нужен закрытый ключ.
- Закрытый ключ ни на каком этапе никому не передаётся: ни тайно, ни явно. Его знает только сам адресат.
При переписке двух собеседников, каждый из них просто выполняет вышеописанные пункты: генерирует свой закрытый ключ и парный ему открытый, после чего передаёт открытый ключ своему собеседнику.
Оба собеседника и далее тоже делают совершенно симметричное: шифруют свои сообщения открытым ключом другого собеседника и пересылают ему. При этом расшифровать сообщения сможет только тот, кому оно адресовано, поскольку только у него есть закрытый ключ, требуемый для расшифровки сообщения.
Если, конечно, этот человек по незнанию не передал кому-то свой закрытый ключ.
Независимо от того, используется ли сервер только для установки соединения между собеседниками или через него проходят сами зашифрованные сообщения, никто, включая этот гипотетический сервер, не в состоянии узнать, что именно написано в зашифрованных сообщениях, если закрытые ключи были сгенерированы на компьютере самих собеседников и не были после этого переданы серверу или ещё кому-то.
Смысл устойчивых к взлому шифров именно в этом, а вовсе не в том, что для пересылки сообщений используются какие-то особо честные и не идущие на сделки сервера: зашифрованные таким способом сообщения можно слать даже через сервер ваших врагов и единственное, что они смогут сделать, - не переслать это сообщение адресату. Но прочитать его они не смогут, даже если они чудовищно коварны и очень сильно вас ненавидят.
Более того, небольшая модификация алгоритма не позволит им даже сымитировать сообщения от вашего собеседника, вписав в них какую-то дезу и зашифровав их вашим открытым ключом.
Для борьбы с подобного рода подлогом используется ровно та же система.
Кстати, она, по совместительству, и есть «электронная подпись».
Прежде чем зашифровать сообщение вам вашим открытым ключом, собеседник сам шифрует его, но уже своим закрытым ключом. В этом случае получается обратная ситуация: любой может открытым ключом расшифровать это сообщение, но зашифровать его может только владелец ключа.
Таким образом, у нас получается что-то вроде системы из двух вложенных друг в друга контейнеров: внешний контейнер может расшифровать только адресат, внутри же него лежит контейнер, который мог бы расшифровать кто угодно, но зашифровать мог бы только конкретный отправитель, что позволяет адресату убедиться, что сообщение пришло именно от того самого собеседника и содержит оно ровно то самое, что этот собеседник написал.
Даже если коварный недруг попытается подменить или даже слегка изменить письмо, то получатель всё равно мгновенно узнает, что письмо изменено или подменено.
В результате у недруга остаётся только один вариант. Он может сгенерировать свою пару ключей и попробовать некриптографическими методами убедить адресата, что вот такой-то открытый ключ - это и есть ключ того самого Васи Пупкина, который разговаривает с адресатом.
Однако даже так он сможет лишь имитировать письма от некоторого конкретного собеседника, но не читать те, которые посылает адресату любой его другой собеседник.
Лекс Кравецкий
«XXII ВЕК», 18 апреля 2018