- 1、本文档共16页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
教学内容 第1章 引论 第2章 古典密码学 第3章 流密码算法与伪随机数产生器 第4章 分组密码算法 第5章 分组密码算法的工作模式 第6章 单向散列(Hash)函数 第7章 公钥密码算法与数字签名算法 第8章 认证与密钥交换协议 第7章 公钥密码算法 数论是密码学特别是公钥密码学的基本工具,本章首先介绍密码学中常用的一些数论知识,然后介绍公钥密码体制的基本概念和几种重要算法。 第7章 公钥密码算法 7.1 数论 1. 因子 设a,b(b≠0)是两个整数,如果存在另一整数m,使得a=mb,则称b整除a,记为b|a,且称b是a的因子。 2. 素数 称整数p(p1)是素数,如果p的因子只有±1,±p。 任一整数a(a1)都能惟一地分解为以下形式: 其中p1p2…pt是素数,ai0(i=1,…,t)。例如 91=7×11,11011=7×112×13 第7章 公钥密码算法 7.1 数论(续) 3. 互素数 称c是两个整数a、b的最大公因子,如果 ① c是a的因子也是b 的因子,即c是a、b的公因子。 ② a和b的任一公因子,也是c的因子。 表示为c=gcd(a, b)。 确定大数的素因子不很容易。 如果gcd(a,b)=1,则称a和b互素。 第7章 公钥密码算法 7.1 数论(续) 4. 模运算 设n是一正整数,a是整数,如果用n除a,得商为q,余数为r,则 a=qn+r,0≤rn, q =「a/n」 其中「x」为小于或等于x的最大整数。 用a mod n表示余数r,则 。 如果(a mod n)=(b mod n),则称两整数a和b模n同余,记为a≡b mod n。称与a模n同余的数的全体为a的同余类,记为[a],称a为这个同余类的表示元素。 注意: 如果a≡0(mod n),则n|a。 第7章 公钥密码算法 7.1 数论(续) 5. 模乘逆元 对x,若有y,使得x×y≡1 mod n,如3×3≡1 mod 8,则称y为x的倒数,也称为模乘逆元。并非每一x都有模乘逆元。 定理 设a∈Zn,gcd(a, n)=1,则a在Zn中有模乘逆元。 设p为一素数,则Zp中每一非0元素都与p互素,因此有模乘逆元。 第7章 公钥密码算法 7.1 数论(续) 6. 费尔玛定理 Fermat定理 若p是素数,a是正整数且gcd(a, p)=1,则ap-1≡1 mod p。 Fermat定理也可写成如下形式: 设p是素数,a是任一正整数,则ap≡a mod p。 第7章 公钥密码算法 7.1 数论(续) 7. 欧拉函数与欧拉定理 设n是一正整数,小于n且与n互素的正整数的个数称为n的欧拉函数,记为φ(n)。 若n是素数,则显然有φ(n)=n-1。 定理 若n是两个素数p和q的乘积,则φ(n)=φ(p)×φ(q)=(p-1)×(q-1)。 Euler定理 若a和n互素,则aφ(n)≡1 mod n。 第7章 公钥密码算法 7.1 数论(续) 8. 素性检验 素性检验是指对给定的数检验其是否为素数。对于大数的素性检验来说没有简单直接的方法。 引理 如果p为大于2的素数,则方程x2≡1(mod p)的解只有x≡1和x≡-1。 引理的逆否命题为:如果方程x2≡1 mod p有一解x0{-1,1},那么p不为素数。 第7章 公钥密码算法 7.1 数论(续) 9. 欧几里得算法 Euclid算法是数论中的一个基本技术,是求两个正整数的最大公因子的简化过程。而推广的Euclid算法不仅可求两个正整数的最大公因子,而且当两个正整数互素时,还可求出其中一个数关于另一个数的模乘逆元。 1)求最大公因子 Euclid算法是基于下面一个基本结论: 对任意非负整数a和正整数b,有gcd(a, b)=gcd(b, a mod b)。 7.1 数论7.1.9 欧几里得算法——求最大公因子 可假定算法的输入是两个正整数,设为d,f,并设f d。 Euclid(f, d) 1. X←f; Y←d; 2. if Y=0 then return X=gcd(f,d); 3. R=X mod Y; 4. X=Y; 5. Y=R; 6. goto 2。 7.1.9 欧几里得算法——扩展Euclid算法(求模乘逆元) Extended Euclid(f, d) (设 f d) 1. (X1,X2,X3)←(1,0,f);(Y1,Y2,Y3)←(0,1,d); 2. if Y3=0 then return X3=gcd(f, d);no inverse; 3. if Y3=1 then return Y3=gcd(f, d);Y2=d-1 mod
文档评论(0)