<< Предыдущая

стр. 31
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

- генерируют случайный эфемерный ключ А:,
- вычисляют Ci — G^^
- находят С2 — тп • if ^,
- выдают получившийся шифротекст в виде пары С = (Ci, С2).
Заметим, что при каждом шифровании применяется свой кратко­
временный ключ. Поэтому, шифруя одно сообщение дважды, мы
получаем разные шифротексты.
Чтобы расшифровать пару данных С = (Ci, (72), производят сле­
дующие преобразования:

С2 _ m • Я^ _

_ m-G^_
- Qxk
— m.
Разберем небольшой пример, выбрав сначала параметры домена.
Пусть
Q = 101, Р = 809 и 0 = 3.
Легко проверить, что Q действительно делит число Р — 1, а порядок
элемента G в группе Fp делится на Q, Порядок элемента G равен
808, поскольку
3«°« = l ( m o d P ) ,
И ни при каких меньших степенях такого равенства не получается.
В качестве пары открытого и секретного ключа выберем
ж = 68 и Я = С ^ - 3 ^ ^ = 65 (modP).
Допустим, нам нужно зашифровать сообщение, численное предста­
вление которого равно т = 100. Поступаем следующим образом.
- Генерируем случайный эфемерный ключ к = 89,
- Находим Ci - G^ = 3^^ = 345 (modP).
- Получаем ^2 = m • Я^ - 100 • 65^^ = 517 (modP).
- Отправляем шифротекст С = (345,517).
Партнер сможет восстановить текст, делая также вычисления:

С1 34568
Глава 7. Основные алгоритмы шифрования с открытым ключом

Последнее равенство получается чуть более сложно, чем в веще­
ственных числах: сначала число 345 возводится в степень 68 по моду­
лю 809, вычисляется мультипликативный обратный к результату по
этому же модулю, а затем найденный обратный умножается на 517.
Позже мы увидим, что система Эль-Гамаль в том виде, о кото­
ром только что было рассказано, беззащитна против атак с выбором
шифротекста. Поэтому обычно применяют модифицированные схе­
мы шифрования. Тем не менее, Эль-Гамаль сможет выстоять против
атаки с выбором открытого текста, если считать, что задача Диф­
фи-Хеллмана трудна А^ля решения. Опять-таки, здесь мы исполь­
зуем наивное понятие криптостойкости алгоритма, считая, что си­
стема защищена, если противник не сможет обратить шифрующую
функцию.

Лемма 7.8. Если задача Диффи - Хеллмана трудноразрешима, то
система Эль-Гамаль защищена против атак с выбором открытого
текста, где защищенность означает, что нападающий не может вос­
становить открытый текст по перехваченной шифрограмме за ра­
зумное время.
Доказательство. Чтобы показать защищенность системы Эль-
Гамаль от атак с выбором открытого текста в предположении о
сложности задачи Диффи - Хеллмана, будем считать, что у нас есть
оракул (!?, вскрывающий шифр Эль-Гамаль. На вход оракула подает­
ся открытый ключ Н и шифротекст (Ci,C2), а выходными данны­
ми служит дешифрованный открытый текст. Покажем теперь, как
с помощью оракула решается задача Диффи - Хеллмана, т.е. даны
G^ и СУ,
и требуется вычислить G^^.
Выберем открытый ключ в системе Эль-Гамаль в соответствии
с поставленной задачей, т. е. положим


Заметим, что мы не знаем секретного ключа х. Теперь выписываем
«шифротекст»:
С = (СьС2),
где Ci = G^, а. С2 случайный элемент поля Fp. Вводим этот ши­
фротекст в оракул, взламывающий Эль-Гамаль, и получаем соот­
ветствующий открытый текст М = 0{H,{Ci,Q2))^ который по рас­
шифровывающей процедуре Эль-Гамаль должен получаться в виде
отношения М = ^ . Используя полученные данные, мож;но решить
1,5. Криптосистема Рабина

исходную задачу Диффи-Хеллмана, вычисляя
С2 _ М • Cf
[oyf = с'у.
М М



7.5. Криптосистема Рабина
Есть еще одна криптосистема, принадлежащая Рабину, которая
основывается на трудной проблеме факторизации больших целых
чисел. Более точно, она связана с трудностью извлечения квадрат­
ного корня по модулю составного числа N = р - q. Напомним, что
эти задачи эквивалентны, т. е.
- зная простые делители числа ЛГ, мы можем извлекать квадрат­
ные корни по модулю 7V,
- умея извлекать квадратные корни по модулю iV, мы в состоя­
нии разложить N на простые множители.
Потому такую систему можно считать в некотором отношении бо­
лее криптостойкой, чем RSA. Процесс шифрования в алгоритме Ра­
бина происходит намного быстрее, чем практически в любой дру­
гой криптосистеме с открытым ключом. Однако, несмотря на эти
преимущества, система Рабина используется все же реже, чем RSA.
Тем не менее, система Рабина важна как с исторической точки зре­
ния, так и в качестве наглядного примера криптосистемы, основные
идеи которой используются в протоколах более высокого уровня.
Выберем разные простые числа, удовлетворяющие условию:
pz= q = S (mod4).
Такой специальный вид простых чисел сильно ускоряет процедуру
извлечения корней по модулю р VL q. Секретным ключом системы
является пара (p^q). Для определения соответствующего открытого
ключа берут произведение N = р - q и генерируют случайное целое
число Б G {О, . . . , А — 1}. Отк{>ытый ключ — это пара
Г
iN,B).
Для шифрования сообщения т в алгоритме Рабина вычисляют
С = 7п{т + В) (modTV).
Таким образом, шифрование состоит из операций сложения и умно­
жения по модулю 7V, что обеспечивает более высокую скорость ши-
204 Глава 7. Основные алгоритмы шифрования с открытым ключом

фрования, чем в RSA^ даже если в последней выбирают небольшую
шифрующую экспоненту.
Расшифрование в этом алгоритме гораздо более сложное. По су-
ш;еству, нам нужно вычислить

т=^^ + С-^ (modiV).

На первый взгляд здесь не требуется никакой секретной инфор­
мации, но, очевидно, для извлечения корней по модулю N очень и
очень полезно знать разложение последнего на простые делители.
Поскольку N — произведение двух простых чисел, суш;ествует че­
тыре возможных квадратных корня из числа по модулю N. Поэто­
му при расшифровании получается четыре возможных открытых
текста. Чтобы выбор был более определенным, стоит к открытому
тексту добавлять некую избыточную информацию.
Объясним, почему при расшифровании мы действительно полу­
чаем т. Напомним, что шифротекст имеет вид
С = т(т + В) (modiV),
поэтому
/^2 + 4ш(т + В)
4"^ 2˜V 4 2
JAm? + АВт + В'^ В_
V 4 2"
/ ( 2 т + В)2 В
V 4 2
2т + В В
= т.
2 2
Конечно, здесь мы цредполагаем, что выбрали правильный корень
из четырех возможных.
Закончим главу примером шифрования в алгоритме Рабина. Пусть
открытые и секретные ключи имеют такой вид:
- р = 127 и 9 = 131,
- А = 1 6 6 3 7 и В = 12 345.
Г
Для шифрования сообщения т = 4410 вычисляем
С = т{т + В) (modN) = 4633.
При обратной операции сначала находим
Г = В^/4 + С (modiV) = 1500,
7.5. Криптосистема Рабина

а затем извлекаем квадратные корни из Т по модулю р и q:
Vf (modp) = ±22, Vf (modq) = ±37.
После этого, применяя Китайскую теорему об остатках к паре
±22 (modp) и ± 3 7 (mod9),
находим квадратный корень из Т по модулю N:
s = Vf (mod TV) = ±3705 или ± 14373.
Четыре варианта расшифрования
4410, 5851, 15078, или 16 519.
получаются из формулы
В 12 345
S—— —S .
2 2

К р а т к о е содерлсание главы

- Шифрование с открытым ключом требует односторонних функ­
ций, примерами которых служат факторизация чисел, извлече­
ние корней, дискретное логарифмирование и задача Диффи-
Хеллмана.
- Между этими задачами существуют связи, которые можно вы­
явить сведением одной задачи к другой.
- RSA — наиболее популярная криптосистема с открытым клю­
чом. Ее защищенность по вычислениям основывается на труд­
ности решения задачи RSA, которая близка проблеме факто­
ризации, но не совпадает с ней.
- Криптостойкость системы Эль-Гамаль зависит от трудности
решения задачи Диффи - Хеллмана.
- Криптостойкость алгоритма Рабина гарантируется сложно­
стью извлечения корней по составному модулю. Поскольку эта
задача полиномиально эквивалентна проблеме факторизации,
можно считать, что безопасность системы Рабина опирается
на проблему разложения на множители.

Дополнительная литература
Оригинальная статья Диффи и Хеллмана все еще остается самым
лучшим и быстрым введением в концепцию криптографии с откры­
тым ключом. Кроме того, можно посмотреть работы, касающиеся
Эль-Гамаль, RSA и системы Рабина.
Глава 7, Основные алгоритмы шифрования с открытым ключом

W. Diffie and М. Hellman. New directions in cryptography. IEEE Trans,
on Info. Theory, 22, 644-654, 1976.
T. ElGamal. A public key cryptosystem and a signature scheme based
on discrete logarithms. IEEE Trans. Info. Theory, 31, 469-472, 1985.
R.L. Rivest, A. Shamir and L.M. Adleman. A method for obtaining digi­
tal signatures and public-key cryptosystems. Comm. ACM, 21, 120-126,
1978.
M. Rabin. Digitized signatures and public key functions as intractable as
factorization. MIT/LCS/TR-212, MIT Laboratory for Computer Sci­
ence, 1979.

Контрольные вопросы
7.1.1. Что представляет собой самый быстрый на сегодняшний день
алгоритм разложения на множители?

7.1.2. В чем заключаются задачи факторизации, RSA и определе­
ния квадратичного вычета? Расположите эти проблемы в по­
рядке увеличения сложности.

7.1.3. Расскажите о проблеме дискретного логарифмирования и за­
дачах Диффи-Хеллмана. Расположите их в порядке увеличе­
ния сложности

7.1.4. Опишите алгоритм шифрования RSA.

7.1.5. Может ли шифрующая экспонента в системе RSA быть четной?

7.1.6. Обсудите утверждения:
(а) Информация о расшифровываюп];ей экспоненте в алго­
ритме RSA равносильна разложению модуля шифрования на
множители.
(б) Взлом алгоритма шифрования в RSA эквивалентен раз­
ложению на множители модуля шифрования.
7.1.7. В шифровании по алгоритму Эль-Гамаль присутствует эле­
мент случайности, что обеспечивает разные шифротексты
при шифровании одного сообщения дважды. Хорошо это или
плохо?

7.1.8. Расскажите о двух преимуществах, которые система Раби-
на имеет перед RSA. Имеет ли алгоритм Рабина какие-либо
недостатки?
7.5. Криптосистема Рабина

Лабораторные работы
7.2.1. Разработайте программы шифрования и расшифровывания
сообш;ений для алгоритмов Эль-Гамаль и Рабина. Какая из
них более эффективна при шифровании, а какая при обрат­
ной процедуре?

Упражнения
7.3.1. Пусть N — модуль шифрования алгоритма RSA и X{N) =
= НОК {р — l^q — 1). Докажите, что если Е — шифруюш;ая
экспонента алгоритма, то расшифровываюш;ую экспоненту d
можно выбрать так, чтобы
E-d=l (modA(iV)).

Указание. Покажите, что А(Л^) — максимальный порядок эле­
ментов группы (Z/iVZ)*.

7.3.2. Пусть N — модуль в RSA и X{N) = НОК {p-l,q- 1). Пред­
положим, что порядок шифруюш;ей экспоненты Е в группе
(Z/A(Ar)Z)* равен К. Покажите, что
трк

т — т (mod А/').
Выведите отсюда, что порядок элемента Е по модулю р — \
или q — \ должен быть большим.

7.3.3. Опишите схему шифрования Эль-Гамаль, основанную на эл­
липтических кривых.

<< Предыдущая

стр. 31
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>