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确实是一个密码学安全的随机数或者伪随机数），虽然信息可能会泄漏一点点，但无论过多长时间都无法积累到危险的程度。
