Асимметричные системы шифрования

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

EK(M) = C
DK(c) = M, где K – ключ, M – исходный текст; C – зашифрованный текст.

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

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

Конгруентность (сравнимость). a конгруентно b по модулю n (a є nb), если при делении на n a и b, получается идентичный остаток. Так 100 є 1134 (100 и 34 при делении на 11 дают остаток 1) и –6 є 810 (ведь –6 =8(-1)+2). Мы всегда имеем a є nb для некоторого 0 Ј bЈ n-1. Если a єnb и сє d, то справедливы равенства:

a +c є n(b + d) и ac єnbd

Аналогичная процедура для деления не всегда справедлива: 6є 1218 но 3 9.

Наибольший общий делитель (НОД). Для a и b число (a,b) является наибольшим общим делителем, который делит a и b без остатка:

(56,98)=14; (76,190)=38

Теорема 1. Для любых a,b существуют целые числа x,y, для которых ax+by=(a,b).

В этом можно убедиться, решая уравнение 30x+69y=3 путем последовательных упрощающих подстановок (ищется целочисленное решение):

30x+69y=3

30x'+9y=3

[x'=x+2y]

3x'+9y'=3

[y'=y+3x']

3x"+0y'=3

[x"=x'+3y']

Легко видеть, что x"=1, y'=0 является решением окончательного уравнения. Мы можем получить решение исходного уравнения путем обратной подстановки.

x'=x"-3y'=1 y=y'-3x'=-3 x=x'-1y=7

Мы можем решить уравнение вида 30x+69y=15 путем умножения нашего решения: y=-15, x=35. Должно быть ясно, что уравнение не будет иметь целочисленного решения, если 15 заменить на что-то некратное (30,69)=3.

Все другие целочисленные решения 30x+69y=15 могут быть получены, варьируя первое решение:

y=-15+(30/3)t x=35 –(69/3)t для целого t

Если мы проделаем то же для произвольного равенства ax+by=(a,b), мы возможно получим один из коэффициентов равным нулю, а другой – (a,b). В действительности эта процедура представляет собой алгоритм Евклида для нахождения наибольшего общего делителя.

Важно то, что этот процесс реализуем на ЭВМ даже в случае, когда a и b имеют несколько сотен значащих цифр. Легко показать, что 600-значное число не потребует более чем 4000 уравнений. Теорема 1 справедлива и для простых чисел.

Следствие 1.

Если p является простым числом, ar є pas и a 0, тогда r є s.

Следствие 2.

Если p простое число и a 0 mod p, тогда для любого b существует y, для которого ay є pb.

Следствие 3.

("Китайская теорема об остатках"). Если (p,q)=1, тогда для любого a,b существует n, для которого n є pa и nє qb.

Во многих криптографических приложениях используется:

a a2 a3 … mod p, где a и p целые числа.

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

432678 mod 987.

Фокус заключается в том, что берется число и осуществляется возведение в квадрат.

4322 = 186624; 186624 mod 987 = 81; 4324 mod 987 = 812 mod 987 = 639
4328 -> 6392 mod 987 -> 690 …. 432512 -> 858
так как 678= 512+128+32+4+2, то:
432678->(81)(639)….(858) -> 204

Вычисления с использованием показателя включают в себя ограниченное число умножений. Если числа содержат несколько сотен цифр, необходимы специальные подпрограммы для выполнения таких вычислений. Рассмотрим последовательность степеней 2n mod 11:

2 4 8 5 10 9 7 3 6 1

Здесь числа от 1 до 10 появляются в виде псевдослучайной последовательности.

Теорема 2

Пусть p является простым числом. Существует такое a, что для каждого 1Ј b Ј p-1
существует такое 1Ј x Ј p-1, что axє pb.

Степени 2 mod 7 равны 2, 4, 1. Далее числа повторяются, а числа 3, 5, или 6 не могут быть получены никогда. Рассмотрим некоторые следствия этой теоремы.

Следствие 4. Пусть a соответствует требованиям теоремы 2, тогда ap-1 є p1.
Следствие 5.
Для любого b 0, bp-1 є p1.
Следствие 6
. Если x є (p-1)y, тогда bx є pby

Лемма
Пусть b 0, d наименьшее положительное число, такое что bd єp1. Тогда для любого с>0 c bc єp1 d делит c без остатка. В частности для следствия 5, d делит p-1 без остатка.

Согласно теореме 2, если p простое число, существует такое a, при котором равенство ax є pb имеет решение для любого b 0. Такое значение a называется примитивным корнем p, а x называется дискретным логарифмом b. Получение b при заданных a и x относительно просто, определение же x по a и b заметно сложнее. Многие современные системы шифрования основываются на факте, что никаких эффективных путей вычисления дискретных логарифмов не найдено. Никакого эффективного метода определения примитивных корней также неизвестно. Однако часто возможно найти примитивные корни в некоторых специальных случаях. Возьмем p=1223. p-1=2*13*47. Согласно лемме, если a не примитивный корень, тогда мы либо имеем a26, a94 или
a611 є 12231. a=2 и a=3 не годятся, но a=5 соответствует всем трем условиям, таким образом, это значение является примитивным корнем. Мы могли бы сказать, что a=4 не может быть признано примитивным корнем без проверки.

Легко показать, что если a примитивный корень, ax примитивный корень в том и только том случае, если (x,p-1)=1. В этом примере это означает, что число примитивных корней равно

1222*(1/2)*(12/13)*(46/47)=552

Таким образом, если мы выберем а произвольно, вероятность того, что это будет примитивный корень равна ~.45. Выбирая а наугад и тестируя, можно сравнительно быстро найти примитивный корень.

Современные системы шифрования используют асимметричные алгоритмы с открытым и секретным ключами, где нет проблемы безопасной транспортировки ключа. К числу таких систем относится алгоритм rsa (rivest-shamir-adleman - разработчики этой системы – Рональд Ривест, Ади Шамир и Леонард Адлеман, 1977 год), базирующийся на разложение больших чисел на множители.

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

  • шифрованный текст трудно (практически невозможно) расшифровать с использованием открытого ключа.

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

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

 

Алгоритм шифрования RSA

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

Сообщение представляется в виде числа M. Шифрование осуществляется с помощью общедоступной функции f(M), и только адресату известно, как выполнить операцию f-1 . Адресат выбирает два больших простых (prime) числа p и q, которые делает секретными. Он объявляет n=pq и число d, c (d,p-1)=(d,q-1)=1 (один из возможных способов выполнить это условие, выбрать d больше чем p/2 и q/2). Шифрование производится по формуле:

f(M) є Md mod n,

где M и f(M) оба Ј n-1. Как было показано, может быть вычислено за разумное время, даже если M, d и n содержит весьма большое число знаков. Адресат вычисляет M на основе Md, используя свое знание p и q. В соответствие со следствием 6, если
dc є(p-1)1, тогда (Md)eє p1.

Исходный текст M получается адресатом из зашифрованного F(M) путем преобразования: M = (F(M))e (mod pq). Здесь как исходный текст, так и зашифрованный рассматриваются как длинные двоичные числа.

Аналогично (Md)e є qM, если dc є (q-1)1. e удовлетворяет этим двум условиям, если cd є (p-1) (q-1)1. Теорема 1 гласит, что мы можем позволить e=x, когда x является решением уравнения dx + (p-1)(q-1)y = 1.

Так как (Md)e – M делимо на p и q, оно делимо и на pq, следовательно, мы можем определить M, зная Md, вычислив его значение в степени e и определив остаток от деления на pq. Для соблюдения секретности важно, чтобы, зная n, было нельзя вычислить p и q. Если n содержит 100 цифр, подбор шифра связан с перебором ~1050 комбинаций. Данная проблема изучается уже около 100 лет. RSA-алгоритм запатентован (20 сентября 1983, являлся стандартом до 2000 года).

Теоретически можно предположить, что возможно выполнение операции f-1, не вычисляя p и q. Но в любом случае задача эта не проста и разработчики считают ее трудно факторизуемой.

Предположим, что мы имеем зашифрованный текст f(M) и исходный текст M, и мы хотим найти значения p и q. Нетрудно показать, что таких исходных данных для решения задачи недостаточно – надо знать все возможные значения Mi.

Проясним использование алгоритма RSA на конкретном примере. Выбираем два простые числа p=7; q=17 (на практике эти числа во много раз длиннее). В этом случае n = p*q будет равно 119. Теперь необходимо выбрать e, выбираем e=5. Следующий шаг связан с формированием числа d так, чтобы d*e=1 mod [(p-1)(q-1)]. d=77 (использован расширенный алгоритм Эвклида). d – секретный ключ, а e и n характеризуют открытый ключ. Пусть текст, который нам нужно зашифровать представляется M=19. С = Memod n. Получаем зашифрованный текст C=66. Этот “текст” может быть послан соответствующему адресату. Получатель дешифрует полученное сообщение, используя М= Cdmod n и C=66. В результате получается M=19.

На практике общедоступные ключи могут помещаться в специальную базу данных. При необходимости послать партнеру зашифрованное сообщение можно сделать сначала запрос его открытого ключа. Получив его, можно запустить программу шифрации, а результат ее работы послать адресату. На использовании общедоступных ключей базируется и так называемая электронная подпись, которая позволяет однозначно идентифицировать отправителя. Сходные средства могут применяться для предотвращения внесения каких-либо корректив в сообщение на пути от отправителя к получателю. Быстродействующие аппаратные 512-битовые модули могут обеспечить скорость шифрования на уровне 64 кбит в сек. Готовятся ИС, способные выполнять такие операции со скоростью 1 Мбайт/сек. Разумный выбор параметра e позволяет заметно ускорить реализацию алгоритма.

Нарушение конфиденциальности

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

Рис.1

Если хакер умудрится вставить свою ЭВМ в разрыв канала, соединяющего субъектов А и В, у него появляется возможность перехватывать в том числе и шифрованные сообщения. Пусть субъект А сформировал пару ключей К и К (ключ с индексом 2 является секретным), аналогичную пару ключей сгенерировал субъект В (К и К). Хакер же тем временем подготовил две пары ключей (К1ХА2ХА и К1ХВ2ХВ). Когда субъект А пошлет открытый ключ К субъекту В, хакер его подменит ключом К1ХА. Аналогичную процедуру он проделает с ключом К, посланным от В к А. Теперь сообщение А к В, зашифрованное с помощью ключа К1ХА будет послано В. Хакер его перехватывает, дешифрует с помощью ключа К2ХА, шифрует с помощью ключа К1ХВ и посылает В. Субъект В, получив послание, дешифрует его с помощью "секретного" ключа К2ХВ, полученного от хакера (о чем он, естественно, не подозревает). Аналогичная процедура будет проведена и при посылки сообщения от В к А. В сущности единственным параметром который изменится существенным образом будет время доставки сообщения, так как это время будет включать дешифровку и повторную шифровку сообщения. Но при использовании быстродействующей ЭВМ и при работе с традиционной электронной почтой это может оказаться незаметным. Понятно, что между А и В появится дополнительный шаг (hop). Но и это может быть легко замаскировано под прокси сервер или Firewall.

Решить эту проблему можно путем пересылки открытого ключа своему партнеру по какому-то альтернативному каналу или сверки его по телефону.