6.5. Алгоритмы с открытыми ключами
Термин “открытые ключи” появился в криптографии после того, как два американских ученых Мартин Хеллман (Martin Hellman) , Уитфилд Диффи (Whitfield Diffie) опубликовали свою знаменитую статью “Новые направления в криптографии“ в 1976 году [Dif76].
6.5.1.Основные принципы
Диффи и Хеллман сформулировали оосновные принципы построения криптографических систем с открытыми ключами:
- вычисление пары открытого и закрытого (E, D) ключей на основе некоторого начального условия должно быть простым;
- зная открытый ключ E и открытый текст M, легко вычислить значение криптограммы C;
- зная секретный ключ D и значение криптограммы C, можно легко расшифровать сообщение и получить открытый текст M;
- зная только открытый ключ E, невозможно вычислить парный ему секретный ключ D;
- зная только значение открытого ключа E и криптограмму C невозможно восстановить открытый текст М.
Односторонние функции
В основе алгоритмов с открытыми ключами лежит понятие односторонних функций с потайным ходом. У таких функций очень легко вычислить их значение по известному аргументу, но совершенно невозможно определить аргумент, если известно только значению функции. Определить аргумент можно, если известна некоторая секретная дополнительная информация, называемая потайным ходом. Таким образом, любой может вычислить значение односторонней функции, то есть выполнить процедуру шифрования. Обратную процедуру расшифрования и определения исходного аргумента функции, может выполнить только тот, кто знает секретную информацию, то есть ключ расшифрования. За годы развития криптографии с открытыми ключами предлагались различные варианты односторонних функций, на основе которых можно было бы разрабатывать криптоалгоритмы. Однако с течением времени выделились следующие три основные задачи:
· факторизация;
· дискретное логарифмирование в конечном поле;
· дискретное логарифмирование в группе точек эллиптической кривой (ЭК), определенной в конечном поле.
Факторизация
Легко вычислить Z=X*Y, но сложно найти X и Y из Z.
Дискретное логарифмирование
Легко вычислить Z=Yx (mod n), но сложно найти Y из Z и x.
Дискретное логарифмирование на эллиптической кривой
Легко вычислить точку Z=x*Y, но сложно найти x из Y из Z.
6.5.2.Алгоритм шифрования RSA
В 1978 г. была предложена и опубликована наиболее известная и распространенная на сегодняшний день криптосистема с открытыми ключами RSA. Название системы образовано по первым буквам ее разработчиков Ривеста, Шамира и Адлемана (Rivest, Shamir, Adleman). Алгоритм RSA может использоваться для шифрования данных и для электронной цифровой подписи.
Рассмотрим схему шифрования RSA:
Генерация параметров
p, q - большие простые числа
n=p*q - модуль шифрования
(n)=(p-1)(q-1) - функция Эйлера
Открытый ключ e выбирается из интервала 1<e<n. Числа e и n должны быть взаимно простыми.
Секретный ключ d вычисляется по расширенному алгоритму Евклида: ed=1 (mod (n))
Операция шифрования исходного сообщения m:
c = me (mod n)
Операция расшифрования:
m=cd (mod n)
Секретные значения: p, q, d
Открытый ключ: e
Рассмотрим конкретный пример шифрования по RSA:
Генерация параметров
Пусть p=5 и q=11
n=p*q=5*11=55
(n)=(p-1)(q-1) = (5-1)(11-1)=4*10=40
Пусть открытый ключ e = 7
Тогда секретный ключ d=23
Операция шифрования исходного сообщения m=2:
c = 27 (mod 55) = 18
Операция расшифрования:
m=1823 (mod 55) = 2
Секретные значения: p=5, q=11, d=23
Открытый ключ: e=7
Считается, что надежность системы состоит в вычислительной сложности решения задачи факторизации больших чисел. Действительно, если разложить на множители значение модуля шифрования n, то можно определить числа p и q. Зная числа p и q можно вычислить секретный ключ. В таком случае возможно нелегальное прослушивание сетевого трафика, извлечение и расшифрование передающихся криптограмм.
Однако на существующем уровне развития вычислительной техники нет способа на практике эффективно раскладывать большие числа на множители. Под словом эффективно тут понимается полиномиальная зависимость времени работы от размера числа. Следует отметить, что с 1994 г. теоретически для квантового компьютера были предложены полиномиальные алгоритмы факторизации, а также решения некоторых других сложных проблем, включая задачу дискретного логарифмирования [Ман99]. Однако существующий уровень технологий все еще не позволяет полноценно использовать эти алгоритмы. Для обеспечения действительной и достаточно долгосрочной секретности сегодня на практике рекомендуется использовать числа размером от 1024 бит. Приведем в таблице зависимости требуемой производительности для осуществления успешной атаки на RSA в зависимости от размера модуля шифрования [Чмо2001].
|
Размер модуля шифрования, бит |
512 |
768 |
1024 |
1280 |
1536 |
2048 |
|
Производительность (M/Y) |
3*104 |
2*108 |
3*1011 |
1*1014 |
3*1016 |
3*1020 |
1 M/Y – год работы компьютера, который выполняет один миллион операций в секунду. Эквивалентной мощностью обладает, например, DEC VAX 11/780. Предполагается, что к 2004 г. вычислительный потенциал атаки со стороны некоторой крупной организации может достигнуть уровня до 108 M/Y, а к 2014 г. – до 1011 M/Y. Возможные атаки с привлечением вычислительных ресурсов компьютеров, подключенных к глобальной открытой сети, например к Интернет, достигнут еще большего уровня и составят в 2004 г. до 2*109 M/Y, а в 2014 г. – до 1013 M/Y.
В 2003 году известный ученый Ади Шамир, один из разработчиков RSA, вместе со своим коллегой Ираном Тромером, опубликовал работу [Sha03], в которой была предложена схема нового аппаратного устройства, получившего название TWIRL (The Weizmann Institute Relation Locator). Это устройство предназначено для разложения чисел на множители и, по сути, является специализированной интегральной схемой, выполненной по 0.13-микронной технологии. На данный момент разработана принципиальная схема устройства и оценена ориентировочная стоимость его создания. Ожидается, что стоимость реализации TWIRL для взлома шифра RSA с длиной ключа в 512 бит менее чем за 10 минут составит $10 000, а для 1024 бит за 1 год - $1 000 000. На практике схема TWIRL еще не реализована.