现代密码学第七讲：公钥密码学

1 公钥密码（一） 现代密码学 第七章 上讲内容回顾 单向函数 Hash函数的定义 MD5算法 SHA-256算法 SHA-512和 SHA-384算法 消息鉴别码简介 CBC-MAC算法 HMAC算法 3 本章主要内容 公钥密码体制的提出及分类 公钥密码体制的基本概念 单向陷门函数的概念 设计公钥加密算法 -背包密码体制 RSA算法及攻击方法 ElGmal算法及椭圆曲线密码体制 密钥分配 ：加密者指定一个密钥后，必须得 想方设法把密钥分发出去给解密者，同时还 得小心翼翼确保密钥不被泄露。这是对称密 码算法固有的一个矛盾，如何解决呢？ 对称密码进行密钥分配的要求： 已经共享一个密钥： 利用密钥分配中心： 第一个密钥如何获得 和 KDC之间的密钥如何获得 公钥密码体制的提出 密钥管理 ：在有多个用户的网络中，任何两 个用户之间都需要有共享的秘密钥，当网络 中的用户 n很大时，需要管理的密钥数目是 n *（ n-1） /2 无签名功能 当主体 A收到主体 B的电子文挡 （电子数据）时，无法向第三方证明此电子 文档确实来源于 B。 公钥密码体制的提出 6 公钥加密体制的原理 邮箱的例子 任何人可以向邮箱投举报信 用户 (审计人员 )才能打开邮箱，读信的内容 7 公钥加密模型 公钥加密体制的原理 密钥分配 8 参数生成过程： 1） 要求接收消息的端系统，产生一对用来加密和 解密的密钥，如图中的接收者 B，产生一对密钥 PKB， SKB，其中 PKB是公开钥， SKB是秘密钥 . 2）端系统 B将加密密钥（图中的 PKB）予以公开， 另一密钥被保密 (图中的 SKB). 公钥加密体制的原理 9 公钥加密体制的原理 参数生成需满足的要求： 公开密钥 (public-key), 可以被任何人知道 , 用 于加密或验证签名； 私钥 (private-key), 只能被消息的接收者或签名 者知道 ,用于解密或 签名 ； 由私钥及公开参数容易计算出公开密钥； 由公钥及公开参数推导私钥是困难的； 10 加解密过程： 1) A要想向 B发送消息 m，则使用 B的公开钥加密 m， 表示为 c=EPKBm, 其中 c是密文， E是加密算法 . 2) B收到密文 c后，用自己的秘密钥 SKB解密，表示 为 m=DSKBc，其中 D是解密算法 . 公钥密码体制的原理 11 Public Key Establishment Schemes (PKES) 用于交换秘密信息 常用于对称加密算法的密钥分配 Public Key Encryption (PKE) 用于加密任何消息 任何人可以用公钥加密消息 私钥的拥有者可以解密消息 任何公钥加密方案能够用于密钥分配方案 PKDS 一些公钥加密方案也是数字签名方案 Signature Schemes (SS) 用于生成对某消息的数字签名 私钥的拥有者生成数字签名 任何人可以用公钥验证签名 公钥密码体制的分类 12 公钥密码体制的发展历史 1976年 Diffie和 Hellman 在 密码学的新方向 中首次公开提 出了非对称密码算法的思想，但是 没有实现加密方案，只给出 一个密钥协商协议； 1978年 Rivest,Shamir和 Adleman提出应用广泛的 RSA算法； 1984年 Shamir提出 基于身份的密码体制 ， 没有实现加密体制， 只给出一个基于身份的数字签名算法 2001年 Boneh,Franklin和 Cocks分别独立提出基于身份的加密 算法 2003年 Al-Riyami提出的无证书的密码体制 公钥密码体制的发展历史 Diffie和 Hellman 公钥密码体制的发展历史 Ronald Rivest, Adi Shamir, and Len Adleman 15 基本概念： 公钥密码体制也称为双钥密码体制 /非对称 密码体制； 算法的最大特点是采用两个相关密钥将加 密和解密能力分开，其中一个密钥是公开的， 称为公开密钥，简称公开钥，用于加密；另 一个密钥是为用户专用，因而是保密的，称 为秘密密钥，简称秘密钥，用于解密 . 利用公开密钥（及公开参数）推导私有密钥 困难。 公钥加密算法的特点 16 公钥加密体制框图 公钥加密算法的特点 发 送 者 接 收 者 信 源 分 析 者 加 密 解 密无 噪 信 道 安 全 信 道 M M M C K K 密 钥 源 无 噪 信 道 17 加解密算法需满足要求： 加、解密次序可换，即 EPKBDSKB(m)=DSKBEPKB(m) 这一条虽然非常有用，但不是对所有的算法都作要求 . 加解密速度比对称算法慢， 因此公钥密码体制目前主要用于密钥 管理和数字签字 . 类似于对称算法 ,穷搜索在理论上是能够破解公钥密码 . 实际上 , 密钥足够长 (512bits)保证计算安全 . 安全性依赖于 足够大 的困难性差别，如 NP和 P问题（利用公钥及公 开参数加密明文容易计算；利用私钥及公开参数解密密文容易计 算；只利用公钥解密密文困难）； 公钥加密算法的特点 18 定义 单向函数 是两个集合 X、 Y之间的一个映 射，使得 Y中每一元素 y都有惟一的一个原像 x X，且由 x易于计算它的像 y，由 y计算它 的原像 x是不可行的 . 一个函数是 单向陷门函数 ，是指该函数是易 于计算的，但求它的逆是不可行的，除非再 已知某些附加信息。当附加信息给定后，求 逆可在多项式时间完成 . 单向陷门函数 19 单向陷门函数是一族可逆函数 fk，满足 Y=fk(X)易于计算（当 k和 X已知时） . X=f-1k(Y)易于计算（当 k和 Y已知时） . X=f-1k(Y)计算上是不可行的（当 Y已知但 k 未知时） . 研究公钥密码算法就是要找出合适的陷门单 向函数 单向陷门函数 20 背包问题 ： 设 A=(a1,a2, ,an)是由 n个不同的 正整数构成的背包向量， s是背包容积 .求 A的 子集 A，使子集中的元素 ai的和恰好等于 s. 例 . A=（ 43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523）， s=3231. 由于 3231=129+473+903+561+1165. 所以从 A中找出的满足要求的子集合是 129、 473、 903、 561、 1165. 背包密码体制 21 原则上讲，通过检查 A的所有子集，总可找 出问题的解（如果有解的话） . 上例中， A的子集共有 210=1024个（包括空集） . 如果 A中元素个数 n很大，子集个数 2n将非常 大 , 且寻找满足要求的 A的子集没有比穷搜索 更好的算法，因此背包问题是 NP问题 . 只要 n 足够大，那么，计算不可行 . 背包密码体制 背包密码体制 背包问题可以构造一个 单向函数 f. 将 x(1x2n-1)写成长为 n的二元表示 : 则， f(x)定义为 . 上例中 f(364) = f(0101101100)=129+473+903+561+1165 = 3231， 类似地可求出 : f(609)=2942, f(686)=3584, f(32)=903, f(46)=3326, f(128)=215, f(261)=2817. 12( , , , ) , 0 , 1 , 1niX x x x x i n 1 () n ii i f x A X x a f的定义可见： 已知 x很容易求 f(x)，但已知 f(x)求 x就是要解 背包问题，当 n较大时是计算不可行的 . 在实际应用中， n不能太小，至少为 200. 23 若用 f充当加密函数对明文消息 m加密 : 首先将 m写成二元表示，再将其分成长为 n的分组； 然后求每一分组的函数值，以函数值 (背 包容积 )作为密文分组 . 背包密码体制 24 例 . 背包向量仍取上例中的 A，设待加密的明文 是 SAUNA AND HEALTH. 因为 A长为 10，所以应将明文分成长为 10比特 （即两个明文字母）的分组 SA， UN， A ， AN， D ， HE， AL， TH, 其相应的二元序列为 1001100001， 1010101110， 0000100000， 0000101110， 0010000000， 0100000101， 0000101100， 1010001000. 分别对以上二元序列作用于函数 f，得密文 : （ 2942， 3584， 903， 3326， 215， 2817， 2629， 819） . 背包密码体制 若明文消息是英文文本，则可将每个字母用其在 字母表中的序号表示，再将该序号转换为二进制 形式（ 5位即可），其中符号 表示空格 25 构造单向陷门函数 f(x)，为此引入一种特殊 类型的背包向量 . 定义 背包向量 A=(a1,a2, ,an)中的元素满 足下列性质， 则称其为 超递增的 . 1 1 2 , , j ji i a a j n 背包密码体制 怎样解密？ 26 超递增背包向量对应的背包问题存在多项式 时间解法 . 解法： 已知 s为背包容积，对 A从右向左检查每 一元素，以确定是否在解中 : 1) 若 san，则 an在解中，令 xn=1；若 sai，且 gcd(t,k)=1， 即 t在模 k下有乘法逆元 . bitai mod k, i=1,2, ,n. 得新的背包向量 B=(b1,b2, ,bn)，记为 BtA mod k. 用户以 B作为自己的公开密钥 , t、 t-1和 k可作为其秘 密的陷门信息，即解密密钥 . 背包密码体制 利用超递增背包函数作加密变换， 明文接收者可以在多项式时间解密， 但是敌手如果也知道超递增背包向量， 同样也很容易解密 . 28 例： A=(1, 3, 5, 11, 21, 44, 87, 175, 349, 701)是一超递增背包向量 . 取 k=1590， t=43， 满足 gcd(43, 1590)=1. 计算得 B=(43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523). 背包密码体制 29 背包密码体制 加密运算 对明文分组 X=(x1x2 xn)的加密为 c=f(x)=BX tAX mod k 解密运算 首先由 st-1 c mod k，求出 s作为超递增背包向量 A 的容积，再解背包问题即得 x=(x1x2 xn). 因为 t-1 c mod kt-1tAX mod kAX mod k，而由 kai，知 AX701，得 x10=1；令 s=734-701=33，由 33349，得 x9=0；重复 该过程得第一个明文分组是 1001100001， 它对应的英文文本是 SA； 3) 类似地得其他明文分组 ; 4) 解密结果为 SAUNA AND HEALTH. 背包密码体制 32 背包密码体制是继 Diffie和 Hellman 1976 年提出公钥密码体制设想后的第一个公钥密 码算法 . 上述方案由 Merkle和 Hellman 于 1978年提 出 . 两年后该体制即被破译，破译的基本思 想是找出任意模数 k和乘数 t, 使得用 k和 t去 乘公开的背包向量 B时，能够产生超递增的 背包向量即可 . 背包密码体制 本节要点小结 公钥密码体制的提出及分类 公钥密码体制的基本概念 单向陷门函数的概念 设计公钥加密算法 -背包密码体制 作业 1 设背包密码系统的超递增序列为 (3, 4, 9, 17, 35)乘数 t=19，模数 k=73， 1) 求系统的公钥； 2) 写出对明文“ good night”加解密的详细 步骤 . 35 THE END！