Алгоритм обмена секретным ключом Диффи-Хеллмана

 

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

1. Решение проблемы “человек посередине” с помощью ЭЦП

Для борьбы с уязвимостью  “человека посередине” нужна  взаимная аутентификация. И тут на помощь приходит ЭЦП.  
Если у Боба имеется открытый ключ Алисы, и он уверен на сто процентов, что это действительно ключ Алисы, то тогда для защиты от атаки «человек посередине» Алисе достаточно подписать своим закрытым ключом число на шаге 1. Теперь Меллори может сколько угодно пытаться выдать себя за Алису, но подделать ее подпись он не сможет, а Боба сразу начнут терзать «смутные сомненья».

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

Как видно из этой таблицы  размер сообщений увеличивается  в разы. Для решение этой новой проблемы был придуман протокол MQV, избавляющий Диффи-Хеллман от уязвимости и при этом не использующий ЭЦП.

2. Решение проблемы “человек посередине” протоколом MQV

Итак, протокол MQV – протокол распределения ключей, поддерживающий взаимную аутентификацию сторон и тем  самым устраняющий уязвимость к  атаке «человек посередине», присущей классическому Диффи-Хеллману. Помимо прочего, для аутентификации пользователей  не используется никакая вспомогательная  информация, наподобие ЭЦП, что позволяет  существенно сократить размер передаваемых сообщений. 

 

Теперь о самом протоколе. 
Алиса и Боб имеют каждый свою ключевую пару, состоящие из открытых и закрытых ключей:   и . Разумеется, Бобу известен открытый ключ Алисы, а той в свою очередь известен открытый ключ Боба. 
Далее, Алиса и Боб генерируют сеансовую пару ключей:   и  . 
Затем происходит обмен как в классическом протоколе Диффи-Хеллмана: 
Алиса к Бобу:   
Боб к Алисе:   
Теперь Алиса знает: A, B, C, D, a,  . 
А Бобу известны: A, B, C, D, b,  . 
Чтобы получить общий ключ K они должны проделать следующие операции. 
 
Алиса: 
   Выбирает число l, равное размеру сообщения в битах деленному на 2. Так если используется EC-MQV и длина сообщения равна 160 бит, то l=80. 
1. Задает   
2. Находит   
3. Задает   
4. Вычисляет   
5. Находит   
6. Вычисляет   
Боб проделывает те же действия, но со своими закрытыми ключами: 
1. Задает   
2. Находит   
3. Задает   
4. Вычисляет   
5. Находит   
6. Вычисляет   
   Получившиеся в результате вычислений числа   и есть общий секретный ключ. Убедимся в этом: 
, т.к.   и  ; 
, т.к.  ; 
, т.к.   и  ; 
, т.к.  ; 
. 
   Обратите внимание, что в преобразованиях используются секретные ключи как Алисы, так и Боба. Т.е. любой пользователь протокола может быть уверен, что кроме того человека, с которым он хочет установить соединение, получить общий ключ не удастся никому. 

 
    Несмотря на кажущуюся сложность, в скорости протокол MQV ничего не теряет по сравнению со схемой использующей ЭЦП, ведь и там и там используется одна и та же операция возведения в степень по модулю простого числа. Выгода же от использования протокола заключается в следующем. Это, во-первых, устойчивость к атаке «человек посередине», во-вторых, небольшой размер сообщений, а, в-третьих, удобная реализация протокола, избавляющая пользователя от необходимости подписывать каждое отправляемое сообщение.

 

ЗАКЛЮЧЕНИЕ

В ходе  курсовой работы был изучен и проанализирован  алгоритм обмена ключами Диффи - Хеллмана, были рассмотрены основные недостатки этого алгоритма и предложены варианты защиты от атак “человек посередине”, такие как:

• Электронная цифровая подпись;
• Протокол MQV (Менезес-Кью-Ванстоун);

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

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

У программного продукта есть недостатки:

 

• В программном продукте нереализована полная очистка оперативной памяти.
• Секретные ключи хранятся в открытом виде на диске.
• Возможна модификация ключей.
• Не реализована аппаратная система.

 

 

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Коблиц Н. Курс теории чисел и  криптографии – Москва: Научное издательство ТВП, 2001. -254с
2. Завгородний В. И. Комплексная защита информации в  компьютерных системах – Москва: Логос, 2001 г. -264 с.
3. http://e-maxx.ru/algo/primitive_root (Статья)
4. http://ru.wikipedia.org/wiki/Алгоритм_Диффи_—_Хеллмана (Энциклопедия)
5. http://www.intuit.ru/department/security/networksec/7/3.html (Лекция)
6. http://ru.wikipedia.org/wiki/Тест_Миллера_—_Рабина (Энциклопедия)
7. http://www.shoup.net/ntl/doc/ZZ.txt  (Описание класса ZZ)

 

 

ПРИЛОЖЕНИЕ

{ZZ g; ZZ p;} DH_OpenKey;

 

/* Закрытый ключ*//* Открытые параметры */

typedef

typedef ZZ DH_PrivateKey;

 

/* Путь к открытому ключу абонента A и абонента B соответственно */

char A = ”D:\\opka.txt”, B = “D:\\opkb.txt”; 

 

/* Количество бит при генерации чисел: */

long Length = 256;

 

/* Возведение числа a в степень b по модулю p.

   x  =a^b (mod p)

   Скорость вычисление достигается за счет следующих замен (в

   зависимости от четности/нечетности  степени b):

1. b четное (b = 2*k):

      a^(2*k) (mod p) = (a^2 (mod p))^k

2. b нечетное (b = 2*k+1):

     a^(2*k+1) (mod p) = (a*b) (mod p)

*/

ZZ PowMod(const ZZ &a, const ZZ &b, const ZZ &p)

{

ZZ x;

     x = to_ZZ(1);

for (long BitNum = NumBits(b) - 1; BitNum>= 0; BitNum--)

{

x = (x * x) % p;

if (bit(b, BitNum) == 1) x = (x * a) % p;

}

return x;

}

 

/*Функция,  проверяющая является ли число  a свидетелем простоты для 

  числа p:

  1) Представляем p-1 в виде (2^s)*t. t - нечетное

  2) x = a^t (mod p)

  3) Если x = 1 или x = p - 1, то a - свидетель простоты для числа p.

     Завершаем выполнение функции.

  4) Повторяем s - 1 раз

  5) x = x^2 (mod p)

  6) Если x = p - 1, то a - свидетель простоты для числа p. Завершаем

     выполнение функции.     

  7) a - не является свидетелем простоты для числа p.Завершаем

выполнение функции.

*/

bool PrmWtnss(const ZZ &p, const ZZ &a)

{

ZZ t;

      T = p - 1, y, x;

longs = 0;

 

// Разложение p - 1 многократным делением на 2

do

{

t >>= 1;

s++;

}while (bit(t, 0) == 0);

 

x = PowMod(a, t, p);

 

if (x == 1 || x == p - 1) return true;

 

for(long i = 0; i< s - 1; i++)

{

x = (x * x) % p;

if(x == p - 1) return true;

}

Return false;

}

 

/* Тест Миллера-Рабина на простоту:

   1) В дальнейшем будем повторять 31 раз (rounds = 31)

   2) Выберем случайное число a в отрезке [2, p − 2]

   3) Проверим является ли a свидетелем простоты для числа p.

   4) Если все a являются свидетелями простоты, то число p вероятно

      простое

*/

bool MillerRabinTest(const ZZ &p, long rounds)

{

ZZ a;

     Long i;

for (i = 0; i< rounds; i++)

{

a = RandomBnd(p-3) + 2;

if (PrmWtnss(p, a) == false) return false;

}

Return true;

}

 

/*Тест  числа на простоту делением  его на простые числа до 256

  Этот тест исключает все четные числа и 80%

  нечетных

*/

bool TestDiv(const ZZ &p)

{

unsigned int i,  prost[55]={2,3,4,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,

61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,

151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,

239,241,251};

for(i = 0; i< 55; i++)

if(p % prost[i] == 0) return p == prost[i];

return true;

}

 

/*Общий  тест числа на простоту включающий  в себя оба предыдущих теста 

  (тест Миллера-Рабина и тест  делением).

*/

bool TestProst(const ZZ &p)

{

return (TestDiv(p) && MillerRabinTest(p, 31));

}

 

/* Генерация случайного простого числа:

1. Генерируем число разрядностью SizeBits
2. Делаем его нечетным (т.к. четное неможет быть простым)
3. Проверяем его, является ли оно простым. Если число простое, то функция возвращает это число. Если число не является простым, то мы проверяем на простоту последовательно, каждое предыдущее нечетное число, пока не получим простое.

*/

ZZ RandomProst(long SizeBits)

{

 

ZZ a;

     a = RandomLen_ZZ(SizeBits);

SetBit(a, 0);

while(!TestProst(a)) a -= 2;

return a;

}

 

/* Функция находит первообразный корень по простому модулю p */

ZZ generator (ZZ &p) {

vector<ZZ> fact;

ZZ phi = p-1,  n = phi, i, res;

for (i=2; i*i<=n; ++i)

if (n % i == 0) {

fact.push_back (i);

while (n % i == 0)

n /= i;

}

if (n > 1)

fact.push_back (n); 

 

for (res=2; res<=p; ++res) {

bool ok = true;

for (size_t i=0; i<fact.size() && ok; ++i)

ok &= PowMod (res, phi / fact[i], p) != 1;

if (ok)  return res;

}

return -1;

}

 

/* Генерация открытых параметров */

void DH_GenerateParam (DH_OpenKey &OpenKey, long Length)

{ OpenKey.p = RandomProst(Length);

  OpenKey.g = generator (OpenKey.p);

}

 

/* Генерация закрытого ключа */

void DH_GenerateKey (DH_PrivateKey &PrivateKey, long Length)

{

  PrivateKey = RandomProst (Length);

}

 

 

/* Вычисление открытого ключа: */

ZZ CalculateOpenKey(DH_OpenKey &OpenKey, DH_PrivateKey &PrivateKey)

{

return(PowMod(OpenKey.g, PrivateKey, OpenKey.p);

 

 

/* Передача открытых параметров: */

void DH_SendOpPar (DH_OpenKey &OpenKey)

{ ofstream fg (D:\\parg.txt, ios::out),

           fp (D:\\parp.txt, ios::out);

 

  fg << OpenKey.g;

  fp << OpenKey.p;

}

/* Передача открытого ключа от абонента Person: */

void DH_SendOpKey(DH_OpenKey &OpenKey, DH_PrivateKey &PrivateKey, char Person)

{ ofstream opk (Person, ios::out);

 

  opk << CalculateOpenKey(OpenKey, PrivateKey);

}

 

/* Получение абонентом открытых параметров: */

DH_OpenKey DH_ReceiveOpPar ()

{ DH_OpenKey OpenKey;

  ifstream fg (D:\\parg.txt, ios::in),

           fp (D:\\parp.txt,ios::in);

  fg >> OpenKey.g;

  fp >> OpenKey.p;

return (OpenKey);

}

 

/* Получение открытого ключа от абонента Person: */

ZZ DH_ReceiveOpKey (char Person)

{ DH_PrivateKey PrivateKey;

  ifstream opk (Person,ios::in);

  opk >> PrivateKey;

  return (PrivateKey);

}

 

/* Вычисление для абонента A общего ключа K: */ 

void DH_forA()

{ //Инициализация переменных:

  DH_OpenKey par;

  DH_PrivateKey a1,K;

  char c;

 

  // Генерация переменных:

  DH_GenerateParam (par, Length);

  DH_GenerateKey (a1, Length/2);

  // Передача открытых параметров  и открытого ключа абоненту  B:

  DH_SendOpPar (par);

  DH_SendOpKey (par, a1, A);

  //Ожидание обработки абонентом B:

  scanf(“%c”, &c);

  // Вычисление общего ключа K:

  K = PowMod (DH_ReceiveOpKey (B), a1, par.p);

}

 

/* Вычисление для абонента B общего ключа K: */

Void DH_forB()

{ // Инициализация переменных:

  DH_OpenKey par2;

  DH_PrivateKeay b2, K;

  char c2;

 

  // Генерация переменных:

  DH_GenerateKey (b1,Length/2);

  // Ожидание обработки абонентом A:

  scanf (“%c”, &c2);

  // Получение открытых параметров от абонента A:

  par2 = DH_ReceiveOpPar ();

  // Передача открытого ключа абоненту  A:

  DH_SendOpKey (par2, b2, B);

  // Вычисление  общего ключа K:

  K = PowMod(DH_ReceiveOpKey (A), b2, par2.p);

}

Могилёв, 2012