0x01 RSA简介

那么，有无可能在已知n和e的情况下，推导出d？
首先要知道
　　（1）ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。
　　（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
　　（3）n=pq。只有将n因数分解，才能算出p和q。
结论：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。

0x02 常见的RSA攻击方法

0x1 共模攻击

共模攻击，也称同模攻击，英文原名是 Common Modulus Attack 。
同模攻击利用的大前提就是，RSA体系在生成密钥的过程中使用了相同的模数n。
假设COMPANY用所有公钥加密了同一条信息M，也就是
c1 = m^e1%n
c2 = m^e2%n
此时员工A拥有密钥d1他可以通过
m = c1^d1%n
解密得到消息m
同时员工B拥有密钥d2
他可以通过
m = c2^d2%n
解密得到消息m如果，此时有一个攻击者，同时监听了A和B接收到的密文C1,C2，因为模数不变，以及所有公钥都是公开的，那么利用同模攻击，他就可以在不知道d1，d2的情况下解密得到消息m。

贴出破解脚本： #coding=utf-8 import sys; sys.setrecursionlimit(100000); 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 def main(): n= x e1= x e2= x c1= x c2= x s = egcd(e1, e2) s1 = s[1] s2 = s[2] # 求模反元素 if s1<0: s1 = - s1 c1 = modinv(c1, n) elif s2<0: s2 = - s2 c2 = modinv(c2, n) m = (pow(c1,s1,n)*pow(c2,s2,n))%n print m if __name__ == '__main__': main()

0x03 RSA题目

0x1 veryeasyRSA

已知RSA公钥生成参数：
p = 3487583947589437589237958723892346254777
q = 8767867843568934765983476584376578389
e = 65537
求d =
请提交PCTF{d}
直接写py脚本

from libnum import invmod p = 3487583947589437589237958723892346254777 q = 8767867843568934765983476584376578389 e = 65537 fn = (p-1)*(q-1) d = invmod(e,fn) print d

0x2 Easy RSA

还记得veryeasy RSA吗？是不是不难？那继续来看看这题吧，这题也不难。
已知一段RSA加密的信息为：0xdc2eeeb2782c且已知加密所用的公钥：
(N=322831561921859 e = 23)
请解密出明文，提交时请将数字转化为ascii码提交
比如你解出的明文是0x6162，那么请提交字符串ab

首先利用在线分解工具分解大整数
N = 13574881 * 23781539
利用脚本解密
注意要写一个快速计算的额脚本 # coding = utf-8 import libnum def fastExpMod(b, e, m): """ e = e0*(2^0) + e1*(2^1) + e2*(2^2) + ... + en * (2^n) b^e = b^(e0*(2^0) + e1*(2^1) + e2*(2^2) + ... + en * (2^n)) = b^(e0*(2^0)) * b^(e1*(2^1)) * b^(e2*(2^2)) * ... * b^(en*(2^n)) b^e mod m = ((b^(e0*(2^0)) mod m) * (b^(e1*(2^1)) mod m) * (b^(e2*(2^2)) mod m) * ... * (b^(en*(2^n)) mod m) mod m """ result = 1 while e != 0: if (e&1) == 1: # ei = 1, then mul result = (result * b) % m e >>= 1 # b, b^2, b^4, b^8, ... , b^(2^n) b = (b*b) % m return result def decryption(C, d, n): #RSA M = C^d mod n return fastExpMod(C, d, n) p = 13574881 q = 23781539 n = p * q fn = (p - 1) * (q - 1) e = 23 d = libnum.invmod(e,fn) print d C = int('0xdc2eeeb2782c', 16) M = decryption(C, d, n) flag = str(hex(M))[2:-1] print flag.decode('hex')

0x3 Medium RSA

首先利用openssl 生成n e root@kali:/media/sf_vboxshare/mediumRSA# openssl rsa -pubin -text -modulus -in pubkey.pem Public-Key: (256 bit) Modulus: 00:c2:63:6a:e5:c3:d8:e4:3f:fb:97:ab:09:02:8f: 1a:ac:6c:0b:f6:cd:3d:70:eb:ca:28:1b:ff:e9:7f: be:30:dd Exponent: 65537 (0x10001) Modulus=C2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD writing RSA key -----BEGIN PUBLIC KEY----- MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMJjauXD2OQ/+5erCQKPGqxsC/bNPXDr yigb/+l/vjDdAgMBAAE= 其中Exponent即为e值，Modulus即为N值，用yafu分解。
N = 87924348264132406875276140514499937145050893665602592992418171647042491658461
factor(87924348264132406875276140514499937145050893665602592992418171647042491658461) 得到 p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
d = 10866948760844599168252082612378495977388271279679231539839049698621994994673 利用python生成秘钥 # coding=utf-8 import math import sys from Crypto.PublicKey import RSA keypair = RSA.generate(1024) keypair.p = 275127860351348928173285174381581152299 keypair.q = 319576316814478949870590164193048041239 keypair.e = 65537 keypair.n = keypair.p * keypair.q Qn = long((keypair.p-1) * (keypair.q-1)) i = 1 while (True): x = (Qn * i ) + 1 if (x % keypair.e == 0): keypair.d = x / keypair.e break i += 1 private = open('private.pem','w') private.write(keypair.exportKey()) private.close() 然后直接用私钥解密。 root@kali:/media/sf_vboxshare/mediumRSA# openssl rsautl -decrypt -in flag.enc -inkey private.pem -out flag.dec root@kali:/media/sf_vboxshare/mediumRSA# cat flag.dec PCTF{256b_i5_m3dium}