Принципы шифрования и криптографии. Расшифруйте послание!
[музыка] Всем привет! Меня зовут Георгий Вольфсон, и это очередной выпуск моей авторской программы на канале Квер. Сегодня мы с вами, как уже было сказано, поговорим о шифровании.
Итак, давайте прежде всего зададимся таким вопросом: вот вы сами, наверное, когда учились в старшей школе, может быть, потом в институтах и так далее. Я, когда учился на матмехе, задался вопросом: а нафига всё это было надо? Ну, хорошо, когда мы ми о числах, об арифметике, о процентах, я ещё понимаю, где это применяется в жизни. Но если взять такую штуку, как, например, малая теорема Ферма, что если там взять какое-то натуральное число, возвести его в степень простую, то по модулю я лучше закончу да на этом.
Или, скажем, функция Эйлера, которая показывает количество чисел, меньших данного и взаимно простых с данным! Ужас! Я уже прямо вижу, как ваши уши свернулись в трубочки! На самом деле действительно выглядит страшновато и не очень понятно, где вот в реальной жизни это надо.
Но, больше я удивлю вас: на самом деле всё это мы используем каждый день, некоторые даже каждую минуту, когда отправляем сообщение с нашего мобильного телефона. Но обо всём по порядку. На самом деле идея шифровать свои сообщения возникла очень давно. Ну, действительно, много кому придёт в голову захотеть отправлять сообщение так, чтобы прочитать это мог только тот, кому сообщение адресовано.
Да, то есть, если вдруг так получилось, что канал связи — там, Раньше это была, может быть, голубиная почта или гонец, или кто-то ненадёжный, в данном случае, если мы говорим про V век. То могут перехватить просто информацию, которая пролетает там через облако. То разумеется, хотелось бы, чтобы те, кто перехватил информацию, по крайней мере, не могли её прочесть, то есть не могли ей воспользоваться.
Кстати, далеко-то за примерамиходить не надо. Наверняка, многим из вас хотелось бы, чтобы те лайки, которые вы ставите людям противоположного пола, были видны только этим самым людям, а не вашим половинкам, которые потом отсмариет страницы. Отсюда возникает мораль, что, наверное, свои данные надо как-то зашифровать.
И шифры были очень разные, и о некоторых я сегодня поговорю. Сразу скажу, что я не буду говорить о так называемых аппаратных шифрах, то есть когда, например, на теле татуированы. А я буду говорить о шифрах, так сказать, понятийных, то есть когда мы чисто физически делаем что-то с информацией, смещая, как-то заменяем и так далее, и получается какая-то бессмыслица, которую потом можно расшифровать.
Один из старейших шифров, который дошёл до наших дней, так называемый шифр Цезаря. Ну, это тот самый Цезарь, про которого вы подумали: который не салат, а который был в Древнем Риме. В чём суть шифра Цезаря? На самом деле идея такова, что берётся просто алфавит и каждая буковка сдвигается на одно и то же число букв вдоль этого алфавита.
Ну, например, вправо! То есть в этом случае, например, если я сдвину Цезарь, обычно то вместо буквы А у меня будет буква В, вместо буквы Б получится буква Г и так далее. Соответственно, если я скажу какую-нибудь фразу, например, "Математика — это круто" и сдвину каждую буковку на D, то у вас получится что-то вот такое. Как видите, выглядит бессмысленно.
То есть, если кто-то не знает принципа и получает такое сообщение, то он ничего не поймёт. И это для меня круто, потому что я хотел бы, чтобы он это не мог прочитать. С другой стороны, если кто-то знает о том, как в принципе работает шифр Цезаря, то расшифровать его не трудно.
Ну, действительно, сдвинем обратно на те же самые две единицы и получим исходное сообщение. Более того, если мы не знаем, что сдвиг именно на две единицы, то всё равно догадаться несложно. Мы можем просто сделать сдвиги на один, на два, на три, на четыре и так далее. Ну да, я буду это делать не 2 секунды, а может быть 22 минуты, но тем не менее довольно быстро расшифрую сообщения.
Там даже весь текст не надо расшифровывать, а по первому слову уже видно, получилось что-то осмысленное или нет. Поэтому Проблема шифра Цезаря была в том, что расшифровать его было довольно просто даже тем, кто не знал, насколько элементов идёт сдвиг. Это элементарно, и дальше развязалась своеобразная война между шифровальщиками и дешифровальщиками.
Была такая мечта, чтобы все разборки между школьниками, в частности, проходили не на кулаках, а с помощью мозгов. Ну, например, сили двое решают задачку: кто первый решил, тот девочку Тани провожает домой. Ну, к сожалению, это были только детские мечты, потому что я в кулачных боях обычно проигрывал.
Но тем не менее, если мы говорим про криптографию, там примерно так и происходит. То есть на протяжении уже тысяч лет соревнуются лучшие умы: одни пытаются зашифровать так, чтобы другие не расшифровали, а другие пытаются расшифровать то, что первые зашифровали. Цезарь разобрался. Что делать дальше? Дальше люди придумали усложнение шифра Цезаря, так называемый шифр простой замены.
Это значит, что каждый символ заменяется на какой-то другой символ, но теперь уже не со сдвигом, а произвольно. То есть, например, я А заменяю на Г, Б заменяю на Ш, В заменяю на Z и так далее. Сколько в этом случае будет вариантов? Не 33, как в прошлый раз.
У Цезаря даже меньше, потому что латинский алфавит. Но количество сдвигов-то было довольно коротким. А здесь давайте прикинем: первую букву я могу заменить 3Дм способами, если мы говорим про русский алфавит. Вторую букву? Ну, там есть некоторые тонкости в зависимости от того, заменил я А на B или нет. Сейчас не буду в них лезть, но в районе 31 способа и так далее.
Значит, общее количество способов сделать шифр простой замены даже, заменив буквы буквами, будет 32 факториал, и даже больше. Напоминаю, да, что 32 факториал — это произведение всех чисел от одного до 32. Короче, это много. То есть если вы просто ручками попытаетесь перебрать все варианты, вам не хватит всей своей жизни.
Если намер же моя собственная прихватит моё сообщение, которое записано циклом простой замены, то, ну, по крайней мере, ближайшие 10 лет она точно не потревожит, потому что она будет расшифровывать сообщения. Другой вопрос: что, опять же, дальше шарик перешёл к дешифровальщикам?
В тексте посчитать, сколько символов первого типа встречается, сколько второго, и разделить на количество символов. Мы узнаем частоту с которой встречается каждый символ. И если дальше мы возьмём наиболее частые символы, то я могу с большой степенью точности утверждать, что это за символы. В частности, в Википедии вы можете посмотреть таблицу частот для русского языка. Она уже заботливо составлена довольно давно.
Кстати, не глядя, можете попытаться угадать, какая буква в русском языке самая популярная. Ну вот я думаю, многие сейчас подумали про букву "А". На самом деле, нет, самое популярное, причём с небольшим запасом, это буква "О". Она в среднем встречается примерно 11 раз из 100. Второе и третье место по популярности практически делят буквы "А" и "Е", но "А" в нашем случае.
То есть посчитали символы и прикинули, что есть. Помимо этого, на самом деле есть ещё один способ расшифровывать такие тексты смысловой. Ведь, например, в текстах очень часто встречаются конкретные последовательности букв. Ну, например, имя того, кому отправлено это сообщение. И как видите, по этому имени можно расшифровать текст.
В частности, кстати, в литературе есть много примеров, когда использовался тот самый шифр простой замены. Прим заменяли буквы не обязательно буквами, но возможно и символами. В частности, многие, наверное, помнят повесть Конан Дойла, которая называлась "Пляшущие человечки", где каждая буковка заменяла соответствующим человечком.
И Шерлок Холмс, увидев одинаковую последовательность из четырёх букв в каждом сообщении, догадался, что это вполне возможно имя главной героини Ильси, и таким образом он получил целых три буквы: И, Л и С, через которые он дальше шифровал. Но вот и в последовательности человечков он видел, да, что первые и последние человечки одинаковы. Отсюда он и сделал этот самый вывод.
Вот в этом минус шифр простой замены. Поэтому люди научились расшифровывать и его. Дальше дело развивалось, развивалось. Примерно в середине XX века люди ещё использовали некоторые вариации шифра простой замены. В частности, знаменитая шифровальная машина Энигма, которую использовали немцы во время Второй мировой войны, она в общем-то основана на принципе, да, на шифре простой замены, но с некоторыми доработками.
Про них сегодня уже, наверное, говорить не будем. В любом случае, плюс этой машины был в том, что она, помимо всего прочего, ещё и позволяла быстро зашифровываться. [музыка] РСА по первым буквам фамилий тех людей, которые его изобрели, и он был основан в чистом виде на той самой математике, о которой мы говорили в начале: простые числа, малая теорема Ферма, функция Эйлера.
Вкратце расскажу, в чём идея, совсем в глубокую математику лезть не будем. Давайте вспомним такую штуку из начальной школы, а может быть, у кого-то там пятые-шестые классы, как разложение числа на простые множители. В чём суть? Ну, напомню, что число называется простым, если его можно представить в виде произведения только себя и единицы.
Ну, я говорю только про целые. Да, произведения, например, 2 — это 1 на 2, и всё. 3 — это 1 на 3, и всё. 4 — это не 1 на 4 только, а ещё и 2 на 2, поэтому 4 не простое. Ну и так далее. Насколько быстро мы можем разложить число в произведение двух простых множителей?
Ну, если оно раскладывается в такое произведение, если числа маленькие, то быстро. Например, 6 — что это такое? 2х3. 21 — что это такое? 7 на 3. 323 — что это такое? Ага, вот тут уже пауза, потому что число побольше. Если вы немножечко помучаете, то выяснится, что 323 — это 17 на 19. Но это разложение уже чуть более сложное, и даже компьютер тратит какое-то время на то, чтобы перебрать соответствующие варианты до 17, и вы что, число раскладывается как 17 на 19.
А теперь представьте себе, что исходные простые числа не 17 и 19, а тысячные. То есть их даже назвать тяжело. Мы с вами умеем называть там девятизначные, десятизначные числа, а тут, может быть, даже миллионозначное число. Да. И вот вы одно умножаете на другое. В этом случае сделать обратную операцию, то есть разложить на множители, не может в разумное время даже суперкомпьютер.
То есть требуются годы на то, чтобы сделать вот такую вроде простую вещь. Мораль: если я знаю, как разложить число на множители, то я могу использовать это разложение, а никто другой — нет. И вот это положено как раз в принцип шифрования. И, собственно, именно поэтому сейчас многие спецслужбы испытывают большие проблемы с различными мессенджерами, которые пользуются похожими алгоритмами шифрования.
В частности, не секрет, да, что тот самый мессенджер Telegram, про который сейчас много говорят, да, его не могут расшифровать. То есть просят у авторов этого мессенджера, да, авторов алгоритмов предоставить эти самые алгоритмы. Некоторые даже совсем грамотные люди просят предоставить некий шифр, да, чтобы расшифровать. На самом деле даже авторы алгоритма его не могут знать, потому что этот шифр, то есть вот эти простые числа, если говорить про более упрощённые вещи, они генерируются на самом устройстве.
То есть, например, у меня на телефоне, и там условный Павел Дуров не знает, какие числа сгенерировал мой телефон. Взял случайные простые числа. Я, правда, не утверждаю, что именно таким алгоритмом, который я сейчас описал, пользуется Telegram, но суть примерно такая. Более того, ещё один момент, про который хочется поговорить, что вот эта шифровка — это так называемая шифровка с открытым ключом.
Чем шифрование с открытым и закрытым ключами отличается? Давайте в двух словах тоже разберём. Если я хочу, например, с каким-нибудь другом из Австралии договориться о том, какой код я буду использовать, я, конечно, могу с ним договориться заранее. Но предположим, этой возможности у меня не было. То есть если бы я договорился, и мы оба знаем какой-нибудь пароль, который не знает никто другой — это так называемый закрытый ключ.
То есть есть какая-то закрытая штука, которую мы с ним оба знаем. Переводя в термины ключа, предположим, у нас есть некий сундук и два ключа от него, которые его открывают: один ключ у меня, другой у моего австралийского друга. Я просто пересылаю закрытый сундук с моим письмом, вложенным внутрь. Да, бумажным. И открыть его могу либо я, либо мой друг. Будем считать, что никто другой ключик подобрать, по крайней мере, не сможет, а другого ключа ни у кого и нет.
Но проблема в том, что возможно, мы даже и не виделись раньше, и у меня нет возможности передать ему ключ надёжный. Если я пошлю по почте, его могут перехватить. Правда, поэтому действует примерно такой алгоритм: смотрите, допустим, он хочет, чтобы я ему прислал письмо. Тогда он сам делает сундук, и он сам хранит от него ключ. У меня ключа нет. Он пересылает сундук, я в этот сундук засовываю письмо и захлопываю.
Другой, кто этот сундук перехватит, теперь я отправляю закрытый сундук обратно, и мой друг открывает ключом. Вот примерно так работает шифрование, о котором мы говорим. То есть открыто по сети пересылается большое-большое число, равное произведению двух простых — это тот самый сундук, а ключ от него — сами исходные два больших простых числа. Производи́те, да, это храню у меня.
Поэтому расшифровать, если что, могу только я, и это довольно круто. Итак, сегодня мы с вами поговорили о том, как же всё-таки математика, чуть более высокая математика, чем обычное действие с числами и проценты, помогает нам в реальной жизни, буквально в повседневной. То есть как мы этим пользуемся, когда просто пересылаем друг другу сообщения по защищённым каналам.
Вот именно на подобных идеях и строится современное шифрование. То, как оно работает в тех же самых мессенджерах, и поэтому расшифровать никто это дело не может. Ну, разве что с помощью паяльника, но про это мы так и быть говорить не будем. Так что если вы всё ещё сомневаетесь, зачем вам нужна была эта мудрёно математика и зачем она вообще нужна, просто посмотрите на экран своего мобильного телефона и больше не задавайте такого вопроса.
Ну, а на закуску вот вам небольшой зашифрованный текст. Надеюсь, тот, кто его разгадает, почувствует себя Шерлоком Холмсом. Текст перед вами, ждём успешных расшифровок! На этом всё, и до новых встреч. Подписывайтесь на наш канал, здесь ещё очень много интересных видео, и чтобы их посмотреть, ничего расшифровывать не надо. Удачи! [музыка]