writeup-for-2021-第五空间

Posted on Edited on In Word count in article: 21k Reading time ≈ 19 mins.

算是第一次AK密码?

ecc

problem

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
print 'Try to solve the 3 ECC'

from secret import flag
from Crypto.Util.number import *
assert(flag[:5]=='flag{')
flag = flag[5:-1]
num1 = bytes_to_long(flag[:7])
num2 = bytes_to_long(flag[7:14])
num3 = bytes_to_long(flag[14:])

def ECC1(num):
	p = 146808027458411567
	A = 46056180
	B = 2316783294673
	E = EllipticCurve(GF(p),[A,B])
	P = E.random_point() 
	Q = num*P
	print E
	print 'P:',P
	print 'Q:',Q

def ECC2(num):
	p = 1256438680873352167711863680253958927079458741172412327087203
	#import random
	#A = random.randrange(389718923781273978681723687163812)
	#B = random.randrange(816378675675716537126387613131232121431231)
	A = 377999945830334462584412960368612
	B = 604811648267717218711247799143415167229480
	E = EllipticCurve(GF(p),[A,B])
	P = E.random_point() 
	Q = num*P
	print E
	print 'P:',P
	print 'Q:',Q
	factors, exponents = zip(*factor(E.order()))
	primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-1]
	print primes
	dlogs = []
	for fac in primes:
		t = int(int(P.order()) / int(fac))
		dlog = discrete_log(t*Q,t*P,operation="+")
		dlogs += [dlog]
		print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order
	print num
	print crt(dlogs,primes)



def ECC3(num):
	p = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
	A = 0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
	B = 0x926b0e42376d112ca971569a8d3b3eda12172dfb4929aea13da7f10fb81f3b96bf1e28b4a396a1fcf38d80b463582e45d06a548e0dc0d567fc668bd119c346b2
	E = EllipticCurve(GF(p),[A,B])
	P = E.random_point() 
	Q = num*P
	print E
	print 'P:',P
	print 'Q:',Q

ECC1(num1)
print '=============='
ECC2(num2)
print '=============='
ECC3(num3)

不懂, 为啥题目里还有PolligHellman的代码的 提示?

前两个ecc就用PolligHellman就能解出来

剩下最后一个用smart’s attack

参考论文https://wstein.org/edu/2010/414/projects/novotney.pdf

exp

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
from sage.all import *
from Crypto.Util.number import long_to_bytes,bytes_to_long
# Define the curve

p = 146808027458411567
a = 46056180
b = 2316783294673
# Generator
g_x = 119851377153561800
g_y = 50725039619018388
F = FiniteField(p)
E = EllipticCurve(F,[a,b])
G = E.point((g_x, g_y))
n = G.order()
print(n.factor())
'''
2^2 * 7 * 193 * 110603 * 122811083
'''
primes = [4 , 7 , 193 , 110603 , 122811083]
x=22306318711744209
y=111808951703508717
C = E.point((x, y))
dlogs = []
for fac in primes:
    t = int( n // fac )
    dlog = discrete_log( t*C , t*G, operation='+' )
    dlogs += [dlog]
    print("factor:"+str(fac)+",Discrete Log:"+str(dlog))
nC = crt(dlogs,primes)
print(long_to_bytes(nC))
# 第二条曲线跟第一条曲线是一样的 就不再抄一遍了

from Crypto.Util.number import long_to_bytes
p = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
A = 0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
B = 0x926b0e42376d112ca971569a8d3b3eda12172dfb4929aea13da7f10fb81f3b96bf1e28b4a396a1fcf38d80b463582e45d06a548e0dc0d567fc668bd119c346b2
E =EllipticCurve(GF(p),[A,B])

g_x = 10121571443191913072732572831490534620810835306892634555532657696255506898960536955568544782337611042739846570602400973952350443413585203452769205144937861
g_y = 8425218582467077730409837945083571362745388328043930511865174847436798990397124804357982565055918658197831123970115905304092351218676660067914209199149610
G = E.point((g_x, g_y))
x=964864009142237137341389653756165935542611153576641370639729304570649749004810980672415306977194223081235401355646820597987366171212332294914445469010927
y=5162185780511783278449342529269970453734248460302908455520831950343371147566682530583160574217543701164101226640565768860451999819324219344705421407572537
C = E.point((x, y))

def HenselLift(P,p,prec): 
    E = P.curve()     
    Eq = E.change_ring(QQ) 
    Ep = Eq.change_ring(Qp(p,prec)) 
    x_P,y_P = P.xy() 
    x_lift = ZZ(x_P) 
    y_lift = ZZ(y_P) 
    x, y, a1, a2, a3, a4, a6 = var('x,y,a1,a2,a3,a4,a6') 
    f(a1,a2,a3,a4,a6,x,y) = y^2 + a1*x*y + a3*y - x^3 - a2*x^2 - a4*x - a6 
    g(y) = f(ZZ(Eq.a1()),ZZ(Eq.a2()),ZZ(Eq.a3()),ZZ(Eq.a4()),ZZ(Eq.a6()),ZZ(x_P),y) 
    gDiff = g.diff() 
    for i in range(1,prec): 
        uInv = ZZ(gDiff(y=y_lift)) 
        u = uInv.inverse_mod(p^i)       
        y_lift = y_lift - u*g(y_lift) 
        y_lift = ZZ(Mod(y_lift,p^(i+1))) 
    y_lift = y_lift+O(p^prec) 
    return Ep([x_lift,y_lift]) 

def SmartAttack(P,Q,p,prec): 
    E = P.curve() 
    Eqq = E.change_ring(QQ) 
    Eqp = Eqq.change_ring(Qp(p,prec)) 

    P_Qp = HenselLift(P,p,prec)     
    Q_Qp = HenselLift(Q,p,prec)     

    p_times_P = p*P_Qp 
    p_times_Q=p*Q_Qp 
    x_P,y_P = p_times_P.xy() 
    x_Q,y_Q = p_times_Q.xy() 

    phi_P = -(x_P/y_P) 
    phi_Q = -(x_Q/y_Q)     

    k = phi_Q/phi_P 
    k = Mod(k,p) 
    return k 

long_to_bytes(SmartAttack(G,C,p,8))

doublesage

problem

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
from sage.modules.free_module_integer import IntegerLattice
from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
from sage.crypto.lwe import LWE
from sage.crypto.lwe import samples 
import numpy as np
import signal

def Question(n,m,para_D,para_e):  
	signal.alarm(600)     
	print('[+] Question:') 
	# m=n^2-2
	q=next_prime(n^2)                           
	D=DiscreteGaussianDistributionIntegerSampler(para_D*n)
	lwe=LWE(n=n, q=q, D=D)
	Z=[lwe() for _ in range(m)]
	A=matrix([a for (a,c) in Z]).transpose()
	C=vector([c for (a,c) in Z])
	print('[+] The following matrix operations are modulus',q)
	print('\n[+] Matrix A of size',n,'*',m,':'); print(A)
	print('\n[+] Vector C of size',1,'*',m,':'); print(np.array(C))
	E=lwe._LWE__s*A-C
	E=[int(e) for e in E]
	E=vector([e if e <= floor(q/2) else e-q for e in E])
	E_norm=E.norm().n()*para_e
	print('[+] Please give an integer vector x of size',1,'*',m,'(format [1 2 3] or [1, 2, 3]), such that the norm of vector x*A-C <=',E_norm,', where operations are modulus',q,':')
	k=GF(q)^n
	x=k(0)
	u=input()
	try:
		u=np.matrix(u)
		for i in range(n):
			x[i]=u[0,i]
	except:
		print('[+] Wrong format, exit.')
		exit()
	E=x*A-C
	E=[int(e) for e in E]
	E=vector([e if e <= floor(q/2) else e-q for e in E])
	tmp=E.norm().n()
	print('[+] The norm of vector x*A-C is', tmp,',', tmp<E_norm,'.\n')
	if not tmp<E_norm:
		exit()
	

def ReadFlag():
	print('flag{**********}')

Question(5, 23, 1.5, 1.1)
Question(15, 143, 1.5, 3)
ReadFlag()

就是两层lwe….. 直接当成lwe做就好了

exp

手动把远程给的向量和矩阵扔进下面的脚本里 把跑出来的向量传给服务器就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from sage.modules.free_module_integer import IntegerLattice
def BabaisClosestPlaneAlgorithm(L, w):
    G, _ = L.gram_schmidt()
    t = w
    i = L.nrows() - 1
    while i >= 0:
        w -= round( (w*G[i]) / G[i].norm()^2 ) * L[i]
        i -= 1
    return t - w

p = 227


M = Matrix([[55,78,211,140,203,28,205,71,148,55,43,66,34,108,99,6,202,138,90,77,128,85,88,189,135,42,157,159,204,51,211,77,2,64,60,137,53,29,214,153,142,138,0,148,53,115,73,178,78,81,219,103,23,64,146,61,98,86,157,102,222,219,2,69,65,183,93,208,156,80,164,70,200,106,128,123,1,29,175,224,62,166,62,122,102,21,3,166,41,26,164,78,199,194,56,82,6,135,99,107,104,178,32,12,57,205,63,14,159,145,133,19,96,145,20,172,49,213,200,111,148,5,45,6,25,19,81,199,52,119,10,12,101,140,189,61,190,168,23,181,74,153,111],[168,115,109,184,137,28,38,86,70,99,113,24,148,189,43,211,9,3,139,50,120,39,192,179,92,193,96,100,124,22,214,81,216,80,55,208,184,145,132,133,177,84,64,164,121,87,191,134,38,28,2,168,66,194,117,215,83,146,217,224,54,9,188,175,39,45,18,89,68,76,20,226,155,58,70,97,209,135,210,85,108,184,7,92,226,187,205,2,88,71,92,187,186,90,182,14,58,98,32,104,141,29,131,200,85,44,30,159,4,33,113,33,49,201,54,31,158,75,225,109,30,95,142,35,204,55,203,215,156,224,2,171,87,183,175,178,168,22,24,201,28,3,20],[152,97,15,188,52,6,149,182,167,134,60,31,154,36,6,209,28,221,144,88,161,144,13,162,90,110,95,216,196,44,133,124,75,218,170,14,84,186,127,142,59,3,185,132,147,63,121,100,10,88,103,145,3,47,179,127,127,150,133,120,90,84,186,140,21,49,93,167,70,140,161,196,29,207,128,217,125,214,28,211,66,44,33,118,166,43,220,131,26,209,108,171,41,205,163,62,20,127,184,7,95,18,125,66,94,26,33,40,68,49,197,111,46,215,97,204,98,69,206,225,193,116,43,85,153,61,184,178,195,220,127,164,168,45,42,22,104,194,19,0,111,138,191],[54,169,0,103,88,221,86,108,36,171,128,139,198,103,154,83,193,115,84,41,84,136,75,90,20,109,219,22,107,180,136,13,203,98,133,141,57,181,139,226,161,25,21,198,3,200,17,63,223,165,54,74,76,84,189,89,84,95,191,168,91,141,109,148,186,40,5,113,0,71,167,54,29,219,55,64,3,162,34,56,138,109,65,174,43,20,158,22,175,93,136,26,193,60,180,216,24,185,56,86,205,123,31,126,120,84,47,67,165,36,217,153,192,121,142,120,153,39,188,209,119,35,223,155,49,200,215,187,10,111,138,116,223,49,14,127,100,61,197,134,143,164,192],[125,88,118,197,140,200,191,110,135,76,71,33,223,183,34,100,16,53,190,153,185,201,91,118,118,51,10,214,142,223,77,215,11,1,109,166,210,32,63,129,109,146,9,68,28,224,73,43,159,35,185,100,126,218,88,90,111,79,177,54,149,31,86,82,203,11,104,211,200,205,75,226,220,36,31,177,191,200,210,92,60,92,40,96,23,129,99,209,57,55,224,12,154,200,118,25,168,27,28,93,91,175,107,35,22,123,110,86,87,62,149,79,116,28,125,164,114,88,217,80,199,211,113,20,29,68,124,141,157,11,160,85,189,223,135,77,186,172,11,55,40,125,187],[32,42,151,123,149,215,156,87,47,27,160,145,114,118,78,113,205,152,173,92,109,62,185,201,149,216,220,72,208,55,78,1,56,177,147,30,68,223,194,126,155,59,24,10,26,8,104,211,214,119,208,141,188,65,82,130,173,190,107,156,57,157,16,72,43,154,174,52,7,22,39,163,219,134,9,49,20,75,189,182,161,32,82,15,10,22,46,33,145,120,161,216,6,185,131,226,56,53,219,173,150,94,93,10,64,99,124,195,207,220,96,80,207,155,193,223,68,166,99,189,67,78,222,15,76,35,206,19,114,149,1,141,63,20,145,56,214,212,44,186,88,141,204],[114,4,210,127,90,181,97,17,51,156,182,58,167,185,111,54,67,137,213,165,219,211,143,4,65,129,91,190,67,180,163,29,221,185,100,225,103,190,133,208,90,11,123,141,174,93,18,177,124,146,50,107,25,64,219,63,44,186,152,14,25,141,107,188,106,168,136,94,154,6,41,168,193,137,92,179,203,36,85,213,138,149,225,62,89,78,10,180,25,155,38,223,82,221,190,223,42,144,186,49,169,45,161,137,152,180,152,77,97,222,104,98,167,88,116,174,67,75,81,119,205,3,180,24,159,190,102,157,199,152,145,146,131,208,58,121,178,95,211,214,163,196,104],[32,174,189,30,141,182,192,20,103,100,191,80,151,124,185,166,41,32,39,34,169,35,80,108,89,67,150,16,109,8,102,122,85,224,175,115,104,20,116,112,192,66,173,212,29,19,102,66,116,37,146,19,102,65,98,187,0,142,56,192,143,91,20,193,183,107,215,144,184,57,193,86,50,65,220,129,51,212,78,16,91,190,37,116,102,120,178,56,193,146,218,64,142,178,225,207,129,110,104,170,156,148,182,91,220,207,193,124,45,98,57,96,38,67,99,97,149,7,181,138,192,220,195,14,99,152,38,70,186,8,123,204,127,1,39,181,159,75,122,54,41,137,41],[115,170,6,225,99,21,139,118,133,16,175,94,163,163,222,67,220,75,215,142,8,167,86,20,94,7,169,5,145,208,213,153,38,202,191,10,66,133,92,91,95,28,38,86,127,215,3,206,67,170,14,153,108,219,0,10,64,78,74,223,199,180,16,13,169,109,224,213,142,65,12,29,100,109,104,102,131,24,202,92,70,11,215,41,35,112,39,10,182,131,120,95,112,49,116,81,43,49,54,30,225,63,167,16,118,75,193,50,125,224,161,127,186,88,196,3,0,215,219,217,168,221,206,63,86,133,153,216,16,152,39,19,183,155,200,80,33,48,150,104,193,137,189],[19,127,92,102,59,196,66,49,7,211,120,87,95,196,93,17,195,184,187,87,0,151,169,150,82,67,24,85,12,77,20,10,211,203,57,181,156,148,195,123,90,135,14,200,226,135,17,208,15,176,168,140,161,217,2,125,91,167,157,118,100,167,148,155,114,208,159,123,136,95,89,170,21,130,82,10,47,136,88,45,224,23,55,207,200,124,123,113,105,67,80,147,55,127,200,158,209,10,53,135,100,161,27,154,2,80,174,95,12,73,154,17,92,106,206,85,171,69,56,212,213,211,221,166,72,188,78,113,147,26,148,141,41,96,81,31,95,169,164,7,134,125,174],[158,177,225,122,164,132,16,150,170,166,67,2,192,194,28,104,59,148,150,106,179,217,159,94,107,217,209,225,226,39,138,219,163,116,48,40,63,140,8,139,38,144,63,94,205,210,186,217,214,141,22,186,198,114,211,219,82,34,122,92,34,182,156,170,58,41,150,36,212,197,38,131,28,110,48,224,19,109,185,142,186,14,126,156,105,33,79,93,162,183,156,135,43,144,114,8,158,102,145,194,26,29,183,205,219,196,207,142,176,21,225,50,36,22,176,100,40,125,120,114,74,34,176,98,121,77,116,200,85,96,167,63,215,80,1,218,94,29,65,202,42,45,114],[130,124,40,71,145,69,216,122,162,57,134,79,103,8,137,110,8,103,216,172,74,219,141,99,78,104,143,110,130,49,45,54,160,15,196,67,109,208,30,21,195,46,91,38,52,115,173,77,87,111,215,100,91,220,21,4,34,203,173,9,171,129,170,202,9,185,47,198,141,90,216,156,215,99,99,185,194,217,171,155,189,54,14,7,162,173,58,79,34,103,137,208,62,165,104,143,80,33,136,39,111,176,202,207,3,15,173,139,50,49,9,165,170,78,154,180,45,153,40,157,94,73,86,207,26,199,152,12,62,192,175,60,136,96,31,171,114,8,95,17,87,39,177],[51,36,34,69,152,211,6,89,157,60,65,58,78,22,92,23,172,105,12,218,154,171,96,201,41,53,204,215,23,211,216,98,80,45,90,27,177,9,74,169,23,197,221,74,119,152,158,180,73,138,192,149,37,147,80,26,154,180,97,208,130,165,41,180,176,160,20,155,149,213,181,81,62,173,108,80,86,182,35,209,190,217,187,180,201,225,112,125,95,118,48,137,96,79,127,206,49,85,143,139,200,194,49,6,208,109,5,197,75,150,134,194,0,191,72,16,101,4,85,178,131,52,94,139,140,42,14,14,178,94,60,175,16,179,216,14,154,220,136,176,42,145,71],[11,190,138,143,159,121,173,115,63,200,179,44,222,85,202,143,118,197,66,100,116,18,180,77,86,175,32,158,43,133,0,214,162,118,71,224,78,175,82,206,136,137,135,41,146,130,55,42,38,115,165,53,105,189,27,86,61,98,189,7,164,152,188,132,97,2,89,210,14,131,81,11,193,164,174,180,166,112,162,197,27,27,80,120,70,98,197,29,172,88,207,76,81,205,92,37,25,189,66,94,108,222,152,93,116,141,176,72,111,171,204,146,118,5,185,39,171,180,124,78,208,142,85,120,217,61,177,39,77,57,164,139,147,171,149,111,152,168,191,33,98,11,180],[153,44,17,75,199,75,208,31,100,124,210,206,174,223,216,194,156,157,213,101,212,117,162,194,38,184,118,126,10,92,168,197,78,113,71,154,43,177,202,115,27,34,174,54,201,97,112,180,169,32,134,160,104,183,0,145,179,106,156,182,213,214,144,43,226,191,66,34,217,187,137,40,103,194,103,217,13,87,84,151,225,190,26,100,101,30,79,173,207,32,32,150,195,105,162,78,61,16,32,151,4,59,50,219,220,133,13,31,104,122,93,181,5,150,188,25,222,77,111,2,41,12,129,138,107,74,30,145,21,165,192,115,119,118,112,223,74,76,167,167,218,80,121]])
P = [[0 for _ in range(143)] for _ in range(143)]
for i in range(143):
    P[i][i] = p
M = M.stack(Matrix(P))
lattice = IntegerLattice(M, lll_reduce=True)
c = vector([158,93,224,147,157,86,28,224,141,124,150,117,110,88,186,115,109,119,166,206,210,89,28,63,110,16,156,125,122,201,147,185,53,211,46,1,100,217,69,12,147,64,136,20,88,198,43,110,126,101,113,81,170,190,93,82,10,217,184,32,39,18,184,214,24,190,78,152,160,62,152,38,214,16,37,28,125,51,20,54,91,220,214,47,95,113,140,226,133,185,11,214,207,189,94,92,223,34,61,168,191,163,152,203,201,215,106,180,114,140,198,177,215,201,208,152,221,0,59,147,205,3,181,104,199,205,27,145,51,105,83,17,32,221,214,194,193,148,65,20,183,102,174])
'['+str(BabaisClosestPlaneAlgorithm(lattice.reduced_basis, c))[1:-1]+']'

secrets

problem

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
import random, hashlib
from Crypto.Util.number import *
from Crypto.Cipher import AES
from secret import flag

assert(flag[:5] == b"flag{" and flag[-1:] == b"}")

flag = flag[5:-1]

p = getPrime(512)
secrets = [getPrime(32) for i in range(3)]
a = [getPrime(511) for i in range(3)]

e = [[random.randint(0,2) for i in range(3)] for j in range(3)]

c = 0
for i in range(3):
    tmp = 1
    for j in range(3):
        tmp *= secrets[j] ** e[i][j]
    c += a[i] * tmp
    c %= p

key = hashlib.sha256(str(secrets).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
enc_flag = cipher.encrypt(flag).hex()

print(p)
print(a)
print(e)
print(c)
print(enc_flag)

'''
12974234240047250882827277463970749648223428465145328709918053842153820677294215343957019413719473165129078971772191068642653862027980142472460705711018201
[6208495304507502877592974397978564449062722480435998477821753565334623511793847345749111308898139670628857817327159494561065840693449298616913891952427947, 4428365792626193951517975036630823002373517124620690551190165499794155382003347632615508488697880129516880024881940903287205636949002132541035487795791827, 4718311857821047798142460474602800502374374326300654458450570361490723801361197812174259099714079434910279510299556693616702570294307587124784370853830179]
[[0, 2, 2], [1, 0, 1], [2, 1, 1]]
8024639827831958040886215528711059283414630802186262470325506233115495366865722141662305750597559580380055075908821369972992187624854877285935207126822671
bf550e796d6efc92e8543ffcbb8d81fd588900f8f7aecaeeee718d60eaace3bc
'''

背包问题

经典一个等式流

这里的是为了调格子的det, 调到能找到目标向量为止, 找到等式右边的向量就能算出

exp

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
import random, hashlib
from Crypto.Util.number import *
from Crypto.Cipher import AES

enc_flag = 0xbf550e796d6efc92e8543ffcbb8d81fd588900f8f7aecaeeee718d60eaace3bc
a  = [6208495304507502877592974397978564449062722480435998477821753565334623511793847345749111308898139670628857817327159494561065840693449298616913891952427947, 4428365792626193951517975036630823002373517124620690551190165499794155382003347632615508488697880129516880024881940903287205636949002132541035487795791827, 4718311857821047798142460474602800502374374326300654458450570361490723801361197812174259099714079434910279510299556693616702570294307587124784370853830179]

p = 12974234240047250882827277463970749648223428465145328709918053842153820677294215343957019413719473165129078971772191068642653862027980142472460705711018201
c = 8024639827831958040886215528711059283414630802186262470325506233115495366865722141662305750597559580380055075908821369972992187624854877285935207126822671

i = 128

R = 2**i
M = Matrix([[1,0,0,0,a[0] * R],[0,1,0,0,a[1] * R],[0,0,1,0,a[2] * R],[0,0,0,1,-c * R],[0,0,0,0,p * R]])
L = M.BKZ()

s3 = gcd(L[0][0],abs(L[0][1]))
s1 = abs(L[0][1]) // s3
s2 = sqrt(abs(L[0][0]) // s3 // s3)
secrets = [s1,s2,s3]

key = hashlib.sha256(str(secrets).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(long_to_bytes(enc_flag))
flag

signin

problem

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

p = getPrime(512)
q = getPrime(512)
n = p * q
e = 0x10001
x = (p ^ q) & ((1 << 400) - 1)

m = bytes_to_long(flag)

c = pow(m,e,n)

print("c = " + str(c))
print("e = " + str(e))
print("n = " + str(n))
print("x = " + str(x))

'''
c = 41079136228776331983513986502894911009747944746334405367181525535644429164244074690458675696682154772257649811625401364517966224711291000199478649309514306511977247475050430881892635166215911325729515065570801798281126631754714292634605360578171629351703909902943766832088848829679735266081587467028354629832
e = 65537
n = 88873300622677925132392673651975872286851841516213062658793503010409158793653030553313986481205677326846210604582870123515082097235868012724220463515351466605298734168814756198761860328588678124560858545154560701982246840286690871368569184620040790812223630254910190657002367120010677907467764741789052920477
x = 138384108215091704603441412066611031482512354164750119910659929381838248956079740784293945420743011870999379776464932828
'''

plaidCTF 2021里面的那个xorsa改了一下

把给出来的p ^ q 的位数减少到了400位

依旧可以用bfs得到p的低400左右的位数

然后copper p一共就512位

exp

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
from Crypto.Util.number import *
from tqdm import tqdm

c = 41079136228776331983513986502894911009747944746334405367181525535644429164244074690458675696682154772257649811625401364517966224711291000199478649309514306511977247475050430881892635166215911325729515065570801798281126631754714292634605360578171629351703909902943766832088848829679735266081587467028354629832
e = 65537
n = 88873300622677925132392673651975872286851841516213062658793503010409158793653030553313986481205677326846210604582870123515082097235868012724220463515351466605298734168814756198761860328588678124560858545154560701982246840286690871368569184620040790812223630254910190657002367120010677907467764741789052920477
x = bin(138384108215091704603441412066611031482512354164750119910659929381838248956079740784293945420743011870999379776464932828)[2:]
P = []
def find(guessp,i):
    p = int(guessp,2)
    q = int(x[-i:],2) ^^ p

    if (q * p) % 2 ** i == n % 2 ** i:
        if i == 399:
            P.append(p)
        else:
            find('1'+guessp,i+1)
            find('0'+guessp,i+1)

find('1',1)

print(len(P))
pbits = 512
for i in tqdm(range(len(P))):
    _p = P[i]
    kbits = 512 - len(bin(_p)[2:])
    R.<x> = Zmod(n)[]
    f = P[i] + x * 2^len(bin(_p)[2:])
    f = f.monic()
    roots = f.small_roots(X=2^kbits,beta=0.4)
    if roots:
        p = int(_p + roots[0]* 2^len(bin(_p)[2:]))
        print(_p + roots[0]* 2^len(bin(_p)[2:]))
        break
q = n // p
assert p * q == n
phi = (q - 1) * (p - 1)
d = inverse_mod(e,phi)
long_to_bytes(pow(c,d,n))