(13)已知e,n,dp,c求m
题目内容如下:
e=65537
n=9637571466652899741848142654451413405801976834328667418509217149503238513830870985353918314633160277580591819016181785300521866901536670666234046521697590230079161867282389124998093526637796571100147052430445089605759722456767679930869250538932528092292071024877213105462554819256136145385237821098127348787416199401770954567019811050508888349297579329222552491826770225583983899834347983888473219771888063393354348613119521862989609112706536794212028369088219375364362615622092005578099889045473175051574207130932430162265994221914833343534531743589037146933738549770365029230545884239551015472122598634133661853901
dp=81339405704902517676022188908547543689627829453799865550091494842725439570571310071337729038516525539158092247771184675844795891671744082925462138427070614848951224652874430072917346702280925974595608822751382808802457160317381440319175601623719969138918927272712366710634393379149593082774688540571485214097
c=5971372776574706905158546698157178098706187597204981662036310534369575915776950962893790809274833462545672702278129839887482283641996814437707885716134279091994238891294614019371247451378504745748882207694219990495603397913371579808848136183106703158532870472345648247817132700604598385677497138485776569096958910782582696229046024695529762572289705021673895852985396416704278321332667281973074372362761992335826576550161390158761314769544548809326036026461123102509831887999493584436939086255411387879202594399181211724444617225689922628790388129032022982596393215038044861544602046137258904612792518629229736324827解题脚本:
#!/usr/bin/python
#coding:utf-8
import gmpy2
import libnum
from Crypto.Util.number import long_to_bytes
e= 65537
n = 9637571466652899741848142654451413405801976834328667418509217149503238513830870985353918314633160277580591819016181785300521866901536670666234046521697590230079161867282389124998093526637796571100147052430445089605759722456767679930869250538932528092292071024877213105462554819256136145385237821098127348787416199401770954567019811050508888349297579329222552491826770225583983899834347983888473219771888063393354348613119521862989609112706536794212028369088219375364362615622092005578099889045473175051574207130932430162265994221914833343534531743589037146933738549770365029230545884239551015472122598634133661853901
c = 5971372776574706905158546698157178098706187597204981662036310534369575915776950962893790809274833462545672702278129839887482283641996814437707885716134279091994238891294614019371247451378504745748882207694219990495603397913371579808848136183106703158532870472345648247817132700604598385677497138485776569096958910782582696229046024695529762572289705021673895852985396416704278321332667281973074372362761992335826576550161390158761314769544548809326036026461123102509831887999493584436939086255411387879202594399181211724444617225689922628790388129032022982596393215038044861544602046137258904612792518629229736324827
dp = 81339405704902517676022188908547543689627829453799865550091494842725439570571310071337729038516525539158092247771184675844795891671744082925462138427070614848951224652874430072917346702280925974595608822751382808802457160317381440319175601623719969138918927272712366710634393379149593082774688540571485214097
for i in range(1,65538):
if (dp*e-1)%i == 0:
if n%(((dp*e-1)/i)+1)==0:
p=((dp*e-1)/i)+1
q=n/(((dp*e-1)/i)+1)
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)%phi
m = pow(c,d,n)
print long_to_bytes(m)(14)N分解出多个不同的因子
适用情况：题目给出的模数N可直接分解，但是分解之后得到了多个不同的因子
题目: 15-山东省大学生爱好者线上赛-上午RSA
题目给出一个文件里面的内容如下：
n= 544187306850902797629107353619267427694837163600853983242783
e= 39293
c= 439254895818320413408827022398053685867343267971712332011972
m=???
很明显n不大，可直接使用factordb进行分解。
E:\MISC\RSA\yafu-1.34>yafu-x64.exe "factor(544187306850902797629107353619267427694837163600853983242783)"
fac: factoring 544187306850902797629107353619267427694837163600853983242783
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 3, starting 1000 iterations on C60
rho: x^2 + 2, starting 1000 iterations on C60
rho: x^2 + 1, starting 1000 iterations on C60
pm1: starting B1 = 150K, B2 = gmp-ecm default on C60
ecm: 30/30 curves on C60, B1=2K, B2=gmp-ecm default
ecm: 10/49 curves on C60, B1=11K, B2=gmp-ecm default
starting SIQS on c43: 8035348176477081799669008169226677154776273
==== sieving in progress (1 thread): 960 relations needed ====
==== Press ctrl-c to abort and save state ====
892 rels found: 450 full + 442 from 3656 partial, (21619.29 rels/sec)
SIQS elapsed time = 0.2329 seconds.
Total factoring time = 0.6579 seconds
***factors found***
P17 = 67724172605733871
P20 = 11571390939636959887
P24 = 694415063702720454699679
ans = 1
E:\MISC\RSA\yafu-1.34>分解得到了3个因子，其实当时做这题时我也是一脸懵的，从没遇到过，试了n种方法，最后推到了这个方法。
解题脚本如下:
#!/usr/bin/python
#coding:utf-8
import gmpy2
from Crypto.Util.number import long_to_bytes
n= 544187306850902797629107353619267427694837163600853983242783
e= 39293
c= 439254895818320413408827022398053685867343267971712332011972
p1 = 67724172605733871
p2 = 11571390939636959887
p3 = 694415063702720454699679
phi = (p1-1)*(p2-1)*(p3-1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
print long_to_bytes(m)(15)LSB Oracle Attack
适用情况：可以通过选择输入的密文进而泄露最低位解题。
该攻击方式详细请参考该文章：
RSA Least-Significant-Bit Oracle Attack
introspelliam.github.io/2018/03/27/crypto/RSA-Least-Significant-Bit-Oracle-Attack/
题目: 14-SUCTF-RSA
正式进入rsa解题之前会让你提供一个字符串str，只有md5(str+给定的值salt) == 给定的部分哈希值part_hash，才能进入正式的题目。
然后，通过输入D,服务端会帮你解给出的给出的密文，但只会返回这个数是奇数(odd)还是偶数(even)，通过G选项可以测试你输入的m是否正确，如果正确就会进入下1轮的
解题(3轮都是相同的原理，只是给出数c,n不同)(必须使用交互式解题)
解题脚本:
LSB Oracle Attack
github.com/Mr-Aur0ra/RSA/blob/master/(15)LSB%20Oracle%20Attack/exp.py
本题摘自Nu1L战队提供的wp,膜，膜，膜
(16)PKCS1_OAEP模式的RSA
西湖论剑2020--BrokenSystems。
题目给出三个文件，一个加密脚本BrokenSystems.py，一个密文文件message，一个RSA公钥文件public.key。
通过openssl查看，可以看到该公钥文件的e特别大，此时便存在rsa-wiener-attack攻击，通过此可以求出d。
通过rsa-wiener-attack求解d：
from Crypto.PublicKey import RSA
import ContinuedFractions, Arithmetic
def wiener_hack(e, n):
# firstly git clone https://github.com/pablocelayes/rsa-wiener-attack.git !
frac = ContinuedFractions.rational_to_contfrac(e, n)
convergents = ContinuedFractions.convergents_from_contfrac(frac)
for (k, d) in convergents:
if k != 0 and (e * d - 1) % k == 0:
phi = (e * d - 1) // k
s = n - phi + 1
discr = s * s - 4 * n
if (discr >= 0):
t = Arithmetic.is_perfect_square(discr)
if t != -1 and (s + t) % 2 == 0:
print("First: Hacked d.")
return d
return False
n = 0xC20745223FF5B94B2CD8412166F7288A21F2187E1A421453918CAB03C80253451233EB1BDC2363744228AA8694A8C2CBC833F80DDF40831A68901B230B83F3F0FED4B72D0B942B5E95DEDAC8DCC0047A2AFB90C81ED72D3AD49B72FC8BD0D3167DDDAA6AB5167C058DF36AF190B216085BBD9D621F9BD23A093E4E3D9CC387B6274F2C339C88E1B2D908ACB33F4E20E647ABEE0714A3CCE4646E896294B78103DCC9A4DB7ED681164C6E6CC7FD33476E174A6C707037B250491365F9F0EB76AEABA07DB2F662D88048AF98C88C76C6710DB9658D49FCA0CAF1F5CD99DC07F188432B48F85571168AD10FC824B7B682BAD6CAA5D12FF6F04C92786B738AB19BB7
e = 0x1d2d2f1f173f81cf368fec06d40d47fd92f8615c12eec14168f288427952b8cf5a538f70ba3341b6a173ae80375a96b0d384d9722b19149f78947375e0a33df5e693edabd5e4d44cffa9e525ea014f3fa499b5f7b29b219d90b88da55aae3a08637338d7bed056e3aec575be56bbde534b355a2e7757db7aeca96e78d67f21530b7c3ec24ac61f9b474ab283220dd9545135d065a724ce2f8f44e32e460eef5f9958009c58af595193d77e72c25f0cb01505b993c135328b11b500dcabc955c9177f839dd043586e25a31335e7d5437dc9e6cd6d4ebecb2937e16026c2792e1745f44eed5411beaab55ed0905db9198cbd431111be87462f46369e31d1a4613f
message = open('./message', 'r')
secret = message.read()
d = wiener_hack(e, n)
此时，我们便可以求出d。已知d，我们便可以求出p和q。
def getpq(n,e,d):
p = 1
q = 1
while p==1 and q==1:
k = d * e - 1
g = random.randint ( 0 , n )
while p==1 and q==1 and k % 2 == 0:
k /= 2
y = pow(g,k,n)
if y!=1 and gcd(y-1,n)>1:
p = gcd(y-1,n)
q = n/p
return p,q
因为加密脚本采用了PKCS1_OAEP模式下的RSA加密，所以我们需要通过手动构造私钥进而才可以去解密密文。采用原始的pow(c,d,n)是无法正确的解密密文的。
因此，我们需要先采用PKCS1_OAEP模式构造私钥，然后利用这个私钥来解密密文文件。
privkey = RSA.construct((long(n), long(e), long(d), long(p), long(q)))
key = PKCS1_OAEP.new(privkey)
m = key.decrypt(secret)
print m
完整的exp如下：
#rsa-wiener-attack/exp1.py
#!/usr/bin/python
#coding:utf-8
import gmpy2
import random
from Crypto.PublicKey import RSA
import ContinuedFractions, Arithmetic
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Util.number import long_to_bytes
def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
temp = a % b
a = b
b = temp
return a
def getpq(n,e,d):
p = 1
q = 1
while p==1 and q==1:
k = d * e - 1
g = random.randint ( 0 , n )
while p==1 and q==1 and k % 2 == 0:
k /= 2
y = pow(g,k,n)
if y!=1 and gcd(y-1,n)>1:
p = gcd(y-1,n)
q = n/p
return p,q
def wiener_hack(e, n):
# firstly git clone https://github.com/pablocelayes/rsa-wiener-attack.git !
frac = ContinuedFractions.rational_to_contfrac(e, n)
convergents = ContinuedFractions.convergents_from_contfrac(frac)
for (k, d) in convergents:
if k != 0 and (e * d - 1) % k == 0:
phi = (e * d - 1) // k
s = n - phi + 1
discr = s * s - 4 * n
if (discr >= 0):
t = Arithmetic.is_perfect_square(discr)
if t != -1 and (s + t) % 2 == 0:
print("First: Hacked d.")
return d
return False
def main():
n = 0xC20745223FF5B94B2CD8412166F7288A21F2187E1A421453918CAB03C80253451233EB1BDC2363744228AA8694A8C2CBC833F80DDF40831A68901B230B83F3F0FED4B72D0B942B5E95DEDAC8DCC0047A2AFB90C81ED72D3AD49B72FC8BD0D3167DDDAA6AB5167C058DF36AF190B216085BBD9D621F9BD23A093E4E3D9CC387B6274F2C339C88E1B2D908ACB33F4E20E647ABEE0714A3CCE4646E896294B78103DCC9A4DB7ED681164C6E6CC7FD33476E174A6C707037B250491365F9F0EB76AEABA07DB2F662D88048AF98C88C76C6710DB9658D49FCA0CAF1F5CD99DC07F188432B48F85571168AD10FC824B7B682BAD6CAA5D12FF6F04C92786B738AB19BB7
e = 0x1d2d2f1f173f81cf368fec06d40d47fd92f8615c12eec14168f288427952b8cf5a538f70ba3341b6a173ae80375a96b0d384d9722b19149f78947375e0a33df5e693edabd5e4d44cffa9e525ea014f3fa499b5f7b29b219d90b88da55aae3a08637338d7bed056e3aec575be56bbde534b355a2e7757db7aeca96e78d67f21530b7c3ec24ac61f9b474ab283220dd9545135d065a724ce2f8f44e32e460eef5f9958009c58af595193d77e72c25f0cb01505b993c135328b11b500dcabc955c9177f839dd043586e25a31335e7d5437dc9e6cd6d4ebecb2937e16026c2792e1745f44eed5411beaab55ed0905db9198cbd431111be87462f46369e31d1a4613f
message = open('./message', 'r')
secret = message.read()
d = wiener_hack(e, n)
p,q = getpq(n,e,d)
#print p
#print q
privkey = RSA.construct((long(n), long(e), long(d), long(p), long(q)))
key = PKCS1_OAEP.new(privkey)
m = key.decrypt(secret)
print m
if __name__=="__main__":
main()注意，该脚本需要rsa-wiener-attack工具包的目录中执行，还需提前将密文文件message一同放到该目录下。
解题脚本如下：
基于rsa-wiener-attack解题
github.com/Mr-Aur0ra/RSA/blob/master/(16)PKCS1_OAEP%E6%A8%A1%E5%BC%8F%E7%9A%84RSA/rsa-wiener-attack/exp1.py
以上是我当时做的步骤。
大佬们其实只要几行代码就可以解决，膜膜膜。
以下是ChaMd5团队给出的本题WriteUp(我进行了部分修改，便于理解)：
维纳攻击，公钥文件中获取到e很大，利用维纳攻击可以拿到d。
维纳攻击
github.com/pablocelayes/rsa-wiener-attack
然后利用e、d、n获取p、q，生成私钥文件：
#exp2.py
from Crypto.PublicKey import RSA
from Crypto.Util.number import inverse, long_to_bytes
e = 3683191938452247871641914583009119792552938079110383367782698429399084083048335018186915282465581498846777124014232879019914546010406868697694661244001972931366227108140590201194336470785929194895915077935083045957890179080332615291089360169761324533970721460473221959270664692795701362942487885620152952927112838769014944652059440137350285198702402612151501564899791870051001152984815689187374906618917967106000628810361686645504356294175173529719443860140795170776862320812544438211122891112138748710073230404456268507750721647637959502454394140328030018450883598342764577147457231373121223878829298942493059211583
d = 1779217788383673416690068487595062922771414230914791138743960472798057054853883175313487137767631446949382388070798609545617543049566741624609996040273727
n = 24493816160588971749455534346389861269947121809901305744877671102517333076424951483888863597563544011725032585417200878377314372325231470164799594965293350352923195632229495874587039720317200655351788887974047948082357232348155828924230567816817425104960545706688263839042183224681231800805037117758927837949941052360649778743187012198508745207332696876463490071925421229447425456903529626946628855874075846839745388326224970202749994059533831664092151570836853681204646481502222112116971464211748086292930029540995987019610460396057955900244074999111267618452967579699626655472948383601391620012180211885979095636919
p=163724217068973025857079545677048587508164102644298632911494474022224582218067057349189211462632427829087720476013052665037199232658015194718500750961261016558605363103092187533086949903145449057015220561698195502163792192055762108803714387175594231859738263839090338762578040513451585421537323416472060788989
q=149604112324264915811376746906108325951188179904814259006959765070266946659481820938211689946210254302179197289522748397160602946376246768419310765669852537378426700376878745285639531531077237124655345323906476180103106894642043615024716862503414785057646920410083538192951872861366496901158348770066798098371
keypair = RSA.generate(2048)
keypair.p = p
keypair.q = q
keypair.e = e
keypair.n = n
keypair.d = d
private_key = keypair.exportKey().decode('utf-8')
f = open('pri.pem', 'w') #生成的私钥文件是pri.pem。
f.write(private_key)openssl解密即可。
详细的openssl使用方法可参考：
openssl常用命令，签名、非对称加解密 - kk Blog -- 通用基础
abcdxyzk.github.io/blog/2018/02/09/tools-openssl/