RSA 加密方案
RSA 算法
- RSA 加密和签名:因大整数因子分解难算,合数可成公钥。
d - 私钥,e - 公钥,n - 可公开的合数,(e,n) 作为公钥可以公开,(d,n) 作为私钥。
详细理论证明参考:RSA算法原理(二)
假设明文消息为 M,密文为 C
加密过程:
M
e
m
o
d
??
n
=
C
M^e\mod{n}=C
Memodn=C
解密过程:
C
d
m
o
d
??
n
=
M
C^d\mod{n}=M
Cdmodn=M
RSA 签名举例
#-*- coding:utf-8 -*-
import random
# 求最大公约数
def gcd(a, b):
if a < b:
return gcd(b, a)
elif a % b == 0:
return b
else:
return gcd(b, a % b)
# 快速幂+取模
def power(a, b, c):
ans = 1
while b != 0:
if b & 1:
ans = (ans * a) % c
b >>= 1
a = (a * a) % c
return ans
# 快速幂
def quick_power(a: int, b: int) -> int:
ans = 1
while b != 0:
if b & 1:
ans = ans * a
b >>= 1
a = a * a
return ans
# 大素数检测
def Miller_Rabin(n):
a = random.randint(2, n - 2) # 随机第选取一个a∈[2,n-2]
# print("随机选取的a=%lld\n"%a)
s = 0 # s为d中的因子2的幂次数。
d = n - 1
while (d & 1) == 0: # 将d中因子2全部提取出来。
s += 1
d >>= 1
x = power(a, d, n)
for i in range(s): # 进行s次二次探测
newX = power(x, 2, n)
if newX == 1 and x != 1 and x != n - 1:
return False # 用二次定理的逆否命题,此时n确定为合数。
x = newX
if x != 1: # 用费马小定理的逆否命题判断,此时x=a^(n-1) (mod n),那么n确定为合数。
return False
return True # 用费马小定理的逆命题判断。能经受住考验至此的数,大概率为素数。
# 卢卡斯-莱墨素性检验
def Lucas_Lehmer(num: int) -> bool: # 快速检验pow(2,m)-1是不是素数
if num == 2:
return True
if num % 2 == 0:
return False
s = 4
Mersenne = pow(2, num) - 1 # pow(2, num)-1是梅森数
for x in range(1, (num - 2) + 1): # num-2是循环次数,+1表示右区间开
s = ((s * s) - 2) % Mersenne
if s == 0:
return True
else:
return False
# 扩展的欧几里得算法,ab=1 (mod m), 得到a在模m下的乘法逆元b
def Extended_Eulid(a: int, m: int) -> int:
def extended_eulid(a: int, m: int):
if a == 0: # 边界条件
return 1, 0, m
else:
x, y, gcd = extended_eulid(m % a, a) # 递归
x, y = y, (x - (m // a) * y) # 递推关系,左端为上层
return x, y, gcd # 返回第一层的计算结果。
# 最终返回的y值即为b在模a下的乘法逆元
# 若y为复数,则y+a为相应的正数逆元
n = extended_eulid(a, m)
if n[1] < 0:
return n[1] + m
else:
return n[1]
# 按照需要的 bit 来生成大素数
def Generate_prime(key_size: int) -> int:
while True:
num = random.randrange(quick_power(2, key_size - 1), quick_power(2, key_size))
if Miller_Rabin(num): # 大概率是素数
return num
# 生成公钥和私钥
def KeyGen(p: int, q: int):
n = p * q
e = random.randint(1, (p - 1) * (q - 1))
while gcd(e, (p - 1) * (q - 1)) != 1:
e = random.randint(1, (p - 1) * (q - 1))
d = Extended_Eulid(e, (p - 1) * (q - 1))
return n, e, d
def Sign(x: int, d: int, n: int) -> int:
s = power(x, d, n)
return s
def Verify(s: int, e: int, n: int) -> int:
x_ = power(s, e, n)
return x_
if __name__ == '__main__':
key_size = 512
p = Generate_prime(key_size)
q = Generate_prime(key_size)
n, e, d = KeyGen(p, q)
# 消息
x = int(input("Message: "))
if type(x) != int: raise ValueError("Must be an integer!")
# 签名
s = Sign(x, d, n)
# 验证
x_ = Verify(s, e, n)
Valid = (x_ == x)
# Attack
s_ = random.randint(1, (p - 1) * (q - 1))
m_ = random.randint(1, (p - 1) * (q - 1))
# 记录
print("p:\t", p)
print("q:\t", q)
print("Private Key↓")
print("N:\t", n)
print("d:\t", d)
print("Public Key↓")
print("N:\t", n)
print("e:\t", e)
print("Signature↓")
print("s:\t", s)
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!