CTF中关于RSA算法的攻击方式
RSA算法本身是安全的.
但是他的不正确用法使得RSA算法的攻击成功率提高了.
RSA算法在之前的文章中详细的介绍了.其攻击的核心就是获取两个大素数p和q.
RSA算法也是针对c, m, e, d, n, p, q这几个参数展开的.
但是题目不会直接给出, 而是以其他方式间接给出,或者要求我们获取.
一种最常见的就是给出pem文件, 我们可以通过openssl(kali自带)提取.
openssl的用法:
密钥生成参数:
rsa指定密钥生成(对密钥的操作)
-inkey 指定私钥文件
-out 指定解密后的文件
-pubin 表示输入文件为公钥.
-pubout 输出公钥
-text 以明文形式输出各种参数
-modulus 输出模数值
从私钥中提取公钥:
openssl rsa -pubout -in <pr.pem> -out <pu.pem>
密钥加解密参数:
rsautl 对明文和密文的操作
-in 输入文件
-inkey 输入的密钥
-encrypt 使用公钥加密
-decrypt 使用私钥解密
使用密钥解密文件.
openssl rsautl -decrypt -in <input.file> -inkey <pr.pem> -out <output.file>
使用密钥文件加密文件.
openssl rsautl -encrypt -in <input.file> -inkey <pr.pem> -out <output.file>
另一种则是有交互的,给一个IP,一个端口号,然后nc连接, 多轮交互,在交互中给出参数.
然后参数有了, 就开始各种各样的攻击.
下面讲解在CTF中, rsa的攻击手法
一.模数分解
RSA算法题目中, 最简单的就是分解模n.
分解之后获得大素数p和q, 进而求得d.
在之前的文章中只写了RSA的理论部分,现在把代码补上.
以下写几个python脚本:
1. 已知e,p,q,求d:
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('逆元不存在') else: return x % m e = p = q = d = modinv(e, (p-1)*(q-1))
2. 已知大数n, 求p,q.
给出一个大数n, 直接分解.
利用工具:
RSATool
利用在线网站:
分解完成之后, 就回到了上面1中的问题.
3.利用公约数
在一次加密中, 使用了两个大数n,
并且两个n都拥有相同的素因子,那么就可以直接通过欧几里得算法直接分解.
原理:
n1 = p * p1
n2 = p * p2
这种题目,一般会给出很多n, 而e可能是全部相同的.
直接上代码:
def gcd(a, b): if a < b: a, b = b, a while b != 0: temp = a % b a = b b = temp return a
通过脚本可以得到相同的素因子, 从而得到另一个素因子.
4.yafu
针对大整数的分解有很多种算法,性能上各有优异
有Fermat方法,Pollard rho方法,试除法,以及椭圆曲线法,连分数法,二次筛选法,数域分析法等等。
其中一些方法应用在RSA的攻击上也有奇效。
在p,q的取值差异过大,或者p,q的取值过于相近的时候,
Format方法与Pollard rho方法都可以很快将n分解成功
有个工具, 叫yafu, 下面的下载地址是基于window的.
当p和q的值相差较大或相差较小时, 可以使用这个工具.
下载地址:
用法:
解压到一个目录.为了方便使用, 将yafu-x64.exe改名成yafu.exe,
然后给这个目录添加path环境.
当有一个大数:
够大吧.
新建一个记事本, 把大数放里面, 在末位记得加一个换行.
然后执行:
yafu "factor(@)" -batchfile 1.txt
得到:
但是,原先的1.txt就没了.
二.低加密指数攻击
参数e, 也叫做加密指数. 在之前的文章中说到过, e是可以随意选取的
典型的就是e比较小, 而且只有一组加密, 比如这样:
n=0x7003581fa1b15b80dbe8da5dec35972e7fa42cd1b7ae50a8fc20719ee641d6080980125d18039e95e435d2a60a4d5b0aaa42d5c13b0265da4930a874ddadcd9ab0b02efcb4463a33361a84df0c02dfbd05c0fdc01e52821c683bd265e556412a3f55e49517778079cb1c1c1c22ef8a6e0bccd5e78888ff46167a471f6bff25664a34311c5cb8d6c1b1e7ac2ab0e6676d594734e8f7013b33806868c151316d0cf762a50066c596244fd70b4cb021369aae432e174da502a806e7a8ab13dad1f1b83ac73c0e9e39648630923cbd5726225f17cc0d15afadb7d2c2952b6e092ffc53dcff2914bfddedd043bbdf9c6f6b6b5a6269c5bd423294b9deac4f268eaadb e=0x3 c=0xb2ab05c888ab53d16f8f7cd39706a15e51618866d03e603d67a270fa83b16072a35b5206da11423e4cd9975b4c03c9ee0d78a300df1b25f7b69708b19da1a5a570c824b2272b163de25b6c2f358337e44ba73741af708ad0b8d1d7fa41e24344ded8c6139644d84dc810b38450454af3e375f68298029b7ce7859f189cdae6cfaf166e58a22fe5a751414440bc6bce5ba580fd210c4d37b97d8f5052a69d31b275c53b7d61c87d8fc06dc713e1c1ce05d7d0aec710eba2c1de6151c84d7bc3131424344b90e3f8947322ef1a57dd3a459424dd31f65ff96f5b8130dfd33111c59f3fc3a754e6f98a836b4fc6d21aa74e676f556aaa5a703eabe097140ec9d98只有n, e, c, 然后e就等于3, 典型的低加密指数攻击了, 直接贴脚本吧:
from gmpy2 import iroot n= e= c= i = 0 while True: if iroot(c + i * n, 3)[1] == True: print("Success!") print(iroot(c + i * n, 3)) break i += 1
n=0x92411fa0c93c1b27f89e436d8c4698bcf554938396803a5b62bd10c9bfcbf85a483bd87bb2d6a8dc00c32d8a7caf30d8899d90cb8f5838cae95f7ff5358847db1244006c140edfcc36adbdcaa16cd27432b4d50d2348b5c15c209364d7914ef50425e4c3da07612cc34e9b93b98d394b43f3eb0a5a806c70f06697b6189606eb9707104a7b6ff059011bac957e2aae9ec406a4ff8f8062400d2312a207a9e018f4b4e961c943dfc410a26828d2e88b24e4100162228a5bbf0824cf2f1c8e7b915efa385efeb505a9746e5d19967766618007ddf0d99525e9a41997217484d64c6a879d762098b9807bee46a219be76941b9ff31465463981e230eecec69691d1 e=0x6f6b385dd0f06043c20a7d8e5920802265e1baab9d692e7c20b69391cc5635dbcaae59726ec5882f168b3a292bd52c976533d3ad498b7f561c3dc01a76597e47cfe60614f247551b3dbe200e2196eaa001a1d183886eeacddfe82d80b38aea24de1a337177683ed802942827ce4d28e20efef92f38f1b1a18c66f9b45f5148cceabfd736de8ac4a49e63a8d35a83b664f9f3b00f822b6f11ff13257ee6e0c00ca5c98e661ea594a9e66f2bd56b33d9a13f5c997e67a37fcf9a0c7f04d119fe1ba261127357e64a4b069aefed3049c1c1fe4f964fd078b88bedd064abea385cfebd65e563f93c12d34eb6426e8aa321033cfd8fe8855b9e74d07fe4f9d70de46f c=0x2add7528efe278a70a43f97fc5af83bbaab1238364735d998de005d7feb1a8ab931c7410f0f785db455857b8154a68de318bfffd2099c5b06d6a5e859b3812752e0c28dd626dfa1c26e1dbf8bc43686de75863da5f9df96331d81302cb6269e9d71661b03910726db6add3b8b2f7629cc981800f88376ae5541b0e6b072a72bd22505cde978b5a8433c7279407083d585cc6e0d74bff7e1a62b1e895fccc0144145528f3c32433a1a66cb85fb16749ac1e9ff176bedf8fbf2157a616bcd8e457e7ac571df1c8e07b31c8eaa47f01dee15367389ea0d0e40fc58f2a2658d220922b046eb1fb78e99ccb4c166c9cf5750a91b17b21ef8d80a131466ed98e5c4d4a维纳攻击的代码直接去GitHub下:
import sys sys.setrecursionlimit(10000000)
from hashlib import sha256 from gmpy2 import invert, iroot from libnum import xgcd, invmod def commonN(n, e1, c1, e2, c2): s1, s2, _ = xgcd(e1, e2) if s1 < 0: s1 = -s1 c1 = invmod(c1, n) if s2 < 0: s2 = -s2 c2 = invmod(c2, n) m = (pow(c1, s1, n) * pow(c2, s2, n)) % n return m n = c1 = c2 = e1 = e2 = print(commonN(n,e1,c1,e2,c2)) # m=pow(c,d,n)
from libnum import gcd n1= n2= print("p -> {}".format(gcd(n1, n2))) print("q1 -> {}".format(n1 / gcd(n1, n2))) print("q2 -> {}".format(n2 / gcd(n1, n2)))
from gmpy2 import invert, iroot from libnum import xgcd, invmod def broadcast(n1, n2 ,n3, c1, c2, c3): n = [n1, n2, n3] C = [c1, c2, c3] N = 1 for i in n: N *= i Ni = [] for i in n: Ni.append(N / i) T = [] for i in xrange(3): T.append(long(invert(Ni[i], n[i]))) X = 0 for i in xrange(3): X += C[i] * Ni[i] * T[i] m3 = X % N m = iroot(m3, 3) return m[0] n1= c1= n2= c2= n3= c3= print(broadcast(n1, n2 ,n3, c1, c2, c3))
等待更新...