文章作者：Loking
取前四个质数的测试称为四阶费马测试，PGP采用的就是它。一阶测试误判的概率是 10^-13 ，二阶后是 10^-26 ，作完四阶测试后是 10^-52。而且它绝对不会漏掉一个质数。当然将合数误判为质数的可能性是存在的，这种能通过费马测试的合数被称为Carmichael 数，象 561,1105,1729 等等。它们很稀少，在 10^9 范围内只有 255 个。
下面是几种针对RSA有效的攻击方法，它们实际上对PGP没有效力，因为它们攻击的是加密协议环节上的漏洞，而不是RSA本身的。从这些例子可以看到PGP是如何在实现上堵住这些漏洞的。
● 选择密文攻击
由于RSA密文是通过公开渠道传播的，攻击者可以获取密文。我们假设攻击者为A，密文收件人为T，A得到了发往T的一份密文c，他想不通过分解质因数的方法得到明文。
换句话说，他需要 m = c^d 。
为了恢复 m，他找一个随机数 r ， r < n，当然他有T的公匙(e,n)。他计算：
x=r^e % n （用 T 的公匙加密 r）
y=x*c % n （将临时密文x与c相乘）
t=r^-1 % n
A 知道RSA具有下面的一个特性：
如果 x=r^e % n，那么 r=x^d % n
因此他想办法让T对 y 用T自己的私匙签名（实际上就是把 y 解密了），然后将结果 u=y^d % n 寄回给A。A只要简单地计算：
m = t*u % n
上面结论的推导是这样的：
t*u % n = (r^-1)*(y^d) & n
= (r^-1)*(x^d)(c^d) % n
= (c^d) % n
= m
要防止这种攻击的办法就是不要对外来的随机信息签名，或者只对信息的MD5特征值签名。在这里就很容易明白为什么要强调MD5的单向性了，因为MD5的结果是不能预定的，就是说A难以凑出一份刚好能产生 y 这样的MD5特征值的明文来让T签名。
● 过小的加密指数 e
看起来，e 是一个小数并不降低RSA的安全性。从计算速度考虑，e 越小越好。可是，当明文也是一个很小的数时就会出现问题。例如我们取 e=3 ，而且我们的明文 m 比 n 的三次方根要小，那么密文 c = m^e % n 就会等于 m^3。这样只要对密文开三次方就可以得到明文。
PGP对这个漏洞的处理是在明文上加上一个随机数，这样保证 m > n ，而且缺省的e 值为17，如果不行再用19，23 等等。
● RSA的计时攻击法
这是一种另辟蹊径的方法。是由 Paul Kocher 发表的。大家可以发现，RSA的基本运算是乘方取模，这种运算的特点是耗费时间精确取决于乘方次数。这样如果 A 能够监视到RSA解密的过程，并对它计时，他就能算出d来。细节我就不复述了。我想说的是如何抵御它。Rivest说，最简单的方法就是使RSA在基本运算上花费均等的时间，而与操作数无关。其次在加密前对数据做一个变换（花费恒定时间），在解密端做逆变换，这样总时间就不再依赖于操作数了。
至于PGP根本不用担心计时攻击，因为PGP采用了中国余数理论的方法加速了运算，同时也使耗时与操作数无关。同时计时攻击对攻击者资源的要求太高，实时监视加密过程不是任何人都可能做到的。在这里提出这种攻击是因为：虽然它目前还不实用，但从理论上是一个崭新的思路，值得注意。
● 其他对RSA的攻击法
还有一些对RSA的攻击，象公共模数攻击。它是指几个用户公用一个模数 n ，各自有自己的 e 和 d，在几个用户之间公用 n 会使攻击者能够不用分解 n 而恢复明文。但是PGP是不会在用户之间公用模数的。
最后谈谈RSA密匙长度的问题，多长的密匙是安全的。专家指出，任何预言都是不理智的，就目前的计算机水平用1024-bits的密匙是安全的，2048-bits是绝对安全的。但是他们并不指望这个局面延续到下世纪，他们只是指出：如果RSA象有些人说的那样脆弱，就不可能从1977年一直保持到现在还没有被攻破。
◎ MD5 的安全性问题
MD5是一种在PGP中被用来单向变换用户口令和对信息签名的单向散列算法。
一种单向散列的强度体现在它能把任意的输入随机化到什么程度并且能产生唯一的输出。对单向散列的直接攻击可以分为普通直接攻击和“生日”攻击。
● 对MD5的普通直接攻击
所谓直接攻击又叫野蛮攻击。攻击者为了找到一份和原始明文 m 散列结果相同的明文 m' ，就是 H(m)=H(m') 。普通直接攻击，顾名思义就是穷举可能的明文去产生一个和 H(m) 相同的散列结果。对MD5来说散列结果为128-bits，就是说如果攻击者有一台每秒尝试1,000,000,000条明文的机器需要算约10^22年，同时兴许会同时发现m本身:))。
● 对MD5的生日攻击
生日攻击实际上只是为了找到两条能产生同样散列结果的明文。记得那个有名的概率生日问题吗？在 N 个人中至少有两个人生日相同的概率是多少？所谓生日攻击实际上只是用概率来指导散列冲突的发现，对于MD5来说如果尝试2^64条明文，那么它们之间至少有一对发生冲突的概率就是 50％。仅此而已，对当今的科技能力来说，它也是不可能的。一台上面谈到的机器平均需要运行585年才能找到一对，而且并不能马上变成实际的攻击成果。因为码长和速度的关系，对crypt(3)的生日攻击就成功得多。
● 其他对MD5的攻击
微分攻击被证明对MD5的一次循环是有效的，但对全部4次循环无效。（微分攻击是通过比较分析有特定区别的明文在通过加密后的变化传播情况来攻击加密体系的。）
有一种成功的MD5攻击，不过它是对MD5代码本身做了手脚，是一种crack而不是hack更算不上cryptanalysis了。而且如果你做了PGP发行包的签名校验，是容易发现代码被替换过了的。
● 口令长度和信息论
根据传统信息论，英语的每个8-bits字母的信息熵为1.3bits。如果口令足够长，MD5的结果就会足够随机。对 128-bits 的MD5输出来说，一个长达98个字符的口令将给出一个随机的密匙。
(8/1.3)*(128/8) = 98.46 chars
可是谁会用一个象下面这样长的口令呢？
12345678901234567890123456789012345678901235678901234567890
1234567890123456789012345678
1.3 bits 的信息熵来自于英语语法的规律性这个事实，字母出现概率的不等造成了熵的减小。如果26个拉丁字母出现的概率均等，信息熵将会增至
log(26)/log(2) = 4.7 bits
这样一个随机密匙所需口令长度就减为 27.23 chars 了，如果再加上大小写和几个符号还可以减少。关于选择口令的问题可以参考任何关于安全性的书籍，它们都适用，上面是关于PGP本身特色的部分。
◎ 随机数的安全性问题
PGP使用两个伪随机数发生器（PRNG)，一个是ANSI X9.17发生器，另一个是从用户击键的时间和序列中计算熵值从而引入随机性。ANSI X9.17 PRNG使用IDEA而不是 3DES 来产生随机数种子。Randseed.bin 文件最初是利用用户击键信息产生的，每次加密前后都会引入新的随机数，而且随机数种子本身也是加密存放的。
● ANSI X9.17 PRNG
官方发布的 ANSI X9.17 标准使用的是 Triple DES 作为内核，这个很容易改用IDEA实现。 X9.17 需要randseed.bin中的 24 bytes 的随机数，PGP把其他384 bytes用来存放其他信息。X19.7 工作过程大致如下：
E() = IDEA 加密函数，使用一个可复用的密匙（使用明文产生）。
T = 从 randseed.bin 文件中来的时间
V = 初始化向量
R = 生成的随机密匙（用来加密一次PGP明文）
R = E[E(T) XOR V]
下一次的初始化向量计算如下：
V = E[E(T) XOR R]
● 用户击键引入随机性
这是真正的随机数，没有什么好说的，只是尽量使击键无规则就行。输入的熵越大输出的随机数的熵就越大。
● X9.17 用MD5进行预洗
所谓“洗”就是指象洗牌一样把数据打乱，加密前叫预洗，加密后为下一次加密的准备叫后洗。PGP的日常随机数产生器 X19.7 是用明文的MD5值来预洗的，它基于攻击者不知道明文这样一个假设。如果攻击者知道明文他就没有太大必要去攻击了，当然也有这种可能，不过这只是会削弱一点PRNG的随机性罢了。下面我们将看到还有后洗操作。
● randseed.bin 的后洗操作
后洗操作被认为是更安全的。更多的随机字节被用来重新初始化 randseed.bin 文件，它们被用当前的随机临时PGP密匙来加密。同样如果攻击者知道这个密匙，他就不用攻击 randseed.bin 文件，相反他更关心 randseed.bin 文件当前的状态，因为可能从中获得下次加密的部分信息。因此对 randseed.bin 文件的保护和公匙环及私匙环文件同样重要。当然，如果不是密码专家这些文件都给他也没事。
◎ PGP的密匙和口令的安全性问题
最简单的失密方式就是你让你的口令写在某处，又无法保证除你之外没有其他人能看到。如果别人得到你的口令和你的私匙文件，整个加密体系就无密可言了。
另一个古老的话题就是口令不要太简单，注意PGP用的是“口令” passphase，而不是“密码”password 就是说可以在口令中包含多个词和空格。一个老谋深算的攻击者可能会用一本名言录来寻找你的口令。因此为了得到好记又难猜的口令，你可以生造一些句子或者找些非常生僻的文学篇章中的句子。我个人推荐的办法是采用一句话中的首字母的序列，然后在其中加入几个符号，如“.”，“-”，“;”等，长度最好大于等于8个字符，同时也可夹杂大小写。由于有被人在旁边窥探你的击键动作的可能，最好不用空格键，因为敲它的声音很特殊。同样，需要手指伸得很远的数字键也可不用。例如：
从 “You can't get it without my passphase” 可以得到“yCgi.wyp”这个口令，用穷举法试探出这个口令的可能性微乎其微，因为它用到了大小写字母和符号。平均要试探约 50^8 次才可能成功，以IDEA的速度，这在一般大型计算机上也不是轻而易举的事。因此短的口令只要足够随机，一样很安全，而且输入口令时间越短，被窥探的可能也越小。
公匙的篡改和冒充可说是PGP的最大威胁，在《PGP简介中》我已经讲得比较详细了，要点就是：当你用别人的公匙时，确信它是直接从对方处得来或是由另一个可信的人签名认证过的。确信没有人可以篡改你自己的公匙环文件。保持你对自己密匙环文件的物理控制权，尽量存放在自己的个人电脑里而不是一个远程的分时系统里。备份自己的密匙环文件。
◎ 没有完全删除的文件
一般的操作系统在删除文件时都并没有彻底删除文件的数据，当你加密明文后将明文删除，可是没有从物理上把明文的数据清除。一些有经验的攻击者可能从你的磁盘数据块中恢复明文。当然象碎纸机一样，也有从物理上销毁文件的办法，它们是一些工具软件，如果没有，最简单的办法是用无用的信息将明文文件覆盖。在PGP 后加上 -w 参数也可以达到这一目的。不过即使你覆盖了所有明文曾占用的磁盘空间，仍然会有微小的剩磁留在磁盘上，专用的设备可以恢复这些数据，只是一般人没有这个条件。
对于你使用的密匙环文件同样存在这个问题，特别是私匙环文件，直接关系到你的私匙的安全。因此除了你专用的个人电脑，最好不要将密匙环拷入其他机器，让它们留在软盘上或许是个安全的办法。
◎ 物理安全性
这是PGP所不能赋予你的。如果政府要调查你的话，它蛮可以直接去物理侵犯你的隐私，就象在水门事件中一样。而且这种攻击比密码学分析要便宜得多。PGP无法在一个不保密的环境中保护你的未加密的明文。当然物理安全性也包括对PGP数据的物理安全保护象防火、防水、防雷等等，可是这都不如防人来得难办。
◎ 多用户系统下的泄密
PGP最初是为MS-DOS设计的，它假设本身在用户的直接物理控制下。可是随着PGP的普及，多用户系统上也出现了PGP，这样暴露明文和密匙或口令的可能就增大了。例如：
如果你在Unix系统下在PGP的命令行中使用自己的口令，其他用户将能用ps命令直接看到它。同样的问题在连上局域网的MS-DOS机器上也有。我并不是说在Unix上就不能用PGP，有人将Unix系统装在笔记本电脑上，你当然可以用PGP而不用担心其他用户。多用户系统也有安全的，它们禁得起所有入侵者所能获得的手段的攻击，或者是它的用户都是可以信赖的，要不就是根本没有感兴趣的入侵者。正如下面将要谈到的现实的PGP攻击中谈到的，在多用户系统中泄密的风险要大得多。对此PGP作者的建议是：尽量在一个孤立的单用户系统里使用PGP，而且保证系统处于你的直接物理控制之下。
◎ PGP的时间标戳可靠性
PGP签名上的时间标戳是不可信的，因为任何想伪造一个“错误”的时戳的人都可以通过修改系统时间达到目的。而在商业上又有这种利用PGP签名的时间来确认责任的需要，这样第三方的时间公证体系就被建立了。很明显，只要公证方在邮件上签上标准的时间，就解决了这个问题。实际上这个问题对于手写的签名也存在，签字时需要一个公证人，用以证明签名的时间，数字签名也一样。PGP作者设想的模式是让第三方提供公证服务，服务器对每个送来的签名自动加上自己的签名后发回，同时留下一份记录，这份记录是公开的，需要仲裁的人可以去查阅。
◎ 流量分析
虽然攻击者无法阅读密文的真实内容，但他至少可以通过观察邮件从哪儿来、到哪儿去、邮件大小以及邮件发送的时间等等而获得一些有用的信息，就象他可以查阅你的长途电话费单，但是他不知道你谈话的内容一样。这就叫流量分析。单独靠PGP是无法阻止流量分析的，借助一些网络通讯协议可以防止这些信息的暴露，甚至可以采用另一些加密通讯体系的协助。
◎ 现实的PGP攻击
上面所说的都是一些对一般攻击者不可能或者太费事的攻击方法。实际上有一些“可行的”PGP攻击，它们不是攻击PGP密码体系本身（刚才的论述证明它是牢固的），而是PGP的实现系统。
先看被动攻击：
● 击键窥探
一种非常有效的被动攻击方法；简单地说就是记录用户的击键从中获得口令。攻击者通过键盘记录器窥探用户的击键序列，具体方法因不同系统而异。在DOS下的PGP实现在这方面是最脆弱的，而且它拥有最多的键盘记录器程序。而且攻击者甚至可以从网络上远程启动和停止记录器，在DOS下有些引导区病毒也可以完成这一工作。目前已经出现了至少一种Windows下的记录器，这就对基于Windows的PGP外壳产生了威胁。对UNIX环境下的键盘记录有点复杂，因为需要root权限，除非被攻击者是在X-Windows环境下输入口令的，X-Windows下的记录器不用root权限。
防止这种攻击，一句话，对工作环境要仔细检查，同时作好私匙环文件的保存。
● 电磁泄露窥探
这很好懂，任何计算机设备尤其是显示器都有电磁泄露，通过合适的设备可以收到目标显示器上的信息，那么你的明文显示时就无密可言了。我这里有一个 FBI通过类似装置监听到一个间谍的显示器和键盘信号的案例：他们通过偷偷设置在嫌疑犯计算机里的发射器，远程接收信号，然后通过NSA专用的FFT芯片去除噪音，完成了取证工作。射频信号大约22MHz，在接收端加上 27KHz 的水平同步信号和 59.94 Hz 的垂直同步信号就可以得到清晰的图象。至于键盘用的是串行单片机通讯接口，信号更容易稳定。
加装一个射频信号干扰器可以有效防止显示器信号泄露。键盘信号传不远，只要没人在你计算机里安“耳朵”就不怕泄露。
● 内存空间窥探
在UNIX这样的多用户系统中，只要有合适的权限谁都可以检查机器的物理内存。和分解一个巨大的合数相比，打开/dev/kmem这个系统虚存交换文件，找到用户的页面，直接读出e,d来不是省心得多吗？
● 磁盘缓存窥探
在Windows这样的多任务操作系统中，系统有把内存中的内容交换到磁盘的习惯，而且这些交换文件是对用户透明的。更坏事的是，这些内容并不会很快被清除，有可能在磁盘上保留很久。如果在网络环境中，可能连用户自己都感觉不到，就被人偷走了这些信息。
● 报文嗅探
在网络环境下，信息是以报文的形式在线路中传输的。如果你是通过网络远程使用PGP，那么就有可能被人从报文传输途中监听到。如果信息是以明文的形式存放在报文中你的口令也就被攻击者知道了。
使用一些加密联机的通讯程序，象 SSH，DESlogin 或者干脆使用有加密性能的网络协议栈（点到点或端到端），可以防止网络嗅探的攻击。因为嗅探者要处理大量的信息，如果不是明文，他们一般没有兴趣去研究。
再看看主动攻击：
● 特洛伊木马
木马是个古老的计谋，关于特洛伊木马应该所有人都不陌生。我不想给它下个定义。
下面是一个虚拟的现代PGP木马：
一些精英程序员开发了一个崭新的PGP的Windows外壳。所有新手都FTP到了一份拷贝。它工作得太棒了，有各种按钮和滚动条，甚至它还提供了一堆WAV文件，还支持 SoundBlaster AWE 32 的音效，因此你可以一边加密文件一边欣赏着 16 位CD音质的音响。它占用很少的内存，编程精练，功能强大，而且它还能截获操作系统的中断，从而阻止它把重要信息交换到磁盘去而泄密。
了不起吧？可问题在于，这个程序里有那么几行恶意布置的代码记录了你的口令，并且当它发现机器上装了一个Modem，它会向Modem发出一条atm0命令（关闭Modem的蜂鸣器），然后向天知道什么地方拨号并且传出了你的口令.
