密码算法、协议分析攻击 对称密码算法分析 非对称密码算法分析 密钥协商协议分析攻击 哈希函数分析攻击主要内容主要内容 Ciphertext-only attack（唯密文攻击）•deduce the decryption key or plaintext by only observing ciphertext. Known-plaintext attack（已知明文攻击）•using a quantity of plaintext and corresponding ciphertext.Chosen-plaintext attack（选择明文攻击）•chooses plaintext and is then given corresponding ciphertext. Adaptive chosen-plaintext attack（自适应选择明文攻击）•chosen-plaintext attack where the choice of plaintext may depend on the ciphertext received from previous requests.Chosen-ciphertext attack（选择密文攻击）•selects the ciphertext and is then given the corresponding plaintext.Adaptive chosen-ciphertext attack（自适应选择密文攻击）•chosen-ciphertext attack where the choice of ciphertext may depend on the plaintext received from previous requests.密码分析攻击简单分类 方法二：差分密码分析Differential Cryptanalysis•历史 1990年，以色列密码学家Murphy、Biham和Shamir首次提出用差分密码分析攻击分组密码和散列函数，是第一种可以以少于255的复杂性对DES进行破译的方法。
Differential Cryptanalysis compares two related pairs of encryptions.•至今最有效的攻击迭代密码的方法•差分密码分析攻击方法 with a known difference in the input, searching for a known difference in output when same subkeys are used.两个报文的异或Δm=m⊕m’，中间过程有Δmi=mi⊕mi’，则以选择明文攻击为例 差分密码分析：基本思想差分密码分析：基本思想通过分析明文对的差值对密文对的差值影响来恢复某些密钥比特未破译16轮DES破译轮数低的DES很有效利用差分攻击来破译DES必须要收集到2^47个明文及其相对应的密文，从而使计算复杂度从暴力破解的2^56显著地下降到了2^47 8 rounds: 2^14 chosen plaintexts12 rounds: 2^31 chosen plaintexts16 rounds: 2^47 chosen plaintexts推广方法：截断差分密码分析、高阶差分密码分析、不可能差分密码分析等 差分密码分析：攻击差分密码分析：攻击DES 或者是在某个集合中，通过多组明密文对即可恢复出密钥 首先说明：1. 对于DES的分析，可忽略初始置换IP和IP-1。
2. 对DES限制到n轮（n<=16）3. 以L0R0为明文，且以LnRn作为n轮DES的密文4. 对两个明文L0R0和L0*R0*，规定它们的异或值为L0´R0 ´ =L0R0 L0*R0*，整个讨论都使用撇号（ ´）表示两个比特串的异或值定义1：设Sj是一个特定的S盒（1<=j<=8)，考虑长度为6的比特串的一个有序对（Bj,Bj*）,我们说Sj的输入异或是Bj Bj*, 输出异或是Sj(Bj) Sj(Bj*)注：输入异或是长度为注：输入异或是长度为6的比特串，输出异或是长度的比特串，输出异或是长度为为4的比特串的比特串 定义2：对任何一个Bj´(Z2)6= {a0,a1,a2,a3,a4,a5|aj∈ {0,1}}，定义集合△(Bj´)是由输入异或为Bj´的有序对(Bj,Bj*)组成注注：1*. 对比特串Bj´来说，集合△ (Bj´)包含26=64个有序对元素有 △ (Bj´)={(Bj,Bj Bj´)| Bj ∈(Z2)6} 2*. 对△ (Bj´)中的每一对，我们能计算出Sj的输出异或，同时用表列出结果的分布 有64个输入异或，它们经Sj的输出分布在24=16种可能值之中，这些分布的非均匀性，就是攻击就是攻击DES的基础。
的基础 3*. 表示一个S盒的所有可能对的输入异或和输出异或分布的表称为该S盒的差分分布表若考虑第一个S盒S1，输入异或为B1´=110100, 那么： △ (B1´)= △(110100)={(000000,110100), (000001, 110101), …., (111111, 001011)}对集合△ (B1´)中的每一对，计算S1盒的输出异或 例如 S1(000000)=E16=1110 S1(110100)=916=1001所以(000000,110100)的输出异或是0111计算△ (B1´)= △ (110100)= △（34x）中所有64对的输出异或，得输出异或分布表：+ 0个 8个 16个 6个 2个 0个 0个 12个1000 1001 1010 1011 1100 1101 1110 1111 6个 0个 0个 0个 0个 8个 0个 6个0000 0001 0010 0011 0100 0101 0110 0111 表一 注意！16个可能输出异或中，仅有8种出现。
它们的分布是不均匀的为描述这类分布如何产生的，先表述一些进一步的概念 表二 定义3：对长度为6的比特串Bj´和长度为4的比特串Cj´ (1<=j<=8), 定义 INj(Bj´,Cj´)={Bj（Z2）6|Sj(Bj) Sj(Bj Bj´)=Cj´} Nj(Bj´,Cj´)=|INj(Bj´,Cj´)|注：1*. 这里Nj(Bj´,Cj´)用来表示输入对异或值为Bj´的数目，这些输入对经过特定S盒的Sj输出异或值均为Cj´ 2*.例子1中的输出异或分布表表示N1（110100，C1´）(其中C1´ (Z2)4)，表示对S盒S1来说，它的输入异或为（110100）且相应的输出异或为C1´的输入对数目分布情况 3*. 集合IN1（110100，C1´）将输入异或为（110100）的所有2*中的数目列举出来，见下页： 表三 考虑一般的情况：对于DES的8个S盒的每一个盒有64种可能的输入异或，于是可算出有512个分布回忆DES：知在第i轮中S盒的输入为B=E J，其中E=E（Ri-1）是Ri-1的扩展，J=Ki是由第i轮的密钥比特组成现在对所有8个S盒的输入异或计算如下： B´ =B B*=(E J) (E* J)= E E*=E´由此可见，输入异或不依赖于密钥比特J. 这也说明E´=B´将B，B*，E，E*和J，J*均写成8个6比特串的并： B=B1B2B3B4B5B6B7B8 ；B*=B*1B*2B*3B*4B*5B*6B*7B*8 E=E1E2E3E4E5E6E7E8； E*=E*1E*2E*3E*4E*5E*6E*7E*8 J=J1J2J3J4J5J6J7J8 ； J*=J*1J*2J*3J*4J*5J*6J*7J*8假设我们知道Ej和Ej*的值（对某一个j,1<= j<=8）和Sj的输出异或值Cj ´=Sj(Bj) Sj(Bj*), 那么必有 Ej Jj=BjINj(Bj ´,Cj ´)=INj(Ej ´,Cj ´)， Bj ´=Ej ´=Ej Ej* 我们的目的是要破译密钥J的部分比特串Jj。
定义测试集合Testj定义4（Testj）:设Ej和Ej*是长度为6的比特串，Cj´是长度为4的比特串，定义 Testj(Ej,Ej*,Cj´)={Bj Ej =Jj |Bj∈INj(Ej´,Cj´)}这里Bj Ej 是Jj的形式，Ej是固定的,Ej´=Bj ´=Ej Ej*我们有定理1：假设Ej和Ej*是S盒Sj的两个输入，Sj的输出异或为Cj ´，记Ej ´=Ej Ej* ，那么密钥比特Jj出现在集合Testj(Ej,Ej*,Cj ´)之中注：在集合Testj(Ej,Ej*,Cj ´)中， Jj的正确值一定是Nj(Ej ´,Cj ´)or Nj(Bj ´,Cj ´)个可能值中的一个 例子2：假设E1=000001，E1*=110101和C1 =1101，因为N1（110100，1101）=8，（由表一or表二），可知集合Test1(000001，110101，1101）中，刚好有8个比特串：可从表三中得到： IN1（110100，1101）={000110，010000，010110，011100，100010，100100，101000，110010}分别计算它们与E1=000001的异或得： Test1(000001,110101,1101)={000111,010001,0101111,011101,100011,100101,101001,110011}如果有两个这样的三元组E1，E1*，C1 ，那么就可得到J1中密钥比特可能值的第2个集合Test1(2)(E1,E1*,C1)。
易见密钥比特Jj∈Test1∩Test1 (2) !! 自然这样的三元组如果更多些，定出Jj是肯定的关于这方面的计算，可想出若干技巧 攻攻击3轮DES Li=Ri-1Ri=Li-1 f(Ri-1,Ki)R1=L0 f(R0,K1)R2=L1 f(R1,K2)R3=L2 f(R2,K3)明文P(64bits)FFF+L0++密文R0K1K2K3L1=R0L2=R1L3=R23轮轮DES图图ABC DES的的F函数函数输入32比特E48bitsE1|E2|E3|E4|E5|E6|E7|E8子密钥J1|J2|J3|J4|J5|J6|J7|J8+ BB1 B2 B3 B4 B5 B6 B7 B8S1S2S3S4S5S6S7S8C1 C2 C3 C4 C5 C6 C7 C8POutput(32bits) 我们对3轮作选择明文攻击用明文对和相应的密文对开始我们的分析：明文对为：L0R0; L0*R0*密文对为：L3R3; L3*R3*。
有表达式： R3=L2 f(R2,K3)=R1 f(R2,K3) =L0 f(R0,K1) f(R2,K3)R3*可用类似的方法得到： R3*=L0* f(R0*,K1) f(R2*,K3), 于是有 R3´=L0´ f(R0,K1) f(R0*,K1) f(R2,K3) f(R2*,K3) 假设选择了明文，使R0=R0*,此时R0´=00…0则f(R0,K)=f(R0*,K)，所以 R3´=L0´ f(R2,K3) f(R2*,K3)由于R3´可从两个密文R3,R3*计算出，可知R3´和L0´已知有： f(R2,K3) f(R2*,K3)=R3´ L0´ 知f(R2,K3)=P(C) 和f(R2*,K3)=P(C*),其中C和C*分别表示8个S盒的两个输出而P是固定的，为公开已知的置换，因此 P(C) P(C*)=P(C C*)=R3´ L0´,由此可知 C´=C C*=P-1(R3´ L0´)….为3轮中8个S盒的两个输出异或另外，R2=L3和R2*=L3*是已知的（它们是密文的一部分），因此，可用公开已知的扩展函数E计算E=E(R2)=E(L3)和E*=E(R2*)=E(L3*)对第三轮说来，它们是S盒的输入。
于是可由E，E*和C象前面的例子那样对J1，J2，J3，J4，J5，J6，J7，J8中密钥比特可能值，着手构造集合Test1,Test2,…, Test8由它们来确定第三轮密钥K3中的48bits56bits密钥中剩下的8比特可通过穷举28=256种可能来确定 3轮轮DES的差分攻击模式：的差分攻击模式：输入：L0R0,L0*R0*,L3R3和L3*R3*，其中R0=R0*1.计算C =P-1(R3 L0 )2.计算E=E(L3)和E* =E(L3*) 3. For j=1 to 8 do 计算Testj(Ej,Ej*,Cj )例子3我们有如下三组明密文对，并有固定的异或值用相同的密钥进行加密为简单用16进制表示.明文密文748502CD3845109703C70306D8A09F1038747564 3845109778560A0960E6D4CB48691102 6ACDFF3145FA28BE5ADC730375BD31F6ACDFF31134F7915AC253457357418DA013FEC86D8A31B2F28BBC5CF12549847 013FEC860F317AC2B23CB944 对第一组，可计算S盒的输入（对第三轮），它们是 E=E(L3)=0000000001111110000011101 00000000110100000001100E*=E(L3*)=10111111000000101010110000 0001010100000001010010还可算出S盒的输出异或为：C=C C*=P-1(R3 L0 )=10010110010111010101101100111对第二组，第二组给出相同的计算，结果（略）。
我们给出八个计数器阵列，每个阵列为16*4这样按书写方式排有64个位置：0,1,2,…,63在第一组中，我们有E1 =101111和C1 =1001,集合IN1(101111,1001)={000000,000111,101000,101111} 因为E1=000000，E1*=101111，有J1∈Test1(E1，E1* ， C1 ）=Test1（000000,101111,1001)={ 000000, 000111,101000,101111}将其中6bits串用2进制数表示成对应J1阵列中的位置数0,7,40,47对应于{000000,000111,101000,101111}, 相当于在阵列表的空位的相应位置增值1 J1 对三组算得的三个集合Test1(1),Test1(2),Test1(3)它们中的元素对应的数增值J1位置处的1个单位数于是算得J1=47=101111，类似地方法定出J2=000101，J3=010011，J4=0000000，J5=011000，J6=000111，J7=000111，J8=110001注：1*.差分攻击技术还可用于6轮DES，对8轮的DES需214个组选择明文。
现在对16轮DES也是相当有效的2*. 对其它体制的攻击，例Feal,LOKI,REDOC-II，也是有效的 是1993年提出的另一种统计攻击，基于找到DES中进行变换的线性近似，可以在有247个已知明文的情况下破译DES密钥基本思想•一种已知明文攻击方法•基本思想是通过寻找一个给定密码算法的有效线性近似表达式来破译密码算法•可用247个已知明文破译16轮的DES•某些情况下还能够进行唯密文攻击方法三：方法三：线性密性密码分析分析Linear Cryptanalysis 差分密码分析、线性密码分析技术改善了破译速度，降低了破译计算复杂度，但仍然不够理想新一代密码分析技术：基于物理特性的分析技术•电压分析技术•电磁辐射分析技术•时间分析技术•高阶差分分析技术•汉明差分分析技术例子：智能卡加密的能量分析、定时攻击：利用半导体逻辑电路和密码器件的性能特征，通过检测器件的电子活动，运用先进的物理统计方法确定器件上的秘密信息，如密钥和个人身份信息等方法四：方法四：边界信道攻界信道攻击 能量分析能量分析Encryption/DecryptionSecret key KinputoutputPowerHave access to power supply? Power AnalysisDifference caused by jump instruction 参考书籍：分组密码的攻击方法与实例分析，李超，科学出版社，2010.5 在公钥密码体制中，攻击者拥有公钥，可以随便选择明在公钥密码体制中，攻击者拥有公钥，可以随便选择明文进行加密，攻击者还有机会获得密文，而且还可能利文进行加密，攻击者还有机会获得密文，而且还可能利用各种途径来获得解密，为此，公钥密码体制应该不会用各种途径来获得解密，为此，公钥密码体制应该不会泄露其他密文的的明文信息，这就要求该密码体制能抗泄露其他密文的的明文信息，这就要求该密码体制能抗选择密文攻击选择密文攻击抗选择密文攻击密码体制是一种安全性很高的体制。
现抗选择密文攻击密码体制是一种安全性很高的体制现在它已是被密码学家们普遍接受的概念，研究表明，利在它已是被密码学家们普遍接受的概念，研究表明，利用抗选择密文攻击密码体制，可以设计许多安全强度很用抗选择密文攻击密码体制，可以设计许多安全强度很高的重要的密码协议高的重要的密码协议•密钥传输，密钥交换，公平交换协议等等密钥传输，密钥交换，公平交换协议等等• Bellare和和Rogaway提出的提出的OAEP（（1994）体制就成为）体制就成为SET协议的新的加密标准协议的新的加密标准•抗选择密文攻击是当今公钥加密侯选标准的最重要的要求之抗选择密文攻击是当今公钥加密侯选标准的最重要的要求之一，一，2004年的最新的几个候选标准的原型就是几个重要的抗年的最新的几个候选标准的原型就是几个重要的抗选择密文攻击公钥加密密码方案选择密文攻击公钥加密密码方案公钥密码算法分析公钥密码算法分析 二二公钥密码体制按照可能的攻击目标，可以分为：公钥密码体制按照可能的攻击目标，可以分为：单向性（单向性（OWOW）安全：由密文不能恢复相应的明文）安全：由密文不能恢复相应的明文不可区分性（不可区分性（INDIND）安全：对已知给定的的两个明文，加）安全：对已知给定的的两个明文，加密者随机的选择其中一个进行加密，攻击者无法从密文密者随机的选择其中一个进行加密，攻击者无法从密文中知道是对哪个明文的加密中知道是对哪个明文的加密非延展性（非延展性（NMNM）安全：攻击者无法构造与已给密文相关）安全：攻击者无法构造与已给密文相关的新密文的新密文以上安全性概念依次加强：以上安全性概念依次加强：NMNM比比INDIND强，强，INDIND比比OWOW强强 不可区分性不可区分性(IND)(IND)AttackerChallengerM0, M1b’{0,1}Attacker wins if b=b’C=E(Mb) bR{0,1}ChallengeDecryption oracleC 按照可能的攻击模型可分为：按照可能的攻击模型可分为：选择明文（CPA）攻击：攻击者可以先适应性选择明文，获得相应的密文非适应性选择密文（CCA1）攻击：攻击者除了可以适应性选择明文攻击外，在给定Challenge密文前，还可以选择密文获得相应的解密适应性选择密文（CCA2）攻击：攻击者的唯一限制就是不可以直接用Challenge密文获得相应的明文，但还可以在给定Challenge密文后，选择密文获得相应的解密同时考虑攻击目标和攻击模型，可以获得不同的安全，其中最重要的是IND-CCA2和NM-CCA2安全，而二者被证明是等价的，所以加密中通常所说的选择密文安全是指IND-CCA2安全 方法一：强力攻击（密钥空间穷搜索），不可能，密钥长，以RSA为例：至少1024比特64位密钥，有效密钥长度为56-bit 密钥有256 = 72,057,584,037,927,936 ≈ 7.2亿亿之多 那么1024呢？2048？？？强力搜索( brute force search ) 到21世纪的今天也非常困难 方法二：加密方式弱点攻击，仍然以RSA为例RSA 直接明文加密方式public key: (N,e)Encrypt: C = Me (mod N)private key: d Decrypt: Cd = M (mod N) (M ZN* )不安全的加密模式 - RSA陷门置换不再成为加密系统 - 不满足安全的基本定义 RSA 直接明文加密方式的简单攻击直接明文加密方式的简单攻击Session-key K ：64 bits. View K {0,…,264}中间窃听者: C = Ke (mod N) . 假设 K = K1 K2 where K1, K2 < 234 . (prob. 20%)Then: C/K1e = K2e (mod N)构建表格: C/1e, C/2e, C/3e, …, C/234e . time: 234For K2 = 0,…, 234 test if K2e is in table. time: 23434攻击复杂度: 240 << 264WebBrowserWebServerCLIENT HELLOSERVER HELLO (e,N)dC=RSA(K)Randomsession-key K 通用通用 RSA 加密方式加密方式不再直接对明文进行加密 RSA in practice:问题:•如何进行预处理?•Can we argue about security of resulting system?msgPreprocessingciphertextRSA PKCS1 V1.5PKCS1 mode 2:(加密模式)预处理后的结果进行RSA加密在web servers and browsers中广泛使用安全性分析不够全面02random padFFmsg1024 bits16 bits 针对针对PKCS1PKCS1的攻击的攻击Bleichenbacher 98. 选择密文攻击（Chosen-ciphertext attack）PKCS1 used in SSL:attacker can test if 16 MSBs of plaintext = ’02’.攻击: 用下述方法进行密文C的解密:•选取 r ZN 计算 C’ = reC = (r PKCS1(M))e.•将 C’发送至 web server 并且等待返回Bleichenbacher, D. "Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS#1", in H. Krawczyk (editor), Advances in Cryptology -CRYPTO '98 Proceedings, Lecture Notes in Computer Science 1462 (1998), Springer-Verlag, pp. 1-12AttackerWebServerd是否为PKCS1?ciphertextC=CYes: continueNo: error02 PKCS1 V2.0 - OAEPPKCS1 V2.0 - OAEP加入了新的函数功能: OAEP (BR94)结论: RSA 为有效的 trap-door permutation 如果H,G可以看做随机预言机，则 OAEP 符合 CCS实际使用中: 采用SHA-1 or MD5 作为 H 和 G.H+G+Plaintext to encryptwith RSArand.M01 00..0Check padon decryption.Reject CT if invalid.{0,1}n-1 改进的一些改进的一些OAEPOAEPOAEP+: (Shoup’01) 对任意陷门函数F，若，H,G,W 为随机预言机，则 F-OAEP+ 为CCS SAEP+: (B’01) 若H,W为随机预言机，则 RSA-SAEP+ 为CCSRH+G+MW(M,R)RH+MW(M,R) 方法三：弱参数攻击，以RSA为例（一）共模攻击：整个系统使用相同的ｎ，互素的e1和e2。
y1=xe1 y2=xe2 则攻击者知道e1,e2,n,y1,y2 根据扩展的Euclid除法： 存在s,t 使t*e1+s*e2=1 (注意是相等) y1t*y2s=x mod n 方法三：弱参数攻击，以RSA为例（二）低加密指数攻击：使用相同较小的e Y1=x3 mod n1 Y2=x3 mod n2 Y3=x3 mod n3 根据同余性质=> Y=x3 mod (n1*n2*n3) n1,n2,n3一般互素，x3
这个问题在代数学、密码学、计算复杂性理论和量子计算机等领域中均有重要意义 N=pq大整数分解问题：给出两个大素数，很容易就能将它们两个相乘反过来，给出它们的乘积，找出它们的素因子是困难的（计算上可不行） 这就是许多现代密码系统的关键所在如果能够找到解决整数分解问题的快速方法，几个重要的密码系统将会被攻破，包括RSA公钥算法和Blum Blum Shub随机数发生器尽管快速分解是攻破这些系统的方法之一，仍然会有其它的不涉及到分解的方法所以情形完全可能变成这样：整数分解问题仍然是非常困难，这些密码系统却是能够很快攻破有的密码系统则能提供更强的保证：如果这些密码系统被快速破解（即能够以多项式时间复杂度破解），则可以利用破解这些系统的算法来快速地（以多项式时间复杂度）分解整数这样的密码系统包括 Rabin密码系统（RSA的一个变体），以及 Blum Blum Shub 随机数发生器 部分研究成果部分研究成果从目前的资料分析,分解大整数的方法有试除法;费马方法;蒙特卡罗方法;连分数法（勒让德方法）(CFRAC) ; 发现于70年代二次筛法（QS）; 1981年由卡尔帕梅让斯发现。
p±1方法;Pollard在1974年发现椭圆曲线分解(ECM)；1987年由H.Lenstra发现数域筛法（NFS）；1993年由Car Pomerance 发现.量子计算机，美国Peter Shor在1994年提出用量子计算机分解400位十进制的整数需要不到一年的时间 试除法试除法无论素数判定还是因子分解，试除法(Trial Division)都是首先要进行的步骤在试除的策略上有两种不同的选择： - 用足够大的空间来储存试除用的素数因子 - 不耗费大量空间来储存所有需要的素因子，这时需要 一个快速生成素数的子程序 Pollard p-1算法算法 二次筛法（二次筛法（QSQS））用二次筛选法对一个数字 n 进行因数分解，就是要找到两个数字 x 和 y ，它们模 n 之后不相等，并且 x 和 -y 模 n 之后也不相等，但是 x 2 =y 2 (mod n) 如果找到了这两个数字，那么就可以说 ( x+ y) ( x- y) = 0 (mod n) 因此 x+ y 和 x- y 就一定与 n 具有相同的非平凡因数用二次筛选法进行因数分解有赖于是否能够找到一组数字，这组数的因数可以表示为一些预先选择的素数的乘积。
然后用幂向量的形式将这些因数记录下来一旦具备了足够多的向量，就可以构造一个包含线性依赖关系的集合用这种线性依赖关系就可以找到两个平方后模 n 相等的数字为实现这一目标，二次筛选方法使用了一个素数集合，称作因数基（ factor base）然后，搜索出那些可以完全分解成这个因数基中的素数的数字如果因数基中有 k 个素数，那么每一个可分解为因数基中素数的数字就存储为一个 k 维的向量，向量 y 中的第 i 个项表示因数基中第 i 个素数在 y 因数分解结果当中的幂最后进行筛选操作，找出 f( r) = r 2 - n 的那些值，而这些值因数分解的结果完全包含在这个因数基中然后像 Dixon 因数分解法中那样应用高斯消除法，找出是某数的完全平方的一组 f( r) 数域筛法（数域筛法（NFSNFS））QS 与NFS 的主要目标，都是寻找两个整数x与y，使得x2 = y2 (mod N)，其中N 是欲分解的大整数在选取适当的 “因数基底” (factor base) 之後，QS使用二次多项式来选择足够多的多项式值，可由此因数基底完全分解，再解出对应的线性方程组，得到合适的组合成为完全平方数NFS 则必须分别选择整数Z和相应代数整数环Z[α]的的基底基底，，并选择大量整数对并选择大量整数对(a, b)，使得a − bm与a − b α 皆为对应基底的完全分解。
此后在对方程组求解，获得由其中一部分 (a, b) 所组成的集合S，同时构成两个不同代数结果中的完全平方数 尽管数字域筛选（NFS）在启发式分解方面比 QS 快，而 QS 依然是分解 50 至 110 位数字时的首选方法从本质上讲，这两种方法都是基于同样的思想，如因数基、平滑、筛选以及查找依赖关系等概念NFS 是从 QS 所使用的技术发展出来的，而 QS 又对以前的一些算法做了进一步的发展大多数现代的因数分解技术都将所有这些技术组合起来，以期达到最优的性能 如果一个大的，有n个二进制数位长度的数是两个差不多大小相等的素数的乘积，现在还没有很好的算法来以多项式时间复杂度分解它这就意味着没有已知算法可以在O(nk)（k为常数）的时间内分解它但是现在的算法是比O (en)快的换句话说，现在我们已知最好的算法比指数数量级时间要快，比多项式数量级时间要慢已知最好的渐近线运行时间是普通数域筛选法(GNFS)对于平常的计算机，GNFS是我们已知最好的对付n个二进制数位大素数的方法不过，对于量子计算机， Peter Shor 在1994年发现了一种可以用多项式时间来解决这个问题的算法如果大的量子计算机建立起来，这将对密码学有很重要的意义。
这个算法在时间上只需要O(n3)，空间只要O(n)就可以了 构造出这样一个算法只需要2n量子位2001年，第一个7量子位的量子计算机第一个运行这个算法，它分解的数是15 实际工作实际工作最早成功分解RSA-512 的工作由1999 年完成，共有Arjen K. Lenstra等17 位国际密码学者参与2005年，作为公共研究一部分的有663个二进制数位之长的RSA-200已经被一种一般用途的方法所分解2010年，768-bit的RSA大整数被攻破eprint.iacr.org/2010/006.pdf2015？，1024-bit的RSA被攻破？ 方法五：边界信道攻击定时攻击 - 利用测定RSA解密进行的时间来估计解密指数d，然后再精确出d的值故障攻击功耗分析等 协议分析攻击是指利用密码协议（认证、协议分析攻击是指利用密码协议（认证、密钥交换）设计过程所存在的漏洞进行分密钥交换）设计过程所存在的漏洞进行分析攻击的方法析攻击的方法•中间人攻击中间人攻击•重放攻击重放攻击•窃听攻击等窃听攻击等密码协议分析密码协议分析 方法一方法一：中间人攻击（：中间人攻击（Diffie-Hellman））Assumption 1 The Discrete LogarithmDiscrete Logarithm ( (DLDL) ) assumption for group G states that it is hard to compute x given generator g and random group element gx.Assumption 2 The (Computational) Diffie-HellmanDiffie-Hellman ( (DHDH) ) assumption for group G states that it is hard to compute gxy given generator g and random group elements gx, gy.Assumption 3 The Decision Diffie-HellmanDecision Diffie-Hellman ( (DDHDDH) ) assumption for group G states that it is hard to decide whether zxy mod n given generator g and random group elements gx, gy, gz. Diffie-Hellman Diffie-Hellman 密钥交换协议密钥交换协议Suppose two parties, A and B, have agreed upon a group Gn = , where we require n to be prime. The Diffie-Hellman key exchange protocol enables parties A and B to arrive at a shared key K by exchanging messages over a public channel. Key K remains unknown to any eavesdropper.•Party A picks a value xA Zn uniformly at random, and sends yA = gxA to party B. Similarly, party B picks a value xB Zn uniformly at random, and sends yB = gxB to party A.•Upon receipt of yB, party A computes key KAB yBxA . Similarly, party B computes key KBA yAxB .•Clearly, K = KAB = KBA is a shared key for A and B Passive AttacksA passive attacker (or eavesdropper) learns the values yA = gxA and yB = gxB. Under the DL assumption it is infeasible to determine xA and xB from yA and yB. However, this does not guarantee that the value of K = yAxB cannot be determined given just yA and yB. To exclude this possibility we need the DH assumption. A stronger assumption（DDH假设） is needed to ensure that an eavesdropper does not learn any information whatsoever on K. In general, an eavesdropper may learn some partial information on K, while full recovery of K is infeasible. Active Attacks（中间人攻击）（中间人攻击） 经典的经典的Needham-Schroeder 密钥交换协议密钥交换协议 方法二方法二：假冒攻击：假冒攻击 该协议是否安全？该协议是否安全？ 方法三方法三：重放攻击（：重放攻击（Replay）） 哈希哈希/杂凑杂凑/散列函数分析散列函数分析Hash函数广泛应用于加密和数字签名，保护数据安全和验证数据完整。
自Hash函数公布以来就一直收到密码学家的分析与攻击一种Hash函数的告破有以下情况： －函数的单向性被攻破，是最彻底的攻破对给定的明文及散列值，能够以数学计算的方式求出能产生相同散列值的等价明文 －对给定的明文及散列值，能够用随机碰撞的方法找到另一个随机的等价明文 －能够用随机碰撞的方法找到具有相同散列值的两个不同的明文 Hash函数的攻击方法 －Hash函数的一个评价方案是看找到一对碰撞所要花费的代价有多大目前对Hash函数的攻击目标是找到一对或更多的碰撞，已有的攻击方法中有可用于攻击任何Hash的一般方法，如生日生日攻击方法攻击方法；还有一些针对特定Hash方案的特殊方法，如攻击具有分组链结构Hash的中间相遇攻击中间相遇攻击，攻击基于模运算Hash的修修正分组攻击正分组攻击还有差分攻击差分攻击可用来攻击一些分组密码结构的Hash函数，最新出现的ReboundRebound攻击攻击可用来攻击一些特殊的Hash算法等 生日攻击 －生日攻击可用来攻击任何的Hash函数，它没有利用Hash函数的结构或任何弱性质，其攻击只依赖于Hash值的长度这种攻击说明“短的Hash是很不安全的”。
生日攻击源于所谓的生日问题：一个教室里最少要有多少名学生才能使至少两名学生的生日在同一天的概率不小于50%？设H：X->Y是一个Hash函数，X和Y都是有限的，记|X|=m，|Y|=n，在m≥2n时显然至少有n个碰撞，如何找到碰撞？很自然的我们可以选取k个不同的明文x1，x2，…xk∈X,计算yi＝H（xi），1≤i≤k，然后判断是否出现碰撞下面计算这种方法找到碰撞概率的下界，这个下界只与k和n相关，而不依赖于mHash函数攻函数攻击（一）（一） 我们假定对任意y∈Y，|H-1（y）|≈m/n，这是合理的假设，如果原像集个数不是近似相等的，则找到碰撞的概率会增大由原像集个数近似相等且xi随机选择，可将yi＝H（xi） （1≤i≤k）视作Y中的随机元素考虑没有碰撞，即yi（1≤i≤k）各不相同的概率为：因此碰撞的概率 略去－k项有：取 有这表明只要取 个随机明文就能以50%的概率找到碰撞例如散列值为64位，则n＝264，只需选取232（约40亿）个随机明文作Hash就可以50%概率找到碰撞，这在一般的计算机上也只需数分钟的时间因此目前的Hash值长度至少在128位以抵抗生日攻击。
Hash函数攻函数攻击（二）（二）王晓云对MD5的攻击－2005年欧密会上王晓云教授的论文宣布攻破MD4、MD5、sha-0等Hash函数，引起轰动在论文How to Break MD5 and Other Hash Functions中说明了对MD5的攻击－王晓云采用整数模减的差分方法，不同于一般异或的差分，目的是在MD5初始值： 寻找两个1024bits的消息组合（M0，M1）和（M0’，M1’）它们的Hash值相同步骤如下： 第一步：选择两个512bits的消息 和 表示两个消息分组的差异 模减表示第i个字（32bits）不同做一个带两次迭代的差分碰撞： 其中 其中 表示第5,12,15的位置上是非零输入，之所以这样选择是要保证MD5的第三轮和第四轮能以较高的概率产生差分， 还要保证能产生输出差分， 是第一轮迭代后的4个链接值的差分。
随机选择消息 第二步计算差分特征根据差分特征来确定使这些差分特征成立的充分条件第三步消息修正修改消息中的一些比特值使得第二步中的大部分条件满足，分简单明文修改和高级明文修改修正明文能以2-37的概率产生第一次迭代的差分，以2-30的概率产生第二次迭代的差分 重复操作，直到找到第一次迭代的差分选取随机消息M1，作类似操作直到找到第二次迭代的差分由差分出现的概率，可得在第一次迭代中找到差分（M0，M0’）需要239次的MD5操作，在第二次迭代中找到差分（M1，M1’）需要232次的MD5操作 在王晓云的其他论文中对MD4的攻击复杂度不超过28次运算；对HAVAL-128的攻击复杂度为27～29次运算；对SHA-0的攻击复杂度少于239次运算；对SHA-1的攻击复杂度约263 。