信息安全数学基础陈恭亮pdf

信息安全数学基础一、说明（一）课程性质本课程是继《高等数学》、《线性代数》课之后，为信息与计算科学专业计算方向开设的一门数学基础理论课程。

本课程主要介绍用算术的方法研究整数性质以及近世代数中群与群结构、环论和有限域等内容。

（二）教学目的通过本课程的学习，使学生能熟练掌握用算术的方法研究整数性质以及近世代数中群与群结构、环论和有限域等内容，并且能够掌握如何应用信息安全数学基础中的理论和方法来分析研究信息安全中的实际问题，从而为学习密码学、网络安全、信息安全等打下坚实的基础。

（二）教学内容正确理解并掌握整数的整除概念及性质，带余除法，欧几里得除法，同余及基本性质，欧拉函数和欧拉定理。

一次同余式和二次同余式的解法，平方剩余与平方非剩余，指数及基本性质。

了解群环域等基本概念。

要求基本会用数论知识解决某些代数编码问题。

要求基本会用所学知识解决某些代数编码以及密码学问题。

（三）教学时数54学时（四）教学方式课堂讲授为主。

二、本文第一章整数的可除性教学要点：1. 整除的概念及欧几里得除法2. 算术基本定理教学内容：§1 整除概念和带余除法§2 最大公因式与欧几里得除法§3 整除的性质及最小公倍数§4 素数和算术基本定理§5 素数定理教学时数 6 学时考核要求：1.熟练掌握整除概念及性质，掌握带余除法。

2.理解欧几里得除法，会求最大公因数和最小公倍数。

3.理解素数概念和算术基本定理。

第二章同余教学要点：1.同余及基本性质，2.剩余类及完全剩余系的概念和性质3.欧拉函数和欧拉定理教学内容：§1 同余概念及其基本性质§2 剩余类及完全剩余系§3 简化剩余系与欧拉函数§4 欧拉定理与费尔马定理§5 模重复平方计算法教学时数 6 学时考核要求:1．理解同余概念，掌握其基本性质2．理解剩余类及完全剩余系，了解简化剩余系，熟悉欧拉函数3．掌握欧拉定理和费尔马定理4．掌握模重复平方计算法第三章同余式教学要点：一次同余式和二次同余式的解法，中国剩余定理教学内容：§1 基本概念及一次同余式§2 中国剩余定理§3 高次同余式的解数及解法§4 素数模的同余式教学时数 6 学时考核要求:1. 理解同余式概念，会熟练求解一次同余式2. 理解中国剩余定理第四章二次同余式与平方剩余教学要点：1.平方剩余与平方非剩余，2.勒让德符号和雅可比符号3.合数模教学内容：§1 一般二次同余式§2 模为奇素数的平方剩余与平方非剩余§3 勒让德符号§4 二次互反律§5 雅可比符号§6 模p平方根§7 合数模§8 素数的平方表示教学时数 8学时考核要求:1.熟悉高次同余式的解法2.理解素数模的同余式和一般二次同余式3.理解模为奇素数的平方剩余与平方非剩余4.掌握勒让德符号和雅可比符号5.掌握二次互反律6.理解合数模的二次同余式及其解法第五章原根与指标教学要点：1.指数及其基本性质2.原根存在的条件以及原根求解教学内容：§1 指数及其基本性质§2 原根存在的条件§3 指标及n次剩余教学时数 6 学时考核要求:1.掌握指数及基本性质2.理解原根存在的条件，理解指标和n次剩余概念第六章群教学要点：1.陪集、正规子群和商群的概念2.同态、同构的概念教学内容：§1 群的基本概念§2 循环群§3 陪集和Lagrange定理§4 正规子群和商群教学时数 8学时考核要求:1.掌握群理论与同余理论之间的关系2.熟练群、循环群、同态、同构的概念第七章环和域教学要点：1．环和域的基本概念以及与同态、同构的概念2．理想、商环和多项式环教学内容：§1 环和域的基本概念§2 理想和商环§3 多项式环教学时数 6 学时考核要求:掌握环和域的基本概念以及与同态、同构的概念，理想、商环和多项式环的概念第八章有限域教学要点：1．有限域的概念2．有限域上的多项式教学内容：§1 域的有限扩张§2 有限域的性质§3 有限域的表示§4 有限域上的多项式教学时数 6 学时考核要求:1.掌握有限域的基本概念及定理2.掌握域的扩张的概念3.掌握有限域上多项式的性质三、参考书[1] 信息安全数学基础。

第一章参考答案（1） 5,4,1,5.（2） 100=22*52, 3288=23*3*137.（4） a,b可以表示成多个素因子的乘积a=p1p2––pr, b=q1q2––qs,又因为(a,b)=1，表明a, b没有公共(相同)素因子. 同样可以将a n, b n表示为多个素因子相乘a n=(p1p2––pr)n, b n=(q1q2––qs)n明显a n, b n也没有公共(相同)素因子.（5）同样将a, b可以表示成多个素因子的乘积a=p1p2––pr, b=q1q2––qs,a n=(p1p2––pr)n, b n=(q1q2––qs)n,因为a n| b n所以对任意的i有, pi的n次方| b n,所以b n中必然含有a的所有素因子, 所以b中必然含有a的所有素因子, 所以a|b.（6）因为非零a, b, c互素,所以(a, b)=(a, c)=1,又因为a=p1p2––pr,b=q1q2––qs, ab=p1p2––prq1q2––qs, 又因为a, b, c互素, 所以a, b, c中没有公共(相同)素因子, 明显ab和c也没有公共(相同)素因子.所以(ab, c)= (a, b)(a, c).（7）2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,9 7,101,103,107, 109, 113, 127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199.（11）对两式进行变形有21=0(mod m), 1001=0(mod m),可以看出要求满足的m即使求21和1001的公约数, 为7和1.（12）(70!)/(61!)= 62*63*––*70=(-9)*(-8)*––*(-1)=-9!=-362880=1(mod 71). 明显61!与71互素, 所以两边同乘以61!, 所以70!=61!(mod 71).（13）当n为奇数时2n=(-1)n=-1=2(mod 3), 两边同时加上1有2n+1=0(mod 3), 所以结论成立.当n为偶数时2n=(-1)n=1(mod 3), 两边同时加上1有2n+1=2(mod 3), 所以结论成立.（14）第一个问：因为(c,m)=d, m/d为整数.假设ac=k1m+r, bc=k2m+r,有ac=k1d(m/d)+r, bc=k2d(m/d)+r所以ac=bc(mod m/d),因为(c,m/d)=1,所以两边可以同除以一个c, 所以结论成立.第二个问题：因为a=b(mod m), 所以a-b=ki *mi，a-b是任意mi的倍数，所以a-b是mi 公倍数，所以[mi]|a-b.(利用式子：最小公倍数=每个数的乘积/最大公约数, 是错误的, 该式子在两个数时才成立)（15）将整数每位数的值相加, 和能被3整除则整数能被3整除, 和能被9整除则整数能被9整除, (1)能被3整除, 不能被9整除，(2)都不能，(3)都不能，(4)都不能第二章答案（5）证明：显然在群中单位元e满足方程x2=x, 假设存在一个元素a满足方程x2=x, 则有a2=a, 两边同乘以a-1有a=e. 所以在群中只有单位元满足方程x2=x.（6）证明：因为群G中每个元素都满足方程x2=e, 所以对群中任意元素a,b 有aa=e, bb=e, (ab)2=abab=e. 对abab=e, 方程两边左乘以a, 右乘以b有aababb=(aa)ba(bb)=ba=aeb=ab, 有ab=ba, 所以G是交换群.（7）证明：充分性：因为在群中对任意元素a,b有(ab)2=a2b2即abab=aabb, 方程两边左乘以a的逆元右乘以b的逆元, 有a-1ababb-1= a-1aabbb-1, 有ab=ba, 所以G是交换群.必要性：因为群G是交换群, 所以对任意元素a,b有ab=ba, 方程两边左乘以a右乘以b有abab=aabb, 有(ab)2=a2b2.（8）证明：因为xaaba=xbc，所以x-1xaxbaa-1b-1=x-1xbca-1b-1，所以存在唯一解x=a-1bca-1b-1使得方程成立。

7.1拟素数7.2 素性检测7.3 Euler拟素数第7章素性检测2019/6/2计算机科学与技术学院12019/6/2计算机科学与技术学院2定义1设n是一个奇合数.如果整数b, (b,n)=1,使得同余式b n-1=1 (mod n) 成立,则n叫做对于基b的拟素数.2340=1 mod 341, 2560=1 mod 561, 2644=1 mod 645, 2019/6/2计算机科学与技术学院32019/6/2计算机科学与技术学院42019/6/2计算机科学与技术学院52019/6/2计算机科学与技术学院67.1 拟素数7.2 素性检测7.3 Euler拟素数第7章素性检测2019/6/2计算机科学与技术学院7生成大素数:素性检测•随机生成一个大奇数•然后检验它是否是素数•需要检验多少个随机整数?–一般每ln n个整数有一个素数•对于一个512 bit的n, ln n = 355. 平均需要检测大约177=355/2个奇数•需要解决素性检验问题8•欧拉定理: 若a和n互素,则a (n) 1 mod n•费马小定理:设p是素数, 由于对任意的a(0<a<p), 有gcd(a,p)=1,则a p-1 1 mod p9•Miller-Rabin算法(费马测试)•n 是素数 a n-1 1 mod n•n-1=2k m且a n-1=((a m)2)2…–a m 1 mod n a n-1 1 mod n–((a m)2)2 … 1 mod n a n-1 1 mod n10Miller-Rabin 检验•确定一个给定的数n是否是素数–n-1 = 2k m, (m 是奇数)–选择随机整数a, 1 a n-1–b ← a m mod n–若b=1,则返回“n 是素数”–计算b, b2,b4,…,b2^(k-1) mod n, 若发现 1,返回“n 是素数”–返回“n 是合数”11Why Rabin-Miller Test Work?•声明:若输出“n 是合数”, 则n一定不是素数•Proof:if we choose a number n and returns composite–Then a m 1, a m -1, a2m -1, a4m -1, …, a2^{k-1}m -1 (mod n)–Suppose n is prime,–Then a n-1=a2^{k}m=1 (mod n)–There are two square roots modulo n: 1 and -1 a2^{k-1}m= 1 (mod n)–There are two square roots modulo n: 1 and -1 a2^{k-2}m= 1 (mod n)–…–Then a m= 1 (contradiction!)–因此若n是素数, 算法不将输出“合数”12偏“是”•Bias to YES–如果n是素数,那么Rabin-Miller 检测一定返回“素数”–但a n-1 1 mod n 不能证明n 是素数–合数以1/4的概率通过检测–我们可以检验多次来减少错误概率!•但是有一些非素数!–Carmichael 数: 561, 1105, …13Carmichael 数2019/6/2计算机科学与技术学院147.1 拟素数7.2 素性检测7.3 Euler拟素数第7章素性检测2019/6/2计算机科学与技术学院152019/6/2计算机科学与技术学院207.3 Euler拟素数2019/6/2计算机科学与技术学院21第7章素性检测7.1 拟素数7.2 素性检测7.3 Euler拟素数2019/6/2计算机科学与技术学院22。

信息安全数学基础习题答案信息安全数学基础习题答案1.简答题 a) 什么是信息安全？信息安全是指保护信息的机密性、完整性和可用性，以防止未经授权的访问、使用、披露、干扰、破坏或篡改信息的行为。

b) 什么是加密？加密是指通过对信息进行转换，使其无法被未经授权的人理解或使用的过程。

加密算法通常使用密钥来对信息进行加密和解密。

c) 什么是对称加密算法？对称加密算法是一种使用相同的密钥进行加密和解密的算法。

常见的对称加密算法有DES、AES等。

d) 什么是非对称加密算法？非对称加密算法是一种使用不同的密钥进行加密和解密的算法。

常见的非对称加密算法有RSA、ECC等。

e) 什么是哈希函数？哈希函数是一种将任意长度的数据映射为固定长度的输出的函数。

哈希函数具有单向性，即很难从哈希值逆推出原始数据。

2.选择题 a) 下列哪种算法是对称加密算法？ A. RSA B. AES C. ECC D.SHA-256答案：B. AESb) 下列哪种算法是非对称加密算法？ A. DES B. AES C. RSA D. SHA-256答案：C. RSAc) 下列哪种函数是哈希函数？ A. RSA B. AES C. ECC D. SHA-256答案：D. SHA-2563.计算题 a) 使用AES算法对明文进行加密，密钥长度为128位，明文长度为64位。

请计算加密后的密文长度。

答案：由于AES算法使用的是128位的块加密，所以加密后的密文长度也为128位。

b) 使用RSA算法对明文进行加密，密钥长度为1024位，明文长度为64位。

请计算加密后的密文长度。

答案：由于RSA算法使用的是非对称加密，加密后的密文长度取决于密钥长度。

根据经验公式，RSA算法中加密后的密文长度为密钥长度的一半。

所以加密后的密文长度为1024/2=512位。

c) 使用SHA-256哈希函数对一个长度为128位的明文进行哈希计算，请计算哈希值的长度。

答案：SHA-256哈希函数的输出长度为256位。

“信息安全数学基础”习题答案第一章1、证明： (1)|()|()()|a b b ma m Z c d d nc n Z bd acmn mn Z ac bd ⇒=∈⇒=∈∴=∈∵，，，即。

(2)12111112|,|,,|11(3)|(),,k k k k a b a b a b a b c b c b c c c c ∴−+++∵ ，根据整除的性质及递归法，可证得：，其中为任意整数。

2、证明：1-2(2)(3,5)13|5|15|,(15,7)17|105|a a a a a =∴=∴∵∵∵根据例题的证明结论知：，又且,又，且,。

3、证明：1n p n p n >>因为，且是的最小素因数，若假设n/p 不是素数，则有121223131312,2,,,,2,,k k n p p p p k p p p p k n p p p p n p p n n p n n p =×××≥≥==×≥∴≥≤>> （其中为素数且均）若，则即,与题设矛盾，所以假设不成立，即为素数得证。

7、证明：首先证明形如6k -1的正整数n 必含有6k -1形式的素因子，这显然是成立的。

因为如果其所有素因数均为6k +1形式，则12,(61,1,2,,)j i i n p p p p k i j =×××=+= ,从而得到n 是形如6k +1形式的正整数，这与题设矛盾。

其次，假设形如6k -1的素数为有限个，依次为1212,,6s s q q q n q q q = ，考虑整数-1， 则n 是形如6k -1的正整数，所以n 必有相同形式的素因数q ，使得使得q = q j (1≤j ≤s )。

由整数的基本性质(3)有：12|(6)1s q q q q n −= ，这是不可能的。

故假设错误，即存在无穷多个形如4k -1的素数得证。

2n3n最小非负余数最小正余数绝对值最小余数最小非负余数最小正余数绝对值最小余数3 0、1 1、3 0、1 0、1、2 1、2、3 -1、0、14 0、1 1、4 0、1 0、1、3 1、3、4 -1、0、1 8 0、1、4 1、4、8 1，0 0、1、3、5、7 1、3、5、7、8 3、1、-3、-1、0 10 0、1、4、5、6、9 1、4、5、6、9、10 -4、-1、0、1、4、5 0,1,2,3,4,5,6,7,8,9 1,2,3,4,5,6,7,8,10-5,-4,-3,-2,-1,0,1,2,3,413、解： (1)259222137222376(222,259)37372592221,1,1s t =×+=×⇒==−×∴==−(2)139571316827136821316823122(1395,713)31317136821713(13957131)2713(1)1395,1,2s t =×+=×+=×⇒==−×=−−×=×+−×∴=−=16、解： (1)(112,56)5611256[112,56]112(112,56)=×== (2)(67,335)6767335[67,335]335(67,335)=×== (3)(1124,1368)411241368[1124,1368]384408(1124,1368)=×==(7,4)1,0,7(1)4211,24410,1,2,771||1000142||100040,1,1427c s t k x k k k y k x k y x kk y k ==∴×−+×=∴=−=⎧=−=−⎪⎪=±±⎨⎪==⎪⎩≤⎧∴≤⎨≤⎩=−⎧∴=±±⎨=⎩∵ 而不定方程的一切解为：　其中，又方程的全部解为　，其中 ，第二章1、解：(1) 错误。