2.1　非对称加密RSA算法

由于RSA算法也是隐私计算中经常用到的基础算法（比如在不经意传输、同态加密等隐私计算中），因此在这里对RSA算法做简单的介绍。在此之前，先介绍RSA算法的一些基础知识，然后再介绍RSA算法的密钥生成以及加解密。

2.1.1　RSA算法基础

1. 欧拉函数

任意给定正整数n，在小于等于n的正整数中，有多少个数与n构成互质关系？（比如，在1到8中，有多少个数与8构成互质关系？）计算这些值的方法叫作欧拉函数，以φ(n)表示。在1到8中，与8形成互质关系的是1、3、5、7，所以φ(8)=4。

2. 欧拉定理

如果两个正整数a和n互质，则n的欧拉函数φ(n)可以让下面的等式成立：

aφ(n)≡1(mod n)

也就是说，a的φ(n)次方被n除的余数为1。或者说，a的φ(n)次方减去1，可以被n整除。比如，3和7互质，而7的欧拉函数φ(7)等于6，所以3的6次方（也就是729）减去1，可以被7整除（728/7=104）。欧拉定理的证明比较复杂，且不是本书的重点，此处省略。

3. 费马小定理

再来看一下欧拉定理的一个特殊情况。假设正整数a与质数n互质，因为质数n的φ(n)等于n-1，则欧拉定理可以写成下面的公式：

an-1≡1(mod n)

它是欧拉定理的特例，也被称为费马小定理。

4. 欧拉函数之积

欧拉定理还有一个特点，如果n可以分解成两个互质的整数之积，即n=p1×p2，则

φ(n)=φ(p1×p2)=φ(p1)×φ(p2)

即积的欧拉函数等于各个因子的欧拉函数之积。比如，φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。

5. 模反元素

如果两个正整数a和n互质，那么一定可以找到整数b，使得ab-1被n整除，或者说ab被n除的余数是1。

ab≡1(mod n)

这时，b就叫作a的模反元素。比如，3和11互质，那么3的模反元素就是4，因为(3×4)-1可以被11整除。显然，模反元素不止一个，比如15也是3的模反元素。而欧拉定理可以用来证明模反元素必然存在。可以看到，a的φ(n)-1次方就是a的模反元素。

aφ(n)=a×aφ(n)-1≡1(mod n)

欧拉定理是RSA算法的核心。理解了这个定理，我们就可以来进一步了解RSA的密钥生成了。

2.1.2　密钥生成

这里分6步来描述RSA公私钥的生成过程。

1）随机选择两个不相等的质数p和q，比如61和53。实际应用中，这两个质数越大，就越难破解。

2）计算p和q的乘积n。比如n=61×53=3233。

3）计算n的欧拉函数φ(n)。φ(n)=φ(p×q)=φ(p)φ(q)=(p-1)(q-1)。因此，φ(3233)等于60×52，即3120。注意,这里用到了上面提到的欧拉函数之积。

4）随机选择一个整数e，选择条件是1<e<φ(n)，且e与φ(n)互质。比如在1到3120之间，随机选择17。

5）计算e对于φ(n)的模反元素d。根据上文提到的模反元素的定义，ed≡1(mod φ(n))。

这个式子等价于ed-1=k φ(n)。因此找到模反元素d，实质上就是对下面这个二元一次方程求解：ex+φ(n)y=1。即已知e=17, φ(n)=3120，17x+3120y=1。

这个方程可以用“扩展欧几里得算法”（又叫辗转相除法）求解，此处省略具体过程。总之，可以计算出一组整数解为（x, y）=（2753, -15），即d=2753。至此，所有计算完成。

6）将n和e封装成公钥，n和d封装成私钥。在这个例子中，n=3233，e=17，d=2753，所以公钥就是（3233, 17），私钥就是（3233, 2753）。

实际应用中，公钥和私钥的数据都采用ASN.1格式表达。标准的ASN.1编码规则有基本编码规则（Basic Encoding Rule，BER）、规范编码规则（Canonical Encoding Rule，CER）、唯一编码规则（Distinguished Encoding Rule，DER）、压缩编码规则（Packed Encoding Rule，PER）和XML编码规则（XML Encoding Rule，XER）。在实践过程中，我们需要注意加载的密钥所使用的编码规则。

2.1.3　加密与解密

生成公私钥后，我们就可以进行加密计算了。加密计算公式为：me≡c(mod n)，其中m就是要加密的信息，c就是计算生成的密文。沿用上面的例子，假设m=65，则6517≡2790(mod 3233)。解密使用计算公式为：cd≡m(mod n)，将密文2790代入公式计算可得27902753≡65(mod 3233)。

为什么用私钥解密就一定可以得到m呢？根据加密公式可知c=me-kn，将c代入解密公式可得(me-kn)d≡m(mod n)，也就是说我们需要证明这个公式成立，等同于求证med≡m(mod n)。

根据模反元素的定义，由于ed≡1(mod φ(n))，也就是ed=hφ(n)+1，所以等同于求证mhφ(n)+1≡m(mod n)。接下来分两种情况进行证明。

1. 假设m与n互质

根据欧拉定理，mφ(n)≡1(mod n)，可得(mφ(n)h×m≡m(mod n)，即原式得到了证明。

2. 假设m与n不互质

m、n必定含有非1公因子，而n等于质数p和q的乘积，因此m必然等于kp或kq。以m=kp为例，考虑到这时kp与质数q必然互质，根据费马小定理可知(kp)(q-1)≡1(mod q)成立，进一步通过构造可得[(kp)(q-1)]h(p-1)×kp≡kp(mod q)成立。

因为n等于质数p和q的乘积，根据欧拉函数之积的特点，已知(p-1)(q-1)=φ(p)φ(q)=φ(p×q)=φ(n)，同时根据模反元素定义ed=hφ(n)+1，可得(kp)ed≡kp(mod q)。

将等式改写成(kp)ed=tq+kp，进一步改写成(kp)ed-kp=tq。因为p和q互质，这时t必然能被p整除（因为等式左边是p的倍数，等式右边也应该是p的倍数），即t=t'p，则等式又可改为(kp)ed=t'pq+kp。

因为m=kp，n=pq，所以med≡m(mod n)，即原式得到了证明。

2.1.4　基于RSA算法的盲签名

盲签名（Blind Signature）是一种在不让签名者获取所签署消息具体内容的情况下进行数字签名的技术。盲签名允许拥有消息的一方先将消息盲化，而后让签名者对盲化的消息进行签名，最后消息拥有者对签字除去盲因子，得到签名者关于原消息的签名。

盲签名的一个通俗的解释是：Alice想让Bob在一张信件上签名，但是不想让Bob看到信件上面所写的字。于是，Alice在信件上面放了一张复写纸，然后将信件和复写纸放到了信封中交给Bob。Bob在拿到信封之后直接在信封上面签字，这样字迹就通过复写纸写到了信件上。Alice拿到信封之后就可以得到Bob签过字的信件。

基于RSA算法可以实现盲签名，假设Alice要让Bob对消息m进行盲签名，Bob拥有私钥对(n, d)，并共享了公钥对(n, e)，其具体实现步骤如下：

1）Alice选取与n互质的盲因子k，然后计算t≡mke (mod n)，并把t发送给Bob。

2）Bob对t进行签名，即计算td≡(mke)d (mod n)，并把计算结果发送给Alice。

3）Alice计算盲因子k的逆元k-1，并计算s≡k-1 td (mod n)，根据费马小定理，可得td≡(mke)d≡md ked-1 k≡md k(mod n)，进而可得s≡k-1 md k≡md (mod n)。

最终Alice获得了Bob的签名，但Bob并不知晓所签名的消息m的具体内容，即Alice获得了Bob的盲签名。