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

Задача о ранце в криптографии (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

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

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

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

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

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

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

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

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

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

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

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

Первая группа, очень широко распространенная — это криптопровайдеры (или 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-порт. Возможно подключение устройства к компьютеру непосредственно в процессе работы.

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

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

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

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

6.6. Криптографические методы защиты

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

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

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

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

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

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

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

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

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

Основные сведения о криптографии. Под криптологией (от греческого kruptos — тайный и logos сообщение) понимается наука о безопасности (сек­ретности) связи.

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

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

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

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

Структурно подсистема состоит из:

♦ программных средств симметричного шифрования данных;

♦ программно-аппаратных средств цифровой подписи электронных документов (ПАС ЦП). Функции подсистемы предусматривают;

♦ обеспечение целостности передаваемой по каналам связи и хранимой информации;

♦ имитозащиту сообщений, передаваемых по каналам связи;

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

♦ обеспечение юридической значимости электронных документов;

♦ обеспечение аутентификации источника данных.

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

♦ угрозы, направленные на несанкционированное ознакомление с информацией;

♦ несанкционированное чтение информации на машинных носителях и в ЗУ ЭВМ;

♦ незаконное подключение к аппаратуре и линиям связи;

♦ снятие информации на шинах питания;

♦ перехват ЭМИ с линий связи;

♦ угрозы, направленные на несанкционированную модификацию (нарушение целостности) информации:

♦ изменение служебной или содержательной части сообщения;

♦ изъятие (уничтожение) сообщения.

♦ угрозы, направленные на искажение аутентичности отправителя сообщения:

♦ незаконное присвоение идентификаторов другого пользователя, формирование и отправка электрон­ного документа от его имени (маскарад), либо утверждение, что информация получена от некоего пользователя, хотя она сформирована самим нарушителем;

♦ повторная передача документа, сформированного другим пользователем;

♦ искажение критичных с точки зрения аутентичности полей документа (даты формирования, поряд­кового номера, адресных данных, идентификаторов отправителя и получателя и др.).

♦ угрозы, связанные с непризнанием участия:

♦ отказ от факта формирования электронного документа;

♦ отказ от факта получения электронного документа или ложные сведения о времени его получения;

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

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

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

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

Аутентификация пользователя сети — установление подлинности личности пользователя сети, которому требуется доступ к защищаемой информации или необходимо подключиться к сети;

Аутентификация сети — установление подлинности сети, к которой получен доступ;

Аутентификация хранящихся массивов программ и данных — установление факта, что данный массив не был изменен в течение времени, когда он был вне посредственного контроля, а также решение вопро­сов об авторстве этого массива данных;

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

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

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

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

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

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

♦ скрытие содержания сообщения;

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

Цифровая подпись обеспечивает:

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

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

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

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

Имитозащита обеспечивает — целостность сообщения в соответствии со свойствами контрольной суммы.

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

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

Шифрование сообщений осуществляется на абонентском или канальном уровне. Средства шифрования реализуются программно, аппаратно-программно или аппаратно.

Разработки в области канального шифрования ведутся в основном в странах НАТО. Среди фирм, изготав­ливающих подобное оборудование, наиболее известными являются: CyLink, Fredericks, Harris, GTE, E-Systems (США), Newbridge Microsystems (Канада), Siemens, Telefunken, Tele Security Timman (Германия), Philips USFA (Нидерланды), Cryptech Belgie (Бельгия), Plessy, Racal, Corros, Marconi (Великобритания).

Интересным с точки зрения перспектив развития средств канального шифрования является предложенный фирмой Newbridge Microsystems (Канада) процессор СА20СОЗА для шифрования данных по стандарту DES. Ключ хранится в энергонезависимой постоянной памяти, не имеющей доступа извне. Предлагаются версии процессора с тактовыми частотами 2,5 и 5 МГц.

Наиболее важными характеристиками средств шифрования, работающих на канальном уровне, являются:

♦ возможность работы в сетях с коммутацией пакетов Х.25;

♦ тип возможных к использованию модемов;

♦ протоколы обмена ключевой информацией;

♦ способ ввода ключей;

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

В основном скорости шифрования равны 64 Кбит/с для синхронного ре­жима и 19,2 Кбит/с для асинхронного. Этого вполне достаточно для работы по выделенным телефонным линиям, но совершенно не приемлемо для об­мена зашифрованной информацией по оптоволоконным линиям связи.

Для таких приложений могут подойти только высокоскоростные шифра­торы CIDEC-HS, CIDEC-HSi, и CIDEC-VHS фирмы Cylink — мирового лидера в производстве средств канального шифрования. Устройство FX-709 также обеспечивает высокую скорость работы, но является мостом для соеди­нения сетей Ethernet через интерфейсы RS-422 и RS-449.

Для канального шифрования, как правило, используются потоковые шифры. Главным их достоинством является отсутствие размножения ошибок и высокая скорость. Единственным стандартным методом генери­рования последовательностей для поточного шифрования остается метод, применяемый в стандарте шифро­вания данных DES в режиме обратной связи от выхода. Поэтому многие производители разрабатывают собственные алгоритмы, например фирма British Telecom реализовала в своих приборах B-CRYPT собствен­ный секретный алгоритм В-152.

Программа аттестации коммерческих средств защиты связи ССЕР (Commercial COMSEC endorsement program) Агентства национальной безопасности (АНБ) США предусматривает выдачу секретных криптоалго­ритмов некоторым фирмам-изготовителям интегральных микросхем США для использования их только в США. Первый такой алгоритм был реализован фирмой Harris Semiconductor в ее криптографическом крис­талле с интег-ральными микросхемами HS3447 Cipher.

Шифраторы, работающие на низких скоростях, обычно совмещают с модемами (STM-9600, Glo-Warm, Mesa 432i). Для средне- и высокоскоростных шифраторов изготовители обеспечивают совместимость с про­токолами V.35, RS-449/422, RS-232 и Х.21. Определенная группа приборов ориентирована на применение в узлах и конечных пунктах сетей с коммутацией пакетов Х.25 (Datacriptor 64, Secure X.25L, Secure X.25H, Telecript-Dat, CD225, KryptoGuard). Управление ключами — принципиально важный вопрос в любой криптосис-теме. Большинство канальных шифраторов американского производства ориен-тировано на иерархический метод распределения ключей, описываемый национальным стандартом ANSI X9.17. В коммерческом секторе получают распространение криптосистемы с открытым распределением ключей. Напри-мер, фирма Cylink помимо реализации ANSI X9.17 имеет собственную запатентованную систему автоматического распределения ключей SEEK.

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

Фирма Airtech, одна из первых начавшая производство стандартных встраиваемых блоков шифрования Rambutan, применяет магнитные карты для ввода ключей в канальные шифраторы. Фирма British Telecom выпускает карточку шифрования Lector 3000 для «дорожной» ЭВМ Toshiba TS 200/100 в версии с блоком Rambutan. Блок Rambutan разработан Группой безопасности связи и электронных средств CESG (Communications Electronics Security Group) Правительственного Управления связи Великобритании GCHQ (Government Communications Headguarters) специально для встраивания в аппаратуру, предназначенную для обработки и передачи важной правительственной информации, включающей и информацию с грифом «кон­фиденциально».

Шифраторы фирмы Cylink имеют клавиатуру для ввода ключей и могут передавать сигналы тревоги и состояния прибора. Дистанционная система управления сетью CNMS (Cylink Network Management System) фирмы Cylink может контролировать до 256 шифраторов CIDECHSi из одного центрального пункта.

Несимметричные криптосистемы используются для формирования цифровой подписи и шифрования (формирования) симметричных ключей при их рассылке по каналам связи. Среди протоколов распределения ключей на практике используется метод Диффи-Хеллмана и метод цифрового конверта. Среди методов циф­ровой подписи наибольшее применение нашли RSA-подобные алгоритмы и алгоритмы на основе метода Эль-Гамаля, стандар-тизованные в ряде стран. Наиболее перспективным представляется использование усовершенствованного метода цифровой подписи Эль-Гамаля, который в последние годы стандартизован в США и России.

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

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

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

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

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

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

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

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