第4章 公钥密码 4.1 密码学中一些常用的数学知识 4.2 公钥密码体制的基本概念 4.3 RSA算法 4.4 背包密码体制 第4章 公钥密码 4.1 密码学中一些常用的数学知识 4.2 公钥密码体制的基本概念 4.3 RSA算法 4.4 背包密码体制 4.5 Rabin密码体制 4.6 椭圆曲线密码体制 习题

4.1 密码学中一些常用的数学知识

1. 因子 设a，b(b≠0)是两个整数，如果存在另一整数m，使得a=mb，则称b整除a，记为b|a，且称b是a的因子。 4.1.2 素数和互素数 1. 因子 设a，b(b≠0)是两个整数，如果存在另一整数m，使得a=mb，则称b整除a，记为b|a，且称b是a的因子。

整数具有以下性质： ① a|1，那么a=±1。 ② a|b且b|a，则a=±b。 ③ 对任一b (b≠0)，b|0。 ④ b|g，b|h，则对任意整数m、n有b|(mg+nh)。 性质④的证明： 由b|g，b|h知，存在整数g1、h1，使得g=bg1, h=bh1所以mg+nh=mbg1+nbh1=b(mg1+nh1),因此b|(mg+nh)。

2. 素数 称整数p(p>1)是素数，如果p的因子只有±1，±p。 任一整数a(a>1)都能惟一地分解为以下形式： 其中p1<p2<…<pt是素数，ai>0 (i=1,…,t)。例如 91=7×11，11011=7×112×13

这一性质称为整数分解的惟一性，也可如下陈述： 设P是所有素数集合，则任意整数a (a>1)都能惟一地写成以下形式： 其中ap≥0,等号右边的乘积项取所有的素数，然而大多指数项ap为0。相应地，任一正整数也可由非0指数列表表示。例如： 11011可表示为 {a7=1, a11=2, a13=1} 两数相乘等价于对应的指数相加，即由k=mn 可得：对每一素数p, kp=mp+np。而由a|b可得： 对每一素数p, ap≤bp。这是因为pk只能被pj (j≤k)整除。

3. 互素数 称c是两个整数a、b的最大公因子，如果 ① c是a的因子也是b 的因子，即c是a 、 b的公因子。 ② a和b的任一公因子，也是c的因子。 表示为c =gcd(a, b)。 如果gcd(a, b)=1，则称a和b互素

由于要求最大公因子为正，所以gcd(a,b)=gcd(a,-b)=gcd(-a,b)=gcd(-a,-b)。一般gcd(a,b)=gcd(|a|,|b|)。由任一非0整数能整除0，可得gcd(a,0)=|a|。如果将a，b都表示为素数的乘积，则gcd（a, b）极易确定。 例如： 300=22×31×52 18=21×32 gcd(18,300)=21×31×50=6 一般由c=gcd(a,b)可得： 对每一素数p，cp=min(ap,bp)。

4.1.2 模运算 设n是一正整数，a是整数，如果用n除a，得商为q，余数为r，则 a=qn+r,0≤r<n, 4.1.2 模运算 设n是一正整数，a是整数，如果用n除a，得商为q，余数为r，则 a=qn+r,0≤r<n, 其中 为小于或等于x的最大整数。 用a mod n表示余数r，则 。 如果(a mod n)=(b mod n)，则称两整数a和b模n同余，记为a≡b mod n。称与a模n同余的数的全体为a的同余类，记为[a]，称a为这个同余类的表示元素。 注意： 如果a≡0(mod n)，则n|a。

同余有以下性质： ① 若n|(a-b)，则a≡b mod n。 ② (a mod n)≡(b mod n)，则a≡b mod n。 ③ a≡b mod n,则b≡a mod n。 ④ a≡b mod n,b≡c mod n,则a≡c mod n。 从以上性质易知，同余类中的每一元素都可作为这个同余类的表示元素。

求余数运算（简称求余运算）a mod n将整数a映射到集合{0,1, …,n-1}，称求余运算在这个集合上的算术运算为模运算，模运算有以下性质： ① [(a mod n)+(b mod n)] mod n=(a+b) mod n。 ② [(a mod n)-(b mod n)] mod n=(a-b) mod n。 ③ [(a mod n)×(b mod n)] mod n=(a×b) mod n。

性质①的证明： 设（a mod n）=ra，(b mod n)=rb，则存在整数j、k使得a=jn+ra，b=kn+rb。 因此 (a+b) mod n=[(j+k)n+ra+rb] mod n=(ra+rb) mod n = [(a mod n)+(b mod n)] mod n （证毕） 性质②、③的证明类似。

例4.1 设Z8={0,1,…,7}，考虑Z8上的模加法和模乘法

从加法结果可见，对每一x，都有一y，使得x+y≡0 mod 8。如对2，有6，使得2+6≡0 mod 8，称y为x的负数，也称为加法逆元。 对x，若有y，使得x×y≡1 mod 8，如3×3≡1 mod 8，则称y为x的倒数，也称为乘法逆元。本例可见并非每一x都有乘法逆元。

一般地，定义Zn为小于n的所有非负整数集合，即Zn={0,1, …,n-1}，称Zn为模n的同余类集合。其上的模运算有以下性质： ① 交换律 (w+x) mod n=(x+w) mod n (w×x) mod n=(x×w) mod n ② 结合律 [(w+x)+y] mod n=[w+(x+y)] mod n [(w×x)×y] mod n=[w×(x×y)] mod n

③ 分配律 [w×(x+y)] mod n=[w×x+w×y] mod n ④ 单位元 (0+w) mod n=w mod n (1×w) mod n=w mod n ⑤ 加法逆元 对w∈Zn，存在z∈Zn，使得w+z≡0 mod n，记z=-w。

此外还有以下性质： 如果(a+b)≡(a+c) mod n，则b≡c mod n，称为加法的可约律。 该性质可由(a+b)≡(a+c) mod n的两边同加上a的加法逆元得到。

然而类似性质对乘法却不一定成立。例如6×3≡6×7≡2 mod 8，但37 mod 8。原因是6乘以0到7得到的8个数仅为Z8的一部分，见例4.1。即如果将对Z8作6的乘法6×Z8（即用6乘Z8中每一数）看作Z8到Z8的映射的话，Z8中至少有两个数映射到同一数，因此该映射为多到一的，所以对6来说，没有惟一的乘法逆元。但对5来说，5×5≡1 mod 8，因此5有乘法逆元5。仔细观察可见，与8互素的几个数1，3，5，7都有乘法逆元。 这一结论可推广到任一Zn。

定理4.1 设a∈Zn，gcd(a, n)=1，则a在Zn中有乘法逆元。 证明： 首先证明a与Zn中任意两个不相同的数b、c（不妨设c<b）相乘，其结果必然不同。否则设a×b≡a×c mod n，则存在两个整数k1,k2，使得ab=k1n+r，ac=k2n+r，可得a(b-c)=(k1-k2)n，所以a是(k1-k2)n的一个因子。又由gcd(a，n)=1，得a是k1-k2的一个因子，设k1-k2=k3a，所以a(b-c)=k3an，即b-c=k3n，与0<c<b<n矛盾。所以|a×Zn|=|Zn|，又知a×Zn Zn，所以a×Zn=Zn。因此对1∈Zn，存在x∈Zn，使得a×x≡1 mod n，即x是a的乘法逆元。记为x=a-1。 （证毕）

设p为一素数，则Zp中每一非0元素都与p互素，因此有乘法逆元。类似于加法可约律，可有以下乘法可约律： 如果(a×b)≡(a×c) mod n且a有乘法逆元，那么对(a×b)≡(a×c) mod n两边同乘以a-1，即得b≡c mod n

{a mod p,2a mod p,…,(p-1)a mod p}={1,2,…,p-1} 4.1.3 费尔玛定理和欧拉定理 1. 费尔玛定理 定理4.2 (Fermat)若p是素数，a是正整数且gcd(a, p)=1，则ap-1≡1 mod p。 证明：由4.1.2的讨论知当gcd(a, p)=1时,a×Zp=Zp，其中a×Zp表示a与Zp中每一元素做模p乘法。又知a×0≡0 mod p，所以a×Zp-{0}=Zp-{0}，a×(Zp-{0})=Zp-{0}。即 {a mod p,2a mod p,…,(p-1)a mod p}={1,2,…,p-1}

a×2a×…×(p-1)a≡[(a mod p)×(2a mod p)×…× 所以 a×2a×…×(p-1)a≡[(a mod p)×(2a mod p)×…× ((p-1)a mod p)] mod p≡(p-1)! mod p 另一方面 a×2a×…×(p-1)a=(p-1)!ap-1 因此 (p-1)!ap-1≡(p-1)! mod p 由于(p-1)!与p互素，因此(p-1)!有乘法逆元，由乘法可约律得ap-1≡1 mod p。 （证毕）

Fermat定理也可写成如下形式： 设p是素数，a是任一正整数，则ap≡a mod p。 2. 欧拉函数 设n是一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为φ(n)。 例如： φ(6)=2 ，φ(7)=6 ，φ(8)=4。 若n是素数，则显然有φ(n)=n-1。

定理4.3 若n是两个素数p和q的乘积，则φ(n)=φ(p)×φ(q)=(p-1)×(q-1)。 证明：考虑Zn={0,1,…,pq-1}，其中不与n互素的数有3类，A={p,2p,…,(q-1)p}，B={q,2q,…,(p-1)q},C={0}，且A∩B=Φ，否则ip=jq，其中1≤i≤q-1，1≤j≤p-1,则p是jq的因子，因此是j的因子，设j=kp，k≥1。则ip=kpq，i=kq，与1≤i≤q-1矛盾。所以 φ(n)=|Zn|-[|A|+|B|+|C|]=pq-[(q-1)+(p-1)+1] =(p-1)×(q-1)=φ(p)×φ(q) （证毕） 例如： 由21=3×7，得φ(21)=φ(3)×φ(7)=2×6=12。

3. 欧拉定理 定理4.4（Euler） 若a和n互素，则aφ(n)≡1 mod n。 证明： 设R={x1, x2, …, xφ(n)}是由小于n且与n互素的全体数构成的集合，a×R={ax1 mod n, ax2 mod n,…, axφ(n) mod n}，对a×R中任一元素axi mod n，因a与n互素，xi与n互素，所以axi与n互素，且axi mod n<n，因此axi mod n∈R，所以a×RR。

又因a×R中任意两个元素都不相同，否则axi mod n=axj mod n，由a与n互素知a在 mod n下有乘法逆元，得xi=xj。所以|a×R|=|R|，得a×R=R，所 以 ， , ，由每一xi与n互素，知 与n互素， 在 mod n下有乘法逆元。所 以aφ(n)≡1 mod n。 (证毕）

素性检验是指对给定的数检验其是否为素数。对于大数的素性检验来说没有简单直接的方法，本节介绍一个概率检验法，为此需要以下引理。 4.1.4 素性检验 素性检验是指对给定的数检验其是否为素数。对于大数的素性检验来说没有简单直接的方法，本节介绍一个概率检验法，为此需要以下引理。

引理: 如果p为大于2的素数，则方程x2≡1(mod p)的解只有x≡1和x≡-1。 证明：由x2≡1 mod p，有x2-1≡0 mod p，(x+1)(x-1)≡0 mod p，因此p|(x+1)或p|(x-1)或 p|(x+1)且p|(x-1)。 若p|(x+1)且p|(x-1)，则存在两个整数k和j，使得x+1=kp，x-1=jp,两式相减得2=(k-j)p，为不可能结果。所以有p|(x+1)或p|(x-1)。 设p|(x+1)，则x+1=kp，因此x≡-1(mod p)。 类似地可得 x≡1(mod p)。（证毕）

引理的逆否命题为：如果方程x2≡1 mod p有一解 x0{-1,1}，那么p不为素数。 例如： 考虑方程x2≡1(mod 8)由4.1.2节Z8上模乘法的结果得 12≡1 mod 8, 32≡1 mod 8, 52≡1 mod 8, 72≡1mod 8 又5≡-3 mod 8，7≡-1 mod 8，所以方程的解为1，-1，3，-3，可见8不是素数。

下面介绍Miller-Rabin的素性概率检测法。首先将n-1表示为二进制形式bkbk-1…b0，并给d赋初值1，则算法Witness(a,n)的核心部分如下： for i=k downto 0 do { x←d; d←(d×d) mod n; if d=1 and(x≠1)and(x≠n-1)then return False; if bi=1 then d←(d×a) mod n } if d≠1 then return False; return True.

此算法有两个输入参数，n是待检验的数，a是小于n的整数。如果算法的返回值为False，则n肯定不是素数，如果返回值为True，则n有可能是素数。 for循环结束后，有d≡an-1 mod n，由Fermat定理知，若n为素数，则d为1。因此若d≠1，则n不为素数，所以返回False。 因为n-1≡-1 mod n，所以(x≠1)and(x≠n-1),指x2≡1 (mod n)有不在{-1,1}中的根，因此n不为素数，返回False。

该算法有以下性质： 对s个不同的a，重复调用这一算法，只要有一次算法返回为False，就可肯定n不是素数。如果算法每次返回都为True，则n是素数的概率至少为1-2-s，因此对于足够大的s，就可以非常肯定地相信n为素数。

4.1.5 欧几里得算法 欧几里得（Euclid）算法是数论中的一个基本技术，是求两个正整数的最大公因子的简化过程。而推广的Euclid算法不仅可求两个正整数的最大公因子，而且当两个正整数互素时，还可求出其中一个数关于另一个数的乘法逆元。

1. 求最大公因子 Euclid算法是基于下面一个基本结论： 对任意非负整数a和正整数b，有gcd(a, b)=gcd(b, a mod b)。 证明：b是正整数，因此可将a表示为a=kb+r， a mod b=r, 其中k为一整数，所以a mod b =a-kb。 设d是a，b的公因子，即d|a，d|b，所以d|kb。由d|a和d|kb得d|(a mod b)，因此d是b和a mod b的公因子。 所以得出a，b的公因子集合与b，a mod b的公因子集合相等，两个集合的最大值也相等。（证毕）

例如： gcd(55, 22)=gcd(22, 55 mod 22)=gcd(22,11)=gcd(11, 0)=11。 在求两个数的最大公因子时，可重复使用以上结论。 例如： gcd(18,12)=gcd(12,6)=gcd(6,0)=6, gcd(11,10)=gcd(10,1)=1。

Euclid算法就是用这种方法，因gcd(a, b)=gcd(|a|, |b|)，因此可假定算法的输入是两个正整数，设为d，f，并设f >d。 EUCLID（f, d） 1. X ← f; Y ← d； 2. if Y=0 then return X=gcd (f，d)； 3. if Y=1 then return Y=gcd (f，d)； 4. R=X mod Y； 5. X=Y； 6. Y=R； 7. goto 2.

例4.2 求gcd(1970, 1066)。 1970=1×1066+904, gcd(1066, 904) 1066=1×904+162, gcd(904, 162) 904=5×162+94, gcd(162, 94) 162=1×94+68, gcd(94, 68) 94=1×68+26, gcd(68, 26) 68=2×26+16, gcd(26, 16) 26=1×16+10, gcd(16, 10) 16=1×10+6, gcd(10, 6) 10=1×6+4, gcd(6, 4) 6=1×4+2, gcd(4, 2) 4=2×2+0, gcd(2, 0) 因此gcd(1970, 1066)=2。

2. 求乘法逆元 如果gcd(a, b)=1 ，则b在mod a下有乘法逆元（不妨设b<a），即存在一x (x<a)，使得bx≡1 mod a。推广的Euclid算法先求出gcd(a, b)，当gcd(a, b)=1时，则返回b的逆元。

例4.3 求gcd(1769, 550)。

4.1.6 中国剩余定理 中国剩余定理是数论中最有用的一个工具，定理说如果已知某个数关于一些两两互素的数的同余类集，就可重构这个数。 4.1.6 中国剩余定理 中国剩余定理是数论中最有用的一个工具，定理说如果已知某个数关于一些两两互素的数的同余类集，就可重构这个数。 例如：Z10中每个数都可从这个数关于2和5（10的两个互素的因子）的同余类重构。比如已知x关于2和5的同余类分别是[0]和[3]，即x mod 2≡0，x mod 5≡3。可知是偶数且被5除后余数是3，所以可得8是满足这一关系的惟一的x。

定理4.5（中国剩余定理） 设m1,m2,…,mk是两两互素的正整数， ，则一次同余方程组 对模M有惟一解: 其中ei满足

证明：设 ,i=1,2,…,k，由Mi的定 义得Mi 与mi是互素的，可知Mi在模mi下有惟一的 乘法逆元，即满足 的ei是惟一的。

下面证明对i∈{1,2,…,k}，上述x满足ai(mod mi)≡x。注意到当j≠i时，mi|Mj，即Mj≡0(mod mi)。所以 (Mj×ej mod mj) mod mi ≡((Mj mod mi)×((ej mod mj) mod mi)) mod mi ≡0 而(Mi×(ei mod mi)) mod mi≡(Mi×ei) mod mi≡1 所以x(mod mi)≡ai，即ai(mod mi)≡x

下面证明方程组的解是惟一的。设x’是方程组的另一解，即 x’ ≡ai (mod mi) (i=1,2,…,k) 由x≡ai (mod mi)得x’ -x≡0(mod mi)， 即mi|(x’ -x)。再根据mi两两互素，有M|(x’ -x)，即x’ -x≡0(mod M)，所以x’ (mod M)=x(mod M)。 (证毕) 中国剩余定理提供了一个非常有用的特性，即在模M下可将非常大的数x由一组小数(a1, a2,…, ak)表达。

例4.4 由以下方程组求x。 解： M=2·3·5·7=210，M1=105，M2=70，M3=42，M4=30,易求e1≡M-11 mod 2≡1,e2≡M-12mod 3≡1,e3≡M-13 mod 5≡3,e4≡M-14 mod 7≡4,所以 x mod 210≡ (105×1×1+70×1×2+42×3×3+30×4×5) mod 210≡173，或写成x≡173 mod 210。

例4.5 将973 mod 1813由模数分别为37和49的两个数表示。 解： 取x=973, M=1813, m1=37, m2=49。 由a1≡973 mod m1≡11, a2≡973 mod m2≡42 得x在模37和模49下的表达为（11, 42）。

4.1.7 离散对数 1. 求模下的整数幂 Euler定理指出如果gcd(a, n)=1，则aφ(n)≡1 mod n。现在考虑如下的一般形式: am≡1 mod n 如果a与n互素，则至少有一整数m（比如m=φ(n)）满足这一方程。称满足方程的最小正整数m为模n下a的阶。

例如： a=7，n=19，则易求出71≡7 mod 19,72≡11 mod 19,73≡1 mod 19，即7在模19下的阶为3。 由于73+j=73·7j≡7j mod 19, 所以74≡7 mod 19,75≡72 mod 19, …, 即从74 mod 19开始所求的幂出现循环，循环周期为3，即循环周期等于元素的阶。

ak≡(am)qar≡ar≡1(mod n) 定理4.6 设a的阶为m，则ak≡1 mod n的充要条件是k为m的倍数。 证明：设存在整数q，使得k=qm，则ak≡(am)q≡1 mod n。 反之，假定ak≡1 mod n，令k=qm+r,其中0<r≤m-1，那么 ak≡(am)qar≡ar≡1(mod n) 与m是阶矛盾。（证毕）

推论：a的阶m整除φ(n)。 如果a的阶m等于φ(n)，则称a为n的本原根。如果a是n的本原根，则 a,a2,…,aφ(n) 在mod n下互不相同且都与n互素。 特别地，如果a是素数p的本原根，则 a,a2,…,ap-1 在 mod p下都不相同。

例如：n=9，则φ(n)=6，考虑2在mod 9下的幂21 mod 9≡2,22 mod 9≡4 23 mod 9≡8,24 mod 9≡7，25 mod 9≡5,26 mod 9≡1。即2的阶为φ(9)，所以2为9的本原根。 例如： n=19，a=3在mod 19下的幂分别为 3，9，8，5，15，7，2，6，18，16，10，11，14，4，12，17，13，1。 即3的阶为18=φ(19)，所以3为19的本原根。

本原根不惟一。可验证除3外，19的本原根还有2，10，13，14，15。 注意并非所有的整数都有本原根，只有以下形式的整数才有本原根： 2,4,pα,2pα 其中p为奇素数。

2. 指标 首先回忆一下一般对数的概念，指数函数y=ax(a>0,a≠1)的逆函数称为以a为底x的对数，记为y=logax。对数函数有以下性质： loga1=0, logaa=1, logaxy=logax+logay, logaxy=ylogax 在模运算中也有类似的函数。设p是一素数，a是p的本原根，则a,a2,…,ap-1产生出1到p-1之间的所有值，且每一值只出现一次。因此对任意b∈{1,…,p-1}，都存在惟一的i(1≤i≤p-1)，使得b≡ai mod p。称i为模p下以a为底b的指标，记为i=inda,p(b)。

指标有以下性质： ① inda,p(1)=0。 ② inda,p(a)=1。 分别由以下关系得出： a0 mod p=1 mod p=1, a1 mod p=a。 以上假定模数p是素数，对于非素数也有类似的结论。

例4.6 设p=9，则φ(p)=6，a=2是p的一个本原根，a的不同的幂为（模9下） 20≡1,21≡2,22≡4,23≡8,24≡7,25≡5,26≡1 由此可得a的指数表如表4.3（a）所示。 重新排列表4.3（a），可求每一与9互素的数的指标如表4.3（b）所示。

证明：因a和p互素，所以a在模p下存在逆元a-1，在az≡aq mod p两边同乘以(a-1)q，得az-q≡1 mod p。由Euler定理aφ(p)≡1 mod p知存在一整数k，使得z-q≡kφ(p)，所以z≡q mod φ(p)。 由上述结论可得指标的以下两个性质： ③ inda,p(xy)=[inda,p(x)+inda,p(y)] mod φ(p)。 ④ inda,p(yr)=[r×inda,p(y)] mod φ(p)。

性质③的证明：设 由模运算的性质得： 所以inda,p(xy)=[inda,p(x)+inda,p(y)] mod φ(p) （证毕）

性质④是性质③的推广。 从指标的以上性质可见，指标与对数的概念极为相似。

3. 离散对数 设p是素数，a是p的本原根，即a1,a2,…,ap-1在 mod p下产生1到p-1的所有值，所以对b∈{1,…,p-1}，有惟一的i∈{1,…,p-1}使得b≡ai mod p。称i为模p下以a为底b的离散对数，记为i≡logab(mod p)。 当a、p、i已知时，用4.3.2节将介绍的快速指数算法可比较容易地求出b，但如果已知a、b和p，求i则非常困难。目前已知的最快的求离散对数算法其时间复杂度为： 所以当p很大时，该算法也是不可行的。

设n是一正整数，a小于n ，称a是n的平方剩余，如果方程 x2≡a (mod n) 有解。否则称为非平方剩余。 4.1.8 平方剩余 设n是一正整数，a小于n ，称a是n的平方剩余，如果方程 x2≡a (mod n) 有解。否则称为非平方剩余。

例如：x2≡1 mod 7有解x=1，x=6； x2≡2 mod 7有解x=3，x=4； x2≡3 mod 7无解； x2≡4 mod 7有解x=2，x=5； x2≡5 mod 7无解； x2≡6 mod 7无解。 可见共有3个数（1、2、4）是模7的平方剩余，且每个平方剩余都有两个平方根（即例中的x）。

容易证明，模p的平方剩余的个数为(p-1)/2，且与模p的非平方剩余的个数相等。如果a是模p的一个平方剩余，那么a恰有两个平方根，一个在0到(p-1)/2之间，另一个在(p-1)/2到(p-1)之间，且这两个平方根中的一个也是模p的平方剩余。

定义4.1 设p是素数，a是一整数，符号 的定义如下： 称符号 为Legendre符号。

例如： 计算 有一个简单公式： 例如：p=23，a=5，a(p-1)/2 mod p≡511 mod p=-1，所以5不是模23的平方剩余。 计算 有一个简单公式： 例如：p=23，a=5，a(p-1)/2 mod p≡511 mod p=-1，所以5不是模23的平方剩余。

Legendre符号有以下性质： 定理4.7 设p是奇素数，a和b都不能被p除尽，则 ① 若a≡b mod p，则 ② ③ ④ 证明从略。

以下定义的Jacobi符号是Legendre符号的推广。 定义4.2 设n是正整数，且 ，定义Jacobi符号为 其中右端的符号是Legendre符号。 当n为素数时，Jacobi符号就是Legendre符号。

Jacobi符号有以下性质： 定理4.8 设n是正合数，a和b是与n互素的整数，则 ① 若a≡b mod n，则 ② ③ ④ 对一些特殊的a，Jacobi符号可如下计算：

定理4.9（Jacobi符号的互反律） 设m、n均为大于2的奇数，则 若m≡n≡3 mod 4，则 ；否则 。

以上性质表明： 为了计算Jacobi符号（包括Legendre符号作为它的特殊情形），并不需要求素因子分解式。例如105虽然不是素数，在计算Legendre符号 时，可以先把它看作Jacobi符号来计算，由上述两个定理得

一般在计算 时，如果有必要，可用m mod n代替m，而互反律用以减小 的分母。 可见，引入Jacobi符号对计算Legendre符号是十分方便的，但应强调指出Jacobi符号和Legendre符号的本质差别是： Jacobi符号 不表示方程x2≡a mod n是否有解。比如n=p1p2，a关于p1和p2都不是平方剩余，即x2≡a mod p1和x2≡a mod p2都无解，由中国剩余定理知x2≡a mod n也无解。但是，由于 ,所以 。即x2≡a mod n虽无解，但Jacobi符号 却为1。

例4.7 考虑方程x2≡2 mod 3599，由于3599=59×61，所以方程等价于方程组 由于 ，所以方程组无解，但Jacobi符号

下面考虑公钥密码体制中一个非常重要的问题。 设n是两个大素数p和q的乘积。由上述结论，1到p-1之间有一半数是模p的平方剩余（记这些数的集合为 ） ，另一半是模p的非平方剩余（记这些数的集合为 ） ，对q也有类似结论（分别记两个集合为 和 ） 。另一方面，a是模n的平方剩余，当且仅当a既是模p的平方剩余也是模q的平方剩余,即 。

设a是模n的平方剩余，即存在x使得x2≡a mod n成立，因a既是模p的平方剩余，又是模q的平方剩余，所以存在y、z，使得(±y)2≡a mod p,(±z)2≡a mod q，当p≡q≡3 mod 4时，y和z可容易地求出.因此 x≡±y mod p,x≡±z mod q 由中国剩余定理可求得a mod n的4个平方根，记为±u mod n和±w mod n，且u±w mod n。 以上结果表明，已知n的分解n=pq，且a是模n的平方剩余，就可求得a mod n的4个平方根。

下面考虑相反的问题，即已知a mod n的两个不同的平方根（u mod n和w mod n，且u±w mod n），就可分解n。事实上由u2≡w2 mod n得(u+w)(u-w)≡0 mod n，但n不能整除u+w也不能整除u-w，所以必有 p|(u+w),q|(u-w) 或 p|(u-w),q|(u+w) 所以 gcd(n,u+w)=p,gcd(n，u-w)=q 或 gcd(n,u-w)=p,gcd(n,u+w)=q 因此得到了n的分解式。

将以上讨论总结为： 定理4.10 当p≡q≡3 mod 4时，求解方程 x2≡a mod n 与分解n是等价的。 第2个重要结论是： 当p≡q≡3 mod 4时，a mod n的两个不同的平方根u和w的Jacobi符号有如下关系： 证明： 由以上讨论知，u、w满足 p|(u+w),q|(u-w) 或 p|(u-w),q|(u+w) 即u≡-w mod p,u≡w mod q或u≡w mod p,u≡-w mod q。

若为第一种情况， 设 ，则 ，所以上式等于 （证毕） 同理可证第二种情况。 设 ，则 ，所以上式等于 （证毕） 同理可证第二种情况。

4.2 公钥密码体制的基本概念 在公钥密码体制以前的整个密码学史中，所有的密码算法，包括原始手工计算的、由机械设备实现的以及由计算机实现的，都是基于代换和置换这两个基本工具。而公钥密码体制则为密码学的发展提供了新的理论和技术基础，一方面公钥密码算法的基本工具不再是代换和置换，而是数学函数；另一方面公钥密码算法是以非对称的形式使用两个密钥，两个密钥的使用对保密性、密钥分配、认证等都有着深刻的意义。可以说公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的革命。

公钥密码体制的概念是在解决单钥密码体制中最难解决的两个问题时提出的，这两个问题是密钥分配和数字签字。 单钥密码体制在进行密钥分配时, 要求通信双方或者已经有一个共享的密钥，或者可籍助于一个密钥分配中心。对第一个要求，常常可用人工方式传送双方最初共享的密钥，这种方法成本很高，而且还完全依赖信使的可靠性。第二个要求则完全依赖于密钥分配中心的可靠性。 第二个问题数字签字考虑的是如何为数字化的消息或文件提供一种类似于为书面文件手书签字的方法。 1976年W.Diffie和M.Hellman对解决上述两个问题有了突破，从而提出了公钥密码体制。

4.2.1 公钥密码体制的原理 公钥密码算法的最大特点是采用两个相关密钥将加密和解密能力分开，其中一个密钥是公开的，称为公开密钥，简称公开钥，用于加密；另一个密钥是为用户专用，因而是保密的，称为秘密密钥，简称秘密钥，用于解密。因此公钥密码体制也称为双钥密码体制。算法有以下重要特性： 已知密码算法和加密密钥，求解密密钥在计算上是不可行的。

图4-1 公钥体制加密的框图

加密过程有以下几步： ① 要求接收消息的端系统，产生一对用来加密和解密的密钥，如图中的接收者B，产生一对密钥PKB，SKB，其中PKB是公开钥，SKB是秘密钥。 ② 端系统B将加密密钥（如图中的PKB）予以公开。另一密钥则被保密（图中的SKB）。 ③ A要想向B发送消息m，则使用B的公开钥加密m，表示为c=EPKB[m],其中c是密文，E是加密算法。 ④ B收到密文c后，用自己的秘密钥SKB解密，表示为m=DSKB[c]，其中D是解密算法。

图4-2 公钥密码体制认证框图

因为只有B知道SKB，所以其他人都无法对c解密。 公钥加密算法不仅能用于加、解密，还能用于对发方A发送的消息m提供认证，如图4.2所示。用户A用自己的秘密钥SKA对m加密，表示为 c=ESKA[m] 将c发往B。B用A的公开钥PKA对c解密，表示为 m=DPKA[c]

因为从m得到c是经过A的秘密钥SKA加密，只有A才能做到。因此c可当做A对m的数字签字。另一方面，任何人只要得不到A的秘密钥SKA就不能篡改m，所以以上过程获得了对消息来源和消息完整性的认证。

在实际应用中，特别是用户数目很多时，以上认证方法需要很大的存储空间，因为每个文件都必须以明文形式存储以方便实际使用，同时还必须存储每个文件被加密后的密文形式即数字签字，以便在有争议时用来认证文件的来源和内容。改进的方法是减小文件的数字签字的大小，即先将文件经过一个函数压缩成长度较小的比特串，得到的比特串称为认证符。认证符具有这样一个性质： 如果保持认证符的值不变而修改文件这在计算上是不可行的。用发送者的秘密钥对认证符加密，加密后的结果为原文件的数字签字。这一内容在第7章中会详细介绍。

以上认证过程中，由于消息是由用户自己的秘密钥加密的，所以消息不能被他人篡改，但却能被他人窃听。这是因为任何人都能用用户的公开钥对消息解密。为了同时提供认证功能和保密性，可使用双重加、解密。如图4.3所示。

图4.3 公钥密码体制的认证、保密框图

发方首先用自己的秘密钥SKA对消息m加密，用于提供数字签字。再用收方的公开钥PKB第2次加密，表示为 c=EPKB[ESKA[m]] 解密过程为 m=DPKA[DSKB[c]] 即收方先用自己的秘密钥,再用发方的公开钥对收到的密文两次解密。

4.2.2 公钥密码算法应满足的要求 公钥密码算法应满足以下要求: ① 接收方B产生密钥对（公开钥PKB和秘密钥SKB）在计算上是容易的。 4.2.2 公钥密码算法应满足的要求 公钥密码算法应满足以下要求: ① 接收方B产生密钥对（公开钥PKB和秘密钥SKB）在计算上是容易的。 ② 发方A用收方的公开钥对消息m加密以产生密文c，即 c=EPKB[m] 在计算上是容易的。 ③ 收方B用自己的秘密钥对c解密，即m=DSKB[c]在计算上是容易的。

EPKB[DSKB(m)]=DSKB[EPKB(m)] ④ 敌手由B的公开钥PKB求秘密钥SKB在计算上是不可行的。 ⑤ 敌手由密文c和B的公开钥PKB恢复明文m在计算上是不可行的。 ⑥ 加、解密次序可换，即 EPKB[DSKB(m)]=DSKB[EPKB(m)] 其中最后一条虽然非常有用，但不是对所有的算法都作要求。

单向函数是两个集合X、Y之间的一个映射，使得Y中每一元素y都有惟一的一个原像x∈X，且由x易于计算它的像y，由y计算它的原像x是不可行的。 这里所说的易于计算是指函数值能在其输入长度的多项式时间内求出，即如果输入长n比特，则求函数值的计算时间是na的某个倍数，其中a是一固定的常数。这时称求函数值的算法属于多项式类P，否则就是不可行的。例如，函数的输入是n比特，如果求函数值所用的时间是2n的某个倍数，则认为求函数值是不可行的。

注意这里的易于计算和不可行两个概念与计算复杂性理论中复杂度的概念极为相似，然而又存在着本质的区别。在复杂性理论中，算法的复杂度是以算法在最坏情况或平均情况时的复杂度来度量的。而在此所说的两个概念是指算法在几乎所有情况下的情形。 称一个函数是陷门单向函数，是指该函数是易于计算的，但求它的逆是不可行的，除非再已知某些附加信息。当附加信息给定后，求逆可在多项式时间完成。

总结为： 陷门单向函数是一族可逆函数fk，满足 ① Y=fk(X)易于计算（当k和X已知时）。 ② X=f-1k(Y)易于计算（当k和Y已知时）。 ③ X=f-1k(Y)计算上是不可行的（当Y已知但k未知时）。 因此，研究公钥密码算法就是要找出合适的陷门单向函数。

4.2.3 对公钥密码体制的攻击 和单钥密码体制一样，如果密钥太短，公钥密码体制也易受到穷搜索攻击。因此密钥必须足够长才能抗击穷搜索攻击。然而又由于公钥密码体制所使用的可逆函数的计算复杂性与密钥长度常常不是呈线性关系，而是增大得更快。所以密钥长度太大又会使得加解密运算太慢而不实用。因此公钥密码体制目前主要用于密钥管理和数字签字。 对公钥密码算法的第2种攻击法是寻找从公开钥计算秘密钥的方法。目前为止，对常用公钥算法还都未能够证明这种攻击是不可行的。

还有一种仅适用于对公钥密码算法的攻击法，称为可能字攻击。例如对56比特的DES密钥用公钥密码算法加密后发送，敌手用算法的公开钥对所有可能的密钥加密后与截获的密文相比较。如果一样，则相应的明文即DES密钥就被找出。因此不管公钥算法的密钥多长，这种攻击的本质是对56比特DES密钥的穷搜索攻击。抵抗方法是在欲发送的明文消息后添加一些随机比特。

4.3 RSA算法 RSA算法是1978年由R.Rivest, A.Shamir和L.Adleman提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。

算法描述 l     密钥的产生 1）选大素数p和q (各100～200位十进制数字)，计算 n=p×q , (n)=(p－1)(q－1) 随机选一整数e， 1e<(n)，((n), e)=1。因而在模(n)下，e有逆元. 计算 d=e -1 (mod (n)) 取公钥为{e ， n}。秘密钥为d (p, q不再需要，可以销毁)

加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n。然后对每个明文分组m，作加密运算 c=me mod n l   解密 对密文分组c的解密运算为 m=cd mod n

证明： 由加密过程知c≡me mod n，所以 cd mod n≡med mod n≡mkφ(n)+1 mod n 下面分两种情况： 下面证明RSA算法中解密过程的正确性。 证明： 由加密过程知c≡me mod n，所以 cd mod n≡med mod n≡mkφ(n)+1 mod n 下面分两种情况： ① m与n互素，则由Euler定理得 mφ(n)≡1 mod n,mkφ(n)≡1 mod n,mkφ(n)+1≡m mod n 即cd mod n≡m。 ② gcd(m,n)≠1，先看gcd(m,n)=1的含义，由于n=pq，所以gcd(m,n)=1意味着m不是p的倍数也不是q的倍数。因此gcd(m,n)≠1意味着m是p的倍数或q的倍数，不妨设m=tp，其中t为一正整数。此时必有gcd(m,q)=1，否则m也是q的倍数，从而是pq的倍数，与m<n=pq矛盾。

由gcd(m,q)=1及Euler定理得mφ(q)≡1 mod q，所以 mkφ(q)≡1 mod q,［mkφ(q)］φ(p)≡1 mod q, mkφ(n)≡1 mod q 因此存在一整数r，使得mkφ(n)=1+rq，两边同乘以m=tp得 mkφ(n)+1=m+rtpq=m+rtn 即mkφ(n)+1≡m mod n，所以cd mod n≡m。(证毕)

例4.8 选p=7，q=17。求n=p×q=119，φ(n)=(p-1)(q-1)=96。取e=5，满足1<e<φ(n)，且gcd(φ(n),e)=1。确定满足d·e=1 mod 96且小于96的d，因为77×5=385=4×96+1，所以d为77，因此公开钥为{5，119}，秘密钥为{77，119}。设明文m=19，则由加密过程得密文为 c≡195 mod 119≡2476099 mod 119≡66 解密为 6677mod 119≡19

(a×b) mod n=[(a mod n)×(b mod n)] mod n 4.3.2 RSA算法中的计算问题 1. RSA的加密与解密过程 RSA的加密、解密过程都为求一个整数的整数次幂，再取模。如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。如上例中解密运算6677 mod 119，先求6677再取模，则中间结果就已远远超出了计算机允许的整数取值范围。而用模运算的性质： (a×b) mod n=[(a mod n)×(b mod n)] mod n 就可减小中间结果。

再者，考虑如何提高加、解密运算中指数运算的有效性。例如求x16，直接计算的话需做15次乘法。然而如果重复对每个部分结果做平方运算即求x，x2，x4，x8，x16则只需4次乘法。 求am可如下进行，其中a，m是正整数： 将m表示为二进制形式bk bk-1…b0，即 m=bk2k+bk-12k-1+…+b12+b0 因此

例如：19=1×24+0×23+0×22+1×21+1×20，所以 a19=((((a1)2a0)2a0)2a1)2a1 从而可得以下快速指数算法： c=0; d=1； For i=k downto 0 d0 { c=2×c; d=(d×d) mod n; if bi =1 then { c=c+1; d=(d×a) mod n } return d.

其中d是中间结果，d的终值即为所求结果。c在这里的作用是表示指数的部分结果，其终值即为指数m，c对计算结果无任何贡献，算法中完全可将之去掉。

例4.9 求7560 mod 561。 将560表示为1000110000， 所以7560 mod 561=1。

2. RSA密钥的产生 产生密钥时，需要考虑两个大素数p、q的选取，以及e的选取和d的计算。 因为n=pq在体制中是公开的，因此为了防止敌手通过穷搜索发现p、q，这两个素数应是在一个足够大的整数集合中选取的大数。如果选取p和q为10100左右的大素数，那么n的阶为10200，每个明文分组可以含有664位（10200≈2664），即83个8比特字节，这比DES的数据分组（8个8比特字节）大得多，这时就能看出RSA算法的优越性了。因此如何有效地寻找大素数是第一个需要解决的问题。

寻找大素数时一般是先随机选取一个大的奇数（例如用伪随机数产生器），然后用素性检验算法检验这一奇数是否为素数，如果不是则选取另一大奇数，重复这一过程，直到找到素数为止。素性检验算法通常都是概率性的，但如果算法被多次重复执行，每次执行时输入不同的参数，算法的检验结果都认为被检验的数是素数，那么就可以比较有把握地认为被检验的数是素数。例如4.1.4节中介绍的Miller-Rabin算法。

可见寻找大素数是一个比较繁琐的工作。然而在RSA体制中，只有在产生新密钥时才需执行这一工作。 p和q决定出后，下一个需要解决的问题是如何选取满足1<e<φ(n)和gcd(φ(n),e)=1的e，并计算满足d·e≡1 mod φ(n)的d。这一问题可由推广的Euclid算法完成。

4.3.3 RSA的安全性 RSA的安全性是基于分解大整数的困难性假定，之所以为假定是因为至今还未能证明分解大整数就是NP问题，也许有尚未发现的多项式时间分解算法。如果RSA的模数n被成功地分解为p×q，则立即获得φ(n)=(p-1)(q-1)，从而能够确定e模φ(n)的乘法逆元d，即d≡e-1 mod φ(n)，因此攻击成功。

随着人类计算能力的不断提高，原来被认为是不可能分解的大数已被成功分解。例如RSA-129（即n为129位十进制数，大约428个比特）已在网络上通过分布式计算历时8个月于1994年4月被成功分解，RSA-130 已于1996年4月被成功分解。RSA-140 已于1999年2月被成功分解，RSA-155（512比特） 已于1999年8月被成功分解，得到了两个78位（十进制）的素数。

对于大整数的威胁除了人类的计算能力外，还来自分解算法的进一步改进。分解算法过去都采用二次筛法，如对RSA-129的分解。而对RSA-130的分解则采用了一个新算法，称为推广的数域筛法，该算法在分解RSA130时所做的计算仅比分解RSA-129多10%。将来也可能还有更好的分解算法，因此在使用RSA算法时对其密钥的选取要特别注意其大小。估计在未来一段比较长的时期，密钥长度介于1024比特至2048比特之间的RSA是安全的。

是否有不通过分解大整数的其他攻击途径？下面证明由n直接确定φ(n)等价于对n的分解。 设n=p×q中，p>q，由φ(n)=(p-1)(q-1)，则有 p+q=n-φ(n)+1 以及 由此可见，由p、q确定φ(n)和由φ(n)确定p、q是等价的。

为保证算法的安全性，还对p和q提出以下要求： 则 也小，因此 稍大于 n ， 稍大于 。可得n的如下分解步骤： ① 顺序检查大于 的每一整数x，直到找到一个x使得x2-n是某一整数（记为y）的平方。 ② 由x2-n=y2，得n=(x+y)(x-y)。

（2） p-1和q-1都应有大素因子 这是因为RSA算法存在着可能的重复加密攻击法。设攻击者截获密文c，可如下进行重复加密：

若 ，即 ，则 有 ，即 ，所以在上 述重复加密的倒数第2步就已恢复出明文m，这种攻击法只有在t较小时才是可行的。为抵抗这种攻击，p、q的选取应保证使t很大。

设m在模n下阶为k，由 得 ，所以k|(et-1)，即et≡1(mod k)，t取为满足上式的最小值（为e在模k下的阶）。又当e与k互素时t|φ(k)。为使t大，k就应大且φ(k)应有大的素因子。又由k|φ(n)，所以为使k大，p-1和q-1都应有大的素因子。 此外，研究结果表明，如果e<n且d<n1/4，则d能被容易地确定。

4.3.4 对RSA的攻击 RSA存在以下两种攻击，并不是因为算法本身存在缺陷，而是由于参数选择不当造成的。 1. 共模攻击 在实现RSA时，为方便起见，可能给每一用户相同的模数n，虽然加解密密钥不同，然而这样做是不行的。

设两个用户的公开钥分别为e1和e2，且e1和e2互素（一般情况都成立），明文消息是m，密文分别是c1≡me1(mod n) 敌手截获c1和c2后，可如下恢复m。用推广的Euclid算法求出满足 re1+se2=1 的两个整数r和s，其中一个为负，设为r。再次用推广的Euclid算法求出c-11，由此得 (c-11)-rcs2≡m(mod n)。

2. 低指数攻击 假定将RSA算法同时用于多个用户（为讨论方便，以下假定3个），然而每个用户的加密指数（即公开钥）都很小。设3个用户的模数分别为ni (i=1,2,3)，当i≠j时，gcd(ni,nj)=1，否则通过gcd(ni,nj)有可能得出ni和nj的分解。设明文消息是m，密文分别是 c1≡m3(mod n1) c2≡m3(mod n2) c3≡m3(mod n3) 由中国剩余定理可求出m3(mod n1n2n3)。由于m3<n1n2n3，可直接由m3开立方根得到m。

4.4 背包密码体制 设A=(a1,a2,…,an)是由n个不同的正整数构成的n元组，s是另一已知的正整数。背包问题就是从A中求出所有的ai，使其和等于s。其中A称为背包向量，s是背包的容积。 例如,A=（43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523），s=3231。由于 3231=129+473+903+561+1165 所以从A中找出的满足要求的数有129、473、903、561、1165。

原则上讲，通过检查A的所有子集，总可找出问题的解（如果有解的话）。本例A的子集共有210=1024个（包括空集）。然而如果A中元素个数n很大，子集个数2n将非常大。如A中有300个元素，A的子集有2300。寻找满足要求的A的子集没有比穷搜索更好的算法，因此背包问题是NPC问题。

由背包问题构造公钥密码体制同样是要构造一个单向函数f，将x(1≤x≤2n-1)写成长为n的二元表示0…001,0…010，0…011,…,1…111, f(x)定义为A中所有ai的和，其中x的二元表示的第i位为1，即 f(1)=f(0…001)=an f(2)=f(0…010)=an-1 f(3)=f(0…011)=an-1+an  … f(2n-1)=f(1…111)=a1+a2+…+an 使用向量乘，有f(x)=A·Bx，其中Bx是将x的二元表示写成的列向量。

上例中f(364) = f(0101101100) = 129+473+903+561+1165 = 3231， 类似地可求出: f(609)=2942, f(686)=3584, f(32)=903, f(46)=3326, f(128)=215, f(261)=2817, f(44)=2629, f(648)=819。 由f的定义可见，已知x很容易求f(x)，但已知f(x)求x就是要解背包问题。当然在实际应用中，n不能太小，比如说，至少为200。

用f对明文消息m加密时，首先将m写成二元表示，再将其分成长为n的分组（最后一个分组不够长的话，可在后面填充一些0），然后求每一分组的函数值，以函数值作为密文分组。 例如，明文消息是英文文本，则可将每个字母用其在字母表中的序号表示，再将该序号转换为二进制形式（5位即可），如表4.5所示，其中符号‘ ’表示空格。

背包向量仍取上例中的A，设待加密的明文是SAUNA AND HEALTH。因为A长为10，所以应将明文分成长为10比特（即两个明文字母）的分组SA，UN，A‘ ’，AN，D‘ ’，HE，AL，TH相应的二元序列为 1001100001，1010101110，0000100000，0000101110， 0010000000，0100000101，0000101100，1010001000。

分别对以上二元序列作用于函数f，得密文为 （2942，3584，903，3326，215，2817，2629，819）。 解密运算分别以每一密文分组做为背包容积，求背包问题的解。为使接收方能够解密，就需找出单向函数的陷门。为此需引入一种特殊类型的背包向量。 定义背包向量A=(a1,a2,…,an)称为超递增的，如果

超递增背包向量对应的背包问题很容易通过以下算法（称为贪婪算法）求解。 已知s为背包容积，对A从右向左检查每一元素，以确定是否在解中。若s≥an，则an在解中，令xn=1；若s<an，则an不在解中，令xn=0。下面令 对an-1重复上述过程，一直下去，直到检查出a1是否在解中。检查结束后得 x=(x1x2…xn)，Bx=(x1x2…xn)T。

然而，敌手如果也知道超递增背包向量，同样也很容易解密。为此可用模乘对A进行伪装，模乘的模数k和乘数t皆取为常量，满足k>∑ai，gcd(t,k)=1，即t在模k下有乘法逆元。设 bi ≡t·ai mod k, i=1,2,…,n 得一新的背包向量B=(b1,b2,…,bn)，记为B≡t·A mod k，用户以B作为自己的公开钥。

c=f(x)=B·Bx≡t·A·Bx mod k 例4.10 A=(1, 3, 5, 11, 21, 44, 87, 175, 349, 701)是一超递增背包向量，取k=1590，t=43， gcd(43, 1590)=1，得 B=(43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523)。 在得到B后，对明文分组x=(x1x2…xn)的加密运算为 c=f(x)=B·Bx≡t·A·Bx mod k 对单向函数f(x)，t、t-1和k可作为其秘密的陷门信息，即解密密钥。解密时首先由s≡t-1 c mod k，求出s作为超递增背包向量A的容积，再解背包问题即得x=(x1x2…xn)。这是因为t-1 c mod k≡t-1tABx mod k≡ABx mod k，而由k>∑ai，知ABx<k，所以t-1c mod k=ABx，是惟一的。

例4.11 接例4.10，A=(1, 3, 5, 11, 21, 44, 87, 175, 349, 701)是一超递增背包向量，k=1590，t=43，得t-1 ≡37 mod 1590，设用户收到的密文是(2942, 3584, 903, 3326, 215, 2817, 2629, 819) ，由 37×2942≡734 mod 1590, 37×3584≡638 mod 1590, 37×903≡21 mod 1590, 37×3326≡632 mod 1590, 37×215 ≡5 mod 1590, 37×2817≡879 mod 1590, 37×2629≡283 mod 1590, 37×819≡93 mod 1590, 得(734, 638, 21, 632, 5, 879, 283, 93)。

取s=734，由734>701，得x10=1；令s=734-701=33，由33<349，得x9=0；重复该过程得第一个明文分组是1001100001，它对应的英文文本是SA；类似地得其他明文分组，解密结果为SAUNA AND HEALTH。

背包密码体制是Diffie和Hellman 1976年提出公钥密码体制的设想后的第一个公钥密码体制，由Merkle和Hellman 1978年提出。然而又过了两年该体制即被破译，破译的基本思想是不必找出正确的模数k和乘数t（即陷门信息），只须找出任意模数k′和乘数t′，使得用k′和t′去乘公开的背包向量B时，能够产生超递增的背包向量即可。

4.5 Rabin密码体制 对RSA密码体制，n被分解成功，该体制便被破译，即破译RSA的难度不超过大整数的分解。但还不能证明破译RSA和分解大整数是等价的，虽然这一结论已得到普遍共识。Rabin密码体制已被证明对该体制的破译与分解大整数一样困难。

Rabin密码体制是对RSA的一种修正，它有以下两个特点： 它不是以一一对应的单向陷门函数为基础，对同一密文，可能有两个以上对应的明文; 破译该体制等价于对大整数的分解。 RSA中选取的公开钥e满足1<e<φ(n)，且gcd(e,φ(n))=1。Rabin密码体制则取e=2。

1. 密钥的产生 随机选择两个大素数p、q，满足p≡q≡3 mod 4，即这两个素数形式为4k+3；计算n=p×q。以n作为公开钥，p、q作为秘密钥。 2. 加密 c≡m2 mod n 其中m是明文分组，c是对应的密文分组。 3. 解密 求c模n的平方根，即解x2≡c mod n，

由中国剩余定理知解x2≡c mod n, 等价于解方程组 由于p≡q≡3 mod 4，下面将看到，方程组的解可容易地求出，其中每个方程都有两个解，即

经过组合可得4个同余方程组 由中国剩余定理可解出每一方程组的解，共有4个，即每一密文对应的明文不惟一。为了有效地确定明文,可在m中加入某些信息,如发送者的身份号、接收者的身份号、日期、时间等。

下面证明，当p≡q≡3 mod 4，两个方程 x2≡c mod p,x2≡c mod q 的平方根都可容易地求出。

所以 和 是方程x2≡c mod p的两个 根。同理 和 是方程x2≡c mod q的两个 根。 由4.1.8节知，求解方程x2≡a mod n与分解n是等价的，所以破译Rabin密码体制的困难程度等价于大整数n的分解。

4.6 椭圆曲线密码体制 为保证RSA算法的安全性，它的密钥长度需一再增大，使得它的运算负担越来越大。相比之下，椭圆曲线密码体制ECC（elliptic curve cryptography）可用短得多的密钥获得同样的安全性，因此具有广泛的应用前景。ECC已被IEEE公钥密码标准P1363采用。

4.6.1 椭圆曲线 椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似。一般来讲，椭圆曲线的曲线方程是以下形式的三次方程： y2+axy+by=x3+cx2+dx+e (4.1) 其中a，b，c，d，e是满足某些简单条件的实数。定义中包括一个称为无穷点的元素，记为O。图4.4 是椭圆曲线的两个例子。

图4.4 椭圆曲线的两个例子

从图可见，椭圆曲线关于x轴对称。 椭圆曲线上的加法运算定义如下： 如果其上的3个点位于同一直线上，那么它们的和为O。 进一步可如下定义椭圆曲线上的加法律（加法法则）： ① O为加法单位元，即对椭圆曲线上任一点P，有P+O=P。 ② 设P1=(x,y)是椭圆曲线上的一点, 它的加法逆元定义为P2=-P1=(x, -y)。 这是因为P1、P2的连线延长到无穷远时，得到椭圆曲线上的另一点O，即椭圆曲线上的3点P1、P2，O共线，所以P1+P2+O=O，P1+P2=O，即P2=-P1。 由O+O=O，还可得O=-O

③ 设Q和R是椭圆曲线上x坐标不同的两点，Q+R的定义如下： 画一条通过Q、R的直线与椭圆曲线交于P1（这一交点是惟一的，除非所做的直线是Q点或R点的切线，此时分别取P1=Q和P1=R）。由Q+R+P1=O得Q+R=-P1。 ④ 点Q的倍数定义如下： 在Q点做椭圆曲线的一条切线，设切线与椭圆曲线交于点S，定义2Q=Q+Q=-S。类似地可定义3Q=Q+Q+Q+，…，等。 以上定义的加法具有加法运算的一般性质，如交换律、结合律等。

4.6.2 有限域上的椭圆曲线 密码中普遍采用的是有限域上的椭圆曲线，有限域上的椭圆曲线是指曲线方程定义式(4.1)中，所有系数都是某一有限域GF(p)中的元素（其中p为一大素数）。其中最为常用的是由方程 y2≡x3+ax+b(mod p) (a,b∈GF(p),4a3+27b2(mod p)≠0) (4.2) 定义的曲线。

例4.12 p=23，a=b=1，4a3+27b2(mod 23)≡8≠0 ，方程(4.2)为y2≡x3+x+1，其图形是连续曲线，由图4.4(b)所示。 然而我们感兴趣的是曲线在第一象限中的整数点。设Ep(a,b)表示方程(4.2)所定义的椭圆曲线上的点集{(x,y)|0≤x<p,0≤y<p，且x,y均为整数}并上无穷远点O。本例中E23(1,1)由表4.6给出，表中未给出O

一般来说，Ep(a,b)由以下方式产生： ① 对每一x(0≤x<p且x为整数），计算x3+ax+b(mod p)。 ② 决定①中求得的值在模p下是否有平方根，如果没有，则曲线上没有与这一x相对应的点；如果有，则求出两个平方根（y=0 时只有一个平方根）。

Ep(a,b)上的加法定义如下： 设P，Q∈Ep(a,b)，则 ① P+O=P。 ② 如果P=(x,y)，那么(x, y)+(x, -y)=O，即 (x, -y)是P的加法逆元，表示为-P。 由Ep(a,b)的产生方式知，-P也是Ep(a,b)中的点，如上例，P=(13,7)∈E23(1,1)，-P=(13, -7)，而-7 mod 23≡16，所以-P=(13, 16)，也在E23(1,1)中。

③ 设P=(x1,y1)，Q=(x2,y2)，P≠-Q，则P+Q=(x3,y3)由以下规则确定： x3≡λ2-x1-x2(mod p) y3≡λ(x1-x3)-y1(mod p) 其中

例4.13 仍以E23(1,1)为例，设P=(3,10)，Q=(9,7)，则 所以P+Q=（17,20），仍为E23(1,1)中的点。

若求2P则 所以2P=(7,12)。

倍点运算仍定义为重复加法，如 4P=P+P+P+P。 从例4.13看出，加法运算在E23(1,1)中是封闭的，且能验证还满足交换律。对一般的Ep(a,b)，可证其上的加法运算是封闭的、满足交换律，同样还能证明其上的加法逆元运算也是封闭的，所以Ep(a,b)是一个Abel群。

4.7.5 椭圆曲线上的密码 为使用椭圆曲线构造密码体制，需要找出椭圆曲线上的数学困难问题。 4.7.5 椭圆曲线上的密码 为使用椭圆曲线构造密码体制，需要找出椭圆曲线上的数学困难问题。 在椭圆曲线构成的Abel群Ep(a,b)上考虑方程Q=kP，其中P，Q∈Ep(a,b)，k<p，则由k和P易求Q，但由P、Q求k则是困难的，这就是椭圆曲线上的离散对数问题，可应用于公钥密码体制。Diffie-Hellman密钥交换和ElGamal密码体制是基于有限域上离散对数问题的公钥体制，下面考虑如何用椭圆曲线来实现这两种密码体制。

1. DiffieHellman密钥交换 首先取一素数p≈2180和两个参数a、b，则得方程(4.2)表达的椭圆曲线及其上面的点构成的Abel群Ep(a,b)。第2步，取Ep(a,b)的一个生成元G(x1,y1)，要求G的阶是一个非常大的素数，G的阶是满足nG=O的最小正整数n。Ep(a,b)和G作为公开参数。

两用户A和B之间的密钥交换如下进行： ① A选一小于n的整数nA，作为秘密钥，并由PA=nAG产生Ep(a,b)上的一点作为公开钥。 ② B类似地选取自己的秘密钥nB和公开钥PB。 ③ A、B分别由K=nAPB和K=nBPA产生出双方共享的秘密钥。 这是因为K=nAPB=nA(nBG)=nB(nAG)=nBPA。 攻击者若想获取K，则必须由PA和G求出nA，或由PB和G求出nB，即需要求椭圆曲线上的离散对数，因此是不可行的。

例4.14 p=211，Ep(0,-4)，即椭圆曲线为y2≡x3-4，G=(2,2)是E211(0,-4)的阶为241的一个生成元，即241G=O。A的秘密钥取为nA=121，公开钥为PA=121(2,2)=(115,48)。B的秘密钥取为nB=203，公开钥为PB=203(2,2)=(130,203)。由此得到的共享密钥为121(130,203)=203(115,48)=(161,169)，即共享密钥是一对数。如果将这一密钥用作单钥加密的会话密钥，则可简单地取其中的一个，如取x坐标，或取x坐标的某一简单函数。

2. ElGamal密码体制 (1) ElGamal密码体制的原理 密钥产生过程： 首先选择一素数p以及两个小于p的随机数g和x，计算y≡gx mod p。以(y, g, p)作为公开密钥，x作为秘密密钥。 加密过程： 设欲加密明文消息M，随机选一与p-1互素的整数k，计算C1≡gk mod p,C2≡ykM mod p，密文为C=(C1,C2)。 解密过程： 这是因为

(2) 利用椭圆曲线实现ElGamal密码体制 首先选取一条椭圆曲线，并得Ep(a,b)，将明文消息m通过编码嵌入到曲线上得点Pm，再对点Pm做加密变换。 取Ep(a,b)的一个生成元G，Ep(a,b)和G作为公开参数。

Pm+kPA-nAkG=Pm+k(nAG)-nAkG=Pm 用户A选nA作为秘密钥，并以PA=nAG作为公开钥。任一用户B若想向A发送消息Pm，可选取一随机正整数k，产生以下点对作为密文： Cm={kG,Pm+kPA} A解密时，以密文点对中的第二个点减去用自己的秘密钥与第一个点的倍乘，即 Pm+kPA-nAkG=Pm+k(nAG)-nAkG=Pm 攻击者若想由Cm得到Pm，就必须知道k。而要得到k，只有通过椭圆曲线上的两个已知点G和kG，这意味着必须求椭圆曲线上的离散对数，因此不可行。

例4.15 取p=751，Ep(-1,188)，即椭圆曲线为y2≡x3-x+188,Ep(-1,188)的一个生成元是G=(0,376)，A的公开钥为PA=(201,5)。假定B已将欲发往A的消息嵌入到椭圆曲线上的点Pm=(562,201)，B选取随机数k=386，由kG=386(0,376)=(676,558)， Pm+kPA=(562，201)+386(201,5)=(385,328)， 得密文为{(676,558),(385,328)}。

3. 椭圆曲线密码体制的优点 与基于有限域上离散对数问题的公钥体制（如Diffie-Hellman密钥交换和ElGamal密码体制）相比，椭圆曲线密码体制有如下优点。

（1） 安全性高 攻击有限域上的离散对数问题可以用指数积分法，其运算复杂度为 ，其中p是模数（为素数）。而它对椭圆曲线上的离散对数问题并不有效。目前攻击椭圆曲线上的离散对数问题的方法只有适合攻击任何循环群上离散对数问题的大步小步法，其运算复杂度为 ，其中pmax是椭圆曲线所形成的Abel群的阶的最大素因子。因此，椭圆曲线密码体制比基于有限域上的离散对数问题的公钥体制更安全。

(2) 密钥量小 由攻击两者的算法复杂度可知，在实现相同的安全性能条件下，椭圆曲线密码体制所需的密钥量远比基于有限域上的离散对数问题的公钥体制的密钥量小。

(3) 灵活性好 有限域GF(q)一定的情况下，其上的循环群（即GF(q)-{0}）就定了。而GF(q)上的椭圆曲线可以通过改变曲线参数，得到不同的曲线，形成不同的循环群。因此，椭圆曲线具有丰富的群结构和多选择性。

正是由于椭圆曲线具有丰富的群结构和多选择性，并可在保持和RSA/DSA体制同样安全性能的前提下大大缩短密钥长度（目前160比特足以保证安全性），因而在密码领域有着广阔的应用前景。表4.7给出了椭圆曲线密码体制和RSA/DSA体制在保持同等安全的条件下各自所需的密钥的长度。

习题 4-1 证明以下关系： （1）(a mod n)=(b mod n) ，则 a≡b mod n； （2）a≡b mod n ，则 b≡a mod n； （3）a≡b mod n ，b≡c mod n ，则 a≡c mod n。 4-2证明以下关系： （1）[(a mod n) - (b mod n)] mod n=(a-b) mod n； （2）[(a mod n)×(b mod n)] mod n=(a×b) mod n 。 4-3 用Fermat定理求3201 mod 11 。

4-4 用推广的Euclid算法求67 mod 119的逆元。 4-5 求gcd(4655, 12075) 。 4-6 求解下列同余方程组： 4-7 计算下列Legendre符号： (1) (2) (3)

4-8 求25的所有本原根。 4-9 设通信双方使用RSA加密体制，接收方的公开钥是(e,n)=(5,35)，接收到的密文是C=10，求明文M。 4-10 在ElGamal加密体制中，设素数p=71，本原根g=7， (1) 如果接收方B的公开钥是yB=3，发送方A选择的随机整数k=2，求明文M=30所对应的密文。 (2) 如果A选择另一个随机整数k，使得明文M=30加密后的密文是C=(59,C2)，求C2。

4-11 设背包密码系统的超递增序列为(3, 4, 9, 17, 35)，乘数t=19，模数k=73，试对good night加密。 4-13 在Rabin密码体制中设p=53，q=59 (1) 确定1在模n下的4个平方根。 (2) 求明文消息2347所对应的密文。 (3) 对上述密文，确定可能的4个明文。

4-14 椭圆曲线E11(1,6)表示y2≡x3+x+6 mod 11，求其上的所有点。 4-15 已知点G=(2,7)在椭圆曲线E11(1,6)上，求2G和3G。 4-16 利用椭圆曲线实现ElGamal密码体制，设椭圆曲线是E11(1,6)，生成元G=(2,7)，接收方A的秘密钥nA=7。 (1) 求A的公开钥PA。 (2) 发送方B欲发送消息Pm=(10,9)，选择随机数k=3，求密文Cm。 (3) 显示接收方A从密文Cm恢复消息Pm的过程。