Математическая криптография.
Криптографические методы защиты информации
Если сторона В хочет установить общий секретный ключ со стороной А, то В вычисляет KB=f (xB) и посылает Кв, но открытому каналу к А. В свою очередь сторона, А вычисляет Кл = f (xA) и посылает Кл по открытому каналу к В. В силу свойств функции/(х) = gv (mod р) каждая из сторон может получить общий для них секретный ключ Клв: сторона В как Клв = (KA)XB (modp) и сторона, А как Клв = = (KB)x*(modp… Читать ещё >
Математическая криптография. Криптографические методы защиты информации (реферат, курсовая, диплом, контрольная)
В математической криптографии существует два основных подхода к определению стойкости криптографических схем: теоретикоинформационный и теоретико-сложностной. Теоретико-информационный (шенноновский) подход предполагает, что криптоаналитик (противник) не имеет никакой информации для раскрытия этой схемы[1]. Теоретико-сложностной подход предполагает, что противник располагает ограниченными вычислительными ресурсами для раскрытия криптографической схемы. Поэтому для применения теоретико-сложностного подхода необходимо, чтобы задача, вычислительную сложность которой предполагается использовать, была бы массовой. В связи с этим необходимо рассматривать математические модели криптографических схем. При этом такие модели зависят от некоторого параметра, именуемого параметром безопасности. И здесь важно понимать, что будет подразумеваться под ограниченными вычислительными ресурсами. Величина этих ресурсов не может быть просто константой, — она должна быть представлена функцией от растущего параметра безопасности. А сами криптографические схемы должны быть эффективными, т. е. реализуемыми за полиномиальное время[2], — время, ограниченное некоторым полиномом от длины параметра безопасности.
Таким образом, задача обоснования стойкости криптографических схем при теоретико-сложностном подходе сводится к доказательству отсутствия полиномиального алгоритма, который решает задачу, стоящую перед противником по раскрытию схемы. К сожалению, на настоящий момент теоретико-сложностная стойкость криптографических схем может быть установлена только с привлечением каких-либо недоказанных предположений1. Поэтому основные направления исследований в этой области связаны с поиском наиболее слабых достаточных условий для существования криптографических схем различных типов. В основном рассматриваются теоретико-сложностные предположения о решении некоторых широко известных математических задач (табл. 1.1), в основном задач из области теории чисел.
Таблица 1.1
Часто используемые в криптографии вычислительно сложные задачи.
Условное обозначение. | Наименование задачи. | Дано. | Найти. |
FACTORING | Задача факторизации целых чисел. | N | Рр егп=рер-… р^ где Pi — попарно простые числа,. et> 1. |
RSA | Задача RSA | п = pq, е: НОД (с, (р -)(q-)) = = 1, с е Z | т: trf = с (mod я). |
SRA | Усиленная задача RSA | n=pq, ze Z"*. | Г-Г (2)>1,. У е К: У' ~ г. |
QRP | Задача о квадратичных вычетах. | п — нечетное составное целое число,. (а} а е Z: — =1. W. | а € QR" |
SQROOT | Задача извлечения квадратного корня по модулю п | п — составное число, а е QR" | х: х2 = «(mod/?). |
DLP | Задача дискретного логарифмирования. | р — простое число, а— образующий элемент р € к | х: 0 < х < р — 2, ах = p (modp). |
1 Например, предположения о существовании однонаправленных функций. Хотя существование таких функций и «выглядит правдоподобно», однако все существующие на сегодня однонаправленные функции являются гипотетическими (кри птографическим и) объектам и.
Условное обозначение | Наименование задачи | Дано | Найти |
GDLP | Обобщенная задача дискретного логарифмирования | G — конечная циклическая группа, | G | = пу а — обр. элемент в G, р € Г | х: 0 < х< п — 1, а[3] = р |
DIIP | Задача Диффи — Хеллмана | р — простое число, а — образующий элемент Z* a" (mod/;), ал(тоd/;) | aaA(mod/;) |
GDIIP | Обобщенная задача Диффи — Хеллмана | G — конечная циклическая группа, а — образующий элемент в G, а" , а[3]' | а" '' |
DDHP | Задача распознавания (decision) Диффи — Хеллмана | р — простое число, а — образующий элемент a" (modр), ай(modр), ar(mod /;) | aab = a[3]'(mod р) |
SUBSET | Задача о рюкзаке | {av а2,…, — множество положительных целых чисел, s — положительное целое число | ;е{ 1…" } |
Для размышления Наиболее характерным примером обоснования гипотетической стойкости криптографических схем является получение нижних оценок сложности решения задачи дискретного логарифмирования, которую может решать противник при раскрытии многих известных криптографических схем, например, схемы открытого распределения ключей Диффи — Хеллмана[3].
Основная задача ключевого обмена Диффи — Хеллмана заключается в следующем: «Каким образом можно установить секретный ключ между сторонами, А и В по открытому каналу связи, а затем использовать его для шифрованной передачи сообщений?» Эти авторы предложили следующую элегантную конструкцию для этой цели.
Сторона, А выбирает однонаправленную функцию / следующего вида. Пусть g — образующий группы (подгруппы) G вычетов по модулю большого простого числа р с порядком | G|. Тогда функция.
f (pc) = g'(mod p) является однонаправленной, так как в соответствии с гипотезой о вычислительной сложности решения задачи извлечения дискретных логарифмов, получить х = log^/(х) можно лишь с пренебрежимо малой вероятностью.
Если сторона В хочет установить общий секретный ключ со стороной А, то В вычисляет KB=f (xB) и посылает Кв но открытому каналу к А. В свою очередь сторона, А вычисляет Кл = f (xA) и посылает Кл по открытому каналу к В. В силу свойств функции/(х) = gv(mod р) каждая из сторон может получить общий для них секретный ключ Клв: сторона В как Клв = (KA)XB(modp) и сторона, А как Клв = = (KB)x*(modp). В любом случае ключ Клв получается у обоих участников протокола одинаковым, поскольку Клв = gXAXB(modp).
Так как противник в силу свойств предложенной Диффи и Хеллманом однонаправленной функции гипотетически не может ее инвертировать, то он не может и вычислить Клв, имея в наличии лишь Кл и Кв, но не имея ни одного секретного ключа. Таким образом, установленный ключ Клв может использоваться обеими сторонами для защищенной связи с использованием как криптосистем с секретным ключом, так и криптосистем с открытым ключом.
- [1] Например, для упомянутого выше шифра Бернама.
- [2] См. приложения Г и Д.
- [3] Другие известные криптографические схемы, стойкость которых гипотетически основана на сложности решения задачи дискретного логарифмирования, рассмотрены в гл. 3 и 4.
- [4] Другие известные криптографические схемы, стойкость которых гипотетически основана на сложности решения задачи дискретного логарифмирования, рассмотрены в гл. 3 и 4.
- [5] Другие известные криптографические схемы, стойкость которых гипотетически основана на сложности решения задачи дискретного логарифмирования, рассмотрены в гл. 3 и 4.
- [6] Другие известные криптографические схемы, стойкость которых гипотетически основана на сложности решения задачи дискретного логарифмирования, рассмотрены в гл. 3 и 4.