RSA blind算法－－让RSA抵抗时间分析攻击

对于了解RSA算法并且也了解密码算法时间分析攻击的人，可以跳过A,B两部分。

A.先大致说一下RSA算法：

公开密钥(n,e)，私有密钥(n,d)
其中n = p*q，p,q是两个随机选择的巨型素数（必须保密），d,e满足d*e≡1 (mod(p-1)(q-1))

----====以下公式中，如果不加特殊说明，所有运算都是(mod n)的运算====----

于是根据Fermat小定理，x^(d*e) = x

假设明文为m，密文为c，那么

利用公钥(n,e)的加密过程：c = m^e
利用私钥(n,e)的解密过程：m = c^d = (m^e)^d = m^(e*d)，根据Fermat小定理，m^(e*d)刚好等于m。

当然，RSA算法真实实现比这要复杂很多，需要用到大素数的随机生成算法、强素数的生成算法、中国剩余定理、快速的模幂运算等，但这些对与我们要讨论的RSA blind没有什么关系，因此不再深入了。

B.再大致介绍一下时间分析攻击：

时间分析攻击，实际上是选择密文攻击的一种，利用了一种边带（side channel）信息的泄漏

B.1先说说选择密文攻击：

所谓选择密文攻击，是指攻击者能够获取解密服务，但不知道密钥的情况下，对系统进行的一种攻击。

例如，一个职员，在任职期间可以得到其主管机器的解密服务，因此可以阅读主管收到的加密邮件并且代主管回复邮件，但并不知道主管的密钥。但该职员离职之后，该解密服务随即停止。因此该职员不再能够继续阅读主管的邮件，因为他没有主管的密钥。如果该职员在任职期间，利用职务的便利，通过精心构造一批密文，并且使用主管机器提供的解密服务，根据这批密文的解密结果（注意，解密结果不一定仅仅包括明文信息，解密指定密文所消耗的时间，系统产生的热量，此类信息都术语解密结果信息）设法确定了主管的密钥，那么他就可以在离职之后继续读取主管的邮件。这个职员的攻击方法就被称作选择密文攻击。

稍微正式一点地描述选择密文攻击：攻击者精心设计一组密文ci，使用能够获取到的解密服务对密文ci进行解密，假设每个ci对应的解密结果所包含的信息是ri，那么我们就得到了这组ci和ri的之间的关系Rk:
ri = Rk(ci)。Rk与密钥k之间肯定是有关系的，通过这个Rk确定密钥k的过程就是选择密文攻击。

如果对于一个算法，Rk与k之间的关系并不复杂，有办法在可接受的时间内由Rk确定密钥k，那么就说这个算法对于选择密文攻击是脆弱的。

B.2再说说时间攻击：

所谓时间（分析）攻击，所利用的解密结果信息就是解密服务解密密文ci所用的时间ti。如果精心设计密文，获取了ci和ti的关系Tk:
ti = Tk(ci)，通过分析Tk和密钥k之间的关系来确定密钥的方法，就是所谓的时间分析攻击。

一个非密码学的时间分析攻击的例子：如果我要窃取你在键盘上输入的口令，我不一定非要看到敲击口令的过程，我只要在旁边听你相邻两次击键的时间间隔，就可以得到一些信息：间隔短的两次击键，很可能意味着两个键的距离比较近，间隔长的两次击键，很可能意味着两个键的距离比较远。如果我有机会尝试攻击你的口令，我可以仅仅尝试哪些在时间间隔模式上跟我窃听到的你的击键过程的时间间隔很相似的口令，这样我所需要进行尝试的数量就会远小于完全的暴力攻击。

对于RSA算法，数学上的攻击，至少在目前来说，没有已知的特别高效的攻击手段。但是，对于一个具体的RSA算法实现，只要我知道算法的具体代码，我就可以给出解密一个指定密文ci所需要的时间ti，与密钥每个bit的值之间的函数关系。这样我只要精心构造出一组密文ci，并测量时间ti，就可以把密钥的每个bit作为未知数，建立一组方程把每个密钥bit求出来。这个方程甚至很可能是线性的。

有人可能怀疑解密时间可能不能精确测量，那么这种攻击是否还能奏效呢？当然可以，首先，时间不精确可以重复多次地对同一个密文进行解密取平均值而得到。其次，即便测量不精确，不能唯一地确定密钥，至少也可以只试探那些最可能的密钥，大大缩小密钥搜索空间。

注意，这种攻击并不仅仅是理论上未来可能出现的攻击，有一些密码学家已经成功地利用此类攻击攻破了一些密码算法。

之所以这种攻击也属于边带信息或者带外信息泄漏的一种，就是因为这种攻击并非对RSA的数学结构进行攻击，而是对RSA具体实现过程中软硬件特性所泄漏的密钥信息进行攻击，而这些信息在RSA算法本身所建立的安全信道之外，是一种经常被"忽视"的信道。在此类信道上的信息泄漏，常常可以称为边带信息泄漏或者带外信息泄漏。

知道了时间分析攻击，能量分析攻击就简单了，就是通过测量密码系统在解密一个特定密文的时候的发热量，来猜测密钥信息的方法。由于发热量的测量相对于时间来说更加不准确，而且实际情况中常常难以对系统的能量进行测量，因此一般来说这种攻击比时间攻击更难实施，效率也更低，但一旦能够实施这种攻击，仍然比暴力搜索要快若干数量级（别忘了，系统发热量虽然不能准确测量，但我仍然可以对一个密文重复测量1000000次取平均）。

为了防范时间分析攻击，一种容易想到的方法就是设法确定算法在最坏情况下所消耗的时间，然后任何一次解密，如果没有达到最坏时间，都不输出结果。这样做一个是估计最坏时间很麻烦，而且与平台相关，同时也大大降低算法效率。而且即便这种方法能够阻止时间分析攻击，也难以阻止能量分析攻击，因为等待到最坏时间的过程，毕竟跟计算过程不同，因此所消耗的能量也不同。为了防止能量分析攻击，容易想到的方法是对硬件做功率补偿控制，永远让系统消耗恒定功率。这些容易想到的方法成本都很高。

C.RSA blind算法
在解密密文c之前（这个密文c可能是攻击者精心构造出来用来刺探时间信息的密文），我们生成一个均匀分布于[0,n)之间的随机数r（必须是密码学意义上安全的随机数或者伪随机数），对r进行加密并且与c相乘得到变换后的密文s：
s = r^e * c（注意，这里往后的运算还是都要对n取模的）
（这一步很快，因为RSA加密指数e总是很小，因此这一步的速度常常比解密过程快几十倍）

这里要说一句：r是一个[0,n)之间均匀分布的随机变量，可以断言r^e以及s
= r^e * c也都是这样的随机变量，只是三者不是相互独立的。但任何一个单独来看，都仍然是一个密码学意义上安全的随机数。

这个过程涉及到公钥中的加密指数e，由于这个过程中并没有涉及到私钥中的解密指数d，因此不必担心任何信息的泄漏。

然后对s进行解密并且除以r，就可以得到明文m：（别忘了(mod n)运算！）
m = s^d / r
因为s^d / r = (r^e * c)^d / r = r^(e*d) * c^d / r = r * c^d / r = c^d = m

注意，这个过程中，s^d运算与d的值相关，让我们来分析一下是否可能会泄漏d的信息。

密文c可能是攻击者精心构造用来刺探解密指数d的信息的数据，那么攻击者只要建立了解密时间t与密文c之间的关系t=t(c)，就可能以此获取私钥d的信息。

但由于s是一个密码学意义上安全的随机数，那么可以肯定的是，无论攻击者如何精心地构造了c，最终使用d进行解密的都是随机数s，于是攻击者实际上无法建立解密时间t与密文c之间的关系，解密时间t实际上是一个与密文c完全无关的随机变量s相关的时间。最后还有一个除法，这个除法所需要的时间跟r有关，但r也是一个与密文c完全独立的随机变量。

于是在整个过程中，攻击者得不到ti和ci的关系t，因此时间攻击也就无法奏效。

说实话，前面的讨论中我打了一个马虎眼。第一步s = r^e * c过程，所需要的时间与随机数r的值也有关系，因此这一步的时间可能会与随机数r的值相关。但即便这一步的时间被单独测量了，所得到的关于r的信息也是很少的，因为花费同样时间的不同r值太多了（简并度太大:D）。而且最关键的是，r值是每次系统解密的时候重新随机生成的，用过就丢，因此不能通过多次精心设计的刺探过程来积累有关某一次使用过的r值的信息（前提是r确实是一个密码学安全的随机数或者伪随机数），虽然信息可能会泄漏一点点，但无论过多长时间都无法积累到危险的程度。

关于电子自旋和量子态的简单科普

电子自旋与经典的自转不同。你可以在任何方向上测量电子的自旋。但是无论你选择什么方向，你测量的结果只能是两种，可以用（与该方向相关的）↑和↓来表示。在你不进行测量的时候，电子的自旋可以处于该方向的↑和↓两种状态的“相干叠加态”。

实际上，只有当你选定了一个测量方向，你才能测得电子自旋。在这个方向上，能够测得的两种状态↑和↓被称为“该方向上电子自旋的本征态”。注意，称一个状态为本征态，并不是指这个状态比其他的状态更“基本”。这个本征态之所以是本征态，仅仅是因为你选定了一个方向。所以。实际上在任何一个方向上，电子自旋都有两个本征态。一个方向上所确定的电子自旋的两个本征态，对于另外一个不同方向来说，就变成了·相干叠加态·。

如果你想要同时测量电子自旋在两个相互不同方向上的分量来确定电子“自转轴”的空间指向，在量子力学的理论框架中是绝对做不到的。你只能先在一个方向上测量，然后在另外一个方向上测量。但是如果你先在一个方向上测量，那么测量本身就会迫使电子自旋进入该方向的↑和↓两个状态之一（这通常被称为波函数的坍塌），此时如果你紧接着进行另一个方向的测量，就相当于你把先前的测量结果按照量子相干叠加的方式分解到新方向的↑和↓两个本征态上，你仍然只能测得新方向的两个本征态之一。也就是说，你想要通过测量两个方向电子自旋的方向来确定电子自旋的取向，在量子力学的框架中完全是徒劳的。

至于这个相干叠加态，简称叠加态，跟通常概率统计意义上按概率分布的多种状态是完全不同的。如果我不知道桌子底下的一个硬币是正面还是反面，我可以说这个硬币处于正面和反面的概率分别是多少多少。但这仅仅是因为我不知道硬币的状态，实际上这个硬币当然必定处于正面或者反面两种情况之一，·根本没有·处于正面和反面的某种“叠加态”上。在量子力学中，把这种由于不知道系统所处的状态而导致的多种状态按照概率的分布，叫做“混合态”，而不叫做叠加态。而把叠加态（叠加态包括本征态）叫做“纯态”，叠加态实际上是一个精确的状态，并不是多个不同状态的混合。混合态才是多个纯态按照概率分布的混合。混合态之中，各个纯态的概率之和必须是1。而任何一个纯态则可以在指定了测量方式之后，被唯一地分解到对应该测量方式的若干本征态上去，但是分解之后的各个本征态系数是复数。这些复数的模的平方和必须是1，而它们自身的和并不一定是1。例如电子可以处于(1/√2)↑ + (1/√2)↓或者(1/√2)↑ - (1/√2)↓或者(1/2)i↑ + (√3/2)↓等等。无论是叠加态还是本征态，都是纯态，他们的区别仅仅是你所选择的表达量子态的基底不同造成的，就好像建立坐标系的时候选用的基向量不同一样。实际上基向量和其他向量之间并没有本质的区别，完全可以随意选择。你可以说一个叠加态是若干个本征态的叠加，你也可以把一个本征态表示为某些叠加态的某种叠加。只不过后者由于不代表具体测量值，因而不太方便。

一旦你对量子系统选定了一个（可以实际操作的）测量手段，那么你就确定了一组本征态（相当于向量空间的一组基底）。这时候你对一个量子系统进行测量，你就只能得到这些本征态之一，而且测量操作也将立即迫使系统进入你所测得的本征态。对于一个叠加态，你的测量结果是某个本征态的概率，等于该叠加态在这个本征态上投影系数的模的平方。

principle, law, rule在学科中的含义解释

principle：原理、原则。

principle 作为原理，往往是指一个理论最基本的假定，有时候也可以叫作基本定律（basic law）。一个理论以原理为基本假设，推导出一些导出结论而构建起来。例如相对论的原理，量子力学的原理，经济学的原理。原理在一个理论中是用来解释和推 导其他内容的，其本身不能在理论内部得到解释。有时候，A理论的一些原理在B理论中可能是导出结论，而B理论的一些原理也可能在A理论中作为导出结论。特 别地，随着理论的发展，往往会出现这种情况：原来以为很基本的原理，在新理论中不再基本；而原来的导出结果，在新理论被认为更加基本而作为原理。

principle 作为原则，往往指一些先入为主的规则。例如，你做人坚决不说谎，而且根本不管这是为什么，反正就是不说谎，丝毫没得商量。这种情况下可以认为不说谎是你做 人的原则。但是这和原理的含义实际上是有差别的，一个东西作为理论的原理，在理论内部是不能得到解释的，这一点跟原则的含义相似。但这不等于这些原理不能 被解释，也不等于这些原理不能被放弃。前面说了在B理论中A理论的部分原理变成了导出结论，那么实际上B理论就对A理论的这些原理给出了解释。当理论和事 实冲突的时候，我们更相信事实，而不是原理。而原则和现实利益相互冲突的时候，一些人会选择坚持原则。有时候盲目坚持原则会带来好处，因为某些你不清楚原 因的原则并不是真的没有原因。但有时候盲目坚持原则会带来恶果，因为你可能不知道这个原则的适用情况而滥用了这个原则。


law：定律（法律这个意思我就不提了）。

law 作为定律，大部分情况应该是指通过对试验数据进行分析而得到的一些经验规律，但是却能够经受广泛严格的试验检验。例如理想气体定律，安培定律，万有引力定 律，能量守恒定律。当一个定律在某个理论框架中得到了解释，在这个理论框架中这个定律就作为一个导出结论而存在。例如，机械能守恒在牛顿理论中作为一个导 出结论。但是，能量守恒（包括机械能守恒）在热力学中变成了原理（基本定律）。现在看来，能量守恒定律是比牛顿运动定律更加基本的规律，因此在后来的理论 中往往也被拿来作为理论的原理。


rule：规律、规则。

rule作为规则，就是指制定出来的必须遵守的一些约定。例如数学推导规则，语法规则，游戏规则，交通规则等。

对 于人制定的规则，既然是人的约定，实际上就存在任意性，例如交通规则的右侧通行或者左侧通行，数学推导中使用什么符号，语法规则中的语序等。虽然有任意 性，但是也不能不做约定，否则就无法解决混乱。但是在若干都能够解决混乱的约定之间做出选择，就是比较随意的事情了。例如，为了解决人和人之间交流思想的 问题，世界上出现了大量不同的语言；为了保证交通秩序，世界上出现了许多不同的交通规则。他们都能够解决特定领域的混乱，相互间往往很难比较孰优孰劣，但 是却互不兼容。

rule作为规律，我猜其最原始的含义应该是“造物主所制定的用于指导宇宙运转的规则”，实际上也是规则。但这个规则不是 人制定的，而这个宇宙事实上却按照这个规则运转。到底是不是造物主制定的我们根本不用关心，但是作为规律，这个词的含义往往是指一个领域所研究的对象所遵 循的·事实·上的关系。例如经济规律，物理规律，化学规律。

有时候如果一个理论经过大量检验后被认为是准确有效的，我们往往也会把这个理 论的各种结论称为规律。但这仅仅是在这个理论的预言与观察结果一致的情况下。如果在某些情况下与事实不一致，那么至少在这些情况下，我们就不能再称之为规 律。如果发现某些事实没有现有理论能够解释，可以称这个地方有我们尚未发现的规律。