现代密码学理论与实践 第10章 密钥管理和其他公钥密码体制 Fourth Edition by William Stallings Slides by 杨寿保 syang@ustc.edu.cn http://staff.ustc.edu.cn/~syang 2012年10月 2018/9/20 现代密码学理论与实践-10

本章要点 公钥密码方案是安全的，仅当公钥的真实性能够得到保证。公钥证书方案提供了必要的安全性。 一个简单的公钥算法是Diffie-Hellman密钥交换协议。这个协议使得通信双方利用基于离散对数问题的公钥算法建立秘密密钥。这个协议是安全的，仅当通信双方的真实性能够得到保证。 椭圆曲线算术可以用来开发许多椭圆曲线密码ECC方案，包括密钥交换，加密和数字签名。 就ECC而言，椭圆曲线算术是指使用定义在有限域上的椭圆曲线方程。方程里的系数和变量都是域里的元素。已经开发了很多使用Zp和GF(2m)的方案。 Opening quote. 2018/9/20 现代密码学理论与实践-10

10.1.1 密钥管理之公钥的分配 公开密码的主要作用之一就是解决密钥分配问题，公钥密码实际上可以用于以下两个不同的方面 几种公钥分配方法 公钥密码用于传统密码体制的密钥分配 几种公钥分配方法 公开发布、公开可访问的目录 公钥授权、公钥证书 公钥的公开发布 用户将他的公钥发送给另一通信方，或者广播给通信各方，比如在电子邮件后附上PGP密钥，或者发布到邮件列表上 最大问题在于任何人都可以伪造这种公钥的发布 2018/9/20 现代密码学理论与实践-10

自由的公钥发布 2018/9/20 现代密码学理论与实践-10

公开可访问的目录 维护一个动态可访问的公钥目录可以获得更大程度的安全性 一个可信实体或组织负责这个公开目录的维护和分配 目录包含{name, public-key}等项 每一通信方通过目录管理员以安全的方式注册一个公钥 通信方在任何时刻可以用新的密钥替代当前的密钥 目录定期更新 目录可通过电子方式访问 一旦攻击者获得目录管理员私钥，则可传递伪造的公钥，可以假冒任何通信方以窃取消息，或者修改已有的记录 2018/9/20 现代密码学理论与实践-10

公开可访问的目录 2018/9/20 现代密码学理论与实践-10

公钥授权 A发送带有时间戳的消息给公钥管理员, 请求B的当前公钥 管理员给A发送用其私钥KRauth加密的消息, A用管理员的公钥解密，可以确信该消息来自管理员： B的公钥KUb，用来加密； 原始请求，A可以验证其请求未被修改； 原始时间戳, A可以确定收到的不是来自管理员的旧消息。 A保存B的公钥, 并用它对包含A的标识IDA和Nonce1的消息加密, 然后发送给B B以同样方式从管理员处得到A的公钥 B用KUa对A的N1和B的N2加密, 发送给A A用B的公钥对N2加密并发送给B, 使B相信其通信伙伴是A 2018/9/20 现代密码学理论与实践-10

公钥分配方案 2018/9/20 现代密码学理论与实践-10

10.1.2 公钥证书 有了公钥证书使得不通过实时访问公钥授权部门而实现公钥交换成为可能 公钥证书将一个通信方的身份与他的公开密钥绑定在一起，通常还包括有效期和使用方法等 证书的所有内容必须经由可信公钥授权方或者证书授权方签名后方可生效 知道公钥授权当局公开密钥的任何人都可以验证一个用户的公开密钥证书的有效性 对于申请者A，管理员提供的证书为： CA = EKRauth [T, IDA, KUa] 其他人读取并验证： DKUauth[CA]=DKUauth [EKRauth [T, IDA, KUa]]=(T, IDA, KUa) 2018/9/20 现代密码学理论与实践-10

公钥证书的交换 2018/9/20 现代密码学理论与实践-10

10.1.3 利用公钥密码分配传统密码体制的密钥 采用前述方法获得的公开密钥可以用于保密和认证之需 公钥密码算法速度较慢，因此更适合作为传统密码中实现秘密密钥分配的一种手段 因此，需要产生会话密码来加密 已经有一些方法用来协商适当的会话密钥 2018/9/20 现代密码学理论与实践-10

一种简单的秘密密钥分配方法 Merkle在1979提出一种简单的方法 这个协议不安全，因为会受到中间人攻击 A产生公/私钥对{PUa,PRa}, 将含有PUa和标识IDA的消息发给B B产生秘密密钥(会话密钥)Ks, 并用A的公钥加密后发给A A解密D(PRa,E(PUa,Ks), 得到Ks, 这样双方即可通信 这个协议不安全，因为会受到中间人攻击 2018/9/20 现代密码学理论与实践-10

具有保密性和真实性的密钥分配 2018/9/20 现代密码学理论与实践-10

10.2 Diffie-Hellman密钥交换 Diffie和Hellman在1976年首次提出了公钥算法，给出了公钥密码学的定义，该算法通常被称为Diffie-Hellman密钥交换算法 Diffie-Hellman密钥交换算法是一种公钥分发机制 它不是用来加密消息的 所生成的是通信双方共享的会话密钥，必须保密，其值取决于通信双方的私钥和公钥信息 Diffie-Hellman密钥交换算法是基于有限域GF中的指数运算的(模一素数或多项式) Diffie-Hellman密钥交换算法的安全性依赖于求解离散对数问题DLP 2018/9/20 现代密码学理论与实践-10

离散对数问题Discrete Logarithm Problem 如果a是素数p的一个原根(本原元素)，则 a mod p, a2 mod p, ......, ap-1 mod p，生成模p的完全剩余集{1, 2, ......, p-1} 对于所有素数，其原根必定存在，即 对于一个整数b和素数p的一个原根a，可以找到唯一的指数i, 使得 b = ai mod p, 其中 0<= i <= p-1 指数i称为b的以a为基数的模p的离散对数或者指数。 离散对数密码体制的安全性基于DLP问题, 在已知C和P的情况下, 由d求M很容易, 由M求d很困难, d = logCM in GF(P), 最快的算法需要T=exp((ln(P)lnln(P)1/2)次运算。当P是200位时, T = 2.7x1011, 如果1μs解一次, 需要2~3天；如果P = 664位, 则T = 1.2x1023, 约1012天或2.739x109年, 约2.7亿年. 只要P足够大,可以达到足够安全。 2018/9/20 现代密码学理论与实践-10

Diffie-Hellman Key Exchange 通信双方约定一个大素数(或多项式)p, 和模p的一个素根α 各方产生公开密钥 选择一个秘密钥(数值)，如xA< p， xB< p 计算公钥, 如yA = αxA mod p, yB = αxB mod p, 并相互交换 双方共享的会话密钥KAB可以如下算出 KAB = αxA.xB mod p = yAxB mod p (which B can compute) = yBxA mod p (which A can compute) KAB是双方用对称密码通信时共享的密钥 如果双方继续通信，可以继续使用这个密钥，除非他们要选择新的密钥 攻击者如果想要获得x, 则必须解决DLP问题 2018/9/20 现代密码学理论与实践-10

Diffie-Hellman Example Users Alice & Bob who wish to swap keys Agree on prime p=353 and α =3 Select random secret keys: A chooses xA=97, B chooses xB=233 Compute public keys: yA=397 mod 353 = 40 (Alice) yB=3233 mod 353 = 248 (Bob) Compute shared session key as: KAB= yBxA mod 353 = 24897 mod 353 = 160 (Alice) KAB= yAxB mod 353 = 40233 mod 353 = 160 (Bob) 2018/9/20 现代密码学理论与实践-10

10.2.2 Diffie-Hellman密钥交换协议 本协议不能抵抗中间人攻击 2018/9/20 现代密码学理论与实践-10

基于DLP的概率密码系统 ElGamal Cryptosystem 假设A和B互相通信，共享大素数p，本原元素α，0≤m≤p-1 加密： A选择k∈[0, p-1], k的作用其实即为xA, A访问公共区域找到B的公开密钥YB = αxB mod p, 计算： K = (YB)k mod p, 即K = αxBk mod p c1 = αk mod p c2 = mK mod p 密文即为 (c1, c2) 解密： B首先恢复K：K = c1xB mod P = αkxB mod p 然后恢复m：m = c2/K mod P = c2K-1 mod p 2018/9/20 现代密码学理论与实践-10

ElGamal Cryptosystem 这里特别注意，k不能重复使用，如果 (1) c1,1 =αk mod p c2,1 = m1K mod p (2) c1,2 = αk mod p c2,2 = m2K mod p 得：m1/m2 = c2,1/c2,2 mod p. 如果m1已知，m2即可算出。 ElGamal密码体制是概率密码体制，同样的明文每次加密得到不同的密文, 因为每次随机选择k。 ElGamal密码体制加密效率是50%，因为密文大小是明文的两倍。 ElGamal密码体制的破译难度同Diffie-Hellman的方法,即基于DLP，离散对数问题，最快的算法需要T=exp((ln(p)lnln(p)1/2)次运算。 2018/9/20 现代密码学理论与实践-10

ElGamal Cryptosystem 例：P = 17, α= 3, xA = 2, xB = 5, m = 11, m从A发送到B, A选择k = 7. 求：密文(c1, c2)并解密 加密：YA = αxA mod P = 32 mod 17 = 9 YB = αxB mod P = 35 mod 17 = 5 K = (YB)k mod P = 57 mod 17 = 10 c1 = αk mod P = 37 mod 17 = 11 c2 = mK mod P = 10x11 mod 17 = 8 所以，密文C = (c1, c2) = (11, 8) 解密：K = c1xB mod P = 115 mod 17 = 10 c2 = mK mod P = 10m mod 17 = 8 m = c2/K mod P = c2K-1 mod P K K-1 mod P = 1，即10 K-1 mod 17 = 1，得K-1 = 12 所以，明文m = c2K-1 mod P = 8x12 mod 17 = 11 2018/9/20 现代密码学理论与实践-10

10.3 椭圆曲线算术 椭圆曲线密码编码学ECC 椭圆曲线并非椭圆, 它指的是由Weierstrass威尔斯特拉斯方程所确定的平面曲线： 使用椭圆曲线密码系统ECC,可以达到如RSA, D-H同样的安全但位数要小得多。 椭圆曲线并非椭圆, 它指的是由Weierstrass威尔斯特拉斯方程所确定的平面曲线： y2 + axy + by = x3 + cx2 + dx + e 一般形式： y2 = x3 + ax + b 满足上述方程的数偶(x, y)称为椭圆曲线E上的点。 同时定义无穷点(point at infinity)或零点(zero point)的O。 2018/9/20 现代密码学理论与实践-10

实数域上的椭圆曲线 一般形式 具有不同根的条件 例子 2018/9/20 现代密码学理论与实践-10

椭圆曲线举例 (a) y2=x3-x (b) y2=x3+x+1 2018/9/20 现代密码学理论与实践-10

单位元和逆元 逆元： P+P’=O 单位元 P’(x, -y)=P(x, y) 关于X轴对称点。 P+O=P 2018/9/20 现代密码学理论与实践-10

椭圆曲线上的形式加法 如果椭圆曲线上的三个点处于一条直线上, 那么它们的和为O。加法规则： O是加法的单位元(additive identity), O = －O；对于椭圆曲线上的任一点P, 有 P + O = P。 一条垂直线与曲线相交于P1=(x, y)和P2=(x, －y), 也相交于无穷点O, 有P1+P2+O = O和 P1 = －P2。 对具有不同的x坐标的Q和R相加, 在它们之间画一条直线求出第三个交点P1, 这种交点是唯一的。因为Q+R+P1=O, 因此Q+R=－P1 对点Q加倍, 画一切线求出另一交点S, 则Q+Q=2Q=－S 一条椭圆曲线上的一点P被一个正整数k相乘的乘法被定义为k个P的相加 2018/9/20 现代密码学理论与实践-10

椭圆曲线的加法 椭圆曲线上的点集及其上的加法操作构成一个群 点集 操作 椭圆曲线上的所 有点和无穷点 点加法 R=P+Q （或 R=P*Q） 2018/9/20 现代密码学理论与实践-10

点的累加 二倍 过点P(x, y)的切线 R=P+P 2018/9/20 现代密码学理论与实践-10

反复累加 kP=P+…+P 或写为： 2018/9/20 现代密码学理论与实践-10

数学描述 直线g: y=sx+y0 与曲线相交： (sx+y0)2=x3+ax+b R点坐标： 其中： 2018/9/20 现代密码学理论与实践-10

数学描述 切线g：y=sx+y0 与曲线相交： (sx+y0)2=x3+ax+b R点坐标： 2018/9/20 现代密码学理论与实践-10

有限域上的椭圆曲线 Finite Elliptic Curves 可以将椭圆曲线定义于有限域GFP上 y2=x3+ax+b mod p p是一个素数, 并且 {0, 1, …, p-1}是模p加的交换群(Abelian)； {1, …, p-1}是模p乘的交换群 椭圆曲线密码系统采用变量和系数有限的曲线来实现 2018/9/20 现代密码学理论与实践-10

两种有限域上的椭圆曲线 定义在Zp上的素曲线(prime curves)Ep(a,b) 定义在GF(2n)上的二元曲线E2n(a,b) 最适合用软件实现 定义在GF(2n)上的二元曲线E2n(a,b) 变量和系数取自GF(2n), 模素多项式(二进制多项式) 最适合硬件实现 Ep(a,b)表示满足下列条件的模p椭圆群, 群中元素(x, y)是满足如下方程的小于p的非负整数另外加上无穷点O：y2 mod p = (x3+ax+b) mod p. 例如： p=23, 有4a3+27b2=4x13+27x12 mod 23 =8≠0, 满足条件(这里a, b =1) 2018/9/20 现代密码学理论与实践-10

椭圆曲线E23(1,1)上的点 对于每个满足0≤x<p的x, 计算y2=x3+x+1 mod p 对于上一步得到的每个结果确定它是否有一个模p的平方根, 如果没有, 在E23(1,1)中就没有具有这个x值的点；如果有, 就有两个满足平方根运算的y值(除非这个值是单个的y值0)。这些(x, y)就是E23(1,1)上的点 2018/9/20 现代密码学理论与实践-10

椭圆曲线E23(1,1)上的点 2018/9/20 现代密码学理论与实践-10

椭圆曲线上的点 在GF11上找出满足椭圆曲线方程的点P(x, y): y2=x3+x+6 mod 11 有12个点, 加上无穷远点O共有n=13个元素 2018/9/20 现代密码学理论与实践-10

椭圆曲线点加运算 将y2=x3+x+6 mod 11上的点(2, 4) 反复累加 计算2P=P+P （或记为 P2=P*P ) 计算3P=P+P+P=2P+P（或记为P3=P*P*P=P2*P) 所有运算均在GF11上进行 2018/9/20 现代密码学理论与实践-10

椭圆曲线点加运算 取P(2, 4), 计算2P=P+P （或记为P2=P*P ) 再计算3P=P+P+P=2P+P （或记为P3=P2*P ) 2018/9/20 现代密码学理论与实践-10

GF(2n)上的椭圆曲线 有限域GF(2n)由2n个元素及定义在多项式上的加法和乘法运算组成 给定某n, 对于GF(2n)上的椭圆曲线，使用变元和系数均在GF(2n)上取值的三次方程，且利用GF(2n)中的算术运算规则来进行计算 可以证明，GF(2n)上适合椭圆曲线密码应用的三次方程与Zp上的三次方程有所不同，形为 y2+xy=x3+ax2+b 其中变元x和y以及系数a和b是GF(2n)中的元素，计算在GF(2n)中进行 2018/9/20 现代密码学理论与实践-10

GF(2n)上的椭圆曲线 考虑所有整数对(x, y)和无穷远点O组成的集合E2n(a,b) 例如，使用不可约多项式f(x)=x4+x+1(10011)定义的有限域GF(24)，其生成元g满足f(g)=0, 即g1=0010, g4=g+1, 或二进制0011, g5=(g4)(g)=g2+g=0110 g0=0001 g4=0011 g8=0101 g12=1111 g1=0010 g5=0110 g9=1010 g13=1101 g2=0100 g6=1100 g10=0111 g14=1001 g3=1000 g7=1011 g11=1110 g15=0001 2018/9/20 现代密码学理论与实践-10

GF(2n)上的椭圆曲线 例如，考虑椭圆曲线y2+xy=x3+g4x2+1, a=g4=0011, b=g0=0001, 满足该方程的一个点(x, y)为(g5, g3)： (g3)2+(g5)(g3)=(g5)3+(g4)(g5)2+1 g6+g8=g15+g14+1 1100+0101=0001+1001+0001 1001=1001 2018/9/20 现代密码学理论与实践-10

2018/9/20 现代密码学理论与实践-10

10.4 椭圆曲线密码学 大多数公开密钥密码系统如RSA, D-H都使用具有非常大数目的整数或多项式，计算量大，密钥和报文存储量也极大。使用椭圆曲线密码系统ECC，可以达到同样安全但位数要小得多。 ECC的加类似于模乘，ECC的重复加类似于模指数 ECC需要有对应于DLP的难解问题 Q=kP, Q, P属于Ep(a, b), k<P 给定k, P, 容易计算Q=kP 但是给定Q, P, 求k难 这就是椭圆曲线对数问题 2018/9/20 现代密码学理论与实践-10

椭圆曲线对数问题 给定曲线 通过连续自加k-1次计算 目前存在这样的快速算法。 问题：当Q已知时能否计算k? 答案：这是一个被称为椭圆 y2=x3+ax+b mod p 以及其上一点P，我们可以 通过连续自加k-1次计算 Q=kP, (或Q=Pk)。 目前存在这样的快速算法。 问题：当Q已知时能否计算k? 答案：这是一个被称为椭圆 曲线对数的难题。 2018/9/20 现代密码学理论与实践-10

椭圆曲线密码学 例：E23(9, 17), 即y2=(x3+9x+7) mod 23, 以P=(16,5)为底的Q=(4, 5)的离散对数k为多少？ 可以通过穷举攻击方法，多次计算P的倍数直至找到Q为止，这样 P=(16,5);2P=(20,20);3P=(14,14);4P=(19,20); 5P=(13,10);6P=(7,3);7P=(8,7);8P=(12,17); 9P=(4,5) 所以, 以P=(16,5)为底的Q=(4,5)的离散对数k为9 实际应用中，k的值非常大，穷举攻击不可行 2018/9/20 现代密码学理论与实践-10

椭圆曲线密码学 椭圆曲线密码系统的定义 椭圆曲线公钥系统 域标识：定义椭圆曲线采用的有限域 椭圆曲线：系数a和b 基准点(base)：指定的椭圆曲线上的点P 阶(order)：P点的阶n，使得nP=O 椭圆曲线公钥系统 EP(a, b), GFP Base point P(x, y) 选择 e 作为私有密钥 公开密钥为Q=eP 2018/9/20 现代密码学理论与实践-10

10.4.1Diffie-Hellman的椭圆曲线实现 选定椭圆曲线上一点G A、B分别随机选取a, b并保密 A QA= aG B QB= bG A: Q=a(QB) =abG B: Q=b(QA)=baG=abG 2018/9/20 现代密码学理论与实践-10

2018/9/20 现代密码学理论与实践-10

ECC与Diffie-Hellman密钥交换的类比 类似于D-H，ECC也可以实现密钥交换 用户选择合适的ECC, Ep(a,b) 选择基点G=(x1, y1), 满足nG=O的最小n是一个大素数 A和B之间的密钥交换如下 A和B选择私钥nA<n, nB<n 计算公钥PA=nA×G, PB=nB×G A与B交换PA 和 PB 计算共享密钥K=nA×PB= nB×PA, 因为K=nA×nB×G，所以这两个密钥是一样的。 2018/9/20 现代密码学理论与实践-10

用ECC实现Diffie-Hellman密钥交换 例如 Ep(0, -4), 即 y2=x3-4, G=(2, 2), p=211,n=240; 计算 240G=O nA=121, PA=121(2, 2)=(115, 48) nB=203, PB=203(2, 2)=(130, 203) K = 121(130, 203) =203(115, 48)=(161, 69) 2018/9/20 现代密码学理论与实践-10

Massey-Omura公钥体制 A meA B meA eB (meA eB)da = meB 在GF(q)上, 用户A的加密、解密密钥为eA, dA gcd(eA,q-1)=1, eAdA =1 mod (q-1) 同样, 用户B的加密、解密密钥为eB, dB gcd(eB,q-1)=1, eBdB =1 mod (q-1) A将消息m发送给B: A meA B meA eB (meA eB)da = meB B: ( meB )dB = m 2018/9/20 现代密码学理论与实践-10

Massey-Omura在椭圆曲线上实现 m嵌入椭圆曲线上的点Pm n：椭圆曲线上的点数(已知大素数) 用户随机选择e：1<e<n, gcd(e, n)=1, ed=1 mod n A将消息m发送给B： A eAPm B eBeAPm dA( eBeAPm )= eBPm B: dB( eBPm )=Pm 2018/9/20 现代密码学理论与实践-10

ElGamal算法在椭圆曲线上实现 E(a, b), base point G 属于E A选择a并保密, 0<a<n，n为G的阶(order) aG公开 B向A发送消息m B将m嵌入点Pm，选择随机数k, A (kG, Pm +k(aG)) B A： Pm = Pm +k(aG) –a(kG) 本质上：A,B共享秘密akG 2018/9/20 现代密码学理论与实践-10

10.4.2 椭圆曲线加/解密 首先将明文消息m编码为x-y的点Pm, 点Pm就是要进行加密和解密的, 不能简单地把消息编码为点的x坐标或y坐标，因为并不是所有的坐标都在Eq(a,b)中。 类似于D-H密钥交换，加解密系统也需要点G和椭圆群Eq(a,b)这些参数。 用户A选择私钥nA<n, 并产生公钥PA=nA×G 用户B选择私钥nB<n, 并产生公钥PB=nB×G AB: Pm A随机选择一个正整数k, 加密点Pm产生密文： Cm={kG, Pm+kPB} B解密Cm, 计算： Pm+kPB–nB(kG) = Pm+k(nBG)–nB(kG) = Pm 2018/9/20 现代密码学理论与实践-10

ECC Encryption/Decryption 例如, Ep(-1,188), 即y2=x3-x+188, G=(0,376), p=751 A要向B发送消息 Pm=(562, 201) A首先随机选择k=386, 并获得B的公钥PB=(201,5) 计算kG=386(0, 376)=(676, 558) Pm+ kPB = (562, 201) + 386(201, 5)=(385, 328) 这样, 密文即为 Cm={kG, Pm+kPB}={(676, 558), (385, 328)} B要解密 Pm+kPB–nB(kG) = Pm+k(nBG)–nB(kG) = Pm 2018/9/20 现代密码学理论与实践-10

椭圆曲线密码的安全性 ECC的安全性是建立在由kP和P确定k的难度之上的，即椭圆曲线对数问题elliptic curve logarithm problem，Pollard rho方法是已知求椭圆曲线对数问题的最快方法。 相比FAC，可以使用比RSA短得多的密钥 在密钥长度相同时，ECC与RSA所执行的计算量也差不多 与具有同等安全性的RSA相比，由于ECC使用的密钥更短，所以ECC所需的计算量比RSA少 2018/9/20 现代密码学理论与实践-10

椭圆曲线密码与RSA的效率比较 2018/9/20 现代密码学理论与实践-10

Equivalent Cryptographic Strength 2018/9/20 现代密码学理论与实践-10

第10章习题 第四版：1, 7, 8, 10, 11, 12, 13, 16 提示：16题可以利用如下列表 Due: Nov. 20, 2012 2G = (5, 2) 3G = (8, 3) 4G = (10, 2) 5G = (3, 6) 6G = (7, 9) 7G = (7, 2) 8G = (3, 5) 9G = (10, 9) 10G = (8, 8) 11G = (5, 9) 12G = (2, 4) 13G = (2, 7) 2018/9/20 现代密码学理论与实践-10