4.2 公钥密码算法的数学基础

数论中的一些定理和概念在设计公钥算法时是必不可少的，所以，在介绍公钥密码前，先回顾一下初等数论的一些定理和概念。

4.2.1 若干基本定理

4.2.1.1 算术基本定理

任意整数a > 1都可以唯一地因子分解为：

其中p1＞ p2＞…＞ pi都是素数而且每一个( 1，2，3，i= …。)

4.2.1.2 中国剩余定理（CRT）

《孙子算经》是我国南北朝时期一部重要的数学著作，书中有一个“物不知数”问题，也称为“孙子问题”：今有物，不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？这就是要求解同余方程组：

的正整数解。

明代著名的大数学家程大位，在他所著的《算法统宗》中，对于“孙子问题”的解题方法，还编出了四句歌诀：三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。意思是：一个数用3除，除得的余数乘70；用5除，除得的余数乘21；用7除，除得的余数乘15。最后把这些乘积加起来再减去105的倍数，就知道这个数是多少。运用这一歌诀来解答这道“物不知数”问题，便是

70×2+21×3+15×2=233

233-105-105=23

所以这些物品最少有23个。不过，这一歌诀只能解答用3、5、7作除数的题目。

“孙子定理”给出这类题目的一般解答形式，国际上称为中国剩余定理（Chinese Remainder Theory，CRT），其实质是给出了一种求解线性同余方程组的方法，是数论中最重要的定理之一。该定理说明某一范围内的整数可以通过它对两两互素的整数取模所得的余数来重构。

中国剩余定理有多种表示形式，其中一种常用表示形式为：设自然数m1，m2，…，mr两两互素，并记N = m1m2…mr，N = mi Mi，i =1，2，…，r，则同余方程组

在模N同余的意义下有唯一解

证明：由于gcd（mi，mj）= 1，（1≤ i，j ≤ r，i≠j），得gcd（Mi，mi）= 1，故对每一Mi，有一Mi′存在，使得

M i′M i ≡1(mod mi )，i=1，2…，r

另外，N=miMi，因此，mj|Mi，i≠j，故

为方程组的解。

若x1，x2是适合同余方程组的任意两个整数，则

由于gcd（mi，mj）=1，于是，解在模N同余的意义下唯一。

4.2.1.3 Fermat定理

Fermat小定理：若p是素数，a是正整数且不能被p整除，则

ap-1≡1mod p

证明：考虑集合{1，2，…，p-1}，对每个数乘以a，得到集合{a mod p， 2a mod p，…，（p-1）a mod p}，对于p，后者两两不同且都在1与p-1之间，因此两个集合相同，于是：

（p-1）!=1×2×…×（p-1）

≡[（a mod p）×（2a mod p）×…×（（p-1）a mod p）]mod p

≡[a ×2a ×…×（p-1）a]mod p

≡[ap-1×（p-1）!]mod p

注意到（p-1）!与p互素，因此定理成立。

推论：p是素数，a是任意正整数，则：ap≡a mod p。

4.2.1.4 Euler定理

Euler函数φ（n）定义为小于n且与n互素的正整数个数。特别地，有如下几种情况：

● 若n是素数，φ（n）=n-1。

● 若 n 的因子分解为 n =∏ ipiα，ai > 0，pi 互不相同，则 φ（n）= ∏ ipiα ×（1-1/pi）=n（1-1/p1）（1-1/p2）…（1-1/pn），p1，p2，…，pn是n的素数因子。

● 若gcd（m,n）=1，则 φ（mn）=φ（m）φ（n），特别地，若 p≠q 且都是素数，φ（pq）=（p-1）（q-1）。

例如，20=2×2×5，有两个素数2和5，这样，φ（20）=20（1-1/2）（1-1/5）=8，即20中有8个整数与20是互素的，即它们没有2或5为因子，这8个整数分别为：1，3，7，9，11，13，17，19。

Euler定理：若a与n为互素的正整数，则：aφ（n）≡1mod n。

证明：设R ={x1，x2，…，xφ（n）}为所有小于n且与n互素的正整数，考虑集合。

S={（ax1mod n），（ax2mod n），…，（axφ（n）mod n）}，（axi mod n）与n互素，（axi mod n）两两不等，由（axi mod n）=（axj mod n）可以得出 xi mod n=xj mod n，S有φ（n）个元素，故S也是所有小于n且与n互素的正整数，因此S=R，从而

∏xi=∏（axi mod n）≡（∏（axi））mod n≡（aφ（n）∏xi）mod n

注意到xi与n互素，从而得到结论。

推论：若n=pq，p≠q都是素数，k是任意整数，则

mk（p-1）（q-1）+1≡m mod n，对任意0≤ m≤ n。

证明：若m=0或n，结论是显然的；若m与n互素，注意到φ（n）=（p-1）（q-1），由Euler定理可得到结论；否则m必定是p或者q的倍数，不妨设m=sp，则0<s<q为正整数，m与q互素，由Euler定理得到：

mφ（q）≡1mod q

（mφ（q））kφ（p）≡1mod q

mk（p -1）（q -1） = tq +1，t是整数

等式两边乘以m = sp，得到：

mk（p-1）（q-1）+1=（tq+1）sp=tspq+sp≡m mod n

mk（p-1）（q-1）+1≡m mod n，对任意0≤ m≤ n

这个推论对于证明RSA算法的有效性非常有用。

4.2.2 离散对数难题

4.2.2.1 有限循环群上的离散对数

对于普通的正实数，对数函数是指数函数的反函数。对模运算也是类似的。设G是一个阶为p的有限循环群，g是它的生成元，则G的元素可表示为：G = {1，g，g2，…，gp-1}，由此可见，对G的任何元素y，一定存在某一个正整数x，0≤x≤p-1，使得y = gx mod p，这里，称整数x是群G上元素y关于生成元g的离散对数。

离散对数难题（Discrete Logarithm Problem，DLP）是：在G上，对于方程y = gx mod p，已知g，x，p，计算y是容易的，已知y，g，p，计算x是困难的。

密码学中常用的是三个有限群上的离散对数，这三个有限群是：

● 有限域GF（p）上的乘法群。

● 有限域GF（2n）上的乘法群。

● 有限域F上的椭圆曲线群。

4.2.2.2 有限域GF（p）上的离散对数

设p是一个给定的素数，现考虑有限域GF（p）= {0，1，2，…，p-1}上非零元组成的乘法群={1，2，…，p-1}。

由Euler定理，若a与n为互素的正整数，则aφ(n) ≡ 1 mod n。考虑am ≡ 1 mod n，满足上式的最小指数m称为a（mod n）的阶，a属于（mod n）的指数，a的生成周期长度。如果最小的m = φ (n)，那么a被称为n的原根（Primitive root）。并不是所有整数都有原根，只有2，4，pa，2pa这样形式的整数才有原根，其中p为奇素数。

取p = 13，有限域GF(13) ={0，1，2，…，12}上的非零元组成乘法群： *Z13={1，2，…，12}。这一乘法群是一个有限循环群。可以验证，元素2，6，7，11中的每一个都能生成 *Z13，因此，这3个元素都可以作为它的生成元。这4个元素也是素数13的原根。表4.2给出了整数模13的幂，表中带阴影的部分表明了该行整数在计算模幂时重复出现的幂结果，也就是我们说的阶和生成周期长度。从表中可以看出，2模13的阶为12，而12模13的阶为2。

如果a是素数p的原根，则数a mod p，a2 mod p， …，ap-1 mod p是不同的并且包含1到p -1的整数的某种排列，也即

因此，乘法群 *Zp是一个有限循环群。

在有限域GF(p)的乘法群 *Z p上的离散对数问题是，给定任意整数b，求x，使ax = b mod p。对任意的整数b和素数p的原根a，我们可以找到唯一的指数x满足：

b ≡ ax mod p 0≤ x ≤（p-1）

x称为b以a（mod p）为底数的指数（离散对数），记为x = logab mod p，ind a,p（b）。