-
历史
1977年三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。一直公开被破解的秘钥长度为768位，超过768位的可认为是安全的，1024长度的非常安全，2048位的极其安全
-
数学原理
-
互质关系
如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。
-
欧拉函数
任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？计算这个值的方法就叫做欧拉函数，以φ(n)表示。
-
欧拉定理
如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：
aφ(n)≡1(mod n)
也就是说，a的φ(n)次方被n除的余数为1 -
模反元素
如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。
ab ≡ 1(mod n)
这时，b就叫做a的”模反元素”。
-
-
RSA密钥生成步骤
-
随机选择两个不相等的指数p和q
实际应用中，这两个质数越大，就越难破解。
-
计算p和q的乘积n。
n需要转换为二进制，二进制的位数就是密钥长度，一般密钥长为1024，重要场合用2048位
-
计算n的欧拉函数φ(n)
根据公式：φ(n) = (p-1)(q-1)
-
随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质
实际应用中，常常选择65537。
-
计算e对于φ(n)的模反元素d。
ed ≡ 1 (mod φ(n))
-
将n和e封装成公钥，n和d封装成私钥。
实际应用中，公钥和私钥的数据都采用ASN.1格式表达
-
-
RSA算法的可靠性
一共出现p q n φ(n) e d 这几个关键数字
d是最重要的是因为它和n组成了私钥
（1）ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。
（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
（3）n=pq。只有将n因数分解，才能算出p和q。
所以，对n的因式分解的难度基本上等于RSA破解的难度。事实上人类已经分解的最大整数是232个十进制位，768个二进制位。比它更大的因数分解，还没有被报道过，因此目前被破解的最长RSA密钥就是768位。 -
加密和解密
-
加密要用公钥 (n,e)
所谓加密就是算出下式的c
me ≡ c (mod n) -
解密要用私钥(n,d)
公式：cd ≡ m (mod n) m即为加密前的明文
你可能会问，公钥(n,e) 只能加密小于n的整数m，那么如果要加密大于n的整数，该怎么办？有两种解决方法：一种是把长信息分割成若干段短消息，每段分别加密；另一种是先选择一种”对称性加密算法”（比如DES），用这种算法的密钥加密信息，再用RSA公钥加密DES密钥。
-
-
私钥解密的证明
一系列数学公式【头晕】
RSA加密算法笔记
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 参考【philippica】萌萌哒弱受RSA和强攻wiener想像这样一个场景，一堆情侣，每天早上alice站在东...
- 参考【philippica】萌萌哒弱受RSA和强攻wiener 想像这样一个场景，一堆情侣，每天早上alice站在...
- 密码学是在编码与破译的斗争实践中逐步发展起来的,并随着先进科学技术的应用，已成为一门综合性的尖端技术科学。 密码学...
