Математические основы защиты информации. Ишмухаметов Ш.Т - 70 стр.

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Методы, основанные на задаче дискретного логарифмирования 71
Пример 2. Примером односторонней функции может служить
вычисление функции f(x) = a
x
mod n , где a и n - некоторые
фиксированные натуральные числа. Задача вычисления обратного значения
x по известному f(x) называется задачей дискретного логарифмирования.
На вычислительной сложности задачи дискретного логарифмирования
основан один из распространенных методов двухключевой криптографии -
метод Эль-Гамаля.
Пример 3. Функция f(k) = [k]P вычисления кратного точки p
эллиптической кривой: даны конечное поле GF
q
, эллиптическая кривая E
над полем GF
q
, точка P на кривой E . По известным координатам точки
P и аргументу k функция f вычисляет координаты т. [k]P . Эта задача
полиномиально вычислима.
Обратная задача нахождения координат т.P по известным k и
координатам т.[k]P является вычислительно сложной задачей, имеющей
субэкспоненциальный алгоритм вычисления.
Пример 4. Примером использования односторонней функции
может служить следующая схема аутентификации. Абоненты A и B
договариваются при встрече или вырабатывают с помощью протокола
Диффи- Хеллмана общий ключ x. Теперь когда абоненты выходят на связь,
то один из них, скажем A, посылает другому послание M , некоторое число
k > 2 и число y , равное результату применения к аргументу x k -кратной
итерации односторонней функции f(x):
y = f
(k)
(x) = f(f( . . . (x) . . .)
Абонент В, получив число k, также вычисляет значение y = f
(k)
(x)
и сравнивает его с полученным. Если результат совпал, то сообщение М
получено именно от абонента A. Абонент B , возвращая ответное послание
М
2
, прикладывает к нему значение y
k−1
= f
(k−1)
(x). Взломщик не может
подделать сообщение y
k−1
, т.к. даже зная f
(k)
(x), он не может вычислить
y = f
(k−1)
(x). При следующем обмене пересылается число y
k−2
= f
(k−2)
(x),
и т.д., что обеспечивает взаимную аутентификацию при каждом новом сеансе
связи.
Методы, основанные на задаче дискретного логарифмирования                71

         Пример 2. Примером односторонней функции может служить
вычисление функции f (x) = ax mod n , где a и n - некоторые
фиксированные натуральные числа. Задача вычисления обратного значения
x по известному f (x) называется задачей дискретного логарифмирования.
На вычислительной сложности задачи дискретного логарифмирования
основан один из распространенных методов двухключевой криптографии -
метод Эль-Гамаля.

         Пример 3. Функция f (k) = [k]P вычисления кратного точки p
эллиптической кривой: даны конечное поле GFq , эллиптическая кривая E
над полем GFq , точка P на кривой E . По известным координатам точки
P и аргументу k функция f вычисляет координаты т. [k]P . Эта задача
полиномиально вычислима.
         Обратная задача нахождения координат т.P по известным k и
координатам т.[k]P является вычислительно сложной задачей, имеющей
субэкспоненциальный алгоритм вычисления.

         Пример    4. Примером использования односторонней функции
может служить следующая схема аутентификации. Абоненты A и B
договариваются при встрече или вырабатывают с помощью протокола
Диффи- Хеллмана общий ключ x. Теперь когда абоненты выходят на связь,
то один из них, скажем A, посылает другому послание M , некоторое число
k > 2 и число y , равное результату применения к аргументу x k -кратной
итерации односторонней функции f (x):

                         y = f (k) (x) = f (f ( . . . (x) . . .)

         Абонент В, получив число k, также вычисляет значение y = f (k) (x)
и сравнивает его с полученным. Если результат совпал, то сообщение М
получено именно от абонента A. Абонент B , возвращая ответное послание
М2 , прикладывает к нему значение yk−1 = f (k−1) (x). Взломщик не может
подделать сообщение yk−1 , т.к. даже зная f (k) (x), он не может вычислить
y = f (k−1) (x). При следующем обмене пересылается число yk−2 = f (k−2) (x),
и т.д., что обеспечивает взаимную аутентификацию при каждом новом сеансе
связи.

Страницы