Ваш ребёнок — школьник, который разбирается в математике? Тогда скорее участвуйте в олимпиаде по криптографии имени И.Я. Верченко!
Это отличный шанс проверить свои знания по этим точным наукам. Задания будут непростые, но и ставки высоки — победители и призёры смогут поступить в вуз без экзаменов! Все подробности читайте в правилах на сайте.
Отборочный этап проходит онлайн, поэтому можно участвовать из любого города. Скорее регистрируйтесь!
Иван Яковлевич Верченко — советский математик, криптограф, педагог, доктор физико-математических наук.
Когда вы спрашиваете голосовой помощник о погоде, курсе валют и пробках на дороге, он ищет в интернете свежие данные, извлекает их, после чего «оборачивает» в стандартную фразу и сообщает вам. Помогает ему в этом RAG — Retrieval Augmented Generation, что можно перевести как генерация (ответа) с использованием дополнительной информации.
Технически это метод программного дополнения вывода (большой) языковой модели данными из внешних источников. Его можно применить в задачах, где ИИ требуется постоянно оперировать свежими данными. Также этот метод позволяет адаптировать LLM под собственные базы знаний без необходимости дообучать её.
Например, RAG используют для подключения LLM в режиме реального времени к новостным каналам и лентам социальных сетей, дополнения выдачи поисковых систем актуальной информацией.
Несмотря на простую идею, внутреннее устройство RAG довольно сложно. Прежде, чем добавить данные в свой ответ, необходимо найти релевантную информацию в базе знаний. Для этого информация хранится в виде векторных представлений, которые позволяют выполнять семантический поиск.
Для этого приходится перефразировать запросы, разбивать их на фрагменты, ранжировать поисковую выдачу и делать много другой алгоритмической работы. Это и есть Retrieval — отдельное искусство «найти нужное дерево в лесу».
Ярый сторонник движения за свободное ПО лингвист и программист Ларри Уолл часто радует перлами. Один из них родился в 1987 году и остаётся популярным до сих пор. Речь о Perl — Practical Extraction and Report Language, языке для практического извлечения данных и обработки отчётов.
Ключевая идея Perl выражается наиболее известной фразой Ларри Уолла: «Простые вещи должны оставаться простыми, а сложные — становиться возможными».
Изначально язык предназначался для автоматизированной обработки текстовых файлов, но со временем его функциональность расширилась. Сегодня Perl используют в научных исследованиях, создании сайтов, приложений и пользовательских интерфейсов.
Ещё одна фраза Ларри иллюстрирует универсальность языка: «Есть несколько способов сделать что-либо». Связано это с тем, что Perl поддерживает как объектно-ориентированный подход, так и процедурную, и функциональную парадигмы.
Perl можно назвать Си-подобным, с заимствованиями из LISP, Бейсика, текстового редактора sed, языка сценариев AWK, командного интерпретатора UNIX и бог знает чего ещё. Это весьма необычный сплав структуры и синтаксиса совершенно разных программных продуктов.
При должном знании английского изучать Perl сравнительно легко из-за обилия бесплатной литературы, свободно распространяемых модулей и развитого сообщества, насчитывающего десятки тысяч программистов. На основе Perl создан язык Raku (ранее — Perl 6), который развивается как самостоятельный диалект.
Наши коллеги-криптографы приняли участие в конференции CTCrypt2024. Вот, о чём были их доклады.
Степан Давыдов, старший специалист-исследователь лаборатории криптографии, рассказал об инвариантных подпространствах матриц-циркулянтов.
Один из перспективных методов криптоанализа — изучение инвариантных подпространств матрицы линейного преобразования.
В работе изучаются инвариантные подпространства линейных преобразований, заданных матрицами-циркулянтами. Они используются в шифрсистемах AES, SM4, а также хэш-функции Whirlpool.
Юрий Шкуратов, младший специалист-исследователь лаборатории криптографии, рассказал о самодуальности квазициклических алгеброгеометрических кодов, ассоциированных с эллиптической кривой.
В современной криптографии (особенно постквантовой) применяется теория помехоустойчивого кодирования.
❗️С её помощью были разработаны криптографические системы, основанные на кодах. Они могут быть устойчивы к взлому классическими суперкомпьютерами и квантовыми.
📌Одним из перспективных направлений в разработке надёжных кодовых криптосистем являются модификации криптосистемы Мак-Элиса на квазициклических кодах Гоппы. Предложенный Валерием Гоппой класс алгеброгеометрических кодов позволяет оптимизировать затраты памяти на хранение секретного ключа и ускорить процесс шифрования.
В этой работе изучается конкретный подкласс алгеброгеометрических кодов: для него рассматривается возможность одновременного наличия свойств квазицикличности и самодвойственности.
В анализе видеопотока с помощью ИИ выделяют два подхода. Первый из них называется обработкой разреженного (sparse) видео. Он решает задачу предсказания одного результата по анализу видеофрагмента (массива кадров).
Второй подход решает задачу предсказания одного результата на кадр. Такую покадровую обработку называют анализом плотного (dense) видео. Модели ML для работы с плотным видео востребованы там, где требуется уловить кратковременные события и проанализировать быстрые изменения сцен.
❗️Существующие модели глубокого анализа видео (например, 3D CNNs) достигли впечатляющих результатов при обработке разреженного видео. Однако их адаптация к задачам плотного видео сопряжена с рядом проблем.
В частности, эти модели менее эффективны при работе с избыточными кадрами, с трудом улавливают временные корреляции на больших интервалах и неоправданно дороги в развёртывании.
Чтобы решить эти проблемы, коллектив исследователей из Белфаста (Ирландия) разработал TDViT — модель трансформера для обработки плотного видео с блоками временнóго расширения.
Эксперименты с наборами данных ImageNet VID и YouTube VIS показали, что TDViT эффективно извлекает пространственно-временны́е представления и ослабляет негативный эффект временнóй избыточности. Также иерархическая структура блоков позволяет моделировать динамику на больших временных интервалах.
Эль-76 — язык программирования высокого уровня, с которым мы хотим вас сегодня познакомить.
«Эль-76» был написан коллективом ИТМиВТ под руководством Владимира Пентковского, позже работавшего в Intel над серией процессоров Pentium.
Вместе со специалистами в области высокопроизводительных вычислений Всеволодом Сергеевичем Бурцевым и Борисом Бабаяном он принимал участие в создании серии супер-ЭВМ «Эльбрус» и уникального языка для неё.
Изначально этот язык называли «автокодом», поскольку для «Эльбрусов» он был нативным, а все остальные программы транслировались в него. Но по своей структуре «Эль-76» — типичный язык высокого уровня, созданный в соответствии с парадигмой структурного программирования. Он поддерживал использование условных переходов, создание циклов, обработку исключений и встроенные типы данных.
Последнее было крайне важно. Явное определение типа переменных упростило поиск участков кода, где их обработка выполнялась некорректно. Проще говоря, компьютер больше не пытался внезапно разделить число на символ или логический ноль.
Написание программ на «Эль-76» облегчалось использованием русскоязычных команд: «начало», «если», «иначе», «конец» и другими. На «Эль-76» были написаны программы для самых ответственных задач, включая обеспечения работы Центра управления полётами.
Схема электронной подписи «Шиповник» на основе кодов, исправляющих ошибки — один из кандидатов на новый российский стандарт постквантовых механизмов.
Наши специалисты-исследователи лаборатории криптографии Виктория Высоцкая и Диана Дас провели углублённый анализ стойкости этой схемы. Об этом они рассказали на конференции РусКрипто'24.
В работе приведена классификация атак на «Шиповник» с использованием алгоритмов, решающих задачи поиска прообраза и второго прообраза внутренней троичной хэш-функции, а также поиска коллизии хэш-функции Стрибог. Анализ коллег показал, что текущий набор параметров позволяет обеспечить стойкость схемы к рассмотренному множеству атак.
Атбаш появился приблизительно в середине первого тысячелетия до н. э. С помощью атбаша были зашифрованы, например, некоторые слова в Библии, а также в религиозных текстах Кумранских рукописей — общее название манускриптов, впервые обнаруженных в 1947 году в пещерах Кумрана и других местах Иудейской пустыни.
Слово «атбаш» составлено из первой, последней, второй и предпоследней букв еврейского алфавита — «алеф», «тав», «бет» и «шин» — и объясняет принцип шифрования. Чтобы зашифровать сообщение, нужно заменить первую букву открытого текста на последнюю букву в алфавите, вторую букву — на предпоследнюю и так далее. Чтобы расшифровать сообщение, нужно знать язык, на котором оно написано, и определить принцип шифрования. Так, например, слово «зима» превращается в «чцтя». Атбаш относится к моноалфавитным шифрам простой замены.
Ну что за тарабарщина? Это мы про русскую тайнопись прошлых веков.
Первые тайнописные тексты появились на Руси примерно в ХII веке. Большинство форм и способов тайнописи были взяты из Византии. В том числе и литорея — шифр простой замены, который стал основной системой шифрования на Руси в XIII—XVI веках.
Существовало две разновидности литореи: «простая» и «мудрая». В простой заменяли каждую из десяти согласных, идущих по порядку азбуки. Их прописывали в один ряд, а затем заменяли на буквы из второго ряда: он состоял из десяти других согласных, написанных в обратном порядке. Гласные и глухие оставались на своих местах, а сложные буквы исключались и заменялись созвучными. В мудрой литорее заменяли каждую букву, в том числе и гласную.
В XIX веке простую литорею стали называть тарабарщиной, тарабарским языком или тарабарской азбукой. Я фащыс, гко жокес панилакь! — на тарабарском это значит «Я забыл, что хотел написать!».
Скитала— первое известное устройство для шифрования. Оно появилось предположительно в VIII-VII веках до н. э. в Древней Греции.
Скитала (или сцитала, от греческого σκυτάλη — жезл) — это античное устройство шифрования, состоящее из стержня определённой толщины и узкой полоски кожи, намотанной на него по спирали. Именно толщина стержня определяла количество букв на одном витке и служила ключом.
У историков есть два мнения, зачем использовали скиталу:
Одни считают, что с ее помощью древнегреческие полководцы зашифровывали и передавали секретные указания во время военных действий.
Другие, что это устройство использовали для удобства доставки или хранения обычных посланий.
Как зашифровать сообщение с помощью скиталы?
Нужно подготовить две одинаковые палки по длине и диаметру: одна понадобится отправителю, а вторая — получателю.
Вырезать длинную и узкую полоску кожи.
Плотно, по спирали, обмотать палку лентой кожи, не оставляя промежутков.
Написать сообщение вдоль оси скиталы.
Снять ленту со скиталы и отправить ее адресату.
Получатель, чтобы прочитать сообщение, должен намотать ленту на вторую палку.
Если она будет отличаться по длине или диаметру, послание прочитать не выйдет.
Впервые о скитале говорит писатель и философ Плутарх в книге «Сравнительные жизнеописания». Это первое известное устройство для шифрования, описанное античными авторами.
«Пляшущие человечки» — это один из рассказов про Шерлока Холмса. В нём детектив раскрывает загадочное убийство с помощью шифра, который выглядит как...пляшущие человечки!
Детектив использовал частотный криптоанализ. Это способ расшифрования сообщения на основе знания частоты появления символов в языке, на котором написан незашифрованный текст.
Например, в русском языке чаще всего встречаются буквы "о" (11%) и "е" (8,5%), а реже всего — буква "ф" (0,27%) и твёрдый знак (0,04%). Поэтому в переводе рассказа на русский в зашифрованных посланиях самые часто используемые фигуры человечков соответствуют буквам "о" и "е".
Чем больше объём накопленных шифрограмм, тем ближе в них частотное распределение к среднему. Зная это и перехватив несколько зашифрованных сообщений, можно подобрать отдельные слова (как в кроссворде или "Поле чудес"), а затем с их помощью выяснить, каким фигурам соответствуют другие буквы.
Постепенно так восстановится вся таблица шифрования, что позволит не только читать все новые шифрограммы (пассивная атака), но и создавать их самому (активная атака), вмешиваясь в зашифрованную переписку.
Частотный криптоанализ применим не ко всем шифрам. Так как в произведении использован шифр простой замены (каждая буква открытого текста заменяется на одну и ту же букву по таблице замены), то Шерлоку удалось дешифровать сообщение. Шифры простой замены уязвимы к частотному криптоанализу.
Решётка Кардано — это один из методов стеганографии*, в котором использовался трафарет с вырезанными ячейками для букв или целых слов. Такое шифрование помогало спрятать важные послания в повседневных письмах. Оно использовалось с XVI века.
*Стеганография — это технология сокрытия самого факта передачи секретного сообщения. Оно как бы растворяется в другом, несекретном сообщении, а не шифруется.
Как выглядела решётка Кардано?
Решётку Кардано вырезали из плотной бумаги, картона или даже металлической пластины. Трафарет мог быть квадратным, прямоугольным или произвольной формы — главное, чтобы в нём в случайном порядке были сделаны прорези.
Как работала решётка Кардано?
Шифровальщик брал решётку, клал её на бумагу и вписывал в прорези буквы или даже целые слова секретного сообщения, которое необходимо передать. Оно раскидывалось фрагментарно по всему пространству листа.
Затем решётку убирали, и пустые места на бумаге заполнялись посторонним текстом так, чтобы секретное сообщение стало его частью. Важно, чтобы общее послание было естественным, иначе это вызвало бы подозрение!
Как расшифровать сообщение?
Важно, чтобы у получателя была такая же решётка, вырезанная из первичного трафарета. Иначе расшифровать сообщение практически невозможно. Принцип построения и работы решётки впервые описал итальянский математик, инженер и философ Джероламо Кардано в трактате «О тонких материях» в 1550 году.
Рассказываем, что такое азбука перестукивания и как с её помощью общались арестанты.
Этот оригинальный способ связи имеет греческие корни. В Древней Греции существовали таблицы для кодирования сообщений сигнальными кострами или взмахами факела. Первым одну из них описал историк Полибий, поэтому все подобные таблицы часто называют «квадрат Полибия», хотя они могут иметь и прямоугольную форму из-за разного числа строк и столбцов.
Свои модификации «тюремной азбуки» были у декабристов, петрашевцев и других народовольцев. Один из дошедших до нас вариантов был описан русским литератором и революционером Николаем Александровичем Морозовым.
Его вариант азбуки перестукивания состоит из 28 букв. Для сокращения он убрал семь наименее употребительных букв того времени — ё, й, i, ъ, ь, ѣ (ять), ѳ (фита), а остальные расположил по порядку в таблице из шести строк и пяти столбцов.
Заключённые выстукивали каждую букву в два приёма: сначала номер строки, затем — номер столбца. Они стучали каблуком об пол или ложкой, кружкой, пуговицей по стене или ножке кровати.
Особо популярна тюремная азбука была в тюрьме Трубецкого бастиона в Санкт-Петербурге. Там во времена имперской России сидели политические заключённые. Акустика этой тюрьмы позволяла слышать звуки, доносившиеся даже из камер другого этажа. Так арестанты общались друг с другом, хотя перестукивание и считалось серьёзным нарушением.
Мы уже рассказывали о шифре Цезаря — моноалфавитном шифре, который использовали ещё до нашей эры. Теперь поговорим о первом полиалфавитном шифре Альберти. Его создание стало важным шагом в развитии криптографии.
Полиалфавитный шифр — совокупность моноалфавитных шифров, которые по очереди применяются к буквам шифруемого текста.
В середине XV века философ Леон Альберти создал на основе шифра Цезаря собственное шифровальное устройство. Оно также состояло из двух соосных дисков, вложенных друг в друга.
Внешний диск содержал 20 букв латинского алфавита по порядку (H, J, K, U W и Y Альберти пожертвовал, т.к. их можно было заменить похожими по написанию или звучанию) и 4 цифры.
Внутренний диск содержал 24 буквы в случайном порядке, и это была очень важная особенность. Когда человек расшифровывал текст, он должен был делать сдвиг в пределах другого алфавита (упорядоченного набора букв). А он был известен только владельцам двух одинаковых дисков.
Леон Альберти разработал этот шифр по заказу папы Римского Павла II, и подробно описал его в 1466 году в «Трактате о шифрах» — одной из первых научных работ по криптографии. По сути Альберти изобрёл полиалфавитную систему шифрования, но её авторство чаще приписывают другому учёному — французу Блеза де Вижнеру. Почему?
Работа Альберти «Тракт о шифрах» считалась утерянной до конца XIX века, и о его диске никто не знал. А шифр Вижнера обрёл огромную популярность, хоть и был создан на 120 лет позже. О нём мы расскажем в следующий раз.
Рассказываем об одном из самых известных шифров, использовавшихся ещё до нашей эры. Гай Юлий Цезарь применял его для передачи военных приказов и дипломатических сообщений, поэтому в историю он вошёл как «шифр Цезаря».
Шифр Цезаря в Музее криптографии
Технически это сдвиговый шифр: при шифровании сообщения каждая буква исходного слова заменяется другой буквой, находящейся от неё в алфавите дальше на N символов. В классическом варианте N равнялось трём, поэтому латинская А заменялась на D, B — на E и так далее.
Например, подпись «Gaius Iulius Caesar» в зашифрованном виде выглядела как «Jdlxv Lxolxv Fdhvdu». Для кириллического алфавита выполняется аналогичный сдвиг на три буквы вправо: А → Г, Б → Д … Я → В (алфавит замыкается). Таким образом, «Гай Юлий Цезарь» превращается в «Ёгм Болм Щзкгуя», а «Криптонит» в «Нултхсрлх». Конечно, N может быть любым целым числом, и даже отрицательным (тогда сдвиг выполняется влево).
Для удобства шифрования и расшифровки таких сообщений был изготовлен диск, а точнее — два диска разного диаметра, закреплённых на одной оси. Каждый из них разделён на 26 секторов по числу латинских букв. На обоих дисках буквы записаны как в алфавите и по одной в каждом секторе. Зная ключ, достаточно было сдвинуть на это значение диски относительно друг друга, чтобы прочитать зашифрованное сообщение, или написать своё. Например, если ключ равен трём, то диски вращаются до тех пор, пока напротив A не появится литера D.
