ECC例题分析

Crypto学习记录 ECC

Created At : 2023-04-30 14:19

Count:1.3k Views 👀 :

总结
ECC学习文章

来自HGame2023 Week4的ECRSA，对于我这个刚接触ECC的菜鸟来说，我觉得很有必要单独拿出来作记录，文中的内容会很啰嗦，主要是都不懂😭，希望海涵。

源码：

from sage.all import *
from sage.all_cmdline import *
from Crypto.Util.number import *
from secret import flag

Nbits = 512
x = bytes_to_long(flag)
f = open('./output', 'w')

def gen_pubkey(Nbits):
    p = getPrime(Nbits // 2)
    q = getPrime(Nbits // 2)
    n = p*q
    while True:
        a = getRandomInteger(Nbits // 2)
        b = getRandomInteger(Nbits // 2)
        if gcd(4*a**3 + 27*b**2, n) == 1:
            break
    E = EllipticCurve(Zmod(n), [a, b])
    e = getPrime(64)
    f.write(f"p={p}\nq={q}\n")
    return n, E, e

n, E, e = gen_pubkey(Nbits)
pt = E.lift_x(Integer(x))
ct = pt * e
f.write(f"n = {n}\na = {E.a4()}\nb = {E.a6()}\ne = {e}\n")
f.write(f"ciphertext = {long_to_bytes(int(ct.xy()[0]))}\n")

RSA与ECC结合。

密文ct是通过使用明文pt和随机数e进行加密得到的，其中pt是一个椭圆曲线上的点，而e是一个整数。因此，我们需要先求出pt这个点。$pt = E.lift_x(Integer(x))$来将明文x转换为椭圆曲线上的点$pt$。但是，在实际运行时可能会出现无法找到满足x坐标的点的情况，这时我们需要使用$lift_y$函数来寻找满足y坐标的点。对于在有限域上的椭圆曲线，每个x坐标对应的y坐标可能有0个、1个或2个。因此，我们需要分别在$GF(p)和GF(q)$中求出满足x坐标的y值，然后使用中国剩余定理将它们合并成一个在$Zmod(n)$上的y值。

from sage.all import *
from sage.all_cmdline import *
from Crypto.Util.number import *

p = 115192265954802311941399019598810724669437369433680905425676691661793518967453
q = 109900879774346908739236130854229171067533592200824652124389936543716603840487
n = 1265973137163332340636107173548074387094288440751164714475805591193132153433
a = 3457301624586139606837804088262299224575469302815229087413111295501888448568
b = 1032821371338209482066820365696715669963814382548975103442891640397173555138
e = 11415307674045871669
ciphertext = b''

Ep = EllipticCurve(Zmod(p), [a, b])
Eq = EllipticCurve(Zmod(q), [a, b])
cx = bytes_to_long(ciphertext)
cp = Ep.lift_x(Integer(cx))
cq = Eq.lift_x(Integer(cx))
dp = inverse(e, Ep.order())
dq = inverse(e, Eq.order())
mp = (dp * cp).xy()[0]
mq = (dq * cq).xy()[0]

flag = CRT_list([ZZ(mp), ZZ(mq)], [p, q])
print(long_to_bytes(int(flag)))

初学者，所以对代码作详细解释，会很啰嗦：

Ep = EllipticCurve(Zmod(p), [a, b])
Eq = EllipticCurve(Zmod(q), [a, b])

分别构造以$p、q$为域的椭圆曲线，系数相同均为$a、b$，如下：

y^2 = (x^3 + a*x + b) mod p
y^2 = (x^3 + a*x + b) mod q

cx = bytes_to_long(ciphertext)
cp = Ep.lift_x(Integer(cx))
cq = Eq.lift_x(Integer(cx))

这里将cx转为整数后，分别在有限域GF(p)和GF(q)上找到满足x坐标为cx的点cp和cq。

这个Integer函数可以不加，作保险起见吧。

我输出了下cp、cq的结果，如下：

(0 : 68179883496530713257477536240611223816942458437112513090828235340489931605592 : 1) 
(0 : 22872408154206024463287219703888573608694484866139369114952150185047577317172 : 1)

分别是cp、cq的x、y、z坐标。

dp = inverse(e, Ep.order())
dq = inverse(e, Eq.order())
mp = (dp * cp).xy()[0]
mq = (dq * cq).xy()[0]

椭圆曲线Ep和Eq上的点的阶，解释：在椭圆曲线上，每个点都有一个阶，表示通过不断进行点加运算得到的最小循环周期。具体地，如果点P的阶为n，则有nP = O，其中O表示椭圆曲线上的无穷远点。对于椭圆曲线Ep和Eq，它们上面的点的阶分别表示为Ep.order()和Eq.order()。

$dp = inverse(e, Ep.order())$，椭圆曲线里求逆元的方式。

然后，将dp和dq分别与cp和cq相乘，得到解密后的结果mp和mq。其中，mp和mq是椭圆曲线上的点。使用mp.xy()[0]和mq.xy()[0]函数分别取出mp和mq的x坐标，得到明文的两个部分。（mp = (dp * cp).xy()[1]即表示求y坐标）

flag = CRT_list([ZZ(mp), ZZ(mq)], [p, q])

将mp和mq作为同余方程组的解，p和q分别作为模数传入CRT_list函数。函数返回值flag表示满足以上两个同余方程的最小非负整数解，即解密后的明文。mp、mq已经为整数了，用ZZ转其实也是作保险起见吧。

整体代码如下：

from Crypto.Util.number import *

p = 115192265954802311941399019598810724669437369433680905425676691661793518967453
q = 109900879774346908739236130854229171067533592200824652124389936543716603840487
n = 12659731371633323406361071735480743870942884407511647144758055911931321534333057725377899993936046070028289182446615763391740446071787318153462098556669611
a = 34573016245861396068378040882622992245754693028152290874131112955018884485688
b = 103282137133820948206682036569671566996381438254897510344289164039717355513886
e = 11415307674045871669
ciphertext = b'f\xb1\xae\x08`\xe8\xeb\x14\x8a\x87\xd6\x18\x82\xaf1q\xe4\x84\xf0\x87\xde\xedF\x99\xe0\xf7\xdcH\x9ai\x04[\x8b\xbbHR\xd6\xa0\xa2B\x0e\xd4\xdbr\xcc\xad\x1e\xa6\xba\xad\xe9L\xde\x94\xa4\xffKP\xcc\x00\x907\xf3\xea'

Ep = EllipticCurve(Zmod(p), [a, b])
Eq = EllipticCurve(Zmod(q), [a, b])
cx = bytes_to_long(ciphertext)
cp = Ep.lift_x(Integer(cx))
cq = Eq.lift_x(Integer(cx))
dp = inverse(e, Ep.order())
dq = inverse(e, Eq.order())
mp = (dp * cp).xy()[0]
mq = (dq * cq).xy()[0]

flag = CRT_list([ZZ(mp), ZZ(mq)], [p, q])
print(long_to_bytes(int(flag)))