Дискретная математика. Ерош И.Л - 131 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

131
Одна из идей криптографии с открытым ключом основана на трудно
стях логарифмирования сравнений. Так, если имеется равенство a
x
= b,
где a и b известны, и требуется найти x, то значение x находится элемен
тарно: x = loga/logb.
Если же имеется сравнение a
x
º b mod p, где известны a, b и p, то
для нахождения неизвестного x часто требуется произвести полный пе
ребор.
В классической (симметричной) криптографии важной является
проблема распределения ключей. Она частично решается с использо
ванием так называемого несимметричного шифрования. Когда были
опубликованы результаты по системам с открытым распределением
ключей, большинству специалистов это показалось фантастикой. Два
абонента, обмениваясь некоторыми данными по открытой сети, пере
давали секретные сообщения друг другу или вырабатывали общий
ключ для его применения в системах симметричного шифрования. Пе
реворот в криптографии был произведен с использованием модульной
арифметики (теории чисел). Позже появились аналогичные системы:
RSA [2], ElCamal, алгоритмы шифрования на эллиптических кривых
и некоторые другие.
Двухступенчатая передача сообщений с использованием
модульной арифметики
Сообщение может быть передано непосредственно от А к В за не
сколько шагов при использовании очень больших модулей.
Рассмотрим сначала случай, когда по открытому каналу Алиса и
Боб договариваются использовать для шифрования своих сообщений
некоторое очень большое простое число P. Пусть, например, P имеет
100 десятичных знаков. Тогда Алиса может зашифровать сообщение
m возведением в некоторую степень x, известную только ей, и передать
Бобу. Боб может возвести полученное сообщение в степень y, извест
ную только ему, и возвратить Алисе. Алиса «снимет» свою степень x
и передаст сообщение Бобу. Боб «снимет» свою степень y и прочитает
сообщение. Общая схема выглядит следующим образом.
Алиса берет сообщение m, которое хочет передать Бобу, возводит в
некоторую степень x, при этом (x, P–1) = 1, т. е. x и P–1 взаимно про
стые числа:
m
x
º S
1
mod P
и передает S
1
Бобу. Боб возводит S
1
в некоторую степень y, (y, P–1) = 1:
1
Y
S
º m
xy
º S
2
mod P
и возвращает S
2
Алисе.

Страницы