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

Определение 3: функция называется отображением в себя, если каждый элемент области значений 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, а областью ее значений – множество Х.

f: X ->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

f: S->S
Рис. 2. Инволюция f для множества S = {1,2,3,4,5}
На рис. 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
,

Арифметика вычетов
a≡b (mod n), если a = b+kn для некоторого целого k. Если а неотрицательно и 0

(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) 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 метод Монтгомери, алгоритм Баррета.

Операция, обратная возведению в степень по модулю 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 и Aj хотят установить между собой криптосвязность для обмена секретными сообщениями, то корреспондент Ai , имея свой секретный ключ xi и открытый ключ yj корреспондента Aj вычисляет Kij=yxj mod p Корреспондент A j по своему секретному ключу xj и открытому ключу yi корреспондента Ai вычисляет Kji аналогичным образом: Kji=yxi mod p. Покажем, что, имея разную ключевую информацию, корреспонденты сформировали одинаковые ключи:
В силу коммутативности операции возведения
,
.

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

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

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

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

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

Однонаправленная функция РША с потайным ходом
В 1978 году была предложена первая однонаправленная функция с потайным ходом, положенная в основу широко используемой на практике несимметричной криптографической системы РША. Первые буквы фамилий авторов - Р. Ривеста; А. Шамира и Л. Адлемана - образовали общепринятое название предложенной ими функции и криптосистемы. Для описания направленной функции РША с потайным ходом требуются некоторые знания из элементар-ной теории чисел. Пусть НОД(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