信息安全数学基础课件

信息安全数学基础课程第一章导论信息安全与数学的桥:梁信息安全学科发展数学的核心地位从早期密码术到现代网络安全信息安密码学的安全性本质上依赖于数学难,全已成为数字时代的核心保障随着题的计算复杂性从对称加密到公钥互联网普及和数据价值提升安全技术密码数学理论为安全性提供了可证明,,的数学基础愈发重要的理论保障三大数学难题信息安全的现实意义与挑战网络安全威胁现状当今世界面临着前所未有的网络安全挑战从年勒索软件全球爆发到年2017WannaCry,2021攻击导致美国燃油供应中断网络攻击造成的经济损失和社会影响日益严重数Colonial Pipeline,据泄露事件频发数亿用户信息暴露风险,密码技术的关键作用密码技术是信息安全的核心防线协议保护网页浏览安全数字签名确保交易真实性端到SSL/TLS,,端加密守护通信隐私从在线支付到云存储密码算法无处不在地保护着我们的数字生活,数学基础的保障价值第二章预备知识整数与整除理论:0102整数基本性质除法算法整数集合具有加法和乘法的封闭性、结对于任意整数和正整数存在唯一的整数Z a b,合律、交换律和分配律零元素和负元素和使得其中这个商余q r,a=bq+r,0≤rb的存在使整数构成一个环结构为后续理论定理是整数运算的基础定理,奠定基础欧几里得算法同余理论基础同余的定义同余方程求解若整数和除以正整数的余数相同则称与模同余记作线性同余方程有解的充要条件是整除当有a bm,a bm,a≡b ax≡b mod m gcda,m b同余关系是等价关系具有自反性、对称性和传递性解时可通过扩展欧几里得算法求出模逆进而得到通解mod m,,,模运算规则密码学应用模运算是和等公钥算法的核心运算:RSA ElGamal模运算满足加法、减法和乘法的保持性质基础同余方程求解用于密钥生成和解密过程:,若则±±•a≡b mod m,c≡d modm,a c≡b d modm若则•a≡b modm,c≡d modm,ac≡bd modm幂运算•:a^k≡b^k modm模运算示意图钟表算术与同余关:系钟表是理解模运算最直观的模型小时制的时钟展示了模运算点后小时是1212:1031点因为这种循环特性正是同余关系的本质数字在模数的,10+3mod12=1——环上循环加法示例乘法示例就像点后小时×展示模运算的乘9+5≡2mod12,9535≡3mod12,到达点法性质2周期性质每个单位回到起点形成循环群结构12,第三章素数与素性检验素数是大于且只能被和自身整除的自然数素数在整数中的分布既稀疏又无规律但11,却是数论的基石根据素数定理小于的素数个数约为欧几里得证明了素数,n n/lnn有无穷多个这一优美定理至今令人赞叹,试除法1最直接的方法用小于的所有素数试除对大数效率低下但概念简单,√n n,,适合小规模验证费马素性测试2基于费马小定理若是素数则概率性算法可能:p,a^p-1≡1mod p,误判卡迈克尔数米勒拉宾测试3-改进的概率算法错误率可控制在以下现代密码系统中生成大素,4^-k数的标准方法平衡了效率与准确性,在等密码算法中需要生成位甚至位的大素数高效的素性检验算法RSA,10242048使得在合理时间内生成密码学强度的素数成为可能素数在密码学中的应用算法的素数基础素数生成实现流程RSA算法的安全性完全依赖于两个大素数和的选择模数公开但分解得到和在计算RSA p q n=pq,n p qfunction generatePrimebits:while true:n=上不可行这个非对称性创造了公钥密码学的奇迹公钥可以公开但私钥无法从公钥推导——,randomOddNumberbits ifmillerRabinn,k:return素数和的选择需要满足多个安全条件nfunction millerRabinn,k:write n-1as2^r*d fori=1p q:to k:a=random2,n-2x=a^d mod n if x==1or x==n-和应当足够大通常各为位或更多•pq,10241:continue forj=1to r-1:x=x^2mod nifx==n-1:不能太小避免费马分解攻击•|p-q|,continue outerreturn falsereturn true和应有大素因子抵御算法•p-1q-1,Pollard p-1应该较小增强安全性•gcdp-1,q-1,第四章欧拉函数与欧拉定理欧拉函数定义欧拉定理表示小于等于且与互质的正若则φn n n gcda,n=1,a^φn≡1mod整数个数对于素数这是费马小定理的推广提供了模p,φp=p-1n,对于两个素数的乘积指数运算的周期性是理解公钥密码的,φpq=p-,这个性质是的数学核心关键定理1q-1,RSA中的应用RSA选择加密指数和解密指数满足利用欧拉定理可证明RSA ed ed≡1modφn,实现加密解密的正确性m^e^d≡m mod n,贝祖等式与扩展欧几里得算法贝祖等式的数学表达模逆的求解对于任意整数和存在整数和使得这个等式被称若则在模下的逆元满足ab,x y,ax+by=gcda,b gcda,m=1,a ma^-1a·a^-1≡1modm为贝祖等式或裴蜀定理是整数线性组合理论的基础通过扩展欧几里得算法求出中的则就是模的逆元,ax+my=1x,x am扩展欧几里得算法密码学中的关键作用在计算的同时回溯求出贝祖等式中的系数和算法从的模逆运算在密码算法中至关重要gcda,b,x ygcd:递归过程反向推导时间复杂度仍为,Olog n密钥生成计算•RSA:d≡e^-1modφn解密需要计算逆元•ElGamal:function extGCDa,b:if b==0:return a,1,0数字签名验证涉及模逆运算g,x1,y1=extGCDb,a modb x=y1y=x1-•:a/b*y1return g,x,y密钥协商协议等•:Diffie-Hellman没有高效的模逆算法现代公钥密码学将无法实际应用,第五章群论基础群是代数学中最基本的结构之一由集合和二元运算组成满足四个公理封闭性、结合律、单位元存在、逆元存在群论为密码学提供了抽象而强大的数,G*,:学框架使我们能够在统一的理论下理解各种密码构造,封闭性结合律对于任意∈运算结果仍在中对所有元素成立a,b G,a*b Ga*b*c=a*b*c逆元单位元每个元素都存在逆元使得存在∈使得对所有成立a a^-1a*a^-1=e eG e*a=a*e=a a循环群是密码学中最重要的群结构若群中存在元素使得中每个元素都可表示为的幂次则称为循环群为生成元模素数的乘法群是阶为G g,G g,G,g pZ*_p的循环群这是密钥交换和算法的基础p-1,Diffie-Hellman ElGamal置换群与对称性置换的定义对称性与密码设计个对象的置换是这些对象的一种重新排列个对象的所有置换构成对称群置换群的概念启发了许多密码设计nnS_n,:其阶数为置换可以用循环记号表示如表示n!,1321→3,3→2,2→1分组密码和等算法本质上是对明文分组进行复杂置换:DES AES置换群运算盒设计盒是小规模置换非线性性来自置换的复杂性S:S,扩散原理通过置换实现比特的充分混合:两个置换的复合仍是置换满足群的定义置换的逆就是反向操作每个置换可唯,密钥调度利用置换变换生成轮密钥一分解为不相交循环的乘积这种分解揭示了置换的内在结构:,提出的混淆和扩散原则在数学上可以用置换和代Claude Shannonconfusion diffusion,替来理解置换群理论帮助我们分析密码算法的对称性和弱密钥问题是设计安全分组密码的重要工具,第六章环与多项式环环的定义多项式环构造不可约多项式环×是具有两个二元运算的代数结构给定环可构造多项式环其元素是系在有限域上不能分解为次数更低的多项式R,+,R,R[x],F,加法构成阿贝尔群乘法满足结合律和分配数在中的多项式多项式的加法和乘法遵之积的多项式称为不可约多项式它类似于,R律整数、模剩余类环都是环的例循通常规则保持环结构多项式环是构造整数中的素数在构造扩域时起到关键作用Z nZ_n,,子有限域的关键工具判别多项式是否不可约是一个重要问题对于上的多项式可以通过检查是否能被次数较小的不可约多项式整除来判断算法使用的就是F_2[x],AES上的次不可约多项式来构造F_28x^8+x^4+x^3+x+1GF2^8有限域基础有限域的定义有限域的性质有限域伽罗瓦域是元素个数有限的域记作或基本定理表明有限域的阶数必须是某个素数的的乘法群是阶为的循环群存在本原元使得每个非零元,GFq F_q:q pGFq GFq*q-1,g GFq*={1,g,g^2,...,g^q-2}幂次即对于每个这样的存在唯一的同构意义下有限域素满足,q=p^n q,GFq aa^q-1=1的构造密码学应用GFp^n构造的标准方法在上进行字节替换和混合列运算GFp^n:AES:GF2^8纠错码码基于有限域构造选择上的次不可约多项式:Reed-Solomon

1.F_p nfx密钥共享方案使用有限域上的多项式插值即模的多项式剩余类:Shamir

2.GFp^n=F_p[x]/fx,fx流密码线性反馈移位寄存器工作在上加法多项式加法模:GF

23.:p乘法多项式乘法模再模

4.:fx p有限域运算示意图加法与乘法表:以为例该域可表示为使用不可约多项式域中个元素可表GF8,GF2^3,x^3+x+18示为其中是本原元满足{0,1,α,α^2,α^3,α^4,α^5,α^6},α,α^3=α+1加法运算乘法运算按位异或满足交换律和结合多项式乘法模不可约多项式例如XOR,律例如:α^2·α^3=α^5,α^3·α^4=α^7=α^⊕:α^2+α^3=010100=1100=1=α^2+α逆元计算的逆元是因为例如的逆元是α^iα^7-i,α^7=1α^3α^4有限域的运算表完全确定了域的代数结构是实现等密码算法的基础通过查表或,AES对数表可以高效实现有限域运算第七章椭圆曲线理论基础椭圆曲线是代数几何中的重要对象在密码学中有广泛应用实数域上的椭圆曲线方程,为要求判别式以保证曲线光滑无奇点曲线上的y^2=x^3+ax+b,Δ=4a^3+27b^2≠0点加上无穷远点构成一个阿贝尔群O0102点加法的几何定义点加法的代数公式给定曲线上两点和连接的直线与曲设若斜率P Q,PQ P=x1,y1,Q=x2,y2,x1≠x2,线相交于第三点则定义为关于则R,P+Q R xλ=y2-y1/x2-x1,P+Q=x3,y3,轴的对称点这个几何操作满足群公理其中Rx3=λ^2-x1-x2,y3=λx1-x3-y103倍点公式点的倍加相当于处的切线与曲线的第三个交点关于轴的对称若斜P2P P x P=x1,y1,率λ=3x1^2+a/2y1无穷远点是群的单位元任意点的逆元是其关于轴的对称点点的标量O,Px-P=x,-y乘法通过反复倍加和加法实现是密码算法的核心运算kP,ECC椭圆曲线密码学ECC椭圆曲线离散对数问题是安全性的基础给定椭圆曲线上的点和求解标量与普通离散对数ECDLP ECC:E PQ=kP,k问题相比更难目前没有亚指数时间算法除非曲线选择不当,ECDLP,优势对比ECC vsRSA密钥长度位位安全强度:256ECC≈3072RSA计算效率签名和密钥生成更快:ECC带宽需求更小的密钥和签名适合物联网:,安全边际抗量子计算能力略强:ECDLP关键算法流程ECC密钥生成:选择标准椭圆曲线和基点阶为的大素数

1.E Gn随机选择私钥∈

2.d[1,n-1]计算公钥

3.Q=dG密钥协商ECDH:发送公钥

1.Alice Q_A=d_A·G发送公钥

2.Bob Q_B=d_B·G双方计算共享密钥

3.K=d_A·Q_B=d_B·Q_A=d_A·d_B·G第八章经典公钥密码算法数学基础1RSA1978基于大整数分解困难性安全参数模数的长度通常位或更:n=pq,2048长数学基础欧拉定理和模幂运算:2ElGamal1985基于有限域上的离散对数问题安全参数素数的长度通常位:p,2048数学基础循环群理论和模幂运算:3ECC1985基于椭圆曲线离散对数问题安全参数曲线参数和基点阶通常位:,256数学基础椭圆曲线群和点运算:这三类算法代表了公钥密码学的主要方向最经典应用最广提供随机化RSA,;ElGamal加密效率最高是移动和嵌入式设备的首选它们的安全性都依赖于不同但相关的;ECC,数学难题算法详解RSA密钥生成数学步骤解密过程选择素数独立随机选择大素数和各位以上密文明文正确性证明:pq1024c,m=c^d mod n:计算模数:n=pq,φn=p-1q-1选择公钥指数选使常用:e gcde,φn=1,e=65537计算私钥指数用扩展欧几里得算法求:d≡e^-1modφn输出密钥对公钥私钥最后一步由欧拉定理保证假设:n,e,n,dgcdm,n=1加密过程安全基础明文密文模幂运算使用平方乘算已知求等价于分解或直接求解次剩余问题这两者都被认为是计算困m0≤mn,c=m^e mod n-n,e,c,m ne,法高效实现难的目前对位模数的分解仍然不可行2048RSA的安全性要求和选择得当且私钥绝对保密如果攻击者能分RSA pq,d解得到和就能计算进而得到n pq,φn d算法数学机制ElGamal系统参数生成选择大素数和其本原根即生成的乘法群这些参数可以公开被多个用户共享p gg Z*_p,密钥生成随机选择私钥∈计算公钥私钥保密公钥公开x[1,p-2],y=g^x mod p x,y加密过程对明文随机选择∈计算密文对每次加密m,k[1,p-2],c1,c2=g^k mod p,m·y^k mod p使用不同的实现语义安全k,解密过程利用私钥计算正确性因此x m=c2·c1^x^-1modp:c1^x=g^kx=y^k,c2/c1^x=m·y^k/y^k=m的安全性基于离散对数问题已知求在计算上不可行同时密文扩展两倍明文ElGamal:p,g,y=g^x,x,长度和随机性要求是其特点可以自然扩展为数字签名方案这是的基础ElGamal,DSA算法数学实现ECC椭圆曲线上的密钥生成数字签名ECDSA选择标准曲线参数如椭圆曲线基点阶大素数用户随机选择私钥∈计算公钥签名生成NIST P-256:E,G,nd[1,n-1],:点的标量乘法Q=dG计算消息哈希

1.e=Hm密钥协商随机选择∈

2.k[1,n-1]ECDH计算点令

3.x1,y1=kG,r=x1modn和各自生成密钥对和交换公钥后双方计算共享密钥Alice Bobd_A,Q_A d_B,Q_B,,:计算

4.s=k^-1e+rd modn计算•Alice K=d_A·Q_B=d_A·d_B·G签名为

5.r,s计算•Bob K=d_B·Q_A=d_B·d_A·G签名验证:由于点加法交换律双方得到相同的其坐标作为共享密钥,K,x计算

1.e=Hm计算

2.w=s^-1modn计算

3.u1=ew modn,u2=rw modn计算点

4.x1,y1=u1G+u2Q验证

5.r≡x1modn第九章数学算法的编程实现大素数生成算法模幂运算优化模逆高效计算结合随机数生成和米勒拉宾测试迭代直到找到平方乘算法将复杂度降至通过扩展欧几里得算法在求的同时回溯计算贝祖-,-On Olog n gcd通过轮测试的候选素数时错误概率小二进制展开指数只进行位次数的平方和乘法系数得到模逆时间复杂度是密k k=64,log,Ologn,RSA于运算钥生成的关键步骤2^-128同余方程与中国剩余定理应用中国剩余定理密码学中的优化应用CRT设两两互质则同余方程组加速解密时不直接计算而是m1,m2,...,mk,:RSA-CRT:RSA,m=c^d modn,:计算

1.m_p=c^d modp-1modp计算

2.m_q=c^dmod q-1modq用组合得到

3.CRT mmodn由于指数和模数减半计算量减少约,75%具体计算示例在模下有唯一解M=m1·m2·...·mk求解x≡2mod3,x≡3mod5,x≡2mod7:构造性证明CRT×וM=357=105,M1=35,M2=21,M3=15令则求模的逆元则解为M_i=M/m_i,gcdM_i,m_i=1M_i m_i t_i,:•t1=235·2≡1mod3•t2=121·1≡1mod5•t3=115·1≡1mod7•x=2·35·2+3·21·1+2·15·1=233≡23mod105二次剩余与勒让德符号二次剩余定义若存在使得则称是模的二次剩余否则称为二次非剩余模素数恰有个二次剩余不含x x^2≡a modp,a p,p,p-1/20勒让德符号定义是二次剩余是二次非剩余整除勒让德符号具有乘性a/p=1a,=-1a,=0p a:ab/p=a/pb/p欧拉判别准则对奇素数和有这提供了计算勒让德符号的高效方法p gcda,p=1,a/p≡a^p-1/2modp密码学应用密码系统基于模合数的平方根求解困难性概率加密利用二次剩余的判别问题某些零知识证明协议使用二次剩余性质Rabin Goldwasser-Micali离散对数问题的数学难点离散对数的定义在循环群中给定生成元和元素求整数使得称为以为底的离散G,g h,x g^x=h,x hg对数记作x=log_gh计算复杂性对于比特的群离散对数问题n,:常见攻击方法暴力搜索时间:O2^n算法当群阶有小素因子时可加速防御选择大素数阶子群小步大步算法时间和空间为群阶Pohlig-Hellman:::O√q,q算法时间常数空间Pollardρ:O√q,指数筛法对的乘法群最有效防御使用足够大的素数位GNFS:Z*_p:2048指数筛法亚指数时间仅对特定群有效以上:L[1/2],防御策略对于位模数目前最好算法需要约次运算实际上不可行1024,2^80,选择强素数使有大素因子•p,p-1使用大素数阶的子群•考虑椭圆曲线群指数筛法无效•参数选择遵循标准如推荐•NIST第十章信息安全数学前沿与发展趋势轻量级密码数学基础物联网和嵌入式设备对密码算法提出了低功耗、小资源的要求基于简单代数结构如小有限域、轻量级盒的密码设计成为研究热点、SSIMON等轻量级分组密码在数学上追求简洁高效SPECK量子计算的挑战算法可在多项式时间内分解大整数和求解离散对数威胁、Shor,RSA ECC等系统算法使对称密码安全强度减半后量子密码学研究基于Grover格、编码、多变量等量子计算机难解问题的新密码体制新兴数学工具同态加密基于格理论允许密文直接计算零知识证明利用多项式承诺实,现隐私保护验证多方安全计算结合秘密共享与同态性质区块链中的密码学创新推动了群签名、聚合签名等技术发展课程总结与学习建议重点知识点回顾数学与安全实践结合数论基础信息安全不仅需要扎实的数学基础还要理,解工程实现和安全实践:整除、同余、素数、欧拉函数是理解公钥密码的基石•参数选择的安全考量实现中的侧信道防护•群环域理论标准协议的正确使用•安全审计与漏洞分析抽象代数为密码算法提供统一的数学框•架未来学习路径椭圆曲线建议学习顺序:巩固数学基础数论、抽象代数现代高效密码学的数学基础必须深入

1.,掌握深入学习具体密码算法

2.实践编程实现与测试

3.算法实现研读密码学标准文档

4.跟踪学术前沿进展理论联系实际编程实践加深理解

5.,参考教材与学习资源经典教材推荐在线课程资源开源代码与实验平台《信息安全数学基础》陈恭亮清华大学出版上海交通大学《密码学》网易云课堂配开源密码库学习实现细节•,•-•OpenSSL-,社本课程主要参考教材系统全面套视频讲解-,密码算法库•Crypto++-C++《应用密码学》密码学课程斯坦福大学•Bruce Schneier-•Coursera Cryptography数学软件适合密码学实验•SageMath-,实践经典英文精品课程-密码学教学软件可视化演示•CrypTool-,《现代密码学教程》谷利泽等理论深入中国大学密码学课程多所高校开设•-•MOOC-浅出密码学课程免费•MIT OpenCourseWare-《开放资源•Introduction toModern》国际Cryptography KatzLindell-权威教材信息安全数学体系结构图信息安全数学基础形成了一个完整的知识体系三大核心模块相互支撑、有机统一,:抽象代数模块群论、环论、域论提供统一框架有限域运算,支撑群结构支撑AES,ElGamal数论模块整除理论、同余运算、素数分布、欧拉定理构成经典密码学基础支撑等算法,RSA椭圆曲线模块椭圆曲线群结合代数几何与数论提供高效密,码原语是现代密码学核心工具,三大模块通过共同的数学语言和方法论相互联系数论提供计算基础抽象代数提供结构框架椭圆曲线实现高效安全掌握这个体系就掌握了信息安,,,全的数学基石致谢与互动环节感谢各位同学的参与本课程系统介绍了信息安全的数学基础从基本数论到椭圆曲线从理论证明到算法实现希,,望通过讲的学习大家对密码学背后的数学原理有了深刻理解为进一步学习和研究奠定30,,坚实基础欢迎提问与讨论对课程内容有任何疑问欢迎随时提出我们可以就以下方面深入讨论联系方式与后续支持,:数学定理的证明细节•课程邮箱:crypto-math@university.edu密码算法的安全性分析•答疑时间每周三下午点:2-4编程实现的技术问题•在线讨论课程论坛和学习群前沿研究方向的探讨:•延伸资源课程网站提供补充材料和习题解答:祝各位在信息安全领域不断探索学有所成,!。