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

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


 

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

34370. Оптимизация и экономическая оценка технологических процессов 23 KB
  Другими словами можно определить что расходные коэффициенты – это затраты на единицу продукции с учетом качества потребляемого сырья и стоимости. Эти затраты связаны с увеличением степени чистоты используемого сырья. характеризует сколько может получится целевого продукта с единицы сырья. К= m сырья m целевого продукта C1 C2 = Пц Пп В технологических процессах используется несколько видов сырья.
34371. Понятие технологического процесса, основные его параметры и характеристики 30 KB
  Производственный процесс это совокупность всех действий людей и орудий труда необходимых для изготовления или ремонта продукции. Технологический процесс это основная часть производственного процесса направленная на получения из сырья готовой продукции. Экономические: производительность выпускаемой продукции П = Q t кГ ч т ч; где Q количество произведенной продукции кГ т шт. 100 где Qф фактическое количество произведенной продукции кГ т шт.
34372. Динамика произв. затрат при развитии технол. процесса 55 KB
  Прошлого овеществленного труда Тп включающего в себя все затраты труда связанные с получением исходного для данной технологии продукта а также затраты на орудия труда используемые в анализируемом технологическом процессе; 2. Живого труда Тж включающего все затраты человеческого труда предусмотренные в анализируемом технологическом процессе на выпуск готовой продукции. Общие удельные затраты на единицу продукции представляющие собой сумму прошлого и живого труда Тс = Тп Тж min являются наиболее обобщенными технологическими...
34373. Структура технологического процесса 50 KB
  Структура технологического процесса. Любой технологический процесс можно рассматривать как систему более мелких технологических процессов или как часть более сложного техн. В структуре сложного техн. процесса можно выделить всегда элементарный техн.
34374. Основные варианты развития технологических процессов и их характеристика 23 KB
  элементов приводит к росту производительности живого труда за счет высвобождения человека и сокр. труда за счет увеличения доли прошлого труда что соотв. такое развитие процессов при котором увеличение производительности совокупного труда происходит при увеличении затрат прошлого труда за счет механизации и автоматизации вспом. за счет уменьшения как живого так и прошлого труда на единицу продукции.
34375. Закон рационалистического развития технологических процессов 24.5 KB
  развития технологического процесса происходит прямая замена живого труда прошлым. При этом каждое последующее увеличение производительности труда требует все больших затрат прошлого труда на единицу прироста производительности совокупного труда. Достигнутый уровень затрат прошлого труда это техн. Годовые затраты прошлого труда сумма годовых амортизационных отчислений от стоимости оборудования и всех остальных годовых затрат за исключением затрат на предмет труда обозначим через Фт руб год.
34377. Определения уровня технологического процесса 19.5 KB
  Уровень технологии – это показатель эффективности переноса прошлого труда на технологический процесс. Уровень технологии определяется произведением производительности прошлого и живого труда. Понятие уровень технологии – важная характеристика любого технологического процесса. Для расчета уровня технологии необходимо иметь зависимости Тж от Тп.
34378. Платёжный баланс, его роль, содержание и прогнозирование 60.5 KB
  Процентные ставки на международных рынках являются важным фактором определяющим чистые процентные поступления на текущий счет а вместе с процентными ставками на внутреннем рынке они заметно влияют на объем и направление потоков капитала. При прогнозировании важно учитывать сочетание прогнозного результата по текущему счету с допустимыми значениями притока капитала для покрытия дефицита. При прогнозировании финансового счета необходимо различать три основные категории: прямые инвестиции перемещения средне и долгосрочного капитала и...