信息安全问题的思考与对策精.ppt

信息安全问题的思考与对策第1页，本讲稿共48页目 录1 1 1 1、密码学密码学密码学密码学的基本概念的基本概念的基本概念的基本概念2 2 2 2、古典、古典、古典、古典密码密码密码密码3 3 3 3、数据加密标准（、数据加密标准（、数据加密标准（、数据加密标准（DESDESDESDES）4 4 4 4、高级、高级、高级、高级数据加密标准（数据加密标准（数据加密标准（数据加密标准（AESAESAESAES）5 5 5 5、中国商用密码（、中国商用密码（、中国商用密码（、中国商用密码（SMS4SMS4SMS4SMS4）6 6 6 6、分组密码的应用技术、分组密码的应用技术、分组密码的应用技术、分组密码的应用技术7 7 7 7、序列密码、序列密码、序列密码、序列密码8 8 8 8、习题课：复习对称密码、习题课：复习对称密码、习题课：复习对称密码、习题课：复习对称密码9 9 9 9、公开密钥密码（、公开密钥密码（、公开密钥密码（、公开密钥密码（1 1 1 1）第2页，本讲稿共48页目 录10101010、公开密钥密码（公开密钥密码（公开密钥密码（公开密钥密码（2 2 2 2）1111、数字签名（数字签名（数字签名（数字签名（1 1）1212、数字签名（、数字签名（、数字签名（、数字签名（2 2）13131313、HASHHASH函数函数函数函数14141414、认证、认证、认证、认证15151515、密钥管理、密钥管理、密钥管理、密钥管理16161616、PKIPKIPKIPKI技术技术技术技术17171717、习题课：复习公钥密码、习题课：复习公钥密码、习题课：复习公钥密码、习题课：复习公钥密码18181818、总复习、总复习、总复习、总复习/检查：检查：检查：检查：综合实验综合实验综合实验综合实验第3页，本讲稿共48页一一、ELGamalELGamal公钥密码的基本情况公钥密码的基本情况1 1、基本情况：、基本情况：ELGamalELGamal密码是除了密码是除了RSARSA密码之外最有代表密码之外最有代表性的公开密钥密码。性的公开密钥密码。RSARSA密码建立在大合数分解的困难性之上。密码建立在大合数分解的困难性之上。ELGamalELGamal密码建立在离散对数的困难性之上。密码建立在离散对数的困难性之上。第4页，本讲稿共48页一一、ELGamalELGamal公钥密码的基本情况公钥密码的基本情况2 2、离散对数问题：、离散对数问题：设设设设p p p p为素数，则模为素数，则模为素数，则模为素数，则模p p p p的剩余构成有限域：的剩余构成有限域：的剩余构成有限域：的剩余构成有限域：F F F Fp p p p=0,1,2,=0,1,2,=0,1,2,=0,1,2,p-1,p-1,p-1,p-1F F F Fp p p p 的非零元构成循环群的非零元构成循环群的非零元构成循环群的非零元构成循环群F F F Fp p p p*F F F Fp p p p*=1,2,=1,2,=1,2,=1,2,p-1,p-1,p-1,p-1 =，2 2 2 2，3 3 3 3，p-1p-1p-1p-1 ，则称则称则称则称为为为为F F F Fp p p p*的生成元的生成元的生成元的生成元或模或模或模或模 p p p p 的本原元。的本原元。的本原元。的本原元。求求求求的摸幂运算为的摸幂运算为的摸幂运算为的摸幂运算为:y=y=y=y=x x x x mod mod mod mod p p p p，1xp-1,1xp-1,1xp-1,1xp-1,第5页，本讲稿共48页一一、ELGamalELGamal公钥密码的基本情况公钥密码的基本情况2 2、离散对数问题：、离散对数问题：求对数求对数求对数求对数 X X X X 的运算为的运算为的运算为的运算为 x=logx=logx=logx=logy y y y，1xp-11xp-11xp-11xp-1由由由由于于于于上上上上述述述述运运运运算算算算是是是是定定定定义义义义在在在在模模模模p p p p有有有有限限限限域域域域上上上上的的的的，所所所所以以以以称称称称为为为为离离离离散散散散对数运算。对数运算。对数运算。对数运算。从从从从x x x x计计计计算算算算y y y y是是是是容容容容易易易易的的的的。可可可可是是是是从从从从y y y y计计计计算算算算x x x x就就就就困困困困难难难难得得得得多多多多，利利利利用用用用目目目目前前前前最最最最好好好好的的的的算算算算法法法法，对对对对于于于于小小小小心心心心选选选选择择择择的的的的p p p p将将将将至至至至少少少少需需需需用用用用O(pO(pO(pO(p )次次次次以以以以上上上上的的的的运运运运算算算算，只只只只要要要要p p p p足足足足够够够够大大大大，求求求求解解解解离离离离散散散散对对对对数数数数问问问问题题题题是是是是相相相相当困难的。当困难的。当困难的。当困难的。第6页，本讲稿共48页二二、ELGamalELGamal公钥密码公钥密码 准备：准备：准备：准备：随机地选择一个大素数随机地选择一个大素数随机地选择一个大素数随机地选择一个大素数p p p p，且要求，且要求，且要求，且要求p-1p-1p-1p-1有大素有大素有大素有大素数因子。再选择一个模数因子。再选择一个模数因子。再选择一个模数因子。再选择一个模p p p p的本原元的本原元的本原元的本原元。将将将将p p p p和和和和公开。公开。公开。公开。密钥生成密钥生成密钥生成密钥生成 用用用用户户户户随随随随机机机机地地地地选选选选择择择择一一一一个个个个整整整整数数数数d d d d作作作作为为为为自自自自己己己己的的的的秘秘秘秘密密密密的的的的解解解解密密密密钥钥钥钥，2dp-2 2dp-2 2dp-2 2dp-2。计算计算计算计算y=y=y=y=d d d d mod pmod pmod pmod p，取，取，取，取y y y y为自己的公开的加密钥。为自己的公开的加密钥。为自己的公开的加密钥。为自己的公开的加密钥。由由由由公公公公开开开开钥钥钥钥y y y y 计计计计算算算算秘秘秘秘密密密密钥钥钥钥d d d d，必必必必须须须须求求求求解解解解离离离离散散散散对对对对数数数数，而而而而这这这这是极困难的。是极困难的。是极困难的。是极困难的。第7页，本讲稿共48页二二、ELGamalELGamal公钥密码公钥密码 加密加密加密加密b b将明文消息将明文消息将明文消息将明文消息M M M M（0Mp-1)0Mp-1)0Mp-1)0Mp-1)加密成密文的过程如下：加密成密文的过程如下：加密成密文的过程如下：加密成密文的过程如下：随机地选取一个整数随机地选取一个整数随机地选取一个整数随机地选取一个整数k k k k，2kp-22kp-22kp-22kp-2。计算：计算：计算：计算：U U U U y y y y k k k k mod p mod p mod p mod p；C C C C1 1 1 1k k k k mod p mod p mod p mod p；C C C C2 2 2 2UM mod pUM mod pUM mod pUM mod p；取取取取 C C C C（C C C C1 1 1 1 ，C C C C2 2 2 2）作为的密文。）作为的密文。）作为的密文。）作为的密文。第8页，本讲稿共48页二二、ELGamalELGamal公钥密码公钥密码 解密解密b b将密文（将密文（C C1 1 ，C C2 2）解密的过程如下：）解密的过程如下：计算计算V VC C1 1 d d mod p mod p；计算计算M MC C2 2 V V-1-1 mod p mod p。第9页，本讲稿共48页二二、ELGamalELGamal公钥密码公钥密码 解密的可还原性可证明如下：解密的可还原性可证明如下：解密的可还原性可证明如下：解密的可还原性可证明如下：C C C C2 2 2 2 V V V V-1-1-1-1 mod p mod p mod p mod p(UM)V(UM)V(UM)V(UM)V-1-1-1-1 mod p mod p mod p mod p UMUMUMUM（C C C C1 1 1 1 d d d d）-1-1-1-1 mod p mod p mod p mod p UMUMUMUM（k k k k）d d d d）-1-1-1-1 mod p mod p mod p mod p UMUMUMUM（d d d d）k k k k）-1-1-1-1 mod p mod p mod p mod p UMUMUMUM（y y y y）k k k k）-1-1-1-1 mod p mod p mod p mod p UMUMUMUM（U U U U）-1-1-1-1 mod p mod p mod p mod p M mod p M mod p M mod p M mod p 第10页，本讲稿共48页二二、ELGamalELGamal公钥密码公钥密码 安全性安全性b b由由由由于于于于ELGamalELGamalELGamalELGamal密密密密码码码码的的的的安安安安全全全全性性性性建建建建立立立立在在在在GFGFGFGF（p p p p）离离离离散散散散对对对对数数数数的的的的困困困困难难难难性性性性之之之之上上上上，而而而而目目目目前前前前尚尚尚尚无无无无求求求求解解解解GFGFGFGF（p p p p）离离离离散散散散对对对对数数数数的的的的有有有有效效效效算算算算法法法法，所所所所以以以以在在在在p p p p足足足足够够够够大大大大时时时时ELGamalELGamalELGamalELGamal密密密密码码码码是是是是安安安安全的。全的。全的。全的。b b为为为为了了了了安安安安全全全全p p p p应应应应为为为为150150150150位位位位以以以以上上上上的的的的十十十十进进进进制制制制数数数数，而而而而且且且且p-1p-1p-1p-1应应应应有大素因子。有大素因子。有大素因子。有大素因子。b b为了安全加密和签名所使用的为了安全加密和签名所使用的为了安全加密和签名所使用的为了安全加密和签名所使用的k k k k必须是一次性的。必须是一次性的。必须是一次性的。必须是一次性的。b bd d d d和和和和k k k k都不能太小。都不能太小。都不能太小。都不能太小。第11页，本讲稿共48页二二、ELGamalELGamal公钥密码公钥密码 安全性安全性b b如如如如果果果果 k k k k不不不不是是是是一一一一次次次次性性性性的的的的，时时时时间间间间长长长长了了了了就就就就可可可可能能能能被被被被攻攻攻攻击击击击着着着着获获获获得得得得。又又又又因因因因y y y y是是是是公公公公开开开开密密密密钥钥钥钥，攻攻攻攻击击击击者者者者自自自自然然然然知知知知道道道道。于于于于是是是是攻攻攻攻击击击击者者者者就就就就可可可可以以以以根根根根据据据据U U U Uy y y y k k k k mod mod mod mod p p p p计计计计算算算算出出出出U U U U，进进进进而而而而利利利利用用用用EuclidEuclidEuclidEuclid算算算算法法法法求求求求出出出出U U U U1 1 1 1。又又又又因因因因为为为为攻攻攻攻击击击击者者者者可可可可以以以以获获获获得得得得密密密密文文文文C C C C2 2 2 2，于于于于是是是是可可可可根根根根据据据据式式式式C C C C2 2 2 2UM UM UM UM mod mod mod mod p p p p通通通通过过过过计计计计算算算算U U U U1 1 1 1C C C C2 2 2 2得得得得到到到到明明明明文文文文M M M M。b b设设设设用用用用同同同同一一一一个个个个k k k k加加加加密密密密两两两两个个个个不不不不同同同同的的的的明明明明文文文文M M M M和和和和M M M M，相相相相应应应应的的的的密密密密文文文文为为为为（C C C C1 1 1 1 ，C C C C2 2 2 2）和和和和（C C C C1 1 1 1，C C C C2 2 2 2）。因因因因为为为为C C C C2 2 2 2CCCC2 2 2 2 MMMMMMMM，如果攻击者知道，如果攻击者知道，如果攻击者知道，如果攻击者知道M M M M，则很容易求出，则很容易求出，则很容易求出，则很容易求出M M M M。第12页，本讲稿共48页二二、ELGamalELGamal公钥密码公钥密码 ELGamalELGamal密码的应用密码的应用 b b由由于于ELGamalELGamal密密码码的的安安全全性性得得到到世世界界公公认认，所所以以得得到到广广泛泛的的应应用用。著著名名的的美美国国数数字字签签名名标标准准DSSDSS，采采用用了了ELGamalELGamal密密码码的的一一种种变变形。形。b b为为了了适适应应不不同同的的应应用用，人人们们在在应应用用中中总总结结出出1818种不同的种不同的ELGamalELGamal密码的变形。密码的变形。第13页，本讲稿共48页二二、ELGamalELGamal公钥密码公钥密码 ELGamalELGamalELGamalELGamal密码的应用密码的应用密码的应用密码的应用 加解密速度快加解密速度快加解密速度快加解密速度快由于实际应用时由于实际应用时由于实际应用时由于实际应用时ELGamalELGamal密码运算的素数密码运算的素数密码运算的素数密码运算的素数p p比比比比RSARSA要小，要小，要小，要小，所以所以所以所以ELGamalELGamal密码的加解密速度比密码的加解密速度比密码的加解密速度比密码的加解密速度比RSARSA稍快。稍快。稍快。稍快。随机数源随机数源随机数源随机数源由由由由ELGamalELGamal密码的解密钥密码的解密钥密码的解密钥密码的解密钥d d和随机数和随机数和随机数和随机数k k都应是高质量的随机都应是高质量的随机都应是高质量的随机都应是高质量的随机数。因此，应用数。因此，应用数。因此，应用数。因此，应用ELGamalELGamal密码需要一个好的随机数源，也就是密码需要一个好的随机数源，也就是密码需要一个好的随机数源，也就是密码需要一个好的随机数源，也就是说能够快速地产生高质量的随机数。说能够快速地产生高质量的随机数。说能够快速地产生高质量的随机数。说能够快速地产生高质量的随机数。大素数的选择大素数的选择大素数的选择大素数的选择为了为了为了为了ELGamalELGamal密码的安全，密码的安全，密码的安全，密码的安全，p p应为应为应为应为150150位（十进制数）以位（十进制数）以位（十进制数）以位（十进制数）以上的大素数，而且上的大素数，而且上的大素数，而且上的大素数，而且p-1p-1应有大素因子。应有大素因子。应有大素因子。应有大素因子。第14页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码1 1、椭圆曲线密码的一般情况椭圆曲线密码的一般情况b b受受ELGamalELGamal密密码码启启发发，在在其其它它离离散散对对数数问问题题难难解解的的群群中中，同同样样可可以以构构成成ELGamalELGamal密密码码。于于是是人人们们开开始始寻寻找找其其它它离离散散问问题题难难解解的群。的群。b b研研究究发发现现，有有限限域域GFGF（p p）上上的的椭椭圆圆曲曲线线的的解解点点构构成成交交换换群群，而而且且离离散散对对数数问问题题是是难难解解的的。于于是是可可在在此此群群上上建建立立ELGamalELGamal密密码，并称为码，并称为椭圆曲线密码椭圆曲线密码。第15页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码1 1、椭圆曲线密码的一般情况椭圆曲线密码的一般情况b b椭椭圆圆曲曲线线密密码码已已成成为为除除RSARSA密密码码之之外外呼呼声声最高的公钥密码之一。最高的公钥密码之一。b b它它密密钥钥短短、签签名名短短，软软件件实实现现规规模模小小、硬硬件实现电路省电。件实现电路省电。b b普普遍遍认认为为，160160位位长长的的椭椭圆圆曲曲线线密密码码的的安安全全性性相相当当于于10241024位位的的RSARSA密密码码，而而且且运运算算速度也较快。速度也较快。第16页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码1 1、椭圆曲线密码的一般情况椭圆曲线密码的一般情况b b一一些些国国际际标标准准化化组组织织已已把把椭椭圆圆曲曲线线密密码码作作为为 新新 的的 信信 息息 安安 全全 标标 准准。如如，IEEE IEEE P1363/D4P1363/D4，ANSI ANSI F9.62F9.62，ANSI ANSI F9.63F9.63等等标标准准，分分别别规规范范了了椭椭圆圆曲曲线线密密码码在在InternetInternet协协议议安安全全、电电子子商商务务、WebWeb服服务务器器、空空间间通信、移动通信、智能卡等方面的应用。通信、移动通信、智能卡等方面的应用。第17页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码2 2、椭圆曲线椭圆曲线设设p p是大于是大于3 3的素数，且的素数，且4a4a3 3+27b+27b2 2 0 mod p 0 mod p，称，称 y y2 2=x=x3 3+ax+b+ax+b，a,ba,bGFGFGFGF(p)(p)为为GFGFGFGF（p p）上的）上的椭圆曲线椭圆曲线椭圆曲线椭圆曲线。由椭圆曲线可得到一个同余方程：由椭圆曲线可得到一个同余方程：y y2 2=x=x3 3+ax+b mod p+ax+b mod p其其解解为为一一个个二二元元组组，x,yx,yGFGFGFGF(p)(p)，将将此此二二元元组组描描画画到到椭椭圆圆曲曲线线上上便便为为一一个个点点，于于是是又又称称其其为为解解解解点点点点。第18页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码2 2、椭圆曲线椭圆曲线 为为为为了了了了利利利利用用用用解解解解点点点点构构构构成成成成交交交交换换换换群群群群，需需需需要要要要引引引引进进进进一一一一个个个个O O O O元元元元素素素素，并并并并定定定定义如下的加法运算：义如下的加法运算：义如下的加法运算：义如下的加法运算：定义单位元定义单位元定义单位元定义单位元 引进一个无穷点引进一个无穷点O O（，），简记为），简记为0 0，作为，作为0 0元素。元素。O O（，）O O（，）0 00 00 0。并定义对于所有的解点并定义对于所有的解点P P（x x ，y y），），P P（x x ，y y）+O+OO+PO+P（x x ，y y）P P（x x ，y y）。）。第19页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码2 2、椭圆曲线椭圆曲线定义逆元素定义逆元素定义逆元素定义逆元素 设设P P（x x1 1 ，y y1 1）和和Q Q（x x2 2 ，y y2 2）是是解解点点，如如果果x x1 1=x=x2 2 且且y y1 1=-y=-y2 2，则，则 P P（x x1 1 ，y y1 1）Q Q（x x2 2 ，y y2 2）0 0。这说明这说明任何解点任何解点任何解点任何解点R R R R（x x x x，y y y y）的逆就是）的逆就是）的逆就是）的逆就是 R R R R（x x x x，-y-y-y-y）。）。）。）。注意：规定无穷远点的逆就是其自己。注意：规定无穷远点的逆就是其自己。注意：规定无穷远点的逆就是其自己。注意：规定无穷远点的逆就是其自己。O O（，）-O-O（，）第20页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码2 2、椭圆曲线椭圆曲线定义加法定义加法定义加法定义加法b b设设P(xP(x1 1，y y1 1)Q(x)Q(x2 2，y y2 2)，且，且P P和和Q Q不互逆不互逆 ，则，则 P P（x x1 1 ，y y1 1）Q Q（x x2 2 ，y y2 2）R R（x x3 3 ，y y3 3）。其其中中 x x3 3=2 2 -x-x1 1-x-x2 2，y y3 3=(x=(x1 1 x x3 3)-y)-y1 1，=（y y2 2-y-y1 1 ）/(x/(x2 2-x-x1 1）。）。第21页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码2 2、椭圆曲线椭圆曲线定义加法定义加法定义加法定义加法b b当当P P（x x1 1 ，y y1 1）=Q(x=Q(x2 2，y y2 2)时时 P P（x x1 1 ，y y1 1）Q(x Q(x2 2，y y2 2)2 P2 P（x x1 1 ，y y1 1）R R（x x3 3 ，y y3 3）。）。其中其中 x x3 3=2 2 -2x-2x1 1，y y3 3 =(x=(x1 1 x x3 3)-y)-y1 1，=（3x3x1 12 2 +a+a）/（2 y2 y1 1）。）。第22页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码2 2、椭圆曲线椭圆曲线b b作集合作集合E=E=全体解点，无穷点全体解点，无穷点O O。b b可以验证，如上定义的集合可以验证，如上定义的集合E E和加法运算构和加法运算构成加法交换群。成加法交换群。b b复习：群的定义复习：群的定义 G G是一个非空集，定义了一种运算，且运算是自封闭的；是一个非空集，定义了一种运算，且运算是自封闭的；运算满足结合律；运算满足结合律；G G中有单位元；中有单位元；G G中的元素都有逆元；中的元素都有逆元；第23页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码3 3、椭圆曲线解点加法运算的几何意义、椭圆曲线解点加法运算的几何意义：设设P P（x x1 1 ，y y1 1）和和Q Q（x x2 2 ，y y2 2）是是椭椭圆圆曲曲线线的的两两个个点点，则则连连接接P P（x x1 1 ，y y1 1）和和Q Q（x x2 2 ，y y2 2）的的直直线线与与椭椭圆圆曲曲线线的的另另一一交交点点关关于于横横轴轴的的对对称称点点即即为为P P（x x1 1 ，y y1 1）+Q+Q（x x2 2 ，y y2 2）点。）点。第24页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码3 3、椭圆曲线解点加法运算的几何意义、椭圆曲线解点加法运算的几何意义：x xy y0 0P PQ QP+QP+Q第25页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码4 4、举例、举例：b b取p=11，椭圆曲线y2=x3+x+6。由于p较小，使GFGF(p)也较小，故可以利用穷举的方法根据y2=x3+x+6 mod 11求出所有解点。b b复习：平方剩余复习：平方剩余 设设p p为素数，如果存在一个正整数为素数，如果存在一个正整数x x，使得，使得 x x2 2=a mod p,=a mod p,则称则称 a a是模是模p p的平方剩余。的平方剩余。第26页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码 x xx x3 3+x+6 mod 11 +x+6 mod 11 是否模是否模1111平方剩余平方剩余 y y 0 6 No 0 6 No 1 8 No 1 8 No 2 5 Yes 2 5 Yes 4,74,7 3 3 Yes 3 3 Yes 5,65,6 4 8 No 4 8 No 5 4 Yes 5 4 Yes 2,92,9 6 8 No 6 8 No 7 4 Yes 7 4 Yes 2,92,9 8 9 Yes 8 9 Yes 3,83,8 9 7 No 9 7 No 10 4 Yes 10 4 Yes 2,92,9第27页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码 根据表可知全部解点集为：根据表可知全部解点集为：根据表可知全部解点集为：根据表可知全部解点集为：(2(2，4),(24),(2，7),(37),(3，5),(35),(3，6),(56),(5，2),2),(5(5，9),(79),(7，2),(72),(7，9),(89),(8，3),(83),(8，8),8),(10(10，2),(102),(10，9)9)。再加上无穷远点再加上无穷远点再加上无穷远点再加上无穷远点O O O O，共，共，共，共13131313的点构成一个加法交换群。的点构成一个加法交换群。的点构成一个加法交换群。的点构成一个加法交换群。由于群的元素个数为由于群的元素个数为由于群的元素个数为由于群的元素个数为13131313，而，而，而，而13131313为素数为素数为素数为素数，所以此群是，所以此群是，所以此群是，所以此群是循环群循环群循环群循环群，而且任何一个非，而且任何一个非，而且任何一个非，而且任何一个非O O O O元素都是生成元。元素都是生成元。元素都是生成元。元素都是生成元。第28页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码 由由 于于 是是 加加 法法 群群，n n个个 元元 素素 G G相相 加加，G+G+.+G G+G+.+G nG nG。我我们们取取G G（2 2，7 7）为生成元，具体计算加法表如下：为生成元，具体计算加法表如下：2G=2G=（2 2，7 7）+（2 2，7 7）=（5 5，2 2）因因为为=（32322 2+1+1）（2727）-1-1 mod mod 11 11=23=23-1-1 mod mod 11=24 11=24 mod mod 11=8 11=8。于于是是，x x3 3 =8=82 2-22-22 mod mod 11=5 11=5，y y3 3=8=8（2-52-5）-7-7 mod 11=2mod 11=2。第29页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码 G G（2 2，7 7），），2G 2G（5 5，2 2），），3G 3G（8 8，3 3），），4G 4G（1010，2 2），），5G 5G（3 3，6 6），），6G 6G（7 7，9 9），），7G 7G（7 7，2 2），），8G 8G（3 3，5 5），），9G 9G（1010，9 9），），10G 10G（8 8，8 8），），11G 11G（5 5，9 9），），12G 12G（2 2，4 4），），13G 13G O O（，）。）。第30页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码 除除了了GF(p)GF(p)上上的的椭椭圆圆曲曲线线，外外还还有有定定义义在在GFGF(2(2m m)上上的的椭椭圆圆曲曲线线。这这两两种种椭椭圆圆曲曲线线都都可可以构成安全的椭圆曲线密码。以构成安全的椭圆曲线密码。在在上上例例中中，由由于于p p较较小小，使使GF(p)GF(p)也也较较小小，故故可可以以利利用用穷穷举举的的方方法法求求出出所所有有解解点点。但但是是，对对于于一一般般情情况况要要确确切切计计算算椭椭圆圆曲曲线线解解点数点数N N的准确值比较困难。的准确值比较困难。N N满足以下不等式满足以下不等式 P+1-2P P+1-2P 1/21/2NP+1+2P NP+1+2P 1/2 1/2 。第31页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码5 5、椭圆曲线密码椭圆曲线密码 ELGamalELGamal密密码码建建立立在在有有限限域域GFGF（p p）的的乘乘法法群群的的离离散散对对数数问问题题的的困困难难性性之之上上。而而椭椭圆圆曲曲线线密密码码建建立立在在椭椭圆圆曲曲线线群群的的离离散散对对数数问问题题的的困困难难性性之之上上。两两者者的的主主要要区区别别是是其其离离散散对对数数问问题题所所依依赖赖的的群群不不同同。因因此此两两者有许多相似之处。者有许多相似之处。第32页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码5 5、椭圆曲线密码椭圆曲线密码 椭圆曲线群上的离散对数问题椭圆曲线群上的离散对数问题 在在上上例例中中椭椭圆圆曲曲线线上上的的解解点点所所构构成成的的交交换换群群恰恰好好是是循循环环群群，但但是是一一般般并并不不一一定定。于于是是我我们们希希望望从从中中找找出出一一个个循循环环子子群群E E1 1 。可可以以证证明明当当循循环环子子群群E E1 1 的的阶阶n n是是足足够够大大的的素素数数时时，这这个个循循环环子子群群中中的的离离散散对对数数问问题是困难的。题是困难的。第33页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码5 5、椭圆曲线密码椭圆曲线密码 椭圆曲线群上的离散对数问题椭圆曲线群上的离散对数问题 设设P P和和Q Q是是椭椭圆圆曲曲线线上上的的两两个个解解点点，t t 为为一一正正整整数数，且且1tn1tn。对对于于给给定定的的P P和和t t，计计算算tPtPQ Q是是容容易易的的。但但若若已已知知P P和和Q Q点点，要要计计算算出出t t则则是是极极困困难难的的。这这便便是是椭椭圆圆曲曲线线 群群 上上 的的 离离 散散 对对 数数 问问 题题，简简 记记 为为ECDLP(Elliptic Curve Discrete Logarithm Problem)。第34页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码5 5、椭圆曲线密码椭圆曲线密码 椭圆曲线群上的离散对数问题椭圆曲线群上的离散对数问题 除除了了几几类类特特殊殊的的椭椭圆圆曲曲线线外外，对对于于一一般般ECDLPECDLP目目前前尚尚没没有有找找到到有有效效的的求求解解方方法法。于于是是可可以以在在这这个个循循环环子子群群E1中中建建立立任任何何基基于于离离散散对对数数困困难难性性的的密密码码，并并称称这这个个密密码码为为椭圆曲线密码椭圆曲线密码。第35页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码椭圆曲线密码椭圆曲线密码 T=T=b bp p为大于为大于3 3素数，素数，p p确定了有限域确定了有限域GFGF（p p）；）；b b元素元素a,bGF(p),aa,bGF(p),a和和b b确定了椭圆曲线；确定了椭圆曲线；b bG G为为循循环环子子群群E E1 1的的生生成成元元点点，n n为为素素数数且且为为生成元生成元G G的阶，的阶，G G和和n n确定了循环子群确定了循环子群E E1 1；b bh=|E|/nh=|E|/n，并并称称为为余余因因子子，h h将将交交换换群群E E和和循环子群联系起来。循环子群联系起来。第36页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码椭圆曲线密码椭圆曲线密码 密钥：密钥：b b用户的私钥定义为一个随机数用户的私钥定义为一个随机数d d，d1,2,d1,2,n-1,n-1。b b用户的公开钥定义为用户的公开钥定义为Q Q点，点，Q=dG Q=dG。第37页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码椭圆曲线密码椭圆曲线密码b b设设d d为用户私钥，为用户私钥，Q Q为公钥，将为公钥，将Q Q存入存入PKDBPKDB。b b设设要要加加密密的的明明文文数数据据为为M M，将将M M划划分分为为一一些些较较小小的的数数据据块块，M=mM=m1 1，m m2 2，m mt t，其中其中0m0mi i n n。第38页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码椭圆曲线密码椭圆曲线密码 加密过程：加密过程：加密过程：加密过程：A A A A把把把把M M M M加密发给加密发给加密发给加密发给B B B BAAAA查查查查PKDBPKDB，查到，查到，查到，查到B B B B的公开密钥的公开密钥的公开密钥的公开密钥Q Q Q QB B B B。AAAA选择一个随机数选择一个随机数选择一个随机数选择一个随机数k k k k，且，且，且，且k1,2,k1,2,k1,2,k1,2,n-1,n-1,n-1,n-1。AAAA计算点计算点计算点计算点X X X X1 1 1 1（x x x x1 1 1 1 ，y y y y1 1 1 1）=kG=kG=kG=kG。AAAA计算点计算点计算点计算点X X X X2 2 2 2（x x x x2 2 2 2 ，y y y y2 2 2 2）=kQ=kQ=kQ=kQB B B B，如果分量，如果分量，如果分量，如果分量x x x x2 2 2 2=O=O=O=O，则转，则转，则转，则转。AAAA计算密文计算密文计算密文计算密文 C=m C=m C=m C=mi i i i x x x x2 2 2 2 mod n mod n mod n mod n。AAAA发送加密数据（发送加密数据（发送加密数据（发送加密数据（X X X X1 1 1 1，C C C C）给）给）给）给B B B B。第39页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码椭圆曲线密码椭圆曲线密码b b解密过程：解密过程：b b用户用户B B用自己的私钥用自己的私钥d dB B 求出点求出点X X2 2：d dB BX X1 1=d=dB B（kGkG）=k(d=k(dB B G)G)=k Q =k QB B =X=X2 2（x x2 2 ，y y2 2）b b对对C C解密，得到明文解密，得到明文m mi i=C x=C x2 2 1 1 mod n mod n 。第40页，本讲稿共48页三三、椭圆曲线密码椭圆曲线密码椭圆曲线密码椭圆曲线密码b b椭圆曲线密码的实现椭圆曲线密码的实现b b由由于于椭椭圆圆曲曲线线密密码码所所依依据据的的数数学学基基础础比比较较复杂，从而使得其具体实现也比较困难。复杂，从而使得其具体实现也比较困难。难点：难点：b b安全椭圆曲线的产生；安全椭圆曲线的产生；b b倍点运算。倍点运算。第41页，本讲稿共48页四四、公钥公钥密码的理论模型密码的理论模型1 1、单向函数单向函数 设设设设函函函函数数数数 y=f(x)y=f(x)，如如如如果果果果满满满满足足足足以以以以下下下下两两两两个个个个条条条条件件件件，则则则则称称称称为单向函数：为单向函数：为单向函数：为单向函数：b b如果对于给定的如果对于给定的如果对于给定的如果对于给定的 x x，要计算出，要计算出，要计算出，要计算出 y y很容易；很容易；很容易；很容易；b b而对于给定的而对于给定的而对于给定的而对于给定的 y y，要计算出，要计算出，要计算出，要计算出 x x很难。很难。很难。很难。2、单向函数的应用、单向函数的应用b b安全安全安全安全HASHHASH函数函数函数函数b b操作系统口令操作系统口令操作系统口令操作系统口令第42页，本讲稿共48页四四、公钥公钥密码的理论模型密码的理论模型3 3、利用、利用单向函数构造密码单向函数构造密码b b用正变换作加密，加密效率高；用正变换作加密，加密效率高；用正变换作加密，加密效率高；用正变换作加密，加密效率高；b b用逆变换作解密，安全，敌手不可破译；用逆变换作解密，安全，敌手不可破译；用逆变换作解密，安全，敌手不可破译；用逆变换作解密，安全，敌手不可破译；b b但是加密后不能还原。但是加密后不能还原。但是加密后不能还原。但是加密后不能还原。第43页，本讲稿共48页四四、公钥公钥密码的理论模型密码的理论模型4 4、单向陷门函数单向陷门函数 设设设设函函函函数数数数 y=f(x)y=f(x)，且且且且 f f 具具具具有有有有陷陷陷陷门门门门，如如如如果果果果满满满满足足足足以以以以下下下下两个条件，则称为单向陷门函数：两个条件，则称为单向陷门函数：两个条件，则称为单向陷门函数：两个条件，则称为单向陷门函数：b b如果对于给定的如果对于给定的如果对于给定的如果对于给定的 x x，要计算出，要计算出，要计算出，要计算出 y y很容易；很容易；很容易；很容易；b b而而而而对对对对于于于于给给给给定定定定的的的的 y y，如如如如果果果果不不不不掌掌掌掌握握握握陷陷陷陷门门门门要要要要计计计计算算算算出出出出 x x很很很很难难难难，而而而而如果掌握陷门要计算出如果掌握陷门要计算出如果掌握陷门要计算出如果掌握陷门要计算出 x x就很容易。就很容易。就很容易。就很容