W'Blog

Wbuildings的自勉小屋

0%

国城杯2024

发表于 分类于 Valine：
本文字数： 16k 阅读时长 ≈ 15 分钟

稍晚再补充一下其他师傅的思路

EZ_sign

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

flag = b'D0g3xGA{***************}'
msg = b'e = ?'

def sign(pub, pri, k):
    (p,q,g,y) = pub
    x = pri
    r = int(powmod(g, k, p) % q)
    H = bytes_to_long(sha1(os.urandom(20)).digest())
    s = int((H + r * x) * invert(k, q) % q)
    return (H,r,s)

k1 = getPrime(64)
k2 = k1 ** 2
pri = bytes_to_long(msg)
a = 149328490045436942604988875802116489621328828898285420947715311349436861817490291824444921097051302371708542907256342876547658101870212721747647670430302669064864905380294108258544172347364992433926644937979367545128905469215614628012983692577094048505556341118385280805187867314256525730071844236934151633203
b = 829396411171540475587755762866203184101195238207
g = 87036604306839610565326489540582721363203007549199721259441400754982765368067012246281187432501490614633302696667034188357108387643921907247964850741525797183732941221335215366182266284004953589251764575162228404140768536534167491117433689878845912406615227673100755350290475167413701005196853054828541680397
y = 97644672217092534422903769459190836176879315123054001151977789291649564201120414036287557280431608390741595834467632108397663276781265601024889217654490419259208919898180195586714790127650244788782155032615116944102113736041131315531765220891253274685646444667344472175149252120261958868249193192444916098238

pub = (a, b, g, y)

H1, r1, s1 = sign(pub, pri, k1)

H2, r2, s2 = sign(pub, pri, k2)

p = getPrime(128)
q = getPrime(128)
n = p * q
c = powmod(bytes_to_long(flag), e, n)

C = p**2 + q**2

print(f'(H1, r1, s1) = {H1}, {r1}, {s1}')
print(f'(H2, r2, s2) = {H2}, {r2}, {s2}')
print(c)
print(C)

'''
(H1, r1, s1) = 659787401883545685817457221852854226644541324571, 334878452864978819061930997065061937449464345411, 282119793273156214497433603026823910474682900640
(H2, r2, s2) = 156467414524100313878421798396433081456201599833, 584114556699509111695337565541829205336940360354, 827371522240921066790477048569787834877112159142
c = 18947793008364154366082991046877977562448549186943043756326365751169362247521
C = 179093209181929149953346613617854206675976823277412565868079070299728290913658
'''

exp：

DSA线性 k，复数域分解

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

(H1, r1, s1) = 659787401883545685817457221852854226644541324571, 334878452864978819061930997065061937449464345411, 282119793273156214497433603026823910474682900640
(H2, r2, s2) = 156467414524100313878421798396433081456201599833, 584114556699509111695337565541829205336940360354, 827371522240921066790477048569787834877112159142

a = 149328490045436942604988875802116489621328828898285420947715311349436861817490291824444921097051302371708542907256342876547658101870212721747647670430302669064864905380294108258544172347364992433926644937979367545128905469215614628012983692577094048505556341118385280805187867314256525730071844236934151633203
b = 829396411171540475587755762866203184101195238207
g = 87036604306839610565326489540582721363203007549199721259441400754982765368067012246281187432501490614633302696667034188357108387643921907247964850741525797183732941221335215366182266284004953589251764575162228404140768536534167491117433689878845912406615227673100755350290475167413701005196853054828541680397
y = 97644672217092534422903769459190836176879315123054001151977789291649564201120414036287557280431608390741595834467632108397663276781265601024889217654490419259208919898180195586714790127650244788782155032615116944102113736041131315531765220891253274685646444667344472175149252120261958868249193192444916098238


R.<k1> = PolynomialRing(Zmod(b))
f = k1^2*r1*s2 - k1*r2*s1 - H2*r1 + H1*r2
# f=f.monic()

roots=f.roots()
print(roots)

k = roots[1][0]
m = (s1*k-H1)*gmpy2.invert(r1,b) % b
print(long_to_bytes(int(m)))

import libnum
from Crypto.Util.number import *

N = 179093209181929149953346613617854206675976823277412565868079070299728290913658
zn = ZZ[i](N)
for d in divisors(ZZ[i](N)):
    pp, qq = map(int, d)
    if is_prime(pp) and is_prime(qq):
        print("yes", pp, qq)

# yes 295488723650623654106370451762393175957 302951519846417861008714825074296492447
# yes 7247215681561944590028089613581484765881 7247215681561944590028089613581484765881

p = 295488723650623654106370451762393175957
q = 302951519846417861008714825074296492447
C = 179093209181929149953346613617854206675976823277412565868079070299728290913658

ccc = p**2+q**2
print(ccc==C)

c = 18947793008364154366082991046877977562448549186943043756326365751169362247521
n = p*q
phi = (p-1)*(q-1)
e = 44519
d = inverse(e,phi)
print(libnum.gcd(e,phi))
m = pow(c,d,n)
print(libnum.n2s(int(m)))

# D0g3xGC{EZ_DSA_@nd_C0mplex_QAQ}

复数域分解那边，稍稍有点问题，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
N = 179093209181929149953346613617854206675976823277412565868079070299728290913658

Zn = ZZ[i](N)
for d in divisors(Zn):
    p, q = map(int, d)
    # if is_prime(p) and is_prime(q) and d.norm() == N:
    if is_prime(q):
        print(p)
        print(q)

# -7247215681561944590028089613581484765881
# 7247215681561944590028089613581484765881
# -302951519846417861008714825074296492447
# 295488723650623654106370451762393175957
# -108
# 43
# 0
# 2
# 108
# 43
# 13513
# 13513
# 2196800710668294903
# 4459379860824713653
# 157606014243244438240601
# 157606014243244438240601

附上官方解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
C=179093209181929149953346613617854206675976823277412565868079070299728290913658
f = ZZ[I](C)
divisors_f = divisors(f)
for d in divisors_f:
    a,b = d.real(), d.imag()
    if a**2 + b**2 == C:
        p = abs(int(a))
        q = abs(int(b))
        if is_prime(p) and is_prime(q):
            print(p)
            print(q)
            break

# 302951519846417861008714825074296492447
# 295488723650623654106370451762393175957

babyRSA

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
from secret import flag
from Crypto.Util.number import*
from gmpy2 import*

flag = b'D0g3xGC{****************}'

def gen_key(p, q):
    public_key = p*p*q
    e = public_key
    n = p*q
    phi_n = (p-1)*(q-1)
    private_key = inverse(e,phi_n)
    return public_key,private_key,e

p = getPrime(512)
q = getPrime(512)

N,d,e = gen_key(p,q)

c = gmpy2.powmod(bytes_to_long(flag),e,N)

print(N)
print(d)
print(c)

'''
n = 539403894871945779827202174061302970341082455928364137444962844359039924160163196863639732747261316352083923762760392277536591121706270680734175544093484423564223679628430671167864783270170316881238613070741410367403388936640139281272357761773388084534717028640788227350254140821128908338938211038299089224967666902522698905762169859839320277939509727532793553875254243396522340305880944219886874086251872580220405893975158782585205038779055706441633392356197489
d = 58169755386408729394668831947856757060407423126014928705447058468355548861569452522734305188388017764321018770435192767746145932739423507387500606563617116764196418533748380893094448060562081543927295828007016873588530479985728135015510171217414380395169021607415979109815455365309760152218352878885075237009
c = 82363935080688828403687816407414245190197520763274791336321809938555352729292372511750720874636733170318783864904860402219217916275532026726988967173244517058861515301795651235356589935260088896862597321759820481288634232602161279508285376396160040216717452399727353343286840178630019331762024227868572613111538565515895048015318352044475799556833174329418774012639769680007774968870455333386419199820213165698948819857171366903857477182306178673924861370469175
'''

exp：

已知ed分解n（多运行几遍，输出结果p、q的对位不尽相同，可手动判断）

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
import random
from hashlib import md5

import libnum

def factor_with_ed(e,d,n):
    p=1
    q=1
    while p==1 and q==1:
        k = e*d -1
        g = random.randint(1,n)
        while k%2==0:
            k //= 2
            x = pow(g,k,n)
            if x>1 and libnum.gcd(x-1,n)>1:
                p = libnum.gcd(x-1,n)
                q = n//p
    return p,q

n = 539403894871945779827202174061302970341082455928364137444962844359039924160163196863639732747261316352083923762760392277536591121706270680734175544093484423564223679628430671167864783270170316881238613070741410367403388936640139281272357761773388084534717028640788227350254140821128908338938211038299089224967666902522698905762169859839320277939509727532793553875254243396522340305880944219886874086251872580220405893975158782585205038779055706441633392356197489
d = 58169755386408729394668831947856757060407423126014928705447058468355548861569452522734305188388017764321018770435192767746145932739423507387500606563617116764196418533748380893094448060562081543927295828007016873588530479985728135015510171217414380395169021607415979109815455365309760152218352878885075237009
c = 82363935080688828403687816407414245190197520763274791336321809938555352729292372511750720874636733170318783864904860402219217916275532026726988967173244517058861515301795651235356589935260088896862597321759820481288634232602161279508285376396160040216717452399727353343286840178630019331762024227868572613111538565515895048015318352044475799556833174329418774012639769680007774968870455333386419199820213165698948819857171366903857477182306178673924861370469175
e = n

q,p = factor_with_ed(e,d,n)
# p = libnum.nroot(p,2)
m = pow(c,d,p)
print(libnum.n2s(m))

# D0g3xGC{W1sh_Y0u_Go0d_L@ucK-111}

2023ISCTF | DexterJie’Blog

考察Schmidt-Samoa密码系统

image-20241207194115982

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import gmpy2

N = 539403894871945779827202174061302970341082455928364137444962844359039924160163196863639732747261316352083923762760392277536591121706270680734175544093484423564223679628430671167864783270170316881238613070741410367403388936640139281272357761773388084534717028640788227350254140821128908338938211038299089224967666902522698905762169859839320277939509727532793553875254243396522340305880944219886874086251872580220405893975158782585205038779055706441633392356197489
d = 58169755386408729394668831947856757060407423126014928705447058468355548861569452522734305188388017764321018770435192767746145932739423507387500606563617116764196418533748380893094448060562081543927295828007016873588530479985728135015510171217414380395169021607415979109815455365309760152218352878885075237009
c = 82363935080688828403687816407414245190197520763274791336321809938555352729292372511750720874636733170318783864904860402219217916275532026726988967173244517058861515301795651235356589935260088896862597321759820481288634232602161279508285376396160040216717452399727353343286840178630019331762024227868572613111538565515895048015318352044475799556833174329418774012639769680007774968870455333386419199820213165698948819857171366903857477182306178673924861370469175
e = N
q = 11682728569119442765104955520443100815157800894598441208197112854870727710574811372574729254669600080697371923918009290021699237499317800284984683861345681
p = 46171054277314433550502593578876802976126614469930960512504812790589501500634087385124270498497135178250381413608162419922589329573991058504482940549550990812496782396771932599800636901295867760056413478165542887208036189079832707301595316035118578227851919617106397634601546986746993172265255550456834105569

tmp = pow(2,d*N,N) - 2
pq = gmpy2.gcd(tmp,N)

m = pow(c,d,pq)
print(bytes.fromhex(hex(m)[2:]))
# D0g3xGC{W1sh_Y0u_Go0d_L@ucK-111}

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

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

    x3 = (x1*y2 + y1*x2) * inverse(1 + d*x1*x2*y1*y2, p) % p
    y3 = (y1*y2 - a*x1*x2) * inverse(1 - d*x1*x2*y1*y2, p) % p
    return (x3, y3)

def mul(x, P):
    Q = (0, 1)
    while x > 0:
        if x % 2 == 1:
            Q = add(Q, P)
        P = add(P, P)
        x = x >> 1
    return Q

p = 64141017538026690847507665744072764126523219720088055136531450296140542176327
a = 362
d = 7
e=0x10001

gx=bytes_to_long(b'D0g3xGC{*****************}')

PR.<y>=PolynomialRing(Zmod(p))
f=(d*gx^2-1)*y^2+(1-a*gx^2)
gy=int(f.roots()[0][0])

assert (a*gx^2+gy^2)%p==(1+d*gx^2*gy^2)%p

G=(gx,gy)

eG = mul(e, G)
print(eG)

#eG = (34120664973166619886120801966861368419497948422807175421202190709822232354059, 11301243831592615312624457443883283529467532390028216735072818875052648928463)

exp：

ECRSA ，Twisted Edwards Curves-->Montgomery curves-->Weierstrass curves

转成 Weierstrass curves，将 G求出来后再转回 Twisted Edwards Curves 

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
from sage.all import EllipticCurve
from Crypto.Util.number import *


c = 1
eG = (34120664973166619886120801966861368419497948422807175421202190709822232354059, 11301243831592615312624457443883283529467532390028216735072818875052648928463)
p = 64141017538026690847507665744072764126523219720088055136531450296140542176327
a = 362
d = 7
e=0x10001

assert (a * eG[0] ** 2 + eG[1] ** 2) % p == c ** 2 * (1 + d * eG[0] ** 2 * eG[1] ** 2) % p
print("符合曲线方程 ax^2+y^2 = c^2(1+dx^2y^2)")


def TEdwards_to_TEdwards(G, a, c, d):
    x, y = G
    x1 = x * pow(c, -1, p)
    y1 = y * pow(c, -1, p)
    d = d * c ** 4
    G = (x1, y1)
    return (G, a, d)


def TEdwards_to_Montgomery(G, a, d):
    x, y = G
    A = 2 * (a + d) * pow(a - d, -1, p)
    B = 4 * pow(a - d, -1, p)
    u = (1 + y) * pow(1 - y, -1, p)
    v = u * pow(x, -1, p)
    G = (u, v)
    return (G, A, B)


def Montgomery_to_Weierstrass(G, A, B):
    x, y = G
    u = x * pow(B, -1, p) + A * pow(3 * B, -1, p)
    v = y * pow(B, -1, p)
    a = (3 - A ** 2) * pow(3 * B ** 2, -1, p)
    b = (2 * A ** 3 - 9 * A) * pow(27 * B ** 3, -1, p)
    G = (u, v)
    return (G, a, b)

S = eG

S, a2, d2 = TEdwards_to_TEdwards(S, a, c, d)
S, A2, B2 = TEdwards_to_Montgomery(S, a2, d2)
S, a2, b2 = Montgomery_to_Weierstrass(S, A2, B2)

assert S[1] ** 2 % p == (S[0] ** 3 + a2 * S[0] + b2) % p
print("符合曲线方程 y^2 = x^3+ax+b")

print(a2)
# -1224261044206399925356430010135296712635792417521135910885416781888600933905620865199856868360889789284943068368564365666276380479381907366960457257772903953976709302103704785389309480484333474620264496615838536762521933374939312718759

E = EllipticCurve(GF(p), [a2, b2])

S = E(S)

# 曲线基点的阶
# n = E.order()
order1 = E.order()

d = gmpy2.invert(e,order1)

mx,my = (int(d) * S).xy()
print(mx)
print(my)
print(long_to_bytes(int(mx)))
print(long_to_bytes(int(my)))

print(A2)
print(B2)

# 符合曲线方程 ax^2+y^2 = c^2(1+dx^2y^2)
# 符合曲线方程 y^2 = x^3+ax+b
# -1224261044206399925356430010135296712635792417521135910885416781888600933905620865199856868360889789284943068368564365666276380479381907366960457257772903953976709302103704785389309480484333474620264496615838536762521933374939312718759
# 27187730508972340952968757317784016242701318562300937028671961847912353008932
# 28762061935048981479334030974369661189235127913239080624566845477265058969851
# b'<\x1b\xb5\xccEhK2\xce\x94Q\xa8Ll3\xb6\x87\xd8\x85\xa0h\xe5\x01x\xd4\x96]\xbbI\\\x8d$'
# b'?\x96\xc0\n[\xff,u\xe2\xc8\xe9\xc0v\xf7X\x84\x8c\xc7\xddU\xa8E\xa1\xe2\x9c\x1b\xe2M\xb6\x9a8\xfb'
# 30268417194578758903998786511102912346647687061485835281133993640313353432764388
# 164056461759234465604329466184839633315163615509408321306959315123649612101704
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
import libnum

x = 27187730508972340952968757317784016242701318562300937028671961847912353008932
y = 28762061935048981479334030974369661189235127913239080624566845477265058969851
p = 64141017538026690847507665744072764126523219720088055136531450296140542176327

GG = (x,y)

def Montgomery_to_Weierstrass_inv(G, A, B):
    x, y = G
    u = (x - A * pow(3 * B, -1, p))*B
    v = y * B
    G = (u, v)
    return (G)

A2 = 30268417194578758903998786511102912346647687061485835281133993640313353432764388
B2 = 164056461759234465604329466184839633315163615509408321306959315123649612101704
GM = Montgomery_to_Weierstrass_inv(GG,A2,B2)
Gx,Gy =(GM)

x = libnum.invmod(Gy,p)*Gx % p    
print(x)
print(x.bit_length())
print(libnum.n2s(x))

# D0g3xGC{SOlvE_The_Edcurv3}
-------------　　　　本文结束　　感谢阅读　　　　-------------