|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Понятие однонаправленных функцийКонцепция асимметричных криптографических систем с открытым ключом основана на применении однонаправленных функций. Неформально однонаправленную функцию можно определить следующим образом. Пусть X и Y – некоторые произвольные множества. Функция f: X ® Y является однонаправленной, если для всех xÎX можно легко вычислить функцию y = f (x), где yÎY. И в то же время для большинства yÎY достаточно сложно получить значение xÎX, такое, что f (x)=y (при этом полагают, что существует по крайней мере одно такое значение x). Основным критерием отнесения функции f к классу однонаправленных функций является отсутствие эффективных алгоритмов обратного преобразования Y ® X. В качестве первого примера однонаправленной функции рассмотрим целочисленное умножение. Прямая задача – вычисление произведения двух очень больших целых чисел P и Q, т.е. нахождение значения N = P*Q, (6.1) является относительно несложной задачей для ЭВМ. Обратная задача – разложение на множители большого целого числа, т.е. нахождение делителей P и Q большого целого числа N = P*Q, является практически неразрешимой задачей при достаточно больших значениях N. По современным оценкам теории чисел при целом N»2664 и P»Q для разложения числа N потребуется около 1023 операций, т.е. задача практически неразрешима на современных ЭВМ. Следующий характерный пример однонаправленной функции – это модульная экспонента с фиксированными основанием и модулем. Пусть A и N – целые числа, такие, что 1£ А < N. Определим множество ZN: ZN = {0, 1, 2,..., N –1}. Тогда модульная экспонента с основанием А по модулю N представляет собой функцию fA,N : ZN ® ZN, fA,N (x) = Ax (mod N), (6.2) где X – целое число, 1£ x £ N –1. Существуют эффективные алгоритмы, позволяющие достаточно быстро вычислить значения функции fA,N (x). Если y = Ax, то естественно записать x = logA (у). Поэтому задачу обращения функции fA,N(x) называют задачей нахождения дискретного логарифма или задачей дискретного логарифмирования. Задача дискретного логарифмирования формулируется следующим образом. Для известных целых A, N, Y найти целое число X, такое, что Ax mod N = y. Алгоритм вычисления дискретного логарифма за приемлемое время пока не найден. Поэтому модульная экспонента считается однонаправленной функцией. По современным оценкам теории чисел при целых числах A» 2664 и N» 2664 решение задачи дискретного логарифмирования (нахождение показателя степени x для известного y) потребует около 1026 операций, т.е. эта задача имеет в 103 раз большую вычислительную сложность, чем задача разложения на множители. При увеличении длины чисел разница в оценках сложности задач возрастает. Следует отметить, что пока не удалось доказать, что не существует эффективного алгоритма вычисления дискретного логарифма за приемлемое время. Исходя из этого, модульная экспонента отнесена к однонаправленным функциям условно, что, однако, не мешает с успехом применять ее на практике. Вторым важным классом функций, используемых при построении криптосистем с открытым ключом, являются так называемые однонаправленные функции с "потайным ходом" (с лазейкой). Дадим неформальное определение такой функции. Функция f: X ® Y относится к классу однонаправленных функций с "потайным ходом" в том случае, если она является однонаправленной и, кроме того, возможно эффективное вычисление обратной функции, если известен "потайной ход" (секретное число, строка или другая информация, ассоциирующаяся с данной функцией). В качестве примера однонаправленной функции с "потайным ходом" можно указать используемую в криптосистеме RSA модульную экспоненту с фиксированными модулем и показателем степени. Переменное основание модульной экспоненты используется для указания числового значения сообщения M либо криптограммы C. Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.) |