第六章 公钥密码学
1 什么是公钥密码体制
钥密码又称为双钥密码、非对称密码，是1976年由Diffie 和Hellman 在其“密码学新方向”一文中提出的，见划时代的文献：
W .Diffie and M.E.Hellman, New Directrions in Cryptography , IEEE Transaction on Information Theory, V .IT-22.No.6, Nov 1976, PP .644-654
单向陷门函数是满足下列条件的函数f ：
(1)给定x ，计算y=f(x)是容易的；
(2)给定y , 计算x 使y=f(x)是困难的。
(所谓计算x=f -1(y)困难是指计算上相当复杂，已无实际意义。)
(3)存在δ，已知δ 时, 对给定的任何y ，若相应的x 存在，则计算x 使y=f(x)是容易的。 注：1*. 仅满足(1)、(2)两条的称为单向函数；第(3)条称为陷门性，δ 称为陷门信息。 2*. 当用陷门函数f 作为加密函数时，可将f 公开，这相当于公开加密密钥。此时加密密钥便称为公开钥，记为Pk 。 f 函数的设计者将δ 保密，用作解密密钥，此时δ 称为秘密钥匙，记为Sk 。由于加密函数是公开的，任何人都可以将信息x 加密成y=f(x)，然后送给函数的设计者（当然可以通过不安全信道传送）；由于设计者拥有Sk ，他自然可以解出x=f-1(y)。
3*.单向陷门函数的第(2)条性质表明窃听者由截获的密文y=f(x)推测x 是不可行的。
2.Diffie-Hellman 密钥交换算法
Diffie 和Hellman 在其里程碑意义的文章中，虽然给出了密码的思想，但是没有给出真正意义上的公钥密码实例，也既没能找出一个真正带陷门的单向函数。然而，他们给出单向函数的实例，并且基于此提出Diffie-Hellman 密钥交换算法。这个算法是基于有限域中计算离散对数的困难性问题之上的：设F 为有限域，g ∈ F 是F 的乘法群F*=F\{0}=生成元。并且对任意正整数x ，计算gx 是容易的；但是已知g 和y 求x 使y= gx，是计算上几乎不可能的。这个问题称为有限域F 上的离散对数问题。公钥密码学中使用最广泛的有限域为素域FP .
对Diffie-Hellman 密钥交换协议描述：Alice 和Bob 协商好一个大素数p ，和大的整数g ，1。p 和g 无须保密，可为网络上的所有用户共享。
对于一个素数q ，如果数值：a mod q，a2 mod q，„„，aq-1 mod q，是各不相同的整数，并且以某种排列方式组成了从1到q-1的所有整数
则称整数a 是素数q 的一个本原元（原根）
当Alice 和Bob 要进行保密通信时，他们可以按如下步骤来做：
由(4)知，Alice 和Bob 已获得了相同的秘密值K 。双方以K 作为加解密钥以传统对称密钥算法进行保密通信。
注：Diffie-Hellman 密钥交换算法拥有美国和加拿大的专利。
3 RSA 公钥算法
RSA 公钥算法是由Rivest,Shamir 和Adleman 在1978年提出来的（见Communitions of the ACM. Vol.21.No.2. Feb. 1978, PP.120-126) 该算法的数学基础是初等数论中的Euler （欧拉) 定理，并建立在大整数因子的困难性之上。
4 RSA 密码体制的实现
于是要求：若使RSA 安全，p 与q 必为足够大的素数，使分析者没有办法在多项式时间内将n 分解出来。建议选择p 和q 大约是100位的十进制素数。 模n 的长度要求至少是 512比特。EDI 攻击标准使用的RSA 算法中规定n 的长度为512至1024比特位之间，但必须是128的倍数。国际数字签名标准ISO/IEC 9796中规定n 的长度位512比特位。 为了抵抗现有的整数分解算法，对RSA 模n 的素因子p 和q 还有如下要求：
(1)|p-q|很大，通常 p 和q 的长度相同；
(2)p-1 和q-1分别含有大素因子p1和q1
(3)P1-1和q1-1分别含有大素因子p2和q2
(4)p+1和q+1分别含有大素因子p3和q3
为了提高加密速度，通常取e 为特定的小整数，如EDI 国际标准中规定 e ＝216＋1，ISO/IEC9796中甚至允许取e ＝3。这时加密速度一般比解密速度快10倍以上。
下面研究加解密算术运算，这个运算主要是模n 的求幂运算。著名的“平方-和-乘法”方法将计算xc(mod n) 的模乘法的数目缩小到至多为2l ，这里的l 是指数c 的二进制表示比特数。若设n 以二进制形式表示有k 比特，即k=[log2n]+1。 由l ≤ k ，这样xc(mod n)能在o(k3)时间内完成。（注意，不难看到，乘法能在o(k2)时间内完成。）
平方－和－乘法算法：
指数c 以二进制形式表示为：
5 攻击RSA
因数分解攻击(Factorization Attack)
选择密文攻击(chosen-Ciphertext attack)
对加密指数的攻击
对解密指数的攻击
明文攻击(plaintext attack)
对模的攻击
执行攻击
◆ 因数分解攻击
(Factorization Attack)
现在有许多种因数分解算法，但是没有一种可以分解带有多项式时间复杂度的大整数。为了安全，目前的RSA 要求n 必须大于300个十进制数位，这就是说模必须最小是1024比特。即使运用现在最大最快的计算机，分解这么大的整数所要花费的时间也是不可想象的。这就表明只要还没有发现更有效的因数分解算法，RSA 就是安全的。
◆ 选择密文攻击
(chosen-Ciphertext attack)
◆ 对加密指数的攻击
为了缩短加密时间，使用小的加密指数e 是非常诱人的。普通的e 值是e = 3(第
二个素数) 。不过有几种针对低加密指数的潜在攻击，在这里我们只作简单的讨论。这些攻击一般不会造成系统的崩溃，不过还是得进行预防。为了阻止这些类型的攻击，我们推荐使用 (或者一个接近这个值的素数) 。
◆ Coppersmith 定理攻击
主低加密指数攻击称为Coppersmith 定理攻击(Coppersmith theorem attack) 。该项定理表明在一个e 阶的mod n多项式f(x)中，如果有一个根小于n1/e，就可以运用一个复杂度为log n 的算法求出这些根。这个定理可以应用
于
的RSA 密码系统。如果e = 3并且在明文当
中只有三分之一的比特是未知的，那么这种算法可以求出明文中所有的比特。
◆ 广播攻击
如果一个实体使用相同的低加密指数给一个接收者的群发送相同的信息，就会
发动广播攻击(broadcast attack)。例如，假设有如下的情节：Alice 要使用相同的公共指数e = 3和模数n1、n2、n3给三个接收者发送相同的信息。
对这些等式运用CRT ，攻击者就可以求出形式为
的等式。
这就表明P3
◆ 相关信息攻击
相关信息攻击(related message attack)是由Franklin Reiter 提出来的，下面我们就简单描述一下这种攻击。Alice 用e = 3加密两个明文P1和P2，然后再把C1和C2发送给Bob 。如果通过一个线性函数把P1和P2联系起来，那么攻击者就可以在一个可行的计算时间内恢复P1和P2。
◆ 短填充攻击
短填充攻击(short pad attack)是由Coppersmith 提出来的，下面我们就简单描述一下这种攻击。Alice 有一条信息M 要发送给Bob 。她先用r1对信息填充，加密的结果是得到了C1，并把C1发送给Bob 。攻击者拦截C1并把它丢掉。Bob 通知Alice 他还没有收到信息，所以Alice 就再次使用r2对信息填充，加密后发送给Bob 。攻击者又拦截了这一信息。攻击者现在有C1和C2，并且她知道C1和C2都是属于相同明文的密文。Coppersmith 证明如果r1和r2都是短的，攻击者也许就能恢复原信息M 。
◆ 对解密指数的攻击
可以对解密指数发动攻击的两种攻击方式：
1. 暴露解密指数攻击(revealed decryption exponent attack)
如果攻击者可以求出解密指数d ，她就可以对当前加密的信息进行解密。不过，到这里攻击并还没有停止。如果攻击者知道d 的值，她就可以运用概率算法(这里不讨论) 来对n 进行因数分解，并求出p 和q 值。因此，如果Bob 只改变了泄露解密指数但是保持模n 相同，因为攻击者有n 的因数分解，所以她就可以对未来的信息进行解密。这就是说，如果Bob 发现解密指数已经泄露，他就要有新的p 和q 的值还要计算出n ，并创建所有新的公钥和私钥。
2. 低解密指数攻击(low decryption exponent attack)。
Bob 也许会想到，运用一个小的私钥d 就会加快解密的过程。Wiener
表示如果
，一种基于连分数(一个数论当中的问题) 的特殊攻击类型就可以危
害RSA 的安全。要发生这样的事情，必须要有q
在RSA 中，我们推荐用来防止低加密指数攻击。
◆ 明文攻击(plaintext attack)
攻击者已经知道了有关明文的一些内容。这一特征也许就会引起一些针对明文的攻击。在这一部分中我们提到三种攻击：短信息攻击、循环攻击和公开攻击。
◆ 短信息攻击(short message attack)
在短信息攻击中，如果攻击者知道可能的明文组，那么她除了知道明文是密文的转换之外，还知道一些别的信息。攻击者可以对所有可能的信息进行加密，直到结果和所拦截的信息相同。例如，如果知道Alice 正在发送一个4位数的数字，攻击者就可以轻易地试验0000~9999的明文数字，来发现明文。为此，短信息必须要在开头和结尾用随机比特进行填充，来阻止这类攻击。
◆ 循环攻击(cycling attack)
循环攻击是基于这样一个事实，那就是密文是明文的一个置换，密文的连续加密最终结果就是明文。也就是说，如果对所拦截的密文C 连续加密，攻击者最终就得到了明文。不过，攻击者不知道明文究竟是什么，所以她就不知道什么时候要停止加密。她就要往前多走一步。这样如果她再次得到了密文C ，她只要返回一步就得到了明文。
◆ 公开信息攻击(unconcealed message attack)
是一种基于明文和密文之间置换关系的攻击。一则公开信息就是自身加密(不被隐藏) 的信息。已经证明总有一些信息是自身加密的。因为通常加密指数是一个奇数，有一些明文如P = 0和P = 1，都是自身加密的。如果加密指数是仔细选出来的，那就会有更多的这种信息被忽略。如果算出来的密文和明文相同，加密程序总要在提交密文之前阻止并拒绝明文。
◆ 同模攻击(common modulus attack)
如果一个组织使用一个共同的模n ，那就有可能发动同模攻击。例如，一个组织中的人也许会让一个可信机构选出p 和q ，计算出n=pq，并为每一个实体创建一对指数(ei, di) 。现在假定Alice 要发送一则信息给Bob 。发给Bob
的密文是
Bob
用他的私密指数来对他的信息。解密。问题是如果攻击者是该组织中的一个成员，并且像我们在“低解密指数攻击”那一部分中学过的那样，她也得到了分配的指数对，这样她也就可以对信息解密。运用她自己的指数对(eE和dE) ，攻击者可以发动一个概率攻击来分解n 并得到Bob 的dB 。为了阻止这种类型的攻击，模必须不是共享的。每一个实体都要计算她或他的模。
◆ 执行攻击
前面所述的攻击都基于RSA 的基本的结构。正像Dan Boneh所论述的那样，有几种针对RSA 执行的攻击。
时序攻击
能量攻击
◆ 时序攻击(timing attack)
Paul Kocher 精密地论证了这种纯密文攻击，我们称为时序攻击。这种攻击基于快速指数算法(前面讨论过) 。如果私密指数d 中的相关比特是0的话，这种算法只应用平方；如果相关的位是1，这种算法就既应用平方也应用乘法。也就是说，如果相关的比特是1，完成每一个迭代需要的时序会更长。这种时序上的不同就可以使攻击者逐一找出d 中的比特值。
有两种方法可以阻止时序攻击：
(1) 把随机延迟加到指数上使每一个指数所消耗的时间相同。
(2) Rivest引入了盲签名(blinding)。这个概念就是在解密前用一个随机数乘以密文。
◆ 能量攻击(power attack)
能量攻击和时序攻击相似。Kocher 表示，如果攻击者能够准确测量出解密过程中所消耗的能量，她就可以发动一个基于时序攻击原则的能量攻击。涉及乘法和平方的迭代所消耗的能量要比只涉及平方的迭代多。可以用来避免时序攻击的同类技术也可以用来阻止能量攻击。
5 RSA 签名方案
签名的基本概念
传统签名（手写签名）的特征：
（1）一个签名是被签文件的物理部分；
（2）验证物理部分进行比较而达到确认的目的。(易伪造)
定义： (数字签名方案）一个签名方案是有签署算法与验证算法两部分构成。可由五元关系组（P ,A,K,S,V ）来刻化：
(1)P是由一切可能消息(messages)所构成的有限集合；
(2)A是一切可能的签名的有限集合；
(3)k为有限密钥空间，是一些可能密钥的有限集合；
(4)任意k ∈K ，有签署算法Sigk ∈ S 且有对应的验证算法V erk ∈V , 对每一个
第六章 公钥密码学
1 什么是公钥密码体制
钥密码又称为双钥密码、非对称密码，是1976年由Diffie 和Hellman 在其“密码学新方向”一文中提出的，见划时代的文献：
W .Diffie and M.E.Hellman, New Directrions in Cryptography , IEEE Transaction on Information Theory, V .IT-22.No.6, Nov 1976, PP .644-654
单向陷门函数是满足下列条件的函数f ：
(1)给定x ，计算y=f(x)是容易的；
(2)给定y , 计算x 使y=f(x)是困难的。
(所谓计算x=f -1(y)困难是指计算上相当复杂，已无实际意义。)
(3)存在δ，已知δ 时, 对给定的任何y ，若相应的x 存在，则计算x 使y=f(x)是容易的。 注：1*. 仅满足(1)、(2)两条的称为单向函数；第(3)条称为陷门性，δ 称为陷门信息。 2*. 当用陷门函数f 作为加密函数时，可将f 公开，这相当于公开加密密钥。此时加密密钥便称为公开钥，记为Pk 。 f 函数的设计者将δ 保密，用作解密密钥，此时δ 称为秘密钥匙，记为Sk 。由于加密函数是公开的，任何人都可以将信息x 加密成y=f(x)，然后送给函数的设计者（当然可以通过不安全信道传送）；由于设计者拥有Sk ，他自然可以解出x=f-1(y)。
3*.单向陷门函数的第(2)条性质表明窃听者由截获的密文y=f(x)推测x 是不可行的。
2.Diffie-Hellman 密钥交换算法
Diffie 和Hellman 在其里程碑意义的文章中，虽然给出了密码的思想，但是没有给出真正意义上的公钥密码实例，也既没能找出一个真正带陷门的单向函数。然而，他们给出单向函数的实例，并且基于此提出Diffie-Hellman 密钥交换算法。这个算法是基于有限域中计算离散对数的困难性问题之上的：设F 为有限域，g ∈ F 是F 的乘法群F*=F\{0}=生成元。并且对任意正整数x ，计算gx 是容易的；但是已知g 和y 求x 使y= gx，是计算上几乎不可能的。这个问题称为有限域F 上的离散对数问题。公钥密码学中使用最广泛的有限域为素域FP .
对Diffie-Hellman 密钥交换协议描述：Alice 和Bob 协商好一个大素数p ，和大的整数g ，1。p 和g 无须保密，可为网络上的所有用户共享。
对于一个素数q ，如果数值：a mod q，a2 mod q，„„，aq-1 mod q，是各不相同的整数，并且以某种排列方式组成了从1到q-1的所有整数
则称整数a 是素数q 的一个本原元（原根）
当Alice 和Bob 要进行保密通信时，他们可以按如下步骤来做：
由(4)知，Alice 和Bob 已获得了相同的秘密值K 。双方以K 作为加解密钥以传统对称密钥算法进行保密通信。
注：Diffie-Hellman 密钥交换算法拥有美国和加拿大的专利。
3 RSA 公钥算法
RSA 公钥算法是由Rivest,Shamir 和Adleman 在1978年提出来的（见Communitions of the ACM. Vol.21.No.2. Feb. 1978, PP.120-126) 该算法的数学基础是初等数论中的Euler （欧拉) 定理，并建立在大整数因子的困难性之上。
4 RSA 密码体制的实现
于是要求：若使RSA 安全，p 与q 必为足够大的素数，使分析者没有办法在多项式时间内将n 分解出来。建议选择p 和q 大约是100位的十进制素数。 模n 的长度要求至少是 512比特。EDI 攻击标准使用的RSA 算法中规定n 的长度为512至1024比特位之间，但必须是128的倍数。国际数字签名标准ISO/IEC 9796中规定n 的长度位512比特位。 为了抵抗现有的整数分解算法，对RSA 模n 的素因子p 和q 还有如下要求：
(1)|p-q|很大，通常 p 和q 的长度相同；
(2)p-1 和q-1分别含有大素因子p1和q1
(3)P1-1和q1-1分别含有大素因子p2和q2
(4)p+1和q+1分别含有大素因子p3和q3
为了提高加密速度，通常取e 为特定的小整数，如EDI 国际标准中规定 e ＝216＋1，ISO/IEC9796中甚至允许取e ＝3。这时加密速度一般比解密速度快10倍以上。
下面研究加解密算术运算，这个运算主要是模n 的求幂运算。著名的“平方-和-乘法”方法将计算xc(mod n) 的模乘法的数目缩小到至多为2l ，这里的l 是指数c 的二进制表示比特数。若设n 以二进制形式表示有k 比特，即k=[log2n]+1。 由l ≤ k ，这样xc(mod n)能在o(k3)时间内完成。（注意，不难看到，乘法能在o(k2)时间内完成。）
平方－和－乘法算法：
指数c 以二进制形式表示为：
5 攻击RSA
因数分解攻击(Factorization Attack)
选择密文攻击(chosen-Ciphertext attack)
对加密指数的攻击
对解密指数的攻击
明文攻击(plaintext attack)
对模的攻击
执行攻击
◆ 因数分解攻击
(Factorization Attack)
现在有许多种因数分解算法，但是没有一种可以分解带有多项式时间复杂度的大整数。为了安全，目前的RSA 要求n 必须大于300个十进制数位，这就是说模必须最小是1024比特。即使运用现在最大最快的计算机，分解这么大的整数所要花费的时间也是不可想象的。这就表明只要还没有发现更有效的因数分解算法，RSA 就是安全的。
◆ 选择密文攻击
(chosen-Ciphertext attack)
◆ 对加密指数的攻击
为了缩短加密时间，使用小的加密指数e 是非常诱人的。普通的e 值是e = 3(第
二个素数) 。不过有几种针对低加密指数的潜在攻击，在这里我们只作简单的讨论。这些攻击一般不会造成系统的崩溃，不过还是得进行预防。为了阻止这些类型的攻击，我们推荐使用 (或者一个接近这个值的素数) 。
◆ Coppersmith 定理攻击
主低加密指数攻击称为Coppersmith 定理攻击(Coppersmith theorem attack) 。该项定理表明在一个e 阶的mod n多项式f(x)中，如果有一个根小于n1/e，就可以运用一个复杂度为log n 的算法求出这些根。这个定理可以应用
于
的RSA 密码系统。如果e = 3并且在明文当
中只有三分之一的比特是未知的，那么这种算法可以求出明文中所有的比特。
◆ 广播攻击
如果一个实体使用相同的低加密指数给一个接收者的群发送相同的信息，就会
发动广播攻击(broadcast attack)。例如，假设有如下的情节：Alice 要使用相同的公共指数e = 3和模数n1、n2、n3给三个接收者发送相同的信息。
对这些等式运用CRT ，攻击者就可以求出形式为
的等式。
这就表明P3
◆ 相关信息攻击
相关信息攻击(related message attack)是由Franklin Reiter 提出来的，下面我们就简单描述一下这种攻击。Alice 用e = 3加密两个明文P1和P2，然后再把C1和C2发送给Bob 。如果通过一个线性函数把P1和P2联系起来，那么攻击者就可以在一个可行的计算时间内恢复P1和P2。
◆ 短填充攻击
短填充攻击(short pad attack)是由Coppersmith 提出来的，下面我们就简单描述一下这种攻击。Alice 有一条信息M 要发送给Bob 。她先用r1对信息填充，加密的结果是得到了C1，并把C1发送给Bob 。攻击者拦截C1并把它丢掉。Bob 通知Alice 他还没有收到信息，所以Alice 就再次使用r2对信息填充，加密后发送给Bob 。攻击者又拦截了这一信息。攻击者现在有C1和C2，并且她知道C1和C2都是属于相同明文的密文。Coppersmith 证明如果r1和r2都是短的，攻击者也许就能恢复原信息M 。
◆ 对解密指数的攻击
可以对解密指数发动攻击的两种攻击方式：
1. 暴露解密指数攻击(revealed decryption exponent attack)
如果攻击者可以求出解密指数d ，她就可以对当前加密的信息进行解密。不过，到这里攻击并还没有停止。如果攻击者知道d 的值，她就可以运用概率算法(这里不讨论) 来对n 进行因数分解，并求出p 和q 值。因此，如果Bob 只改变了泄露解密指数但是保持模n 相同，因为攻击者有n 的因数分解，所以她就可以对未来的信息进行解密。这就是说，如果Bob 发现解密指数已经泄露，他就要有新的p 和q 的值还要计算出n ，并创建所有新的公钥和私钥。
2. 低解密指数攻击(low decryption exponent attack)。
Bob 也许会想到，运用一个小的私钥d 就会加快解密的过程。Wiener
表示如果
，一种基于连分数(一个数论当中的问题) 的特殊攻击类型就可以危
害RSA 的安全。要发生这样的事情，必须要有q
在RSA 中，我们推荐用来防止低加密指数攻击。
◆ 明文攻击(plaintext attack)
攻击者已经知道了有关明文的一些内容。这一特征也许就会引起一些针对明文的攻击。在这一部分中我们提到三种攻击：短信息攻击、循环攻击和公开攻击。
◆ 短信息攻击(short message attack)
在短信息攻击中，如果攻击者知道可能的明文组，那么她除了知道明文是密文的转换之外，还知道一些别的信息。攻击者可以对所有可能的信息进行加密，直到结果和所拦截的信息相同。例如，如果知道Alice 正在发送一个4位数的数字，攻击者就可以轻易地试验0000~9999的明文数字，来发现明文。为此，短信息必须要在开头和结尾用随机比特进行填充，来阻止这类攻击。
◆ 循环攻击(cycling attack)
循环攻击是基于这样一个事实，那就是密文是明文的一个置换，密文的连续加密最终结果就是明文。也就是说，如果对所拦截的密文C 连续加密，攻击者最终就得到了明文。不过，攻击者不知道明文究竟是什么，所以她就不知道什么时候要停止加密。她就要往前多走一步。这样如果她再次得到了密文C ，她只要返回一步就得到了明文。
◆ 公开信息攻击(unconcealed message attack)
是一种基于明文和密文之间置换关系的攻击。一则公开信息就是自身加密(不被隐藏) 的信息。已经证明总有一些信息是自身加密的。因为通常加密指数是一个奇数，有一些明文如P = 0和P = 1，都是自身加密的。如果加密指数是仔细选出来的，那就会有更多的这种信息被忽略。如果算出来的密文和明文相同，加密程序总要在提交密文之前阻止并拒绝明文。
◆ 同模攻击(common modulus attack)
如果一个组织使用一个共同的模n ，那就有可能发动同模攻击。例如，一个组织中的人也许会让一个可信机构选出p 和q ，计算出n=pq，并为每一个实体创建一对指数(ei, di) 。现在假定Alice 要发送一则信息给Bob 。发给Bob
的密文是
Bob
用他的私密指数来对他的信息。解密。问题是如果攻击者是该组织中的一个成员，并且像我们在“低解密指数攻击”那一部分中学过的那样，她也得到了分配的指数对，这样她也就可以对信息解密。运用她自己的指数对(eE和dE) ，攻击者可以发动一个概率攻击来分解n 并得到Bob 的dB 。为了阻止这种类型的攻击，模必须不是共享的。每一个实体都要计算她或他的模。
◆ 执行攻击
前面所述的攻击都基于RSA 的基本的结构。正像Dan Boneh所论述的那样，有几种针对RSA 执行的攻击。
时序攻击
能量攻击
◆ 时序攻击(timing attack)
Paul Kocher 精密地论证了这种纯密文攻击，我们称为时序攻击。这种攻击基于快速指数算法(前面讨论过) 。如果私密指数d 中的相关比特是0的话，这种算法只应用平方；如果相关的位是1，这种算法就既应用平方也应用乘法。也就是说，如果相关的比特是1，完成每一个迭代需要的时序会更长。这种时序上的不同就可以使攻击者逐一找出d 中的比特值。
有两种方法可以阻止时序攻击：
(1) 把随机延迟加到指数上使每一个指数所消耗的时间相同。
(2) Rivest引入了盲签名(blinding)。这个概念就是在解密前用一个随机数乘以密文。
◆ 能量攻击(power attack)
能量攻击和时序攻击相似。Kocher 表示，如果攻击者能够准确测量出解密过程中所消耗的能量，她就可以发动一个基于时序攻击原则的能量攻击。涉及乘法和平方的迭代所消耗的能量要比只涉及平方的迭代多。可以用来避免时序攻击的同类技术也可以用来阻止能量攻击。
5 RSA 签名方案
签名的基本概念
传统签名（手写签名）的特征：
（1）一个签名是被签文件的物理部分；
（2）验证物理部分进行比较而达到确认的目的。(易伪造)
定义： (数字签名方案）一个签名方案是有签署算法与验证算法两部分构成。可由五元关系组（P ,A,K,S,V ）来刻化：
(1)P是由一切可能消息(messages)所构成的有限集合；
(2)A是一切可能的签名的有限集合；
(3)k为有限密钥空间，是一些可能密钥的有限集合；
(4)任意k ∈K ，有签署算法Sigk ∈ S 且有对应的验证算法V erk ∈V , 对每一个