公钥密码系统.ppt

NetworkandInformationSecurityNetworkandInformationSecurity问题的提出：挑战！公钥加密算法NetworkandInformationSecurityNetworkandInformationSecurityNetworkandInformationSecurity910NetworkandInformationSecurityNetworkandInformationSecurityNetworkandInformationSecurityRSA的基本原理:RSA是基于大整数难分解的公钥密码技术。
大整数的分解问题可以被表述：已知整数n，n是两个素数的积，即n=p.q。求解p、q的值。
大整数分解是计算上困难的问题，目前还不存在一般性的有效解决算法。
RSA的数学基础最大公约数与互为素数：
设且a，b，c∈z，如果c|a,c|b，称c是a和b的公约数。正整数d称为a和b的最大公约数，如果它满足：
（1）d是a和b的公约数；
（2）对a和b的任何一个公约数c，有c|d.
a和b的最大公约数记为gcd(a,b)=d。
如果gcd(a,b)=1，则称a与b是互素的，即a和b互为素数。
例：8和15是互素的，即gcd（8，15）＝1。1911mod8=3；15mod8=7
（11+15）mod8=26mod8=2
[（11mod8）+（15mod8）]mod8=（3+7）mod8=2
（11-15）mod8=-4mod8=4
[（11mod8）-（15mod8）]mod8=（3-7）mod8=4
（11*15）mod8=165mod8=5
[（11mod8）*（15mod8）]mod8=（3*7）mod8=5
加法逆元：对于a∈Zn，存在b∈Zn，使得a＋b≡0（modn）,则b是a的加法逆元。记b=-a。
例：11＋15≡0（mod26），则称11模26的加法逆元是15
即-11（代表11模26的加法逆元）的结果为15
乘法逆元：设a∈Zn，如果存在b∈Zn满足a×b≡1(modn)，则称b是a的模n乘法逆元，记为x=a-1(modn)
7×15≡1(mod26)，则称7模26的乘法逆元是15
加法一定存在逆元，乘法不一定存在逆元。

22NetworkandInformationSecurity求解乘法逆元的方法例如：k=7,求解7-1（7关于模26的乘法逆元）费马（Fermat）定理
描述1：若p是素数，a是正整数且gcd（a,p）=1，则
ap-1≡1（modp）
描述2：对于素数p，若a是任一正整数，则
ap≡a（modp）
例：p=5,a=3,则35-1=81≡1mod5
35=243≡3mod5欧拉函数
欧拉函数φ(m)：当m>1时，φ(m)表示比m小且与m互素的正整数的个数。
例：m＝24，比24小且与24互素的正整数有：1、5、7、11、13、17、19、23，共8个。因此φ(24)＝8
1）m是素数，则φ(m)=m-1
2)m=pq,且p和q是互异的素数，则φ(m)=φ(p)φ(q)=(p-1)(q-1)
例：φ(21)=φ(3)φ(7)=（3-1)(7-1)=12,这12个数是{1,2,4,5,8,10,11,13,16,17,19,20}
欧拉定理：对于任何互素的两个整数a和m，有
aφ(m)≡1(modm)
例：设a=4，m=5
则有φ(5)=4，44=256，256≡1(mod5)
RSA密码算法RSA算法操作过程RSA算法加密/解密过程RSA算法的证明例1：选p=7，q=17。
n=p×q=119，φ(n)=(p-1)(q-1)=96。
取e=5，满足1<e<φ(n)，且gcd(φ(n),e)=1。
确定满足d·e=1mod96且小于96的d，d＝77。
因此公钥为{5，119}，私钥为{77，119}。
设明文m=19，则由加密过程得密文为
C＝195mod119≡2476099mod119≡66
解密为M＝6677mod119≡1933343536例3：设通信双方使用RSA加密体制，接收方的公开密钥是（5,35），接收到的密文是10，求明文。例4：已知RSA密码体制的公钥为（11，51）
（1）若明文M=3，求C
（2）若截获得的密文C=9，求MNetworkandInformationSecurity4041对称密码体制中的一个苦恼怎样进行密钥协商3、一个基于离散对数的密钥协商协议Diffie-Hellman密钥协商有限域上的离散对数问题数学知识
生成元
素数p的生成元（primitiveroot）的定义：如果a是素数p的生成元，则数amodp,a2modp,…,ap-1modp是不同的并且包含从1到p-1之间的所有整数的某种排列。
注：本原