文档介绍：2017-2-28 1第四章: 公钥密码一、公钥密码的基本概念二、公钥密码 RSA 三、背包公钥密码四、公钥密码 Rabin 五、 ElGamal 公钥密码六、公钥密码 NTRU 七、椭圆曲线公钥密码 ECC 八、 McEliece 公钥密码 2017-2-28 2一、公钥密码的基本概念双钥密码体制(公钥密码体制) 于1976 年由 W. Diffie 和 M. Hellman[1976] 提出,同时 R. Merkle[1978] 也独立提出了这一体制。可用于保密通信,也可用于数字签字。这一体制的出现在密码学史上是划时代的事件,它为解决计算机信息网中的安全提供了新的理论和技术基础。公钥体制的基本原理是陷门单向函数。 2017-2-28 3一、公钥密码的基本概念一个函数 f:A?B,若它满足: 1 o对所有 x?A,易于计算 f(x)。 2 o对“几乎所有 x?A”,由 f(x)求x“极为困难”,以至于实际上不可能做到。则称 f为一单向( One-way) 函数。定义中的“极为困难”是对现有的计算资源和算法而言。陷门单向函数( Trapdoor one-way function) , 是这样的单向函数: ?在不知陷门信息下, 由f(x)求x“极为困难”,; ?当知道陷门信息后, 由f(x)求x是易于实现的。 2017-2-28 4单向函数举例离散对数 DL 。给定一大素数 p (比如, p在2 1024 数量级), p-1 含另一大素数因子。称 log 2p 为素数 p的长度。{1, 2,…, p -1} 关于 mod p 乘法构成了一乘群 Z p*, 它是一个 p-1 阶循环群。该循环群的生成元一共有φ(p -1) 个。?设一个生成元为整数 g,1< g<p-1。?设一个整数 x,1< x<p-1。?设y满足 y= g x mod p。 2017-2-28 5单向函数举例已知 x,g,p,求 y= g x mod p容易。这是因为,采用折半相乘,只需要不超过 2log 2p 次的 mod p乘法运算。(实际上只需要不超过 2log 2x次的 mod p乘法运算。如x =15=1111 2, g 15 mod p =((( g) 2g) 2g) 2g mod p, 要用 6次 mod p乘法) 2017-2-28 6单向函数举例若已知 y,g,p,求x满足 y= g x mod p,称为求解离散对数问题。记为 x= log g y mod p。求解离散对数问题的“最笨的方法”当然就是穷举,对每一个 x∈{0, 1, 2, …, p-1}检验是否 y= g x mod p。穷举求解法的运算次数约为( p- 1)/2 。许多求解离散对数问题的算法比穷举快得多,比如 Shanks 算法, Pohlig-Hellman 算法等。最快求解法的运算次数约为数量级))) ln )(ln (ln (exp( ppO 2017-2-28 7单向函数举例这个计算量称为亚指数计算量。这是什么概念呢? 我们知道 p的长度是 log 2p。看以下的不等式。当 log 2p≈1024 时, 亚指数计算量不小于 2 100数量级。至少在在当前的计算水平之下是不能实现的。. log ~ ln )) ln )(ln ln (ln exp( )) ln )(ln (ln exp( ;2 )) )(ln (ln exp( )) ln )(ln (ln exp( 2 log 2pp pp pp p pppp p??????? 2017-2-28 8单向函数举例大整数分解 FAC 。设有二大素数 p和q。设 n= pq。若已知 p和q,求 n= pq只需一次乘法。但若已知 n,求p和q 满足 n= pq ,则称为大整数分解问题。迄今为止,已知的各种算法的渐近运行时间约为: 试除法: n /2。二次筛( QS) : 椭圆曲线( EC) : 数域筛( NFS) : ) ln ln ln (exp nnO) ln ln ln2 (exp ppO)) ln (ln ) (ln 92 .1 (exp( 3 23 1nnO 2017-2-28 9单向函数举例背包问题。已知向量 A =( a 1, a 2, …, a N),a i为正整数, 称其为背包向量,称每个 a i为物品重量。给定向量 x =(x 1, x 2,…, x N),x i?{0, 1} , 求和式(称为背包重量) S = a 1x 1 + a 2x 2+…+a Nx N 容易,只需要不超过 N-1 次加法。但已知 A和S,求x 则非常困难,称其为背包问题,又称作子集和( Subset-Sum) 问题。一般只能用穷举搜索法,有 2 N种可能。 N大时,相当困难。 2017-2-2