Шифр Эль-Гамаля

Пусть имеются абоненты А, В, С,..., которые хотят передавать друг другу зашифрованные сообщения, не имея никаких защищенных каналов связи. В этом разделе мы рассмотрим шифр, предложенный Эль-Гамалем (Taher ElGamal), который решает эту задачу, используя, в отличие от шифра Шамира, только одну пересылку сообщения. Фактически здесь используется схема Диффи-Хеллмана, чтобы сформировать общий секретный ключ для двух абонентов, передающих друг другу сообщение, и затем сообщение шифруется путем умножения его на этот ключ. Для каждого следующего сообщения секретный ключ вычисляется заново. Перейдем к точному описанию метода.

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

Затем каждый абонент группы выбирает свое секретное число с_i, 1 <с_i<р- 1, и вычисляет соответствующее ему открытое число d_i,

d_i= mod p. (3.24)

В результате получаем таблицу 3.3.

Таблица 3.3

Ключи пользователей в системе Эль-Гамаля

Абонент	Секретный ключ	Открытый ключ
А В С	cА cB cC	dA dB dC

Покажем теперь, как А передает сообщение т абоненту В. Будем предполагать, как и при описании шифра Шамира, что сообщение представлено в виде числа т<р.

Шаг 1. А формирует случайное число k, 1 kр -2, вычисляет числа

r = g^k mod p, (3.25)

e = m·d_B^k mod p (3.26)

и передает пару чисел (r, е) абоненту В.

Шаг 2. В, получив (r, е), вычисляет

m’ =e mod p. (3.27)

Утверждение 3.11 (свойства шифра Эль-Гамаля).

1) Абонент В получил сообщение, т.е. т' = т,

2) противник, зная р, g, d_B, r и е, не может вычислить т. Доказательство. Подставим в (3.27) значение е из (3.26):

m’ = m d_B^k mod p.

Теперь вместо r подставим (3.25), а вместо d_B - (3.24):

m'= m mod p =m mod p = m mod p.

По теореме Ферма

mod р = 1 ^k mod p =1,

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

Для доказательства второй части заметим, что противник не может вычислить k в равенстве (3.25), так как это задача дискретного логарифмирования. Следовательно, он не может вычислить т, в равенстве (3.26), так как т было умножено на неизвестное ему число. Противник также не может воспроизвести действия законного получателя сообщения (абонента В), так как ему не известно секретное число с_B (вычисление с_B на основании (2.24) - также задача дискретного логарифмирования).

3.6. Односторонняя функция с «лазейкой» и шифр RSA

Названный в честь его разработчиков Ривеста (Ron Rivest), Шамира (Adi Shamir) и Адлемана (Leonard Adleman), этот шифр до сих пор является одним из самых широко используемых.

Мы видели, что шифр Шамира полностью решает задачу обмена сообщениями, закрытыми для прочтения, в случае, когда абоненты могут пользоваться только открытыми линиями связи. Однако при этом сообщение пересылается три раза от одного абонента к другому, что является недостатком. Шифр Эль-Гамаля позволяет решить ту же задачу за одну пересылку данных, но объем передаваемого шифротекста в два раза превышает объем сообщения. Система RSA лишена подобрых недостатков. Интересно то, что она базируется на другой односторонней функции, отличной от дискретного логарифма. Кроме того, здесь мы встретимся с еще одним изобретением современной криптографии - односторонней функцией с «лазейкой» (trapdoor function).

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

1) задача проверки числа на простоту является сравнительно легкой;

2) задача разложения чисел вида п = pq (p и q - простые числа) на множители является очень трудной, если мы знаем только п, а р и q - большие числа (это так называемая задача факторизации).

Пусть в нашей системе есть абоненты А, В, С,.... Каждый абонент выбирает случайно два больших простых числа Р и Q. Затем он вычисляет число

N = PQ. (3.28)

(Число N является открытой информацией, доступной другим абонентам.) После этого абонент вычисляет число =(Р -1)(Q- 1) и выбирает некоторое число d< , взаимно простое с , и по обобщенному алгоритму Евклида находит число с, такое, что

cd mod =1. (3.29)

Таблица 3.4.

Ключи пользователей в системе RSA

Абонент	Секретный ключ	Открытый ключ
А В C	cA cB cC	dA ,NA dB,,NB dC, NC

Вся информация, связанная с абонентами и являющаяся их открытыми и секретными ключами, представлена в табл. 3.4.

Опишем протокол RSA. Пусть Алиса хочет передать сообщение m Бобу, причем сообщение m рассматривается как число, удовлетворяющее неравенству т<N_B (далее индекс В указывает на то, что соответствующие параметры принадлежат Бобу).

Шаг 1. Алиса шифрует сообщение по формуле

e= mod N_B, (3.30)

используя открытые параметры Боба, и пересылает е по открытой линии.

Шаг 2. Боб, получивший зашифрованное сообщение, вычисляет

m' = mod N_B. (3.31)

Утверждение 3.12. Для описанного протокола т'=т, т.е. абонент В получает исходящее от А сообщение.

Доказательство. По построению протокола

т' = mod N_B = mod N_B. Равенство (3.29) означает, что для некоторого k

c_Bd_B = k _в+ 1.

Согласно утверждению 3.5

_B= (Р_B- 1)(Q_B -1)=,

где (·)функция Эйлера. Отсюда и из теоремы 3.8 следует

т’= mod N_B =m.

Утверждение 3.13 (свойства протокола RSA).

1)Протокол шифрует и дешифрует информацию корректно;

2) злоумышленник, перехватывающий все сообщения и знающий всю открытую информацию, не сможет найти исходное сообщение при больших Р и Q.

Доказательство. Первое свойство протокола следует из утверждения 3.12. Для доказательства второго свойства заметим, что злоумышленник знает только открытые параметры N и d. Для того чтобы найти с, он должен знать значение =(Р- 1)(Q-1), а для этого, в свою очередь, ему требуется знать Р и Q. Вообще говоря, он может найти Р и Q, разложив N на множители, однако это трудная задача (см. пункт 2 в начале раздела). Отметим, что выбор больших случайных Р и Q возможен за приемлемое время, так как справедлив пункт 1.

Односторонняя функция у=x^d mod N, применяемая в системе RSA, обладает так называемой «лазейкой», позволяющей легко вычислить обратную функцию х= mod N, если известно разложение N на простые множители. (Действительно, легко вычислить = (Р- 1)(Q-1), а затем с = d ^-1 mod .) Если Р и Q неизвестны, то вычисление значения обратной функции практически невозможно, а найти Р и Q по N очень трудно, т.е. знание Р и Q - это «лазейка» или «потайной ход»). Такие односторонние функции с лазейкой находят применение и в других разделах криптографии.

Отметим, что для схемы RSA важно, чтобы каждый абонент выбирал собственную пару простых чисел Р и Q, т.е. все модули Na, Nb, Nc, должны быть различны (в противном случае один абонент мог бы читать зашифрованные сообщения, предназначенные для другого абонента). Однако этого не требуется от второго открытого параметра d. Параметр d может быть одинаковым у всех абонентов. Часто рекомендуется выбирать d= 3 (при соответствующем выборе Р и Q,). Тогда шифрование выполняется максимально быстро, всего за два умножения.

Дата добавления: 2014-01-11