Бюллетень
Викторина
Глава
Диплом
Доклад
Методическая разработка Оренбург, 2016 удк 372. 8 преподавание отдельных дисциплин Рецензент
 Скачать 1.11 Mb.
|
Functiom Flag(n: longint): Boolean; var i, k: longint; begin k := Round (sqrt(n)); {максимально возможный делитель} if n = 2 then flag := true else if not odd (n) then flag := false else begin flag := true; for i := 2 to k do if n mod i = 0 then flag := false end; if flag then writeln('Простое число') else writeln('Составное число'); readln; end. 2. Определение функции Эйлера. function f(n : longint) : longint; var res, en, i : longint; begin res := n; n := round(sqrt(n)) + 1; for i := 2 to en do if (n mod i = 0) then begin //если i - делитель while (n mod i = 0) do //пока делится, делим n := n div i; dec(res, res div i); end; if (n > 1) then dec(res, res div i); f := res; end; 3. Определение являются ли два числа взаимно простыми Function Nod(x, y: Longint): longint; {Функция вычисления НОД, чтобы числа были взаимно простыми} Begin Repeat If x > y Then x:=x Mod y Else y := y Mod x; Until (x=0) Or (y=0);{до тех пор, пока одно из чисел не станет равно нулю} Nod := x+y; End; 4. Нахождение остатка от деления произведения двух чисел Function Ostatok (x, y, t: longint): longint; {Вычисление остатка от деления произведения x*y на t} var i, k: longint; begin k := 1; for i := 1 to y do k := (k*x) mod t; Ostatok := k; end; 2. Разработка программы шифрования. Полностью листинг программы можно посмотреть в Приложении 3. Занятие №8. Комбинированные алгоритмы Цели занятия:
Задачи занятия:
Учебные вопросы, рассматриваемые на занятии: 1. Комбинированные алгоритмы Материал для проведения занятия 1. Комбинированные алгоритмы Симметричное и асимметричное шифрование остаются актуальными и криптографически гарантированными методами защиты информации. При передаче и хранении ценной или секретной информации её защищают с помощью криптосистем смешанного типа. С помощью двухключевых асимметричных алгоритмов решается задача распределения ключей для симметричных шифров. Алгоритмы с симметричными ключами имеют очень высокую производительность. Криптография с симметричными ключами очень стойкая, что делает практически невозможным процесс дешифрования без знания ключа. При прочих равных условиях стойкость определяется длиной ключа. Так как для шифрования и дешифрования используется один и тот же ключ, при использовании таких алгоритмов требуются очень надёжные механизмы для распределения ключей. Асимметричное шифрование сложнее. В схеме кодирования с открытым ключом невозможно вычислить процедуру дешифрования, зная процедуру шифрования. Более точно, время работы алгоритма, вычисляющего процедуру расшифровки, настолько велико, что его нельзя выполнить на любых современных компьютерах, равно как и на любых компьютерах будущего. Следует отметить, что алгоритм асимметричного шифрования сильно проигрывает симметричным с точки зрения времени шифрования и расшифровки данных, поэтому многие современные системы шифрования используют комбинацию асимметричной и традиционной симметричной систем шифрования. Шифрование с открытым ключом используется для передачи симметричного ключа, который служит непосредственно для шифрования информации. Всем системам открытого шифрования присущи следующие основные недостатки: ключ должен передаваться по секретному каналу; к службе генерации ключей предъявляются повышенные требования, обусловленные тем, что для n абонентов при схеме взаимодействия «каждый с каждым» требуется n·(n-1)/2 ключей, то есть зависимость числа ключей от числа абонентов является квадратичной. Основным недостатком симметричного шифрования является то, что секретный ключ должен быть известен и отправителю, и получателю. Шифрование с несимметричным ключом является более криптостойким, но более медленным и дорогим по сравнению с шифрованием с симметричным ключом. Двухключевые шифры редко применяются для непосредственного шифрования. Они в основном используются при работе с электронными документами. Рис. 2. Схема шифрования с симметричным и ассиметричным алгоритмом Схема работы комбинированной системы приведена на Рис. 2.. На первом этапе пользователь А шифрует исходный файл с помощью симметричного алгоритма. На втором этапе он получает из открытых источников публичный (открытый) ключ, принадлежащий пользователю В, и с помощью этого ключа зашифровывает симметричный ключ, который использовался на первом этапе. На третьем этапе зашифрованный файл и зашифрованный симметричный ключ передаются пользователю В посредством интернета. После того как пользователь В на четвёртом этапе получил передаваемые ему данные, он на пятом этапе расшифровывает симметричный ключ с помощью своего частного (закрытого) ключа. На последнем, шестом этапе пользователь В, применяя расшифрованный на предыдущем этапе симметричный ключ, расшифровывает посланный ему файл. Когда кто-то получает от вас сообщение, зашифрованное вашим частным ключом, он уверен в аутентичности послания, шифрование эквивалентно поставленной подписи (электронная цифровая подписи). Занятие №9. Электронная цифровая подпись Цели занятия:
Задачи занятия:
Учебные вопросы, рассматриваемые на занятии: 1. Положительные свойства цифровой подписи и реализация ЦП через посредника. 2. Реализация электронной цифровой подписи через асимметричные криптосистему. Материал для проведения занятия 1. Положительные свойства цифровой подписи и реализация ЦП через посредника Рукописные подписи издавна используются как доказательство авторства документа или, по крайней мере, согласия с ним. Какими же свойствами обладает подпись? 1. Достоверность. Она убеждает получателя документа в том, что подписавший сознательно подписал документ. 2. Неподдельность. Она доказывает, что именно подписавший, и никто иной, сознательно подписал документ. 3. Однократность применения. Она не может быть использована повторно. Она является частью документа, жулик не сможет перенести подпись на другой документ. 4. Неизменность. Подписанный документ нельзя изменить. После того, как документ подписан, его невозможно изменить. 5. Необратимость. От неё невозможно отречься. Подпись и документ материальны. Подписавший не сможет впоследствии утверждать, что он не подписывал документ. В действительности, ни одно из этих утверждений не является полностью справедливым. Подписи можно подделать, документы, в некоторых случаях, могут быть изменены после подписания. Однако, мы миримся с этими проблемами из-за того, что мошенничество затруднительно и может быть обнаружено. Хотелось бы реализовать что-нибудь подобное и на компьютерах, но есть ряд проблем. Во-первых, компьютерные файлы скопировать не просто, а очень просто. Даже если подпись человека трудно подделать (например, графическое изображение рукописной подписи), можно легко вырезать правильную подпись из одного документа и вставить в другой. Простое наличие такой подписи ничего не означает. Во-вторых, компьютерные файлы очень легко можно изменить после того, как они подписаны, не оставляя ни малейшего следа изменения. Подпись документа с помощью симметричных криптосистем и посредника Пользователь А хочет подписать цифровое сообщение и отправить его Пользователю В. Он может это сделать с помощью посредника и симметричной криптосистемы. Посредник – третье «лицо», обладающее властью, которому доверяют. Он может связываться со всеми пользователями, желающими подписывать цифровые документы. Он выдаёт секретный ключи пользователям. Эти ключи определяются задолго до начала действия протокола и могут быть использованы многократно для многих подписей. Порядок передачи сообщения выглядит следующим образом:
Откуда Посредник узнает, что сообщение пришло именно от Пользователя А, а не от какого-то самозванца? Он делает этот вывод из шифрования сообщения. Также ли это хорошо, как подпись на бумаге? Посмотрим на требуемые свойства: 1. Эта подпись достоверна. В нашем случае Посредник – залуживает доверия, и Он знает, что сообщение получено от Пользователя А. Подтверждение Посредника служит доказательством для Пользователя В. 2. Эта подпись неподдельна. Только Пользователь А (и Посредник, но ему все верят) знает ключ которым шифрует сообщение Пользователь А, поэтому только Пользователь А мог прислать Посреднику сообщение, зашифрованное этим ключом. Если кто-нибудь попытается выдать се бя за Пользователя А, Посредником это сразу будет обнаружено, и он не заверит подлинность сообщения от Пользователя А. 3. Эту подпись нельзя использовать повторно. Если Пользователь В попытается взять подтверждение Посредника и присоединить его к другому сообщению, Пользователь А начнёт возмущаться. Посредник попросит Пользователя В предъявить его сообщение и шифрованное сообщение Пользователя А. Но так как Пользователь В не обладает ключом Пользователя А, то подлог сообщений будет сразу обнаружен. 4. Подписанный документ нельзя изменить. Если Пользователь попытается, получив документ, изменить его, Посредник обнаружит мошенничество сравнением исходящего сообщения от Пользователя А и нового измененного сообщения от Пользователя В. 5. От подписи невозможно отказаться. Если впоследствии Пользователь А заявит, что он никогда не посылал сообщение, подтверждение Посредника докажет обратное. (Слова и действия Посредника – всегда истина). Эти протоколы работают, но они требуют от Посредника немалых затрат времени. Он должен целыми днями расшифровывать и шифровать сообщения, посредничая между каждой парой людей, которые хотят обмениваться подписанными документами. Он должен хранить сообщения в базе данных (хотя этого можно избежать, посылая получателю копию шифрованного сообщения отправителя). Он будет узким местом любой системы связи, даже если он - просто бесчувственная компьютерная программа. Такого посредника, которому будут доверять все корреспонденты, тяжело найти и тяжело сохранить. Посредник должен быть непогрешим и абсолютно безопасен, иначе ему нельзя будет доверять. Такая схема теоретически может работать, но она недостаточно хороша для практического применения. Подпись документа с помощью криптографии с открытыми ключами Существуют алгоритмы с открытыми ключами, которые можно использовать для цифровых подписей. В некоторых алгоритмах - примером является RSA - для шифрования может быть использован или открытый, или закрытый ключ. Зашифруйте документ своим закрытым ключом, и вы получите надёжную цифровую подпись. В других случаях - примером является DSA - для цифровых подписей исполь зуется отдельный алгоритм, который невозможно использовать для шифрования. Эта идея впервые была изо бретена Диффи и Хеллманом. Основной протокол прост и представлен на Error: Reference source not found: Этот протокол гораздо лучше предыдущего. Посредник становиться не нужным. Такая подпись соответствует всем требованиям: 1. Эта подпись достоверна. Когда Пользователь В расшифровывает сообщение с помощью открытого ключа Пользователя А, он знает что она подписала это сообщение. 2. Эта подпись неподдельна. Только Пользователь А знает свой закрытый ключ. 3. Эту подпись нельзя использовать повторно. Подпись является функцией документа и не может быть перенесена на другой документ. 4. Подписанный документ нельзя изменить. После любого изменения документа подпись не сможет больше подтверждаться открытым ключом Пользователя А. 5. От подписи невозможно отказаться. Пользователю В не требуется помощь Пользователя А при проверке её подписи. Подпись документа и метки времени На самом деле, при определённых условиях Пользователь В сможет смошенничать. Он может повторно использовать документ и подпись совместно. Это не имеет значения, если подписанным документом был контракт или договор, а если цифровая подпись была поставлена под чеком? Можно сохранить копию электронного чека и получать по нему деньги ежедневно! Поэтому в цифровые подписи часто включают метки времени. Дата и время подписания документа добав ляются к документу и подписываются вместе со всем содержанием сообщения. Банк сохраняет эту метку времени в базе данных. Теперь, если мошенник попытается получить наличные по чеку во второй раз, банк проверит метку времени по своей базе данных. Так как банк уже оплатил этот чек с той же меткой времени, то повторных выплат не будет. Занятие №10. Официальные стандарты AES и ГОСТ Цели занятия:
Задачи занятия:
Учебные вопросы, рассматриваемые на занятии: 1. Стандарт шифрования США – AES. 2. ГОСТ 28147-89 Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. 3. Криптостойкость алгоритма ГОСТ 28147-89. Материал для проведения занятия 1. Стандарт шифрования США – AES. Используя суперкомпьютер стоимостью 250 тыс. долл., сотрудники RSA Laboratory «взломали» утвержденный правительством США алгоритм шифрования данных (DES) менее чем за три дня. (Предыдущий рекорд по скорости взлома был установлен с помощью огромной сети, состоящей из десятков тысяч компьютеров, и составил 39 дней). На специально организованной по этому случаю пресс-конференции ученые с беспокойством говорили о том, что злоумышленники вряд ли упустят случай воспользоваться подобной уязвимостью. Эксперимент проходил в рамках исследования DES Challenge II, проводимого RSA Laboratory под руководством общественной организации Electronic Frontier Foundation (EFF), которая занимается проблемами информационной безопасности и личной тайны в Internet. Суперкомпьютер, построенный в RSA Laboratory для расшифровки данных, закодированных методом DES по 56-разрядному ключу, получил название EFF DES Cracker. Как утверждали правительственные чиновники и некоторые специалисты, для взлома кода DES требуется суперкомпьютер стоимостью в несколько миллионов долларов. «Правительству пора признать ненадежность DES и поддержать создание более мощного стандарта шифрования», - сказал президент EFF Барри Штайнхардт [1]. 26 мая 2002 года алгоритм AES был объявлен правительством США новым стандартом шифрования в результате пятилетнего конкурса, в котором принимали участие изначально 15 алгоритмов кандидатов из различных стран мира. Данный алгоритм разработан двумя специалистами по криптографии из Бельгии Йона Дамена и Винсента Рэмена. Он является нетрадиционным блочным шифром, поскольку не использует сеть Фейштеля для криптопреобразований. Алгоритм представляет каждый блок кодируемых данных в виде двумерного массива байт размером 4х4, 4х6 или 4х8 в зависимости от установленной длины блока. Далее на соответствующих этапах преобразования производятся либо над независимыми столбцами, либо над независимыми строками, либо вообще над отдельными байтами в таблице. Все преобразования в шифре имеют строгое математическое обоснование. Сама структура и последовательность операций позволяют выполнять данный алгоритм эффективно как на 8-битных так и на 32-битных процессорах. В структуре алгоритма заложена возможность параллельного исполнения некоторых операций, что на многопроцессорных рабочих станциях может еще поднять скорость шифрования в 4 раза. Алгоритм состоит из некоторого количества раундов (от 10 до 14 – это зависит от размера блока и длины ключа), в которых последовательно выполняются следующие операции: 1. ByteSub – табличная подстановка 8х8 бит 2. ShiftRow – сдвиг строк в двумерном массиве на различные смещения 3. MixColumn – математическое преобразование, перемешивающее данные внутри столбца 4. AddRoundKey – добавление материала ключа операцией XOR В последнем раунде операция перемешивания столбцов отсутствует, что делает всю последовательность операций симметричной. Алгоритм демонстрирует превосходную производительность на всех рассматриваемых в состязании платформах. Для шифра характерны быстрое разворачивание ключа и низкие требования к памяти, так что он также хорошо работает и в аппаратной реализации, и в ограниченных по памяти условиях. Простая конструкция схемы и консервативный выбор операций должны облегчить дальнейший криптоанализ шифра. Кроме того, специалистами отдельно отмечается, что избранные конструкторами операции относительно просто защитить от известных опасных атак на физическую реализацию криптоалгоритма. Ещё одна важная положительная характеристика (хотя и не рассматривавшаяся при выборе финалистов) - в шифре имеется существенный потенциал к распараллеливанию, то есть к получению выгод в производительности благодаря применению компьютерных процессоров, позволяющих одновременно выполнять множество инструкций. 2. ГОСТ 28147-89 Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования ГОСТ 28147-89 — советский и российский стандарт симметричного шифрования, введённый в 1990 году, также является стандартом СНГ. Схема алгоритма представлена на Рис. 2.. Из рисунка видно, что схема алгоритма довольно проста, что упрощает его программную или аппаратную реализацию. Алгоритм шифрует информацию блоками по 64 бита, которые разбиваются на два субблока (N1 и N2) по 32 бита в каждом. Субблок N1 определенным образом обрабатывается, после чего его значение складывается со значением субблока N2 (сложение выполняется по модулю 2), затем суб блоки меняются местами. Такое преобразование выполняется определенное количество раундов: 16 или 32 в зависимости от режима работы алгоритма (описаны далее). В каждом раунде выполняются следующие операции: 1. Наложение ключа. Содержимое субблока N1 складывается по модулю 232 с частью ключа Кх. Ключ шифрования алгоритма ГОСТ 28147-89 имеет размерность 256 би тов, а Кх— это его 32-битная часть, т. е. 256-битный ключ шифрования представляется в виде конкатенации 32-битных подключей (Рис. 2.): К1, К2, К3, К4, К5, К6, К7. Рис. 2. Схема алгоритма ГОСТ 28147-89 В процессе шифрования используется один из этих подключей — в зави симости от номера раунда и режима работы алгоритма. Рис. 2. Ключ шифрования алгоритма ГОСТ 2.Табличная замена. После наложения ключа субблок N1 разбивает ся на 8 частей по 4 бита, значение каждой из которых по отдельности заменяется в соответствии с таблицей замены для данной части суб блока. Табличные замены (Substitution box, S-box) часто используются в современных алгоритмах шифрования, поэтому стоит рассмотреть их подробнее. Табличная замена используется таким образом: на вход подаётся блок данных определённой размерности (в этом случае — 4-битный), числовое представление которого определяет номер выходного значения. Напри мер, имеем S-box следующего вида: 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1. Пусть на вход пришёл 4-битный блок «0100», т. е. значение 4. Согласно таблице, выходное значение будет равно 15, т.е. «1111» (0 заменяется на 4, 1 — на 11, значение 2 не изменяется и т. д.). Как видно, схема алгоритма весьма проста, что означает, что наибольшая нагрузка по шифрованию данных ложится на таблицы замен. К сожале нию, алгоритм обладает тем свойством, что существуют «слабые» табли цы замен, при использовании которых алгоритм может быть раскрыт криптоаналитическими методами. К числу слабых относится, например, таблица, в которой выход равен входу: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15. 3.Побитовый циклический сдвиг влево на 11 битов. 3. Криптостойкость алгоритма ГОСТ 28147-89 В 1994 г. описание алгоритма ГОСТ 28147-89 было переведено на англий ский язык и опубликовано; именно после этого стали появляться ре зультаты его анализа, выполненного зарубежными специалистами; однако в течение значительного времени не было найдено каких-либо атак, прибли жающихся к практически осуществимым. Высокая стойкость алгоритма ГОСТ 28147-89 дости гается за счет следующих факторов: большой длины ключа — 256 битов; вместе с секретной синхропосылкой эффективная длина ключа увеличивается до 320 битов; 32 раундов преобразований; уже после 8 раундов достигается полный эф фект рассеивания входных данных: изменение одного бита блока откры того текста повлияет на все биты блока шифртекста, и наоборот, т. е. су ществует многократный запас стойкости [10]. Занятие №11. Элементы криптоанализа Цели занятия:
Задачи занятия:
Учебные вопросы, рассматриваемые на занятии: 1. Теория криптоанализа. 2. Пример криптоанализа алгоритма Цезаря. 3. Другие способы возможного криптоанализа. Материал для проведения занятия 1. Теория криптоанализа Смысл криптографии - в сохранении открытого текста (или ключа, или и того, и другого) в тайне от злоумышленников (также называемых взломщиками, соперниками, врагами, перехватчиками). Предполагается, что злоумышленники полностью контролируют линии связи между отправителем и получателем. Криптоанализ - это наука получения открытого текста, не имея ключа . Успешно проведенный криптоанализ может раскрыть открытый текст или ключ. Он также может обнаружить слабые места в криптосистемах, что в конце концов приведет к предыдущему результату. (Раскрытие ключа не криптологическими способами называется компрометацией.) Попытка криптоанализа называется вскрытием. Основное предположение криптоанализа, впервые сфор мулированное в девятнадцатом веке Датчманом А. Керкхофсом, состоит в том, что безопасность полностью определяется ключом. Керкхофс предполагает, что у криптоаналитика есть пол ное описание алгоритма и его реализации. (Конечно же, у ЦРУ не в обычае сообщать Моссад о своих криптографических алгоритмах, но Моссад возможно все равно добудет их.) Хотя в реальном мире криптоаналитики не всегда обладают подробной информацией, такое предположение является хорошей рабочей гипотезой. Если противник не сможет взломать алгоритм, даже зная, как он работает, то тем более враг не сможет вскрыть алгоритм без этого знания. С формальной точки зрения, укрепление любого звена кроме самого слабого — пустая трата времени. На практике же все обстоит далеко не так про сто. Злоумышленник может не знать, какое звено является самым слабым, и нападет на более сильное звено. Самое слабое звено может различаться для разных типов злоумышленников. Прочность любого звена зависит от навыков злоумышленника и имеющихся у него средств. Поэтому самое слабое звено во многом определяется той или иной ситуацией. Необходимо укрепить любое звено, которое в определенной ситуации может оказаться самым слабым. [15] Существует четыре основных типа криптоаналитического вскрытия. Для каждого из них, конечно, предпо лагается, что криптоаналитик обладает всей полнотой знания об используемом алгоритме шифрования: 1. Вскрытие с использованием только шифротекста. У криптоаналитика есть шифротексты нескольких сообщений, зашифрованных одним и тем же алгоритмом шифрования. Задача криптоаналитика состоит в раскрытии открытого текста как можно большего числа сообщений или, что лучше, получении ключа (ключей), использованного для шифрования сообщений, для дешифрирования других сообщений, зашифрованных теми же ключами. 2. Вскрытие с использованием открытого текста. У криптоаналитика есть доступ не только к шифротекстам нескольких сообщений, но и к открытому тексту этих сообщений. Его задача состоит в полу чении ключа (или ключей), использованного для шифрования сообщений, для дешифрирования других сообщений, зашифрованных тем же ключом (ключами). 3. Вскрытие с использованием выбранного открытого текста. У криптоаналитика не только есть доступ к шифротекстам и открытым текстам нескольких сообщений, но и возможность выбирать о т-крытый текст для шифрования. Это предоставляет больше вариантов, чем вскрытие с использованием открытого текста, так как криптоаналитик может выбирать шифруемые блоки открытого текста, что может дать больше информации о ключе. Его задача состоит в получении ключа (или ключей), использованного для шифрования сообщений, или алгоритма, позволяющего дешифрировать новые с о-общения, зашифрованные тем же ключом (или ключами) . 4. Адаптивное вскрытие с использованием открытого текста Это частный случай вскрытия с ис пользованием выбранного открытого текста. Криптоаналитик не только может выбирать шифруемый текст, но также может строить свой последующий выбор на базе полученных результатов шифрования. При вскрытии с использованием выбранного открытого текста криптоаналитик мог вы брать для шифрования только один большой блок открытого текста, при адаптивном вскрытии с и с-пользованием выбранного открытого текста он может выбрать меньший блок открытого текста, затем выбрать следующий блок, используя результаты первого выбора и так далее. Существует по крайней мере ещё три типа криптоаналитической вскрытия. 5. Вскрытие с использованием выбранного шифротекста Криптоаналитик может выбрать различ ные шифротексты для дешифрирования и имеет доступ к дешифрированным открытым текстам. На пример, у криптоаналитика есть доступ к «черному ящику», который выполняет автоматическое д е-шифрирование. Его задача состоит в получении ключа. Такой тип вскрытия обычно применим к алгоритмам с открытым ключом. Вскрытие с использование выбранного шифротекста иногда также эффективно против симметричных алгоритмов. (Иногда вскрытие с использованием выбранного открытого текста и вскрытие с использованием выбранного шифротекста вместе называют вскрытием с использованием выбранного текста.) 6. Вскрытие с использованием выбранного ключа. Такой тип вскрытия означает не то, что криптоаналитик может выбирать ключ, а что у него есть некоторая информация о связи между различными ключами. 7. Бандитский криптоанализ. Криптоаналитик угрожает, шантажирует или пытает кого-нибудь, пока не получит ключ. Взяточничество иногда называется вскрытием с покупкой ключа. Это очень мощные способы вскрытия, часто являющиеся наилучшим путем взломать алгоритм. Вскрытия с известным открытым текстом и с использованием выбранного открытого текста встречаются чаще, чем можно подумать. Не является невозможным для криптоаналитика добыть открытый текст шифрованного сообщения или подкупить кого-нибудь, кто зашифрует выбранное сообщение. Может и не потребо ваться никого подкупать - передав письмо послу, вы, возможно, обнаружите, что письмо будет зашифровано и отправлено в его страну для изучения. Многие сообщения имеют стандартные начало и окончание, что может быть известно криптоаналитику. Особенно уязвим шифрованный исходный код из-за частого использования ключевых слов: #define, struct, else, return. Те же проблемы и у шифрованного исполнимого кода: функции, циклические структуры и так далее. Вскрытия с известным открытым текстом (и вскрытия с выбранным шифротекстом) успешно использовались в борьбе с немцами и японцами в ходе Второй мировой войны. И не забывайте о предположении Керкхофса: если мощь вашей новой криптосистемы опирается на то, что взломщик не знает, как работает алгоритм, вы пропали. Если вы считаете, что хранение принципа работы ал горитма в секрете лучше защитит вашу криптосистему, чем предложение академическому сообществу проанализировать алгоритм, вы ошибаетесь. А если вы думаете, что кто-то не сможет дезассемблировать ваш исходный код и восстановить ваш алгоритм, вы наивны. В 1994 году такое произошло с алгоритмом RC4. Нашими лучшими алгоритмами являются те, которые были разработаны открыто, годами взламывались лучшими криптографами мира и все еще несокрушимы. (Агентство Национальной Безопасности хранит свои алгоритмы в секрете, но у них работают лучшие криптографы мира, а у вас - нет. Кроме того, они обсуждают свои алгоритмы друг с другом, полагаясь на способность товарища обнаружить все слабости в своей работе.) У криптоаналитиков не всегда есть доступ к алгоритмам (например, вскрытие в ходе Второй мировой войны Соединенными Штатами японского дипломатического кода PURPLE), но часто они его получают. Если алгоритм используется в коммерческой программе безопасности, то это просто вопрос времени и денег, удастся ли дизассемблировать программу и раскрыть алгоритм. Если же алгоритм используется в военной системе связи, то это просто вопрос времени и денег купить (или украсть) аппаратуру и реконструировать алгоритм. Те, кто стремится получить нераскрываемый шифр, считая этот шифр таковым только потому, что они сами не смогли его взломать, либо гении, либо дураки. К несчастью, последних в мире достаточно много. Остере гайтесь людей, расхваливающих надежность своих алгоритмов, но отказывающихся их опубликовать. Доверять таким алгоритмам нельзя. Хорошие криптографы опираются на мнение других, отделяя хорошие алгоритмы от плохих [17]. 2. Пример криптоанализа алгоритма Цезаря Обратимся теперь к анализу действий противника, пытающего ся расшифровать сообщение и узнать секретный ключ, иными слова ми, вскрыть, или взломать шифр. Каждая попытка вскрытия шифра называется атакой на шифр (или на криптосистему). В криптогра фии принято считать, что противник может знать использованный алгоритм шифрования, характер передаваемых сообщений и пере хваченный шифротекст, но не знает секретный ключ. Это называется «правилом Керкгоффса», в честь учёного, впервые сформу лировавшего основные требования к шифрам. Иногда это правило кажется «перестраховкой», но такая «перестра ховка» отнюдь не лишняя, если, скажем, передается распоряжение о переводе миллиона долларов с одного счета на другой. В нашем примере: Пользователь С знает, что шифр был построен в соответ ствии с (2.1), что исходное сообщение было на русском языке и что был передан шифротекст ТИУИПИРГ, но ключ С не известен. Наиболее очевидная попытка расшифровки — последователь ный перебор всех возможных ключей (это так называемый метод «грубой силы» (brute-force attack)). Итак, Пользователь С перебирает последова тельно все возможные ключи к = 1, 2, ..., подставляя их в алгоритм дешифрования и оценивая получающиеся результаты. Попробуем и мы использовать этот метод. Результаты дешифрования по (2.2) при различных ключах и шифротексте ТИУИПИРГ сведены в Таблица 2.. В большинстве случаев нам достаточно было расшифровать две-три буквы, чтобы отвергнуть соответствующий ключ (из-за отсутствия слова в русском языке, начинающегося с такого фрагмента). Таблица 2. Расшифровка слова ТИУИПИРГ путем перебора ключей
Из Таблица 2. мы видим, что был использован ключ к = 3 и зашифровано сообщение ПЕРЕМЕНА. Причем для того, чтобы про верить остальные возможные значения ключа, нам не требовалось дешифровать все восемь букв, а в большинстве случаев после ана лиза двух-трех букв ключ отвергался (только при к = 8 надо было дешифровать пять букв, зато при к = 22,23,24 хватало и одной, так как в русском языке нет слов, начинающихся с Ь, Ъ, Ы). Из этого примера мы видим, что рассмотренный шифр совер шенно нестоек, для его вскрытия достаточно проанализировать нес колько первых букв сообщения и после этого ключ к однозначно определяется (и, следовательно, однозначно дешифруется все сооб щение). В чем же причины нестойкости рассмотренного шифра и как можно было бы увеличить его стойкость? Рассмотрим еще один при мер. Пользователь А спрятал важные документы в ячейке камеры хранения, снабженной пяти декадным кодовым замком. Теперь он захотела бы сообщить Пользователю В комбинацию цифр, открывающую ячейку. Он реши ла использовать аналог шифра Цезаря, адаптированный к алфавиту, состоящему из десятичных цифр: с= (т + к) mod 10, (2.3) Допустим, А послала В шифротекст 26047. Пользователь С пытается рас шифровать его, последовательно перебирая все возможные ключи. Результаты попыток сведены в Таблица 2.. Таблица 2. Расшифровка сообщения 26047 путём перебора ключей
Мы видим, что все полученные варианты равнозначны и пользователь С не может понять, какая именно комбинация истинна. Анализируя шиф ротекст, он не может найти значения секретного ключа. Конечно, до перехвата сообщения у С было 105 возможных значений кодовой комбинации, а после — только 10. Однако важно отметить то, что в данном случае всего 10 значений ключа. Поэтому при таком ключе (одна десятичная цифра) А и В не могли рассчитывать на большую секретность. В первом примере сообщение — текст на русском языке, поэто му оно подчиняется многочисленным правилам, различные буквы и их сочетания имеют различные вероятности и, в частности, мно гие наборы букв вообще запрещены. (Это свойство называется из быточностью текста). Поэтому-то и удалось легко подобрать ключ и дешифровать сообщение, т.е. избыточность позволила «взломать» шифр. В противоположность этому, во втором примере все комби нации цифр допустимы. «Язык» кодового замка не содержит избы точности. Поэтому даже простой шифр, применённый к сообщени ям этого языка, становится невскрываемым. Описанная в приведённых примерах атака называется атакой по шифротексту. Но часто на шифр может быть проведена атака по известному тексту. Это происходит, если Пользователь С получает в своё распоряжение какие-либо открытые тексты, соответствующие ран нее переданным зашифрованным. Сопоставляя пары «текст-шифротекст», Пользователь С пытается узнать секретный ключ, чтобы с его помощью дешифровать все последующие сообщения от А к В. Можно представить себе и более «серьёзную» атаку — атаку по выбранному тексту, когда противник пользуется не только предо ставленными ему парами «текст-шифротекст», но может и сам фор мировать нужные ему тексты и шифровать их с помощью того клю ча, который он хочет узнать. Например, во время Второй мировой войны американцы, подкупив охрану, выкрали шифровальную ма шину в японском посольстве на два дня и имели возможность по давать ей на вход различные тексты и получать соответствующие шифровки. (Они не могли взломать машину с целью непосредствен ного определения заложенного в неё секретного ключа, так как это было бы замечено и повлекло бы за собой смену всех ключей.) Может показаться, что атаки по известному и выбранному тек сту надуманы и далеко не всегда возможны. Отчасти это так. Но раз работчики современных криптосистем стремятся сделать их неуяз вимыми даже и по отношению к атакам по выбранному тексту и на этом пути достигнуты значительные успехи. Иногда считается, что более надёжно использовать шифр, противостоящий атаке по выбранному тексту, чем организационно обеспечивать неосуществи мость такой атаки, хотя наиболее осторожные пользователи делают и то, и другое [13]. 3. Различные способы криптоанализа Оценки времени и стоимости вскрытия грубой силой Вспомните, что вскрытие грубой силой обычно является вскрытием с использованием известного открытого текста, для этого нужно немного шифротекста и соответствующего открытого текста. Если вы предполагаете, что наиболее эффективным способа взлома алгоритма является вскрытие грубой силой - большое допущение - то ключ должен быть достаточно длинным, чтобы сделать вскрытие невозможным. Насколько длинным? Скорость вскрытия грубой силой определяется двумя параметрами: количеством проверяемых ключей и скоростью проверки одного ключа. Большинство симметричных алгоритмов в качестве ключа могут использовать в качестве ключа любую битовую последовательность фиксированной длины. Длина ключа DES составля ет 56 бит, всего может быть 256 возможных ключей. Длина ключей для ряда алгоритмов, обсуждаемых в этой книге, равны 64 битам, всего может быть 264 возможных ключей. Другие алгоритмы используют 128-битовые ключи. Скорость, с которой может быть проверен каждый ключ, имеет менее важное значение. Для проводимого анализа я предполагаю, что скорость проверки ключа для каждого алгоритма примерно одинакова. В действительности скорость проверки одного алгоритма может быть в два, три или даже десять раз выше, чем другого. Но так как для тех длин ключей, для которых мы проводим поиск, время поиска в миллионы раз больше, чем время проверки одного ключа, небольшие отличия в скорости проверки не имеют значения. В криптологической среде большинство споров по поводу вскрытия грубой силой сконцентрированы вокруг алгоритма DES. В 1977 году Уитфилд Диффи и Мартин Хеллман сформулировали условия существования специализированной машины по взлому DES. Эта машина состоит из миллионов микросхем, каждая из которых проверяет миллион ключей в секунду. Такая машина за два часа сможет проверить 256 за 20 часов. При вскрытии алгоритма с 64-битовым ключом проверка всех 264 потребует 214 дней. Задача вскрытия грубой силой как будто специально придумана для параллельных процессоров. Каждый процессор проверяет подмножество пространства ключей. Процессорам не нужно обмениваться между собой информацией, единственным используемым сообщением будет сообщение, сигнализирующее об успехе. Не тре буется и доступ к одному участку памяти. Сконструировать машину с миллионом процессоров, каждый из которых работает независимо от других, нетрудно. Сконструировать машину для взлома грубой силой решил Майкл Винер. (Он сконструировал машину для DES, но анализ может быть выполнен почти для всех алгоритмов.) Он разработал специализиро ванные микросхемы, платы и стойки, оценил затраты и сделал вывод, что за миллион долларов можно построить машину, которая сможет взломать 56-битный ключ DES key в среднем за 3.5 часа (и наверняка за 7 часов). Соотношение стоимость/скорость является линейным. Вспомните о законе Мура: мощь вычислительных средств удваивается приблизительно каждые 18 месяцев. Это означает, что затраты будут уменьшаться на порядок каждые пять лет, и то, что в 1995 году стоит миллион долларов, в 2000 году будет стоить около 100000 долларов. Ещё более упростить процесс вычислений могла бы конвейеризация. Для 56-битовых ключей эти суммы оказываются вполне по карману большинству крупных корпораций и многим криминальным организациям. Военные бюджеты большинства промышленно развитых стран могут позволить взламывать и 64-битные ключи. Вскрытие 80-битного ключа все ещё за пределами возможного, но если текущая тенденция сохранится, то через каких-нибудь тридцать лет все может измениться. Конечно, нелепо прогнозировать компьютерную мощь на 35 лет вперёд (см. Таблица 2.). Технологические прорывы, попу лярные в научной фантастике, могут сделать эти прогнозы смешными. С другой стороны, неизвестные в на стоящее время физические ограничения могут сделать эти прогнозы нереально оптимистичными. В криптогра фии умнее быть пессимистом. Применение в алгоритме 80-битного ключа кажется недостаточно дальновидным. Используйте ключ, длина которого, по меньшей мере, 112 бит. Таблица 2. Оценки среднего времени для аппаратного вскрытия грубой силой в 1995 году
Если взломщик очень сильно хочет взломать ключ, все, что ему нужно, это потратить деньги. Следовательно, стоит попытаться определить минимальную «цену» ключа: в пределах какой стоимости сведе ний можно пользоваться одним ключом прежде, чем его вскрытие станет экономически выгодным? Крайний случай: если шифрованное сообщение стоит $1.39, то нет финансового смысла устанавливать аппаратуру стои мостью 10 миллионов долларов для взлома этого ключа. С другой стороны, если стоимость открытого текста – 100 миллионов долларов, то дешифрирование этого одиночного сообщения вполне окупит стоимость аппаратуры взлома. Кроме того, стоимость многих сообщений со временем очень быстро падает. Программное вскрытие Без специализированной аппаратуры и огромных параллельных машин вскрытие грубой силой намного сложнее. Программное вскрытие в тысячи раз медленнее, чем аппаратное. Реальная угроза программного вскрытия грубой силой страшна не своей неизбежностью, а тем, что такое вскрытие «свободно». Ничего не стоит загрузить простаивающий микрокомпьютер проверкой возможных ключей. Если правильный ключ будет найден - замечательно, если нет - ничего не потеряно. Ничего не стоит ис пользовать для этого целую сеть микрокомпьютеров. В недавних экспериментах с DES 40 рабочих станций в течение одного дня сумели проверить 234 ключей. При этой скорости для проверки всех ключей потребуется четыре миллиона дней, но если попытки вскрытия будут предприняты достаточным количеством людей, то кому-нибудь где-нибудь повезёт. Основной угрозой программного вскрытия является слепое везение. Представьте себе университетскую сеть из 512 объединённых в сеть рабочих станций. Для некоторых университетских городков это сеть весьма среднего размера. Такие сети могут даже расползтись по всему миру, координируя свою деятельность по электронной почте. Пусть каждая рабочая станция способна работать (с алгоритмом) со скоростью 15000 шифрований в секунду... С учётом накладных расходов на проверку и смену ключей уменьшим скорость до 8192 проверок в секунду на машину. Чтобы, используя описанную систему, исчер пать пространство (56-битовых) ключей потребуется 545 лет (в предположении, что сеть тратит на эту задачу 24 часа в сутки). Заметим, однако, что с помощью таких вычислений сторонники нашего студента получают один шанс из 200000 рас крыть ключ в течение одного дня. За долгий уикенд их шансы возрастают до одного из шестидесяти шести тысяч. Чем быст рее их аппаратура, или чем больше задействовано машин, тем лучше становятся их шансы. Вероятность заработать на жизнь, выигрывая на скачках, невысока, но разве не эти выигрыши заполняют собой пресс-релизы. К примеру, это гораздо большая вероятность, чем возможность выигрыша в правительственных лотереях. «Один на миллион?» «Один раз за тысячу лет?» Больше невозможно с полной ответственностью делать такие заявления. Является ли приемлемым этот продолжающийся риск? Использование алгоритма с 64-битовым ключом вместо 56-битового ключа делает это вскрытие в 256 раз сложнее. А 40-битовый ключ делает картину просто безрадостной. Сеть из 400 компьютеров с производитель ностью 32000 шифрований (на сегодняшний день персональные компьютеры в миллион раз производительнее) в секунду может за день выполнить вскрытие грубым взломом 40-битового ключа. Производительность современных суперкомпьютеров по сравнению с 1997 годом увеличилась в 1000 раз, а персональных в сотни тысяч раз. 128-битовый ключ вроде и должен быть надёжным, но современные алгоритмы шифрования AES используют ключи 128/192/256 бит что делает нелепым даже мысль о скрытии грубым взломом. По оценке Gartner к концу 2014 года в мире будет использоваться более 2 миллиардов компьютеров. Даже если все эти компьютеры будут брошены на вскрытие грубой силой, и каждый из них будет выполнять миллиард шифрований в секунду, время раскрытия ключа все равно будет в сотни тысяч раз больше времени существования вселенной. Нейронные сети Нейронные сети не слишком пригодны для криптоанализа, в первую очередь из-за формы пространства решений. Лучше всего нейронные сети работают с проблемами, имеющими непрерывное множество решений, одни из которых лучше других. Это позволяет нейронным сетям обучаться, предлагая все лучшее и лучшие решения. Отсутствие непрерывности в алгоритме почти не оставляет места обучению: вы либо раскроете ключ, либо нет. (По крайней мере, это верно при использовании любого хорошего алгоритма.) Нейронные сети хоро шо работают в структурированных средах, где обучение возможно, но не в высокоэнтропийном, кажущемся случайным мире криптографии. Вирусы Самая большая трудность в получении миллионов компьютеров для вскрытия грубым взломом - это убедить миллионы компьютерных владельцев принять участие во вскрытии. Вы могли бы вежливо попросить, но это требует много времени, и они могут сказать нет. Вы могли бы пробовать силой ворваться в их компьютеры, но это потребует еще больше времени и может закончиться вашим арестом. Вы могли бы также использовать компьютерный вирус, чтобы распространить программу взлома среди как можно большего количества компьюте ров. Взломщик пишет и выпускает на волю компьютерный вирус. Этот вирус не переформатирует жёсткий диск, не удаляет файлы, но во время простоя компьютера он работает на криптоаналитической проблемой грубого взлома. Различные исследования показали, что компьютер простаивает от 70 до 90 процентов времени, так что у вируса не будет проблем со временем для решения этой задачи. Если он нетребователен и в других отношениях, то его работа даже не будет заметна. В конце концов, одна из машин наткнётся на правильный ключ. В этот момент имеются два варианта про должения. Во-первых, вирус мог бы породить другой вирус. Он не делал бы ничего, кроме самовоспроизведения и удаления всех найденных копий вскрывающего вируса, но содержал бы информацию о правильном ключе. Этот новый вирус просто распространялся бы среди компьютеров, пока не добрался бы до компьютера человека, который написал первоначальный вирус. Другим, трусливым подходом был бы вывод на экран следующего сообщения: В этом компьютере есть серьёзная ошибка. Пожалуйста, позвоните 1-8001234567 и продиктуйте оператору следующее 64-битовое число: xxxx xxxx xxxx xxxx Первому, кто сообщит об этой ошибке будет выплачено вознаграждение 100 долларов. Насколько эффективно такое вскрытие? Пусть типичный заражённый компьютер проверяет тысячу ключей в секунду. Эта скорость намного меньше потенциальных возможностей компьютера, ведь мы полагаем, что он иногда будет делать и другие вещи. Предположим также, что типичный вирус инфицирует 10 миллионов машин. Этот вирус может вскрыть 56-битовый ключ за 83 дня, а 64 битовый - за 58 лет. Вам возможно при шлось бы подкупить разработчиков антивирусного программного обеспечения, но это уже ваши проблемы. Лю бое увеличение скорости компьютеров или распространения вируса, конечно, сделало бы это нападение более эффективным. Занятие №12. Перспективные направления криптографии Цели занятия:
Задачи занятия:
Учебные вопросы, рассматриваемые на занятии: 1. Развитие облачных технологий. 2. Квантовая криптография. Материал для проведения занятия 1. Развитие облачных технологий Облачные технологии продолжают трансформировать отрасль за отраслью, появляясь там, где их появление, казалось бы, наименее логично. Процесс в значительной степени напоминает рождение и триумфальное шествие компьютеров по разнообразному ландшафту человеческой деятельности. Сегодня уже мало кто задумывается о том, как компьютеры изменили изготовление газет и журналов, производство, сельское хозяйство, а особенно бизнес во всех его проявлениях. Теперь же точно так же меняют всё вокруг облака, и некоторые области уже по второму кругу. Например, бухгалтерию. В 1994 году Главное управление безопасности ФАПСИ разработало первый стандарт электронной подписи в России, но тогда в стране было ещё весьма смутное время, поэтому по-настоящему об электронной подписи заговорили лишь 8 лет спустя, в 2002-м, когда был утверждён новый стандарт криптозащиты ЭП, фактически уравнивающий российское понятие «электронная подпись» и международное — «цифровая подпись». Так что история этой технологии в нашей стране хоть и насчитывает уже двадцать лет, но фактически применяется не больше десяти. И бóльшую часть этого десятилетия технология работала следующим образом. На компьютеры организации (как правило, лишь в бухгалтерии), устанавливалось специальное ПО для работы с ЭП, а на USB-носителе содержались персонализированные ключи, хранившиеся в единственном экземпляре. Надо сказать, что безопасность в этом случае обеспечивалась практически полная. Не завладев той самой «флешкой» с ключами — токеном, — невозможно было подписать документы от имени организации. Но ведь были и минусы! Токен можно украсть, потерять, уничтожить физически — и тогда придётся вновь проходить процедуру авторизации в удостоверяющем центре. А если нужно подписать срочные документы? Словом, облачные технологии уже стояли у порога, чтобы навсегда изменить очередную отрасль, и сегодня сектор электронного документооборота может стать локомотивом их развития. Как привычная технология ЭП выглядит в облаке? Удостоверяющий центр создаёт вашу электронную подпись и располагает её в собственном облаке. Никаких токенов в этом случае не нужно: авторизация происходит по СМС, через привязанный мобильный телефон. Сама подпись располагается в облаке, поэтому подписывать счета и прочие документы можно с любого устройства с доступом в интернет: с офисного компьютера, с личного ноутбука, с планшета или даже смартфона. У такого подхода есть очевидные плюсы: 1. Её стоимость ниже. Приобретение облачной электронной подписи требует меньше затрат, чем покупка в обычном режиме. Это связано с тем, что для работы с этой подписью не нужно приобретать носитель и средство криптографической защиты информации (далее — СКЗИ). В случае облачной электронной подписи СКЗИ находится только на сервере, где хранится закрытый ключ. Всё это оформляется соответствующими соглашениями и доверенностями. 2. Мобильность. Сейчас интернет есть практически везде, а это значит, что и подписывать документы облачной электронной подписью можно с любого планшета, смартфона, устройства, поддерживающего выход в интернет. Ни бумага, ни электронная подпись на носителе не дают такой возможности. СКЗИ для мобильных устройств сейчас, конечно, разрабатываются, но вообще без СКЗИ на вашем устройстве, согласитесь, работать проще. Кроме того, закрытый ключ облачной ЭП не придётся устанавливать вам лично или платить сотруднику УЦ, который все настроит. Не нужно будет обучать пользователей работе со СКЗИ и сертификатами ЭП. Но, обладая массой положительных качеств, облачная подпись имеет и негативные моменты. Несмотря на то, что через популярные бухгалтерские сервисы уже выдали более 100 000 облачных ЭП за 2013 год, широкое применение подписей все ещё под вопросом. Одним из главных минусов — скорее из понятийной области. Сущность электронной подписи подразумевает замену собственноручной: то есть вы лично, собственными руками подписываете документ с помощью конфиденциальной части ключа. Она должна быть у вас и только у вас. В облачном же варианте закрытый ключ оказывается не в ваших руках — а где-то там на сервере УЦ. То есть фактически вы ставите подпись не собственными руками, а через посредника. Конечно, все это будет оформлено документально, а сами серверы надёжно защищены, но не во всех организациях служба безопасности одобрит такое. Если вам важно, чтобы документы подписывали сами владельцы закрытых ключей, то облачная электронная подпись вам не подойдёт. В целом же перспективы облачной ЭП и электронного документооборота в нашей стране обнадёживают. Госдума уже утвердила план развития электронного правительства до 2018 года, который включает и ряд мер по содействию бизнесу. Например, «снижение среднего числа обращений представителей бизнес-сообщества в орган госвласти для получения одной госуслуги». И пусть тезис звучит не очень внушительно, поскольку количество обращений планируют сократить лишь до двух, это уже определённый прогресс, приводящий нас к европейскому сценарию. То есть такой ситуации когда открыть бизнес, заплатить налоги и подписать любые документы можно будет в интернете, а зачастую и со смартфона [18]. 2. Квантовая криптография В перспективах возможно разработать методы и их программно-аппаратную реализацию по увеличению длины псевдослучайной последовательности, а также осуществить передачу ключей на основе квантовой криптографии. Идея вычислительной системы основана на вероятностной логике и работает с квантовыми битами - кубитами, которые могут находится в трёх состояниях - двух фиксированных и в состояние суперпозиции. Квантовые компьютеры должны обладать высокой вычислительной мощностью, но ограничение квантовой механики не позволяли создать рабочий модели. В конце 2012 года учёным удалось создать из двух кубитов первый прототип квантового логического инвертора - элемент, осуществляющий операцию «контролируемое НЕ». Конечно, одного логического элемента недостаточно для создания полноценной вычислительной системы, но последние исследования в области квантовой физики открывают пути к дальнейшим развитиям в данной области. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||