Современная прикладная криптография (стр. 40 )

Классический протокол Диффи - Хеллмана можно адаптировать применительно к группе точек эллиптической кривой следующим образом. Прежде всего заметим, что в качестве ключа классической криптосистемы можно использовать случайную точку (x, у) эллиптической кривой, если А и Б условятся, как конвертировать ее в натуральное число. Например, для этого можно взять одну из её координат, например, х и отобразить ее определенным образом, условившись об использовании некоторого отображения из Fp во множество натуральных чисел.

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

Допустим, что Е - эллиптическая кривая и Q - предварительно согласованная и опубликованная точка этой кривой. А выбирает, сохраняя в секрете, случайное число кa, вычисляет координаты точки kAQ и пересылает их Б. Аналогично Б выбирает кв, вычисляет и пересылает А kbQ - Общим ключом является точка Р = кaквО,- А вычисляет ее умножая на свой секретный ключ кa сообщение, поступившее от Б, а Б вычисляет ее, умножая сообщение, поступившее от А на свой секретный ключ кв - Ввиду того, что группа точек эллиптической кривой абелева, результат не зависит от порядка вычисления и, следовательно, А и Б имеют одинаковые точки:

кa{квQ) = kB(kAQ) = kAkBQ.

Теперь А и Б имеют одинаковые копии искомой секретной точки эллиптической кривой.

Проблема, стоящая перед посторонним наблюдателем, имеющим намерение узнать секретный ключ, заключается в вычислении кaкв по известным Q, kaQ-, kbQ, но при неизвестных кa, кв-Она называется проблемой Диффи-Хеллмана для эллиптических кривых.

Проблема дискретного логарифма для эллиптических кривых заключается в вычислении числа х, такого, что Р = xQ, где Р и Q - известные точки заданной эллиптической кривой. Ясно, что если эта проблема имеет эффективное решение, то и проблема Диффи-Хеллмана для эллиптических также легко решаема, и рассмотренный протокол не имеет смысла. В то же время гипотеза об эквивалентности проблем дискретного логарифма и проблемы Диффи-Хеллмана для эллиптических кривых не доказана.

ECMQV: Elliptic Curve Menezes-Qu-Vanstone

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

Действительно, если А и Б взаимодействуют, например, по протоколу Диффи-Хеллмана, то К, перехватив передачу открытого ключа кaP А, передаст Б свой открытый ключ ксР, Б передаст ей свой открытый ключ квР, после чего Б и К будут иметь общий закрытый ключ кckbР - Далее Если К передаст свой открытый ключ также А, то К и А будут иметь общий секретный ключ кaксР (он может отличаться от ключа Кэтрин и Боба).

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

Для предотвращения таких действий активного криптоаналитика (его еще называют man - in_ the middle) необходима аутентификация (авторизация) этих кратковременных ключей кaР и квР (ключей одноразового использования), для чего используются публикуемые долговременные ключи daP и dвР (ключи многоразового использования). При этом протокол организуется таким образом, что кратковременный открытый ключ функционально связывается с долговременным и поэтому третье лицо, не сможет стать посредником коммуникаций между двумя абонентами. Более точно, для успеха ему необходимо вмешаться в процессы передачи как долговременных, так и кратковременных ключей и более того воспрепятствовать возможности А и Б проверить правильность передачи долговременных ключей (на это у этих абонентов найдется время: долговременные ключи передаются редко).

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

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

В обоих случаях используется двоякая трактовка координат точек эллиптической кривой –

1) как элементов расширения поля, над которым строится кривая,

2) как кодов целых чисел.

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

Во всех случаях А и Б располагают точкой Р эллиптической кривой порядка n, над которой и осуществляются все вычисления. Кроме того они знают долговременные и кратковременные ключи друг друга: ключи Б

QB = dBP = (aB, bB),

RB = kBP = (хв, Ув)

известны А, а её ключи

QA = dAP = {аА, bА),

RA = kAP = (хА, уА)

известны Б.

Рассмотрим описание и обоснование протокола с использованием модульной арифметики.

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

На первом этапе А и Б вычисляют числа

$А = кА + xaaadA (mod n),

(sB = кв + xBaBdB (mod n)),

(при этом они используют свои секретные данные /с^, dA и кв, ds соответственно.)

На втором этапе они вычисляют точки эллиптической кривой

UА = RB + XBaBQB,

Uв = RA + XAaAQA-

На третьем этапе А и Б вычисляют точку эллиптической кривой

W = sAUA,

W = sBUB.

Одно и то же обозначение здесь выбрано не случайно, так как результаты вычислений совпадут:

sAUA = SBUB.

Действительно, в соответствии с использованными обозначениями, получим

sAUA = (кА + xAaAdA (mod n))( RB + XBaBQB) =

(кА + xaaadA (mod n))( кв + xBaBdB) = (кА + xaaadA (mod n))( кв + xBaBdB)Р =

(кА + xaaadA)( кв + xBaBdB) (mod n)P.

Аналогично получим для Б.

Как видим, в рассмотренной интерпретации протокола модульная числовая арифметика сочетается с арифметикой эллиптической кривой.

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

Заметим, что А может вычислить точку Ua эллиптической кривой, выполнив умножение точки QB на константу ав, и умножив затем результат на константу хв и, наконец, сложив полученную точку с точкой RB. Аналогичным образом Б может получить точку UB.

Для получения точки W А и Б, имея в виду, что надо умножить полученные точки на константы зд и зв могут проделать это по следующему алгоритму (описываются действия А):

1) Вычислить kaUa (умножая точку эллиптической кривой на

константу),

2) Вычислить xa{aa{(daUa)) (последовательно умножая точку

UА на константу da, затем результат - на константу aa и полу

ченную точку - на константу xa),

3) Сложить две точки эллиптической кривой, полученные в п. п.

1)и2).

Действия Б аналогичны.

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

Шифрование с использованием эллиптических кривых

ECIES

Интегрированная схема шифрования на основе эллиптических кривых (The Elliptic Curve Integrated Encryption Scheme (ECIES)) была предложена Белларом и Рогэвеем как модифицированный вариант схемы шифрования Эль-Гамаля с открытым ключом. Данная схема стандартизована в ANSI X9.63 и ISO/IEC 15946-3, а также в черновом стандарте IEEE P1363a.

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

1. KDF (key derivation function) – функция выработки ключа, которая получается с помощью хэш-функции H. Если необходим ключ длиной бит тогда KDF(S) определена как конкатенация хэш-значений H(S, i), где i – счётчик, инкрементирующийся после каждого вычисления хэш-функции до тех пор пока не сгенерированы все бит хэш-значений.

2. ENC – функция шифрования для схемы шифрования с симметричным ключом, такой как, например, AES. DEC – это функция расшифрования.

3. MAC – алгоритм кода аутентификации сообщения, например, HMAC

ECIES зашифрование

Входные данные: открытый ключ Q, открытый текст M.

Выходные данные: шифртекст

1.  Выбираем

2.  Вычисляем и . Если , то переходим к шагу 1

3.  , где - x-координата Z

4.  Вычисляем и