Цифровая подпись

Схема шифрования Эль-Гамеля

Схема шифрования RSA

Асимметричные шифры

Симметричные шифры

Шифрование с открытым ключом

Односторонняя функция с секретом

Односторонние функции

Односторонней называется функция, обладающая следующими свойствами:

1) легко вычислить f(x);

2) для почти всех сложно вычислить.

До сих пор не доказано существование односторонних функций.

Пример:

1) умножение целых чисел:;

2) возведение в степень по модулю:;

3) сложение чисел из фиксированного набора.

Односторонней функцией с секретом (Trapdoor function) k называется параметризируемая функция f_k: X→Y:

1. просто вычислить даже не зная k;

2. просто вычислить зная k;

3. сложно вычислить для почти всех у не зная k.

Пример: Функция RSA:

(N,e) – ключ шифрования;

(N,d) – ключ расшифрования.

;

;

, где p,q – различные простые числа примерно равной длины.

взаимо простые с (р-1)(q-1).

Утверждение: При перечислении условий – односторонняя функция с секретом (p,q).

Доказательство:

1. Легко вычислить, T=(O³) – простой алгоритм.

2. Если известны (p,q) => N=pq => φ(N) – функция Эйлера.

φ(N)–количество натуральных чисел меньше N и взаимно простых с N.

.

Существует простой алгоритм Эвклида, который позволяет найти число d:

,.

;

.

Теорема Эйлера:

Если числа a и N взаимно просты, то.

=>;

=>;

=>.

Если p и q известны, то легко вычислить число d, а возведение в степень d является функцией обратной к RSA.

Доказательство:

для x – не взаимно простого и N=pq опускается.

Если p и q не известны, то сложно вычислить.

Утверждение: Задача нахождения d при неизвест. с эквивал. (имеет один класс сложности) с задачей разложения N на множители.

Задача разложения на множители: сложная.

– субъэкспоненциальная сложность.

Шифр (X, Y, K, E, D)

E={E_k: X→Y}, D={D_k: Y→X};

Свойства:

1);

2) легко вычислить и зная k;

3) сложно вычислить и не зная k.

Все перечисленное относится к схемам с симметричными ключами.

Шифр (X, Y, K, E, D)

E={E_k: X→Y}, D={D_k: Y→X};

Свойства:

1);

2) легко вычислить;

3) трудно вычислить не зная k;

4) легко вычислить зная k;

E_k – односторонняя функция с секретом.

С симметричным ключом:

.

С ассиметричным ключом:

Всего: секретных ключей – n; открытых ключей – n.

У каждого: 1 секретный ключ. Надо обеспечить достоверность n-1 открытых ключей.

;

.

;

.

Шифрование:;

Расшифрование:.

Закрытый ключ: (N,d);

Открытый ключ: (N,e).

,, где p и q – простые.

RSA не рекомендует использовать N короче 1024.

;

;

;

;

=>, t ϵ Z.

По теореме Эллера:.

Была предложена в 1984 г.

Параметры:

- простое число p;

- число g: 1<g<p.

Ключи:

- закрытый ключ – случайное число x: 1<x<p, взаимно простое с p-1;

- открытый ключ –.

Чтобы зашифровать сообщение m, (E_k(m)):

1) сгенерировать случайное число k: 1<k<p, взаимно простое с p-1;

2) вычисляются два числа:;

3) зашифровать сообщение:

Расшифрование (D_k(c)):

1) C = (a,b);

2).

Проверим корректность:,

,

если,.

Безопасность (стойкость) схемы:

Для атак необходимо по y узнать x, следовательно, это задача дискретного логарифмирования.

Собственноручная подпись:

- возможность определения автора документа (аутентификация);

- определение в документе внесены ли исправления после подписи (целостность);

- автор не может отказаться от подписи (неотказуемость).

Закон №63-ФЗ «Об электронной подписи».

Предыдущий закон: №1-ФЗ «Об электронной цифровой подписи».

ГОСТ Р 34.10-94, в настоящее время действует ГОСТ Р 34.10-2001, в будущем ГОСТ Р-2013.

Электронно-цифровая подпись (ЭЦП) – это строка бит, полученная в результате процесса формирования подписи.

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

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

Ключ подписи (закрытый ключ) – элемент секретных данных специфичный для субъекта и используемый только данным субъектом в процессе формирования ЦП.

Ключ проверки подписи (открытый ключ) – элемент данных, математически связанных с ключом подписи и используемый проверяющей стороной в процессе проверки ЦП.

Параметры схемы ЭЦП – элемент данных общий для всех субъектов схем цифровой подписи известный или доступный всем этим субъектам.

Процесс формирования ЭЦП (S):

Процедура проверки подписи (V):

с = s(x,k₁,p), f = V(c, k₂,p),

x ϵ X – пространство сообщений;

(k₁, k₂) ϵ K – множество ключей;

p ϵ P – множество параметров;

c ϵ C – множество подписанных сообщений;

f = Z₂ – двоичное множество (нет/да).

,;

.

Электронная подпись – это информация в электронной форме которая присоединяется к другой информации в электронной форме (подписываемой информации) или иным образом связанная с электронной подписью и которая используется для определения лица подписанной информации.

Схема цифровой подписи:

X, K, C, P

,;

Свойства:

1);

2) легко вычислить зная k₁;

3) трудно вычислить не зная k₁;

4) легко вычислить.