Crypto趣题-RSA(二)

该文章是记录一些RSA相关的趣题的第二篇

RSA Fault

题目来源：广东省大学生攻防大赛 2022

题目：

from Crypto.Util.number import *
from secrets import randbelow
import os

p=getPrime(2048)
q=getPrime(2048)
n=p*q

def fault_signature(m,dp,p):
    bits = list(range(dp.bit_length()))
    # Random Errors
    for i in range(2):
        dp ^= 1 << bits.pop(randbelow(len(bits)))
    return pow(m,dp,p)

def fast_sign(p,q,m,d):
    Sp=fault_signature(m,d%(p-1),p)
    Sq=fault_signature(m,d%(q-1),q)
    q_inv_p=inverse(q,p)
    return Sq+((Sp-Sq)*q_inv_p%p)*q

flag=open("./flag.txt","rb").read()
flag=flag+os.urandom(512-len(flag))
m=bytes_to_long(flag)
e=65537
d=inverse(e,(p-1)*(q-1))
c=pow(m,e,n)
m_=fast_sign(p,q,c,d)

print(f"n={n}")
print(f"c={c}")
print(f"e={e}")
print(f"m_={m_}")
if m_!=m:
    print("It seems that something is wrong with RSA")

# n=574370586922196377355321224190746373039960224108385243176501127428241048239267855106791452531127716395867009150959315133488286007016233693579335880694651355103104937242790643593308890788070770218317565926178413379641001140239463599845984585594216005669250735996427555432706918692021991171275999765908594644925310142503285857206438695393554469523893825536665449736024054747514990216868678037268511584416901858031484008394871632441625217801474466940448366132590034239161293582715621533020233700914500451000518789317508997706548731775994224900635411275356861073588492237057246039324320408280417962081059669609944892848853780428862986621290797973749713412083663630592820568996851852624888672199864050563167321198235872086549523724070759241183192416218511190119068501395848056263721692763920519420483450363920749842894919641617223824549955451175853298676915196907992214900910995739550922989640910170960485331090144764984190331659966983894284549074935918333832010695306946738396909292095557434605170122130253447970074530010535669698871315126545879037607033278200101983233974781109773521793185318497615158089955239305362817170200396186939592803861438759399366317967907276433739944705398688186125687434884160720331949648831768235019520753051
# c=362746477666691362768020792694001662947338474716913368693174463002520197020564066827257658031973928782798475691408938544507860754837561076547768524746177804704585961840013195670850383664598530250844247051357401431355747035161872296498272254812117528152035029837329888665483050219346048506686826529658339084796751613191344103470399897412327265769031997892130002446603232458409236206943209821169103651387451247194645094911282908657256087747570185214886614187576679719039472798093505360214315789098466937327166004179112376884521755838649234980317596136131856395020357496102439866802500120832803908679095031213229175799928906606183829594039803465175754892790016569054202014492252632598390521485126555541028488750683218149923230255353856768460065582373942152212466578732981079533510158716511814895961705462125751613632997737277288382147402327477915047046907933387151859100428914053565582939275934201969543786806286829008145312080251388532179582069076383305307261868697565579486745927759554919760999971562169014832448067746716988944857402974596263631030324458073601261131647030891982010744785938573077302132228457909917393551651580730603193283673617373961392738841147569262489888662190518624689563339261875140574320207133638608459439737908
# e=65537
# m_=181132170825291068274428850998643597061484670852441092778734815200952945165798640567559048182854905384108012241001865806757291292964878403693878633267090257939702439086938795033128278779133834594418004509584542651057754389391530368493133213945631248904554493258521520798694334742694993906802448945319763766711250429667767598356479263059390167552213786607866923685142648716071350485727194734337940552363833868066952302121733855882534848604214379852034329599650298994536987432597047148545264456233041626319601655687038246563924371156826280023920057214856878486989521822479101902273314188727929753114744387793613654594486456078456745565816416446216301510436912147365878585967444947975888852483708054850555285865986707367641310078228756765470506112047816213856326341605584860221570211438661212837691148838965467195299751453604986777239749470579607668379117939736929002608940866262332919423512927188694030664492052057406513313547841154542784730283602499247284074861014689921502985853652524070575242018309321538365113665998744193304726118797289396908257027371761721071940141406755037691084908985405935268861122559095563199460082893754126987724947094729974089127671509635467188911500940561377499209529543406027692937688249517323189766222196
# It seems that something is wrong with RSA

题目基于RSA的CRT解密故障，正常流程下，RSA的CRT解密流程是：

• 计算mp = c^dp % p
• 计算mq = c^dq % q
• CRT组合得到模n下的明文m

而在这一题目中也是按照这个流程进行解密的，只是解密时出现了一点故障，如下：

def fault_signature(m,dp,p):
    bits = list(range(dp.bit_length()))
    # Random Errors
    for i in range(2):
        dp ^= 1 << bits.pop(randbelow(len(bits)))
    return pow(m,dp,p)

也就是说，在计算mp、mq时，dp、dq都发生了两比特的随机翻转，这会导致什么后果呢？我们以dp做例子看一看错误结果与正确结果的关系是什么，假设发生故障后，dp的第i比特位由1变成0，第j比特位由0变成1，则有：

$$dp' = dp - 2^i + 2^j$$

那么计算明文时，原本正确的mp应该是：

$$m_p = c^{dp} \quad(mod\;p)$$

而发生了故障后变为：

$$m_p' = c^{dp'} = c^{dp - 2^i + 2^j} \quad(mod\;p)$$

也就是：

$$m_p' = m_pc^{- 2^i + 2^j} \quad(mod\;p)$$

这就是正确值和错误值的关系所在，那么怎么利用呢？我们观察他的CRT组合过程：

def fast_sign(p,q,m,d):
    Sp=fault_signature(m,d%(p-1),p)
    Sq=fault_signature(m,d%(q-1),q)
    q_inv_p=inverse(q,p)
    return Sq+((Sp-Sq)*q_inv_p%p)*q

这样计算CRT，在m正确时与我们熟知的那个公式是没有区别的，但是发生了故障时，就可以为我们所用。我们注意到它返回的结果其实可以写成如下形式：

$$m' = m_q' + kq$$

然后转到模q下分析，就可以去除后面的kq项，此时式子变为：

$$m' \equiv mc^{- 2^i + 2^j} \quad(mod\;q)$$

两边的指数部分同时乘e，就有：

$$m'^e \equiv m^ec^{e(-2^i + 2^j)} \quad(mod\;q)$$

又因为：

$$c \equiv m^e \quad(mod\;q)$$

所以：

$$m'^e \equiv cc^{e(-2^i + 2^j)} \quad(mod\;q)$$

那么我们计算下式：

$$m'^e - cc^{e(-2^i + 2^j)} \quad(mod\;n)$$

然后与n求解gcd就可以得到q了，有了n的分解后就可以求解flag。

但是还有一个麻烦的点，首先，我们需要爆破i、j分别的取值，这就有2048x2048=2^22种可能性；其次，我们还需要爆破他们对应的比特是0变1还是1变0，这就又要乘上4；这就有2^24的复杂度。并且每一层最内的的基础操作是模幂运算，即使用最快的powmod来算，由于n是个4096位的大数字，快速幂也要计算4096次，这就导致爆破的复杂度有点不可接受。

而这一部分我的处理方式就是碰运气，毕竟故障发生的比特位只有两个，我假设他们都落在0-512这个区间，就可以显著降低复杂度，当然成功的概率也就降低到了十六分之一，但是事实就是他们确实落在了这个区间内，所以就能出。

exp：

from Crypto.Util.number import *
from tqdm import *
from gmpy2 import powmod

n=574370586922196377355321224190746373039960224108385243176501127428241048239267855106791452531127716395867009150959315133488286007016233693579335880694651355103104937242790643593308890788070770218317565926178413379641001140239463599845984585594216005669250735996427555432706918692021991171275999765908594644925310142503285857206438695393554469523893825536665449736024054747514990216868678037268511584416901858031484008394871632441625217801474466940448366132590034239161293582715621533020233700914500451000518789317508997706548731775994224900635411275356861073588492237057246039324320408280417962081059669609944892848853780428862986621290797973749713412083663630592820568996851852624888672199864050563167321198235872086549523724070759241183192416218511190119068501395848056263721692763920519420483450363920749842894919641617223824549955451175853298676915196907992214900910995739550922989640910170960485331090144764984190331659966983894284549074935918333832010695306946738396909292095557434605170122130253447970074530010535669698871315126545879037607033278200101983233974781109773521793185318497615158089955239305362817170200396186939592803861438759399366317967907276433739944705398688186125687434884160720331949648831768235019520753051
c=362746477666691362768020792694001662947338474716913368693174463002520197020564066827257658031973928782798475691408938544507860754837561076547768524746177804704585961840013195670850383664598530250844247051357401431355747035161872296498272254812117528152035029837329888665483050219346048506686826529658339084796751613191344103470399897412327265769031997892130002446603232458409236206943209821169103651387451247194645094911282908657256087747570185214886614187576679719039472798093505360214315789098466937327166004179112376884521755838649234980317596136131856395020357496102439866802500120832803908679095031213229175799928906606183829594039803465175754892790016569054202014492252632598390521485126555541028488750683218149923230255353856768460065582373942152212466578732981079533510158716511814895961705462125751613632997737277288382147402327477915047046907933387151859100428914053565582939275934201969543786806286829008145312080251388532179582069076383305307261868697565579486745927759554919760999971562169014832448067746716988944857402974596263631030324458073601261131647030891982010744785938573077302132228457909917393551651580730603193283673617373961392738841147569262489888662190518624689563339261875140574320207133638608459439737908
e=65537
m_=181132170825291068274428850998643597061484670852441092778734815200952945165798640567559048182854905384108012241001865806757291292964878403693878633267090257939702439086938795033128278779133834594418004509584542651057754389391530368493133213945631248904554493258521520798694334742694993906802448945319763766711250429667767598356479263059390167552213786607866923685142648716071350485727194734337940552363833868066952302121733855882534848604214379852034329599650298994536987432597047148545264456233041626319601655687038246563924371156826280023920057214856878486989521822479101902273314188727929753114744387793613654594486456078456745565816416446216301510436912147365878585967444947975888852483708054850555285865986707367641310078228756765470506112047816213856326341605584860221570211438661212837691148838965467195299751453604986777239749470579607668379117939736929002608940866262332919423512927188694030664492052057406513313547841154542784730283602499247284074861014689921502985853652524070575242018309321538365113665998744193304726118797289396908257027371761721071940141406755037691084908985405935268861122559095563199460082893754126987724947094729974089127671509635467188911500940561377499209529543406027692937688249517323189766222196


if(0):
    temp = pow(m_,e,n)*inverse(c,n) % n
    is_positive = [(1,1),(1,-1),(-1,1),(-1,-1)]
    for i in trange(1,2**9):
        for j in range(1,2**9):
            for k in is_positive:
                pow1 = k[0] * (1 << i)
                pow2 = k[1] * (1 << j)

                powpow = e*(pow1+pow2)
                temp1 = powmod(c,powpow,n)
                if(GCD(temp-temp1,n) != 1):
                    print(GCD(temp-temp1,n))
                    exit()

p = 22729650064982784569842293886112765216527000770423090114368848726216608009470242046289112001066994207864986803275467348289746127450153723652496430471357120041795298501429299577023455880461653074271752126909063527106805373676824002441432786073264913608717964699805549233067291369590239167126966358735428766668880762276154481715084785307608648063807156963867353713246912838175911702373808989338864178007028831198106910117378309595596445705841624769259901086135441435201197082487810720560245568126972348046187117147996691190165006379956721543713979012391623875001928207563847027939516349080119621035628223197354404395029
q = n // p
phi = (p-1)*(q-1)
d = inverse(e,phi)
print(long_to_bytes(pow(c,d,n)))

#flag{r$a_fault_w1th_C5T_m3thod_01a7da73}

Easy RSA 2

题目来源：ISITDTU-CTF 2019

题目：

from Crypto.Util.number import *
import gmpy2

flag = '##################################'
p1 = getPrime(512)
p2 = gmpy2.next_prime(p1)
q1 = getPrime(512)
q2 = gmpy2.next_prime(q1)
n = p1*p2*q1*q2
e = 65537
phi = (p1-1)*(p2-1)*(q1-1)*(q2-1)
d = gmpy2.invert(e,phi)
c = pow(bytes_to_long(flag),e,n)

print pow(p1+q2,65537,n)
#5043622010330564722783560796388733110223192234657313797979729183216316602247790170027393145104828283812158304519218370476380897023249898720267053051908498011845198383126598688185743313040451851234309071530873683667360872515868401870834371902623509762498919172464493397284930232415029297203698778851121422456149280629701148108649396642433199634388011535777204188207597427548981195309015900421249473588077922607729093939587454170211363784480831197764238579460361668878037335596700513382133341370374840639374005225742007557272153800433699784092511039693877686425832957477808359462507401596842526527374816943302475357302
print pow(p2+q1,65537,n)
#7919283184559406259028604751155413696993375814336862337694645459367829841130544291770103966362177145582007048754925168845793555136985754996486596987205043932984314934297789456823769422776642272151478021108135062833657996366160688598742804847633068533451034898357435150319123770512604358033881809960916484049603490477616900480883862825416570459592254659007024761917196293369565486538943942938968226701375668351560376904094935919442322484791587819687743780031411339960372463937311578960714219580981945254129150844798674023932645363519148439092971133029751088847668041720574694350298717079140377388740434213791727288722
print n 
#8573641536164485111081609341110540574423426701587222458588002464807917555910942077276167528046769327390058096169685188870928286845342631974847171845103806710768418462668311621275704636581042137915505959767806384415314024549489538717607173007829067492516776714817262226691787436227002924225311861164296655909746846329870548266285498682510415418053656271623482202491805513797215793596385014264449282551352796096361524482384994633912515104414237252657058698433260597636367614328512751722615849959987780969423318207123668118325176544879335267439096589035064596631756303300860315257404427016819145298919974287174103934503
print c 
#8436043641135865531308468859210199431445831063674810351906331674115825605849862045115409554309732867926457428348729196827592921108183774070414343257409618631078896543782150761081732376735501920417229787663210936174854000594130785353102718054331606096192133481536724402629697019651921188121029927710787682993814748802295545306899075962041017278877203965796981792702098381465051289581518257202127401748725944229037078896857591660248467597356051123218945757343652461844056927461929195427880969904210166880623689090977714615839624798930450630919330253477634839161931755642681718034910946900928731231093352169252474939674

题目的n由四个素数组成：

$$n = p_1q_1p_2q_2$$

由于有nextprime函数参与，四个素因子还满足以下关系：

$$p_2 = p_1 + k$$ $$q_2 = q_1 + s$$

其中，k和s是nextprime带来的较小偏移量，此外题目还提供给我们两个信息：

$$hint_1 = (p_1+q_2)^e \quad(mod\;n)$$ $$hint_2 = (p_2+q_1)^e \quad(mod\;n)$$

要求我们利用这些信息，获得n的完整分解，从而求解RSA明文。

首先，利用n的因子相差较小的特点，可以将其分解为以下两组：

$$n = (p_1q_1)(p_2q_2)$$ $$n = (p_1q_2)(p_2q_1)$$

而第二组的因子相差肯定比第一组更近，因此费马分解得到的第一组分解是p1q2和p2q1。

但事实上改变返回条件，就可以继续求解下一组因子，也就是p1q1和p2q2，然后求GCD就能得到完整因子分解了。exp如下：

from Crypto.Util.number import *
from gmpy2 import *

factorlist = []

def fermat(num):
    global factorlist
    x = iroot(num, 2)[0]
    if x * x < num:
        x += 1

    while (True):
        y2 = x * x - num
        y = iroot(y2, 2)[0]
        if y * y == y2:
            factorlist.append((int(x + y), int(x - y)))
            if(len(factorlist) == 2):
               return
        x += 1

hint1 = 5043622010330564722783560796388733110223192234657313797979729183216316602247790170027393145104828283812158304519218370476380897023249898720267053051908498011845198383126598688185743313040451851234309071530873683667360872515868401870834371902623509762498919172464493397284930232415029297203698778851121422456149280629701148108649396642433199634388011535777204188207597427548981195309015900421249473588077922607729093939587454170211363784480831197764238579460361668878037335596700513382133341370374840639374005225742007557272153800433699784092511039693877686425832957477808359462507401596842526527374816943302475357302
hint2 = 7919283184559406259028604751155413696993375814336862337694645459367829841130544291770103966362177145582007048754925168845793555136985754996486596987205043932984314934297789456823769422776642272151478021108135062833657996366160688598742804847633068533451034898357435150319123770512604358033881809960916484049603490477616900480883862825416570459592254659007024761917196293369565486538943942938968226701375668351560376904094935919442322484791587819687743780031411339960372463937311578960714219580981945254129150844798674023932645363519148439092971133029751088847668041720574694350298717079140377388740434213791727288722
n = 8573641536164485111081609341110540574423426701587222458588002464807917555910942077276167528046769327390058096169685188870928286845342631974847171845103806710768418462668311621275704636581042137915505959767806384415314024549489538717607173007829067492516776714817262226691787436227002924225311861164296655909746846329870548266285498682510415418053656271623482202491805513797215793596385014264449282551352796096361524482384994633912515104414237252657058698433260597636367614328512751722615849959987780969423318207123668118325176544879335267439096589035064596631756303300860315257404427016819145298919974287174103934503
c = 8436043641135865531308468859210199431445831063674810351906331674115825605849862045115409554309732867926457428348729196827592921108183774070414343257409618631078896543782150761081732376735501920417229787663210936174854000594130785353102718054331606096192133481536724402629697019651921188121029927710787682993814748802295545306899075962041017278877203965796981792702098381465051289581518257202127401748725944229037078896857591660248467597356051123218945757343652461844056927461929195427880969904210166880623689090977714615839624798930450630919330253477634839161931755642681718034910946900928731231093352169252474939674
e = 65537

fermat(n)
p1 = GCD(factorlist[0][0],factorlist[1][0])
q2 = factorlist[0][0] // p1
q1 = factorlist[1][0] // p1
p2 = factorlist[0][1] // q1
phi = (p1-1)*(p2-1)*(q1-1)*(q2-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

#ISITDTU{C0ngratu1ati0ns_Attack_RSA_Multi_prim3!!!!}

但是这样好像根本没有用上hint，而只要用费马分解的话，hint就没什么用。因此我想了想不用费马分解，而利用hint的办法。

首先hint可以写成：

$$hint_1 = (p_1+q_1 + s)^e \quad(mod\;n)$$ $$hint_2 = (p_1+q_1 + k)^e \quad(mod\;n)$$

把p1+q1看作一个整体m，就有：

$$hint_1 = (m + s)^e \quad(mod\;n)$$ $$hint_2 = (m + k)^e \quad(mod\;n)$$

s和k是小量，因此理论上可以爆破s和k，用相关消息攻击求解出p1+q1的值，同时也就求出了s和k，因此获得n的全部分解。但是事实上多项式的次数过大，即使用HGCD求解一次GCD也需要一两分钟，因此时间复杂度过高了，所以用费马分解就是最合理的解法。