writeup for 2020 祥云杯 Crypto

Posted on Edited on In Word count in article: 10k Reading time ≈ 9 mins.

只会做密码的菜鸡

Crypto

0x01 SimpleRSA

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
import gmpy2

p, q, r = [getPrime(512) for i in range(3)]
n = p * q * r
phi = (p - 1) * (q - 1) * (r - 1)
d = getPrime(256)
e = gmpy2.invert(d , phi)

flag = b"flag{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}"

c = pow(bytes_to_long(flag), e, n)

print(e, n)
print(c)
'''
1072295425944136507039938677101442481213519408125148233880442849206353379681989305000570387093152236263203395726974692959819315410781180094216209100069530791407495510882640781920564732214327898099944792714253622047873152630438060151644601786843683746256407925709702163565141004356238879406385566586704226148537863811717298966607314747737551724379516675376634771455883976069007134218982435170160647848549412289128982070647832774446345062489374092673169618836701679 
1827221992692849179244069834273816565714276505305246103435962887461520381709739927223055239953965182451252194768935702628056587034173800605827424043281673183606478736189927377745575379908876456485016832416806029254972769617393560238494326078940842295153029285394491783712384990125100774596477064482280829407856014835231711788990066676534414414741067759564102331614666713797073811245099512130528600464099492734671689084990036077860042238454908960841595107122933173
1079929174110820494059355415059104229905268763089157771374657932646711017488701536460687319648362549563313125268069722412148023885626962640915852317297916421725818077814237292807218952574111141918158391190621362508862842932945783059181952614317289116405878741758913351697905289993651105968169193211242144991434715552952340791545323270065763529865010326192824334684413212357708275259096202509042838081150055727650443887438253964607414944245877904002580997866300452
'''

思路

说实话这题能做出来也是运气好…
wiener还没有自己复现过, 一直都是用现成的脚本. 而这次的n是多个素因子的, 之前的脚本不能用了. 本来是想着去学一下怎么复现的, 结果直接找到原题了(祥云杯好像挺多都能找到原题或者是很像的题的

这是找到的原题的wp

直接抄脚本就能算出d了, 所以到底该怎么写wiener呢?

咕咕咕…有空一定学会它!

代码

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
def hex2text(Hex):  
    if len(Hex) % 2: Hex = '0' + Hex
    return ''.join([chr(int(b, 16)) for b in [Hex[i:i + 2] for i in range(0, len(Hex), 2)]])


def dec2text(Dec):  
    Hex = hex(Dec)[2:]
    return hex2text(Hex)


def wiener(e, n):
    m = 12345
    c = pow(m, e, n)
    q0 = 1

    list1 = continued_fraction(Integer(e) / Integer(n))
    conv = list1.convergents()
    for i in conv:
        k = i.numerator()
        q1 = i.denominator()

        for r in range(20):
            for s in range(20):
                d = r * q1 + s * q0
                m1 = pow(c, d, n)
                if m1 == m:
                    return d
        q0 = q1
c = 1079929174110820494059355415059104229905268763089157771374657932646711017488701536460687319648362549563313125268069722412148023885626962640915852317297916421725818077814237292807218952574111141918158391190621362508862842932945783059181952614317289116405878741758913351697905289993651105968169193211242144991434715552952340791545323270065763529865010326192824334684413212357708275259096202509042838081150055727650443887438253964607414944245877904002580997866300452
e = 1072295425944136507039938677101442481213519408125148233880442849206353379681989305000570387093152236263203395726974692959819315410781180094216209100069530791407495510882640781920564732214327898099944792714253622047873152630438060151644601786843683746256407925709702163565141004356238879406385566586704226148537863811717298966607314747737551724379516675376634771455883976069007134218982435170160647848549412289128982070647832774446345062489374092673169618836701679
n = 1827221992692849179244069834273816565714276505305246103435962887461520381709739927223055239953965182451252194768935702628056587034173800605827424043281673183606478736189927377745575379908876456485016832416806029254972769617393560238494326078940842295153029285394491783712384990125100774596477064482280829407856014835231711788990066676534414414741067759564102331614666713797073811245099512130528600464099492734671689084990036077860042238454908960841595107122933173
d = wiener(e,n)
print(dec2text(pow(c,d,n)))

0x02 RSAssss

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
from gmpy2 import next_prime

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

n = p * q * next_prime(p) * next_prime(q)
e = 0x10001

flag = b"flag{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}"
cipher = pow(bytes_to_long(flag), e, n)

print(n, cipher)
'''
8030860507195481656424331455231443135773524476536419534745106637165762909478292141556846892146553555609301914884176422322286739546193682236355823149096731058044933046552926707682168435727800175783373045726692093694148718521610590523718813096895883533245331244650675812406540694948121258394822022998773233400623162137949381772195351339548977422564546054188918542382088471666795842185019002025083543162991739309935972705871943787733784491735500905013651061284020447578230135075211268405413254368439549259917312445348808412659422810647972872286215701325216318641985498202349281374905892279894612835009186944143298761257 
3304124639719334349997663632110579306673932777705840648575774671427424134287680988314129312593361087606243819528298610131797078262351307396831985397555390640151391138633431951746748156610463582479645561779194981806129898009876517899450840875569675976765155608446799203699927448835004756707151281044859676695533373755798273892503194753948997947653100690841880925445059175494314198605475023939567750409907217654291430615102258523998394231436796902635077995829477347316754739938980814293304289318417443493019704073164585505217658570214989150175123757038125380996050761572021986573934155470641091678664451080065719261207
'''

思路

费马分解! 我怎么会没想到呢, 两个接近的因子就可以用fermat了.
这题也是运气好,在这个大数分解网站后台跑了两个钟分出两半来了(真的是没注意放后台跑的

分出的两半:

1
2
x1 = 89615068527538836315602124154008300286636934599617334867509053076622715365809371740037316558871796433906844464070995869293654082577887578197182408045175035339285085728002838220314068474670975228778464240088084331807420720121364486765011169669747553393661650912114228227308579940164269877101973728452252879383
x2 = 89615068527538836315602124154008300286636934599617334867509053076622715365809371740037316558871796433906844464070995869293654082577887578197182408045172781798703173650574737644914515591522256758848089955578713458715234536664415216526830967831862301518636586702212189087959136509334102772855657664091570630079

考虑到np = next_prime(p)所以p和np不会相差太远, 可以有 不妨假设

又因为p,q是随机生成的两个大素数, 他们相等的可能性太低. 而分出的x1, x2(x1>x2)非常接近, 则x1,x2可能有的组合有

或者是

(可能还有没考虑到的?…

首先尝试第一种组合(直接中了
x1和x2相减有

消元

则可以有关于q的二次方程

因为解是整数, 所以delta应该为完全平方数

所以利用这个特点可以爆破出a,b 从而解出q,再而就能有p,q+b , p+a了

(有一点不明白就是按理来说a,b只有1组?可能是我没考虑周到,跑出来4组a,b, 发现只有第四组跑出来的q是真正的q(其他三组都是kq), 所以直接采用第四组的q和a,b

想明白了! 因为二次项的系数是a, 如果a的因数里面有完全平方数, 那么就可能解出kq这个解了!

求出n的四个素因子之后常规的RSA解密就行了

代码

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
# coding=utf-8
from gmpy2 import iroot, gcd, invert
from Crypto.Util.number import long_to_bytes

n = 8030860507195481656424331455231443135773524476536419534745106637165762909478292141556846892146553555609301914884176422322286739546193682236355823149096731058044933046552926707682168435727800175783373045726692093694148718521610590523718813096895883533245331244650675812406540694948121258394822022998773233400623162137949381772195351339548977422564546054188918542382088471666795842185019002025083543162991739309935972705871943787733784491735500905013651061284020447578230135075211268405413254368439549259917312445348808412659422810647972872286215701325216318641985498202349281374905892279894612835009186944143298761257
x1 = 89615068527538836315602124154008300286636934599617334867509053076622715365809371740037316558871796433906844464070995869293654082577887578197182408045175035339285085728002838220314068474670975228778464240088084331807420720121364486765011169669747553393661650912114228227308579940164269877101973728452252879383
x2 = 89615068527538836315602124154008300286636934599617334867509053076622715365809371740037316558871796433906844464070995869293654082577887578197182408045172781798703173650574737644914515591522256758848089955578713458715234536664415216526830967831862301518636586702212189087959136509334102772855657664091570630079

x = x1 - x2
for a in range(1, 2000):
    for b in range(1, 2000):
        delta_sq = (x + a * b) ** 2 + 4 * a * b * x2
        delta = iroot(delta_sq, 2)
        if delta[1]:
            p1 = (-(a * b + x) + delta[0]) // (2 * a)
            p2 = (-(a * b + x) - delta[0]) // (2 * a)
            if p1 > 0 and gcd(p1, n) != 1:
                print(p1, a, b)
            if p2 > 0 and gcd(p2, n) != 1:
                print(p2, a, b)
'''
    result:
    59509622824623675050066481062107171504849863374230362259884081452647743246974989796952759980519162117328441285479164180294347299033843912200899999033032168 1 1536
    29754811412311837525033240531053585752424931687115181129942040726323871623487494898476379990259581058664220642739582090147173649516921956100449999516516084 2 768
    14877405706155918762516620265526792876212465843557590564971020363161935811743747449238189995129790529332110321369791045073586824758460978050224999758258042 4 384
    7438702853077959381258310132763396438106232921778795282485510181580967905871873724619094997564895264666055160684895522536793412379230489025112499879129021 8 192
'''

q = 7438702853077959381258310132763396438106232921778795282485510181580967905871873724619094997564895264666055160684895522536793412379230489025112499879129021
np = x2 // q
nq = q + 192
p = np - 8

e = 0x10001
c = 3304124639719334349997663632110579306673932777705840648575774671427424134287680988314129312593361087606243819528298610131797078262351307396831985397555390640151391138633431951746748156610463582479645561779194981806129898009876517899450840875569675976765155608446799203699927448835004756707151281044859676695533373755798273892503194753948997947653100690841880925445059175494314198605475023939567750409907217654291430615102258523998394231436796902635077995829477347316754739938980814293304289318417443493019704073164585505217658570214989150175123757038125380996050761572021986573934155470641091678664451080065719261207
phi = (p - 1) * (q - 1) * (np - 1) * (nq - 1)
d = invert(e, phi)

print(long_to_bytes(pow(c, d, n)))

这道题算的时候还算轻松的, 猜出组合之后用delta爆破也不是第一次做了

总结

还是太菜…能做的就只有简单的…
剩下的密码题还有

  1. more_calc
  2. Exposure
  3. easy matrix
  4. Blowfish

more_calc

看过了Nu1l的WP, S确实是可以用别的办法算的…这几天一定要把原理搞懂(这个应该不难

Exposure和easy matrix

都是需要用到LLL的知识的…这个真的还没学会 吃了大亏, 格理论真的要好好的去查一查资料了
特别是Exposure…论文都查到了!就是因为不会LLL就不会做了(好菜啊

一定要学会LLL!

Blowfish

第一次接触Blowfish, 先暂时放着吧..

真の总结

很多理论知识还没有学会吧. 真的感觉题目是水的, 自己菜做不出来而已.
然后就是关于RSA, 做了这次明白了其实很多时候用到的方法都是已经学过的, 观察题目给的条件的特点, 再想想自己会的方法的特点(费马分两个接近pq, wiener适合特别大的e等等. 这样做的可能会更有思路更快一点