Алгоритм ЭЦП на основе сложности дискретного логарифмирования

@andrewromanov · Регистрация: 07.10.2014

Студворк — интернет-сервис помощи студентам

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

Подскажите как необходимо высчитывать значения k и g, чтобы получать значения, аналогичные представленным в примере.
Скриншот примера -

Алгоритм ЭЦП на основе сложности дискретного логарифмирования

Учебник - Молдовян, Практикум по криптосистемам с открытым ключом

@grizlik78 · 12.06.2017, 21:56

Формулы для k и g перепутаны, но значения правильные.
Вот программка на python, выполняющая эти вычисления:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from __future__ import print_function
 
p = 1188242948802635102242772106637989280357
a = 682502200821353544223897742429626534895
gamma = 187266130527359358103409790533
delta = 1000000000000000003
x = 12345678900987654321
 
y = pow(a, x, p)
print('y =', y)
H = 11223344556677889900
U = 13894564231549754238457865456
Z = pow(a, U, p)
print('Z =', Z)
d = (1 + gamma) // 2
k = ((U + x*Z + (H*Z) % delta) * d) % gamma
g = ((U - x*Z - (H*Z) % delta) * d) % gamma
print('k =', k)
print('g =', g)
S = pow(a, g, p)
print('S =', S)

результат работы:

Code
1
2
3
4
5
y = 515195030626449857135211347072944115270
Z = 647016984661564319416569408164688002775
k = 68742013608792151040356901280
g = 132418681150116961301510754709
S = 2512740207764180842719228564280308315

@andrewromanov · 13.06.2017, 10:00 **[ТС]**

Сообщение от grizlik78

Формулы для k и g перепутаны, но значения правильные.
Вот программка на python, выполняющая эти вычисления:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from __future__ import print_function
 
p = 1188242948802635102242772106637989280357
a = 682502200821353544223897742429626534895
gamma = 187266130527359358103409790533
delta = 1000000000000000003
x = 12345678900987654321
 
y = pow(a, x, p)
print('y =', y)
H = 11223344556677889900
U = 13894564231549754238457865456
Z = pow(a, U, p)
print('Z =', Z)
d = (1 + gamma) // 2
k = ((U + x*Z + (H*Z) % delta) * d) % gamma
g = ((U - x*Z - (H*Z) % delta) * d) % gamma
print('k =', k)
print('g =', g)
S = pow(a, g, p)
print('S =', S)

результат работы:

Code
1
2
3
4
5
y = 515195030626449857135211347072944115270
Z = 647016984661564319416569408164688002775
k = 68742013608792151040356901280
g = 132418681150116961301510754709
S = 2512740207764180842719228564280308315

А с проверкой подписи получается тоже что-то не так?

Python
1
2
compare1 = (S * y^((a^k * S) % p) * a^(((H * ((a^k * S) % p))) % delta)) % p
compare2 = a ^ k;

compare1 = 750481722866102561102226893656246942165
compare2 = 682502200845519936091824910284307720783

@grizlik78 · 13.06.2017, 10:42

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

Python
1
2
3
akS = pow(a, k, p) * S % p
compare1 = (S * pow(y, akS, p) * pow(a, H * akS % delta, p)) % p
compare2 = pow(a, k, p)

@andrewromanov · 14.06.2017, 11:03 **[ТС]**

grizlik78, а можете еще подсказать, как будет правильно в таком случае?
[IMG]http://i.**********/3CZ7HT5.png[/IMG]

Python
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
26
27
28
29
30
31
32
33
p = 1188242948802635102242772106637989280357
a = 682502200821353544223897742429626534895
gamma = 187266130527359358103409790533
delta = 1000000000000000003
x = 12345678900987654321
 
y = pow(a, x, p)
print('y =', y)
H = 11223344556677889900
U = 13894564231549754238457865456
Z = pow(a, U, p)
print('Z =', Z)
#k = ((U + x*Z + (H*Z) % delta) * d) % gamma
#g = ((U - x*Z - (H*Z) % delta) * d) % gamma
 
d = (1 + gamma) // x
k = ((Z - U) * d) % gamma
d = (1 + gamma) // (Z - U)
g = ((U * x) * d) % gamma
 
print('k =', k)
print('g =', g)
S = pow(a, g, p)
print('S =', S)
 
#akS = pow(a, k, p) * S % p
#compare1 = (S * pow(y, akS, p) * pow(a, H * akS % delta, p)) % p
#compare2 = pow(a, k, p)
compare1 = pow(S*y, k, p)
compare2 = pow(a, pow(S, k, p), p)
 
print('compare1 =', compare1)
print('compare2 =', compare2)

y = 515195030626449857135211347072944115270
Z = 647016984661564319416569408164688002775
k = 69723436066911832210851543645
g = 0
S = 1
compare1 = 617813055556188823797630213346059079690
compare2 = 682502200821353544223897742429626534895

@grizlik78 · 14.06.2017, 15:28

Да, нужно было, конечно пояснить. Деление на число по модулю заменяется умножением на мультипликативно-обратный элемент, то есть на такое число, которое при умножение на исходное даёт единицу в результате приведения по модулю. Формула, которую я использовал, справедлива только для двойки. В общем случае обратный элемент можно найти с помощью расширенного алгоритма Евклида. Готовую реализацию можно взять, например, из модуля gmpy2.

Python
1
2
3
4
5
6
from gmpy2 import invert
 
d = int(invert(x, gamma))
k = ((Z - U) * d) % gamma
d = int(invert(Z - U, gamma))
g = ((U * x) * d) % gamma

Новые блоги и статьи Все статьи Все блоги /
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .

@andrewromanov 0 / 0 / 0 Регистрация: 07.10.2014 Сообщений: 62

	Алгоритм ЭЦП на основе сложности дискретного логарифмирования 11.06.2017, 13:27. Показов 3513. Ответов 5 Метки нет (Все метки) Возникла следующая проблема, есть определенные формулы для расчета, но при повторении расчета по этим формулам получаются совершенно иные значения. Подскажите как необходимо высчитывать значения k и g, чтобы получать значения, аналогичные представленным в примере. Скриншот примера - Учебник - Молдовян, Практикум по криптосистемам с открытым ключом 0

Алгоритм ЭЦП на основе сложности дискретного логарифмирования

Решение