密码学非对称密码体制ppt课件.ppt

第六章非对称密码体制 信息安全技术 1 6 1概述6 1 1对称密码体制的缺陷密钥的安全传递比较困难n个用户多点通信所需密钥数为n n 1 2个难以提供对主动攻击的抗击6 1 2公钥 非对称 密码体制的基本思想WhitfieldDiffie和MartinHellman在1976年首先提出 用公开的密钥 公钥 加密 用与之对应的不公开的密钥 私钥 解密 公钥密码体制提出的标志性文献 密码学的新方向 W DiffieandM E Hellman NewDirectionsinCryptography IEEETransactiononInformationTheory V IT 22 No 6 Nov1976 PP 644 654 2 例 程嘉要传送密信给雷蕾 用雷蕾的公钥对明文进行加密 然后通过公共信道将密文传送给雷蕾 雷蕾用的与自己的公钥对应的私钥 只有雷蕾自己知道 解密得到明文 康威企图知道密信内容 截获到密文 虽然他也知道加密所用的公钥 但他无法通过公钥倒推出相应的私钥 当然就不可能解密出明文 3 6 1 2对公钥密码体制的要求 1 参与方B容易通过计算产生一对密钥 公开密钥KUb和私有密钥KRb 2 在知道公钥和待加密报文M的情况下 对于发送方A 很容易通过计算产生对应的密文 C EKUb M 3 接收方B使用私钥容易通过计算解密所收到的密文C以便恢复原来的明文 M DKRb C DKRb EKUb M 4 攻击者即使知道公钥KUb 要确定其对应的私钥KRb在计算上是不可行的 5 攻击者即使知道公钥KUb和密文C 要想恢复原来的明文M在计算上也是不可行的 6 加密和解密函数可以以两个次序中的任何一个来使用 M DKRb EKUb M 机密性 或M EKUb DKRb M 数字签名 4 6 1 3单向陷门函数公钥密码体制必须设计一个满足下列条件的函数f 正向易算性 由消息x和密钥pk容易计算y fpk x 反向不可算性 在不知道密钥sk的情况下 由任意的y倒过来计算x f 1sk y 都是不可行的陷门依赖性 如果给定另一密钥sk 则f 1 y 是可以计算的 sk与pk配对 相当于陷门 满足1 2的函数称为单向函数满足1 2 3的函数被称为带陷门的单向函数 5 6 6 1 4公钥密码体制的特点无需密钥的安全传递n个用户仅需n个 公钥 私钥 对支持对主动攻击的抗击安全性基于带陷门的单向函数加密 解密速度比DES AES等分组密码体制慢可用于对称密钥的交换 7 6 2数论背景 欧拉函数与欧拉定理欧拉数设正整数n 则欧拉数 n 定义为小于n且与n互素的正整数的个数 特殊地 1 1 例如 6 2 小于6且与6互素的是1和5 7 6 1 2 3 4 5 6 11 10 1 10 素数的欧拉数对于素数p 其欧拉数 p p 1 1 p 1 欧拉数的初等性质当p q都是素数时 pq p q p 1 q 1 例 15 3 5 2 4 8 1 2 4 7 8 11 13 14 8 当e与m互素 则存在正整数d 使得ed 1 modm 称d是e关于模m的乘法逆元 简称 模乘逆元 或 模逆元 记作e 1例如 设m 13 则5 8 40 3 13 1 1 mod13 故5 1 8欧拉定理假设m n互素 则m n 1 modn 例如 设m 13 n 7 则136 4826809 689544 7 1 1 mod7 9 费马小定理 欧拉定理的推论设p与m互素 且p是素数 则mp 1 1 modp 因为 p p 1 基础定理 RSA的理论基础设n是两个不同的素数p q之积 x是小于n的非负整数 k是非负整数 则有 xk n 1 x modn 10 证明 若x不是素数p的倍数 则p与x互素 由费马小定理可得 xp 1 1 modp 于是由前述各式可得 xk n xk pq xk p q xk p 1 q 1 xp 1 k q 1 1 modp 故xk n 1 x modp 若x是p的倍数 则x 0 modp 于是也有 xk n 1 0 x modp 故存在非负整数i 使得xk n 1 ip x modp 同理存在非负整数j 使得xk n 1 jq x modq 从而可得ip jq又由于p q互素 故q i 设整商为t 即i tq 于是 xk n 1 ip x tqp x tn x x modn 即最后证得 xk n 1 x modn 11 6 3RSA算法6 3 1概述发明人RSA RonRivest AdiShamir和LeonardAdleman 1977年在麻省理工学院开发1978年发表是最典型的公钥密码体制算法基于单向陷门函数的原理以模幂运算为基本运算安全性基于大数因子分解的困难性 将一个充分大的正整数分解成两个素数之积几乎是不可能的 数学基础是著名的欧拉 Euler 数论 12 6 3 2RSA密码体制的创建选择两个充分大的不同的素数p和q计算积n pq及其欧拉数 n p 1 q 1 选择一个介于1到 n 之间且与 n 互素的正整数e即1 e n 且GCD e n 1求出d e 1 mod n 即ed 1 mod n 对明文空间0 n 1中的数x 例 P115 例6 2 以为公钥加密 y E x xe modn 以为私钥解密 x D y yd modn 13 解密还原性的证明 由于ed 1 mod n 故存在非负整数k 使得 ed k n 1 于是由基础定理可得 D E x xe d xed xk n 1 x modn 注1 p q从理论上讲也是私钥的组成部分 但因在解密过程中不用 故在确定e d之后应予以销毁注2 加密前明文M需表示为若干0 n 1的代码Mi 14 实例 对英文字母从1 26编码 空格为0 对明文双字母编码 如 itsallgreektome 编码为 0920 1900 0112 1200 0718 0505 1100 2015 0013 0500设p 47 q 59 则n 2773 2773 46 58 2668因17 157 2669 1 mod2668 故取公钥为 私钥为对明文组M 0920加密 C 92017 242322122805021463846350650290995200000000000000000 0948 mod2773 190017 54803868577848021859390000000000000000000000000000000000 2342 mod2773 其余各组的密文为 1084 1444 2663 2390 0778 0774 0219 1655 15 对密文组C 948解密 M 948157 228511974050288606356776902344003250786765339280429567483703996687679918754310808116762581946500309044935063895813994903862607889435410969372665687695332125577189642781886048649411339280291847319790295052238061530036066382680768550813673301548951552880234295829603371076580111293376807996489026124001520858798504685685090226812534126526485193603752385784652819655258004954411544721976443792145433128756776848416542537051430937496263760556207832371853899712995186966528 920 mod2773 详见 RSA加密解密实例 doc 16 6 3 4计算方法及其程序实现如何计算模逆元要在已知e m的情况下 求d 使得e d 1 modm 也即找整数k 使得e d mk 1这相当于求解d k都是未知数的二元一次不定方程e d mk 1的最小整数解 17 扩展Euclid算法输入 正整数a b输出 GCD a b 及满足ax by GCD a b 的整数x y例如 设a 21 b 15 则GCD a b 3 x 2 y 3算法步骤描述 置x1 1 x2 0 y1 0 y2 1计算q a b r a b若r 0 则GCD a b b x x2 y y2 算法结束 否则做下步依次令a b b r t x2 x2 x1 qx2 x1 t t y2 y2 y1 qy2 y1 t 然后转2 附 扩展Euclid算法 CPP 18 乘法逆元的计算输入 正整数e m输出 GCD e m 及满足ed GCD e m modm 的整数d当GCD e m 1 即e m互素 则d e 1 modm 例如 设e 7 m 17 则GCD 7 17 1 d 5 7 1 因为7 5 35 17 2 1 1 mod17 算法 在扩展Euclid算法中令a e b m 则ex my GCD e m modm 即ex GCD e m modm 若结果GCD e m 1 则d e 1 x 否则e没有逆元 附 求乘法逆元 CPP 19 解密指数 最小正逆元的计算 附 求最小正逆元 CPP 设d是e的逆元 即ed 1 modm 由于e d km ed ekm ed 1 modm 故d km也是e的逆元 可见乘法逆元不惟一 在上述乘法逆元算法中得到的逆元最接近零 但有可能为负 例如 设e 3 m 40 则GCD 3 40 1 但d 13 显然不能用作RSA算法的解密指数 因此必须将这种负逆元调整为正逆元 才能得到解密指数 改进后的算法如下 输入 正整数e m输出 GCD e m 及满足ed GCD a m modm 的最小正整数d 当CD e m 1 则d e 1 modm 就是所求解密指数 20 模幂的快速算法输入 整数n 正整数m e输出 C ne modm 算法 将e表示为二进制形式 bkbk 1 b1b0 C 1对于从k到0的i做C C C modm 如果bi 1则再做C C n modm 返回C 附 快速求模幂 CPP 21 素性检测算法之一 Miller Rabin算法 对于充分大的正奇数n 设n 1 2km 其中k是非负整数 m是正奇数 若bm 1 modn 或b2jm 1 其中0 j i 1 则称n通过以b为基的Miller Rabin素性检测也即n以 1 1 4b 的概率是素数 22 输入 大奇数n 检测次数t输出 确定n是合数或者以 1 1 4t 的概率是素数 如 t 5 则判定n是素数的正确性约为 1 1 45 0 9990234375算法 将n 1表示为二进制形式 bkbk 1 b1b0 随机选取从1到n 1的整数ax 1对于从k到0的i依次做 x0 x x x2 modn 如果x 1 x0 1 x0 n 1则返回 是 算法结束 如果bi 1则再做x x a modn 如果x 1则返回 是 算法结束转2 直至算法结束或完成t回测试 若完成t回测试则返回 不是 即n是伪素数 附 用M R检测素数 CPP求65535以下的素数 CPP 23 形如2p 1 其中P为素数 的素数称为梅森素数 Mersenneprime 它是以17世纪法国数学家 法兰西科学院奠基人马林 梅森的姓命名的 2008年8月 美国加州大学洛杉矶分校 UCLA 的计算机专家史密斯 E Smith 通过参加了一个名为 因特网梅森素数大搜索 GIMPS 的国际合作项目 发现了第46个也是目前最大的梅森素数243112609 1 它有12 978 189 近1300万 位数 如果用普通字号将这个巨数连续写下来 它的长度可超过50公里 这一成就被美国的 时代 杂志评为 2008年度50项最佳发明 之一 排名在第29位 由于这种素数珍奇而迷人 因此被人们誉为 数学海洋中的璀璨明珠 梅森素数一直是数论研究的一项重要内容 也是当今科学探索的热点和难点 6 3 5梅森素数 24 6 3 6RSA方案的设计流程用素性检测法选两个充分大的素数p q计算n pq及 n p 1 q 1 选择一个介于1到 n 之间的正整数e用扩展Euclid算法计算GCD e n 若为1则转下步 否则转3 选出e的最小正逆元d e 1 mod n 销毁p q 选e d中的较小的一个与n组成公钥并予以公布 另一个作为私钥予以严格保密设计加密方案 以某种规则将明文消息表示为若干个小于n的非负整数 25 6 3 7RSA算法的安全性对RSA的攻击等效于对模数n的因数分解 属于NP 类计算问题 不确定性多项式时间可解 附 将输入的充分大正整数分解为两个素数之积 可能的话 的算法 整数分解为素数之积 CPPp q应尽量取符合下列要求的强素数 p 1有大的素因子r p 1有大的素因子 r 1有大的素因子知道 n 则可求得p q 故应予以保密或销毁泄漏解密指数d将有利于对n的分解 因此不能光换d而必须选择新的p q 26 不同用户不可共享n和p q在一对加密 解密指数中 尽可能让e d目前p q在1024位 1 8 10308 2048位 3 2 10616 之内是安全的安全的RSA方案速度较DES AES慢 一般用于对称加密体制中的密钥传递和交换 27 6 3 9安全RSA算法的实例n 1024位二进制 256位十六进制 328C74784DF31119C526D18098EBEBB943B0032B599CEE13CC2BCE7B5FCD15F90B66EC3A85F5005DBDCDED9BDFCB3C4C265AF164AD55884D8278F791C7A6BFDAD55EDBC4F017F9CCF1538D4C2013433B383B47D80EC74B51276CA05B5D6346B9EE5AD2D7BE7ABFB36E37108DD60438941D2ED173CCA50E114705D7E2BC511951公钥e 10001H 6 3 8RSA算法的演示RSA TOOL 28 私钥d E760A3804ACDE1E8E3D7DC0197F9CEF6282EF552E8CEBBB7434B01CB19A9D87A3106DD28C523C29954C5D86B36E943080E4919CA8CE08718C3B0930867A98F635EB9EA9200B25906D91B80A47B77324E66AFF2C4D70D8B1C69C50A9D8B4B7A3C9EE05FFF3A16AFC023731D80634763DA1DCABE9861A4789BD782A592D2B1965设明文编码M 11111111111122222222222233333333333 29 则加密后的密文C Me modn 17b287be418c69ecd7c39227ab681ac422fcc84bb35d8a632543b304de288a8d4434b73d2576bd45692b007f3a2f7c5f5aa1d99ef3866af26a8e876712ed1d4cC4b293e26bc0a1dc67e247715caa6b3028f9461a3b1533ec0cb476441465f10d8ad47452a12db0601c5e8beda686dd96d2acd59ea89b91f1834580c3f6d90898解密后还原成明文M Cd modn 11111111111122222222222233333333333 30 相对于对称密码体制 公钥密码体制有何优点 请用生活中的例子简述用于机密性的公钥密码体制的加密解密过程最典型的公钥密码体制是哪一个 RSA密码体制的数学基础是什么 RSA密码体制的安全性依赖于什么 请简述一个具体的RSA方案的设计过程RSA密码体制的主要缺点是什么 p q至少取十进制几位才能使RSA方案具有安全意义 什么是单向函数 能否用私钥加密而用公钥解密 有何用途 附 关于公钥密码体制与RSA的讨论 31 6 4ElGamal TaherElGamal提出 密码体制6 4 1数论背景离散对数 在模意义下的对数 设正整数 a和p 若 a modp 则称a是 的以 为底在模p意义下的离散对数 记作a log modp 例如 因54 625 9 mod11 故log59 mod11 4 32 本原元和循环群 定义 设p是素数 Zp 0 1 2 3 p 1 Zp 1 2 3 p 1 若对任一 Zp 总存在正整数a 使得 a modp 也即 Zp中任意非0元素总存在离散对数log modp 则 称为Zp 或p 的本原元 或生成元 基元 原根 也即Zp对模p乘构成循环群 33 可以证明 对于素数p Zp 共有 p 1 个本原元对于素数p 设Zp 有一个本原元g 则Zp 的所有本原元由以下集合给出 gt 1 t p 1 GCD t p 1 1 对于素数p 判断g是否Zp 的本原元 不需要逐一计算g1 g2 gp 1 而仅需要计算所有gt modp 其中t p 1 只要不产生重复结果 g就是素数p的本原元 34 例如 Z19 0 1 2 3 18 18 6 1 5 7 11 13 17 故Z19 1 2 3 18 共有6个本原元 2 3 10 13 14 15 验证15是Z19 的本原元 满足t 18的t有 1 2 3 6 9151 15 152 16 153 12 156 11 159 18 附 求本原元 CPP 35 6 4 2密码体系设计步骤 选择合适的大素数p 建立循环群Zp 0 1 2 3 p 1 使得在Zp中求离散对数是困难的选择Zp 的本原元 针对某用户任选a Zp 计算 a modp 以形成公钥 p 和私钥a加密 对于明文x Zp 随机选取正整数r Zp 计算y1 r modp 和y2 x r modp 得到密文对 y1 y2 解密 x y2 y1a 1 modp 36 6 4 3解密还原性的证明 注意 y1a 1 modp y1a modp 1 modp 因为 y1 r modp y2 x r modp a modp 所以 y2 y1a 1 modp x r r a 1 modp x a r r a 1 modp x ar ra 1 modp x modp 37 6 4 4安全性及算