偶遇题目，拼尽全力无法战胜，故深入学习

参考文章，建议细细研读

https://zhuanlan.zhihu.com/p/4783052681

https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch19.pdf

https://doc.sagemath.org/html/en/reference/polynomial_rings/sage/rings/polynomial/polynomial_modn_dense_ntl.html#sage.rings.polynomial.polynomial_modn_dense_ntl.small_roots

https://www.ruanx.net/coppersmith/

定理

设N是一个大整数，$ p \geq N^\beta $是 N 的一个因子，设 $ f(x) $ 是一个d阶(次数为d)的多项式，令$ X=\frac{1}{2}N^{\frac{1}{d} - \varepsilon} $，其中$ 0\le\varepsilon\le min(0.18,\frac{1}{d}) $，那么对于给定的$ (N,f(x)) $，有

  • 在模N意义下，可以快速求出$ f(x)=0 $满足$ \left | x \right | \le X $的全体正整数解（就是求出X以内的根）
  • 给定$ \beta $，可以快速求出模p意义下较小的根（就是求模因子意义下的根，可以解决低位丢失类题目）

原理

有了这个定理，相信大家一定好奇为什么，为什么可以这么做，但是这个原理挺复杂的，站长现水平无法深入理解，但是大家可以点击上面的推荐文章（尤其那本书，感觉找到宝贝了），下面会简单讲一下我的理解，不一定对，建议直接看截图

就是把一个多项式看成一个多维向量，再构造成一个格，之后再运用LLL格基规约找到一个范数最小的向量，然后根据一个引理，就可以找到这个多项式的一个根。

small_roots

知道这么一个定理后我们期望在代码层面实现它，这就要用到Sagemath里的small_roots这个函数，下面会具体介绍这个函数，首先放一个具体实现

1
2
3
4
R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
P = p + x
low_p = P.monic().small_roots(X = 2**340, beta = 0.4)
print(low_p)

PolynomialRing ：构造多项式环

Zmod(n) ：模运算

implementation=’NTL’ ：执行 NTL

small_roots( X=？ , beta=？ , epsilon=？)：计算多项式的小整数根，返回结果是一个列表

X：根的绝对上界，比如说下面那道题目，上界就是2**340

beta：coopersmith里的一个参数，给定$ \beta $，以快速求出模某个p意义下较小的根，其中$ p\ge n^\beta $，是n的因数，$ \beta $一般取0.4

epsilon：也是coopersmith里的一个参数，程序默认好像是$ \beta/8 $，平时不太会用到这个参数，需要时加在beta后面就行

monic()：用于将多项式的首项系数归一化为1。它接受一个多项式作为参数，然后返回一个新的多项式，其中首项系数已经被归一化为1。这个过程可以简化多项式的表达式，使其更易于计算和分析。

这样简单的使用方法就了解了，可以看看下面的题目，自己运用一下

题目

1.where is P?

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
m=bytes_to_long(b'XXXX')
e=65537
p=getPrime(1024)
q=getPrime(1024)
n=p*q
print(p)
c=pow(m,e,n)
P=p>>340
print(P)
a=pow(P,3,n)
print("n=",n)
print("c=",c)
print("a=",a)
#n= 24479907029118467064460793139240403258697681144532146836881997837526487637306591893357774423547391867013441147680031968367449693796015901951120514250935018725570026327610524687128709707340727799633444550317834481416507364804274266363478822257132586592232042108076935945436358397787891169163821061005102693505011197453089873909085170776511350713452580692963748763166981047023704528272230392479728897831538235554137129584665886878574314566549330671483636900134584707867654841021494106881794644469229030140144595938886437242375435914268001721437309283611088568191856208951867342004280893021653793820874747638264412653721
#c= 6566517934961780069851397787369134601399136324586682773286046135297104713708615112015588908759927424841719937322574766875308296258325687730658550956691921018605724308665345526807393669538103819281108643141723589363068859617542807984954436567078438099854340705208503317269397632214274507740533638883597409138972287275965697689862321166613821995226000320597560745749780942467497435742492468670016480112957715214640939272457886646483560443432985954141177463448896521810457886108311082101521263110578485768091003174683555938678346359150123350656418123918738868598042533211541966786594006129134087145798672161268647536724
#a= 22184346235325197613876257964606959796734210361241668065837491428527234174610482874427139453643569493268653377061231169173874401139203757698022691973395609028489121048788465356158531144787135876251872262389742175830840373281181905217510352227396545981674450409488394636498629147806808635157820030290630290808150235068140864601098322473572121965126109735529553247807211711005936042322910065304489093415276688746634951081501428768318098925390576594162098506572668709475140964400043947851427774550253257759990959997691631511262768785787474750441024242552456956598974533625095249106992723798354594261566983135394923063605

考点：已知p高位，求低位 ；coopersmith

根据题目我们可以知道，是将p右移了340位，我们再次左移后得到的p就会缺失低位的340位，这时候我们就得用到small_roots函数（原理是coopersmith）来获取低位。

总的来说就是这个函数可以求一个解，那么我们构造$ f=p_{high}+x $（在模n情况下的解，给定$ \beta $就可以快速求出模某个b意义下较小的根，其中$ b\ge n^\beta $，是n的因数）

这样我们就可以知道p的低位，然后就可以知道p，之后就可以知道q，然后就RSA解密就行，但是题目没有直接给我们p的高位，而是a，a满足下面这个式子

$ a=p^3\mod n $

所以$ p^3=a+k*n $我们爆破一下k，判断是否可以开三次方，就可以求出p（求出来的p要再左移一下才是高位）

代码如下

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

n= 24479907029118467064460793139240403258697681144532146836881997837526487637306591893357774423547391867013441147680031968367449693796015901951120514250935018725570026327610524687128709707340727799633444550317834481416507364804274266363478822257132586592232042108076935945436358397787891169163821061005102693505011197453089873909085170776511350713452580692963748763166981047023704528272230392479728897831538235554137129584665886878574314566549330671483636900134584707867654841021494106881794644469229030140144595938886437242375435914268001721437309283611088568191856208951867342004280893021653793820874747638264412653721
c= 6566517934961780069851397787369134601399136324586682773286046135297104713708615112015588908759927424841719937322574766875308296258325687730658550956691921018605724308665345526807393669538103819281108643141723589363068859617542807984954436567078438099854340705208503317269397632214274507740533638883597409138972287275965697689862321166613821995226000320597560745749780942467497435742492468670016480112957715214640939272457886646483560443432985954141177463448896521810457886108311082101521263110578485768091003174683555938678346359150123350656418123918738868598042533211541966786594006129134087145798672161268647536724
a= 22184346235325197613876257964606959796734210361241668065837491428527234174610482874427139453643569493268653377061231169173874401139203757698022691973395609028489121048788465356158531144787135876251872262389742175830840373281181905217510352227396545981674450409488394636498629147806808635157820030290630290808150235068140864601098322473572121965126109735529553247807211711005936042322910065304489093415276688746634951081501428768318098925390576594162098506572668709475140964400043947851427774550253257759990959997691631511262768785787474750441024242552456956598974533625095249106992723798354594261566983135394923063605
for k in range(100):
    p = a+k*n
    if gmpy2.iroot(p,3)[1]:
        print(k)
        print(gmpy2.iroot(p,3)[0])
p=148500014720728755901835170447203030242113125689825190413979909224639701026120883281188694701625473553602289432755479244507504340127322979884849883842306663453018960250560834067472479033116264539127330613635903666209920113813160301513820286874124210921593865507657148933555053341577090100101684021531775022459
p=p<<340
print(p)
R.<x> = PolynomialRing(Zmod(n), implementation='NTL')

P = p + x
low_p = P.monic().small_roots(X = 2**340, beta = 0.4)[0]
print(p+low_p)
p=p+low_p
q=n//p
n = p * q
phin = (p - 1)*(q - 1)          # 欧拉函数
d = gmpy2.invert(e,phin)
m = pow(c,d,n)
print(long_to_bytes(m))

# LitCTF{Y0U_hAV3_g0T_Th3_r1ghT_AnsW3r}

2.easy_ya

题目

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

from flag import flag
def gen():
    e = 3
    while True:
        try:
            p = getPrime(512)
            q = getPrime(512)
            n = p*q
            phi = (p-1)*(q-1)
            d = inverse(e,phi)
            return p,q,d,n,e
        except:
            continue
    return
p,q,d,n,e = gen()
r = getPrime(512)
m = bytes_to_long(flag+os.urandom(32))
M = m%r
c = pow(m,e,n)
print("r = %d"%r)
print("M = %d"%M)
print("n = %d"%n)
print("e = %d"%e)
print("c = %d"%c)
'''
r = 7996728164495259362822258548434922741290100998149465194487628664864256950051236186227986990712837371289585870678059397413537714250530572338774305952904473
M = 4159518144549137412048572485195536187606187833861349516326031843059872501654790226936115271091120509781872925030241137272462161485445491493686121954785558
n = 131552964273731742744001439326470035414270864348139594004117959631286500198956302913377947920677525319260242121507196043323292374736595943942956194902814842206268870941485429339132421676367167621812260482624743821671183297023718573293452354284932348802548838847981916748951828826237112194142035380559020560287
e = 3
c = 46794664006708417132147941918719938365671485176293172014575392203162005813544444720181151046818648417346292288656741056411780813044749520725718927535262618317679844671500204720286218754536643881483749892207516758305694529993542296670281548111692443639662220578293714396224325591697834572209746048616144307282
'''

考点：coopersmith

一开始看到e很小，想到会不会是低密指数加密，用了那个脚本发现不行，爆不出来，说明得用别的方法，那只能关注M = m%r这个式子，我们可以得到$ m=M+k*r $

再根据rsa加密的式子，我们就可以得到下面这个多项式

$ c=m^e\mod n $

$ m^e-c=(M+k*r)^3-c=0\mod n $

所以$ f=(M+k*r)^3-c $，这样我们就可以根据small_roots()函数求k，唯一有点挑战的是k的上限我们不知道，得猜一下，实测2**80到2**255都可以求出k，这也说明了这个上界参数不是越大越好

具体代码如下

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

r = 7996728164495259362822258548434922741290100998149465194487628664864256950051236186227986990712837371289585870678059397413537714250530572338774305952904473
M = 4159518144549137412048572485195536187606187833861349516326031843059872501654790226936115271091120509781872925030241137272462161485445491493686121954785558
n = 131552964273731742744001439326470035414270864348139594004117959631286500198956302913377947920677525319260242121507196043323292374736595943942956194902814842206268870941485429339132421676367167621812260482624743821671183297023718573293452354284932348802548838847981916748951828826237112194142035380559020560287
e = 3
c = 46794664006708417132147941918719938365671485176293172014575392203162005813544444720181151046818648417346292288656741056411780813044749520725718927535262618317679844671500204720286218754536643881483749892207516758305694529993542296670281548111692443639662220578293714396224325591697834572209746048616144307282


R.<x> = PolynomialRing(Zmod(n), implementation='NTL')

f = (M + x*r)**3-c
k = f.monic().small_roots(X = 2**80, beta = 0.4)[0]
print(k)
k=810968823598060539864535

print(long_to_bytes(M+k*r))

# flag{53a2e494-964d-4506-a2c4-c34b9475dedd}

3.baby_xor

题目

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 *
from secret import flag

m = bytes_to_long(flag)
assert len(flag)==32
p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537
c1 = p^m
c2 = pow(m,e,n)
print(f'n = {n}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
"""
n = 139167681803392690594490403105432649693546256181767408269202101512534988406137879788255103631885736461742577594980136624933914700779445704490217419248411578290305101891222576080645870988658334799437317221565839991979543660824098367011942169305111105129234902517835649895908656770416774539906212596072334423407
c1 = 11201139662236758800406931253538295757259990870588609533820056210585752522925690049252488581929717556881067021381940083808024384402885422258545946243513996
c2 = 112016152270171196606652761990170033221036025260883289104273504703557624964071464062375228351458191745141525003775876044271210498526920529385038130932141551598616579917681815276713386113932345056134302042399379895915706991873687943357627747262597883603999621939794450743982662393955266685255577026078256473601
"""

考点：coopersmith

https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch19.pdf 很好的一本书，偶然发现

很明显，我们得从c1 = p^m这个式子入手，因为len(flag)==32，这就相当于256位，所以p的前256位是正常的，就是低位缺失了，用small_roots函数求低位，但是发现求不出来，后面查了一下才发现是知道应该是高位不够，得再爆破出一部分（看了文献才知道小根好像得小于$ \frac{1}{2\sqrt2}N^{\frac{1}{4}-\varepsilon} $）

网上查了代码，如下（导入的tqdm库就是给一个进度条，好看一点，真的爆了好久好久）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import gmpy2
from tqdm import *

n = 139167681803392690594490403105432649693546256181767408269202101512534988406137879788255103631885736461742577594980136624933914700779445704490217419248411578290305101891222576080645870988658334799437317221565839991979543660824098367011942169305111105129234902517835649895908656770416774539906212596072334423407
c1 = 11201139662236758800406931253538295757259990870588609533820056210585752522925690049252488581929717556881067021381940083808024384402885422258545946243513996
e=65537
pbits = 512
p_high = c1 >> 256
for i in trange(2**8):
     p4 = p_high<<8
     p4 = p4 + i
     kbits = pbits - p4.nbits()
     p4 = p4 << kbits
     PR.<x> = PolynomialRing(Zmod(n))
     f = x + p4
     roots = f.small_roots(X=2^kbits, beta=0.4, epsilon=0.01)
     if roots:
         p = p4 + int(roots[0])
         break
print(p)

# 11201139662236758800406931253538295757259990870588609533820056210585752522925662842097418194280333596411677923137891577493678147771013147838272857867768049

爆出来p就可以基本RSA解密了

1
2
3
4
5
6
7
8
9
10
11
12
13
n = 139167681803392690594490403105432649693546256181767408269202101512534988406137879788255103631885736461742577594980136624933914700779445704490217419248411578290305101891222576080645870988658334799437317221565839991979543660824098367011942169305111105129234902517835649895908656770416774539906212596072334423407
e=65537
p=11201139662236758800406931253538295757259990870588609533820056210585752522925662842097418194280333596411677923137891577493678147771013147838272857867768049
q=n//p
c = 112016152270171196606652761990170033221036025260883289104273504703557624964071464062375228351458191745141525003775876044271210498526920529385038130932141551598616579917681815276713386113932345056134302042399379895915706991873687943357627747262597883603999621939794450743982662393955266685255577026078256473601

phin = (p - 1)*(q - 1)          
d = gmpy2.invert(e,phin)       

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

# LitCTF{oh!!!!coppersmith_is_fun}