北京大学：《网络信息安全》课程教学资源（讲稿）第三讲 公钥密码算法

《网络信息安全》课程 第三讲公钥密码算法 主讲:段云所副教授 北京大学计算机系

网络信息安全 课程 第三讲 公钥密码算法 主讲 段云所 副教授 北京大学计算机系 北京大学计算机系

问题的提出 (1)密钥管理量的困难 传统密钥管理:两两分别用一对密钥时,则n个用 户需要C(n2)=mn-1)2个密钥,当用户量增大时,密 钥空间急剧增大。如 n=100时,C(1002)=4995 n=500时,C(500212,497,500 (2)数字签名的问题 传统加密算法无法实现抗抵赖的需求

1 密钥管理量的困难 传统密钥管理 两两分别用一对密钥时 则n个用 户需要C(n,2)=n(n-1)/2个密钥 当用户量增大时 密 钥空间急剧增大 如: n=100 时 C(100,2)=4,995 n=5000时 C(5000,2)=12,497,500 2 数字签名的问题 传统加密算法无法实现抗抵赖的需求 问题的提出

公钥加密模型 加密 解密 密钥 密钥 密文 明文 明文 加密算法 解密算法

公钥加密模型 明文 明文 密文 加密算法 解密算法 加密 密钥 解密 密钥

1什么是公钥密码体制 ·公钥密码又称为双钥密码和非对称密码,是1976年由 Diffie和 Hellman在其“密码学新方向”一文中提出的,见划时代的文献: W. Diffie and M.E. Hellman, New Directrions in Cryptography, IEEE Transaction on Information Theory, V.IT-22 No 6, Nov 1976, PP. 644-654 单向陷门函数是满足下列条件的函数f: (1)给定x,计算y=fx)是容易的; (2)给定y,计算x使y=fx)是困难的 (所谓计算x=F(Y困难是指计算上相当复杂,已无实际意义。)

1 什么是公钥密码体制 •公钥密码又称为双钥密码和非对称密码 是1976年由Diffie和 Hellman在其“密码学新方向”一文中提出的 见划时代的文献 W.Diffie and M.E.Hellman, New Directrions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654 单向陷门函数是满足下列条件的函数f (1)给定x 计算y=f(x)是容易的 (2)给定y, 计算x使y=f(x)是困难的 (所谓计算x=f-1(Y)困难是指计算上相当复杂 已无实际意义 )

(3)存在8,已知δ时对给定的任何y,若相应的x存在, 则计算x使y=fx)是容易的 注:1:仅满足(1)、(2)两条的称为单向函数;第(3)条称为 陷门性,δ称为陷门信息。 2·当用陷门函数f作为加密函数时,可将讼开,这 相当于公开加密密钥。此时加密密钥便称为公开钥, 记为Pk。f函数的设计者将δ保密,用作解密密钥, 此时δ称为秘密钥匙,记为Sk。由于加密函数是公开 的,任何人都可以将信息x加密成y=x),然后送给函 数的设计者(当然可以通过不安全信道传送);由于 设计者拥有Sk,他自然可以解出x=F(y) 3单向陷门函数的第(2)条性质表明窃听者由截获的 密文y=fx)推测x是不可行的

(3)存在 已知 时,对给定的任何y 若相应的x存在 则计算x使y=f(x)是容易的 注 1*. 仅满足(1) (2)两条的称为单向函数 第(3)条称为 陷门性 称为陷门信息 2*. 当用陷门函数 f 作为加密函数时 可将f公开 这 相当于公开加密密钥 此时加密密钥便称为公开钥 记为Pk f函数的设计者将 保密 用作解密密钥 此时 称为秘密钥匙 记为Sk 由于加密函数是公开 的 任何人都可以将信息x加密成y=f(x) 然后送给函 数的设计者 当然可以通过不安全信道传送 由于 设计者拥有Sk 他自然可以解出x=f-1(y) 3*.单向陷门函数的第(2)条性质表明窃听者由截获的 密文y=f(x)推测x是不可行的

算法代表 背包算法 RSA(Rivest, shamir, adleman 椭圆曲线(ECC, Elliptic Curve Cryptography)

背包算法 RSA(Rivest, Shamir, Adleman) 椭圆曲线 ECC, Eilliptic Curve Croptography) 算法代表

2背包问题 背包问题描述:已知一长度为b的背包及长度分别为aa2an的n 个物品。假定这些物品的直径与背包相同,若从这些物品中选出若 千个正好装满这个背包。那么,究竟是那些物品? 即求解 ∑a:x=b 其中a和b都是正整数。 背包问题是著名的mp完备类困难问题,至今没有好的求解方法。 而对2中可能进行搜索,实际上是不可能的

2 背包问题 背包问题描述 已知一长度为b的背包及长度分别为a1,a2,…an的n 个物品 假定这些物品的直径与背包相同 若从这些物品中选出若 干个正好装满这个背包 那么 究竟是那些物品 即求解 n Σ aixi=b i=1 其中 ai和b都是正整数 背包问题是著名的np完备类困难问题 至今没有好的求解方法 而对2n中可能进行搜索 实际上是不可能的

MH背包公钥密码 背包公钥密码: 选取正整数a1a2.an作为公钥,明文位串为m=mm2mn。利 用公钥加密问题c=a1m+a2m2+…+anmn 从明文c求明文m等价于背包问题。 MH背包公钥密码: 其背包系列a1a22是由超递增系列b12b,(b>∑b)经 MH(Merkle-Hellman)变换a= wb, (mod m得到的。虽然a1a2an不 具有超递增性,但可经变换后成为超递增系列求解

MH背包公钥密码 背包公钥密码 选取正整数a1,a2,…an作为公钥 明文位串为m=m1m2…mn 利 用公钥加密问题 c= a1 m1+ a2 m2+… +an mn. 从明文c求明文m等价于背包问题 MH背包公钥密码 i-1 其背包系列a1,a2,…an是由超递增系列b1,b2,…bn , bi> Σ bj) 经 j=1 MH(Merkle-Hellman)变换ak=wbk(mod m)得到的 虽然a1,a2,…an不 具有超递增性 但可经变换后成为超递增系列求解

3 Diffie-Hellman密钥交换算法 Di6和 Hellman在其里程碑意义的文章中,虽然给出了 密码的思想,但是没有给出真正意义上的公钥密码实例,也 没能找出一个真正带陷门的单向函数。然而,他们给出单向 函数的实例,并且基于此提出 Diffie-hellman密钥交换算法。 这个算法是基于有限域中计算离散对数的困难性问题之上: 设F为有限域,g∈F是F的乘法群FF{0}=。并且对 任意正整数x,计算g是容易的;但是已知g和y求x使y=g, 是计算上几乎不可能的。这一问题称为有限域F上的离散对 数问题。公钥密码学中使用最广泛的有限域为素域Fp 对 Diffie-Hellman密钥交换协议描述: Alice和Bob协商 好一个大素数p,和大的整数g,1<gp,p和g无须保密,可 为网络上的所有用户共享

3.Diffie-Hellman密钥交换算法 Diffie 和Hellman在其里程碑意义的文章中 虽然给出了 密码的思想 但是没有给出真正意义上的公钥密码实例 也 没能找出一个真正 带陷门的单向函数 然而 他 们给出单向 函数的实例 并且基于此提出Diffie-Hellman密钥 交换算法 这个算法是 基于有限域中计算离散对数的困难性问题 之 上 设 F为有限域 g F 是 F 的 乘 法 群 F *=F\{0}= 并且 对 任意正整数 x 计算 g x是容易的 但是已知 g 和 y 求 x 使y= g x 是计算上几乎不可能的 这一问题称为有限域 F上的离散 对 数问题 公钥密码学中使用最广泛的有限域 为素域 F P. 对Diffie-Hellman密钥 交 换协议描述 Alice 和Bob协商 好一个大 素 数 p 和大的整数 g 1<g<p p 和 g 无 须保密 可 为网络上的所有用户共享

当 Alice和Bob要进行保密通信时,他们可以按如下步骤来做: 1) Alicei选取大的随机数x,并计算X=gY(mdP) (2Bob选取大的随机数x,并计算X′=gx'modP) 3) Alice将X传送给Bob;Bob将Ⅹ'传送给 Alice (4) Alice计算K=(X^(modP,Bob计算K′=(X)X(modP) 易见,K=K′=gx(modP) 由(4)知, Alice和Bob已获得了相同的秘密值K。双方以K作为 加解密钥以传统对称密钥算法进行保密通信。 注: Diffie-Hellman密钥交换算法拥有美国和加拿大的专利

当Alice和Bob要进行保密通信时 他们可以按如下步骤来做 (1)Alice选取大的随机数x 并计算 X=gx(mod P) (2)Bob选取大的随机数x′ 并计算 X ′ = gx ′(mod P) (3)Alice将X传送给Bob Bob将X ′传送给Alice (4)Alice计算K=(X ′)X(mod P);Bob计算K ′ X) X ′(mod P), 易见 K=K ′ =g xx ′(mod P) 由(4)知 Alice和Bob已获得了相同的秘密值K 双方以K作为 加解密钥以传统对称密钥算法进行保密通信 注 Diffie-Hellman密钥交换算法拥有美国和加拿大的专利