Лекция 3. Криптографические алгоритмы

Лекция 3. Криптографические алгоритмы

Цель лекции:

-      рассмотреть круг задач, на решение которых ориентированы криптографические методы;

-      изучить основные понятия и определения криптографии;

-      ознакомиться с рекомендациями Microsoft по применению криптографических алгоритмов;

-      рассмотреть отечественный стандарт шифрования данных ГОСТ 28147-89 и американский стандарт шифрования данных AES;

-      изучить концепцию криптосистемы с открытым ключом.

Классификация криптографических алгоритмов

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

1.     Алгоритмы шифрования с секретным ключом (симметричные):

-      блочные шифры;

-      поточные шифры;

2.     Алгоритмы шифрования с открытым ключом (асимметричные).

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

Идея, лежащая в основе большинства итерационных блочных шифров, состоит в построении криптографически стойкой системы путем последовательного применения относительно простых криптографических преобразований. Принцип многоразового шифрования с помощью простых криптографических преобразований был впервые предложен Шенноном в работе: он использовал с этой целью преобразования перестановки и подстановки. Первое из этих преобразований переставляет отдельные символы преобразуемого информационного блока, а второе - заменяет каждый символ (или группу символов) из преобразуемого информационного блока другим символом из того же алфавита (соответственно группой символов того же размера и из того же алфавита). Узлы, реализующие эти преобразования, называются, соответственно, P-блоками (P-box, permutation box) и S-блоками (S-box, substitution box).

В 1973-74 гг. Национальное Бюро Стандартов США (NBS) опубликовало документы, содержащие требования к криптографическому алгоритму, который мог бы быть принят в качестве стандарта шифрования данных в государственных и частных учреждениях. В 1976 г. в качестве такового стандарта был утвержден алгоритм, разработанный фирмой IBM. В 1977 г. этот стандарт был официально опубликован и вступил в силу как федеральный стандарт США для шифрования данных - Data Encryption Standard или сокращенно DES.

В самом схематичном виде DES представляет собой 16-цикловой итерационный блочный шифр. DES работает с блоками данных разрядностью 64 бита с использованием 56-разрядного ключа. Применяемые преобразования – поразрядное сложение по модулю два, подстановки и перестановки. Алгоритм выработки 48-битовых цикловых ключей из 56-битового ключа системы и ряд преобразований служат для обеспечения необходимого перемешивания и рассеивания перерабатываемой информации, однако при анализе DES чаще всего играют не самую существенную роль.

В 1999 г. на конференции, организованной RSA, компания Electronic Frontier Foundation взломала ключ DES менее чем за 24 часа. Одной из замен DES, получившей широкое распространение, стал алгоритм Triple DES. В этом случае алгоритм DES выполняется трижды, при этом используются 3 ключа, каждый из которых состоит из 56 битов (что, по сути, соответствует использованию 168-битного ключа). Тем не менее, криптоаналитики обнаружили способ, позволяющий сделать атаку прямого перебора эквивалентной атаке на 108-битовый ключ. Второй проблемой является значительное снижение скорости зашифрования и расшифрования данных.

В ответ на проблемы с длиной ключа и производительностью, проявившиеся в Triple DES, многие криптографы и компании разработали новые блочные шифры. Наиболее популярными предложениями стали алгоритмы RC2 и RC5корпорации RSA Data Security, IDEA компании Ascom, Cast компании Entrust, Safer компании Cylink и Blowfish компании Counterpane Systems. Коммерческие альтернативы DES получили определенное распространение, но ни одна из них не стала стандартом.

В 1997 г. Национальный институт стандартов и технологий США (NIST) объявил о начале программы по принятию нового стандарта криптографической защиты. В октябре 2000 г. конкурс завершился. Победителем был признан шифр Rijndael, разработанный бельгийцами Д. Дейменом и В. Райменом. Алгоритм Rijndael стал основой для нового американского стандарта AES (Advanced Encryption Standard), который в 2001 г. пришел на смену DES и Triple DES и действует и по сей день. Rijndael - это итерационный блочный шифр, имеющий архитектуру «Квадрат». Он быстрый, простой, защищенный, универсальный и хорошо подходит для реализации на смарт-картах. Шифр имеет переменную длин у блоков и различные длины ключей. Длина ключа и длина блока могут быть равны независимо друг от друга 128, 192 или 256 битам. В стандарте AES определена длина блока, равная 128 битам. Шифр AES характеризуется хорошей устойчивостью по отношению к атакам по мощности и по времени. Именно этот шифр рекомендует использовать Microsoft для симметричного шифрования.

Отечественный стандарт шифрования носит официальное название «Алгоритм криптографического преобразования ГОСТ 28147-89». Как явствует из его номера, стандарт был принят в СССР в 1989 г. Если охарактеризовать алгоритм ГОСТ в самом общем виде, то он является блочным шифром, построенным по схеме Фейстеля с 32 циклами шифрования. Длина информационного блока - 64 бита, длина ключа – 256 бит.

Основные отличия алгоритма ГОСТ от алгоритма DES - в строении функции, которая осуществляет отображение , и алгоритме выработки цикловых ключей. И в том и в другом случае преобразования, используемые в алгоритме ГОСТ, проще для программной реализации. Исследования показывают, что российский стандарт не уступает по стойкости американскому AES.

Основная идея поточного шифрования состоит в том, что каждый из последовательных знаков открытого текста подвергается своему преобразованию. В идеале разные знаки открытого текста подвергаются разным преобразованиям, т.е. преобразование, которому подвергаются знаки открытого текста, должно изменяться с каждым следующим моментом времени. Реализуется эта идея следующим образом. Некоторым способом получается последовательность знаков  называемая ключевым потоком (keystream) или бегущим ключом (running key, RK). Затем каждый знак открытого текста подвергается обратимому преобразованию, зависящему от  - соответствующего знака ключевого потока.

Поточные шифры почти всегда работают быстрее и обычно требуют для своей реализации гораздо меньше программного кода, чем блочные шифры. Наиболее известный поточный шифр был разработан Р. Ривестом; это шифр RC4, который характеризуется переменным размером ключа и байт-ориентированными операциями. На один байт требуется от 8 до 16 действий, программная реализация шифра выполняется очень быстро. Независимые аналитики исследовали шифр, и он считается защищенным. RC4 используется для шифрования файлов в таких изделиях, как RSA SecurPC. Он также применяется для защиты коммуникаций, например, для шифрования потока данных в Интернет-соединениях, использующих протокол SSL.

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

-      DES (Причины: малая длина ключей - 56 бит; если в 1993 г. атака на алгоритм заняла 3,5 часа на машине стоимостью $1 млн., то сегодня взлом можно осуществить в реальном времени; 3DES является более защищенным, но наличие лучших вариантов делает его использование неоправданным);

-      IDEA (International Data Encryption Standard)- хотя длина ключа (128 бит) является приемлемой, Microsoft проводит аналогии с алгоритмом DES: как известно, NSA подозревалось в сознательном ослаблении алгоритма DES, чтобы легко просматривать зашифрованные сообщения;

-      RC2 и RC5 - причины недоверия Microsoft к этим шифрам те же, что к DES и IDEA. Поскольку для шифрования используются «одноразовые блокноты», слабым местом может стать генератор псевдослучайных последовательностей. Современной тенденцией является использование блочных шифров в режиме поточного шифрования (например, поточное шифрование обеспечивают режимы CBF и OFB для алгоритма DES или режим гаммирования для алгоритма ГОСТ 28147-89);

-      Blowfish и Twofish - криптоалгоритмы, разработанные Брюсом Шнайером (B. Schneier), удовлетворяют требованиям стойкости, но не являются стандартами: Twofish, являющийся более поздней версией Blowfish, вышел в финал конкурса на замену DES, но уступил шифру Rijndael;

-      CAST: несмотря на то, что алгоритм показал себя устойчивым к линейному и дифференциальному криптоанализу, он имеет слишком малую длину ключа - 64 бита;

-      ГОСТ 28147-89: Microsoft подозревает стойкий шифр в наличии «лазеек» - «backdoors».

Криптоалгоритмы с открытым ключом

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

Наиболее известные криптосистемы с открытым ключом:

-      Рюкзачная криптосистема (Knapsack Cryptosystem);

-      Криптосистема RSA;

-      Криптосистема Эль-Гамаля – EGCS (El Gamal Cryptosystem;

-      Криптосистема, основанная на свойствах эллиптических кривых – ECCS (Elliptic Curve Cryptosystems).

Применение алгоритмов шифрования с открытым ключом позволяет:

-      избавиться от необходимости секретных каналов связи для предварительного обмена ключами;

-      свести проблему взлома шифра к решению трудной математической задачи, т.е., в конечном счете, принципиально по-другому подойти к обоснованию стойкости криптосистемы;

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

Для решения проблемы, описанной в последнем пункте, были предложены различные схемы электронно-цифровой подписи (ЭЦП). ЭЦП позволяет аутентифицировать автора информации, передающейся в цифровом виде. В определенных ситуациях (например, в электронной коммерции при осуществлении сделок по купле или продаже) ЭЦП по юридической силе приравнивается к обычной подписи «от руки». Кроме того, электронная подпись позволяет убедиться в том, что информация не была искажена при передаче.

Схема ЭЦП должна определять три следующих алгоритма:

-      алгоритм подписи;

-      алгоритм проверки подписи.

-      алгоритм генерации ключевой пары для подписи и ее проверки.

RSA - криптографическая система с открытым ключом, обеспечивающая оба механизма защиты: шифрование и цифровую подпись. Криптосистема RSA была разработана в 1977 году и названа в честь авторов: Рональда Ривеста, Ади Шамира и Леонарда Адлемана.

Принцип её действия в следующем. Берутся два больших случайных простых числа  и  приблизительно равной разрядности и вычисляется их произведение . Затем выбирается число , взаимно простое с произведением  и вычисляется число , взаимно простое с .

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

Чтобы расшифровать полученный шифртекст , получатель вычисляет  в степени  по модулю .

Если абонент А хочет подтвердить свое авторство сообщения, он сначала шифрует его на своем секретном ключе, а потом на открытом ключе абонента Б. Соответственно, абонент Б применяет к полученному сообщению свой секретный ключ и открытый ключ абонента А; успешное расшифрование является гарантией того, что отправить сообщение мог только абонент А.

Схема Эль-Гамаля основана на трудности вычисления дискретных логарифмов в конечном поле в сравнении с лёгкостью возведения в степень в том же самом поле.

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

Открытым ключом становятся ,  и . И , и  можно сделать общими для группы пользователей. Закрытым ключом является . Теперь, чтобы зашифровать сообщение , сначала выбирается случайное , взаимно простое с . Затем вычисляются . Пара  и  является шифртекстом, что увеличивает исходное сообщение в два раза. Для расшифрования вычисляется .

На схеме Эль-Гамаля базировались стандарты ЭЦП в России и США, принятые в 1994 году и действовавшие вплоть до 2001 г.

Последние математические достижения показали, что проблема логарифмирования в конечных полях не является достаточно прочным фундаментом. Наиболее эффективные на сегодняшний день алгоритмы дискретного логарифмирования имеют уже не экспоненциальную, а субэкспоненциальную временную сложность. Это алгоритмы «index-calculus», использующие факторную базу, к числу которых относятся алгоритм Адлемана, несколько версий «COS» (алгоритма Копперсмита – Одлыжко - Шреппеля) и решето числового поля. Ведутся работы по повышению эффективности этих алгоритмов. Так, метод, описанный в, направлен на повышение эффективности решения линейных уравнений в кольцах вычетов, поскольку все субэкспоненциальные методы дискретного логарифмирования сводятся к этой задаче.

Ряд успешных атак, описанных, например, в системах, основанных на сложности дискретного логарифмирования в конечных полях, привел к тому, в 2001 г. России и США были приняты новые стандарты на ЭЦП. Процессы формирования и проверки электронной ЭЦП существенно не изменились, однако вместо элементов конечного поля  или  они оперируют эллиптическими числами, т.е. решениями уравнения эллиптических кривых над указанными конечными полями, а роль операции возведения в степень в конечном поле выполняет операция взятия кратной точки эллиптической кривой. Если старый российский стандарт ЭЦП оперирует 1024-битовыми блоками, то новый - 256-битовыми, но при этом обладает большей стойкостью. Важно отметить, что специальный выбор типа эллиптической кривой позволяет не только во много раз усложнить задачу взлома схемы ЭЦП, но и уменьшить рабочий размер блоков данных. Криптосистемы на основе эллиптической кривой получают все большее распространение скорее, как альтернатива, а не замена системам на основе RSA. Они имеют некоторые преимущества, особенно при использовании в устройствах с маломощными процессорами и/или маленькой памятью. Так, согласно стандарту США на выработку и верификацию цифровой подписи DSS (Digital Signature Standard), ЭЦП может вырабатываться по одному из трех алгоритмов: DSA (Digital Signature Algorithm), основанному на проблеме дискретного логарифма в конечном поле, ANSI X9.31 (RSA DSA) или ANSI X9.63 (EC DSA – алгоритм выработки подписи, основанный на проблеме дискретного логарифма в группе точек эллиптической кривой над конечным полем).

Шифрование на платформе Windows

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

На платформах Windows XP и Windows Server 2003 компания Microsoft рекомендует использовать следующие криптографические алгоритмы:

-      AES-128 (или AES-192, или AES-256);

-      RSA 2048 (или с еще более длинным ключом);

-      SHA-2 (т.е. SHA-256 или SHA-512);

-      DSA (или SHA-2 / RSA).

Криптография Windows Vista (и Longhorn Server) соответствует рекомендациям Агентства Национальной Безопасности США и Национального института стандартов и технологии (NIST) по реализации протоколов «Suite B» и предусматривает использование асимметричных криптоалгоритмов на основе эллиптических кривых. Алгоритмы «Suite B» включают:

-      AES (шифрование);

-      EC-DSA (электронно-цифровая подпись);

-      EC-DH или EC-MQV (обмен секретными ключами);

-      SHA-2 (хеширование).

Далее мы более подробно рассмотрим алгоритмы шифрования (с секретным и открытым ключом) и алгоритмы хеширования, а также приведем рекомендации Microsoft относительно их применения.

Краткие итоги

В данной лекции рассмотрены основные понятия и определения из области криптографии. Описаны схемы работы симметричных и асимметричных шифров. Указаны стандарты, регламентирующие использование криптографии в России и США. Представлены рекомендации Microsoft по применению криптографических алгоритмов.

Скачано с www.znanio.ru