2022-08-18   9 m   1.4 k0 visits

2022巅峰极客Crypto wp

做了一下巅峰极客的Crypto，emm很可惜差点AK（crypto3赛后不久出的）。题目不多，质量一般，有脑残题，也有没遇到过的攻击手法。就当练练手了，稍微记录一下吧。

point-power

题目源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
from gmpy2 import *
from random import *
from secrets import flag

assert len(flag)==42
p=getPrime(600)
a=bytes_to_long(flag)
b=randrange(2,p-1)
E=EllipticCurve(GF(p),[a,b])
G=E.random_element()

x1,y1,_=G
G=2*G
x2,y2,_=G

print(f"p = {p}")
print(f"b = {b}")
print(f"x1 = {x1}")
print(f"x2 = {x2}")

定义了一条椭圆曲线，已知曲线参数b和p，告诉了曲线上随机点G及2G的x坐标，求曲线参数a的值。

那么我们很自然地联想到G和2G之间x坐标的关系式：

然后由于有： 消去可以得到： 解关于a的方程即可

解题脚本solve.sage:

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *

p = 3660057339895840489386133099442699911046732928957592389841707990239494988668972633881890332850396642253648817739844121432749159024098337289268574006090698602263783482687565322890623
b = 1515231655397326550194746635613443276271228200149130229724363232017068662367771757907474495021697632810542820366098372870766155947779533427141016826904160784021630942035315049381147
x1 = 2157670468952062330453195482606118809236127827872293893648601570707609637499023981195730090033076249237356704253400517059411180554022652893726903447990650895219926989469443306189740
x2 = 1991876990606943816638852425122739062927245775025232944491452039354255349384430261036766896859410449488871048192397922549895939187691682643754284061389348874990018070631239671589727

R.<a>=PolynomialRing(Zmod(p))
f=(3*x1^2+a)^2-4*(2*x1+x2)*(x1^3+a*x1+b)
f=f.monic()
res=f.roots()
for a,_ in res:
	print(long_to_bytes(int(a)))

strange curve

题目源码：

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
from Crypto.Util.number import *
from gmpy2 import *
from secrets import flag
import random

def add(P,Q):
    (x1,y1)=P
    (x2,y2)=Q


    x3=(x1+x2)*(1+y1*y2)*invert((1+x1*x2)*(1-y1*y2),p)%p
    y3=(y1+y2)*(1+x1*x2)*invert((1-x1*x2)*(1+y1*y2),p)%p

    return (x3,y3)

def mul(e,P):
    Q=(0,0)
    e=e%p
    while e:
        if e&1:
            Q=add(Q,P)
        P=add(P,P)
        e>>=1
    return Q

def Legendre(a,p):
    return (pow((a%p+p)%p,(p-1)//2,p))%p

def get_ts(p):
    p=p-1
    count=0
    while p%2==0:
        count+=1
        p=p//2
    return count,p

def get_nonre(p):
    a=random.randint(1,p)
    while Legendre(a,p)==1:
        a=random.randint(1,p)
    return a

def amm2(a,p):
    t,s=get_ts(p)
    ta=pow(get_nonre(p),s,p)
    tb=pow(a,s,p)
    h=1
    for i in range(1,t):
        d=pow(tb,2**t-1-i,p)
        if d==1:
            k=0
        else:
            k=1
        tb=(tb*pow(ta,2*k,p))%p
        h=(h*pow(ta,k,p))%p
        ta=pow(ta,2,p)
    return h*pow(a,(s+1)//2,p)%p  

def solve(a,b,c,p):
    tmpa=1
    tmpb=b*inverse(a,p)%p
    tmpc=c*inverse(a,p)%p
    assert Legendre(tmpb**2*inverse(4,p)-tmpc,p)==1
    res1=(amm2(tmpb**2*inverse(4,p)-tmpc,p)-tmpb*inverse(2,p))%p
    res2=(-amm2(tmpb**2*inverse(4,p)-tmpc,p)-tmpb*inverse(2,p))%p
    return (res1,res2)

def lift(x,a,b,p):
    tmp=b*(x**2-1)*inverse(a*x,p)%p
    return solve(1,-tmp,-1,p)[0]

p=9410547699903726871336507117271550134683191140146415131394654141737636910570480327296351841515571767317596027931492843621727002889086193529096531342265353
a=54733430689690725746438325219044741824500093621550218736194675295708808435509
b=75237024593957256761258687646797952793573177095902495908321724558796076392871
x=bytes_to_long(flag)

while True:
    try:
        y=lift(x,a,b,p)
        break
    except:
        x+=1
        continue

assert a*x*(y**2-1)%p==b*y*(x**2-1)%p

P=(x,y)
e=65537

eP=mul(e,P)
print(f"P = {P}")
print(f"eP = {eP}")

脑残题目，要求的P点x坐标直接给出来了，long_to_bytes就完事了。不明白出题人的真实想法，或许是想从eP推回P？

Learning with fault

题目源码：

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
from Crypto.Util.number import *
from gmpy2 import *
from secrets import flag
import os

class RSA():
    def __init__(self,p,q,e):
        self.p=p
        self.q=q
        self.e=e
        self.phi=(p-1)*(q-1)
        self.d=invert(self.e,self.phi)
        self.dp=self.d%(p-1)
        self.dq=self.d%(q-1)
        self.n=p*q
        self.N=getPrime(512)*getPrime(512)

    def sign(self,message):
        m=bytes_to_long(message)
        sig_p=pow(m,self.dp,self.p)
        sig_q=pow(m,self.dq,self.q)
        alpha=q*invert(q,p)
        beta=p*invert(p,q)
        return long_to_bytes((alpha*sig_p+beta*sig_q)%self.n)

    def corrupt_sign(self,message):
        m=bytes_to_long(message)
        sig_p=pow(m,self.dp,self.p)
        sig_q=pow(m,self.dq,self.q)
        alpha=q*invert(q,p)
        beta=p*invert(p,q)
        return long_to_bytes((alpha*sig_p+beta*sig_q)%self.N)

    def verify(self,message,sign):
        return long_to_bytes(pow(bytes_to_long(sign),self.e,self.n))==message

p=getPrime(512)
q=getPrime(512)
e=65537
rsa=RSA(p,q,e)

with open("sign.txt","w") as f1:
    with open("corrupted_sign.txt","w") as f2:
        for _ in range(6):
            message=os.urandom(64)
            sign=rsa.sign(message)
            corrupted_sign=rsa.corrupt_sign(message)
            assert rsa.verify(message,sign)
            f1.write(str(sign)+'\n')
            f2.write(str(corrupted_sign)+'\n')

enc=pow(bytes_to_long(flag),rsa.e,rsa.n)
print(f"n = {rsa.n}")
print(f"N = {rsa.N}")
print(f"e = {rsa.e}")
print(f"enc = {enc}")

RSA签名，不过签名方式不是直接pow(m,d,n)，而是另一种奇怪的方式。sign和corrupt_sign的区别仅在于最后的模数n不同。提供了6组随机消息的签名，需要分解n来解最后的RSA加密。看了一会儿无从下手，然后结合题目名搜了一会儿，发现是Modulus Fault Attacks Against RSA-CRT Signatures，直接有论文讲解了该攻击的原理和具体实施流程。大致思想是利用多维正交格得到规约基，从而构造与n相关的参数并gcd分解。目前细致原理还没仔细研究，只是先实现了出来，这里先码一下，以后有空再研究。

比赛时没写出来，还是写脚本太慢了。

解题脚本solve.sage:

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
34
35
36
37
38
39
40
41
42
43
44
45
from Crypto.Util.number import *
from gmpy2 import *
from random import randrange

sign_data=open('sign.txt','rb').read()
corrupted_data=open('corrupted_sign.txt','rb').read()
signs=[bytes_to_long(eval(s)) for s in sign_data.split(b'\n')[:-1]]
corrupted_signs=[bytes_to_long(eval(s)) for s in corrupted_data.split(b'\n')[:-1]]
n = 99670316685463632788041383175090257045961799409733877510733415402955763322569510896091638507050126669571444467488936880059210773298729542608112756526719533574432327269721804307073353651955251188547245641771980139488000798458617636759823027148955008149512692983471670488580994385743789385091027299901520585729
N = 81332992898551792936282861980393365170738006789835182134055801566584228471896473385776004610279937176800796971820133195300006470892468060034368863410462219133248069442508287516929262751427926825122839525496671527936622212986733708071962237633082743396115729744192159064241674410003857168101669882043743570731
e = 65537
enc = 2476965183785968993595493003363618829317072815989584886372189393899395623714779397354978469504773556228655475355703015337932838278988328384587983506790841663233499939173166353582189202860394411808445422387063648198432242875738065748287034529713834303346017134249834382745931627301273142828893469374138264396
l=6
v=[ crt([s,cs],[n,N]) for s,cs in zip(signs,corrupted_signs)]

k1=randrange(n)
vk=k1*vector(v)

m1=Matrix(ZZ,l,l+1)
m1.set_column(0,vk)
for i in range(l):
	m1[i,i+1]=1
m11=m1.LLL()

k2=randrange(n)
m2=Matrix(ZZ,l,2*l-2)
for i in range(l-2):
	m2.set_column(i,k2*m11.row(i)[1:])
for i in range(l-2,2*l-2):
	m2[i-l+2,i]=1
m22=m2.LLL()
basis=[ m22.row(i)[-l:] for i in range(l)]

for a in range(-10,10):
	for b in range(-10,10):
		z=a*basis[0]+b*basis[1]
		for vv,zz in zip(v,z):
			g=gcd(vv-zz,n)
			if g!=1:
				p=g
				q=n//p
				d=inverse(e,(p-1)*(q-1))
				m=pow(enc,d,n)
				print(long_to_bytes(int(m)))
				exit(0)

2022巅峰极客Crypto wp

https://litao6666.github.io/202208/960e02cb.html

Author

zealot

Posted on

2022-08-18

Updated on

2022-08-27

Licensed under

Catalogue

×