rsa加解密 ######### :ref:`openssl rsa` RSA:: 简介: 1977 年 作者: * 麻省理工学院三位数学家Rivest、Shamir 和 Adleman * 罗纳德・李维斯特（Ron Rivest） * 阿迪・萨莫尔（Adi Shamir） * 伦纳德・阿德曼（Leonard Adleman） 算法: 加密: 密文=明文^E mod N 公钥: E 和 N 的组合 解密: 明文=密文^D mod N 私钥: D 和 N 的组合 说明: 对极大整数做因数分解的难度决定了RSA算法的可靠性 第一个能同时用于加密和数字签名的算法 速度是对应同样安全级别的对称密码算法的1/1000左右 缺点: 前向不安全 * 私钥参与了密钥交换 * 安全性取决于私钥是否安全保存 历史:: 1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名 对极大整数做因数分解的难度决定了RSA算法的可靠性 换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠 RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作 由于进行的都是大数计算，使得RSA最快的情况也比DES慢上好几倍，无论是软件还是硬件实现 速度一直是RSA的缺陷。一般来说只用于少量数据加密 RSA的速度是对应同样安全级别的对称密码算法的1/1000左右 已公开的或已知的攻击方法:: 1999年，RSA-155 (512 bits)被成功分解， 花了五个月时间（约8000 MIPS年）和224 CPU hours在一台有3.2G中央内存的Cray C916计算机上完成 2009年12月12日，编号为RSA-768（768 bits, 232 digits）数也被成功分解 这一事件威胁了现通行的1024-bit密钥的安全性，普遍认为用户应尽快升级到2048-bit或以上 .. figure:: https://img.zhaoweiguo.com/knowledge/images/encrypts/rsa_course.gif :width: 70% PKCS 补位算法 ============= * PKCS 补位算法是一种用于数据加密的填充方法，被广泛应用于公钥加密和数字签名技术中。该算法采用基于二进制补位的填充方式，以确保待加密的数据长度符合加密算法的要求。 * 在 PKCS 补位算法中，如果待加密的数据长度正好是块大小的整数倍，则需要增加一个完整的数据块，其中所有字节都是补位的字节数。如果待加密的数据长度不是块大小的整数倍，则需要添加补位字节，使得数据长度达到下一个块的整数倍。补位字节的值通常等于需要填充的字节数。 * PKCS 补位算法是对称加密算法中常用的一种填充方式，而非对称加密算法则常用 PKCS#1_v1.5 和 OAEP（PKCS#1_v2）等填充算法。 其他变种 ======== :: 1. EIGamal 方式: 与 RSA 不同的点在使用『离散对数』 密文长度是明文的2倍 由 Taher ElGamal 设计，利用了模运算下求离散对数困难的特性。被应用在 PGP 等安全工具中。 2. Rabin方式 与 RSA 不同的点在使用『平方根』 3. ECC(椭圆曲线密码, Elliptic Curve Cryptography): 1985 年由 Neal Koblitz 和 Victor Miller 分别独立提出 ECC 系列算法一般被认为具备较高的安全性，但加解密计算过程往往比较费时。 RSA算法流程 =========== 算法原理 -------- 算法本身基于一个简单的数论知识：给出两个素数，很容易算出乘积，然而通过乘积，计算出这两个素数就非常困难，尤其是素数为几百位的整数的情况下。 公钥和私钥的生成&使用 --------------------- 公钥和私钥的生成:: 准备两个非常大的素数 p 和 q； 计算 p 和 q 的乘积 n = p * q； 计算 （p-1）* (q-1) 的乘积 m =（p-1）* (q-1)； 找到一个数 e (1< e < m)，并满足 e 和 m 最大公约数为 1（即互为素数）； 找到一个数 d 使得 (e * d) % m = 1 即可得到 (n，e) 为公钥，(n，d) 为私钥 RSA 加密:: 对于明文 x，使用公钥（n，e）通过幂运算然后取模，加密过程为：y = x ^ e % n；y 即为密文。 RSA 解密:: 对于密文 y，使用私钥（n，d）解密过程和加密过程类似，为：x = y ^ d % n。 示例 ---- 密钥生成:: 取两个素数 p=11，q=13；计算 n = p * q =143； 计算 m =（p-1）* (q-1) = 10 * 12 = 120； 取一个数 e (1< e < m)，并满足 e 和 m 互为素数，取 e=7; 取一个数 d 使得 (e * d) % m = 1，由于（7 * 103）% 120 = 721 % 120 = 1，取 d = 103； 那么公钥 =（n，e）=（143，7）私钥 =（n，d） =（143， 103）； 加密运算:: 明文 x = 75， 密文 y = (x ^ e % n) = (75 ^ 7 % 143) = 13,348,388,671,875 % 143 = 114 解密运算:: 密文 y = 114，明文 x = (y ^ d % n) = (114 ^ 103 % 143) = 7.2643989613883693165853565422956e+211 % 143 = 75