Новости олимпиады по математике и криптографии

18 февраля 1404 года родился Леон Баттиста Альберти.



Мы предлагаем вашему вниманию статью к. т. н. Ларина Д. А., посвящённую вкладу Леон Баттиста Альберти в мировую криптографическую науку.

Главный революционный прорыв в европейской криптографической науке в XV веке совершил флорентиец Леон Баттиста Альберти (1404-1472) итальянский ученый, архитектор, теоретик искусства. Альберти намного превосходил своих современников и талантом, и любознательностью, и многосторонностью, и особой живостью ума. В нем счастливо сочетались тонкое эстетическое чувство и способность разумно и логично мыслить, опираясь при этом на опыт, почерпнутый от общения с людьми, природой, искусством, наукой, классической литературой. Болезненный от рождения, он сумел сделать себя здоровым и сильным. Из-за жизненных неудач склонный к пессимизму и одиночеству, он постепенно пришел к приятию жизни во всех ее проявлениях. Альберти получил юридическое образование в университете в Болонье. После тяжелой болезни Альберти переключил свое внимание с юриспруденции на искусство и науку. Его талант был универсален. Альберти обладал выдающимися способностями. Он является автором десяти научных трактатов по архитектуре (в т.ч. «О статуе», «О живописи», «О зодчестве»), он также писал поэмы, басни, комедии, музыку, был одним из лучших органистов своего времени. Будучи теоретиком искусства, он обобщил опыт гуманистической науки в изучении античного наследия. Альберти создал палаццо Ручеллаи, церковь Иль Джезу и ряд других замечательных произведений зодчества Италии. Трудолюбие Альберти было поистине безмерно. Он полагал, что человек, подобно морскому кораблю, должен проходить огромные пространства и «стремиться трудом заслужить похвалу и плоды славы». Как писателя, его одинаково интересовали и устои общества, и жизнь семьи, и проблематика человеческой личности, и вопросы этики.

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

Альберти с Дато гуляли в папских садах в Ватикане и заговорили, как часто это делали, о литературе. Немалое восхищение вызвал немецкий изобретатель, который мог взять до трех оригинальных работ какого-либо автора и за 100 дней с помощью подвижных литер изготовить более 200 копий. За один лишь контакт он мог воспроизвести на своей печатной машине копию целой страницы большой рукописи (Здесь идет речь об изобретении в 1440 году книгопечатания Иоганном Гуттенбергом (Германия, г. Майнц), оно заметно повысило грамотность населения Европы). Так они переходили от одной темы к другой, изумляясь человеческой изобретательности, пока Дато не выразил своего неподдельного восхищения людьми, которые могут использовать то, что называют шифрами…

– Вы всегда интересовались этими секретами бытия – сказал Дато, – Что Вы думаете об этих дешифровальщиках? Вы не пробовали свои силы в этом в меру своих познаний?

Альберти знал, что в обязанности Дато входила работа с шифрами. Вот, что он сказал папскому чиновнику:

– Вы начальник папского секретариата. Не приходится ли Вам иногда пользоваться этими вещами в делах очень важных для его святейшества?

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

Результатом этой беседы стала рукопись, написанная Альберти в 1466 или начале 1467 года, где излагаются основы частотного анализа, при этом Альберти заявляет, что додумался до этого метода совершенно самостоятельно. Трактат начинается с описания характерных особенностей латинского языка, затем Альберти коротко останавливается на особенностях итальянского языка и переходит к решению задачи вскрытия шифра простой замены на основе анализа повторяемости букв в тексте. Вот как он описывает процесс дешифрования:

«Сначала я рассмотрю вопрос о количестве букв и те явления, которые зависят от количественных закономерностей. Здесь гласные претендуют на первое место… Без гласной нет и слога. Поэтому, если вы возьмете страницу какого-либо стихотворного или прозаического латинского текста и отдельно подсчитаете в строках гласные и согласные, то вы наверняка убедитесь, что гласных очень много… Если все гласные на одной странице будут насчитывать, скажем, 300 букв, то количество всех согласных, вместе взятых, составит около 400 букв. Я заметил, что среди гласных буква «О», хотя и встречается не менее часто, чем согласные, но реже других гласных… Когда в конце слова согласные следуют за гласной, этой конечной согласной всегда будет «Т», «S» и «X», к которой может быть добавлена «С».

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

Однако Альберти предложил выход из положения – шифр многоалфавитной замены, являющийся стойким к частотному анализу. Принцип построения этого шифра заключается в следующем: для шифрования используются не один, как в простой замене, а несколько шифралфавитов. Первая буква шифруется по первому шифралфавиту, вторая по второму и т.д. «Диск Альберти» состоял из двух дисков – внешнего неподвижного (на нем были нанесены буквы в алфавитном порядке и цифры 1,2,3,4) и подвижного внутреннего диска, на котором буквы были переставлены. Процесс шифрования заключался в нахождении буквы открытого текста на внешнем диске и замене ее на букву с внутреннего диска, стоящую под ней. После этого внутренний диск сдвигался на одну позицию и шифрование второй буквы производилось уже по новому шифралфавиту.

Ключом данного шифра являлся порядок расположения букв на внутреннем диске и его начальное положение относительно внешнего диска.

Другим изобретением Альберти стали коды. Он предложил заменять на упорядоченные двух-, трех- и четырех цифровые комбинации слоги, слова и целые предложения (всего таких комбинаций 336). После этого цифры перешифровывались многоалфавитной заменой. Таким образом, Альберти одним из первых выдвинул идею «двойного шифрования» - текст, полученный в результате первого шифрования, подвергался повторному шифрованию другим шифром.

«Диск Альберти» является одним из первых механических устройств шифрования. Идеи Альберти использовались при создании дисковых шифрмашин в первой половине ХХ века, некоторые из них использовались в разных странах до 1980-х годов. В многоалфавитном шифре Альберти количество алфавитов равно числу букв в алфавите открытого текста плюс четыре. Альберти - изобретатель многоалфавитных шифров, которые, в основном, используются и в наши дни. Однако способ выработки последовательности алфавитов шифрованного текста и их выбор существенно усложнен; у Альберти он определялся циклическим сдвигом на единицу через заранее оговоренное количество шифруемых букв. Таким образом, процесс шифрования стал «динамичным».

Многоалфавитные шифры явились большим шагом вперед, но на практике не использовались в течение более четырех столетий. Потому, что многоалфавитная замена по сравнению с номенклатором отнимала слишком много времени, а «незначительная» ошибка при письме, например, пропуск буквы, приводила к таким искажениям, что получателю сообщения было не суждено расшифровать его даже при наличии верного ключа. В заключении рассказа о криптографической деятельности Альберти приведем следующую цитату: «Должен был появиться человек, - писал Леонардо Ольшки, - который, владея теорией и имея призвание к искусству и практике, поставил бы стремления своего времени на прочную основу и придал бы им определенное направление, в котором им предстояло развиваться в будущем. Этим многосторонним, но в то же время гармоническим умом был Леон Баттиста Альберти». 



Возврат к списку