枫霜月雨のblog

Maple-rain

0%

国赛密码部分wp

发表于 更新于 分类于
本文字数： 13k 阅读时长 ≈ 12 分钟

国赛密码部分wp

这次国赛只做出两道密码，很丢人，便在赛后将能力范围内的赛题简单复现一下。

一卷：classic

题目：

1
AXAXDFDXXAFADFGFXAADFGDXGFDXFFDFAXDXFFFFXGXGAAXAGAFDDXFFDXFFDXDXDXDXGFDFAXFXAADXAAGAXGDGXAXAFAXXFFXADFFGAADXDXAXDFDFDXXAXXDXDAAAAAFAXAAAFGGAFGFGXADXXADFGADXDFDFGAGFDGAXFGAXDGDADXFFFFDAGFADXGDX

解答：

很明显的ADFGX加密，且不给密钥和关键字，也没有hint。显然，出题人希望密码手们能在8小时内自主研发出量子计算机来攻克这题。

复现过程：

使用以下网址

image-20210519130756056

密钥使用以下公开密码表：PHQGMEAYNOFDXKRCVSZWBUTIL

关键字key清空，就能得到一串啥都看不懂的东西：

1
MMYOBFYSBHKOSOXYMOXXIIPBCDOXOXOOOOSYMRPOPCINBBFLXBYKPOOMYYOBLOEPPFBPKCKKBOBYCOYYCSNMKMNEOXXESHIO

没想到吧，然后要进行栅栏密码

image-20210519131121813

然后还要凯撒

image-20210519131157761

终于发现了有一段CISCN字样。将里面的英语翻译一下，即可得到flag

本题总结：

比赛时完全没有做出来，时间都花在爆破密钥、猜关键字、寻觅量子计算机和祈祷图灵转世上了。

参考资料：

1.4 ADFGX原理

睡不醒的某某车赛后wp

二卷：move

题目：

output.txt:

1
2
3
4
5
6
n = 80263253261445006152401958351371889864136455346002795891511487600252909606767728751977033280031100015044527491214958035106007038983560835618126173948587479951247946411421106848023637323702085026892674032294882180449860010755423988302942811352582243198025232225481839705626921264432951916313817802968185697281
e = 67595664083683668964629173652731210158790440033379175857028564313854014366016864587830963691802591775486321717360190604997584315420339351524880699113147436604350832401671422613906522464334532396034178284918058690365507263856479304019153987101884697932619200538492228093521576834081916538860988787322736613809
h1 = 3518005
h2 = 641975
c = (6785035174838834841914183175930647480879288136014127270387869708755060512201304812721289604897359441373759673837533885681257952731178067761309151636485456082277426056629351492198510336245951408977207910307892423796711701271285060489337800033465030600312615976587155922834617686938658973507383512257481837605, 38233052047321946362283579951524857528047793820071079629483638995357740390030253046483152584725740787856777849310333417930989050087087487329435299064039690255526263003473139694460808679743076963542716855777569123353687450350073011620347635639646034793626760244748027610309830233139635078417444771674354527028)

task.py

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
from Crypto.Util.number import *
from math import sqrt, gcd
import random

BITS = 512
f = open("flag.txt", "rb")
flag = f.read()
f.close()

def get_prime(nbit):
    while True:
        p = getPrime(nbit)
        if p % 3 == 2:
            return p


def gen(nbit):
    p = get_prime(nbit)
    q = get_prime(nbit)
    if q > p:
        p, q = q, p
    n = p * q
    bound = int(sqrt(2 * n)) // 12
    while True:
        x = random.randint(1, round(sqrt(bound)))
        y = random.randint(1, bound) // x
        zbound = int(((p - q) * round(n ** 0.25) * y) // (3 * (p + q)))
        z = zbound - ((p + 1) * (q + 1) * y + zbound) % x
        e = ((p + 1) * (q + 1) * y + z) // x
        if gcd(e, (p + 1) * (q + 1)) == 1:
            break
    gifts = [int(bin(p)[2:][:22], 2), int(bin(p)[2:][256:276], 2)]
    return n, e, gifts


def add(p1, p2):
    if p1 == (0, 0):
        return p2
    if p2 == (0, 0):
        return p1
    if p1[0] == p2[0] and (p1[1] != p2[1] or p1[1] == 0):
        return (0, 0)
    if p1[0] == p2[0]:
        tmp = (3 * p1[0] * p1[0]) * inverse(2 * p1[1], n) % n
    else:
        tmp = (p2[1] - p1[1]) * inverse(p2[0] - p1[0], n) % n
    x = (tmp * tmp - p1[0] - p2[0]) % n
    y = (tmp * (p1[0] - x) - p1[1]) % n
    return (int(x), int(y))


def mul(n, p):
    r = (0, 0)
    tmp = p
    while 0 < n:
        if n & 1 == 1:
            r = add(r, tmp)
        n, tmp = n >> 1, add(tmp, tmp)
    return r


n, e, hint = gen(BITS)
pt = (bytes_to_long(flag[:len(flag) // 2]), bytes_to_long(flag[len(flag) // 2:]))
c = mul(e, pt)
f = open("output.txt", "w")
f.write(f"n = {n}\n")
f.write(f"e = {e}\n")
f.write(f"h1 = {hint[0]}\n")
f.write(f"h2 = {hint[1]}\n")
f.write(f"c = {c}\n")
f.close()

解答：

虎符2021 simultaneous原题简化版

直接上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
from Crypto.Util.number import inverse, long_to_bytes
 
def add(p1, p2):
    if p1 == (0, 0):
        return p2
    if p2 == (0, 0):
        return p1
    if p1[0] == p2[0] and (p1[1] != p2[1] or p1[1] == 0):
        return (0, 0)
    if p1[0] == p2[0]:
        tmp = (3 * p1[0] * p1[0]) * inverse(2 * p1[1], n) % n
    else:
        tmp = (p2[1] - p1[1]) * inverse(p2[0] - p1[0], n) % n
    x = (tmp * tmp - p1[0] - p2[0]) % n
    y = (tmp * (p1[0] - x) - p1[1]) % n
    return (int(x), int(y))
 
def mul(n, p):
    r = (0, 0)
    tmp = p
    while 0 < n:
        if n & 1 == 1:
            r = add(r, tmp)
        n, tmp = n >> 1, add(tmp, tmp)
    return r
 
n = 80263253261445006152401958351371889864136455346002795891511487600252909606767728751977033280031100015044527491214958035106007038983560835618126173948587479951247946411421106848023637323702085026892674032294882180449860010755423988302942811352582243198025232225481839705626921264432951916313817802968185697281
e = 67595664083683668964629173652731210158790440033379175857028564313854014366016864587830963691802591775486321717360190604997584315420339351524880699113147436604350832401671422613906522464334532396034178284918058690365507263856479304019153987101884697932619200538492228093521576834081916538860988787322736613809
c = (6785035174838834841914183175930647480879288136014127270387869708755060512201304812721289604897359441373759673837533885681257952731178067761309151636485456082277426056629351492198510336245951408977207910307892423796711701271285060489337800033465030600312615976587155922834617686938658973507383512257481837605, 38233052047321946362283579951524857528047793820071079629483638995357740390030253046483152584725740787856777849310333417930989050087087487329435299064039690255526263003473139694460808679743076963542716855777569123353687450350073011620347635639646034793626760244748027610309830233139635078417444771674354527028)
# M = Matrix(ZZ, [[2**512, e],
#                 [0, -n]])
# GV = M.LLL()[0]
GV = (-352349739892292322999330613117511489276791137416050590322561272098135764509812116210543232353192946492907441641899508311181782397967869533800138447935440769558784357373166666205853969428654899524304252899588626355058283586558885888, -406850608655407486298019095013146348847805975120061760929682791882948049742096195978800022454159691659865169100330308708576847735609146508679126419372034710027124703842712262177437006326228856546452636094881051757653949488135598409)
x = -GV[0] >> 512
y = (e*x+GV[1])//n
k = e*x-n*y
K = k//y
def factor(K, N):
    l = 0
    r = K
    for i in range(518):
        s = (l+r)//2
        v = s*s - (9*s**2*(K-1-s)**2//(round(N**0.25)**2))
        if v < 4*N:
            l = s
        else:
            r = s
    return r
S = factor(K, n)
d = inverse(e, n+1+S)
print(b''.join(long_to_bytes(i) for i in mul(d, c)))

# 商业转载请联系作者获得授权，非商业转载请注明出处。
# For commercial use, please contact the author for authorization. For non-commercial use, please indicate the source.
# 协议(License)：署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)
# 作者(Author)：Wankko Ree
# 链接(URL)：https://www.wkr.moe/ctf/523.html
# 来源(Source)：Wankko Ree's Blog

本题总结：

本题为虎符2021密码原题。太卷了太卷了。详细原理可以看

d33b4t0巨佬博客中对虎符原题的讲解。exp改编自他的解题脚本。其中注释部分除去讲解，均为sage运行。

参考资料：

d33b4t0巨佬虎符CTF密码wp

Wankko Ree国赛wp

三卷：rsa

题目：

out:

已整理进chall.py多行注释中。

chall.py

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
from flag import text,flag
import md5
from Crypto.Util.number import long_to_bytes,bytes_to_long,getPrime

assert md5.new(text).hexdigest() == flag[6:-1]

msg1 = text[:xx]
msg2 = text[xx:yy]
msg3 = text[yy:]

msg1 = bytes_to_long(msg1)
msg2 = bytes_to_long(msg2)
msg3 = bytes_to_long(msg3)

p1 = getPrime(512)
q1 = getPrime(512)
N1 = p1*q1
e1 = 3
print pow(msg1,e1,N1)
print (e1,N1)

p2 = getPrime(512)
q2 = getPrime(512)
N2 = p2*q2
e2 = 17
e3 = 65537
print pow(msg2,e2,N2)
print pow(msg2,e3,N2)
print (e2,N2)
print (e3,N2)

p3 = getPrime(512)
q3 = getPrime(512)
N3 = p3*q3
print pow(msg3,e3,N3)
print (e3,N3)
print p3>>200

'''
cmsg1_e1_n1 = 19105765285510667553313898813498220212421177527647187802549913914263968945493144633390670605116251064550364704789358830072133349108808799075021540479815182657667763617178044110939458834654922540704196330451979349353031578518479199454480458137984734402248011464467312753683234543319955893
e1_n1 = (3, 123814470394550598363280518848914546938137731026777975885846733672494493975703069760053867471836249473290828799962586855892685902902050630018312939010564945676699712246249820341712155938398068732866646422826619477180434858148938235662092482058999079105450136181685141895955574548671667320167741641072330259009L)
cmsg2_e2_n2 = 54995751387258798791895413216172284653407054079765769704170763023830130981480272943338445245689293729308200574217959018462512790523622252479258419498858307898118907076773470253533344877959508766285730509067829684427375759345623701605997067135659404296663877453758701010726561824951602615501078818914410959610
cmsg2_e3_n2 = 91290935267458356541959327381220067466104890455391103989639822855753797805354139741959957951983943146108552762756444475545250343766798220348240377590112854890482375744876016191773471853704014735936608436210153669829454288199838827646402742554134017280213707222338496271289894681312606239512924842845268366950
e2_n2 = (17, 111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977L)
e3_n2 = (65537, 111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977L)
cmsg3_e3_n3 = 59213696442373765895948702611659756779813897653022080905635545636905434038306468935283962686059037461940227618715695875589055593696352594630107082714757036815875497138523738695066811985036315624927897081153190329636864005133757096991035607918106529151451834369442313673849563635248465014289409374291381429646
e3_n3 = (65537, 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147L)
高位p3 = 7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902
'''

解答：

送分题，都是很常见的rsa套路。

从题目可以看出，flag为text的md5值得到。然后text被拆成了3段，需要分别解出message1,message2,message3，拼接成text。

第一段是小加密指数爆破

1
2
3
4
5
6
7
8
9
from Crypto.Util.number import *
import gmpy2
n = 123814470394550598363280518848914546938137731026777975885846733672494493975703069760053867471836249473290828799962586855892685902902050630018312939010564945676699712246249820341712155938398068732866646422826619477180434858148938235662092482058999079105450136181685141895955574548671667320167741641072330259009
e = 3
c = 19105765285510667553313898813498220212421177527647187802549913914263968945493144633390670605116251064550364704789358830072133349108808799075021540479815182657667763617178044110939458834654922540704196330451979349353031578518479199454480458137984734402248011464467312753683234543319955893
k = 0
while (gmpy2.iroot(c + k * n, e)[1] == False):
    	k += 1
print(long_to_bytes(gmpy2.iroot(c + k *n,e)[0]))

image-20210519230937082

解得k=0 ？？？鞭尸红明谷2021密码第一道RSA？

第二段共模攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2
from Crypto.Util.number import long_to_bytes,bytes_to_long

n = 111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977
e1 = 17
c1 = 54995751387258798791895413216172284653407054079765769704170763023830130981480272943338445245689293729308200574217959018462512790523622252479258419498858307898118907076773470253533344877959508766285730509067829684427375759345623701605997067135659404296663877453758701010726561824951602615501078818914410959610
e2 = 65537
c2 = 91290935267458356541959327381220067466104890455391103989639822855753797805354139741959957951983943146108552762756444475545250343766798220348240377590112854890482375744876016191773471853704014735936608436210153669829454288199838827646402742554134017280213707222338496271289894681312606239512924842845268366950

g, x, y = gmpy2.gcdext(e1, e2) #先通过扩展欧几里得算法求出x * e1 + y * e2 = 1中的x和y
#print(x, y)
m = pow(c1, x, n) * pow(c2, y, n) % n #计算(c1的x次方 * c2的y次方) mod n
#print(m)
print(long_to_bytes(m))

image-20210519231043784

第三段coppersmith定理已知高位p

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#Sage
from sage.all import *
n = 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147L
p4 = 7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902
e =  65537
pbits = 512
kbits = pbits - p4.nbits()
print(p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^kbits, beta=0.4)
#经过以上一些函数处理后，n和p已经被转化为10进制
if roots:        
	p = p4+int(roots[0]) 
	print("n: "+str(n))
	print("p: "+str(p))
	print("q: "+str(n//p))

image-20210519231438772

解出p、q后，直接求欧拉函数的逆元一把梭了。

得到三段message后，拼接一下得到text，再用python2求一下md5，得到答案：

1
CISCN{3943e8843a19149497956901e5d98639}

本题总结：

应该是防止三卷爆零设置的rsa套娃题，都是相当基础的解法，不再做分析。

参考链接：

翅膀师傅的RSA讲解

-------------本文结束感谢您的阅读-------------