Современные средства криптографии. Реферат по дисциплине Основы Информационной Безопасности. - Криптология - Скачать бесплатно
как
C[i]^d=(m[i]^e)^e=m[i]^ed=m[i]^kf(n)+1=m[i]*m[i] ^kf(n)=m[i]*1=m[i].
Все вычисления выполняються по модулю n.
Отметим, что сообщение может быть зашифровано с помощью d, а дешифровано с
помощью e, возможен любой выбор.
Рассмотрим короткий пример. Если
p=47 и q=71, то n=pq=3337.
Ключ e не должен иметь общих множителей с
f(n)=46*70=3220.
Выберем (случайное) e равным 79. В этом случае d=79^-1 mod 3220 = 1019.
Опубликуем e и n, сохранив в секрете d. Для шифрования сообщения
m=6882326879666683
сначала разобьем его на блоки. Для выбранных параметров ограничимся
блоками по три десятичных разряда. Сообщение разбивается на шесть блоков
m[i]:
m[1]=688
m[2]=232
m[3]=687
m[4]=966
m[5]=668
m[6]=003
Первый блок шифруется как 688^79 mod 3337 = 1570 = c[1]. Выполняя те же
операции для последующих блоков, создадим шифротекст сообщения:
c=15702756209122762423158.
Для дешифрования нужно выполнить возведение в степень, используя ключ
дешифрования 1019:
1570^1019 mod 3337 = 688 = m[1].
Аналогично восстанавливается оставшаяся часть сообщения.
Эффективность реализации
Существует много публикаций, затрагивающих тему аппаратных реализаций RSA.
Быстродействие аппаратной реализации RSA примерно в 1000 раз ниже, чем
быстродействие аппаратной реализации DES. Быстродействие СБИС-реализации
RSA с 512-битовым модулем - 64 Кбит/сек. Существуют также микросхемы RSA,
которые оперируют с 1024-битовыми числами. В настоящее время
разрабатываются микросхемы, которые, используя 512-битовый модуль,
приблизятся к рубежу 1 Мбит/сек. Производители так же реализуют RSA в
интеллектуальных карточках, однако производительность этих реализаций
невысока. Программная реализация DES примерно в 100 раз быстрее
программной реализации RSA. Эти оценки могут незначительно могут
незначительно меняться в зависимости от используемых технологий, но RSA
никогда не достигнет производительности симметрических алгоритмов.
Шифрование RSA выполняются намного эффективнее, если правильно выбрать
значение e. Чаще всего используются 3, 17 или 65537 = 2^16+1 - двоичное
представление этого числа содержит только две единицы, поэтому для
возведения в степень нужно выполнить лишь 17 умножений. Стандарт X.509
рекомендует число 65537, PEM - 3, PKCS#1 - 3 или 65537. Использование в
качестве e любого из указанных значений (при условии, что сообщение
дополняются случайными числами) не влияет на криптостойкость, даже если
одно и то же значение e используется группой пользователей. Операции с
секретным ключом можно ускорить при помощи китайской теоремы об остатках,
если сохранить значения p и q, а так же заранее по секретному и открытому
ключам вычислить вспомогательные значения: d mod (p-1), d mod (q-1) и q^-1
mod p.
Криптостойкость RSA
Предполагается, что криптостойкостью RSA зависит от проблемы разложения на
множители больших чисел. Однако никогда не было доказано математически,
что нужно разложить n на множители, чтобы восстановить m по c и e. Не
исключено, что может быть открыт совсем иной способ криптоанализа RSA.
Однако, если этот новый способ позволит криптоаналитику получить d, он
также может быть использован для разложения на множители больших чисел.
Так же можно атаковать RSA, угадав значение (p-1)(q-1). Однако этот метод
не проще разложения n на множители. Доказано, что при использовании RSA
раскрытие даже нескольких битов информации по шифротексту не легче, чем
дешифрования всего сообщения. Самой очевидной атакой на RSA является
разложение n на множители. Любой противник сможет получить открытый ключ e
и модуль n. Чтобы найти ключ дешифрования d, противник должен разложить n
на множители. Криптоаналитик может перебирать все возможные d, пока не
подберет правильное значение. Но подобная силовая атака даже менее
эффективна, чем попытка разложения n на множители. В 1993 г. Был предложен
метод кирптоанализа, основанный на малой теореме Ферма. К сожалению, этот
метод оказался медленнее разложения на множители. Существует еще одна
проблема. Большинство общепринятых тестов устанавливает простоту числа с
некоторой вероятностью. Что произойдет, если p или q окажется составным?
Тогда у модуля n будет три или более делителей. Соответственно некоторые
делители будут меньше рекомендованной величины, что, в свою очередь,
открывает возможности для атаки путем факторизации модуля. Другая
опасность заключается в генерации псевдопростых чисел (чисел Кармайкла),
удовлетворяющих тестам на простоту, но при этом не являющихся простыми.
Однако вероятность генерации таких чисел пренебрежимо мала. На практике,
последовательно применяя набор различных тестов на простоту, можно свести
вероятность генерации составного числа до необходимого минимума.
Итоги по безопасности
На основании известных атак можно сформулировать следующие ограничения при
использовании RSA:
* знание одной пары показателей шифрования/дешифрования для данного
модуля позволяет злоумышленнику разложить модуль на множители;
* знание одной пары показателей шифрования/дешифрования для данного
модуля позволяет злоумышленнику вычислить другие пары показателей, не
расладывая модуль на множители;
* в криптографических протоколах с использованием RSA общий модуль
использоваться не должен. (Это являеться очевидным следствием
предыдущих двух пунктов.);
* для предотвращения раскрытия малого показателя шифрования сообщения
должны быть дополнены («набиты») случайными значениями;
* показатель дешифрования должен быть большим.
Отметим, что недостаточно использовать криптостойкий алгоритм; безопасной
должна быть вся криптосистема, включая криптографический протокол. Слабое
место любого из трех компонентов сделает небезопасной всю систему.
Криптосистема ЭльГамаля.
Криптосистему, предложенную ЭльГамалем в 1985 г. Можно использовать как
для цифровых подписей, так и для шифрования. Криптостойкость определяется
трудоемкость вычисления дискретного алгоритма в конечном поле.
Криптоалгоритм не запатентован, но попадает под действие патента на метод
экспоненциального ключевого обмена Диффи-Хеллмана.
Для генерации пары ключей сначала выбираются простое число p и два
случайных числа, g и x; оба этих числа должны быть меньше p. Затем
вычисляется
y=g^x mod p.
Открытым ключом являются y, g и p. И g, и p можно сделать общими для
группы пользователей. Секретным является x.
Вычисление и проверка подписи
Чтобы подписать сообщение M, сначала выбирается случайное число k, взаимно
простое с p-1. Затем вычисляется a=g^k mod p, и с помощью расширенного
алгоритма Евклида из уравнения
M=(xa+kb) mod (p-1)
находиться b. Подписью является пара чисел: a и b. Случайное значение k
должно храниться в секрете. Для проверки подписи необходимо убедиться, что
y^aa^b mod p = g^M mod p.
Каждая новая подпись требует нового значения k, и это значение должно
выбираться случайным образом. Если злоумышленник раскроет k, используемое
Алисой, он сможет раскрыть секретный ключ Алисы x. Если злоумышленник
сможет получить два сообщения, подписанные при помощи одного и того же k,
он сможет раскрыть x, даже не зная k.
Рассмотрим простой пример. Выберем p=11 и g=2. Пусть секретный ключ x=8.
Вычислим
y=g^x mod p = 28 mod 11 = 3.
Открытым ключом являются y=3, g=2 и p=11. Чтобы подписать M=5, сначала
выберем случайное число k=9. Убедимся, что gcd(9,10)=1. Далее вычислим
a=g^k mod p = 29 mod 11 = 6,
и затем с помощью расширенного алгоритма Евклида найдем b из уравнения
5=(8*6+9*b) mod 10.
Решение: b=3, а подпись представляет собой пару: a=6 и b=3. Для проверки
подписи убедимся, что y^aa^b mod p = g^M mod p:
3663 mod 11 = 25 mod 11.
Шифрование/дешифрование
Некоторая модификация позволяет использовать криптосистему для
шифрования/дешифрования сообщений.
Для шифрования сообщения M сначала выбирается случайное число k,
взаимно-простое с p-1. Затем вычисляются:
a=g^k mod p,
b=y^kM mod p.
Пара (a,b) является шифротекстом. Отметим, что шифротекст в два раза
длиннее открытого текста.
0x08 graphic
Для дешифрования (a,b) вычисляются
По сути описанное преобразование - это то же самое, что и экспоненциальный
ключевой обмен по Диффи-Хеллману, за исключением того, что обмен по
Диффи-Хеллману, за исключением того, что - это часть ключа, а при
шифровании сообщение умножается на y^k.
Хеш-функции
Односторонняя функция H применяется к сообщению произвольной длины M и
возвращает значение h=H(M) фиксированной длины m. Многие функции позволяют
значение фиксированной длины по входным данным произвольной длины, но
однонаправленные (или односторонние) хеш-функции обладают рядом
дополнительных свойств:
* зная M, легко вычислить h;
* при заданном h задача нахождения M, для которого H(M)=h, должна быть
вычислительно-трудоемкой;
* при заданном M задача нахождения другого сообщения M', для которого
H(M)=H(M'), должна быть вычислительно трудоемкой.
Смысл применения однонаправленных хеш-функций и состоит в обеспечении для
M уникального значения - «отпечатка пальца» сообщения. Если Алиса
подписала M цифровой подписью с использованием хеш-функции H(M), а боб
может создать другое сообщение M' отличное от M, для которого H(M)=H(M'),
то Боб сможет утверждать, что Алиса подписала сообщение M'. В некоторых
приложениях необходимо выполнение дополнительного требования, называемого
устойчивостью к коллизиям. Смысл данного требования заключается в том, что
задача нахождения двух случайных сообщений M и M', для которых H(M)=H(M'),
должна быть вычислительно-трудоемкой (с экспоненциальным объемом
перебора).
Следующий протокол, впервые описанный Юваловым, показывает, как Алиса
может воспользоваться коллизиями для обмана Боба.
1. Алиса готовит две версии контракта: одну, выгодную для Боба, и другую,
приводящую его к банкротству.
2. Алиса вносит несколько незначительных изменений в каждый документ и
вычисляет хеш-функции. (Этими изменениями могут быть действия,
подобные следующим: замена одного пробела комбинацией пробелов,
вставка одного - двух пробелов перед возвратом каретки и так далее.
Производя или не производя по одному изменению в каждой из 32 строк,
Алиса может Легко получить 2^32 различных документов.)
3. Алиса сравнивает хеш-значения для каждого изменения в каждом из двух
документов, разыскивая пару, для которой эти значения совпадают. (Если
выходом хеш-функции является 64-битное значение, Алиса, как правило,
сможет найти совпадающую пару выполнив 2^32 сравнений.) Таким образом,
она получает два документа, дающих одинаковое значение хеш-функции.
4. Алиса получает подписанную Бобом выгодную для него версию контракта,
используя протокол, в котором он подписывает только значение
хеш-функции.
5. Спустя некоторое время, Алиса подменяет контракт, подписанный Бобом,
другим, которого он не подписывал. Теперь она может убедить арбитра в
том, что Боб подписал другой контракт.
Отметим, что могут применяться и другие атаки. Например, противник может
посылать системе автоматического контроля (может быть, спутниковой)
случайные сообщения со случайными цифровыми подписями. В конце концов
подпись под одним из этих случайных сообщений окажется правильной.
Противник не сможет узнать, к чему приведет эта команда, но если его
единственной целью является вмешательство в работу спутника, он своего
добьется.
Хеш-функции с 64-битным выходным значением не могут противостоять
описанной выше атаке. Хеш-функции, выдающие 128-битовые значения, имеют
определенные преимущества. Для того, чтобы найти коллизию, придется
вычислить значение хеш-функции придется вычислить значение хеш-функции для
2^64 случайных документов, чего, впрочем, недостаточно, если безопасность
должна обеспечиваться в течении длительного периода времени.
Федеральный стандарт СШФ - SHS (алгоритм SHA)
Национальный Институт Стандартов США при участии АНБ разработал алгоритм
вычисления хеш-функции SHA, используемый в алгоритме цифровой подписи DSA
стандарта DSS.
Для любого входного сообщения длиной меньше 2^64 битов SHA выдает
160-битовый «дайджест» сообщения. Далее «дайджест» подается на вход DSA,
который вычисляет подпись для сообщения. Подписывание «дайджеста» вместо
сообщения часто повышает эффективность процесса, так как «дайджест»
намного меньше, чем само сообщение. Тот же «дайджест» сообщения должен
быть получен тем, кто проверяет подпись. При использовании SHA задача
поиска сообщения, соответствующего данному «дайджесту», или двух различных
сообщений с одинаковым «дайджестом» является вычислительно-трудоемкой.
Любые изменения сообщения, произошедшие во время передачи, с очень высокой
вероятностью приведут к изменению «дайджеста», и подпись не пройдет
проверку.
Стандарт России - ГОСТ Р 34.11-94
Разработанная российскими криптографами хеш-функция описана в стандарте
ГОСТ 34.11-94. В ней используется блочный шифр ГОСТа 28147-89, хотя
теоретически может использоваться любой блочный шифр с 64-битным блоком и
256-битным ключом. Хеш-функция выдает 256-битное значение.
Еще стоит отметить такие известные хеш-функции, как MD2, MD4, MD5 и
RIPEMD-160.
В реферате были рассмотрены все основные составляющие современной
криптографии. Это симметрические криптосистемы, асимметрические
криптосистемы и хеш-функции. Так же был коротко затронут механизм цифровой
подписи, и системы использующееся для этого.
Список используемой литературы:
1. Чмора А.Л. Современная прикладная криптография. 2-е изд., стер. - М.:
Гелиос АРВ, 2002. - 256с.: ил.
2. А.Г. Ростовцев, Н.В. Михайлова Методы криптоанализа классических
шифров.
3. А. Саломаа Криптография с открытым ключом.
18
Противник
Отправитель сообщения
Получатель сообщения
Открытый канал
Отправитель сообщения
Секретный канал
Секретный ключ
Шифратор
Дешифратор
Получатель сообщения
Криптоаналитик
Открытый канал
Секретный
Ключ
Открытый
ключ
Дешифратор
Шифратор
Аутентичный канал
Криптоаналитик
Отправитель сообщения
Получатель сообщения
Ключи получателя
Шифратор
Дешифратор
Секретный
ключ
Открытый
ключ
Аутентичный канал
Отправитель сообщения
Криптоаналитик
Получатель сообщения
Ключи отправителя
Открытый текст
Начальная перестановка
L[0
]R[0
]f
L[1]=R[0
]R[1]=L[0] x f(R[0], K[1])
K[1
]f
K[2
]L[2]=R[1
]R[2]=L[1] x f(R[1], K[2])
………………………………………………………………….
L[15]=R[14
]R[15]=L[14] x f(R[15], K[15])
f
L[16]=R[15
]R[16]=L[15] x f(R[15], K[16])
K[16
]Обращение начальной перестановки
Шифротекст
Сдвиг
Сдвиг
Ключ
Ключ
Перестановка со сжатием
Перестановка с расширением
Подстановка в S-блоке
Подстановка в P-блоке
L[i-1
]L[i
]R[i-1
]R[i
]L[i-1
]L[i
]R[i
]R[i-1
]Выбор подключа
Подстановка через S-блок
Циклический сдвиг влево
0x01 graphic
|
