Информационная безопасность. Макаренко С.И. - 126 стр.

UptoLike

ВУЗ: 

МГГУ им. Шолохова | Москва

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

Рубрика: 

126
В качестве первого примера однонаправленной функции рассмотрим
целочисленное умножение. Прямая задача - вычисление произведения двух
очень больших целых чисел Р и Q, т.е. нахождение значения
N = P∙Q,
является относительно несложной задачей для ЭВМ.
Обратная задача-разложение на множители большого целого числа, т.е.
нахождение делителей Р и Q большого целого числа N = P∙Q, является
практически неразрешимой задачей при достаточно больших значениях N.
По современным оценкам теории чисел при целом N ≈ 2
664
и Р ≈ Q для
разложения числа N потребуется около 10
23
операций, т.е. задача
практически неразрешима на современных ЭВМ.
Следующий характерный пример однонаправленной функции - это
модульная экспонента с фиксированными основанием и модулем. Пусть А и
N-целые числа, такие, что 1≤A<N. Определим множество Z
N
:
Z
N
= {0,1, 2, … , N-1}.
Тогда модульная экспонента с основанием А по модулю N
представляет собой функцию
f
A.N
: Z
N
→ Z
N
,
f
A.N
(x) = A
x
mod N,
где Х- целое число, 1 < х < N-1; операция i mod j - остаток от целочисленного
деления i на j.
Существуют эффективные алгоритмы, позволяющие достаточно
быстро вычислить значения функции f
A,N
(x).
Если у = А
х
, то естественно записать х = log
A
(y).
Поэтому задачу обращения функции f
A,N
(x) называют задачей
нахождения дискретного логарифма или задачей дискретного
логарифмирования.
Задача дискретного логарифмирования формулируется следующим
образом. Для известных целых A, N, у найти целое число х, такое, что
А
х
mod N = у.
Алгоритм вычисления дискретного логарифма за приемлемое время
пока не найден. Поэтому модульная экспонента считается однонаправленной
функцией.
По современным оценкам теории чисел при целых числах А≈2
664
и
N≈2
664
решение задачи дискретного логарифмирования (нахождение
показателя степени х для известного у) потребует около 10
26
операций, т.е. 
      В качестве первого примера однонаправленной функции рассмотрим
целочисленное умножение. Прямая задача - вычисление произведения двух
очень больших целых чисел Р и Q, т.е. нахождение значения

                                     N = P∙Q,

является относительно несложной задачей для ЭВМ.
      Обратная задача-разложение на множители большого целого числа, т.е.
нахождение делителей Р и Q большого целого числа N = P∙Q, является
практически неразрешимой задачей при достаточно больших значениях N.
По современным оценкам теории чисел при целом N ≈ 2664 и Р ≈ Q для
разложения числа N потребуется около 1023 операций, т.е. задача
практически неразрешима на современных ЭВМ.
      Следующий характерный пример однонаправленной функции - это
модульная экспонента с фиксированными основанием и модулем. Пусть А и
N-целые числа, такие, что 1≤A

Страницы