Криптосистема Рабина (М. Rabin) является вариантом e и d присвоены значения e = 2 и d = 1/2. Другими словами, шифрование — $$C \equiv {p^2}{\text{ }}(\bmod {\text{ }}n)$$ и P = C1/2 (mod n).
Открытый ключ доступа в n, секретный ключ является (p, q). Каждый может зашифровать сообщение, используя n, но только Боб может расшифровать сообщение, используя p и q. p и q. Рисунок 15.1 показывает шифрование и
(рис 15.1) Шифрование, дешифрование и генерация ключей в криптосистеме Рабина Мы должны подчеркнуть, что если Боб использует d и n и отказаться после p, q и $$\varphi (n)$$. Если Боб использует криптосистему Рабина, он должен сохранить p и q.
Боб использует шаги, показанные в алгоритме 15.1, чтобы создать свой открытый ключ доступа и секретный ключ.
$$\tt\parindent0pt
Rabin\_Key\_Generation
\{
Выберите два больших простых числа $p$ и $q$ в форме $4k +3$ и $p \ne q$.
\ $n \gets p \times q$
Открытый\_ключ $\gets n$\ \ \ \ \ // Может быть объявлен публично
Секретный\_ключ $\gets (q,n)$\ \ \ \ \ // Должен сохраняться в секрете
return Открытый\_ключ и Секретный\_ключ
\} $$
Хотя два простых числа, p и q, могут быть в форме 4k + 1 или 4k + 3, процесс 4k + 3, для того чтобы сделать
Любой может передать сообщение Бобу, используя его открытый ключ доступа. Процесс шифрования показан алгоритмом 15.2.
Rabin_Encryption (n, P) // n — открытый ключ доступа;
P — зашифрованный текст Z*n
{
C <- P2 mod n // C — зашифрованный текст
return C
}
Хотя исходный текст P может быть выбран из множества Zn, но чтобы сделать Zn*.
Шифрование в
Боб может использовать алгоритм 15.3, чтобы расшифровать полученный зашифрованный текст.
Rabin_Decryption (p, q, C) // C — зашифрованный текст; p и q — секретные ключи a1 <- + (C(p+1)/4) mod p a2 <- - (C(p+1)/4) mod p b1 <- + (C(q+1)/4) mod q b2 <- - (C(q+1)/4) mod q // Алгоритм китайской теоремы об остатках вызывается четыре раза. P1 <- Китайский_остаток (a1, b1, p, q) P2 <- Китайский_остаток (a1, b2, p, q) P3 <- Китайский_остаток (a2, b1, p, q) P4 <- Китайский_остаток (a2, b2, p, q) return P1, P2, P3 и P4
Мы должны подчеркнуть здесь несколько моментов. Дешифрация базируется на решении квадратичного сравнения, которое рассмотрено в лекциях 12-13. Поскольку полученный зашифрованный текст — квадрат исходного текста, это гарантирует, что C имеет корни (квадратичные Zn*. Алгоритм китайской теоремы об остатке используется, чтобы найти четыре квадратных корня.
Самый важный пункт в
Пример 15.1
Вот очень тривиальный пример, чтобы проиллюстрировать идею.
1. Боб выбирает p = 23 и q = 7. Обратите внимание, что оба являются сравнениями 3 mod 4.
2. Боб вычисляет $$n = p \times q = 161$$.
3. Боб объявляет n открытым и сохраняет p и q в секрете.
4. Алиса хочет передать исходный текст P = 24. Обратите внимание, что 161 и 24 являются взаимно простыми; 24 находится в Z161*. Она вычисляет C = от 242 = 93 mod 161 и передает зашифрованный текст 93 Бобу.
5. Боб получает 93 и вычисляет четыре значения:
а. a1 = + (93 (23+1)/4) mod 23 = 1 mod 23
b. a2 = – (93 (23+1)/4) mod 23 = 22 mod 23
с. b 1 = + (93 (7+1)/4) mod 7 = 4 mod 7
d. b2 = – (93 (7+l)/4) mod 7 = 3 mod 7
(a1, b 1), (a1, b2),(a2, b 1), (a2, b2) и использует китайскую теорему об остатках, чтобы найти четыре возможных исходных текста: 116, 24, 137 и 45 (все из них взаимно простые к 161 ). Обратите внимание, что только второй ответ — исходный текст Алисы. Боб должен принять решение исходя из ситуации. Обратите внимание также, что все четыре ответа при возведении во вторую степень по модулю n дают зашифрованный текст 93, переданный Алисой.1162 = 93 mod 161 242 = 93 mod 161 1372 = 93 mod 161 452 = 93 mod 161
p и q — большие числа. Сложность n на два простых сомножителя p и q. Другими словами,
Помимо
На основании сведений лекций 12-13, если p — очень большое простое число, e1 — r — целое число, тогда e2 = e1r mod p просто вычисляется с использованием быстрого показательного алгоритма (метод "возведения в квадрат и умножения"). Но по данным e2, e1 и p, невозможно вычислить r = loge1e2 mod p (проблема
Рисунок 15.2 показывает
(рис 15.2) Генерация ключей, шифрование, и дешифрование в криптосистеме Эль-Гамаля Боб использует шаги, показанные в алгоритме 15.4, чтобы создать свои общедоступный и частный ключи.
ElGamal_Key_Generation
{
Выберите большое простое число p
Выберите d, члена группы G = < Zp*, x > , такое, что 1 < d < p – 2
Выберите e1 — первообразный корень в группе G = < Zp*, x >
e2 <- e1d mod p
Общедоступный_ключ <- (e1, e2, p) // Может быть объявлен публично
Частный_ключ <- -d // Должен сохраняться в секрете
return Общедоступный_ключ и Частный_ключ
}
Любой может передать сообщение Бобу, используя его открытый ключ доступа. Процесс шифрования показан в алгоритме 15.5. Если применяется быстрый показательный алгоритм (см. лекции 12-13), шифрование в
ElGamal_Encryption (e1, e2, p) // P — исходный текст
{
Выберите случайное целое число r в группе G = < Zp*, x >
C1 <- e1r mod p
C2 <- (P x e2r) mod p // C1 и C2 – зашифрованные тексты
return C1 и C2 }
Боб может использовать алгоритм 15.6, чтобы расшифровать полученное сообщение зашифрованного текста.
ElGamal_Decryption {d, p, C1, C2) // C1 и C2 — зашифрованный текст
{
P <- [C2(C1d)-1] mod p // P — исходный текст
return P
}
P:
Пример 15.2
Рассмотрим тривиальный пример. Боб выбирает 11 в качестве p. Затем он выбирает e1 = 2. Обратите внимание, что 2 — Z11* (см. приложение J). Затем Боб выбирает d = 3 и вычисляет e2 = e1d = 8. Получены открытые ключи доступа — (2, 8, 11) и секретный ключ — 3. Алиса выбирает r = 4 и вычисляет C1 и C2 для исходного текста 7.
Исходный текст: 7 C1 = e1r mod 11 = 16 mod 11= 5 mod 11 C2 = (P x e2r) mod 11 = (7 x 4096) mod 11 = 6 mod 111 Зашифрованный текст: (5, 6)
Боб получает зашифрованные тексты ( 5 и 6 ) и вычисляет исходный текст.
Зашифрованный текст: [C1 x (C2d)-1] mod 11 = 6 x (53)-1 mod 11 = 6 x 3 mod 11 = 7 mod 11 Исходный текст: 7
Пример 15.3
Вместо того чтобы использовать $$P = [{C_2}{({C_1}^d)^{-1}}]\bmod p$$ для
Очень интересная черта r и сохраняет его в секрете; Боб создает d и сохраняет его в секрете. Это затруднение
a. Алиса передает $${C_2} = [{e_2}^r \times P]{\text{ }}\bmod {\text{ }}p = [({e_1}^{rd}) \times P]{\text{ }}\bmod {\text{ }}p$$. Выражение ( e1rd ) действует как маска, которая скрывает значение P. Чтобы найти значение P, Боб должен удалить эту маску.
b. Поскольку используется модульная арифметика, Боб должен создать точную копию маски и инвертировать ее (мультипликативная
c. Алиса передает Бобу C1 = e1r, что является частью маски. Боб должен вычислить C1d, чтобы cделать точную копию маски, поскольку C1d = (e1r') d= (e1 rd). Другими словами, после получения точной копии маски Боб инвертирует ее и умножает результат на C2, чтобы удалить маску.
d. Это можно представить так, что Боб помогает Алисе сделать маску (e1rd), не показывая значение d ( d уже включено в e2 = e1rd ); Алиса помогает Бобу делать маску ( e1 rd ), не раскрывая значение r ( r уже включено в C1 = e1r ).
Ранее были упомянуты две атаки на криптосистему Эль-Гамаля — атаки, основанные на малом значении модуля, и атаки знания исходного текста.
Если значение модуля p не является достаточно большим, Ева может использовать некоторые эффективные алгоритмы, чтобы решить проблему d или r. Если p мало, Ева может просто найти d = loge1e2 mod p и сохранить его, чтобы расшифровать любое сообщение, передаваемое Бобу. Это может быть сделано единожды и работать, пока Боб использует те же самые ключи. Ева может также использовать значение случайного числа r, применяемого Алисой в каждой передаче r = loge1C1 mod p. Оба этих случая подчеркивают, что безопасность p должны быть по крайней мере 1024 бита ( 300 десятичных цифр).
Когда Алиса использует одно и то же значение случайного показателя степени r для того, чтобы зашифровать два исходных текста P и P', Ева обнаруживает P', если она знает P. Предположим, что $${C_2} = P \times ({e_2}^r)\bmod {\text{ }}p$$ и $${C'_2} = P' \times ({e_2}^r)\bmod {\text{ }}p$$. Ева находит P', используя следующие шаги:
Поэтому рекомендовано, чтобы Алиса брала при каждой передаче новое значение r, чтобы сорвать атаки.
p должен содержать по крайней мере 300 десятичных цифр, новых для каждой шифровки.Пример 15.4
Вот более реальный пример. Боб использует случайное целое число длиной 512 битов (идеально — 1024 ) и целое число p длиной 155 цифр (идеал — 300 цифр). Боб выбирает e1 и d, затем вычисляет e2, как показано ниже; Боб объявляет (e1, e2, p) как свой открытый ключ и d как секретный ключ доступа.
p = 1153489927256167624492531371701433174049009453260983495981434692 19056898698622645932129754737871895144368891765264730936159299937 28061165964347353440008577 ___________________________________________________________________ e1= 2 ___________________________________________________________________ d = 1007 ___________________________________________________________________ e2 = 9788641304300918950876685693809773904388006288733768761002206223 32554507074156189212318317704610141673360150884132940857248537703 1582066010072558707455
Алиса имеет исходный текст P = 3200, чтобы передать Бобу. Она выбирает r = 545131, вычисляет C1 и C2 и передает их Бобу.
P = 3200 r = 545131 _____________________________________________________________________ C1 = 8872970693835284710225704714922756631202600672565621250181883514 29417223599712681114105363661705173051581533189165400973736355080 295736788569060619152881 _____________________________________________________________________ C2 = 7084543330489299445770160123807949995674360218361924469617745069 2124469615516580077945559308034588961440240859952591957920972162 88796813505827795664302950
Боб вычисляет исходный текст $$P{\text{ }} = {C_2} \times {({C_1}^d)^{ - 1}}\bmod p{\text{ }} = 3200\bmod p$$
P = 3200
Хотя
y2 + b1xy + b2y = x3 + a1x2 + a2x +a3
y2 = x3 + ax + b
В этом случае, если $$4{a^3} + 27{b^2} \ne 0$$, уравнение представляет несингулярную эллиптическую кривую ; в противоположном случае оно описывает сингулярную эллиптическую кривую. Для несингулярной x3 + ax + b = 0 имеет три отличных корня (вещественных или комплексных); для сингулярной уравнение x3 + ax + b = 0 не имеет трех отличных корней.
В уравнении, как мы можем видеть, левая сторона ( y2 ) имеет степень 2, в то время как правая сторона имеет степень 3 ( x3 ). Это означает, что горизонтальная линия может пересекать кривую в трех точках, если все корни вещественные. Однако вертикальная линия может пересечь кривую самое большее в двух точках.
Пример 15.5
Рисунок 15.3 показывает две y2 = x3 – 4x и y2 = x 3 – 1. Оба уравнения несингулярны. Однако первое имеет три вещественных корня ( x = -2, x = 0, и x = 2 ), но второе — только один вещественный корень ( x = 1 ) и два мнимых.
(рис 15.3) Две эллиптические кривые в поле вещественных чисел Определим абелеву (коммутативную) группу (см. лекции 5-6), использующую точки на P = (x1, y1) представляет точку на кривой, если x1 и y1 — координаты точки на кривой, которые удовлетворяют уравнению этой кривой. Например, точки P = (2,0; 0,0), Q = (0,0; 0,0), R = (–2,0; 0,0), S = (10,0;30,98), и T = (10,0; –30,98) – точки на кривой y2 = x3 – 4x. Обратите внимание, что каждая точка представлена двумя вещественными числами. По материалам лекций 5-6, для создания абелевой группы мы нуждаемся во множестве операций над множествами и пяти свойствах, которым удовлетворяют операции. В этом случае группа G = <E, +> — абелева.
Множество. Мы определим множество как точки на кривой, где каждая точка — пара вещественных чисел. Например, множество E для y2 = –x3 – 4x показано как
E = {(2,0; 0,0), (0,0; 0,0), (-2,0; 0,0), (10,0; 30,98), (10,0,-30,98)...}
Операция. Заданные свойства несингулярной
R = P + Q, где P = (x1, y1), Q = (x2, y2), и R = (x3, y3)
Для того чтобы найти R на кривой, рассмотрим три случая, как это показано на рис. 15.4.
(рис 15.4) Три случая сложения на эллиптической кривой 1. В первом случае две точки P = (x1, y1) и Q = (x2, y2) имеют различные x -координаты и y -координаты ( $${x_1} \ne {y_1}$$ и $${x_2} \ne {y_2}$$ ), как это показано на рис. 15.4a. Линия, соединяющая P и Q, пересекает кривую в точке, обозначенной R. R есть отражение (-R) относительно y -оси. Координаты точки R, x3 и y3 могут быть найдены по наклону линии, $$\lambda,$$ и затем можно вычислить значений x3 и y3, как показано ниже:
2. Во втором случае две точки совпадают (R = P + P), как показано на рис. 15.4b. Наклон линии и координаты точки R могут быть найдены, как показано ниже.
3. В третьем случае две точки — аддитивные P = (x1, y1), а вторая точка равна Q = (x1, – y1), линия, соединяющая эти две точки, не пересекает кривую в третьей точке. Математики говорят в этом случае, что точка пересечения находится в бесконечности. Они определяют точку О (см. рис. 15.4с) как точку в бесконечности или нулевую точку, которая является аддитивным нейтральным элементом группы.
Свойства операции. Краткие определения свойств операции, как они обсуждались в лекциях 5-6:
(P + Q) + R = P + (Q + R).P + Q = Q + P.P + 0 = 0 + P.x. Другими словами, точки P = (X1,Y1) И Q = (X1, – Y1) — P + Q = 0. Заметим, что нейтральный элемент — это Обратите внимание, что предыдущие рассуждения касаются двух алгебраических структур: группа и поле. Группа определяет множество точек на
Наша предыдущая группа p> 3. В модульной арифметике точки на кривой не
представляют графы, как это можно было видеть на предыдущих рисунках, но сохраняются те же самые основные концепции. Мы используем ту же самую операцию сложения, но с вычислением по модулю p. В результате мы получаем Ep (a, b), где p определяет модуль, и b — коэффициент уравнения y2 = x3 + ax + b. Обратите внимание, что хотя значение x в этом случае от 0 до p, обычно не все точки находятся на кривой.
(x, y) равна (x, – y), где (–y) — аддитивная y. Например, если p = 13, (4, 2) равна (4, 11).
Алгоритм 15.7 показывает программу в Ep (a, b).
$$\tt\parindent0pt
Elliptic\_points (p, a, b) // $p$-модуль
\{
$x \gets 0$
while ($x < p$)
\{
$w \gets (x^{3} + ax + b) \mod p$\ \ \ //$w$ – это $y^{2}$
if ($w$ – целое значение квадратного корня в $Z_{p}$) выход $((x, \sqrt w )(x, - \sqrt w ))$
$x \gets x + 1$
\}
\} $$
Пример 15.6
Определите E13 (1, 1) по уравнению y2 = x3 + x + 1 и вычислите по модулю 13. Точки на кривой могут быть найдены, как показано на рис. 15.5.
(рис 15.5) Точки на эллиптической кривой в поле GF (p)Обратите внимание на следующее:
а. Некоторые значения y2 не имеют квадратного корня по модулю 13. Они не являются точками на этой x = 2, x = 3, x = 6 и x = 9 не находятся на кривой.
б. Каждая точка, определенная на кривой, имеет (7, 0) —
в. Обратите внимание, что для пары обратных точек значения y — аддитивные Zp. Например, 4 и 9 — аддитивные Z13. Так что мы можем сказать, что если 4 — это значение y, то 9— это значение (–y).
г.
Мы используем группу GF (p). Вместо вычитания и деления мы применяем аддитивные и мультипликативные
Пример 15.7
Сложим две точки в примере 15.6, R = P + Q, где P = (4, 2) и Q = (10,6).
а. X = (6 – 2) x (10 – 4) -1 mod 13 = 4 x 6-1 mod 13 != 5 mod 13.
б. x = (52 – 4 – 10) mod 13 = 11 mod 13.
в. y = [5 (4 – 11) – 2] mod 13 = 2 mod 13.
г . R = (11, 2) является точкой на кривой в примере 15.6.
В арифметике умножение числа на константу k означает прибавление числа само к себе k раз. Здесь ситуация та же самая. Умножение точки P на k означает прибавление точки P к себе k раз. Например, в E13 (1, 1), если точка (1, 4) умножается на 4, результат есть точка (5, 1). Если точка (8,1) умножается на 3, результат — точка (10, 7).
Вычисление в группе GF(2n). В соответствии с лекциями 5-6, где мы говорили, что элементы множества в этом поле — n -битовые слова, которые можно интерпретировать как полиномы с коэффициентом в GF(2), сложение и умножение этих элементов такое же, как сложение и умножение полиномов. Для того чтобы определить GF(2n), необходимо только изменить кубическое уравнение. Общее уравнение
y2 + xy = x3 + ax2 + b
где $$b \ne 0$$. Обратите внимание, что значение x, y, a и b — полиномы, представляющие n -битовые слова.
Если P = (x, y), то (–P) = (x, x + y).
Мы можем написать алгоритм для нахождения точек на кривой, используя генераторы для полиномов, которые рассматривали в лекциях 9-10. Но разработку этого алгоритма оставляем как упражнение. Далее следует очень тривиальный пример.
Пример 15.8
Мы выбираем GF (2 3) с элементами (0,1, g, g2, g3, g 4, g5, g6), использующими неприводимый f (x) = x3 + x +1. Этому соответствует g3 + g +1 = 0 или g3 = g + 1. Другие степени g могут быть вычислены, как это показано ниже.
| 0 | 0 | g3 = g + 1 | 0 |
| 1 | 0 | g4 = g2 + g | 1 |
| g | 0 | g5 = g2 + g + 1 | 1 |
| g2 | 1 | g6 = g2 + 1 | 1 |
Используя y2 + xy = x3 + g3x2 + 1, a = g3 и b = 1, мы можем найти точки на этой кривой, как это показано на рисунке 15.6.
(рис 15.6) Точки на эллиптической кривой в GF (2 в степени n)
Правила для сложения точек в GF(2n) немного отличаются от правил GF(p).
1. Если P = (x1, y1), Q = (x2, y2), $$Q \ne -P$$, $$Q \ne P$$, то R = (x3, y3) = P + Q может быть найден как
2.Если Q = P, то R = P + P (или R = 2P ) и может быть найден как
Пример 15.9
Пусть нам надо найти R = P + Q, где P = (0,1) и Q = (g2,1). Мы имеем $$\lambda = 0$$ и R = (g5, g4).
Пример 15.10
Пусть нам надо найти R = 2P, где P = (g2,1). Мы имеем $$\lambda =g^{2} +1 /g^{2} = g^{2}+ g^{5}= g +1$$ и R = (g6, g5).
Для того чтобы умножить точку на константу, точки должны складываться непрерывно согласно правилу R = 2P.
Для шифрования и GF(p) или GF(2n), как это показано на рис. 15.7.
(рис 15.7) Криптосистема Эль-Гамаля, использующая эллиптическую функцию E (a,b) с GF(p) или GF(2n).e1 (x 1, y1 ).d.E (a,b), e1 (x1, y1 ) и e2 (x2, y2) как свой открытый ключ доступа; он сохраняет d как секретный ключ.Алиса выбирает P, точку на кривой, как ее исходный текст, P. Затем она вычисляет пару точек, направляет как зашифрованный текст:
Читатель может задаться вопросом, как произвольным исходным
C1 = r x e1 C2 = P + r x e2
Текстом может быть точка на
Боб, после получения C1 и C2, вычисляет P, исходный текст, используя следующую формулу:
P = C2 – (d x C1) Знак "минус" здесь означает сложение с инверсией.
Мы можем доказать, что P, вычисленный Бобом, — тот же, что передан Алисой, как это показано ниже:
P, C 1, C2 и e2 — это точки на кривой. Обратите внимание, что результат сложения двух обратных точек на кривой — нулевая точка.
Пример 15.11
Вот очень тривиальный пример шифровки с использованием GF (p).
E67 (2, 3) как GF (p).e1 = (2, 22) и d = 4.e2 = (13, 45), где $${e_2} = d \times {e_1}$$.(E, e1, e2).P = (24, 26) Бобу. Она выбирает r = 2.C1= (35, 1), где $${C_1} = r \times {e_1}$$.C2 = (21, 44), где $${C_2} = P \times {e_1}$$.C, и C2. Он использует $$2 \times {C_1}$$, (35, 1) и получает (23, 25).(23, 25) и получает точку (23, 42).(23, 42) с C2 = (21, 44) и получает первоначальный исходный текст P = (24, 26).Ниже приводится краткое сравнение алгоритма Эль-Гамаля с его вариантом, использующим
a. Алгоритм Эль-Гамаля использует мультипликативную группу; вариант — эллиптическую группу.
b. Эти два члена в алгоритме Эль-Гамаля — числа в мультипликативной группе; при применении варианта — точки на
c. Секретный ключ в каждом алгоритме — целое число.
d. Секретные числа, выбираемые Алисой в каждом алгоритме, — целые числа.
e. Возведение в степень в алгоритме Эль-Гамаля заменено умножением точки на константу.
f. Умножение в алгоритме Эль-Гамаля заменено сложением точек.
g.
h. Вычисление обычно легче в
Чтобы расшифровать сообщение, Ева должна найти значение r или d.
a. Если Ева знает значение r, она может использовать $$P = {C_2}-(r \times {e_2})$$, чтобы найти точку P, относящуюся к исходному тексту. Но для того чтобы найти r, Ева должна решить уравнение $${C_1} = r \times {e_1}$$. Это значит — найти две точки на кривой, C1 и e1. Ева должна найти множитель, который создает C1 начиная с e1. Эта проблема известна как проблема логарифма эллиптической кривой, единственный известный метод решения этой проблемы — $$РО(\rho )$$ - алгоритм Поларда, который неосуществим, если задано большое r и p в GF (p) или большое n в GF(2n).
b. Если Ева знает значение d, она может использовать $$P = {C_2} - (d \times {C_1})$$, чтобы найти точку P, относящуюся к исходному тексту. Поскольку $${e_2} = d \times {e_1}$$, это тот же самый тип проблемы, что и в предыдущем пункте. Ева знает значение e1 и e2 — она должна найти d.
Для того же самого уровня безопасности (затраты на вычисление) модуль n, может быть меньшим в эллиптической системе (GF(2n) с n, состоящим из 160 битов, может обеспечить тот же уровень безопасности, как n 1024 битов.
Для более детального изучения положений, обсужденных в этой лекции, мы рекомендуем нижеследующие книги и сайты. Пункты, указанные в скобках, показаны в списке ссылок в конце книги.
Следующие сайты дают больше информации о темах, рассмотренных в этой лекции.
f вычисляется просто, а f -1 вычислить невозможно (в смысле сложности вычислений), если не используется лазейка.e и d, где e — общедоступный ключ, а d является частным (секретным). Алиса использует C = Pe mod n для того, чтобы создать зашифрованный текст C из исходного текста P ; Боб использует P = Сd mod n, чтобы извлечь исходный текст, переданный Алисой.e = 2 и d = 1/2. p и q — большие числа. Сложность n на два простых сомножителя p и q.Zn*. Шифрование и e1 и e2, а секретный ключ — это целое число d. Безопасность y2 = x3 + ax + b, где $$4{a^3} + 27{b^2} \ne 0$$. Абелева группа была определена с помощью GF (p) и GF (2n). Мы показали, как b = [7, 11,23,43,87, 173, 357], r =41 и модуль n = 1001, зашифруйте и расшифруйте букву a, используя ранцевую криптосистему. Используйте [7 6 5 1 2 3 4] как таблицу перестановки.n = 221 и e = 5, найдите d.n =3937 и e =17, найдите d.p = 19, q = 23 и e = 3, найдите n, $$\varphi ,$$ (n) (^) и d.d, если вы знаете, что e =17, а n =187.n и $$\varphi (n)$$, вычислите p и q.e = 13 и n = 100.
Зашифруйте сообщение "HOW ARE YOU", применяя 00 к 25 для букв от A до Z и 26 — для пробела. Используйте различные блоки, чтобы сделать P <n.n = 12091 и e = 13. Зашифруйте сообщение "THIS IS THOGH", используя схему кодирования 00 к 26. Расшифровать зашифрованный текст, чтобы найти первоначальное сообщение.1 как открытый ключ e?2 открытым ключом?(e = 17, n = 19519), чтобы передать сообщение из четырех символов Бобу, применяющему схему $$A \leftrightarrow 0$$, $$B \leftrightarrow 1...Z \leftrightarrow 25$$ кодирования и декодирования по каждому символу отдельно. Ева перехватывает зашифрованный текст (6625 0 2968 17863) и расшифровывает сообщение, не разлагая на множители модуль. Найдите исходный текст; объясните, почему Ева смогла легко взломать зашифрованный текст.(e = 7, n = 143), чтобы передать исходный текст P = 8, зашифрованный в виде текста C = 57. Покажите, как Ева может использовать атаку выборки текста, если она имеет доступ к компьютеру Боба, чтобы найти исходный текст.(e = 3, n = 35) и передает зашифрованный текст 22 Бобу. Покажите, как Ева может найти исходный текст, используя атаку циклического повторения.p = 47 и q =11:P = 17 и найдите зашифрованный текст.p = 31:e1 и d, затем вычислите e2."HELLO" ; используйте 00 к 25 для кодирования. Используйте различные блоки для того, чтобы сделать P<p.C1 и C2 будут изменены в течение передачи?e1 = 2 и e 2 = 8 ), чтобы передать два сообщения — P = 17 и P' = 37. Они оба используют то же самое случайное целое число r = 9. Ева перехватывает зашифрованный текст и так или иначе находит значение P = 17. Покажите, как Ева может использовать атаку знания исходного текста, чтобы найти значение P'.E (1, 2) в поле GF (11):d.E (g4, 1) в поле GF(24):GF(p).GF(2n).Криптосистема Рабина (М. Rabin) является вариантом e и d присвоены значения e = 2 и d = 1/2. Другими словами, шифрование — $$C \equiv {p^2}{\text{ }}(\bmod {\text{ }}n)$$ и P = C1/2 (mod n).
Открытый ключ доступа в n, секретный ключ является (p, q). Каждый может зашифровать сообщение, используя n, но только Боб может расшифровать сообщение, используя p и q. p и q. Рисунок 15.1 показывает шифрование и
(рис 15.1) Шифрование, дешифрование и генерация ключей в криптосистеме Рабина Мы должны подчеркнуть, что если Боб использует d и n и отказаться после p, q и $$\varphi (n)$$. Если Боб использует криптосистему Рабина, он должен сохранить p и q.
Боб использует шаги, показанные в алгоритме 15.1, чтобы создать свой открытый ключ доступа и секретный ключ.
$$\tt\parindent0pt
Rabin\_Key\_Generation
\{
Выберите два больших простых числа $p$ и $q$ в форме $4k +3$ и $p \ne q$.
\ $n \gets p \times q$
Открытый\_ключ $\gets n$\ \ \ \ \ // Может быть объявлен публично
Секретный\_ключ $\gets (q,n)$\ \ \ \ \ // Должен сохраняться в секрете
return Открытый\_ключ и Секретный\_ключ
\} $$
Хотя два простых числа, p и q, могут быть в форме 4k + 1 или 4k + 3, процесс 4k + 3, для того чтобы сделать
Любой может передать сообщение Бобу, используя его открытый ключ доступа. Процесс шифрования показан алгоритмом 15.2.
Rabin_Encryption (n, P) // n — открытый ключ доступа;
P — зашифрованный текст Z*n
{
C <- P2 mod n // C — зашифрованный текст
return C
}
Хотя исходный текст P может быть выбран из множества Zn, но чтобы сделать Zn*.
Шифрование в
Боб может использовать алгоритм 15.3, чтобы расшифровать полученный зашифрованный текст.
Rabin_Decryption (p, q, C) // C — зашифрованный текст; p и q — секретные ключи a1 <- + (C(p+1)/4) mod p a2 <- - (C(p+1)/4) mod p b1 <- + (C(q+1)/4) mod q b2 <- - (C(q+1)/4) mod q // Алгоритм китайской теоремы об остатках вызывается четыре раза. P1 <- Китайский_остаток (a1, b1, p, q) P2 <- Китайский_остаток (a1, b2, p, q) P3 <- Китайский_остаток (a2, b1, p, q) P4 <- Китайский_остаток (a2, b2, p, q) return P1, P2, P3 и P4
Мы должны подчеркнуть здесь несколько моментов. Дешифрация базируется на решении квадратичного сравнения, которое рассмотрено в лекциях 12-13. Поскольку полученный зашифрованный текст — квадрат исходного текста, это гарантирует, что C имеет корни (квадратичные Zn*. Алгоритм китайской теоремы об остатке используется, чтобы найти четыре квадратных корня.
Самый важный пункт в
Пример 15.1
Вот очень тривиальный пример, чтобы проиллюстрировать идею.
1. Боб выбирает p = 23 и q = 7. Обратите внимание, что оба являются сравнениями 3 mod 4.
2. Боб вычисляет $$n = p \times q = 161$$.
3. Боб объявляет n открытым и сохраняет p и q в секрете.
4. Алиса хочет передать исходный текст P = 24. Обратите внимание, что 161 и 24 являются взаимно простыми; 24 находится в Z161*. Она вычисляет C = от 242 = 93 mod 161 и передает зашифрованный текст 93 Бобу.
5. Боб получает 93 и вычисляет четыре значения:
а. a1 = + (93 (23+1)/4) mod 23 = 1 mod 23
b. a2 = – (93 (23+1)/4) mod 23 = 22 mod 23
с. b 1 = + (93 (7+1)/4) mod 7 = 4 mod 7
d. b2 = – (93 (7+l)/4) mod 7 = 3 mod 7
(a1, b 1), (a1, b2),(a2, b 1), (a2, b2) и использует китайскую теорему об остатках, чтобы найти четыре возможных исходных текста: 116, 24, 137 и 45 (все из них взаимно простые к 161 ). Обратите внимание, что только второй ответ — исходный текст Алисы. Боб должен принять решение исходя из ситуации. Обратите внимание также, что все четыре ответа при возведении во вторую степень по модулю n дают зашифрованный текст 93, переданный Алисой.1162 = 93 mod 161 242 = 93 mod 161 1372 = 93 mod 161 452 = 93 mod 161
p и q — большие числа. Сложность n на два простых сомножителя p и q. Другими словами,
Помимо
На основании сведений лекций 12-13, если p — очень большое простое число, e1 — r — целое число, тогда e2 = e1r mod p просто вычисляется с использованием быстрого показательного алгоритма (метод "возведения в квадрат и умножения"). Но по данным e2, e1 и p, невозможно вычислить r = loge1e2 mod p (проблема
Рисунок 15.2 показывает
(рис 15.2) Генерация ключей, шифрование, и дешифрование в криптосистеме Эль-Гамаля Боб использует шаги, показанные в алгоритме 15.4, чтобы создать свои общедоступный и частный ключи.
ElGamal_Key_Generation
{
Выберите большое простое число p
Выберите d, члена группы G = < Zp*, x > , такое, что 1 < d < p – 2
Выберите e1 — первообразный корень в группе G = < Zp*, x >
e2 <- e1d mod p
Общедоступный_ключ <- (e1, e2, p) // Может быть объявлен публично
Частный_ключ <- -d // Должен сохраняться в секрете
return Общедоступный_ключ и Частный_ключ
}
Любой может передать сообщение Бобу, используя его открытый ключ доступа. Процесс шифрования показан в алгоритме 15.5. Если применяется быстрый показательный алгоритм (см. лекции 12-13), шифрование в
ElGamal_Encryption (e1, e2, p) // P — исходный текст
{
Выберите случайное целое число r в группе G = < Zp*, x >
C1 <- e1r mod p
C2 <- (P x e2r) mod p // C1 и C2 – зашифрованные тексты
return C1 и C2 }
Боб может использовать алгоритм 15.6, чтобы расшифровать полученное сообщение зашифрованного текста.
ElGamal_Decryption {d, p, C1, C2) // C1 и C2 — зашифрованный текст
{
P <- [C2(C1d)-1] mod p // P — исходный текст
return P
}
P:
Пример 15.2
Рассмотрим тривиальный пример. Боб выбирает 11 в качестве p. Затем он выбирает e1 = 2. Обратите внимание, что 2 — Z11* (см. приложение J). Затем Боб выбирает d = 3 и вычисляет e2 = e1d = 8. Получены открытые ключи доступа — (2, 8, 11) и секретный ключ — 3. Алиса выбирает r = 4 и вычисляет C1 и C2 для исходного текста 7.
Исходный текст: 7 C1 = e1r mod 11 = 16 mod 11= 5 mod 11 C2 = (P x e2r) mod 11 = (7 x 4096) mod 11 = 6 mod 111 Зашифрованный текст: (5, 6)
Боб получает зашифрованные тексты ( 5 и 6 ) и вычисляет исходный текст.
Зашифрованный текст: [C1 x (C2d)-1] mod 11 = 6 x (53)-1 mod 11 = 6 x 3 mod 11 = 7 mod 11 Исходный текст: 7
Пример 15.3
Вместо того чтобы использовать $$P = [{C_2}{({C_1}^d)^{-1}}]\bmod p$$ для
Очень интересная черта r и сохраняет его в секрете; Боб создает d и сохраняет его в секрете. Это затруднение
a. Алиса передает $${C_2} = [{e_2}^r \times P]{\text{ }}\bmod {\text{ }}p = [({e_1}^{rd}) \times P]{\text{ }}\bmod {\text{ }}p$$. Выражение ( e1rd ) действует как маска, которая скрывает значение P. Чтобы найти значение P, Боб должен удалить эту маску.
b. Поскольку используется модульная арифметика, Боб должен создать точную копию маски и инвертировать ее (мультипликативная
c. Алиса передает Бобу C1 = e1r, что является частью маски. Боб должен вычислить C1d, чтобы cделать точную копию маски, поскольку C1d = (e1r') d= (e1 rd). Другими словами, после получения точной копии маски Боб инвертирует ее и умножает результат на C2, чтобы удалить маску.
d. Это можно представить так, что Боб помогает Алисе сделать маску (e1rd), не показывая значение d ( d уже включено в e2 = e1rd ); Алиса помогает Бобу делать маску ( e1 rd ), не раскрывая значение r ( r уже включено в C1 = e1r ).
Ранее были упомянуты две атаки на криптосистему Эль-Гамаля — атаки, основанные на малом значении модуля, и атаки знания исходного текста.
Если значение модуля p не является достаточно большим, Ева может использовать некоторые эффективные алгоритмы, чтобы решить проблему d или r. Если p мало, Ева может просто найти d = loge1e2 mod p и сохранить его, чтобы расшифровать любое сообщение, передаваемое Бобу. Это может быть сделано единожды и работать, пока Боб использует те же самые ключи. Ева может также использовать значение случайного числа r, применяемого Алисой в каждой передаче r = loge1C1 mod p. Оба этих случая подчеркивают, что безопасность p должны быть по крайней мере 1024 бита ( 300 десятичных цифр).
Когда Алиса использует одно и то же значение случайного показателя степени r для того, чтобы зашифровать два исходных текста P и P', Ева обнаруживает P', если она знает P. Предположим, что $${C_2} = P \times ({e_2}^r)\bmod {\text{ }}p$$ и $${C'_2} = P' \times ({e_2}^r)\bmod {\text{ }}p$$. Ева находит P', используя следующие шаги:
Поэтому рекомендовано, чтобы Алиса брала при каждой передаче новое значение r, чтобы сорвать атаки.
p должен содержать по крайней мере 300 десятичных цифр, новых для каждой шифровки.Пример 15.4
Вот более реальный пример. Боб использует случайное целое число длиной 512 битов (идеально — 1024 ) и целое число p длиной 155 цифр (идеал — 300 цифр). Боб выбирает e1 и d, затем вычисляет e2, как показано ниже; Боб объявляет (e1, e2, p) как свой открытый ключ и d как секретный ключ доступа.
p = 1153489927256167624492531371701433174049009453260983495981434692 19056898698622645932129754737871895144368891765264730936159299937 28061165964347353440008577 ___________________________________________________________________ e1= 2 ___________________________________________________________________ d = 1007 ___________________________________________________________________ e2 = 9788641304300918950876685693809773904388006288733768761002206223 32554507074156189212318317704610141673360150884132940857248537703 1582066010072558707455
Алиса имеет исходный текст P = 3200, чтобы передать Бобу. Она выбирает r = 545131, вычисляет C1 и C2 и передает их Бобу.
P = 3200 r = 545131 _____________________________________________________________________ C1 = 8872970693835284710225704714922756631202600672565621250181883514 29417223599712681114105363661705173051581533189165400973736355080 295736788569060619152881 _____________________________________________________________________ C2 = 7084543330489299445770160123807949995674360218361924469617745069 2124469615516580077945559308034588961440240859952591957920972162 88796813505827795664302950
Боб вычисляет исходный текст $$P{\text{ }} = {C_2} \times {({C_1}^d)^{ - 1}}\bmod p{\text{ }} = 3200\bmod p$$
P = 3200
Хотя
y2 + b1xy + b2y = x3 + a1x2 + a2x +a3
y2 = x3 + ax + b
В этом случае, если $$4{a^3} + 27{b^2} \ne 0$$, уравнение представляет несингулярную эллиптическую кривую ; в противоположном случае оно описывает сингулярную эллиптическую кривую. Для несингулярной x3 + ax + b = 0 имеет три отличных корня (вещественных или комплексных); для сингулярной уравнение x3 + ax + b = 0 не имеет трех отличных корней.
В уравнении, как мы можем видеть, левая сторона ( y2 ) имеет степень 2, в то время как правая сторона имеет степень 3 ( x3 ). Это означает, что горизонтальная линия может пересекать кривую в трех точках, если все корни вещественные. Однако вертикальная линия может пересечь кривую самое большее в двух точках.
Пример 15.5
Рисунок 15.3 показывает две y2 = x3 – 4x и y2 = x 3 – 1. Оба уравнения несингулярны. Однако первое имеет три вещественных корня ( x = -2, x = 0, и x = 2 ), но второе — только один вещественный корень ( x = 1 ) и два мнимых.
(рис 15.3) Две эллиптические кривые в поле вещественных чисел Определим абелеву (коммутативную) группу (см. лекции 5-6), использующую точки на P = (x1, y1) представляет точку на кривой, если x1 и y1 — координаты точки на кривой, которые удовлетворяют уравнению этой кривой. Например, точки P = (2,0; 0,0), Q = (0,0; 0,0), R = (–2,0; 0,0), S = (10,0;30,98), и T = (10,0; –30,98) – точки на кривой y2 = x3 – 4x. Обратите внимание, что каждая точка представлена двумя вещественными числами. По материалам лекций 5-6, для создания абелевой группы мы нуждаемся во множестве операций над множествами и пяти свойствах, которым удовлетворяют операции. В этом случае группа G = <E, +> — абелева.
Множество. Мы определим множество как точки на кривой, где каждая точка — пара вещественных чисел. Например, множество E для y2 = –x3 – 4x показано как
E = {(2,0; 0,0), (0,0; 0,0), (-2,0; 0,0), (10,0; 30,98), (10,0,-30,98)...}
Операция. Заданные свойства несингулярной
R = P + Q, где P = (x1, y1), Q = (x2, y2), и R = (x3, y3)
Для того чтобы найти R на кривой, рассмотрим три случая, как это показано на рис. 15.4.
(рис 15.4) Три случая сложения на эллиптической кривой 1. В первом случае две точки P = (x1, y1) и Q = (x2, y2) имеют различные x -координаты и y -координаты ( $${x_1} \ne {y_1}$$ и $${x_2} \ne {y_2}$$ ), как это показано на рис. 15.4a. Линия, соединяющая P и Q, пересекает кривую в точке, обозначенной R. R есть отражение (-R) относительно y -оси. Координаты точки R, x3 и y3 могут быть найдены по наклону линии, $$\lambda,$$ и затем можно вычислить значений x3 и y3, как показано ниже:
2. Во втором случае две точки совпадают (R = P + P), как показано на рис. 15.4b. Наклон линии и координаты точки R могут быть найдены, как показано ниже.
3. В третьем случае две точки — аддитивные P = (x1, y1), а вторая точка равна Q = (x1, – y1), линия, соединяющая эти две точки, не пересекает кривую в третьей точке. Математики говорят в этом случае, что точка пересечения находится в бесконечности. Они определяют точку О (см. рис. 15.4с) как точку в бесконечности или нулевую точку, которая является аддитивным нейтральным элементом группы.
Свойства операции. Краткие определения свойств операции, как они обсуждались в лекциях 5-6:
(P + Q) + R = P + (Q + R).P + Q = Q + P.P + 0 = 0 + P.x. Другими словами, точки P = (X1,Y1) И Q = (X1, – Y1) — P + Q = 0. Заметим, что нейтральный элемент — это Обратите внимание, что предыдущие рассуждения касаются двух алгебраических структур: группа и поле. Группа определяет множество точек на
Наша предыдущая группа p> 3. В модульной арифметике точки на кривой не
представляют графы, как это можно было видеть на предыдущих рисунках, но сохраняются те же самые основные концепции. Мы используем ту же самую операцию сложения, но с вычислением по модулю p. В результате мы получаем Ep (a, b), где p определяет модуль, и b — коэффициент уравнения y2 = x3 + ax + b. Обратите внимание, что хотя значение x в этом случае от 0 до p, обычно не все точки находятся на кривой.
(x, y) равна (x, – y), где (–y) — аддитивная y. Например, если p = 13, (4, 2) равна (4, 11).
Алгоритм 15.7 показывает программу в Ep (a, b).
$$\tt\parindent0pt
Elliptic\_points (p, a, b) // $p$-модуль
\{
$x \gets 0$
while ($x < p$)
\{
$w \gets (x^{3} + ax + b) \mod p$\ \ \ //$w$ – это $y^{2}$
if ($w$ – целое значение квадратного корня в $Z_{p}$) выход $((x, \sqrt w )(x, - \sqrt w ))$
$x \gets x + 1$
\}
\} $$
Пример 15.6
Определите E13 (1, 1) по уравнению y2 = x3 + x + 1 и вычислите по модулю 13. Точки на кривой могут быть найдены, как показано на рис. 15.5.
(рис 15.5) Точки на эллиптической кривой в поле GF (p)Обратите внимание на следующее:
а. Некоторые значения y2 не имеют квадратного корня по модулю 13. Они не являются точками на этой x = 2, x = 3, x = 6 и x = 9 не находятся на кривой.
б. Каждая точка, определенная на кривой, имеет (7, 0) —
в. Обратите внимание, что для пары обратных точек значения y — аддитивные Zp. Например, 4 и 9 — аддитивные Z13. Так что мы можем сказать, что если 4 — это значение y, то 9— это значение (–y).
г.
Мы используем группу GF (p). Вместо вычитания и деления мы применяем аддитивные и мультипликативные
Пример 15.7
Сложим две точки в примере 15.6, R = P + Q, где P = (4, 2) и Q = (10,6).
а. X = (6 – 2) x (10 – 4) -1 mod 13 = 4 x 6-1 mod 13 != 5 mod 13.
б. x = (52 – 4 – 10) mod 13 = 11 mod 13.
в. y = [5 (4 – 11) – 2] mod 13 = 2 mod 13.
г . R = (11, 2) является точкой на кривой в примере 15.6.
В арифметике умножение числа на константу k означает прибавление числа само к себе k раз. Здесь ситуация та же самая. Умножение точки P на k означает прибавление точки P к себе k раз. Например, в E13 (1, 1), если точка (1, 4) умножается на 4, результат есть точка (5, 1). Если точка (8,1) умножается на 3, результат — точка (10, 7).
Вычисление в группе GF(2n). В соответствии с лекциями 5-6, где мы говорили, что элементы множества в этом поле — n -битовые слова, которые можно интерпретировать как полиномы с коэффициентом в GF(2), сложение и умножение этих элементов такое же, как сложение и умножение полиномов. Для того чтобы определить GF(2n), необходимо только изменить кубическое уравнение. Общее уравнение
y2 + xy = x3 + ax2 + b
где $$b \ne 0$$. Обратите внимание, что значение x, y, a и b — полиномы, представляющие n -битовые слова.
Если P = (x, y), то (–P) = (x, x + y).
Мы можем написать алгоритм для нахождения точек на кривой, используя генераторы для полиномов, которые рассматривали в лекциях 9-10. Но разработку этого алгоритма оставляем как упражнение. Далее следует очень тривиальный пример.
Пример 15.8
Мы выбираем GF (2 3) с элементами (0,1, g, g2, g3, g 4, g5, g6), использующими неприводимый f (x) = x3 + x +1. Этому соответствует g3 + g +1 = 0 или g3 = g + 1. Другие степени g могут быть вычислены, как это показано ниже.
| 0 | 0 | g3 = g + 1 | 0 |
| 1 | 0 | g4 = g2 + g | 1 |
| g | 0 | g5 = g2 + g + 1 | 1 |
| g2 | 1 | g6 = g2 + 1 | 1 |
Используя y2 + xy = x3 + g3x2 + 1, a = g3 и b = 1, мы можем найти точки на этой кривой, как это показано на рисунке 15.6.
(рис 15.6) Точки на эллиптической кривой в GF (2 в степени n)
Правила для сложения точек в GF(2n) немного отличаются от правил GF(p).
1. Если P = (x1, y1), Q = (x2, y2), $$Q \ne -P$$, $$Q \ne P$$, то R = (x3, y3) = P + Q может быть найден как
2.Если Q = P, то R = P + P (или R = 2P ) и может быть найден как
Пример 15.9
Пусть нам надо найти R = P + Q, где P = (0,1) и Q = (g2,1). Мы имеем $$\lambda = 0$$ и R = (g5, g4).
Пример 15.10
Пусть нам надо найти R = 2P, где P = (g2,1). Мы имеем $$\lambda =g^{2} +1 /g^{2} = g^{2}+ g^{5}= g +1$$ и R = (g6, g5).
Для того чтобы умножить точку на константу, точки должны складываться непрерывно согласно правилу R = 2P.
Для шифрования и GF(p) или GF(2n), как это показано на рис. 15.7.
(рис 15.7) Криптосистема Эль-Гамаля, использующая эллиптическую функцию E (a,b) с GF(p) или GF(2n).e1 (x 1, y1 ).d.E (a,b), e1 (x1, y1 ) и e2 (x2, y2) как свой открытый ключ доступа; он сохраняет d как секретный ключ.Алиса выбирает P, точку на кривой, как ее исходный текст, P. Затем она вычисляет пару точек, направляет как зашифрованный текст:
Читатель может задаться вопросом, как произвольным исходным
C1 = r x e1 C2 = P + r x e2
Текстом может быть точка на
Боб, после получения C1 и C2, вычисляет P, исходный текст, используя следующую формулу:
P = C2 – (d x C1) Знак "минус" здесь означает сложение с инверсией.
Мы можем доказать, что P, вычисленный Бобом, — тот же, что передан Алисой, как это показано ниже:
P, C 1, C2 и e2 — это точки на кривой. Обратите внимание, что результат сложения двух обратных точек на кривой — нулевая точка.
Пример 15.11
Вот очень тривиальный пример шифровки с использованием GF (p).
E67 (2, 3) как GF (p).e1 = (2, 22) и d = 4.e2 = (13, 45), где $${e_2} = d \times {e_1}$$.(E, e1, e2).P = (24, 26) Бобу. Она выбирает r = 2.C1= (35, 1), где $${C_1} = r \times {e_1}$$.C2 = (21, 44), где $${C_2} = P \times {e_1}$$.C, и C2. Он использует $$2 \times {C_1}$$, (35, 1) и получает (23, 25).(23, 25) и получает точку (23, 42).(23, 42) с C2 = (21, 44) и получает первоначальный исходный текст P = (24, 26).Ниже приводится краткое сравнение алгоритма Эль-Гамаля с его вариантом, использующим
a. Алгоритм Эль-Гамаля использует мультипликативную группу; вариант — эллиптическую группу.
b. Эти два члена в алгоритме Эль-Гамаля — числа в мультипликативной группе; при применении варианта — точки на
c. Секретный ключ в каждом алгоритме — целое число.
d. Секретные числа, выбираемые Алисой в каждом алгоритме, — целые числа.
e. Возведение в степень в алгоритме Эль-Гамаля заменено умножением точки на константу.
f. Умножение в алгоритме Эль-Гамаля заменено сложением точек.
g.
h. Вычисление обычно легче в
Чтобы расшифровать сообщение, Ева должна найти значение r или d.
a. Если Ева знает значение r, она может использовать $$P = {C_2}-(r \times {e_2})$$, чтобы найти точку P, относящуюся к исходному тексту. Но для того чтобы найти r, Ева должна решить уравнение $${C_1} = r \times {e_1}$$. Это значит — найти две точки на кривой, C1 и e1. Ева должна найти множитель, который создает C1 начиная с e1. Эта проблема известна как проблема логарифма эллиптической кривой, единственный известный метод решения этой проблемы — $$РО(\rho )$$ - алгоритм Поларда, который неосуществим, если задано большое r и p в GF (p) или большое n в GF(2n).
b. Если Ева знает значение d, она может использовать $$P = {C_2} - (d \times {C_1})$$, чтобы найти точку P, относящуюся к исходному тексту. Поскольку $${e_2} = d \times {e_1}$$, это тот же самый тип проблемы, что и в предыдущем пункте. Ева знает значение e1 и e2 — она должна найти d.
Для того же самого уровня безопасности (затраты на вычисление) модуль n, может быть меньшим в эллиптической системе (GF(2n) с n, состоящим из 160 битов, может обеспечить тот же уровень безопасности, как n 1024 битов.
Для более детального изучения положений, обсужденных в этой лекции, мы рекомендуем нижеследующие книги и сайты. Пункты, указанные в скобках, показаны в списке ссылок в конце книги.
Следующие сайты дают больше информации о темах, рассмотренных в этой лекции.
f вычисляется просто, а f -1 вычислить невозможно (в смысле сложности вычислений), если не используется лазейка.e и d, где e — общедоступный ключ, а d является частным (секретным). Алиса использует C = Pe mod n для того, чтобы создать зашифрованный текст C из исходного текста P ; Боб использует P = Сd mod n, чтобы извлечь исходный текст, переданный Алисой.e = 2 и d = 1/2. p и q — большие числа. Сложность n на два простых сомножителя p и q.Zn*. Шифрование и e1 и e2, а секретный ключ — это целое число d. Безопасность y2 = x3 + ax + b, где $$4{a^3} + 27{b^2} \ne 0$$. Абелева группа была определена с помощью GF (p) и GF (2n). Мы показали, как b = [7, 11,23,43,87, 173, 357], r =41 и модуль n = 1001, зашифруйте и расшифруйте букву a, используя ранцевую криптосистему. Используйте [7 6 5 1 2 3 4] как таблицу перестановки.n = 221 и e = 5, найдите d.n =3937 и e =17, найдите d.p = 19, q = 23 и e = 3, найдите n, $$\varphi ,$$ (n) (^) и d.d, если вы знаете, что e =17, а n =187.n и $$\varphi (n)$$, вычислите p и q.e = 13 и n = 100.
Зашифруйте сообщение "HOW ARE YOU", применяя 00 к 25 для букв от A до Z и 26 — для пробела. Используйте различные блоки, чтобы сделать P <n.n = 12091 и e = 13. Зашифруйте сообщение "THIS IS THOGH", используя схему кодирования 00 к 26. Расшифровать зашифрованный текст, чтобы найти первоначальное сообщение.1 как открытый ключ e?2 открытым ключом?(e = 17, n = 19519), чтобы передать сообщение из четырех символов Бобу, применяющему схему $$A \leftrightarrow 0$$, $$B \leftrightarrow 1...Z \leftrightarrow 25$$ кодирования и декодирования по каждому символу отдельно. Ева перехватывает зашифрованный текст (6625 0 2968 17863) и расшифровывает сообщение, не разлагая на множители модуль. Найдите исходный текст; объясните, почему Ева смогла легко взломать зашифрованный текст.(e = 7, n = 143), чтобы передать исходный текст P = 8, зашифрованный в виде текста C = 57. Покажите, как Ева может использовать атаку выборки текста, если она имеет доступ к компьютеру Боба, чтобы найти исходный текст.(e = 3, n = 35) и передает зашифрованный текст 22 Бобу. Покажите, как Ева может найти исходный текст, используя атаку циклического повторения.p = 47 и q =11:P = 17 и найдите зашифрованный текст.p = 31:e1 и d, затем вычислите e2."HELLO" ; используйте 00 к 25 для кодирования. Используйте различные блоки для того, чтобы сделать P<p.C1 и C2 будут изменены в течение передачи?e1 = 2 и e 2 = 8 ), чтобы передать два сообщения — P = 17 и P' = 37. Они оба используют то же самое случайное целое число r = 9. Ева перехватывает зашифрованный текст и так или иначе находит значение P = 17. Покажите, как Ева может использовать атаку знания исходного текста, чтобы найти значение P'.E (1, 2) в поле GF (11):d.E (g4, 1) в поле GF(24):GF(p).GF(2n).
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.