RSA算法复习
前段时间笔试,遇到一道题。给定了RSA的公钥(N,E)
,问给密文x=3
加密后的密文为?
由于太久没有做CTF密码题了,看到这道题,我感觉陌生有熟悉。N
和E
代表啥我早已忘记,最后我只能根据以前的印象自己猜测了一个答案写了上去。
因此前几天就把RSA算法又重新复习了一边,并且这次自己用python把算法简单模拟了一下,加深印象。
本文只是自己复习RSA加解密的大致过程,主要参考网上的一些文章,不保证文章正确,很可能有错误。请不要随便参考我的理解哈。本文不涉及任何数学证明(因为我数论基本啥都不会)
算法理解
参数生成
RSA的安全性基于大数质因数分解的困难性。
要执行RSA算法,首先要随机生成两个大质数,记为p
和q
(具体怎么生成的可能有一些算法吧,我对此不了解,只知道可以用随即大数+素性判定来实现,但这样子效率太低,实际环境中应该不会这么弄)
n=pq
\\
m = (p-1)(q-1) = \phi(n)
这里的\phi
表示的是欧拉函数
接下来我们要寻找一组互为乘法逆元的数e
和d
,所谓乘法逆元就是指要满足如下条件
ed=1(mod \ m)
当然这里数e
和d
都要和m
互质,不然不存在乘法逆元
当然的一些特殊情况,比如为1等肯定不行
这里的e
就是我们接下来加密要用到的密钥,d
就是解密要用的公钥
当然因为e
和d
互为乘法逆元,所以公钥和密钥其实交换了也是一样的,在数学上是对称的
这里要获得乘法逆元,我选择的是采用拓展欧几里得算法,不知道实际密码学库里实现是用的什么算法
加解密计算
要加密的信息为x
公钥为(n,e)
enc
为加密后的密文
dec
为解密后得到的信息
加密过程
enc = x^e \ mod \ n
解密过程
dec = enc^d \ mod \ n
算法保证x
和dec
一定是相同的
证明过程我也不太懂,需要基础数论知识
算法Python实现
import random
#拓展欧几里得算法
#输入a,b
#返回r,rx,ry
#r为a和b的最大公因数
#若r==1,有rx*a+ry*b=1
def extgcd(a,b):
if b==0:
return a,1,0
r,x,y = extgcd(b,a%b)
rx = y
ry = x-a//b*y
return r,rx,ry
def gete(m):
while True:
x = random.randint(2,m-1)
a,_,_ = extgcd(x,m)
if a==1:
return x
def getd(m,e):
a,x,y = extgcd(e,m)
assert a==1
if x<0:
x += (((-x)//m)+1)*m
return x
p = 31
q = 29
n = p*q
m = (p-1)*(q-1)
e = gete(m)
d = getd(m,e)
print("m={}".format(m))
print('public key is (n={},e={})'.format(n,e))
print('secret key is (n={},d={})'.format(n,d))
assert (e*d)%m==1
def encrept(s):
s = [ord(c) for c in s]
# print('step 1:',s)
s = [(item**e)%n for item in s]
# print('step 2:',s)
return s
def decrept(s):
# print('step 3:',s)
s = [(item**d)%n for item in s]
# print('step 4:',s)
s = [chr(item) for item in s]
return ''.join(s)
test_str = 'hello world'
encrept_str = encrept(test_str)
decrept_str = decrept(encrept_str)
print('test str:',test_str)
print('encrepted str:',encrept_str)
print('decrepted str:',decrept_str)