国城杯CTF Crypto Writeup

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
#sage
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)

题目实现了一个Twisted Edwards曲线的加法/乘法运算脚本。

方程可由assert语句推出： \(ax^2+y^2\equiv dx^2y^2+1 (mod p)\).

椭圆曲线具有多种表示形式，可以将Twisted Edwards的方程作变量代换，变为熟悉的Weierstrass方程，对其求系数后构建EllipticCurve，
利用Sagemath求其阶后，遵循阿贝尔群的加法法则，乘以e在其阶下的模逆即可。

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

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

x2,y2 =  (34120664973166619886120801966861368419497948422807175421202190709822232354059, 11301243831592615312624457443883283529467532390028216735072818875052648928463)
assert (a*x2^2+y2^2)%p==(1+d*x2^2*y2^2)%p

#一阶段，Edwards转Montgomery
A = 2*(a+d)/(a-d)
B = 4/(a-d)

#二阶段，Montgomery转Weierstrass
aa = (3-A^2)/(3*B^2)
bb = (2*A^3-9*A) / (27*B^3)

E = EllipticCurve(Zmod(p),[0,0,0,aa,bb])
d = int(pow(e,-1,E.order()))

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

eG = (34120664973166619886120801966861368419497948422807175421202190709822232354059, 11301243831592615312624457443883283529467532390028216735072818875052648928463)

print(long_to_bytes(int(mul(d,eG)[0])))

Flag：D0g3xGC{SOlvE_The_Edcurv3}

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
'''

本题分为两部分，第一部分将含有e的信息作为DSA的私钥进行加密，涉及基于蛇皮随机数复用的数学分析
第二部分将p,q的值放进了一个平方和问题

先看第一部分，本来想直接上手写草稿图的
\(k_1 \equiv H_1s_1^{-1}+r_1s_1^{-1}x (mod q)\) \(k_1^2 \equiv H_2s_2^{-1}+r_2s_2^{-1}x (mod q)\)
记 \(r_is_i = A_i\)，\(H_iS_i = B_i\)
整理后可以得到 \(A_1x^2 + (2A_1B_1 - A_2)x + (B_1^2-B_2) \equiv 0 (mod q)\)
利用sage解该同余式方程即可。
第二部分平方和的divisors解法参考了asksage上的一行代码，非常简明精炼。

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
from Crypto.Util.number import *
(H1, r1, s1) = 659787401883545685817457221852854226644541324571, 334878452864978819061930997065061937449464345411, 282119793273156214497433603026823910474682900640
(H2, r2, s2) = 156467414524100313878421798396433081456201599833, 584114556699509111695337565541829205336940360354, 827371522240921066790477048569787834877112159142
q = 829396411171540475587755762866203184101195238207

ss1 = int(pow(s1,-1,q))
ss2 = int(pow(s2,-1,q))

A1 = r1 * ss1
A2 = r2 * ss2
B1 = H1 * ss1
B2 = H2 * ss2

P.<x>=Zmod(q)[]
eq = A1^2*x^2 + (2*A1*B1-A2)*x + (B1^2-B2)
print(eq.roots())
#[(91973915966463187834053272623425597244095846333, 1), (1865444199836044046649, 1)]
#第二个数to_bytes可以得到b'e = 44519'
def all_two_squares(n):
    return [(abs(d[0]),abs(d[1])) for d in divisors(GaussianIntegers()(n)) if norm(d)==n]

probs = all_two_squares(C)
for p,q in probs:
    if not isPrime(int(p)) or not isPrime(int(q)):
        continue
    e = 44519
    c = 18947793008364154366082991046877977562448549186943043756326365751169362247521
    n = p * q
    d = pow(e,-1,(p-1)*(q-1))
    print(long_to_bytes(int(pow(c,d,n))))

不得不说"sage magic"还是挺好用的（毕竟免去了手搓/import乱七八糟东西的麻烦）

flag: D0g3xGC{EZ_DSA_@nd_C0mplex_QAQ}

EzRSA

题目代码

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
'''

就是一个Schmidt-Samoa密码系统，起名叫EzRSA还是有些喧宾夺主的感觉
简单的数论，一把梭。

由欧拉定理可得：\(a^{(p-1)(q-1)} \equiv 1 (mod pq)\)

又有 \(Nd \equiv 1 (mod (p-1)(q-1))\)

故存在 \(a^{Nd} \equiv a^{1+k(p-1)(q-1)} \equiv a (mod pq)\)

故求解 \(gcd(a^{Nd},N)\) 即有极大概率得到pq，此处a可取任意的较小数（如2）

最后执行解密过程即可： \(m \equiv c^{d} (mod pq)\)

exp

1
2
3
4
5
6
7
8
9
from Crypto.Util.number import *
from gmpy2 import gcd

n = 539403894871945779827202174061302970341082455928364137444962844359039924160163196863639732747261316352083923762760392277536591121706270680734175544093484423564223679628430671167864783270170316881238613070741410367403388936640139281272357761773388084534717028640788227350254140821128908338938211038299089224967666902522698905762169859839320277939509727532793553875254243396522340305880944219886874086251872580220405893975158782585205038779055706441633392356197489
d = 58169755386408729394668831947856757060407423126014928705447058468355548861569452522734305188388017764321018770435192767746145932739423507387500606563617116764196418533748380893094448060562081543927295828007016873588530479985728135015510171217414380395169021607415979109815455365309760152218352878885075237009
c = 82363935080688828403687816407414245190197520763274791336321809938555352729292372511750720874636733170318783864904860402219217916275532026726988967173244517058861515301795651235356589935260088896862597321759820481288634232602161279508285376396160040216717452399727353343286840178630019331762024227868572613111538565515895048015318352044475799556833174329418774012639769680007774968870455333386419199820213165698948819857171366903857477182306178673924861370469175

pq = gcd(pow(2,n*d,n)-2,n)
print(long_to_bytes(pow(c,d,pq)))

flag: D0g3xGC{W1sh_Y0u_Go0d_L@ucK-111}

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true