учебники, программирование, основы, введение в,

 

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

Основные требования к алгоритмам асимметричного шифрования
Создание алгоритмов асимметричного шифрования является величайшим и, возможно, единственным революционным достижением в истории криптографии.
Алгоритмы шифрования с открытым ключом разрабатывались для того, чтобы решить две наиболее трудные задачи, возникшие при использовании симметричного шифрования.
Первой задачей является распределение ключа. При симметричном шифровании требуется, чтобы обе стороны уже имели общий ключ, который каким-то образом должен быть им заранее передан. Диффи, один из основоположников шифрования с открытым ключом, заметил, что это требование отрицает всю суть криптографии, а именно возможность поддерживать всеобщую секретность при коммуникациях.
Второй задачей является необходимость создания таких механизмов, при использовании которых невозможно было бы подменить кого-либо из участников, т.е. нужна цифровая подпись. При использовании коммуникаций для решения широкого круга задач, например в коммерческих и частных целях, электронные сообщения и документы должны иметь эквивалент подписи, содержащейся в бумажных документах. Необходимо создать метод, при использовании которого все участники будут убеждены, что электронное сообщение было послано конкретным участником. Это более сильное требование, чем аутентификация.
Диффи и Хеллман достигли значительных результатов, предложив способ решения обеих задач, который радикально отличается от всех предыдущих подходов к шифрованию.
Сначала рассмотрим общие черты алгоритмов шифрования с открытым ключом и требования к этим алгоритмам. Определим требования, которым должен соответствовать алгоритм, использующий один ключ для шифрования, другой ключ - для дешифрования, и при этом вычислительно невозможно определить дешифрующий ключ, зная только алгоритм шифрования и шифрующий ключ.
Кроме того, некоторые алгоритмы, например RSA, имеют следующую характеристику: каждый из двух ключей может использоваться как для шифрования, так и для дешифрования.
Сначала рассмотрим алгоритмы, обладающие обеими характеристиками, а затем перейдем к алгоритмам открытого ключа, которые не обладают вторым свойством.
При описании симметричного шифрования и шифрования с открытым ключом будем использовать следующую терминологию. Ключ, используемый в симметричном шифровании, будем называть секретным ключом. Два ключа, используемые при шифровании с открытым ключом, будем называть открытым ключом и закрытым ключом. Закрытый ключ держится в секрете, но называть его будем закрытым ключом, а не секретным, чтобы избежать путаницы с ключом, используемым в симметричном шифровании. Закрытый ключ будем обозначать KR, открытый ключ - KU.
Будем предполагать, что все участники имеют доступ к открытым ключам друг друга, а закрытые ключи создаются локально каждым участником и, следовательно, распределяться не должны.
В любое время участник может изменить свой закрытый ключ и опубликовать составляющий пару открытый ключ, заменив им старый открытый ключ.
Диффи и Хеллман описывают требования, которым должен удовлетворять алгоритм шифрования с открытым ключом.

  1. Вычислительно легко создавать пару (открытый ключ KU , закрытый ключ KR).
  2. Вычислительно легко, имея открытый ключ и незашифрованное сообщение М, создать соответствующее зашифрованное сообщение:

С = ЕKU[М]

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

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

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

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

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

М = ЕKU[DKR[M]]
Это достаточно сильные требования, которые вводят понятие односторонней функции с люком. Односторонней функцией называется такая функция, у которой каждый аргумент имеет единственное обратное значение, при этом вычислить саму функцию легко, а вычислить обратную функцию трудно.


Y = f(X) - легко

X = f-1(Y) - трудно

Обычно "легко" означает, что проблема может быть решена за полиномиальное время от длины входа. Таким образом, если длина входа имеет n битов, то время вычисления функции пропорционально na, где а - фиксированная константа. Таким образом, говорят, что алгоритм принадлежит классу полиномиальных алгоритмов Р. Термин "трудно" означает более сложное понятие. В общем случае будем считать, что проблему решить невозможно, если усилия для ее решения больше полиномиального времени от величины входа. Например, если длина входа n битов, и время вычисления функции пропорционально 2n, то это считается вычислительно невозможной задачей. К сожалению, тяжело определить, проявляет ли конкретный алгоритм такую сложность. Более того, традиционные представления о вычислительной сложности фокусируются на худшем случае или на среднем случае сложности алгоритма. Это неприемлемо для криптографии, где требуется невозможность инвертировать функцию для всех или почти всех значений входов.
Вернемся к определению односторонней функции с люком, которую, подобно односторонней функции, легко вычислить в одном направлении и трудно вычислить в обратном направлении до тех пор, пока недоступна некоторая дополнительная информация. При наличии этой дополнительной информации инверсию можно вычислить за полиномиальное время. Таким образом, односторонняя функция с люком принадлежит семейству односторонних функций fk таких, что


Y = fk(X) - легко, если k и Х известны

X = fk-1(Y) - легко, если k и Y известны

Х = fk-1(Y) - трудно, если Y известно, но k неизвестно

Мы видим, что разработка конкретного алгоритма с открытым ключом зависит от открытия соответствующей односторонней функции с люком.
Криптоанализ алгоритмов с открытым ключом
Как и в случае симметричного шифрования, алгоритм шифрования с открытым ключом уязвим для лобовой атаки. Контрмера стандартная: использовать большие ключи.
Криптосистема с открытым ключом применяет определенные неинвертируемые математические функции. Сложность вычислений таких функций не является линейной от количества битов ключа, а возрастает быстрее, чем ключ. Таким образом, размер ключа должен быть достаточно большим, чтобы сделать лобовую атаку непрактичной, и достаточно маленьким для возможности практического шифрования. На практике размер ключа делают таким, чтобы лобовая атака была непрактичной, но в результате скорость шифрования оказывается достаточно медленной для использования алгоритма в общих целях. Поэтому шифрование с открытым ключом в настоящее время в основном ограничивается приложениями управления ключом и подписи, в которых требуется шифрование небольшого блока данных.
Другая форма атаки состоит в том, чтобы найти способ вычисления закрытого ключа, зная открытый ключ. Невозможно математически доказать, что данная форма атаки исключена для конкретного алгоритма открытого ключа. Таким образом, любой алгоритм, включая широко используемый алгоритм RSA, является подозрительным.
Наконец, существует форма атаки, специфичная для способов использования систем с открытым ключом. Это атака вероятного сообщения. Предположим, например, что посылаемое сообщение состоит исключительно из 56-битного ключа сессии для алгоритма симметричного шифрования. Противник может зашифровать все возможные ключи, используя открытый ключ, и может дешифровать любое сообщение, соответствующее передаваемому зашифрованному тексту. Таким образом, независимо от размера ключа схемы открытого ключа, атака сводится к лобовой атаке на 56-битный симметричный ключ. Защита от подобной атаки состоит в добавлении определенного количества случайных битов в простые сообщения.
Основные способы использования алгоритмов с открытым ключом
Основными способами использования алгоритмов с открытым ключом являются шифрование/дешифрование, создание и проверка подписи и обмен ключа.
Шифрование с открытым ключом состоит из следующих шагов:

  1. Пользователь В создает пару ключей KUb и KRb, используемых для шифрования и дешифрования передаваемых сообщений.
  2. Пользователь В делает доступным некоторым надежным способом свой ключ шифрования, т.е. открытый ключ KUb. Составляющий пару закрытый ключ KRb держится в секрете.
  3. Если А хочет послать сообщение В, он шифрует сообщение, используя открытый ключ В KUb .
  4. Когда В получает сообщение, он дешифрует его, используя свой закрытый ключ KRb. Никто другой не сможет дешифровать сообщение, так как этот закрытый ключ знает только В.

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

  1. Пользователь А создает пару ключей KRA и KUA, используемых для создания и проверки подписи передаваемых сообщений.
  2. Пользователь А делает доступным некоторым надежным способом свой ключ проверки, т.е. открытый ключ KUA. Составляющий пару закрытый ключ KRA держится в секрете.
  3. Если А хочет послать подписанное сообщение В, он создает подпись EKRa[M] для этого сообщения, используя свой закрытый ключ KRA.
  4. Когда В получает подписанное сообщение, он проверяет подпись DKUa[M], используя открытый ключ А KUA. Никто другой не может подписать сообщение, так как этот закрытый ключ знает только А.

До тех пор, пока пользователь или прикладная система надежно хранит свой закрытый ключ, их подписи достоверны.
Кроме того, невозможно изменить сообщение, не имея доступа к закрытому ключу А; тем самым обеспечивается аутентификация и целостность данных.
В этой схеме все сообщение подписывается, причем для подтверждения целостности сообщения требуется много памяти. Каждое сообщение должно храниться в незашифрованном виде для использования в практических целях. Кроме того, копия сообщения также должна храниться в зашифрованном виде, чтобы можно было проверить в случае необходимости подпись. Более эффективным способом является шифрование небольшого блока битов, который является функцией от сообщения. Такой блок, называемый аутентификатором, должен обладать свойством невозможности изменения сообщения без изменения аутентификатора. Если аутентификатор зашифрован закрытым ключом отправителя, он является цифровой подписью, с помощью которой можно проверить исходное сообщение. Далее эта технология будет рассматриваться в деталях.
Важно подчеркнуть, что описанный процесс создания подписи не обеспечивает конфиденциальность. Это означает, что сообщение, посланное таким способом, невозможно изменить, но можно подсмотреть. Это очевидно в том случае, если подпись основана на аутентификаторе, так как само сообщение передается в явном виде. Но даже если осуществляется шифрование всего сообщения, конфиденциальность не обеспечивается, так как любой может расшифровать сообщение, используя открытый ключ отправителя.
Обмен ключей: две стороны взаимодействуют для обмена ключом сессии, который в дальнейшем можно использовать в алгоритме симметричного шифрования.
Некоторые алгоритмы можно задействовать тремя способами, в то время как другие могут использоваться одним или двумя способами.
Перечислим наиболее популярные алгоритмы с открытым ключом и возможные способы их применения.


Алгоритм

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

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

Обмен ключей

RSA

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

Да

Да

DSS

Нет

Да

Нет

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

Нет

Нет

Да

Алгоритм RSA

Диффи и Хеллман определили новый подход к шифрованию, что вызвало к жизни разработку алгоритмов шифрования, удовлетворяющих требованиям систем с открытым ключом. Одним из первых результатов был алгоритм, разработанный в 1977 году Роном Ривестом, Ади Шамиром и Леном Адлеманом и опубликованный в 1978 году. С тех пор алгоритм Rivest-Shamir-Adleman (RSA) широко применяется практически во всех приложениях, использующих криптографию с открытым ключом.
Алгоритм основан на использовании того факта, что задача факторизации является трудной, т.е. легко перемножить два числа, в то время как не существует полиномиального алгоритма нахождения простых сомножителей большого числа.
Алгоритм RSA представляет собой блочный алгоритм шифрования, где зашифрованные и незашифрованные данные являются целыми между 0 и n -1 для некоторого n.

Описание алгоритма

Алгоритм, разработанный Ривестом, Шамиром и Адлеманом, использует выражения с экспонентами. Данные шифруются блоками, каждый блок рассматривается как число, меньшее некоторого числа n. Шифрование и дешифрование имеют следующий вид для некоторого незашифрованного блока М и зашифрованного блока С.

С = Ме (mod n)
M = Cd (mod n) = (Me)d (mod n) = Med (mod n)

Как отправитель, так и получатель должны знать значение n. Отправитель знает значение е, получатель знает значение d. Таким образом, открытый ключ есть KU = {e, n} и закрытый ключ есть KR = {d, n}. При этом должны выполняться следующие условия:

  1. Возможность найти значения е, d и n такие, что Med = M mod n для всех М < n .
  2. Относительная легкость вычисления Ме и Сd для всех значений М < n.
  3. Невозможность определить d, зная е и n.

Сначала рассмотрим первое условие. Нам необходимо выполнение равенства:

Med = М (mod n)

Рассмотрим некоторые математические понятия, свойства и теоремы, которые позволят нам определить e, d и n.

  1. Если (а · b) (a · c) mod n, то b c mod n, если а и n взаимнопростые, т.е gcd (a, n) = 1.
  2. Обозначим Zp - все числа, взаимнопростые с p и меньшие p. Если p - простое, то Zp - это все остатки. Обозначим w-1 такое число, что w · w-1  1 mod p.

Тогда w Zp z: w · z 1 mod p
Доказательство этого следует из того, что т.к. w и p взаимнопростые, то при умножении всех элементов Zp на w остатками будут все элементы Zp, возможно, переставленные. Таким образом, хотя бы один остаток будет равен 1.

  1. Определим функцию Эйлера следующим образом: Φ(n) - число положительных чисел, меньших n и взаимнопростых с n. Если p - простое, то (р) = p-1.

Если p и q - простые, то Φ(p · q) = (p-1) · (q-1).
В этом случае Zp · q ={0, 1, ј, (p · q - 1)}.
Перечислим остатки, которые не являются взаимнопростыми с p · q:

{p, 2 · p, ј, (q-1)  · p}
{q, 2 · q, ј, (p-1)  · q}
0

Таким образом Φ(p · q) = p · q - [(q-1) + (p-1) + 1] = p · q - (p+q) + 1 = (p-1) · (q-1).

  1. Теорема Ферма.

an-1 1 mod n, если n - простое.
Если все элементы Zn умножить на а по модулю n, то в результате получим все элементы Zn, быть может, в другом порядке. Рассмотрим следующие числа:
{a mod n, 2 · a mod n, ј, (n-1) · a mod n} являются числами {1, 2, ј, (n-1)}, быть может, в некотором другом порядке. Теперь перемножим по модулю n числа из этих двух множеств.

[(a mod n) · (2a mod n) · ... · (n-1)a mod n] 
mod n  (n-1)! mod n(n-1)! an-1  (n-1)! mod n

n и (n-1)! являются взаимнопростыми, если n - простое, следовательно, an-1 1 mod n.

  1. Теорема Эйлера.

aΦ(n) 1 mod n для всех взаимнопростых a и n.
Это верно, если n - простое, т.к. в этом случае Φ(n) = n-1. Рассмотрим множество R = {x1, x2, ј, xΦ(n)}. Теперь умножим по модулю n каждый элемент этого множества на a. Получим множество S = {a · x1 mod n, a · x2 mod n, ј, a · xΦ(n) mod n}. Это множество является перестановкой множества R по следующим причинам.
Так как а является взаимнопростым с n и xi являются взаимнопростыми с n, то a · xi также являются взаимнопростыми с n. Таким образом, S - это множество целых, меньших n и взаимнопростых с n.
В S нет дублей, т.к. если a · xi mod n = a · xj mod n xi = xj.
Следовательно, перемножив элементы множеств S и R, получим:

Φ(n)                Φ(n)
 ∏ (a · xi mod n)   ∏  xi mod n
i=1                 i=1
 Φ(n)         Φ(n)
( ∏ a · xi    ∏ xi ) mod n
 i=1          i=1
          Φ(n)     Φ(n)
( aΦ(n)  ·  ∏ xi    ∏ xi ) mod n
          i=1      i=1
( aΦ(n)  1) mod n

Теперь рассмотрим сам алгоритм RSA. Пусть p и q - простые.

n = p · q.

Надо доказать, что M < n: MΦ(n) = M(p-1) · (q-1) 1 mod n
Если gcd (M, n) = 1, то соотношение выполняется. Теперь предположим, что gcd (M, n) 1, т.е. gcd (M, p · q) 1. Пусть gcd (M, p) 1, т.е. M = c · p gcd (M, q) = 1, так как в противном случае M = c · p и M = l · q, но по условию M < p · q.
Следовательно,

MΦ(q)  1 mod q
(MΦ(q))(p)  1 mod q
MΦ(n)  1 mod q

По определению модуля это означает, что MΦ(n) = 1 + k · q. Умножим обе части равенства на M = c · p. Получим

MΦ(n)+1 = c · p + k · q · c · p.
MΦ(n)  1 mod n

Или

MΦ(n)+1  M mod n

Таким образом, следует выбрать e и d такие, что е · d 1 mod (n)
Или e d-1 mod Φ(n)
e и d являются взаимнообратными по умножению по модулю Φ(n). Заметим, что в соответствии с правилами модульной арифметики, это верно только в том случае, если d (и следовательно, е) являются взаимнопростыми с Φ(n). Таким образом, gcd (Φ(n), d) = 1.

Теперь рассмотрим все элементы алгоритма RSA.


p, q - два простых целых числа

 - открыто, вычисляемо.

n = p · q

 - закрыто, вычисляемо.

d, gcd (Φ(n), d) = 1;

 - открыто, выбираемо.

1 < d < Φ(n)

е d-1 mod Φ(n)

 - закрыты, выбираемы.

Закрытый ключ состоит из {d, n}, открытый ключ состоит из {e, n}. Предположим, что пользователь А опубликовал свой открытый ключ, и что пользователь В хочет послать пользователю А сообщение М. Тогда В вычисляет С = Ме (mod n) и передает С. При получении этого зашифрованного текста пользователь А дешифрует вычислением М = С d (mod n).
Суммируем алгоритм RSA:
Создание ключей


Выбрать простые р и q

Вычислить n = p · q

Выбрать d     gcd (Φ(n), d) = 1; 1 < d < Φ(n)

Вычислить е     е = d-1 mod Φ(n)

Открытый ключ KU = {e, n}

Закрытый ключ KR = {d, n}

Шифрование


Незашифрованный текст: М < n

Зашифрованный текст: С = М е (mod n)

Дешифрование


Зашифрованный текст: С

Незашифрованный текст: М = Сd (mod n)

Рассмотрим конкретный пример:


Выбрать два простых числа: р = 7, q = 17.

Вычислить n = p · q = 7 · 17 = 119.

Вычислить Φ(n) = (p - 1) · (q - 1) = 96.

Выбрать е так, чтобы е было взаимнопростым с Φ(n) = 96 и меньше, чем Φ(n): е = 5.

Определить d так, чтобы d · e 1 mod 96 и d < 96.

d = 77, так как 77 · 5 = 385 = 4 · 96 + 1.

Результирующие ключи открытый KU = {5, 119} и закрытый KR = {77, 119}.

Например, требуется зашифровать сообщение М = 19.

195 = 66 (mod 119); С = 66.

Для дешифрования вычисляется 6677 (mod 119) = 19.

Вычислительные аспекты

Рассмотрим сложность вычислений в алгоритме RSA при создании ключей и при шифровании/дешифровании.

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

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

[(a mod n) · (b mod n)] mod n = (a · b) mod n

Другая оптимизация состоит в эффективном использовании показателя степени, так как в случае RSA показатели степени очень большие. Предположим, что необходимо вычислить х16. Прямой подход требует 15 умножений. Однако можно добиться того же конечного результата с помощью только четырех умножений, если использовать квадрат каждого промежуточного результата: х2, х4, х8, х16.

Создание ключей

Создание ключей включает следующие задачи:

  1. Определить два простых числа р и q.
  2. Выбрать е и вычислить d.

Прежде всего, рассмотрим проблемы, связанные с выбором р и q. Так как значение n = p · q будет известно любому потенциальному противнику, для предотвращения раскрытия р и q эти простые числа должны быть выбраны из достаточно большого множества, т.е. р и q должны быть большими числами. С другой стороны, метод, используемый для поиска большого простого числа, должен быть достаточно эффективным.
В настоящее время неизвестны алгоритмы, которые создают произвольно большие простые числа. Процедура, которая используется для этого, выбирает случайное нечетное число из требуемого диапазона и проверяет, является ли оно простым. Если число не является простым, то опять выбирается случайное число до тех пор, пока не будет найдено простое.
Были разработаны различные тесты для определения того, является ли число простым. Это тесты вероятностные, то есть тест показывает, что данное число вероятно является простым. Несмотря на это они могут выполняться таким образом, что сделают вероятность близкой к 1. Если n "проваливает" тест, то оно не является простым. Если n "пропускает" тест, то n может как быть, так и не быть простым. Если n пропускает много таких тестов, то можно с высокой степенью достоверности сказать, что n является простым. Это достаточно долгая процедура, но она выполняется относительно редко: только при создании новой пары (KU, KR).
На сложность вычислений также влияет то, какое количество чисел будет отвергнуто перед тем, как будет найдено простое число. Результат из теории чисел, известный как теорема простого числа, говорит, что простых чисел, расположенных около n в среднем одно на каждые ln (n) чисел. Таким образом, в среднем требуется проверить последовательность из ln (n) целых, прежде чем будет найдено простое число. Так как все четные числа могут быть отвергнуты без проверки, то требуется выполнить приблизительно ln (n)/2 проверок. Например, если простое число ищется в диапазоне величин 2200, то необходимо выполнить около ln (2200) / 2 = 70 проверок.
Выбрав простые числа р и q, далее следует выбрать значение е так, чтобы gcd(Φ(n), e) = 1 и вычислить значение d, d = e-1 mod Φ(n). Cуществует единственный алгоритм, называемый расширенным алгоритмом Евклида, который за фиксированное время вычисляет наибольший общий делитель двух целых и если этот общий делитель равен единице, определяет инверсное значение одного по модулю другого. Таким образом, процедура состоит в генерации серии случайных чисел и проверке каждого относительно Φ(n) до тех пор, пока не будет найдено число, взаимнопростое с Φ(n). Возникает вопрос, как много случайных чисел придется проверить до тех пор, пока не найдется нужное число, которое будет взаимнопростым с Φ(n). Результаты показывают, что вероятность того, что два случайных числа являются взаимнопростыми, равна 0.6.

Обсуждение криптоанализа

Можно определить четыре возможных подхода для криптоанализа алгоритма RSA:

  1. Лобовая атака: перебрать все возможные закрытые ключи.
  2. Разложить n на два простых сомножителя. Это даст возможность вычислить Φ(n) = (p-1) · (q-1) и d = e-1 (mod (n)).
  3. Определить Φ(n) непосредственно, без начального определения р и q. Это также даст возможность определить d = e-1 (mod Φ(n)).
  4. Определить d непосредственно, без начального определения Φ(n).

Защита от лобовой атаки для RSA и ему подобных алгоритмов состоит в использовании большой длины ключа. Таким образом, чем больше битов в е и d, тем лучше. Однако, так как вычисления необходимы как при создании ключей, так и при шифровании/дешифровании, чем больше размер ключа, тем медленнее работает система.
Большинство дискуссий о криптоанализе RSA фокусируется на задаче разложения n на два простых сомножителя. В настоящее время неизвестны алгоритмы, с помощью которых можно было бы разложить число на два простых множителя для очень больших чисел (т.е. несколько сотен десятичных цифр). Лучший из известных алгоритмов дает результат, пропорциональный:

L (n) = esqrt (ln n * ln (ln n))

Пока не разработаны лучшие алгоритмы разложения числа на простые множители, можно считать, что величина n от 100 до 200 цифр в настоящее время является достаточно безопасной. На современном этапе считается, что число из 100 цифр может быть разложено на множители за время порядка двух недель. Для дорогих конфигураций (т.е. порядка $10 млн) число из 150 цифр может быть разложено приблизительно за год. Разложение числа из 200 цифр находится за пределами вычислительных возможностей. Например, даже если вычислительный уровень в 1012 операций в секунду достижим, что выше возможностей современных технологий, то потребуется свыше 10 лет для разложения на множители числа из 200 цифр с использованием существующих алгоритмов.
Для известных в настоящее время алгоритмов задача определения (n) по данным е и n, по крайней мере, сопоставима по времени с задачей разложения числа на множители.
Для того чтобы избежать выбора значения n, которое могло бы легко раскладываться на сомножители, на р и q должно быть наложено много дополнительных ограничений: р и q должны друг от друга отличаться по длине только несколькими цифрами. Таким образом, оба значения р и q должны быть от 1075 до 10100.
Оба числа (р - 1) и (q - 1) должны содержать большой простой сомножитель.
gcd (p -1, q - 1) должен быть маленьким.
Алгоритм обмена ключа Диффи-Хеллмана
Первая публикация данного алгоритма открытого ключа появилась в статье Диффи и Хеллмана, в которой вводились основные понятия криптографии с открытым ключом и в общих чертах упоминался алгоритм обмена ключа Диффи-Хеллмана.
Цель алгоритма состоит в том, чтобы два участника могли безопасно обменяться ключом, который в дальнейшем может использоваться в каком-либо алгоритме симметричного шифрования. Сам алгоритм Диффи-Хеллмана может применяться только для обмена ключами.
Алгоритм основан на трудности вычислений дискретных логарифмов. Дискретный логарифм определяется следующим образом. Вводится понятие примитивного корня простого числа Q как числа, чьи степени создают все целые от 1 до Q - 1. Это означает, что если А является примитивным корнем простого числа Q, тогда числа
A mod Q, A2 mod Q, . . . , AQ - 1 mod Q
являются различными и состоят из целых от 1 до Q - 1 с некоторыми перестановками. В этом случае для любого целого B < Q и примитивного корня A простого числа Q можно найти единственную экспоненту Х, такую, что
Y = AХ mod Q, где 0  X  (Q - 1)
Экспонента X называется дискретным логарифмом, или индексом Y, по основанию A mod Q. Это обозначается как
indA, Q (Y).
Теперь опишем алгоритм обмена ключей Диффи-Хеллмана.


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

Q

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

A

A < Q и A является примитивным корнем Q

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

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

Xi < Q

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

Yi = AXi mod Q

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

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

Xj < Q

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

Yj = AXj mod Q

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

K = (Yj)Xi mod Q

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

K = (Yi)Xj mod Q

Предполагается, что существуют два известных всем числа: простое число Q и целое A, которое является примитивным корнем Q. Теперь предположим, что пользователи I и J хотят обменяться ключом для алгоритма симметричного шифрования. Пользователь I выбирает случайное число Хi < Q и вычисляет Yi = AXi mod Q. Аналогично пользователь J независимо выбирает случайное целое число Хj < Q и вычисляет Yj = AXj mod Q. Каждая сторона держит значение Х в секрете и делает значение Y доступным для другой стороны. Теперь пользователь I вычисляет ключ как К = (Yj)Xi mod Q, и пользователь J вычисляет ключ как K = (Yi)Xj mod Q. В результате оба получат одно и то же значение:
K = (Yj)Xi mod Q
= (AXj mod Q)Xi mod Q
= (AXj )Xi mod Q
по правилам модульной арифметики
= AXj Xi mod Q
= (AXj )Xj mod Q
= (AXi mod Q)Xj mod Q
= (Yi)Xj mod Q
Таким образом, две стороны обменялись секретным ключом. Так как Хi и Хj являются закрытыми, противник может получить только следующие значения: Q, A, Yi и Yj. Для вычисления ключа атакующий должен взломать дискретный логарифм, т.е. вычислить
Xj = inda, q (Yj)
Безопасность обмена ключа в алгоритме Диффи-Хеллмана вытекает из того факта, что, хотя относительно легко вычислить экспоненты по модулю простого числа, очень трудно вычислить дискретные логарифмы. Для больших простых чисел задача считается неразрешимой.
Следует заметить, что данный алгоритм уязвим для атак типа "man-in-the-middle". Если противник может осуществить активную атаку, т.е. имеет возможность не только перехватывать сообщения, но и заменять их другими, он может перехватить открытые ключи участников Yi и Yj , создать свою пару открытого и закрытого ключа (Xоп, Yоп) и послать каждому из участников свой открытый ключ. После этого каждый участник вычислит ключ, который будет общим с противником, а не с другим участником. Если нет контроля целостности, то участники не смогут обнаружить подобную подмену.

 

 
На главную | Содержание | < Назад....Вперёд >
С вопросами и предложениями можно обращаться по nicivas@bk.ru. 2013 г.Яндекс.Метрика