RSA算法及攻击方法(一)

发表于 | 分类于 | | 热度: ℃
字数统计: 2,566 | 阅读时长 ≈ 12

0x00 RSA算法

RSA算法主要基于大整数分解这一困难问题设计.下面介绍一下加解密过程.

首先是需要用到的参数: 

1
2
3
4
5
6
7
m: 需要加密的消息即明文.
c: 加密之后的结果即密文.
p,q: 两个大素数.
N: N=p*q,加解密过程中的模数.
e: 加密密钥.
d: 解密密钥.
phi(N): 模数N的欧拉函数.

然后是加解密关系式:

信息传播过程中,常将(e,N)作为公钥和密文c一同传播,而(d,N)作为私钥留在加密者和合法的接收者手中.选取并通过p*q计算N非常容易,但通过N还原p,q则是困难为题,这保证了该算法的安全性. 具体RSA基础可以参考:RSA基础

0x01 数学基础

模逆运算

如果(a*b) mod c == 1,那么a和b互为对方模c的模逆元/数论倒数,也写作$ a^(-1) \equiv b (mod c) $或$ a*b \equiv 1 (mod c) $

关于最大公约数有一个基本事实:给予两整数a、b,必存在整数x、y,使得a*x + b*y = gcd(a, b).从而当a、b互素时,有a*x + b*y = 1,就有(a*x) mod b == 1,所以x就是a对b的模逆元.

最大公约数有一个定义是:a和b的最大公约数g是a和b的线性和中的最小正整数.

常使用扩展欧几里得算法的一个python实现如下: 

1
2
3
4
5
6
7
8
9
def egcd ( a , b ):
   if (b == 0):
       return 1, 0, a
   else:
       x , y , q = egcd( b , a % b ) # q = GCD(a, b) = GCD(b, a%b)
       x , y = y, ( x - (a // b) * y )
       return x, y, q 
def mod_inv(a,b):
  return egcd(a,b)[0]%b #求a模b得逆元

求模逆也可以使用gmpy2库的函数gmpy2.invert(a, b)。

模运算法则

推荐文章:模运算总结和取模运算涉及的算法

欧几里得算法

基本原理为:gcd(a,b) == gcd(b,a%b) while(b!=0)和gcd(a,0) == a

python实现如下: 

1
2
3
4
5
6
7
8
9
# 递归版
def gcd(a, b):
    return a if not b else gcd(b, a % b)

# 迭代版
def gcd2(a, b):
    while b:
        a, b = b, a % b
    return a

扩展欧几里得算法

扩展欧几里得算法能够求出满足a*x+b*y = gcd(a,b)的一组x,y.

参考文章

python实现如下: 

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
# 递归版
def ext_euclid ( a , b ):
    # ref:https://zh.wikipedia.org/wiki/扩展欧几里得算法
    if (b == 0):
        return 1, 0, a
    else:
        x1 , y1 , q = ext_euclid( b , a % b ) # q = GCD(a, b) = GCD(b, a%b)
        x , y = y1, ( x1 - (a // b) * y1 )
        return x, y, q
# 迭代版
def egcd(a, b):
    # ref:https://blog.csdn.net/wyf12138/article/details/60476773
    if b == 0:
        return (1, 0, a)
    x, y = 0, 1
    s1, s2 = 1, 0
    r, q = a % b, a / b
    while r:
        m, n = x, y
        x = s1 - x * q
        y = s2 - y * q
        s1, s2 = m, n
        a, b = b, r
        r, q = a % b, a / b
    return (x, y, b)

中国剩余定理

具体算法可以参考上文提到的文章.

当mi两两互素的时候,可以使用如下脚本进行计算: 

1
2
3
4
5
6
7
8
9
10
11
def CRT(mi, ai):
    # mi,ai分别表示模数和取模后的值,都为列表结构
    # Chinese Remainder Theorem
    # lcm=lambda x , y:x*y/gcd(x,y)
    # mul=lambda x , y:x*y
    # assert(reduce(mul,mi)==reduce(lcm,mi))
    # 以上可用于保证mi两两互质
    assert (isinstance(mi, list) and isinstance(ai, list))
    M = reduce(lambda x, y: x * y, mi)
    ai_ti_Mi = [a * (M / m) * gmpy2.invert(M / m, m) for (m, a) in zip(mi, ai)]
    return reduce(lambda x, y: x + y, ai_ti_Mi) % M

当mi不互素时,需要两两合并方程组.原理如下:

Mi不互素

实现代码: 

1
2
3
4
5
6
7
8
9
10
11
12
def GCRT(mi, ai):
    # mi,ai分别表示模数和取模后的值,都为列表结构
    assert (isinstance(mi, list) and isinstance(ai, list))
    curm, cura = mi[0], ai[0]
    for (m, a) in zip(mi[1:], ai[1:]):
        d = gmpy2.gcd(curm, m)
        c = a - cura
        assert (c % d == 0) #不成立则不存在解
        K = c / d * gmpy2.invert(curm / d, m / d)
        cura += curm * K
        curm = curm * m / d
    return (cura % curm, curm) #(解,最小公倍数)

0x02 常规攻击方法

由于RSA密码体系是基于大数分解这一困难问题设计,于是最先考虑到的便是分解N,然后根据加解密流程和关系式进行明文还原.

推荐工具

  • 大数分解网站:位数较低的模数(长度一般小于100bits)可以在网站的库中查询分解结果:
    大数分解网站
  • 如果模数的位数较高,可以使用工具yafu进行分解,该工具集成了NFS等分解算法,适用于windows系统
  • python环境下的libnum、gmpy2大数运算集成库
  • github上的集成工具,具体使用方法在项目内部有详细说明:CTF-RSA-Tools

常用脚本

使用欧几里得算法求私钥d

Input_parameters: p, q, e

Output_parameters: d 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 脚本一
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

p = number1
q = number2
e = number3
d = modinv(e,(p-1)*(q-1))
print("d = " + str(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
# 脚本二
#RSA扩展欧几里得算法 已知p,q,e求d
def gcd(a,b):
    while a!=0:
        a,b = b%a,a
    return b
#定义一个函数，参数分别为a,n，返回值为b
def findModReverse(a,m):#这个扩展欧几里得算法求模逆

    if gcd(a,m)!=1:
        return None
    u1,u2,u3 = 1,0,a
    v1,v2,v3 = 0,1,m
    while v3!=0:
        q = u3//v3
        v1,v2,v3,u1,u2,u3 = (u1-q*v1),(u2-q*v2),(u3-q*v3),v1,v2,v3
    return u1%m

p=eval(input('p='))
q=eval(input('q='))
e=eval(input('e='))

N=p*q
s=(p-1)*(q-1)

result=findModReverse(e,s)
print(result)

加密脚本

Input_parameters: m, p, q, e

Output_parameters: c 

1
2
3
4
5
6
7
8
9
import gmpy2 as gp

m = gp.mpz(int(input("m="), 16))
p = gp.mpz(int(input("p=")))
q = gp.mpz(int(input("q=")))
e = gp.mpz(int(input("e=")))
N = p*q
phin = (p-1)*(q-1)
c = gp.powmod(m, e, N)

解密脚本

Input_parameters: c, p, q, e

Output_parameters: m 

1
2
3
4
5
6
7
8
9
10
import gmpy2 as gp

c = gp.mpz(int(input("m="), 16))
p = gp.mpz(int(input("p=")))
q = gp.mpz(int(input("q=")))
e = gp.mpz(int(input("e=")))
N = p*q
phin = (p-1)*(q-1)
d = gp.invert(e, N)
m = gp.powmod(c, d, N)

文件型RSA攻击

所谓文件型RSA的题目,就是提供pubkey.pem和flag.enc文件.我们需要从pubkey.pem即证书文件中提取公钥信息,进行解密后生成private.pem私钥文件,然后对flag.enc文件进行解密得到结果.

常用命令如下(使用openssl对证书进行处理,使用rsatool.py对参数进行解密): 

1
2
3
4
5
6
7
8
openssl rsa -pubin -text -modulus -in warmup -in pubkey.pem
该命令用于从pem文件中提取公钥e和大数n

python rsatool.py -o private.pem -e e -p p -q q
其中,-p,-q,-e之后输入p,q,e的值,rsatool.py放在当前目录下

openssl rsautl -decrypt -in flag.enc -inkey private.pem -out flag.dec
得到公私钥之后使用上面的命令解密 输出可以选择flag.txt

0x03 基础CTF题目

已知p,q,e,求d

题目来源: buuctf RSA

题目描述: 

1
2
在一次RSA密钥对生成中，假设p=473398607161，q=4511491，e=17
求解出d作为flag提交

题目分析: 这是最基础的RSA题目,直接给出p和q的值.直接将所给信息写入脚本中即可求出d.将d按照flag提交要求进行进制转换后提交即可.

已知p,q,e,c,求m

题目来源: buuctf rsarsa

题目描述: 

1
2
3
4
5
6
7
8
9
Math is cool! Use the RSA algorithm to decode the secret message, c, p, q, and e are parameters for the RSA algorithm.


p =  9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q =  11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e =  65537
c =  83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034

Use RSA to find the secret message

题目分析: 该类题目已知p,q,e和c.先通过模逆算法求出d,再通过m = gp.powmod(c, d, p*q)求出m即可

已知p,q,dp,dq,c,求m

题目来源: buuctf RSA1

题目描述: 

1
2
3
4
5
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

题目分析: 其中dp $\equiv$ d mod $\phi$(p), dq $\equiv$ d mod $\phi$(q).

我们发现这是一个同于方程组,使用中国剩余定理合并即可.但是发现p-1和q-1不互素,我们进行推导如下:

我们令$ d = (dp-dq)/dd((q-1)/dd)^{-1}(q-1) + dq $,从而合理运用所给参数得出最终结果.

脚本如下: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import gmpy2 as gp

p = gp.mpz(p)
q = gp.mpz(q)
dp = gp.mpz(dp)
dq = gp.mpz(dq)
c = gp.mpz(c)

n = p*q
phin = (p-1)*(q-1)

dd = gp.gcd(p-1, q-1)

d=(dp-dq)//dd * gp.invert((q-1)//dd, (p-1)//dd) * (q-1) +dq
print(d)

m = gp.powmod(c, d, n)
print('-------------------')
print(m)
print(hex(m)[2:])
print(bytes.fromhex(hex(m)[2:]))

已知e, n, dp, c,求m

题目来源: buuctf RSA2

题目描述: 

1
2
3
4
5
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657

c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

题目分析: 我们根据$ dp \equiv d mod \phi(p)$进行推导.

从而$ k\phi(p) + edp = k’(p-1)*(q-1) + 1 $

移项得:$ (p-1)(k’(q-1)-k) + 1 = edp $

我们通过枚举x可以计算出p-1,从而还原所有参数.脚本如下: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import gmpy2 as gp

e = e
n = gp.mpz(n)
dp = gp.mpz(dp)
c = gp.mpz(c)

for x in range(1, e):
    if(e*dp%x==1):
        p=(e*dp-1)//x+1
        if(n%p!=0):
            continue
        q=n//p
        phin=(p-1)*(q-1)
        d=gp.invert(e, phin)
        m=gp.powmod(c, d, n)
        if(len(hex(m)[2:])%2==1):
            continue
        print('--------------')
        print(m)
        print(hex(m)[2:])
        print(bytes.fromhex(hex(m)[2:]))

文件型RSA

题目来源: buuctf RSA

题目描述: 下载附件之后发现有flag.enc和pub.key文件,于是使用openssl+rsatool解题.

题目分析: 题目中有.enc和.key文件,首先使用openssl的命令进行公钥提取.

111.png-297.4kB

我们可以得到e和n,在线分解n之后作为参数生成私钥.

222.png-368.6kB

最后使用private.pem与flag.enc生成flag文件.

333.png-54.8kB

请作者吃个小鱼饼干吧
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多