RSA密码体制和整数因子分解
整理于2020年5月25日
大整数分解算法
Pollard p-1 算法
原理分析
设p为n的一个素因子，且$p-1=\prod_{i=1}^{s}q^{\alpha_{i}}$
$\Rightarrow \exist \,B,\forall q^{\alpha_{i}},B>q^{\alpha_{i}}$
令$a=2^{B!}mod \,n$
$\Rightarrow \, a\equiv 2^{B!}mod \, p$
$\Rightarrow \, a\equiv 1\,mod \, p, 即a-1=0\,mod \, p$
$\Rightarrow \,\mbox{可通过求}(a-1,n)\mbox{有一定概率求得n的素因子}$
关键是希望p-1的分解中最大的素因子不是很大，
使得B也可以不是很大，就能得出最后n的素因子
具体算法
举个栗子
Pollard ρ 算法
原理分析
若$x\ne x’$且 $x\equiv x’ mod \,p$ (在Zp中找碰撞，类似于生日悖论)
则可通过求 gcd(x-x’ , n)有一定概率求得n的素因子
我们通过$f(x)=x^2+a$ 产生一系列$x_i$
$x_1\subseteq Z_n,x_i\equiv f(x_{i-1})\,mod \, n$
(若$x_i\equiv x_j\,mod\,p\Rightarrow\,f(x_i)\equiv f(x_j)即x_{i+1}\equiv x_{j+1}\,mod\,p\Rightarrow 产生了一个周期序列，周期为j-1$)
举个栗子
具体算法实现
因为一定$\exist \, t\ge i \,且\, t\equiv\,0\,mod\,(j-i)$ ，所$x_t\equiv x_{2t}\,mod \,p$
所以就有以下算法：
费马分解法
原理分析
若能找到$a^2-b^2\equiv 0\,mod \, n$ 则可以通过求$gcd(a\pm b,n)$有一定概率求得n的素因子
算法具体实现
算法举例
#但是存在一个难点，如何求得平滑数呢？
使用二次筛法
求解离散对数算法
Shanks算法
Shanks算法采用大段小段法（是一种时间-存储折中的算法）
原理分析
算法实现 将计算规模降到了$n^{\frac{1}{2}}$
举个栗子
Pollard ρ离散对数算法
和Pollard ρ大整数分解算法类似，也是通过函数迭代构造碰撞，从而求得离散对数，因而也是一个概率算法
算法分析
算法描述
举个栗子
Pohlig-Hellman算法
有待更新…
指数演算法（Index-Calculus算法）
算法分析
通过计算因子基的离散对数（预计算），来计算所需元素的离散对数，是最高效的一种算法，下面是具体说明：
举个栗子
公钥密码体制
对称密码的一些不足
第一个问题（最大的问题）：密钥的交换
通信双方需要用同一个密钥进行加密和解密，因此就涉及到了密钥的交换，然而交换过程中需要的安全信道又很难保障。
第二个问题：密钥管理
N个用户之间相互通信，每人需要保存N-1个密钥，系统需要完成N×(N-1)/2次密钥的交换。
举个栗子：一个5000用户的网络，要保证每个用户能相互加密通信，总共需要完成12,497,500次密钥交换
第三个问题：抵赖
密钥协商和加密过程是双方行为，无法防止其中一方否认自己曾经发送过某条消息
公钥密码体制的一些介绍
单向陷门函数
如果存在一个单向函数，该函数在具有特定知识（称为陷门）后容易求逆。公钥密码体制就是在这样的单陷门函数下，私钥拥有者就是拥有这样的特定知识。这样的 单陷门函数一般是基于一些数学难题：大整数的分解、离散对数问题等等
一些用途
①用于加密
公钥加密、私钥解密，不需要交换密钥
②数字签名
私钥签名，公钥验证，可防抵赖
RSA算法
RSA算法的简要介绍
这里只做了简要介绍，具体数学原理不过多阐述。
加解密过程的快速实现
平方乘算法
算法分析
算法描述
举个栗子
Montgomery算法
算法分析
结合使用平方乘算法
使用中国剩余定理加速RSA解密
由于解密过程已知p q，所以可以大大降低复杂度
素性检测
简要介绍
由于RSA实现过程中需要用到p q两个素数，所以就需要素性检测算法
其实素性检测问题就是因式分解问题，不过目前不存在多项式时间内能完成的因式分解算法，所以目前使用的素性检测算法大多是概率算法。
理论部分
检测理论一
检测理论二
检测理论三
检测理论四
具体的算法
Solovay-Strassen算法
基于上文的理论二
Miller-Rabin算法
基于上文的理论三
AKS算法
基于上文的理论四
RSA算法的安全性
间接分解模数n
p或q不是大整数(Pollard p-1 算法)
因为RSA其实就是大整数分解问题，这也提醒我们在要使得p q也都是大整数
已知φ(n)
这就很容易求出p q
已知解密指数d
共模攻击
RSA实现是给群组中每个人相同的n，但指数e和d不同的情况下，会出现的一些问题
小加密指数攻击
为了获得更快的速度，而使用较小的加密指数会导致的一些问题
OAEP：最优非对称加密填充（Optimal Asymmetric Encryption Padding）
小解密指数的Wiener攻击
理论基础
举个栗子
实践部分
举个栗子