西安电子科技大学：《现代密码学》课程教学资源（PPT课件讲稿）第五章 公钥密码（数论简介）

第五章公钥密码 2021/2/21

2021/2/21 1 第五章 公钥密码

公钥密码 ■数论简介 ■公钥密码体制的基本概念 ■RSA算法 ■椭圆曲线密码体制 2021/2/21

2021/2/21 2 公钥密码 ◼ 数论简介 ◼ 公钥密码体制的基本概念 ◼ RSA算法 ◼ 椭圆曲线密码体制

教论简介 2021/2/21

2021/2/21 3 数论简介

模运算 设n是一正整数a是整数,若 a=qn+r,O≤r<n,则 a mod n=r 若( a mod n)=( o mod n),称为ab模n同余, 记为a≡ b mod n 称与a模n同余的数的全体为a的同余类, 记为[],a称为这个同余类的代表元素 2021/2/21

2021/2/21 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称为这个同余类的代表元素

模运算 ■同余的性质 ■若n(a-b),则a≡ b mod n n( a mod n)≡( b mod n),则a≡ b mod n na≡ b mod n,则b≡ a mod n na≡ b mod n,b≡ cmod n,则a≡ cmod n ■求余运算 a mod n将a映射到集合 {o,1,n-},求佘运算称为模运算 2021/2/21 5

2021/2/21 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},求余运算称为模运算

模运算 模运算的性质 [(a mod n)+( b mod n)]mod n=a+b mod n [(amod n)- b mod n) n=(a-b)mod n [(a mod n)x(b mod n)mod n=(ax b)mod n 2021/2/21 6

2021/2/21 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

模运算 ■例:Z8={0,1,23,4,5,6,7模8加法和乘法 +01234567×01234567 00123456700000000|0 112345670101234567 223456701|202460246 |3345670121303614725 456 012340404040 556701234505274163 66 0 23451606420642 770123456707654321 2021/2/21

2021/2/21 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

模运算 ■若X↓y= o mod n,y为x的加法逆元。每 元素都有加法逆元 若对x,有Xy=1modn,称y为x的乘法 逆元。在上例中,并非所有X都有乘法逆 元 ■定义Zn={0,1,,n-为模n的同余类集合。 2021/2/21

2021/2/21 8 模运算 ◼ 若x+y=0 mod n, y为x的加法逆元。每一 元素都有加法逆元 ◼ 若对x，有xy=1 mod n，称y为x的乘法 逆元。在上例中，并非所有x都有乘法逆 元 ◼ 定义Zn={0,1,..,n-1}为模n的同余类集合

模运算 ■Zn上模运算的性质 交换律 (x+w mod n=(w+x)mod n (×w)modn=W×x)modn ■结合律 I(x+w)+y]mod n=[x+(w+y)] mod n [(X×w)× y] mod n=[×(W×y)]modn ■分配律 w(x+y)modn=[w×x+w×y)]modn 2021/2/21

2021/2/21 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

模运算 单位元 (O+w)mod n=wmod n (1×w)modn= w mod n 加法逆元:对W∈Zn有z∈Zn,满足 W+z=0modn,z为W的加油逆元,记为 加法的可约律 (a+b)≡(a+ c)mod n,则b≡ cmod n 对乘法不一定成立,因为乘法逆元不一定存 2021/2/21 在 10

2021/2/21 10 模运算 ◼ 单位元 (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 对乘法不一定成立，因为乘法逆元不一定存 在