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

Это отображение f:X→Y, такое что существует простой алгоритм вычисления значений функции f(x) и не существует простого алгоритма инвертирования функции f для почти всех y: f-1(y).

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

ПРИМЕР

1) умножение f: Z*Z→Z, f(x,y)=x*y; 2) p – простые числа, a<p, f(x), f:Z_p→Z_p, f(x)=a^x(modp) – прямая задача возведения в степень O(n³), Обратная – логарифмирование субэкспоненциальной сложности; 3) Oneway function – односторонняя функция. Односторонняя функция с секретом k называется f:X→Y – отображение, зависящее от параметра k такое, что просто вычислить значение f_k(x) даже не зная k.

- даже не зная k;

- зная k просто ;

- не зная k сложно почти для всех y.

Эти односторонние функции с секретом называются trapdoorfunction. До сих пор не доказано их существование.

ПРИМЕР

N=p*q, p и q – простые числа примерно равной длины. , взаимопростые с (р-1)( q-1), р, q – секреты. E_(N,e):Z_N→Z_N, E_(N,e)(x)=x^e(modN). Прямая задача – вычисление E_(N,e)(x), T=O(n³), n - длины N; обратная задача - , где - субэкспоненциальной сложности, не зная p и q; зная p и q легко построить число d. , где - функция Эйлера, Теорема Эйлера: Если a взаимнопросто с N, тогда , .

2.2 Схема шифрования с открытым ключом

Шифр – это (X, Y, K, E, D)

E_k: X→Y, D_k: E_k(x)→X;

1) D_k(E_k(x))=X

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

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

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

Схема с О.К. (X, Y, K, E, D)

1) D_k(E_k(x))=X; 2) легко вычислить , где - одностороння функция с секретом; 3) не зная k трудно вычислить ; 4) зная k легко вычислить .

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

D_k, E_k: Z_N→Z_N

1) генерация ключей. Субъект, желающий получить шифрованное сообщение:

- генерируются простые числа р и q (большой разрядности, примерно равной разрядности);

- N=p*q;

- генерируется (множество обратимых элементов таких, что );

- вычисляется , где ;

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

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

Для ускорения [p, q, d]

2) функция Е_к; о.т. на о.к. (N,e). y=x^e(mod N)=E_(N,e)(x)

3) функция D_к; ш.т. y на л.к. (N,d). x=E_(N,d)(y)=y^d(modN).

Свойства:

D_k(E_k(x))=x. (1), где E_(N,e)(x)=(x^e)^d=x^ed= = , где . По теореме Эйлера если x взаимнопростое с N, то (подставляем в **). Для x не взаимнопростого с N (1) выполняется (доказательство другое).

Безопасность криптосхемы RSA

1. правильный выбор p и q;

2. задача факторизации N, , n – длина N в битах;

3. правильная реализация и исполнение:

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

- атака измерения мощности (противник может замерять потребляемую мощность вычислителя и восстанавливать или количество единичных бит показателя или отдельные биты).

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

ЦП – цифровой аналог обычной подписи

- видел данный документ;

- нельзя отказаться;

- подпись нельзя подделать.

Применяется для обеспечения аутентификации и неотказуемости.

ЦП – это реквизит электронного документа, предназначенный для защиты данного документа от подделки.

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

ЦП аналогичная и собственноручная позволяет обеспечить аутентификацию, неотказуемость и контроль целостности.

Схема ЦП состоит: (G, S, V), где G – генерация, S - формирование, V – верификация.

- генерация: О.К. k₁, З.К. k₂, параметры ЦП;

- формирование ЦП: s=S(m, k₂).

Требования:

- не зная k₂, трудно вычислить s,

- зная k₂, легко вычислить s

- верификация (проверка) ЦП: V(m, S, k₁)= 0 или 1.

Условия:

- если s=S(m, k₂), то V(m, S, k₁)= 1 – положительный результат проверки ЦП;

- трудно вычислить s:V(m, S, k₁)= 1, не зная k₂;

- легко вычислит V(m, S, k₁)/