dede网站地图插件,周口建设企业网站公司,thinkphp搭建的微网站,免费建网站平台哪个好目录 一、算法简介二、算法描述2.1 密钥产生2.2 加密过程2.3 解密过程2.4 证明解密正确性 三、相关算法3.1 欧几里得算法3.2 扩展欧几里得算法3.3 模重复平方算法3.4 Miller-Rabin 素性检测算法 四、算法实现五、演示效果 一、算法简介 RSA算法是一种非对称加密算法#xff0c… 目录 一、算法简介二、算法描述2.1 密钥产生2.2 加密过程2.3 解密过程2.4 证明解密正确性 三、相关算法3.1 欧几里得算法3.2 扩展欧几里得算法3.3 模重复平方算法3.4 Miller-Rabin 素性检测算法 四、算法实现五、演示效果 一、算法简介 RSA算法是一种非对称加密算法它基于一个简单的数论事实将两个大质数相乘是容易的但反过来对它们的乘积进行因数分解却极其困难。RSA算法由罗纳德·李维斯特Ron Rivest、阿迪·萨莫尔Adi Shamir和伦纳德·阿德曼Leonard Adleman在1977年共同发明因此以他们姓氏的首字母命名。 RSA算法的特点总结以下是一些关键点 非对称加密 RSA是一种非对称加密算法使用一对密钥公钥用于加密私钥用于解密。这种设计使得RSA非常适合于安全通信因为公钥可以公开分享而私钥必须保密。 安全性 RSA的安全性基于大整数分解的困难性。只要密钥长度足够长目前没有已知的算法能在合理时间内破解RSA加密。 数字签名 RSA算法不仅可以用于加密还可以用于数字签名。发送者可以用自己的私钥对消息进行签名接收者可以用发送者的公钥验证签名确保消息的完整性和来源。 密钥长度 RSA需要较长的密钥长度来保证安全性。随着计算能力的提升推荐的密钥长度也在不断增加目前推荐至少使用2048位的密钥长度。 计算效率 相比于对称加密算法RSA在加密和解密时的计算效率较低特别是对于大量数据的处理。因此RSA通常不用于大量数据的直接加密而是用于加密对称密钥或进行数字签名。 广泛的应用 RSA算法被广泛应用于互联网安全通信如SSL/TLS协议中用于安全地传输敏感信息如信用卡信息、个人身份信息等。 标准化 RSA算法已经被多个国际标准组织采纳为标准如ISO/IEC和ITU-T。 密钥管理 由于RSA使用非对称密钥密钥管理相对复杂需要确保私钥的安全存储和传输。 抗量子计算 随着量子计算的发展RSA算法可能面临安全威胁。量子计算机理论上能够快速分解大整数从而破解RSA加密。因此后量子密码学正在研究能够抵抗量子攻击的加密算法。 灵活性 RSA算法允许用户根据需要选择不同的参数如密钥长度和加密指数以满足不同的安全和性能需求。
RSA算法的这些特点使其成为现代密码学中一个非常重要的工具尽管它也有一些局限性如计算效率和密钥管理的复杂性。
二、算法描述
2.1 密钥产生
1选取两个保密的大素数 p p p和 q q q 2计算模数 n p ∗ q np*q np∗q 和 n n n的欧拉函数值 φ ( n ) ( p − 1 ) ( q − 1 ) φ(n)(p-1)(q-1) φ(n)(p−1)(q−1) 3在 ( 1 , φ ( n ) ) (1,φ(n)) (1,φ(n))之间任选一整数 e e e使其满足 g c d ( e , φ ( n ) ) 1 gcd(e,φ(n))1 gcd(e,φ(n))1即 e e e和 φ ( n ) φ(n) φ(n)互素 4计算 e e e在模 φ ( n ) φ(n) φ(n)下的乘法逆元 d d d即 e ∗ d ≡ 1 ( m o d φ ( n ) ) e*d\equiv 1\pmod{φ(n)} e∗d≡1(modφ(n))因为 e e e和 φ ( n ) φ(n) φ(n)互素由裴蜀定理可知整数 d d d一定且唯一存在 5 { e , n } \{e,n\} {e,n}作为公钥 { d , n } \{d,n\} {d,n}作为私钥
2.2 加密过程
为了保证加解密的正确性首先将明文 m m m进行分组每个分组对应的十进制数值应小于模数 n n n即分组长度小于 log 2 n \log_2 n log2n然后进行分组加密。 加密运算 m e m o d n c 加密运算m^{e}\mod{n}c 加密运算memodnc
2.3 解密过程
对密文 c c c进行分组解密 解密运算 c d m o d n m 解密运算c^{d}\mod{n}m 解密运算cdmodnm
2.4 证明解密正确性
由加密过程 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可知 c d m o d n m e d m o d n c^{d}\mod{n}m^{ed}\mod{n} cdmodnmedmodn 又因为 e ∗ d ≡ 1 ( m o d φ ( n ) ) e*d\equiv 1\pmod{φ(n)} e∗d≡1(modφ(n))可得 e ∗ d k φ ( n ) 1 e*dkφ(n)1 e∗dkφ(n)1 k ∈ Z k\in\mathbb{Z} k∈Z所以 c d m o d n m e d m o d n m k φ ( n ) 1 m o d n c^{d}\mod{n}m^{ed}\mod{n} m^{kφ(n)1}\mod{n} cdmodnmedmodnmkφ(n)1modn 所以要证 c d m o d n m c^{d}\mod{n}m cdmodnm成立即证 m k φ ( n ) 1 m o d n m m^{kφ(n)1}\mod{n}m mkφ(n)1modnm成立注意: m n mn mn 分两种情况讨论 1 m m m和 n n n互素 由欧拉定理可得 m φ ( n ) ≡ 1 ( m o d n ) m^{φ(n)}\equiv 1\pmod{n} mφ(n)≡1(modn)则有 m k φ ( n ) m o d n 1 k m o d n 1 m o d n m^{kφ(n)}\mod{n}1^k\mod{n}1\mod{n} mkφ(n)modn1kmodn1modn所以 m k φ ( n ) 1 ≡ m ( m o d n ) m^{kφ(n)1}\equiv m\pmod{n} mkφ(n)1≡m(modn)即证 m k φ ( n ) 1 m o d n m m^{kφ(n)1}\mod{n}m mkφ(n)1modnm成立 2 m m m和 n n n不互素 因为 m n mn mn所以 m m m一定为 p p p或 q q q的倍数(如果 m m m同时是 p p p和 q q q的倍数则 m m m一定是 p ∗ q p*q p∗q的倍数与条件 m n p ∗ q mnp*q mnp∗q矛盾)。假设 m t ∗ p mt*p mt∗p t ∈ Z t\in\mathbb{Z}^ t∈Z则有 g c d ( m , q ) 1 gcd(m,q)1 gcd(m,q)1由欧拉定理可得 m φ ( q ) ≡ 1 ( m o d q ) m^{φ(q)}\equiv 1\pmod{q} mφ(q)≡1(modq)则有 m k φ ( q ) ≡ 1 ( m o d q ) m^{kφ(q)}\equiv 1\pmod{q} mkφ(q)≡1(modq) m k φ ( q ) ∗ φ ( p ) m k φ ( n ) ≡ 1 ( m o d q ) m^{kφ(q)*φ(p)}m^{kφ(n)}\equiv 1\pmod{q} mkφ(q)∗φ(p)mkφ(n)≡1(modq) 所以存在 r ∈ Z r\in\mathbb{Z} r∈Z使得 m k φ ( n ) r ∗ q 1 m^{kφ(n)}r*q1 mkφ(n)r∗q1等式两边同乘 m m m可得 m k φ ( n ) 1 m ∗ r ∗ q m ( t ∗ p ) ∗ r ∗ q m t ∗ r ∗ n m m^{kφ(n)1}m*r*qm(t*p)*r*qmt*r*nm mkφ(n)1m∗r∗qm(t∗p)∗r∗qmt∗r∗nm 由上述等式可得 m k φ ( n ) 1 ≡ m ( m o d n ) m^{kφ(n)1}\equiv m\pmod{n} mkφ(n)1≡m(modn)即证 m k φ ( n ) 1 m o d n m m^{kφ(n)1}\mod{n}m mkφ(n)1modnm成立 证毕 三、相关算法
3.1 欧几里得算法 欧几里得算法又称辗转相除法是一种用于计算两个非负整数最大公约数GCD的古老算法。该算法最早由古希腊数学家欧几里得在其著作《几何原本》中描述因此得名。 欧几里得算法的基本原理是通过不断用较大的数除以较小的数并取余数然后用较小的数和余数继续进行同样的操作直到余数为0为止。此时最后的非零余数即为这两个数的最大公约数。
其计算公式可以表示为 g c d ( a , b ) g c d ( b , a m o d b ) gcd(a,b)gcd(b,a\mod{b}) gcd(a,b)gcd(b,amodb)其中 a a a和 b b b是两个非负整数。 算法的正确性可以通过数学证明来验证。
例如假设 x x x是 a a a和 b b b的最大公约数则 x x x能够整除 a a a和 b b b表示为 a k 1 x , k 1 ∈ Z ak_{1}x,k_{1}\in\mathbb{Z} ak1x,k1∈Z b k 2 x , k 2 ∈ Z bk_{2}x,k_{2}\in\mathbb{Z} bk2x,k2∈Z 由于 a m o d b a\mod{b} amodb的结果是 a a a除以 b b b的余数根据 a a a和 b b b的表达式有 a m o d b ( k 1 x ) m o d ( k 2 x ) x ( k 1 m o d k 2 ) a\mod{b}(k_{1}x)\mod{(k_{2}x)}x(k_{1}\mod{k_{2}}) amodb(k1x)mod(k2x)x(k1modk2)设 m k 1 m o d k 2 mk_{1}\mod{k_{2}} mk1modk2则有 a m o d b x m a\mod{b}xm amodbxm所以 x x x也能够整除a a m o d b a\mod{b} amodb因此 x x x也是 b b b和 a m o d b a\mod{b} amodb的最大公约数这说明 g c d ( a , b ) g c d ( b , a m o d b ) gcd(a, b) gcd(b, a mod b) gcd(a,b)gcd(b,amodb)成立。
代码实现递归方式
def gcd(a: int, b: int) - int:欧几里得算法-求两个数的最大公约数递归版本:param a: 整数:param b: 整数:return: 返回a、b的最大公约数if b 0:return aelse:return gcd(b, a % b)代码实现非递归方式
def gcd(a: int, b: int) - int:欧几里得算法-求两个数的最大公约数非递归版本:param a: 整数:param b: 整数:return: 返回a、b的最大公约数while b ! 0:a, b b, a % breturn a3.2 扩展欧几里得算法 扩展欧几里得算法Extended Euclidean Algorithm是欧几里得算法也称为辗转相除法的扩展用于计算两个整数的最大公约数GCD以及找到满足裴蜀等式的整数解。具体来说对于任意两个整数 a a a和 b b b该算法不仅能计算出它们的最大公约数 d d d还能找到整数 x x x和 y y y使得 a x b y d axbyd axbyd成立。 扩展欧几里得算法基于裴蜀定理对于任意两个不全为0的整数 a a a和 b b b必存在整数 x x x和 y y y使得 a x b y g c d ( a , b ) axbygcd(a,b) axbygcd(a,b)成立其中 g c d ( a , b ) gcd(a,b) gcd(a,b)表示 a a a和 b b b的最大公约数。
推论 如果 a a a和 b b b是不全为0的整数且 g c d ( a , b ) 1 gcd(a,b)1 gcd(a,b)1则当且仅当存在整数 x x x和 y y y使 a x b y g c d ( a , b ) axbygcd(a,b) axbygcd(a,b)成立
算法通过递归的方式使用辗转相除法逐步缩小问题规模直到找到最大公约数并同时计算出对应的 x x x和 y y y
应用场景
求解线性不定方程扩展欧几里得算法可以用来求解形如 a x b y c axbyc axbyc的线性不定方程其中 a a a、 b b b和 c c c是已知整数 x x x和 y y y是未知整数。求模逆元在模运算中扩展欧几里得算法可以用来求解乘法逆元即找到一个整数 x x x使 a x ≡ 1 ( m o d n ) ax\equiv 1\pmod{n} ax≡1(modn)其中 n n n是模数。求解线性同余方程扩展欧几里得算法还可以用于求解线性同余方程即形如 a x ≡ b ( m o d n ) ax\equiv b\pmod{n} ax≡b(modn)的方程。
代码实现递归方式
def ext_gcd(a: int, b: int) - tuple:扩展欧几里得算法-求乘法逆元(递归版本):param a: 整数:param b: 整数:return: (gcd, x, y)其中gcd是a和b的最大公约数x和y是整数满足 a*x b*y gcdif b 0:return (a, 1, 0)else:gcd, x1, y1 ext_gcd(b, a % b)x y1y x1 - (a // b) * y1return (gcd, x, y)代码实现非递归方式
def ext_gcd(a: int, b: int) - tuple:扩展欧几里得算法-求乘法逆元非递归版本:param a: 整数:param b: 整数:return: (gcd, x, y)其中gcd是a和b的最大公约数x和y是整数满足 a*x b*y gcdx0, x1, y0, y1 1, 0, 0, 1while b ! 0:q, a, b a // b, b, a % bx0, x1 x1, x0 - q * x1y0, y1 y1, y0 - q * y1gcd, x, y a, x0, y0return gcd, x, y3.3 模重复平方算法 模重复平方算法Modular Exponentiation by Repeated Squaring是一种用于高效计算模幂的算法特别适用于处理大整数幂运算。该算法的核心思想是通过将指数二进制分解然后利用平方和乘法来计算幂的值。 该算法的优势在于其时间复杂度为 O ( log b ) O(\log{b}) O(logb) 显著提高了大整数幂运算的效率。因此它在密码学中有着广泛的应用尤其是在RSA加密算法中用于快速计算大整数的模幂。
具体来说模重复平方算法的基本步骤如下计算 a b m o d n a^{b}\mod{n} abmodn
指数二进制分解首先将指数 b b b转换成二进制表示。例如如果 b 560 b560 b560其二进制表示为 1000110000 1000110000 1000110000初始化结果初始化结果变量 d d d为1底数变量 a a a为给定的底数循环计算从高位到低位遍历指数的二进制表示。首先对当前结果变量 d d d进行平方运算对模数 n n n取余如果 b i 1 b_{i}1 bi1则再将当前结果变量 d d d乘以底数a 并对模数 n n n取余最终结果当所有位都处理完毕后得到的结果即为 a b m o d n a^{b}\mod{n} abmodn
例如 7 560 m o d 561 7^{560}\mod{561} 7560mod561 i i i9876543210 b i b_{i} bi1000110000 c c c01248173570140280560 d d d1749157526160241298166671
代码实现
def quick_mod(a: int, b: int, mod: int) - int:模重复平方算法-大数的模幂运算:param a: 底数:param b: 指数:param mod: 模数:return: 返回余数dc, d 0, 1# 将 b 转为二进制字符串bin_b bin(b)[2:]for i in bin_b:c c * 2d d * d % modif i 1:c c 1d (d * a) % modreturn d3.4 Miller-Rabin 素性检测算法 Miller-Rabin素性检测算法是一种用于判断一个数是否为素数的概率性算法。该算法基于费马小定理的逆定理并通过随机化方法来提高素性检测的准确性。Miler-Rabin算法的核心思想是利用费马小定理及其扩展形式。 算法检测过程 给定奇数 n ≥ 3 n\geq{3} n≥3和安全参数/检测次数 k k k记 n − 1 2 s d n-12^{s}d n−12sd d d d为奇数
随机选取整数 a a a 2 ≤ a ≤ n − 2 2\leq{a}\leq{n-2} 2≤a≤n−2计算 x 0 ≡ a d ( m o d n ) x_{0}\equiv a^{d}\pmod{n} x0≡ad(modn)如果 x 0 1 x_{0}1 x01或 x 0 n − 1 x_{0}n-1 x0n−1则通过检验 n n n可能为素数回到 1 1 1否则计算 x 1 ≡ x 0 2 ( m o d n ) x_{1}\equiv x_{0}^{2}\pmod{n} x1≡x02(modn)如果 x 1 n − 1 x_{1}n-1 x1n−1则通过检验可能为素数回到1否则计算 x 2 ≡ x 1 2 ( m o d n ) x_{2}\equiv x_{1}^{2}\pmod{n} x2≡x12(modn)如此继续计算 x i x_{i} xi下去直到计算到 x s − 1 x_{s-1} xs−1;如果 x s − 1 n − 1 x_{s-1}n-1 xs−1n−1则通过检验可能为素数回到1否则 n n n为合数上述过程重复 k k k次
代码实现
def miller_rabin(n: int, k: int 100) - bool:使用 Miller-Rabin 算法判断一个整数是否为素数:param n: 待检测的整数:param k: 迭代次数k 越大准确率越高:return: 如果 n 是素数返回 True否则返回 False# 特殊情况处理if n 1:return Falseif n 3:return Trueif n % 2 0:return False# 将 n-1 写成 2^r * d 的形式r, d 0, n - 1while d % 2 0:r 1d // 2# 进行 k 次迭代for _ in range(k):a random.randint(2, n - 2)x pow(a, d, n)if x 1 or x n - 1:continuefor _ in range(r - 1):x pow(x, 2, n)if x n - 1:breakelse:return Falsereturn True四、算法实现
import randomdef int2bytes(integer: int) - bytes:整数转换成字节串:param integer::return: 返回字节串# 1.计算所需的最小字节数if integer 0:len 1else:len int((integer.bit_length() 7) // 8)# 2.整数转换为字节串byte_string integer.to_bytes(len, byteorderbig)return byte_stringdef calculate_block_size(n: int) - int:计算块大小:param n: 模数n:return: 返回块大小单位:字节/块return (n.bit_length() - 1) // 8def gcd(a: int, b: int) - int:欧几里得算法-求两个数的最大公约数:param a: 整数:param b: 整数:return: 返回a、b的最大公约数while b ! 0:a, b b, a % breturn adef ext_gcd(a: int, b: int) - tuple:扩展欧几里得算法-求乘法逆元:param a: 整数:param b: 整数:return: (gcd, x, y)其中gcd是a和b的最大公约数x和y是整数满足 a*x b*y gcdx0, x1, y0, y1 1, 0, 0, 1while b ! 0:q, a, b a // b, b, a % bx0, x1 x1, x0 - q * x1y0, y1 y1, y0 - q * y1gcd, x, y a, x0, y0return gcd, x, ydef miller_rabin(n: int, k: int 100) - bool:使用 Miller-Rabin 算法判断一个整数是否为素数:param n: 待检测的整数:param k: 迭代次数k 越大准确率越高:return: 如果 n 是素数返回 True否则返回 False# 特殊情况处理if n 1:return Falseif n 3:return Trueif n % 2 0:return False# 将 n-1 写成 2^r * d 的形式r, d 0, n - 1while d % 2 0:r 1d // 2# 进行 k 次迭代for _ in range(k):a random.randint(2, n - 2)x pow(a, d, n)if x 1 or x n - 1:continuefor _ in range(r - 1):x pow(x, 2, n)if x n - 1:breakelse:return Falsereturn Truedef gen_prime(bits: int) - int:随机生成指定位数的素数:param bits: 指定随机生成素数的位数:return: 返回指定位数的随机生成素数while True:# 1.生成一个随机的bits的位奇数candidate random.getrandbits(bits)candidate | (1 (bits - 1)) | 1 # 确保最高位和最低位为1# 2.使用Miller-Rabin素性检测算法判断是否为素数if miller_rabin(candidate):return candidatedef quick_mod(a: int, b: int, mod: int) - int:模重复平方算法-大数的模幂运算:param a: 底数:param b: 指数:param mod: 模数:return: 返回余数dc, d 0, 1# 将 b 转为二进制字符串bin_b bin(b)[2:]for i in bin_b:c c * 2d d * d % modif i 1:c c 1d (d * a) % modreturn ddef gen_key(bits: int 1024) - tuple:生成密钥对:param bits: 指定生成p,q两个质因数的位数:return: (e,n),(d,n)# 1.生成p和q两个质因数p gen_prime(bits)while True:q gen_prime(bits)if p ! q:break# 2.计算除数n和n的欧拉函数值phin p * qphi (p - 1) * (q - 1)# 3.生成与phi互质的公钥e# e65537while True:e random.randint(2, phi - 1)# 判断是e、phi否互质if gcd(e, phi) 1:break# 4.计算私钥d# 确保d是正数并且在 phi 的范围内d ext_gcd(e, phi)[1] % phireturn (e, n), (d, n)def rsa_encrypt(m: bytes, public_key: int, n: int) - tuple:RSA加密函数:param m: 明文:param public_key: 公钥:param n: 模数:return: 返回加密明文# 1.计算块的大小# 保证每明文块的十进制数小于n,单位:字节/块block_size calculate_block_size(n)# 2.进行加密bytes_encrypted_blocks []int_encrypted_blocks []for i in range(0, len(m), block_size):# 取出单个明文快block m[i:i block_size]# 将明文块转换为整数int_block int.from_bytes(block, byteorderbig)# 对明文快进行加密int_encrypted_block quick_mod(int_block, public_key, n)int_encrypted_blocks.append(int_encrypted_block)# 整数转成字节串bytes_encrypted_block int2bytes(int_encrypted_block)bytes_encrypted_blocks.append(bytes_encrypted_block)return bytes_encrypted_blocks, int_encrypted_blocks # 字节串列表/整数列表def rsa_decrypt(c: list, private_key: int, n: int) - tuple:RSA解密函数:param c: 密文:param public_key: 私钥:param n: 模数:return: 返回解密密文# 1.计算块的大小block_size calculate_block_size(n)# 2.进行解密bytes_decrypted_blocks []int_decrypted_blocks []for block in c:# 将密文块转换为整数int_block int.from_bytes(block, byteorderbig)# 对密文块进行解密int_decrypted_block quick_mod(int_block, private_key, n)int_decrypted_blocks.append(int_decrypted_block)# 整数转成字节串bytes_decrypted_block int2bytes(int_decrypted_block)bytes_decrypted_blocks.append(bytes_decrypted_block)return bytes_decrypted_blocks, int_decrypted_blocks # 字节串列表/整数列表if __name__ __main__:# 1.生成密钥对public_key, private_key gen_key()print(f公钥e:{public_key[0]})print(f私钥d:{private_key[0]})print(f模数n:{private_key[1]})# 2.加密m 你好世界Hello world!m_ m.encode()print(f待加密明文:{m})print(f待加密明文-字节:{m_})print(f待加密明文-数字:{int.from_bytes(m_, byteorderbig)})c rsa_encrypt(m_, public_key[0], public_key[1])print(f加密明文-字节:{b.join(c[0])})print(f加密明文-数字:{c[1]})# 3.解密m rsa_decrypt(c[0], private_key[0], private_key[1])print(f解密密文:{b.join(m[0]).decode()})print(f解密密文-字节:{b.join(m[0])})print(f解密密文-数字:{m[1]})五、演示效果
