Принципы построения функций, используемы в криптографических системах

множествами X и Y и правилом, которое назначает каждому элементу

из множества X один элемент из множества Y.
Множество X называется областью определения функции и множе-ство Y - областью ее значений. Если элемент х∈ Х, то образом дан-ного элемента является элемент из множества Y: у =f(x) , где у ∈ Y. Соответственно, прообразом у является элемент х ∈ Х, для которого выполняется у = f(x) . Обычно записывают, что функция f, отобража-ющая элементы из множества X в множество У есть : X -> Y. Множество всех элементов из У, имеющих хотя бы один прообраз, называется образом функции а и обозначается Im(f)=Y.
Определение 2: функция называется однозначной (отображением один в один), если каждый элемент из множества Y является образом не более одного элемента из множества X. Пример – гипербола y=1/x

области значений Y есть образ по крайней мере одного элемента

области определения.
Например, функция f: X -> Y есть отображение в себя, если множество всех образов совпадает с областью значений данной функции: Im(f) = Y. Пример-парабола у=х3-7х+6
Определение 4: функция называется биекцией, если она является однозначной и Im(f) = Y .Пример-парабола y=x3
Определение 5: если функция f является биекцией X в Y, то существует простой способ вычислить биекцию Y в X следующим образом: для каждого у∈ Y определяют значение функции g(у)=x, где х∈ Х и f(x) = у.
Функция g, полученная из f, называется обратной функцией к f и обозначается g=f-1 .
Рассмотрим простой пример биективной функции и обратной к ней. Пусть множество Х= { а, Ь, с, d, е} и множество Y= { 1, 2, 3, 4, 5 } . Зададим функцию f: X ->Y графически (рис. 2.1). Легко убедиться, что данная функция биективная и что существует обратная к ней функция g=f-1. Областью определения функции g является множество Y, а областью ее значений – множество Х.

g:

Y-> X

Рис. 1. Биективная функция f и обратная к ней g=f-1

.

Существование обратной функции к функции шифрования является основой построения систем шифрования информации. Если биективную функцию использовать для шифрования сообщений из множества X в множество криптограмм У, то с помощью обратной функции можно однозначно дешифровать криптограммы в сообщения. Если функция шифрования не является биективной, то однозначное дешифрование невозможно (из криптограммы по обратному отображению восстанавливается несколько различных сообщений).

построения симметричных криптографических систем защиты информации. Такие функции называются инволюциями

и существуют при условии, что область определения X функции совпадает с областью ее изменения Y, т. е. Х=Y = S.
Определение 6: пусть S есть конечное множество и функция f является биекцией, отображающей S в S (т. е. f : S ->S ). Функция f называется инволюцией, если f=f-1.
Из определения видно, что у инволюции совпадают не только область определения и область изменения функции, но и обратная функция с прямой функцией. Поэтому если множество сообщений совпадает с множеством криптограмм, то при использовании инволюции функция шифрования совпадает с функцией дешифрования, что очень удобно при построении систем шифрования информации. Следовательно, последовательное применение сначала функции шифрования, а затем функции дешифрования к произвольному сообщению x ∈ S однозначно восстанавливает данное сообщение: f(f(x))=x

рис. 2 показан простой пример инволюции f для множества S

= { 1,2,3,4,5 }. Легко убедиться, что четное число последовательных при­менений инволюции f восстанавливает любой зашифрованный элемент x множества S. Пример – побитовая функция ХОR (⊕), т.е.f(x)=x ⊕ a, где a=const, тогда f(f(x))=(x ⊕ a) ⊕ a = x

которые в общем случае не являются биективными.
Определение7: однонаправленная функция есть

такая функция f для которой для каждого х из области ее определения X вычислительно просто определить значение функции у = f(x), но практически для всех у из области Y функции, вычислительно невозможно отыскать любое х такое, что у =f(x).
Принципиальным условием однонаправленности функции является сложность (невозможность) вычисления обратного преобразования к ней. Обратное преобразование к ОНФ может существовать, но не являться функцией в смысле определения 1. Обратное преобразование может быть также неоднозначным, то есть практически для всех у из области значений Y функции невозможно отыскать единственное значение х такое, что у = f(x) . Неоднозначность обратного преобразования означает, что допустимых значений х∈ Х может быть множество, и каждое из них удовлетворяет уравнению у = f(x).

выполнение прямого и обратного преобразований не обеспечивает взаимно однозначного соответствия

между элементами множеств X и Y. Примером существования неоднозначных обратных преобразований является функция y=x2 , для которой каждому образу y ∈ Y (исключая у=0) соответствуют два отличающиеся друг от друга прообраза xi и xj :

которых обратное преобразование существует и однозначно, но вычислительно нереализуемо. Такие

ОНФ называются вычислительно необратимыми функциями.
В качестве примера однонаправленной функции у = f(x) рассмотрим известную дискретную функцию дискретного возведе-ния в степень y=ax(mod p), где х - целое число от 1 до р -1 включительно, а вычисление производится по модулю р, где р - очень большое простое число; а - целое число (1 < а< p) степени которого a1,a2,…a p-1 , взятые по mod p , равняются в некотором порядке числам 1,2, ...,р -1. Такие значения а называются примитивными элементами. Напомним, что простым числом называется целое число, которое не делится ни на какие числа, кроме себя самого и единицы.
Например, при простом числе р = 7 можно выбрать примитивный элемент а=3 , т.к. a1 (mod 7)=3, a2 (mod 7)=2, a3 (mod 7)=6, a4 (mod 7)=4, a5 (mod 7)=5, a6 (mod 7)=1

,

целого k. Если а неотрицательно и 0

как остаток при делении а на n. Иногда b называют вычетом а по модулю n, иногда а называется конгруэнтным b по модулю n. Множество чисел от 0 до n-1 образует полное множество вычетов по модулю n. Это означает, что для любого целого а его остаток по модулю n является некоторым числом от 0 до n-1. Операция a mod n обозначает остаток от а , являющийся некоторым числом от 0 до n-1. Эта операция – приведение по модулю. 5 mod 3=2. n добавляется к результату операции получения остатка, если она возвращает отрицательное число. Арифметика остатков коммутативна, ассоциативна, дистрибутивна, кроме того, приведение каждого промежуточного результата по модулю n дает тот же результат, как и выполнение всего вычисления с последующим приведением конечного результата по модулю n.

mod n)) mod n
(a - b) mod n ==((a mod

n) - (b mod n)) mod n
(a * b) mod n ==((a mod n) * (b mod n)) mod n
(a *(b + c)) mod n ==(((a *b) mod n)+((a*c) mod n)) mod n
Арифметика вычетов легче реализуется на РС , т.к. она ограничивает диапазон промежуточных значений и результата – для k битовых вычетов n они будут не длиннее, чем 2 k бит. Вычисление степени числа по модулю другого числа представляет собой последователь-ность умножений и делений, и существуют приемы, ускоряющие эти действия. Например, аx mod n при х=8:
а*а*а*а*а*а*а*а mod n равноценно
((а2 mod n)2 mod n)2 mod n
Эффективные алгоритмы многократного приведения по модулю для одного n метод Монтгомери, алгоритм Баррета.

дискретный логарифм. Обратное число для 4 – ¼, т.к. 4*1/4=1.
4*х

=1 (mod 7) эквивалентно обнаружению целых x и k, таких, что 4х=7к+1,т.е. х такого, что 1=(а*х) mod n
Для вычисления обратных функций ( и НОД двух чисел) используется алгоритм Эвклида (300 лет д.н.э.+200). Алгоритм итеративен, Кнут показал, что среднее число делений равно: 0.843*log2(n) +1.47. Функция вида y=ax(mod p) вычисляется сравнительно просто, а обратная к ней функция вида y=loga y является вычислительно сложной практически для всех 1 < у < р при условии, что не только р велико, но и р-1 имеет большой простой множитель (лучше всего, если это будет другое простое число, умноженное на 2). Известно, что для дискретного возведения в степень ( требуется примерно 2log2p умножений и порядка 3log2p бит памяти, а для вычисления обратной функции (задача вычисле-ния дискретных логарифмов требуется не менее p1/2 операций и такое же количество бит памяти..

об субэкспоненциальной вычислительной сложности их выполнения, и при значениях р

длиною сотни и тысячи бит данные алгоритмы вычислительно нереализуемы Рассмотрим возможные варианты использования ОНФ:1. решение задачи обеспечения безопасности использования пароля, по которому осуществляется доступ пользователя к ресурсам и услугам в автоматизированных системах. Известно, что размещение в явном виде в памяти ЭВМ паролей доступа пользо-вателей небезопасно. Нарушитель, просмотрев файл паролей дос-тупа, способен выдать себя за любого законного пользователя системы; 2. задача аутентификации пользователей автоматизиро-ванной системы может быть эффективно решена с использованием ОНФ. В частности, безопасным решением этой задачи может быть размещение в доступном для просмотра злоумышленником блоке памяти автоматизированной системы не самих паролей, а значений ОНФ от паролей доступа. Пусть каждый пользователь случайно выберет свой секретный пароль х и вычислит значение y=ax(mod p)

в список паролей доступа в блок памяти ЭВМ. Законный пользователь

для получения доступа в автоматизированную систему предъявляет свое число х. ЭВМ вычисляет по этому числу значение однонаправленной функции и сравнивает с хранящимся значением у. При совпадении этих значений пользователь становится идентифицированным и получает требуемый доступ. Злоумышленник, узнавший у, не в состоянии вычислить х и тем самым получить доступ как законный пользователь к защищаемым ресурсам и услугам. Если злоумышленник способен подсмотреть ввод пароля законным пользователем, то значение х и соответст-вующее ему у должны меняться после каждого использования (пароль должен быть одноразовым). Очевидно, что знание злоумы-шленником некоторых значений функции и соответствующих им аргументов не должно облегчать ему задач вычисления пароля по известному значению функции. Другим примером использования данной ОНФ является криптосистема открытого распространения ключа В. Диффи и М. Хеллмана.

предварительного обмена секретной ключевой информацией. Пусть каждому корреспонденту сети известны

значения чисел а и р. Эта часть ключевой информа-ции является открытой, и допустимо ее знание нарушителем.
Каждый корреспондент, например, корреспондент Ai, независимо от других случайно и равновероятно выбирает себе число xi из множества целых чисел 1,2. . ,р-1. Значение xi является индивиду-альным секретным ключом корреспондента Ai вычисляет свой открытый ключ yi =ax (mod p) и помещает число yi в открытый заве-ренный справочник, доступный всем для чтения и защищенный от подмены. Точно так же каждый корреспондент Aj сети выбирает свой секретный ключ xj вычисляет открытый ключ yj =ax (mod p) и открыто публикует его

между собой криптосвязность для обмена секретными сообщениями, то корреспондент Ai

, имея свой секретный ключ xi и открытый ключ yj корреспондента Aj вычисляет Kij=yxj mod p Корреспондент A j по своему секретному ключу xj и открытому ключу yi корреспондента Ai вычисляет Kji аналогичным образом: Kji=yxi mod p. Покажем, что, имея разную ключевую информацию, корреспонденты сформировали одинаковые ключи:

В силу коммутативности операции возведения

,

.

корреспонденты могут затем использовать как ключ шифрова-ния передаваемых друг другу

секретных сообщений. Для определе-ния ключа Kij нарушитель должен решить задачу вычисления дискретного логарифма, например, вычисляя xi=logayi , что при соответствующем выборе размерности параметра p может быть сделано вычислительно нереализуемым. Используемая в криптосис-теме открытого распространения ключей Диффи Хеллмана однонаправленная функция не имеет вычислительно простого обратного отображения даже для законных пользователей, знающих секретную ключевую информацию. Однонаправленные функции, не имеющие и не требующие вычислительно простого обратного отображения для законных пользователей, широко применяются в таких криптографических задачах, в которых используется необра-тимое преобразование некоторых данных. Наиболее часто встречае-мой задачей такого типа является формирование в шифрообразую-щем устройстве из сравнительно коротких ключей значительно более длинных шифрующих последовательностей, используемых для криптографической защиты сообщений.

является основой построения поточных шифраторов. Стойкость данного типа систем шифрования

в основном определяется вычислительной сложностью нахождения нарушителем обратного отображения к функции формирования шифрующей последовательности. Кроме однонаправленных функций, не имеющих вычислительно простого обратного отображения даже для законных пользователей, знающих секретную ключевую информацию, в криптографии широко используются однонаправленные функции, для которых знание секретного ключа дает возможность законному пользователю вычислительно просто находить обратное отображение. Такие ОНФ получили название однонаправленных функций с потайным ходом, иногда их называют однонаправленными функциями с лазейкой.).

потайным ходом есть однонаправленная функция fz с дополнительным свойством, называемым

“потайным ходом", таким, что, зная информацию z потайного хода для каждого y∈Im(f) , вычислительно просто определить х∈ Х, удовлетворяющее уравнению y = fz(x). Для нарушителя, не знающего информации z потайного хода, нахождение обратного отображения x=fz-1(y) может быть сделано вычислительно нереализуемым. Поэтому информация z может служить секретным ключом законного пользователя ОНФ с потайным ходом.
Стремительное развитие криптографии в последние два десятиле-тия во многом стало возможным благодаря открытию американс-кими учеными В.Диффи и М. Хэллманом однонаправленных функций с потайным ходом, которые используются для различных криптосистем защиты информации.

аутентификации информации в условиях взаимного недоверия корреспондентов системы шифрования информации,

в которых отправители сообщений могут пользоваться несекретными ключами шифрования, криптосистемы обмена секретной ключевой информации по открытым каналам связи и многие другие криптосистемы, существование которых было невозможным до появления рассматриваемых криптографических функций. Оценивая стойкость криптосистем, построенных на основе известных однонаправленных функций с потайным ходом, отметим, что ни одна из них не является безусловно стойкой Это объясняется тем, что нарушитель с бесконечными вычислительны-ми ресурсами способен вычислить обратное отображение к таким функциям Однонаправленные функции с потайным ходом относятся к вычислительно необратимым функциям.
Определение 9: функция вычислительно необратима, если не существуют алгоритмы нахождения обратного отображении к ней с полиномиальной вычислительной сложностью.

функции с произвольно большой сложностью Поэтому стойкость произвольных криптосистем на

основе однонаправленных функций с потайным ходом заведомо ниже безусловно стойкой и может быть оценена не выше вычислительно стойкой.

предложена первая однонаправленная функция с потайным ходом, положенная в основу

широко используемой на практике несимметричной криптографической системы РША. Первые буквы фамилий авторов - Р. Ривеста; А. Шамира и Л. Адлемана - образовали общепринятое название предложенной ими функции и криптосистемы. Для описания направленной функции РША с потайным ходом требуются некоторые знания из элементар-ной теории чисел. Пусть НОД(I,n) означает наибольший общий делитель целых i и n. Для каждого положительного целого числа п функция Эйлера Ф(n) определяется как число положительных целых чисел i, не превосходящих n и таких, что НОД(i,n)=1. Если для целых чисел i и n выполняется НОД(i,n)=1, то такие числа называются взаимно простыми числами, т.е. они не имеют никаких общих делителей, кроме единицы. Очевидно, что для i простого числа p все числа, меньшие его, являются взаимно простыми с ним и значение функции Эйлера: Ф(p)=p-1 (2.8) Соответственно для произведения n=pq для двух неравных простых чисел p и q

удовлетворяющего условиям 0

число d такое, что 0de=1 (modФ(n)) (2.10) Однонаправленная функция РША с потайным ходом определяется как дискретное возведение значения х в степень ключа е
fz (x): y=xe(mod n) (2.11) где x есть положительное целое число, не превосходящее n (0<еf-1z ( y): x=yd(mod n) (2.12) где значение d есть единственное положительное целое, меньшее Ф(п) и удовлетворяющее условию
de=1(mod Ф(n))