广州公司制作网站,0735郴州网,网站数据接口怎么做,百度识图网页入口RSA 算法
RSA 加密和签名#xff1a;因大整数因子分解难算#xff0c;合数可成公钥。 d - 私钥#xff0c;e - 公钥#xff0c;n - 可公开的合数#xff0c;(e,n) 作为公钥可以公开#xff0c;(d,n) 作为私钥。
详细理论证明参考#xff1a;RSA算法原理#xff08;二…RSA 算法
RSA 加密和签名因大整数因子分解难算合数可成公钥。 d - 私钥e - 公钥n - 可公开的合数(e,n) 作为公钥可以公开(d,n) 作为私钥。
详细理论证明参考RSA算法原理二
假设明文消息为 M密文为 C 加密过程 M e m o d n C M^e\mod{n}C MemodnC 解密过程 C d m o d n M C^d\mod{n}M CdmodnM
RSA 签名举例
#-*- coding:utf-8 -*-
import random# 求最大公约数
def gcd(a, b):if a b:return gcd(b, a)elif a % b 0:return belse:return gcd(b, a % b)# 快速幂取模
def power(a, b, c):ans 1while b ! 0:if b 1:ans (ans * a) % cb 1a (a * a) % creturn ans# 快速幂
def quick_power(a: int, b: int) - int:ans 1while b ! 0:if b 1:ans ans * ab 1a a * areturn 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 - 1while (d 1) 0: # 将d中因子2全部提取出来。s 1d 1x 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 newXif x ! 1: # 用费马小定理的逆否命题判断此时xa^(n-1) (mod n)那么n确定为合数。return Falsereturn True # 用费马小定理的逆命题判断。能经受住考验至此的数大概率为素数。# 卢卡斯-莱墨素性检验
def Lucas_Lehmer(num: int) - bool: # 快速检验pow(2,m)-1是不是素数if num 2:return Trueif num % 2 0:return Falses 4Mersenne pow(2, num) - 1 # pow(2, num)-1是梅森数for x in range(1, (num - 2) 1): # num-2是循环次数1表示右区间开s ((s * s) - 2) % Mersenneif s 0:return Trueelse:return False# 扩展的欧几里得算法ab1 (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, melse:x, y, gcd extended_eulid(m % a, a) # 递归x, y y, (x - (m // a) * y) # 递推关系左端为上层return x, y, gcd # 返回第一层的计算结果。# 最终返回的y值即为b在模a下的乘法逆元# 若y为复数则ya为相应的正数逆元n extended_eulid(a, m)if n[1] 0:return n[1] melse: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 * qe 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, ddef Sign(x: int, d: int, n: int) - int:s power(x, d, n)return sdef Verify(s: int, e: int, n: int) - int:x_ power(s, e, n)return x_if __name__ __main__:key_size 512p 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)# Attacks_ 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)
