Презентацию к лекции Вы можете скачать здесь.
Цель лекции
Рассмотреть круг задач, на решение которых ориентированы криптографические методы
Изучить основные понятия и определения криптографии
Ознакомиться с рекомендациями Microsoft по применению криптографических алгоритмов
Рассмотреть отечественный стандарт шифрования данных ГОСТ 28147-89 и американский стандарт шифрования данных AES
Изучить концепцию криптосистемы с открытым ключом.
Классификация криптографических алгоритмов
В настоящее время общепризнанным является подразделение криптографических алгоритмов на следующие основные категории:
алгоритмы шифрования с секретным ключом (симметричные)блочные шифры
поточные шифры
алгоритмы шифрования с открытым ключом (асимметричные)
Криптоалгоритмы с секретным ключом
Идея, лежащая в основе большинства итерационных блочных шифров, состоит в построении криптографически стойкой системы путем последовательного применения относительно простых криптографических преобразований. Принцип многоразового шифрования с помощью простых криптографических преобразований был впервые предложен Шенноном в работе [5.1]: он использовал с этой целью преобразования перестановки и подстановки. Первое из этих преобразований переставляет отдельные символы преобразуемого информационного блока, а второе - заменяет каждый символ (или группу символов) из преобразуемого информационного блока другим символом из того же алфавита (соответственно группой символов того же размера и из того же алфавита). Узлы, реализующие эти преобразования, называются, соответственно, P-блоками ( P-box, permutation box ) и S-блоками ( S-box, substitution box ).
В 1973-74 гг. Национальное Бюро Стандартов США ( NBS ) опубликовало документы, содержащие требования к криптографическому алгоритму, который мог бы быть принят в качестве стандарта шифрования данных в государственных и частных учреждениях. В 1976 г. в качестве такового стандарта был утвержден алгоритм, разработанный фирмой IBM. В 1977 г. этот стандарт был официально опубликован и вступил в силу как федеральный стандарт США для шифрования данных - Data Encryption Standard или сокращенно DES [5.2].
В самом схематичном виде 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 [5.3] корпорации RSA Data Security, IDEA [5.5] компании Ascom, Cast [5.4] компании Entrust, Safer [5.6] компании Cylink и Blowfish [5.7] компании Counterpane Systems. Коммерческие альтернативы DES получили определенное распространение, но ни одна из них не стала стандартом.
В 1997 г. Национальный институт стандартов и технологий США ( NIST ) объявил о начале программы по принятию нового стандарта криптографической защиты. В октябре 2000 г. конкурс завершился. Победителем был признан шифр Rijndael [5.8], разработанный бельгийцами Д. Дейменом и В. Райменом. Алгоритм Rijndael стал основой для нового американского стандарта AES (Advanced Encryption Standard), который в 2001 г. пришел на смену DES и Triple DES и действует и по сей день. Rijndael - это итерационный блочный шифр, имеющий архитектуру "Квадрат". Он быстрый, простой, защищенный, универсальный и хорошо подходит для реализации на смарт-картах. Шифр имеет переменную длин у блоков и различные длины ключей. Длина ключа и длина блока могут быть равны независимо друг от друга 128, 192 или 256 битам. В стандарте AES определена длина блока, равная 128 битам. Шифр AES характеризуется хорошей устойчивостью по отношению к атакам по мощности и по времени. Именно этот шифр рекомендует использовать Microsoft для симметричного шифрования.
Отечественный стандарт шифрования носит официальное название "Алгоритм криптографического преобразования ГОСТ 28147-89" [5.10]. Как явствует из его номера, стандарт был принят в СССР в 1989 г. Если охарактеризовать алгоритм ГОСТ в самом общем виде, то он является блочным шифром, построенным по схеме Фейстеля с 32 циклами шифрования. Длина информационного блока - 64 бита, длина ключа - 256 бит.
Основные отличия алгоритма ГОСТ от алгоритма DES - в строении функции, которая осуществляет отображение $$Z_2^32 \times Z_2^48 \to Z_2^32$$, и алгоритме выработки цикловых ключей. И в том и в другом случае преобразования, используемые в алгоритме ГОСТ, проще для программной реализации. Исследования [5.9] показывают, что российский стандарт не уступает по стойкости американскому AES.
Основная идея поточного шифрования состоит в том, что каждый из последовательных знаков открытого текста подвергается своему преобразованию. В идеале разные знаки открытого текста подвергаются разным преобразованиям, т.е. преобразование, которому подвергаются знаки открытого текста, должно изменяться с каждым следующим моментом времени. Реализуется эта идея следующим образом. Некоторым способом получается последовательность знаков $$k_1,k_2, \ldots,$$ называемая ключевым потоком ( keystream ) или бегущим ключом ( running key, RK ). Затем каждый знак $$x_i$$ открытого текста подвергается обратимому преобразованию, зависящему от $$k_i$$ - соответствующего знака ключевого потока.
Поточные шифры почти всегда работают быстрее и обычно требуют для своей реализации гораздо меньше программного кода, чем блочные шифры. Наиболее известный поточный шифр был разработан Р. Ривестом; это шифр 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 ) [5.13];
Криптосистема RSA ;
Криптосистема Эль-Гамаля - EGCS ( El Gamal Cryptosystem );
Криптосистема, основанная на свойствах эллиптических кривых - ECCS ( Elliptic Curve Cryptosystems ).
Применение алгоритмов шифрования с открытым ключом позволяет:
избавиться от необходимости секретных каналов связи для предварительного обмена ключами;
свести проблему взлома шифра к решению трудной математической задачи, т.е., в конечном счете, принципиально по-другому подойти к обоснованию стойкости криптосистемы;
решать средствами криптографии задачи, отличные от шифрования, например, задачу обеспечения юридической значимости электронных документов.
Для решения проблемы, описанной в последнем пункте, были предложены различные схемы электронно-цифровой подписи ( ЭЦП ). ЭЦП позволяет аутентифицировать автора информации, передающейся в цифровом виде. В определенных ситуациях (например, в электронной коммерции при осуществлении сделок по купле или продаже) ЭЦП по юридической силе приравнивается к обычной подписи "от руки". Кроме того, электронная подпись позволяет убедиться в том, что информация не была искажена при передаче.
Схема ЭЦП должна определять три следующих алгоритма:
алгоритм подписи;
алгоритм проверки подписи.
алгоритм генерации ключевой пары для подписи и ее проверки;
RSA [5.14] - криптографическая система с открытым ключом, обеспечивающая оба механизма защиты: шифрование и цифровую подпись. Криптосистема RSA была разработана в 1977 году и названа в честь авторов: Рональда Ривеста, Ади Шамира и Леонарда Адлемана.
Принцип её действия в следующем. Берутся два больших случайных простых числа $$p$$ и $$q$$ приблизительно равной разрядности и вычисляется их произведение $$n=pq$$. Затем выбирается число $$e$$, взаимно простое с произведением $$(p-1)(q-1) $$ и вычисляется число $$d=e^{-1} (mod(p-1)(q-1)) $$, взаимно простое с $$n$$.
Числа $$e$$ и $$n$$ становятся открытым ключом, число $$d$$ - закрытым. Чтобы создать шифртекст $$c$$, отправитель возводит сообщение $$m$$ в степень $$e$$ по модулю $$n$$, где $$e$$ и $$n$$ - показатели открытого ключа получателя: $$c=m^e(mod n) $$.
Чтобы расшифровать полученный шифртекст $$c$$, получатель вычисляет $$c$$ в степени $$d$$ по модулю $$n : m=c^d(mod n) $$.
Если абонент А хочет подтвердить свое авторство сообщения, он сначала шифрует его на своем секретном ключе, а потом на открытом ключе абонента Б. Соответственно, абонент Б применяет к полученному сообщению свой секретный ключ и открытый ключ абонента А; успешное расшифрование является гарантией того, что отправить сообщение мог только абонент А.
Схема Эль-Гамаля [5.15] основана на трудности вычисления дискретных логарифмов в конечном поле в сравнении с лёгкостью возведения в степень в том же самом поле.
Для генерации пары ключей сначала выбирается простое число $$p$$ и два случайных числа, $$g$$ и $$x$$ ; оба эти числа должны быть меньше $$p$$. Затем вычисляется $$y=g^x (mod p) $$.
Открытым ключом становятся $$y$$, $$g$$ и $$p$$. И $$g$$, и $$p$$ можно сделать общими для группы пользователей. Закрытым ключом является $$x$$. Теперь, чтобы зашифровать сообщение $$m$$, сначала выбирается случайное $$k$$, взаимно простое с $$p-1$$. Затем вычисляются $$a=g^k (mod p), b=y^k m(mod p) $$. Пара $$a$$ и $$b$$ является шифртекстом, что увеличивает исходное сообщение в два раза. Для расшифрования вычисляется $$m=b/a^x (mod p) $$.
На схеме Эль-Гамаля базировались стандарты ЭЦП в России и США, принятые в 1994 году [5.17, 5.16] и действовавшие вплоть до 2001 г.
Последние математические достижения показали, что проблема логарифмирования в конечных полях не является достаточно прочным фундаментом. Наиболее эффективные на сегодняшний день алгоритмы дискретного логарифмирования имеют уже не экспоненциальную, а субэкспоненциальную временную сложность. Это алгоритмы "index-calculus", использующие факторную базу, к числу которых относятся алгоритм Адлемана [5.18], несколько версий "COS" (алгоритма Копперсмита-Одлыжко-Шреппеля) [5.19] и решето числового поля [5.20]. Ведутся работы по повышению эффективности этих алгоритмов. Так, метод, описанный в [5.21], направлен на повышение эффективности решения линейных уравнений в кольцах вычетов, поскольку все субэкспоненциальные методы дискретного логарифмирования сводятся к этой задаче.
Ряд успешных атак, описанных, например, в [5.23], на системы, основанные на сложности дискретного логарифмирования в конечных полях, привел к тому, в 2001 г. России и США были приняты новые стандарты на ЭЦП [5.22, 5.24]. Процессы формирования и проверки электронной ЭЦП существенно не изменились, однако вместо элементов конечного поля $$GF(2^n) $$ или $$GF(p) $$ они оперируют эллиптическими числами, т.е. решениями уравнения эллиптических кривых над указанными конечными полями, а роль операции возведения в степень в конечном поле выполняет операция взятия кратной точки эллиптической кривой. Если старый российский стандарт ЭЦП оперирует 1024-битовыми блоками, то новый - 256-битовыми, но при этом обладает большей стойкостью. Важно отметить, что специальный выбор типа эллиптической кривой позволяет не только во много раз усложнить задачу взлома схемы ЭЦП, но и уменьшить рабочий размер блоков данных. Криптосистемы на основе эллиптической кривой получают все большее распространение скорее как альтернатива, а не замена системам на основе RSA. Они имеют некоторые преимущества, особенно при использовании в устройствах с маломощными процессорами и/или маленькой памятью. Так, согласно стандарту США [5.24] на выработку и верификацию цифровой подписи DSS ( Digital Signature Standard ), ЭЦП может вырабатываться по одному из трех алгоритмов: DSA ( Digital Signature Algorithm ), основанному на проблеме дискретного логарифма в конечном поле, ANSI X9.31 (RSA DSA) [5.26] или ANSI X9.63 [5.25] ( EC DSA - алгоритм выработки подписи, основанный на проблеме дискретного логарифма в группе точек эллиптической кривой над конечным полем).
Шифрование на платформе Windows
Шифрование - это форма криптографии, предназначенная для преобразования открытого текста с помощью некоторого алгоритма таким образом, чтобы результат был бессмыслицей для лица, не обладающего некоторым секретом для раскрытия исходных данных. Шифрование лежит в основе таких мер безопасности, как цифровая подпись, цифровой сертификат, инфраструктура открытых ключей и др. Перечисленные технологии позволяют повысить безопасность операций, выполняемых с использованием вычислительной техники. Для зашифрования и расшифрования информации используются ключи. Ключ - это переменная, длина которой измеряется в битах. Чем больше двоичных разрядов в используемом ключе, тем сложнее в общем случае будет взломать шифр.
На платформах Windows XP и Windows Server 2003 компания Microsoft рекомендует использовать следующие криптографические алгоритмы [5.11]:
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" [5.12] и предусматривает использование асимметричных криптоалгоритмов на основе эллиптических кривых. Алгоритмы "Suite B" включают:
AES (шифрование);
EC-DSA (электронно-цифровая подпись);
EC-DH или EC-MQV (обмен секретными ключами );
SHA-2 (хеширование).
Далее мы более подробно рассмотрим алгоритмы шифрования (с секретным и открытым ключом) и алгоритмы хеширования, а также приведем рекомендации Microsoft относительно их применения.
Краткие итоги
В данной лекции рассмотрены основные понятия и определения из области криптографии. Описаны схемы работы симметричных и асимметричных шифров. Указаны стандарты, регламентирующие использование криптографии в России и США. Представлены рекомендации Microsoft по применению криптографических алгоритмов.
