武汉大学密码学课件-张焕国教授71379

《武汉大学密码学课件-张焕国教授71379》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、密密码码学学（第九讲）公开密钥密码（公开密钥密码（22））张焕国武汉大学计算机学院目目录录11、、密码学密码学的基本概念的基本概念22、古典、古典密码密码33、数据、数据加密标准（DES加密标准（DES））44、、高级高级数据加密标准（数据加密标准（AESAES））55、中国、中国商用密码（SMS4商用密码（SMS4））66、分组、分组密码的应用技术密码的应用技术77、、序列密码序列密码88、习题、习题课：复习对称密码课：复习对称密码99、公开、公开密钥密码（1密钥密码（1））目目录录1010、、公开密钥密码（公开密钥密码（22

2、））11、、数字签名（数字签名（1）12、数字签名（2）1313、、HASH函数1414、、认证认证1515、、密钥管理密钥管理1616、、PKIPKI技术技术1717、习、习题课：复习公钥密码题课：复习公钥密码1818、总复习、总复习//检查：检查：综合实验一一、、ELGamalELGamal公钥密码的基本情况公钥密码的基本情况11、基本情况：、基本情况：①ELGamalELGamal密码是除了密码是除了RSARSA密码之外最有代表密码之外最有代表性的公开密钥密码。②RSARSA密密码建立在大合数分解的困难性之上。码建立在大合

3、数分解的困难性之上。③ELGamalELGamal密码建立在离散对数的困难性之上密码建立在离散对数的困难性之上。一一、、ELGamalELGamal公钥密码的基本情况公钥密码的基本情况22、离散、离散对数问题：对数问题：①设设pp为素数，则模为素数，则模pp的剩余构成有限域：的剩余构成有限域：F={0,1,2,…,p,p--1}1}p*F的非零元构成循环群成循环群FFpp*F={1,2,…,p,p--1}1}p23pp--11={α={α，，αα，，αα，，，，αα}}，，*则称αα为为FF的生成元或模或模pp的本原元。的本原元

4、。p②求求αα的摸幂运算为的摸幂运算为::xy=αmodpp，，1≤x≤p1≤x≤p--1,1,一一、、ELGamalELGamal公钥密码的基本情况公钥密码的基本情况22、离散、离散对数问题：对数问题：求对数求对数XX的运算为的运算为x=logyy，，11≤x≤p≤x≤p--11α由于上述运算是定义在模由于上述运算是定义在模pp有限域上的有限域上的，，所以称为所以称为离散对数运算离散对数运算。。③从从xx计算计算yy是容易的是容易的。。可是从可是从yy计算计算xx就困难得多就困难得多，，利用目前最好的算法利用目前最好的算法，，

5、对于小心选择的对于小心选择的pp将至少将至少½需用需用O(pO(p))次以上的运算次以上的运算，，只要只要pp足够大足够大，，求解求解离散对数问题是相当困难的问题是相当困难的。。二二、、ELGamalELGamal公钥密码•准备：随机地选择一个大素数p，且要求，且要求pp--11有有大素数因子。再选择一个模子。再选择一个模pp的本原元的本原元α。将将pp和和αα公开。公开。⑴密钥生成•用户用户随机地选择一个整数随机地选择一个整数d作为自己的秘密的解密钥密钥，，22≤d≤p≤d≤p--22。。•d计算y=αmodmodpp，，取取

6、y为自己的公开的加密钥为自己的公开的加密钥。。•由公开钥由公开钥yy计算秘密钥计算秘密钥dd，，必须求解离散对数必须求解离散对数，，而这是极困难的而这是极困难的。。二二、、ELGamalELGamal公钥密码⑵加密•将明文消息将明文消息MM（（00≤M≤p≤M≤p--11))加密成密文的过程如加密成密文的过程如下：①随机地选取一个整数取一个整数kk，，22≤k≤p≤k≤p--22。。②k计算：UU＝＝yymodmodpp；；kC＝＝ααmodpp；；1C＝＝UMUMmodmodpp；；2③取取CC＝＝（（CC，，CC））作为的密

7、文作为的密文。。12二二、、ELGamalELGamal公钥密码⑶解密•将密文将密文（（CC，，CC））解密的过程如下：解密的过程如下：12①d计算VV＝＝CCmodp；p；1②--11计算MM＝＝CCVmodmodpp。。2二二、、ELGamalELGamal公钥密码•解密的可还原性可证明如下：C2V--11modmodpp＝＝(UM)V(UM)V--11modp＝＝UMUM（（CC1d）--11modmodpp＝＝UMUM（（（（ααk）d）--11modmodpp＝＝UMUM（（（（ααd）k）--11modmodpp＝＝

8、UMUM（（（（yy））k）--11modp＝＝UMUM（（UU））--11modmodpp＝＝MMmodmodpp二二、、ELGamalELGamal公钥密码⑷安全性•由于由于ELGamalELGamal密码的安全性建立在密码的安全性建立在GFGF（（pp））