7. Модель криптосистемы с секретным ключом

В системе, показанной на рис. 2.1, в информационных отношениях принимают участие три действующих лица: отправитель (абонент А) и получатель информации (абонент В), а также противник (W). Современные одноключевые криптосистемы предполагают использование взаимно-обратных преобразований E (encryption) и D (decryption) блоков данных фиксированной длины. Для задания блочной криптосистемы необходимо определить:

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

• размер раундового ключа, число раундов шифрования;

• р аундовую функцию F шифрования;

• алгоритм получения раундовых ключей из исходного ключа kAB .

Задача абонента А заключается в том, чтобы передать получателю конфиденциальное сообщение m, состоящее из t блоков длины n, т. е. m = m1m2 ...mi ...mt , i = .

Задача абонента В заключается в том, чтобы, получив переданное сообщение c c1c2 ...ci ...ct , понять его содержание. Для того чтобы только получатель мог прочитать посланное сообщение, отправитель преобразует открытый текст m с помощью функции зашифрования Е и секретного (известного только А и В) ключа kAB в шифротекст с: c = EAB (m) , который и поступает в канал связи. Получатель восстанавливает исходный текст сообщения с помощью функции расшифрования D и того же секретного ключа kAB : m = DAB (c).

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

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

8. Модель криптосистемы с открытым ключом. Криптосистема rsa

Криптосистема с открытым ключом (public key cryptosystem) (рис. 5.1), основанную на применении односторонних функций с секретом, можно реализовать следующим образом. Пользователь B, который хочет получать конфиденциальные сообщения, должен выбрать одностороннюю функцию EB с секретом (ключом) kB . Он сообщает всем заинтересованным описание своей функции зашифрования EB , например, публикует его в справочнике открытых ключей. При этом ключ kB , а, следовательно, и алгоритм расшифрования DB держатся в секрете. Если теперь пользователь A хочет послать B секретное сообщение m, то он находит в справочнике функцию EB , а затем вычисляет c = EB (m) и посылает шифротекст c по открытому каналу пользователю B. Последний, зная секрет kB , т.е. умея инвертировать EB , определяет m по полученному c, вычисляя m = DB (c). Противник, не зная ключа kB , в силу второго свойства односторонней функции с секретом не сможет прочитать секретную информацию. В отличие от криптосистемы с секретным ключом, если абонент A, зашифровав некоторое сообщение m для абонента B, сохранит шифротекст c, но потеряет m или забудет его содержание, он не будет иметь никаких преимуществ перед противником в раскрытии исходного текста m по известному c.

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

Шифрование с открытым ключом может использоваться в тех из рассмотренных в гл. 2 режимах, которые для зашифрования и расшифрования используют разные функции соответственно Ek и Dk (например, ECB и CBC, при этом, очевидно, что второй вариант предпочтительней).

Наиболее известные системы с открытым ключом:

• рюкзачная криптосистема (Knapsack Cryptosystem);

• криптосистема RSA;

• криптосистема Эль-Гамаля (ElGamal Cryptosystem);

• криптосистема, основанная на свойствах эллиптических кривых.(Elliptic Curve Cryptosystem (ECCS)).

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

Криптосистема RSA

Система RSA, название которой происходит от первых букв фамилий авторов – Р. Ривеста, А. Шамира и Л. Адлемана (R. Rivest, A. Shamir, L. Adleman), является наиболее распространенной и изученной криптосистемой с открытым ключом. Она основана на использовании того факта, что легко перемножить два больших простых числа, в то же время крайне трудно разложить на множители их произведение. В результате произведение может быть использовано в качестве элемента открытого ключа зашифрования. Исходные простые числа необходимы для расшифрования, при этом задача их восстановления до сих пор сопротивляется всем атакам криптоаналитиков. Таким образом, имеются хорошие предпосылки для построения односторонней функции с секретом.

• Открытый ключ зашифрования: числа n и e.

• Закрытый ключ расшифрования: числа p, q и d.

• Алгоритм зашифрования сообщения m: Ek (m) = m^e (mod n) = c

• Алгоритм расшифрования закрытого сообщения с: Dk (c) = c^d (mod n) = m

П римечание. Необходимым условием является уничтожение чисел p и q после вычисления ключей e и d. Единственный способ найти алгоритм расшифрования Dk при известных e и n состоит в том, чтобы разложить на простые множители число n, найти p и q, а, следовательно, и d. Правильный выбор разрядности чисел p и q (первоначально авторы RSA предлагали в качестве p и q использовать не менее чем 40-разрядные десятичные числа) делает задачу факторизации n практически неосуществимой. Пример шифрования по приведенной схеме показан на рис. 5.5.

Авторы RSA при описании принципов функционирования своей системы выбрали в качестве исходного текста фразу «ITS ALL GREEC TO ME» («Для меня все это совершенно непонятно»).

Для того чтобы преобразовать этот текст в одно большое число, закодировали пробел между словами 0, букву А – 1, букву В – 2, букву С – 3, ... , букву Z – 26. На представление каждого символа выделили пять двоичных разрядов. В результате приведенной фразе стало соответствовать число m = 09201900011212000718050511002015001305. Для шифрования авторы выбрали e = 9007 и n =

11438162575788886766923577997614661201021829672124236

25626518429357069352457338978305971235639587050589890

75147599290026879543541.

После зашифрования получили число c = m^e (modn) =

19993513149780510045231712274026064742320401705839146

31037037174062597160894892750439920962672582675012893

554461353823769748026.

Ч исло n было произведением 64-значного и 65-значного простых чисел p и q, выбранных случайным образом. Если исходный текст слишком велик, чтобы с ним можно было обращаться как с одним числом, то его следует разбить на блоки и каждый блок рассматривать как отдельное число, при этом необходимо использовать шифрование со сцеплением блоков (режим CBC). При разработке криптосистемы сначала выбираются два различных простых числа p и q. Для этого произвольно выбирается нечетное число r подходящего размера (например, сторазрядное) и проверяется на простоту. В случае, если тест дает отрицательный результат, проверяется число r + 2 и т.д. Существует приблизительно 100-разрядных простых чисел.

Учитывая, что всего существует (10¹⁰⁰ -10⁹⁹ )/ 2 100-разрядных нечетных чисел, вероятность успеха одного конкретного теста равна приблизительно 0,00868. После того как p и q выбраны, кандидаты на e проверяются с помощью алгоритма Евклида. Когда e удовлетворяет условию (e, фи(n)) =1, цепочка равенств, получаемых в результате применения алгоритма Евклида, дает нам и значение d. Процедура шифрования суть модульное возведе ние в степень, данную операцию следует осуществлять методом последовательного возведения в квадрат, т.е. после каждого возведения в квадрат результат берется по модулю r. При этом никогда не возникают числа большие n².