42015

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

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

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

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

Русский

2013-10-27

212 KB

49 чел.

Лабораторная работа № 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

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


 

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

23629. СКОЛЬКО НА ПЛАНЕТЕ ЯЗЫКОВ 808 KB
  Сканировал и проверил Илья Франк СКОЛЬКО НА ПЛАНЕТЕ ЯЗЫКОВ На скольких языках говорят люди населяющие планету Ответить на этот вопрос казалось бы не так уж трудно. Но почему тогда разные ученые называют различное число языков планеты: одни говорят о 20 тысячах другие о 10 тысячах третьи о 5 тысячах а некоторые лингвисты полагают что население нашей планеты изъясняется всегонавсего на 2 тысячах языках. Но можно ли провести границу при исчислении количества языков между языком и его диалектом Мы знаем что на Юге России говорят не...
23630. ЯЗЫКОВОЕ РОДСТВО СЛАВЯНСКИХ НАРОДОВ 346 KB
  литовский белорус. белорусский нем. старославянский древнепрус. древнепрусский укр.
23631. Философия языка А.Ф.Лосева: типологический лик, генетические истоки, основные идеи и подходы 58 KB
  если слово не действенно и имя не реально. И вот рассмотреть его как имя я и дерзаю. имя. Имя откровение личности.
23632. Теория языка вчера и сегодня 2.61 MB
  Теория языка вчера и сегодня Глава I. Модель языка как органона а формы существования конкретных языковых явлений 3. Знаковая природа языка в модель структуры языка 4. Система sf языкового типа d понятие языка и его признаки Глава II.
23633. Закон «Об обеспечении единства измерений». Государственная система обеспечения единства измерений в стране 19.86 KB
  Государственная система обеспечения единства измерений (ГСИ) - государственное управление субъектами, нормами, средствами и видами деятельности по обеспечению заданного уровня единства измерений в стране...
23634. МОРФОНОЛОГИЯ В ОПИСАНИИ ЯЗЫКОВ 433.5 KB
  Таково например противопоставление классов сильных и слабых глаголов в германских языках. например противопоставление сильных и слабых глаголов в германских языках противопоставление процессов словообразования происходящих с исконными и неисконными элементами лексики в современном английском языке разграничение первичных и вторичных основ типа другдружитьдрузья в русском языке и т. Из пяти русских глаголов на оть только один молоть маркирован морфонологически ср. Причина чередования лежит по нашему мнению в предотвращении...
23635. ЛАОКООН, ИЛИ О ГРАНИЦАХ ЖИВОПИСИ И ПОЭЗИИ 676.5 KB
  Поглощенные этой мыслью они самоуверенным тоном произносят самые поверхностные приговоры считая главными недостатками в произведениях художников и поэтов отклонения друг от друга этих двух родов искусства и большую склонность 386 поэта или художника к тому или другому роду искусства в зависимости от собственного вкуса. Как сильны эти выражения гнева скорби и отчаяния если даже поэтическое выражение их заставляло содрогаться театр Третье действие этой трагедии находят вообще несравненно более кратким чем остальные. Легко раненная Венера...