实验室Crypto招新题WriteUp

shmily

分析：题目文件这种有两段信息，一段是”guess what i am：”，另一段应该就是加密后的信息。加密的信息特别长，推测可能是将密文藏在其中的某个地方，或者是某种类型文件（如图片等）转编码后的信息。划到最后发现 “==”，则加密后的信息很可能是base64编码后的信息。同时由于文本过长，推测最有可能是图片经过base64编码。

  • 使用站长工具的base64转图片功能，将信息进行解码。

  • 发现解码之后确实是一张图片，但还没有得到我们的flag。

  • 根据图片上的内容，推测是RSA加密。但是我们发现私钥d都直接给了，而且N、e、d、密文c的数值都特别小，那这部分的破解应该还有其他玄机。（不管了，先按常规解密把RSA的解密部分搞出来）

    1
    2
    3
    4
    5
    6
    7
    from Crypto.Util.number import long_to_bytes
    d = 937
    N = 2537
    c = '156 821 1616 41 140 2130 1616 793 205 1616 959 140 41 140 959'.split()
    for i in c:
        m = pow(int(i), d, N)
        print(long_to_bytes(m), end='')

    运行结果：

    1
    b'\x08'b'\x0b'b'\x0e'b'\x15'b'\x04'b'\x18'b'\x0e'b'\x14'b'\x067'b'\x11'b'\x04'b'\x15'b'\x04'b'\x11'
  • 第一次破解没有得到具有’flag’字样的文本，说明有问题。而且由于每段密文的数值很小，long_to_bytes转换应该用不上。
    1
    2
    3
    4
    5
    6
    d = 937
    N = 2537
    c = '156 821 1616 41 140 2130 1616 793 205 1616 959 140 41 140 959'.split()
    for i in c:
        m = pow(int(i), d, N)
        print(m, end=' ')
    运行结果：
    1
    8 11 14 21 4 24 14 20 5 14 17 4 21 4 17
  • 敏锐的察觉到，这些数值很小，而且没有超过25（从编号0-25的26个字母），说明这些数值可能对应26个字母。那试一下查表。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    d = 937
    N = 2537
    c = '156 821 1616 41 140 2130 1616 793 205 1616 959 140 41 140 959'.split()
    list = 'abcdefghijklmnopqrstuvwxyz'
    res = ''
    for i in c:
        m = pow(int(i), d, N)
        res += list[m]
    print(res)
    运行结果：
    1
    iloveyouforever
  • 虽然没有得到flag字样，但是我们发现解密后的信息是一句话（i love you forever），故flag应该就是flag{iloveyouforever}

hex2Virginia

分析：题目hex2Virginia，暗示可能先经历16进制转换，再进行Virginia加密。再观察题目文件文本，发现文本很长，有可能还是图片转码后的信息。再根据但是Virginia的密钥是啥呢？？？发现题目hex2Virginia，推测题目中藏着密钥：”hex”、”2”（谐音”two”，”to”，”too”）、”Virginia”。其中如果”hex”和”Virginia”提示加密方式，那么”2”最可能是密钥。

  • 使用bugku的Virginia解密工具，对”2”可能正确的密钥（谐音”two”，”to”，”too”），进行Virginia解密，然后再使用LZL在线工具将解密后的信息进行十六进制转图片试试。

  • 经过测试，two是Virginia的密钥，解密后的信息由十六进制转图片得到flag。

eerie_RSA

分析：题目eerie_RSA，很显然提示RSA加密，看看加密脚本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
from flag import text, encode
from Crypto.Util.number import bytes_to_long,getPrime


flag = encode(text.encode()).hexdigest() # 貌似你得先破译出text

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

msg1 = bytes_to_long(msg1.encode('utf-8'))
msg2 = bytes_to_long(msg2.encode('utf-8'))
msg3 = bytes_to_long(msg3.encode('utf-8'))

p1 = getPrime(1024)
q1 = getPrime(1024)
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)

还有这段加密脚本的输出out：

1
2
3
4
5
6
7
8
9
27528752709372781693551004366113434327704364966327966920113025388926796768744682470041386868052048130473156235233339186242520091753843237368352496842819494105438389493904140079513323999807825961
(3, 10868005002987872478564232564184658608497304389729124151755510645560639657768384371842392209992296907775464353385455638136302905843908960025127174501244457168020835335009494877298459630560752552574900002346680159767602205707678172534063759885003648154304972388531365704272254343438311540595215464787689307248794947430403553990346151443577265222135793045464254869363690118113968871272497506584736299145988038274048038272072698682403015167982366978448788068847892982237547719448320770963530412422818040904700330008466831087208337851302164584780504159957343377972632123707770281440710921619869071460585665076910505466023)
57759833095439932548929032355173977128055814411392871278525447238499198255131762911016950621597755676744124529654615332697148158364858793088308482252111010219325180722773181241427725010781167907766598041304824280786426399864293928708446535160603690193883778066146829602063397058591872667825084423994582952739
125833879567603829472997469832639672082944929255438014095148199114259589079041705920285390696681067739294166723113861842341292475088350641990738527138272224063130673971984768633189217086321219116703740213157924297089706139330387995225875779975500347953323858654533018779318725831207548708859936604519275697200
(17, 130549149634325998934371679372441877305654417728218277372812347216175714010949976506043489052602323484946527833025486931514892896144092697702747887712285987612213704341011964521388429778790977851167052801660525961166295744673414939170472668041781977595893453774403628628815443424490188961875827460096543600547)
(65537, 130549149634325998934371679372441877305654417728218277372812347216175714010949976506043489052602323484946527833025486931514892896144092697702747887712285987612213704341011964521388429778790977851167052801660525961166295744673414939170472668041781977595893453774403628628815443424490188961875827460096543600547)
54367958849933200243179462444122523871491663312935351993323068511750118996062087190152015173394121762028285701153282290238606935019537485343711645316168503284124751816314774988383949340156555258402564393372354689757624797457471156036687040685106233116890561656032445139547018538521138133210859844566234792455
(65537, 116662545522798722893275827592805290837338575225370322326893820720045572348830522763576413804861056978630559471454152633832329979917036126294342939685305794050617663883894705494591693017970891761801455755757300555988864501542743289811481012532168792014891940186182705863208247338340429673157385458363831238463)
5658290878208013932006802720085715976996571136535678140342324023380213776742744788337411960180

  • 观察加密脚本，发现密文被分为三段，每段密文长度不同。然后分别对每段密文进行不同的参数的RSA加密。

    1. msg1的加密，可以发现e的值特别小，这意味着我们可以使用低加密指数攻击。解密脚本如下：
      1
      2
      3
      c1=27528752709372781693551004366113434327704364966327966920113025388926796768744682470041386868052048130473156235233339186242520091753843237368352496842819494105438389493904140079513323999807825961
      e1=3
      m1=g.iroot(c1,e1)[0]
    2. msg2的加密，分别使用了两个不同的加密指数对同一段明文进行加密得到两段密文，这意味着我们可以尝试共模攻击。解密脚本如下：
      1
      2
      3
      4
      5
      6
      7
      c2 = 57759833095439932548929032355173977128055814411392871278525447238499198255131762911016950621597755676744124529654615332697148158364858793088308482252111010219325180722773181241427725010781167907766598041304824280786426399864293928708446535160603690193883778066146829602063397058591872667825084423994582952739
      C2 = 125833879567603829472997469832639672082944929255438014095148199114259589079041705920285390696681067739294166723113861842341292475088350641990738527138272224063130673971984768633189217086321219116703740213157924297089706139330387995225875779975500347953323858654533018779318725831207548708859936604519275697200
      n2=130549149634325998934371679372441877305654417728218277372812347216175714010949976506043489052602323484946527833025486931514892896144092697702747887712285987612213704341011964521388429778790977851167052801660525961166295744673414939170472668041781977595893453774403628628815443424490188961875827460096543600547
      e2=17
      e3=65537
      s,s1,s2=g.gcdext(e2,e3)
      m2=(pow(c2,s1,n2)*pow(C2,s2,n2))%n2

    3. msg3的加密，我们发现”print (p3>>200)”，这意味着p3的高位泄露，可以使用sagemath工具运行脚本来爆获取p3。解密脚本如下：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      # 在线sagemath：https://sagecell.sagemath.org/

      p3 = 5658290878208013932006802720085715976996571136535678140342324023380213776742744788337411960180
      n = 116662545522798722893275827592805290837338575225370322326893820720045572348830522763576413804861056978630559471454152633832329979917036126294342939685305794050617663883894705494591693017970891761801455755757300555988864501542743289811481012532168792014891940186182705863208247338340429673157385458363831238463

      #全位数
      pbits = 512

      #缺省位数
      kbits = pbits - p4.nbits()  #nbits()位数
      print (p4.nbits())
      p4 = p4 << kbits
      PR.<x> = PolynomialRing(Zmod(n))

      f = x + p4
      x0 = f.small_roots(X=2^kbits, beta=0.4)[0]
      p = p4+x0
      print ("p: ", hex(int(p)))
      assert n % p == 0

      获取到p3，使用Python脚本进行解密：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      c3=54367958849933200243179462444122523871491663312935351993323068511750118996062087190152015173394121762028285701153282290238606935019537485343711645316168503284124751816314774988383949340156555258402564393372354689757624797457471156036687040685106233116890561656032445139547018538521138133210859844566234792455
      e3=65537
      n3=116662545522798722893275827592805290837338575225370322326893820720045572348830522763576413804861056978630559471454152633832329979917036126294342939685305794050617663883894705494591693017970891761801455755757300555988864501542743289811481012532168792014891940186182705863208247338340429673157385458363831238463

      p=0xad9b53775a8e93d4b711e7055dcb1ab264a9745e966e09374d31f2e11462e587a5cbc112232d747dcd5d3dd53747d1954f7d0bc753c5f6fbbe7d0c3d21753257
      q=n3//p
      phi=(p-1)*(q-1)
      d=inverse(e3,phi)
      m3=pow(c3,d,n3)
    4. 将3段解出来的明文先转为字符串再拼接。
      1
      text=long_to_bytes(m1)+long_to_bytes(m2)+long_to_bytes(m3)

由于”flag = encode(text.encode()).hexdigest()”，使用了md5，所以结合以上脚本，得到最终解密脚本：

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
from Crypto.Util.number import *
import gmpy2 as g
from hashlib import md5

'''低加密指数小明文，求第一部分'''
c1=27528752709372781693551004366113434327704364966327966920113025388926796768744682470041386868052048130473156235233339186242520091753843237368352496842819494105438389493904140079513323999807825961
e1=3
m1=g.iroot(c1,e1)[0]

'''共模攻击，求第二部分'''
c2 = 57759833095439932548929032355173977128055814411392871278525447238499198255131762911016950621597755676744124529654615332697148158364858793088308482252111010219325180722773181241427725010781167907766598041304824280786426399864293928708446535160603690193883778066146829602063397058591872667825084423994582952739
C2 = 125833879567603829472997469832639672082944929255438014095148199114259589079041705920285390696681067739294166723113861842341292475088350641990738527138272224063130673971984768633189217086321219116703740213157924297089706139330387995225875779975500347953323858654533018779318725831207548708859936604519275697200
n2=130549149634325998934371679372441877305654417728218277372812347216175714010949976506043489052602323484946527833025486931514892896144092697702747887712285987612213704341011964521388429778790977851167052801660525961166295744673414939170472668041781977595893453774403628628815443424490188961875827460096543600547
e2=17
e3=65537
s,s1,s2=g.gcdext(e2,e3)
m2=(pow(c2,s1,n2)*pow(C2,s2,n2))%n2

'''p高位泄露,求第三部分'''
'''
https://sagecell.sagemath.org/
 
#p4已知高位
p4 = 5658290878208013932006802720085715976996571136535678140342324023380213776742744788337411960180
n = 116662545522798722893275827592805290837338575225370322326893820720045572348830522763576413804861056978630559471454152633832329979917036126294342939685305794050617663883894705494591693017970891761801455755757300555988864501542743289811481012532168792014891940186182705863208247338340429673157385458363831238463
 
#全位数
pbits = 512
 
#缺省位数
kbits = pbits - p4.nbits()  #nbits()位数
print (p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
 
f = x + p4
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]
p = p4+x0
print ("p: ", hex(int(p)))
assert n % p == 0
'''
c3=54367958849933200243179462444122523871491663312935351993323068511750118996062087190152015173394121762028285701153282290238606935019537485343711645316168503284124751816314774988383949340156555258402564393372354689757624797457471156036687040685106233116890561656032445139547018538521138133210859844566234792455
e3=65537
n3=116662545522798722893275827592805290837338575225370322326893820720045572348830522763576413804861056978630559471454152633832329979917036126294342939685305794050617663883894705494591693017970891761801455755757300555988864501542743289811481012532168792014891940186182705863208247338340429673157385458363831238463

p=0xad9b53775a8e93d4b711e7055dcb1ab264a9745e966e09374d31f2e11462e587a5cbc112232d747dcd5d3dd53747d1954f7d0bc753c5f6fbbe7d0c3d21753257
q=n3//p
phi=(p-1)*(q-1)
d=inverse(e3,phi)
m3=pow(c3,d,n3)

text=long_to_bytes(m1)+long_to_bytes(m2)+long_to_bytes(m3)
print(text, '\n')

'''md5加密'''
print(md5(text).hexdigest())

运行脚本得到：

1
2
3
b'If you see this, it means you have successfully cracked my encryption, Three types of RSA encryption, thats pretty cool, isnt it? But it is not over yet, Remember to use MD5 encryption to get the flag.' 

3012329b11d9855a7437ff6fc3c8d99d

得到flag：flag{3012329b11d9855a7437ff6fc3c8d99d}