文档介绍：第五章公钥密码
2018/7/24
1
公钥密码
数论简介
公钥密码体制的基本概念
RSA算法
椭圆曲线密码体制
2018/7/24
2
数论简介
2018/7/24
3
模运算
设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称为这个同余类的代表元素
2018/7/24
4
模运算
同余的性质
若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},求余运算称为模运算
2018/7/24
5
模运算
模运算的性质
[(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
2018/7/24
6
模运算
例: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
2018/7/24
7
模运算
若x+y=0 mod n, y为x的加法逆元。每一元素都有加法逆元
若对x,有xy=1 mod n,称y为x的乘法逆元。在上例中,并非所有x都有乘法逆元
定义Zn={0,1,..,n-1}为模n的同余类集合。
2018/7/24
8
模运算
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
2018/7/24
9
模运算
单位元
(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的加法逆元,记为z=-w。
加法的可约律
(a+b)≡(a+c) mod n, 则b≡c mod n
对乘法不一定成立,因为乘法逆元不一定存在。
2018/7/24
10