RSA加密算法

0x01 RSA介绍

RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。
对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。假如有人找到一种快速因数分解的算法的话,那么用RSA加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA钥匙才可能被强力方式解破。到目前为止,世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长,用RSA加密的信息实际上是不能被解破的。

0x02 RSA算法

RSA的安全基于大数分解的难度。其公钥和私钥是一对大素数(100到200位十进制数或更大)的函数。从一个公钥和密文恢复出明文的难度,等价于分解两个大素数之积(这是公认的数学难题)。
  RSA的公钥、私钥的组成,以及加密、解密的公式可见于下表:

算法描述:
(1)选择一对不同的、足够大的素数p,q。

(2)计算n=pq。

(3)计算f(n)=(p-1)(q-1),同时对p, q严加保密,不让任何人知道。

(4)找一个与f(n)互质的数e,且1<e<f(n)。

(5)计算d,使得de≡1 mod f(n)。这个公式也可以表达为d ≡e-1 mod f(n)

(6)公钥KU=(e,n),私钥KR=(d,n)。

(7)加密时,先将明文变换成0至n-1的一个整数M。若明文较长,可先分割成适当的组,然后再进行交换。设密文为C,则加密过程为

(8)解密过程为

0x03 python计算私钥

已知p,q,e,求d

1
2
3
4
5
6
7
import gmpy2
p=473398607161
q=4511491
e=17
phi=(p-1)*(q-1)
d=long(gmpy2.invert(e,phi))
print d

0x04 python解密

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

1
2
3
4
5
6
7
8
9
10
11
12
import gmpy2

n=73069886771625642807435783661014062604264768481735145873508846925735521695159
e=65537
p = 386123125371923651191219869811293586459
q = 189239861511125143212536989589123569301
assert n==p*q

c=15116717704501623028903918131505510580599561357387431295289012193980554012811
d=gmpy2.invert(e,(p-1)*(q-1))
m=pow(c,d,n)
print (m)

0x05 已知e,d,n求p,q

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
28
29
30
31
32
33
34
35
36
import random  

def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
temp = a % b
a = b
b = temp
return a

def getpq(n,e,d):
p = 1
q = 1
while p==1 and q==1:
k = d * e - 1
g = random.randint ( 0 , n )
while p==1 and q==1 and k % 2 == 0:
k /= 2
y = pow(g,k,n)
if y!=1 and gcd(y-1,n)>1:
p = gcd(y-1,n)
q = n/p
return p,q

def main():

n = 0xa66791dc6988168de7ab77419bb7fb0c001c62710270075142942e19a8d8c51d053b3e3782a1de5dc5af4ebe99468170114a1dfe67cdc9a9af55d655620bbab
e = 0x10001
d = 0x123c5b61ba36edb1d3679904199a89ea80c09b9122e1400c09adcf7784676d01d23356a7d44d6bd8bd50e94bfc723fa87d8862b75177691c11d757692df8881
p,q = getpq(n,e,d)
print "p: "+hex(p)
print "q: "+hex(q)

if __name__ == '__main__':
main()

0x06 公因数分解n

1
2
3
4
5
6
7
8
9
10
11
12
13
def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
temp = a % b
a = b
b = temp
return a
n1=9051013965404084482870087864821455535159008696042953021965631089095795348830954383127323853272528967729311045179605407693592665683311660581204886571146327720288455874927281128121117323579691204792399913106627543274457036172455814805715668293705603675386878220947722186914112990452722174363713630297685159669328951520891938403452797650685849523658191947411429068829734053745180460758604283051344339641429819373112365211739216160420494167071996438506850526168389386850499796102003625404245645796271690310748804327
n2=13225948396179603816062046418717214792668512413625091569997524364243995991961018894150059207824093837420451375240550310050209398964506318518991620142575926623780411532257230701985821629425722030608722035570690474171259238153947095310303522831971664666067542649034461621725656234869005501293423975184701929729170077280251436216167293058560030089006140224375425679571181787206982712477261432579537981278055755344573767076951793312062480275004564657590263719816033564139497109942073701755011873153205366238585665743
print "p: "+str(gcd(n1,n2))
print "q1: "+str(n1/gcd(n1,n2))
print "q2: "+str(n2/gcd(n1,n2))

0x07

OpenSSL 使用PEM 文件格式存储证书和密钥。PEM 实质上是Base64 编码的二进制内容,再加上开始和结束行,如证书文件的—–BEGIN CERTIFICATE—–和—–END CERTIFICATE—–在这些标记外面可以有额外的信息,如编码内容的文字表示。

解题思路是:①使用openssl解密.pem中参数–>②参数十六进制转换为十进制–>③利用factor对大整数进行分解,得到p和q –>④用rsatool生成私钥文件: private.pem–>⑤用private.pem解密flag.enc

解析加密密钥

openssl rsa -pubin -text -modulus -in pub.key
openssl rsa -pubin -text -modulus -inwarmup -in pubkey.pem

生成解密密钥

rsatool: https://github.com/ius/rsatool

python rsatool.py -o private.pem -e 65537 -p XXX-q XXX

python rsatool.py -f PEM -o key.key -p 1 -q 1 -e 1

openssl rsautl -decrypt -inkey key.pem -in flag.enc -out flag
脚本生成解密密钥
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# coding=utf-8
import math
import sys
from Crypto.PublicKey import RSA

keypair = RSA.generate(1024)
keypair.p =
keypair.q =
keypair.e =
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()

解密

openssl rsautl -decrypt -in flag.enc -inkey private.pem
-------------本文结束感谢您的阅读-------------
/*
*/