GHCTF2024新生赛_2023四省联考 2024.6.7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
p = getPrime(256)
a = getPrime(256)
b = getPrime(256)
E = EllipticCurve(GF(p),[a,b])
m = E.random_point()
G = E.random_point()
k = getPrime(256)
K = k * G
r = getPrime(256)
c1 = m + r * K
c2 = r * G
cipher_left = bytes_to_long(flag1) * m[0]
cipher_right = bytes_to_long(flag2) * m[1]

print(f"p = {p}")
print(f"a = {a}")
print(f"b = {b}")
print(f"k = {k}")
print(f"E = {E}")
print(f"c1 = {c1}")
print(f"c2 = {c2}")
print(f"cipher_left = {cipher_left}")
print(f"cipher_right = {cipher_right}")

题目给出了较多的基本信息，只要求解m即可。可以看出 直接sage求解即可，没有sage也可以自己实现椭圆曲线的点加和标量乘法求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#sage
from Crypto.Util.number import *
p = 89483595401193659714875788802968429205691837099576262739461780495250135533277
a = 64826237317229947176929808786908866900942344000188828024006529547932535008343
b = 78534056584783370803046009116134540449521103461992771640264791547574821609373
k = 67913488585481211548108713418125579002164994747094092682155324503393614823971
F=GF(p)
E=EllipticCurve(F,[a,b])
c1 = E(... , ... )
c2 = E(... , ... )
cipher_left = ...
cipher_right = ...
m=c1-k*c2

f1 = cipher_left /m[0]
f2 = cipher_right / m[1]
print(long_to_bytes(int(f1))+long_to_bytes(int(f2)))

GHCTF2024新生赛_2024四九联考　2024.6.8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
m = bytes_to_long(flag)
def getKey():
    p = getPrime(1024)
    q = getPrime(1024)
    n = p*q
    assert m < n
    _g = randint(1,n)
    _a = randint(1,n)
    _b = randint(1,n)
    return 

def encrypt():
    key = getKey()#[0] _g, [1] _a, [2] _b, [3] p, [4] n
    _key = pow(key[0], key[1] * (key[3]-1), key[4])#  k=_g^(_a*(p-1))%n
    c = (pow(_key, key[2], key[4]) * m) % key[4]# k^b*m%n
    return key[4], _key, c

if __name__ == '__main__':
    print(encrypt())

已知 , 变换可得 , 两边同时模p，由小费马定理得 , 所以 , 可得 。 又已知 , , 再次同时模p, $ c;mod;p=k^b;mod;pm;mod;p题目只给了，但大概率小于所以 c;mod ;p=k^b; omd ; pm$ —-> 

1
2
3
4
x=(..., ..., ...)
n,k,c=x
p=gmpy2.gcd(n,k-1)
print(long_to_bytes(c%p))
HZNUCTF2023 final_一步到喂 2024.7.13
1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *
from secret import flag,x,y
p=getPrime(512)
q=getPrime(512)
n=p*q
e=x
assert 1293023064232431070902426583269468463*pow(x,2)==105279230912868770223946474836383391725923*pow(y,2)+1293023064232431070902426583269468463
m=bytes_to_long(flag)
c=pow(m,e,n)
print(p,q)
print(c)

看完题没有头绪，搜索发现是使用pell方程求解，学习一下。详细过程看pell方程博客。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
p=9850212100620338486478343799784951721581757936621772924971218807300819701941457605399099898870264241518769370682330612103782092302148525012450902351701339
q=10749429992014823019923966246896511618886613763258781706004694804949547801668777655988055847885755337127548775758133804022361510427909703124161450470578543
c=66847321508502017574023222490247591875197038421108556106531660421662626233521063441647157067220450229816184622038471812597874582613385516838920632450015292570673816423432903604941781889308906893966588610214614726388822851471695742453496232748358301888465563812947038856742838097152549971517159475947566599664

a=1293023064232431070902426583269468463
b=105279230912868770223946474836383391725923
n=1293023064232431070902426583269468463

D=b//a
N=1

from sympy.solvers.diophantine.diophantine import diop_DN
# sympy求解 x^2-Dy^2=N 输入(D,N)
x =int(diop_DN(D,N)[0][0])
d=gmpy2.invert(x,q-1)
print(long_to_bytes(pow(c,d,q)))