|
|
Оглавление1. Понятие информационной безопасности 2. Основные классификации угроз информационной безопасности 3. Программы с потенциально опасными последствиями 5. Элементарные методы цифрового шифрования 6. Симметричные системы защиты информации 7. Криптография с открытым ключом. 8. Аутентификация 9. Методы криптоанализа классических шифров Методические указания к лабораторным работам Контрольно-измерительные материалы Методические рекомендации по разработке курсовых работ Для бесплатного чтения доступна только часть главы! Для чтения полной версии необходимо приобрести книгу7. КРИПТОГРАФИЯ С ОТКРЫТЫМ КЛЮЧОМТрадиционно криптография основывалась на том, что отправитель и получатель сообщения знали и использовали один и тот же секретный ключ. Отправитель с его помощью шифровал сообщение, а получатель – расшифровывал. Этот метод называется криптографией с секретным ключом (secret-key cryptography) или симметричная криптография (symmetric cryptography). Главная проблема такого метода заключается в том, чтобы получатель и отправитель использовали один и тот же ключ, который должен быть неизвестен всем остальным. Если они находятся на большом расстоянии друг от друга, им приходится доверять курьеру, телефону или другой системе передачи сообщений, скрывая то, что передается секретный ключ. Создание, передача и хранение ключей называется распределением ключей (key management). Все криптосистемы должны выполнять распределение ключей, однако при использовании метода криптографии с секретным ключом этот процесс имеет весьма сложный характер. В 1976 г. был разработан метод криптографии с открытым ключом для распределения ключей. Этот метод предполагает наличие двух ключей – открытого и личного. Открытый ключ можно разглашать, а личный необходимо хранить в тайне. При этом необязательно, чтобы и отправитель, и получатель имели доступ к одной и той же секретной информации. При обмене сообщениями пересылается только открытый ключ. Таким образом, пользуясь данным методом, можно не беспокоиться о надежности каналов передачи информации. Более того, криптография с открытым ключом, в отличие от криптографии с секретным ключом, может применяться не только для секретности (шифрование), но и для аутентификации (цифровая подпись). Несколько слов о том, как выполняется шифрование при использовании открытого ключа. Если я хочу послать сообщение адресату А., я нахожу в справочнике открытый ключ А., использую его для кодирования сообщения и отправляю письмо. Получив мое послание, А. с помощью своего личного ключа декодирует и читает мое сообщение. Таким образом, любой может послать А. закодированное сообщение, но только А. может прочесть его. Естественно, единственное требование к такому методу – исключение возможности получения личного ключа из соответствующего открытого ключа. При аутентификации криптография с открытым ключом применяется следующим образом. Для того чтобы подписать сообщение, я выполняю определенные вычисления, применив секретный ключ и само сообщение. В результате я получаю подпись, которая дополняет отправляемое сообщение. Если А. хочет убедиться в подлинности подписи, он также выполняет некоторые вычисления, используя полученный текст, подпись и мой открытый ключ. Если после решения несложных математических уравнений получаем правильный результат, подпись подлинная. В противном случае, можно сделать вывод, что подпись была подделана либо сообщение изменено. 7.1. Алгоритм RSAАлгоритм RSA, предложенный в 1977 гг. Р.Ривестом (Ron Rivest), А.Шамиром (Adi Shamir) и Л.Эдлеманом (Leonard Adleman), предназначен для шифрования и цифровой подписи. В настоящее время RSA является наиболее распространенной криптосистемой – стандартом де-факто для многих криптографических приложений. Статус де-факто послужил причиной включения алгоритма RSA в принятые ранее криптографические стандарты. Из всех предложенных за эти годы алгоритмов с открытыми ключами RSA проще всего понять и реализовать. Алгоритм RSA многие годы противостоит интенсивному криптоанализу. Безопасность RSA основана на трудности разложения на множители больших чисел. Открытый и закрытый ключи являются функциями двух больших (100–200 разрядов или даже больше) простых чисел. Предполагается, что восстановление открытого текста по шифртексту и открытому ключу эквивалентно задаче факторизации. Для генерации двух ключей используются два больших случайных простых числа: p и q. Для максимальной безопасности нужно выбирать p и q равной длины. Рассчитывается произведение: n = pq. Затем случайным образом выбирается ключ шифрования е, такой что е и (p - 1)(q - 1) являются взаимно простыми числами. Наконец расширенный алгоритм Евклида используется для вычисления ключа дешифрирования d, такого, что ed = 1(mod(p - 1)(q - 1)). Другими словами, d = e-1mod((p - 1)(q - 1)). При этом d и n – также взаимно простые числа. Числа е и n – это открытый ключ, а число d – закрытый. Два простых числа p и q хранятся в секрете. Они должны быть отброшены, но не должны быть раскрыты. Для шифрования сообщения m необходимо выполнить его разбивку на цифровые блоки, каждый из которых меньше n (для двоичных данных выбирается самая большая степень числа 2, меньшая n). То есть если p и q – 100-разрядные простые числа, то n будет содержать около 200 разрядов, и каждый блок сообщения mi должен быть около 200 разрядов в длину. Если нужно зашифровать фиксированное число блоков, их можно дополнить несколькими нулями слева, чтобы гарантировать, что блоки всегда будут меньше n. Зашифрованное сообщение с будет состоять из блоков сi той же самой длины. Формула шифрования выглядит так: ci = mei mod n. Для расшифровки сообщения необходимо взять каждый зашифрованный блок ci и вычислить mi = cdi mod n. Так как формула XXX восстанавливает сообщение, то все вычисления выполняются по mod n. Параметры криптосистемы и процедуры шифрования и дешифрования сведены в табл. 7.1. Таблица 7.1 Шифрование RSA
Вообще сообщение может быть зашифровано с помощью d, а дешифровано с помощью е, возможен любой выбор. Быстродействие аппаратной реализации RSA примерно в 1000 раз ниже, чем быстродействие аппаратной реализации DES. Скорость работы самой быстрой СБИС-реализации RSA с 512-битовым модулем – 64 килобита в секунду. Существуют также микросхемы, которые выполняют 1024-битовое шифрование RSA. В настоящее время разрабатываются микросхемы, которые, используя 512-битовый модуль, приблизятся к рубежу 1 Мбит/с. Производители также применяют RSA в интеллектуальных карточках, однако производительность этих реализаций невысока. Программная реализация DES примерно в 100 раз быстрее RSA. Эти оценки могут незначительно отличаться при изменении технологии, но RSA никогда не достигнет скорости симметричных алгоритмов. В табл. 7.2 приведены примеры программной реализации RSA для 8-битовой экспоненты шифрования и различной разрядности модуля. Для взлома ключей системы RSA необходимо разложить модуль N на простые множители. Из-за большой популярности этой системы в настоящее время в этой области криптоанализа работает очень много ученых и, необходимо отметить, не без успеха. Рекомендуется использовать RSA-ключи с длиной верхних границ, которые приводятся в табл. 7.3. Таблица 7.2 Эффективность программной реализации RSA (в секундах на SPARC II)
Таблица 7.3 Длина верхних границ RSA-ключей
Безопасность RSA полностью зависит от проблемы разложения на множители больших чисел. Однако никогда не было доказано математически, что нужно разложить n на множители, чтобы восстановить m по c и е. Не исключено, что может быть открыт совсем иной способ криптоанализа RSA. Однако, если этот новый способ позволит криптоаналитику получить d, он также может быть использован для разложения на множители больших чисел. Также можно атаковать RSA, угадав значение (p - 1)(q - 1). Однако этот метод не проще разложения n на множители. При использовании RSA раскрытие даже нескольких битов информации по шифртексту не легче, чем дешифрование всего сообщения. Самой очевидной атакой на RSA является разложение п на множители. Любой противник сможет получить открытый ключ е и модуль п. Чтобы найти ключ дешифрования d, противник должен разложить п на множители. Криптоаналитик может перебирать все возможные d, пока не подберет правильное значение. Но подобная силовая атака даже менее эффективна, чем попытка разложения п на множители. В 1993 г. был предложен метод криптоанализа, основанный на малой теореме Ферма. К сожалению, этот метод оказался медленнее разложения на множители. Существует еще одна проблема. Большинство общепринятых тестов устанавливает простоту числа с некоторой вероятностью. Что произойдет, если р или q окажется составным? Тогда у модуля п будет три или более делителей. Соответственно некоторые делители будут меньше рекомендованной величины, что, в свою очередь, открывает возможности для атаки путем факторизации модуля. Другая опасность заключается в генерации псевдопростых чисел (чисел Кармайкла), удовлетворяющих тестам на простоту, но при этом не являющихся простыми. Однако вероятность генерации таких чисел пренебрежимо мала. На практике, последовательно применяя набор различных тестов на простоту, можно свести вероятность генерации составного числа до необходимого минимума. Атака на основе выборочного шифртекста Некоторые вскрытия работают против реализаций RSA. Они вскрывают не сам базовый алгоритм, а надстроенный над ним протокол. Само по себе использование RSA не обеспечивает безопасности. Дело в реализации. Никогда нельзя пользоваться алгоритмом RSA для подписи случайных документов. Применение хеш-функций в технологии RSA-подписи строго обязательно. Формат блоков ISO 9796 предотвращает это вскрытие. Атака на основе общего RSA-модуля При реализации RSA можно попробовать раздать всем абонентам криптосети одинаковый модуль n, но каждому – свои значения показателей степени e и d. При этом наиболее очевидная проблема заключается в том, что если одно и то же сообщение когда-нибудь шифровалось разными показателями степени (при фиксированном модуле) и эти два показателя – взаимно простые числа (как обычно и бывает), то открытый текст может быть раскрыт даже при неизвестных ключах дешифрования. Существует два других, более тонких метода раскрытия подобного типа. Один использует вероятностный метод для разложения п на множители. Другой – детерминированный алгоритм вычисления какого-нибудь секретного ключа без разложения модуля на множители. Таким образом, использование общего для группы пользователей параметра п может отрицательно сказаться на уровне безопасности криптосети. Шифрование коротких сообщений Известно, что криптосистема RSA обладает низкой криптостойкостью при шифровании короткого сообщения малым е. Действительно, при с = me < п открытый текст т может быть восстановлен по шифртексту с при помощи процедуры извлечения корня. Фактически подобная атака возможна и тогда, когда в процессе возведения в степень выполнялось некоторое количество приведений по модулю. При с > п трудоемкость такой атаки ниже трудоемкости исчерпывающего перебора для т. Однако меры противодействия также очевидны: либо открытый ключ е должен быть достаточно большим, либо открытый текст не должен быть коротким. Выбор малого е обусловлен соображениями вычислительной эффективности шифрования и проверки подписи. Таким образом, разумный подход заключается в искусственном наращивании коротких открытых текстов (“набивки”). При этом необходимо следить за тем, чтобы удлиненный открытый текст при числовом отображении не превращался в набор множителей некоторого известного числа Р, например P = 21, что происходит при дополнении открытого текста последовательностью нулей справа (со стороны младших разрядов). Раскрытие малого показателя шифрования Дж.Хэстед (J.Hasted) продемонстрировал уязвимость RSA при условии, если криптоаналитик может получить множество шифртекстов фиксированного сообщения из зашифрованного текста при помощи криптосистемы RSA с различными секретными параметрами р и q, но при использовании фиксированного открытого ключа е. При соблюдении сформулированных условий можно раскрыть сообщение т. Эта атака возможна только при условии, что исходные сообщения получены известным криптоаналитику способом (фиксированное сообщение т является частным случаем). Меры противодействия сводятся к использованию псевдослучайного контекста для “набивки” сообщений перед их шифрованием. Метод “набивки” из стандарта PKCS # 1 в настоящее время пересматривается в связи с разработкой нового оптимального метода “набивки” для асимметричных криптосистем (Optimal Asymmetric Encryption Padding). Раскрытие малого показателя дешифрования Данная атака позволяет раскрывать d, когда d не превышает четверти размера п, а е < п. При случайном выборе е и d это маловероятно и никогда не произойдет, если значение е мало. Значение d должно быть большим. Практическая криптостойкость RSA: оценки и прогнозы Известно, что практическая криптостойкость RSA зависит от вычислительной трудоемкости задачи факторизации – разложения двусоставного модуля (произведение двух простых чисел) на сомножители. Факторизация модуля позволяет раскрыть секретный ключ и, как следствие, дешифровать любое сообщение, подделать цифровую подпись. Чем больше число, тем выше вычислительная трудоемкость факторизации. Необходимо отметить, что повышение производительности компьютеров положительно сказалось на успехах в области факторизации, но криптостойкость RSA при этом также возросла. Эффект объясняется различиями в вычислительной трудоемкости процедур факторизации и шифрования/дешифрования: в результате очередного скачка производительности число, поддающееся факторизации, увеличивается на два разряда, тогда как RSA-модуль, без потери вычислительной эффективности, – на двенадцать разрядов. Однако факторизация возможна в случае, если рост производительности не учитывается при периодичности смены ключей. Нельзя полностью исключить возможность атак на основе иных, отличных от факторизации методов. Кроме того, вычислительная трудоемкость модульного возведения в степень (основной операции при шифрова-нии/дешифровании) возрастает с увеличением разрядности модуля. Основная задача при выборе модуля RSA – одновременное обеспечение криптостойкости и вычислительной эффективности процедуры шифрования/дешифрования. Таким образом, при выборе модуля необходимо исходить из реальных оценок роста производительности компьютеров и достижений в области вычислительной теории чисел. Согласно оценкам, для обеспечения адекватного уровня практической криптостойкости разрядность модуля RSA должна быть увеличена в ущерб вычислительной эффективности. Однако идея разбалансированной RSA, предложенная А.Шамиром, позволяет этого избежать. В настоящее время криптосистема RSA с модулем 512 бит, реализованная во многих криптографических приложениях, не гарантирует объявленной криптостойкости. Отмечают, что в отличие от строгого обоснования низкой криптостойкости RSA с модулем 512 бит прогнозы на будущее менее конкретны; пока анализируются лишь тенденции роста производительности компьютеров и возможные пути развития вычислительной теории чисел. Оценки опираются на предположение о последовательной природе криптографических алгоритмов и использовании стандартной технологии СБИС при их реализации. Для исключительно секретной информации представляется разумным выбор RSA-модуля с разрядностью порядка 5000 бит. Основная причина стремительного роста разрядности надежного модуля заключается в субэкспоненциальной оценке времени работы современных алгоритмов факторизации. Для сравнения: трудоемкость силовой атаки на симметричную криптосистему, например DES, определяется объемом ключевого пространства (2n – в худшем случае и 2n-1 – в среднем, при n-разрядном ключе). Тенденция к увеличению размера модуля криптосистемы RSA вполне обоснованна – атака на основе факторизации представляет реальную угрозу. Тем более, когда речь идет о хранении долговременных секретов (например, долговременных долговых обязательств, закладных и т.д.). Однако с увеличением разрядности модуля сложность вычислений возрастает кубически. Таким образом, выбор разрядности модуля представляет собой компромисс между вычислительной эффективностью и криптостойкостью. А.Шамир (A.Shamir) предложил новый подход к решению проблемы RSA-модуля. Криптосистема с модулем, построенным методом Шамира, получила название “разбалансированной RSA”. В такой криптосистеме – разрядность модуля п = pq увеличена в десять раз (до 5000 бит), а разрядность делителя р в два раза (до 500 бит). Соответственно на делитель q приходится 4500 бит. Название криптосистемы отражает диспропорцию в разрядности делителей п. Такой выбор делителей, по мнению А.Шамира, учитывает тенденции развития методов целочисленной факторизации и обеспечит адекватную криптостойкость в течение длительного времени. Основная проблема заключается в том, что при таком модуле быстродействие реализации RSA – в 1000 раз ниже: теперь задержка на одну операцию модульного возведения в степень вместо одной секунды (при микропроцессорной реализации и 500-битном модуле) составит 16 минут, что неприемлемо. Широко распространенный способ повышения вычислительной эффективности RSA при шифровании с = me(mod n) заключается в выборе малого е. Однако при заданных делителях выбор е < 10 не обеспечивает приведения по модулю в процессе шифрования, так как длина сообщения т составляет десятую часть от длины модуля п. При е ≈ 20 разрядность me приблизительно в два раза превышает разрядность модуля n, что обеспечивает приведение по модулю в процессе шифрования. Таким образом, при 20 < е < 100 быстродействие шифрования при 5000-битном модуле сравнимо с быстродействием дешифрования при 500-бигном модуле (менее одной секунды). Несмотря на то, что разбалансированная и стандартная криптосистемы RSA имеют сравнимую вычислительную трудоемкость, затраты памяти для хранения открытых ключей разбалансированной RSA возрастают в десять раз. Для устранения этого недостатка было предложено несколько методов. Необходимо также отметить, что разбалансированность может использоваться для удвоения производительности существующих в настоящее время реализаций RSA, в которых делители р и q имеют одинаковый размер. Причем для RSA-подписи такая оптимизация не подходит, так как проверяющему неизвестен делитель р. Кроме того, способ, при котором опубликованный короткий открытый ключ на самом деле является длинным, является чрезвычайно полезным при ограничениях на размер модуля, аналогичных экспортным ограничениям на длину ключа для симметричных криптосистем. Пакетная RSA Пакетная RSA (batch RSA) представляет собой метод, позволяющий выполнять множество RSA-дешифрований (порядка n/log2(n)), где n – секретный параметр, логарифм берется по основанию 2) с вычислительной эффективностью одиночного RSA-дешифрования. При этом предполагается, что используется единый модуль, но различные и попарно взаимно простые экспоненты шифрования е. Проблема вычислительной эффективности RSA возникает в ряде криптографических приложений с централизованным управлением. Так, например, некоторые схемы цифровой подписи предполагают наличие депозитарно-распределительного центра, генерирующего заверенные цифровой подписью квитанции для каждой транзакции. В других распространенных приложениях центральный компьютер должен обслуживать поток запросов в режиме on-line, например при управлении ключами в сетях со звездообразной топологией. Таким образом, пакетная RSA позволяет минимизировать вычислительную нагрузку центра. На основании перечисленных атак можно сформулировать следующие ограничения при использовании RSA: – знание одной пары показателей шифрования/дешифрирования для данного модуля позволяет взломщику разложить модуль на множители; – знание одной пары показателей шифрования/дешифрирования для данного модуля позволяет взломщику вычислить другие пары показателей, не раскладывая модуль на множители; – в криптографических протоколах с использованием RSA общий модуль использоваться не должен. (Это является очевидным следствием предыдущих двух пунктов.); – для предотвращения вскрытия малого показателя шифрования сообщения должны быть дополнены случайными значениями; – показатель дешифрирования должен быть большим. Недостаточно использовать безопасный криптографический алгоритм, должны быть безопасными вся криптосистема и криптографический протокол. Слабое место любого из трех этих компонентов сделает небезопасной всю систему. RSA de facto является стандартом почти по всему миру. RSA служит информационным дополнением ISO 9796. Французское банковское сообщество приняло RSA в качестве стандарта, так же поступили и австралийцы. В Соединенных Штатах из-за давления NSA в настоящее время нет стандарта для шифрования с открытым ключом. Многие американские компании используют PKCS, написанный RSA Data Security, Inc. RSA определен и в качестве чернового банковского стандарта ANSI. 7.2. Алгоритм Диффи-ХеллманаУ.Диффи и М.Хеллман предложили для создания криптографических систем с открытым ключом функцию дискретного возведения в степень. Необратимость преобразования в этом случае обеспечивается тем, что достаточно легко вычислить показательную функцию в конечном поле Галуа, состоящим из p элементов (р – либо простое число, либо простое в любой степени). Вычисление же логарифмов в таких полях – значительно более трудоемкая операция. Если y = аx’, 1 < x < p - 1, где р – фиксированный элемент поля GF(p), то x = logay над GF(p). Имея x, легко вычислить у. Для этого потребуется 2ln(x + y) операций умножения. Внимание! Авторские права на книгу "Современные технологии информационной безопасности. Учебно-методический комплекс" ( Шаханова М.В. ) охраняются законодательством! |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
