《网络安全》第5-6讲(2.4)

第2章密码技术 2 4公钥 非对称 密码体制 在对称密钥密码体制中 加密运算与解密运算使用同样的密钥 在公共的计算机网络上安全地传送和保管密钥是一个严峻的问题 公开密钥加密 Public keycryptography 也称为 非对称 密钥 加密 该思想最早由雷夫 莫寇 RalphC Merkle 在1974年提出 之后在1976年 狄菲 Diffie 与赫尔曼 Hellman 两位学者发表了著名论文 密码学的新方向 提出了建立 公开密钥密码体制 为发讯与收讯的两方建立密钥 这两个密钥是数学相关 用某用户加密密钥加密后所得的信息 只能用该用户的解密密钥才能解密 如果知道了其中一个 并不能计算出另外一个 因此如果公开了一对密钥中的一个 并不会危害到另外一个的秘密性质 称公开的密钥为公钥 2 4公钥 非对称 密码体制 2 4 1公钥密码体制的基本概念公钥体制下 一个用户可以将自己设计的加密公钥和加密算法对外公布 而只保留解密用的私钥 任何人都可以获取这个用户的加密公钥和加密算法 并向该用户发送加密过的信息 该用户接收后可以使用私钥还原消息 在这个公钥加解密的过程中 会涉及到公私密钥对 数字证书以及电子签证机关等主要内容 2 4公钥 非对称 密码体制 2 4 1公钥密码体制的基本概念1 密钥对在基于公钥体系的安全加密系统中 密钥生成过程每次都产生一个公钥和一个私钥 形成加密和解密的密钥对 在实际应用中 私钥由用户私人保存 而公钥则通过某种手段对外公布 公钥体系的基础问题是公钥的分发与管理 这是电子商务等业务系统能够广泛应用的基础 一个集体如果成员之间可以互信 比如A和B两人形成小集体 他们之间完全互信并直接交换公钥 在互联网上进行保密通信 不存在密钥和身份安全问题 这个集体再稍微扩大一点 成员之间有基本的信任关系 虽然从法律角度讲这种信任有一定风险 但通常也可以完成安全通信 如果在开放环境下 如互联网环境下 通信双方缺乏基本的信任关系 并且存在大量的恶意用户 密钥和身份的信任问题就成了一个大问题 2 4公钥 非对称 密码体制 2 4 1公钥密码体制的基本概念2 数字证书公开密钥体系需要在开放环境下使用 公钥加密体系采取将公钥和公钥的主人名字联系在一起的方法 再请一个有信誉的公正权威机构对每个公钥和所有者身份进行确认 确认后的公钥信息加上这个权威机构的签名 就形成了数字证书 也称为证书 由于证书上有权威机构的签字 因此人们公认证书上的内容是可信任的 又由于证书上有主人的名字等身份信息 别人就能很容易地知道公钥的主人是谁 有了数字证书之后 互联网上的庞大用户群之间可以通过权威机构建立起基本的信任关系 使得彼此都不能轻易信任的用户之间可以完成通信 证书就是用户在网上的电子个人身份证 在电子商务中的作用同日常生活中使用的个人身份证作用一样 2 4公钥 非对称 密码体制 2 4 1公钥密码体制的基本概念3 电子签证机关电子签证机关 即CA 是负责颁发数字证书的权威机构 CA自身拥有密钥对 可以使用私钥完成对其他证书的数字签名 同时也拥有一个对外开放的证书 内含公钥 网上的公众用户通过验证CA的数字签名建立信任 任何人都可以得到CA的证书 含公钥 用以验证它所签发的其他证书 如果用户想建立自己的证书 首先要向CA提出申请证书的请求 在CA判明申请者的身份后 便为他分配一个密钥对 并且CA将申请者的公钥与身份信息绑在一起 在为之完成数字签名后 便形成证书发给那个用户 申请者 如果一个用户想鉴别数字证书是否为假冒的 可以用证书发证机构CA的公钥对该证书上的数字签名进行验证 数字签名验证的过程是使用CA公钥解密的过程 验证通过的证书就被认为是有效的 CA在公开密码体系中非常重要 负责签发证书以及证书和密钥的管理等必要工作 CA相当于网上公安机构 专门发放 验证电子身份证 2 4公钥 非对称 密码体制 2 4 1公钥密码体制的基本概念4 公钥加密体制具有以下优点 1 密钥分配相对简单 不需要复杂的流程 2 密钥的保存量少 且私钥和公钥分别存储 3 可以实现互不相识的人之间进行私人通信时的保密性要求 4 可以完成通信双方的数字签名和数字身份鉴别 当然 由于公钥加密体制依赖的算法基础是难解问题 并不是真正的无解问题 若计算机达到足够的计算能力 花费足够的时间的话 还是有可能被破解的 只要花费的代价足够大就可以保证信息在一定时间内的安全性 2 4公钥 非对称 密码体制 2 4 2公钥密码体制的原理公钥密码体系中由于公钥与私钥之间存在依存关系 因此 信息使用公钥加密后 只有私钥拥有者本人才能解密该信息 任何未授权用户甚至信息的发送者都无法将此信息解密 近代公钥密码系统的研究主要基于难解的可计算问题 该方法保证了整个体系和算法的安全性 常用的难解可计算问题包括 1 大数分解问题 2 计算有限域的离散对数问题 3 平方剩余问题 4 椭圆曲线的对数问题等 2 4公钥 非对称 密码体制 2 4 2公钥密码体制的原理公钥密码体制的基本数学方法和基本原理如下所述 1 可逆函数和单向函数1 可逆函数令f是集A到集B的一个映射 如果对任意的x1 x2 x1 x2 A 有y1 y2 y1 y2 B 则称f是从A到B的单射 或1 1映射 或可逆的函数 记为y f x 2 单向函数一个可逆函数y f x 如果满足以下两条就称为一个单向函数 对于给定的所有x A 能方便地计算出f x 对于给定的所有y 求x是困难的 以至于实际是做不到的 2 4公钥 非对称 密码体制 2 4 2公钥密码体制的原理公钥密码体制的基本数学方法和基本原理如下所述 1 可逆函数和单向函数例2 1有限域GF p 中的指数函数 其中p是素数 即也就是x为满足0 x p 1的整数 其逆运算是求离散对数 即给定x求y是容易的 但是当p很大时 从x logby中要计算x是非常困难的 如b 2 p 2100 给定x求y 只需作100次乘法 利用高速计算机可在0 1ms内完成 而给定y求x 所需计算量为1600年 可见 有限域GF p 中的指数函数f x bx是一个单向函数 x logby 2 4公钥 非对称 密码体制 2 4 2公钥密码体制的原理公钥密码体制的基本数学方法和基本原理如下所述 2 用于构造公钥密码的常用单向函数1 多项式求根有限域GF p 上的一个多项式当给定多项式的系数和x p以后 利用Honer算法 最多进行n次乘法 n 1次加法 就可以求得y的值 但已知多项式的系数a和y p以后 要求x 就需要对高次方程求根 至少要进行不小于n2 lbp 2的整数次乘法 当n p很大时很难求解 2 4公钥 非对称 密码体制 2 4 2公钥密码体制的原理公钥密码体制的基本数学方法和基本原理如下所述 2 用于构造公钥密码的常用单向函数 离散对数如果p是一个足够大的素数 a是 0 1 2 p 1 中与p互素的数 则已知p a x的值 计算f x axmodp并不困难 若已知p a y的值 则计算x logbymodp 是一个离散对数问题 就很困难了 若p 512 则计算乘法次数为1077 2 4公钥 非对称 密码体制 2 4 2公钥密码体制的原理公钥密码体制的基本数学方法和基本原理如下所述 2 用于构造公钥密码的常用单向函数3 大整数分解若已知两个大素数p q 求n p q仅需一次乘法 但已知n求p q则是几千年来数论专家的一道难题 已知的各种算法有 试除法 二次筛 数域筛 椭圆曲线 其中RSA问题是FAC问题的特例 n是两个素数p q之积 给定n以后求p q的问题称为RSA问题 求n p q分解问题有以下几种形式 1 分解整数n为p q 2 给定整数M C 求d使得Cd Mmodn 3 给定整数k C 求M使得Mk Cmodn 4 给定整数x C 决定是否存在y使得x y2modn 二次剩余问题 2 4公钥 非对称 密码体制 2 4 2公钥密码体制的原理公钥密码体制的基本数学方法和基本原理如下所述 2 用于构造公钥密码的常用单向函数 迪菲 赫尔曼 Diffie Hellman 问题给定素数p 可构造一乘群Z p 令 为Z p的生成元 若已知 a b 求 ab的问题即为菲 赫尔曼问题 二次剩余问题给定一个奇合数n和整数a 决定a是否为modn平方剩余问题就称为二次剩余问题 2 4公钥 非对称 密码体制 2 4 2公钥密码体制的原理公钥密码体制的基本数学方法和基本原理如下所述 3 公钥密码体制的原理若用户A有一个加密密钥ka 同时还有一个解密密钥k a 可将加密密钥ka公开 而解密密钥k a保密 若用户B要向A传送信息的明文为m 可查A的公开密钥ka 若用A的公开密钥ka加密得到密文c Eka m 则A收到密文c以后 用只有自己才知道的解密密钥k a对c进行解密得m Dk a c 图2 14公钥密码体系模型 2 4公钥 非对称 密码体制 2 4 3RSA算法1978年 美国麻省理工学院 MIT 的研究小组成员 李维斯特 Rivest 沙米尔 Shamir 艾德曼 Adleman 提出了一种基于公钥密码体制的优秀加密算法 RSA算法 RSA的取名就是来自于这三位发明者的姓的第一个字母 后来 他们在1982年创办了以RSA命名的公司RSADataSecurityInc 和RSA实验室 该公司和实验室在公开密钥密码系统的研究和商业应用推广方面具有举足轻重的地位 RSA密码系统的安全是基于大整数分解因子的难度 其公开密钥 现在一般是1024位甚至更长 和私人密钥是一对大素数的函数 一般来说 求一对大素数的乘积相对比较容易 但要对这个乘积进行因式分解则非常困难 因此 可以把一对大素数的乘积作为公开密钥公布 而把素数作为私钥 从而从一个公开密钥和密文中恢复出明文的难度等价于分解两个大素数之积 2 4公钥 非对称 密码体制 2 4 3RSA算法1 RSA密钥的产生RSA密钥的产生过程如下 1 选择两个大素数p q 选择的素数要保密 2 计算乘积n pq和 n p 1 q 1 3 随机选择加密密钥e 要求e和 n 互质 4 利用Euclid算法计算解密密钥d 应满足d e 1mod n 其中n和d也要互素 数 n e 是公钥 n d 是私钥 两个素数p q不再需要 应该丢弃 不要让任何人知道 2 4公钥 非对称 密码体制 2 4 3RSA算法1 RSA密钥的产生例2 2已知解方程d e 1mod2436 即937 13 1 mod 2436 取e 13 d 937 2436 13 187 513 5 2 35 3 23 2 11 3 2 2 5 3 3 13 5 2 5 2436 13 187 2 4公钥 非对称 密码体制 2 4 3RSA算法2 RSA加密 1 加密信息为m 二进制表示 时 首先把m分成等长数据块m1 m2 mi 块长s 其中2s n s要尽可能的大 2 对应的密文是 3 RSA解密对加密消息进行解密计算时 计算 ci miemodn 2 4公钥 非对称 密码体制 2 4 3RSA算法2 RSA加密例2 2续 若取明文 publickeyencryptions 先将明文按两个一组进行分块 再将明文数字化 如按英文字母表的顺序得pu 1520 bl 0111 ic 0802 ke 1004 ye 2404 nc 1302 ry 1724 pt 1519 io 0814 ns 1318 再利用加密密钥 2537 13 进行加密得密文 pu 0095 bl 1648 ic 1410 ke 1299 ye 1365 nc 1379 ry 2333 pt 2132 io 1751 ns 1324 使用解密密钥 2537 937 可将密文恢复成明文 2 4公钥 非对称 密码体制 2 4 4RSA算法中的计算问题RSA算法中首先遇到的问题就是如何选取大的素数 数百年来 人们对素数的研究一直有很大兴趣 是否有一个简单的公式可以产生素数 从目前的研究结果来看 答案是否定的 曾有人猜想若n 2n 2 2n 2能被2整除 则n为素数 n 3 3 23 2 n 341时这一猜想是正确的 但n 341时 此猜想是错误的 2 4公钥 非对称 密码体制 2 4 4RSA算法中的计算问题1 概率测试素数法概率测试素数法有Solovay Strassen测试法 Lehman测试法 Miller Rabin测试法等 它们都是利用数论理论构造一种算法 对于一个给定的大正整数 进行一次测试 是素数的概率为1 2 若进行了r次测试 则第n步是素数的概率为 2 r n为素数的概率为1 若r足够大 如r 100 则几乎可以认为n是素数 若概率测试法得到的准素数是合数 出现的概率很小 也不会造成太大的问题 因为该结果在RSA体制的加解密时会出现异常 我们可以丢弃该结果重新产生 2 4公钥 非对称 密码体制 2 4 4RSA算法中的计算问题2 确定性验证素数法确定性验证素数法是RSA体制实用化研究的基础问题之一 定理2 1令pi 1 hipi 1 若满足下述条件 则pi 1必为素数 2 4公钥 非对称 密码体制 2 4 4RSA算法中的计算问题2 确定性验证素数法1 安全素数幂剩余函数具有特殊的周期性 反复运算M Cemod n若干次后 将还原为最初的M 例如 p 17 q 11 n pq 187 e 7 m 123 可以验证 m经过4次RSA连续变换 可得m4 m 过程如下 2 4公钥 非对称 密码体制 2 4 4RSA算法中的计算问题2 确定性验证素数法1 安全素数早期的RSA算法就曾被人用这种方法破译 所以在生成密钥时 应采用 安全素数 所谓安全素数p 应满足 1 p是一个位数足够大的随机素数 2 p 1含有一个大的素数因子r 3 p 1含有一个大的素数因子 4 r 1含有一个大的素数因子t 2 4公钥 非对称 密码体制 2 4 4RSA算法中的计算问题2 确定性验证素数法2 安全素数的获得 1 选择两个指定长度的奇数a b 2 在a附近产生随机素数s 在b附近产生随机素数t 3 由t产生素数r r 1 2t 若r非素数 则r r 2直到r是素数 4 由r s生成p p sr 1 rs 1 mod rs 若p为偶数 则p p rs p p 2rs直到p为素数 2 4公钥 非对称 密码体制 2 4 4RSA算法中的计算问题2 确定性验证素数法3 高次幂的求模算法C Memod p RSA加 解密变换都要进行高次幂的求模运算 求C Me mod p可通过对指数e的二进制化来实现 例如 求117mod17 计算如下 7 111 2即7 22 21 20 117mod17 11 22 112 11 mod17 具体步骤如下 将e用二进制表示为e klkl 1 k0 ki 0 1 0 i lC 1fori l 0C C2mod p若ki 1 则C C M mod p 2 4公钥 非对称 密码体制 2 4 5RSA算法的安全性RSA算法之所以具有安全性 是基于数论中的一个事实 将两个大的素数合成一个大数很容易 而逆过程则非常困难 即若n pq被分解 则 RSA 便被攻击 若p q已知 则 n p 1 q 1 便可算出 解密密钥d和e满足d e 1mod n 故d便求出 2 4公钥 非对称 密码体制 2 4 5RSA算法的安全性攻击者通常会考虑通过已知的公钥推算私钥 但是这要将模数因式分解成组成它的质数 计算的难度很大 算法可以采用足够长的密钥 使其在现有的计算水平下基本不可能实现 RSA实验室给出了不同应用场合的密钥长度建议 普通公司使用的密钥长度应为1024 bit 对于极其重要的资料 使用双倍长度即2048 bit 对于普通用户 使用768 bit的密钥长度已足够 因为使用当前技术和计算能力无法轻易破解 2 4公钥 非对称 密码体制 2 4 5RSA算法的安全性由此可见 RSA的安全性依赖于大数分解 目前 进行大数分解速度最快的方法 其时间复杂度为 exp sqrt ln n lnln n 由时间复杂度可见 RSA的安全性是依赖于作为公钥的大数n的位数长度的 为保证足够的安全性 三位数学家建议取p q为100位的十进制数 这样大数n为200位十进制数 即使采用每秒107次运算的超高速电子计算机 至少也要计算108年 但在实际应用中 一般认为现在的个人应用可以采用512 bit的公钥 公司需要用1024bit的公钥 极其重要的场合必须使用2048bit的公钥 2 4公钥 非对称 密码体制 2 4 5RSA算法的安全性RSA算法的重大问题是无法从理论上证明其保密性能 RSA的安全性依赖于大数因子分解 而密码学界多数人士倾向于因子分解不是NPC问题 普遍认为从一个密钥和密文推断出明文的难度等同于分解两个大素数的积 但这一假设并没有从理论上得到证明 目前 RSA 的一些变种算法已被证明等价于大数分解 不管怎样 分解n是最直接的攻击方法 人们已经分解的最新纪录是129位十进制的大素数 因此 公钥的大数n必须选择得足够大 加密算法的应用不仅要考虑保密强度 还要考虑算法的运算效率 密钥越长安全性越高 其加解密所耗的时间也越长 因此 加密密钥的长度需要根据所保护信息的敏感程度 攻击者破解所要花的代价以及系统所要求的反应时间来综合考虑决定 尤其对于商业信息领域更是如此 2 4公钥 非对称 密码体制 2 4 6RSA算法的实用性及数字签名1 RSA的实际应用选用RSA算法作为公开密钥加密系统的主要算法的原因是该算法安全性好 在模N足够长时 每lnN个整数中就有一个大小接近于N的素数 在模长为1024bit时 可以认为RSA密码系统的可选密钥个数足够多 可以得到随机 安全的密钥对 目前 RSA算法已经广泛应用于安全通信 在互联网的许多领域也得到了采用 例如在安全接口层 SSL 标准中选择了RSA算法来保证网络浏览器建立安全的互联网连接 RSA加密系统也大量应用于智能IC卡和网络安全产品中 2 4公钥 非对称 密码体制 2 4 6RSA算法的实用性及数字签名1 RSA的实际应用公开密钥密