Открытое распределение ключей

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

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

Рассмотрим практическую реализацию (протокол обмена ключами).

Необходима определенная подготовительная работа:

· получить p – большое простое число;

· получить полное разложение числа (p –1) на множители;

· вычислить первообразный корень r по модулю p (r mod p)

Всякое составное число можно разложить на простые множители (множители – простые числа или их положительные целые степени, возможно нулевые).

где p_i– простые числа; b_i – степени простых чисел.

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

Протокол обмена ключами Диффи–Хеллмана

1. А генерирует элемент , вычисляет и отправляет результат В.

2. Вгенерирует элемент , вычисляет и отправляет результатА.

3. А вычисляет значение .

4. В вычисляет значение .

Замечание: после получения значения и должны быть уничтожены.

В результате выполнения протокола каждый из абонентов А и Вполучает общий ключ , который может быть использован в симметричных системах шифрования, причем противник, которому известен открытый ключ (p,r) и который перехватил числа и не сможет вычислить значение .

Пример Пусть p = 43 (простое число), r = 3 – первообразный корень по ; пара чисел (43,3) – открытый ключ для выработки секретного ключа .

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

Аналогичные действия В дают следующий результат: элемент , и вычисление . После выполнения пунктов 3, 4 протокола результат следующий: .

Рекомендации для практической реализации

1 Простое число p необходимо выбирать так, чтобы число p -1 имело достаточно большой сомножитель p_max >2¹⁶⁰ .

2 r – не обязательно должен быть первообразным корнем; достаточно следующего:

r ≠ 1; и .

Криптосистема RSA

RSA –система ассиметричного шифрования, в которой для кодирования сообщения используется один ключ, а для расшифровки другой. Названа в честь математиков-криптологов Рона Ривеста (Rivest), Ади Шамира (Shamir) и Лена Адельмана (Adelman) из Масачуссетского Технологического Института, разработавших алгоритм в 1977 году.

Система RSA используется для защиты программного обеспечения и в схемах цифровой подписи. Также она используется в открытой системе шифрования PGP. Из-за низкой скорости шифрования (около 30 кбит/с при 512 битном ключе на процессоре 2ГГц), сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным ключом, а с помощью RSA шифруют только этот ключ, который в зашифрованном виде помещают в начало шифротекста.

В связи со схемой RSA возникает ряд алгоритмических задач.

1. Для генерации ключей надо уметь генерировать большие простые числа. Близкой задачей является проверка простоты целого числа.

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

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

1. Выбрать два случайных простых числа pи q , причем |p|≈ |q| (т.е. числа примерно одинаковой длины).

2. Вычислить N = p q.

3. Вычислить функцию Эйлера φ(N)= (p-1) (q-1) (см. примечание).

4. Выбрать случайное целое число e < φ (N)взаимно простое с φ(N)

т.е. НОД(e , Ф (N)) = 1 и найти число d обратное e по модулю φ (N)(e^-1 = d)

e d≡ 1 mod (φ (N)) = 1 + φ (N) ∙n(n – любое целое число).

5. В качестве параметров открытого ключа сообщить пару (e , N) всем, кто будет передавать ему зашифрованную информацию; секретный ключ dне разглашать и надежно хранить; числа p, q , φ (N)– уничтожить.

ПримечаниеФункция Эйлера φ(N)равна количеству целых чисел, взаимно простых с N. Вычислить эту функцию в общем виде для любого N можно через его разложение на простые сомножители. Пусть N= p₁^b1p₂^b2p₃^b3 …p_n^bn , тогда функция Эйлера вычисляется по формуле φ(N) = N (1- 1/ p₁)(1- 1/ p₂) (1- 1/ p₃) …(1- 1/ p_n) .

Шифрование

В хочет зашифровать сообщение m и переслать его А по открытому каналу причем (m < N); для получения шифротекста В выполняет следующее преобразование:

m ^e (mod N) → c,

где c – шифротекст, который передается А по открытому каналу.

Замечание: Если В утратил исходное сообщениеm, то по c он не сможет восстановить m.

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

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

C d (mod N) → m.

Математически убедимся в этом:

c ^d (mod N)= m ^{e d} (mod N)= m^{(1 + φ (N)∙n)} (mod N)= m m^{φ (N)∙n}(mod N) =

= m (m^{φ (N)∙} (mod N)) ⁿ = m.

Последнее преобразование выполнено в соответствии с теоремой Эйлера.

Теорема Если НОД ( m,N) = 1, то m ^{φ (N)∙}≡ 1(mod N ). (это в нашем случае всегда так за исключением двух совпадений m = p и m = q ).Предполагается, что вероятность таких совпадений ничтожно мала при больших p и q в реальных криптосистемах.

Пример(учебный)

ПустьАвыбрал N = p ∙q = 7х13 = 91 и e= 5; тогда φ(N)∙= 6х12 = 72 . Открытый ключ (91,5) . Для вычисления секретного ключа dнеобходимо решить уравнение

5 d≡ 1(mod 72) ;или . 72 n +5 d =1

Подставляя в это уравнение числа = 0, ± 1, ± 2 и т.д. получим единственное целочисленное решение при n = –2 d = 29 (секретный ключ).

Пусть В решил отправить А сообщение m =3. Используя открытый ключ (91,5) он получил шифротекст 3 ⁵ (mod 91) →61. Шифротекст 61 В передает по открытому каналу А. Для восстановления исходного сообщения А выполняет следующее вычисление:

61 ²⁹ (mod 91) →3.