Использование односторонней функции для решения задач

Сравнение вычислений прямой и обратной функций

Эффективное возведение в степень.

Сначала кажется, что для возведения в степень a^x требуется (x-1) умножение. Действительно a¹⁶ = a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*- 15 умножений. Однако a¹⁶ = (((a²) ²) ²) ²– 4 умножения. Для эффективного возведения в степень предлагается следующий алгоритм.

1. Представить степень х как двоичное число с разрядами x_i={0,1}, т.е. x=(х_tx_{t 1}…x₁x₀)₂. Тем более, что число х в компьютере уже хранится в двоичном виде.

2. Вычислить а, а², а⁴, а⁸, а¹⁶, а³²,…,а^2t. Здесь t умножений. t< log₂p.

3. Вычислить произведение тех степеней а²ⁱ, для которых x_i=1. a^x=П а²ⁱ_{│ xi=1}. Здесь меньше или равно t умножений.

Число умножений при эффективном возведении в степень не превосходит 2*log₂p (a^xmodp, x<p).

Для вычисления дискретного логарифма одним из самых быстрых методов является метод “шаг младенца-шаг великана”. Он позволяет найти дискретный логарифм за 2 умножений. Покажем, что для больших чисел pвычислениеобратной функции по сравнению с вычислением прямой функции происходит значительно труднее. Т.е. функция y=a^xmod p является односторонней. Составим следующую таблицу.

Табл. 7.1.

Количество десятичных цифр в числе р	Количество умножений для вычисления прямой функции, 2*log2p	Количество умножений для вычисления обратной функции, 2*
	2*40=80	2*10^6
	2*200=400	2*10^30
	2*300=600	2*10^45

90 десятичных цифр соответствует 298 двоичным цифрам или 37 символам.

Рассмотрим компьютер, который способен умножить два 90-значных числа за 10^-14 секунды или 100 триллионов пар чисел за одну секунду. Таких компьютеров пока не существует.

Тогда прямая функция вычисляется за t_пр = 600*10^-14 = 6*10^-12секунд.

Обратная функция вычисляется за t_обр = 2*10⁴⁵*10^-14 =2*10³¹секунд = 10²²лет.

Видно, что вычисление обратной функции для 90-значных десятичных чисел (37-символьных паролей) практически невозможно.

Расскажем, как решаются поставленные в пункте 7.1 задачи.

1) Хранение паролей в компьютере.

Идея состоит в том, чтобы пароли в явном виде вообще не хранить в компьютере. Пусть имя пользователя «Конфета», а пароль «Тузик». Компьютер рассматривает слово «Тузик» как число «х» и вычисляет y=a^xmod p, где «а» и «р» известные всем числа. После первого ввода в памяти компьютера заводится пара («Конфета»;у). При дальнейших входах после ввода пары («Конфета»; «Тузик») компьютер вычисляет «у _новое» и сравнивает с хранящимися у него в памяти. Если у _новое=у, то это легальный пользователь. Злоумышленник может прочитать «у» и попытаться по нему вычислить пароль «х», но для 37-символьных паролей на это уйдет 10²² лет.

2) Банк-клиент.

Здесь имеется два варианта.

Вариант а. Пусть клиент банка имеет секретное имя «Титан», известное только банку и клиенту. Клиент посылает финансовый документ в 11.56 12 октября 2012 года. Компьютер клиента формирует слово «Титан 11561210 2012», рассматривает его как число «х», вычисляет y=a^xmod p, посылает «у» в банк по телефону. Банк вычисляет соответствующие «у» для всех зарегистрированных клиентов (с учетом времени). Если полученный от клиента «у» совпадает с одним из вычисленных, то клиент свой. Если клиент свой, то банк принимает сопутствующий финансовый документ.

Противник не может взломать эту систему, т.к.:

1) он не знает секретного слова «Титан»,

2) он не может найти его по перехваченному «у», т.к. это практически невозможно,

3) он не может скопировать «у» и повторить, т.к. время все же разное и от одного клиента поступают разные «у».

У этого варианта есть проблемы:

· требуется точная синхронизация часов клиента и банка. Решается приемом меток мирового времени.

· Противник может перехватить «у» и повторить его в течение одной минуты.

· Клиент посылает «у» в конце 56 минуты, а банк получает его в начале 57-й.

Вариант б. Пусть имеется дополнительный открытый канал связи от банка к клиенту, та же самая телефонная сеть. Каждый клиент имеет секретное имя, например, «Титан». Получив сигнал клиента о необходимости связи, банк посылает ему случайное слово «а» (вызов). Клиент вычисляет y=a^xmod p, где х = «Титан», и посылает «y» в банк. Банк проводит те же вычисления для всех зарегистрированных клиентов и сравнивает вычисленные «у» с полученным. Здесь не нужно синхронизировать часы. Противник не может повторить «у», т.к. вызов «а» все время разный. Противник не может вычислить «у», т.к. не знает «х». Противник не может вычислить секретный «х» по известным ему «a,p,y».

3) Свой-чужой самолет.

Решается аналогично второй задаче. Оба рассмотренных варианта формирования пароля применяются в реальных системах «свой-чужой». В решении Банк заменяется на ПВО, Клиент заменяется Самолетом, Телефон – воздушной средой.

Вариант а. Пусть свой самолет имеет свое секретное имя, например, «Орел», известное только ПВО и самолету. Самолет приближается к границе в 17.35 31\03\2012. Бортовой компьютер формирует слово «Орел 17 35 31 03 2012», рассматривает его как число х, вычисляет y=a^xmod p, посылает у на ПВО. ПВО вычисляет соответствующие удля всех зарегистрированных самолетов (с учетом времени). Если полученный у совпадает с одним из вычисленных, то самолет свой. Противник не может взломать эту систему, т.к.:

1) он не знает секретного слова «Орел».

2) он не может найти его по перехваченному у, т.к. это практически невозможно.

3) он не может скопировать у и повторить, т.к. время все же разное.

У этого варианта есть проблемы:

1) Требуется точная синхронизация часов самолета и ПВО.

2) Противник может перехватить у и повторить его в течение одной минуты.

3) Самолет посылает «у» в конце 35 минуты, а ПВО получает его в начале 36минуты.

Вариант б. Вариант возникает при наличии дополнительного открытого канала связи от ПВО к самолету. Каждый свой самолет имеет секретное имя, например, «Орел». Обнаружив самолет, ПВО посылает ему случайное слово «а» (вызов), самолет вычисляет y=a^xmod p, где х = «Орел», и посылает на ПВО. ПВО проводит те же вычисления для всех своих самолетов и сравнивает вычисленное«у» с полученным. Здесь не нужно синхронизировать часы. Противник не может повторить у, т.к. вызов а все время разный. Противник не может вычислить секретный х по известным ему a,p,y.

Задача «свой-чужой» была исторически первой, где использовались односторонние функции.

Дата добавления: 2014-01-04