close

Вход

Забыли?

вход по аккаунту

?

МСЗКИ 5 лабораторная работа

код для вставкиСкачать
Криптосистемы с открытым ключом Задания
1. Напишите программу генерации простых целых чисел. Для указанного интервала [a, b] она должна сформировать текстовый файл из простых чисел (по одному в строке).
2. Напишите программу генерации целого числа Мерсенна (M(n)=2n-1, где n - простое) большой размерности и проверки его на простоту.
3. Напишите программу калькулятор, реализующий символьную арифметику с целыми числами размерностью до 250 десятичных знаков. Реализовать память (переменные) на десять регистров (R0-R9) и команды ввода и вывода значений этих регистров из текстового файла и обратно в текстовый файл.
4. Напишите библиотеку подпрограмм для символьных вычислений с целыми числами размерностью не превышающих 512 двоичных знаков. Реализуйте операции: сложения, вычитания, деления, умножения, mod, div, abs, возведения в квадрат, форматированного ввода и вывода, операции сравнения (=, >, <, >=, <=, <>), определения размерности. 5. Напишите библиотеку подпрограмм для модульной арифметики, использующей для чисел представление Монтгомери. В представлении Монтгомери умножение по модулю p эквивалентно двум обычным умножениям. Menezes A., van Oorschot P., Vanstone S. Handbook of applied cryptography. CRC Press, 1996. 661 p. (http://www.cacr.math.uwaterloo.ca/ hac/). 6. Реализуйте алгоритм степеней (ae mod n) для больших целых чисел размерностью до 250 десятичных знаков.
7. Реализуйте алгоритм степеней (ae mod n) для больших целых чисел размерностью до 512 двоичных знаков.
8. Реализуйте программы шифрования и расшифровки по методу RSA.
9. Реализуйте программы шифрования и расшифровки по методу Эль-Гамаля.
10. Реализуйте программы шифрования и расшифровки с использованием эллиптических кривых.
11. Реализуйте программы формирования и проверки электронной подписи по методу шифрования RSA.
12. Реализуйте программы формирования и проверки электронной подписи на основе ГОСТ Р34.10-94.
13. Реализуйте программы формирования и проверки электронной подписи на эллиптической кривой (ГОСТ Р34.10-2001).
14. Разложите число n = 3 552 377 на простые множители, если известно, что оно равно произведению двух разных простых чисел и φ(n) = 3 548 580.
15. Дешифруйте следующий текст, зашифрованный по методу RSA:
22752 - 6198 - 14204 - 23191 - 10723 - 14065,
если известно, что n=23393, e=5, а каждая буква русского алфавита представлена двузначным десятичным числом (А-10, Б-11, ..., Я - 41) Ё - исключено, пробел кодируется числом 99. 16. Дешифруйте сообщение 3410 - 5693 - 7112, зашифрованное по методу RSA с n=7597, e=4947и φ(n) =7420. Способ кодирования символов - как в предыдущем варианте задания.
17. Дешифруйте сообщение 4944 - 6022 - 4656 - 2295 - 9293 - 5289 - 3566 - 2589, зашифрованное по методу RSA с n=10403, e=1399и φ(n) =7420. Способ кодирования символов - как в предыдущем варианте задания.
18. Реализуйте программу обмена ключами по методу Диффи-Хеллмана.
19. Реализуйте программу обмена ключами по методу Диффи-Хеллмана, заменив возведение в степень на операцию композиции точки на эллиптической кривой.
20. Реализуйте программы формирования и проверки электронной подписи по стандарту DSS. Для создания цифровой подписи используется алгоритм DSA (Digital Signature Algorithm), а в качестве хэш-алгоритма - SHA-1 (Sequre Hash Algorithm). 21. Реализуйте программу шифрования и расшифрования ключей по методу Шамира.
Асимметричные методы шифрования
В асимметричных методах применяются два разных ключа. Один из них, несекретный, используется для шифровки и может публиковаться вместе с адресом пользователя, другой - секретный, применяется для расшифровки и известен только получателю.
Алгоритм Шамира
Алгоритм может использоваться для передачи короких сообщений, например, ключей. Пусть абонент А хочет передать сообщение m абоненту В в зашифрованном виде. А выбирает случайное большое число p и открыто передает его В. Затем А выбирает два числа Са и Da, такие что Са·Da mod (p-1) = 1. B точно также выбирает Сb и Db. Поле этого можно передать сообщение m, используя следующий трехступенчатый протокол.
Шаг 1. A вычисляет число x1 = mCa mod p , где m - исходное сообщение, и пересылает x1 к B.
Шаг 2. B, получив x1, вычисляет число x2 = x1Cb mod p и пересылает x2 к A.
Шаг 3. A вычисляет число x3 = x2Da mod p и пересылает его к B.
Шаг 4. B, получив x3, вычисляет число x4 = x3Db mod p.
Криптосистема RSA
Криптосистема RSA, была разработана в 1977 году и получила название в честь своих создателей: Рона Райвеста (Rivest), Ади Шамира (Shamir) и Леонарда Адлемана (Adleman).
Они воспользовались тем фактом, что нахождение больших простых чисел осуществляется легко, но разложение на множители произведения двух таких чисел практически невыполнимо. В 1993 г. метод RSA был обнародован и принят в качестве стандарта (PKCS # 1: RSA Encryption Standard).
Генерация ключей
1. Выбираются два больших простых целых числа p и q приблизительно одинакового размера. 2. Вычисляется модуль системы n = pq и φ(n) = (p-1)(q-1) - функция Эйлера.
3. Выбирается достаточно большое число d, удовлетворяющее условию 1 < d < φ(n), и взаимно простое с φ(n), то есть НОД( d, (p-1)(q-1) ) = 1.
4. Используя расширенный алгоритм Евклида, вычисляется большое целое число e, отвечающее условию (ed) mod φ(n) = 1, 1 < e < φ(n). Метод Евклида находит множество пар (e, y), каждая из которых является решением уравнения: e * d + ( p - 1)(q - 1) * y = 1 в целых числах.
Таким образом, секретным ключом является пара чисел (n,d), а открытым - пара чисел (n,e), но можно взять и наоборот.
Зашифрование и расшифрование
1. Входное сообщение разбивается на блоки mi, их размер определяется целым k, соответствующим неравенству 10k-1 < n < 10k.
2. Вычисляется значение ci = mie mod n.
3. Значение ci, которое является зашифрованным блоком сообщения, посылается по открытым каналам передачи данных.
4. Расшифрование заключается в вычислении значения mi = cid mod n.
Математические основы RSA
Рассмотрим математические результаты, положенные в основу этого алгоритма.
Теорема 1. Малая теорема Ферма
Если р - простое число, то
xp-1 = 1 (mod p) (1)
для любого х, простого относительно p,
и
xp = х (mod p) (2)
для любого х.
Определение. Функцией Эйлера φ(n) называется число положительных целых, меньших n и простых относительно n.
n23456789101112φ (n)122326464104 Теорема 2. Если n=pq, (p и q - отличные друг от друга простые числа), то φ(n)=(p-1)(q-1).
Теорема 3. Если n=pq, (p и q - отличные друг от друга простые числа), то для любого x имеет место равенство:
x(p-1)(q-1) mod n = 1.
Следствие . Если n=pq, (p и q - отличные друг от друга простые числа) и е простое относительно (n), то отображение Еe,n: xxe (mod n)
является взаимно однозначным на Zn.
Очевиден и тот факт, что если е - простое относительно (n), то существует целое d, такое, что ed = 1 (mod (n)) (3)
На этих математических фактах и основан популярный алгоритм RSA.
Пусть n=pq, где p и q - различные простые числа. Если e и d удовлетворяют уравнению (3), то отображения Еe,n и Еd,n являются инверсиями на Zn. Как Еe,n, так и Еd,n легко рассчитываются, когда известны e, d, p, q. Если известны e и n, но p и q неизвестны, то Еe,n представляет собой одностороннюю функцию; нахождение Еd,n по заданному n равносильно разложению n. Если p и q - достаточно большие простые, то разложение n практически не осуществимо. Это и заложено в основу системы шифрования RSA. Для расшифровки RSA-сообщений воспользуемся этой формулой. Возведем обе ее части в степень (-y):
x(-y)(p-1)(q-1) mod n = 1(-y) = 1.
Теперь умножим обе ее части на x:
x(-y)(p-1)(q-1)+1 mod n = 1 * x = x.
Вспомним, как мы создавали открытый и закрытый ключи. Мы подбирали с помощью алгоритма Евклида e такое, что e·d + (p-1)(q-1) ·y = 1,
то есть e·d = (-y)(p-1)(q-1) + 1.
А следовательно в последнем выражении предыдущего абзаца мы можем заменить показатель степени на число (e·d). Получаем xe*d mod n = x.
То есть для того чтобы прочесть сообщение ci = mie mod n достаточно возвести его в степень d по модулю n: cid mod n = mie*d mod n = mi.
После шифрования, сообщение невозможно раскрыть с помощью открытого ключа. Даже если злоумышленник знает числа e и n, то по ci прочесть исходные сообщения mi он не может никак, кроме как полным перебором mi и возведением его в степень e или отысканием d путем разложения n на множители. Владелец же закрытого ключа без труда может расшифровать принятое сообщение.
Пример, иллюстрирующий применение алгоритма RSA
Зашифруем сообщение "САВ". Для простоты будем использовать маленькие числа (на практике применяются много большие). 1. Выберем p=3 и q=11.
2. Определим n=3*11=33. Найдем (p-1)(q-1)=20.
3. Выберем в качестве d, взаимно простое с 20, например, d=3.
4. Выберем число е. В качестве такого числа может быть взято любое число, для которого удовлетворяется соотношение (е*3) mod 20 = 1, например 7.
5. Представим шифруемое сообщение как последовательность целых чисел с помощью отображения: А1, В2, С3. Тогда сообщение принимает вид (3,1,2). Зашифруем сообщение с помощью ключа {7,33}.
ШТ1 = (37) mod 33 = 2187 mod 33 = 9,
ШТ2 = (17) mod 33 = 1 mod 33 = 1,
ШТ3 = (27) mod 33 = 128 mod 33 = 29.
6. Расшифруем полученное зашифрованное сообщение (9,1,29) на основе закрытого ключа {3,33}:
ИТ1 = (93) mod 33 = 729 (mod 33) = 3,
ИТ2= (13) mod 33 = 1 (mod 33) = 1,
ИТ3 = (293) mod 33 = 24389 (mod 33) = 2.
Практическая реализация RSA
В конце 1995 года удалось практически реализовать раскрытие шифра RSA для 500-значного ключа. Для этого с помощью сети Интернет было задействовано 1600 компьютеров.
Сами авторы RSA рекомендуют использовать следующие размеры модуля n:
* 768 бит - для частных лиц;
* 1024 бит - для коммерческой информации;
* 2048 бит - для особо секретной информации.
Числа p и q должны быть одинаковой длины. Если n занимает 1024 бита, то длина p и q должна быть равна 512 битам. Различие между p и q должно быть большим.
p-1 должно иметь большой простой делитель (r); p+1 должно иметь большой простой делитель;
r-1 должно иметь большой простой делитель.
Криптосистема Эль-Гамаля
Автор шифра - Эль-Гамаль (Taher ElGamal). (Данная система является альтернативой RSA и при равном значении ключа обеспечивает ту же криптостойкость). В отличие от RSA метод Эль-Гамаля основан на проблеме дискретного логарифма. Этим он похож на алгоритм Диффи-Хелмана. Если возводить число в степень в конечном поле достаточно легко, то восстановить аргумент по значению (то есть найти логарифм) довольно трудно.
Пусть имеются абоненты А, В, С, ..., которые хотят передавать друг другу зашифрованные сообщения. Для всей группы абонентов выбираются некоторое большое простое число р и целое число g. Числа р и g передаются абонентам в открытом виде.
Затем каждый j-й абонент выбирает свое секретное число сj , 1 < сj < р-1, и вычисляет соответствующее ему открытое число dj,
dj = gCj mod p.
В результате получаем пары ключей: cA dA , cB dB , cC dC , ...
Покажем теперь, как А передает сообщение т абоненту В. Будем предполагать, что сообщение представлено в виде чисел mi < р .
1. А формирует случайное число k , 1 < k < р-2 , вычисляет числа
ri = gk mod p,
еi = m i • dB k mod p
и передает пару чисел (ri, еi) абоненту В. 2. В, получив (ri, еi), вычисляет
тi = еi • ri р-1-СB mod p.
Пример. Передадим сообщение т = 15 от А к В. Возьмем р = 23, g = 5. Пусть абонент В выбрал для себя секретное число CB =13 и вычислил dB = 513 mod 23 = 21.
Абонент А выбирает случайно число k, например k = 7, и вычисляет:
r = 57 mod 23 = 17, е = 15 • 217 mod 23 = 15 • 10 mod 23 = 12.
Теперь А посылает к В зашифрованное сообщение в виде пары чисел (17,12). В вычисляет т = 12 • 1723-1-13 mod 23 = 12 • 179 mod 23 = 12 • 7 mod 23 = 15.
Заметим, что объем шифра в два раза превышает объем сообщения.
Есть и другой вариант зашифрования и расшифрования, где вместо умножения используется побитовое сложение по модулю 2 ():
ei = mi dk,
mi = (ri C j mod p) ei.
Пример. е = 15 (217 mod 23) = 15 10 = 5,
т = (1713 mod 23) 5 = 10 5 = 15.
Стандарты на электронную (цифровую) подпись
Рассмотрим российский государственный стандарт ГОСТ Р34.10-94 и стандарт США FIPS 186. Российский стандарт был принят в 1994 году, американский - в 1991. В основе обоих стандартов лежит по сути один и тот же алгоритм, называемый DSA (Digital Signature Algorithm) и являющийся вариацией подписи Эль-Гамаля. Рассмотрим российскую версию алгоритма, а затем отличия от нее американской версии.
Вначале для некоторого сообщества пользователей выбираются общие несекретные параметры. Прежде всего необходимо найти два простых числа, q длиной 256 бит и р длиной 1024 бита, между которыми выполняется соотношение
p = bq + 1 (1)
для некоторого целого b. Старшие биты в р и q должны быть равны единице. Затем выбирается число а > 1, такое, что
aq mod р = 1. (2)
В результате получаем три общих параметра - р , q и a .
Замечание 1. Равенство (2) означает, что при возведении а в степени по модулю р показатели приводятся по модулю q , и такое приведение будет постоянно выполняться при генерации и проверке подписи. В результате длина показателей степени в рамках рассматриваемого алгоритма никогда не будет превышать 256 бит, что упрощает вычисления.
Далее каждый пользователь выбирает случайно число х , 0 < х < q , и вычисляет
y = ax mod p. (3)
Число х будет секретным ключом пользователя, а число у - открытым ключом. Предполагается, что открытые ключи всех пользователей указываются в некотором несекретном, но "сертифицированном" справочнике, который должен быть у всех, кто собирается проверять подписи. Отметим, что в настоящее время найти х по у практически невозможно при указанной выше длине модуля р. На этом этап выбора параметров заканчивается, и мы готовы к тому, чтобы формировать и проверять подписи.
Пусть имеется сообщение m, которое необходимо подписать. Генерация подписи выполняется следующим образом:
1. Вычисляем значение хеш-функции h = h(m) для сообщения m (в российском варианте хеш-функция определяется ГОСТом P34.11-94).
2. Формируем случайное число k , 0 < k < q.
3. Вычисляем r = (ak mod p) mod q . Если оказывается, что r = 0 ,
то возвращаемся к шагу 2.
4. Вычисляем s = (kh + xr) mod q. Если s = 0 , то возвращаемся к шагу 2.
5. Получаем подписанное сообщение <m; r, s>.
Для проверки подписи делаем следующее.
1. Вычисляем хеш-функцию для сообщения h = h(m).
2. Проверяем выполнение неравенств 0 < r <q , 0 < s < q .
3. Вычисляем u1 = s • h-1 mod q, u2 = -r • h-1 mod q.
4. Вычисляем v = (au1yu2 mod p) mod q.
5. Проверяем выполнение равенства v = r.
Если хотя бы одна из проверок на шагах 2 и 5 не дает нужного результата, то подпись считается недействительной. Если же все проверки удачны, то подпись считается подлинной.
Замечание 2. Чтобы найти параметр а, удовлетворяющий (2), рекомендуется использовать следующий метод. Берем случайное число g > 1 и вычисляем
а = g(р-1)/q mod р.(4)
Если а > 1, то это то, что нам нужно. Действительно, на основании (4) и теоремы Ферма имеем
aq mod р = g((p-1)/q) q mod p = gp-l mod p = 1,
т.е. выполняется равенство (2). Если при вычислении по (4) мы получаем а = 1 (крайне маловероятный случай), то нужно просто взять другое число g.
Пример. Выберем общие несекретные параметры
q = 11, р = 6q + 1 = 67,
возьмем g = 10 и вычислим
а = 106 mod 67 = 25.
Выберем секретный ключ х = 6 и вычислим открытый ключ
у = 256 mod 67 = 62.
Сформируем подпись для сообщения m = baaaab. Пусть для хеш-функции этого сообщения h(m) = 3. Возьмем случайно число k = 8. Вычислим
r = (258 mod 67) mod 11 = 24 mod 11 = 2,
s = (8 • 3 + 6 • 2) mod 11 = 36 mod 11 = 3.
Получаем подписанное сообщение
<baaaab; 2, 3>.
Теперь выполним проверку подписи. Если сообщение не изменено, то h = 3. Вычислим
h-1 = 3-1 mod 11 = 4,
u1 = 3 • 4 mod 11 = 1,
u2 = -2 • 4 mod 11 = -8 mod 11 = 3,
v = (251 • 623 mod 67) mod 11 = (25 • 9 mod 67) mod 11 = 24 mod 11 = 2.
Мы видим, что v = г , значит подпись верна.
Теперь остановимся на отличиях американского стандарта от российского. Они сводятся к следующему.
1. Длина числа q берется равной 160 бит.
2. В качестве хеш-функции используется алгоритм SHA-1.
3. При генерации подписи на шаге 4 параметр s вычисляется по формуле s = k-l(h + xr) mod q .
4. При проверке подписи на шаге 3 u1 и u2 вычисляются по формулам u1 = h • s-1 mod q , u2 = r • s-1 mod q .
Криптосистемы на эллиптических кривых
Использование эллиптических кривых в криптографических целях было впервые предложено Коблицом (Neal Koblitz) и Миллером (Victor Miller) в 1985 году.
В 1998 году были приняты стандарты США ANSI X9.62 и FIPS 186-2, а в 2001 году аналогичный российский стандарт ГОСТ Р34.10-2001.
Криптографические алгоритмы, основанные на эллиптических кривых имеют более высокую стойкость (по отношению к другим асимметричным алгоритмам) при равной трудоемкости. Это объясняется тем, что для вычисления обратных функций на эллиптических кривых известны только алгоритмы с экспоненциальным ростом трудоемкости, тогда как для обычных систем предложены субэкспоненциальные методы. В результате тот уровень стойкости, который достигается, скажем, в RSA при использовании 1024-битовых модулей, в системах на эллиптических кривых реализуется при размере модуля 160 бит.
Изучение эллиптических кривых требует знаний алгебраической геометрии.
Математические основы
Кривая третьего порядка Е , задаваемая уравнением вида
Е: Y2 = X3 + аХ + b, (1)
называется эллиптической кривой.
Поскольку Y = ± Х3 + аХ + b , график кривой симметричен относительно оси абсцисс. Чтобы найти точки его пересечения с осью абсцисс, необходимо решить кубическое уравнение
X3 + аХ + b = 0, (2)
используя известные формулы Кардано. Дискриминант этого уравнения
(3)
a) D < 0; б) D = 0; в) D > 0.
Рис. 1. Эллиптическая кривая:
Кривая на рис. б) называется сингулярной. В ее точке сингулярности (β,0) имеются две касательные. Сингулярные кривые мы будем исключать из нашего рассмотрения. Поэтому при задании кривой с помощью параметров а и b потребуем выполнения условия 4 a3 + 27 b2 ≠ 0. (4)
Определим операцию композиции точек на кривой. Возьмем какие-либо две точки Р = (x1, y1), Q = (x2, y2)  Е и проведем через них наклонную прямую (рис. 2). Эта прямая обязательно пересечет кривую в третьей точке, которую обозначим через R'.
Рис. 2. Композиция точек R = Р + Q
Точку R = (хз, уз) получим путем изменения знака ординаты точки R'. Будем обозначать описанную операцию композиции точек следующим образом: R = Р + Q.
Пусть точка Р  Е имеет координаты (х, у). Тогда точку с координатами (х, -у), будем обозначать -Р. Будем считать, что вертикальная прямая, проходящая через Р и -Р, пересекает кривую в бесконечно удаленной точке О, т.е. Р + (-Р) = O. По соглашению Р + О = О + Р = Р. Точка О будет играть роль нуля в операциях на эллиптической кривой.
Теперь представим, что точки Р и Q (рис. 2) сближаются друг с другом и, наконец, сливаются в одну точку Р = Q = (x1, y1) . Тогда композиция R = (хз,yз) = Р + Q = Р + Р будет получена путем проведения касательной в точке Р и отражения ее второго пересечения с кривой R' относительно оси абсцисс (рис. 3). Будем использовать следующее обозначение: R =
Р + Р = [2]Р. Композицию точек часто называют сложением точек. Удобно ввести следующие обозначения.
[m]P = Р + Р+...+ Р (m слагаемых),
[0]Р = О,
[-т]Р = - ( Р + Р+...+ Р) (m слагаемых).
Рис. 3. Удвоение точки R = Р + Р = [2]Р
Обозначим через k угловой коэффициент прямой. . (5)
Тогда формулы для вычисления координат точки R:
x3 = k2 - x1 - x2, (6)
y3 = k ( x1 - x3 ) - y1, (7)
(8)
В криптографии используется кривая
Ер(a,b): Y 2 = X 3 + аХ + b (mod p).(9)
В уравнении (9) переменные X, Y и коэффициенты a, b, где a, b < р , принимают целочисленные значения, а все вычисления выполняются по модулю р. В соответствии с (4) на a, b накладывается ограничение
(4 а 3 + 27 b 2) mod р ≠ 0. (10)
Количество точек в будем обозначать #Ер(а, b). Пример. Рассмотрим кривую
E7(2,6): Y2 = Х3 + 2Х + 6 (mod 7). (11)
Проверим условие (10):
4 • 23 + 27 • 62 = 4 • 1 + 6 • 1 = 3 ≠ 0 (mod 7).
Данная кривая несингулярна. Найдем какую-нибудь (случайную) точку. Пусть x = 5 . Тогда
Y 2 = 5 3 + 2 • 5 + 6 = 6 + 3 + 6 = 1 (mod 7)
и у = 1 (mod 7) или у = -1 = 6 (mod 7) . Мы нашли сразу две точки: (5,1) и (5,6). Найдем еще пару точек путем вычисления композиции. Вначале найдем [2](5,1). Используя (8), (6) и (7), вычисляем
Мы получили [2](5,1) = (4,6) (можно убедиться, что полученная точка лежит на кривой, подставив ее координаты в уравнение (10) ). Найдем еще одну точку [3](5,1) = (5,1) + (4,6) . Используя (5),(6) и (7), вычисляем
х3 = 22 - 5 - 4 = 2 (mod 7),
у3 = 2 · (5 - 2) - 1 = 2 · 3 - 1 = 5 (mod 7).
Мы получили [3](5,1) = (2,5). Итак, мы нашли четыре точки.
Цифровая подпись на эллиптической кривой (ГОСТ Р34.10-2001)
Данный метод полностью аналогичен описанному ранее методу ГОСТ Р34.10-94, но возведение в степень заменяется операцией композиции на кривой. Для сообщества пользователей выбирается общая эллиптическая кривая Ep(a, b) и точка G на ней, такая, что G, [2]G , [3]G, ..., [q]G суть все различные точки множества Ep(a, b), и q = #Ер(а, b), причем [q]G = О. Число точек на кривой, при надлежащем выборе параметров р, а и b, может быть простым числом, #Ер(а, b) = q. В этом случае любая точка (кроме О) является генератором всего множества точек. Длина числа q берется равной 256 бит.
Каждый пользователь U выбирает случайное число хU (секретный ключ), 0 < хU < q , и вычисляет точку на кривой YU = [хU]G (открытый ключ). Параметры кривой и список открытых ключей передаются всем пользователям.
Чтобы подписать сообщение m пользователь А делает следующее:
1) вычисляет значение хеш-функции сообщения h = h(m);
2) выбирает случайно число k , 0 < k < q ;
3) вычисляет P = [k]G = (x, у) ;
4) вычисляет r = х mod q (при r = 0 возвращается к шагу 2);
5) вычисляет s = (k h + r xА) mod q (при s = 0 возвращается к шагу 2);
6) подписывает сообщение парой чисел (r, s).
Для проверки подписанного сообщения (m; r, s) любой пользователь, знающий открытый ключ YA , делает следующее:
1) вычисляет h = h(m);
2) убеждается, что 0 < r, s < q;
3) вычисляет u1 = s · h-1 mod q и u2 = -r · h-l mod q;
4) вычисляет композицию точек на кривой P = [u1]G + [u2]YA = (х, у) и если Р = О , отвергает подпись;
5) если х mod q = r, принимает подпись, в противном случае отвергает ее.
Эффективная реализация операций Вычисление m-кратной композиции
ВХОД: точка Р, число m = (mt mt-1...m1)2.
ВЫХОД: Q = [m]P.
1Q <-- O;
2 FOR i = t, t-1, ..., 1 DO
3Q <-- [2]Q;
4IF mi = 1 THEN Q <-- Q + P;
5 RETURN Q.
Данный алгоритм требует t удвоений и в среднем t/2 сложений.
Пример: Вычислим [21]P. Здесь 21 = (10101)2 , t = 5. imi51:Q <-- O,Q <-- Q + P = P ;40:Q <-- [2]Q = [2]P ;31:Q <-- [2]Q = [4]P,Q <-- Q + P = [5] P ;20:Q <-- [2]Q = [10]P ;11:Q <-- [2]Q = [20]P,Q <-- Q + P = [21] P . Вместо 20 сложений было выполнено 4 удвоения и 3 сложения.
Сложение в проективном представлении
При вычислении композиции можно избавиться от вычисления инверсии, если в качестве координат использовать рациональные числа, производя вычисления отдельно с числителем и знаменателем. Наиболее выгодным оказалось взвешенное проективное представление координат:
Формулы вычисления x3 и y3:
Алгоритм:
ВХОД: P1 = (X1,Y1,Z1), P2 = (X2,Y2,Z2), P1,P2 ≠ O, P1 ≠ ±P2
ВЫХОД: P3 = (X3,Y3,Z3) = P1 + P2
λ1 = X1Z22
λ2 = X2Z12
λ3 = λ2 - λ1
λ4 = Y1Z23
λ5 = Y2Z13
λ6 = λ5 - λ4 λ7 = λ1 + λ2 λ8 = λ4 + λ5 Z3 = Z1 Z2 λ3
X3 = λ62 - λ7λ32
λ9 = λ7λ32 - 2X3
Y3 = (λ9λ6 - λ8λ33) / 2
Пример.
P1 = (5,1,1), P2 = (4,6,1)
λ1 = 5 · 1 = 5,
λ2 = 4 · 1 = 4,
λ3 = 4 - 5 = 6,
λ4 = 1 · 1 = 1,
λ5 = 6 · 1 = 6,
λ6 = 6 - 1 = 5, λ7 = 5 + 4 = 2,
λ8 = 1 + 6 = 0,
Z3 = 1 · 1 · 6 = 6,
X3 = 52 - 2 · 62 = 2,
λ9 = 2 · 62 - 2 · 2 = 2 - 4 = 5,
Y3 = (5 · 5 - 0 · 63) / 2 = 25 / 2 = (25+7) / 2 = 16 = 2.
P3 = (2,2,6) = (2/62, 2/63) = (2·6-2, 2·6-3) = (2·1, 2·6) = (2, 5).
Удвоение в проективном представлении
Формулы вычисления x3 и y3:
Алгоритм:
ВХОД: P1 = (X1,Y1,Z1), P1≠ O
ВЫХОД: P3 = (X3,Y3,Z3) = [2]P1
λ1 = 3X12 + aZ14
λ2 = 4X1Y12
Z3 = 2Y1Z1
X3 = λ12 - 2λ2
λ3 = 8Y14
Y3 = λ1(λ2 - X3) - λ3
Обмен ключами по алгоритму Диффи-Хеллмана
Данный алгоритм помогает обмениваться секретным ключом для симметричных криптосистем, но использует метод, очень похожий на асимметричный алгоритм RSA. Алгоритм назван по фамилиям его создателей Диффи (Whitfield Diffie) и Хеллмана (Martin Hellman). Предположим, что двум абонентам необходимо провести конфиденциальную переписку, а в их распоряжении нет первоначально оговоренного секретного ключа. Однако, между ними существует канал, защищенный от модификации. Пусть абонентам известны некоторые два числа v и n. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют случайные или псевдослучайные простые числа: абонент A - число Xa, абонент B - число Xb. Затем абонент A вычисляет и пересылает абоненту B значение:
A  B: (vXa) mod n,
а абонент B вычисляет и пересылает абоненту A:
B  A: (vXb) mod n,
A: k12 = ( ((vXb) mod n)Xa ) mod n,
B: k21 = ( ((vXa) mod n)Xb ) mod n.
На самом деле операция возведения в степень переносима через операцию взятия модуля по простому числу (то есть коммутативна в конечном поле), то есть у обоих абонентов получилось одно и то же число: (vXa·Xb) mod n. Его они и могут использовать в качестве секретного ключа. Пример.
v = 17; n = 23;
Xa = 3;
vXa = 173 mod 23 = 4 913 mod 23 = 14;
Xb = 5;
vXb = 175 mod 23 = 1 419 857 mod 23 = 21;
kab = (vXb)Xa = 213 = 9 261 mod 23 = 15;
kba = (vXa)Xb = 145 = 537 824 mod 23 = 15.
Аналог алгоритма Диффи-Хеллмана с использованием эллиптических кривых
Сначала выбираются параметры эллиптической кривой Ep(a,b) (p ≈ 2180) и генерирующая точка G, принадлежащая этой кривой. При выборе G важно, чтобы наименьшее значение q, при котором [q]G = O, оказалось очень большим простым числом. Эти параметры известны всем абонентам системы.
1. A: выбирает целое число nA < q; вычисляет точку PA = [nA]G;
2. B: выбирает целое число nB < q; вычисляет точку PB = [nB]G;
3. A  B: PA;
4. A  B: PB;
5. A: K = [nA]PB;
6. B: K = [nB]PA.
Приложение 1. Генерация простых чисел
Проверка на простоту
Для доказательства простоты данного нечетного числа n можно применять следующую стратегию:
1) проверяем, делится ли n на какое-нибудь простое число не превосходящее 5 000;
2) если n не делится ни на одно из них, то применяем к нему тест Миллера, используя в качестве оснований первые 20 простых чисел;
3) если тест Миллера по всем этим основаниям дает неопределенный ответ, то подвергаем n тесту на простоту.
Тест Миллера
Ввод: нечетное натуральное n и основание b, где 1 < b < n-1.
Вывод: одно из двух сообщений: "n составное" или "ничего определенного сказать нельзя".
Шаг 1. Последовательно делим n - 1 на 2 пока не получим нечетного частного. В результате найдем положительное целое k≥1 и нечетное q, для которых n - 1 = 2kq.
Шаг 2. Присвоим i нулевое значение, а r значение вычета bq по модулю n.
Шаг 3. Если i = 0 и r = 1, или i > 0, а r = n - 1, то вывести сообщение: "ничего определенного сказать нельзя"; в противном случае переходим к шагу 4.
Шаг 4. Увеличиваем i на 1 и заменяем r на r2 по модулю n; переходим к шагу 5.
Шаг 5. Если i < k, то возвращаемся к шагу 3; в противном случае выдаем сообщение: "n составное".
Пример: n = 561, b = 2.
560 = 24 * 35.
(Степени) i0 (35)1 (2*35)2 (2235)3 (23*35)(Вычеты) r263166671Тест на простоту
Пусть n - нечетное натуральное число, причем
n - 1 = p1e1... prer,
где p1<...<pr - простые числа. Если для каждого i=1,2,...,r существует такое целое число bi (2≤bi≤n-1), что bin-1 mod n ≡ 1 и bi(n-1)/pi mod n 1,
то n - простое.
Ввод: нечётное натуральное n
Вывод: одно из двух сообщений: "n простое" или "n не простое".
Шаг 1. Получаем разложение n - 1 на r простых множителей и присваиваем i значение 1.
Шаг 2. Если i > r, то вывести сообщение: "n простое", в противном случае присвоим b значение 2 и переходим к шагу 3.
Шаг 3. Если не выполняется условие и и b < n, то переходим к шагу 4, иначе переходим к шагу 5.
Шаг 4. Увеличиваем b на единицу и возвращаемся к шагу 3.
Шаг 5. Если b = n, то вывести сообщение: "n не простое"; в противном случае увеличиваем i на единицу и возвращаемся к шагу 2.
Решето Эратосфена
Решето Эратосфена - это старейший из известных способов выписывания простых чисел.
Он не требует вычисления отдельных делителей, прост в программировании и находит все простые числа меньшие, чем определенная верхняя граница, но этот алгоритм неэффективен при поиске очень больших простых чисел, так как он требует уйму памяти и огромного количества итераций.
Ввод: нечетное натуральное n. Вывод: список всех нечетных положительных простых чисел, меньших или равных n.
Шаг 1. Начинаем с создания вектора v с (n -1) / 2 ячейками, каждой из которых присвоено значение 1, и полагаем P = 3.
Шаг 2. Если P2 > n, выписываем все числа 2j + 1, для которых значение j-й ячейки вектора равно 1 и останавливаемся; в противном случае переходим к шагу 3. Шаг 3. Если значение ячейки вектора v с номером (P-1)/2 равно 0, увеличиваем P на 2 и возвращаемся к шагу 2; в противном случае переходим к шагу 4.
Шаг 4. Присваиваем новой переменной T значение P2; замещаем 0 значение ячейки вектора v c номером (T-1)/2 и увеличиваем T на 2P; повторяем эти два шага до тех пор, пока T<=n, затем увеличиваем P на 2 и возвращаемся к шагу 2.
Тест Люка - Лемера
Пусть p - простое число. Число Мерсенна М(p) является простым тогда и только тогда, когда Sp-2 mod M(p) = 0.
Главная составная часть теста - последовательность натуральных чисел: S0, S1, S2, ..., определяемая рекуррентной формулой
S0 = 4 и Sk+1 = (Sk2 -2) mod M(p).
Простые числа Мерсенна (M(p)=2p-1, где p - простое):
2357131719316189107127521607127922032281321742534423968999411121319937217012320944497862431105031320492160911398269Приложение 2. Разложение на множители
Алгоритм разложения путем деления методом проб
Ввод: натуральное число n.
Вывод: натуральное число f > 1 - наименьший простой делитель числа n - или сообщение о том, что n простое.
Шаг 1. Положить F = 2.
Шаг 2. Если n / F целое, то сообщить: "F является делителем числа n", и завершить работу; в противном случае перейти к шагу 3.
Шаг 3. Увеличить F на единицу и перейти к шагу 4.
Шаг 4. Если F ≥ , то сообщить: "n простое", и завершить работу; в противном случае перейти к шагу 2.
Расширение алгоритма для нахождения разложения числа на простые множители
Предположим, что в результате применения алгоритма разложения путем деления методом проб к n мы нашли делитель q1 этого числа. Тогда q1 - его наименьший простой множитель. Применим тот же алгоритм к числу n / q1. Предположим, что число n / q1 составное и q2 - его наименьший простой делитель. Ясно, что q2 ≥ q1. Заметим, однако, что эти делители могут оказаться равными. Такая возможность реализуется, если n делится на q12. Продолжая в том же духе, мы применяем алгоритм к n / (q1 q2) и т.д. В результате мы получаем последовательность простых чисел q1 ≤ q2 ≤ q3 ≤ ... ≤ qs , каждое из которых является делителем числа n. Критерием завершения работы алгоритма является получение делителя qk равного 1.
Пример: n = 450.
450 / 2 = 225 → 225 / 3 = 75 → 75 / 3 = 25 → 25 / 5 = 5 → 5 / 5 = 1. Стоп.
450 = 2 * 32 * 52.
Алгоритм Ферма разложения на множители
Если разность |p-q| мала, то произведение n = pq легко разлагается на множители с помощью алгоритма Ферма.
Ввод: нечетное натуральное число n.
Вывод: множитель числа n или сообщение о том, что n простое.
Шаг 1. Положить . Если n = х2, то х является делителем числа n, и работа алгоритма останавливается; в противном случае увеличить х на 1 и перейти к шагу 2. Шаг 2. Если х = (n + 1) / 2, то число n простое, и работа алгоритма останавливается; в противном случае вычислить .
Шаг 3. Если число у целое (т.е., если [у]2 = х2 - n), то n раскладывается в произведение (х + у)(х - у), и работа алгоритма останавливается; в противном случае увеличить х на 1 и перейти к шагу 2.
Как показывает следующий пример, этот алгоритм очень прост в применении. Допустим, мы хотим разложить на множители число n = 1 342 127. Сначала переменной х присваивается целая часть числа . В примере она равна х = 1158. Однако
х2 = 11582 = 1 340 964 < 1 342 127.
Поэтому мы должны увеличить х на 1. Мы продолжим этот процесс до тех пор, пока число не станет целым или не будет выполняться равенство х = (n+1) / 2. Заметим, что в нашем примере (n + 1) / 2 = 671064. Значения переменных х и у после завершения каждого цикла приведены в таблице.
x115933,97...116058,93...116176,11...116290,09...1163102,18...1164113 Таким образом, на шестом цикле мы получили целое число. Значит, искомые числа х = 1164 и у = 113. Соответствующие множители равны
х + у = 1277 и x - у = 1051.
Разложение n на p и q по φ(n)
Если n = pq и φ(n) = (p-1)(q-1) известны, то
φ(n) = (p-1)(q-1) = pq - (p+q) + 1 = n - (p + q) + 1,
так что сумма искомых простых делителей p + q = n - φ(n) + 1 известна. Далее,
(p+q)2 - 4n = (p2 + q2 + 2pq) - 4pq = (p - q)2,
поэтому разность тоже известна. Теперь, решая простую систему линейных уравнений, находим p и q.
Приложение 3. Алгоритмы арифметических вычислений
Модульное умножение A × B mod n
Для более эффективной работы алгоритма полезно представить множитель B в двоичной системе счисления: B = bk2k + bk-12k-1 + ... + b12 + b0,
где коэффициенты b0,...,bk могут принимать значения 0 или 1.
А умножение B на А производить поразрядно в цикле сразу же при этом вычисляя остаток от деления на n:
R = 0
for i from k to 0 do R = ( 2*R + A*bi ) mod n
return (R)
Модульная редукция B mod n
Суть метода Барета заключается в вычислении значения R = B mod n, для чего предварительно вычисляется m = [22k / n]. Эти числа можно запомнить, если выполняются многократные вычисления с использованием данного модуля:
Входные данные:
B = b2k-122k-1 + ... + b12 + b0;
n = nk-12k-1 + ... + n12 + n0 (mk-1 = 0);
m = 22k div n.
q1 = b div 2k-1
q2 = q1 m
q3 = q2 div 2k+1
r1 = b mod 2 k+1
r2 = (q3 n) mod 2 k+1
r = r1 - r2
if r < 0 then r = r + 2k+1
while r >= n do r = r - n
return (r) Несмотря на то, что в данном алгоритме производится большое количество операций деления, все они легко реализуются с помощью правого сдвига. При этом следует учитывать, что q2 используется для вычисления q3. В связи с этим в q2 используется только k+1 младших разрядов.
Алгоритм квадратных корней
Ввод: целое число n > 2.
Вывод: целая часть квадратного корня из n.
Шаг 1. Начинаем с присвоений: X = n и У = [(n + 1)/2] и переходим к шагу 2.
Шаг 2. Если X = У, то останавливаемся и выписываем Х; в противном случае переходим к шагу 3.
Шаг 3. Заменяем значение X на текущее значение У, а переменной Y присваиваем значение [(X2 + n) / 2Х] и возвращаемся к шагу 2.
Модульное возведение в степень AB mod n
Предположим, что даны три натуральных числа а, е и n. Опишем алгоритм определения вычета степени ае по модулю n. Для более эффективной работы алгоритма полезно представить показатель е в двоичной системе счисления:
где коэффициенты могут принимать значения 0 или 1. Таким образом,
Заметим, что может быть равно 1 (если bо = 0) или а (если bо = 1). Обозначив через P1, получаем
Теперь положим . Тогда
Продолжая начатую процедуру, мы определяем последовательность целых чисел где . Конечно, поскольку мы делаем вычисления с элементами из Zn, нам надлежит находить вычет всех произведений по модулю n на каждом шаге алгоритма.
Обратите внимание на то, что на каждом этапе мы либо возводим в квадрат число, либо вычисляем произведение Более того, если на каком-то шаге нам попалось нулевое значение bi, нам совершенно не нужно вычислять.
На практике представление показателя е в двоичной системе счисления происходит одновременно с вычислением степени. Так, например, если е нечетно, то bо = 1, в противном случае, bо = 0. Аналогично, основываясь на четности или нечетности числа
можно определить значение b1 . Заметьте, что выписанная сумма равна одному из следующих отношений: е / 2, если е - четно, и (е - 1) / 2, если оно нечетно. Формализованный алгоритм выглядит следующим образом:
Алгоритм степеней
Ввод: целые числа а, е и n, где а, n > 0 и е ≥ 0. Вывод: вычет степени ае по модулю n.
Шаг 1. А = а, Р = 1, Е = е.
Шаг 2. Если Е = 0, то выводим сообщение: "ае  Р (mod n)"; в противном случае переходим к шагу 3.
Шаг 3. Если Е нечетно, то присваиваем переменной Р вычет произведения А ·Р по модулю n, а Е - значение (Е - 1)/2, после чего переходим к шагу 5; в противном случае идем к шагу 4.
Шаг 4. Если Е четно, то присваиваем Е значение Е/2 и идем к шагу 5.
Шаг 5. Заменяем текущее значение переменной А на вычет А2 по модулю n и переходим к шагу 2.
Приложение 3. Расширенный алгоритм Евклида
Алгоритм Евклида предназначен для вычисления наибольшего общего делителя двух натуральных чисел. Наибольший общий делитель чисел a и b - наибольшее целое число d, на которое и а, и b делятся: d = НОД(a,b). Если НОД(а, b) = 1, то числа а и b взаимно простые.
Алгоритм Евклида
Ввод: натуральные числа а и b, а≥ b.
Вывод: наибольший общий делитель чисел а и b.
Шаг 1. Положить А = аиВ = b.
Шаг 2. Заменить значение R остатком от деления А на В и перейти к шагу 3.
Шаг 3. Если R = 0, то сообщить: наибольший общий делитель чисел a u b равен В", и остановиться; в противном случае перейти к шагу 4.
Шаг 4. Заменить значение А на значение B, значение В на значение R и возвратиться к шагу 2.
Расширенный алгоритм Евклида
Пусть a и b - два целых положительных числа. Тогда существуют целые (не обязательно положительные) числа x и y, такие, что
ax + by = НОД(a, b). (1)
Расширенный алгоритм Евклида служит для отыскания НОД(a, b), x и y, удовлетворяющих данному равенству.
Введем три вектора U = (u1, u2, u3), V = (v1, v2, v3), T = (t1, t2, t3).
ВХОД: Положительные целые числа a, b, a >= b.
ВЫХОД: НОД(a, b), x, y, ax + by = НОД (a, b).
1. U <-- (a, 1, 0), V <-- (b, 0, 1).
2. WHILE v1 <> 0 DO
3. q <-- u1 div v1;
4. T <-- (u1 mod v1, u2 - qv2, u3 - qv3);
5. U <-- V, V <-- T.
6. RETURN U=( НОД(a, b), x, y). Во многих задачах криптографии для заданных чисел c, m требуется найти такое число d < m, что
cd mod m = 1 . (2)
Такое d существует тогда и только тогда, когда c и m - взаимно простые числа.
Число d называется инверсией c по модулю m и часто обозначается c-1 mod m.
Естественно будет выглядеть запись
cс-1 mod m = 1 .
Умножение на c-1 соответствует делению на с при вычислениях по модулю m.
Покажем, как можно вычислить инверсию с помощью расширенного алгоритма Евклида. Равенство (2) означает, что для некоторого целого k
cd - km = 1 . (3)
Учитывая, что c и m взаимно просты, перепишем (3) в виде m(-k) + cd = НОД(m, c) . (4)
Если число d получится отрицательным, то к нему надо прибавить m.
Пример. Найдем 3-1 mod 11.
a = 11, b = 3, U1110
V U301
T V U21-3q = 3
T V U1-14q = 1
T V0 3-11q = 2
Получается: 3-1 mod 11 = 4
Литература
1. ГОСТ Р 34.10-94. Государственный стандарт Российской Федерации. Криптографическая защита информации. Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма.
2. Коутинхо С. Введение в теорию чисел. Алгоритм RSA. М.: Постмаркет, 2001. - 328 с.
3. Программирование алгоритмов защиты информации. Учебное пособие // Домашев А.В., Грунтович М.М., Попов В.О., Правиков Д.И., Прокофьев И.В., Щербаков А.Ю. - М.: Издатель Молгачева С.В., Издательство "Нолидж", 2002.- 416 с.
4. Петров А. А. Компьютерная безопасность. Криптографические методы защиты. - М.: ДМК, 2000. - 448 с.
5. Виноградов И. М. Основы теории чисел. М.: Наука, 1982.
6. Кнут Д. Искусство программирования на ЭВМ. Т. 2. Получисленные алгоритмы. М.: Мир, 1977.
7. Прахар К. Распределение простых чисел. М.: Мир 1967.
8. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.
9. Акритас А. Основы компьютерной алгебры с приложениями. Пер. с англ.- М.: Мир, 1994. - 544 с.
10. Саломаа А. Криптография с открытым ключом. М.: Мир, 1996. - 318 с.
11. Лебедев А. Н. Криптография с открытым ключом и возможности ее практического применения // Защита информации. 1992. Вып. 2. С. 129-147.
12. Уильямс Х. Проверка чисел на простоту с помощью вычислительных машин // Кибернетический сборник. 1986. Вып. 23. С. 51-99.
13. Menezes A., van Oorschot P., Vanstone S. Handbook of applied cryptography. CRC Press, 1996. 661 p. (http://www.cacr.math.uwaterloo.ca/ hac/).
Документ
Категория
Рефераты
Просмотров
149
Размер файла
296 Кб
Теги
мсзки, работа, лабораторная
1/--страниц
Пожаловаться на содержимое документа