Односторонней функцией с секретом (Trapdoor function) k называется параметризируемая функция fk: X→Y:
Просто вычислить даже не зная k;
Просто вычислить зная k;
Сложно вычислить для почти всех у не зная k.
Пример: Функция RSA:
(N,e) – ключ шифрования;
(N,d) – ключ расшифрования.
;
;
, где p,q – различные простые числа примерно равной длины.
взаимо простые с (р-1)(q-1).
Утверждение: При перечислении условий – односторонняя функция с секретом (p,q).
Доказательство:
1. Легко вычислить , T=(O3) – простой алгоритм.
2. Если известны (p,q) => N=pq => φ(N) – функция Эйлера.
φ(N)–количество натуральных чисел меньше N и взаимно простых с N.
.
Существует простой алгоритм Эвклида, который позволяет найти число d:
, .
;
.
Теорема Эйлера:
Если числа a и N взаимно просты, то .
=> ;
=> ;
=> .
Если p и q известны, то легко вычислить число d, а возведение в степень d является функцией обратной к RSA.
Доказательство:
для x – не взаимно простого и N=pq опускается.
Если p и q не известны, то сложно вычислить .
Утверждение: Задача нахождения d при неизвест. с эквивал. (имеет один класс сложности) с задачей разложения N на множители.
Задача разложения на множители: сложная.
– субъэкспоненциальная сложность.
2.2 Шифрование с открытым ключом
2.2.1 Симметричные шифры
Шифр (X, Y, K, E, D)
E={Ek: X→Y}, D={Dk: Y→X};
Свойства:
1) ;
Легко вычислить и зная k;
Сложно вычислить и не зная k.
Все перечисленное относится к схемам с симметричными ключами.
2.2.2 Асимметричные шифры
Шифр (X, Y, K, E, D)
E={Ek: X→Y}, D={Dk: Y→X};
Свойства:
1) ;
Легко вычислить ;
Трудно вычислить не зная k;
Легко вычислить зная k;
Ek – односторонняя функция с секретом.
С симметричным ключом:
.
С ассиметричным ключом:
Всего: секретных ключей – n; открытых ключей – n.
У каждого: 1 секретный ключ. Надо обеспечить достоверность n-1 открытых ключей.
2.2.3 Схема шифрования RSA
;
.
;
.
Шифрование: ;
Расшифрование: .
Закрытый ключ: (N,d);
Открытый ключ: (N,e).
, , где p и q – простые.
RSA не рекомендует использовать N короче 1024.
;
;
;
;
=> , t ϵ Z.
По теореме Эллера: .
2.2.4 Схема шифрования Эль-Гамеля
Была предложена в 1984 г.
Параметры:
- простое число p;
- число g: 1<g<p.
Ключи:
- закрытый ключ – случайное число x: 1<x<p, взаимно простое с p-1;
- открытый ключ – .
Чтобы зашифровать сообщение m, (Ek(m)):
1) сгенерировать случайное число k: 1<k<p, взаимно простое с p-1;
2) вычисляются два числа: ;
3) зашифровать сообщение:
Расшифрование (Dk(c)):
1) C = (a,b);
2) .
Проверим корректность: ,
,
если , .
Безопасность (стойкость) схемы:
Для атак необходимо по y узнать x, следовательно, это задача дискретного логарифмирования.
2.3 Цифровая подпись
Собственноручная подпись:
- возможность определения автора документа (аутентификация);
- определение в документе внесены ли исправления после подписи (целостность);
- автор не может отказаться от подписи (неотказуемость).
Закон №63-ФЗ «Об электронной подписи».
Предыдущий закон: №1-ФЗ «Об электронной цифровой подписи».
ГОСТ Р 34.10-94, в настоящее время действует ГОСТ Р 34.10-2001, в будущем ГОСТ Р-2013.
Электронно-цифровая подпись (ЭЦП) – это строка бит, полученная в результате процесса формирования подписи.
Процесс формирования подписи – это процесс, в качестве исходных данных которого используются сообщения, ключ-подписи и параметры схемы цифровой подписи, а в результате формируется цифровая подпись (ЦП).
Процесс правильности (ЦП) – это процесс в качестве исходных данных которого используется подписанное сообщение, ключ проверки подписи, параметры схемы цифровой подписи, а результатом которого является заключение о правильности или ошибки ЦП.
Ключ подписи (закрытый ключ) – элемент секретных данных специфичный для субъекта и используемый только данным субъектом в процессе формирования ЦП.
Ключ проверки подписи (открытый ключ) – элемент данных, математически связанных с ключом подписи и используемый проверяющей стороной в процессе проверки ЦП.
Параметры схемы ЭЦП – элемент данных общий для всех субъектов схем цифровой подписи известный или доступный всем этим субъектам.
Процесс формирования ЭЦП (S):
Процедура проверки подписи (V):
с = s(x,k1,p), f = V(c, k2,p),
x ϵ X – пространство сообщений;
(k1, k2) ϵ K – множество ключей;
p ϵ P – множество параметров;
c ϵ C – множество подписанных сообщений;
f = Z2 – двоичное множество (нет/да).
, ;
.
Электронная подпись – это информация в электронной форме которая присоединяется к другой информации в электронной форме (подписываемой информации) или иным образом связанная с электронной подписью и которая используется для определения лица подписанной информации.
