Студопедия

КАТЕГОРИИ:


Архитектура-(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)

Первая система с открытым ключом - система Диффи-Хеллмана


 

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

Эта криптосистема была открыта в середине 70-х годов американскими учеными Диффи (Whitfield Diffie) и Хеллманом (Martm Hellman) и привела к настоящей революции в криптографии и ее практических применениях. Это первая система, которая позволяла защищать информацию без использования секретных ключей, передаваемых по защищенным каналам. Для того чтобы продемонстрировать одну из схем применения таких систем, рассмотрим сеть связи с N пользователями, где N - большое число. Пусть мы хотим организовать секретную связь для каждой пары из них. Если мы будем использовать обычную систему распределения секретных ключей, то каждая пара абонентов должна быть снабжена своим секретным ключом, т.е. всего потребуется ключей.

Пусть строится система связи для абонентов А,В,С,….У каждого абонента есть своя секретная и открытая информация. Для организации этой системы выбирается большое простое число р и некоторое число g, 1<g<р-1, такое, что все числа из множества {1,2,…,р-1} могут быть представлены как различные степени g mod p (известны различные подходы для нахождения таких чисел g, один из них будет представлен ниже). Числа р и g известны всем абонентам.

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

(3.9)

В результате получаем следующую таблицу.

Таблица 3.2

Ключи пользователей в системе Диффи—Хеллмана

Абонент Секретный ключ Открытый ключ
А В С ХА ХB Хс YA Yb Yc

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

ZAB = (YB)mod p (3.10)

(никто другой кроме А этого сделать не может, так как число Ха секретно). В свою очередь, абонент В вычисляет число

ZBA = (Ya)mod p. (3.11)

Утверждение 3.2.Zab = Zba

Доказательство. Действительно,

Zab = (YB) mod p = (g)mod p = gmod p = (YA) mod p = ZBA.

(Здесь первое равенство следует из (3.10), второе и четвертое - из (3.9), последнее - из (3.11).).

Отметим главные свойства системы:

1) абоненты А и В получили одно и то же число Z = ZAB — ZBA , которое не передавалось по открытой линии связи;

2) Ева не знает секретных чисел ХA, ХB,, поэтому не может вычислить число ZAB (вообще говоря, она могла бы попытаться найти секретное число ХA по YB ), однако при больших р это практически невозможно (требуются миллионы лет)).



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

Остановимся теперь на упомянутой выше задаче выбора числа g. При произвольно заданном р она может оказаться трудной задачей, связанной с разложением на простые множители числа р-1. Дело в том, что для обеспечения высокой стойкости рассмотренной системы число р-1 должно обязательно содержать большой простой множитель (в противном случае алгоритм Полига-Хеллмана быстро вычисляет дискретный логарифм). Поэтому часто рекомендуют использовать следующий подход. Простое число р выбирается таким, чтобы выполнялось равенство

p=2q+1,

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

1<g<р-1 и gq mod р 1.

<== предыдущая лекция | следующая лекция ==>
Предыстория и основные идеи | Элементы теории чисел

Дата добавления: 2014-01-11; Просмотров: 239; Нарушение авторских прав?;


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



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

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