信息安全导论5密码学数学基础

《信息安全导论5密码学数学基础》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息安全导论第五讲密码学技术中的数学基础华中科技大学图象所信息安全研究室Dr.ZuxiWang2021/8/181密码学是研究密码系统或通信安全的一门学科，分为密码编码学和密码分析学。密码编码学是使得消息保密的学科，从事此行的称为密码编码者。密码分析学（密码破译学）是研究加密消息的破译的学科，从事此行的称为密码分析者。精于此道的人被称为密码学家，现代的密码学家通常是理论数学家。2021/8/182密码学是一门交叉学科，它很大程度上是应用数学学科。密码学中涉及数论、代数、概率论、组合数学、计算复杂理论等多种数学知识。还涉及信息论学

2、科知识。密码学所涉及的知识十分广阔，这里仅介绍部分数学基本知识。2021/8/183数论基础素数同余、模运算中国剩余定理Euclean算法Fermat定理、Euler定理素性检验因子分解离散对数2021/8/184整除、素数记整数集合Z={…,-3,-2,-1,0,1,2,3,…}整除设a,b∈Z，a≠0，如果存在m∈Z，使得b=ma，则称a整除b，以a

3、b表示，a是b的一个因子或约数。如果没有任何m，使得b=ma，则称a不能整除b,记a†b，此时有a=mb+r且01被称为素数是指p的因子仅有1，-

4、1，p，-p。否则，称为合数。2021/8/185整除基本性质a

5、a;b≠0，b

6、0;Ifa

7、b,b

8、c,thena

9、c;ifa

10、1,thena=±1;ifa

11、b,andb

12、a,thena=±b;ifb

13、gandb

14、h,thenb

15、(mg+nh),foranyintegersmandn注意:ifa=0modn,thenn

16、a2021/8/186互素与最大公约数最大公约数（最大公因子）：若a,b,c∈Z，如果c∣a，c∣b，称c是a和b的公约数。正整数d称为a和b的最大公约数(记d=gcd(a,b)或(a,b))，如果它满足:d是

17、a和b的公约数。对a和b的任何一个公约数c有c∣d。等价的定义形式是：gcd(a,b)=max{k:k∣a，k∣b}若gcd(a,b)=1，称a与b是互素的。2021/8/187最小公倍数最小公倍数a,b的倍数中最小者称为a,b的最小公倍数，记为：lcm(a,b)a,b不全为0，有ab=gcd(a,b)·lcm(a,b).注意：对有限个整数a1,a2,…,an,也可定义最大公约数gcd(a1,a2,…,an)和最小公倍数lcm(a1,a2,…,an).2021/8/188带余除法带余除法：a∈Z,m>0，可找出两个唯一确定的整

18、数q和r使a=qm+r,0≤r

19、ab，则有p

20、a或p

21、b；素数有无穷多个；素数定理:记π(x)为不大于x的素数的个数，则有它表明，对于充分大的x，可以用xlnx近似地表示π(x

22、)。算术基本定理：任何一个不等于0的正整数a都可以写成唯一的表达式，这里P1>P2>P3…>Pt是素数，其中αi>0整数。2021/8/1810目前没有可用于整数分解的有效算法。对于整数a,b(a,b≥2)，a,b的素数分解式分别为：，，其中ei，fi≥0,t≥i≥1，则有：2021/8/1811带余除法中，a∈Z，m>0，a=qm+r，0≤r

23、余称整数a模正整数m同余(数)于整数b，并写a≡b（modm）是指m∣(a－b),m称为模数。note:ifa=0modm,thenm

24、a整数同余式和同余方程2021/8/18121、模关系：相对于某个固定模数m的同余关系，是指整数间的一种等价关系。具有等价关系的三点基本性质：自反性：对任意整数a，有a≡a（modm）对称性：若a≡b(modm)，则b≡a（modm）传递性：若a≡b(modm),b≡c(modm),则a≡c(modm)全体整数集合Z可按模m（m>1）分成一些两两不交的等价类（剩余类）。2、整数模m同余类共有m个

25、，他们分别为mk+0,mk+1,mk+2,…mk+(m-1);k∈z，每一个算一类，每一类都可以选一个代表元，一般选这一类中的最小的非负整数。于是称[0],[1],[2],…[m-1]为标准完全剩余系。其中与m互素的剩余类构成模m的简约剩余系。Z模12的标准完全