密码系列9-数论不白学之RSA
0x00 RSA算法描述
RSA算法是1978年由R.Rivest, A.Shamir和L.Adleman提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。
1. 密钥的产生
让我们结合前面介绍的数论姿势来解释下每一步具体应该如何实现。
1. 选两个保密的大素数p 和q
这一步的实现需要用到我们前面讲的素性检测的姿势
素性检测算法采用Miller-Rabin素性检测算法，这一步我们已经可以实现，看下一步
2. 计算n = p× q,φ( n) = ( p - 1 ) ( q - 1) , 其中φ( n) 是n 的欧拉函数值。
这一步没什么好说的，上一步p,q都产生了，n自然就生成了，欧拉函数值也就产生了。这里由于p和q是素数，所以n的欧拉函数值是(p-1)(q-1)，关于欧拉函数值的具体如何计算，前面也介绍过。看下一步
3. 选一整数e, 满足1 < e< φ( n) , 且gcd(φ( n) , e) = 1
对于整数e的选取，一般取较小的素数，比如3啊，5啊之类的，对于是否满足最大公约数为1的验证，我们前面也介绍了可以用辗转相除法求最大公约数，如果经验证当前选中的e与n的欧拉函数值不互素的话，再换一个e，知道选中合适的e即可，这一步也不难。看下一步
4.计算d, 满足d· e≡1 mod φ( n) , 即d 是e 在模φ( n)下的乘法逆元, 因e 与φ( n)互素, 由模运算可知, 它的乘法逆元一定存在。
对于d的计算，即乘法逆元的计算问题，前面提到过用逆推辗转相除法来实现求逆元。也不难，看下一步
5.以{ e, n} 为公开钥, { d , n}为秘密钥。
这一步更没什么说的了。。。
到这，我们已经实现了生成RSA算法的公开钥和秘密钥，接下来就可以用这两个钥匙了。可以看出，有了前面的数论基础，RSA的每一步实现都是挺简单的，接下来，我们看一些RSA其他的东西。
2. 加密
加密时首先将明文比特串分组, 使得每个分组对应的十进制数小于n, 即分组长度小于log2 n，因为需要进行模n运算嘛，当然不能超过n了，要不然就会加密不完全，我也不知道该怎么描述，反正就是仔细一想的话，如果超过n的话，超过n的那一部分可以说在一开始就是多余的，模n的话跟直接舍去没什么两样。然后对每个明文分组m, 作加密运算:c≡m^e mod n
3. 解密
对密文分组的解密运算为： m≡c^d mod n
我们举个例子来看下RSA的具体运用以及计算过程：
0x01 RSA 算法中解密过程的正确性
排版麻烦，直接截图了
0x02 RSA算法中的计算问题
通过上面的介绍，我们对于RSA的整体流程已经没有问题了，下面我们来讨论下在RSA中如何优化一些比较复杂的计算步骤。
1. RSA的加密与解密过程
RSA 的加密、解密过程都为求一个整数的整数次幂, 再取模。如果按其含义直接计算, 则中间结果非常大, 有可能超出计算机所允许的整数取值范围。如上例中解密运算6677 mod 119 , 先求6677 再取模, 则中间结果就已远远超出了计算机允许的整数取值范围。这时我们就要采取策略了。
策略1 提高指数运算的有效性
例如求x^16 , 直接计算的话需做15 次乘法。然而如果重复对每个部分结果做平方运算即求x, x^2 ,x^4 , x^8 , x^16 则只需4 次乘法。我们这里将指数用二进制形式表示可以提高指数运算的有效性。
将指数运算化为这种形式后，此时并没有什么卵用，别急，要结合策略2
策略2 模运算的性质
运用模运算性质：( a× b) mod n = [ ( a mod n) × ( b mod n) ] mod n来简化运算。我们运用策略1将指数运算化为上述形式后，结合策略2，那么我们最多只需计算2次幂就可以得到最终结果。举个例子：
简化指数运算对应的代码为：1
2
3
4
5
6
7
8
9
10c= 0 ; d = 1;
for i = k downto 0 d0 {
c= 2× c;
d= ( d× d) mod n;
if bi = 1 then {
c= c+ 1 ;
d = ( d× a) mod n
}
}
return d
其中d 是中间结果, d 的终值即为所求结果。c 在这里的作用是表示指数的部分结果, 在这里起到便于理解的目的，其终值即为指数m, c 对计算结果无任何贡献, 算法中完全可将之去掉。
2. RSA密钥的产生
这个问题我们在上面讨论流程的时候已经说过了，下面说的详细点。
产生密钥时, 需要考虑两个大素数p、q 的选取, 以及e 的选取和d 的计算。因为n = pq 在体制中是公开的, 因此为了防止敌手通过穷搜索发现p、q, 这两个素数应是在一个足够大的整数集合中选取的大数。如果选取p 和q 为1010 0 左右的大素数, 那么n 的阶为1020 0 , 每个明文分组可以含有664 位( 1020 0 ≈2664 ) , 即83 个8 比特字节, 这比DES 的数据分组(8 个8 比特字节) 大得多, 这时就能看出RSA 算法的优越性了。因此如何有效地寻找大素数是第一个需要解决的问题。寻找大素数时一般是先随机选取一个大的奇数(例如用伪随机数产生器) , 然后用素性检验算法检验这一奇数是否为素数, 如果不是则选取另一大奇数, 重复这一过程, 直到找到素数为止。素性检验算法通常都是概率性的, 但如果算法被多次重复执行, 每次执行时输入不同的参数, 算法的检验结果都认为被检验的数是素数, 那么就可以比较有把握地认为被检验的数是素数。例如Miller-Rabin 算法。可见寻找大素数是一个比较繁琐的工作。然而在RSA 体制中, 只有在产生新密钥时才需执行这一工作。p 和q 决定出后, 下一个需要解决的问题是如何选取满足1 < e< φ( n) 和gcd (φ( n) ,e) = 1 的e, 并计算满足d· e≡1 mod φ( n)的d。这一问题可由推广Euclid 算法完成。
0x03 RSA的安全性
RSA 的安全性是基于分解大整数的困难性假定, 之所以为假定是因为至今还未能证明分解大整数就是NP问题(NP问题自行google), 也许有尚未发现的多项式时间分解算法。如果RSA 的模数n 被成功地分解为p×q, 则立即获得φ( n) = ( p - 1) ( q - 1 ) ,从而能够确定e 模φ( n) 的乘法逆元d, 即d≡ e^(-1) mod φ( n) , 因此攻击成功。
随着人类计算能力的不断提高, 原来被认为是不可能分解的大数已被成功分解。例如RSA-129 (即n 为129 位十进制数, 大约428 个比特)已在网络上通过分布式计算历时8 个月于1994 年4 月被成功分解, RSA-130 已于1996 年4 月被成功分解。
对于大整数的威胁除了人类的计算能力外, 还来自分解算法的进一步改进。分解算法过去都采用二次筛法, 如对RSA-129 的分解。而对RSA-130 的分解则采用了一个新算法, 称为推广的数域筛法, 该算法在分解RSA-130 时所做的计算仅比分解RSA-129 多10%。将来也可能还有更好的分解算法, 因此在使用RSA 算法时对其密钥的选取要特别注意其大小。估计在未来一段比较长的时期, 密钥长度介于1024 比特至2048 比特之间的RSA 是安全的。
是否有不通过分解大整数的其他攻击途径? 下面证明由n 直接确定φ( n)等价于对n的分解。
所以，n 直接确定φ( n)等价于对n的分解。但是，从上面的证明过程我们发现了新的问题。为保证算法的安全性, 对p 和q 提出以下要求:
- | p - q| 要大
- p - 1 和q - 1 都应有大素因子
上图已经说明了要避免这种重复加密攻击，须使t大，但这跟 p - 1 和q - 1 都应有大素因子有卵关系，别急，下面证明二者的等价性：
0x04 一定条件下对RSA算法的攻击
1. 共模攻击
在实现RSA时，为方便起见，可能给每一用户相同的模数n，虽然加解密密钥不同，然而这样做是不行的。
攻击手段：
2. 低指数攻击
0x05 RSA算法的填充
PKCS#1 v2.1或IEEE P1363都推荐使用e=3,因为这样加密速度很
PKCS#1模式中，如果密钥长度为1024位，那么输出的密文块长度为128个字节，输入的明文块长度最大是117个字节，如果输入的明文块小于117位。EM = 0x00 || 0x02 || PS || 0x00 || M
PS为随机数保证了同一M不同次加密不一样, PS长度为128- 3 - Len(M)
OS2IP 则是将一八位串转换为一非负整数,它的描述如下(RFC3447):
x = x(xLen-1) 256^(xLen-1) + x(xLen-2)256^(xLen-2) + …+ x_1 256 + x_0
RSA就到这。。。
