Курс лекций «Проблемы безопасности в информационных технологиях»



жүктеу 4.51 Mb.
бет12/44
Дата13.09.2017
өлшемі4.51 Mb.
түріКурс лекций
1   ...   8   9   10   11   12   13   14   15   ...   44

Криптоанализ


Если процесс шифрования описать в виде Y = EK[X], где X – исходное сообщение, K – криптографический ключ, то процесс выявления X и/или K называется криптоанализом. Самая простая атака на алгоритм шифрования – это полный перебор всех возможных ключей (brute force, метод «грубой силы»). Если ключ имеет достаточную длину, время перебора становится нереально большим. При длине ключа n количество возможных ключей представляет число 2n, т.е. время перебора в общем случае растёт экспоненциально от длины ключа.

Существуют различные типы атак, основанные на том, что противнику известно определенное количество пар незашифрованное сообщение – зашифрованное сообщение. При анализе зашифрованного текста часто применяется статистические методы анализа текста. При этом противник может иметь общее представление о типе текста, например, английский это или русский текст, выполнимый файл конкретной ОС, исходный текст на некотором конкретном языке программирования и т.д. Во многих случаях криптоаналитик имеет достаточно много информации об исходном тексте. Криптоаналитик может иметь возможность перехвата одного или нескольких незашифрованных сообщений вместе с их зашифрованным видом. Или криптоаналитик может знать основной формат или основные характеристики сообщения. Говорят, что криптографическая схема абсолютно безопасна, если зашифрованное сообщение не содержит никакой информации об исходном сообщении. Говорят, что криптографическая схема вычислительно безопасна, если:




  • Цена расшифровки сообщения больше цены самого сообщения (об этом уже говорилось выше).

  • Время, необходимое для расшифровки сообщения, больше срока жизни сообщения.

Дифференциальный и линейный криптоанализ


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

Понятие дифференциального криптоанализа было введено Эли Бихамом (Biham) и Ади Шамиром (Shamir) в 1990 году. Конечная задача дифференциального криптоанализа – используя свойства алгоритма, в основном свойства S-box, определить подключ раунда. Конкретный способ дифференциального криптоанализа зависит от рассматриваемого алгоритма шифрования.

Если в основе алгоритма лежит сеть Фейстеля, то можно считать, что блок m состоит из двух половин - m0 и m1. Дифференциальный криптоанализ рассматривает отличия, которые происходят в каждой половине при шифровании. (Для алгоритма DES «отличия» определяются с помощью операции XOR, для других алгоритмов возможен иной способ). Выбирается пара незашифрованных текстов с фиксированным отличием. Затем анализируются отличия, получившиеся после шифрования одним раундом алгоритма, и определяются вероятности различных ключей. Если для многих пар входных значений, имеющих одно и то же отличие Х, при использовании одного и того же подключа одинаковыми (Y) оказываются и отличия соответствующих выходных значений, то можно говорить, что Х влечет Y с определенной вероятностью. Если эта вероятность близка к единице, то можно считать, что подключ раунда найден с данной вероятностью. Так как раунды алгоритма независимы, вероятности определения подключа каждого раунда следует перемножать. Считается, что результат шифрования данной пары известен. Результаты дифференциального криптоанализа используются как при разработке конкретных S-box, так и при определении оптимального числа раундов.

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


P[1], … , P[n] - незашифрованный блок сообщения.

C[1], … , C[n] - зашифрованный блок сообщения.

K[1], … , K[m] - ключ.

A[i, j, …, k] = A[i] A[j] … A[k]


Целью линейного криптоанализа является поиск линейного уравнения вида

P[α1, α2, …, αa] C[β1, β2, …, βb] = K[γ1, …, γc]

выполняющееся с вероятностью р 0.5. αi, βi и γi – фиксированные позиции в блоках сообщения и ключе. Чем больше р отклоняется от 0.5, тем более подходящим считается уравнение.

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

Уравнения составляются следующим образом. Вычисляются значения левой части для большого числа пар соответствующих фрагментов незашифрованного и зашифрованного блоков. Если результат оказывается равен нулю более чем в половине случаев, то полагают, что K[γ1, …, γс] = 0. Если в большинстве случаев получается 1, полагают, что K[γ1, …, γс] = 1. Таким образом получают систему уравнений, решением которой является ключ.

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


Криптография с открытым ключом


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

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

Открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу и используется для проверки ЭЦП и для шифрования сообщения. Для генерации ЭЦП и для расшифровки сообщения используется секретный ключ (связанный с открытым ключом). Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS/SSL (лежащих в основе HTTPS), в SSH. Также они используется в PGP, S/MIME.

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

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

Все участники информационного обмена имеют доступ к открытым ключам друг друга.

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

Диффи и Хеллман описывают требования, которым должен удовлетворять алгоритм шифрования с открытым ключом:




  • Вычислительно легко создавать пару (открытый ключ KU, закрытый ключ KR).

  • Вычислительно легко, имея открытый ключ и незашифрованное сообщение М, создать соответствующее зашифрованное сообщение:

С = ЕKU[М]



  • Вычислительно легко дешифровать сообщение, используя закрытый ключ:

М = DKR[C] = DKR[EKU[M]]




  • Вычислительно невозможно, зная открытый ключ KU, определить закрытый ключ KR.

  • Вычислительно невозможно, зная открытый ключ KU и зашифрованное сообщение C, восстановить исходное сообщение М.

Можно добавить шестое требование, хотя оно не выполняется для всех алгоритмов с открытым ключом:




  • Шифрующие и дешифрующие функции могут применяться в любом порядке:

М = ЕKU[DKR[M]]


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

Но сама односторонняя функция бесполезна в применении: ею можно зашифровать сообщение, но расшифровать нельзя. Поэтому криптография с открытым ключом использует односторонние функции с лазейкой (люком). Лазейка — это некий секрет (дополнительная информация), который помогает расшифровать. То есть существует такой k, что зная f(x) и k, можно вычислить x. При наличии этой дополнительной информации инверсию можно вычислить за полиномиальное время:


y = f k(x) – легко, если k и x известны

x = f(y) – легко, если k и y известны

x = f(y) – вычислительно трудно, если y известно, но k неизвестно.
Также как и симметричные алгоритмы, шифрование с открытым ключом подвержено атаке полного перебора (лобовая атака, brute force). Рецепт противодействия такой же: использование длинных ключей.

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

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

Схема шифрования с открытым ключом выглядит следующим образом:





Рис.18 Шифрование с открытым ключом


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

  2. Чтобы послать сообщение m Бобу, Алиса применяет одностороннюю функцию шифрования, определённую открытым ключом e: Ee(m)=c, где c — полученный шифротекст.

  3. Боб расшифровывает шифротекст c, применяя обратное преобразование Dd, однозначно определённое значением d (люк, лазейка).

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

Схема создания и проверки электронной подписи работает так:




Рис.19 Использование электронной подписи


  1. Пользователь Алиса создает пару (e,d), используемых для создания и проверки подписи передаваемых сообщений.

  2. Пользователь Алиса делает доступным некоторым надежным способом свой ключ проверки, т.е. открытый ключ e. Составляющий пару закрытый ключ d держится в секрете.

  3. Если Алиса хочет послать подписанное сообщение пользователю Боб, она создает подпись Ed(m) для этого сообщения, используя свой закрытый ключ d.

  4. Когда Боб получает подписанное сообщение, он проверяет подпись De(m), используя открытый ключ Алисы e. Никто другой не может подписать сообщение, так как этот закрытый ключ знает только Алиса.

Если пользователь (конечная система) надежно хранит свой закрытый ключ, их подписи достоверны. Невозможно изменить сообщение, не имея доступа к закрытому ключу Алисы, т.е., обеспечивается аутентификация и целостность передаваемых данных. Процесс создания ЭЦП не обеспечивает конфиденциальности сообщений.

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

Некоторые алгоритмы допускают использование во всех трёх вариантах, некоторые – только в двух или одном. Ниже приведена таблица для некоторых распространённых алгоритмов с открытым ключом и возможные способы их применения:




Алгоритм

Шифрование / расшифрование

Цифровая подпись

Обмен ключей

RSA

Да; непригоден для больших блоков

Да

Да

DSS

Нет

Да

Нет

Диффи-Хеллман

Нет

Нет

Да

Эллиптические кривые

Да

Да

Да

Может сложиться впечатление, что криптосистема с открытым ключом – идеальная система, не требующая безопасного канала для передачи ключа шифрования. Это подразумевало бы, что два легальных пользователя могли бы общаться по открытому каналу, не встречаясь, чтобы обменяться ключами. К сожалению, это не так. Рисунок ниже иллюстрирует, как Ева (злоумышленник), выполняющая роль активного перехватчика, может захватить систему (расшифровать сообщение, предназначенное Бобу) без взлома системы шифрования.




Рис.20 Перехват обмена ключами
В этой модели Ева перехватывает открытый ключ e, который Боб послал Алисе. Затем создает пару ключей e' и d', «маскируется» под Боба, посылая Алисе открытый ключ e', который, как думает Алиса, открытый ключ, присланный ей Бобом. Ева перехватывает зашифрованные сообщения от Алисы к Бобу, расшифровывает их с помощью секретного ключа d', заново зашифровывает открытым ключом e Боба и отправляет сообщение Бобу. Таким образом, никто из участников не догадывается, что есть третье лицо, которое может как просто перехватить сообщение m, так и подменить его на ложное сообщение m'. Это так называемая атака man-in-the-middle («человек посередине»). Такого рода угрозы обосновывают необходимость аутентификации открытых ключей. Для этого обычно используют сертификаты. Распределённое управление ключами в PGP решает возникшую проблему с помощью поручителей.

Большинство криптосистем с открытым ключом основаны на проблеме факторизации больших чисел. К примеру, RSA использует в качестве открытого ключа n произведение двух больших чисел. Сложность взлома такого алгоритма состоит в трудности разложения числа n на множители. Но эту задачу решить реально. И с каждым годом процесс разложения становится все быстрее. Ниже приведены данные разложения на множители с помощью алгоритма «Квадратичное решето».




Год

Число десятичных разрядов
в разложенном числе


Во сколько раз сложнее разложить
на множители 512-битовое число


1983

71

> 20 млн.

1985

80

> 2 млн.

1988

90

250 тыс.

1989

100

30 тыс.

1993

120

500

1994

129

100

Для многих методов несимметричного шифрования криптостойкость, полученная в результате криптоанализа, существенно отличается от величин, заявляемых разработчиками алгоритмов на основании теоретических оценок. Поэтому во многих странах вопрос применения алгоритмов шифрования данных находится в поле законодательного регулирования. В частности, в России к использованию в государственных и коммерческих организациях разрешены только те программные средства шифрования данных, которые прошли государственную сертификацию в административных органах, в частности, в ФСБ, ФСТЭК.


Алгоритм RSA


RSA (аббревиатура от фамилий Rivest, Shamir и Adleman) – криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел. Алгоритм был разработан в 1977 году под впечатлением от статьи Уитфилда Диффи и Мартина Хеллмана «Новые направления в криптографии» (New Directions in Cryptography) и был опубликован в 1978 году. С тех пор алгоритм RSA широко применяется практически в очень многих приложениях, использующих криптографию с открытым ключом.

Криптосистема RSA стала первой системой, пригодной и для шифрования, и для цифровой подписи. Алгоритм используется в большом числе криптографических приложений, включая PGP, S/MIME, TLS/SSL, IPSEC/IKE и других.

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

В криптографической системе с открытым ключом каждый участник располагает как открытым ключом (public), так и закрытым ключом (private). В криптографической системе RSA каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и закрытый ключ самостоятельно. Закрытый ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно и/или публиковать их. Открытый и закрытый ключи каждого участника обмена сообщениями в криптосистеме RSA образуют «согласованную пару» в том смысле, что они являются взаимно обратными, то есть:


сообщения m M, где M — множество допустимых сообщений.

допустимых открытого и закрытого ключей P и S

соответствующие функции шифрования Ep(x) и расшифрования Ds(x), такие что
m=Ds(Ep(m))

m=Dp(Es(m))


RSA-ключи генерируются по следующему алгоритму:


  1. Выбираются два различных случайных простых числа p и q заданного размера (например, 1024 бита каждое).

  2. Вычисляется их произведение n = pq, которое называется модулем.

  3. Вычисляется значение функции Эйлера от числа n:

φ(n) = (p-1)(q-1)




  1. Выбирается целое число e (1 < e < φ(n)), взаимно простое3 со значением функции φ(n). Обычно в качестве e берут простые числа, содержащие небольшое количество единичных бит в двоичной записи, например, простые числа Ферма4 17, 257 или 65537.

° Число e называется открытой экспонентой (public exponent)

° Время, необходимое для шифрования с использованием быстрого возведения в степень, пропорционально числу единичных бит в e.

° Слишком малые значения e, например 3, потенциально могут ослабить безопасность схемы RSA.


  1. Вычисляется число d, мультипликативно обратное к числу e по модулю φ(n), то есть число, удовлетворяющее условию:

de 1 mod φ(n)


° Число d называется секретной экспонентой. Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.

  1. Пара {e, n} публикуется в качестве открытого ключа RSA (public key).

  2. Пара {d, n} играет роль закрытого ключа RSA (private key) и держится в секрете.

Процедура шифрования и расшифрования с конкретными примерами приведена ниже. Предположим, Боб хочет послать Алисе сообщение m. Сообщениями являются целые числа в интервале от 0 до n-1, т.е. m Zn.





Рис.21 RSA – шифрование/расшифрование


º Взять открытый ключ (e,n) Алисы

º Принять зашифрованное сообщение C

º Взять открытый текст m

º Взять свой закрытый ключ (d,n)

º Зашифровать сообщение с использованием открытого ключа Алисы:

c = E(m) = me mod n (1)



º Применить закрытый ключ для расшифрования сообщения:

m = D(c) = cd mod n (2)


Уравнения (1) и (2), на которых основана схема RSA, определяют взаимно обратные преобразования множества Zn.


Пример работы шифрования/расшифрования:


Этап

Описание операции

Результат операции

Генерация ключей

Выбрать два простых числа

p = 3557, q = 2579

Вычислить модуль

n = p · q =3557 · 2579 = 9173503


Вычислить функцию Эйлера

φ(n) = (p-1)(q-1) = 9167368


Выбрать открытую экспоненту

e = 3

Вычислить секретную экспоненту

d = e-1 mod φ(n)

d = 6111579




Опубликовать открытый ключ

{e,n} = {3,9173503}


Сохранить закрытый ключ

{d,n} = {6111579,9173503}


Шифрование

Выбрать текст для зашифровки

m = 111111


Вычислить шифротекст

c = E(m) = me mod n = 1111113 mod 9173503 = 4051753

Расшифрование

Вычислить исходное сообщение

m = D(c) = cd mod n = 40517536111579 mod 9173503 = 111111

Алгоритм RSA может использоваться не только для шифрования, но и для цифровой подписи. Предположим, что Алисе (стороне A) нужно отправить Бобу (стороне B) сообщение m, подтверждённое электронной цифровой подписью.





Рис.22 RSA – цифровая подпись


º Взять открытый текст m

º Принять пару {m, s}

º Создать цифровую подпись Sc помощью своего закрытого ключа {d, n}:

s = Sa(m) = md mod n



º Взять открытый ключ {e, n}Алисы

º Передать пару {m, s}, состоящую из сообщения и подписи.

º Вычислить прообраз сообщения из подписи:

m´ = PA(s) = se mod n






º Проверить подлинность подписи (и неизменность сообщения), сравнив m и m´

Скорость работы алгоритма RSA: поскольку генерация ключей происходит значительно реже операций, реализующих шифрование, расшифрование, а также создание и проверку цифровой подписи, задача вычисления a = bc mod n представляет основную вычислительную сложность. Эта задача может быть разрешена с помощью алгоритма быстрого возведения в степень. Время выполнения операций растёт с увеличением количества ненулевых битов в двоичном представлении открытой экспоненты e. Чтобы увеличить скорость шифрования, значение e часто выбирают равным 17, 257 или 65537 — простым числам, двоичное представление которых содержит лишь две единицы: 1710=100012, 25710=1000000012, 6553710=100000000000000012 (простые числа Ферма).

По эвристическим оценкам длина секретной экспоненты d, нетривиальным образом зависящей от открытой экспоненты e и модуля n, с большой вероятностью близка к длине n. Поэтому расшифрование данных идёт медленнее, чем шифрование, а проверка подписи быстрее, чем её создание.

Алгоритм RSA работает намного медленнее, чем AES и другие алгоритмы блочного шифрования.

На 2009 год система шифрования на основе RSA считается надёжной, начиная с размера n в 1024 бита, но от шифрования ключом длиной в 1024 бит стоит отказаться в ближайшие три-четыре года.

Алгоритм Диффи-Хелмана


Алгоритм Диффи — Хеллмана (Diffie-Hellman, DH) — алгоритм, позволяющий двум сторонам получить общий секретный ключ, используя незащищенный от прослушивания, но защищённый от подмены канал связи. Этот ключ может быть использован для шифрования дальнейшего обмена с помощью алгоритма симметричного шифрования. Впервые был опубликован в 1976 году.

Алгоритм основан на трудности вычислений дискретных логарифмов. Дискретный логарифм определяется следующим образом. Вводится понятие примитивного (первообразного) корня простого числа q как числа, чьи степени создают все целые от 1 до q - 1. Это означает, что если α является первообразным корнем простого числа q, тогда числа

α mod q, α2 mod q, . . . , αq-1 mod q

являются различными и состоят из целых от 1 до q-1, возможно с некоторыми перестановками. В этом случае для любого целого Y < q и первообразного корня α простого числа α можно найти единственную экспоненту Х, такую, что

Y = αХ mod q, где 0 X (q - 1)

Экспонента X называется дискретным логарифмом, или индексом Y, по основанию α mod q. Это обозначается как



indα,q(Y)
В схеме обмена DH имеются два открытых для всех числа: простое число q и его первообразный корень α. Предположим, пользователя A и B намерены обменяться ключами. Пользователь A выбирает случайное целое число Xa < q и вычисляет Ya = α Xa mod q. Аналогично пользователь B выбирает своё случайное целое число Xb < q и вычисляет Yb = α Xb mod q. Каждая сторона сохраняет значение X в тайне (закрытый ключ), а значение Y делает свободно доступным другой стороне. Пользователь A вычисляет ключ K по формуле K = (Yb)Xa mod q, а пользователь B – по формуле K = (Ya)Xb mod q. Эти две формулы дают при вычислении одинаковый результат. В таблицах ниже алгоритм представлен более компактно:



Общеизвестные элементы

q

простое число

α

α < q и α является первообразным корнем q




Создание пары ключей пользователем A

Выбор случайного числа Хa (закрытый ключ)

Xa < q

Вычисление числа Ya (открытый ключ)

Ya = αXa mod q




Создание открытого ключа пользователем B

Выбор случайного числа Хb (закрытый ключ)

Xb < q

Вычисление случайного числа Yb (открытый ключ)

Yb = αXb mod q




Создание общего секретного ключа пользователем A

K = (Yb)Xa mod q




Создание общего секретного ключа пользователем B

K = (Ya)Xb mod q

Доказательство того, что A и B получат в результате один и тот же ключ, достаточно просто:


K = (Yb)Xa mod q

= (αXb mod q)Xa mod q

= (αXb)Xa mod q – по правилам модульной арифметики

= αXbXa mod q

= (αXa)Xb mod q

= (αXa mod q)Xb mod q

= (Ya)Xb mod q
Защищённость обмена ключами по схеме Диффи-Хеллмана опирается на тот факт, что степени по модулю некоторого простого числа вычисляются легко, в то время как обратная задача вычисления дискретного логарифма вычислительно сложна (особенно для больших простых чисел), фактически атакующий должен вычислить

Xb = indα,q (Yb)

Практический числовой пример обмена ключом для q = 71 и его первообразного (примитивного) корня α = 7. Пользователи A и B выбирают свои секретные ключи Xa=5 и Xb=12, соответственно. Каждый вычисляет свой открытый ключ:

Ya = 75 = 51 mod 71,

Yb = 712 = 4 mod 71.
После обмена открытыми ключами, каждый из них сможет вычислить общий (одинаковый) секретный ключ:
K = (Yb)Xa mod 71 = 45 = 30 mod 71,

K = (Ya)Xb mod 71 = 5112 = 30 mod 71.


Имея {51, 4}, противнику не удастся легко вычислить секретный ключ 30. По своей природе алгоритм DH уязвим для атак типа "man-in-the-middle" («человек посередине»). Атакующий заменяет сообщения переговоров о ключе на свои собственные и таким образом получает два ключа — свой для каждого из законных участников протокола. Далее он может перешифровывать переписку между участниками, своим ключом для каждого, и таким образом ознакомиться с их сообщениями, оставаясь незамеченным. Этот факт был проиллюстрирован на рис.20.



Достарыңызбен бөлісу:
1   ...   8   9   10   11   12   13   14   15   ...   44


©kzref.org 2019
әкімшілігінің қараңыз

    Басты бет