Скачать 1.43 Mb.
|
Ck(j)=(j+k)(mod n),где n - количество букв в алфавите, k- ключ шифрования, j – номер шифруемого символа в алфавите. Очевидно, что обратной подстановкой являетсяCk(j)=(j+n-k)(mod n)Частотный анализ использует то свойство зашифрованного текста, что частота встречаемости символов в нем совпадает с частотой встречаемости соответствующих символов в открытом тексте. Если же учесть, что частоты встречаемости различных символов в текстах соответствующего языка распределены неравномерно (так, например, относительная частота встречаемости буквы «А» в текстах на русском языке составляет 0.069, а буквы «Ф» 0.003), то, подсчитав относительную частоту встречаемости букв в шифротексте, можно предположить, что символ, наиболее часто встречающийся в шифротексте, соответствует символу, наиболее часто встречающемуся в текстах на соответствующем языке, и найти таким образом ключ k. Такой метод криптоанализа применим только к моноалфавитным криптоалгоритмам, и для его успешной работы требуются тексты большого размера. Для современных криптоалгоритмов используются более совершенные методы криптоанализа: дифференциальный, линейный, силовая атака. Дифференциальный метод криптоанализа был предложен Э.Бихамом и А.Шамиром в 1990 г. Дифференциальный криптоанализ представляет собой атаку на основе выборочного шифротекста. В качестве материала для анализа используется изменение меры несходства двух открытых текстов при их прохождении по основным этапам криптопреобразования. В качестве меры несходства двух двоичных векторов используется расстояние Хэмминга – количество бит, в которых эти вектора отличаются друг от друга. Успех попыток вскрытия r-циклического шифра зависит от существования дифференциалов (r-1)-го цикла c большей долей вероятности. Дифференциал i-го цикла определяется как пара ( a , b ) i такая, что пара различных открытых текстов x, x* c расстоянием Хэмминга a может привести к паре выходных текстов y, y* после i-ого цикла, имеющих расстояние Хэмминга b. Вероятность i-циклового дифференциала ( a ,b ) i - это условная вероятность P( D y(i)=b | D x(i)= a ) того, что расстояние Хэмминга пары шифртекстов ( y, y*) после i-ого цикла равна b при условии, что пара текстов (x, x*) имеет расстояние a. Алгоритм дифференциального криптоанализа включает следующие этапы: 1. На предварительном этапе путем многократного шифрования различных текстов накапливаем статистику для множества (r-1)-цикловых дифференциалов (a1, b1)r-1 , (a2,b2)r-1 ,.... (as,bs)r-1 . Упорядочиваем это множество дифференциалов по величине их вероятности. 2. Выбираем открытый текст x произвольным образом и подбираем x* так, чтобы расстояние Хэмминга между x и x* было равно a1 . Тексты x и x* шифруются на подлинном ключе и после r циклов получаем пару шифртекстов y , y*. Предполагаем, что на выходе предпоследнего (r-1)-ого цикла разность шифртекстов равна наиболее вероятной: Dy(r-1)= b1 . Для тройки ( D y(r-1), y , y*) находим каждое возможное значение подключа последнего цикла к(r) . Добавляем его к количеству появлений каждого такого значения подключа к(r) . 3. Повторяем п.2 до тех пор, пока одно или несколько значений подключа к(r) не станет появляться чаще других. Этот подключ или множество таких подключей используем в качестве криптографического решения для подключа к(r) . 4. Повторяем пп.1-3 для предпоследнего цикла, при этом значения y(r-1) вычисляются расшифрованием шифртекстов на найденном подключе последнего цикла к(r) . Далее действуем аналогично, пока не будут раскрыты ключи всех циклов шифрования. Для успешного осуществления дифференциального криптоанализа необходимо иметь большой набор пар открытый текст/шифротекст (до 247 подобных пар для атаки на 16 раундов DES). Повышение стойкости шифра к дифференциальному криптоанализу возможно путем увеличения количества раундов: для алгоритма DES при 17 раундах шифрования дифференциальный криптоанализ не эффективнее силовой атаки. Линейный метод криптоанализа был предложен японским математиком Мацуи в 1993 г. Метод также является атакой на основе выборочного шифротекста. Метод использует линейные приближения, предполагающие с определенной вероятностью, что существует линейная зависимость между некоторыми битами открытого текста, шифротекста и ключа: mi1 mi2 … mir cj1 cj2 … cjs = kt1 kt2 … ktn, (2.1) где i1..ir, j1..js, t1..tn – позиции некоторых бит открытого текста m, шифротекста c и ключа k. Пусть p - вероятность того, что (2.1) выполняется для случайно выбранных m и с. Тогда необходимо, чтобы p 1/2 и величина | p -1/2 | должна быть как можно больше. Если | p -1/2 | достаточно велика и криптоаналитику известно достаточное число пар открытых и соответствующих зашифрованных текстов, то сумма по модулю 2 бит ключа на соответствующей позиции в правой части (2.1) равна наиболее вероятному значению суммы по модулю 2 соответствующих бит открытых и зашифрованных текстов в левой части. Если p > 1/2, то сумма бит ключа в правой части (2.1) равна нулю, если сумма бит в левой части равна нулю больше, чем для половины пар зашифрованных текстов, и сумма бит ключа в правой части (2.1) равна единице, если сумма бит в левой части равна единице больше, чем для половины текстов . Если p < 1/2 , то наоборот, сумма бит ключа в правой части (2.1) равна нулю, если сумма бит в левой части равна единице больше, чем для половины пар открытых и зашифрованных текстов, и сумма бит ключа в правой части (2.1) равна единице, если сумма бит в левой части равна нулю больше, чем для половины текстов. Таким образом формируется система линейных уравнений, неизвестными в которых являются биты ключа, и задача дальнейшего анализа заключается в поиске решения этой системы. Для увеличения стойкости алгоритма к линейному криптоанализу в его состав вносят нелинейные функции преобразования (например, табличные подстановки). Силовая атака на блочные шифры предполагает полный перебор всех возможных ключей шифрования, и ее эффективность зависит от размера ключевого пространства шифра. Так, если ключ шифрования имеет размер 56 бит, то возможно использование 256 ключей, что, как уже отмечалось, не составляет в настоящее время вычислительных трудностей криптоаналитику, особенно если учесть, что задача полного перебора ключей легко поддается распараллеливанию. Так, при проведении фирмой RSA Data Security inc. в сети Internet конкурса по взлому шифра RC5 количество компьютеров, одновременно участвующих в атаке, достигло 4500 единиц, а пиковая производительность – 440 млн. ключей в секунду[11]. По оценкам ведущих специалистов в области криптографии длина ключа шифрования, гарантирующая криптостойкость к силовой атаке, должна составлять от 75 до 90 бит. 2.4. Симметричное поточное шифрование Поточные шифры характерны тем, что шифруют информацию по одному биту за такт шифрования. Учитывая, что среди операций с битами существуют только две обратимые – сумма по модулю 2 и логическое отрицание, то выбор принципа шифрования очевиден – биты открытого текста должны складываться с битами ключевой последовательности с помощью операции : ci = mi ki. Дешифрование происходит аналогичным образом: mi = ci ki. Учитывая свойства операции сложения по модулю 2, можно отметить, что выполняется: ki = ci mi, поэтому криптостойкость поточных шифров полностью зависит от качества генератора потока ключей. Очевидно, что если поток ключей будет включать в себя только двоичные нули, то шифротекст будет представлять собой точную копию открытого текста. Поток ключей поточных шифров принято обозначать греческой буквой (гамма), вследствие чего подобные шифры получили название шифров гаммирования. Большинство современных генераторов гаммы построено на линейных регистрах сдвига (ЛРС). Он представляет собой (рис.2.9) последовательность бит, которая на каждом такте шифрования сдвигается вправо на 1 разряд, при этом выход из крайнего правого бита является выходом генератора, а на вход крайнего левого бита подается значение, вычисляемое как сумма по модулю 2 нескольких разрядов ЛРС. Ключ шифрования поточного шифра заносится в ЛРС перед началом генерации гаммы. Рассмотрим работу ЛРС на примере трехразрядного регистра, структура которого приведена на рис.2.10 Занесем в регистр начальное значение 010 и посмотрим, какие значение получим на выходе гаммы. Таблица 2.2 Результат работы генератора гаммы на основе ЛРС
Из таблицы видно, что состояние ЛРС повторяется через 7 тактов (начальное состояние ЛРС совпадает с его состоянием на 7-м такте). Повтор состояния ЛРС означает, что и гамма будет периодически повторяться. Повторение гаммы снижает криптостойкость поточных шифров, позволяя криптоаналитику проводить анализ шифротекстов, полученных кодированием на одной и той же гамме. Поэтому при проектировании структуры ЛРС встает проблема достижения максимального периода повтора ЛРС. Для ЛРС длиной n бит максимальный период составляет 2n-1 тактов (состояние, когда все биты равны нулю, недопустимо, поскольку ЛРС любой структуры не выходит из этого состояния, зацикливаясь в нем). Построение ЛРС оптимальной структуры с точки зрения периода повторения гаммы имеет четкую математическую основу в виде теории неприводимых полиномов. Структура ЛРС описывается многочленом вида: b1*xn+b2*xn-1+b3*xn-2+…+bn-1*x2+ bn*x+1, где bi=0, если i-й бит слева не участвует в обратной связи, и bi=1, если участвует. ЛРС будет иметь максимально возможный период повторения гаммы, если описывающий его многочлен не раскладывается на произведение многочленов меньшей степени. Основной проблемой ЛРС является их нестойкость к атаке на основе известного открытого текста. Даже если неизвестна внутренняя структура ЛРС, криптоаналитик с помощью алгоритма Берлекэмпа-Мэсси по известным 2N битам открытого текста и соответствующего шифротекста имеет возможность построить ЛРС, порождающую подобную последовательность. Поэтому современные поточные шифры строятся на основе нелинейных регистров сдвига (НРС). Нелинейные регистры сдвига строятся на основе линейных с добавлением в структуру нелинейных элементов: логического сложения и логического умножения. Наиболее популярными классами нелинейных регистров сдвига на сегодня являются фильтрующие, комбинирующие и динамические поточные шифры [6]. Фильтрующие НРС строятся с использованием дополнительной комбинационной схемы – фильтра – на выходах некоторых бит ЛРС (рис.2.11). Выход комбинационной схемы и является гаммой. К омбинирующие НРС также используют комбинационную схему с нелинейными преобразованиями бит, но на вход этой комбинационной схемы подаются выходы нескольких ЛРС (рис.2.12). При проектировании НРС комбинирующего типа необходимо следить, чтобы комбинационная схема равномерно перемешивала выходы каждого из ЛРС, иначе может возникнуть ситуация доминирования одного из ЛРС, когда его выход на подавляющем большинстве тактов совпадает с общим выходом НРС. Динамические НРС также строятся на основе нескольких ЛРС, но здесь они вступают друг с другом в отношения «главный-подчиненный» (рис.2.13). В зависимости от выхода управляющего ЛРС на общий выход НРС подается либо выход первого, либо второго ЛРС. В качестве примера поточного шифра, построенного на основе регистров сдвига, можно привести алгоритм A5, используемый для кодирования в стандарте GSM. A5 включает 3 ЛРС длиной 19, 22 и 23 бита на выход гаммы подается сумма по модулю 2 выходов всех регистров. Используется схема динамического НРС, когда каждый регистр тактируется в зависимости от состояния средних разрядов всех трех регистров сдвига. Поточными являются также шифры RC4, SEAL, WAKE [12]. 2.5. Асимметричное шифрование Симметричное шифрование имеет недостатки, которые ограничивают возможности его применения в ряде конкретных случаев. В частности, зачастую невозможно организовать секретный канал для обмена ключами шифрования между участниками взаимодействия. Еще одним недостатком симметричных шифров является необходимость хранения большого количества ключей: для того чтобы в вычислительной сети могли конфиденциально попарно взаимодействовать N участников, необходимо наличие в системе N*(N-1)/2 ключей. Эти недостатки можно устранить, используя алгоритмы асимметричного шифрования. Например, для асимметричной системы достаточно иметь 2*N пар открытый/закрытый ключ, чтобы можно было организовать секретный канал между каждой парой участников. 2.5.1. Математические основы асимметричного шифрования Основная идея асимметричного шифрования заключается в существовании сразу двух ключей для обмена информацией – открытого, известного любому желающему, и закрытого, который известен лишь получателю информации. Очевидно, что открытый и закрытый ключи генерируются одновременно и между ними существует определенная математическая связь. Основная задача проектировщика асимметричного алгоритма заключается в том, чтобы по известному открытому ключу было бы невозможно (очень трудоемко) получить секретный ключ шифрования. Для этого в основу асимметричных алгоритмов закладываются вычислительно трудные задачи факторизации, дискретного логарифмирования, проецирования точек на эллиптической кривой и т.д. Объединяет все эти задачи то, что они используют операцию получения остатка от целочисленного деления. Для любого положительного целого числа n и любого a при делении a на n мы получаем некоторое целое частное q и остаток r, удовлетворяющий соотношению
где int(x) обозначает наибольшее целое число, не превышающее x. Если a является целым, а n - положительным, то a mod n определяется как остаток от деления a на n. Таким образом, для любого целого числа a можно записать
Говорят, что два целых числа a и b являются сравнимыми по модулю n, если (a mod n) = (b mod n). Это записывается в виде: a b mod n. Операции сравнения по модулю имеют следующие свойства:
Операции арифметики в классах вычетов обладают следующими свойствами:
Пусть Zn обозначает множество всех не отрицательных целых чисел, которые меньше n:
Это множество называется ещё множеством вычетов (остатков) по модулю n. Для арифметических операций по модулю n в этом множестве выполняются следующие свойства:
Существует одна особенность арифметики в классах вычетов, которая делает её отличной от обычной арифметики. Заметим сначала, что, как и в обычной арифметике, имеет место следующее свойство
Данное свойство согласуется с существованием аддитивного обратного. Прибавив к обеим частям данного равенства аддитивное обратное элемента а, получим:
Однако следующее утверждение: если (a * b) (a * c) mod n, то b c mod n
Если p является простым, то все элементы Zp будут взаимно простыми с p. Это даёт нам возможность добавить ещё одно свойство к тем, которые были приведены выше:
Для поиска мультипликативного обратного можно использовать расширенный алгоритм Евклида, который позволяет в целых числах найти решение уравнения ax+by=1 при заданных а и b. Очевидно, что если решение существует, то x будет величиной, мультипликативно обратной а по модулю b. Алгоритм Евклида 1. Определить матрицу E: 2. Вычислить r –остаток от деления числа a на b: a = bq + r, 0 r < b 3. Если r=0, то первый столбец матрицы E является решением уравнения. 4.Если r 0, заменить матрицу Е: 5.Поменять местами столбцы матрицы Е. 6. Заменить пару чисел a, b на b, r и перейти к шагу 2. 2.5.2. Алгоритмы асимметричного шифрования Исторически первой системой с открытым ключом стал метод экспоненциального ключевого обмена Диффи - Хеллмана, разработанный в 1976 году. Метод предназначен для передачи секретного ключа симметричного шифрования. В обмене задействованы два участника А и Б. Сначала они выбирают большие простые числа n и g<n (эти числа секретными не являются). Затем участник A выбирает большое целое число х, вычисляет Х=gx mod n и передает Х участнику Б. Б в свою очередь выбирает большое целое число y, вычисляет Y=gy mod n и передает Y участнику А. Б вычисляет K’=Xy mod n, А вычисляет K’’=Yx mod n. Легко заметить, что K’=K’’=gxy mod n, и это значение оба участника могут использовать в качестве ключа симметричного шифрования. Криптостойкость этого метода определяется трудоемкостью вычисления дискретного логарифма в конечном поле. Действительно, злоумышленник может узнать такие параметры алгоритма, как n, g, X, Y, но вычислить по ним значения x или y – задача, требующая очень больших вычислительных мощностей и времени. Метод легко можно обобщить на случай ключевого обмена большего количества участников. Использование метода Диффи - Хеллмана на практике должно сопровождаться сертификацией «открытых» ключей X и Y. Иначе злоумышленник может провести атаку, которая известна под названием «человек посередине» (man-in-the-middle), когда передаваемые участниками А и Б сообщения перехватываются злоумышленником и подменяются сообщениями X’ и Y’, вычисленными на основе его закрытого ключа. В итоге будут установлены два соединения «А - зломышленник» и «Б - злоумышленник», причем А и Б будут уверены, что обмениваются сообщениями друг с другом. Необходимо также отметить, что алгоритм Диффи - Хеллмана не является асимметричным алгоритмом шифрования, шифрование при его использовании необходимо выполнять с использованием симметричного шифра. Примером действительно асимметричного алгоритма шифрования, основанного на проблеме дискретного логарифма, является алгоритм Эль-Гемаля, разработанный в 1985 г. Последовательность действий при генерации ключей, шифровании и дешифрации представлена на рис. 2.14. Необходимо пояснить процедуру дешифрования. Так как axgkx mod p, то имеем: Таким образом, кодируемое сообщение М разбивается на части, каждая из которых m интерпретируется как число в диапазоне [0 .. p-1], и выполняется операция шифрования согласно схеме на рис.2.14. На практике при использовании данного алгоритма рекомендуется выбирать ключи размером 768, 1024 и 1536 бит. Самым первым, действительно асимметричным алгоритмом стал алгоритм RSA, названный так по первым буквам фамилий своих разработчиков. Алгоритм был разработан в 1978 году. В основу криптостойкости RSA положена задача факторизации (разложения на множители) больших (более 200 двоичных разрядов) целых чисел. Процедуры генерации ключей, шифрования и дешифрования для этого алгоритма представлены на рис. 2.15. На этапе генерации ключей формируется пара ключей: закрытый d и открытый e. Шифрование данных должно начинаться с его разбиения на блоки m размером k=[log2 (n)] бит каждое, чтобы блок m можно было рассматривать как целое число в диапазоне [0.. n-1]. Обратимость операции шифрования и дешифрования RSA требует доказательства. Из теоремы Эйлера известно, что для двух целых чисел n и x, таких, что (n,x)=1, выполняется: x(n)1 mod n, (2.2) где (n) – функция Эйлера, значение которой равно количеству чисел меньших n и взаимно простых с ним. Для n=pq из алгоритма RSA, где p и q – простые числа, можно записать (n)=(p-1)(q-1). Тогда (2.2) можно переписать в виде: x(p-1)(q-1)1 mod n (2.3) Возведем обе части (2.3) в степень –y: x(-y)(p-1)(q-1) 1(-y) mod n 1 mod n (2.4) Умножим обе части (2.4) на x: x(-y)(p-1)(q-1) +1 mod n = x (2.5) Но при генерации ключей мы получили e и d такие, что ed 1 mod (p-1)(q-1), а это означает, что в (2.5) можно заменить 1-y(p-1)(q-1) на ed: xed mod n = x Тогда, если мы возведем шифротекста c=me mod n в степень d по модулю n, как мы это и делаем при дешифровании, то получим: (cd ) mod n= (me mod n)d mod n = med mod n = m Очевидно, что основная задача криптоаналитика при взломе этого шифра – узнать закрытый ключ d. Для этого он должен выполнить те же действия, что и получатель при генерации ключа – решить в целых числах уравнение ed + y (p-1)(q-1) =1 относительно d и y. Однако, если получателю известны входящие в уравнение параметры p и q, то криптоаналитик знает только число n – произведение p и q. Следовательно, ему необходимо произвести факторизацию числа n, то есть разложить его на множители. Для решения задачи факторизации к настоящему времени разработано множество алгоритмов: квадратичного решета, обобщенного числового решета, метод эллиптических кривых. Но для чисел большой размерности это очень трудоемкая задача. Ее трудоемкость можно подтвердить следующими цифрами [11]: для факторизации числа 100D (число с 100 десятичными разрядами) потребовалась вычислительная мощность 7MY (1 MY – величина, равная годовой производительности компьютера, выполняющего один миллион целочисленных инструкций в секунду), для числа 130D – 500MY, для числа 140D – 2000 MY. Современная криптография к надежным ключам шифрования RSA относит ключи длиной 768, 1024, 2048 бит. Необходимо отметить, что математически не была доказана единственность способа восстановления m по с и e разложением n на множители. Криптоаналитики не исключают, что может быть открыт совсем иной способ криптоанализа RSA, и тогда алгоритм станет абсолютно непригодным для практического использования. Еще одной проблемой является генерация больших простых чисел для алгоритма. Строгое доказательство простоты сгенерированного случайного числа требует решение той же самой задачи факторизации, поэтому большинство общепринятых тестов устанавливает простоту числа с некоторой вероятностью. Что произойдет, если p или q окажется составным? Тогда у модуля n будет три или более делителей. Соответственно некоторые делители будут меньше рекомендованной величины, что, в свою очередь, открывает возможности для атаки путем факторизации модуля. Некоторые атаки используют уязвимость протокола использования алгоритма RSA [12]. Важно понимать, что само по себе использование RSA не обеспечивает требуемого уровня безопасности системы. Рассмотрим некоторые возможные атаки на протокол шифрования RSA. Если злоумышленнику удалось перехватить сообщение c, зашифрованное с помощью открытого RSA-ключа пользователя А, то для раскрытия m = сd он сначала выбирает первое случайное число r, меньшее n, и затем, воспользовавшись открытым ключом А е, вычисляет x = re mod n, y = xc mod n, t = r-1 mod n. Если х = re mod n , то r= xdmod n Далее злоумышленник каким-либо способом вынуждает А закодировать сообщение y на его секретном ключе. А посылает злоумышленнику u = yd mod n Теперь злоумышленник раскрывает m, вычисляя tu mod n =r-1yd mod n = r-1 xdcd mod n =cd mod n = m |
Учебное пособие является логическим продолжением пособия «Методы... Пласковский А. М., Новопашенный А. Г., Подгурский Ю. Е., Заборовский В. С. Методы и средства защиты компьютерной информации. Межсетевое... |
Миит кафедра “сапр транспортных конструкций и сооружений” ... |
||
Учебное пособие рпк «Политехник» Гринчук Ф. Ф., Хавроничев С. В. Комплектные распределительные устройства напряжением 610 кВ. Часть I: Учеб пособие / Воггту, Волгоград,... |
Учебное пособие рпк «Политехник» Гринчук Ф. Ф., Хавроничев С. В. Комплектные распределительные устройства напряжением 610 кВ. Часть II: Учеб пособие / Воггту, Волгоград,... |
||
Учебное пособие рпк «Политехник» Авторы: Б. А. Карташов (главы 5, 6); Е. В. Матвеева (главы 1, 2); Т. А, Смелова (глава 3); А. Е. Гаврилов (введение, глава 4) |
Учебное пособие Рекомендовано учебно-методическим объединением по... Шевченко Н. Ю. Электронная техника. Руководство к лабораторным работам: Учеб пособие / Волггту, Волгоград, 2006. – 52 с |
||
Учебное пособие Викторова Т. С., Парфенов С. Д. Системы компьютерной графики. Учебное пособие, том 13 Вязьма: филиал фгбоу впо «мгиу» в г. Вязьме,... |
Учебное пособие для подготовки войск го по зомп, М, гу по делам го... Ионизирующие излучения и методика их обнаружения. Приборы радиационной, химической разведки и дозиметрического контроля |
||
Учебное пособие М74 модели и методы управления персоналом: Российско-британское учебное пособие /Под ред. Е. Б. Моргунова (Серия «Библиотека журнала... |
Разъяснения по получению средства криптографической защиты информации «Континент-ап» Выдача средства криптографической защиты информации (далее скзи) «Континент-ап» производится на основании заключенного договора об... |
||
Учебное пособие Пенза 2014 удк 004. 415. 2(076. 5) М31 Рецензен т... М31 Методы и средства проектирования программного обеспечения : учеб пособие / Т. В. Черушева, Т. Ю. Горюнова. – Пенза : Пенз филиал... |
Монография рпк «Политехник» Книга предназначена для инженерно-технических работников проектных и эксплуатационных организаций объектов электроэнергетики и электротехники,... |
||
«защита информации от несанкционированного доступа» Фз о защите информации, который рассматривает проблемы защиты информации и задачи защиты информации, а также решает некоторые уникальные... |
И. Н. Привалов Современные методы и технические средства для испытаний... Учебное пособие предназначено для работников кабельных сетей энергосистем и промышленных предприятий |
||
А. И. Мансурова, Р. Р. Зиннатов методы кха в экологическом мониторинге учебное пособие Методы кха в экологическом мониторинге: Методическое пособие к лабораторным и практическим занятиям для студентов направления подготовки... |
Методические указания к практическим занятиям рпк «Политехник» Методические указания предназначены для проведения практических занятий по дисциплине “Базы данных” в соответствии со стандартом... |
Поиск |