第0章-数论引导篇

1、李锋lfgzdx72105132010.3,信息安全数学基础数论篇,2020/6/18,2,课程内容的设置,初等数论抽象代数：群论关心素数、余数、有限域,2020/6/18,3,课程要求,本课程属于数学理论及应用课程，既强调对数学理论的掌握(一些数学定理的证明)，更强调数学理论的应用，特别是在信息安全和密码学方面的应用。希望在教师引导下，学生逐步学会和掌握现代数学语言，进而了解信息安全学科的最新进展，以利今后的创新工作。,2020/6/18,4,实验（上机）内容和基本要求本课程无实验和上机的教学安排，但要求学生结合本专业的特点和所研究的课题，选择部分算法自己上机实现。要求学生熟悉至少一门数学软

2、件平台（Mathematica/matlab/Maple）和至少一种编程语言。,2020/6/18,5,课程的重点是密码学（对称密码学和非对称密码学）所涉及数学理论和有效算法实现：计算复杂性、欧几里得除法、模同余、欧拉定理、模重复平方计算、蒙哥马利算法、中国剩余定理、二次同余、原根、有限群、对称群、多项式、本原多项式、有限域及其构造、椭圆曲线、素数产生、大数分解。特别对2002年印度数学家发现的AKS素性检验给出了详细证明。,2020/6/18,6,康德ImmanuelKant(1724-1804),2020/6/18,7,关于数论,整数的理论：最古老的以整除性为中心数学是科学之王，数论是数学

3、之王纯数学：一切都为了解方程以严格和简洁著称，既丰富又深刻问题浅显易懂但特别迷人从经验归纳但难于证,2020/6/18,8,传奇人物,欧几里德毕达格拉斯,2020/6/18,9,传奇人物,费马,欧拉,2020/6/18,10,传奇人物,拉格朗日高斯,2020/6/18,11,数学基础的意义,计算机的大家都是数学家离散数学不可或缺的一部分所有深奥的内容背后其实都是一个简单的思想重计算方法，重应用数学思维最基本的两大方面应该是“证”和“算”但证明更有意义,2020/6/18,12,对称,2020/6/18,13,互联网安全,计算机安全,保密通信数据安全,信息安全,2020/6/18,14,一个欺骗

4、的例子：中间人,A：诚实的人,B：保单填写者,C对B说“我是A”；对A说“我是B”通过制作假网站,假公钥,让B上当,2020/6/18,15,简单数字签名,原始信息,Hash算法,Hash值,加密,加密结果（称为签名）,私钥,原始信息,Hash算法,Hash值,解密,公钥,Hash值,=?,Sender,Receiver,2020/6/18,16,原始信息,Hash算法,Hash值,加密,加密结果（数字签名）,发送者私钥,原始信息,Hash算法,Hash值,解密,发送者公钥,Hash值,=?,Receiver,加密信息,接收者公钥,解密信息,接收者私钥,Sender,带加密的数字签名,2020

5、/6/18,17,数论与密码,随着计算机技术，信息技术，通信技术的迅速发展，以及网络的普及，我们已经进入到信息社会人们对信息的需求是与日俱增，不仅从语言交谈和报纸，电视及广播等获取信息，而且也从互联网上获取信息，特别是电子邮件使得人们的文字交流更为快捷此外，人们也将信息用于日常的政务活动和商业活动中，如电子政务和电子商务等，在这些信息交流中，人们自然要考虑信息的机密性、真实性、完整性和不可抵赖性。机密性是保证信息不能被未经授权者阅读。真实性或可鉴性是保证收到的信息确实是由发送者发送的。完整性是保证信息在传递过程中没有被篡改，更换。不可抵赖性是保证发送者不能否认其发送过信息以及接受信息否认接受信

6、息。密码技术是保证信息安全的核心技术。,2020/6/18,18,传统密码,通常保密通信模型A方将明文M通过安全信道发给对方B。实现保密通信的条件：1、面对面的交谈。2、没有窃听可能。存在问题：1、不能面对面交谈。2、有窃听可能。,2020/6/18,19,对称密码模型,对称密码（私钥密码）加解密用同一个密钥，大多数常用的软件如Word、WinRAR都采用这类方法。,明文,密文,密钥k,2020/6/18,20,对称密码,实现保密通信的条件：1、双方有相同的密钥K，2、第三方无法破解密文C，得到明文M。存在问题：1、需要多人保守密钥的机密性。（密钥数量（多于2个）不能实现数字签名）。2、需要定

7、期或不定期的更换密钥。3、密钥管理较为困难。（n个人的密码系统要n(n-1)/2个）例如：恺撒密码系统，密码本，3-DES，AES。涉及数学问题，模运算，置换，域的构造,2020/6/18,21,非对称密码,非对称密码（公钥密码）加解密采用不同的密钥，在通信中具有重要意义。如果你想把密钥告诉一个远在美国的朋友，难道要坐飞机赶过去吗,明文,密文,密钥k1,密钥k2,2020/6/18,22,非对称密码,实现保密通信的条件：1、保密解密密钥d.2、第三方无法破解密文C，得到明文M。3、由加密密钥e无法推导出d,除非知道某些线索。优点：1、只需一人保守解密密钥的机密性。（可实现数字签名）2、可以随时

8、更换密钥。3、密钥管理较为简单。（n个人的密码系统只需要n把加密密钥，且可以在公开途径获得）,2020/6/18,23,公钥密码学概述：1976年，Diffie和Hellman在美国国家计算机会议上首次提出了公开密钥密码学的概念，并发表了开创性的论文“NewDirectioninCryptography”（“密码学的新方向”）。人们就积极寻求满足上述需求的公钥密码系统，也就是说，要寻求单向陷门函数，其从一方是很容易计算的（知道加密密钥），而从另一方无法计算（不知道解密密钥）例1、从门内出来容易，但进入门内需要钥匙。例2、将信放进邮箱容易，但取出邮件需要钥匙。,2020/6/18,24,第一个公

9、钥密码系统：基于背包问题的背包公钥密码系统。目前，大家所公认的高效安全的公钥密码体制，按其所基于的数学难题可分为三类：一、基于大整数分解难题的公钥体制，例如RSA和Rabin-William体制；二、基于有限域上离散对数难题的公钥体制，例如美国政府的数字签名算法DSA,Diffie-Hellman的密钥交换体制,ElGamal加密和签名体制等;三、基于椭圆曲线离散对数难题的公钥体制，即椭圆曲线密码系统简称ECC，绝大多数是基于有限域上离散对数的数学难题，优势较大，如同等强度的椭圆曲线与RSA比较，密钥较短。,2020/6/18,25,RSA公钥密码系统RSA公钥密码系统以其发明者R.Rives

10、t,A.Shamir和L.Adleman的三个姓的首个字母命名的，它是应用最广泛的公钥密码系统，其于大整数因数分解问题。RSA公钥密码系统的描述：每个使用者产生各自的公钥e和私钥d。1、随机产生两个不同的大素数p和q，具有相同的阶；（何谓素数）2、计算n=pq和(p-1)(q-1);（何谓欧拉函数）3、随机选取整数e,1e(p-1)(q-1),其中e与(p-1)(q-1）没有公约数；（何谓公约数）3、运用广义欧几里得算法，计算唯一的整数d,e,1d(p-1)(q-1),使得ed-1被(p-1)(q-1）整除；（何谓广义欧几里得算法和整除）4、公钥是n,e，私钥是d;加密过程：解密过程：,202

11、0/6/18,26,涉及数学问题,整除b|a,因数二次剩余欧几里得算法指标广义欧几里得算法原根或素域生成元素数素数的产生整数的分解有限群公因数最大公因数置换群模运算环中国剩余定理域欧拉函数有限域的生成欧拉定理安全椭圆曲线费马小定理要学习数学语言，并用数学语言描述信息安全问题例如，密码系统，安全性证明,2020/6/18,27,用数学语言描述RSA系统,每个使用者产生各自的公钥和私钥1、随机产生两个不同的大素数p和q，具有相同的阶；以下略；,2020/6/18,28,学习主要内容,分为三类：数论、代数、椭圆曲线具体是：整除b|a,因数二次剩余欧几里得算法指标广义欧几里得算法原根或素域生成元素数素数的产生整数的分解安全椭圆曲线公因数最大公因数模运算中国剩余定理欧拉函数欧拉定理费马小定理,2020/6/18,29,根据公钥解释如下特性,机密性真实性完整性不可抵赖性唯一性认证,2020/6/18,30,抽象代数,近世代数，代数结构正整数与正偶数那个多？整体大于部分？n=2m：一一对应？一条直线上的点与一个平面上的点哪个多？理想、群、环、域、格、流形,2020/6/18,31,信息安全数学基础,上课要求:1)不准迟到，不准旷课；2）成绩分布情况；平时+作业：30分考试：70分交流方式：lfgzdx7210513课外讨论等