Слайд 1 Лекции Web-технологии защиты данных. - презентация

1 Слайд 1 Лекции Web-технологии защиты данных

2 Слайд 2 Причины появления технологий защиты Будем исходить из того, что защита данных безопасность Причины: »Использование открытой (общедоступной) «транспортной сети» (линии связи, сетевые протоколы) для для передачи критически важной или конфиденциальной информации. »Территориальная раcпределенность программных компонент и пользователей Принципы решения: «Шифрование данных («симметричные» и «несимметричные» алгоритмы) «Контроль за неизменностью данных (шифрование + MAC- и хэш-функции, цифровая подпись) «Аутентификация пользователей/программных компонент (все выше перечисленное, сертификаты)

3 Слайд 3 Передача данных по открытым каналам связи Причины развития крипто-технологий: »Использование открытой (общедоступной) «транспортной сети» (линии связи, сетевые протоколы) для для передачи критически важной или конфиденциальной информации. »Территориальная распределенность программных компонент и пользователей Принципы решения: «Шифрование данных («симметричные» и «несимметричные» алгоритмы) «Контроль за неизменностью данных (шифрование + MAC- и хэш- функции, цифровая подпись) «Аутентификация пользователей/программных компонент (все выше перечисленное, сертификаты) Основные понятия А ----->????>------> B Сообщение (P)

4 Слайд 4 Основные понятия: K – секретный ключ (известный A и B); P – исходный (нешифрованный текст); Е K (.) – алгоритм шифрования; D K (.) – алгоритм дешифрования; C = Е K (P) – крипто-текст (передаваемый по открытому каналу). Алгоритмы Е K (.) и D K (.) – известны (!). Секретом является только параметр K ! Классификация алгоритмов: u Потоковые: P – шифруется как поток символов, каждый символ крипто-текста C, вообще говоря, зависит от ВСЕХ символов исходного P; u Блочные (наиболее распространенные): P = {m 1, m 2, m 3, …}, | m 1 |=| m 2 |=| m 3 |=…= fixe, длина блока (4, 8, 16 символов ASCII, или 32, 64, 128 битов) E K (P) = С = {c 1, c 2, c 3, …}, c i = E K (m i ), | c i | = | m i | Симметричное шифрование (1) А >???> > B K P C=E K (P)--> C >-->P=D K (C)

5 Слайд 5 Основные требования к алгоритмам: u криптографический алгоритм должен быть достаточно сильным, чтобы зашифрованное сообщение невозможно было расшифровать без ключа, используя только различные статистические закономерности зашифрованного сообщения или какие-либо другие способы, основанные на семантике класса текстов, грамматике и орфографии языка исходного сообщения. u безопасность передаваемого сообщения должна зависеть ТОЛЬКО от секретности ключа, но не от секретности алгоритма. Алгоритм должен быть исследован специалистами, чтобы исключить наличие слабых мест, когда проявляется взаимосвязь между незашифрованным и зашифрованным сообщениями. u алгоритм должен быть таким, чтобы трудно было узнать ключ, даже зная достаточно много пар (зашифрованное сообщение, незашифрованное сообщение), полученных при шифровании с использованием данного ключа E K (m) m(?), [{E K (m 1 ),m 1 }, {E K (m 1 ),m 1 }, {E K (m 3 ),m 3 },...] K(?) вычислительно ТРУДНЫЕ задачи Симметричное шифрование (2)

6 Слайд 6 Основные операции алгоритмов: блоки и ключи – трактуются, либо как битовые последовательности { }, либо как положительные числа в двоичном представлении. В большинстве блочных алгоритмов симметричного шифрования используются следующие типы операций: »Табличная подстановка, при которой группа битов отображается в другую группу битов. Так называемые S-box. »Перемещение (перестановка) битов исходного сообщения. I={i 1, i 2, i 3,..., i |m| }, m={b 1,b 2,b 3,...b |m| }, I(m) {b i 1,b i 2, b i 3,...,b i |m| } »Операция сложения по модулю 2, XOR или : 0 0=0, 0 1=1 0=1, 1 1=0) »Операция сложения по модулю 2 32 или по модулю »Циклический сдвиг на некоторое число битов (>>>: >>>{0111}={1011}). Все эти операции имеют целью «перемешать» биты исходного сообщения так, чтобы затруднить его восстановление по зашифрованному, и при этом оставалась возможность однозначного восстановления исходной последовательности битов, если известны параметры «перемешивания». Эти параметры и есть секретный ключ алгоритма шифрования. Симметричное шифрование (3)

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

8 Слайд 8 Сети Фейстеля/Фейштеля (Feistel): Входной блок делится на несколько подблоков равной длины, называемых ветвями. В случае, если блок имеет длину 64 бита, используются две ветви по 32 бита каждая. Каждая ветвь обрабатывается независимо от другой, после чего осуществляется циклический сдвиг всех ветвей влево. Такое преобразование выполняется несколько циклов или раундов подряд. В случае двух ветвей, каждый раунд имеет структуру, показанную на рисунке: Симметричное шифрование (5)

9 Слайд 9 Пример : принят как стандарт в 1977 U.S. Federal Information Processing Standards, обновлен в Декабре |K| = 56 бит; |m| = 64 бита. На рисунке изображен i-й раунд шифрования, справа – преобразование m, слева – вычисление подключа. Симметричное шифрование (6) Всего выполняется 16 раундов. Дешифрование производится аналогично.

10 Слайд 10 Характеристики используемых алгоритмов В настоящее время длина ключа «обычного» DES считается недостаточной даже для «лобовой атаки» основанной на переборе всех (2 56 ) ключей (для известной пары {c=E K (m),m}). Поэтому был предложен усиленный «тройной» DES: K={K1,K2}, |K1|=|K2|=56, |K|=112 бит. E 3DES,K (m) = E DES,K1 [ D DES,K2 [ E DES,K1 (m) ] ] Симметричное шифрование (7)

11 Слайд 11 Основные понятия: {KO,KR} – пара ключей (открытый и секретный); M – исходное (нешифрованное) сообщение (число); Е KO (.) – алгоритм шифрования; D KR (.) – алгоритм дешифрования; Несимметричное шифрование (1) А >???> > B KO B {KO B, KR B } M C=E KO B (M)-> C >-->P= D KR B (C) C = Е KO (M) – зашифрованное сообщение (по открытому каналу). Алгоритмы Е KO (.), D KR (.) и открытый ключ KO – известны (!). Секретом является только закрытый ключ KR ! Дополнительным (к тем, что типичны для симметричных алг.) требованием является трудность определения KR по известному KO. Основная проблема симметричных алгоритмов – передача секретного ключа по открытым каналам связи.

12 Слайд 12 Практическое применение: 1.цифровая подпись (в дальнейшем). 2.передача секретного ключа СА, вместо шифрования всего текста (использование в комбинации с СА, например, в системе PGP) Несимметричное шифрование (2) А >???> > B KO B {KO B, KR B } P - текст K – выбранный случайным образом («сессионный») ключ СА C=E СА,K (P) - (зашифрованный текст) Z=E НА,KO B (K) > {C,Z}> > K=D НА,KR B (Z) (зашифрованный ключ СА) P=D СА,K (С) Характеристика несимметричных алгоритмов (НА )по сравнению с симметричными (СА): Относительно большая вычислительная трудоемкость НА Большая длина ключа НА (~ в 10 раз)

13 Слайд 13 Несимметричное шифрование (3) Математический аппарат известных алгоритмов НА: Теория чисел разложение на простые множители, т. Эйлера и Ферма (RSA) целочисленные логарифмы (схемы Эль-Гамаля, Дифи-Хеллмана) Теория эллиптических кривых (пока еще не получили широкого применения). Осн. понятия (ниже, все леммы и теоремы, являются минимально необходимыми для обоснования алгоритма RSA) В дальнейшем, все числа (a, b, x, y, d, n, k,...) - целые, из множества Z = {..., -3, -2, -1, 0, 1, 2, 3,...}. Обозначения для «делимости» и «делителей»: d|x {x=k d, для некоторого целого k}, т.е. d «делит» x «без остатка»; для любого x, x|0 и 1|x, т.е. 0 «делится» на любое x, 1 - делит любое число. НОД(a,b) = max{d > 0: d|a и d|b} (наибольший общий делитель a и b). Лемма (НОД). Для любых a и b, НОД(a,b) = min {s: s= x a + y b, s 0} число p, p 2 – называется простым, если для всех q, 1 q p-1, НОД(q,p)=1 Теорема (Факторизация). Любое целое число n, может быть единственным образом разложено на простые множители, т.е. представлено в виде n = (p 1 ) k 1 (p 2 ) k 2... (p r ) k r, где все p k – простые числа, все k r - целые

14 Слайд 14 Несимметричное шифрование (4) Классы вычетов по модулю n: Z n = {0, 1, 2,..., a,..., n-1} - классы эквивалентности, x n y n | (x - y) Арифм. операции «по модулю n»: [x] n = x (mod n) = r, где r - остаток от деления x/n, x = k n + r, r [0, n - 1] ; x + n y = (x+y) (mod n); x n y = (x y) (mod n). Все эти операции коммутативны и ассоциативны «как обычные»: x+ n y n [x] n +[y] n ; x n y n [x] n [y] n ; (x+y) z n [x z] n + [y z] n ;... Хотя операция деления – особенная: 6 36(mod10), но 1 6(mod10). Лемма (об «обратных по модулю»). Условие НОД(k,n) = 1, достаточно для того, чтобы для любых a и b, k a=k b(mod n) a=b(mod n). Малая теорема Ферма (1640 год). Пусть p – простое число и a < p. Тогда a p-1 =1(mod n) (в частности, a p =a(mod n)). Определение (функция Эйлера). Пусть n > 1. Функцией Эйлера от n называют величину (n) = |{r: 1 r

15 Слайд 15 Несимметричное шифрование (5) Значение функции Эйлера (n) зависит от результатов разложения аргумента на простые множители. Примеры:простые множители для простого p, (p) = p-1; для n=pq, где p и q – простые, (n) = (p-1)(q-1); если известна факторизация числа n, n=(p 1 ) k 1 (p 2 ) k 2...(p r ) k r, тофакторизация (n)=(p 1 -1)(p 1 ) k 1 -1 (p 2 -1)(p 2 ) k (p r -1)(p r ) k r -1 Малая т. Ферма Малая т. Ферма имеет важное обобщение, непосредственно используемое одним из алгоритмов несимметричного шифрования RSA. Теорема Эйлера (~1770 год). Возьмем произвольное n. Тогда для любого a, такого что НОД(a,n)=1, верно a (n) n 1. Следствие 1. Для любого a, НОД(a,n)=1, и любого k, верно a k (n)+1 n a Следствие 2. Если N = p q, где p и q – простые, то для любого m < N, и любого k, верно m k (n)+1 N m. (Заметьте, что, по сравнению со Следствием 1, здесь нет предположения НОД(m,N)=1)

16 Слайд 16 Несимметричное шифрование (5). RSA В 1978 году Роналд Л. Ривест, Ади Шамир и Леонард Адлеман бросили вызов специалистам по криптографии. Они пообещали 100$ тому, кто восстановит текст, зашифрованный в виде числа (129 цифр, 426 бит) «C= » При этом они опубликовали алгоритм шифрования: »Исходный английский текст был преобразован в число по простому правилу: все символы текста были заменены двухцифровыми комбинациями по простому правилу (A = 01, B = 02, С=03,... Z = 26, и символ «пробел»=00). Получившаяся цепочка цифр использовалась как десятичная запись неизвестного числа M (сообщалось, что M содержит не более 129 цифр). »Было взято большое число (129 цифр, 426 бит) N= , полученное в результате произведения двух простых чисел p и q (N = p q). »Было взято число e=9007, такое что НОД(e, (N))=1, (N)=(p-1)(q-1). »Наконец, зашифрованное сообщение было вычислено по формуле С= M e (mod N). Авторы сообщили значения {N,e}, но сохранили в секрете простые множители p и q. Более того, они объяснили как можно найти неизвестное M, для чего нужно определить число d < N, для которого d e=1(mod (N) ), и получить M по формуле С d (mod N). Это следует непосредственно из Следствия 2, т.к. d e=k (N)+1, С d n M e d n MСледствия 2

17 Слайд 17 Несимметричное шифрование (6). RSA Это было сделано только через 17 лет, в 1994 году. Для того чтобы расшифровать фразу the magic words are squeamish ossifrage, команде из 600 человек потребовалось 220 дней работы и 1600 компьютеров, связанных через Интернет ( В общей сложности это потребовало 5000 MIPS лет (1 MIPS в год – означает число операций, выполняемых с интенсивностью 1 млн. операций в секунду за год). «Единственная» сложность данной задачи состояла в том, чтобы найти разложение 426 битного числа N на простые множители. После того как эти два (всего !) числа были найдены (ими оказались 212- и 215-битные числа) p= , q= , вычисление чисел (N), d («псевдообратного» к e по модулю (N) ) и восстановление M не составляет труда (см. подробности в Приложении). С того времени лаборатория RSA Security ( регулярно предлагает всем желающим «взломать» алгоритм RSA для ключей различной длины. Последний из взломанных шифров соответствовал 640-битному N, за что команда криптоаналитиков в ноябре 2005получила $ Желающим взломать 1024-битный ключ предлагается $100000, а 2048-битный - $ (см.

18 Слайд 18 Несимметричное шифрование (7). RSA Формальное описание алгоритма RSA Генерация пары ключей, для чего выбираются два «секретных» больших простых числа p, q и вычисляются N=pq и (N)=(p-1)(q-1); в результате эффективного перебора находится число e, взаимно простое с (N), НОД(e, (N))=1; находится число d < N, «псевдообратное» к e по модулю (N), т.е. d e=1(mod (N) ) (применяется расширенный алгоритм Евклида, см. далее) Составляется пара ключей [KO, KR], где открытый ключ KO есть пара чисел {e,N}, а закрытый KR – пара чисел {d,N}. Процедура шифрования исходного сообщения, представленного в виде целого числа M

19 Слайд 19 Несимметричное шифрование (8). Схема Диффи-Хеллмана. Именно эти двое авторов в 1977 году сформулировали саму идею несимметричного шифрования, а также предложили первый НА, предназначенный для «безопасного» обмена общим секретным ключом в результате обмена «открытыми» сообщениями. Предложенная ими процедура использует еще одно понятие из теории чисел: дискретный логарифм. Определение. Первообразным (примитивным) корнем числа n (не обязательно простого) называется такое число 1 является вычислительно ТРУДНОЙ.

20 Слайд 20 Именно эти двое авторов в 1977 году сформулировали саму идею несимметричного шифрования, а также предложили первый НА, предназначенный для «безопасного» обмена общим секретным ключом в результате обмена «открытыми» сообщениями по следующему протоколу: 1. Стороны A и B обменивается частью открытого ключа, используемой для всех сессий протокола, – парой {N, }, где - примитивный корень N. 2. Каждая из сторон A и В выбирает свой «секретный» ключ для данной «сессии» обмена, произвольное число (пусть это будут 1

21 Слайд 21 Корректность указанного протокола основана на взаимной однозначности отображения x (mod N): Z N Z N, благодаря определению примитивного корня. Надежность схемы основана на отсутствии эффективной процедуры вычисления дискретных логарифмов, т.к. определение секретного ключа K требует определения неизвестных (секретных) x A или x B, являющимися дискретными логарифмами от известных y A и y B ; x A =ind,N (y A ), x B =ind,N (y B ). Непосредственное использование схемы Диффи-Хеллмана в качестве алгоритма несимметричного шифрования (см. Слайд) невозможно, поэтому их идея использовать дискретный логарифм была доведена до практического использования в алгоритме цифровой подписи Эль-Гамаля (Taher Elgamal) в 1984 году ( ). В 1993 году немного модифицированный алгоритм Эль-Гамаля был принят правительством США в качестве национального стандарта DSA (Digital Signature Algorithm), см. Слайд Российские стандарты ЦП ГОСТ (и более поздний ГОСТ ), также соответствуют схеме Эль-Гамаля. Несимметричное шифрование (8). Схема Диффи-Хеллмана.

22 Слайд 22 Назначение хэш-функций (ХФ) состоит в том, чтобы отслеживать случайные или преднамеренные изменения содержания сообщений, пересылаемых по открытым сетям (аутентификация сообщений). Формально, хэш-функция H(M), определяется как отображение множества битовых последовательностей M («сообщений») большой длины (|M|

23 Слайд 23 На первый взгляд, 3-е требование кажется естественным следствием условия l1 есть k -1. Таким образом, «в среднем» необходимо перебрать 2 l-1 сообщений Y. С этой точки зрения ХФ, с длиной хэша в 64 бита кажется уже весьма надежной. ХФ, удовлетворяющие еще и требованию 5 принято называть сильными. Хэш-функции (2). Обсуждение требований.

24 Слайд 24 Однако условие 5 оказывается гораздо более жестким. Здесь обычно принято вспоминать о «парадоксе одинаковых дней рождения», который можно сформулировать в форме следующего утверждения Утверждение. Если через P(k,n) обозначить значение вероятности того, что случайная выборка k элементов из n-элементного множества НЕ содержит пары совпадающих элементов, то выполнена оценка Это неравенство легко следует из тождества и хорошо известного неравенства 1-x exp(-x), верного для всех x 0. Из данного утверждения следует, что если k (k-1) 2 ln(2) n, то P(k,n)

25 Слайд 25 В таблице сведены основные параметры трех популярных алгоритмов ХФ (все – сильные). Три из указанных алгоритмов подробно описаны в рекомендованной литературе и в сети (для целей курса достаточно Wikipedia) MD5 [ SHA [ en.wikipedia.org/wiki/SHA_hash_functions] RIPFMD [ (интересно, что число сильных алгоритмов ХФ заметно меньше числа известных стойких алгоритмов симметричного шифрования; фактически три ХФ против десятка СА). Хэш-функции (4). Известные алгоритмы ХФ.

26 Слайд 26 Фактически, технологии ЦП решают проблему аутентификации сообщений, пересылаемых по открытым сетям, в результате координированного использования одного из несимметричных алгоритмов (НА) и какого-либо алгоритма вычисления ХФ. (Вообще говоря, НА можно использовать для подписывания сообщений и без ХФ, однако ее использование значительно повышает производительность процедур создания и верификации ЦП). Рассмотрим ситуацию когда сторона A желает отправить стороне B сообщения M, заверенные своей (A) подписью. Общая схема ЦП: Шаг 0. (предваряет отправку сообщений) А создает пару ключей [KO A, KR A ] и обеспечивает надежную (защищенную от подмены) доставку открытого ключа KO A стороне B, кроме того, А сообщает B какая хэш-функция H будет использоваться. Следующие шаги соответствуют отправке сообщений. Шаг 1. A вычисляет s KR A (M)=E KR A (H(M)). Зашифрованное закрытым ключом отправителя значение H(M) и есть ЦП сообщения M. Шаг 2. A отправляет B сообщение и подпись {M,s(M)}. Шаг 3. (верификация) сторона B, получив структуру {M,s} проверяет подлинность сообщения. Для этого, B вычисляет h=H(M), и сравнивает значения h и D KO A (s). Равенство, с точностью до надежности используемых НА и ХФ, считается доказательством подлинности M, т.е. равенства M=M. Цифровая подпись (1). Общая схема.

27 Слайд 27 Заметьте, что в отличие от схемы использования НА для шифрования отправляемых сообщений, где А был нужен открытый ключ принимающей стороны B, схема ЦП требует закрытого ключа A для шифрования значения ХФ. Это накладывает дополнительные требования на используемый алгоритм НА. Необходимо, чтобы процедуры E K (.) и D K (.) можно было бы применять с обоими ключами из пары {KO,KR}. Алгоритм RSA обладает этим свойством, поэтому именно он соответсвует, т.н. детерминированной ЦП, когда для одного и того сообщения будет создана одна и та же подпись. Соответствующий алгоритм ЦП зафиксирован стандартом PKCS (Public-Key Cryptography Standards) #1 (стандарты PKCS являются общедоступным продуктом RSA Laboratory, использования НА для шифрования отправляемых сообщений Семейство алгоритмов ЦП Эль-Гамаля, не пригодных для обмена зашифрованными сообщениями, применяются только для создания ЦП в результате шифрования хэша сообщения закрытым ключом отправляющей стороны. Такие алгоритмы могут при создании подписи (для повышения надежности) использовать случайно выбираемый параметр. В этом случае говорят о недерминированной ЦП, когда одно и то же сообщение может снабжаться различными подписями. Общеизвестным примером недетерминированного алгоритма является DSA (Digital Signature Algorithm), см. DSA определяется стандартом FIPS (2000 год), Цифровая подпись (2).

28 Слайд 28 Надежность схем шифрования сообщений и ЦП основаны на предположении, что имеется надежная инфраструктура распространения открытых ключей. Основным здесь является требование, что сторона X, получившая открытый ключ другой стороны Y, действительно должна быть уверена, что этот публичный ключ не подменен, т.е. действительно принадлежит X. Иначе, либо зашифрованные данные могут стать известными третьей стороне (когда НА используется для шифрования), либо ЦП может быть скомпрометирована (т.е., сторона отправившая сообщение со своей подписью, может затем отказаться от содержания послания, сославшись на то, что ее подпись была подделана. Цифровые сертификаты (1). Проблема компрометации KO. На рисунке изображен пример, когда сторона Z, «перехватила» и подменила открытый ключ KO Y, чтобы затем читать/изменять сообщения, направляемые от Y к X.

29 Слайд 29 Технология цифровых сертификатов (ЦС) призвана решить проблему надежного (с точки зрения защиты от компрометации) распространения публичных ключей. Концепция ЦС заключается в том, что публичный ключ доставляется заинтересованной стороне, будучи заверенным ЦП, созданной при участии выделенной третьей стороны, чей публичный ключ защищен от компрометации. Этого выделенного участника технологии ЦС принято называть Центром Авторизации (ЦА или СА, Certif. Authority). Ниже изображена схема отправки KO X стороне Y в составе сертификата, заверенного подписью CA. CA {KO CA, KR CA } сторона X сторона Y запрос на выдачу ЦС: отправка сертификата X, [KO X, {name X, mail X,...}] подписанного CA CA =[KO X, {name X, mail X,...}, s KR CA ({KO X, прочее содержимое })] Y, KO CA X, {KO X,KR X } (Y хранит ключ СА) 3. отправка KO X в составе сертификата CA Y может проверить подлинность сертификата CA, располагая открытым ключом CA. Цифровые сертификаты (2). Общая схема.

30 Слайд 30 Принято разделять собственно стандарт создания и формат ЦС (X.509, RFC 2459) и средства их хранения и распространения (т.н. PKI - Public Key Infrastructure). См., например, где приводится подборка ссылок на соотв. стандарты, с комментариями. Цифровые сертификаты (3). стандарт X.509 ЦС в формате X.509 содержит: »открытый ключ KOX; »данные стороны X, названия и смысл атрибутов С, O, OU, CN,... определяются стандартом X.500; »данные Центра Авторизации выдавшей сертификат; »срок действия; »уникальный номер сертификата; »подпись, заверяющая содержимое KO X KO X Subject: Subject:C=, O=, OU=, CN= Issuer: C=CH, O=CERN, OU=GRID, CN=CERN CA Expiration date: Aug 26 08:08: GMT Serial number: 625 (0x271) ЦП на основе закрытого ключа CA Осн. элементы в составе ЦС X.509

31 Слайд 31 Спецификации PKI основаны на двух группах стандартов: X.509 ITU-T (Международный комитет по телекоммуникациям) и PKCS (лаборатория RSA). Они определяют политики выпуска цифровых сертификатов, выдача их и аннулирование, хранение информации, необходимой для последующей проверки правильности сертификатов. Когда говорят о PKI, обычно имеют ввиду программные средства (приложения), поддерживающие PKI: WEB-браузеры и серверы, электронная почта, системы платежей, и т.п.PKCS В рамках курса, достаточно знать, что реализация PKI встроена в многие WEB- приложения, и представляет собой средства управления (импорт/экспорт, просмотр), хранения и доступа к другим хранилищам сертификатов. См. ниже примеры PKI GUI в браузере Firefox и популярном приложении PGP - системе «персональной безопасности» ( Цифровые сертификаты (4). Стандарты PKI

32 Слайд 32 На общей схеме обе стороны X и Y используют один центр авторизации, однако спецификация X.509 допускает появление иерархии центров сертификации (см. рисунок), которые могут удостоверять ключи друг-друга (двухсторонние стрелки), и, - выдавать ЦС «оконечным» сторонам сетевого взаимодействия (обычные стрелки). Эта иерархия необходима для обслуживания большого количества ЦС конечных сторон. Процедура проверки подлинности ЦС в условиях иерархии ЦА использует понятия цепь сертификатов. На рис. зеленой линией обозначена цепь сертификатов, соответствующая ЦС компоненты g. В X.509 для цепи предусмотрено обозначение {A, B, F, H }, где запись X, означает сертификат X, выданный X. Пусть, сторона u, получила от g сертификат H. Что нужно u чтобы проверить его подлинность? Ответ: доступ к цепочке и открытый ключ первого ЦА в цепочке (в форме корневого «самоподписанного» сертификата A ). Располагая KO A, u может последовательно проверить подлинность сертификата A, а значит КО B. Далее,общей схеме Цифровые сертификаты (5). Иерархия центров авторизации зная КО B, u может убедиться в подлинности КО F, затем КО H и далее по цепочке. Сертификаты CA, которым доверяет данная сторона (trusted), хранятся ею «локально» в т.н. хранилище надежных ключей (защищенными паролем и в зашифрованном виде!). корневой СА

33 Слайд 33 Доступ к цепочкам сертификатов и к хранилищу надежных сертификатов надежных ЦА обеспечивается средствами PKI, встроенными в соответствующее приложение. Сертификаты основных, общеизвестных центров авторизации ( thawte.com/, verisign.com/,...), обычно встроены в дистрибутивы Web- приложений. Например, справа приводится пример списка сертификатов из хранилища браузера Firefox. При этом, среди них могут быть сертификаты, подписанные другими CA, т.е. не корневые. thawte.com/verisign.com/ Цифровые сертификаты (6). «Надежные» сертификаты

34 Слайд 34 Перечисляются некоторые из популярных программных систем, реализующих технологии защиты данных. OpenSSL, (самый распространенный из семейства open source, язык реализации C++, Windows, *nix). Java SDK Cryptography Extension (JCE), (имеет некоторые ограничения в реализации PKI, например, может создавать толь самоподписанные ЦС). IAIK JCE, Коммерческая реализация Java Cryptography Extension (начиная с ~$500, PGP (Pretty Good Privacy), Создана Филиппом Циммерманом (Mass. Inst. Tech) в начале 90-х и с тех пор постоянно развиваемая персональная криптосистема, предназначенная в первую очередь для защиты почты. Реализует некоторые важные функции PKI. Bouncy Castle, Языки Java, C# (пока – бета-версии). Программные средства

35 Слайд 35 Рекомендуемые источники [1.] В. Столлинг. Криптография и защита сетей: принципы и практика. – М.: Изд. дом "Вильямс", – 672 с. (Симметричное и несимметричное шифрование, хэш-функции, цифровая подпись и цифровые сертификаты, протоколы SSL,...) [2.] Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы: построение и анализ, 2-е издание. - М.: Изд. дом "Вильямс", – 1296 с. (Алгоритм RSA и связанные с этим элементы теории чисел, а также эффективные теоретико-числовые вычислительные процедуры) [3.] Сайт Раздел «Безопасность информационных технологий» (DES, функции хэширования, основы RSA и цифровой подписи) [4.]

36 Слайд 36 Приложение. Алгоритмы модульной арифметики Арифметика вычислений «по модулю» является основным инструментом несимметричных алгоритмов шифрования. Далее приводятся примеры реализаций двух эффективных (для БОЛЬШИХ чисел) алгоритмов, используемых на практике: «Расширенный алгоритм Евклида» для поиска наибольшего общего делителя НОД(a,b) (с вычислением псевдообратного), и «Вычисления степеней повторным возведением в квадрат», т.е. x y (mod N). Оба алгоритма эффективны в том смысле, что число арифметических операций в них, соответственно, пропорционально log 2 (max{a,b}) для алг. Евклида, и log 2 (y) - для возведения в степень, причем в последнем случае значения всех промежуточных результатов вычислений не превосходят N. Заметим, что для целого числа x значение log 2 (x) с точностью до 1 есть число символов «0» или «1» в двоичной записи x. Оба алгоритма используются в системах шифрования RSA и ЦП Эль-Гамаля. Возведение в степень - в схеме Диффи-Хеллмана.

37 Слайд 37 Приложение. Расширенный алгоритм Евклида Напомним, что НОД(a,b) = min {s: s=x a + y b, s 0} Расширенный алгоритм Евклида находит указанное выше значение s, а также соответствующие множители x и y (возможно, что одно из них будет отрицательным). Если a>b и НОД(a,b)=s=1, то значение c=y(mod a) будет псевдообратным к b по модулю a. Действительно, в этом случае имеем (ниже k может быть отрицательным, если y оказалось меньше нуля) 1=x a + y b, y=c+k a, т.е. с b = 1 - (k b+x) a 1(mod a). Идея алгоритма основана на легко проверяемом тождестве НОД(a,b)=НОД( b, a(mod b) ). (если b=0, то НОД(a,b)=a) Таким образом рекурсивный алгоритм может выглядеть так (ниже использована запись на языке пакета Maxima, maxima.sourceforge.net, «:» - оператор «присваивания значения»)maxima.sourceforge.net /* Extended_Euclid */ extgcd(a,b):=block([d,x,y], if (b=0) then (return([a,1,0])), dxy: extgcd(b,mod(a,b)), /* mod(x,y) - остаток от деления x/y, т.е. x mod(y) */ f:floor(a/b), /* целая часть от деления a/b */ d:dxy[1],x:dxy[3],y:dxy[2]-f*d[3], return([d,x,y]) );

38 Слайд 38 Приложение. Возведение в степень. Легко было видеть, что операция взятия остатка по модулю от результата возведения больших чисел в большую степень является основной во всех упомянутых ранее алгоритмах несимметричного шифрования. Причем, именно эта операция используется в процедурах шифрования/дешифрования и вычисления ключей. Прямое возведение чисел, запись которых составляет несколько сотен цифр, в такие же степени (чтобы после этого взять остаток), - ни к чему хорошему не приведет и практически - невыполнимо. Эффективный алгоритм вычисления x y (mod N) (см., например, en.wikipedia.org/wiki/Exponentiation_by_squaring) использует тождествоen.wikipedia.org/wiki/Exponentiation_by_squaring x y 1 +y 2 (mod N)=(x y 1 (mod N) x y 2 (mod N))(mod N) и представление показателя степени в виде суммы степеней 2 (что соответствует двоичной записи y). Например, x 13 = x 1101 =x (12^3 + 12^2 + 02^1 + 12^0) =x 8 x 4 x 1 =((x 2 x) 2 ) 2 x - т.е. вместо 13-ти умножений мы получили всего 5 (причем, включая операцию возведения в квадрат). На языке пакета Maxima: /* Modular Exp, biny - список символов двоичной записи y */ expmod(x,biny,N):=block(res:1, len:length(biny), /* число символов в двоичном представлении y*/ for i:1 thru len do ( res:mod(res*res,N), if (biny[i]=1) then (res:mod(res*x,N)) ), return (res) );