Слайд 1Асимметричные алгоритмы. Продолжение.
Слайд 2Предположим, что обоим абонентам известны некоторые два числа g и p
(например, они могут быть «зашиты» в программное обеспечение), которые не являются секретными и могут быть известны также другим заинтересованным лицам. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют большие случайные числа: первый абонент — число a, второй абонент — число b. Затем первый абонент вычисляет значение A = gamod p и пересылает его второму, а второй вычисляет B = gbmod p и передаёт первому. Предполагается, что злоумышленник может получить оба этих значения, но не модифицировать их (то есть у него нет возможности вмешаться в процесс передачи). На втором этапе первый абонент на основе имеющегося у него a и полученного по сети B вычисляет значение Bamod p = gabmod p, а второй абонент на основе имеющегося у него b и полученного по сети A вычисляет значение Abmod p = gabmod p. Как нетрудно видеть, у обоих абонентов получилось одно и то же число: K = gabmod p. Его они и могут использовать в качестве секретного ключа, поскольку здесь злоумышленник встретится с практически неразрешимой (за разумное время) проблемой вычисления gabmod p по перехваченным gamod p и gbmod p, если числа p,a,b выбраны достаточно большими.
Слайд 3При работе алгоритма, каждая сторона:
генерирует случайное натуральное число a — закрытый
ключ
совместно с удалённой стороной устанавливает открытые параметры p и g (обычно значения p и g генерируются на одной стороне и передаются другой), где
p является случайным простым числом
g является первообразным корнем по модулю p
вычисляет открытый ключ A, используя преобразование над закрытым ключом
A = ga mod p
обменивается открытыми ключами с удалённой стороной
вычисляет общий секретный ключ K, используя открытый ключ удаленной стороны B и свой закрытый ключ a
K = Ba mod p
К получается равным с обеих сторон, потому что:
Ba mod p = (gb mod p)a mod p = gab mod p = (ga mod p)b mod p = Ab mod p
В практических реализациях, для a и b используются числа порядка 10100 и p порядка 10300. Число g не обязано быть большим и обычно имеет значение в пределах первого десятка.
Слайд 4Алгоритм Диффи-Хеллмана работает на линиях связи, надежно защищенных от модификации. Однако,
в тех случаях, когда в канале возможна модификация данных, появляется очевидная возможность вклинивания в процесс генерации ключей "злоумышленника-посредника".
Для защиты используются различные варианты надежной аутитификации.
Атака с подставкой (Man-in-the-middle attack): Две стороны обмениваются ключами для секретной коммуникации. Противник внедряется между ними на линии обмена сообщениями. Далее противник выдает каждой стороне свои ключи. В результате, каждая из сторон будет иметь разные ключи, каждый из которых известен противнику. Теперь противник будет расшифровывать каждое сообщение своим ключом и затем зашифровывать его с помощью другого ключа перед отправкой адресату. Стороны будут иметь иллюзию секретной переписки, в то время как на самом деле противник читает все сообщения.
Одним из способов предотвратить такой тип атак заключается в том, что стороны при обмене ключами вычисляют криптографическую хэш-функцию значения протокола обмена (или по меньшей мере значения ключей), подписывают ее алгоритмом цифровой подписи и посылают подпись другой стороне. Получатель проверит подпись и то, что значение хэш-функции совпадает с вычисленным значением. Такой метод используется, в частности, в системе Фотурис (Photuris).
Слайд 5Криптографическая стойкость алгоритма Диффи — Хеллмана (то есть сложность вычисления K=gab
mod p по известным p, g, A=ga mod p и B=gb mod p), основана на предполагаемой сложности проблемы дискретного логарифмирования.
Слайд 6Схема Эль-Гамаля (Elgamal) — криптосистема, предложенная в 1984 году. Схема Эль-Гамаля
лежит в основе стандартов электронной цифровой подписи в США и России.
Схема Эль-Гамаля
Слайд 7Генерация ключей
Генерируется случайное простое число p длины n.
Выбирается произвольное целое
число g, являющееся первообразным корнем по модулю p.
Выбирается случайное число x из интервала (1,p).
Вычисляется y = gx mod p.
Открытым ключом является тройка (p,g,y),
закрытым ключом — число x.
Слайд 8Шифрование
Сообщение М шифруется так:
Выбирается случайное секретное число k из отрезка [1,
p-2].
Вычисляется a = gk mod p, b = yk M mod p,
где M — исходное сообщение.
Пара чисел (a,b) является шифротекстом.
Длина шифротекста в схеме Эль-Гамаля длиннее исходного сообщения M вдвое.
Дешифрование
Зная закрытый ключ x, исходное сообщение можно вычислить из шифротекста (a,b) по формуле:
При этом нетрудно проверить, что
и .
Слайд 9Криптостойкость данной схемы основана на вычислительной сложности проблемы дискретного логарифмирования, где
по известным p, g и y требуется вычислить х, удовлетворяющий сравнению:
Слайд 17коммутативный и ассоциативный законы
Слайд 29Квантовый объект:
1. Измерение изменяет состояния объекта.
2. Невозможно получить полную информацию
о квантовом объекте, и следовательно, невозможно его скопировать.
Слайд 31Идея использовать квантовые объекты для защиты информации от подделки и несанкционированного
доступа впервые была высказана Стефаном Вейснером (Stephen Weisner) в 1970 г.
Спустя 10 лет Беннет и Брассард, которые были знакомы с работой Вейснера, предложили использовать квантовые объекты для передачи секретного ключа. В 1984 г. они опубликовали статью, в которой описывался протокол квантового распространения ключа ВВ84.
Слайд 381989 г. В Уотсоновском исследовательском центре IBM Чарльзом Беннетом, Джилом Брасардом
и их студентами была построена первая система - 10 бит/с на расстоянии 30 см.
24.07.2009 Исследователи из Университета Женевы (University of Geneva) в Швейцарии и Corning Inc. продемонстрировали новый QKD-прототип, который может распределять квантовые ключи на расстоянии 250 км в лабораторных условиях.
20.04. 2010 Создана рекордно быстрая система распространения квантовых ключей со скоростью, превышающей 1 Мбит/с.
Экспериментальная реализация