Вопрос 7 Криптографические методы закрытия данных. Несимметричные криптосистемы.

Несимметричные криптографические системы или системы с открытым ключом

Функция у=f(x) является односторонней, если она за сравнительно небольшое число операций преобразует элемент открытого текста x в элемент шифротекста у для всех значений x из области определения функции, а обратная операция x=f^-1(y) при известном y является вычислительно трудоемкой или невозможной (в идеале)

В качестве простейшей односторонней функции используют:

1) умножение матриц

2)скалярное произведение

3) вычисление значения полинома по модулю

4)экспоненциальные вычисления

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

Под односторонней функцией с секретом (с лазейкой, с потайной дверью - a trap-door one-way) называется зависящая от параметра k фукция y=f_k(x), такая, что знание k дает возможность легко построить обратное преобразование x=f_k^-1(y), тогда как без знания k определение х по известному y вычислительно не осуществимо.

В несим криптосистемах общедоступным является только ключ для процесса шифрования, а процедура дешифрования известна лишь обладателю секретного ключа.

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

В асимметричных системах должно удовлетворяться следующее требование: нет такого алгоритма (или он пока неизвестен), который бы из криптотекста и открытого ключа выводил исходный текст. Стойкость шифра зависит от длины ключа, и, если, пожертвовав скоростью, применить ключевую последовательность достаточного размера, можно добиться любой требуемой степени надежности.

ПРИМЕРЫ современных несимметричных алгоритмов

1. RSA

2. PGP – Pretty Good Privacy (Филипп Циммерман)

3. Диффи-Хеллмана

4. Эль-Гамаля

Одним из первых алгоритмов шифрования с открытым ключом стал шифр RSA. Этот алгоритм оказался настолько гибким и эффективным, что стал стандартом де-факто в асимметричной криптографии. Именно этот шифр используется практически во всех программах, где нужно применить алгоритм с открытым ключом. Стойкость шифра зависит от длины ключа, и, если, пожертвовав скоростью, применить ключевую последовательность достаточного размера, можно добиться любой требуемой надежности. Пример такой системы — широко известная криптосистема RSA с 1024-битовым ключом.

Алгоритм rsa

Фирма RSA Data Security образована в США в 1982 г. тремя математиками-выпускниками Массачусетского технологического института Rivest-Shamir-Adleman. RSA опубликован в 1978. Был частной собственностью, срок действия патента закончился в 2000г.

Алгоритм RSA (по первым буквам фамилий его создателей Rivest-Shamir-Adleman) основан на свойствах простых чисел (причем очень больших) и китайской теореме об остатках – CRT Chinese Remainder Theorem – в своей базовой форме впервые была доказана китайским математиком Сунь Цзе, жившем в первом веке до н.э.

Простыми называются такие числа, которые не имеют делителей, кроме самих себя и единицы. А взаимно простыми называются числа, не имеющие общих делителей, кроме 1.

Пусть p и q – простые числа, для каждого целого числа X можно вычислить пару (x mod p, x mod q). CRT утверждает, что можно выполнить и обратную операцию: зная пару (x mod p, x mod q), восстановить исходное значение Х.

Для начала выберем два очень больших простых числа p и q, длина каждого из которых составляет порядка 1000 бит и более (большие исходные числа нужны для построения больших криптостойких ключей. Например, Unix-программа ssh-keygen по умолчанию генерирует ключи длиной 1024 бита).

Определим параметр n как результат перемножения p и q, которые должны быть примерно одного размера.

= (p -1)*(q -1) - функция Эйлера

Выберем большое случайное число и назовем его e < , причем оно должно быть взаимно простым с .

Отыщем такое число d < , для которого верно соотношение

(e*d) mod = 1

Открытым ключом является пара чисел e и n, а закрытым —d и n.

При шифровании исходный текст рассматривается как числовой ряд, и над каждым его числом мы совершаем операцию

C = (Oi^e) mod n.

В результате получается последовательность C(i), которая и составит криптотекст. Декодирование информации происходит по формуле

Oi = (Ci^d) mod n.

Как видите, расшифровка предполагает знание секретного ключа.

Система относится к блочным экспоненциальным системам, так как каждый блок О_i открытого текста рассматривается как целое число в интервале (0,..., n-1) и преобразуется в блок С_i открытым преобразованием

Без знания простых сомножителей p и q значение ключей е и d определить очень трудно. Поэтому если делать открытыми числа e и n, а число d держать в секрете, то нахождение О из С сводится к трудной задаче извлечения корня степени е из числа С по модулю n. Это и означает, что алгоритм RSA может быть использован для построения криптосистемы с открытым ключом, т.е. системы открытого шифрования, когда преобразование шифрования открыто, а преобразование дешифрования держится в секрете. Стойкость алгоритма RSA можно оценить сверху сложностью разложения целого числа n на простые сомножители p и q. Это весьма трудная задача. (Единственная возможность вычислить d – это попытаться разложить n на простые множители p, q ) При достаточно большом значении n не существует известного на сегодня алгоритма, который мог бы определить закрытый ключ за приемлемое время. Вот почему разложение на простые множители играет такую важную роль в криптографии. Так как в силу открытости любой злоумышленник имеет доступ к преобразованию шифрования E_(e,n), то он может всегда выбрать любой открытый текст и получить соответствующий ему шифротекст. Поэтому криптосистемы с открытым ключом должны быть устойчивы к методам криптоанализа по паре открытый/закрытый текст.

Рассмотрим конкретный пример: Выбрать два простых числа: р = 7, q = 17. Вычислить n = p·q = 7 · 17 = 119. Вычислить (n) = (p - 1)·(q - 1) = 96. Выбрать е так, чтобы е было взаимнопростым с (n) = 96 и меньше, чем (n): е = 5. Определить d так, чтобы d·e ≡ 1 mod 96 и d < 96. d = 77, так как 77 · 5 = 385 = 4 · 96 + 1. Результирующие ключи открытый Kp = {5, 119} и закрытый KS = {77, 119}. Например, требуется зашифровать сообщение O = 19. 19⁵ (mod 119) = 66; С = 66. Для дешифрования вычисляется 66⁷⁷ (mod 119) = 19.

Для определения того, является ли число простым применяют различные алгоритмы: решето Эратосфена, цикличный перебор всех целых чисел, или метод основанный на малой теореме Ферма – при простом числе P и любом целом числе K < P справедливо следующее тождество  K^P-1 mod P = 1

Для полноты изложения отметим, что для алгоритма RSA существует малая вероятность того, что шифровка числа O возведем в степень е по модулю n может не изменить открытый текст O. Это следует из теоретического факта, что для каждого значения е существует, по крайней мере, 9 таких значений O, что

Например, для n=p·q= 47·59=2773 это числа

O = 0,1,2773,2537,2303,235,2538,471,236.

Электронная Цифровая Подпись – ЭЦП. Служит для :

1. удостоверения подлинности документа

2. удостоверения подлинности автора

3. запрета отказа от авторства подписанного документа

4. защищает от изменения документа.

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

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

ХЭШ

Перевод сообщения O в число H(O) (схема Горнера):

H(O)=

где X – основание системы

Возьмем в качестве подписи название алгоритма, т.е. RSA. Чтобы перевести RSA в число будем считать букву R= 18, S= 19, A = 1 по порядковому номеру в латинском алфавите. Пусть X=32 Тогда слову RSA будет соответствовать число

Kp = {5, 119} и закрытый KS = {77, 119}

RSA – 18 19 1

отправитель шифрует подпись своим закрытым ключом + делает хэш-отпечаток подписи и посылает все это получателю  86 66 1 + 1650. Получатель принимает сообщение и дешифрует подпись открытым ключом, затем выполняет вычисление h-кода. Если все совпало, то документ истинный и получен от истинного лица

Шифруем подпись открытым ключом

C(0)= 18⁵ mod 119= 86 C(1)= 19⁵ mod 119 =66 C(2)= 1⁵ mod 119= 1

Присоединяем хэш 1650

Отправляем

Получатель дешифрует

О(0)= 86⁷⁷ mod 119= 18 О(1)= 66⁷⁷ mod 119=19 О(2)= 1⁷⁷ mod 119= 1 вычисляет хэш

сравнивает

Одно из важных назначений электронной подписи — подтверждение авторства сообщения. Обычно в файлы ключей ЭЦП помимо собственно ключа записываются разные дополнительные сведения вроде ФИО и места работы его владельца, срока действия подписи и т. п. А в подпись, стоящую под сообщением или документом, копируются данные из секретного ключа, и прежде всего сведения о его хозяине, что позволяет установить авторство.

-----------------------------------------------

Криптосистема RSA широко применяется в Интернете. Когда вы подсоединяетесь к защищенному серверу по протоколу SSL (Secure Socket Layer – протокол безопасных соединений), устанавливаете на свой ПК сертификат WebMoney (Secure Electronic Payments Protocol - протокол безопасных электронных платежей) либо подключаетесь к удаленному серверу с помощью Open ISH (Information Super Highway - информационная супермагистраль) или SecureShell, то все эти программы применяют шифрование открытым ключом с использованием идей алгоритма RSA.