Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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




 

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

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

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

di= mod p. (3.24)

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

Таблица 3.3

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

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

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

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

r = gk mod p, (3.25)

e = m·dBk mod p (3.26)

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

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

m’ =e mod p. (3.27)

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

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

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

m’ = m dBk mod p.

Теперь вместо r подставим (3.25), а вместо dB - (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 рассматривается как число, удовлетворяющее неравенству т<NB (далее индекс В указывает на то, что соответствующие параметры принадлежат Бобу).

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

e= mod NB, (3.30)

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

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

m' = mod NB. (3.31)

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

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

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

cBdB = k в+ 1.

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

B= (РB- 1)(QB -1)=,

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

т’= mod NB =m.

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

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

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

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

Односторонняя функция у=xd 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; Просмотров: 1533; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.026 сек.