Қолтаңба алгоритмі

Эль-Гамаль алгоритмінің протоколы

Эль-Гамаль цифрлық қолтаңбасы дискретті логарифм мәселесінің қиындығына негізделеді. Төменде кілт генерациялау, қолтаңба құру және қолтаңбаны тексеру кезеңдері жүйелі түрде берілген.

1) Кілттерді генерациялау

1

p үлкен жай санын кездейсоқ түрде таңдаймыз және Z_p^* тобынан туынды элемент ретінде g аламыз.
2

a құпия мәнін таңдаймыз: 1 < a < p − 1. Бұл мән ұзақ мерзімді құпия кілт ретінде қолданылады.
3

Ашық параметрді есептейміз: y = g^a (mod p).
4

Ашық кілт: (p, g, y), құпия кілт: a.

2) Қолтаңба құру алгоритмі

Қолтаңбамен қамтамасыз етілетін хабарлама m (plaintext түріндегі, еркін ұзындықты бинарлы тізбек) болсын. Әдетте алдымен хэш есептеліп, әрі қарай сол мән қолданылады.

Маңызды қағида

k — бір реттік кездейсоқ мән. Әр жаңа қолтаңба үшін жаңа k таңдалуы тиіс.

1

k санын таңдаймыз: 0 < k < p − 1 және gcd(k, p − 1) = 1. Бұл мән маска рөлін атқарады және бір-ақ рет қолданылады.
2

k мәнінің кері элементін есептейміз: k⁻¹ (mod p − 1). Бұл мән (егер k дұрыс таңдалмаса немесе ашылып қалса) қолтаңбаның қауіпсіздігіне тікелей әсер етеді.
3

r есептейміз: r = g^k (mod p).
4

s есептейміз: s = k⁻¹(m − a·r) (mod p − 1).
5

Қолтаңба нәтижесі: (r, s) жұбы.

3) Қолтаңбаны тексеру алгоритмі

Қолтаңбаны тексеру ашық кілт (p, g, y) арқылы орындалады. Теңдік орындалған жағдайда ғана қолтаңба дұрыс деп қабылданады.

Есептеу

u = y^r · r^s (mod p)
v = g^m (mod p)

Шешім

Егер u = v теңдігі орындалса, онда қолтаңба қабылданады. Кері жағдайда — қабылданбайды.

Сандық мысал

Төмендегі мысал Эль-Гамаль қолтаңбасының қалай құрылатынын және тексерілетінін көрсетеді.

Бастапқы параметрлер

p: 2357
g (генератор): 2
Құпия кілт a: 1751
y = g^a (mod p): 1185

Ашық кілт: (2357, 2, 1185) (мәтінде ашық кілт жолында қате кетіп, a мәні көрсетілген; дұрысы — y).

Қолтаңба құру

Бір реттік мән ретінде k = 1529 таңдаймыз, сонда:

r = 1490
k⁻¹ = 245 (mod 2356)
s = 245 · (1463 − 1751 · 1490) ≡ 1777 (mod 2356)

Қолтаңба: (r, s) = (1490, 1777)

Тексеру нәтижесі

Тексеру кезінде есептеулер жүргізіліп, екі жақтың мәндері сәйкес келетіні көрсетіледі:

Сол жақ

1185¹⁴⁹⁰ · 1490¹⁷⁷⁷ ≡ 1072

(mod 2357)

Оң жақ

2¹⁴⁶³ ≡ 1072

(mod 2357)

Екі нәтиже бірдей болғандықтан, қолтаңба қабылданады.