Размещено на http://www.allbest.ru/

План

• Введение
• 1. Задача дискретного логарифмирования
• 1.1 Проблема дискретного логарифмирования (DLP) в
• 1.2 Обобщенная проблема дискретного логарифма
• 1.3 Атака на Задачи дискретного логарифма
• 2. Эллиптические кривые
• 2.1 Определение эллиптических кривых
• 2.2 Группа операций на эллиптических кривых
• 2.3 Электронный обмен ключами Диффи-Хеллмана
• 2.4 Обмен ключам Дифф-Хельмана на эллиптических кривых
• 2.5 Безопасность
• Список литературы


Введение

Средства и системы криптографической защиты информации играют важную роль в современных компьютерных информационных системах, используемых в сфере финансовой и коммерческой деятельности. Интерес к ним обусловлен не только возрастающими общественными потребностями в переводе экономических и государственно-правовых отношений на «электронную основу», но и сильно расширившимися возможностями передачи, обработки и хранения информации в распределенных вычислительных системах. Применение специальных криптографических протоколов и криптосистем позволяет осуществлять многообразные экономические отношения «дистанционно», исключая необходимость личной встречи участников этих отношений, а также поддерживать при этом должную финансовую и правовую дисциплину. К криптографическим протоколам относят протоколы шифрования, электронной цифровой подписи (ЭЦП), идентификации и протоколы аутентифицированного распределения ключей.

В 1985 году Нил Коблиц и Виктор Миллер независимо предложили использовать в криптографии некоторые алгебраические свойства эллиптических кривых. С этого момента началось бурное развитие нового направления в криптографии, для которого используется термин криптография на эллиптических кривых (Elliptic Curve Cryptography, сокращенно ECC). Криптосистемы с открытым ключом на эллиптических кривых обеспечивают такую же функциональность, как и алгоритм RSA. Однако их криптостойкость основана на другой проблеме, а именно на проблеме дискретного логарифма в группе точек эллиптической кривой (Elliptic Curve Discrete Logarithm Problem, сокращенно ECDLP). В настоящее время лучшие алгоритмы для решения ECDLP имеют экспоненциальное время работы, в отличие от алгоритмов для решения проблемы простого дискретного логарифма и проблемы факторизации целого числа, которые имеют субэкспоненциальное время работы. Это означает, что в системах на эллиптических кривых желаемый уровень безопасности может быть достигнут при значительно меньшей длине ключа, чем, например, в схеме RSA. Например, 160-битный ключ в ECC обеспечивает тот же уровень безопасности, что и 1024-битный ключ в RSA. В этой работе подробно рассматривается задача дискретного логарифмирования, определяется эллиптическая кривая и группа операций на ней, так же показана проблема обмена ключами Диффи-Хелмана.



1. Задача дискретного логарифмирования

Задача дискретного логарифмирования представляет большой интрес в области криптосистем с открытым ключом. Большинство существующих алгоритмов нахождения дискретного логарифма основаны на предрположении о чрезвычайно высокой вычислительной сложности (вопрос о решении дисрктного логарифма за полиномиальное время на персональном комьютере остаётся открытым до сих пор), чем сложнее её решить, тем более криптобезопасной является пересылка информации.

Задачи дискретного логарифмирования (DLP), непосредственно могут быть объяснены с помощью циклических групп.

Начнем с DLP над, где р простое.

1.1 Проблема дискретного логарифмирования (DLP) в

Для начала дадим определение.

Определение. Проблема дискретного логарифмирования

Пусть дана конечная циклическая группа порядка р-1 и примитивный элемент б ?, и другой элемент в ?Zp. Проблема дискретного логарифмирования состоит в определении целого 1 ?x ? р-1 такого, что:

б ^x?в mod p

Такое целое число х должно существовать, так как это примитивный элемент и каждая группа элементов может быть выражена с помощью любого примитивного элемента. Это число х называется дискретной логарифм в по основанию б, и мы можем формально записать:

x = log_б в mod p

Вычисление дискретных логарифмов по простому модулю является очень трудной задачей, если параметры являются достаточно большими.

Пример 2.1

Рассмотрим дискретный логарифм в группе , в котором б = 5 является примитивным элементом. Для в= 41 проблема дискретного логарифмирования это:

Найти положительные целые х такие, что

5^x ?41 mod 47

Даже для таких маленьких чисел вычисление х не есть однозначным. Используем грубую атаку, то есть переберём все возможные значения для х, мы получим решение х = 15.

На практике часто бывает желательно иметь DLP в группах с простым порядком, чтобы предотвратить атаки Похлига-Хеллмана.

Так как порядок группы равен p?1, который, очевидно, не простой, часто использует DLP в подгруппах из с простым порядком, а не в самой группе . Проиллюстрируем это на примере.

Пример 2.2.

Рассмотрим группу , которая имеет порядок 46. Подгруппы в имеют порядок 23, 2 и 1. б = 2 элемент в подгруппе с Z₂₃ элементами, а так как 23 - простое, б является примитивным элементом в подгруппе.

Возможно проблема дискретного логарифма дается для в= 36 (который также в подгруппе):

Найти натуральное число х, 1 ?x ?23, например,

2^x ?36 mod 47



С помощью грубой атаки, мы получим решение для х = 17.

1.2 Обобщенная проблема дискретного логарифма

Особенность, которая делает DLP особенно полезно в области криптографии, это то, что она ограничивается не только мультипликативной группой , р простое, но может быть определена по отношению к любым циклических группап.

Это называется обобщенной задачей дискретного логарифмирования (GDLP) и может быть сформулирована следующим образом.

Определение Обобщенная проблема дискретного логарифма

Дана конечная циклическая группа G с операцией ? и порядком р.

Рассмотрим примитивный элемент б? G и другой элемент в? G.

Задача дискретного логарифмирования заключается в том, чтобы найти х,

где 1 ?x ?n, такое, что:

в=б?б?…?б=б^x

Как и в случае с DLP в ,искомое число х должно существовать, так как это примтивній элемент, и, таким образом, каждый элемент из группы G может быть получен путем многократного применения групповой операции на б.

Важно понимать, что есть циклические группы, в которых DLP не является сложнім. Такие группы не могут быть использованы для открытого ключа криптосистемы с DLP не одностороннем порядке.

Рассмотрим следующий пример.

Пример 2.3.

В этот раз мы рассмотрим аддитивную группу целых чисел по простому модулю.

Например, если мы выбираем простое р = 11, G = (,+) является конечной циклической группой с примитивным элементом б= 2.

Порождает группу таким образом:

Мы стараемся сейчас решить DLP для элемента в= 3, то есть мы должны вычислить число 1 ?x ?11 таким образом, что

Вот как работает «атака» против DLP. Даже если операция группы адитивна, мы можем выразить отношения между б и в с помощью дискретного логарифма х в терминах умножения:

x·2 ? 3 mod 11

Для того чтобы решить для х, мы просто должны инвертировать примитивный элемент:

x ?2?1 3 mod 11

Используя, например, расширенный алгоритм Евклида, мы можем вычислить

2?1? 6 mod 11,

из чего:

x ?2?1 3 ?7 mod 11

Дискретный логарифм может быть верифицирован глядя на маленький столбик, предоставленный выше. Мы можем обобщить выше проделанный трюк для любой группой (,+) для произвольного n,и элементов б и в ? . Следовательно, мы приходим к выводу, что обобщенное DLP является вычислительно простой над . Причина, по которой DLP может быть решена здесь заключается в том, что мы имеем математические операции, которые не являются аддитивными в группе, а именно умножение и инверсия.

После этого контрпримера мы можем указать список групп, для которых применима Задача дискретного логарифмирования:

1. мультипликативная группа поля или ее подгруппа. Например, классический Обмен ключами Диффи-Хеллмана использует эту группу, но также шифрование Эль-Гамаля или Алгоритм цифровой подписи (DSA).

2. циклическая группа, образованная эллиптической кривой. Эллиптические криптосистемы кривая приводятся в главе 3. Они стали популярны в практике на протяжении последнего десятилетия.

3. мультипликативная группа поля Галуа GF (2^m) или ее подгруппа. Эти группы могут быть использованы полностью аналогично мультипликативных групп простых полей и схем, обмен ключами Диффи-Хеллмана могут быть реализованы с ними. Они не так популярны на практике, потому что атаки на них несколько более мощные, чем те, против Задач дискретного логарифмирования в . Следовательно Задачи дискретного логарифмирования более GF (2^m), требуют несколько более длинной передачи данных для обеспечения того же уровня безопасности, чем те, над

4. Гиперэллиптические кривые или алгебраические многообразия, которые можно рассматривать как обобщение эллиптических кривых. В настоящее время они редко используются на практике, но, в частности, гиперэллиптические кривые имеют некоторые преимущества, такие как короткие длины операндов.

1.3 Атака на Задачи дискретного логарифма

Рассмотрим алгоритм вычисления дискретных логарифмов с помощью метода Шенкса (метод больших и малых шагов).

Метод Шенкса.

Идея основана на представлении дискретного логарифма x = log_б в в двузначном виде:

x = xg m+xb для 0 ?xg,xb <m.

Выбирается значение

.

Теперь мы можем записать дискретный логарифм в виде

что приводит к

Идея алгоритма заключается в поиске решения (xg,xb)для уравнения



,

и что второе уравнение может быть представлено через первое.

В первой фазе алгоритма мы вычисляем и храним все значения xb,

где 0? xb <m. Это малый шаг, который требует

m?v ^-| G |

шагов (операция группы) и должен хранить

m ? v| G |

группы элементов.

На фазе больших шагов алгоритм проверяет все xg в диапазоне

0 ? xg < m

выполняется ли условие заполнения:

Хранится б xb, которая рассчитывается на фазе малых шагов. В случае совпадения, т.е.,

для некоторой пары , дискретного логарифма дается

Метод Шенкса требует вычислительных шагов и такое же количество памяти.

В группе порядка 2⁸⁰, злоумышленнику необходимо приблизительно криптосистем с открытым ключом на основе дискретного логарифма проблемы примерно 2⁴⁰ = v2⁸⁰ вычислений и ячеек памяти. Таким образом, для того, чтобы получить атаки общей сложностью 2⁸⁰, группа должна быть, по меньшей мере | G | ? 2¹⁶⁰ порядка. В случае групп G = , выбирать простое р следует, таким образом, чтобы его длина была по крайней мере 160 бит.

Пример 2.4.

y= (18, 5, 97)

p=97, g=5, x=18

1. Выбрать числа k и m такое, что k*m>p

k=m=10

2. Построить ряды

x, xg, xg², …, xg^m-1: 18, 90, 62, 19, 95, 87, 47, 41, 11, 55

g^m, g^2m, …, g^{km :} 53, ⁹³, 79. 16, 72, 33, 3, 62

3. Найти совпадения

xgⁱ=g^im (mod p)

i= 8, j=2

4. Вычислить

y=im-j

y=80-2=78



Мы стараемся усложнить задачу дискретного логарифмирования и поэтому рассмотрим криптографию на эллиптических кривых.

Почему эта задача сложная?

Группа - циклическая и поэтому там относительно легко найти примитивный корень. Группа точек на эллиптической кривой, вообще говоря, не циклическая, и мы не можем определить количество первообразных корней. Не зная разложение этой группы в прямое разложение циклических, нам трудно находить элементы максимального порядка.

Мы можем побеспокоится, чтобы выбранная нами точка на эллиптической кривой имела высокий порядок, и тогда задача дискретного логарифмирования на эллиптической кривой описывается так:

берётся точка P этой кривой, порядок которой достаточно большой и для выбранного n натурального вычисляем точку nP, которая будет равна

P+P+P+..,

таким образом получаем точку Q. И теперь по P и Q требуется опреедлить n.

Поэтому опишем задачу сложения точек на эллиптической кривой над конечным полем.

Но сначала изложим теорию эллиптических кривых (По Вейерштрассу).



2. Эллиптические кривые

2.1 Определение эллиптических кривых

Эллиптическая криптография построена на предположении о сложности решения задачи дискретного логарифмирования над полем точек эллиптической кривой.

Основное преимущество «эллиптики» перед классической асимметричной криптографией заключается в гораздо меньших размерах ключей. Объясняется это тем, что для классической задачи дискретного логарифмирования существуют так называемые субэкспоненциальные алгоритмы решения, имеющие следующую вычислительную сложность

.

Поэтому для достижения стойкости порядка 2⁸⁰ необходимо чтобы число p имело размер в 1024 бит.

Для задачи дискретного логарифмирования над точками эллиптической кривой субэкспоненциальных алгоритмов найдено не было. Наиболее быстрые алгоритмы для данного типа задач имеют сложность . Это позволяет использовать числа размерами всего 160 бит для достижения того же самого порога стойкости в 2⁸⁰.

Под «кривыми», мы имеем в виду множество точек (х, у ), которые есть решением уравнений. Например,точка (x = r,y = 0) удовлетворяет уравненияю окружности и, таким образом, в наборе. Точка (x =r/2,y=r/2) не есть решением многочлена

x2 +y2 = r2



и, таким образом, не набор элементов. Эллиптическая кривая это особый тип полиномиального уравнения. Для использования в криптографии, мы должны рассмотреть кривую не над полем вещественных чисел, а над конечным полем. Самый популярный выбор поле простых чисел GF (р, где вся арифметика выполняется по модулю простого числа р.

Определение Элиптических кривых.

Элиптические кривые над полем Zp, p > 3, это такой набор точек (x,y) ? Zp,который удовлетворяет

y2 ?x3 +a·x+b mod p (9.1)

Вместе с мнимой точкой бесконечности ?, где a,b ?Zp и условием

4·a3 +27·b2 = 0 mod p.

Определение эллиптической кривой требует, чтобы кривая была несингулярна. Геометрически говоря, это означает, что она не должна иметь самопересечений или вершины, что достигается, если дискриминант кривой ?16(4a3 +27b2) отличен от нуля.

Для использования в криптографии мы заинтересованы в изучении кривой над полем простых чисел, как и в определении. Однако, если мы наносим такую эллиптическую кривую над полем Zp, мы не получаем ничего отдаленно напоминающее кривую. Тем не менее, ничто не мешает нам принимать эллиптическое уравнение кривой и построения его на множестве действительных чисел.

Пример 3.1. На рисунке 3.1 построение эллиптической кривой

y2 = x3 ?3x+3



показано над полем вещественных чисел.

Отметим несколько вещей из построения этой эллиптической кривой.

Во-первых,эллиптическая кривая симметрична по отношению к оси абсцисс. Это непосредственно следует из того факта, что для всех значений xi, которые находятся на эллиптической кривой, оба

yi =v(x3 +a·xi +b)

и

y?_i = v(x ³i +a·xi +b)

есть решениями.

Во-вторых, есть одно пересечение с осью х. Это следует из того, что уравнение кубическое,если мы ищем решение для у = 0, которое имеет одно вещественное решение ( пересечение с осью х ) и два комплексных решений (которые не отображаются в построении). Есть также эллиптические кривые с трех пересечений с осью х.

Рис. 3.1 y2 = x3 ?3x+3 на R

Вернемся теперь к нашей первоначальной цели о нахождении кривой с большой циклической группой, которая необходима для построения задачи дискретного логарифмирования. Первая задача для нахождения этой группы делается, а именно определение набора элементов. В случае эллиптической кривой, элементами группы являются точки, которые удовлетворяют уравнение. Следующий вопрос : как мы определяем группу операций ?

криптографический информация дискретный логарифмирование

2.2 Группа операций на эллиптических кривых

Обозначим групповую операцию добавлением знака «+». «Добавление» означает, что, учитывая две точки и их координаты, скажем

P = ( x₁, y₁ )

и

Q = (x₂, y₂),

мы должны вычислить координаты третьей точки R такой, что:

Р + Q = R

( x₁, y₁ ) + ( x₂, y₂ ) = (х₃, у₃ )

Как мы увидим ниже, оказывается, что это операция сложения выглядит довольно спорно. К счастью, есть хорошая геометрическая интерпретация операции сложения, если мы рассмотрим кривую, определённую над полем вещественных чисел. Для этой геометрической интерпретации, мы должны различать два случая: сложение двух различных точек (названого точечное сложение) и сложение одной точки с собой же ( названного удвоенная точка ).

Точечное сложение P + Q.

Это случай, когда мы вычисляем

R = P + Q

и P ?Q. Построение происходит следующим образом: Рисуем линию, проходящую через P и Q и получаем третью точку пересечения между эллиптической кривой и прямой. Отражаем эту третью точку пересечения относительно оси х. Эта зеркальный точка есть, по определению,точка Р.

Рис. 3.2. Сложение точек на эллиптической кривой над полем вещественных чисел.

Рисунок 3.2. показывает точку сложения на эллиптической кривой над полем вещественных чисел.

Удвоенная точка P + P.

Это случай, когда мы вычисляем P + Q, но P = Q. Таким образом, мы можем написать

R = P + P = 2P.

нужен новый рисунок.

Мы проведем касательную линию через P и получим вторую точку пересечения этой линии и эллиптической кривой. Отобразим эту точку пересечения отночительно оси х. Полученная точка R и будет результатом сложения P и P. Рисунок 3.3. показывает Удвоенную точку для эллиптической кривой над полем вещественных чисел.



Рис. 3.3. Удвоенная точка на эллиптической кривой над вещественными числами

Вы можете задаться вопросом, почему для груп операций такие неспорные формы. Исторически, этот метод касательных-и-хорд был использован для построения третьей точки, если две точки уже были известны, используя только четыре стандартных алгебраических операций сложения, вычитания, умножения и деления. Оказывается, что если сложение точек на эллиптической кривой происходит именно таким образом,то множество точек также удовлетворяет большинству условий необходимости для групп, то есть, замкнутость, ассоциативность, существование единичного элемента и существование обратного.

Конечно, в криптосистеме мы не можем выполнить геометрические построения. Однако, применяя простую координатную геометрию, мы можем выразить геометрические с помощью аналитических выражений, т.е. формул. Как указано выше, эти формулы включают только четыре основных алгебраических операции. Эти операции могут быть выполнены в любом поле, не только над полем вещественных чисел. В частности, мы можем взять уравнение кривой сверху, но теперь мы рассмотрим его на премьер- полях GF (р ), а не над вещественными числами. Это дает следующие аналитические выражения для группы операций.

Точка сложения и удвоенная точка для Элиптических кривых.

x₃ = s2 -x₁ -x₂ mod p

y₃ = s(x₁?x₃)?y₁ mod p

где

, если P?Q

, если P=Q

Заметим, что параметр s представляет собой наклон линии, проходящей через P и Q в случае точка того или наклона касательной через точку Р в случае удвоения точки.

Даже если мы достигли значительного прогресса на пути к созданию конечной группы, мы еще не там. Одна вещь, которая еще отсутствует - идентичность (или нейтральный) элемент ?, что:

P + ? = P

для всех точек Р на эллиптической кривой. Оказывается, что нет ни одной точки (х, у), удовлетворяющей условию. Вместо этого мы определяем абстрактную точку на бесконечности как нейтральный элемент ?. Эту точку на бесконечности можно представить в виде точки, расположенной в сторону «плюс « бесконечности относително оси у или в направлении « минус» в бесконечности относительно оси у.

По определению группы, теперь мы можем найти обратной -Р любого элемента группы Р, как:

P + (- P) = ?.

Вопрос в том, как мы находим -P ? Если мы применим метод касательных и хорд сверху, то получается, чтообратная точки P = (xp,yp) является точка

?P = (xp,?yp),

т.е. точку, которая отражается относительно оси х.

Рис. 3.4. Обратная точки Р на эллиптической кривой

Рисунок 9.6 показывает точку Р вместе со своим обратным. Обратите внимание, что нахождение обратной к точке P = (xp,yp) теперь тривиально. Мы просто возьмём его отрицательные координаты у. В случае эллиптических кривых над полем простых чисел GF (р) (наиболее интересный случай в криптографии ), это легко достигается так как

?yp ? p?yp mod p,

следовательно,

?P = (xp,p?yp).

Теперь у нас определены все свойства группы для эллиптических кривых, мы посмотрим на пример для Групп операций.

Пример 3.2. Рассмотрим кривую на малом поле Z17:

E : y2 ?x3 +2x+2 mod 17

Мы хотим Удвоенную точку P = ( 5,1 ).

Для наглядности мы проверяем будет ли результат 2P = (6,3) на самом деле точкой на кривой, вставив координаты в уравнение кривой:

y2 ? x3 +2·x+2 mod 17

32 ? 63 +2·6+2 mod 17

9 = 230 ?9 mod 17

Говоря о точках на эллиптических кривых, стоит упомянуть Теорему Хассе,

Теорема Хассе об эллиптических кривых, также называемая границей Хассе, даёт оценку числа точек на эллиптической кривой над конечным полем, причём ограничивает значения как сверху, так и снизу. Эта гипотеза была первоначально выдвинута Эмилем Артином в его диссертации. Доказал её Хельмут Хассе в 1933 году и опубликовал в серии статей в 1936 году.

Теорема Хассе об эллиптических кривых утверждает, что количество точек на эллиптической кривой близко к числу элементов конечного поля:



что влечёт:

Обычно теоремой Хассе называют более точную оценку:

Пример 3.3

p	Ep	2vp	t=Ep-p-1
11	14	7,3	2
13	11	7,8	-3

2.3 Электронный обмен ключами Диффи-Хеллмана

Электронный обмен ключами Диффи-Хеллмана (DHKE), предложенный Уитфилдом Диффи Мартином Хеллманом 1976 году, был первым с асимметричной схемой опубликованной в открытой литературе. Два изобретателя были также под влиянием работы Ральфа Маркла. Она обеспечивает практическое решение ключевой проблемы распределения, то есть, это позволяет обеим сторонам получить общий секретный ключ, с помощью общения через небезопасный канал. В DHKE очень впечатляет применение задачи дискретного логарифмирования. Этот фундаментальный ключ соглашенный технически реализуется во многих открытых и коммерческих криптографических протоколах, таких как Secure Shell (SSH), Transport Layer Security (TLS), и Internet Protocol Security (IPSec).В Основная идея в том, что DHKE возведение в степень в Z?, p простое, является односторонней функцией, а возведение в степень является коммутативным, т.е.



k = ( x)y ?( y)x mod p

Значение k = ( x)y ?( y)x mod p это общий секрет, который может быть использован в качестве ключа сеанса между двумя сторонами.

Рассмотрим теперь, как электронный обмен ключами протокола Диффи-Хеллмана над Z? работает. В этом протоколе мы имеем две стороны, Алиса и Боб, которые хотели бы создать общий секретный ключ. Существует, возможно, довереная третья сторона, что правильно выбирает открытые параметры, которые необходимы для обмена ключами. Тем не менее, также возможно, что Алиса и Боб генерируют открытые параметры. Строго говоря, DHKE состоит из двух протоколов, протокол установки и основной протокол, который выполняет фактический обмен ключами. Протокол Установка состоит из следующих шагов:

Строим протокол Диффи-Хеллмана:

1. Выбераем большое простое р.

2. Выбераем число б ? {2,3,..., p-2}.

3. Опубликовать р и б.

Эти два значения иногда называют параметрами домена. Если Алиса и Боб оба знают параметры p и б вычисляя совместный ключ на стадии создания - они могут генерировать совместный секретный ключ к со следующим протоколом обмена ключами:

Вот доказательство того, что это удивительно простой протокол является правильным, то есть, что Алиса и Боб фактически вычислили kAB - ключа сеанса.

Доказательство.

Алиса вычислила Ba ?(бb)a ?бab mod p

Пока Боб вычислил Ab ?(бa)b ?бab mod p и, таким образом Алиса и Боб оба разделяют ключ сеанса kAB ? ab mod p. Ключ теперь может быть использованы для установления безопасной связи между Алисой и Бобом, например, kAB как ключ для симметричного алгоритма AES или 3DES.

Теперь мы посмотрим на простом примере с небольшими числами:

Пример 3.3.

Параметры Диффи-Хеллмана р = 29 и б = 2. Протокол протекает следующим образом:

Alice

Выбирает a = kpr,A = 5

A = kpub,A = 25 ?3 mod 29

Bob

Выбирает b = kpr,B = 12

B = kpub,B = 212 ?7 mod 29

Как видно, обе стороны вычислили значение kAB = 16, который может быть использован в качестве совместного секрета, например, в качестве ключа сеанса для симметричного шифрования.

Во время фактического протокола, мы в первую очередь должны выбрать приватные ключи a и b. Они должны вытекать из истинного генератора случайных чисел для того, чтобы помешать злоумышленнику угадать их.

То, что показано выше, является классическим протоколом обмена ключей Диффи-Хеллмана в группе Z *, где р простое. Протокол может быть обобщен, в частности, для групп эллиптических кривых. Это приводит к криптографии на эллиптических кривых, который стал очень популярным в асимметричных схемах на практике.

2.4 Обмен ключам Дифф-Хельмана на эллиптических кривых

В полной аналогии с обычной обмена ключами Дифф-Хальмана (DHKE ), теперь мы можем реализовать обмен ключами с использованием эллиптических кривых. Это называется обмена ключами эллиптических кривых Дифф-Хельмана или ECDH. Во-первых, мы должны согласовать параметры области, который подходит эллиптической кривой над которым мы можем работать, и примитивный элемент на этой кривой.

Параметры обасти ECDH

1. Выберите простое число р и эллиптической кривой

E : y2 ?x3 +a·x+b mod p

2. Выберите примитивный элемент P = (xP,yP)

Параметр р,кривая, заданная ее коэффициенты a, b, и примитивный элемент P являются доменными параметры.

Обратите внимание, что на практике найти подходящую эллиптическую кривую являетсяотносительно сложной задачей. Кривые должны показать определенные свойства, чтобы быть безопасным. Подробнее об этом будет ниже указанной. Фактический обмен ключами осуществляется так же, как это было сделано для обычного протокола Дифф-Хельмана.



Правильность расчётов легко доказать.

Доказательство:

Алиса считает пока Боб считает

aB = a(bP)

bA = b(aP).

Так как сложение точек ассоциативно (помните, что ассоциативность является одним из свойств группы ), вычисление с обеих сторон дают тот же результат, а именно точку

TAB = abP.

Как видно в протоколе, Алиса и Боб выбирают закрытые ключи a и b, соответственно, два большие целые числа. С помощью закрытых ключей генерируют свои соответствующие открытые ключи А и В, которые являются точками на кривой. Открытые ключи вычисляются путем умножения точки. Обе стороны меняются этими открытыми параметрами друг с другом. Совместный секрет TAB Затем вычисляется по Алиса и Боб, применяя вторую точку умножение с участием открытого ключа они получили и их собственный секретный параметр. Совместное секретное TAB можно использовать для получения ключа сеанса, например, в качестве входных данных для алгоритма AES. Заметим, что две координаты (xAB,yAB) не являются независимыми друг от друга : Зная xAB,другой координаты могут быть вычислены, просто вставив х значение в эллиптическое уравнение кривой. Таким образом, только один из двух координат следует использовать для вывода ключа сеанса. Давайте посмотрим на пример с небольшими числами:

Пример 3.5.

Рассмотрим ECDH со следующими параметрами обмена. Эллиптическая кривая y2 ?x3 +2x+2 mod 17, которая образует циклическую группу порядка #E = 19 базовая точка Р = (5,1 ). Протокол переходит следующим образом:

Два скалярных умножения. И каждый Алиса и Боб требуют алгоритм сложения и удвоеннх.

Один из координат совместной тайной TAB теперь может быть использован в качестве ключа сеанса. На практике, часто в координаты Х перемешиваются и затем используются в качестве симметричного ключа. Типически, не все биты необходимы. Например, в 160 -битной схеме ECC смешивание х-координаты с SHA- 1 приводит к 160- битовый выход из которой только 128 будут использоваться в качестве ключа AES.

2.5 Безопасность

Причина, по которой мы используем эллиптические кривые в том, что ECDLP имеет очень хорошие односторонние характеристики. Если злоумышленник Оскар хочет разорвать ECDH, он имеет следующую информацию : E, p, P, A, и B. Он хочет вычислить совместный секрет между Алисой и Бобом TAB = a·b·P. Это называется эллиптической задачей Диффи-Хеллмана( ECDHP ). Там, только один способ вычислить ECDHP, а именно решить любую из задач дискретных логарифмов:

a = logP A

или

b = logP B

Если эллиптическая кривая выбрана с осторожностью, самые известные нападения на ECDLP значительно слабее, чем лучшие алгоритмы решения задачи DL по модулю р, и лучших факторных алгоритмов, которые используются для RSA атак. Для тщательно отобранных эллиптических кривых единственный оставшийся нападения - обобщенные алгоритмы DL, то есть Шенкса карликовых и гигантских шагов и метод Полларда. Так число шагов, необходимых для такого нападения примерно равна квадратному корню из группы мощности,порядок группы, по крайней мере 2¹⁶⁰ должен быть использован. Согласно теореме Хассе, это требует, чтобы простое р используемое для эллиптической кривой должно быть примерно 160 -разрядное. Если мы атакуем такую группу с базовыми алгоритмами, мы должны совершить около шагов. Уровень безопасности 80 бит обеспечивает среднесрочную безопасности. На практике, эллиптические кривые длиной до 256 бит являются комплексными - обычно используются такие, которые обеспечивают уровень безопасности до 128 бит.

Следует подчеркнуть, что это безопасность достигается только при использовании криптографически сильных эллиптических кривых. Есть несколько семейств кривых, обладающих криптографически слабыми сторонами, например, суперсингулярным кривые. Их относительно легко обнаружить.

Криптосистемы на элиптических кривых (ECC-криптография) является новым членом трех семей с открытым ключом алгоритмов.ECC используется с середины 1980-х годов.

ECC обеспечивает такой же уровень безопасности, как RSA или логарифм дискретных систем с существенно более короткими операндами (примерно 160-256 бит против 1024-3072 бит). ЕСС базируется на основе обобщенной задачи дискретного логарифма, и, таким образом, DL- протоколы, такие как обмен ключами Диффи-Хеллмана также могут быть реализованы с помощью эллиптических кривых. Во многих случаях ECC имеет преимущества в производительности (меньше вычислений) и преимущества в записи (более короткие подписи и ключи) над RSA и Дискретным логарифмом (DL) схем.

Обмен документами в электронном виде возможен лишь в том случае, если обеспечивается их конфиденциальность, надежная защита от подделки или несанкционированного изменения, гарантирована доставка адресату, имеется возможность разрешения споров, связанных с фальсификацией сообщений и отказом от авторства.

Бурное развитие криптографические системы получили в годы первой и второй мировых войн. Начиная с послевоенного времени и по нынешний день появление вычислительных средств ускорило разработку и совершенствование криптографических методов.

В современном программном обеспечении (ПО) криптоалгоритмы широко применяются не только для задач шифрования данных, но и для аутентификации и проверки целостности. На сегодняшний день существуют хорошо известные и апробированные криптоалгоритмы (как с симметричными, так и несимметричными ключами), криптостойкость которых либо доказана математически, либо основана на необходимости решения математически сложной задачи (факторизации, дискретного логарифмирования и т.п.).



Список литературы

1. Understanding Cryptography.A Textbook for Students and Practitioners - Paar Christof, Pelzl Jan, 2010

2. Элементарное введение в эллиптическую криптографию. Протоколы криптографии на эллиптических кривых - Болотов А.А. и др., 2006

3. Основы криптографии. - Алфёров А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин

Размещено на Allbest.ru

...