标题: 椭圆曲线加密算法科普系列的作业

创建: 2023-12-08 14:17
更新: 2023-12-18 18:55
链接: https://scz.617.cn/misc/202312081417.txt

前几天推荐Andrea Corbellini的椭圆曲线加密算法科普系列，共四篇，非常精彩，
深入浅出。

--------------------------------------------------------------------------
Elliptic Curve Cryptography: a gentle introduction - Andrea Corbellini [2015-05-17]
https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/

Elliptic Curve Cryptography: finite fields and discrete logarithms - Andrea Corbellini [2015-05-23]
https://andrea.corbellini.name/2015/05/23/elliptic-curve-cryptography-finite-fields-and-discrete-logarithms/

Elliptic Curve Cryptography: ECDH and ECDSA - Andrea Corbellini [2015-05-30]
https://andrea.corbellini.name/2015/05/30/elliptic-curve-cryptography-ecdh-and-ecdsa/

Elliptic Curve Cryptography: breaking security and a comparison with RSA - Andrea Corbellini [2015-06-08]
https://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/
--------------------------------------------------------------------------

有不少人转载收藏，但据我二十多年经验看，绝大多数属于「转载即学习」，没怎么
看吧？相信还是有人看完了，我来布置几道作业，看一下谁不是懒渣。

设有限域Zp上椭圆曲线如下:

--------------------------------------------------------------------------
y^2 ≡ x^3 + a*x + b (mod p)
p   = 10177777
a   = 1
b   = -1
--------------------------------------------------------------------------

提问:

--------------------------------------------------------------------------
(1) 该椭圆曲线的阶N是多少
(2) 该椭圆曲线用于加密算法时，其n阶循环子群的n是多少
(3) 求一个n阶循环子群生成元G，说一下G在实平面的坐标
(4) 设第3步已求得一个G，且已知两个用户的私钥如下:

dA  = 158903
dB  = 17

提问，这两个用户的公钥是多少:

HA  = ?
HB  = ?

说一下HA、HB在实平面的坐标
--------------------------------------------------------------------------

这个作业改一下，比如套ECDSA算法，就可充作CTF赛题。坑爹水果题都能用作CTF赛
题，正经椭圆曲线加密算法题更应该可以。

--------------------------------------------------------------------------

2023-12-18 18:55

0x指纹(5845952017)的答案

在线SageMath
https://sagecell.sagemath.org

--------------------------------------------------------------------------
from sage.all import *

p   = 10177777
a   = 1
b   = -1
E   = EllipticCurve(GF(p), [a,b])
N   = E.order()
n   = factor(N)[-1][0]
h   = N // n
P   = E.random_point()
while h*P == E(0) :
    P   = E.random_point()

G   = h*P
dA  = 158903
dB  = 17
HA  = dA*G
HB  = dB*G
print( n, G, HA, HB )
--------------------------------------------------------------------------