信安数学重点.ppt

单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,,*,,*,,,,,,,,单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,,*,,*,信息安全数学基础,,Review,教 师：张立江,,E-mail:,,,2024/9/20,1,Chapter 1,：整除,整除的概念和基本性质,,素数的个数和判别方法,,爱拉托斯散筛法,,素数无穷多,,欧几里得除法,,最大公因子及其基本性质,,辗转相除法,,最小公倍数及其计算,,算术基本定理的描述,,2024/9/20,2,,chapter 2,：不定方程和同余,n,元一次不定方程解数的判定和求解,,,同余的概念和基本性质、应用（求余数等）,,,完全剩余类、简化剩余系的概念和性质,,,欧拉函数及其性质,,,欧拉定理和费尔马小定理的描述和证明,,,模平方指数法,,2024/9/20,3,,chapter 3,：同余方程,一次同余式的求解,,,利用欧几里得除法求逆元,,,中国剩余定理,2024/9/20,4,,chapter 4,：,二次同余式和二次（非）剩余,二次（非）剩余的概念和基本性质,,,勒让德符号,,,二次互反律的描述、证明和应用,,,雅克比符号,,2024/9/20,5,,chapter 5,：原根与指标,指数、原根、指标的概念和基本性质,,,原根存在的条件,,,原根的求法,,,简单,n,次同余方程的求解,,,2024/9/20,6,,chapter 6,：素判定,几种常见的素检测方法,,,2024/9/20,7,,chapter 7,：连分数,连分数的基本概念,2024/9/20,8,,chapter 8,：群、环、域,群、环、域的基本概念,,,群环域的判断,,,多项式环,,,有限域,2024/9/20,9,,chapter 9:,椭圆曲线,椭圆曲线的定义和运算法则,2024/9/20,10,,密码学中常用的三个数学难题,大整数因子分解问题：,,,给定两个素数,p,q,,计算成绩,n=pq,很容易，但给定整数,n,，求,n,的素因子,p,q,使得,n=pq,是困难的,,,密码学中典型应用：,,RSA,公钥密码体制（加密,+,签名）,,,2024/9/20,11,,离散对数问题：,,已知有限循环群,G=={g,k,|k=0,1,2,…},及其生成元,g,和阶,|G|=n.,给定整数,a,，求,h=g,a,很容易；但是给定元素,h,，计算整数,x,，使得,h=g,x,非常困难,,,密码学中典型应用：,,Elgamal,公钥密码体制（加密,+,签名）,,DSS,,Schnorr,签名方案,,2024/9/20,12,,椭圆曲线离散对数问题：,,已知有限,F,p,上的椭圆曲线群：,E(F,p,)={(x,y)|∈F,p,*F,p,,y,2,=x,3,+ax+b, a,b∈F,p,} ∪{,O,},,,及点,P=(x,y),的阶为一个大素数。

给定整数,a,，计算点,Q=aP,很容易，但是给定,Q,，计算整数,x,，使得,xP=Q,是困难问题,,密码学中典型应用：,,,椭圆曲线公钥密码体制（加密,+,签名）,,,基于身份的密码体制,2024/9/20,13,,。