关于CTF-RSA题目类型解题思路

 鼎新安全

持续关注

RSA加密是一种非对称加密算法， 由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在1977年首次公开提出。RSA是它们三人姓氏的首字母组成的。

2.1、算法基础 - 数论知识

• 互质关系：如果两个正整数，除了 1 以外，没有其他公因数，那么这两个数是互质关系。例如，15 和 8 是互质的，因为 15 的因数是 1、3、5、15，8 的因数是 1、2、4、8，它们只有公因数 1。

• 欧拉函数：对于正整数n，欧拉函数表示小于等于n且与n互质的正整数的个数。例如，当时，与 6 互质的数有 1 和 5，所以。如果n是质数p，那么，因为所有小于p的正整数都与p互质。

• 模运算：模运算即求余数的运算。例如，，表示 7 除以 3 的余数是 1。在 RSA 算法中，模运算起到了关键作用，许多运算都是在模某个数的环境下进行的。

• 费马小定理和欧拉定理     * 费马小定理：假如p是质数，且a与p互质，那么。例如，当时，。     * 欧拉定理：若a与n互质，则。它是费马小定理的推广，当n为质数时，，就退化成费马小定理。

2.2、密钥生成过程

• 步骤一：选择两个大质数p和q

• • 这两个质数要足够大，例如可以选择p = 61，q = 53。大质数的选择是为了增加破解的难度，因为分解两个大质数的乘积是非常困难的计算问题。

• 步骤二：计算n = p × q和     * 对于前面所选的p = 61和q = 53，n = 61 × 53 = 3233，。

• 步骤三：选择一个整数e，使得且e与互质     * 通常选择一个较小的质数作为e，比如e = 17，因为17与3120互质，满足条件。这个e就是公钥的一部分。

• 步骤四：计算d，使得，即d是e在模下的乘法逆元     * 可以使用扩展欧几里得算法来计算d。对于e = 17和，通过计算得到d = 2753。这个就是私钥的一部分。

• 最终密钥：公钥是(e，n)，即(17，3233)；私钥是(d，n)，即(2753，3233)。

2.3、加密过程

• 假设要加密的消息是m（必须是小于n的整数），例如m = 123。使用公钥(e，n)进行加密，加密公式为

• 对于e = 17，n = 3233，m = 123，计算。通过计算得到c = 855，这就是加密后的密文。

2.4、解密过程

• 使用私钥(d，n)对密文c进行解密，解密公式为。

• 对于前面得到的c = 855，d = 2753，n = 3233，计算，经过计算可以得到m = 123，即还原出了原始消息。

刚才我们介绍了RSA算法的概述，现在我们来了解部分RSA题目的原理和解题思路。

题目基本上会直接给我们n和c还有e的值。

这时我们就需要分解n，得到p和q，从而进一步求出明文m。

关于分解n，我知道的就有三种方法一下逐个介绍。

如果说题目给的n的值很小的话，我们可以尝试写一个小脚本进行爆破。

但是要注意，爆破出来的值需要是素数，否则就是错误的值。

通过在线网站：https://factordb.com/，即可分解出p和q。

但是有时会分解不出来，这时就需要考虑其他的解题方法了。

使用cmd命令进入到yafu所在的目录下，或者将目录添加到环境变量中。

分解方法如下：

如果数比较小，可以直接使用

:::info .yafu-x64.exe “factor(**)”

:::

命令，（**）是要分解的数。

如果数比较大，可以将因数用文本文件存放在 yafu 目录下，例如：data.txt 。文件最后一行一定要换行，否则eof; done processing batchfile。

命令如下：

:::info .yafu-x64.exe “factor(@)” -batchfile data.txt

:::

题目如下：

from Crypto.Util.number import getPrime, bytes_to_longimport uuidflag = "flag{"+str(uuid.uuid4())[:13]+"}"p = getPrime(100)q = getPrime(100)n = p*qe = 0x10001m = bytes_to_long(flag.encode())assert(m < n)c = pow(m, e, n)# print(f"flag = {flag}")print(f"n = {n}")print(f"c = {c}")"""n = 625718246679843150194146350359795658237410693353450690028041c = 118795719073790634455854187484104547013000179946116068066473"""

这道题目将n，c，e的值直接给我们了，我们分解n获取素数p和q。

上面分解的那个值就是这题的n，这里就不多做演示了。

p = 768780063730500942699787302253q = 813910604866037851538498611597

有了p和q的值，那么就可以尝试解开明文m了。

p = 768780063730500942699787302253q = 813910604866037851538498611597c = 118795719073790634455854187484104547013000179946116068066473e = 0x10001import gmpy2  #gmpy2 是一个用于高效数学运算的库。from Crypto.Util.number import long_to_bytes  #inverse 用于计算模逆。  long_to_bytes 用于将长整型转换为字节串。n=(p*q)  # n 是 RSA 模数，等于两个质数 p 和 q 的乘积。phi_n=(q-1)*(p-1) #phi_n 是欧拉函数值，用于计算私钥。d=gmpy2.invert(e,phi_n)  #d 是 RSA 私钥，使用 inverse 函数计算 e 关于 phi_n 的模逆。m=pow(c,d,n)  #使用 RSA 解密公式 m = c^d mod n，计算出明文 m。print(long_to_bytes(m)) #将解密得到的长整型明文 m 转换为字节串并打印出来。

运行代码即可解出flag

在CTF-RSA中，e的值一般都是65537，但也有题目的e的值会很小，然后n的值很大，这种一般就是低加密指数攻击。

当n很大时分解n一般都是不会成功的，（但我们可以尝试一下，说不定就成功了）如果没有成功我们就可以换一种思路，例如当e很小时，比如e = 3 ，有c = m^e + kn ，我们可以尝试对k进行爆破，直到c - kn可以开根，一般能开出来就是明文m。

题目如下：

from Crypto.Util.number import *from flag import flagassert flag[0:7] == b'moectf{'assert flag[-1:] == b'}'flag = flag[7:-1]assert len(flag) == 32m1 = bytes_to_long(flag[0:16])m2 = bytes_to_long(flag[16:32])def enc1(m):    p = getPrime(512)    q = getPrime(512)    n = p * q    e = 3    c = pow(m,e,n)return n,e,cdef enc2(m):    p = getPrime(512)    q = getPrime(512)    e = 65537    d = inverse(e,(p-1)*(q-1))    n = p * q     dp2 = d % (p-1)    c = pow(m,e,n)return n,e,c,dp2n1,e1,c1 = enc1(m1)n2,e2,c2,dp2 = enc2(m2)print("n1="+ str(n1))print("e1="+ str(e1))print("c1="+ str(c1))print("n2="+ str(n2))print("e2="+ str(e2))print("c2="+ str(c2))print("dp2="+ str(dp2))'''n1=133024413746207623787624696996450696028790885302997888417950218110624599333002677651319135333439059708696691802077223829846594660086912881559705074934655646133379015018208216486164888406398123943796359972475427652972055533125099746441089220943904185289464863994194089394637271086436301059396682856176212902707e1=3c1=1402983421957507617092580232325850324755110618998641078304840725502785669308938910491971922889485661674385555242824n2=159054389158529397912052248500898471690131016887756654738868415880711791524038820158051782236121110394481656324333254185994103242391825337525378467922406901521793714621471618374673206963439266173586955520902823718942484039624752828390110673871132116507696336326760564857012559508160068814801483975094383392729e2=65537c2=37819867277367678387219893740454448327093874982803387661058084123080177731002392119369718466140559855145584144511271801362374042596420131167791821955469392938900319510220897100118141494412797730438963434604351102878410868789119825127662728307578251855605147607595591813395984880381435422467527232180612935306dp2=947639117873589776036311153850942192190143164329999603361788468962756751774397111913170053010412835033030478855001898886178148944512883446156861610917865'''

审题，发现flag被分为两个部分，被分别进行了加密，第一段就是低加密指数

低指数加密攻击：

import gmpy2import binasciin=gmpy2.mpz(133024413746207623787624696996450696028790885302997888417950218110624599333002677651319135333439059708696691802077223829846594660086912881559705074934655646133379015018208216486164888406398123943796359972475427652972055533125099746441089220943904185289464863994194089394637271086436301059396682856176212902707)e=3c=gmpy2.mpz(1402983421957507617092580232325850324755110618998641078304840725502785669308938910491971922889485661674385555242824)k=0while True:    res=gmpy2.iroot(k*n+c,e)if(res[1]==True):print(binascii.unhexlify(hex(res[0])[2:]))break    k+=1

这一道CTF题目的flag被分为了两个部分，第一部分就是低加密指数攻击，第二部分则是dp泄露，后面会讲。

简单介绍一下，这种攻击利用了在某些特定条件下，多个使用相同低加密指数加密的密文可以被组合起来破解原始明文的原理。

适用情况：

很多组不同的n和c，但是的是同一个e且很小。

攻击原理—基于中国剩余定理（CRT）

• 中国剩余定理内容：设是两两互质的正整数，对于同余方程组在模下有唯一解。

• 应用到广播攻击中：假设截获了k个密文，可以构建同余方程组

• 由于两两互质，根据中国剩余定理，可以求出这个同余方程组在模下的唯一解x。而这个x实际上就是

• 例如，当e = 3，如果求出了x，那么就可以通过计算来得到原始明文m。因为在这种情况下，利用同余方程组求出的使得我们能够避开直接求解 RSA 加密中的模数的分解难题，从而破解加密信息。

示例说明

• 假设存在三个模数，它们两两互质。加密指数e = 3。

• 有三个明文（假设），加密后得到密文：

• 攻击者截获了以及对应的模数

• 根据中国剩余定理求解同余方程组得到x = 216（这个计算过程可以通过中国剩余定理的算法来完成）。

• 因为e = 3，所以（在这个简单示例中恰好能得到整数解，实际情况可能更复杂，但原理相同），从而破解了原始明文。

题目如下：

N = 331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004 c = 310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243N = 302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114 c = 112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344N = 332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323 c = 10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242题目种给了我们3组n和c当n很大时我们就可以考虑e=3的低指数情况，把n和c放到数组里，像n=[n1,n2,n3]，c=[c1,c2,c3].然后最方便的是使用中国剩余定理，也就是crt(c,n)方法直接可以求出m的e次，然后开方得到m就行了。解题代码如下：import gmpy2import libnumfrom Crypto.Util.number import long_to_bytesfrom sympy.ntheory.modular import crtN1 = int('331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004',5)c1 = int('310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243',5)N2 = int('302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114',5)c2 = int('112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344',5)N3 = int('332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323',5)c3 = int('10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242',5)e = 3n = [N1,N2,N3]c = [c1,c2,c3]resultant, mod = crt(n, c)value, is_perfect = gmpy2.iroot(resultant, e)print(long_to_bytes(value))

有时候除了e,n,c之外题目还会给你像dp,dq这样的值，这是为了方便计算产生的，同时也给了我们另一种解题思路。

dp定义为dp = d mod (p-1)，其中d是 RSA 私钥，p是用于生成n = (p * q)（为另一个大质数）的大质数之一。

攻击原理：

• 当dp泄露时，攻击者可以利用以下原理对 RSA 加密进行攻击：

• 已知公钥（e,n）和dp，因为dp = d mod (p-1)，所以可以设d = k * (p - 1)，其中k为整数。

• 根据 RSA 中的关系，将d = k * (p - 1) + dp代入可得：     * e × (k × (p - 1) + dp) mod ((p - 1)× (q - 1)) = 1。     * 对这个等式进行展开和化简，通过一些数学推导（涉及到模运算的性质和等式变换），在已知e、dp和n = p * q的情况下，可以尝试求解出p和q，从而破解 RSA 加密。

示例说明：

• 假设n = 143(即p × q = 11× 13)，公钥e = 7，泄露的dp = 5。

• 设d = k × (p - 1) + dp，即d = k × 10 + 5。

• 根据，这里。

• 代入可得7 × (k × 10 + 5) mod 120 = 1。

• 通过计算（可以通过逐步尝试的值），当k = 7时，7 × (7 × 10 + 5) = 7 × 75 =525，525 mod 120 =45，不符合要求；当k = 8时，7 × (8 × 10 + 5) = 7 × 85 =595，595 mod 120 = 1，符合要求。

• 此时d = 8 × 10 + 5 =85。并且通过一些数学方法（如利用n = p × q和已求出的d等信息）可以进一步求出p = 11和q = 13，从而成功破解 RSA 加密。

题目如下：

from Crypto.Util.number import *from flag import flagassert flag[0:7] == b'moectf{'assert flag[-1:] == b'}'flag = flag[7:-1]assert len(flag) == 32m1 = bytes_to_long(flag[0:16])m2 = bytes_to_long(flag[16:32])def enc1(m):    p = getPrime(512)    q = getPrime(512)    n = p * q    e = 3    c = pow(m,e,n)return n,e,cdef enc2(m):    p = getPrime(512)    q = getPrime(512)    e = 65537    d = inverse(e,(p-1)*(q-1))    n = p * q     dp2 = d % (p-1)    c = pow(m,e,n)return n,e,c,dp2n1,e1,c1 = enc1(m1)n2,e2,c2,dp2 = enc2(m2)print("n1="+ str(n1))print("e1="+ str(e1))print("c1="+ str(c1))print("n2="+ str(n2))print("e2="+ str(e2))print("c2="+ str(c2))print("dp2="+ str(dp2))'''n1=133024413746207623787624696996450696028790885302997888417950218110624599333002677651319135333439059708696691802077223829846594660086912881559705074934655646133379015018208216486164888406398123943796359972475427652972055533125099746441089220943904185289464863994194089394637271086436301059396682856176212902707e1=3c1=1402983421957507617092580232325850324755110618998641078304840725502785669308938910491971922889485661674385555242824n2=159054389158529397912052248500898471690131016887756654738868415880711791524038820158051782236121110394481656324333254185994103242391825337525378467922406901521793714621471618374673206963439266173586955520902823718942484039624752828390110673871132116507696336326760564857012559508160068814801483975094383392729e2=65537c2=37819867277367678387219893740454448327093874982803387661058084123080177731002392119369718466140559855145584144511271801362374042596420131167791821955469392938900319510220897100118141494412797730438963434604351102878410868789119825127662728307578251855605147607595591813395984880381435422467527232180612935306dp2=947639117873589776036311153850942192190143164329999603361788468962756751774397111913170053010412835033030478855001898886178148944512883446156861610917865'''

第一段的低加密指数攻击我们刚才已经说过了，这里的代码主要是解后半段的dp泄露。

第二段dp泄露：

import gmpy2e = 65537n = 159054389158529397912052248500898471690131016887756654738868415880711791524038820158051782236121110394481656324333254185994103242391825337525378467922406901521793714621471618374673206963439266173586955520902823718942484039624752828390110673871132116507696336326760564857012559508160068814801483975094383392729c = 37819867277367678387219893740454448327093874982803387661058084123080177731002392119369718466140559855145584144511271801362374042596420131167791821955469392938900319510220897100118141494412797730438963434604351102878410868789119825127662728307578251855605147607595591813395984880381435422467527232180612935306dp = 947639117873589776036311153850942192190143164329999603361788468962756751774397111913170053010412835033030478855001898886178148944512883446156861610917865for x in range(1, e):if (e * dp % x == 1):        p = (e * dp - 1) // x + 1if (n % p != 0):continue        q = n // p        phin = (p - 1) * (q - 1)        d = gmpy2.invert(e, phin)        m = pow(c, d, n)if (len(hex(m)[2:]) % 2 == 1):continueprint("m:", m)# print(hex(m)[2:])print("flag:", bytes.fromhex(hex(m)[2:]))

刚才我们已经将dp泄露说过了，这里是dp，dq同时泄露，dq泄露的原理和dp是差不多的。

适用情况：dp,dq同时泄露

有的时候题目把dpdq都给我们了，这个时候我们不用知道e也可以解密。

此时有：

:::info <font style="color:rgb(77, 77, 77);"></font>m1 = c^dpmodp

m2 = c^dqmodq

m = (((m1-m2)I)%p)q+m2

其中I为对pq求逆元

:::

题目如下：

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

题目将p，q，dp，dq还要密文c全给我们了那么我们就可以用刚才提到的公式求解。

解题代码如下：

import gmpy2p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852I = gmpy2.invert(q,p)m1 = pow(c,dp,p)m2 = pow(c,dq,q)m = (((m1-m2)*I)%p)*q+m2print(m)                               #10进制明文print(hex(m)[2:])                      #16进制明文print(bytes.fromhex(hex(m)[2:]))       #16进制转文本

产生的原因

• 密钥生成环节：在 RSA 密钥生成过程中，选择e时应该确保它与（其中，p和q是两个大质数）互素。但如果这个条件没有满足，例如，在选择e时出现错误或者计算φ(n)有误，就会导致e和φ(n)不互素。

攻击可能性及原理

• 当e和φ(n)不互素时，假设（gcd表示最大公因数）。

• 设和，对于加密后的密文，可以写成。

• 根据数论中的一些性质，攻击者可能通过分析c与n之间的关系，结合g和φ1等信息（这些信息在某些情况下可能被推断出来），来获取关于m的部分信息，甚至完全破解加密。例如，如果g相对较小，攻击者可能通过穷举等方法来寻找m的可能值。

示例说明

• 假设n = 15（此时p = 3，q = 5，），如果错误地选择e = 4（此时e和φ(n)不互素，）。

• 对于明文m = 2，加密后。

• 对于另一个明文m = 7，加密后。

• 可以看到，不同的明文加密后得到了相同的密文，这就说明加密过程出现了问题，攻击者可以利用这种规律来获取明文信息。例如，通过收集足够多的明文 - 密文对，发现这种重复的密文情况，从而推断出可能的明文范围。

题目如下：

from Crypto.Util.number import *m=bytes_to_long(b'xxxxxx')p=getPrime(256)q=getPrime(256)e=74n=p*qc=pow(m,e,n)print("p=",p)print("q=",q)print("c=",c)#p= 86053582917386343422567174764040471033234388106968488834872953625339458483149#q= 72031998384560188060716696553519973198388628004850270102102972862328770104493#c= 3939634105073614197573473825268995321781553470182462454724181094897309933627076266632153551522332244941496491385911139566998817961371516587764621395810123

我首先使用传统RSA解密，结果报错了。排查了以下，发现是不互素，明白是什么就可以对症下药了。

解题代码：

from Crypto.Util.number import *from gmpy2 import *from gmpy2 import gcd, invert, iroot# 已知参数p = 86053582917386343422567174764040471033234388106968488834872953625339458483149q = 72031998384560188060716696553519973198388628004850270102102972862328770104493c = 3939634105073614197573473825268995321781553470182462454724181094897309933627076266632153551522332244941496491385911139566998817961371516587764621395810123e = 74# 计算n和欧拉函数φ(n)n = p * qphi = (p-1) * (q-1)# 检查e与p-1和q-1的最大公约数print(gcd(e, p-1))  # 检查e和p-1是否互素print(gcd(e, q-1))  # 检查e和q-1是否互素# 计算e与φ(n)的最大公约数t = gcd(e, phi)# 计算修正后的私钥dd = invert(e//t, phi)  # 使用e/t代替e来计算私钥# 解密得到m的t次方m2 = pow(c, d, n)# 开t次方根得到原始消息mm = iroot(m2, 2)[0]  # iroot返回一个元组(结果, 是否为精确值)# 将数字转换回字节并打印print(long_to_bytes(m))

攻击原理在 RSA 中的体现

• 加密公式特性利用：在 RSA 加密中，加密公式为当m（明文）的值较小时，的计算结果可能会落在一个相对较小的数值范围内，并且可能具有一些可被攻击者利用的规律。

• 穷举攻击可能性：例如，如果明文m是一个较小的整数（如小于 100），攻击者可以通过穷举m的可能值，计算，然后与截获的密文c进行比较。如果加密指数e和模数n是已知的（公钥信息），这种穷举在一定范围内是可行的。

• 数学关系挖掘：除了穷举，对于一些特殊的小数值明文，还可能存在数学关系帮助攻击者破解。比如，当m是一些特定的小质数或者 1 之类的特殊值时，根据数论知识和加密公式的特点，攻击者可能通过分析密文c与n、e之间的关系来推断明文m。

示例说明

• 假设 RSA 加密中，模数n = 101（这里只是为了方便示例，实际应用中会是很大的数），加密指数e = 3。

• 如果明文m = 2，那么密文。

• 攻击者知道公钥(e = 3，n = 101)，并且截获了密文c = 8。由于明文范围较小，攻击者可以尝试从m = 1开始穷举：     * 当时m = 1，，不符合。     * 当时m = 2，，找到了匹配的明文。

• 再比如，对于一些特殊数学关系的利用。假设，明文m = 1，则密文。攻击者截获密文后，根据数论知识，很容易猜测明文m可能是 1，因为对于任何数a，。

查看附件

只有flag的密文和n，我们小明文攻击爆破。构造代码：

from gmpy2 import irootimport sympyimport binasciiflag = 25166751653530941364839663846806543387720865339263370907985655775152187319464715737116599171477207047430065345882626259880756839094179627032623895330242655333n = 134109481482703713214838023035418052567000870587160796935708584694132507394211363652420160931185332280406437290210512090663977634730864032370977407179731940068634536079284528020739988665713200815021342700369922518406968356455736393738946128013973643235228327971170711979683931964854563904980669850660628561419def small_m_atk(c, n):    e = 2while e < 2 ** 10:        i = 0while i < 10:            res = iroot(c + i * n, e)if res[1]:print("破解成功！", e, i, res)return res[0]print(e, i, res)            i += 1        e = sympy.nextprime(e)print("flag:", binascii.unhexlify(hex(small_m_atk(flag, n))[2:]))

攻击原理

• 假设存在两个用户，其公钥分别为和，对应的私钥分别为和。对于相同的明文m（m<n），加密后的密文分别为和。

• 攻击者如果截获了和，并且知道和n，就可以利用扩展欧几里得算法找到整数x和y，使得（gcd表示最大公因数）。

• 在（通常情况下是这种情况）的条件下，通过计算可以得到明文m。例如，如果x是正数，那么（这里表示在模n下的乘法逆元）。

示例说明

• 假设模数n = 33，第一个用户的公钥，第二个用户的公钥，明文m = 7。

• 第一个用户加密后的密文。

• 第二个用户加密后的密文。

• 攻击者截获了和，以及和 n= 33。

• 首先使用扩展欧几里得算法找到x和y，使得3x + 5y = 1，解得x = 2，y = -1。

• 然后计算明文，先求，即。

• 最后计算，成功获取了原始明文。

题目如下：

from secret import efrom Crypto.Util.number import getStrongPrime, isPrimep = getStrongPrime(1024)q = getStrongPrime(1024)N = p * qphi = (p - 1) * (q - 1)with open('flag.txt', 'rb') as f:    flag = int.from_bytes(f.read(), 'big')assert(isPrime(e))assert(isPrime(e + 2))assert(isPrime(e + 4))e1 = pow(e, 0x10001, phi)e2 = pow(e + 2, 0x10001, phi)e3 = pow(e + 4, 0x10001, phi)c1 = pow(flag, e1, N)c2 = pow(flag, e2, N)c3 = pow(flag, e3, N)print(f'p = {p}')print(f'q = {q}')print(f'c1 = {c1}')print(f'c2 = {c2}')print(f'c3 = {c3}')p = 167710954518007348037383082265231465648795974011761905177264545864288011527333715495850532989338171489309608848431113452814709692343039027970312735521415071265608660628968391884287240987858607818275329135585153511665148279408708087727501421558738163577629329044315775019460018956186674179846621352371150072281q = 130354329753344570838569091064852072757046774566775609047544069941246798511317343102715733555464772099991834579660053860799207243561908291522943696711982657846373844514551117658179060004064010647453939332217996817580433587341521331941287365948919907797478197717562721233289937471168288241937022054501586986443c1 = 2560344169447809042170685026483682125499025654554670516499742981486615082413150123244985585751880264831112089324011804397189638172356179296987581738515619297036118472798499254785110885662931526277474101787493114656242031264678448394380651657330967744585361662315313462698221954777506355498445242300193032704972074020068699180111637362566860530694807230108024167631423062629721393506643291591971626450262144814424411172618188943774725105690851574922374544865628890948773274109561622040022136970632948166009941425683576381155722191980954262373394704682297682490061906408535261437100820855976015526295573831744458528440c2 = 9041231631916227099296501948589424780380702196870972231114747229225732542137483840187783630590878594711315671224997985975031038623195921968945234067183003568830416719957054703139219879265482072634572699299971785171441858501409377942183918216246312330291820452436486171483461790388518159980027140392750222843449604265528929311978655519463562520038992870162220913137870017065557254099767583925177889051326144499369420594398043223307161794788085369471538477803421726790780799629276012701406231535048423554314287152404245482928538931953627397633165453319078105028671410039195670727134471011040601278722143504641171853743c3 = 3193069356811106774640161554961405075257002069448498144279061282023129342916422283816661697787316681475161942522570615456264481238277711114193792510286127129056376618422336477707825009085263623755329815306483253646072909132096678270667136193038337386976289222105363398033633185639402128949635525665502328717781718263894690234837016959581149138917064108193064639981137359869717065147934752707676203651598070046066514316196771853484143158367616177332902152347890310640338106015356361617700741042461419248117687350565094928451141103632305400493998164788411031832078388030194992306440474662871408938796429927990102583837

看到题目给出的c1，c2，c3就明白这是共模攻击了，但是没有e的值，根据这几个断言语句猜测，e的值为3。

解题代码如下：

from xenny.ctf.crypto.modern.asymmetric.rsa import same_moduleimport hashlibfrom Crypto.Util.number import *p = 167710954518007348037383082265231465648795974011761905177264545864288011527333715495850532989338171489309608848431113452814709692343039027970312735521415071265608660628968391884287240987858607818275329135585153511665148279408708087727501421558738163577629329044315775019460018956186674179846621352371150072281q = 130354329753344570838569091064852072757046774566775609047544069941246798511317343102715733555464772099991834579660053860799207243561908291522943696711982657846373844514551117658179060004064010647453939332217996817580433587341521331941287365948919907797478197717562721233289937471168288241937022054501586986443c1 = 2560344169447809042170685026483682125499025654554670516499742981486615082413150123244985585751880264831112089324011804397189638172356179296987581738515619297036118472798499254785110885662931526277474101787493114656242031264678448394380651657330967744585361662315313462698221954777506355498445242300193032704972074020068699180111637362566860530694807230108024167631423062629721393506643291591971626450262144814424411172618188943774725105690851574922374544865628890948773274109561622040022136970632948166009941425683576381155722191980954262373394704682297682490061906408535261437100820855976015526295573831744458528440c2 = 9041231631916227099296501948589424780380702196870972231114747229225732542137483840187783630590878594711315671224997985975031038623195921968945234067183003568830416719957054703139219879265482072634572699299971785171441858501409377942183918216246312330291820452436486171483461790388518159980027140392750222843449604265528929311978655519463562520038992870162220913137870017065557254099767583925177889051326144499369420594398043223307161794788085369471538477803421726790780799629276012701406231535048423554314287152404245482928538931953627397633165453319078105028671410039195670727134471011040601278722143504641171853743c3 = 3193069356811106774640161554961405075257002069448498144279061282023129342916422283816661697787316681475161942522570615456264481238277711114193792510286127129056376618422336477707825009085263623755329815306483253646072909132096678270667136193038337386976289222105363398033633185639402128949635525665502328717781718263894690234837016959581149138917064108193064639981137359869717065147934752707676203651598070046066514316196771853484143158367616177332902152347890310640338106015356361617700741042461419248117687350565094928451141103632305400493998164788411031832078388030194992306440474662871408938796429927990102583837phi = (p-1)*(q-1)e1 = pow(3,65537,phi)e2 = pow(5,65537,phi)e3 = pow(7,65537,phi)m = same_module.attack(p*q,e2,e3,c2,c3)print(long_to_bytes(m))print(hashlib.md5(str('You are intuitively understanding the distribution of prime numbers! Bonus: You can solve this challenge w/ N instead of p and q!').encode('utf-8')).hexdigest())

攻击原理

• 假设存在两个 RSA 密钥对，第一个密钥对的模数，第二个密钥对的模数。如果攻击者知道和并且发现它们共享一个素数p，可以通过计算最大公因数来找到这个共享素数p。

• 例如，使用欧几里得算法来计算，一旦找到共享素数p，就可以通过（对于第一个密钥对）和（对于第二个密钥对）来获取和。

• 知道了p和（或），就可以计算出对应的（或）。再结合已知的公钥指数（或），通过求解（或）来找到私钥指数（或），从而破解这两个密钥对的加密信息。

示例说明

• 假设第一个 RSA 密钥对的模数（其中p = 17，），第二个 RSA 密钥对的模数（其中p = 17，）。

• 攻击者计算，使用欧几里得算法：     *      * 所以，找到了共享素数 p =17。

• 对于，计算；对于，计算。

• 然后可以计算，。

• 假设第一个密钥对的公钥指数，通过求解，可以找到私钥指数（计算过程略）。同样可以对第二个密钥对进行类似操作，从而破解这两个密钥对的加密。

题目如下：

from flag import flagfrom Crypto.Util.number import *m = bytes_to_long(flag)e = 65537f = open("output.txt", "r")a = f.readlines()for i in a:    n = int(i)    c = pow(m, e, n)    m = cprint'c = %s' % (m)f.close()'''c = 38127524839835864306737280818907796566475979451567460500065967565655632622992572530918601432256137666695102199970580936307755091109351218835095309766358063857260088937006810056236871014903809290530667071255731805071115169201705265663551734892827553733293929057918850738362888383312352624299108382366714432727'''654390779683975409890654893374159407845292694296846493650653786513534830303048434390039496495433763118718456188191073506464372529801449784479249764709439300758128342373684253745782159776412658848598754407993348076074787059321751486731603535778758900741013930425067140016173382652849103818492592987726421906198684323542682354501742201439891678090906205345679025639230497354851748913298466767963738641694840993079616237784452582996831758574995605714993052354746323014737619282075380286836222513783022596795382647577904745455595827184603552631903638912758735201714941754918785078289292469151139853617809003195836548349957839320383142814687522363258949714784622321678585619281948174372461045134361003939684803510572969567182690634502610963365500727981041136988638273942465134797850643121827808482673619534240872593224537996099454035648829692386918230535360101064254854063175494150147494342652670585674593236663514793256521719547526681688981293613564203331776790199463078530754639610680717906531590902269046258850802361742316651785384055478287680437065154649226110512213947046785589223398864802476631387024813490980772915849920824144942754636703305346136078529992916455003911115970098681889746712491182130400574291131743776100949569932697987584804463119416035191810573880422944674873620697603324343637301069525994561310483764571204869551420449413700501577063742151039276076337163948013385192044925250652542383743481169363821045885199050278565573804234811538596460408087218012154314706318094553271359371272652700290905481848558423799321513963024373100501797447180147684637554796375398455002202770022931512541062214916136294604754404667725341796896161398464327153718845280194035978972665664657052946003418121755545770123205426883869361411412259838522099085901563107814985172942977520233320215882707710717870398128412272218474014381169303848087621856187879891495465553977594303430989366901389825443675616619140514991123455352381088006655315883768065464993744576343971616701405200600649633918262201777984427073816407232480340613139745222334158157956565702209029744848651767285356606277123748353299676087282167497345297614315923458165928758073188763471514213936717636644910745066117244286803215386367509823585568921869527941443518292351035601295715594154848316087327104045236864492670381270786477990071505115267370508200276144584756149529545546004190247328273125926887037592121558915728862275748887953944149839627625758912030299124230037836410124644809495563445977936168664379694880331320743031437708811856697413105291652061062223857313580221562305807771003185061831752133665835648647560103986928466217390444724672894866216636981793418219455653595717274553950715056120806463449033181486699963584346517910081706586345546292894426402568226579894766693070066214488743160957135286739213705210017884761571455431756742090831943258533881163856244402320366797089178570957480705975750689554231652966654296486945413532497873374642720952604107176597260128068368847994769957589023616787379681936743686883539354241863892071236377342305502668107665859031340043228489853207907881697778409245956454637871895180143011817145696624607185256115618314013654196062366108005667366446678566958509292648219469125446143086630226296062401591537192778880966138731809796820936490762559956233972270004144434211689926680201834015563595961467759770875801202498158314352125915263948000322892415197120869504325154875840721818789566387310111118839703578797261862424304499548882114635944516216618095145194843718635007052242072452831460162126955481326379219639313067967998826898344673513019946299427614605216960081461930080199023399060417820769438661351988322185620598552697590115678078498754112860310272842870106790357443602405008865116282919

题目中给出了多个n，初步猜测是共享素数，尝试分解验证一下。

猜测正确，是共享素数。

明白是什么，那就可以对症下药了。

from Crypto.Util.number import *p = 7552850543392291177573335134779451826968284497191536051874894984844023350777357739533061306212635723884437778881981836095720474943879388731913801454095897a = list(map(int, open('E:/桌面/output.txt').read().splitlines()))c = 38127524839835864306737280818907796566475979451567460500065967565655632622992572530918601432256137666695102199970580936307755091109351218835095309766358063857260088937006810056236871014903809290530667071255731805071115169201705265663551734892827553733293929057918850738362888383312352624299108382366714432727e = 65537for i in a[::-1]:    n = int(i)    q = n // p    d = inverse(e, (p-1)*(q-1))    m = pow(c, d, n)    c = mprint(long_to_bytes(m))

攻击原理

• 在 RSA 中，公钥为（e，n），私钥为（d，n），其中n = p * q（p和q是两个大素数），并且满足。

• 维纳攻击利用了连分数的性质。如果d相对于n较小（具体来说，如果），那么可以通过计算公钥指数e与n的连分数展开式来恢复私钥d。

• 连分数展开可以将一个实数表示为一个整数序列的形式。对于有理数，其连分数展开是有限的。在维纳攻击的情况下，通过对进行连分数展开，并检查展开后的收敛子，可以找到可能的私钥d值。

举例说明

• 假设n = 119（这里n是一个较小的值用于示例，实际的 RSA 中n是非常大的），e = 13。

• 首先计算的连分数展开。

• 其连分数展开为[0;3,1,1,2]，对应的收敛子依次为等。

• 通过检查这些收敛子，找到满足 RSA 密钥关系的值d。在实际应用中，会根据一定的条件来判断哪个收敛子可能对应正确的私钥d。

例题：

题目如下：

n = 12238605063252292170613110607692779326628090745751955692266649177882959231822580682548279800443278979485092243645806337103841086023159482786712759291169541633901936290854044069486201989034158882661270017305064348254800318759062921744741432214818915527537124001063995865927527037625277330117588414586505635959411443039463168463608235165929831344586283875119363703480280602514451713723663297066810128769907278246434745483846869482536367912810637275405943566734099622063142293421936734750356828712268385319217225803602442033960930413469179550331907541244416573641309943913383658451409219852933526106735587605884499707827e =  11850552481503020257392808424743510851763548184936536180317707155841959788151862976445957810691568475609821000653594584717037528429828330763571556164988619635320288125983463358648887090031957900011546300841211712664477474767941406651977784177969001025954167441377912326806132232375497798238928464025466905201977180541053129691501120197010080001677260814313906843670652972019631997467352264392296894192998971542816081534808106792758008676039929763345402657578681818891775091140555977382868531202964486261123748663752490909455324860302967636149379567988941803701512680099398021640317868259975961261408500449965277690517c = 4218884541887711839568615416673923480889604461874475071333225389075770098726337046768413570546617180777109293884545400260353306419150066928226964662256930702466709992997796154415790565112167663547017839870351167884417142819504498662037048412313768450136617389372395690363188005647619061128497371121168347810294424378348301835826084732747005110258557662466626720961279087145559906371505117097599774430970980355531235913439823966628008554872896820907555353892843539526041019103819804854883231421963308265517622470779089941078841902464033685762524196275032288319744157255628189204988632871276637699312750636348750883054

请解出明文！！！

e很大，不是一般的大，一般来说e很大那就维纳攻击。

解题代码如下：

import gmpy2import libnumdef continuedFra(x, y):    cf = []while y:        cf.append(x // y)        x, y = y, x % yreturn cfdef gradualFra(cf):    numerator = 0    denominator = 1for x in cf[::-1]:        numerator, denominator = denominator, x * denominator + numeratorreturn numerator, denominatordef solve_pq(a, b, c):    par = gmpy2.isqrt(b * b - 4 * a * c)return (-b + par) // (2 * a), (-b - par) // (2 * a)def getGradualFra(cf):    gf = []for i in range(1, len(cf) + 1):        gf.append(gradualFra(cf[:i]))return gfdef wienerAttack(e, n):    cf = continuedFra(e, n)    gf = getGradualFra(cf)for d, k in gf:if k == 0: continueif (e * d - 1) % k != 0:continue        phi = (e * d - 1) // k        p, q = solve_pq(1, n - phi + 1, n)if p * q == n:return dn = 12238605063252292170613110607692779326628090745751955692266649177882959231822580682548279800443278979485092243645806337103841086023159482786712759291169541633901936290854044069486201989034158882661270017305064348254800318759062921744741432214818915527537124001063995865927527037625277330117588414586505635959411443039463168463608235165929831344586283875119363703480280602514451713723663297066810128769907278246434745483846869482536367912810637275405943566734099622063142293421936734750356828712268385319217225803602442033960930413469179550331907541244416573641309943913383658451409219852933526106735587605884499707827e =  11850552481503020257392808424743510851763548184936536180317707155841959788151862976445957810691568475609821000653594584717037528429828330763571556164988619635320288125983463358648887090031957900011546300841211712664477474767941406651977784177969001025954167441377912326806132232375497798238928464025466905201977180541053129691501120197010080001677260814313906843670652972019631997467352264392296894192998971542816081534808106792758008676039929763345402657578681818891775091140555977382868531202964486261123748663752490909455324860302967636149379567988941803701512680099398021640317868259975961261408500449965277690517c = 4218884541887711839568615416673923480889604461874475071333225389075770098726337046768413570546617180777109293884545400260353306419150066928226964662256930702466709992997796154415790565112167663547017839870351167884417142819504498662037048412313768450136617389372395690363188005647619061128497371121168347810294424378348301835826084732747005110258557662466626720961279087145559906371505117097599774430970980355531235913439823966628008554872896820907555353892843539526041019103819804854883231421963308265517622470779089941078841902464033685762524196275032288319744157255628189204988632871276637699312750636348750883054d = wienerAttack(e, n)m=pow(c, d, n)print(libnum.n2s(m).decode())