我所理解的RSA加密算法

RSA简介

• 非对称加密算法。有一对公私钥组成。
• 1977年由三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，没错RSA是三个人名字的首字母。
• 密钥越长越难破解，1024位目前无法破解，因此1024位的RSA密钥基本安全，2048位的密钥极其安全。
• 公私钥的使用。公钥是公开的，一般公钥加密私钥解密（当然也可以反过来，但不安全），另外，使用私钥签名，公钥验证签名。

RSA原理

取一对RSA的公私钥，需要了解欧拉函数，欧拉定理 。这部分这里有详细介绍。在这我只总结下。
欧拉函数 —— 任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系。
用 φ(n) 表示，例如 φ(8) = 4 (1, 3, 5, 7 与其有互斥关系)

欧拉定理 —— 两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：

即，a的φ(n)次方 - 1 是 n 整数倍。

RSA公私钥生成步骤

• 选取两个质数 p, q
• n=p*q （n转化为二进制表示，即为RSA位数，位数越多越难破解）
• 计算出n的欧拉函数 φ(n) = (p-1)(q-1)
• 随机选择一个整数e, 条件是 1 < e < φ(n)， 且 e 与 φ(n) 互质。
• 计算e对于φ(n)的模反元素d
• 将n和e封装成公钥，n和d封装成私钥

ed ≡ 1 (mod φ(n))

RSA 实现

见github(java，android实现)

参考资料

RSA算法原理