Содержание
- 2. Определение 3: функция называется отображением в себя, если каждый элемент области значений Y есть образ по
- 3. f: X ->Y g: Y-> X Рис. 1. Биективная функция f и обратная к ней g=f-1
- 4. Среди биективных функций есть класс функций, наиболее часто используемый для построения симметричных криптографических систем защиты информации.
- 5. f: S->S Рис. 2. Инволюция f для множества S = {1,2,3,4,5} На рис. 2 показан простой
- 6. ОДНОНАПРАВЛЕННЫЕ ФУНКЦИИ Особую роль в криптографии играют однонаправленные функции (ОНФ), которые в общем случае не являются
- 7. Для выяснения неоднозначности обратного преобразования конкретной функции необходимо убедиться, что выполнение прямого и обратного преобразований не
- 8. . Для построения криптографических систем зашиты информа-ции чаще пользуются ОНФ, для которых обратное преобразование существует и
- 9. Арифметика вычетов a≡b (mod n), если a = b+kn для некоторого целого k. Если а неотрицательно
- 10. (a + b) mod n ==((a mod n) + (b mod n)) mod n (a -
- 11. Операция, обратная возведению в степень по модулю n , вычисляет дискретный логарифм. Обратное число для 4
- 12. Оценки временной и емкостной сложности алгоритмов нахождения дискретных логарифмов свидетельствуют об субэкспоненциальной вычислительной сложности их выполнения,
- 13. Открытое значение у вместе с именем пользователя может быть помещено в список паролей доступа в блок
- 14. Она предназначена для обеспечения криптосвязности двух корреспондентов сети связи без предварительного обмена секретной ключевой информацией. Пусть
- 15. . Когда пара корреспондентов Ai и Aj хотят установить между собой криптосвязность для обмена секретными сообщениями,
- 16. И поэтому Kij = Kji. Сформированный таким образом секретный ключ корреспонденты могут затем использовать как ключ
- 17. Формирование непредсказуемых для нарушителя и равновероятных шифрующих последовательностей большой длины является основой построения поточных шифраторов. Стойкость
- 18. ОДНОНАПРАВЛЕННЫЕ ФУНКЦИИ С ПОТАЙНЫМ ХОДОМ Определение 8: однонаправленная функция с потайным ходом есть однонаправленная функция fz
- 19. На основе однонаправленных функций с потайным ходом можно построить криптосистемы аутентификации информации в условиях взаимного недоверия
- 20. Данное определение предполагает, что могут существовать алгоритмы обращения вычислительно необратимой функции с произвольно большой сложностью Поэтому
- 21. Однонаправленная функция РША с потайным ходом В 1978 году была предложена первая однонаправленная функция с потайным
- 23. Скачать презентацию
Определение 3: функция называется отображением в себя, если каждый элемент области
Определение 3: функция называется отображением в себя, если каждый элемент области
Например, функция 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
f: X ->Y g: Y-> X
Рис. 1. Биективная функция f
.
Существование обратной функции к функции шифрования является основой построения систем шифрования информации. Если биективную функцию использовать для шифрования сообщений из множества X в множество криптограмм У, то с помощью обратной функции можно однозначно дешифровать криптограммы в сообщения. Если функция шифрования не является биективной, то однозначное дешифрование невозможно (из криптограммы по обратному отображению восстанавливается несколько различных сообщений).
Среди биективных функций есть класс функций, наиболее часто используемый для построения
Среди биективных функций есть класс функций, наиболее часто используемый для построения
Определение 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}
На рис.
f: S->S
Рис. 2. Инволюция f для множества S = {1,2,3,4,5}
На рис.
ОДНОНАПРАВЛЕННЫЕ ФУНКЦИИ
Особую роль в криптографии играют однонаправленные функции (ОНФ), которые
ОДНОНАПРАВЛЕННЫЕ ФУНКЦИИ
Особую роль в криптографии играют однонаправленные функции (ОНФ), которые
Определение7: однонаправленная функция есть такая функция f для которой для каждого х из области ее определения X вычислительно просто определить значение функции у = f(x), но практически для всех у из области Y функции, вычислительно невозможно отыскать любое х такое, что у =f(x).
Принципиальным условием однонаправленности функции является сложность (невозможность) вычисления обратного преобразования к ней. Обратное преобразование к ОНФ может существовать, но не являться функцией в смысле определения 1. Обратное преобразование может быть также неоднозначным, то есть практически для всех у из области значений Y функции невозможно отыскать единственное значение х такое, что у = f(x) . Неоднозначность обратного преобразования означает, что допустимых значений х∈ Х может быть множество, и каждое из них удовлетворяет уравнению у = f(x).
Для выяснения неоднозначности обратного преобразования конкретной функции необходимо убедиться, что выполнение
Для выяснения неоднозначности обратного преобразования конкретной функции необходимо убедиться, что выполнение
.
Для построения криптографических систем зашиты информа-ции чаще пользуются ОНФ, для которых
.
Для построения криптографических систем зашиты информа-ции чаще пользуются ОНФ, для которых
В качестве примера однонаправленной функции у = 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 для некоторого целого
Арифметика вычетов
a≡b (mod n), если a = b+kn для некоторого целого
(a + b) mod n ==((a mod n) + (b mod
(a + b) mod n ==((a mod n) + (b mod
(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 , вычисляет дискретный
Операция, обратная возведению в степень по модулю n , вычисляет дискретный
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 операций и такое же количество бит памяти..
Оценки временной и емкостной сложности алгоритмов нахождения дискретных логарифмов свидетельствуют об
Оценки временной и емкостной сложности алгоритмов нахождения дискретных логарифмов свидетельствуют об
Открытое значение у вместе с именем пользователя может быть помещено в
Открытое значение у вместе с именем пользователя может быть помещено в
Она предназначена для обеспечения криптосвязности двух корреспондентов сети связи без предварительного
Она предназначена для обеспечения криптосвязности двух корреспондентов сети связи без предварительного
Каждый корреспондент, например, корреспондент Ai, независимо от других случайно и равновероятно выбирает себе число xi из множества целых чисел 1,2. . ,р-1. Значение xi является индивиду-альным секретным ключом корреспондента Ai вычисляет свой открытый ключ yi =ax (mod p) и помещает число yi в открытый заве-ренный справочник, доступный всем для чтения и защищенный от подмены. Точно так же каждый корреспондент Aj сети выбирает свой секретный ключ xj вычисляет открытый ключ yj =ax (mod p) и открыто публикует его
. Когда пара корреспондентов Ai и Aj хотят установить между собой
. Когда пара корреспондентов Ai и Aj хотят установить между собой
В силу коммутативности операции возведения
,
.
И поэтому Kij = Kji. Сформированный таким образом секретный ключ корреспонденты
И поэтому Kij = Kji. Сформированный таким образом секретный ключ корреспонденты
Формирование непредсказуемых для нарушителя и равновероятных шифрующих последовательностей большой длины является
Формирование непредсказуемых для нарушителя и равновероятных шифрующих последовательностей большой длины является
ОДНОНАПРАВЛЕННЫЕ ФУНКЦИИ С ПОТАЙНЫМ ХОДОМ Определение 8: однонаправленная функция с потайным
ОДНОНАПРАВЛЕННЫЕ ФУНКЦИИ С ПОТАЙНЫМ ХОДОМ Определение 8: однонаправленная функция с потайным
Стремительное развитие криптографии в последние два десятиле-тия во многом стало возможным благодаря открытию американс-кими учеными В.Диффи и М. Хэллманом однонаправленных функций с потайным ходом, которые используются для различных криптосистем защиты информации.
На основе однонаправленных функций с потайным ходом можно построить криптосистемы аутентификации
На основе однонаправленных функций с потайным ходом можно построить криптосистемы аутентификации
Определение 9: функция вычислительно необратима, если не существуют алгоритмы нахождения обратного отображении к ней с полиномиальной вычислительной сложностью.
Данное определение предполагает, что могут существовать алгоритмы обращения вычислительно необратимой функции
Данное определение предполагает, что могут существовать алгоритмы обращения вычислительно необратимой функции
Однонаправленная функция РША с потайным ходом
В 1978 году была предложена
Однонаправленная функция РША с потайным ходом
В 1978 году была предложена