当前位置:首页 > 信息安全 > 正文内容

CTF中关于RSA算法的攻击方式

七星4年前 (2020-08-17)信息安全2040

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

利用在线网站:

http://factordb.com/

分解完成之后, 就回到了上面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.zip

用法:

解压到一个目录.为了方便使用, 将yafu-x64.exe改名成yafu.exe,

然后给这个目录添加path环境.

当有一个大数:

image.png

够大吧.

新建一个记事本, 把大数放里面, 在末位记得加一个换行.

然后执行:

yafu "factor(@)"  -batchfile 1.txt

得到:

image.png

但是,原先的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 

三.维纳攻击(低解密指数攻击)
与低加密指数基本相同, e取很大是为了加快解密的过程, 所以当e很大时, 可以使用维纳攻击碰碰运气, 比如:
n=0x92411fa0c93c1b27f89e436d8c4698bcf554938396803a5b62bd10c9bfcbf85a483bd87bb2d6a8dc00c32d8a7caf30d8899d90cb8f5838cae95f7ff5358847db1244006c140edfcc36adbdcaa16cd27432b4d50d2348b5c15c209364d7914ef50425e4c3da07612cc34e9b93b98d394b43f3eb0a5a806c70f06697b6189606eb9707104a7b6ff059011bac957e2aae9ec406a4ff8f8062400d2312a207a9e018f4b4e961c943dfc410a26828d2e88b24e4100162228a5bbf0824cf2f1c8e7b915efa385efeb505a9746e5d19967766618007ddf0d99525e9a41997217484d64c6a879d762098b9807bee46a219be76941b9ff31465463981e230eecec69691d1
e=0x6f6b385dd0f06043c20a7d8e5920802265e1baab9d692e7c20b69391cc5635dbcaae59726ec5882f168b3a292bd52c976533d3ad498b7f561c3dc01a76597e47cfe60614f247551b3dbe200e2196eaa001a1d183886eeacddfe82d80b38aea24de1a337177683ed802942827ce4d28e20efef92f38f1b1a18c66f9b45f5148cceabfd736de8ac4a49e63a8d35a83b664f9f3b00f822b6f11ff13257ee6e0c00ca5c98e661ea594a9e66f2bd56b33d9a13f5c997e67a37fcf9a0c7f04d119fe1ba261127357e64a4b069aefed3049c1c1fe4f964fd078b88bedd064abea385cfebd65e563f93c12d34eb6426e8aa321033cfd8fe8855b9e74d07fe4f9d70de46f
c=0x2add7528efe278a70a43f97fc5af83bbaab1238364735d998de005d7feb1a8ab931c7410f0f785db455857b8154a68de318bfffd2099c5b06d6a5e859b3812752e0c28dd626dfa1c26e1dbf8bc43686de75863da5f9df96331d81302cb6269e9d71661b03910726db6add3b8b2f7629cc981800f88376ae5541b0e6b072a72bd22505cde978b5a8433c7279407083d585cc6e0d74bff7e1a62b1e895fccc0144145528f3c32433a1a66cb85fb16749ac1e9ff176bedf8fbf2157a616bcd8e457e7ac571df1c8e07b31c8eaa47f01dee15367389ea0d0e40fc58f2a2658d220922b046eb1fb78e99ccb4c166c9cf5750a91b17b21ef8d80a131466ed98e5c4d4a 
维纳攻击的代码直接去GitHub下:
使用代码分解出d直接就出来了.
避坑:
当代码报错时候, 可以在最前面加上:
import sys
sys.setrecursionlimit(10000000) 


四. 共模攻击
和上面的一样, 都有一些特征, 共模, 看字面意思就是, 使用同一个n, 但是有多组c和e, 直接上解密脚本:
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)

五. n的公约数分解
当给了很多组n时, 可以尝试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)))

六. 广播攻击
多个n和c共用一个e, 可以尝试广播攻击, 解密代码:
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))



等待更新...

七星比特

相关文章

DC-1 对一个靶场的综合渗透

DC-1 对一个靶场的综合渗透

环境准备1. 下载下载地址 2. 导入直接使用VMware导入即可,网络选择nat,方便nmap直接扫描。 开始1. 确认目标确定网络正常后,使用nmap开始扫描nat全段:254是网关,1是我物...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。