现代密码系列：RSA密码详解
现代密码系列：RSA密码详解
前言
对常见现代密码做个归纳 本篇是最常见的RSA密码
- RSA简介
- 数学基础
- RSA原理
- RSA攻击
1、RSA简介
1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法
RSA是目前最有影响力和最常用的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准
今天只有短的RSA钥匙才可能被强力方式解破。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。目前普遍认为，模式n至少应该取1024位，最好是2048位。但在分布式计算和量子计算机理论日趋成熟的今天，RSA加密安全性受到了挑战和质疑
2、数学基础
（1）欧拉函数
在数论中，对正整数n，欧拉函数φ(n)是小于或等于n的正整数中与n互质的数的数目
此函数以其首名研究者欧拉命名，它又称为φ函数（由高斯所命名）或是欧拉总计函数
通式：φ(x) = x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn)
其中p1, p2……pn为x的所有质因数，x是不为0的整数
例如：φ(8) = 4 ,因为1，3，5，7均与8互质
性质：
- 欧拉函数是积性函数：若m,n互质，则
φ(mn)=φ(m)φ(n) - 当n为奇数时，
φ(2n)=φ(n) - p是素数时，
φ(p)=p-1
（2）辗转相除算法
用于求两个数的最大公约数
两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数
即GCD(x,y) = GCD(y，x mod y) ，x>y。
代码实现：
def GCD(x, y):|
if(y==0):
return x
else:
return GCD(y,x %y调库
from gmpy2 import*
m = gcd(a,b)
#from Crypto.Util. number import*
#m = GCD(a, b)（3）模运算
a模n的运算给出了a对模n的余数，这种运算称为模运算 注意：模运算的结果是从0到n-1的一个整数
性质：
- 模运算可交换、可结合、可分配
- 对每一个中间结果进行模m运算后再进行模m运算，其作用与先进行全部运算，然后再进行模m运算所得到的结果是一样的
(a+b)mod m=((a mod m)+(b mod m)) mod m(a-b)mod m=((a mod m)-(b mod m)) mod m(a×b)mod m=((a mod m) ×(b mod m)) mod m(a×(b+c))mod m=((a×b) mod m+(a×c) mod m) mod m
用途：
- 用于判断一个数是否能被另一个数整除。对 2 取模即可判断整数的奇偶性；从 2 到 n-1 取模则可判断一个数是否为质数
- 进制之间的转换
- 用于求取最大公约数的辗转相除法使用取模运算
- 密码学中的应用：从古老的凯撒密码到现代常用的RSA、椭圆曲线密码，它们的实现过程均使用了取模运算
（4）模逆元
任意三个整数a,b,N，如果满足 a*b mod N=1,则称b是a关于N的模逆元
3、RSA原理
RSA算法基于一个十分简单的数论事实:将两个大质数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥
加密过程
即对明文的E次方除以N后求余数 所以公钥＝(E , N)
解密过程
即对密文的D次方除以N后求余数 所以私钥＝(D, N)
直观理解
下面可以看两张图一张表直观理解 图出处：密码学：RSA加密算法详解
表出处：RSA 非对称加密原理（小白也能看懂哦~）
密钥对的生成
（1）求N
准备两个素数p，q
有N=p*q
N的二进制长度作为密钥的长度
这两个素数的挑选还没有有效的方法 但一定要是大素数且相距较远 挑选过程一般如下：
- 随机挑选一个大奇数n
- 随机选择一个整数a<n
- 执行概率素数测试，若n未通过则重选，多次通过则接受
（2）求L
L是 p－1 和 q－1的最小公倍数
有 L = φ(N)=（p-1)(q-1）
（3）求E
E必须满足两个条件
1<E<Lgcd(E,L)=1，需要E和L的最大公约数为1是为了保证一定存在解密时需要使用的数D
此时已经得到了公钥（E,N）
（4）求D
通过E计算D
1 < D < LD=(1 mod L) / E
于是得到私钥（D,N）
4、RSA算法脚本
# /usr/bin/env python
# -*- coding: UTF-8 -*-
import random
import time
import math
def pow_mod(p, q, n):
'''
幂模运算，快速计算(p^q) mod (n)
这里采用了蒙哥马利算法
'''
res = 1
while q :
if q & 1:
res = (res * p) % n
q >>= 1
p = (p * p) % n
return res
def gcd(a,b):
'''
欧几里得算法求最大公约数
'''
while a!=0:
a, b =b%a , a
return b
def mod_1(x, n):
'''
扩展欧几里得算法求模逆
取模负1的算法:计算x2= x^-1 (mod n)的值
'''
x0 = x
y0 = n
x1 = 0
y1 = 1
x2 = 1
y2 = 0
while n != 0:
q = x // n
(x, n) = (n, x % n)
(x1, x2) = ((x2 - (q * x1)), x1)
(y1, y2) = ((y2 - (q * y1)), y1)
if x2 < 0:
x2 += y0
if y2 < 0:
y2 += x0
return x2
def probin(w):
'''
随机产生一个伪素数，产生 w表示希望产生位数
'''
list = []
list.append('1') #最高位定为1
for i in range(w - 2):
c = random.choice(['0', '1'])
list.append(c)
list.append('1') # 最低位定为1
# print(list)
res = int(''.join(list),2)
return res
def prime_miller_rabin(a, n): # 检测n是否为素数
'''
第一步，模100以内的素数，初步排除很显然的合数
'''
Sushubiao=(2,3,5,7,11,13,17,19,23,29,31,37,41
,43,47,53,59,61,67,71,73,79,83,89,97)# 100以内的素数，初步排除很显然的合数
for y in Sushubiao:
if n%y==0:
#print("第一步就排除了%d %d"%(n,y))
return False
#print('成功通过100以内的素数')
'''
第二步 用miller_rabin算法对n进行检测
'''
if pow_mod(a, n-1, n) == 1: # 如果a^(n-1)!= 1 mod n, 说明为合数
d = n-1 # d=2^q*m, 求q和m
q = 0
while not(d & 1): # 末尾是0
q = q+1
d >>= 1
m = d
# if pow_mod(a, m, n) == 1:
# # 满足条件
# return True
# for i in range(q+1): # 0~q
# u = m * (2**i) # u = 2^i*m
# if pow_mod(a, u, n) == n-1:
# # 满足条件 这里为什么 2^q * m == n-1也满足条件？？？？？
# return True
# return False
# else:
# return False
for i in range(q): # 0~q-1, 我们先找到的最小的a^u，再逐步扩大到a^((n-1)/2)
u = m * (2**i) # u = 2^i * m
tmp = pow_mod(a, u, n)
if tmp == 1 or tmp == n-1:
# 满足条件
return True
return False
else:
return False
def prime_test(n, k):
while k > 0:
a = random.randint(2, n-1)
if not prime_miller_rabin(a, n):
return False
k = k - 1
return True
# 产生一个大素数(bit位)
def get_prime(bit):
while True:
prime_number = probin(512)
# prime_number = 12053183412038934244199647849825520631926841159909870489683772445800307815934262271616287581789478437690748874723873375535588732777117648057138401098671371
# print('生成的数字是%d\n'%prime_number)
for i in range(50): # 伪素数附近50个奇数都没有真素数的话，重新再产生一个伪素数
u = prime_test(prime_number, 5)
if u:
break
else:
prime_number = prime_number + 2*(i)
if u:
return prime_number
else:
continue
if __name__=='__main__':
p = get_prime(500) # 密钥p
q = get_prime(550) # 密钥q
n = p * q # 公开n
OrLa = (p-1)*(q-1) # 欧拉函数
while True: # 取一个合适的e，这里的e要和OrLa互素才行
e = 65537
if gcd(e, OrLa) == 1:
break
else:
e = e-1
d = mod_1(e, OrLa)
print('私钥p,q,d分别为:\n')
print('p: %d\n' % p)
print('q: %d\n' % q)
print('d: %d\n\n' % d)
print('公钥n,e分别为:\n')
print('n: %d\n' % n)
print('e: %d\n\n' % e)
M = int(input("请输入待加密的明文："))
C = pow_mod(M, e, n) # 加密
print('\n加密完成，得到的密文：\n%d\n'%C)
M = pow_mod(C, d, n) # 解密
print('解密完成，得到的明文为：\n%d\n'%M)5、RSA攻击
其实还是一个计算力的问题
最终得到p、q、e 就可以逆向解密
脚本
import libnum
from Crypto.Util.number import long_to_bytes
q = int("0xa6055ec186de51800ddd6fcbf0192384ff42d707a55f57af4fcfb0d1dc7bd97055e8275cd4b78ec63c5d592f567c66393a061324aa2e6a8d8fc2a910cbee1ed9",16)
p = int("0xfa0f9463ea0a93b929c099320d31c277e0b0dbc65b189ed76124f5a1218f5d91fd0102a4c8de11f28be5e4d0ae91ab319f4537e97ed74bc663e972a4a9119307",16)
e = int("0x6d1fdab4ce3217b3fc32c9ed480a31d067fd57d93a9ab52b472dc393ab7852fbcb11abbebfd6aaae8032db1316dc22d3f7c3d631e24df13ef23d3b381a1c3e04abcc745d402ee3a031ac2718fae63b240837b4f657f29ca4702da9af22a3a019d68904a969ddb01bcf941df70af042f4fae5cbeb9c2151b324f387e525094c41",16)
c = 0x7fe1a4f743675d1987d25d38111fae0f78bbea6852cba5beda47db76d119a3efe24cb04b9449f53becd43b0b46e269826a983f832abb53b7a7e24a43ad15378344ed5c20f51e268186d24c76050c1e73647523bd5f91d9b6ad3e86bbf9126588b1dee21e6997372e36c3e74284734748891829665086e0dc523ed23c386bb520
n = q*p
d = libnum.invmod(e, (p - 1) * (q - 1))
m = pow(c, d, n) # m 的十进制形式
string = long_to_bytes(m) # m明文
print(string)但这不太可能 一般是一些特殊情况
（1）给了公钥和密文
用公钥生成私钥去解密 已经有工具RsaCtfTool 可以通过公钥和密文解密 或者先生成私钥再解密
示例
- 攻防世界 Crypto高手进阶区 3分题 wtc_rsa_bbq
- 攻防世界 Crypto高手进阶区 3分题 cr4-poor-rsa
或者用openssl去获取e和n 然后大数分解 素数分解
示例
- 攻防世界 Crypto高手进阶区 4分题 RSA256
（2）共模攻击
场景：
- 同一个n，对相同的m进行了加密，e取值不一样，得到c1,c2
- e1和e2互质，即gcd(e1,e2)=1
于是可以在知道n,e1,e2,c1,c2 但不知道d1,d2的情况下，解出m
过程如下：
- 首先，密文有
c1 = m^e1 % n
c2 = m^e2 % n- 然后，因为
gcd(e1,e2)=1，必然存在一正一负的整数s1、s2使得e1*s1+e2*s2 = 1 - 于是，我们可以计算得到m
(c1 ^ s1 * c2 ^ s2) % n
= (m ^ e1 % n) ^ s1 * (m ^ e2 % n) ^ s2 % n
= m ^ (e1 * s1 + e2 * s2) % n
= m % n
= m示例
- 攻防世界 Crypto高手进阶区 4分题 best_rsa
结语
对RSA做了个归纳总结
工具
- 在线RSA公钥加密解密
- 在线RSA私钥加密解密
- RsaCtfTool
- Ubuntu下RsaCtfTool的安装及使用
- 素数分解
红客突击队于2019年由队长k龙牵头，联合国内多位顶尖高校研究生成立。其团队从成立至今多次参加国际网络安全竞赛并取得良好成绩，积累了丰富的竞赛经验。团队现有三十多位正式成员及若干预备人员，下属联合分队数支。红客突击队始终秉承先做人后技术的宗旨，旨在打造国际顶尖网络安全团队。
腾讯云开发者
