2. Дискретное логарифмирование в конечном простом поле (проблема Диффи-Хеллмана).

Допустим, задано большое простое число р и пусть g - примитивный элемент поля GF{p). Тогда для любого а вычислить g(mod р) просто, а вычислить а по заданным к = g(mod р) ир оказывается затруднительным.

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

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

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

3.3. Асимметричные системы шифрования 3.3.1. Криптосистема Эль-Гамаля

Система Эль-Гамаля - это криптосистема с открытым ключом, основанная на проблеме логарифма Система включает как алгоритм шифрования, так и алгоритм цифровой подписи.

Множество параметров системы включает простое число р и целое число g, степени которого по модулю р порождают боль-

шое число элементов Zp. У пользователя А есть секретный ключ а и открытый ключ у, где у = g" (mod р). Предположим, что пользователь В желает послать сообш,ение т пользователю А. Сначала В выбирает случайное число к, меньшее р. Затем он вычисляет

У1 = g (mod p)wy2m®{y" (mod p)),

где ® обозначает побитовое "исключаюш,ее ИЛИ". В посылает А пару (уь уг).

После получения шифрованного текста пользователь А вычисляет

т = {ух" modр) ® yj.

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

т = yjlyi" mod p.

Однако, схема Эль-Гамаля не лишена определенных недостатков. Среди них можно указать следуюш,ие:

1. Отсутствие семантической стойкости. Если g - примитивный элемент Zp, то за полиномиальное время можно определить, является ли некоторое число х квадратичным вычетом, или нет. Это делается возведением в степень х*" mod р. Если результат равен 1, то х - квадратичный вычет по модулю р, если -1, то X - квадратичный невычет. Далее пассивный противник проверяет, являются ли и g" квадратичными вычетами, g* будет квадратичным вычетом тогда и только тогда, когда и g*, и g" будут квадратичными вычетами. Если это так, то у2 = т-у mod р будет квадратичным вычетом, тогда и только тогда, когда само сообш,ение т будет квадратичным вычетом. То есть пассивный противник получает некоторую информацию об исходном тексте, имея лишь шифрованный текст и открытый ключ получателя.

2. Делимость шифра. Если дан шифрованный текст (уь уг), то мы можем получить другой шифрованный текст, изменив только вторую часть сообш,ения. В самом деле, умножив у2 на g" {и Ф 0), мы получим шифртекст для другого сообш,ения т= m-g".

Для заш,иты от подобных атак Шнорром и Якобссоном было предложено объединить схему шифрования Эль-Гамаля с цифровой подписью Шнорра, что позволяет не только шифровать сообш,ение, но и аутентифицировать его.

Зашифрование осуш,ествляется следуюш,им образом. Автор сообш,ения выбирает случайные к, s g Zg. далее от вычисляет g*" mod р, ту"" mod р,с h{g\ g, ту) mz = s + ск mod q. Шифрованный текст представляет собой четверку (g*", /иу*", с, z).

Получив сообш,ение (h,f,c,z), приемная сторона вначале верифицирует его, проверяя выполнение равенства h{gh~,h,f) = с . В случае успешной верификации открытый

текст получается по формуле т = f I mod p. Расшифрование

корректно, поскольку h = , f = my mod p, так что

flh = mgg~ mod p = m.

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

Указанными авторами было предложено обобш,ение данной схемы на случай, когда пространство сообш,ений М представляет собой произвольную аддитивную группу, например М = Ъ. Используются две статистически независимые хэш-функции Н: GxM и Нм: G М. В базовой схеме шифрования ту*" mod р заменяется на т + Нм(у) е М. Верификация шифрованного текста (/г,/, с, z) остается без изменений, а расшифрование

будет проводиться по формуле f - Нf{h).

3.3.2. Криптосистема, осповаппая па проблеме Диффи-

Хеллмапа

Данная система шифрования была представлена Мишелем Абдаллой, Михиром Беллэром и Филлипом Рогэвэем в рамках

европейского проекта NESSIE (New European Schemes for Signatures, Integrity and Encryption). Эта система столь же эффективна, что и система Эль-Гамаля, но обладает дополнительными свойствами безопасности. Более того, стойкость системы может быть доказана в предположении о стойкости лежаш,их в ее основе криптографических примитивов.

Данная криптосистема реализуема на основе любой циклической группы, для которой может быть сформулирована проблема Диффи-Хеллмана, например, в {Zp } или в группе точек на эллиптической кривой (см. 3.3.5).

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

Опишем криптографические примитивы, входяш,ие в схему.

Циклическая группа G= {g}. Мы будем использовать мультипликативную запись групповой операции. Алгоритмы, реали-зуюш,ие эту операцию, будут работать с представлениями элементов группы в виде битовых строк фиксированной длины gLen g TV. Способ кодирования G {О, 1}™ не фиксируется и может выбираться, например, из соображений эффективности.

Код аутентификации сообщения позволяет пользователям, обладаюш,им обш,им секретным ключом, выработать битовую строку для аутентификации и проверки целостности данных. Пусть Msg={0, 1} - пространство сообш,ений, тКеу = {О, 1}"™ - пространство ключей для вычисления MAC для некоторого тЬеп g TV, Tag = {О, 1 }™ - включаюш,ее множество всех возможных значений MAC для некоторого tLen g TV. В этих обозначениях код аутентификации сообш,ений представляет собой пару алгоритмов MAC = {MAC.gen, MAC.ver}. Алгоритм генерации MAC определяется как отображение

MAC.gen(A:, х): тКеу X Msg Tag

и может быть вероятностным.

Алгоритм верификации MAC является отображением

MAC.ver(A:, x, т): тКеу X Msg X Tag {0, 1}

CO свойством MAC.ver(A:, x, MAC.gen(A:, x)) = \.

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

Сгшметричный шифр позволяет пользователям, обладаю-ш,им обш,им секретным ключом, обеспечить секретность. Пусть Msg, как и ранее, пространство сообш,ений, еКеу= {О, 1}""" -пространство ключей для некоторого еЬеп g TV, Ctext = {О, 1} -включаюш,ее множество всех возможных значений шифрованного текста и Coins = {О, 1}°° - множество строк бесконечной длины. В этих обозначениях шифр представляет собой пару алгоритмов SYM = {SYM.enc, SYM.dec}. Алгоритм зашифрования определяется как отображение

SYM.enc(A:, х, г): еКеу X Msg X Coins Ctext

Алгоритм расшифрования является отображением

SYM.dec(, у): еКеу х Ctext Msg и {BAD},

где значение BAD выдается, если шифртекст у не является результатом зашифрования никакого открытого текста

Асимметричный шифр. Пусть Msg, Ctext, Coins определены как и ранее, РК с {О, 1}*, SK с {О, 1}* - множества открытых и секретных ключей. Асимметричный шифр определяется как тройка алгоритмов ASYM = {ASYM.enc, ASYM.dec, ASYM.key}. Алгоритм зашифрования является отображением

ASYM.enc(pA:, х, г): РК X Msg X Coins Ctext

а расшифрования:

ASYM.enc(s,>;): SK х Ctext Msg u {BAD}

Алгоритм выработ1си ключа в качестве аргумента берет строку г g Coins и выдает пару ключей (рк, sk) g РК х SK. При этом должно выполняться следуюш,ее свойство: V {рк, sk): 3 г g Coins: {рк, sk) = ASYM.key(r), V г g Coins V х g Msg ASYM.dec(s, ASYM.encCp, x, r)) = x.

Функция хэширования является отображением следуюш,его вида:

Н: {О, {О, 1)

mLen + eLen

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

Все ключевые пары в данном алгоритме выбираются так же, как и в криптосистеме Эль-Гамаля, т.е. пара {рк, sk) = (g", v) для некоторого случайного v. При отсылке сообш,ения выбирается некоторое случайное значение и и получателю отсылается g", что обеспечивает неявный обмен ключами по семе Диффи-Хеллмана. Таким образом, зашифрованное сообш,ение состоит из одноразового открытого ключа, текста, зашифрованного симметричным шифром, и кода аутентификации сообш,ения, выработанного с помош,ью алгоритма MAC .gen.

Процесс расшифрования и аутентификации графически представлен на рис. 3.2. Элементы принятого сообш,ения также выделены двойной рамкой.

Открытый ключ получателя

Вычисление секретного значения

ASYM.key

Общее секретное значение

тасКеу

Одноразовый открытый ключ

открытый текст 1

епсКеу

SYM.enc

II II

шифртекст

Рис. 3.2. Процесс зашифрования. Двойной рамкой выделены элементы зашифрованного сообш,ения.