Михаил Масленников – Занимательная криптография. Часть 1 (страница 1)
Михаил Масленников
Занимательная криптография. Часть 1
Предисловие
В детстве я очень любил читать книгу Я. И. Перельмана «Занимательная физика». В предисловии к одному из изданий этой книги сказано: «Составитель старался, насколько мог, придавать изложению внешне интересную форму, сообщать привлекательность предмету». Мне, будучи тогда еще школьником средней школы, очень нравилась манера изложения и разъяснения автором сложных физических понятий и эффектов, вопреки довольно скучному стилю типового учебника по физике. Недаром Яков Исидорович Перельман остался в памяти у многих поколений людей как замечательный популяризатор естественных наук, в частности физики и математики.
Слово «криптография», как я надеюсь, слышали многие. Это наука о тайнописи, известная еще с доисторических времен Цезаря и древней Спарты.
Классическая криптография – это наука о тайнописи, о том, как сохранить в тайне какое-то секретное сообщение от посторонних глаз. Для этого еще в глубокой древности придумали много разных способов, заменяя в секретном сообщении понятный текст на непонятный набор символов в зависимости от некоторого секретного ключа, известного только тем, с кем ведется секретная переписка. Отправитель и получатель должны иметь один и тот же секретный ключ – это классическая криптография, традиционная симметричная схема.
Пока вопросов нет, вроде все ясно даже простому человеку, далекому от криптографии. Но различные симметричные схемы шифрования были хороши только до определенного момента времени, до тех пор, пока не появились компьютеры и Интернет. Дело в том, что при появлении Интернета и компьютерных сетей резко возросла потребность в шифровании передаваемой по ним информации.
Потребность в шифровании резко возросла, следовательно, резко возросла и потребность в ключах, на которых осуществляется шифрование. И вот тут традиционные симметричные схемы оказались неудобными из-за того, что ключи для зашифрования и расшифрования должны быть одинаковыми у отправителя и получателя. Как этого добиться?
Первое, что приходит в голову – заготавливать комплекты секретных ключей заранее и выдавать их каким-то секретным способом абонентам, ведущим между собой секретную переписку. Сотни лет именно так и поступали, из-за чего симметричная криптография становилась все более тяжеловесной и неудобной для широкого практического применения.
Криптографы стали думать и гадать, как упростить процедуру шифрования, чтобы сделать ее доступной в обычных, повседневных случаях, не связываясь с тяжеловесной симметричной ключевой системой.
В середине 70-х годов ХХ века американцы совершили революцию в криптографии – предложили новые и весьма нетривиальные подходы к шифрованию сообщений, ввели такое понятие, как электронно-цифровая подпись, или сокращенно ЭЦП. В обиходе криптографов появилось такое понятие, как асимметричная криптография. С появлением и внедрением в повседневную жизнь компьютерных сетей и Интернета роль криптографии стала стремительно расти. Без нее сейчас немыслимы банковские расчеты в режиме OnLine, работа различных серверов, содержащих конфиденциальную информацию, защищенный обмен конфиденциальными сообщениями и многое, многое другое. Потребность в использовании криптографии стремительно растет, а осведомленность потребителей в современных криптографических методах защиты информации часто остается на прежнем уровне, когда все, что касалось криптографии, было строжайше засекречено.
Я решил попробовать изложить некоторые современные понятия криптографии на простом и понятном языке неискушенному читателю, популяризировать криптографию. Криптография – это один из разделов математики, поэтому при ее популяризации не обойтись без математических выкладок с математическими понятиями и формулами, которые могут быть непонятны рядовому читателю. Я, как мог, постарался объяснить их на простом житейском языке, частенько прибегая к различным выдумкам и фантазиям. Надеюсь, что получилась занимательная криптография, которая может быть полезной широкому кругу читателей.
Сказка про числа, которые не хотели делиться
В действительном множестве, рациональном подмножестве жили-были натуральные числа. То есть числа 1, 2, 3, 4, 5 и т.д. Их еще иногда «числами в натуре» называли. Основным занятием натуральных чисел было умножаться-делиться в соответствии с операциями умножения и деления. Про умножение – все понятно, любое число могло умножаться с любым другим числом без проблем, а вот с делением все обстояло куда как сложнее. Не со всяким другим числом могло делиться натуральное число, бывало заартачится: не хочу с ним делиться, хоть обнуляйте меня совсем! Столько споров и дискуссий вызывала эта операция деления натуральных чисел, что в конце концов она-то и стала главной в этой сказке.
Понятно, что все делились с числом 1, это число было вроде как Царь-Батюшка во всем множестве натуральных чисел (МНЧ). Но деление с этим числом было совсем безобидное, в результате такого деления каким было число до деления, таким и оставалось после него, вроде как лозунг «Коммунизм победит» в советское время – количество мяса в магазинах от него не изменялось. Поэтому все натуральные числа периодически исполняли этот религиозный обряд – деление на 1 – без каких-либо последствий для себя, просто как символ верности МНЧ и проводимой им политике арифметических операций.
У числа 1, как и у любого нормального Царя, была своя Администрация, где утверждали важнейшие арифметические Законы МНЧ: кто, с кем и как будет делиться. А в штате Администрации были молоденькие запятые, которые целыми днями отпечатывали эти законы на пишущих машинках, ибо компьютеров в те далекие времена в МНЧ еще не знали.
Ну а о другом важном числе – 0 – нельзя со 100% уверенностью сказать, что оно жило в МНЧ. У него был специальный особняк, который все другие числа называли Конторой числа 0, или просто Конторой. Все числа из МНЧ побаивались числа 0, а причина – простая. Само число 0 могло делиться на кого угодно, после чего результат навсегда попадал в Контору, а вот если кто-то сам пытался делиться на 0, то его без лишних эмоций превращали в лагерную пыль. То есть число 0 жило по своим арифметическим законам, отличным от законов МНЧ, и ожидать от него можно было всего, чего угодно.
Число 2 было хитрым. Оно разделило ровно пополам всех обитателей МНЧ на тех, кто с ним делился, и тех, кто это делать категорически отказывался. Первых число 2 называло честными и даже создало из них специальную партию: Партию Честных Чисел. Мы ее, для краткости и по привычке, всюду в этой сказке будем звать просто партией. В партии, как и положено, было создано Политбюро из наиболее известных честных чисел: 2,4,6 и 8. Параграф 1 Устава партии гласил, что в ней могут состоять любые числа, признающие Устав и Программу партии и оканчивающиеся на одного из членов Политбюро. Устав приняли под бурные и продолжительные аплодисменты, но когда число 2 принесло его на согласование в Контору, там параграф 1 дополнили: и 0. Так его и утвердил Царь. А Программа партии была простая: наша цель – бесконечность. Эту программу Царь признал светлым будущим всех прогрессивных чисел из МНЧ.
В партии сразу же появились карьеристы, которые стремились поделиться с числом 2 не один, а целых два раза. Они попытались было, по примеру старших товарищей, создать партию честных – пречестных чисел, но Царь сказал, что и одной партии вполне достаточно, две народ просто не прокормит. Так что название «честное-пречестное число» осталось на уровне анекдотов и народного фольклора.
Число 2, как партийный вождь, было очень идейным. «Удвоение ВВП», «Две нормы за смену» – такие лозунги постоянно появлялись на улицах МНЧ. Оно также очень скрупулезно следило за чистотой партийных рядов, не разрешая одному члену партии делиться на другого. Иногда за такие проступки могли и партбилет отобрать.
А вот за числом 3 закрепилась – как бы это поделикатнее сказать – отличная от числа 2 репутация. Алкогольная. Как соберутся в weekend числа отметить какое-нибудь событие, так обязательно разобьются на группы по три числа в каждой. Часто болела головушка у числа 3, допилось оно в результате до чертиков и стало мистическим символом МНЧ: три богатыря, три белых коня, пятилетку – в три года. Тяжело было числам из МНЧ строить свое светлое будущее – бесконечность, вот и почитателей у числа 3 было достаточно. Вместо красных носов у чисел ходило такое правило: число является алкоголиком, если сумма его цифр – алкоголик. Так и утвердил это правило Царь.
Еще пару слов про число 5. Оно было в Президиуме всех праздничных собраний и юбилейных дат, все в наградах и орденах аж до самого своего нижнего кончика, поэтому и звали число 5 нашим дежурным юбиляром. Безобидное число, партий своих создавать не пыталось, а на выборах всегда выдвигалось от единого и нерушимого блока честных и беспартийных. Делились на него те, у кого на конце было 5. Или 0, справедливо дополнили меня в Конторе.
Кстати, о Конторе. Там собирали разные сплетни из жизни МНЧ и вот какую историю я узнал от местных аборигенов.
В гости к жителям МНЧ часто заезжали другие, ненатуральные числа. И вот как-то раз приехал важный гость – заморское число π, ему как раз на днях исполнилось ровно 100 лет – два честных-пречестных юбиляра-разюбиляра. Естественно, по такому случаю число π устроило праздничный банкет, на который пригласило число 100 и другие числа: 1, 2, 4, 5, 10, 20, 25, 50, но только не 3. Число π терпеть не могло этого алкоголика, с которым его вечно путали. Ну, понятное дело, дым коромыслом, праздник в разгаре, гости начали разбиваться на группы по 3 числа. А число π никак не хочет принимать участие в группе из 3-х чисел, и, прихватив число 100, нашло себе компаньона – какого-то генерала с денщиком. Получилась как бы группа не на троих, а, с учетом денщика, на 3,14. Число π было жутко довольно, и, как потом писало число 100 в донесении числу 0, рассказывало неприличные истории про число 3. В частности, американский алгоритм шифрования 3DES – Triple DES – обзывало «Триппер DES».