Rabin算法的攻击方法

1. 有关Miller-Rabin算法

在《现代密码学-原理与协议》这本书里看到过类似结论的证明. （7.38）

不过这个1/2不是针对1~n-1的整数集，而是针对1~n-1中元素构成的模n的乘法群Zn*，这个群中仅有那些满足gcd(a, n) = 1这个条件的元素a。另外，需假设n若n为合数，则至少有一个证据证明它是合数。

需要一点群论的知识

1. 若G为有限群，假设H含有G的“1”(幺元)，且对于H中任意的a、b恒有ab属于H，则H是G的子群

2. 若H为有限群G的真子群，则|H| <= |G/2|. （| |代表元素数)

证明：

定义Bad为乘法群Zn*中，不是"n为合数"的证据的元素的集合。（即满足 a^(n-1) = 1 mod n）

显然，1 属于 Bad。

若a,b属于Bad, 则 (ab) ^ (n-1) = a^(n-1) * b^(n-1)= 1*1 mod n =1 mod n

所以 ab 也属于 Bad

由 1 可得 (Bad, *)是Zn*的一个子群

而因为若n为合数，则至少有一个1~n-1中的数使a^(n-1) 不等于 1 mod n，因此Bad为Zn*的真子群

再由2可得 Bad中元素数小于等于Zn*元素数的一半

那么，反过来，Zn*中可以成为证据的元素至少占Zn*中全体元素的1/2

维基网络Miller-Rabin的英文词条下面的参考文献中，他们的原始论文里有完整的对于n为奇合数的判定成功概率的完整证明

2. Hello，密码学：第三部分，公钥密码（非对称密码）算法

在 《Hello，密码学：第二部分，对称密码算法》 中讲述了对称密码的概念，以及DES和AES两种经典的对称密码算法原理。既然有对称密码的说法，自然也就有非对称密码，也叫做公钥密码算法。 对称密码和非对称密码两种算法的本质区别在于，加密密钥和解密密钥是否相同 ：

公钥密码产生的初衷就是为了解决 密钥配送 的问题。

Alice 给远方的 Bob 写了一封情意慢慢的信，并使用强悍的 AES-256 进行了加密，但她很快就意识到，光加密内容不行，必须要想一个安全的方法将加密密钥告诉 Bob，如果将密钥也通过网络发送，很可能被技术高手+偷窥癖的 Eve 窃听到。

既要发送密钥，又不能发送密钥，这就是对称密码算法下的“密钥配送问题” 。

解决密钥配送问题可能有这样几种方法：

这种方法比较高效，但有局限性：

与方法一不同，密钥不再由通信个体来保存，而由密钥分配中心（KDC）负责统一的管理和分配。 双方需要加密通信时，由 KDC 生成一个用于本次通信的通信密钥交由双方，通信双方只要与 KDC 事先共享密钥即可 。这样就大大减少密钥的存储和管理问题。

因此，KDC 涉及两类密钥：

领略下 KDC 的过程：

KDC 通过中心化的手段，确实能够有效的解决方法一的密钥管理和分配问题，安全性也还不错。但也存在两个显着的问题：

使用公钥密码，加密密钥和解密密钥不同，只要拥有加密密钥，所有人都能进行加密，但只有拥有解密密钥的人才能进行解密。于是就出现了这个过程：

密钥配送的问题天然被解决了。当然，解密密钥丢失而导致信息泄密，这不属于密钥配送的问题。

下面，再详细看下这个过程。

公钥密码流程的核心，可以用如下四句话来概述：

既然加密密钥是公开的，因此也叫做 “公钥（Public Key）” 。
既然解密密钥是私有的，因此也叫做 “私钥（Private Key） 。

公钥和私钥是一一对应的，称为 “密钥对” ，他们好比相互纠缠的量子对， 彼此之间通过严密的数学计算关系进行关联 ，不能分别单独生成。

在公钥密码体系下，再看看 Alice 如何同 Bob 进行通信。

在公钥密码体系下，通信过程是由 Bob 开始启动的：

过程看起来非常简单，但为什么即使公钥被窃取也没有关系？这就涉及了上文提到的严密的数学计算关系了。如果上一篇文章对称密钥的 DES 和 AES 算法进行概述，下面一节也会对公钥体系的数学原理进行简要说明。

自从 Diffie 和 Hellman 在1976年提出公钥密码的设计思想后，1978年，Ron Rivest、Adi Shamir 和 Reonard Adleman 共同发表了一种公钥密码算法，就是大名鼎鼎的 RSA，这也是当今公钥密码算法事实上的标准。其实，公钥密码算法还包括ElGamal、Rabin、椭圆曲线等多种算法，这一节主要讲述 RSA 算法的基本数学原理。

一堆符号，解释下，E 代表 Encryption，D 代表 Decryption，N 代表 Number。

从公式种能够看出来，RSA的加解密数学公式非常简单（即非常美妙）。 RSA 最复杂的并非加解密运算，而是如何生成密钥对 ，这和对称密钥算法是不太一样的。 而所谓的严密的数学计算关系，就是指 E 和 D 不是随便选择的 。

密钥对的生成，是 RSA 最核心的问题，RSA 的美妙与奥秘也藏在这里面。

1. 求N

求 N 公式：N = p × q

其中， p 和 q 是两个质数 ，而且应该是很大又不是极大的质数。如果太小的话，密码就容易被破解；如果极大的话，计算时间就会很长。比如 512 比特的长度（155 位的十进制数字）就比较合适。

这样的质数是如何找出来的呢？ 需要通过 “伪随机数生成器（PRNG）” 进行生成，然后再判断其是否为质数 。如果不是，就需要重新生成，重新判断。

2. 求L

求 L 公式：L = lcm(p-1, q-1)

lcm 代表 “最小公倍数（least common multiple）” 。注意，L 在加解密时都不需要， 仅出现在生成密钥对的过程中 。

3. 求E

E 要满足两个条件：
1）1 < E < L
2）gcd(E,L) = 1

gcd 代表 “最大公约数（greatest common divisor）” 。gcd(E,L) = 1 就代表 “E 和 L 的最大公约数为1，也就是说， E 和 L 互质 ”。

L 在第二步已经计算出来，而为了找到满足条件的 E， 第二次用到 “伪随机数生成器（PRNG）” ，在 1 和 L 之间生成 E 的候选，判断其是否满足 “gcd(E,L) = 1” 的条件。

经过前三步，已经能够得到密钥对种的 “公钥：{E, N}” 了。

4. 求D

D 要满足两个条件：
1）1 < D < L
2）E × D mod L = 1

只要 D 满足上面的两个条件，使用 {E, N} 进行加密的报文，就能够使用 {D, N} 进行解密。

至此，N、L、E、D 都已经计算出来，再整理一下

模拟实践的过程包括两部分，第一部分是生成密钥对，第二部分是对数据进行加解密。为了方便计算，都使用了较小的数字。

第一部分：生成密钥对

1. 求N
准备两个质数，p = 5，q = 7，N = 5 × 7 = 35

2. 求L
L = lcm(p-1, q-1) = lcm (4, 6) = 12

3. 求E
gcd(E, L) = 1，即 E 和 L 互质，而且 1 < E < L，满足条件的 E 有多个备选：5、7、11，选择最小的 5 即可。于是，公钥 = {E, N} = {5, 35}

4. 求D
E × D mod L = 1，即 5 × D mod 12 = 1，满足条件的 D 也有多个备选：5、17、41，选择 17 作为 D（如果选择 5 恰好公私钥一致了，这样不太直观），于是，私钥 = {D, N} = {17, 35}

至此，我们得到了公私钥对：

第二部分：模拟加解密

明文我们也使用一个比较小的数字 -- 4，利用 RSA 的加密公式：

密文 = 明文 ^ E mod N = 4 ^ 5 mod 35 = 9
明文 = 密文 ^ D mod N = 9 ^ 17 mod 35 = 4

从这个模拟的小例子能够看出，即使我们用了很小的数字，计算的中间结果也是超级大。如果再加上伪随机数生成器生成一个数字，判断其是否为质数等，这个过程想想脑仁儿就疼。还好，现代芯片技术，让计算机有了足够的运算速度。然而，相对于普通的逻辑运算，这类数学运算仍然是相当缓慢的。这也是一些非对称密码卡/套件中，很关键的性能规格就是密钥对的生成速度

公钥密码体系中，用公钥加密，用私钥解密，公钥公开，私钥隐藏。因此：

加密公式为：密文 = 明文 ^ E mod N

破译的过程就是对该公式进行逆运算。由于除了对明文进行幂次运算外， 还加上了“模运算” ，因此在数学上， 该逆运算就不再是简单的对数问题，而是求离散对数问题，目前已经在数学领域达成共识，尚未发现求离散对数的高效算法 。

暴力破解的本质就是逐个尝试。当前主流的 RSA 算法中，使用的 p 和 q 都是 1024 位以上，这样 N 的长度就是 2048 位以上。而 E 和 D 的长度和 N 差不多，因此要找出 D，就需要进行 2048 位以上的暴力破解。即使上文那个简单的例子，算出（ 蒙出 ） “9 ^ D mod 35 = 4” 中的 D 也要好久吧。

因为 E 和 N 是已知的，而 D 和 E 在数学上又紧密相关（通过中间数 L），能否通过一种反向的算法来求解 D 呢？

从这个地方能够看出，p 和 q 是极为关键的，这两个数字不泄密，几乎无法通过公式反向计算出 D。也就是说， 对于 RSA 算法，质数 p 和 q 绝不能被黑客获取，否则等价于交出私钥 。

既然不能靠抢，N = p × q，N是已知的，能不能通过 “质因数分解” 来推导 p 和 q 呢？或者说， 一旦找到一种高效的 “质因数分解” 算法，就能够破解 RSA 算法了 。

幸运的是，这和上述的“离散对数求解”一样，当下在数学上还没有找到这种算法，当然，也无法证明“质因数分解”是否真的是一个困难问题 。因此只能靠硬算，只是当前的算力无法在可现实的时间内完成。 这也是很多人都提到过的，“量子时代来临，当前的加密体系就会崩溃”，从算力的角度看，或许如此吧 。

既不能抢，也不能算，能不能猜呢？也就是通过 “推测 p 和 q 进行破解” 。

p 和 q 是通过 PRNG（伪随机数生成器）生成的，于是，又一个关键因素，就是采用的 伪随机数生成器算法要足够随机 。

随机数对于密码学极为重要，后面会专门写一篇笔记 。

前三种攻击方式，都是基于 “硬碰硬” 的思路，而 “中间人攻击” 则换了一种迂回的思路，不去尝试破解密码算法，而是欺骗通信双方，从而获取明文。具体来说，就是： 主动攻击者 Mallory 混入发送者和接收者之间，面对发送者伪装成接收者，面对接收者伪装成发送者。

这个过程可以重复多次。需要注意的是，中间人攻击方式不仅能够针对 RSA，还可以针对任何公钥密码。能够看到，整个过程中，公钥密码并没有被破译，密码体系也在正常运转，但机密性却出现了问题，即 Alice 和 Bob 之间失去了机密性，却在 Alice 和 Mallory 以及 Mallory 和 Bob 之间保持了机密性。即使公钥密码强度再强大 N 倍也无济于事。也就是说，仅仅依靠密码算法本身，无法防御中间人攻击 。

而能够抵御中间人攻击的，就需要用到密码工具箱的另一种武器 -- 认证 。在下面一篇笔记中，就将涉及这个话题。

好了，以上就是公钥密码的基本知识了。

公钥密码体系能够完美的解决对称密码体系中 “密钥配送” 这个关键问题，但是抛开 “中间人攻击” 问题不谈，公钥密码自己也有个严重的问题：

公钥密码处理速度远远低于对称密码。不仅体现在密钥对的生成上，也体现在加解密运算处理上。

因此，在实际应用场景下，往往会将对称密码和公钥密码的优势相结合，构建一个 “混合密码体系” 。简单来说： 首先用相对高效的对称密码对消息进行加密，保证消息的机密性；然后用公钥密码加密对称密码的密钥，保证密钥的机密性。

下面是混合密码体系的加解密流程图。整个体系分为左右两个部分：左半部分加密会话密钥的过程，右半部分是加密原始消息的过程。原始消息一般较长，使用对称密码算法会比较高效；会话密钥一般比较短（十几个到几十个字节），即使公钥密码算法运算效率较低，对会话密钥的加解密处理也不会非常耗时。

着名的密码软件 PGP、SSL/TLS、视频监控公共联网安全建设规范（GB35114） 等应用，都运用了混合密码系统。

好了，以上就是公钥密码算法的全部内容了，拖更了很久，以后还要更加勤奋一些。

为了避免被傻啦吧唧的审核机器人处理，后面就不再附漂亮姑娘的照片（也是为了你们的健康），改成我的摄影作品，希望不要对收视率产生影响，虽然很多小伙儿就是冲着姑娘来的。

就从喀纳斯之旅开始吧。

3. Miller Rabin算法的优化实现

Miller-Rabin算法最为耗时的步骤在2.2模幂操作和2.3.2 循环。对算法的优化实现主要集中在对这两部分运算的优 化。对模幂操作的优化有两种途径：减少模幂算法中的模乘 操作和优化模乘操作。在求模幂的过程中不能先求幂最后一次求模，这样会产生一个十分巨大的中间结果，造成实际的 不可操作，所以在求模幂的算法中用模乘代替乘法，使得中 间结果的长度不超过模的长度。对模幂算法的优化，我们使 用改进的滑动窗口算法结合Montgomery模乘和模平方算法。表1给出模幂算法的比较。 模幂算法 预先计算 模平方 模乘法 模平方 模乘法 最坏情况 平均情况 平方乘算法滑动窗口类算法 改进的滑动窗口算法 011 02k -32k-1-1 tt-(k-1)≤次数≤t t-(k-1)≤次数≤t t (t/k)-1 (t/k)-1 t/2 t/k(2k-1)/ 2kk≤t/k(2 -1)/ * 模幂算法比较，其中k是窗口大小，根据情况 选择以达到最优，t是指数的二进制位数。 优化的模幂算法描述：输入： x，e=(e tet-1?e1e0)2，其中et=1，k≥1( 窗口大小)输出： xe mod n1、预计算1.1、x1← MontMul(x， R2，n)，x2←MontSqu(x 1， n)1.2、对i 从1 到2k-1-1计算x2i+1←MontMul(x2i-1， x2，n)2、A←R，i ←t3、 当i≥ 0时作下面的操作： 3.1、如果ei=0，A←MontSqu(A ，n)，i← i-13.2、否则找到最长的位串eiei-1?es使得i-s+1≤k并且es=1,计算3.2.1、A <－A2i-s+1 ， (利 用MontSqu函数计算)3.2.2、A <－A*X(ee ...e )2 ，(利 用MontMul函数计算)3.2.3、i ←s-14、A←MontMul(A ，1 ，n)5、返回A其中MontMul(x,y,n) 是Montgomery模乘函数，函数输出 结果为x*y*R-1 mod n，MontSqu(x,n) 是Montgomery模平方函 数，输出结果为x2R-1 mod n。模乘算法如果采用大整数乘法 和除法求模乘，因为涉及耗时的除法操作，所以要相对较 慢，结合大整数乘法和Barrett求模算法可以用2(n2+3n+1) 步 单精度乘法完成。使用Montgomery求模算法结合大整数乘法 算法，可以 在 2n(n+1) 步单精度乘法内完成算法。 Montgomery模平方的操作可以在3n(n+1) /2步单精度乘法内 完成，而Barrett模平方需要(3n(n+3)/2+1) 步单精度乘法。结 合改进的滑动窗口算法和Montgomery类算法，可以得到目前 非特殊情况下的最优的模幂算法。在Miller-Rabin算法的2.3.2循环中的模平方操作我们没有 使用Montgomery模平方算法，因为该算法给出的结果带有R-1这个参数，在2.3.2循环中处理掉这个参数将占整个循环运 行时间中的很大部分，尤其是在循环的控制参数s 相对较小的时候。我们在这里使用大整数平方算法结合Barrett求模算 法，2.3.2的循环最坏情况需要(s-1)(3n(n+3)/2+1)步单精度乘法。

4. C语言 设计并实现一种大素数随机生成方法； 实现一种快速判定任意一个大数是否是素数方法 跪求啊

Rabin -Miller算法是典型的验证一个数字是否为素数的方法。判断素数的方法是Rabin-Miller概率测试，那么他具体的流程是什么呢。假设我们要判断n是不是素数，首先我们必须保证n 是个奇数，那么我们就可以把n 表示为 n = (2^r)*s+1,注意s 也必须是一个奇数。然后我们就要选择一个随机的整数a (1<=a<=n-1)，接下来我们就是要判断 a^s=1 (mod n) 或a^((2^j)*s)= -1（mod n）(0<=j如果任意一式成立，我们就说n通过了测试，但是有可能不是素数也能通过测试。所以我们通常要做多次这样的测试，以确保我们得到的是一个素数。（DDS的标准是要经过50次测试）
采用Rabin-Miller算法进行验算
首先选择一个代测的随机数p，计算b，b是2整除p-1的次数。然后计算m，使得n=1+(2^b)m。
（1） 选择一个小于p的随机数a。
（2） 设j=0且z=a^m mod p
（3） 如果z=1或z=p-1，那麽p通过测试，可能使素数
（4） 如果j>0且z=1, 那麽p不是素数
（5） 设j=j+1。如果j且z<>p-1,设z=z^2 mod p，然后回到(4)。如果z=p-1，那麽p通过测试，可能为素数。
（6） 如果j=b 且z<>p-1，不是素数

#include<iostream.h>
#include<time.h>
#include<stdlib.h>

//随机数产生器
//产生m~n之间的一个随机数
unsigned long random(unsigned long m,unsigned long n)
{
srand((unsigned long)time(NULL));
return(unsigned long)(m+rand()%n);
}
//模幂函数
//返回X^YmodN
long PowMod(long x,long y,long n)
{
long s,t,u;

s=1;t=x;u=y;
while(u){
if(u&1)s=(s*t)%n;
u>>=1;
t=(t*t)%n;
}
return s;
}

//Rabin-Miller素数测试，通过测试返回1，否则返回0。
//n是待测素数。
//注意：通过测试并不一定就是素数，非素数通过测试的概率是1/4

int RabinMillerKnl(unsigned long n)
{
unsigned long b,m,j,v,i;
//先计算出m、j，使得n-1=m*2^j，其中m是正奇数，j是非负整数
m=n-1;
j=0;
while(!(m&1))
{
++j;
m>>=1;
}
//随机取一个b，2<=b<n-1
b=random(2,m);
//计算v=b^mmodn
v=PowMod(b,m,n);
//如果v==1，通过测试
if(v==1)
{
return 1;
}

i=1;
//如果v=n-1，通过测试
while(v!=n-1)
{
//如果i==l，非素数，结束
if(i==j)
{
return 0;
}
//v=v^2modn，i=i+1
v=PowMod(v,2,n);
i++;
}
return 1;
}
intmain()
{
unsigned long p;
int count=0;
cout<<"请输入一个数字"<<endl;
cin>>p;
for(int temp=0;temp<5;temp++)
{
if(RabinMillerKnl(p))
{
count++;
}
else
break;

}

if(count==5)
cout<<"一共通过5次测试，是素数！"<<endl;
else
cout<<"不是素数"<<endl;
return 0;
}

5. Miller Rabin算法的在应用中的考虑

(i)(ii)p k ,1pk , tk 2 4 2k 3 / 2 2 tkfor k 2t 1 / 2 4 2 tk(iii) p 7 k 2 5t k , t201 k15 / 4 27k / 2 2 t12 k 2k / 4 3tfor k / 9(iv) pk , tt k / 4, k1 k15 / 4 2721k / 22t for tk / 4, k 21Miller-Rabin算法的应用主要集中在构建密码安全体系的素数生成模块中，当输入的待测数n是很大(例如： 1024bits)的随机数的时候，算法的误判概率远远小于上面给出的理论 上的误判概率上界。设Pk,t 代表(k=log2 n，t是测试的轮数)在 素数生成算法中应用t轮Miller-Rabin 算法给出错误结果的概 率，则有如上所示的误判概率公式。在一般的密码安全体系中，误判概率小于 (1/2)就可以满足安全需求。表2给出了当p(k,t) ≤ (1/2)80的时候对应的k和t的值。
表2 k,t对应值 k 100 150 200 25 300 350 400 450 550 650 850 1300 t 27 18 15 12 9 8 7 6 5 4 3 2 在基底的选择上，因为以2作为基底可以剔除很大部分 合数，并且对以2为底的模幂的运算很快，所以可以考虑在 应用中固定使用基底2，其它基底随机选择，这样的改进可 以提高算法的运行速度。