0x00 前言

省赛两个rsa题，都没做出来，差2分一等奖，欲哭无泪

0x01 RSA算法

这次就针对ctf来总结一下各种RSA的解密方法,结合一些实际的例题。

基本上，RSA的题目都是围绕着：私钥d、n，公钥e、n，明文m，以及p、q，这几个参数展开的，所以我们要做的就是一步一步提取出这些参数，得到n,d就可以进行解密。

e.g1
1
2
3
4
5
6
c=0x23091e42fa7609c73f1941b320fad6d2ff6e47be588d1623f970f1fee7abd221c9834b208f3c888902fe87ca76ec1e1363757d93c6e25c49f1c61c72b141c0b8848b54a117427d8e30eeab89694eb5f849cafecb0e5361b9b2b0e3f89e0fdbcc66a6aad4a1a4a85d828083a01a5d569b7eeb6f9151794453382b524aa52993f9
d=0x28b95b7e3159a851cbf537e007ae49864b7dbb93fc370a5
n=0x9a724c6747de9eadccd33f4d60ada91754b8be8c65590cafe66f69a2f4afbfd359e47ca6fd2dbde8948062dc116bc574f4313ab99b2bb6d8ae47beaa0c1ebedd * 0x8c1c81cc005ce3dd6d684ebb88151dc0c53b1cef8a29b1cb8121860fb57d93117bf449aac4300dc6103ac6211c6f8ae68987d99aff0dd8967a4afa00f2116873
m=pow(c,d,n)
print hex(m)[2:len(hex(m))-1].decode('hex')
e.g2

当e=1时，相当于没有加密，直接对密文c进行 .decode(hex)，直接拿到flag

0x02 pem + enc文件

有时候赛题会提供你一些文件：

pem文件

我们可以从文件中提取出n,e

1、使用openssl提取 

openssl rsa -in public.pem -pubin -modulus -text

2、利用python脚本 

1
2
3
4
5
6
7
from Crypto.PublicKey import RSA
pub = RSA.importKey(open('./pub.pem').read())
n = long(pub.n)
e = long(pub.e)
print n
print e

然后将得到的n进行大数分解，这里用到工具yafu，比msieve好用，没有长度限制。 还有一个在线的工具factordb.com 

yafu-x64 "factor(@)" -batchfile n.txt

分解后得到p,q
使用rsatool生成私钥 

python rsatool.py -p xxx -q xxx -o priv.key

enc文件

就是保存密文的文件，结合上面生成的私钥，利用openssl来解密 

openssl rsautl -decrypt -in flag.enc -inkey priv.key -out flag.txt

即可得到明文flag

e.g http://www.shiyanbar.com/ctf/1918

0x03 n可以快速分解

将n大数分解得到p,q

然后模数分解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
e=23
p=23781539
q=13574881
d=modinv(e,(p-1)*(q-1))
print d

得到d之后我们就可以进行解密了

e.g jarvisoj BASIC-Easy RSA

0x04 有多个n

他们的q是相同的，我们取两个，求最大公约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
p = gcd(n1,n2)
print "p=",p,"\n\n","q=" , n1 // p
def gcd(a, b):
    if a < b:
        a, b = b, a
    while b != 0:
        temp = a % b
        a = b
        b = temp
    return a
n1 = 28989197955870674811941817152881961892555962828020048566215146047714999804743571465320756664500939106612607504133407755470924915037883788416084924998195415611009578161228226056524027626453567996030151847302248848345942762209886902216532270655286303624781479379460319335849225128417295447574269158603952744753408534894136230960676590980945838733350143370605144754932401806068003166087495356366335014736018745371974324955357717635855207674309628146381030418983172039685916675081977078212813718313201568394044637347955108623458947913411108888733982376607647705302281273170230540579872437433435253235534772724624778056181
n2 = 29703811006265969568420235185761287243393105045336995893094671661145408859269297497044834735198371987472186770953203812235003929122122129964989222762478116003185582578013431109127657242169359697936471497781547555222392181694624446976869099519331688628488881595076878345856808384797954271081176432330698334469596003760530797898645529616535584139559768170011693043197581376652770244664582733792825511473683193195672487559140733668442863818306947800631472845430628311685792799840854080385208783178691512540436222290062939858472754953657763052720510548438848633979413756332920634307585878271699119574149435107725143578613
p = gcd(n1,n2)
print "p=",p,"\n\n","q=" , n1 // p

得到p、q，注意这是n1的p
接下来与上面解法相同，可以将c.decode(‘hex’)写入文件利用openssl解密，也可以求出d利用脚本

e.g

n is 28989197955870674811941817152881961892555962828020048566215146047714999804743571465320756664500939106612607504133407755470924915037883788416084924998195415611009578161228226056524027626453567996030151847302248848345942762209886902216532270655286303624781479379460319335849225128417295447574269158603952744753408534894136230960676590980945838733350143370605144754932401806068003166087495356366335014736018745371974324955357717635855207674309628146381030418983172039685916675081977078212813718313201568394044637347955108623458947913411108888733982376607647705302281273170230540579872437433435253235534772724624778056181
e is 65537
c is 14200655400630956617529154837540349350095534430543196299987252783320359338882400858000649938298574946882176873795065987640380185922571487987903069796872680567596754211592988768630729844485795253975027297563832927176988502771266530781452168489731952873297707254669904609865565861351429459102567318447934677565870915603816516557032164955329497823771897899211076176905132170360842951444390670253036307048815943908305457043184642918674003085039564350070641592716116089015861491205237748561298604957423077954850396167621218521884114394431799317165818964438359695744604198246716410783223931430682808151056020475306791729591

n is 29703811006265969568420235185761287243393105045336995893094671661145408859269297497044834735198371987472186770953203812235003929122122129964989222762478116003185582578013431109127657242169359697936471497781547555222392181694624446976869099519331688628488881595076878345856808384797954271081176432330698334469596003760530797898645529616535584139559768170011693043197581376652770244664582733792825511473683193195672487559140733668442863818306947800631472845430628311685792799840854080385208783178691512540436222290062939858472754953657763052720510548438848633979413756332920634307585878271699119574149435107725143578613
e is 65537
c is 4578343924026570978472440931890325318245466288503599188533732998304051832656861172828218449138067382663459418589454854723253403947485557649615240187148291946554256687236506349553390057789720132702311963022032912389266835192465297150080916409872411988524410949952643478505491642457481045586019802683635095575472601541635397816830552539347027587330022646372943452066068029168471475125499435879399193076604330172042202401974524486727842888375820659903161039255979785711025431762267505041403586092799995451754527655054098031095440553010856162282818464431911828926227552966047893177859591679867661412947560702301353393344

0x05 低加密指数攻击

就是说e很小的时候，例如
e=3
当e=3，如果明文很小，导致明文的三次方仍然小于n，那么直接对密文开三次方，就可得到明文
如果明文三次方大于n，可以进行爆破

e.g jarvisoj (Extremely hard RSA)

脚本爆破

1
2
3
4
5
6
7
8
9
10
11
12
13
import gmpy
e=3
N=0xB0BEE5E3E9E5A7E8D00B493355C618FC8C7D7D03B82E409951C182F398DEE3104580E7BA70D383AE5311475656E8A964D380CB157F48C951ADFA65DB0B122CA40E42FA709189B719A4F0D746E2F6069BAF11CEBD650F14B93C977352FD13B1EEA6D6E1DA775502ABFF89D3A8B3615FD0DB49B88A976BC20568489284E181F6F11E270891C8EF80017BAD238E363039A458470F1749101BC29949D3A4F4038D463938851579C7525A69984F15B5667F34209B70EB261136947FA123E549DFFF00601883AFD936FE411E006E4E93D1A00B0FEA541BBFC8C5186CB6220503A94B2413110D640C77EA54BA3220FC8F4CC6CE77151E29B3E06578C478BD1BEBE04589EF9A197F6F806DB8B3ECD826CAD24F5324CCDEC6E8FEAD2C2150068602C8DCDC59402CCAC9424B790048CCDD9327068095EFA010B7F196C74BA8C37B128F9E1411751633F78B7B9E56F71F77A1B4DAAD3FC54B5E7EF935D9A72FB176759765522B4BBC02E314D5C06B64D5054B7B096C601236E6CCF45B5E611C805D335DBAB0C35D226CC208D8CE4736BA39A0354426FAE006C7FE52D5267DCFB9C3884F51FDDFDF4A9794BCFE0E1557113749E6C8EF421DBA263AFF68739CE00ED80FD0022EF92D3488F76DEB62BDEF7BEA6026F22A1D25AA2A92D124414A8021FE0C174B9803E6BB5FAD75E186A946A17280770F1243F4387446CCCEB2222A965CC30B3929
c=0x85c0de5f89e88720afd485f91ded38e9eaeda3a61ddee7087bbd29920ee40b6d53565edd1e418095586bd4f33015729d433af413c660e4c0b164ed025f91216d904578f7f20c5fb1e09e71992198d8e8d7fbd917597aee45ebf4ca80124ce9b47ed163f0b9d5716a9d6e1f5b8ae09b16cae30bbd64a15e17cc39a90fb62536ad943cdda9a4aac5978e3c93502535d5353638bc708c9b59cc9dc7bcb1d873336ce081591522b1d48904463783dd6837b1c41b8011889648e0acdfbd3ee259f717990828d16db34eb982446216db534dc06b9e7aaf90bccb54a1cc77c2813bdfe9a1b5c2e958c3ea8ca103ba1a89036b7014bbc962eb7a8c910e095bb83791bd9feee0d8f6af0c2e030cccc6d8729743419bdee0a1e45ab5e7324a344761c8cc8db30961a971d566e49c4562924c3ee001edece3445cd28dba264ba8a90c5e533542096c26aa7d874997a308025a5e95bfc6949ebd16cea889d242ab2e2ff2446090d07666d7574946e391d3f153d50346bc75da94634182df80f7ba97b77af8922f13e43b2df788902a209b9e569dd3c6faa4dd7b43899f59798845df642edeef34a186949cbe83c099f085f87a299591e715ccb4fe74612b00aebe25c114819cf887c256121915416acbcb058937e3d39eb7ef7143e145131119da9c3d9818599a0e5109727fb581bbc20eb3e6a25011b8e9034537c0e580a0ee8f1553805be8
i=0
while 1:
    if(gmpy.root(c + i*N, 3)[1]==1):
        print gmpy.root(c + i*N, 3)
        break
    i=i+1