NEKO

RSA例题

2018/02/09

windows下openssl链接:
https://pan.baidu.com/s/1nvstpB7 密码:00l0

最基础的RSA

jarvis mediumRSA
链接:https://pan.baidu.com/s/1bAa1yu 密码:7281

利用openssl工具

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.PublicKey import RSA

def egcd(a,b):
if b==0:
return a,1,0
else:
g,x,y=egcd(b,a%b)
return g,y,x-a//b*y

pub=RSA.importKey(open("C:\\Users\\kuraraneko\\Desktop\\pubkey.pem").read())
n=pub.n #n
e=pub.e #e
p=275127860351348928173285174381581152299
q=319576316814478949870590164193048041239 #p,q用工具或网站http://factordb.com/求出
print(egcd(e,(p-1)*(q-1)))#求d
d=10866948760844599168252082612378495977388271279679231539839049698621994994673

private=RSA.construct((n,e,d)).exportKey().decode()#生成密钥

with open('private.pem','w') as f:#生成密钥文件
f.write(private)

上述代码用于生成密钥文件
将生成的密钥文件和密文文件放到openssl的bin文件夹内
运行openssl.exe
rsautl -decrypt -in flag.enc -inkey private.pem -out flag.dec
生成flag.dec.

直接用脚本

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
from Crypto.PublicKey import RSA
import codecs
def egcd(a,b):
if b==0:
return a,1,0
else:
g,x,y=egcd(b,a%b)
return g,y,x-a//b*y

pub=RSA.importKey(open("C:\\Users\\kuraraneko\\Desktop\\pubkey.pem").read())
n=pub.n #n
e=pub.e #e
p=275127860351348928173285174381581152299
q=319576316814478949870590164193048041239 #p,q用工具或网站http://factordb.com/
print(egcd(e,(p-1)*(q-1)))#求d
d=10866948760844599168252082612378495977388271279679231539839049698621994994673

c=int(codecs.encode(open('C:\\Users\\kuraraneko\\Desktop\\flag.enc','rb').read(),'hex_codec'),16)#将密文还原成16进制

m=hex(pow(c,d,n))[2:]#明文的16进制

if(len(m)%2==1):#16进制解密要求密文不能为奇数,在头部填0即可
m='0'+m

print(codecs.decode(m,'hex_codec'))#输出明文

(但输出结果前面一堆乱七八糟的东西没搞清是什么)

Rabin,e=2

Jarvis hardRSA
链接:https://pan.baidu.com/s/1bpbcTmn 密码:07c3
此题为Rabin加密算法http://blog.sina.com.cn/s/blog_64370f500100lhqz.html,用中国剩余定理求解。
求出e为2,发现和φ(n)不互素,判断是Rabin加密(雾,此处猜测)
由c≡m2mod n⇒mp≡√cmod p和mq≡√cmod q.根据c是模p的充分必要条件c(p-1)/2≡1 mod p⇒mp≡c(p+1)/4mod p 和mq≡c(q+1)/4mod q.下面应用中国剩余定理求解
代码:

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
35
from Crypto.PublicKey import RSA
import gmpy2
import codecs
#16进制解密
def run(m):
m=hex(m)[2:]
if len(m)%2==1:
m='0'+m
print(codecs.decode(m,'hex_codec'))

pub=RSA.importKey(open("C:\\Users\\kuraraneko\\Desktop\\pubkey.pem").read())
n=pub.n
e=pub.e
p=275127860351348928173285174381581152299
q=319576316814478949870590164193048041239
c=int(codecs.encode(open('C:\\Users\\kuraraneko\\Desktop\\flag.enc','rb').read(),'hex_codec'),16)

#下面是中国剩余定理求出4个解,其中必有一解为明文
M1=q
M2=p
M_1=gmpy2.invert(M1,M2)#M1的逆
M_2=gmpy2.invert(M2,M1)#M2的逆

a1=pow(c,(p+1)//4,p)
a2=pow(c,(q+1)//4,q)

x1=(a1*M1*M_1+a2*M2*M_2)%n
x2=(a1*M1*M_1-a2*M2*M_2)%n
x3=n-x1
x4=n-x2

run(x1)
run(x2)
run(x3)
run(x4)

两个有公因子的n

如果给了两个分解不出来的n,但他们两个有公因数,那么这个公因数就是q,就能求出p1和p2了

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
35
36
37
38
import codecs
def egcd(a,b):
if b==0:
return a,1,0
else:
g,x,y=egcd(b,a%b)
return g,y,x-a//b*y
def gcd(a,b):
if b==0:
return a
else:
return gcd(b,a%b)
n1=18263905851567773440446838695766097054252159817375942220432646590577605535001102705343902666589196712209131000424743250389209817386462242094905266578654348699073317748484503797678183012090375022172700739930717847219593096973008967105897376613550069563133191469825170677181620033104899474861544205137427444083416158205978241738189319430709815369614381957092634679663073529915011800029514945250518582469896694087993939399022631417819581576165949892810231692555896017395242464371112868608767990194529216988324463096379599680586615395063392235579858007086701467453321499203151052012397135583838714605379937464734426058203
n2=16950818485762084795193828768953323876388698051219062552262211712110062204954209462306530235388240321343855913666709750794055992220667151032536667937762799073479211925880106492191394846770654371623007051501782616639485222511300384032213459590408774089539345780246233268007572472533774114330568959631749390932599046733958624832563792588926026242133422467392689761450865841250657088270966077177543599222351800102728976845282712937106806976091210265560260177661816495238213887970556095475226646345568545415814035277834069152282458515989066082948101449829801979628039212597995349260855092279108102204886522855975419755219
c1=16274856857661787783089247952446020386301296490309822420733326939579521159181274564159881569720941773424141684911497028248685883897404191432880449283023146073930043226457053587418510143359803678057561120305169670182063356905346792409675959838228170818653485027257264058185367161472527834396804757004371950225319647551718070122431050642186905590213972232201966833949845104276760241004644118590467546314025479853604227295841523010158969804175921406672115195772809154058842429049437301440993794765038365224477229612151404063782303298937771968709567577283974551173044172598459482531433545960749147311254443274915272200560
c2=9946468920119252596998213656931348575944985856629754429330209121534145245119561878513995066589817036899299533093751237144960328759208855732474853794711347203865156360078772132790431594811682581926722057546683437873159107885652842304739962490836998123152090675606004046425633751397173768982047965656687448847259753864171018963561303276197312504508548802813909914926514763930195218396740593919987596462341469781868335025782329081775818968846955110510048099746584203570892950955431181639182647914240604278151551608856971433512600491550082244566145491335738112881861092354219766862656988674738232228115996349755982641605
e1=1804229351
e2=17249876309

q=gcd(n1,n2)
p1=n1//q
p2=n2//q

d1=egcd(e1,(p1-1)*(q-1))[1]
d2=egcd(e2,(p2-1)*(q-1))[1]

while d1<0:
d1+=(p1-1)*(q-1)
while d2<0:
d2+=(p2-1)*(q-1)
m2=hex(pow(c2,d2,n2))[2:]
m1=hex(pow(c1,d1,n1))[2:]
if(len(m2)%2==1):
m2='0'+m2
if (len(m1) % 2 == 1):
m1 = '0' + m1
print(codecs.decode(m1,'hex_codec'))
print(codecs.decode(m2,'hex_codec'))

2个e,一个n的共模攻击

Jarvis veryhardRSA
链接:https://pan.baidu.com/s/1hsamKV6 密码:aiud

当n到达2048或4096位时,无法分解出p,q,此时需要其他解法。
由加密脚本知明文被分别用e1,e2加密成2份密文,且n相同,属于共模攻击。
e1,e2互素,则存在s1,s2使s1e1+s2e2=1
则可以将c1≡me1mod n和c2≡me2mod n转化为
m≡c1s1*c2s2mod n

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
import codecs
import gmpy2
def egcd(a,b):
if b==0:
return a,1,0
else:
g,x,y=egcd(b,a%b)
return g,y,x-a//b*y

n=0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929
c1=int(codecs.encode(open("C:\\Users\\kuraraneko\\Desktop\\flag.enc1",'rb').read(),'hex_codec'),16)
c2=int(codecs.encode(open("C:\\Users\\kuraraneko\\Desktop\\flag.enc2",'rb').read(),'hex_codec'),16)
e1=17
e2=65537
s1=egcd(e1,e2)[1]
s2=egcd(e1,e2)[2]
#此处判断s1和s2是否小于0,因为pow()函数里s1和s2不能为负,
if(s1<0):
s1=-s1
c1=gmpy2.invert(c1,n)#若s1为负,s1取正,c1取逆
if(s2<0):
s2=-s2
c2=gmpy2.invert(c2,n)
m=codecs.decode(hex(pow(c1,s1,n)*pow(c2,s2,n)%n)[2:],'hex_codec')
print(m)

e=3,低指数攻击

Jarvis Extremely hard RSA
发现e=3
属于低指数攻击
c≡m3 mod n
则m=(c+kn)1/3 mod n k=0,1,2….
需要用到gmpy库的一个函数root,python3貌似只支持gmpy2,但gmpy2里的root改了(应该有其他方法替代,我就不想探索了),只好用kali里的python2.7去跑脚本了(跑到k=118719488的时候跑出结果)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import gmpy

c=545666236924510340010249577709750283325731706774285241719627277546281629429734726717293022303311450772262647904537263500252284243393598944613964442974546950954108203106726282255676706429218187217515454665602130999856741523362906632677988245886500953095201122016935004088287862399317170828388632964668574391252399791901016522260191839164586088073933168096433230663402492577707149742261018318811473591856287943664733276898405984282679026758294364432874973387827086342720762945025346962005339728347282927842299962927871005260338747371451546554777112213044710533502191671159066680035742327279159127279685106716107705888068319962657817786581813767331740609788885735155741039564703781141646102609725965697004923161084032164730408824475517786576979990372940555488021025837456038491436690372760376483602299268887032528766383572923258228355911069631275397149328319966792315903921085816103476508992023873616148326626245855060470294978538631677232260545724075728912626994884533001056079733734460116442499311813113038763837974777469202302071221647473459505245546281400799833123812072606012604323510933244028733287443734697557314202167934768160824072400916728008549350662843995750077421616789178835625661267955774815287104291379928002318796086248

n=721059527572145959497866070657244746540818298735241721382435892767279354577831824618770455583435147844630635953460258329387406192598509097375098935299515255208445013180388186216473913754107215551156731413550416051385656895153798495423962750773689964815342291306243827028882267935999927349370340823239030087548468521168519725061290069094595524921012137038227208900579645041589141405674545883465785472925889948455146449614776287566375730215127615312001651111977914327170496695481547965108836595145998046638495232893568434202438172004892803105333017726958632541897741726563336871452837359564555756166187509015523771005760534037559648199915268764998183410394036820824721644946933656264441126738697663216138624571035323231711566263476403936148535644088575960271071967700560360448191493328793704136810376879662623765917690163480410089565377528947433177653458111431603202302962218312038109342064899388130688144810901340648989107010954279327738671710906115976561154622625847780945535284376248111949506936128229494332806622251145622565895781480383025403043645862516504771643210000415216199272423542871886181906457361118669629044165861299560814450960273479900717138570739601887771447529543568822851100841225147694940195217298482866496536787241
e=3
i=0
while 1:
if gmpy.root((c+i*n),e)[1]==1:
print "yes"
m=gmpy.root((c+i*n),e)[0]
print m
print i
break
i=i+1

结果转成字符串即可

n&e都很大

http://www.shiyanbar.com/ctf/730
当n和e都特别大时可以用github上的脚本:https://github.com/pablocelayes/rsa-wiener-attack
RSAwienerHacker.py可以求出d:

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
'''
Created on Dec 14, 2011

@author: pablocelayes
'''

import ContinuedFractions, Arithmetic, RSAvulnerableKeyGenerator

def hack_RSA(e,n):
'''
Finds d knowing (e,n)
applying the Wiener continued fraction attack
'''
frac = ContinuedFractions.rational_to_contfrac(e, n)
convergents = ContinuedFractions.convergents_from_contfrac(frac)

for (k,d) in convergents:

#check if d is actually the key
if k!=0 and (e*d-1)%k == 0:
phi = (e*d-1)//k
s = n - phi + 1
# check if the equation x^2 - s*x + n = 0
# has integer roots
discr = s*s - 4*n
if(discr>=0):
t = Arithmetic.is_perfect_square(discr)
if t!=-1 and (s+t)%2==0:
print("Hacked!")
return d

# TEST functions

def test_hack_RSA():
print("Testing Wiener Attack")
times = 5

while(times>0):
e,n,d = RSAvulnerableKeyGenerator.generateKeys(1024)
print("(e,n) is (", e, ", ", n, ")")
print("d = ", d)

hacked_d = hack_RSA(e, n)

if d == hacked_d:
print("Hack WORKED!")
else:
print("Hack FAILED")

print("d = ", d, ", hacked_d = ", hacked_d)
print("-------------------------")
times -= 1

if __name__ == "__main__":
#test_is_perfect_square()
#print("-------------------------")
#test_hack_RSA()
d=hack_RSA(30749686305802061816334591167284030734478031427751495527922388099381921172620569310945418007467306454160014597828390709770861577479329793948103408489494025272834473555854835044153374978554414416305012267643957838998648651100705446875979573675767605387333733876537528353237076626094553367977134079292593746416875606876735717905892280664538346000950343671655257046364067221469807138232820446015769882472160551840052921930357988334306659120253114790638496480092361951536576427295789429197483597859657977832368912534761100269065509351345050758943674651053419982561094432258103614830448382949765459939698951824447818497599,109966163992903243770643456296093759130737510333736483352345488643432614201030629970207047930115652268531222079508230987041869779760776072105738457123387124961036111210544028669181361694095594938869077306417325203381820822917059651429857093388618818437282624857927551285811542685269229705594166370426152128895901914709902037365652575730201897361139518816164746228733410283595236405985958414491372301878718635708605256444921222945267625853091126691358833453283744166617463257821375566155675868452032401961727814314481343467702299949407935602389342183536222842556906657001984320973035314726867840698884052182976760066141)
print(d)

改下脚本,控制台下运行即可。
求出d后直接就能求明文了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.PublicKey import RSA

import codecs
def egcd(a,b):
if b==0:
return a,1,0
else:
g,x,y=egcd(b,a%b)
return g,y,x-a//b*y

pub=RSA.importKey(open("C:\\Users\\kuraraneko\\Desktop\\warmup.pub").read())
n=pub.n #n
e=pub.e #e

d=4221909016509078129201801236879446760697885220928506696150646938237440992746683409881141451831939190609743447676525325543963362353923989076199470515758399
c=0x1e04304936215de8e21965cfca9c245b1a8f38339875d36779c0f123c475bc24d5eef50e7d9ff5830e80c62e8083ec55f27456c80b0ab26546b9aeb8af30e82b650690a2ed7ea407dcd094ab9c9d3d25a93b2140dcebae1814610302896e67f3ae37d108cd029fae6362ea7ac1168974c1a747ec9173799e1107e7a56d783660418ebdf6898d7037cea25867093216c2c702ef3eef71f694a6063f5f0f1179c8a2afe9898ae8dec5bb393cdffa3a52a297cd96d1ea602309ecf47cd009829b44ed3100cf6194510c53c25ca7435f60ce5f4f614cdd2c63756093b848a70aade002d6bc8f316c9e5503f32d39a56193d1d92b697b48f5aa43417631846824b5e86

m=hex(pow(c,d,n))[2:]#明文的16进制

if(len(m)%2==1):#16进制解密要求密文不能为奇数,在头部填0即可
m='0'+m

print(codecs.decode(m,'hex_codec'))#输出明文

参考:
http://blog.csdn.net/veritas501/article/details/55257957
http://blog.sina.com.cn/s/blog_64370f500100lhqz.html

更多链接:
https://err0rzz.github.io/2017/11/14/CTF%E4%B8%ADRSA%E5%A5%97%E8%B7%AF/
https://github.com/0x01f/crypto_repo/blob/master/QWB_nextrsa/writeup.md

原文作者: n3k0

发表日期: February 9th 2018, 4:36:34

发出嘶吼: 没有魔夜2玩我要死了

CATALOG
  1. 1. 最基础的RSA
    1. 1.1. 利用openssl工具
    2. 1.2. 直接用脚本
  2. 2. Rabin,e=2
  3. 3. 两个有公因子的n
  4. 4. 2个e,一个n的共模攻击
  5. 5. e=3,低指数攻击
  6. 6. n&e都很大