Crypto-4｜Big and Small

做题历程 & 感想

一道非常经典的低加密指数小密文攻击板子题～

还是短学期 TA 讲过所以 Bruce 就把它秒啦～

---

Writeup

当e极小（如e=3），且m也较小时

\[ c≡m^{3}(mod\ n) \]

则可以写成

\[ m^{3}=c+kn \]

进一步

\[ m=\sqrt[3]{c+kn} \]

m很小时只需暴力枚举k的值，即可得到答案。

编写 python 程序如下：

import gmpy2

n = 20279309983698966932589436610174513524888616098014944133902125993694471293062261713076591251054086174169670848598415548609375570643330808663804049384020949389856831520202461767497906977295453545771698220639545101966866003886108320987081153619862170206953817850993602202650467676163476075276351519648193219850062278314841385459627485588891326899019745457679891867632849975694274064320723175687748633644074614068978098629566677125696150343248924059801632081514235975357906763251498042129457546586971828204136347260818828746304688911632041538714834683709493303900837361850396599138626509382069186433843547745480160634787
e = 3
c = 150409620528288093947185249913242033500530715593845912018225648212915478065982806112747164334970339684262757

i = 0
while 1:
    res = gmpy2.iroot(c+i*n,3)
    if(res[1] == True):
        m = res[0]
        print(bytes.fromhex(hex(m)[2:]).decode('ascii'))
        break
    print("i="+str(i))
    i = i+1

运行即可得到 flag：flag{xt>is>s>b}

评论