《无线网络安全技术》研讨课-第三讲.ppt

第三讲公钥密码学与RSA 无线网络安全技术songyubo 公钥密码学 公钥密码体制的基本原理RSA算法 引言1Diffie生平 Diffie 1944 1965年 获得麻绳理工学院数学学士学位1976年 和Hellman联合发表 密码学新方向 1991年 任职于Sun公司1992年 1992年瑞士联邦理工学院授予博士头衔 引言2Diffie的问题 Diffie考虑的问题 加密过程中密钥分发问题手工分发不符合实际情况 而KDC的存在意味着通信双方的隐私会被第三方监视 数字签名 问题 寻找一个正确判断消息来源的方法 即象手写签名一样 以保证消息却是出自特定的人 引言3双重加密方案 双重加密方案Alice把消息放到箱子里 用自己的锁锁上发送给BobBob收到箱子后加上自己的锁 在把箱子返回给AliceAlice除掉自己的锁 再把箱子寄给BobBob除掉自己的锁 读取消息 双重加密方案的数学描述 Alice发送EA P 给BobBob发送EB EA P 给AliceAlice发送DA EB EA P DA EA EB P EB P 给BobBob解密DB EB P P双重加密方案的分析要求构造一个函数 满足 EB EA P EA EB P 无法验证Alice或Bob的身份Diffie的解决方法 使用两个密钥而不是一个密钥 引言4单向函数 现实生活中的例子单向路 只允许沿着一个方向走 加密 但你不能沿着反方向走 解密 电话号码本 很容易根据人名找到电话号码 加密 但是根据号码找对应的人很难 解密 单向函数 函数值计算很容易逆计算是不可行的 单向陷门函数 函数值计算很容易若知道某种附加的信息 则逆计算是可行的 否则不可行 公钥密码的要求 DiffieandHellman 1976 密钥对的生成在计算上是容易的加密在计算上是容易的解密在计算上是容易的已知公钥的情况下 攻击者想要确定私钥在计算上是不可行的已知公钥和密文的情况下 攻击者想要恢复明文在计算上是不可行的加密和解密的顺序可以交换 M DPUb EPRb M DPRb EPUb M PrinciplesofPKC 对称密码和公钥密码 对称密码加密解密使用相同的算法和密钥成员共享算法和密钥密钥必须秘密保存加密算法的安全轻度必须足够高即使知道明文和密文以及算法细节也不影响密钥的安全性 公钥密码算法相同 但加解密使用的密钥不同成员共享算法 但只拥有密钥对中的一个有一个密钥必须保密加密算法的安全轻度必须足够高即使知道明文和密文 算法细节以及其中的一个密钥 也不影响另一个密钥的安全性 PrinciplesofPKC 用公钥密码进行加密 PrinciplesofPKC 用公钥密码进行认证 PrinciplesofPKC 公钥密码基于的数学难题 背包问题大整数分解问题 TheIntegerFactorizationProblem IFP RSA有限域的乘法群上的离散对数问题 TheDiscreteLogarithmProblem DLP ElGamal椭圆曲线上的离散对数问题 TheEllipticCurveDiscreteLogarithmProblem ECDLP 椭圆曲线上的ElGamal RSA算法 作者1977年 R S ARonRivestAdiShamirLenAdleman S R A RSA算法 基本特征 基于大数 100到200位十进制素数 分解难题分组密码算法 要求分组的二进制值小于n 分组长度即为log2 n 基于整数乘法明 密文分组以及公 私钥被看作小于n的整数加 解密是模乘运算明文 密文是0到n 1之间的整数 通常n的大小为1024位或309位十进制数 数学基础 素数费马定理和欧拉定理离散对数 素数 素数 除了1和此整数自身外 没法被其他数整除的自然数 素数是无限多的 不存在最大的素数 欧几里得 已知的最大素数 232582657 1 230402457 1 225964951 1GIMPS组织 因特网梅森素数大搜索 www mersenne org算术基本定理 素数唯一分解定理 分解的存在性 分解的唯一性 即若不考虑排列的顺序 正整数分解为素数乘积的方式是唯一的 素数的分布 2000的素数 孪生素数猜想存在无穷多个素数p 有p 2也是素数 5 7 11 13 101 103 4967 4969 梅森素数形如2n 1的数237156667 1 费马定理和欧拉定理 费马定理 若p是素数 a是正整数且不能被p整除 则 ap 1 1modp推论1 若p是素数 a是正整数且不能被p整除 则 ap amodp推论2 若p是素数 a是正整数且不能被p整除 则 a的逆元为ap 2 9099mod101 55 欧拉函数 EulerTotientFunction 对正整数n 欧拉函数 n 是少于或等于n的数中与n互质的数的数目 例 8 4 1 3 5 7和8互素 性质 1 1若p为素数 p p 1若p为素数 a为一非负整数 则有 pa pa pa 1 p 1 pa 1若有素数m和n 且m n 则有 mn m n 若n p1a1p2a2 ptat 则 n n 1 1 p1 1 1 p2 1 1 pt 欧拉定理 对任何两个互素的正整数a n 有 a n 1modn当n是质数p时 此式则为 ap 1 1modp 费马定理 推论 a n 1 amodn若gcd a n 1 则a n 1为a模n下的逆元 离散对数 考虑如下整数 amodn a2modn a3modn ammodn 定义 令a与n互素 则满足am 1modn的最小整数m称为 a模n的阶 记为ordna 模n下a的指数由a生成的周期长度若a与n互素 则必有一整数m n 满足am 1modn 定理 若a与n互素 则有 1 ordna n 2 av 1modn ordna v 3 ordn au ordna gcd u ordna 4 ai ajmodn i jmodordna a primitiveroot 模算术的对数 对任意整数b和素数p的本原根g 存在唯一指数i 有 b gimodpwhere0 i p 1 指数i称为 b以g为底模p的离散对数 dlogg p b gdlogg p b bmodpdlogg p 1 0 g0modp 1 dlogg p g 1 g1modp g 例 dlog2 19 a 定理 令p为一非负整数 其本原根为g 令a和b与p互素 则有 1 dlogg p 1 0 mod p 2 dlogg p g 1 mod p 3 dlogg p ab dlogg p a dlogg p b mod p 4 dlogg p ak k dlogg p a mod p 离散对数的计算 y gxmodp给定g x p 可以直接算出给定g y p 难以算出x 算法描述 找素数选取两个随机素数p q计算模n和Euler函数 n n pq n p 1 q 1 随机选择加密密钥e 使e和 p 1 q 1 互素 利用欧几里德扩展算法找ed 1mod n d e 1mod n 发布发布 e n 这是公钥ked保密 d n 是私钥kd RSA加密解密 加密明文分组m做为整数须小于nc memodn解密m cdmodn RSA的正确性 证明依据Euler定理 在modn的含义下cd me d medmodn mk n 1modn mmodn 据Euler定理 关于mk n 1 如果n pq 则mk n 1 mmodn如果m和n互素 直接使用欧拉定理即得如果m和n不互素 则公因子必是p 或者q 事实上 此时mk n 1 mmodp 因为m是p的倍数 mk n 1 mmodq 根据Fermat小定理 mk n 1 mmodpq 由以上两式 RSA考虑 素数必须够大 否则对手可能很快分解n判定 试除法不可行判定 采用Miller Rabin概率测试方法强素数 p 1 2和 q 1 2应是素数选取较小的e 较大的d e 3 65537 模幂乘举例 97221 2003 都在模2003意义下 97221 97128 64 16 8 4 1 9712897649716978974971依次计算971 972 974 978 9716 97128一直平方下去即可 并保持模2003如果某次方在1式出现 则累乘累积开始是1 乘法次数O log2Y 攻击RSA 枚举枚举所有可能明文m 用e加密和c比较枚举所有可能的私钥d 已知明文 数学方法分解n pq 就可以计算 n 就可从e求得d不分解n 而直接求 n 再求d不求 n 直接求d 对RSA的主要支持和批评 形式简单 易于理解 研究深入 支持广泛既能用来加密 又可签名安全性的模糊 疑为等价于因子分解的难度 随机素数产生并不容易运算量大 速度受局限 尤其在嵌入式设备中 关于公钥密码学的几点认识 公钥算法是基于数学函数而不是基于替换和置换 公钥算法是非对称的 它使用两个独立的密钥 加密和解密各使用不同的密钥 两个密钥必须保密其中一个 若知道算法 其中一个密钥去推导另一个密钥是不可行的 公钥密码学轶事 马丁 加纳德 一种新密码 要几百万年才能破解 美国科学人 1977年公开了密文和公钥N 11438162575788886766923577997614661201021829672124236256284293570693524573389783059712356395870505898907