RSA那点事儿
2016-12-18 本文已影响72人
行走的程序猿
从工具入手
RSA-Tool 2使用说明
生成
- 按下start，随意移动鼠标指针，以生成随机数（算法？）
- 设置密钥长度，即n的长度，一般为2048bit（支持到4096）
- 设置指数e以及指数的进制，一般为10进制的63357
- 按下generate等待生成p/q/n/d
- 两次或两次以上生成相同的密钥对是不可能的
分解
- 将模数n复制到对应编辑框中，点击factor按钮，进行分解尝试
由p和q计算私钥d
- 选择p和q的进制
- 复制到对应编辑框
- 点击calc.d按钮
再来看看算法
生成算法
- 选取两个大素数p和q（p和q不相等）
- 定义模数n，n=pq
- 选取一个指数e，满足条件1<e<(p-1)(q-1)，e和(p-1)(q-1)互素（欧拉函数）
- 计算e的模反元素d，即ed = 1 mod (p-1)(q-1)，d就是私钥
- 分发公钥(N, e)
rsa可靠性来源
在n和e已知的情况下，是否能够求取私钥d？
ed≡1 mod (p-1)(q-1)
n=pq，已知p和q时才能求解d，而只知道n，就需要因数分解，基于大整数因数分解十分困难的事实，rsa在密钥长度足够的情况下，安全性得到了保证。
加解密算法
加密：m^e ≡ c (mod n)，其中m为明文，c为密文，(n, e)为公钥
解密：c^d ≡ m (mod n)，(n, d)为私钥
