easy_factor系列

本文记录 NSS 靶场 tangcuxiaojkuai 的 easy_factor 系列题解/学习笔记。该系列主要围绕 费马小定理 展开，核心收获是：当已知 φ(n)，或者已知形如 k·φ(n) 的信息时，可以利用这些条件对 n 进行分解，从而还原 RSA 的关键参数。

这个假期整体状态不算太好——毕竟过年嘛，比赛也比较少，刷题节奏自然就慢了些。靶场里一些相对简单的密码题我基本都做得差不多了（/(ㄒoㄒ)/~~），接下来打算把重心放到更进阶的方向：二元 Coppersmith、广义 RSA，以及 LWE 相关问题上。

[tangcuxiaojkuai]easy_factor1

from Crypto.Util.number import *
from Crypto.Util.Padding import *
from Crypto.Cipher import AES
from hashlib import sha256
from random import *
from secret import flag
​
p,q,r = getPrime(256),getPrime(256),getPrime(256)
n = p*q*r
phi = (p-1)*(q-1)*(r-1)
​
key = sha256(str(p+q+r).encode()).digest()
enc = AES.new(key, AES.MODE_ECB)
c = enc.encrypt(pad(flag,16))
​
print("n =",n)
print("hint =",getrandbits(256)*phi**3)
print("c =",c)
​
'''
n = 343127312894441264623060100705188723106648253383902349620699412384677995734576572885137280031507308915752070128528949423639735964709160841591038148069185325450544546735392923674211031016035209702254447128968565740534765322198664691
hint = 3802744632475774666777934738986183209966233570124815804333822490240409933768208822899072601181527365734196352249978937639454658680559993507805820991037544059215540360338084909833242583087617315128513337647913472696515770688338805196215328080662137260951972365100322795737835152857750114216709340410268143017180826135339564387228460663261697814425298725805568817218360964967025967384766127098203664964210047103829182895016532403825215903779806760754721373523135367007867453212189953817229696304611549977864533229540971457717668560698088917340909962348110683581294453903261530189579223087858081200349343639420534779115290433982968345085704202494045885911950427043282588446343291558819683037970053828479057449781943479407877748772895179095205885377333120540311815022381056
c = b';#\x1b\xa6R\xe2\x1d\x9dpf\x8e\xda\xe4\x14\x9a\xfb\tr\x99\x8a\xc9r\x03C\xb58Zb\x97\x0b\xc7S\x0fa\x88\xb4\xe4\x16.M\x92\x94\x94\x8b\xa9Ki\x9b\xe4\xe9d5\xa3~\x1a\x9cx\x03\xdc\x1f\x87\x14E\x90'
'''

本题用到了费马小定理（做题的时候还是经常用到的，但是经常"差一点"），是一种已知phi进行分解n的思路

费马小定理：

其实我们可以扩展一下，得到下面的两个式子

回归题目

我们尝试先将hint分解

hint=k*(fai^3)

那么这里面的三次大概率就是fai的

而fai=(p-1)(q-1)(r-1)

那么例如7，如果是fai分解得到的因子，必定是其中一个p-1分解得到的

那么当我们fai//(7^3)之后，相当于破坏了fai(p)，即fai !=k*fai(p)

我们得到式子

但由于fai = k*fai (qr)

那么我们此时a^(hint//r)(mod qr)-1和n进行gcd得到的是qr

逐个这样我们就可以分解到所有的素数

学会了这个就学会利用fai进行分解n了

其实走到这里可以感觉到和p-1光滑的思路是一样的收集fai(p)的因子，得到k*fai(p)就可以gcd出来p

解码代码

from gmpy2 import gmpy2
from Crypto.Util.number import *
from Crypto.Util.Padding import *
from Crypto.Cipher import AES
from hashlib import sha256
from random import *
n = 343127312894441264623060100705188723106648253383902349620699412384677995734576572885137280031507308915752070128528949423639735964709160841591038148069185325450544546735392923674211031016035209702254447128968565740534765322198664691
hint = 3802744632475774666777934738986183209966233570124815804333822490240409933768208822899072601181527365734196352249978937639454658680559993507805820991037544059215540360338084909833242583087617315128513337647913472696515770688338805196215328080662137260951972365100322795737835152857750114216709340410268143017180826135339564387228460663261697814425298725805568817218360964967025967384766127098203664964210047103829182895016532403825215903779806760754721373523135367007867453212189953817229696304611549977864533229540971457717668560698088917340909962348110683581294453903261530189579223087858081200349343639420534779115290433982968345085704202494045885911950427043282588446343291558819683037970053828479057449781943479407877748772895179095205885377333120540311815022381056
c = b';#\x1b\xa6R\xe2\x1d\x9dpf\x8e\xda\xe4\x14\x9a\xfb\tr\x99\x8a\xc9r\x03C\xb58Zb\x97\x0b\xc7S\x0fa\x88\xb4\xe4\x16.M\x92\x94\x94\x8b\xa9Ki\x9b\xe4\xe9d5\xa3~\x1a\x9cx\x03\xdc\x1f\x87\x14E\x90'
​
 # 2^11 · 3^6 · 7^3 · 13^6 · 41^3 · 79^3 · 83^3 · 277^3 · 248701^3 
​
list_=[2,4,8,3,9,7,13,13^2,41,79,83,277,248701]
primes=[]
for i in list_:
    # print(gcd(n,pow(2,hint//i,n)-1))
    # print(i)
    if gcd(n,pow(2,hint//(i**3),n)-1)==n:
        continue
    else:
        prime=n//gcd(n,pow(2,hint//(i**3),n)-1)
        if gmpy2.is_prime(prime) and len(bin(prime))-2==256:
            primes.append(prime)
            # print(prime)
primes = list(set(primes))
# print(primes)
p,q,r=primes
key = sha256(str(p+q+r).encode()).digest()
enc = AES.new(key, AES.MODE_ECB)
flag = enc.decrypt(c)
print(flag)

[tangcuxiaojkuai]easy_factor2

还不是很熟悉，之后会补齐

[tangcuxiaojkuai]easy_factor3

题目代码

from Crypto.Util.number import *
from secret import flag
​
def gen_noisy_sum_of_base(m,p):
    sum = 0
    while(m):
        sum += m % p
        m //= p
    return sum//1000
​
flag = bytes_to_long(flag)
e = 65537
p = getPrime(256)
q = getPrime(256)
n = p*q
​
m1 = getRandomNBitInteger(2048)
m2 = getRandomNBitInteger(2048)
print("m1 =",m1)
print("m2 =",m2)
print("sum1 =",gen_noisy_sum_of_base(m1,p))
print("sum2 =",gen_noisy_sum_of_base(m2,p))
print("n =",n)
print("c =",pow(flag,e,n))
​
'''
m1 = 23145761572719481962762273155673006162798724771853359777738044204075205506442533110957905454673168677138390288946164925146182350082798412822843805544411533748092944111577005586562560198883223125408349637392132331590745338744632420471550117436081738053152425051777196723492578868061454261995047266710226954140246577840642938899700421187651113304598644654895965391847939886431779910020514811403672972939220544348355199254228516702386597854501038639792622830084538278039854948584633614251281566284373340450838609257716124253976669362880920166668588411500606044047589369585384869618488029661584962261850614005626269748136
m2 = 21293043264185301689671141081477381397341096454508291834869907694578437286574195450398858995081655892976217341587431170279280993193619462282509529429783481444479483042173879669051228851679105028954444823160427758701176787431760859579559910604299900563680491964215291720468360933456681005593307187729279478018539532102837247060040450789168837047742882484655150731188613373706854145363872001885815654186972492841075619196485090216542847074922791386068648687399184582403554320117303153178588095463812872354300214532980928150374681897550358290689615020883772588218387143725124660254095748926982159934321361143271090861833
sum1 = 309575642078438773208947649750793560438038690144069550000470706236111082406
sum2 = 303394719183577651416751448350927044928060280972644968966068528268042222965
n = 4597063839057338886607228486569583368669829061896475991448013970518668754752831268343529061846220181652766402988715484221563478749446497476462877699249731
c = 3253873276452081483545152055347615580632252871708666807881332670645532929747667442194685757039215506084199053032613562932819745309368748317106660561209205
'''

简单测试函数gen_noisy_sum_of_base(m,p)

其功能就是将m转换成p进制下的数字，对其系数求和，然后除以1000，那么我们爆破1000以内就可以了

我们将sum1乘以1000并进行爆破，得到

此时m1减去sum1可以得到

其实m1-sum1是整除p-1的

第一项a_0*(p^0-1)显然是0

对应后面的项

我这几天看EZ_Fermat的题目时候看到这个性质了

m1-sum1=k*fai(p)

那么，根据费马小定理

本题不需要m2和hint2即可分解

from Crypto.Util.number import *
m1 = 23145761572719481962762273155673006162798724771853359777738044204075205506442533110957905454673168677138390288946164925146182350082798412822843805544411533748092944111577005586562560198883223125408349637392132331590745338744632420471550117436081738053152425051777196723492578868061454261995047266710226954140246577840642938899700421187651113304598644654895965391847939886431779910020514811403672972939220544348355199254228516702386597854501038639792622830084538278039854948584633614251281566284373340450838609257716124253976669362880920166668588411500606044047589369585384869618488029661584962261850614005626269748136
m2 = 21293043264185301689671141081477381397341096454508291834869907694578437286574195450398858995081655892976217341587431170279280993193619462282509529429783481444479483042173879669051228851679105028954444823160427758701176787431760859579559910604299900563680491964215291720468360933456681005593307187729279478018539532102837247060040450789168837047742882484655150731188613373706854145363872001885815654186972492841075619196485090216542847074922791386068648687399184582403554320117303153178588095463812872354300214532980928150374681897550358290689615020883772588218387143725124660254095748926982159934321361143271090861833
sum1 = 309575642078438773208947649750793560438038690144069550000470706236111082406
sum2 = 303394719183577651416751448350927044928060280972644968966068528268042222965
n = 4597063839057338886607228486569583368669829061896475991448013970518668754752831268343529061846220181652766402988715484221563478749446497476462877699249731
c = 3253873276452081483545152055347615580632252871708666807881332670645532929747667442194685757039215506084199053032613562932819745309368748317106660561209205
e=65537
sum1=sum1*1000
for i in range(1000):
    fai1=m1-(sum1+i)
    a=pow(2,fai1,n)
    # print(gcd(a-1,n))
    if gcd(a-1,n)==1:
        continue
    else:
        p=gcd(a-1,n)
        q=n//p
        d=pow(e,-1,(p-1)*(q-1))
        m=pow(c,d,n)
        print(long_to_bytes(int(m)))

[tangcuxiaojkuai]easy_factor4

题目代码

from Crypto.Util.number import *
from Crypto.Util.Padding import *
from Crypto.Cipher import AES
from hashlib import sha256
from random import *
from secret import flag
​
p = getPrime(256)
q = getPrime(256)
n = p*q
phi = (p-1)*(q-1)
e = 65537
d = inverse(e,phi)
​
key = sha256(str(p+q).encode()).digest()
enc = AES.new(key, AES.MODE_ECB)
c = enc.encrypt(pad(flag,16))
hint = getPrime(20)*d**3 + getPrime(128)*phi**2
​
print("n =",n)
print("c =",c)
print("hint =",hint)
​
​
'''
n = 8218998145909849489767589224752145194323996231101223014114062788439896662892324765430227087699807011312680357974547103427747626031176593986204926098978521
c = b'\x9a \x8f\x96y-\xb4\tM\x1f\xe6\xcc\xef\xd5\x19\xf26`|B\x10N\xd7\xd0u\xafH\x8d&\xe3\xdbG\x13\x8e\xea\xc0N\n\r\x91\xdc\x95\x9b\xb1Ny\xc1\xc4'
hint = 1860336365742538749239400340012599905091601221664081527583387276567734082070898348249407548568429668674672914754714801138206452116493106389151588267356258514501364109988967005351164279942136862087633991319071449095868845225164481135177941404709110974226338184970874613912364483762845606151111467768789248446875083250614540611690257121725792701375153027230580334095192816413366949340923355547691884448377941160689781707403607778943438589193122334667641037672649189861
'''

我们主要观察hint这个式子

hint = getPrime(20)*d**3 + getPrime(128)*phi**2

又是熟悉的费马小定理的形式了，a是20位，完全可以爆破，然后思路和easy_factor1一样了

解码代码

from Crypto.Util.number import *
from Crypto.Util.Padding import *
from Crypto.Cipher import AES
from hashlib import sha256
from gmpy2 import *
from tqdm import *
n = 8218998145909849489767589224752145194323996231101223014114062788439896662892324765430227087699807011312680357974547103427747626031176593986204926098978521
c = b'\x9a \x8f\x96y-\xb4\tM\x1f\xe6\xcc\xef\xd5\x19\xf26`|B\x10N\xd7\xd0u\xafH\x8d&\xe3\xdbG\x13\x8e\xea\xc0N\n\r\x91\xdc\x95\x9b\xb1Ny\xc1\xc4'
hint = 1860336365742538749239400340012599905091601221664081527583387276567734082070898348249407548568429668674672914754714801138206452116493106389151588267356258514501364109988967005351164279942136862087633991319071449095868845225164481135177941404709110974226338184970874613912364483762845606151111467768789248446875083250614540611690257121725792701375153027230580334095192816413366949340923355547691884448377941160689781707403607778943438589193122334667641037672649189861
e = 65537
hint=hint*(e**3)
for a in tqdm(range(2**20)):
    if not gmpy2.is_prime(a):
        continue
    if pow(2,hint-a,n)==1:
        hint=hint-a
        print('found a=',i)
        break
print(hint)
list_=[2,4,8,16,3,3^2,3^3,3^4,11,31,73,101,137,179,397,1871,6113,74713,1050887,106031326409,1081244969177,7836595938569,9491217938233]
for i in list_:
    k_fai=hint//i
    if GCD(pow(2,k_fai,n)-1,n)==1 or GCD(pow(2,k_fai,n)-1,n)==n:
        continue
    else:
        print(GCD(pow(2,k_fai,n)-1,n))
        p=GCD(pow(2,k_fai,n)-1,n)
        q=n//p
        print(gmpy2.is_prime(p),gmpy2.is_prime(q))
        key = sha256(str(p+q).encode()).digest()
        enc = AES.new(key, AES.MODE_ECB)
        flag = enc.decrypt(c)
        print(flag)
        break