《密码学第7章公钥密码算法与数字签名算法》由会员分享，可在线阅读，更多相关《密码学第7章公钥密码算法与数字签名算法（13页珍藏版）》请在金锄头文库上搜索。
1、密码学Cryptology,计算机学院 黄玉划办公室：北门A12号楼11613675155711,教学内容,第1章 引论第2章 古典密码学第3章 流密码算法与伪随机数产生器第4章 分组密码算法第5章 分组密码算法的工作模式第6章 单向散列(Hash)函数第7章 公钥密码算法与数字签名算法第8章 认证与密钥交换协议,第7章 公钥密码算法,数论是密码学特别是公钥密码学的基本工具，本章首先介绍密码学中常用的一些数论知识，然后介绍公钥密码体制的基本概念和几种重要算法。,第7章 公钥密码算法 7.1 数论,1. 因子设a，b(b0)是两个整数，如果存在另一整数m，使得a=mb，则称b整除a，记为b|a，
2、且称b是a的因子。2. 素数称整数p(p1)是素数，如果p的因子只有1，p。任一整数a(a1)都能惟一地分解为以下形式： 其中p1p2pt是素数，ai0(i=1,t)。例如91=711，11011=711213,第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，余数
3、为r，则a=qn+r,0rd。Euclid（f, d）1. Xf; Yd；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 f;4. Q=X3Y3 ；5. (T1,T2,T3)(X1-QY1,X2-QY2,X3-QY3);6. (X1,X2,X3)(Y1,Y2,Y3);7. (Y1,Y2,Y3)(T1,T2,T3);8. goto 2。,
