第4章公开密钥密码

1、第4章 公开密钥密码4.1 公钥密码概述l公开密钥算法中用作加密的密钥不同于用作解密的密钥，而且解密密钥不能根据加密密钥计算出来（至少在合理假定的长时间内），所以加密密钥能够公开，每个人都能用加密密钥加密信息，但只有解密密钥的拥有者才能解密信息。l在公开密钥算法系统中，加密密钥叫做公开密钥（简称公钥），解密密钥叫做秘密密钥（私有密钥，简称私钥）。l公开密钥算法主要用于加密/解密、数字签名、密钥交换。 讨论议题讨论议题l为什么要设计公钥密码算法密钥分配l公钥密码体制概述及其应用l公钥密码算法的实现Diffie-Hellman密钥交换算法背包算法RSA算法EIGamal算法椭圆曲线密码算法ECC1

2、. 为什么要设计公钥密码体制密钥分配（Key Distribution）保密通信双方需共享密钥共享密钥要经常更换A选择密钥并手工传递给B第三方C选择密钥分别手工传递给A,B用A,B原有共享密钥传送新密钥与A,B分别有共享密钥的第三方C传送新密钥给A和/或BN个用户集需要N(N-1)/2个共享密钥密钥分发中心(Key Distribution Center)密钥分发中心（KDC）l每个用户与KDC有共享密钥(Master Key)lN个用户,KDC只需分发N个Master Keyl两个用户间通信用会话密钥(Session Key)用户必须信任KDCKDC能解密用户间通信的内容 （1）密钥管理量的

3、困难）密钥管理量的困难 传统密钥管理：两两分别用一对密钥时，则传统密钥管理：两两分别用一对密钥时，则n个用个用户需要户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密个密钥，当用户量增大时，密钥空间急剧增大。如钥空间急剧增大。如: n=100 时，时， C(100,2)=4,995 n=5000时，时， C(5000,2)=12,497,500 （2）数字签名的问题）数字签名的问题 传统加密算法无法实现抗抵赖的需求。传统加密算法无法实现抗抵赖的需求。问题的提出问题的提出起源l公钥密码又称为双钥密码和非对称密码，是1976年由Diffie和Hellman在其“密码学新方向”一文中提出

4、的，见划时代的文献： W.Diffie and M.E.Hellman, New Directrions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654lRSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的, 见 Communitions of the ACM. Vol.21.No.2. Feb. 1978, PP.120-126公开密钥密码的重要特性加密与解密由不同的密钥完成加密: mc: c = EK(m)解密: cm: m =

5、 DB(c) = DB(EK(m)知道加密算法,从加密密钥得到解密密钥在计算上是不可行的两个密钥中任何一个都可以用作加密而另一个用作解密(不是必须的)m = DB(EK(m) = EK(DB(m)2. 公钥密码体制的应用概述公钥加密算法l传统加密过程加密和解密使用相同密钥加密和解密使用相同密钥明文明文明文明文密文密文公钥加密算法l公钥密码算法加密和解密使用加密和解密使用不同密钥不同密钥明文明文明文明文密文密文 用公钥密码实现保密用公钥密码实现保密BBBBkkkkk )kkAliceBobcEmBobDcDEmm用户拥有密钥对（k,公钥 公开，私钥 保密： （ ）： （ ）（ ）基于公开密钥的加

6、密过程 用公钥密码实现用公钥密码实现认证认证AAAAkkkkk )kkAliceBobcEmBobDcDEmm用户拥有密钥对（k,公钥 公开，私钥 保密： （ ）： （ ）（ ）基于公开密钥的认证过程 用公钥密码实现用公钥密码实现保密与认证保密与认证BAABABABBAkkkkkkkkkkk )kkAliceBobcEDmBobDDDEDmm用户拥有密钥对（k,公钥 公开，私钥 保密： （ ）： （E (c)） （E (c)） （E (（ ）)） 公钥密钥的应用范围加密加密/解密解密数字签名数字签名(身份鉴别身份鉴别)密钥交换密钥交换算法加/解密数字签名密钥交换RSA是是是Dieffie-He

7、llman否否是DSS否是否3. 公钥密码算法基本思想和要求l涉及到各方：发送方、接收方、攻击者l涉及到数据：公钥、私钥、明文、密文l公钥算法的条件：产生一对密钥是计算可行的已知公钥和明文，产生密文是计算可行的接收方利用私钥来解密密文是计算可行的对于攻击者，利用公钥来推断私钥是计算不可行的已知公钥和密文，恢复明文是计算不可行的(可选)加密和解密的顺序可交换单向陷门函数函数单向陷门函数函数 满足下列条件的函数满足下列条件的函数f f： (1) 给定给定x，计算，计算y=f(x)是容易的是容易的 (2) 给定给定y, 计算计算x使使y=f(x)是困难的是困难的 (3) 存在存在z，已知，已知z 时

8、时, 对给定的任何对给定的任何y，若相应的，若相应的x存存 在，则计算在，则计算x使使y=f(x)是容易的是容易的所谓计算所谓计算x= x= f-1(Y)(Y)困难是指计算上相当复杂，已无困难是指计算上相当复杂，已无实际意义实际意义单向陷门函数说明单向陷门函数说明仅满足仅满足(1)、(2)两条的称为单向函数；第两条的称为单向函数；第(3)条称为陷条称为陷门性，门性，z 称为陷门信息称为陷门信息当用陷门函数当用陷门函数f作为加密函数时，可将作为加密函数时，可将f公开，这相当公开，这相当于公开加密密钥，此时加密密钥便称为公开钥，记为于公开加密密钥，此时加密密钥便称为公开钥，记为Pkf函数的设计者将

9、函数的设计者将z保密，用作解密密钥，此时保密，用作解密密钥，此时z称为秘称为秘密钥匙，记为密钥匙，记为Sk。由于设计者拥有。由于设计者拥有Sk，他自然可以解，他自然可以解出出x=f-1(y)单向陷门函数的第单向陷门函数的第(2)条性质表明窃听者由截获的密文条性质表明窃听者由截获的密文y=f(x)推测推测x是不可行的是不可行的 公钥密码基于的数学难题公钥密码基于的数学难题 背包问题背包问题 大 整 数 分 解 问 题 （大 整 数 分 解 问 题 （ T h e I n t e g e r T h e I n t e g e r Factorization Problem,RSAFactoriz

10、ation Problem,RSA体制）体制） 有限域的乘法群上的离散对数问题有限域的乘法群上的离散对数问题 (The Discrete Logarithm Problem,(The Discrete Logarithm Problem, ElGamal ElGamal体制）体制） 椭圆曲线上的离散对数问题（椭圆曲线上的离散对数问题（The EllipticThe Elliptic Curve Discrete Logarithm Problem, Curve Discrete Logarithm Problem, 类比的类比的ElGamalElGamal体制）体制）一、背包问题l背包问题：已

11、知一长度为B的背包，及长度分别为a1,a2,.,an的n个物品。假定这些物品的半径和背包相同，若从这n个物品中选出若干个正好装满这个背包。现在反过来问：究竟是哪些物品？背包问题数学描述ii112x011,2,., ,a,.,bniininxba aa求 或 ，使其满足：其中和 都是整数背包问题求解NPNP背包问题属于完备类（问题中难度最大的一类）对这一问题没有有效算法11(2,3,., )ijja in12ni但是，如果序列a ,a ,.,a 是超递增序列：a背包问题有多项式解法超递增序列背包问题求解方法123456248163243xxxxxxn12n例:已知序列a ,a ,.,a 是超递增

12、序列：1,2,4,8,.,2求 背包问题的解思路：思路：xi取值只可能为取值只可能为0或者或者1；如果为；如果为0，表示，表示不能装入对应的物体，否则可以装入。不能装入对应的物体，否则可以装入。超递增序列背包问题求解方法123456123452481632432481611xxxxxxxxxxx（2）带入：1116,05（3）因为所以有x（不能选）123451234248161124811xxxxxxxxx（4）带入：16(1)对于体积为32的物体，因为3243，所以x（可以选）1246121xxxxxx（ 5 ） 继 续 上 述 过 程 ， 可 得 ： 0MerkleHellman背包公钥算

13、法122c.nnma ma m1（ 2 ） 利 用 公 钥 加 密 如 下 ： a1212a ,.,.nnaamm mm（1）选取一组正整数作为公钥予以公布是n位0，1明文符号串。12c.nm mm（3）从密文 求明文等价于背包问题MerkleHellman背包公钥算法12明文： m 10110110，m 11001001123456782832aaaaaaa例如：已知: a ， ， 11， 08 71， 51， 43， 6712分别加密得到密文： c2 8 + 1 1 + 8 + 5 1 + 4 3 1 4 1 c2 8 + 3 2 + 7 1 + 4 7 = 1 9 8MerkleHell

14、man背包公钥算法l问题：如何解密？对公钥密码算法的误解l公开密钥算法比对称密钥密码算法更安全？任何一种算法都依赖于密钥长度、破译密码的工作量，从抗分析角度，没有一方更优越l公开密钥算法使对称密钥成为过时了的技术？公开密钥很慢，只能用在密钥管理和数字签名，对称密钥密码算法将长期存在l使用公开密钥加密，密钥分配变得非常简单？事实上的密钥分配既不简单，也不有效 自从自从19761976年公钥密码的思想提出来年公钥密码的思想提出来以后，国际上已经提出许多种公钥密码以后，国际上已经提出许多种公钥密码体制，但比较流行的主要有两类：一类体制，但比较流行的主要有两类：一类是基于大整数因子分解问题的，其中最是

15、基于大整数因子分解问题的，其中最典型的代表是典型的代表是RSA;RSA;另一类是基于离散对另一类是基于离散对数问题的，比如数问题的，比如ElGamaLElGamaL公钥密码和影公钥密码和影响比较大的椭圆曲线公钥密码。下面对响比较大的椭圆曲线公钥密码。下面对这三个公钥方法进行阐述。这三个公钥方法进行阐述。一、公钥密码4.2 基于大整数分解的公开密钥密码体系l一、大整数分解问题：已知整数n，n是两个素数的乘积，即n=q*p，求解p与q的值。l大整数分解是计算上的难题，目前还不存在一般性的有效解决算法。lRSA就是基于大整数分解问题的公开密钥密码体制代表算法1. 1. RSA算法概述算法概述 197

16、8年，美国麻省理工学院(MIT)的研究小组成员：李维斯特(Rivest)、沙米尔(Shamir)、艾德曼(Adleman)提出了一种基于公钥密码体制的优秀加密算法RSA算法。 RSA算法是一种分组密码体制算法，它的保密强度是建立在具有大素数因子的合数，其因子分解是困难的。是否是NP问题尚未确定。RSA得到了世界上的最广泛的应用，ISO在1992年颁布的国际标准X.509中,将RSA算法正式纳入国际标准。1999年美国参议院已通过了立法，规定电子数字签名与手写签名的文件、邮件在美国具有同等的法律效力。2.数论知识简介数论知识简介数论概念数论概念: 研究研究“离散数字集合离散数字集合”运算是运算是

17、“+” ,“”例例:整数整数: 5 + 9 = 14; 5 5 + 9 = 14; 5 3 = 5 + 5 + 5 = 15 3 = 5 + 5 + 5 = 15 多项式多项式: x x2 2+1 + x = x+1 + x = x2 2+x+1; x +x+1; x x x2 2+1 = x+1 = x3 3+x+x l运算： （1）模数运算（2）模多项式运算l进一步运算:指数运算,逆运算数论是理解公钥算法的基础1 1）运算概念）运算概念l对整数 b!=0 及 a , 如果存在整数如果存在整数 m 使得 a=mb,称 b 整除 a, 也称b是a的因子l记作 b|a l例 1,2,3,4,6,

18、8,12,24 整除 24 2 2）整除）整除l素数: 只有因子 1 和自身l1 是一个平凡素数l例 2,3,5,7 是素数, 4,6,8,9,10 不是l素多项式或不可约多项式irreducible: l 不可写成其他因式的乘积l x2+x = x x+1 是非不可约多项式; x3+x+1 是不可约多项式3 3）素数与不可约多项式）素数与不可约多项式l200 以内的素数:l 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149

19、 151 157 163 167 173 179 181 191 193 197 199 4 4）一些素数）一些素数l把整数n写成素数的乘积l分解整数要比乘法困难l整数 n的素数分解是把它写素数的乘积 eg. 91 = 7 13 ; 3600 = 24 32 52 5 5）素数分解）素数分解( (PrimeFactorisation）l整数 a, b 互素是指 它们没有除1之外的其它因子l8 与15 互素 l8的因子1,2,4,8 l15的因子 1,3,5,15 l1 是唯一的公因子6 6）整数互素）整数互素l除法取余运算 l同余( congruence) for a = b mod n l如

20、果a,b 除以n,余数相同leg. 100 = 34 mod 11 lb 叫做a模n的剩余 l通常 0=b=n-1 leg. -12mod7 = -5mod7 = 2mod7 = 9mod7 l可以进行整数运算 7 7）模算式）模算式l加法加法 a+b mod n l减法减法 a-b mod n = a+(-b) mod n l乘法乘法 a.b mod n 重复加法l除法除法 a/b mod n 乘以b的逆元: a/b = a.b-1 mod n 如果n是素数, b-1 mod n 存在 s.t b.b-1 = 1 mod n 例. 2.3=1 mod 5 hence 4/2=4.3=2 mo

21、d 58 8）模算术运算）模算术运算数论基础la与b的最大公因数：gcd（a, b）gcd（20, 24）=4 , gcd（15, 16）=1l如果gcd（a, b）=1 ，称a与b 互素l模运算 moda= q n +r 0rn ; q=a/n ; x 表示小于或等于x的最大整数a=a/nn + （a mod n） , r = a mod n 如果 （a mod n ）= （b mod n） ，则称a 与b 模模n同余同余，记为 a b mod n 例如， 23 8 mod 5 , 8 1 mod 7数论基础（续）l模运算对加法和乘法是可交换的、可结合的、可分配的（a+b） mod n =

22、（a mod n ） + （b mod n） ） mod n（a-b） mod n = （a mod n） （b mod n） ） mod n（ab） mod n = （a mod n ） （b mod n） ） mod n （a （b+c） ） mod n = （ a b） mod n + （a c） mod n） mod nl幂,模运算 ma mod n m2 mod n = （mm） mod n = （m mod n ） 2 mod n m4 mod n = （m2 mod n ） 2 mod nm8 mod n = （m2 mod n ）2 mod n ）2 mod n m25 mod

23、 n = （m m8 m16） mod n 数论基础（续）l欧拉函数(n)n是正整数， (n)是比n小且与n 互素的正整数的个数(2) = |1| =1(3) = |1, 2| =2 (4) = |1, 3| =2 (5) = |1, 2, 3, 4 | =4 (6) = |1, 5| =4 (7) = |1, 2, 3, 4, 5, 6| =6(10) = |1, 3, 7, 9| =4 (11) = |1, 2,3,4,5,6, 7,8, 9,10| =10 如果p是素数，则(p)=(p-1), 比如(2), (5)， (11)如果p,q 是素数，则(pq)=(p)(q) (p-1)(q-

24、1),比如, (10)数论基础（续）例如： m=3, n=10; (10)=4 m(n)=34=81 ; 81 mod 10 = 1 即 81 1 mod 10 34+1 = 243 3 mod 10 (等价形式等价形式)欧拉定理欧拉定理 若整数若整数m 和和n 互素，则互素，则等价形式等价形式nmmn mod 1)(nmn mod 1)(n若m是素数， gcd （a，m）=1，则am-1 1（mod m）。 或者：若m是素数，则am mod m=a例：46 mod 7=4096 mod 7=1 mod 7 费马（费马（Fermat）小定理）小定理数论基础（续）数论基础（续）l定理2：给定两个

25、素数p, q , 两个整数 n, m ，使得n=pq, 0mn ； 则对于任意整数k ，下列关系成立： m k(n)+1 m mod n4.2.2 RSA4.2.2 RSA算法描述算法描述1取两个随机大素数p和q（保密）2计算公开的模数n=p*q(n公开)3计算秘密的欧拉函数(n) =（p-1)*(q-1)，丢弃p和q，不要让任何人知道。4随机选取整数e,满足 gcd(e, (n)=1(公开e加密密钥)5计算d满足de1(mod (n)(保密d解密密钥) 6加密：将明文x（按模为n自乘e次幂以完成加密操作，从而产生密文y（X、Y值在0到n-1范围内）。 Y=xe mod n7解密：将密文y按模

26、为n自乘d次幂。 X=Yd mod n例例设设p=13,q=17,n=pq=13*17=221, (n)=(p-1)(q-1) =12*16 =192, 取取e=71,根据（扩展）欧几里得算法求根据（扩展）欧几里得算法求e的逆元的逆元dd=e-1 mod (n)= 71-1 mod 192 =119将将e 与与n公开，而保密公开，而保密p、q及及d。即公钥是（即公钥是（e，n） 私钥是（私钥是（d，p，q）加密加密 c=me mod n = 571 mod 221 =112解密解密m=cd mod n = 112119 mod 221=5=mRSA举例：举例：1选择选择p=7,q=17。2计算

27、计算n=p*q=119，(n）=(p-1)*(q-1)=96。3选选e=5，因为，因为5和和96互素。互素。4根据根据5d mod 96=1，得，得d=77。5公钥为公钥为(5,117),密钥为密钥为77。如：明文为如：明文为P=6密文密文: C=Pe mod n = 65 mod 119 =41。解密：解密：P=Cd mod n = 4177 mod 119= 6。RSA: 例例选择两个素数: p=17 & q=11计算 n = pq =1711=187计算 (n)=(p1)(q-1) =1610=160选择 e : gcd(e,160)=1; 其中e=7RSA: 例例1计算d: de=1

28、mod 160 且d 160 ，则 d=23 （因为237=161= 10160+1）公布公钥KU=7,187保存私钥KR=23,17,11l如果待加密的消息 M = 88 (注意： 88187)l加密：C = 887 mod 187 = 11 l解密:M = 1123 mod 187 = 88 RSA：例RSA：例lBob选择 p=885320693， q=238855417， 则可以计算 n=p*q=211463707796206571， 设加密系数为 e=9007，将n和e发送给Alice。l假设Alice传递的信息是cat。 令a=01 c=03 t=20，则cat=030120=30

29、120。 Alice计算： c me 301209007 113535859035722866(mod n) 她将c传给Bob。RSA：例：例lBob已知p和q的值，他用扩展欧几里德算法计算d： de 1(mod(p-1)(q-1)， 得到 d=116402471153538991 然后Bob计算： cd 113535859035722866116402471153538991 30120(mod n) 由此他可以得到最初的信息。RSA 算法的性能l速度软件实现比DES 慢100倍硬件实现比DES慢1000倍512位768位1024位加密0.030.050.08解密0.160.480.93签名

30、0.160.520.97验证0.020.070.08RSA算法的脆弱性算法的脆弱性不能证明不能证明RSA密码破译等同于大数因子分解密码破译等同于大数因子分解速度问题速度问题 提高提高pq将使开销指数级增长将使开销指数级增长至少有至少有9个明文，加密后不变，即个明文，加密后不变，即me mod n=m普通用户难于选择普通用户难于选择p、q。对。对p、q的基本要求：的基本要求： p、q不相同，即不要太接近，又不能差别太大不相同，即不要太接近，又不能差别太大 p-1、q-1都有大素数因子，增加猜测都有大素数因子，增加猜测(r) 难度难度 gcd( p-1,q-1)应当小应当小P、q选择不当，则变换周

31、期性、封闭性而泄密选择不当，则变换周期性、封闭性而泄密 例：例：p=17，q=11，e=7，则，则n=187。设。设m=123，则，则 C1=1237 mod 187=183 C2=1837 mod 187=72 C3=727 mod 187=30 C4=307 mod 187=123 明文明文m经过经过4次加密，恢复成明文。次加密，恢复成明文。总之，总之，RSA对用户要求太苛刻，密钥不能常更换。对用户要求太苛刻，密钥不能常更换。RSARSA算法的特点之一是数学原理简单、在工算法的特点之一是数学原理简单、在工程应用中比较易于实现，但它的单位安全程应用中比较易于实现，但它的单位安全强度相对较低。

32、目前用国际上公认的对于强度相对较低。目前用国际上公认的对于RSARSA算法最有效的攻击方法算法最有效的攻击方法-一般数域筛一般数域筛(NFS)(NFS)方法去破译和攻击方法去破译和攻击RSARSA算法，它的破算法，它的破译或求解难度是亚指数级的。译或求解难度是亚指数级的。 依赖于大数分解，但是否等同于大数分解一直未能证依赖于大数分解，但是否等同于大数分解一直未能证明。不管怎样，分解明。不管怎样，分解n是最显然的攻击方法。是最显然的攻击方法。 1994年年4月月26日，美国各大媒体报道：由日，美国各大媒体报道：由RSA发明人在发明人在17年前出的年前出的129位数字已被因子分解位数字已被因子分解

33、. 目前，已能分解目前，已能分解140位十进制的大素数。因此，模数位十进制的大素数。因此，模数n必须选大一些。必须选大一些。 RSA最快的情况也比最快的情况也比DES慢上慢上100倍，无论是软件还倍，无论是软件还是硬件实现。速度一直是是硬件实现。速度一直是RSA的缺陷。一般只用于少量的缺陷。一般只用于少量数据加密。数据加密。RSA 的安全性的安全性4.3基于离散对数的公开密钥密码体制4.3.1 对数与Zp上的离散对数问题lc=adld=logac lZp 上的离散对数问题是指对于循环群Zp（p是一个素数）a Zp是群Zp的生成元，对于任意c Zp，寻找唯一整数d（0=d=p-1)满足cad（mod p)l我们把整数d记为logac ，并称之为离散对数4.3.1 对数与Zp上的离散对数问题l建立在Zp上的公开密钥算法：Diffie-Hellman密