В чем состоит задача криптографа

В чем состоит задача криптографа

Криптография — наука о методах обеспечения конфиденциальности и аутентичности информации. Математическая криптография возникла как наука о шифровании информации, т.е. как наука о криптосистемах. В классической модели системы секретной связи имеют место два полностью доверяющих друг другу участника, которым необходимо передавать между собой информацию, не предназначенную для третьих лиц. Такая информация называется конфиденциальной или секретной. Задача обеспечения конфиденциальности, т.е. защита секретной информации от противника — первая задача криптографии.

Часто возникает ситуация, когда информация не является конфиденциальной, но важен факт поступления сообщений в неискаженном виде, т.е. наличие гарантии, что сообщение не было подделано. Такая гарантия называется обеспечением целостности информации и составляет вторую задачу криптографии.

При передаче электронных документов (в том числе и через Интернет) возможна как их подмена или редактура, так и — в случае секретного текста — доступ посторонних лиц к передаваемой информации. Таким образом, электронные документы также нуждаются в криптографической защите.

• Обеспечение уверенности получателя в том, что документ подлинный и корректный, т.е. при передаче не был подменен или отредактирован;
• Обеспечение невозможности доступа посторонних лиц к содержанию документа.

Когда речь идет об электронных документах, первая задача решается применением электронной подписи, вторая — зашифрованием документа.

Электронная подпись (ЭП) — цифровой аналог ручной подписи, обеспечивающий возможность проверки подлинности и корректности документа. Существует техническая возможность проверки электронной подписи: если документ подменен или искажен при передаче, подпись при проверке будет признана некорректной.

Зашифрование документа — видоизменение текста документа таким образом, что только тот или те, для кого текст документа предназначен, в состоянии восстановить исходный текст.

Криптографические программные продукты

Для защиты информации используются специальные пользовательские программные продукты. Они разделяются на две основные группы.

Первая группа, очень широко распространенная — это криптопровайдеры (или CSP, Cryptographic Service Providers). CSP не являются самостоятельными приложениями, они предоставляют криптографические функции другим приложениям — например, таким, как почтовые программы. Пользователь фактически не имеет дела непосредственно с CSP, работая с привычным ему пользовательским интерфейсом. CSP обладают универсальностью — один и тот же CSP может использоваться для работы со множеством различных программ. Примером такого продукта производства ООО «Криптоком» является криптопровайдер МагПро CSP.

Вторая группа — это библиотеки криптографических функций. Такие библиотеки содержат готовые функции, решающие криптографические задачи, и могут использоваться для создания новых приложений. Примером такого продукта производства ООО «Криптоком» является программный продукт «МагПро КриптоПакет».

Криптографические алгоритмы

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

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

Совокупность операций, которые производятся над текстом при криптографическом преобразовании, называется криптографическим алгоритмом.

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

Алгоритмы, т.е. сами последовательности действий, не являются секретными.

Стандарты на криптографические алгоритмы

На криптографические алгоритмы существуют стандарты. Надежность алгоритмов, соответствующих стандартам, тщательно анализируется специалистами. При работе с официальной документацией разрешается пользоваться только алгоритмами, соответствующими стандартам.

В разных странах существуют различные стандарты на алгоритмы. В программном обеспечении широко используются алгоритмы, соответствующие американским стандартам, чаще всего это алгоритм RSA.

В России существуют собственные государственные стандарты на алгоритмы шифрования и выработки/проверки электронной подписи: ГОСТ 28147-89, ГОСТ Р 34.10-2012, ГОСТ Р 34.10-2012.

Для выработки и проверки электронной подписи, а также зашифрования и расшифрования документов используются определенные последовательности действий, называемые криптографическими алгоритмами.

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

На криптографические алгоритмы существуют стандарты, т.е. официально оформленные совокупности требований, которым эти алгоритмы должны отвечать. Эти стандарты различны в разных странах и изменяются со временем. Популярные американские алгоритмы — RSA, DSA и т.д. — которые часто используются в распространенных программных продуктах, отвечают американским стандартам.

В России также приняты государственные стандарты на криптографические алгоритмы. Российские производители, в том числе ООО «Криптоком», используют в своих программных продуктах алгоритмы, соответствующие российским стандартам.

Криптографические ключи

В качестве секретной информации используются криптографические ключи.

Криптографический ключ представляет собой последовательность символов, выработанную по определенным правилам. Эта последовательность используется при криптографических преобразованиях текстов. Для каждого криптографического алгоритма существуют свои требования, в соответствии с которыми создаются ключи. Каждый ключ создается для определенного алгоритма.

Для того чтобы обеспечить невоспроизводимость электронной подписи и невозможность прочтения зашифрованных текстов посторонними людьми, в криптографии применяются криптографические ключи.

Современный криптографический ключ — это последовательность чисел определенной длины, созданная по определенным правилам на основе последовательности случайных чисел. Для каждого ключа последовательность случайных чисел создается заново, ни одна последовательность не используется более одного раза. Для генерации последовательностей случайных чисел используются специальные программные объекты или устройства, называемые датчиками случайных чисел.

Каждый алгоритм предъявляет собственные требования к ключам, поэтому любой криптографический ключ создается для определенного алгоритма и используется только с этим алгоритмом.

Если выработка электронной подписи и ее проверка, или зашифрование и расшифрование текста выполняются с помощью одного и того же ключа, такой подход называется симметричной криптографией (соответственно симметричные алгоритмы и симметричные ключи). Операции симметричной криптографии выполняются быстро и сравнительно просты. Но они требуют знания ключа по меньшей мере двумя людьми, что значительно повышает риск их компрометации (т.е. доступа к ним посторонних лиц).

Поэтому сейчас в основном используется асимметричная криптография. В асимметричной криптографии выработка электронной подписи или зашифрование выполняются на одном ключе, а проверка подписи или расшифрование — на другом, парном ключе.

В асимметричной криптографии применяются так называемые ключевые пары (key pairs). Каждая такая пара состоит из двух связанных между собой ключей. Один из этих ключей — закрытый (private key). Он известен только владельцу ключа и ни при каких условиях не должен быть доступен никому другому. Другой ключ — открытый (public key), он может быть доступен любому желающему.

Для выработки ЭП необходим закрытый ключ автора сообщения, для проверки — открытый. Таким образом, создать ЭП может только владелец закрытого ключа, а проверить — любой пользователь, получивший соответствующий открытый ключ.

Для зашифрования текста применяется открытый ключ адресата, для расшифрования — закрытый. Таким образом, зашифровать сообщение может любой человек, а расшифровать — только владелец соответствующего закрытого ключа, т.е. адресат.

Ключевая пара, используемая для работы с ЭП (выработки и проверки ЭП), называется ключами подписи (signature keys). Ключевая пара, используемая для зашифрования и расшифрования сообщений, называется ключами обмена (exchange keys).

Проблема асимметричной криптографии состоит в том, что зашифрование по асимметричным алгоритмам происходит намного медленнее, чем по симметричным. Кроме того, если зашифрованный текст предназначен для нескольких адресатов, в отправляемое сообщение приходится включать копию текста для каждого адресата, что резко увеличивает как объем сообщения, так и время, необходимое для его зашифрования.

Эта проблема решается с помощью так называемой гибридной криптографии.

В процессе шифрования прежде всего создается одноразовый (так называемый сеансовый) ключ шифрования (session encryption key). Это симметричный ключ, т.е. один и тот же ключ используется и для зашифрования, и для расшифрования. Одноразовым или сеансовым он называется потому, что используется для зашифрования/расшифрования только одного сообщения.

На сеансовом ключе шифрования зашифровывается сообщение. Поскольку сообщение зашифровывается по симметричному алгоритму, процесс зашифровывания сообщения происходит достаточно быстро.

Затем сам ключ шифрования зашифровывается по асимметричному алгоритму на открытом ключе обмена получателя. Поскольку ключ шифрования представляет собой сравнительно небольшой объем данных, зашифрование такого ключа не занимает много времени.

Зашифрованный ключ шифрования включается в сообщение.

В результате сообщение получается незначительно больше по объему (за счет добавленной зашифрованной копии ключа шифрования), но процесс зашифрования происходит гораздо быстрее, чем если бы само сообщение зашифровывалось по асимметричному алгоритму.

Если получателей несколько, то сообщение зашифровывается один раз на сеансовом ключе шифрования, а ключ (сравнительно небольшой объем данных) зашифровывается отдельно на открытом ключе обмена каждого получателя. Таким образом, зашифрованное сообщение вместо нескольких копий сообщения, зашифрованных для каждого получателя, содержит одну зашифрованную копию сообщения и несколько копий одноразового сеансового ключа шифрования, зашифрованных для каждого получателя. Объем зашифрованного сообщения и время, необходимое для его зашифрования, оказываются существенно меньшими, чем если бы сообщение шифровалось по асимметричному алгоритму для каждого получателя.

Когда адресат получает сообщение, среди зашифрованных сеансовых ключей, включенных в сообщение, ищется сеансовый ключ, зашифрованный на открытом ключе обмена получателя. Если такой ключ находится, он расшифровывается с помощью закрытого ключа обмена получателя, а потом с помощью этого ключа расшифровывается само сообщение.

Таким образом, основное требование к процессу зашифрования по асимметричному алгоритму — чтобы к закрытому ключу обмена никто не имел доступа, кроме владельца этого ключа — соблюдается. Для того, чтобы получить доступ к ключу шифрования, необходим доступ к закрытому ключу обмена; но после того, как произведено расшифрование ключа шифрования с помощью закрытого ключа обмена, этот ключ шифрования больше никогда не используется, так что говорить о его компрометации не имеет смысла.

Сертификаты

Сертификаты — это принятая сейчас форма хранения и передачи открытых ключей. Сертификат — это набор данных специального формата, содержащий сам открытый ключ и всю информацию о нем и о его владельце. Все открытые ключи хранятся и передаются в виде сертификатов.

Сертификаты выпускаются специальными уполномоченными центрами, которые могут носить различные названия: удостоверяющий центр, центр сертификации, пункт регистрации абонентов и т.д. В любом случае такой центр выполняет административные функции. Центр и пользователи (абоненты), которые пользуются услугами центра, составляют криптосеть.

Для того чтобы центр выпустил сертификат на открытый ключ, абоненту необходимо прислать заявку (запрос) на такой сертификат. Заявка содержит открытый ключ и всю информацию о нем и о владельце. Центр проверяет подлинность и корректность этой информации (как именно — зависит от регламента центра) и выпускает сертификат, заверяя его своей электронной подписью.

Цепочки доверия

Часто возникает необходимость проверять документ с помощью другого документа, который так же требует проверки. Например, подпись под документом проверяется с помощью сертификата на открытый ключ, парный тому секретному, на котором подпись выработана. Но сам сертификат — это тоже документ, корректность и подлинность которого требует проверки. Подпись под сертификатом проверяется на сертификате на открытый ключ подписи того центра, который выпустил сертификат. Сертификат центра, в свою очередь, тоже может быть подписан электронной подписью и требовать проверки.

Такие цепочки документов, каждый из которых проверяется на следующем, называются цепочками доверия.

Очевидно, что в конце концов цепочка заканчивается — в ней обязательно существует документ, который невозможно проверить на другом документе (например, самый первый сертификат центра). Такие документы могут называться самозаверенными, корневыми, доверенными и т.д. Существуют разные способы проверки корректности и подлинности таких документов, зависящие от используемого программного обеспечения и принятого регламента: контрольные записи, цифровые отпечатки и т.д. Общим во всех этих способах проверки является то, что они требуют участия каких-то бумажных документов (распечаток) и не могут быть проверены автоматически: необходимо, чтобы человек сравнил информацию из проверяемого электронного документа с распечатанной и убедился в совпадении.

Документ может считаться корректным только в том случае, если корректны все документы, входящие в цепочку доверия от данного документа до документа, которым заканчивается цепочка (корневого).

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

Датчики случайных чисел и создание ключей

Ключи создаются по специальным алгоритмам на основе последовательностей случайных чисел.

Для того чтобы криптографическая защита на ключе была надежной, последовательность случайных чисел, на которой создана ключевая пара, должна быть уникальной для каждой ключевой пары. Кроме того, она должна быть действительно случайной, т.е. не допускать повторов даже через очень большие промежутки.

Такие уникальные последовательности случайных чисел генерируются во время создания ключей с помощью специальных устройств или программ, называемых датчиками случайных чисел.

Очень удобны и быстры так называемые аппаратные датчики случайных чисел, представляющие собой физические устройства — платы, подключенные к компьютеру. Такие датчики создают последовательности случайных чисел на основе физических процессов. Генерация последовательностей случайных чисел с помощью аппаратного датчика происходит очень быстро и без участия пользователя.

Но такие датчики устанавливаются не на каждом компьютере. Поэтому часто для создания ключей используется клавиатурный датчик случайных чисел~— программа, использующая для создания последовательности случайных чисел физический процесс нажатия клавиш пользователем. Для инициализации такого датчика пользователю необходимо нажать определенное количество указываемых ему клавиш (если все клавиши нажаты безошибочно, то нужно 40 нажатий; если пользователь допускает ошибочные нажатия, количество необходимых нажатий увеличивается). Создание ключей с помощью клавиатурного датчика — более медленный процесс, чем создание ключей с помощью аппаратного датчика, но его можно осуществить на любом компьютере.

Хранение закрытых ключей

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

• Устройство должно включать в себя область памяти, достаточной, чтобы записать туда закрытые ключи (иногда эту область памяти называют «хранилищем ключей»);
• Устройство должно легко подключаться к компьютеру, чтобы ключи могли быть считаны;
• Устройство должно легко отключаться от компьютера, чтобы злоумышленники не могли считать с него ключи.

Таким условиям удовлетворяет USB-токен «Вьюга», разработанный в ООО «Криптоком». Устройство «Вьюга» включает в себя генератор случайных чисел (т.е. может использоваться как датчик случайных чисел при генерации ключей) и область памяти объема, достаточного для хранения ключей. Устройство подключается к компьютеру через USB-порт. Возможно подключение устройства к компьютеру непосредственно в процессе работы.

Компрометация ключей

Компрометация ключей — понятие, которое включает в себя факт доступа посторонних лиц к секретным ключам, а также возможность такого доступа или подозрение на него. Скомпрометированный секретный ключ — главная опасность для любой системы защиты информации, поэтому принимаются специальные меры для защиты секретных ключей: их никогда не записывают на жесткий диск компьютера, их держат на отдельных носителях, их зашифровывают, их защищают на пароле и т.д. Тем не менее, случаи компрометации возможны.

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

Основные понятия криптографии

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

Любой протокол имеет следующие свойства:

• при выполнении протокола важен порядок действий; каждое действие должно выполняться в свою очередь и только по окончании предыдущего;
• протокол должен быть непротиворечивым;
• протокол должен быть полным, то есть для каждой возможной ситуации должно быть предусмотрено соответствующее действие.

Свойства протокола напоминают известные нам из курса информатики свойства алгоритма. На самом деле протокол – это и есть алгоритм действия нескольких сторон в определенной ситуации. Участники протокола должны знать протокол и выполнять полностью все его этапы. Участниками криптографического протокола обычно являются абоненты некоторой системы связи. Участники протокола могут не доверять друг другу, поэтому криптографические протоколы должны защищать их участников не только от внешнего противника, но и от нечестных действий партнеров.

Криптографические протоколы – сравнительно молодая отрасль криптографической науки. Первые протоколы появились во второй половине ХХ века. С тех пор эта область криптографии бурно развивалась, и на настоящий момент имеется уже несколько десятков различных типов криптографических протоколов. Все эти типы можно условно разделить на две группы: прикладные протоколы и примитивные. Прикладной протокол решает конкретную задачу, которая возникает (или может возникнуть) на практике. Примитивные же протоколы используются как своеобразные «строительные блоки» при разработке прикладных протоколов. Мы в данном учебном пособии будем рассматривать только примитивные криптографические протоколы, которые при некоторой адаптации к реальным системам связи могут использоваться на практике.

Рассмотрим назначение некоторых видов протоколов.

1. Протоколы конфиденциальной передачи сообщений. Задача конфиденциальной передачи сообщений состоит в следующем. Имеются два участника протокола, которые являются абонентами сети связи. Участники соединены некоторой линией связи, по которой можно пересылать сообщения в обе стороны. Линию связи может контролировать противник. У одного из абонентов имеется конфиденциальное сообщение m, и задача состоит в том, чтобы это сообщение конфиденциальным же образом передать второму абоненту. Протоколы этого типа, наверно, появились раньше других криптографических протоколов, так как задача конфиденциальной передачи сообщений – исторически первая задача, которая решалась криптографией.
2. Протоколы аутентификации и идентификации. Они предназначены для предотвращения доступа к некоторой информации лиц, не являющихся ее пользователями, а также предотвращения доступа пользователей к тем ресурсам, на которые у них нет полномочий. Типичная сфера применения – организация доступа пользователей к ресурсам некоторой большой информационной системы.
3. Протоколы распределения ключей необходимы для обеспечения секретными ключами участников обмена зашифрованными сообщениями.
4. Протоколы электронной цифровой подписи позволяют ставить под электронными документами подпись, аналогичную обыкновенной подписи на бумажных документах. В результате выполнения протокола электронной цифровой подписи к передаваемой информации добавляется уникальное числовое дополнение, позволяющее проверить ее авторство.
5. Протоколы обеспечения неотслеживаемости («Электронные деньги»). Под электронными деньгами в криптографии понимают электронные платежные средства, обеспечивающие неотслеживаемость, то есть невозможность проследить источник пересылки информации.

Рассмотрим простейший протокол для обмена конфиденциальными сообщениями между двумя сторонами, которые будем называть абонент №1 и абонент №2. Пусть абонент №1 желает передать зашифрованное сообщение абоненту №2. В этом случае их последовательность действий должна быть следующей.

1. Абоненты выбирают систему шифрования (например, шифр Цезаря со сдвигом на n позиций).
2. Абоненты договариваются о ключе шифрования.
3. Абонент №1 шифрует исходное сообщение с помощью ключа выбранным методом и получает зашифрованное сообщение.
4. Зашифрованное сообщение пересылается абоненту №2.
5. Абонент №2 расшифровывает зашифрованное сообщение с помощью ключа и получает открытое сообщение .

Этот протокол достаточно прост, однако он может действительно использоваться на практике. Криптографические протоколы могут быть простыми и сложными в зависимости от назначения. Со многими из них мы познакомимся в различных главах этого курса.

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

Ключевые термины

Ciphertext – зашифрованное сообщение (закрытый текст, криптограмма).

Deciphering – расшифрование .

Enciphering – преобразование открытого текста в криптограмму (зашифрование).

Рlaintext – исходное сообщение или открытый текст .

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

Алфавит — конечное множество используемых для кодирования информации символов.

Ключ – информация , необходимая для шифрования и расшифрования сообщений.

Криптоанализ – наука о преодолении криптографической защиты информации.

Криптографическая система защиты информации – система защиты информации, в которой используются криптографические методы для шифрования данных.

Криптографический протокол – алгоритм взаимодействия двух или более абонентов с использованием криптографических средств, в результате которой абоненты достигают своей цели, а их противники — не достигают.

Криптография изучает построение и использование систем шифрования, в том числе их стойкость, слабости и степень уязвимости относительно различных методов вскрытия.

Криптостойкость – характеристика шифра, определяющая его стойкость к дешифрованию без знания ключа (т.е. способность противостоять криптоанализу).

Пассивная криптографическая атака – атака , при которой противник не имеет возможности изменять передаваемые сообщения. При пассивной атаке возможно лишь прослушивание передаваемых сообщений, их дешифрование и анализ трафика .

Принцип Керкхоффса – правило разработки криптографических систем, согласно которому в засекреченном виде держится ключ шифрования , а остальные параметры системы шифрования могут быть открыты без снижения стойкости алгоритма . Другими словами, при оценке надёжности шифрования необходимо предполагать, что противник знает об используемой системе шифрования всё, кроме применяемых ключей. Впервые данный принцип сформулировал в XIX веке голландский криптограф Огюст Керкхоффс.

Символ — это любой знак, в том числе буква, цифра или знак препинания.

Система шифрования, или шифрсистема, – это любая система, которую можно использовать для обратимого изменения текста сообщения с целью сделать его непонятным для всех, кроме тех, кому оно предназначено.

Шифр – совокупность заранее оговоренных способов преобразования исходного секретного сообщения с целью его защиты.

Шифрование с закрытым ключом (симметричное шифрование) – методы обратимого преобразования данных, в которых используется один и тот же ключ , который обе стороны информационного обмена должны хранить в секрете от противника. Все известные из истории шифры, например, шифр Цезаря – это шифры с закрытым ключом.

Шифрование с открытым ключом (асимметричное шифрование) – методы шифрования, в которых для шифрования и расшифрования данных используются два разных ключа. При этом один из ключей (открытый ключ ) может передаваться по открытому (незащищенному) каналу связи. Шифрование с открытым ключом используется на практике лишь со второй половины ХХ века.

Электронная (цифровая) подпись – присоединяемый к сообщению блок данных , полученный с использованием криптографического преобразования. Электронная подпись позволяет при получении текста другим пользователем проверить авторство и подлинность сообщения.

Краткие итоги

Криптография в переводе с греческого означает «тайнопись». В настоящее время криптография занимается поиском и исследованием математических методов преобразования информации. Параллельно развивается и совершенствуется криптоанализ – наука о преодолении криптографической защиты информации.

Криптография решает следующие задачи: шифрование данных с целью защиты от несанкционированного доступа; проверка подлинности сообщений; проверка целостности передаваемых данных; обеспечение невозможности отказа.

Для современных криптографических систем защиты информации сформулированы следующие требования:

• зашифрованное сообщение должно поддаваться чтению только при наличии ключа;
• знание алгоритма шифрования не должно влиять на надежность защиты;
• любой ключ из множества возможных должен обеспечивать надежную защиту информации;
• алгоритм шифрования должен допускать как программную, так и аппаратную реализацию.

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

Информация в процессе хранения, передачи и преобразования подвергается воздействию атак. Основными нарушениями информационной безопасности являются раскрытие информационных ценностей ( потеря конфиденциальности ), модификация без разрешения автора (потеря целостности) или неавторизованная потеря доступа к этим ценностям (потеря доступности).

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

Голландский криптограф Огюст Керкхоффс сформулировал принцип, называемый в настоящее время принципом Керкхоффса – правило разработки криптографических систем, согласно которому в засекреченном виде держится ключ шифрования , а остальные параметры системы шифрования могут быть открыты без снижения стойкости алгоритма . Другими словами, при оценке надёжности шифрования необходимо предполагать, что противник знает об используемой системе шифрования всё, кроме применяемых ключей. Принцип Керкхоффса направлен на то, чтобы сделать безопасность алгоритмов и протоколов независимой от их секретности; открытость не должна влиять на безопасность . Большинство широко используемых систем шифрования, в соответствии с принципом Керкхоффса, используют известные, не составляющие секрета криптографические алгоритмы.

В современной криптографии большое внимание уделяется разработке криптографических протоколов, то есть процедур или алгоритмов взаимодействия абонентов с использованием криптографических средств. В основе протокола лежит набор правил, регламентирующих использование криптографических преобразований. Некоторые виды протоколов: протоколы конфиденциальной передачи сообщений; протоколы аутентификации и идентификации; протоколы распределения ключей ; протоколы электронной цифровой подписи; протоколы обеспечения неотслеживаемости.

Набор для практики

Вопросы для самопроверки

1. Назовите проблемы, при решении которых могут использоваться криптографические методы.
2. В чем отличие криптографии от стеганографии?
3. Какие задачи решает современная криптография?
4. Сформулируйте требования к криптографическим системам защиты информации.
5. Дайте определения понятиям: алфавит, криптограмма, криптографическая система , криптографический протокол, символ, шифр, электронная (цифровая) подпись .
6. В чем заключается правило шифрования методом Цезаря?
7. Почему невозможно вскрыть криптограмму, содержащую код для кодового замка?
8. Почему проблема использования криптографических методов в информационных системах стала в настоящий момент особо актуальной?
9. Что такое криптографическая атака?
10. Какие типы криптографических атак существуют?
11. Что такое криптографический протокол?
12. Поясните назначение следующих криптографических протоколов:
    • обмена конфиденциальными сообщениями;
    • формирования электронной цифровой подписи;
    • распределения ключей .

Упражнения для самопроверки

1. Определите ключи шифра Цезаря, если известны следующие пары открытый текст – шифротекст (исходный алфавит: АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ ):
   • АПЕЛЬСИН — ТВЧЮОДЫА
   • МАНДАРИН – ТЁУЙЁЦОУ

Задачи по криптографии

Мы открываем на нашем сайте задачник. Время от времени мы будем добавлять в него очередную задачу по криптографии или смежным областям математики. В течение месяца решения задачи будут приниматься по адресу: agievich at bsu by. Имена решивших задачу верно будут (по умолчанию) опубликованы на сайте. Ровно через месяц будет оглашаться верное решение, возможно из числа присланных.

В задачах участвуют:

Алиса. Любит разговаривать по открытым каналам связи. Забывает пароли и вложения к электронным письмам.

Боб. Любит разговаривать с Алисой. Читает «Искусство программирования» и «Искусство войны».

Трент. Ему доверяют Алиса и Боб. Делает то, что должен делать. Делает это хорошо. Не делает ничего лишнего. Надежен. Проложил к Алисе и Бобу секретные каналы связи.

Виктор. Интересуется всем. В особенности перепиской Алисы и Боба. Владеет искусством перевоплощения, практиками обфускации и таинствами конкатенации. Измеряет мощность своих компьютеров акрами.

Дополнительные персонажи будут появляться по мере развития событий.

Задача № 60. Zerosum

Найти попарно различные 128-битовые слова X₁, . X₁₂₈ такие, что сумма

состоит из одних нулей. Здесь + обозначает поразрядное по модулю 2 сложение двоичных слов (XOR), Belt₀ – зашифрование Belt (СТБ 34.101.31) на нулевом ключе.

Дата публикации : 11.07.2017.

Решение: pdf.

Задача № 59. Размножение вирусов

Компьютер Боба заражен вирусом, который непрерывно размножается. Одну миллисекунду вновь рожденный вирус обживается, а затем каждую следующую миллисекунду производит новую копию самого себя. Все началось с одной единственнной копии. Боб обратился за помощью к Тренту, и тот нашел ошибку в программе вируса. Оказывается, что, как только количество копий станет кратно 2 32 , все они будут мгновенно уничтожены, и компьютер будет спасен. Стоит ли Бобу надеяться на спасение? Если да, то как долго придется ждать?

Дата публикации : 11.05.2017.

Правильно решили: М. Казловский, В. Палуха

Решение: pdf.

Задача № 58. Такт Belt

На i-м такте Belt (СТБ 34.101.31) 128-битовое слово X преобразуется в 128-битовое слово Y . Входы и выходы задаются четырьмя 32-разрядными регистрами a, b, c и d. Преобразование задается набором из семи 32-разрядных тактовых ключей:

Доказать, что для любой пары (X,Y) найдется ровно 2 96 наборов тактовых ключей, переводящих X в Y.

Дата публикации : 11.04.2017.

Решение: pdf.

Задача № 57. Отпечатки пальцев-II

Боб использует в качестве пароля случайную десятичную строку длины n. Пароль вводится на сенсорном устройстве Suxen. Виктор может разглядеть отпечатки пальцев Боба и узнать, сколько в пароле нулей, единиц, двоек и так далее. Виктор может воспользоваться наблюдениями и уменьшить число паролей, которые требуется проверить. Если, например, Виктор знает, что в пароле ровно одна единица, то ему требуется проверить не 10 n , а только n 9 n -1 паролей. Во сколько раз уменьшается среднее число паролей, которые требуется проверить Виктору?

Дата публикации: 11.02.2017.

Правильно решили: В. Палуха.

Решение: pdf.

Задача № 56. 2017

Бобу требуется по заданной точке P эллиптической кривой найти 2017-кратную точку, т.е. сумму 2017 экземпляров P. В распоряжении Боба – операции сложения, вычитания, удвоения и утроения точек. Бобу нужно организовать вычисления, затратив как можно меньше операций. Например, с помощью представления 2017 = 3 7 — 2 * 3 4 — 3 2 + 1 Боб может найти кратную точку за 11 операций: 7 утроений, 1 удвоение, 2 вычитания и 1 сложение. Можно ли еще быстрее?

Дата публикации : 11.01.2017.

Правильно решили : В. Палуха (10 операций).

Решение: pdf.

Задача № 55. Открыть все

Бобу нужно как можно быстрее открыть n замков, используя 2n ключей. Каждый ключ открывает ровно один замок, и каждый замок открывается ровно двумя ключами. Боб решил открывать замки поочередно, перебирая оставшиеся ключи. Как только ключ подошел, Боб откладывает его и переходит к следующему замку. Алиса критикует Боба. Она предлагает переходить к следующему замку только после того, как найден второй ключ от текущего замка. Алиса утверждает, что при применении ее стратегии среднее число попыток (проверок ключа в замке) будет меньше. Кто прав – Алиса или Боб?

Дополнительный вопрос (*) : существуют ли стратегии с еще меньшим средним числом попыток?

Дата публикации : 11.12.2016.

Правильно решили: В. Палуха (спасибо за подробности).

Решение: pdf.

Задача № 54. Омографическая атака

10 символов русского и английского алфавитов имеют одинаковое начертание. Это A, B, E, K, M, H, O, P, T, X. Виктор открыл агенство по регистрации имен в доменной зоне Трента. На самом деле Виктор готовится к омографической атаке. Он ищет одинаково записываемые слова (доменные имена), осмысленные и в русском, и в английских языках. Первое из найденных им слов: MOPE. Виктор собирается предложить Бобу зарегистрировать русское доменное имя и одновременно самому зарегистрировать английский зеркальный аналог. Виктор добивается того, чтобы пользователи сайта Боба вводили пароли на зеркале Виктора. Найдите как можно больше подходящих русско-английских слов, чтобы помочь Тренту составить словарь запрещенных доменных имен и тем самым защититься от атаки Виктора.

Дата публикации : 11.10.2016.

cryptographer99 (НЕ аббревиатуры, НЕ междометия, НЕ союзы, НЕ частицы):

OH OM
BAP BOP MAT MAX MOP MOT ОКА OPT POM POT TOM TOP
АTOM BATT BEEP KAMA MAMA MOPE ТАРА
MOTET TOTEM

Upd1 (23.01.2017). Трент забыл про букву C (спасибо Д. Попову за подсказку). Дополнения в словарь (спасибо cryptographer99 за программу):

AC
COM COP OCA OCT TEC
BOCK COPT COXA PACA
BACCA CAPOC MECCA

Upd2 (23.01.2017). Самое длинное слово:

TOPEPO (тореадор vs a hybrid between the tomato and the sweet pepper )

Задача № 53. Карта кодов

Алиса получила от Трента карту с 40 кодами. Каждое утро Алиса обращается к серверу Трента, и в ответ получает запрос со случайным номером кода. Алиса находит нужный код на карте и возвращает его Тренту. Если Алиса ошибается, то сервер блокируется на 3 суток. Виктор перехватывает все запросы Трента и все ответы Алисы. После n суток наблюдений, накопив n кодов (некоторые из них могут повторяться), Виктор обращается к серверу Трента от лица Алисы. Если номер кода в запросе Трента уже отправлялся, то Виктор предъявляет нужный код и получает доступ к серверу. Если же номер не отправлялся, то Виктор ошибется (код очень длинный) и сможет повторить попытку аутентификации только через 3 суток. Как Виктору выбрать n, чтобы минимизировать среднее время ожидания успеха аутентификации?

Дата публикации : 11.07.2016.

Правильно решили: В. Палуха.

Решение: pdf.

Задача № 52. Код доступа

Замок чемодана запирается 4-значным десятичным кодом. Цифры кода задются 4 роторами. Для подбора кода Виктор поворачивает некоторый из роторов либо по часовой стрелке, либо против часовой, увеличивая либо уменьшая на 1 (по модулю 10) цифру ротора. Каждый набранный на роторах код сравнивается с истинным. В случае совпадения замок отпирается. В случае несовпадения Виктор может поворачивать роторы и дальше. Может ли Виктор гарантированно открыть замок после 9999 поворотов? Если да, то как он должен действовать. Вначале замок закрыт.

Дата публикации : 11.05.2016.

Правильно решили: В. Палуха, hellman.

Решение: pdf.

Задача № 51. А была ли ошибка?

Боб написал программу для шифровальной машины Amgine . Алиса оценила объем программы и стиль программирования Боба. Алиса утверждает, что программа содержит ошибку с вероятностью α. В ответ Боб разработал систему из n тестов. Тест номер i обнаруживает ошибку с вероятностью p_i независимо от других тестов. Все тесты прошли успешно. Какова вероятность того, что в программе все-таки есть ошибка?

Дополнительный вопрос (★): Изменятся ли выводы, если учитывать результат очередного теста сразу после его выполнения?

Дата публикации : 11.04.2016.

Решение: pdf.

Задача № 50. Граф

В функции хэширования Bash план криптографического перемешивания задается специальным ориентированным графом. Это граф на 8 вершинах, из каждой вершины выходит 3 дуги, в каждую вершину заходит 3 дуги, любые 2 вершины можно связать маршрутом длины 2, в любую вершину можно вернуться за 2 шага ровно 2 способами. Докажите, что любой подходящий граф перенумерацией вершин можно преобразовать в следующий:

Дата публикации: 11.03.2016.

Решение: pdf.

Задача № 49. L3

Дата публикации: 11.02.2016.

Решение: pdf.

Задача № 48. Биективный S-блок

Боб строит S-блок, который выполняет преобразование 16-разрядных слов с помощью следующей функции языка Си:

static const u16 S0[256] = <. >;

static const u16 S1[256] = <. >;

register u32 y0 = S0[x & 255];

register u32 y1 = S1[x >> 8];

return (y0 + 1) * (y1 + 1) % 65537 — 1;

Найти заполнение массивов S0 и S1 , при котором S-блок будет биективным.

Дата публикации : 11.01.2016.

Правильно решили: hellman.

Решение: pdf.

Задача № 47. DH-d

Пусть G – циклическая группа большого простого порядка. Трент разработал алгоритм DH-d , который по образующему g группы G и ее элементу g x находит g x d . Здесь d – небольшое натуральное число. Как с помощью машины DH-d решить задачу Диффи – Хеллмана: по ( g , g x , g y ) найти g xy . Предложите решение с минимальным числом обращений к машине.

Дата публикации : 11.01.2016.

Примечание. Внеочередная задача, одна из задач олимпиады NSUCRYPTO-2015.

Решение: pdf.

Задача № 46. Шифрмашина

Шифрмашина работает с двоичной лентой, в начале которой записано входное слово длины n, а затем идут нули. Машина зашифровывает входное слово, возвращая результат на его месте. Шифрмашина может выполнять две операции:

1) менять местами любые два символа ленты;

2) применять к первым m символам ленты фиксированную подстановку S.

Ко всем входным словам применяется одна и та же последовательность операций. Эта последовательность (программа шифрмашины) определяется преобразованием зашифрования – биекцией на словах длины n. При каких условиях на S с помощью шифрмашины можно реализовать любую биекцию?

Дата публикации : 11.01.2016.

Примечание. Внеочередная задача, одна из задач олимпиады NSUCRYPTO-2015.

Решение: pdf.

Задача № 45. Имя + имя

Трент поручил Бобу наладить аутентификацию между сотрудниками его организации. Боб предложил следующее решение. Сначала все сотрудники получают у Трента общий секретный ключ K. Затем для проверки подлинности друг друга пары сотрудников обмениваются своими именами. Каждый из сотрудников проверяет, что его имя отличается от имени визави, а затем вычисляет на ключе K имитовставку от своего имени, дополненного именем визави и меткой времени. Например, Алиса для аутентификации перед Бобом вычисляет имитовставку от строки

а Боб – от строки

Корректность имитовставки для некоторой метки времени в 10-секундном интервале назад доказывает подлинность противоположной стороны. Трент забраковал решение Боба. Почему?

Дата публикации : 07.10.2015.

Решение: pdf.

Задача № 44. Определить режим

Шифратор Amgine реализует алгоритмы СТБ 34.101.31. Известно, что шифрование выполняется либо в режиме сцепления блоков (CBC), либо в режиме гаммирования с обратной связью (CFB), либо в режиме счетчика (CTR). Виктору требуется определить, какой из трех режимов используется. Разрешается подать на вход шифратора два открытых текста вместе с синхропосылками и получить соответствующие шифртексты. Помогите Виктору.

Дата публикации : 07.09.2015.

Дополнительное условие (★): синхропосылки повторять нельзя.

Правильно решили: mathematic_by ★ .

Решение: pdf.

Задача № 43. 3-битовый S-блок

Боб проектирует блочную криптосистему, в которой используется следующий 3-битовый S-блок, заданный многочленами Жегалкина:

Помогите Бобу реализовать действие S-блока 7 логическими операциями из стандартного списка: ¬ (НЕ), ∧ (И), ∨ (ИЛИ), ⊕ (исключающее ИЛИ).

Дата публикации: 07.07.2015.

Поддержка: В. Семенов.

Правильно решили: В. Палуха, mathematic_by .

Решение: pdf.

Задача № 42. QuadDH

Пусть G – циклическая группа большого простого порядка. Трент разработал алгоритм QuadDH , который по образующему g группы G и ее элементу g x находит g x 4 . Виктор всеми силами пытается заполучить описание алгоритма. Виктор считает, что с его помощью он сможет атаковать протокол Диффи – Хеллмана: по (g, g x , g y ) находить g xy . Восстановите ход рассуждений Виктора.

Дата публикации: 07.06.2015.

Правильно решили: mathematic_by.

Решение: pdf.

Задача № 41. Разделить подстановку

Трент выполняет шифрование слов в алфавите A = m – 1>, m – нечетное, с помощью секретной подстановки f : символ открытого текста x при шифровании меняется на символ шифртекста f ( x ). Трент хочет разделить подстановку f между Алисой и Бобом. Для этого Трент находит подстановки f₁ и f₂ , также действующие на A , такие, что f ( x ) = ( f₁ (x) + f₂ ( x )) mod m . Подстановку f₁ Трент передает Алисе, а подстановку f₂ – Бобу. Помогите Тренту выполнить разделение. Докажите, что при четном m разделение невозможно.

Дата публикации: 07.05.2015.

Решение: pdf.

Задача № 40. Вычитание

Боб продолжает разработку программ шифровальной машины Amgine. Помогите Бобу переписать следующую функцию на языке Си, реализующую вычитание из большого числа a , заданного n машинными словами, одиночного машинного слова w :

word zzSubW(word a[], register word w, size_t n) register word t;
size_t i;
for (i = 0; w && i < n; ++i)
t = (a[i] < w), a[i] -= w, w = t;
t = 0;
return w;
>

Перепишите функцию так, чтобы в ней не было локальных переменных.

Дата публикации: 07.02.2015.

Решение: pdf.

Задача № 39. AddRot

Боб разрабатывает алгоритм шифрования, в котором к n-битовым машинным словам применяются преобразования двух типов: Add_с – сложение слова-как-числа с числом c по модулю 2 n , Rot_r – циклический сдвиг слова на r битов влево, c = 1, 2. 2 n – 1, r = 1, 2. n – 1. Доказать, что с помощью сложений Add_с и сдвигов Rot_r можно реализовать любое биективное преобразование машинных слов.

Дата публикации: 11.12.2014.

Примечание. Внеочередная задача, одна из задач олимпиады NSUCRYPTO-2014.

Решение: pdf.

Задача № 38. Комбинаторный компьютер

Трент научился управлять большими ансамблями квантовых частиц и построил компьютер, который может эффективно решать различные комбинаторные задачи, например, за приемлемое время вычислять значение функции
f(n, m, k) = |m по k частиц>| mod n.
Покажите, как с помощью компьютера Трента Боб может за приемлемое время разложить на множители большое составное число.

Дата публикации: 07.12.2014.

Решение: pdf.

Задача № 37. Группа над кольцом

Боб разрабатывает криптосистему, стойкость которой базируется на сложности решения задачи дискретного логарифмирования в группе G. Эта группа составлена из элементов кольца R, операция в G задается многочленом f(x, y) над R: x * y = f(x, y). Сколько способов выбора f имеется у Боба?

Дата публикации: 07.10.2014.

Решение: pdf.

Задача № 36. Телефонный справочник

Трент поручил Бобу разработать интерактивный телефонный справочник. Боб написал программу, которая на запрос имя отвечает парой ( имя , номер_телефона ), сопровождаемой подписью Трента. Подпись доказывает, что абонент с определенным именем действительно имеет определенный номер телефона. К сожалению, Боб не учел, что справочник покрывает только часть имен. Помогите Бобу модернизировать программу так, чтобы она дополнительно возвращала доказательство отсутствия в справочнике абонента с определенным именем. Доказательство должно представлять собой структуру данных, подписанную Трентом. Трент опасается передавать Бобу личный ключ подписи, поэтому все доказательства должны быть созданы Трентом заранее, в момент формирования справочника.

Дата публикации: 07.08.2014.

Решение: pdf.

Задача № 35. Оценки на экзамене

Алиса получила на экзамене оценку a, Боб – оценку b. Оценки выставляются по 10-балльной шкале: a, b ∈ . Алиса и Боб хотят сравнить свои оценки, не раскрывая их друг другу. В распоряжении Алисы и Боба есть 10 шкафов с замками и по 2 ключа от каждого замка. Помогите Алису и Бобу организовать следующие сравнения: 1) a = b? 2) a ≥ b?

Дата публикации: 07.06.2014.

Решение: pdf.

Задача № 34. Умножение и обращение

Умножение по простому модулю p = 2 256 – 189, используемому в СТБ 34.101.45, выполняется за 1 мкс, а мультипликативное обращение по этому модулю – за 100 мкс. Бобу требуется написать программу, которая обрабатывает переменные X_i, Y_i ∈ p – 1> и на месте X_i возвращает X_i * Y_i -1 mod p, i = 1, 2. 100. Вычисления должны быть выполнены не более чем за 500 мкс. Дополнительные переменные вводить нельзя. Помогите Бобу.

Дата публикации: 07.04.2014.

Решение: pdf.

Задача № 33. 2014

В СТБ 34.101.31 используется умножение в поле из 2 128 элементов. Умножение обладает следующим свойством: возведение в квадрат a * a выполняется значительно быстрее, чем общее умножение a * b. Поэтому при возведении элемента a в определенную степень важно организовать вычисления так, чтобы минимизировать число общих умножений, не обращая внимания на число возведений в квадрат. Можно ли найти a 2014 с помощью 5 умножений? С помощью 4 умножений?

Дата публикации: 07.03.2014.

Правильно решили: Владимир Палуха.

Задача № 32. Координаты

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

Дата публикации: 07.02.2014.

Решение: pdf.

Задача № 31. Поиск ключа DES

Алиса и Боб поспорили, кто из них быстрее найдет ключ DES, выбранный наудачу Трентом. Алиса и Боб разбили ключевое пространство пополам и Алиса начала проверять ключи, выполняя контрольные зашифрования и сравнивая результаты с данными, предоставленными Трентом. Алиса уже проверила половину своего ключевого сегмента и не нашла ключ, а Боб еще не начал проверку, что нарушает правила спора. Трент опасается, что спор может затянуться и указывает половину сегмента Боба, которая не содержат ключ. Трент предлагает Алисе поменяться с Бобом оставшимися у них частями сегментов. Следует ли Алисе меняться?

Дата публикации: 07.01.2014.

Решение: pdf.

Задача № 30. Централизованное тестирование

Трент поручил Алисе провести среди студентов тестирование по алгебре. Алиса подготовила очень сложную задачу, в которой требуется найти многочлен f(x) положительной степени с целыми коэффициентами. Боб предложил Алисе организовать проверку решения самими студентами. Боб написал программу, которая сравнивает найденное решение с искомым многочленом, внедренным в код программы. Алиса против проверяющей программы. Алиса опасается, что студент Виктор дизассемблирует код и восстановит f(x), не решая задачу. Помогите Бобу переписать программу так, чтобы определить по ней f(x) было вычислительно трудно.

Дата публикации: 07.12.2013.

Решение: pdf.

Задача № 29. Регулярное сложение

Боб узнал, что если в криптографических программах имеются условные переходы и условия переходов определяются обрабатываемыми данными (но не их размерностями), то эти программы подвержены атакам, основанным на замерах времени или питания. Боб решил переписать программы шифровальной машины Amgine так, чтобы все вычисления были регулярными, т.е. не содержали бы небезопасных условных переходов. Помогите Бобу переписать следующую функцию, реализующую сложение больших чисел:

word zzAdd(word c[], const word a[], const word b[], size_t n) register word carry = 0;
register word w;
size_t i;
for (i = 0; i < n; ++i) w = a[i] + carry;
if (w < carry)
c[i] = b[i];
else
w += b[i], carry = w < b[i], c[i] = w;
>
w = 0;
return carry;
>

Функция написана на языке Си. Большие числа задаются массивами из n машинных слов. Буферы a и c , b и c либо не пересекаются, либо совпадают.

Дата публикации: 07.10.2013.

Решение: pdf.

Задача № 28. Подвесить сервер

При изучении программ поискового сервера Moctod Виктор нашел объявление переменной a :

Виктор выяснил, что эта переменная меняется только при обработке двух специальных поисковых запросов. При обработке запроса «Ring ring ring» переменная преобразуется следующим образом:

a = a / 2 ^ (a % 2) * 96;

а при обработке запроса «In the finite field» немного по-другому:

a ^= a / 2 ^ (a % 2) * 96;

Как только переменная a снова примет значение 1, сервер зависнет. Сможет ли Виктор подвесить сервер, выполнив 18 запросов? 19 запросов?

Дата публикации: 07.09.2013.

Решение: pdf.

Задача № 27. Секретные материалы

Активист Нед Вонс разместил в Интернет секретные материалы, зашифрованные с помощью AES-256. Каждый месяц Нед рассылает в редакции газет всего мира ключ, на котором был зашифрован очередной секретный документ, делая его содержимое общедоступным. Документы Неда производят фурор, все редакции пытаются первыми опубликовать выдержки из них. Уже второй раз подряд в газету Gnutiez приходят письма Виктора. Виктор утверждает, что умеет атаковать AES-256 и в качестве доказательства указывает первый байт следующего ключа, который будет открыт Недом. Этот прогноз каждый раз оказывается верным! В третьем письме Виктор предлагает заплатить за предсказание всех следующих ключей. Трент, который редактирует газету, отказывается платить, утверждая, что Виктор – мошенник. Почему Трент так считает?

Дата публикации: 07.08.2013.

Правильно решили: CryptoOfficer.

Решение: pdf

Задача № 26. Связь между филиалами

Компания Tenhtam является молодой и динамично развивающейся. Прием на работу в Tenhtam идет по всему миру. Для того, чтобы стать сотрудником требуется ответить всего на один вопрос: каким будет следующий элемент последовательности 4 / 10, 25 / 100, 168 / 1000, 1229 / 10000? Бобу поручено наладить защищенное взаимодействие между филиалами компании. Боб организовал в каждом филиале закрытую корпоративную сеть и установил шифровальную машину Amgine. На Amgine попадает вся исходящая корреспонденция филиала и, наоборот, Amgine доставляет сотрудникам филиала всю адресованную им корреспонденцию. Данные, передаваемые между машинами различных филиалов, зашифровываются на общем парном секретном ключе этих филиалов. Объем передаваемых данных быстро растет. Боб опасается, что Виктор, который контролирует открытые каналы связи, может накопить много шифрматериала и определить парный ключ. Поэтому каждое утро парный ключ меняется: новый парный ключ является результатом расшифрования текущей даты на старом ключе. Помогите Виктору найти парный ключ.

Дата публикации: 07.07.2013.

Правильно решили: CryptoOfficer.

Решение: pdf.

Задача № 25. PIN, PIN, PIN,…

У Боба все больше пластиковых карточек. Для каждой карточки требуется помнить PIN-код – число x от 0 до 9999. Как обычно, при трех попытках ввода неверного PIN карточка блокируется. Боб не может запомнить x наверняка. Тем не менее, при предъявлении 7 или 8 PIN-кодов конкретной карточки Боб всегда может выбрать из них тройку, в которой обязательно окажется x . Боб решил действовать следующим образом:

1. Выбирается ключ k – натуральное число. Ключ записывается в очень защищенный блокнот.
2. PIN x зашифровывается, ему ставится в соответствие число y = ( x +1) k mod 10009. Шифртекст y сохраняется в другом, не очень защищенном блокноте.

Боб хочет организовать все так, чтобы каждому y соответствовало 7 или 8 вариантов x . Тогда Боб сможет отобрать три из них, включая правильный, и наверняка пройти аутентификацию с трех попыток. А вот Виктору, даже если он завладел двумя блокнотами, придется проверять не менее 7 вариантов. Как Боб должен выбирать k и как должно быть организовано расшифрование y ?

Дата публикации: 07.06.2013.

Поправка (12.06.2013): исправлены неточности (1009 на 10009, «7 вариантов» на «7 или 8 вариантов»).

Решение: pdf.

Задача № 24. Программа EulerPhi

Бобу требуется написать программу, которая определяет количество различных простых делителей заданного натурального числа n. Число n может быть очень большим, его факторизация затруднена. Однако Боб может воспользоваться программой EulerPhi , которая выполняется на суперкомпьютере Трента и за приемлемое время находит значение функции Эйлера от n. Помогите Бобу, используя следующие дополнительные данные: число простых делителей нечетно и все они имеют вид 2 s r + 1, где s – натуральное число, одинаковое для всех простых делителей, r – нечетное число .

Дата публикации: 07.05.2013.

Решение: pdf.

Задача № 23. p ± 1

Боб продолжает разрабатывать программу генерации простых чисел p >2 512 для криптосистемы RSA. Для защиты от некоторых методов факторизации модуля RSA требуется генерировать такие p, что числа p ± 1 имеют максимально большие простые делители. Пусть

где q₀ – максимальный простой делитель p – 1, q₁ – максимальный простой делитель p + 1. Какое минимальное значение может принимать величина D(p)?

Дата публикации: 07.04.2013.

Решение: pdf.

Задача № 22. Матрицы Belt

В алгоритме выработки имитовставки стандарта СТБ 34.101.31 (Belt) используются две матрицы над полем из двух элементов:

0	0	0	1
1	0	0	1
0	1	0	0
0	0	1	0

1	1	0	0
0	0	1	0
0	0	0	1
1	0	0	0

Вместе с единичной матрицей M ₀ они образуют множество S , которое обладает следующим свойством: сумма любого числа любых различных элементов S является обратимой матрицей. Найдите еще одну матрицу M ₃, после добавления которой к S свойство останется справедливым.

Дата публикации: 07.03.2013.

Решение: pdf.

Задача № 21. Деление на малые простые

Боб разрабатывает программу генерации простых чисел для криптосистемы RSA. Первым этапом теста простоты большого натурального числа a , заданного n ≥ 8 32-разрядными словами, является проверка его делимости на малые простые val . Для этого Боб использует следующую функцию языка Си, которая находит остаток a mod val :

uint32 zzModVal( const uint32 a[], size_t n, uint32 val)
uint32 r = 0;
uint64 divisor;
while (n—)
divisor = r,
divisor divisor += a[n],
r = (uint32)(divisor % val);
return r;
>

Для определения остатка требуется выполнить n делений uint64 % uint32 и еще 2 n сложений и сдвигов. Программа Боба будет использоваться в шифровальной машине Amgine. Деление на этой машине выполняется неэффективно, в 8–10 раз медленнее умножения. Перепишите функцию zzModVal так, чтобы в ней использовалось не более 4 делений uint32 % uint32 , не более 2 n умножений uint32 * uint32 , а суммарное число сложений и сдвигов увеличилось не более чем в 2 раза.

Дата публикации: 07.02.2013.

Поправка (05.03.2013): «. не более 2 n + 2 умножений . «.

Решение: pdf.

Задача № 20. Истинно-истинно случайные буквы

Трент подарил Бобу истинно-истинно случайный 6-гранный кубик, результаты бросков которого независимы и равновероятны. Бросая кубик, Боб генерирует истинно-истинно случайные буквы русского алфавита. Верно ли, что для генерации отдельной буквы (одной из 33) Боб может использовать менее √ 5 бросков кубика в среднем?

Дополнительный вопрос (∗): верно ли, что для генерации отдельной буквы английского алфавита (одной из 26) потребуется больше √ 5 бросков в среднем?

Еще один дополнительный вопрос (★): изменятся ли ответы на предыдущие вопросы при замене √ 5 на 21163 / 9721?

Дата публикации: 07.01.2013.

Правильно решили: Владимир Палуха.

Решение: pdf.

Задача № 19. Социальная сеть

Алиса и Боб зарегистрировались в социальной сети и вошли в группу любителей рок-группы The Group. Группа секретная, все ее члены, и только они, знают секретный ключ K. Ключ используется в алгоритмах шифрования СТБ 34.101.31 (режим гаммирования с обратной связью).

С помощью K члены группы проверяют друг друга, а также обмениваются продуктами творчества The Group. Пользователь социальной сети, который хочет получить некоторый продукт, обращается с запросом к предполагаемому члену группы. В ответ ему отправляется письмо со случайной синхропосылкой и предлагается зашифровать имя отправителя, используя K и эту синхропосылку. Если имя зашифровано корректно, то далее высылается запрошенный продукт, зашифрованный на K. При шифровании снова используется случайная синхропосылка, которая отправляется вместе с данными.

Виктор не входит в группу, не знает K, он знает только, что Алиса и Боб уже который год разыскивают треки песен «Alice goes to France» и «Bronze goes to Bob». Виктор, в свою очередь, желает получить слова секретной песни «Navajo know». Помогите Виктору.

Дата публикации: 07.12.2012.

Правильно решили: CryptoOfficer.

Решение: pdf.

Задача № 18. Генерация простых

Боб генерирует простые числа, используя теорему Диемитко: если q – нечетное простое, R – четное, R < 4(q + 1), n = qR + 1 и для некоторого целого a выполняются условия:

Для построения простого n битовой длины k (2 k – 1 < n < 2 k ) Боб находит [k / 2]-битовое простое q (выбирает малое простое или генерирует q снова с помощью теоремы Диемитко). Затем Боб выбирает R так, что n = qR + 1 имеет нужную длину k и проверяет условия 1) и 2) для случайного a.

Алгоритм Боба содержит ошибку. Найдите составное n, которое Боб может признать простым.

Дата публикации: 07.11.2012.

Поправка (05.12.2012): «. Боб выбирает четное R так, что. «.

Решение: pdf.

Задача № 17. Серийное производство

Трент наладил серийное производство шифровальных машин Amgine и выпустил первую серию из n машин. Производственные ресурсы Трента практически неограниченны и Виктор не может сделать никаких априорных выводов об объеме серии. Однако известно, что машины снабжены последовательными серийными номерами (от 1 до n) и выдаются абонентам в случайном порядке. Виктор узнал, что Алиса получила машину с номером 539, Боб – с номером 734, а Глеб – с номером 222. Помогите Виктору оценить n.

Дата публикации: 07.10.2012.

Подходящие оценки: CryptoOfficer.

Решение: pdf.

Задача № 16. Специальное умножение

В стандарте ЭЦП Узбекистана O’z Dst 1092:2009 используется специальное умножение x ® y = x + (1 + x R) y mod p, где p – простой модуль, R – произвольный вычет по этому модулю. Покажите, как можно найти 100-ую степень x относительно операции ®, использовав не более десяти умножений и двух сложений / вычитаний по модулю p. Разрешается проводить предвычисления с p и R.

Дата публикации: 07.09.2012.

Правильно решили: CryptoOfficer, axiomatikos.

Решение: pdf.

Задача № 15. FNV

Функция хэширования FNV (isthe.com/chongo/tech/comp/fnv/) обрабатывает сообщение msg из size октетов следующим образом:

uint32 fnv32( const uint8* msg, size_t size)
uint32 hash = 2166136261;
while (size—)
hash ^= *msg++,
hash *= 16777619;
return hash;
>

Найдите сообщение msg , которое имеет нулевое хэш-значение.

Дата публикации: 07.08.2012.

Правильно решили: CryptoOfficer.

Решение: pdf.

Задача № 14. Матрицы

В системе связи используется протокол Диффи – Хеллмана. Выбран простой модуль p = 2 127 − 1 и найден первообразный корень g по модулю p . Алиса, Боб. выбирают наудачу личные ключи a , b . ∈ и записывают их на собственные сверхзащищенные носители Dractrams. Для связи друг с другом Алиса и Боб, а также другие пары абонентов, обмениваются открытыми ключами g a , g b и определяют общий ключ K = ( g a ) b = ( g b ) a (приведение mod p опускается). Трент обратил внимание на то, что вырабатываемый парами ключ K будет всегда одним и тем же. Это может использовать Виктор, который непрестанно прослушивает каналы связи. Абоненты понимают озабоченность Трента, но не хотят менять надежно защищенные личные ключи. Выход предложил Боб:

1. Публикуется детерминированный алгоритм, который по номеру сеанса строит матрицу M порядка 127 над полем из двух элементов. Матрица M обратима и строится как псевдослучайная.
2. Числа от 0 до 2 127 − 1 отождествляются с двоичными векторами размерности 127. Личный ключ k (как вектор) умножается на матрицу M и произведение (как число) обозначается через M ( k ).
3. Алиса определяет сеансовую матрицу M и посылает Бобу одноразовый открытый ключ g M ( a ) .
4. Боб определяет сеансовую матрицу M и посылает Алисе одноразовый открытый ключ g M ( b ) .
5. Алиса и Боб вычисляют общий сеансовый секретный ключ K_M = g M ( a ) M ( b ) .

Виктор утверждает, что сможет определить личные ключи Алисы и Боба, перехватив данные 130 сеансов связи. Прав ли Виктор?

Дата публикации: 07.07.2012.

Правильно решили: CryptoOfficer.

Решение: pdf.

Задача № 13. Протокол аутентификации

Алиса и Боб проводят взаимную аутентификацию, которая состоит в проверке знания общего секретного ключа θ . На этом ключе стороны выполняют шифрование пар 16-байтовых блоков. Используются алгоритмы шифрования в режиме сцепления блоков СТБ 34.101.31. При шифровании выбираются нулевые синхропосылки. Аутентификация проводится по следующему протоколу:

1. Боб выбирает случайный блок X _B и посылает его Алисе.
2. Алиса выбирает случайный блок X _A и посылает Бобу зашифрованную пару ( X_A , X_B ).
3. Боб выполняет расшифрование принятого сообщения, получая ( X_A ‘, X_B ‘), а затем сравнивает X_B ‘ с X_B . Если блоки отличаются, то Боб завершает протокол с ошибкой. В противном случае Боб признает подлинность Алисы и отсылает ей зашифрованную пару ( X_B , X_A ).
4. Алиса выполняет расшифрование принятого сообщения, получая ( X_B », X_A »), а затем сравнивает X_A » c X_A . Если блоки отличаются, то Алиса завершает протокол с ошибкой. В противном случае Алиса признает подлинность Боба.

Покажите, как Виктор, который не знает θ , может ввести Алису в заблуждение, выдав себя за Боба.

Дата публикации: 07.06.2012.

Правильно решили: CryptoOfficer, axiomatikos.

Решение: pdf.

Задача № 12. Деление многочленов

Боб реализует деление многочленов над полем из двух элементов. Многочлены задаются двоичными словами по правилам СТБ 34.101.31. Боб написал программу на языке C++, в которой многочлен, заданный строкой октетов poly, нацело делится на многочлен g ( x ).

void polyDiv(uint8* poly, size_t n)
<
uint8 a = 0;
for ( int i = 0; i < n; i++)
<
a ^= poly[i];
a ^= a a ^= a poly[i] = a;
a >>= 6;
>
>

Дата публикации: 07.05.2012.

Правильно решили: axiomatikos.

Решение: pdf.

Задача № 11. Умножение многочленов

Боб реализует умножение многочленов над полем из двух элементов. Многочлены задаются двоичными словами по правилам СТБ 34.101.31. Боб утверждает, что при определенном заполнении массивов log1 , log2 , crt1 , crt2 следующая программа на языке C++ реализует умножение многочлена a на многочлен b :

uint16 mul8x8(uint8 a, uint8 b)
<
static const uint8 log1[256] = <. >;
static const uint8 log2[256] = <. >;
static const uint16 crt1[256] = <. >;
static const uint16 crt2[256] = <. >;

if (a == 0 || b == 0)
return 0;

uint16 d1, d2;
if (((d1 = log1[a]) += log1[b]) > 255)
d1 -= 255;
if (((d2 = log2[a]) += log2[b]) > 255)
d2 -= 255;

return crt2[d1] ^ crt1[d2];
>

Восстановите заполнение массивов.

Дата публикации: 07.04.2012.

Правильно решили: axiomatikos.

Решение: pdf.

Задача № 10. Поиск вирусов

Боб проверяет заражение программ на своем компьютере вирусами V ₁. V_n . Как только в проверяемой программе обнаружена сигнатура некоторого из вирусов, Боб помещает эту программу в карантин и переходит к следующей программе. Известно, что программа заражена вирусом V_i с вероятностью p_i независимо от других вирусов. Известно также, что для проверки заражения V_i требуется время t_i . В какой очередности Боб должен проверять сигнатуры вирусов, чтобы среднее время проверки было минимальным?

Дата публикации: 07.03.2012.

Решение: pdf.

Задача № 9. Отпечатки пальцев

Боб использует в качестве пароля случайную двоичную строку длины n. Пароль вводится на сенсорном устройстве Dapi. Виктор может разглядеть отпечатки пальцев Боба и узнать, сколько в пароле единиц и сколько нулей. Виктор может воспользоваться наблюдениями и уменьшить число паролей, которые требуется проверить. Если, например, Виктор знает, что в пароле ровно одна единица, то ему требуется проверить не 2 n , а только n паролей. Во сколько раз уменьшается среднее число паролей, которые требуется проверить Виктору?

Дата публикации: 07.02.2012.

Решение: pdf.

Задача № 8. Генерация ключа

Бобу требуется сгенерировать ключ, который обладает свойствами C ₁. C _n. Боб выбирает ключ наудачу и проверяет его свойства. Как только одно из свойств не выполняется, Боб генерирует новый ключ, проверяет его и так далее, до тех пор пока не будет найден ключ, обладающий всеми свойствами. Известно, что случайный ключ обладает свойством C_i с вероятностью p_i независимо от других свойств. Известно также, что для проверки свойства C_i требуется время t_i. В какой очередности Боб должен проверять свойства, чтобы среднее время генерации ключа было минимальным?

Дата публикации: 07.01.2012.

Правильно решили: axiomatikos.

Решение: pdf.

Задача № 7. Программа умножения

Алиса написала для Amgine программу умножения больших чисел. Программа написана на языке C:

typedef unsigned long word;
typedef unsigned long long dword;
void mul(word c[16], const word a[8], const word b[8])
<
size_t i, j;
word carry;
dword mul;
for (i = 0; i < 16; c[i++] = 0);
for (i = 0; i < 8; ++i)
<
for (j = 0, carry = 0; j < 8; ++j)
((mul = b[i]) *= a[j]) += carry + c[i + j],
c[i + j] = mul,
carry = mul >> sizeof (word) * 8;
c[i + j] = carry;
>
>

Найдите ошибку в программе.

Дата публикации: 07.12.2011.

Правильно решили: axiomatikos.

Решение: pdf.

Задача № 6. Цифры

Трент реализовал в шифровальной машине Amgine алгоритм Digit , который берет на вход вещественное x и натуральное n , и возвращает n -й после запятой десятичный знак x . В качестве x можно использовать любое аналитически заданное выражение. Например, Digit (π, 1) = 1, Digit (π, 2) = 4. Алиса и Боб получили Amgine и решили воспользоваться еe возможностями следующим образом:

1. Стороны по секретному каналу договариваются об общем ключе k – большом натуральном числе.

2. Алиса выбирает натуральное n и вырабатывает гамму Digit ( a k , n ), Digit ( a k , n + 1). где a = 1 + 2 cos(π / 9).

3. Символы гаммы суммируются с символами открытого текста. Полученный шифртекст отправляется вместе с n .

Виктор обрадован. Почему?

Дата публикации: 07.11.2011.

Решение: pdf.

Задача № 5. Последняя теорема Ферма

Виктор утверждает, что найденное Уайлсом доказательство последней теоремы Ферма содержит ошибку. Виктор присылает в математический журнал Selanna показатель n > 2, для которого он знает (?) решение уравнения x n + y n = z n в натуральных числах. Трент, который редактирует журнал, просит Виктора предъявить решение. Но Виктор отказывается это сделать, предлагая Тренту сначала анонсировать его открытие. Трент находится в затруднительном положении.

Предложите криптографический протокол, который, с одной стороны, доказывал бы Тренту, что Виктор действительно знает решение, и, с другой стороны, не раскрывал бы это решение.

Дата публикации: 07.10.2011.

Решение: pdf.

Задача № 4. Период последовательности

В качестве гаммы поточного шифра Алиса использует ненулевую двоичную последовательность (s_t), заданную следующим рекуррентным соотношением:

(сложение выполняется по модулю 2). Найдите период этой последовательности.

Дата публикации: 07.09.2011.

Решение: pdf.

Задача № 3. Временной замок

Боб передает Алисе ключ K так, чтобы им можно было воспользоваться не сразу, а по истечении определенного времени. Боб выбрал простое p = 2 128 – 159 и в течение месяца рассчитывал последовательность Фибоначчи по модулю p:

Последний элемент последовательности Боб использовал в качестве ключа. Компьютеры Алисы уступают компьютерам Боба и поэтому Боб считает, что для определения ключа Алисе потребуется не меньше месяца. Помогите Алисе найти ключ K раньше.

Дата публикации: 07.08.2011.

Решение: pdf.

Задача № 2. Реализация Belt

Трент разрабатывает шифратор Amgine и решает использовать в шифраторе алгоритмы Belt (СТБ 34.101.31). Трент организовал реализацию алгоритмов на языке Си. Алиса написала для Трента функцию

uint32 G(uint32 x, int r);

которая выполняет преобразование G_r 32-разрядного слова x . Боб написал функцию, которая реализует такт зашифрования:

void R(uint32* a, uint32* b, uint32* c, uint32* d, const uint32* key, uint32 i)
<
uint32 e;
*b ^= G(*a + key[7 * i — 7 & 7], 5);
*c ^= G(*d + key[7 * i — 6 & 7], 21);
*a -= G(*b + key[7 * i — 5 & 7], 13);
e = G(*b + *c + key[7 * i — 4 & 7], 21);
*b += e;
*c -= e;
*d += G(*c + key[7 * i — 3 & 7], 13);
*b ^= G(*a + key[7 * i — 2 & 7], 21);
*c ^= G(*d + key[7 * i — 1 & 7], 5);
e = *a, *a = *b, *b = *d, *d = *c, *c = e;
e = 0;
>

Трента не устраивает, что в функции используется локальная переменная e . Ресурсы Amgine ограничены и на счету каждый байт стека. Помогите Бобу переписать функцию так, чтобы в ней не было локальных переменных.

Дата публикации: 07.07.2011.

Решение: pdf.

Задача № 1. Первая цифра

Код сейфа представляет собой последовательность цифр от 1 до 9. Алиса и Боб хотят сгенерировать случайный контрольный код. Каждая из сторон желает влиять на результат генерации. Алиса и Боб договорились, что для генерации каждой цифры кода они будут действовать следующим образом:

– Алиса выбирает наудачу натуральное A, не кратное 10;

– Боб выбирает наудачу натуральное B;

– в качестве цифры кода выбирается первая десятичная цифра A B ;

Виктор обрадован. Почему?

Дата публикации: 07.06.2011.

Решение: pdf.

Задача о ранце в криптографии (Knapsack problem in cryptography)

Задача о рюкзаке (или Задача о ранце) в криптографии (англ. Knapsack problem) — это задача, на основе которой американские криптографы Ральф Меркл и Мартин Хеллман разработали первый алгоритм шифрования с открытым ключом.

Далее в программе

• Формулировка задачи о рюкзаке (+почему рюкзак?)
• Легкая и трудная проблемы
• Примеры
• История

Что такое шифрование с открытым ключом?

Для криптографии с открытым ключом требуется два ключа.

• Один ключ сообщает вам, как зашифровать сообщение, и он является «общедоступным», поэтому любой может его использовать.

• Другой ключ позволяет расшифровать сообщение. Этот код дешифрования хранится в секрете, поэтому только человек, знающий ключ, может расшифровать сообщение.

Некоторые алгоритмы имеют следующую характеристику: каждый из двух ключей может использоваться как для шифрования, так и для дешифрования.

Хотя это кажется малополезным, если вы пытаетесь сохранить что-то в секрете!

Первый общий алгоритм с открытым ключом использовал алгоритмом ранца.

Исходя из определения систем с открытым ключом, чтобы успешно шифровать (и расшифровать) сообщение нужны два ключа. «Легальный» получатель сообщения знает секретный ключ , отправитель же владеет другим открытым ключом .

Что делать, если злоумышленнику стал известен открытый ключ?

Есть ответ: открытый ключ должен получаться из секретного ключа при помощи преобразования ( односторонней функции) , обладающего следующими двумя свойствами:

• , зная A, вычислить саму функцию легко

• , а вычислить обратную функцию трудно

Что такое «легко» и «трудно»?

Алгоритмы с открытым ключом основаны на вычислительной сложности различных задач.
Более точно термин «легко» обычно означает, что проблему можно решить за полиномиальное время от длины входного сообщения. Т.е. пусть входное сообщение состоит из битов, тогда время вычисления — , где — зафиксированная константа. Будем говорить, что алгоритм из класса полиномиальных алгоритмов Р.

Термин «трудно» более сложно определить. В общем случае можно считать, что невозможно решить проблему, если усилия для ее решения больше полиномиального времени от величины входного сообщения.

Т.е. пусть входное сообщение состоит из битов, и время вычисления функции , то будем говорить, что это вычислительно невозможная задача.

Задача о рюкзаке формулируется так

Задан набор (рюкзачный вектор) — это упорядоченный набор из ( различных натуральных чисел . Пусть есть число — целое и положительное. Задачей является нахождение такого набора , чтобы в сумме они давали ровно .

В наиболее известном варианте задачи о рюкзаке требуется выяснить, обладает ли данная пара решением. В варианте, используемом в криптографии, нужно для данного входа построить решение, зная, что такое решение существует. Оба эти варианта являются NP-полными.

Аналогия с рюкзаком

В самом простом случае обозначает размер (вместительность) рюкзака, а каждое из чисел указывает размер (вес) предмета, который может быть упакован в рюкзак. Задачей является нахождение такого набора предметов, чтобы
рюкзак был полностью заполнен.

Т.е представьте, что у вас есть набор гирь 1, 6, 8, 15 и 24, вам нужно упаковать рюкзак весом 30.

В принципе решение всегда может быть найдено полным перебором подмножеств и проверкой, какая из их сумм равна . В нашем случае, это означает перебор подмножеств (включая при этом и пустое множество). Это вполне осуществимо.

Но что будет, если существует несколько сотен чисел ?
В нашем примере n = 5, чтобы не усложнять изложение. В реальных условиях пpимер будет иметь, скажем, 300 . Суть здесь в том, что неизвестны алгоритмы, имеющие существенно меньшую сложность по сpавнению с полным перебором. Поиск среди подмножеств не поддается обработке. В самом деле, задача о рюкзаке известна как NP-полная… NP-полные задачи рассматриваются как трудновычислимые.

Подходит ли функция под указанные требования?

Определим функцию следующим образом. Любое число может быть задано двоичным представлением из pазpядов, где пpи необходимости добавляются начальные нули. Теперь определим как число, получаемое из суммированием всех таких , что соответствующий pазpяд в двоичном представлении равен 1.

Функция определялась набором . Очевидно, что если мы в состоянии вычислить из , то пpактически за то же время будет решена задача о рюкзаке: по немедленно вычисляется его двоичное представление, которое в свою очередь дает компоненты набора , входящие в сумму для . С другой стороны, вычисление из является легким. Так как задача о рюкзаке NP-полна, является хорошим кандидатом для односторонней функции. Конечно, надо потребовать, чтобы было достаточно большим, скажем, не менее .

Шифрование

Открытый текст

Открытый текст (англ. plain text) — в криптографии исходный текст, подлежащий шифрованию, либо получившийся в результате расшифровки. Может быть прочитан без дополнительной обработки (без расшифровки).

Шифровать можно двумя способами:

1. Шифр сообщения получается, если возвести элементы данного рюкзачного вектора в степень соответствующих им бит шифруемого сообщения и далее перемножить все результаты, то есть если , а сообщение , то шифром будет число . Это мультипликативным способ.
2. Шифр сообщения получается, если умножить элементы данного рюкзачного вектора на соответствующие им биты шифруемого сообщения и далее просуммировать все результаты, то есть если , а сообщение , то шифром будет число . Такой способ называют аддитивным.

Для шифрования открытого текста в двоичном представлении его разбивают на блоки длины (например, Вы можете представить вес 30 двоичным кодом 11110). Считается, что единица указывает на наличие предмета в рюкзаке, а ноль на его отсутствие.

Шифрование рюкзака обеспечивает хороший подход к созданию открытых и закрытых ключей, где закрытый ключ прост в использовании, а открытый ключ трудно вычислить.
Так, мы можем составить систему, где:

открытым ключом будет служить «трудная» проблема, т.к. с помощью неё можно легко шифровать и невозможно дешифровать сообщение.

закрытым ключом — будет же служить «лёгкая» проблема, т.к. с помощью неё можно легко дешифровать сообщение. Без закрытого ключа придётся решать «трудную» задачу рюкзака.

«Лёгкая» проблема

Сверхрастущий рюкзачный вектор

Рюкзачный вектор называется сверхрастущим, если для , т.е каждый член последовательности больше суммы предыдущих.

Для сверхрастущих векторов Α задача о рюкзаке легко решаема. Т.е. рюкзак собрать несложно.
Рассмотрим на примере:

Алгоритм

1. Общий вес ранца сравнить с наибольшим весом в последовательности.
   Если общий вес меньше числа, значит, в рюкзаке его нет. Если общий вес больше числа, он в рюкзаке.
2. Вычесть число из общей суммы и сравните со следующим по величине числом.
3. Повторить (1)-(2) пока общая сумма не достигнет нуля.
   Если сумма не достигает нуля, то решения нет.

«Трудная» проблема

Расшифровать задачу о несверхувеличивающемся рюкзаке гораздо сложнее.
Один алгоритм, который использует сверхувеличивающийся рюкзак для частного ключа и несверхувеличивающийся рюкзак для открытого ключа, был создан Мерклом и Хеллманом.
Они сделали это, взяв задачу сверхувеличивающегося рюкзака и преобразовав ее в несверхувеличивающую задачу.
(Меркл и Хеллман, используя модульную арифметику, разработали способ трансформации «лёгкого» рюкзака в «трудный»)

Создание открытого ключа

Несколько важных понятий

• Обозначим наименьший неотрицательный остаток от деления на ,
  где — целые, , [x/m] — целая часть,

• Если вышеуказанное условие заменяется более сильным
  условием , то говорят, что получается из сильным модульным умножением относительно .

• Криптосистема — это завершённая комплексная модель, способная производить двусторонние криптопреобразования над данными произвольного объёма и подтверждать время отправки сообщения, обладающая механизмом преобразования паролей, ключей и системой транспортного кодирования.

Создатель криптосистемы выбирает такую систему , что вектор является сверхрастущим, а получается из сильным модульным умножением относительно . Вектор раскрывается как ключ зашифpования и двоичные блоки длины посылаются к проектировщику как числа , полученные с помощью вектора .

Перехватчик сообщений должен решать задачу о рюкзаке для входа . Создатель же криптосистемы вычисляет
и решает задачу о рюкзаке для входа . Почему все это работает,
показывает следующая лемма.

Лемма. Предположим, что сверхрастущий вектор и вектор получен из сильным модульным умножением относительно . Предположим далее, что , —произвольное натуральное число и . Тогда справедливы следующие утверждения.

(i) Задача о рюкзаке разрешима за линейное время. Если решение существует, то оно единственно.
(ii) Задача о рюкзаке имеет не более одного решения.
(iii) Если существует решение для входа , то оно совпадает с единственным решением для входа .
доказательство(стр. 104)

Возмём сверхрастущую последовательность; например, . Модуль должен быть больше суммы всех чисел в последовательности, например 110. Множитель не должен иметь общих делителей с модулем. Итак, давайте выберем 31.

Итак, мы вычислили открытый ключ: и закрытый ключ — .

Теперь попробуем отправить двоичную последовательность: 100100111100101110

Некоторые преимущества открытых ключей

• При использовании криптосистемы с открытым ключом обе стороны не встречаются, они даже могут не знать друг друга и использовать любые виды связи.

• Длина ключа. В симметричной криптографии, если ключ длиннее исходного сообщения, никакого действительного выигрыша не достигается. Что касается криптосистем с открытым ключом, то у них длина ключа зашифрования не имеет значения, поскольку он открытый и общедоступный. Поэтому и длина ключа расшифрования не так важна (получатель только хранит его в секретном месте)

История

Долгое время ранцевые криптосистемы рассматривались как наиболее привлекательные и перспективные криптосистемы благодаря их NP-полноте и высокой скорости шифрования и дешифрования. Многие схемы используют задачу о ранце (в различных вариациях), вот лишь несколько из них: the compact knapsack problem, the multiplicative knapsack problem, the modular knapsack problem, the matrixcover problem, the group factorization problem…

К сожалению, большинство из них уязвимы для атак. Оказалось, что нетривиально спроектировать защищенную криптосистему на основе задачи о ранце, хотя задача известна как NP-полная. Большинство ранцевых криптосистем было взломано. Несмотря на это, в отличие от целочисленной факторизации и дискретного логарифма, общая задача о рюкзаке (решении) является доказанной NP-полной проблемой.

Некоторые думают, что однажды может быть изобретен алгоритм с полиномиальным временем для решения задач целочисленной факторизации и дискретного логарифмирования, в то время как задача о рюкзаке по-прежнему останется NP-полной задачей.

Тут есть несколько «НО».

Во-первых, NP-полнота основана на анализе наихудшего случая, во-вторых, NP-полнота — это характеристики общей проблемы, а не конкретного случая. Это означает, что если рассматривать среднюю сложность, задача о рюкзаке может быть несложной.

Материал подготовлен на основе данной литературы:

(1) А. Саломаа. Криптография с открытым ключом/ Public-Key Cryptography. — Springer-Verlag, 1990. — Стр. 75-82, стр. 101—111

(2) Мин Кин Лай. Ранцевые криптосистемы: прошлое и будущее — Калифорнийский университет, 2001
(3) Baocang Wang, Qianhong Wu, Yupu Hu. A knapsack-based probabilistic encryption scheme. 2007

• криптографические алгоритмы
• задача о ранце
• криптография
• защита информации