В лекциях 2-11 мы показали принципы криптографии с симметричными ключами. В этой лекции мы начинаем обсуждение асимметрично-ключевой криптографии. Симметричная и асимметрично-ключевая криптографии будут существовать параллельно и продолжать обслуживать общество. Мы верим, что они дополняют друг друга; преимущества одной компенсируют недостатки другой.
Концептуальные отличия между этими двумя системами базируются на том, как эти системы сохраняют секретность. В криптографии с
В сообществе n людей при криптографии с n (n – 1)/2 общедоступных ключей. В асимметрично-ключевой криптографии необходимы только n персональных ключей. Сообщество с количеством участников 1 миллион при криптографии с 1 миллион персональных ключей.
Есть некоторые другие аспекты безопасности помимо шифрования, которые присущи асимметрично-ключевой криптографии. Они включают установление подлинности и цифровые подписи. Всякий раз, когда приложение базируется на персональной тайне, мы должны использовать асимметрично-ключевую криптографию.
Обратим внимание на то, что криптография с
Асимметричная ключевая криптография использует два отдельных ключа: один секретный (частный) и один открытый (общедоступный); шифрование и дешифрование представляют процесс запирания и отпирания замков ключами. В этом случае замок, запертый открытым ключом доступа, можно отпереть только с соответствующим секретным ключом. Рисунок 14.1 показывает, что если Алиса запирает замок открытым ключом доступа Боба, то только секретный ключ Боба может отпереть его.
Рисунок 14.2 показывает общую идею асимметрично-ключевой криптографии при использовании для шифрования. В будущих лекциях мы увидим другие приложения асимметрично-ключевой криптографии. Как показывают рисунки, в отличие от криптографии с
(рис 14.1) Закрытие и открытие в асимметрично - ключевой криптосистемеПервый ключ работает обычно со строкой символов (например, биты), второй — с числами или множеством чисел. Другими словами, мы хотим показать, что ключ засекречивания не является взаимозаменяемым с секретным ключом ; это два различных типа секретности. Рисунок 14.2 иллюстрирует несколько важных фактов.
Первый: подчеркивает асимметричный характер криптографической системы. Ответственность за обеспечение безопасности находится, главным образом, на плечах приемника (в данном случае это Боб). Боб должен создать два ключа: один секретный (частный) и один открытый (общедоступный). Боб не несет ответственность за распределение открытого ключа доступа всему сообществу. Это может быть сделано через канал распределения открытого ключа доступа. Хотя этот канал не обязан обеспечивать секретность, он должен обеспечить установление подлинности и целостность информации о ключе. Ева не должна иметь возможности распространять свой открытый ключ сообществу, представляя его как открытый ключ доступа Боба. На данный момент мы принимаем, что такой канал существует.
(рис 14.2) Общая идея асимметрично-ключевой криптосистемы Второй факт: асимметрично-ключевая криптография означает, что Боб и Алиса не могут использовать одно и то же множество ключей для двухсторонней связи. Каждый объект в сообществе создает свой собственный секретный и открытый ключи доступа. Рисунок 14.2 показывает, как Алиса может использовать открытый ключ доступа Боба, чтобы передать Бобу зашифрованные сообщения. Если Боб хочет ответить, Алиса устанавливает свои собственные секретный и открытый ключи доступа.
Третий: асимметрично-ключевая криптография означает, что Боб нуждается только в одном секретном ключе, чтобы получать всю корреспонденцию от любого участника сообщества. Алиса нуждается в ключах, чтобы связаться с n объектами в сообществе — один ключ доступа для каждого. Другими словами, Алиса нуждается в
В отличие от криптографии с
Шифрование и дешифрование в асимметрично-ключевой криптографии — C = f (K public, P). Исходный текст можно представлять себе как P = g (K private, С). Функция f шифрования используется только для шифрования; функция дешифрования g используется для дешифрования. Далее мы покажем, что функция f нуждается в "лазейке" односторонней функции, чтобы позволить Бобу расшифровывать сообщение, но препятствовать Еве делать то же самое.
Есть очень важный факт, который иногда неправильно истолковывается. Появление асимметрично-ключевой криптографии (открытый ключ доступа) не устраняет потребность в криптографии с
Главная идея асимметрично-ключевой криптографии — понятие "лазейки" в
Хотя понятие функции знакомо из математики, мы дадим неофициальное определение здесь. Функция — правило, по которому связывают (отображают) один элемент во множестве A, называемый доменом, и один элемент во множестве B, называемый диапазоном, как показано на рис. 14.3.
(рис 14.3) Функция отображения домена в диапазон Обратимая функция — функция, которая связывает каждый элемент в диапазоне с точно одним элементом в домене.
Односторонняя функция (
f вычисляется просто. Другими словами, при данном x может быть легко вычислен y = f (x).f -1 вычисляется трудно. Другими словами, при данном y, вычислить x= f ~1 (y) неосуществимо."Лазейка" в односторонней функции (TOWF — Trapdoor One Way) —
3. При данном y и ловушке (секретной) x может быть легко вычислен.
Пример 14.1
Когда n является большим, $$n = p \times q$$ — x — (p, q) двух простых чисел, а y в данном случае — это n. При заданных p и q всегда просто вычислить n. При данном n очень трудно вычислить p и q. Это — проблема разложения на множители, которую мы рассматривали в лекциях 12-13. В этом случае для нахождения функции f -1 нет решения с полиномиальным временем.
Пример 14.2
Когда n является большим, функция y = xk mod n — "лазейка" в x, k и n просто вычислить y, используя алгоритм быстрого возведения в степень, который мы обсуждали в лекциях 12-13. При заданных y, k и n очень трудно вычислить x. Это — проблема дискретного логарифма, которую мы обсуждали в лекциях 12-13. В этом случае нет решения с полиномиальным временем для функции f -1. Однако если мы знаем "лазейку" и k’, такое, что $$k \times k' = 1\bmod \varphi \left( n \right)$$, мы можем использовать x = yk mod n, чтобы найти x. Это — известный
Первая блестящая идея относительно криптографии открытого ключа доступа принадлежит Меркелю и Хеллману — она изложена в их ранцевой криптосистеме. Хотя эта система ненадежна в соответствии с сегодняшними стандартами, главная ее идея дает возможность понять современные криптосистемы с открытым ключом, которые будут рассматриваться позже в этой лекции.
Если нам говорят, какие элементы заранее определенного множества чисел мы имеем, то можно легко вычислить сумму чисел. Если нам говорят сумму, то трудно сказать, какие элементы "находятся в ранце".
Предположим, что нам даны два k -a = [a1,a2, …,ak] и x = [x1,x2, …,xk]. Первый x равен только 0 или l, определяет, какие элементы a должны быть отброшены в ранце. Сумма элементов в ранце равна
s = knapsackSum (a, x) = x1 a1 + x2 a2 + • • • + xkak
По данным a и x просто вычислить s. Однако по данному s трудно найти x. Другими словами, s = knapsackSum (x, a) вычисляется просто, но x= inv_knapmi (s, a) труден. Функция knapsackSum — a - общий k -
Просто вычислить knapsackSum и inv_knapsackSum, если - k -a1 ) больше или равен сумме всех предыдущих элементов. В этом случае мы вычисляем knapsackSum и inv_knapsackSum, как показано в Алгоритме 14.1. Алгоритм inv_knapsackSum запускается от наибольшего элемента и продолжает процесс к наименьшему. В каждой итерации он проверяет, находится ли элемент в рюкзаке.
knapsackSum (x[1,…,k], a[1,…,k] )
{
s <- 0
for (i=1 to k)
{
s <- s + ai x xi
}
return x
}
Inv_knapsackSum (s, a[1,…,k])
{
for (i=k down to 1)
{
if s >= aj
{
xi <- 1
s <- s - ai
}
else xi <- 0
}
return x[1,…,k]
}
Пример 14.3
Как очень тривиальный пример, предположим, что даны a = [17, 25, 46, 94, 201, 400] и s = 272. Таблица 14.1 показывает, как найти inv_knapsackSum в алгоритме 14.1.
В этом случае x = [0, 1, 1,0, 1,0], — это означает, что в рюкзаке находятся 25, 46 и 201.
| i | ai | s | s $$\ge$$ | xi | s $$\gets$$ s - ai x xi |
|---|---|---|---|---|---|
| 6 | 400 | 272 | false | x6=0 | 272 |
| 5 | 201 | 272 | true | x5=1 | 71 |
| 4 | 94 | 71 | false | x4=0 | 71 |
| 3 | 46 | 71 | true | x3=1 | 25 |
| 2 | 25 | 25 | true | x2=1 | 0 |
| 1 | 17 | 0 | false | x1=0 | 0 |
Посмотрим, как Алиса может передать секретное сообщение Бобу, использующему ранцевую криптосистему. Идея показана на рис. 14.4.
(рис 14.4) Секретная связь с использованием ранцевой криптосистемы
Этот процесс:
k -b = [b1, b2,..., bk].n, такой, что n > b 1 + b2 + • • • + bk.r, которое является взаимно простым с n и $${\text{1}} \leqslant r \leqslant n-{\text{1}}$$.k -t = [t1, t2,…….. tk], в котором $${t_i} = r \times {b_i}\bmod n$$.k -объектов и находит новый a = liermute(t).k -a. Секретный ключ — n, r и k -b.Предположим, что Алисе надо послать сообщение Бобу.
k -x=[x1, x2,…. xk], в котором xi — не 0 и не 1. knapsackSum для вычисления s в качестве исходного текста.Боб получает зашифрованный текст s.
Боб вычисляет $$s' = {r^{ - 1}} \times s\bmod n$$.
Боб переставляет x’ для того, чтобы найти x. x есть восстановленный исходный текст.
Пример 14.4
Это тривиальный (очень легко раскрываемый пример). Он приводится только для того, чтобы показать процедуру.
b = [7, 11, 19, 39, 79, 157, 313].n = 900 и r = 37, и [4 2 5 3 1 7 6] как таблицу перестановок.t = [259, 407, 703, 543, 223, 409, 781].a = перестановка (t)= [543, 407, 223, 703, 259, 781, 409].a ; он сохраняет в тайне n, r и b."g" Бобу.7 битов "g", (1100111) 2 и создает x = [1,1,0,0, 1, 1, 1]. Это — исходный текст.s = knulisackSum (a, x) = 2399. Это — зашифрованный текст, передаваемый Бобу.s = 2165.x’ = inv_knalisackSum (s', b) = [1, 1, 0, 1, 0, 1, 1].x = перестановка (x’) = [1, 1, 0, 0, 1, 1, 1]. Он интерпретирует строку (1100111) 2 как символ "g".Вычисление суммы элементов в ранце Алисы — фактически x на матрицу-столбец a. Результат — матрица s $$1 \times 1$$. Матричное умножение: $$s = x \times a
$$, в котором x является матрицей-строкой, а a — матрица-столбец -s и x Ева не сможет легко найти a. Боб, однако, имеет лазейку. Боб использует его $$s' = {r^{ - 1}} \times s$$ и секретную, суперувеличивающуюся матрицу-столбец b, чтобы найти матрицу-строку x. При этом он применяет процедуру inv_knapsackSum. Перестановка позволяет Бобу найти x по известному x’.
Самый общий алгоритм открытого ключа доступа — криптографическая система RSА, названная по имени его изобретателей Ривеста, Шамира, Эделмана (Rivest, Shamir и Adelman).
RSА использует два типа ключей — e и d, где e — открытый, a d — секретный. Предположим, что P — исходный текст и C — зашифрованный текст. Алиса использует C = Pe mod n, чтобы создать зашифрованный текст C из исходного текста P ; Боб использует P = Cd mod n, чтобы извлечь исходный текст (файл), переданный Алисой. Модулей n создается очень большое количество с помощью процесса генерации ключей, который мы обсудим позже.
Для шифрования и дешифрования применяют возведение в степень по модулю. Как мы уже обсуждали в лекциях 12-13, при использовании быстрого алгоритма возведение в степень по модулю выполнимо в полиномиальное время. Однако нахождение модульного логарифма так же сложно, как и разложение числа по модулю. Для него нет алгоритма с полиномиальным временем. Это означает, что Алиса может зашифровать сообщение общедоступным ключом (e) в полиномиальное время. Боб также может расшифровать его в полиномиальное время (потому что он знает d ). Но Ева не может расшифровать это сообщение, потому что она должна была бы вычислить корень e -той степени из C с использованием модульной арифметики. Рисунок 14.5 показывает идею
(рис 14.5) Сложность операций в RSA Другими словами, Алиса использует e -той степени из n, то возведение в степень по модулю n не будет больше односторонней функцией.
Рисунок 14.6 показывает общую идею процедуры, используемой в
(рис 14.6) Шифрование, дешифрование и генерация ключей в RSA Кольца шифрования/дешифрования. Шифрование и дешифрование сделаны с использованием n общедоступен. Любой может послать сообщение Бобу, используя это кольцо для шифрования.
Группы генерирования ключей.
Боб использует шаги, показанные в алгоритме 14.2, чтобы создать свои открытый и секретный ключи. После генерации ключей Боб объявляет (e, n) как свой открытый ключ доступа: Боб сохраняет d как свой секретный ключ. Боб может отказаться от p, q и $$\varphi (n)$$ ; они не могут изменить его секретный ключ, не изменяя модуль. Для безопасности рекомендуется размер для каждого простого p или q — 512 бит (почти 154 десятичные цифры). Это определяет размер модуля, n 1024 бита ( 309 цифр).
$$\tt\parindent0pt
RSA Key\_Generation (RSA - генерация ключа)
\{
Выбрать два больших простых $p$ and $q$, таких, что $p \ne q$.
$n \gets p \times q$
$\varphi (n)\gets (p-1)\times(q–1)$
Выбрать $e$, такое, что $1 < e < \varphi (n)$ и $e$ is — взаимно простое с $\varphi (n)$
$d \gets e^{-1} \mod\ \varphi (n)$\ \ \ \ \ // $d$ - это инверсия $e$ по модулю $\varphi (n)$
Открытый ключ $\gets (e, n)$\ \ \ \ // Объявляется открытым
Секретный ключ $\gets d$\ \ \ \ \ // Сохраняется в секрете
return Public\_key and Private\_key\ \ \ \ // Возврат открытого и секретного ключей
\} $$
Передать сообщение Бобу может любой, используя его открытый ключ доступа. Шифрование в n ; если размер исходного текста больше, то он должен быть разделен на блоки.
RSA_Encryption (P, e, n) // P — исходный текст в Zn и P < n
{
C <- Fast_Exponentiation (P, e, n) //Вычисление (Pe mod n)
return C
}
Чтобы расшифровать сообщение зашифрованного текста, которое Боб получил в n.
RSA_Decryption (C, d, n) //C — зашифрованный текст в Zn
{
P <- Fast_Exponentiation (C, d, n) // Вычисление (Cd mod n)
return P
}
Используя вторую версию теоремы Эйлера, которая обсуждалась в лекциях 12-13, мы можем доказать, что шифрование и дешифрование инверсны друг другу.
$$\tt\parindent0pt Если $n =p \times q < n$, и $k$ - целое число, тогда $a^{k\times\varphi (n)+1} \equiv a (mod\ n)$. $$Предположим, что исходный текст, восстановленный Бобом, есть P1. Докажем, что он эквивалентен P.
Рассмотрим некоторые тривиальные (ненадежные) примеры процедуры
Пример 14.5
Боб выбирает 7 и 11 как p и q и вычисляет $$n = 7 \times 11 = 77
$$. Значение $$\varphi (n) = (7 - 1)(11 - 1)$$ или 60. Теперь он выбирает два ключа, e и d, из Z60*. Если он выбирает e = 13, то d = 37. Обратите внимание, что $$e \times d\bmod {\text{ }}60 = 1$$ (они инверсны друг другу). Теперь предположим, что Алиса хочет передать исходный текст 5 Бобу. Она использует общедоступный ключ 13, чтобы зашифровать 5.
Исходный текст:5 C = 513 = 26 mod 77 Зашифрованный текст: 26
Боб получает зашифрованный текст 26 и использует секретный ключ 37, чтобы расшифровать зашифрованный текст.
Зашифрованный текст: 26 P = от 2637 до 5 mod 77 Исходный текст 5
Переданный Алисой текст получен Бобом как исходный текст 5.
Пример 14.6
Теперь предположим, что другой человек, Джон, хочет передать сообщение Бобу. Джон может использовать открытый ключ доступа, объявленный Бобом (вероятно, на его сайте), - 13 ; исходный текст Джона — 63. Джон делает следующие вычисления:
Исходный текст: 63 C = 6313 = 28 mod 77 Зашифрованный текст: 28
Боб получает зашифрованный текст 28 и использует свой секретный ключ 37, чтобы расшифровать зашифрованный текст.
Зашифрованный текст: 28 P = 2837 = 63 mod 77 Исходный текст: 63
Пример 14.7
Дженнифер создает пару ключей для себя. Она выбирает p = 397 и q = 401. Она вычисляет $$n = 397 \times 401 = 159197$$. Затем она вычисляет $$\varphi (n) = 396 \times 400 = 158400$$. Затем она выбирает e = 343 и d = 12007. Покажите, как Тэд может передать сообщение "No" Дженнифер, если он знает e и n.
Решение
Предположим, что Тэд хочет передать сообщение "No" Дженнифер. Он изменяет каждый символ на число (от 00 до 25 ), сопоставляет каждой букве число, содержащее две цифры. Затем он связывает два 1314. Затем Тэд использует e и n, чтобы зашифровать сообщение. Зашифрованный текст 1314343 = 33677 mod 159197. Дженнифер получает сообщение 33677 и использует d ключ дешифрования, чтобы расшифровать это сообщение: 3367712007 = 1314 mod 159197. Затем Дженнифер расшифровывает 1314 как сообщение "No". Рисунок 14.7 показывает этот процесс.
(рис 14.7) Шифрование и дешифрование в примере 14.7
До настоящего момента не было обнаружено никаких разрушительных атак RSА. Несколько атак были предсказаны. Они основаны на слабом исходном тексте, слабом выборе параметра или несоответствующей реализации. Рисунок 14.8 показывает категории потенциальных атак.
(рис 14.8) Диаграмма возможных атак на RSA Безопасность RSА базируется на следующей идее: модуль настолько большой, что разложение на множители в разумное время неосуществимо. Боб выбирает p и q и вычисляет $$n = p \times q
$$. Число n общедоступно, p и q являются секретными. Если Ева сможет разложить на множители n и получить p и q, то она может вычислить $$\varphi (n) = (p-1)(q-1)$$. Затем Ева тогда может вычислить $$d = {e^{ - 1}}\bmod \varphi (n)$$, потому что e общедоступен. Секретный ключ d — лазейка, которую Ева может использовать, чтобы расшифровать зашифрованное сообщение.
Как мы узнали в лекциях 12-13, есть много алгоритмов разложения на множители, но ни один из них не может найти сомножители большого целого числа с полиномиальной сложностью времени. Для того чтобы обеспечить безопасность, n был больше чем 300 десятичных цифр. Это означает, что модуль должен быть по крайней мере 1024 бита. Даже при использовании мощнейшего и самого быстрого компьютера, доступного на сегодня, разложение на множители целого числа такого размера требует неосуществимо большого времени. Это означает, что
Потенциальная атака RSА базируется на мультипликативном свойстве C = Pe mod n и передает C Бобу. Также предположим, что Боб расшифрует произвольный зашифрованный текст для Евы – С1, отличный от C. Ева перехватывает C и использует следующие шаги, чтобы найти P:
а. Ева выбирает случайное целое число X в Zn*.
б. Ева вычисляет $$Y = C \times {X^e}\bmod n$$.
в. Ева передает Y Бобу для дешифрования и получает Z = Yd mod n ; это шаг атаки выборкой зашифрованного текста.
г. Ева может легко найти P, потому что
Z = Yd mod n = (C x Xe)d mod n = (Cd x Xed) mod n = (Cd x X) mod n = (P x X) mod n Z = (P x X) mod n -> P=Z x X-1 mod n
Ева использует расширенный евклидов алгоритм для того, чтобы найти мультипликативную инверсию X, и в конечном счете значение P.
Чтобы уменьшить время шифрования, можно попытаться использовать короткий ключ шифрования — малое значение числа e, например, значение для e, такое как e = 3 (второе простое число). Однако есть некоторые потенциальные атаки на показатель при его малом значении степени шифрования, которые мы здесь кратко обсуждаем. Эти атаки вообще не кончаются вскрытием системы, но они все-таки должны быть предотвращены. Для того чтобы сорвать эти виды атак, рекомендуется использовать e = 216 + 1 = 65537 (или простое число, близкое к этому значению).
Атака теоремы Куперcмита (Coppersmith) может быть главной для атаки малого показателя степени на ключ шифрования. Основное положение этой теоремы: для полинома f(x) степени e по модулю n, чтобы найти корни, если один из корней является меньшим чем n1/e, можно использовать алгоритм сложности, log n. Эта теорема может быть применена к C = f(P) = Pe mod n.
Если e = 3 и известны хотя бы две трети битов в исходном тексте P, алгоритм может найти все биты в исходном тексте.
Атака широковещательной передачи может быть начата, если один объект передает одно и то же сообщение группе получателей с тем же самым ключом шифрования. Например, предположим следующий сценарий: Алиса хочет передать одно и то же сообщение трем получателям с тем же самым общедоступным ключом e = 3 и модулями n1, n2 и n3.
C1 = P3 mod n1 C2 = P3 mod n2 C3 = P3 mod n3
Применяя китайскую теорему об остатках к этим трем уравнениям, Ева может найти уравнение формы C’ = P3 mod n1n2n3. Это означает, что P3 < n1n2n3 и что C’ = P3 решается с помощью обычной арифметики (не модульной). Ева может найти значение C’ = P1/3.
Атака связанных между собой сообщений была обнаружена Франклином Рейтером (Franklin Reiter). Она может быть кратко описана следующим образом. Алиса зашифровала два исходных текста, P1 и P2, с помощью e = 3 и передает C1 и C2 Бобу. Если P1 связан с P2 P1 и P2 в выполнимое время вычисления.
Атака короткого списка, обнаруженная Куперсмитом, может быть кратко описана следующим образом. Алиса имеет сообщение М для передачи Бобу. Она записывает сообщение и зашифровывает его как сообщение r1, а результат записывает как C1 и передает C1 (Бобу). Ева перехватывает C1 и удаляет его. Боб сообщает Алисе, что он не получил сообщение, так что Алиса заполняет сообщение, снова зашифровывает как сообщение r2 и передает это Бобу. Ева также перехватывает и это сообщение. Ева теперь имеет C1 и C2, и она знает, что оба зашифрованных текста принадлежат одному и тому же исходному тексту. Куперсмит доказал, что если r1 и r2 короткие, то Ева способна восстановить первоначальное сообщение М.
Две формы атак могут быть проведены на показатель степени дешифрации: атака раскрытой степени дешифрации и атака малого показателя степени дешифровации. Они обсуждаются ниже.
Атака раскрытого показателя степени дешифрации. Очевидно, что если Ева может найти показатель степени дешифрации, d, она сможет расшифровать текущее зашифрованное сообщение. Однако на этом атака не останавливается. Если Ева знает значение d, она может использовать вероятностный алгоритм (не обсуждаемый здесь) к числу n и найти значения p и q. Следовательно, если Боб изменит только угрожающий безопасности показатель степени дешифрования, но сохранит тот же самый модуль n, Ева сможет расшифровать будущие сообщения, потому что она сможет разложить на множители n. Поэтому если Боб узнает, что показатель степени скомпрометирован, он должен выбрать новое значение для p и q, вычислить n и создать полностью новые секретный и открытый ключи доступа.
Атака малого значения показателя степени дешифрации. Боб может подумать, что использование малого значения степени секретного ключа d приводит к более быстрой работе алгоритма дешифрации. Винер показал, что в случае d < 1/3n1/4 возможен специальный тип атаки, основанной на цепной дроби, — тема, которая рассматривается в теории чисел. Этот тип атаки может подвергнуть риску безопасность RSА. Для того чтобы это произошло, должно выполняться условие, что q < p < 2q; если эти два условия существуют, Ева может разложить n на сомножители в полиномиальное время.
d > 1/3 n1/4 , чтобы предотвратить атаку малого значения ключа дешифрации.Исходный текст и зашифрованный текст в 0 до n – 1 ). Другими словами, Ева уже знает кое-что об исходном тексте. Эти характеристики могут позволить некоторые атаки исходного текста. Три атаки были уже упомянуты в литературе: атака короткого сообщения, атака циклического повторения и явная атака.
Атака короткого сообщения. В атаке короткого сообщения, если Ева знает множество возможных исходных текстов, то ей известна еще одна информация и дополнительный факт, что зашифрованный текст — перестановка исходного текста. Ева может зашифровать все возможные сообщения, пока результат не будет совпадать с перехваченным зашифрованным текстом. Например, если известно, что Алиса посылает число с четырьмя цифрами Бобу, Ева может легко испытать числа исходного текста 0000 к 9999, чтобы найти исходный текст. По этой причине короткие сообщения должны быть дополнены случайными битами в начале и конце, чтобы сорвать этот тип атаки. Настоятельно рекомендуется заполнять исходный текст случайными битами прежде начала шифрования. Здесь используется метод, называемый OAEP, который будет позже обсужден в этой лекции.
Атака циклического повторения построена на факте, что если переставлять зашифрованный текст (перестановка исходного текста), то непрерывное шифрование зашифрованного текста в конечном счете кончится исходным текстом. Другими словами, если Ева непрерывно шифрует перехваченный зашифрованный текст C, она в итоге получит исходный текст. Однако сама Ева не знает, каков исходный текст, так что ей неизвестно, когда пора остановиться. Она должна пройти один шаг далее. Когда она получает зашифрованный текст C снова, она возвращается на один шаг, чтобы найти исходный текст.
Перехваченный зашифрованный текст C C1 = Ce mod n C2 = C1e mod n ……………… Ck = Ck-1e mod n ->, если Ck = C, останов: исходный текст - P = Ck-1
Может ли это быть серьезной атакой на криптосистему n. Другими словами, нет никакого эффективного алгоритма, который может завершить эту атаку в полиномиальное время, если n является большим.
Явная атака сообщения. Другая атака, которая базируется на отношениях перестановки между исходным текстом и зашифрованным текстом, — явная атака сообщения. Явное сообщение — сообщение, которое зашифровано само в себя (не может быть скрыто). Было доказано, что есть всегда некоторые сообщения, которые шифруются сами в себя. Поскольку ключ шифрования обычно нечетен, имеются некоторые исходные тексты, которые зашифрованы сами в себя, такие как P = 0 и P = 1. Но если ключ шифровки выбран тщательно, число их незначительно. Программа шифровки может всегда проверить, является ли вычисленный зашифрованный текст таким же, как исходный текст, и отклонить $${P^{{e_B}}}$$ исходный текст перед передачей зашифрованного текста.
Главной атакой
Общая атака модуля. Она может быть начата, если сообщество $${C^{{d_B}}}$$ использует общий модуль, n. Например, люди в сообществе могли бы позволить третьей стороне, которой они доверяют, выбирать p и q, вычислять n и $$\varphi (n)$$ и создать пару образцов ( ei, di ) для каждого объекта. Теперь предположим, что Алиса должна передать сообщение Бобу. Зашифрованный текст Бобу — это $$C = {P^{{e_B}}}\bmod n$$ Боб использует свой секретный ключ, dB, чтобы расшифровывать сообщение: $$P = {C^{{d_B}}}\bmod n$$. Проблема в том, что Ева может также расшифровать сообщение, если она — член сообщества и ей была назначена пара образцов ( eE и dE ), как мы узнали в разделе "атака малого значения ключа дешифрации". Используя свои собственные ключи ( eE и dE ), Ева может начать вероятностную атаку на сомножители n и найти dB Боба. Чтобы сорвать этот тип атаки, модуль не должен быть в совместном пользовании. Каждый объект должен вычислить свой собственный модуль.
Предыдущие атаки базировались на основной структуре RSА. Как показал Дэн Бонех (Dan Boneh), есть несколько атак реализации RSА. Мы приведем две из них: атака анализом времени и атака мощности.
Атака анализом времени (Timing attack). Пауль Кочер (Paul Kocher) демонстрировал атаку только зашифрованного текста, называемую атака анализом времени. Атака основана на быстром алгоритме с показательным временем, который рассмотрен в лекциях 12-13. Алгоритм использует только возведение во вторую степень, если соответствующий бит в секретном показателе степени d есть 0 ; он используется и при возведении во вторую степень и умножении, если соответствующий бит — 1. Другими словами, синхронизация требует сделать каждую итерацию более длинной, если соответствующий бит — 1. Эта разность синхронизации позволяет Еве находить значение битов в d, один за другим.
Предположим, что Ева перехватила большое количество зашифрованных текстов от C1 до Cm. Также предположим, что Ева наблюдала, какое количество времени требуется для Боба, чтобы расшифровать каждый зашифрованный текст, от T1 до T2. Ева знает, сколько времени требуется для основных аппаратных средств, чтобы выполнить операцию умножения от t1 до tm., где t1 — время, требуемое для выполнения умножения.
Результат операции умножения = Результат $$\times {C_i}\bmod n$$.
Ева может использовать алгоритм 14.5, который является упрощенной версией алгоритма, используемого практически для вычисления всех бит в d ( d0 до d k-1 ).
Алгоритм устанавливает начальное значение d0 = 1 (потому что d должен быть нечетным) и вычисляет новые значения для T’is (время дешифрования относится к d1 до dk-1 ). Алгоритм затем предполагает, что следующий бит — это 1, и находит несколько значений D1 до D2, основываясь на этом предположении.
RSA_Timing_Attack([T1…Tm])
{
d0 <- 1 // Потому что d — нечетное
Вычислить [t1…tm]
[T1…Tm] <- [T1…Tm] - [t1…tm]
for (j from 1 to k-1)
{ //Обновление Ti для следующего бита
Пересчитать [t1…tm]
//Пересчет ti в предположении, что следующий бит — это 1
[D1…Dm] <- [T1…Tm] -[t1…tm]
var <- variance ([D1…Dm]) – variance ([T1…Tm])
if (var > 0) dj <- 1 else dj <- 0
[T1…Tm] <- [T1…Tm] - dj x [t1…tm] //Обновление Ti для следующего бита
}
}
Если принятое предположение верно, то каждый Di является вероятно меньшим, чем соответствующее время передачи Ti. Однако алгоритм использует дисперсию (или другие критерии корреляции), чтобы рассмотреть все варианты Di и Ti. Если разность 1 в противном случае предполагает, что следующий бит — 0. Алгоритм тогда вычисляет новые Ti, используя для этого оставшиеся биты.
Есть два метода сорвать атаку анализом времени:
1. добавить случайные задержки к возведению в степень, чтобы каждое возведение в степень занимало одно и то же время;
2. Ривест рекомендовал "ослепление". По этой идее зашифрованный текст умножается на случайное число перед дешифрованием. Процедура содержит следующие шаги:
a. Выбрать секретное случайное число r между 1 и (n – 1).
b. Вычислить $${C_1} = C \times {r^e}\bmod n$$.
c. Вычислить P1 = C1d mod n.
d. Вычислить $$P = {P_1} \times {r^{ - 1}}\bmod n$$.
Атака анализом мощности подобна атаке анализом времени. Было показано, что если Ева может точно измерить мощность, использованную в течение дешифрования, она может начать атаку анализа мощности на основании принципов, рассмотренных для атаки анализом времени.
Следующие рекомендации основаны на теоретических и экспериментальных результатах.
n должно быть, по крайней мере, 1024. Это означает, что n должно быть приблизительно 21024, или 309 десятичных цифр.p и q должны каждый быть по крайней мере 512 битов. Это означает, что p и q должны быть приблизительно 2512 или 154 десятичными цифрами.p и q не должен быть очень близки друг к другу.p – 1 и q – 1 должны иметь по крайней мере один большой простой сомножитель.p/q не должно быть близко к n не должен использоваться совместно.e должно быть 216 + 1 или целым числом, близким к этому значению.d, Боб должен немедленно изменить n так же, как e и d. Было доказано, что знание n и одной пары (e, d) может привести к открытию других пар того же самого модуля.Как мы упоминали ранее, короткое сообщение в
(рис 14.9) Оптимальное асимметричное дополнение шифрования (OAEP)Идея, показанная на рисунке 14.9, — это то, что P = P1 || P2, где P1 — замаскированная версия дополненного сообщения, М;
P2 передается, чтобы позволить Бобу найти маску.
Шифрование. Ниже показаны шаги процесса шифрования.
m -битовым. Мы обозначим его М.r из k бит. Обратите внимание, что r применяется только однажды и затем уничтожается.G, которая принимает целое r -битовое число, и создает m -разрядное целое число ( m — размера М, и r <m ). Это — маска.G (r), чтобы создать первую часть исходного текста $${P_1} = M \oplus G(r)$$ является замаскированным сообщением.H — другая общедоступная функция, которая принимает m -битовые входные сообщения и создает k -битовые выходные сообщения. Эта функция может быть криптографической хэш-функцией ю P2 используется для того, чтобы дать возможность Бобу снова создать маску после дешифрации.C = Pe = (P1 || P2) e и передает C Бобу.Дешифрование. Следующие шаги показывают процесс дешифрования:
P = Cd = (P1 || P2).r, используя $$H({P_1}) \oplus {P_2} = H({P_1}) \oplus H\left( {{P_2}} \right) \oplus r = r$$.М, Боб находит первоначальное сообщение.Если хотя бы один бит в течение передачи принят с ошибкой, текст, зашифрованный
Пример 14.8
Вот — реальный пример. Мы выбираем 512 -битовые p и q, вычисляем n и $$\varphi (n)$$, затем выбираем e и испытываем, что оно взаимно простое с $$\varphi (n)$$. Затем мы вычисляем d. Наконец, мы показываем результат шифрования и дешифрования. Целое число p — это число со 159 цифрами.
P = 961303453135835045741915812806154279093098455949962158225831508 796479404550564706384912571601803475031209866660649242019180878 0667421096063354219926661209
Целое число q содержит 160 цифр.
q = 12060191957231446918276794204450896001555925054637033936061 798321731482148483764659215389453209175225273226830107120695604 602513887145524969000359660045617
Модуль $$n = p \times q$$. Это число имеет 309 цифр.
n = 1159350417396761496889250986461588752377145737545414477548552613 7614788540S32635081727687881596832516846884930062548576411125016 241455233918.292716250765677272746009708271412773043496050055634 7274566628060099924037102991424472292215772798531727033839381334 692684137 327622000966676671831831088373420823444370953
$$\varphi (n) = (p-1)(q-1)$$ имеет 309 цифр.
$$\tt\parindent0pt \varphi (n) = 115935041739676149688925098646158875237714573754541447754855 261376147885408326350817276878815968325168468849300625485764111 250162414552339182927162507656751054233608492916752034482627988 117554787657013923444405716989581728196098226361075467211864612 171359107358640614008885170265377277264467341066243857664128 $$Боб выбирает e = 35535 (идеально 65537 ), и испытание на простое число показывает, что это число и $$\varphi (n)$$ — взаимно простые числа. Затем Боб находит инверсию $$e\bmod \varphi (n)$$ — это обозначается d.
e = 35535 ________________________________________________________________ d = 58008302S6003776393609366128967791759466906208965096218042286 6111380593852S2235873170628691003002171085904433840217072986908 760061153062025249598844480475682409662470814858171304632406440 777048331340108509473852956450719367740611973265574242372176176 74620776371642 0760033708533328853214470885955136670294831
Алиса хочет передать сообщение "THIS IS TEST", которое может быть представлено числовыми значениями, используя схему кодирования 00-26 ( 26 — пробел).
P = 1907081826081826002619041819
Шифрованный текст, вычисленный Алисой, — это C = Pe, числовое значение приведено ниже.
С = 4753091236462268272063655506105451809423717960704917165232392 430544529606131993285666178434183591141511974112520056829797945 717360361012782188478927415660904800235071907152771859149751884 658886321011483541033616578984679683867637337657774656250792805 2114814184404814184430812773059004692874248559166462108656 Боб может восстановить из зашифрованного текста исходный
Боб может восстановить из зашифрованного текста исходный текст, используя P = Cd.
P = 1907081826081826002619041819
После расшифровки восстановленный исходный текст — "THIS IS TEST".
Хотя
В лекциях 2-11 мы показали принципы криптографии с симметричными ключами. В этой лекции мы начинаем обсуждение асимметрично-ключевой криптографии. Симметричная и асимметрично-ключевая криптографии будут существовать параллельно и продолжать обслуживать общество. Мы верим, что они дополняют друг друга; преимущества одной компенсируют недостатки другой.
Концептуальные отличия между этими двумя системами базируются на том, как эти системы сохраняют секретность. В криптографии с
В сообществе n людей при криптографии с n (n – 1)/2 общедоступных ключей. В асимметрично-ключевой криптографии необходимы только n персональных ключей. Сообщество с количеством участников 1 миллион при криптографии с 1 миллион персональных ключей.
Есть некоторые другие аспекты безопасности помимо шифрования, которые присущи асимметрично-ключевой криптографии. Они включают установление подлинности и цифровые подписи. Всякий раз, когда приложение базируется на персональной тайне, мы должны использовать асимметрично-ключевую криптографию.
Обратим внимание на то, что криптография с
Асимметричная ключевая криптография использует два отдельных ключа: один секретный (частный) и один открытый (общедоступный); шифрование и дешифрование представляют процесс запирания и отпирания замков ключами. В этом случае замок, запертый открытым ключом доступа, можно отпереть только с соответствующим секретным ключом. Рисунок 14.1 показывает, что если Алиса запирает замок открытым ключом доступа Боба, то только секретный ключ Боба может отпереть его.
Рисунок 14.2 показывает общую идею асимметрично-ключевой криптографии при использовании для шифрования. В будущих лекциях мы увидим другие приложения асимметрично-ключевой криптографии. Как показывают рисунки, в отличие от криптографии с
(рис 14.1) Закрытие и открытие в асимметрично - ключевой криптосистемеПервый ключ работает обычно со строкой символов (например, биты), второй — с числами или множеством чисел. Другими словами, мы хотим показать, что ключ засекречивания не является взаимозаменяемым с секретным ключом ; это два различных типа секретности. Рисунок 14.2 иллюстрирует несколько важных фактов.
Первый: подчеркивает асимметричный характер криптографической системы. Ответственность за обеспечение безопасности находится, главным образом, на плечах приемника (в данном случае это Боб). Боб должен создать два ключа: один секретный (частный) и один открытый (общедоступный). Боб не несет ответственность за распределение открытого ключа доступа всему сообществу. Это может быть сделано через канал распределения открытого ключа доступа. Хотя этот канал не обязан обеспечивать секретность, он должен обеспечить установление подлинности и целостность информации о ключе. Ева не должна иметь возможности распространять свой открытый ключ сообществу, представляя его как открытый ключ доступа Боба. На данный момент мы принимаем, что такой канал существует.
(рис 14.2) Общая идея асимметрично-ключевой криптосистемы Второй факт: асимметрично-ключевая криптография означает, что Боб и Алиса не могут использовать одно и то же множество ключей для двухсторонней связи. Каждый объект в сообществе создает свой собственный секретный и открытый ключи доступа. Рисунок 14.2 показывает, как Алиса может использовать открытый ключ доступа Боба, чтобы передать Бобу зашифрованные сообщения. Если Боб хочет ответить, Алиса устанавливает свои собственные секретный и открытый ключи доступа.
Третий: асимметрично-ключевая криптография означает, что Боб нуждается только в одном секретном ключе, чтобы получать всю корреспонденцию от любого участника сообщества. Алиса нуждается в ключах, чтобы связаться с n объектами в сообществе — один ключ доступа для каждого. Другими словами, Алиса нуждается в
В отличие от криптографии с
Шифрование и дешифрование в асимметрично-ключевой криптографии — C = f (K public, P). Исходный текст можно представлять себе как P = g (K private, С). Функция f шифрования используется только для шифрования; функция дешифрования g используется для дешифрования. Далее мы покажем, что функция f нуждается в "лазейке" односторонней функции, чтобы позволить Бобу расшифровывать сообщение, но препятствовать Еве делать то же самое.
Есть очень важный факт, который иногда неправильно истолковывается. Появление асимметрично-ключевой криптографии (открытый ключ доступа) не устраняет потребность в криптографии с
Главная идея асимметрично-ключевой криптографии — понятие "лазейки" в
Хотя понятие функции знакомо из математики, мы дадим неофициальное определение здесь. Функция — правило, по которому связывают (отображают) один элемент во множестве A, называемый доменом, и один элемент во множестве B, называемый диапазоном, как показано на рис. 14.3.
(рис 14.3) Функция отображения домена в диапазон Обратимая функция — функция, которая связывает каждый элемент в диапазоне с точно одним элементом в домене.
Односторонняя функция (
f вычисляется просто. Другими словами, при данном x может быть легко вычислен y = f (x).f -1 вычисляется трудно. Другими словами, при данном y, вычислить x= f ~1 (y) неосуществимо."Лазейка" в односторонней функции (TOWF — Trapdoor One Way) —
3. При данном y и ловушке (секретной) x может быть легко вычислен.
Пример 14.1
Когда n является большим, $$n = p \times q$$ — x — (p, q) двух простых чисел, а y в данном случае — это n. При заданных p и q всегда просто вычислить n. При данном n очень трудно вычислить p и q. Это — проблема разложения на множители, которую мы рассматривали в лекциях 12-13. В этом случае для нахождения функции f -1 нет решения с полиномиальным временем.
Пример 14.2
Когда n является большим, функция y = xk mod n — "лазейка" в x, k и n просто вычислить y, используя алгоритм быстрого возведения в степень, который мы обсуждали в лекциях 12-13. При заданных y, k и n очень трудно вычислить x. Это — проблема дискретного логарифма, которую мы обсуждали в лекциях 12-13. В этом случае нет решения с полиномиальным временем для функции f -1. Однако если мы знаем "лазейку" и k’, такое, что $$k \times k' = 1\bmod \varphi \left( n \right)$$, мы можем использовать x = yk mod n, чтобы найти x. Это — известный
Первая блестящая идея относительно криптографии открытого ключа доступа принадлежит Меркелю и Хеллману — она изложена в их ранцевой криптосистеме. Хотя эта система ненадежна в соответствии с сегодняшними стандартами, главная ее идея дает возможность понять современные криптосистемы с открытым ключом, которые будут рассматриваться позже в этой лекции.
Если нам говорят, какие элементы заранее определенного множества чисел мы имеем, то можно легко вычислить сумму чисел. Если нам говорят сумму, то трудно сказать, какие элементы "находятся в ранце".
Предположим, что нам даны два k -a = [a1,a2, …,ak] и x = [x1,x2, …,xk]. Первый x равен только 0 или l, определяет, какие элементы a должны быть отброшены в ранце. Сумма элементов в ранце равна
s = knapsackSum (a, x) = x1 a1 + x2 a2 + • • • + xkak
По данным a и x просто вычислить s. Однако по данному s трудно найти x. Другими словами, s = knapsackSum (x, a) вычисляется просто, но x= inv_knapmi (s, a) труден. Функция knapsackSum — a - общий k -
Просто вычислить knapsackSum и inv_knapsackSum, если - k -a1 ) больше или равен сумме всех предыдущих элементов. В этом случае мы вычисляем knapsackSum и inv_knapsackSum, как показано в Алгоритме 14.1. Алгоритм inv_knapsackSum запускается от наибольшего элемента и продолжает процесс к наименьшему. В каждой итерации он проверяет, находится ли элемент в рюкзаке.
knapsackSum (x[1,…,k], a[1,…,k] )
{
s <- 0
for (i=1 to k)
{
s <- s + ai x xi
}
return x
}
Inv_knapsackSum (s, a[1,…,k])
{
for (i=k down to 1)
{
if s >= aj
{
xi <- 1
s <- s - ai
}
else xi <- 0
}
return x[1,…,k]
}
Пример 14.3
Как очень тривиальный пример, предположим, что даны a = [17, 25, 46, 94, 201, 400] и s = 272. Таблица 14.1 показывает, как найти inv_knapsackSum в алгоритме 14.1.
В этом случае x = [0, 1, 1,0, 1,0], — это означает, что в рюкзаке находятся 25, 46 и 201.
| i | ai | s | s $$\ge$$ | xi | s $$\gets$$ s - ai x xi |
|---|---|---|---|---|---|
| 6 | 400 | 272 | false | x6=0 | 272 |
| 5 | 201 | 272 | true | x5=1 | 71 |
| 4 | 94 | 71 | false | x4=0 | 71 |
| 3 | 46 | 71 | true | x3=1 | 25 |
| 2 | 25 | 25 | true | x2=1 | 0 |
| 1 | 17 | 0 | false | x1=0 | 0 |
Посмотрим, как Алиса может передать секретное сообщение Бобу, использующему ранцевую криптосистему. Идея показана на рис. 14.4.
(рис 14.4) Секретная связь с использованием ранцевой криптосистемы
Этот процесс:
k -b = [b1, b2,..., bk].n, такой, что n > b 1 + b2 + • • • + bk.r, которое является взаимно простым с n и $${\text{1}} \leqslant r \leqslant n-{\text{1}}$$.k -t = [t1, t2,…….. tk], в котором $${t_i} = r \times {b_i}\bmod n$$.k -объектов и находит новый a = liermute(t).k -a. Секретный ключ — n, r и k -b.Предположим, что Алисе надо послать сообщение Бобу.
k -x=[x1, x2,…. xk], в котором xi — не 0 и не 1. knapsackSum для вычисления s в качестве исходного текста.Боб получает зашифрованный текст s.
Боб вычисляет $$s' = {r^{ - 1}} \times s\bmod n$$.
Боб переставляет x’ для того, чтобы найти x. x есть восстановленный исходный текст.
Пример 14.4
Это тривиальный (очень легко раскрываемый пример). Он приводится только для того, чтобы показать процедуру.
b = [7, 11, 19, 39, 79, 157, 313].n = 900 и r = 37, и [4 2 5 3 1 7 6] как таблицу перестановок.t = [259, 407, 703, 543, 223, 409, 781].a = перестановка (t)= [543, 407, 223, 703, 259, 781, 409].a ; он сохраняет в тайне n, r и b."g" Бобу.7 битов "g", (1100111) 2 и создает x = [1,1,0,0, 1, 1, 1]. Это — исходный текст.s = knulisackSum (a, x) = 2399. Это — зашифрованный текст, передаваемый Бобу.s = 2165.x’ = inv_knalisackSum (s', b) = [1, 1, 0, 1, 0, 1, 1].x = перестановка (x’) = [1, 1, 0, 0, 1, 1, 1]. Он интерпретирует строку (1100111) 2 как символ "g".Вычисление суммы элементов в ранце Алисы — фактически x на матрицу-столбец a. Результат — матрица s $$1 \times 1$$. Матричное умножение: $$s = x \times a
$$, в котором x является матрицей-строкой, а a — матрица-столбец -s и x Ева не сможет легко найти a. Боб, однако, имеет лазейку. Боб использует его $$s' = {r^{ - 1}} \times s$$ и секретную, суперувеличивающуюся матрицу-столбец b, чтобы найти матрицу-строку x. При этом он применяет процедуру inv_knapsackSum. Перестановка позволяет Бобу найти x по известному x’.
Самый общий алгоритм открытого ключа доступа — криптографическая система RSА, названная по имени его изобретателей Ривеста, Шамира, Эделмана (Rivest, Shamir и Adelman).
RSА использует два типа ключей — e и d, где e — открытый, a d — секретный. Предположим, что P — исходный текст и C — зашифрованный текст. Алиса использует C = Pe mod n, чтобы создать зашифрованный текст C из исходного текста P ; Боб использует P = Cd mod n, чтобы извлечь исходный текст (файл), переданный Алисой. Модулей n создается очень большое количество с помощью процесса генерации ключей, который мы обсудим позже.
Для шифрования и дешифрования применяют возведение в степень по модулю. Как мы уже обсуждали в лекциях 12-13, при использовании быстрого алгоритма возведение в степень по модулю выполнимо в полиномиальное время. Однако нахождение модульного логарифма так же сложно, как и разложение числа по модулю. Для него нет алгоритма с полиномиальным временем. Это означает, что Алиса может зашифровать сообщение общедоступным ключом (e) в полиномиальное время. Боб также может расшифровать его в полиномиальное время (потому что он знает d ). Но Ева не может расшифровать это сообщение, потому что она должна была бы вычислить корень e -той степени из C с использованием модульной арифметики. Рисунок 14.5 показывает идею
(рис 14.5) Сложность операций в RSA Другими словами, Алиса использует e -той степени из n, то возведение в степень по модулю n не будет больше односторонней функцией.
Рисунок 14.6 показывает общую идею процедуры, используемой в
(рис 14.6) Шифрование, дешифрование и генерация ключей в RSA Кольца шифрования/дешифрования. Шифрование и дешифрование сделаны с использованием n общедоступен. Любой может послать сообщение Бобу, используя это кольцо для шифрования.
Группы генерирования ключей.
Боб использует шаги, показанные в алгоритме 14.2, чтобы создать свои открытый и секретный ключи. После генерации ключей Боб объявляет (e, n) как свой открытый ключ доступа: Боб сохраняет d как свой секретный ключ. Боб может отказаться от p, q и $$\varphi (n)$$ ; они не могут изменить его секретный ключ, не изменяя модуль. Для безопасности рекомендуется размер для каждого простого p или q — 512 бит (почти 154 десятичные цифры). Это определяет размер модуля, n 1024 бита ( 309 цифр).
$$\tt\parindent0pt
RSA Key\_Generation (RSA - генерация ключа)
\{
Выбрать два больших простых $p$ and $q$, таких, что $p \ne q$.
$n \gets p \times q$
$\varphi (n)\gets (p-1)\times(q–1)$
Выбрать $e$, такое, что $1 < e < \varphi (n)$ и $e$ is — взаимно простое с $\varphi (n)$
$d \gets e^{-1} \mod\ \varphi (n)$\ \ \ \ \ // $d$ - это инверсия $e$ по модулю $\varphi (n)$
Открытый ключ $\gets (e, n)$\ \ \ \ // Объявляется открытым
Секретный ключ $\gets d$\ \ \ \ \ // Сохраняется в секрете
return Public\_key and Private\_key\ \ \ \ // Возврат открытого и секретного ключей
\} $$
Передать сообщение Бобу может любой, используя его открытый ключ доступа. Шифрование в n ; если размер исходного текста больше, то он должен быть разделен на блоки.
RSA_Encryption (P, e, n) // P — исходный текст в Zn и P < n
{
C <- Fast_Exponentiation (P, e, n) //Вычисление (Pe mod n)
return C
}
Чтобы расшифровать сообщение зашифрованного текста, которое Боб получил в n.
RSA_Decryption (C, d, n) //C — зашифрованный текст в Zn
{
P <- Fast_Exponentiation (C, d, n) // Вычисление (Cd mod n)
return P
}
Используя вторую версию теоремы Эйлера, которая обсуждалась в лекциях 12-13, мы можем доказать, что шифрование и дешифрование инверсны друг другу.
$$\tt\parindent0pt Если $n =p \times q < n$, и $k$ - целое число, тогда $a^{k\times\varphi (n)+1} \equiv a (mod\ n)$. $$Предположим, что исходный текст, восстановленный Бобом, есть P1. Докажем, что он эквивалентен P.
Рассмотрим некоторые тривиальные (ненадежные) примеры процедуры
Пример 14.5
Боб выбирает 7 и 11 как p и q и вычисляет $$n = 7 \times 11 = 77
$$. Значение $$\varphi (n) = (7 - 1)(11 - 1)$$ или 60. Теперь он выбирает два ключа, e и d, из Z60*. Если он выбирает e = 13, то d = 37. Обратите внимание, что $$e \times d\bmod {\text{ }}60 = 1$$ (они инверсны друг другу). Теперь предположим, что Алиса хочет передать исходный текст 5 Бобу. Она использует общедоступный ключ 13, чтобы зашифровать 5.
Исходный текст:5 C = 513 = 26 mod 77 Зашифрованный текст: 26
Боб получает зашифрованный текст 26 и использует секретный ключ 37, чтобы расшифровать зашифрованный текст.
Зашифрованный текст: 26 P = от 2637 до 5 mod 77 Исходный текст 5
Переданный Алисой текст получен Бобом как исходный текст 5.
Пример 14.6
Теперь предположим, что другой человек, Джон, хочет передать сообщение Бобу. Джон может использовать открытый ключ доступа, объявленный Бобом (вероятно, на его сайте), - 13 ; исходный текст Джона — 63. Джон делает следующие вычисления:
Исходный текст: 63 C = 6313 = 28 mod 77 Зашифрованный текст: 28
Боб получает зашифрованный текст 28 и использует свой секретный ключ 37, чтобы расшифровать зашифрованный текст.
Зашифрованный текст: 28 P = 2837 = 63 mod 77 Исходный текст: 63
Пример 14.7
Дженнифер создает пару ключей для себя. Она выбирает p = 397 и q = 401. Она вычисляет $$n = 397 \times 401 = 159197$$. Затем она вычисляет $$\varphi (n) = 396 \times 400 = 158400$$. Затем она выбирает e = 343 и d = 12007. Покажите, как Тэд может передать сообщение "No" Дженнифер, если он знает e и n.
Решение
Предположим, что Тэд хочет передать сообщение "No" Дженнифер. Он изменяет каждый символ на число (от 00 до 25 ), сопоставляет каждой букве число, содержащее две цифры. Затем он связывает два 1314. Затем Тэд использует e и n, чтобы зашифровать сообщение. Зашифрованный текст 1314343 = 33677 mod 159197. Дженнифер получает сообщение 33677 и использует d ключ дешифрования, чтобы расшифровать это сообщение: 3367712007 = 1314 mod 159197. Затем Дженнифер расшифровывает 1314 как сообщение "No". Рисунок 14.7 показывает этот процесс.
(рис 14.7) Шифрование и дешифрование в примере 14.7
До настоящего момента не было обнаружено никаких разрушительных атак RSА. Несколько атак были предсказаны. Они основаны на слабом исходном тексте, слабом выборе параметра или несоответствующей реализации. Рисунок 14.8 показывает категории потенциальных атак.
(рис 14.8) Диаграмма возможных атак на RSA Безопасность RSА базируется на следующей идее: модуль настолько большой, что разложение на множители в разумное время неосуществимо. Боб выбирает p и q и вычисляет $$n = p \times q
$$. Число n общедоступно, p и q являются секретными. Если Ева сможет разложить на множители n и получить p и q, то она может вычислить $$\varphi (n) = (p-1)(q-1)$$. Затем Ева тогда может вычислить $$d = {e^{ - 1}}\bmod \varphi (n)$$, потому что e общедоступен. Секретный ключ d — лазейка, которую Ева может использовать, чтобы расшифровать зашифрованное сообщение.
Как мы узнали в лекциях 12-13, есть много алгоритмов разложения на множители, но ни один из них не может найти сомножители большого целого числа с полиномиальной сложностью времени. Для того чтобы обеспечить безопасность, n был больше чем 300 десятичных цифр. Это означает, что модуль должен быть по крайней мере 1024 бита. Даже при использовании мощнейшего и самого быстрого компьютера, доступного на сегодня, разложение на множители целого числа такого размера требует неосуществимо большого времени. Это означает, что
Потенциальная атака RSА базируется на мультипликативном свойстве C = Pe mod n и передает C Бобу. Также предположим, что Боб расшифрует произвольный зашифрованный текст для Евы – С1, отличный от C. Ева перехватывает C и использует следующие шаги, чтобы найти P:
а. Ева выбирает случайное целое число X в Zn*.
б. Ева вычисляет $$Y = C \times {X^e}\bmod n$$.
в. Ева передает Y Бобу для дешифрования и получает Z = Yd mod n ; это шаг атаки выборкой зашифрованного текста.
г. Ева может легко найти P, потому что
Z = Yd mod n = (C x Xe)d mod n = (Cd x Xed) mod n = (Cd x X) mod n = (P x X) mod n Z = (P x X) mod n -> P=Z x X-1 mod n
Ева использует расширенный евклидов алгоритм для того, чтобы найти мультипликативную инверсию X, и в конечном счете значение P.
Чтобы уменьшить время шифрования, можно попытаться использовать короткий ключ шифрования — малое значение числа e, например, значение для e, такое как e = 3 (второе простое число). Однако есть некоторые потенциальные атаки на показатель при его малом значении степени шифрования, которые мы здесь кратко обсуждаем. Эти атаки вообще не кончаются вскрытием системы, но они все-таки должны быть предотвращены. Для того чтобы сорвать эти виды атак, рекомендуется использовать e = 216 + 1 = 65537 (или простое число, близкое к этому значению).
Атака теоремы Куперcмита (Coppersmith) может быть главной для атаки малого показателя степени на ключ шифрования. Основное положение этой теоремы: для полинома f(x) степени e по модулю n, чтобы найти корни, если один из корней является меньшим чем n1/e, можно использовать алгоритм сложности, log n. Эта теорема может быть применена к C = f(P) = Pe mod n.
Если e = 3 и известны хотя бы две трети битов в исходном тексте P, алгоритм может найти все биты в исходном тексте.
Атака широковещательной передачи может быть начата, если один объект передает одно и то же сообщение группе получателей с тем же самым ключом шифрования. Например, предположим следующий сценарий: Алиса хочет передать одно и то же сообщение трем получателям с тем же самым общедоступным ключом e = 3 и модулями n1, n2 и n3.
C1 = P3 mod n1 C2 = P3 mod n2 C3 = P3 mod n3
Применяя китайскую теорему об остатках к этим трем уравнениям, Ева может найти уравнение формы C’ = P3 mod n1n2n3. Это означает, что P3 < n1n2n3 и что C’ = P3 решается с помощью обычной арифметики (не модульной). Ева может найти значение C’ = P1/3.
Атака связанных между собой сообщений была обнаружена Франклином Рейтером (Franklin Reiter). Она может быть кратко описана следующим образом. Алиса зашифровала два исходных текста, P1 и P2, с помощью e = 3 и передает C1 и C2 Бобу. Если P1 связан с P2 P1 и P2 в выполнимое время вычисления.
Атака короткого списка, обнаруженная Куперсмитом, может быть кратко описана следующим образом. Алиса имеет сообщение М для передачи Бобу. Она записывает сообщение и зашифровывает его как сообщение r1, а результат записывает как C1 и передает C1 (Бобу). Ева перехватывает C1 и удаляет его. Боб сообщает Алисе, что он не получил сообщение, так что Алиса заполняет сообщение, снова зашифровывает как сообщение r2 и передает это Бобу. Ева также перехватывает и это сообщение. Ева теперь имеет C1 и C2, и она знает, что оба зашифрованных текста принадлежат одному и тому же исходному тексту. Куперсмит доказал, что если r1 и r2 короткие, то Ева способна восстановить первоначальное сообщение М.
Две формы атак могут быть проведены на показатель степени дешифрации: атака раскрытой степени дешифрации и атака малого показателя степени дешифровации. Они обсуждаются ниже.
Атака раскрытого показателя степени дешифрации. Очевидно, что если Ева может найти показатель степени дешифрации, d, она сможет расшифровать текущее зашифрованное сообщение. Однако на этом атака не останавливается. Если Ева знает значение d, она может использовать вероятностный алгоритм (не обсуждаемый здесь) к числу n и найти значения p и q. Следовательно, если Боб изменит только угрожающий безопасности показатель степени дешифрования, но сохранит тот же самый модуль n, Ева сможет расшифровать будущие сообщения, потому что она сможет разложить на множители n. Поэтому если Боб узнает, что показатель степени скомпрометирован, он должен выбрать новое значение для p и q, вычислить n и создать полностью новые секретный и открытый ключи доступа.
Атака малого значения показателя степени дешифрации. Боб может подумать, что использование малого значения степени секретного ключа d приводит к более быстрой работе алгоритма дешифрации. Винер показал, что в случае d < 1/3n1/4 возможен специальный тип атаки, основанной на цепной дроби, — тема, которая рассматривается в теории чисел. Этот тип атаки может подвергнуть риску безопасность RSА. Для того чтобы это произошло, должно выполняться условие, что q < p < 2q; если эти два условия существуют, Ева может разложить n на сомножители в полиномиальное время.
d > 1/3 n1/4 , чтобы предотвратить атаку малого значения ключа дешифрации.Исходный текст и зашифрованный текст в 0 до n – 1 ). Другими словами, Ева уже знает кое-что об исходном тексте. Эти характеристики могут позволить некоторые атаки исходного текста. Три атаки были уже упомянуты в литературе: атака короткого сообщения, атака циклического повторения и явная атака.
Атака короткого сообщения. В атаке короткого сообщения, если Ева знает множество возможных исходных текстов, то ей известна еще одна информация и дополнительный факт, что зашифрованный текст — перестановка исходного текста. Ева может зашифровать все возможные сообщения, пока результат не будет совпадать с перехваченным зашифрованным текстом. Например, если известно, что Алиса посылает число с четырьмя цифрами Бобу, Ева может легко испытать числа исходного текста 0000 к 9999, чтобы найти исходный текст. По этой причине короткие сообщения должны быть дополнены случайными битами в начале и конце, чтобы сорвать этот тип атаки. Настоятельно рекомендуется заполнять исходный текст случайными битами прежде начала шифрования. Здесь используется метод, называемый OAEP, который будет позже обсужден в этой лекции.
Атака циклического повторения построена на факте, что если переставлять зашифрованный текст (перестановка исходного текста), то непрерывное шифрование зашифрованного текста в конечном счете кончится исходным текстом. Другими словами, если Ева непрерывно шифрует перехваченный зашифрованный текст C, она в итоге получит исходный текст. Однако сама Ева не знает, каков исходный текст, так что ей неизвестно, когда пора остановиться. Она должна пройти один шаг далее. Когда она получает зашифрованный текст C снова, она возвращается на один шаг, чтобы найти исходный текст.
Перехваченный зашифрованный текст C C1 = Ce mod n C2 = C1e mod n ……………… Ck = Ck-1e mod n ->, если Ck = C, останов: исходный текст - P = Ck-1
Может ли это быть серьезной атакой на криптосистему n. Другими словами, нет никакого эффективного алгоритма, который может завершить эту атаку в полиномиальное время, если n является большим.
Явная атака сообщения. Другая атака, которая базируется на отношениях перестановки между исходным текстом и зашифрованным текстом, — явная атака сообщения. Явное сообщение — сообщение, которое зашифровано само в себя (не может быть скрыто). Было доказано, что есть всегда некоторые сообщения, которые шифруются сами в себя. Поскольку ключ шифрования обычно нечетен, имеются некоторые исходные тексты, которые зашифрованы сами в себя, такие как P = 0 и P = 1. Но если ключ шифровки выбран тщательно, число их незначительно. Программа шифровки может всегда проверить, является ли вычисленный зашифрованный текст таким же, как исходный текст, и отклонить $${P^{{e_B}}}$$ исходный текст перед передачей зашифрованного текста.
Главной атакой
Общая атака модуля. Она может быть начата, если сообщество $${C^{{d_B}}}$$ использует общий модуль, n. Например, люди в сообществе могли бы позволить третьей стороне, которой они доверяют, выбирать p и q, вычислять n и $$\varphi (n)$$ и создать пару образцов ( ei, di ) для каждого объекта. Теперь предположим, что Алиса должна передать сообщение Бобу. Зашифрованный текст Бобу — это $$C = {P^{{e_B}}}\bmod n$$ Боб использует свой секретный ключ, dB, чтобы расшифровывать сообщение: $$P = {C^{{d_B}}}\bmod n$$. Проблема в том, что Ева может также расшифровать сообщение, если она — член сообщества и ей была назначена пара образцов ( eE и dE ), как мы узнали в разделе "атака малого значения ключа дешифрации". Используя свои собственные ключи ( eE и dE ), Ева может начать вероятностную атаку на сомножители n и найти dB Боба. Чтобы сорвать этот тип атаки, модуль не должен быть в совместном пользовании. Каждый объект должен вычислить свой собственный модуль.
Предыдущие атаки базировались на основной структуре RSА. Как показал Дэн Бонех (Dan Boneh), есть несколько атак реализации RSА. Мы приведем две из них: атака анализом времени и атака мощности.
Атака анализом времени (Timing attack). Пауль Кочер (Paul Kocher) демонстрировал атаку только зашифрованного текста, называемую атака анализом времени. Атака основана на быстром алгоритме с показательным временем, который рассмотрен в лекциях 12-13. Алгоритм использует только возведение во вторую степень, если соответствующий бит в секретном показателе степени d есть 0 ; он используется и при возведении во вторую степень и умножении, если соответствующий бит — 1. Другими словами, синхронизация требует сделать каждую итерацию более длинной, если соответствующий бит — 1. Эта разность синхронизации позволяет Еве находить значение битов в d, один за другим.
Предположим, что Ева перехватила большое количество зашифрованных текстов от C1 до Cm. Также предположим, что Ева наблюдала, какое количество времени требуется для Боба, чтобы расшифровать каждый зашифрованный текст, от T1 до T2. Ева знает, сколько времени требуется для основных аппаратных средств, чтобы выполнить операцию умножения от t1 до tm., где t1 — время, требуемое для выполнения умножения.
Результат операции умножения = Результат $$\times {C_i}\bmod n$$.
Ева может использовать алгоритм 14.5, который является упрощенной версией алгоритма, используемого практически для вычисления всех бит в d ( d0 до d k-1 ).
Алгоритм устанавливает начальное значение d0 = 1 (потому что d должен быть нечетным) и вычисляет новые значения для T’is (время дешифрования относится к d1 до dk-1 ). Алгоритм затем предполагает, что следующий бит — это 1, и находит несколько значений D1 до D2, основываясь на этом предположении.
RSA_Timing_Attack([T1…Tm])
{
d0 <- 1 // Потому что d — нечетное
Вычислить [t1…tm]
[T1…Tm] <- [T1…Tm] - [t1…tm]
for (j from 1 to k-1)
{ //Обновление Ti для следующего бита
Пересчитать [t1…tm]
//Пересчет ti в предположении, что следующий бит — это 1
[D1…Dm] <- [T1…Tm] -[t1…tm]
var <- variance ([D1…Dm]) – variance ([T1…Tm])
if (var > 0) dj <- 1 else dj <- 0
[T1…Tm] <- [T1…Tm] - dj x [t1…tm] //Обновление Ti для следующего бита
}
}
Если принятое предположение верно, то каждый Di является вероятно меньшим, чем соответствующее время передачи Ti. Однако алгоритм использует дисперсию (или другие критерии корреляции), чтобы рассмотреть все варианты Di и Ti. Если разность 1 в противном случае предполагает, что следующий бит — 0. Алгоритм тогда вычисляет новые Ti, используя для этого оставшиеся биты.
Есть два метода сорвать атаку анализом времени:
1. добавить случайные задержки к возведению в степень, чтобы каждое возведение в степень занимало одно и то же время;
2. Ривест рекомендовал "ослепление". По этой идее зашифрованный текст умножается на случайное число перед дешифрованием. Процедура содержит следующие шаги:
a. Выбрать секретное случайное число r между 1 и (n – 1).
b. Вычислить $${C_1} = C \times {r^e}\bmod n$$.
c. Вычислить P1 = C1d mod n.
d. Вычислить $$P = {P_1} \times {r^{ - 1}}\bmod n$$.
Атака анализом мощности подобна атаке анализом времени. Было показано, что если Ева может точно измерить мощность, использованную в течение дешифрования, она может начать атаку анализа мощности на основании принципов, рассмотренных для атаки анализом времени.
Следующие рекомендации основаны на теоретических и экспериментальных результатах.
n должно быть, по крайней мере, 1024. Это означает, что n должно быть приблизительно 21024, или 309 десятичных цифр.p и q должны каждый быть по крайней мере 512 битов. Это означает, что p и q должны быть приблизительно 2512 или 154 десятичными цифрами.p и q не должен быть очень близки друг к другу.p – 1 и q – 1 должны иметь по крайней мере один большой простой сомножитель.p/q не должно быть близко к n не должен использоваться совместно.e должно быть 216 + 1 или целым числом, близким к этому значению.d, Боб должен немедленно изменить n так же, как e и d. Было доказано, что знание n и одной пары (e, d) может привести к открытию других пар того же самого модуля.Как мы упоминали ранее, короткое сообщение в
(рис 14.9) Оптимальное асимметричное дополнение шифрования (OAEP)Идея, показанная на рисунке 14.9, — это то, что P = P1 || P2, где P1 — замаскированная версия дополненного сообщения, М;
P2 передается, чтобы позволить Бобу найти маску.
Шифрование. Ниже показаны шаги процесса шифрования.
m -битовым. Мы обозначим его М.r из k бит. Обратите внимание, что r применяется только однажды и затем уничтожается.G, которая принимает целое r -битовое число, и создает m -разрядное целое число ( m — размера М, и r <m ). Это — маска.G (r), чтобы создать первую часть исходного текста $${P_1} = M \oplus G(r)$$ является замаскированным сообщением.H — другая общедоступная функция, которая принимает m -битовые входные сообщения и создает k -битовые выходные сообщения. Эта функция может быть криптографической хэш-функцией ю P2 используется для того, чтобы дать возможность Бобу снова создать маску после дешифрации.C = Pe = (P1 || P2) e и передает C Бобу.Дешифрование. Следующие шаги показывают процесс дешифрования:
P = Cd = (P1 || P2).r, используя $$H({P_1}) \oplus {P_2} = H({P_1}) \oplus H\left( {{P_2}} \right) \oplus r = r$$.М, Боб находит первоначальное сообщение.Если хотя бы один бит в течение передачи принят с ошибкой, текст, зашифрованный
Пример 14.8
Вот — реальный пример. Мы выбираем 512 -битовые p и q, вычисляем n и $$\varphi (n)$$, затем выбираем e и испытываем, что оно взаимно простое с $$\varphi (n)$$. Затем мы вычисляем d. Наконец, мы показываем результат шифрования и дешифрования. Целое число p — это число со 159 цифрами.
P = 961303453135835045741915812806154279093098455949962158225831508 796479404550564706384912571601803475031209866660649242019180878 0667421096063354219926661209
Целое число q содержит 160 цифр.
q = 12060191957231446918276794204450896001555925054637033936061 798321731482148483764659215389453209175225273226830107120695604 602513887145524969000359660045617
Модуль $$n = p \times q$$. Это число имеет 309 цифр.
n = 1159350417396761496889250986461588752377145737545414477548552613 7614788540S32635081727687881596832516846884930062548576411125016 241455233918.292716250765677272746009708271412773043496050055634 7274566628060099924037102991424472292215772798531727033839381334 692684137 327622000966676671831831088373420823444370953
$$\varphi (n) = (p-1)(q-1)$$ имеет 309 цифр.
$$\tt\parindent0pt \varphi (n) = 115935041739676149688925098646158875237714573754541447754855 261376147885408326350817276878815968325168468849300625485764111 250162414552339182927162507656751054233608492916752034482627988 117554787657013923444405716989581728196098226361075467211864612 171359107358640614008885170265377277264467341066243857664128 $$Боб выбирает e = 35535 (идеально 65537 ), и испытание на простое число показывает, что это число и $$\varphi (n)$$ — взаимно простые числа. Затем Боб находит инверсию $$e\bmod \varphi (n)$$ — это обозначается d.
e = 35535 ________________________________________________________________ d = 58008302S6003776393609366128967791759466906208965096218042286 6111380593852S2235873170628691003002171085904433840217072986908 760061153062025249598844480475682409662470814858171304632406440 777048331340108509473852956450719367740611973265574242372176176 74620776371642 0760033708533328853214470885955136670294831
Алиса хочет передать сообщение "THIS IS TEST", которое может быть представлено числовыми значениями, используя схему кодирования 00-26 ( 26 — пробел).
P = 1907081826081826002619041819
Шифрованный текст, вычисленный Алисой, — это C = Pe, числовое значение приведено ниже.
С = 4753091236462268272063655506105451809423717960704917165232392 430544529606131993285666178434183591141511974112520056829797945 717360361012782188478927415660904800235071907152771859149751884 658886321011483541033616578984679683867637337657774656250792805 2114814184404814184430812773059004692874248559166462108656 Боб может восстановить из зашифрованного текста исходный
Боб может восстановить из зашифрованного текста исходный текст, используя P = Cd.
P = 1907081826081826002619041819
После расшифровки восстановленный исходный текст — "THIS IS TEST".
Хотя
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.