2010-5-14 1
第五章 公钥密码
2010-5-14 2
公钥密码
? 数论简介
? 公钥密码体制的基本概念
? RSA算法
? 椭圆曲线密码体制
2010-5-14 3
数论简介
2010-5-14 4
模运算
? 设 n是一正整数,a是整数,若
a=qn+r,0≤r<n,则 a mod n=r
? 若 (a mod n)=(b mod n),称为 a,b模 n同余，
记为 a≡b mod n
? 称与 a模 n同余的数的全体为 a的同余类，
记为 [a],a称为这个同余类的代表元素
2010-5-14 5
模运算
? 同余的性质
? 若 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},求余运算称为模运算
2010-5-14 6
模运算
? 模运算的性质
? [(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
2010-5-14 7
模运算
? 例,Z8={0,1,2,3,4,5,6,7},模 8加法和乘法
＋ 0 1 2 3 4 5 6 7
0 0 1 2 3 4 5 6 7
1 1 2 3 4 5 6 7 0
2 2 3 4 5 6 7 0 1
3 3 4 5 6 7 0 1 2
4 4 5 6 7 0 1 2 3
5 5 6 7 0 1 2 3 4
6 6 7 0 1 2 3 4 5
7 7 0 1 2 3 4 5 6
× 0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7
2 0 2 4 6 0 2 4 6
3 0 3 6 1 4 7 2 5
4 0 4 0 4 0 4 0 4
5 0 5 2 7 4 1 6 3
6 0 6 4 2 0 6 4 2
7 0 7 6 5 4 3 2 1
2010-5-14 8
模运算
? 若 x+y=0 mod n,y为 x的加法逆元。每一
元素都有加法逆元
? 若对 x，有 xy=1 mod n，称 y为 x的乘法
逆元。在上例中，并非所有 x都有乘法逆
元
? 定义 Zn={0,1,..,n-1}为模 n的同余类集合。
2010-5-14 9
模运算
? Zn上模运算的性质
? 交换律
（ x+w) mod n=(w+x) mod n
(x× w) mod n=(w× x) mod n
? 结合律
[(x+w)+y] mod n=[x+(w+y)] mod n
[(x× w) × y] mod n=[x× (w× y)] mod n
? 分配律
[w× (x+y)] mod n=[w× x+w× y)] mod n
2010-5-14 10
模运算
? 单位元
(0+w) mod n=w mod n
(1× w) mod n=w mod n
? 加法逆元：对 w∈Z n,有 z∈Z n，满足
w+z=0 mod n,z为 w的加法逆元，记为
z=-w。
? 加法的可约律
(a+b)≡(a+c) mod n,则 b≡c mod n
对乘法不一定成立，因为乘法逆元不一定存
在 。
2010-5-14 11
模运算
? 定理,设 a∈Z n,gcd(a,n)=1,则 a在 Zn有逆
元
证明思路：
1,用反证法证明 a和 Zn中任何两个不同的数相
乘结果都不相同
2,从 1得出 a× Zn=Zn,因此存在 x∈Z n,使
a× x=1 mod n
? 设 p为素数,Zp中每一个非零元素都与 p
互素，因此有乘法逆元，有乘法可约律
(a× b)=(a× c) mod n,b=c mod n
2010-5-14 12
费尔玛定理和欧拉定理
? 费尔玛定理
若 p是素数,a是正整数且 gcd(a,p)=1，则 ap-1≡1 mod p
证明：
gcd(a,p)=1,则 a× Zp=Zp,a× (Zp-{0})=Zp-{0}
{a mod p,2a mod p,…,(n-1)a mod p} ={0,1,…,p-1}
(a mod p) × (2a mod p) × … × (n-1)a mod p=(p-1)! mod p
(p-1)! × ap-1=(p-1)! mod p
(p-1)!与 p互素，所以乘法可约律,ap-1=1 mod p
2010-5-14 13
费尔玛定理和欧拉定理
? 欧拉函数
? 设 n为一正整数，小于 n且与 n互素的正整数
的个数称为 n的欧拉函数，记为 j(n)
? 定理：若 n是两个素数 p和 q的乘积，则
j(n)＝ j(p) j(q)=(p-1)(q-1)
? 欧拉定理
? 若 a和 n互素,则 aj(n)=1 mod n
2010-5-14 14
素性检验
? 引理,如果 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)?存在 k,j,x+1=kp,x-
1=jp?2=(k-j)p,这是不可能的。
? 引理的逆命题,若方程 x2≡1 mod p 有唯一解 x
不为 +1或 -1,p不是素数
2010-5-14 15
素性检验
? Miller-Rabin素性概率检测法
? n为待检测数,a为小于 n的整数，将 n-1表示为二进
制形式 bkbk-1… b0,d赋初值为 1，算法核心如下
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 the d?(d× a) mod n
}
if d ≠1 then return False;
return True
? 若返回 False,n不是素数,若返回 True,有可能是素数 。
2010-5-14 16
素性检测
? For循环结束,有 d≡a n-1 mod n.由费尔玛定理,
若 n为素数,d为 1.所以 d≠1,则 d不是素数
? n-1≡ -1 mod n,所以 x ≠1 和 x ≠n -1指 x2≡1
mod n 有非 ± 1的根,n不是素数
? 该算法对 s个不同的 a，重复调用，如果
每次都返回 true，则 n是素数的概率大于
等于 1-2-s
2010-5-14 17
欧几里德算法
? 求两个正整数的最大公因子
? 两个正整数互素，可以求一个数关于另一个数
的乘法逆元
? 性质, 对任意非负整数 a和正整数 b,有
gcd(a,b)=gcd(b,a mod b)
? 证明：
a=kb+r≡r mod b ?a mod b=a-kb
设 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公因子集合相同，故最大公因子也相
同
2010-5-14 18
Euclid(f,d) f>d
1,X?f;Y?d;
2,If Y=0 then return X=gcd(f,d)
3,R=X mod Y
4,X=Y;
5,Y=R
6,Goto 2
欧几里德算法
? 例,gcd(55,22)=gcd(22,11)=gcd(11,0)=11
2010-5-14 19
欧几里德算法
? 求乘法逆元
? 若 gcd(a,b)=1,b在模 a下有乘法逆元 (设 b<a)。
即存在 x<a,bx≡1 mod a
Extended Euclid(f,d) (f>d)
1.（ X1 X2 X3)?(1,0,f);(Y1Y2 Y3)?(0,1,d);
2,If Y3=0,then return X3=gcd(f,d);no inverse;
3,If Y3=1,then return X3=gcd(f,d);Y2=d-1 mod f;
4,Q=X3 div Y3;
5,(T1 T2 T3)?(X1-QY1,X2-QY2,X3-QY3);
6,(X1 X2 X3)?(Y1Y2 Y3);
7,(Y1Y2 Y3)?(T1 T2 T3);
8.Goto 2
2010-5-14 20
中国剩余定理
? 如果已知某个数关于一些量量互素的数的同余类
集，就可以重构这个数
? 定理 (中国剩余定理 )：
设 m1,m2,…,mk是两两互素的正整数，
则一次同余方程组
对模 M有唯一解
?
?
? k
i
imM
1
?
?
?
?
?
?
?
?
?
?
kk amx
amx
amx
m o d
m o d
m o d
22
11
?
ii
i
i
kk
k
me
m
M
e
Mae
m
M
ae
m
M
ae
m
M
x
m o d1
m o d)( 22
2
11
1
?
????
满足
?
2010-5-14 21
中国剩余定理
? 中国剩余定理可以将一个很大的数 x表示为一
组较小的数 (a1,… ak)
? 例,x≡ 1 mod 2,x≡ 2 mod 3,x≡ 3 mod 5
x≡ 5 mod 7,求 x
? 解,M＝ 2× 3× 5× 7＝ 210,M1=105,
M2=70,M3=42,M4=30,(Mi=M/mi),可以
求得 e1=1,e2=1,e3=3,e4=4,所以
x=105× 1× 1＋ 70× 1× 2＋ 42× 3× 3＋
30× 4× 5 mod 210＝ 173
2010-5-14 22
离散对数
? 求模下的整数幂
? 根据欧拉定理，若 gcd(a,n)=1,则 af(n) ≡ 1
mod n。 考虑一般 am ≡ 1 mod n,如果 a,n互
素，至少有一个整数 m满足这一方程。称满
足这一方程的最小正整数 m为模 n下 a的 阶 。
? 例,a=7,n=19,71 ≡ 7 mod 19,72 ≡ 11
mod 19,73 ≡ 1 mod 19,所以 7模 19的阶
为 3。从幂次为 4开始出现循环，循环周期
与元素的阶相同
第五章 公钥密码
2010-5-14 2
公钥密码
? 数论简介
? 公钥密码体制的基本概念
? RSA算法
? 椭圆曲线密码体制
2010-5-14 3
数论简介
2010-5-14 4
模运算
? 设 n是一正整数,a是整数,若
a=qn+r,0≤r<n,则 a mod n=r
? 若 (a mod n)=(b mod n),称为 a,b模 n同余，
记为 a≡b mod n
? 称与 a模 n同余的数的全体为 a的同余类，
记为 [a],a称为这个同余类的代表元素
2010-5-14 5
模运算
? 同余的性质
? 若 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},求余运算称为模运算
2010-5-14 6
模运算
? 模运算的性质
? [(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
2010-5-14 7
模运算
? 例,Z8={0,1,2,3,4,5,6,7},模 8加法和乘法
＋ 0 1 2 3 4 5 6 7
0 0 1 2 3 4 5 6 7
1 1 2 3 4 5 6 7 0
2 2 3 4 5 6 7 0 1
3 3 4 5 6 7 0 1 2
4 4 5 6 7 0 1 2 3
5 5 6 7 0 1 2 3 4
6 6 7 0 1 2 3 4 5
7 7 0 1 2 3 4 5 6
× 0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7
2 0 2 4 6 0 2 4 6
3 0 3 6 1 4 7 2 5
4 0 4 0 4 0 4 0 4
5 0 5 2 7 4 1 6 3
6 0 6 4 2 0 6 4 2
7 0 7 6 5 4 3 2 1
2010-5-14 8
模运算
? 若 x+y=0 mod n,y为 x的加法逆元。每一
元素都有加法逆元
? 若对 x，有 xy=1 mod n，称 y为 x的乘法
逆元。在上例中，并非所有 x都有乘法逆
元
? 定义 Zn={0,1,..,n-1}为模 n的同余类集合。
2010-5-14 9
模运算
? Zn上模运算的性质
? 交换律
（ x+w) mod n=(w+x) mod n
(x× w) mod n=(w× x) mod n
? 结合律
[(x+w)+y] mod n=[x+(w+y)] mod n
[(x× w) × y] mod n=[x× (w× y)] mod n
? 分配律
[w× (x+y)] mod n=[w× x+w× y)] mod n
2010-5-14 10
模运算
? 单位元
(0+w) mod n=w mod n
(1× w) mod n=w mod n
? 加法逆元：对 w∈Z n,有 z∈Z n，满足
w+z=0 mod n,z为 w的加法逆元，记为
z=-w。
? 加法的可约律
(a+b)≡(a+c) mod n,则 b≡c mod n
对乘法不一定成立，因为乘法逆元不一定存
在 。
2010-5-14 11
模运算
? 定理,设 a∈Z n,gcd(a,n)=1,则 a在 Zn有逆
元
证明思路：
1,用反证法证明 a和 Zn中任何两个不同的数相
乘结果都不相同
2,从 1得出 a× Zn=Zn,因此存在 x∈Z n,使
a× x=1 mod n
? 设 p为素数,Zp中每一个非零元素都与 p
互素，因此有乘法逆元，有乘法可约律
(a× b)=(a× c) mod n,b=c mod n
2010-5-14 12
费尔玛定理和欧拉定理
? 费尔玛定理
若 p是素数,a是正整数且 gcd(a,p)=1，则 ap-1≡1 mod p
证明：
gcd(a,p)=1,则 a× Zp=Zp,a× (Zp-{0})=Zp-{0}
{a mod p,2a mod p,…,(n-1)a mod p} ={0,1,…,p-1}
(a mod p) × (2a mod p) × … × (n-1)a mod p=(p-1)! mod p
(p-1)! × ap-1=(p-1)! mod p
(p-1)!与 p互素，所以乘法可约律,ap-1=1 mod p
2010-5-14 13
费尔玛定理和欧拉定理
? 欧拉函数
? 设 n为一正整数，小于 n且与 n互素的正整数
的个数称为 n的欧拉函数，记为 j(n)
? 定理：若 n是两个素数 p和 q的乘积，则
j(n)＝ j(p) j(q)=(p-1)(q-1)
? 欧拉定理
? 若 a和 n互素,则 aj(n)=1 mod n
2010-5-14 14
素性检验
? 引理,如果 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)?存在 k,j,x+1=kp,x-
1=jp?2=(k-j)p,这是不可能的。
? 引理的逆命题,若方程 x2≡1 mod p 有唯一解 x
不为 +1或 -1,p不是素数
2010-5-14 15
素性检验
? Miller-Rabin素性概率检测法
? n为待检测数,a为小于 n的整数，将 n-1表示为二进
制形式 bkbk-1… b0,d赋初值为 1，算法核心如下
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 the d?(d× a) mod n
}
if d ≠1 then return False;
return True
? 若返回 False,n不是素数,若返回 True,有可能是素数 。
2010-5-14 16
素性检测
? For循环结束,有 d≡a n-1 mod n.由费尔玛定理,
若 n为素数,d为 1.所以 d≠1,则 d不是素数
? n-1≡ -1 mod n,所以 x ≠1 和 x ≠n -1指 x2≡1
mod n 有非 ± 1的根,n不是素数
? 该算法对 s个不同的 a，重复调用，如果
每次都返回 true，则 n是素数的概率大于
等于 1-2-s
2010-5-14 17
欧几里德算法
? 求两个正整数的最大公因子
? 两个正整数互素，可以求一个数关于另一个数
的乘法逆元
? 性质, 对任意非负整数 a和正整数 b,有
gcd(a,b)=gcd(b,a mod b)
? 证明：
a=kb+r≡r mod b ?a mod b=a-kb
设 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公因子集合相同，故最大公因子也相
同
2010-5-14 18
Euclid(f,d) f>d
1,X?f;Y?d;
2,If Y=0 then return X=gcd(f,d)
3,R=X mod Y
4,X=Y;
5,Y=R
6,Goto 2
欧几里德算法
? 例,gcd(55,22)=gcd(22,11)=gcd(11,0)=11
2010-5-14 19
欧几里德算法
? 求乘法逆元
? 若 gcd(a,b)=1,b在模 a下有乘法逆元 (设 b<a)。
即存在 x<a,bx≡1 mod a
Extended Euclid(f,d) (f>d)
1.（ X1 X2 X3)?(1,0,f);(Y1Y2 Y3)?(0,1,d);
2,If Y3=0,then return X3=gcd(f,d);no inverse;
3,If Y3=1,then return X3=gcd(f,d);Y2=d-1 mod f;
4,Q=X3 div Y3;
5,(T1 T2 T3)?(X1-QY1,X2-QY2,X3-QY3);
6,(X1 X2 X3)?(Y1Y2 Y3);
7,(Y1Y2 Y3)?(T1 T2 T3);
8.Goto 2
2010-5-14 20
中国剩余定理
? 如果已知某个数关于一些量量互素的数的同余类
集，就可以重构这个数
? 定理 (中国剩余定理 )：
设 m1,m2,…,mk是两两互素的正整数，
则一次同余方程组
对模 M有唯一解
?
?
? k
i
imM
1
?
?
?
?
?
?
?
?
?
?
kk amx
amx
amx
m o d
m o d
m o d
22
11
?
ii
i
i
kk
k
me
m
M
e
Mae
m
M
ae
m
M
ae
m
M
x
m o d1
m o d)( 22
2
11
1
?
????
满足
?
2010-5-14 21
中国剩余定理
? 中国剩余定理可以将一个很大的数 x表示为一
组较小的数 (a1,… ak)
? 例,x≡ 1 mod 2,x≡ 2 mod 3,x≡ 3 mod 5
x≡ 5 mod 7,求 x
? 解,M＝ 2× 3× 5× 7＝ 210,M1=105,
M2=70,M3=42,M4=30,(Mi=M/mi),可以
求得 e1=1,e2=1,e3=3,e4=4,所以
x=105× 1× 1＋ 70× 1× 2＋ 42× 3× 3＋
30× 4× 5 mod 210＝ 173
2010-5-14 22
离散对数
? 求模下的整数幂
? 根据欧拉定理，若 gcd(a,n)=1,则 af(n) ≡ 1
mod n。 考虑一般 am ≡ 1 mod n,如果 a,n互
素，至少有一个整数 m满足这一方程。称满
足这一方程的最小正整数 m为模 n下 a的 阶 。
? 例,a=7,n=19,71 ≡ 7 mod 19,72 ≡ 11
mod 19,73 ≡ 1 mod 19,所以 7模 19的阶
为 3。从幂次为 4开始出现循环，循环周期
与元素的阶相同
