42015

Ассиметричная криптосистема Эль-Гамаля. Криптосистемы, основанные на эллиптических кривых

Лабораторная работа

Математика и математический анализ

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

Русский

2013-10-27

212 KB

51 чел.

Лабораторная работа № 3.3

Тема: Ассиметричная криптосистема Эль-Гамаля. Криптосистемы, основанные на эллиптических кривых.

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

Задание

  1.  Рассмотреть общие математические принципы организации процедуры шифрования/дешифрования при использовании метода Эльт-Гамаля.
  2.  Рассмотреть принцип организации опроцедуры шифрования и обмена ключами с использованием эллиптических кривых.
  3.  Реализовать программно алгоритм Эль-Гамаля. Провести шифрование открытого текста, выбранного согласно варианту, указанному преподавателем, и его последующее восстановление.
  4.  Реализовать программно алгоритм шифрования с использованием эллиптических кривых. Провести шифрование открытого текста, выбранного согласно варианту, указанному преподавателем, и его последующее восстановление.
  5.  Рассмотрите эллиптическую кривую Ер(a,b). Определите все точки Ер(a,b). 

Значения параметров a, b, р выбрать согласно варианту, указанному преподавателем.

4. Рассмотрите схему Эль-Гамаля с общим простым числом q и первообразным корнем а. Если пользователь В имеет открытый ключ YB, а пользователь А выбирает случайное число k, то каким будет расшифрованный текст М?

Значения параметров a, YB, q, k выбрать согласно варианту, указанному преподавателем.

Теоретические сведения

Криптосистема Ель-Гамаля

Формирование ключей

Простейший алгоритм шифрования, основывающийся на дискретном логарифмировании, — это криптосистема Эль-Гамаля. В отличие от RSA в алгоритме Эль-Гамаля существуют некоторые открытые параметры, которые могут быть использованы большим числом пользователей. Они называются параметрами домена(ключа)и выглядят следующим образом:

  1.  Выбирается р — большое простое число, т. е. число, насчитывающее около 1024 битов.
  2.  Выбирается g – первообразный корень р.

Напомним, что если число а является первообразным корнем простого числа b, то все числа

а mod b,  а2 mod b, …, ар-1 mod b

должны быть разными и представлять все целые числа от 1 до р – 1 в некоторой перестановке.

После выбора параметров домена определяют открытый и секретный ключи. Секретным ключом может априори быть любое натуральное число x.

Для определения открытого ключа вычисляется число у по следующей формуле:

у = gx(mod p).

Группа чисел (p,g,y) – открытый ключ.

Шифрование

Сообщение в этой системе представляется как элемент m. Для его шифрования поступают следующим образом:

  1.  генерируют случайный эфемерный ключ k, что 1  kp – 1;
  2.  вычисляют C1 = Gk;
  3.  находят С2 = m×yk;
  4.  выдают получившийся шифротекст в виде пары С = (C1,С2).

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

Дешифрование

Чтобы расшифровать пару данных С = (C1,C2), производят следующие преобразования:

C2/C1x = (m×yk)/gkx = (m×gkx)/gkx =m.

Разберем небольшой пример, выбрав сначала параметры домена.

Пусть q = 101, р = 809 и g = 3.

В качестве пары открытого и секретного ключа выберем

x = 68 и y = gx = 368 = 65 (mod p).

Допустим, нам нужно зашифровать сообщение, численное представление которого равно т = 100. Поступаем следующим образом.

  1.  Генерируем случайный эфемерный ключ k = 89;
  2.  Находим C1 = gk = 389 = 345 (mod p).
  3.  Получаем С2 = m×yk = 100 × 6589 = 517 (mod p).
  4.  Отправляем шифротекст С = (345,517).

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

C2/C1x = 517/34568 = 100.

Последнее равенство получается чуть более сложно, чем в вещественных числах: сначала число 345 возводится в степень 68 по модулю 809, вычисляется мультипликативный обратный к результату по этому же модулю, а затем найденный обратный умножается на 517.

На рис. 2 проиллюстрирован принцип шифрования/дешифрования методом Эль-Гамаля.

Рис. 2. Криптосистема Эль-Гамаля

Криптография с использованием эллиптических кривых

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

Большинство продуктов и стандартов, в которых для шифрования и цифровых подписей применяется метод криптографии с открытым ключом, базируется на алгоритме RSA. Но число битов ключа, необходимое для надежной защиты RSA, за последние годы резко возросло, что обусловило соответствующий рост загрузки систем в npиложениях, использующих RSА. Это породило множество проблем, особенно для узлов, специaлизирующихcя на электронной коммерции, где требуется защита большого числа транзакций. В начале 2000-х годов появился подход, который может конкурировать с RSA –  это криптография на основе эллиптических кривых (ЕСС - Elliptic сurvе cryptography). Привлекательность подхода на основе эллиптических кривых в сравнении с RSA заключается в том,  что с использованием эллиптических кривых обеспечивается эквивалентная защита при очень небольшом числе разрядов, вследствие чего уменьшается загрузка процессора.. В то же время, хотя теория криптографии с использованием эллиптических кривых у всех на слуху уже в течении достаточно долгого времени, только недавно начали появляться продукты, представляющие интерес для криптоанализа на предмет наличия соответствующих слабых мест. Таким образом, степень доверия к методам криnтографии с использованием эллиптических кривых еще не настолько высока, как степень доверия к RSA.

Эллиптические кривые - это не эллипсы. Они так называются просто потому, что описываются кубическими уравнениями, теми которые используются для вычисления кривой эллипса. В общем случае кубические уравиения для эллиптических кривых имеют вид

у2 + аху + bу = х3 + сх2 + dx + е,

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

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

1. Объект О выступает в роли нулевого элемента при сложения. Так, О = -О, и для любой точки Р на эллиптической кривой Р + О = Р.

2. Вертикальная линия пересекает кривую в двух точках с одной и той же координатой х скажем, Р1 = (х,у) и Р2 = (х, -у). Эта линия пересекает кривую и в бесконечной точке, поэтому Р1 + Р2 + О = О и Р1 = Р2.  Таким образом, точкой со знаком "минус" является точка с той же координатой х, но с противоположной по знаку координатой у (Рис. 1,с).

З. Чтобы сложить две точки Q и R с разными х, проведите через эти точки прямую и найдите третью точку пересечения Р1, этой прямой с эллиптической кривой. Легко показать, что существует только одна такая точка (если прямая не является касательной к кривой в какой-либо из точек Q и R – в таком случае нужно положить Р1 = Q или Р1 = R, соответственно). Затем нужно воспользоваться тем, что Q + R + Р1 = О, следовательно Q + R= = -Р1 (Рис. 1,а).

4. Чтобы удвоить точку Q, проведите касательную к точке Q и найдите другую точку пересечения S. Тогда Q + Q = 2Q = -S (Рис. 1,b).

Вышеприведенные правила сложения подчиняются всем обычным свойствам сложения, например коммутативному и ассоциативному законам. Умножение точки Р эллиптической кривой на положительное целое число k тоже определено - это сумма k копий точки Р. Так, 2Р = Р + Р, 3Р = Р + Р.

Рис. 1. Примеры эллиптических кривых

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

З + 27b2 (mod р) ≠ 0.

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

 y2 = x3 + ax + b (mod p)                                                           (1)

вместе с точкой в бесконечности О.

Например, пусть р = 23. Рассмотрим эллиптическую кривую y2 = x3 + x + 1. В этом случае а = b = 1 и мы имеем 4 × 13 + 27 × l2 (mоd 23) = 8 ≠ 0, что удовлетворяет условиям эллиптической группы по модулю 23.

Для эллиптической группы рассматриваются только целые значения от (0,0) до (р,р) в квадрантe неотрицательных чисел, удовлетворяющих уравнению по модулю р. В таблице 1 представлены точки, являющиеся элементами Е23(1,1), отличные от (0,0). В 06щем cлyчае список точек создается по следующим правилам:

1. Для каждого такого значения х, что 0 ≤ х < р , вычисляется x3 + ax + b (mod p).

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

Таблица 1. Точки Е23(1,1) на эллиптической кривой

(0,1)

(6,4)

(12,10)

(0,22)

(6,19)

(13,7)

(1,7)

(7,11)

(13,6)

(0,16)

(7,12)

(17,3)

(3,10)

(9,16)

(19,5)

(3,13)

(11,3)

(17,20)

(4,0)

(11,20)

(18,3)

(5,4)

(12,4)

(18,20)

(5,19)

(9,7)

(19,18)

Правила для сложения в Ер(а,b) соответствуют следующим математическим приемам:

1. Р + 0 = Р.

2. Если P = (x,y), то Р + (х,-у) = 0. Точка (х,-у) является отрицательным значением точки Р обозначается . Заметим, что (х,-у) лежит на эллиптической кривой и принадлежит Ep(a,b). Например, в случае Е23(1, 1) для Р = (13, 7) мы имеем –Р = (13,-7). Но -7 mod 23 = 16. Таким образом, = (13, 16), что мы и видим в таблице1.

3. Если Р = (x1,y1) и Q = (x2,y2), где Р ≠ Q, то Р + Q = (x3,y3) определяется в соответствии с правилами:

x3 = λ2 – x1 – x2 (mod p),

y3 = λ(x1 – x3) – y1 (mod p),

 

где 1) (y2 – y1)/(x2 – x1), если P ≠ Q; 2) (3x12 + a)/2y1, если P = Q.

Рассмотрим пример. Пусть Р = (3, 10) и Q = (9, 7). Тогда

λ = (7 – 10)/(9 – 3) = -3/6 = -1/2 = 11 mod 23,

x3 = 112 – 3 – 9 = 109 – 17 mod 23,

y3 = 11(3 – (-6)) – 10 = 89 = 20 mod 23.

Поэтому P + Q = (17,20). Чтобы найти , найдем

λ = (3(32)+1)/(2×10) = 5/20 = 1/4 = 6 mod 23,

x3 = 62 – 3 – 9 = 30 = 17 mod 23,

y3 = 6(3 – 7) – 10 = -34 = 12 mod 23.

и поэтому = (7,12).

Обмен ключами

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

Рассмотрим уравнение Q = kP, где Q,P принадлежат Ер(а,b) и k < р. Относительно легко вычислить Q данным k и Р, но относительно трудно определить k, имея Q и Р.

Обмен ключами с использованием эллиптических кривых может быть выполнен следующим образом. Сначала выбирается простое число р порядка 2180 и параметры а и b для эллиптической кривой в уравнении (1). Это задает эллиптическую группу точек Ер(а,b). Затем в Ер(а,b) выбирается генерирующая точка точка G = (х1, у1). При выборе G важно, чтобы наименьшее значение n при котором nG = О, оказалось очень большим простым числом. Параметры Ер(а,b) и G криптосистемы являются параметрами, известными всем участникам.

Обмен ключами между пользователями А и В можно провести по следующей схеме:

1. Сторона А выбирает целое число nA, меньше n. Это число будет ключом участника А. Затем участник А генерирует открытый ключ РА = nА × G. Открытый ключ представляет собой некоторую точку из Ер(а,b) .

2. Точно так же участник В выбирает личный ключ nВ и вычисляет открытый ключ Рв.

3. Участник А генерирует секретный ключ К = nА × Рв, а участник В генерирует секретный ключ К = nВ × РА.

Две формулы дают один и тот же результат. поскольку

nА × Рв = nА × (nВ × G) = nВ × (nА × G) == nВ × РА.

Чтобы взломать эту схему, противник должен будет вычислить k по данным G и kG, что предполагается трудным делом. .

В качестве примера  возьмем р = 211, Ер(0,-4) и G = (2,2). Можно подсчитать, что 241G = О. Личным ключом пользователя А является nА = 121, поэтому открытым ключом участника А будет РА = 121(2,2) = (115, 48). Личным ключом пользователя В является nВ = =203 , поэтому открытым ключом участника В будет 203(2,2) = (130,203). Общим секретным ключом является 121(130,203) = 203(115,48) = (161,169).

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

Шифрование/дешифрование с использованием эллиптических кривых

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

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

1. Абонент В выбирает эллиптическую группу Eр (a,b).

2. Абонент В выбирает генерирующую точку на кривой G (x1,y1).

3. Абонент В выбирает целое число nВ – его личный ключ.

4. Абонент В вычисляет свой открытый ключ: РВ  = nВ × G. Обратите внимание: умножение здесь означает, что многократное сложение и определяется как раньше.

Секретный и открытый ключ абонента А вычисляются аналогичным образом.

Для того, чтобы отправить абоненту В сообщение Рm, пользователь А выбирает случайное положительное целое число k и вычисляет шифрованный текст Сm, состоящий из пары точек

Сm = {kG, Рm +kPВ}.

Заметим, что сторона А использует открытый ключ стороны Б: Рв. Чтобы дешифровать этот шифрованный текст, В умножает первую точку в паре на секретный ключ В и вычитает результат из второй точки:

Рm + kPB - nB(kG) = Рm + k(nBG) - nB(kG) = Рm.

Пользователь А замаскировал сообщение Рm с помощью добавления к нему kPB. Никто, кроме этого пользователя, не знает значения k, поэтому, хотя РВ и является открытым ключом, никто не сможет убрать маску kPB. Однако пользователь А включает  а сообщение и "подсказку", которой будет достаточно, чтобы убрать маску тому, кто имеет личный ключ nВ. Злоумышленнику для восстановления сообщения придется вычислить k по данным G и kG, что представляется трудной задачей.

В качестве примера подобного шифрования рассмотрим случай р = 751, Ер(-1, 188) (что соответствует кривой у2 = х3 – х + 188) и G = (0, 376). Предположим, что пользователь А собирается отправить пользователю В сообщение, которое кодируется эллиптической точкой Рm = (562, 201), и что пользователь А выбирает случайное число k = 386. Открытым ключом В является Рв = (201, 5) . Мы, имеем 386(0, 376) = (676,558) и (562,201) + 386(201,5) = (385,328). Таким образом, пользователь А должен послать шифрованный текст {(676,558), (385,328)}.

Принцип шифрования/дешифрования сообщений с использованием метода эллиптических кривых показан на рис. 3.

Рис. 3. Шифрование/дешифрование данных с использованием эллиптических кривых

Контрольные вопросы

  1.  Напишите общий вид уравнения для эллиптических кривых.
  2.  Что такое несобственный элемент эллиптической кривой?
  3.  Перечислите правила операций сложения над точками эллиптической кривой.
  4.  Что такое эллиптическая группа?
  5.  Согласно каким правилам производится сложения точек эллиптической группы?
  6.  Опишите процедуру обмена ключами с использованием эллиптических кривых.
  7.  Опишите принцип шифрования с использованием эллиптических кривых.
  8.  Чем обеспечивается криптостойкость методов шифрования, основанных на использовании эллиптических кривых.
  9.  Опишите принцип шифрования с помощью схемы Эль –Гамаля.
  10.  На чем основана криптостойкость алгоритма Эль-Гамаля?

Варианты практических заданий

№ варианта

Задание 3

Задание 4

Задание 5

a

b

p

a

q

YB

k

1

сердцебиение

2

скейтбордист

3

стабильность

4

термостатика

5

упадничество

6

факторизация

7

хронометрист

8

цветоводство

9

шунтирование

10

эксплуататор

11

юрисконсульт

12

абитуриентка

13

балансировка

14

вегетарианец

15

глобальность

16

декомпрессия

17

здравомыслие

18

интерполятор

19

калорийность

20

легитимность

21

магнитосфера

22

нормирование

23

общественник

24

паритетность

25

самозагрузка


 

А также другие работы, которые могут Вас заинтересовать

37293. Социология. Шпаргалка 315 KB
  Принято считать что объектом социологического познания является вся совокупность свойств связей и отношений которые носят название социальных. В марксизме предметом социологического исследования является научное изучение общества как социальной системы и составляющих его структурных элементов личностей социальных обшностсй социальных институтов. Она предстает как система взаимосвязанных представлений понятий взглядов теорий о социальных процессах разных уровней жизнедеятельность отдельных людей социальных групп или...
37295. Проект информационной системы Автоматизированная информационная система предприятия по изготовлению корпусной мебели «АИС Корпусная мебель» 2.91 MB
  Описание потоков данных и бизнес процессов. Описание потоков данных и бизнес процессов. Функциональный блок Изготовление частей изделия получает в качестве входных данных согласованный проект в управлении участвуют характеристики материалов методики изготовления ГОСТы по изготовлению мебели а также согласованный проект. В качестве выходных данных выступают части изделия готовые к сборке Рисунок 1.
37297. МЕТОД ПРОЕКЦИЙ. Центральные проекции и их основные свойства. 902.5 KB
  Перпендикуляр к плоскости перпендикулярен любой прямой проведенной в этой плоскости. Плоскости перпендикулярны если прямая принадлежащая одной плоскости перпендикулярна другой плоскости. Если прямая линия параллельна прямой лежащей в плоскости то она параллельна этой плоскости.
37298. Теория обучения и воспитания 481 KB
  Методические рекомендации и план освоения учебной дисциплины 13 Описание учебнометодического комплекса дисциплины Теория обучения и воспитания 15 Виды учебной работы 16 Тематический план курса 16 8. Задачи: Вооружить студентов системой научных знаний о сущности и особенностях процессов обучения воспитания и развития; Раскрыть потенциалы образовательной среды и ее возможные модификации для обеспечения качества образования; Активизировать развитие у студентов профессиональнопедагогического мышления умения видеть и анализировать...
37299. Перехідна характеристика об’єкта керування 101.5 KB
  Користуючись теоремою розкладення та стандартною функцією перетворення Лапласа розрахувати та побудувати перехідні характеристики об'єкта керування. Перехідну характеристику ht будуємо за допомогою стандартної операції зворотного перетворення Лапласа програмного середовища Mthcd. Спочатку знаходимо перетворення за Лапласом вихідної величини hp Задаємо початкові умови: Знайдемо перехідну функцію за допомогою теореми розкладення. Спочатку знаходимо перетворення за Лапласом...
37300. Общие требования к курсовой работе (для юридических дисциплин) 190 KB
  Структура и содержание курсовой работы Тема курсовой работы избирается студентом исходя из его интересов и согласовывается с научным руководителем. После утверждения темы студентом разрабатывается план работы который также должен быть согласован с научным руководителем. В дальнейшем при написании работы студенту рекомендуется обсуждать с руководителем наиболее принципиальные и спорные вопросы темы. Структура и содержание курсовой работы должны в полной мере раскрывать избранную тему.