Зная секретный ключ (5 ПОЛЯРНИК, 28 ЯРКОЗЕЛЁНЫЙ), прочтите наставление Центра
Зная секретный ключ (5 ПОЛЯРНИК, 28 ЯРКОЗЕЛЁНЫЙ), прочтите наставление Центра:
КЬАПЛД МКМЬЁЪ ДЭБВДМ УАФЗХС ЛШЬЖЖЧ ЩЖДЭЪМ.
Зная секретный ключ (5 ПОЛЯРНИК, 28 ЯРКОЗЕЛЁНЫЙ), прочтите наставление Центра:
КЬАПЛД МКМЬЁЪ ДЭБВДМ УАФЗХС ЛШЬЖЖЧ ЩЖДЭЪМ.
Расшифруй, пожалуйста, следующий текст: Си ечзмци хугэчв хтедоч, м тсд си чочхмц
Молодой человек заменил каждую букву в отправленной своей девушке СМС-ке порядковым номером этой буквы в русском алфавите. Получилось простое число: 3213333323162521206233. Что этот молодой человек написал своей девушке?
Расшифруйте следующий вопрос и ответьте на него:
5343934*150413*6*8156215044414**305041080?
Текст зашифрован с помощью таблицы: каждой цифра обозначает одну из трёх букв, расположенных под ней в таблице, а знак «*» — пробел или одну из букв «ю», «я».
Россия вновь заявила о себе на мировой арене науки! В нашей стране был создан один из самых мощных в мире 50-кубитных ионных квантовых компьютеров, и теперь Россия занимает третье место в мире среди владельцев квантовых технологий. Это знаменательное событие укрепляет наши позиции в области высоких технологий и открывает новые возможности для решения важнейших научных и практических задач.
На сегодняшний день всего шесть стран обладают квантовыми компьютерами с 50 кубитами и более, и теперь Россия входит в эту элитную группу. Ведущим игроком остаются США с их 56-кубитным компьютером от компании Quantinuum, но наш прогресс наглядно подтверждает, что Россия догоняет мировых лидеров. В 2023 году мы располагали квантовым компьютером на 16 кубитов, а теперь — на 50, и это далеко не предел.
Особенность нашего достижения в том, что Россия имеет компьютеры на всех четырёх ключевых квантовых платформах, включая ионные, что делает нас одним из трёх ведущих игроков в мире. К 2030 году в России появится квантовый компьютер на 100 кубитов.
Квантовые компьютеры могут решать задачи, которые обычные компьютеры не осилят даже за десятки лет. Эти машины способны ускорять вычисления в таких сферах, как искусственный интеллект, криптография, обработка больших данных и многое другое. Главное — это не просто демонстрация технологического превосходства, а реальная возможность применения квантовых технологий для решения прикладных задач.
Наши учёные используют этот компьютер для ускорения машинного обучения и решения сложных прикладных задач, что даёт России уникальное конкурентное преимущество.
И главное: эта технология суверенна, она создана и развивается в нашей стране - России.
В условиях, когда российских учёных выдворяют из проекта Большого адронного коллайдера, такие достижения имеют особое значение. Мы уверенно движемся в будущее, обладая ключевыми технологиями, которые могут изменить не только науку, но и мировую экономику.
Подписывайтесь, чтобы не отставать от квантовых исчислений и других новостей: https://t.me/SNN_Russia/132
Вы слышали о кладе Томаса Бейла? Двести лет назад золотоискатель Бейл спрятал где-то в Америке клад из серебра, золота и драгоценных камней – и оставил об этом три зашифрованных документа. Второй документ удалось расшифровать, а вот первый и третий пока никому не дались. Многие до сих пор мечтают найти этот клад (между прочим, его стоимость примерно 30 миллионов долларов).
Кстати, не хотите попытать счастья? Местоположение клада – вот оно, надо только суметь прочитать...
А знаете ли вы, чем прославил своё имя математик Христиан Гольдбах?
Тем, что в в 1742 году сформулировал гипотезу, истинность которой общепризнана, хотя за два с половиной столетия никому не удалось её доказать. Гипотеза очень простая:
(Может быть, вы докажете? )
Простое число – это натуральное число, которое делится только на само себя и на единицу. (Результатом деления его на любое другое число будет дробь.) Почему гипотезу Гольдбаха не удаётся доказать? Ведь очевидно, что 7 является суммой простых чисел 3, 2 и 2 – и так далее?
Вот именно – «и так далее». Можно заниматься подобными вычислениями годами, даже десятилетиями и убеждаться, что каждое новое нечётное положительное целое число, найденное вами, будет соответствовать гипотезе. Но!.. никто ещё не предложил убедительных доказательств того, что не существует нечётного положительного целого числа, которое не является суммой трёх простых чисел. Почему? Потому что нечётных чисел бесконечное множество и доказать верность гипотезы для каждого из них невозможно...
А знаете ли вы, что Гольдбах жил и работал в России... кем?
Ну-ка угадайте!.. (Напишите, кто уже догадался.)
Гольдбах служил при коллегии иностранных дел, то есть, говоря языком современным – в МИДе. Он был статским советником – это генеральский чин! А в 1760 году Гольдбах был пожалован в тайные советники с огромным по тем временам жалованием в 4500 рублей. За что такие деньги и почести? Математику? Да ещё в министерстве иностранных дел?
...За то, что Гольдбах блестяще владел искусством дешифровки. Секретные письма прусских, австрийских, французских послов и министров для него были «семечками». Русская дипломатическая служба читала тайную переписку, была в курсе самых мелких подробностей при заграничных королевских дворах, и Россия извлекала из этого огромную пользу – и во время войны, и во время мира.
Дешифровкой дипломатической переписки также занимались и другие известные математики – Даниил и Николай Бернулли, Леонард Эйлер, Павел Шиллинг (попутно он изобрёл ещё и электрический телеграф собственной конструкции). Вот вам и математики на разведывательной службе!
А знаете ли вы, для чего был сконструирован первый в мире цифровой компьютер – «прадедушка» всех современных ноутбуков, десктопов и планшетов? Случилось это в 1943 году, и был этот компьютер предназначен для «взлома» американцами шифров – прежде всего немецкого и японского, но также и советского, и даже британского. Знать тайны союзников иногда не менее важно, чем тайны врагов, знаете ли... А американский математик Клод Шеннон после войны написал целую книгу, которая так и называется – «Теория связи в секретных системах», и книга эта не про плащи и кинжалы, не про яды и револьверы, а математика, математика, снова математика!
Шведский математик Арне Берлинг в середине 30-х годов прошлого века, перед самой войной, сумел «взломать» советскую систему секретной связи. Эту информацию во время Зимней Войны шведы передавали финнам – и те этой информацией пользовались чрезвычайно умело! Финское командование знало о том, что советские бомбардировщики взлетают с аэродромов ещё до взлёта – и советская авиация сбрасывала бомбы по совершенно пустым целям. С помощью этой информации финны смогли нанести нашей армии тяжёлое поражение под Суомусалми и захватить большое количество военной техники и имущества. Вот что может сделать всего лишь один-единственный математик! И пока наша разведка не догадалась, что финны нас «тотально прослушивают», нашим войскам было очень нелегко...
Вообще, «секретные сообщения» изучают две разные науки. В чём-то схожие, в чём-то совсем непохожие друг на друга. Одна изучает именно шифры – буквенные и цифровые системы секретной передачи данных. Она называется «криптография». Вторая изучает не только буквы и цифры, но и вообще технику секретной передачи данных, создание скрытых сообщений. Она называется «стеганография».
Понимаете разницу? Зашифровать тайное донесение – задача криптографии. А вот искусно зашить это донесение в сапог или разрезать на части и спрятать в горсти пустых внутри грецких орехов в продуктовом мешке – это уже стеганография.
Криптография и стеганография возникли параллельно, примерно в одно и то же время. Сложно сказать, кто был изобретателем первых «секретных систем передачи данных» – древние военные, жрецы, ремесленники, астрологи, врачи? Скажем, древний мастер знает рецепт изготовления особенной краски – яркой и стойкой. Но рецепт этой краски необходимо держать в тайне, иначе её начнут делать все подряд! И вот мастер придумывает особые значки и записывает рецепт «тарабарской азбукой». Или изобретает невидимые чернила. Или прячет буквы рецепта между другими буквами!
Вы, наверное, видели когда-нибудь, как пишут арабскими буквами? Для непосвящённого искусная арабская «вязь», особенно древняя (куфическая) – это бессмысленный набор линий, точек и палочек. Но в этом узоре может быть спрятан самый настоящий текст! В Азербайджане, в столице государства, в Баку, находится замечательный памятник архитектуры – дворец Ширван-шахов. Мавзолей, находящийся внутри дворца, украшает торжественная арабская надпись:
Величайший султан, великий ширваншах, тёзка пророка Аллаха, защита веры Халиль-Улла, да увековечит Аллах его царство и власть, приказал выстроить светлую гробницу для своей матери и своего сына, да помилует их Аллах. Восемьсот тридцать девятый год [1435 по нашему исчислению].
Но султан, сами понимаете, сам ничего не строил. Долгое время считалось, что имя строителя мавзолея утрачено – но в 1954 году архитекторы приставили к одному из декоративных медальонов по бокам от главного входа зеркало – и прочли другую, скрытую надпись!
Аллах, Мухаммад Али, архитектор
Узнай султан о том, что мастер посмел оставить свой «автограф» на стене мавзолея, рядом с именем султана, бедняге Мухаммаду Али немедленно отрубили бы голову. Но архитектор был хитёр и искусно «врисовал» свою монограмму в орнамент, так что почти пятьсот лет никто такого не подозревал!
Вот такие вот «спрятанные», «хитрые» надписи изучает стеганография. Ну, а если вы знакомы со сборником рассказов о Ленине писателя Михаила Зощенко, то должны помнить оттуда забавный рассказ «Иногда можно кушать чернильницы». Ленин не шифровал текст (криптография), он писал его молоком – то есть невидимыми, «симпатическими» чернилами (стеганография).
Кстати, проверяли? Работает?
Ещё с IV века до нашей эры известны «доска Энея» и «книга Энея». Эней был знаменитым древнегреческим полководцем – однако это почти всё, что мы о нём знаем. Он придумал, как шифровать текст с помощью узелков на длинной нити! Нить обматывалась на специальной линейке, которая и была ключом к шифру. Гонец вместо пергамента или папируса нёс просто невинную нить или шнурок с узелками – сами понимаете, такую вещь можно легко спрятать в складках одежды или даже в волосах. Получивший нить доставал в точности такую же линейку, и читал секретное донесение!
Эней придумал и другой вид тайнописи – вместо донесения посылалась книга, обычного содержания, скажем, какие-нибудь стихи. Только нужные буквы были аккуратно надколоты иглами! Знающий об этом мог тайное послание прочесть, а никто другой – нет.
Однако хватит истории. Давайте поиграем!
Самый элементарный шифр, который только можно придумать, это «простая подстановка». Его так и называют часто – «детский» шифр или «пионерский». Потому что его обожают использовать дети, играющие в военные игры. Расставим все буквы по алфавиту и каждой букве припишем номер: буква А – 1, буква Б – 2, буква В – 3 и так далее.
Тогда, скажем, название нашего журнала ЛУЧИК превратится в 13 21 25 10 12.
Почему этот шифр «детский»? Потому что он очень прост. Для того, чтобы его взломать, достаточно догадаться, на каком языке текст написан. То есть буквы какого алфавита мы использовали. Обратите внимание, это важно: если мы знаем, что надпись сделана по-русски, то моментально расшифруем.
А если латинскими буквами? Пронумеруем латинский алфавит и подставим буквы на место цифр:
13 21 25 10 12 – M U Y J K
Кхм... вместо «лучика» какой-то «мужик» получился, уж извините.
Тем не менее, для того, чтобы «угадать» язык послания, есть много способов. Скажем, простой счёт разных букв! Если их 26 (как в английском алфавите), мы имеем дело с латиницей. Если 28 – как в арабском – то «подозрение» падает на арабский язык. Если 33 – то на русский... А вот в рассказе «Золотой жук» у Эдгара По главный герой сразу же знает, что к нему в руки попал зашифрованный текст на английском языке. Откуда? Под текстом стояла подпись, рисунок козлёнка (по-английски «кид»). Игра слов «кид» и «Кидд» (имя пиратского капитана) возможна только в английском языке – и дальше легко, просто рассуждая логически, Легран «взламывает» шифр и находит клад. Хотя внешне документ выглядит жутковато:
53‡‡†305))6*;4826)4‡.)4‡);806*;48†8 !60))85;1‡(;:‡*8†83(88)5*†;46(;88*96 *?;8)*‡(;485);5*†2:*‡(;4956*2(5*—4)8 !8*;4069285);)6†8)4‡‡;1(‡9;48081;8:8‡ 1;48†85;4)485†528806*81(‡9;48;(88;4 (‡?34;48)4‡;161;:188;‡?;
Как герой рассказа разгадал эту загадку? С помощью математического метода, который называется «частотным анализом». Несмотря на современное название, сам метод очень древний – впервые его описал в своей книге арабский математик, музыкант и астроном Абу Юсуф аль-Кинди, ещё в IX веке нашей эры! В чём смысл этого метода? Опять-таки, в умении считать, а также хорошем знании языка оригинала! Скажем, в арабском языке самое распространённое слово – это определённый артикль «аль-». В английском – артикль «the». Кому было адресовано секретное донесение? Кто его составил? Все письма обычно начинаются со слов типа «здравствуйте» и заканчиваются словами типа «до свидания»... Нельзя ли здесь отыскать ключ к разгадке?
Вот и Легран – зная, что в английском слово «the» встречается очень часто, определяет: знак ; в шифровке означает букву t, знак 4 – букву h, а знак 8 – букву e. Так постепенно, букву за буквой, он «распутывает» эту, казалось бы очень сложную, головоломку.
А вот в рассказе про Шерлока Холмса и пляшущих человечков (а это тоже шифр с простой заменой) «ключом» послужило женское имя «Илси». Сыщик знал, что записки часто начинаются с имени того, кому они адресованы – и угадал верно!
С романом «Жангада» у Жюля Верна, кстати, случилась прелюбопытнейшая ситуация. Этот роман печатался в юношеском журнале «Обучение и развлечение» по главам. Писатель вставил в текст самое настоящее шифрованное сообщение – но... вышла промашка! Шифр, который он использовал, был слишком простым – и многие юные читатели смогли этот шифр «взломать», прочитать и тем самым узнать «что же будет дальше». В итоге Жюль Верн был вынужден использовать в книге более сложный шифр – так называемый шифр Виженера. Этот шифр – более крепкий орешек, математики не умели его взламывать целых триста лет! Однако в конце концов научились.
Напоследок давайте научимся составлять секретные сообщения «методом шахматной доски», он же «метод Кардано». Кстати, Джероламо Кардано – это ещё один математик (а ещё заодно астролог, изобретатель и врач) в нашем рассказе. Возможно, вы знаете про карданов вал в автомобиле. А может быть, слышали про формулу Кардано (мы про неё, кстати, скоро напишем). А вот сегодня расскажем, как сделать «решётку Кардано».
Возьмите лист плотной бумаги или картона и аккуратно начертите на нём квадратную «шахматную доску» из 64 клеток (8 клеток на 8). Клетки внимательно пронумеруйте так, как показано на рисунке.
Цифры в каждой четверти «решётки» (мы для наглядности раскрасили четверти в разные цвета) идут от 1 до 16, причём сначала слева направо, затем сверху вниз и справа налево, затем снизу вверх и слева направо, и наконец справа налево и снизу вверх. Запутаться можно, но вы постарайтесь, и у вас всё получится. Вы можете использовать цветные фломастеры или карандаши для того, чтобы раскрасить доску или цифры, то есть правильно расставить цифры по квадратам доски.
Затем внутри маленьких «угловых квадратов» 4 на 4 клетки нужно вырезать по одной или нескольку клеток в каждой строке. А можно вообще не вырезать. Но действовать по строгому правилу: если квадратик с таким номером уже был вырезан в другом «углу», то вырезать его уже нельзя! У нас получится решётка, «сетка».
Отверстия в решетке Кардано прорезаются так чтобы цифры не повторялись
Наложите ее на бумагу и в получившихся окошечках начните писать свой текст.
Затем поверните сетку на девяносто градусов и продолжайте писать сообщение – в «окошечках», если всё было сделано правильно, будет только чистая бумага! Заполните их и поверните решётку ещё раз. И снова пишите.
И ещё.
И ещё.
В результате, когда вы снимете решётку, у вас получится «секретное сообщение» – бессмысленная чехарда из рассыпанных в беспорядке букв.
Но стоит наложить сетку Кардано на бумагу и повернуть 4 раза – и ваше секретное сообщение станет видимым, читаемым! Такое секретное послание станет отличным подарком для друга. Или пригодится для игры в шпионов, уж как сами решите!
А применялись ли такие решётки в действительности, настоящими секретными агентами? – спросите вы. О, ещё как! Например, большим любителем шифровать свои письма с помощью хитро вырезанных решёток Кардано был знаменитый кардинал де Ришелье из романа «Три мушкетёра». Очень долгое время такие решётки были настоящими «королями дипломатической секретной переписки». Почему? Потому что они просты в изготовлении, удобны, а главное – позволяют передавать сообщение «прямым текстом», не шифруя. Упрощённый вариант «решётки» – метод, когда в тексте нужно читать (по предварительной договорённости) строго определённые слова. Тут мы снова можем вспомнить детективные рассказы о Шерлоке Холмсе. Сыщик читает записку, на первый взгляд совершенно бессмысленную:
С дичью дело, мы полагаем, закончено. Глава предприятия Хадсон, по сведениям, рассказал о мухобойках все. Фазаньих курочек берегитесь.
Но потом он догадывается, что читать нужно только каждое третье слово! И записка становится совершенно ясной:
Дело закончено. Хадсон рассказал всё. Берегитесь.
А вот как выглядела настоящая решётка Кардано для дипломатической переписки.
Письмо написано элегантным каллиграфическим почерком по моде XVI или XVII века. Выглядит оно совершенно невинно, как простое очень вежливое купеческое письмо, скажем, от одного торговца или банкира к другому. Однако при наложении решётки «выплывает» сообщение совершенно иного характера: «Испания в мае отправляет корабли на войну». А знание того, когда и какими силами враг собирается напасть на тебя – знание бесценное, что в XVI веке, что в XXI...
Познакомиться с журналом "Лучик" можно по этой ссылке.
Будем рады, если он вам понравится!
А это наш телеграм-канал: https://t.me/luchik_magazine Он не дублирует этот канал, там мы публикуем другие статьи! Присоединяйтесь!
Допустим я хочу зашифровать суперважное сообщение. Для ключа я использую 2 книги, о которых знаю только я и получатель сообщения. В сообщении я пишу что-то подобное: 1.12.13, 2.67.54, где 1 - это книга, 12 - это страница, 13 - слово. Как быстро суперкомпьютеры смогут разгадать этот шифр и смогут ли вообще и каким образом?
Дисклеймер: Никаких сверсекретных сообщений у меня нет и не будет. Вопрос чисто из человеческого любопытства.
В 1868 году математик Чарльз Доджсон (более известный как Льюис Кэрролл) заявил, что схема шифрования под названием «шифр Виженера» является «невзламываемой». У него не было доказательств, однако имелись убедительные подтверждения этой веры: математики безуспешно пытались его взломать более трёх сотен лет.
Была лишь одна небольшая проблема: на самом деле, пятью годами ранее её взломал немецкий пехотный офицер Фридрих Касиски, описав решение в книге, привлёкшей на тот момент мало внимания.
Криптографы играли в эти «кошки-мышки», создавая и взламывая шифры, ещё с тех пор, как люди впервые начали передавать секретную информацию. «Тысячи лет люди пытались найти ответ на вопрос: сможем ли мы разорвать этот круг?», — рассказывает криптограф Рафаэль Пасс из Cornell Tech и Корнеллского университета.
Пять десятилетий назад криптографы сделали широкий шаг в этом направлении. Они продемонстрировали, что можно создавать доказуемо защищённые шифры, если есть доступ к единственному ингредиенту — односторонней функции, которую легко вычислить, но сложно обратить. С тех пор исследователи придумали широкий спектр вариантов односторонних функций, от одиночных операций, основанных на умножении, до более сложных геометрических или логарифмических процедур.
Сегодня подобные функции используются в Интернет-протоколах для выполнения таких задач, как передача номеров кредитных карт и цифровых подписей. «Основная часть используемой в реальном мире криптографии может быть основана на односторонних функциях», — объясняет криптограф Юваль Ишаи [Uval Ishai] из Техниона (Хайфа, Израиль).
Но это достижение не положило конец игре в «кошки-мышки», а лишь сузило её рамки. Теперь криптографам не нужно беспокоиться о защищённости всех аспектов криптографической схемы, им достаточно лишь заниматься лежащей в её основе функцией. Но ни для одной из ныне используемых функций не было определённо доказано, что они являются односторонними, мы даже не знаем точно, существуют ли истинные односторонние функции. Криптографы доказали, что если их нет, то защищённая криптография невозможна.
В условиях отсутствия доказательств криптографам остаётся лишь надеяться на то, что пережившие все атаки функции на самом деле являются надёжными. У исследователей нет обобщённой методики изучения защищённости этих функций, поскольку, по словам Ишаи, каждая функция «взята из своей предметной области и разработана своей командой специалистов».
Криптографы уже давно задавались вопросом, существует ли более обобщённая методика изучения. «Существует ли некая главная задача, которая позволит нам понять, возможна ли криптография в принципе?», — задаётся вопросом Пасс.
Недавно они с аспирантом Корнеллского университета Яньи Лю [Yanyi Liu] доказали, что она существует. Эти учёные доказали, что существование истинных односторонних функций зависит от самой старой и фундаментальной задачи в другой области computer science под названием «теория сложности», или «вычислительная сложность». Эта задача, называемая колмогоровской сложностью, касается определения того, насколько сложно отличить случайные строки чисел от строк, содержащих некую информацию.
Криптограф Cornell Tech и Корнеллского университета Рафаэль Пасс помог найти вопрос, ответ на который позволит выяснить, действительно ли существуют односторонние функции, а значит, и вся современная криптография.
Лю и Пасс доказали, что если конкретная версия колмогоровской сложности является сложновычисляемой, то истинные односторонние функции существуют и есть чёткий способ построения такой функции. Если же эту версию колмогоровской сложности вычислить легко, то односторонних функций не может существовать. «Оказалось, что эта задача, возникшая ещё до того, как люди придумали односторонние функции, полностью их характеризует», — рассказывает Пасс.
Из этого вывода следует, что вместо того, чтобы подыскивать варианты односторонних функций, криптографы могут просто сосредоточить свои усилия на понимании колмогоровской сложности. «Всё зависит от этой задачи», — говорит Ишаи. Доказательство стало «качественно новой работой в фундаментальной криптографии».
Статья стимулирует к более тесному сотрудничеству криптографов и специалистов по теории сложности, вызвав всплеск активности по объединению их методик. «Несколько исследовательских групп уже работают над более глубоким изучением проблемы», — сообщил специалист по computer science Райан Уильямс из Массачусетского технологического института.
Вычисление сложности
Обычно сложность задачи является препятствием. Однако в криптографии, где её можно использовать против своих противников, это благословение. В 1976 году Уитфилд Диффи и Мартин Хеллман написали новаторскую статью в которой написали, что высокая сложность односторонних функций — это именно то, что нужно криптографам в условиях зарождающейся компьютерной эпохи. «Мы стоим на пороге революции в криптографии», — заявили они.
функцию, которая гарантированно была бы односторонней функцией, если они вообще существуют. Однако, по словам специалиста по computer science Эрика Эллендера из Ратгерского университета, эта конструкция была «очень искусственной». «Изучать её можно только для того, чтобы получить такой результат».
На самом деле криптографы стремились найти универсальную одностороннюю функцию, возникшую из некой естественной задачи; она могла бы дать истинное понимание того, существуют ли односторонние функции. Исследователи давно думали о конкретной задаче, появившейся в 1960-х: колмогоровской сложности, являющейся мерой случайности. Однако её связь с односторонними функциями была слабой и ускользающей.
Пасса восхитила эта связь, когда в 2004 году он был аспирантом. На протяжении долгих лет он экспериментировал с этой задачей, но без особого успеха. Однако он чувствовал, что в ней что-то скрывается, и всплеск внимания к колмогоровской сложности за последние пять лет лишь подстегнул его интерес.
Пасс попытался убедить многих аспирантов исследовать этот вопрос вместе с ним, но ни один из них не захотел заниматься тем, что может оказаться бесплодным проектом. Потом аспирантом Корнеллского университета стал Яньи Лю. «Яньи был бесстрашен», — вспоминает Пасс. Вместе они погрузились в изучение задачи.
Что такое случайность?
Концепцию случайности, по самой её природе, сложно объяснить. Есть комикс про Дилберта, в котором на экскурсии по офисам компании Дилберту показывают «генератор случайных чисел» бухгалтерского отдела. Тот оказывается монстром, постоянно повторяющим число 9. «Вы уверены, что он случаен?», — спрашивает Дилберт. «В этом-то и есть проблема случайности — точно никто не знает», — отвечает его гид.
Яньи Лю работал с Пассом над выявлением значимой связи между односторонними функциями и колмогоровской сложностью.
Если кто-то покажет вам строки чисел 99999999999999999999 и 03729563829603547134, и скажет, что их выбрали случайно, то вы не сможете опровергнуть это заявление со всей определённостью: при выборе случайных чисел вероятность создания обеих строк одинакова. Однако вторая строка определённо кажется более случайной.
«Мы считаем, что знаем, что имеем в виду, когда говорим „это случайные данные“. Однако до появления концепции колмогоровской сложности у нас не было математически значимого определения», — говорит Эллендер.
Чтобы прийти к понятию случайной строки чисел, в 1960-х годах Андрей Колмогоров решил сосредоточиться не на процессе генерации строк, а на простоте их описания. Строку 99999999999999999999 можно кратко записать как «20 девяток», однако у строки 03729563829603547134 может и не быть более короткого описания, чем сама строка.
Колмогоров определил сложность строки как длину кратчайшей возможной программы, создающей на выходе эту строку. Если мы имеем дело, допустим, со строками из тысячи цифр, некоторые из них имеют очень короткие программы, например, «напечатать тысячу девяток» или «напечатать число 23319» или «напечатать тысячу знаков пи при помощи следующей формулы...». Другие строки невозможно описать кратко и мы не можем получить программы короче, чем так, которая просто записывает строку целиком и приказывает компьютеру её вывести. А для некоторых строк длина программ находится где-то посередине.
Колмогоровская сложность быстро стала одной из базовых концепций computer science. Это понятие настолько фундаментально, что в 1960-х его по отдельности обнаруживали несколько раз. По словам Пасса, это «глубокая задача, не просто о случайности и математике, но и о науке в целом»..
Однако колмогоровская сложность имеет один недостаток: она невычисляема, то есть не существует программы, способной вычислить сложность любой возможной строки. Мы знаем это, потому что если бы такая программа существовала, мы бы пришли к противоречию.
Чтобы понять это, представим, что у нас есть программа, способная вычислить колмогоровскую сложность любой строки. Назовём эту программу K. Теперь давайте найдём наименьшую строку чисел (назовём её S), колмогоровская сложность которой вдвое больше длины K. Чтобы перейти к конкретике, представим, что K состоит из 1 миллиона символов, поэтому мы будем искать строку S, колмогоровская сложность которой равна 2 миллионам (то есть кратчайшая программа, выводящая S, содержит 2 миллиона символов).
Благодаря наличию программы K вычислить S легко (хоть и необязательно быстро): мы можем написать новую программу под названием P. По сути, программа P приказывает: «Пройди по всем строкам по порядку, используя программу K для вычисления их колмогоровской сложности, пока не найдёшь первую, колмогоровская сложность которой равна 2 миллионам». При создании программы P нам потребуется использовать программу K, поэтому суммарно P будет немного больше 1 миллиона символов. Однако эта программа выводит S, а мы определили S как строку, кратчайшая программа которой содержит 2 миллиона символов. Мы пришли к противоречию.
Однако это противоречие испаряется, если вместо поиска кратчайшей программы, выводящей строку, мы будем искать кратчайшую достаточно эффективную программу, выводящую строку (и
здесь нам нужно указать, что означает «достаточно»). В конечном итоге, для выполнения программы P потребуется огромное количество времени, ведь ей нужно проверить очень много строк. Если мы запретим такие сложные программы, то придём к понятию «ограниченной по времени» колмогоровской сложности. Эта версия колмогоровской сложности вычисляема — мы можем вычислить ограниченную по времени колмогоровскую сложность для любой возможной строки, по крайней мере, теоретически. И в некотором смысле эта концепция столь же естественна, как и сама колмогоровская сложность. Ведь в конечном итоге, по словам Пасса, на самом деле нас волнует только следующий вопрос: «Можно ли сгенерировать строку, пока мы ещё живы, или пока существует Вселенная?»
Так как ограниченная по времени колмогоровская сложность вычисляема, естественно возникает следующий вопрос: насколько сложно её вычислить. И Лю с Пассом доказали, что в этом вопросе скрывается ключ к ответу о существовании односторонних функций. «Это замечательное открытие», — утверждает Эллендер.
В частности, допустим, мы стремимся решить менее амбициозную задачу, чем вычисление точной ограниченной по времени колмогоровской сложности каждой возможной строки: допустим, нам вполне достаточно вычислить её приблизительно и лишь для большинства строк. Лю и Пасс показали, что если существует эффективный способ сделать это, то истинных односторонних функций существовать не может. В таком случае все наши кандидаты на роль односторонних функций мгновенно окажутся взламываемыми, не только теоретически, но и практически. «Тогда можно попрощаться с криптографией», — говорит Пасс.
И наоборот, если задачу вычисления приблизительной ограниченной по времени колмогоровской точности слишком сложно решить эффективно для множества строк, то, как продемонстрировали Лю и Пасс, истинные односторонние функции обязаны существовать. На случай, если это так, в их статье даже приводится конкретный способ создания такой функции. Описанная в их статье односторонняя функция слишком сложна для использования в реальном применении, однако, по словам Ишаи, в криптографии практические конструкции часто следуют за теоретическими прорывами. Он считает, что непрактичность односторонней функции Лю и Пасса «не является фундаментальным ограничением».
И если их функцию можно сделать практичной, её следует предпочесть другим кандидатам на роль односторонних функций, основанным на умножении и других математических операциях. Если уж односторонняя функция существует, то она будет такой. «Если мы сможем сломать подобную схему, то и все остальные схемы тоже могут быть сломаны», — утверждает Пасс.
Расширение теории
Статья породила каскад новых исследований на стыке криптографии и теории сложности. По словам специалиста по теории сложности Рахула Сантханама из Оксфордского университета, хотя обе дисциплины исследуют сложность вычислительных задач, они подходят к этому вопросу под разными углами. Он считает, что криптография подвижна, прагматична и оптимистична, а теория сложности медленна и консервативна. В последней «есть давно нерешаемые вопросы, и что-то происходит лишь раз в десяток лет. Однако эти вопросы очень глубоки и сложны».
Теперь у криптографии и теории сложности появилась общая цель и каждая из областей предлагает свежий взгляд на неё: у криптографов есть причины считать, что односторонние функции существуют, а у специалистов по теории сложности есть столь же весомые причины думать, что ограниченная по времени колмогоровская сложность является сложной задачей. Благодаря новым исследовательским результатам обе эти гипотезы подкрепляют друг друга.
«Если вы верите, что задача колмогоровской сложности сложна, то верите и в существование односторонних функций. А если вы верите в криптографию, то вам придётся поверить, что эта версия ограниченной по времени колмогоровской сложности обязана быть сложной».
Сегодня криптографы столкнулись с задачей приведения односторонней функции Лю и Пасса в более практичный вид. Также они начали исследовать, есть ли другие «главные задачи», наряду с ограниченной по времени колмогоровской сложностью, которые тоже могут руководить существованием односторонних функций или более сложных криптографических инструментов. Тем временем специалисты по теории сложности начинают глубже изучать, насколько сложна колмогоровская сложность.
Всё это намекает нам на то, что истинную пользу открытия мы узнаем в будущем. «Это семя, которое, вероятно, разовьётся в гораздо более обширную теорию», — считает Ишаи.