2015-05-05
836
Российский стандарт ГОСТ 28147-89.
В Российской Федерации установлен государственный стандарт (ГОСТ 28147—89) на алгоритмы криптографического преобразования информации в ЭВМ, вычислительных комплексах и вычислительных сетях. Эти алгоритмы допускается использовать без ограничений для шифрования информации любого уровня секретности. Алгоритмы могут быть реализованы аппаратными и программными способами.
Стандартом определены следующие алгоритмы криптографического преобразования информации:
· простая замена;
· гаммирование;
· гаммирование с обратной связью;
· выработка имитовставки.
Общим для всех алгоритмов шифрования является использование ключа размерностью 256 бит, разделенного на восемь 32-разрядных двоичных слов, и разделение исходной шифруемой двоичной последовательности на блоки по 64 бита.
Криптосистема RSA
Название криптосистемы образовано из первых букв фамилий предложивших ее авторов (Rivest R., Shamir A., Adleman L. A method for obtaining digital signatures and pablic-key cryptosystems. Commun. ACM, v.21, N2, 1978).
|
|
|
Система относится к блочным экспоненциальным системам, так как каждый блок М открытого текста рассматривается как целое число в интервале (0,..., n-1) и преобразуется в блок С следующим открытым преобразованием
C = E (e,n) (M) = Me (mod n),
где E(e,n) - преобразование, а (e,n) - ключ зашифрования.
При расшифровании блок открытого текста М восстанавливается таким же преобразованием, но с другим показателем степени.
M = D (d,n) (C) = Cd (mod n),
где D(d,n) - преобразование, а (d,n) - ключ расшифрования.
В основе этого метода лежит довольно сложное теоретическое обоснование. Числа e и d связаны с n определенной зависимостью и существуют рекомендации по выбору ключевых элементов на основе простых чисел. Если взять два простых числа p и g, определить n = p х q, то можно определить пару чисел e и d, удовлетворяющих заданным условиям. Если сделать открытыми числа e и n, а ключ d (и обязательно p и g) держать в секрете - то предложенная система является RSA-криптосистемой открытого шифрования. Очевидно, ее стойкость определяется сложностью операции извлечения из С корня степени е по модулю n.
Рассмотрим основные этапы реализации алгоритма RSA.
1. Отправитель вычисляет n = p х q и M=(p-1)(q-1).
2. Затем он выбирает случайное целое число e, взаимно простое с М и вычисляет d, удовлетворяющее условию
ed = 1 (mod M).
Напомним, что два числа являются взаимно простыми, если их HOD =1. Числа а и b имеют HOD d, если d делит и а и b и максимальный среди таких чисел.
3. После этого он публикует е и n как свой открытый ключ шифрования, сохраняя d, как закрытый (секретный) ключ.
4. Рассмотрим теперь числа e и d. Предположим, что мы знаем одно из них и знаем соотношение, которым они связаны. Мы могли бы легко вычислить второе число, однако мы не знаем чисел p и q. Следовательно можно одно из чисел подарить кому-нибудь вместе с n и попросить его посылать нам сообщения следующим образом.
|
|
|
5. Сообщение представить как векторы (блоки) длины l
X= (x1,x2...,xl)
0<xi< M;
6. Каждое xi возвести в степень e по mod n.
7. Прислать нам Y=(x1e (mod n), x2e (mod n),...,xle (mod n)).
Обозначим t=yi =хie (mod n) и рассмотрим расшифрование полученной информации.
Для этого возведем полученное число t в степень второго числа пары - d:
R=td(mod n) = xe (mod n)d(mod n) = xed (mod n).
В соответствие с п.2 соотношение ed=1(mod M). а это означает, что ed-1 делится нацело на (p-1)(q-1), т.е. ed=1+a(p-1)(q-1),
где а - целое число.
Утверждается, что
хed(mod n) =x.
Действительно,
xed(mod n) = x1+a(p-1)(q-1) (mod n)
Учитывая,что
xp-1 = 1 mod p, xq-1 = 1 mod q (эти соотношения доказываются как малая теорема Ферма, например в /10/) получим
x(p-1)(q-1) = 1(mod pq)
x1+a(p-1) (g-1)(mod n) = x, т.к.
xa(p-1) (q-1) = 1(mod pq), из-за того,
что x(p-1) (q-1) = 1(mod pq),
x mod n = x, так как x<M.
Что и требовалось доказать.
Цифровая (электронная) подпись
Одним из основных применений криптосистем с открытым ключом является их использование при создании так называемой цифровой или электронной подписи (digital signature). Впервые идея цифровой подписи была высказана в работе Диффи и Хеллмана.
Один из вариантов изложения принципа электронной подписи выглядит так. Требуется, чтобы существовали взаимообратные преобразования Ek и Dk, для которых выполняется
Ek[Dk(M)] =M для любого открытого текста М.
Тогда Dk считается секретным преобразованием, с помощью которого пользователь может зашифровать исходный текст C=Dk(M) и послать это значение в качестве цифровой подписи к сообщению М другим пользователям, обладающим знанием открытого преобразования Ek. Очевидно, что определение Dk при знании Ek должно быть вычислительно неразрешимой задачей.
Система RSA широко используется в системе цифровой подписи, так как ее преобразования обладают всеми необходимыми свойствами. Использование цифровой подписи предполагает существование двух процедур: подписывания и проверки /8.9/.
Процедура подписывания сообщения M – это возведение числа M в степень d по mod n:
S = Md (mod n).
Число S есть цифровая подпись, которую может выработать только владелец секретного ключа.
Процедура проверки подписи S, соответствующей сообщению M – это возведение числа S в целую степень e по mod n:
M’= Se (mod n).
Если M’= M, то сообщение M признается подписанным пользователем, который предоставил ранее открытый ключ e.
В реализации для сокращения времени подписывания и размера подписи, в качестве источника для подписи служит не само исходное сообщение М (произвольной длины), а некоторая производная от него (фиксированной длины). Для ее получения используется общеизвестная функция Н, отображающая любое сообщение М в сообщение Н(М) фиксированного малого размера, которое далее преобразуется в цифровую подпись. Функция Н называется функцией хеширования (hash function), в простейшем случае это может быть, например, функция вычисления контрольной суммы текста сообщения по модулю 232, размер приведенного для электронного подписывания сообщения тогда будет равен 32 двоичным разрядам (четырем байтам).
Стандарт США – DES.
Государственным стандартом США на шифрование информации является стандарт DES (Data Encryption Standard). Алгоритм шифрования, положенный в основу стандарта, был разработан фирмой IBM. После проверки специалистами Агентства Национальной Безопасности США алгоритм получил статус государственного стандарта. Стандарт DES используется федеральными департаментами для закрытия информации в автоматизированных системах, за исключением некоторых видов информации, определенных специальными актами. Кроме того, этот стандарт шифрования широко используется негосударственными организациями не только в США, но и во всем мире.
|
|
|
В стандарте DES исходная информация разбивается на блоки по 64 бита в каждом и подвергается криптографическому преобразованию с использованием ключа, длиной 56 или 64 бита.
Блоки исходной информации подвергаются итерационной обработке с использованием операций перестановки и функции шифрования. Для вычисления функции шифрования предусматривается получение 48-битового ключа из 64-битового, расширение 32-битового кода до 48-битового, преобразование 6-битового кода в 4-битовый и перестановка бит в 32-битовой последовательности.
Процесс расшифрования является инверсным по отношению к процессу шифрования и выполняется с использованием того же ключа, что и при шифровании.
