Файл: Задача 1 Реализация сетевого протокола выработки секретного ключа Протокол ДиффиХеллмана (Diffie, Hellman).pdf

Перспективные технологии защиты информации
Задача № 1
Реализация сетевого протокола выработки секретного ключа
Протокол Диффи–Хеллмана (Diffie, Hellman)
Исходно DH-протокол описывался в рамках простого поля и его мультипликативной группы. Пусть
ℤ
????
– простое поле (p – простое число),
ℤ
????
∗
– его мультипликативная группа с генератором g (числа p и g несекретны и могут коллективно использоваться сообществом). Пользователи A и B выбирают секретные ключи соответственно
????, ???? ∈ ℤ
????
, вычисляют открытые ключи
???? = ????
????
, ???? = ????
????
и обмениваются открытыми ключами (по открытому каналу). Общий для A и B ключ вычисляется ими как
????
????
= ????
????
. (В
ℤ
????
все арифметические операции выполняются по модулю p).
По состоянию знаний на сегодняшний день предпочтительна реализация протокола, когда открытые ключи являются элементами не мультипликативной группы
ℤ
????
∗
, а циклической подгруппы G простого порядка q при
q
p . В этом случае в качестве g берется генератор такой подгруппы, секретные ключи
????, ???? ∈ ℤ
????
, все вычисления выполняются точно так же. Длины чисел, при которых обеспечивается долговременная стойкость по отношению к известным алгоритмам взлома, |
????| = 1024 бит, |????| = 160 бит (в США) или
256 бит (в РФ). Так как вычисленный общий ключ принадлежит G, но выражен числом длиной |
????| бит, его рекомендуется "сжать" до |????| бит с помощью криптографической хэш- функции H. То есть результирующий ключ вычисляется как
???? = ????(????
????
) = ????(????
????
). Хэш- функция также предотвращает манипуляцию битами ключа K путём неслучайного выбора чисел x и y.
Отметим, что подгруппа G может выбираться не только в рамках простого поля
ℤ
????
, но и в других алгебраических структурах, например, в бинарном поле
????
2
????
или в группе точек на эллиптической кривой.
Протокол MQV (Menezes, Qu, Vanstone)
Пусть опять в поле
ℤ
????
имеется циклическая подгруппа G простого порядка q с генератором g. Обозначим через l половину битовой длины числа q:
???? = |????|/2 .
Пользователи A и B генерируют долговременные пары секретных и открытых ключей соответственно a, A и b, B:
????, ???? ∈ ℤ
????
(выбираются случайным образом),
???? = ????
????
,
???? = ????
????
Открытые ключи пересылаются всем пользователям в виде сертифицированного
(подписанного удостоверяющим центром) справочника.
Для построения общего сеансового ключа пользователь A генерирует случайное число
???? ∈ ℤ
????
и вычисляет
???? = ????
????
. Пользователь B генерирует случайное число
???? ∈ ℤ
????
и вычисляет
???? = ????
????
. Затем пользователи обмениваются числами X и Y по открытому каналу связи. Оба пользователя вычисляют числа
???? = 2
????
+ (???? mod 2
????
) , ???? = 2
????
+
(???? mod 2
????
). Пользователь A вычисляет ????
A
= (????????
????
)
????+????????
. Пользователь B вычисляет
????
B
=
(????????
????
)
????+????????
(напомним, что при возведении в степень показатели приводятся mod q).
Результирующий ключ получается следующим образом:
???? = ????(????
A
) = ????(????
B
).

Перспективные технологии защиты информации
Поиск генераторов
Если требуется найти генератор мультипликативной группы, то рекомендуется брать
2 1
p
q


. В этом случае генератором будет любое число g, для которого выполняются условия
1 1
g
p
  
и mod
1
q
g
p  . Такое число быстро находится методом перебора.
Если же нужен генератор циклической подгруппы порядка q, то, наоборот, нужно найти такое число g, что mod
1
q
g
p  . В ситуации, когда
1
p tq
 
и число t очень большое, найти g методом перебора не получится. Нужно взять произвольное число
1
r 
и вычислить mod
t
g r
p

. Если
1
g 
, то это генератор. В противном случае нужно взять другое число r.
Измерение времени вычислений с помощью счетчика циклов процессора
Если используется компилятор GCC, необходимо подключить файл rdtsc.h. В этом файле определены две функции: unsigned long long rdtsc () возвращает полное (64 бита) текущее значение счетчика циклов процессора. unsigned int CC () возвращает младшее слово (32 бита) счетчика циклов процессора, что достаточно, если заранее известно, что измеряемое время не превышает
2 32
циклов процессора.
Задание
1. Самостоятельно изучить библиотеку GMP для реализации арифметики с длинными числами. Руководство и рекомендации по установке находятся в ЭИОС.
По желанию студента допускается использовать другие известные ему средства реализации арифметики с длинными числами.
2. Реализовать программу генерации чисел p, q, g для операций в мультипликативной группе
ℤ
????
∗
и в циклической подгруппе G порядка q.
Сгенерированные числа сохранить для последующего использования в файле.
3. Реализовать исходный алгоритм Диффи–Хеллмана, алгоритм Диффи–Хеллмана в подгруппе, алгоритм MQV. Пока без хэш-функций на последнем этапе.
4. Сделать сетевые версии программ, реализующие действия пользователей A и B на разных компьютерах локальной сети.
5. Осуществить замеры времени (в виде числа процессорных циклов) при выполнении основных этапов во всех алгоритмах и провести их сопоставление.