已阅读5页,还剩40页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
2020 2 16 1 第4章公钥密码 4 1密码学中的一些常用的数学知识 自学 4 2公钥密码体制的基本概念4 3RSA算法4 4背包密码体制4 5Rabin密码体制4 6NTRU公钥密码系统4 7椭圆曲线密码体制4 8基于身份的密码体制 2020 2 16 2 4 2公钥密码体制的基本概念 4 2 1公钥密码体制的原理公钥体制 Publickeysystem Diffie和Hellman 1976 每个用户都有一对选定的密钥 公钥k1 私钥k2 公开的密钥k1可以像电话号码一样进行注册公布 主要特点 加密和解密能力分开多个用户加密的消息只能由一个用户解读 用于公共网络中实现保密通信 只能由一个用户加密消息而使多个用户可以解读 可用于认证系统中对消息进行数字签字 无需事先分配密钥 2020 2 16 3 公钥体制加密 公钥体制加 解密m D c DSKB EPKB m 安全保障从公开钥PKB和密文c要推出明文m或解密钥SKB在计算上是不可行的 由于任一用户都可用用户B的公开钥PKB向他发送机密消息 因而密文c不具有认证性 图4 1公钥体制加密的框图 2020 2 16 4 公钥密码认证体制 用户A以自己的秘密钥SkA对消息m进行A的专用变换DSKA A计算密文 c DSKA m 送给用户B B验证c m EPKA c EPKA DSKA m 安全性 由于SkA是保密的 其他人都不可能伪造密文c 可用A的公开钥解密时得到有意义的消息m 因此可以验证消息m来自A而不是其他人 而实现了对A所发消息的认证 2020 2 16 5 图4 2公钥密码体制认证框图 公钥密码认证体制 2020 2 16 6 为了同时提供认证功能和保密性 可使用双重加 解密 图4 3公钥密码体制的认证 保密框图 公钥保密和认证体制 2020 2 16 7 公钥密码应满足的要求 接收方B产生密钥对在计算上是容易的发送方A用收方的公开钥对消息m加密以产生密文c在计算上是容易的 收方B用自己的秘密钥对密文c解密在计算上是容易的 敌手由密文c和B的公开密钥恢复明文在计算上是不可行的 敌手由密文c和B的公开密钥恢复秘密密钥在计算上是不可行的加解密次序可换 即EPKB DSKB m DSKB EPKB m 不是对任何算法都做此要求 2020 2 16 8 单向函数 一个可逆函数f A B 若它满足 1o对所有x A 易于计算f x 2o对 几乎所有x A 由f x 求x 极为困难 以至于实际上不可能做到 则称f为一单向 One way 函数 定义中的 易于计算 是指函数值能在其输入长度的多项式时间内求出 即若输入长度为n 计算函数的时间是na的倍数 a为一固定的常数 若计算函数时间是an的倍数 则为不可能做到的 2020 2 16 9 限门单向函数 单向函数是求逆困难的函数 而单向陷门函数 Trapdoorone wayfunction 是在不知陷门信息下求逆困难的函数 当知道陷门信息后 求逆是易于实现的 限门单向函数是一族可逆函数fk 满足Y fk X 易于计算 当k和X已知 X f 1k Y 易于计算 当k和Y已知 X f 1k Y 计算上不可行 Y已知但k未知 研究公钥密码算法就是找出合适的单向限门函数 2020 2 16 10 4 2 3对公钥密码体制的攻击 穷搜索攻击寻找从公开钥计算秘密钥的方法可能字攻击 2020 2 16 11 RSA算法概况 MIT三位年青数学家R L Rivest A Shamir和L Adleman Rivest等1978 1979 发现了一种用数论构造双钥的方法 称作MIT体制 后来被广泛称之为RSA体制 它既可用于加密 又可用于数字签字 RSA算法的安全性基于数论中大整数分解的困难性 2020 2 16 12 1 密钥的产生 选两个保密的大素数p和q 计算n p q n p 1 q 1 其中 n 是n的欧拉函数值 选一整数e 满足1 e n 且gcd n e 1 计算d 满足d e 1mod n 即d是e在模 n 下的乘法逆元 因e与 n 互素 由模运算可知 它的乘法逆元一定存在 以 e n 为公开钥 d n 为秘密钥 4 3 1算法描述 2020 2 16 13 算法描述 加密和解密 2 加密加密时首先将明文比特串分组 使得每个分组对应的十进制数小于n 即分组长度小于log2n 然后对每个明文分组m 作加密运算 c memodn3 解密对密文分组的解密运算为 m cdmodn 2020 2 16 14 解密正确性证明 cdmodn medmodn m1modj n modn mkj n 1modnm与n互素 由欧拉定理mj n 1modn mkj n 1modn mkj n 1 mmodngcd m n 1 m是p的倍数或q的倍数 设m cp 此时gcd m q 1 由欧拉定理 mj q 1modq mkj q 1modq mkj q j p 1modqmkj n 1modq 存在一整数r 使mkj n 1 rq两边同乘m cp mkj n 1 m rcpq m rcn 即mkj n 1 mmodn 2020 2 16 15 例4 8选p 7 q 17 求n p q 119 n p 1 q 1 96 取e 5 满足1 e n 且gcd n e 1 确定满足d e 1mod96且小于96的d 因为77 5 385 4 96 1 所以d为77 因此公开钥为 5 119 秘密钥为 77 119 设明文m 19 则由加密过程得密文为c 195mod119 2476099mod119 66解密为6677mod119 19 RSA算法例题 2020 2 16 16 4 3 2RSA算法中的计算问题 1 RSA的加密与解密过程加密与解密过程 都为求一个整数的整数次幂 再取模 再者考虑如何提高加 解密运算中指数运算的有效性 2 RSA密钥的产生产生密钥时 需要考虑两个大素数p q的选取 以及e的选取和d的计算 2020 2 16 17 RSA的安全性 RSA的安全性是基于分解大整数的困难性假定 尚未证明分解大整数是NP问题 如果分解n p q 则立即获得 n p 1 q 1 从而能够确定e的模 n 乘法逆dRSA 129历时8个月被于1996年4月被成功分解 RSA 130于1996年4月被成功分解密钥长度应该介于1024bit到2048bit之间由n直接求 n 等价于分解n p q 要大p 1 q 1都应有大的素因子 e n且d n1 4 则d能被容易的确定 2020 2 16 18 对RSA的攻击 共模攻击 每一用户有相同的模数n设用户的公开密钥分别为e1 e2 且e1 e2互素 明文消息为m 密文为因为 e1 e2 1 用欧几里德算法可求re1 se2 1假定r为负数 从而可知由Euclidean算法可计算 c1 1 r c2s mmodn 2020 2 16 19 对RSA的攻击 低指数攻击 令网中三用户的加密钥e均选3 而有不同的模n1 n2 n3 若有一用户将消息x传给三个用户的密文分别为y1 x3modn1x n1y2 x3modn2x n2y3 x3modn3x n3一般选n1 n2 n3互素 否则 可求出公因子 而降低安全性 利用中国余定理 可从y1 y2 y3求出y x3mod n1n2n3 由x n1 x n2 x n3 可得x3 n1 n2 n3 故有 2020 2 16 20 设A a1 a2 an 是由n个不同的正整数构成的n元组 s是另一已知的正整数 背包问题就是从A中求出所有的ai 使其和等于s 其中A称为背包向量 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 4 4背包密码体制 2020 2 16 21 定义背包向量A a1 a2 an 称为超递增的 如果 4 4背包密码体制 2020 2 16 22 超递增背包向量对应的背包问题很容易通过以下算法求解 已知s为背包容积 对A从右向左检查每一元素 以确定是否在解中 若s an 则an在解中 令xn 1 若s an 则an不在解中 令xn 0 下面令对an 1重复上述过程 一直下去 直到检查出a1是否在解中 检查结束后得x x1x2 xn Bx x1x2 xn T 4 4背包密码体制 2020 2 16 23 解密为此可用模乘对A进行伪装 模乘的模数k和乘数t皆取为常量 满足k ai gcd t k 1 即t在模k下有乘法逆元 设bi t aimodk i 1 2 n得一新的背包向量B b1 b2 bn 记为B t Amodk 用户以B作为自己的公开钥 4 4背包密码体制 2020 2 16 24 例4 10A 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 在得到B后 对明文分组x x1x2 xn 的加密运算为c f x B Bx t A Bxmodk对单向函数f x t t 1和k可作为其秘密的陷门信息 即解密密钥 解密时首先由s t 1cmodk 求出s作为超递增背包向量A的容积 再解背包问题即得x x1x2 xn 这是因为t 1cmodk t 1tABxmodk ABxmodk 而由k ai 知ABx k 所以t 1cmodk ABx 是惟一的 4 4背包密码体制 2020 2 16 25 背包密码体制是Diffie和Hellman1976年提出公钥密码体制的设想后的第一个公钥密码体制 由Merkle和Hellman1978年提出 然而又过了两年该体制即被破译 破译的基本思想是不必找出正确的模数k和乘数t 即陷门信息 只须找出任意模数k 和乘数t 使得用k 和t 去乘公开的背包向量B时 能够产生超递增的背包向量即可 4 4背包密码体制 2020 2 16 26 Rabin密码体制是对RSA的一种修正 它有以下两个特点 它不是以一一对应的单向陷门函数为基础 对同一密文 可能有两个以上对应的明文 破译该体制等价于对大整数的分解 RSA中选取的公开钥e满足1 e n 且gcd e n 1 Rabin密码体制则取e 2 4 5Rabin密码体制 2020 2 16 27 4 5Rabin密码体制 1 密钥的产生随机选择两个大素数p q 满足p q 3mod4 即这两个素数形式为4k 3 计算n p q 以n作为公开钥 p q作为秘密钥 2 加密c m2modn其中m是明文分组 c是对应的密文分组 3 解密解密就是求c模n的平方根 即解x2 cmodn 由中国剩余定理知解该方程等价于解方程组 2020 2 16 28 4 6NTEU公钥密码系统 NTEU是一种基于环的公钥密码系统特点 密钥短且容易产生 算法的运行速度快 所需的存储空间小 1 算法的参数2 密钥的产生3 加密4 解密 2020 2 16 29 4 7椭圆曲线 ECC 密码体制 获得同样的安全性 密钥长度较RSA短得多被IEEE公钥密码标准P1363采用 2020 2 16 30 椭圆曲线 椭圆曲线的曲线方程是以下形式的三次方程y2 axy by x3 cx2 dx ea b c d e是满足某些简单条件的实数 定义中包含一个称为无穷远点的元素 记为O 2020 2 16 31 椭圆曲线加法的定义 如果其上的3个点位于同一直线上 那么它们的和为O O为加法单位元 即对ECC上任一点P 有P O P设P1 x y 是ECC上一点 加法逆元定义为P2 P1 x y P1 P2连线延长到无穷远 得到ECC上另一点O 即P1 P2 O三点共线 所以P1 P2 O O P1 P2 O P2 P1O O O O O 2020 2 16 32 椭圆曲线加法的定义 Q R是ECC上x坐标不同的两点 Q R定义为 画一条通过Q R的直线与ECC交于P1 交点是唯一的 除非做的Q R点的切线 此时分别取P1 Q或P1 R 由Q R P1 O 得Q R P1点Q的倍数定义如下 在Q点做ECC的一条切线 设切线与ECC交于S 定义2Q Q Q S 类似可定义3Q Q Q Q 上述加法满足加法的一般性质 如交换律 结合律等 2020 2 16 33 有限域上的椭圆曲线 曲线方程中的所有系数都是某一有限域GF p 中的元素 p为一大素数 最为常用的曲线方程为y2 x3 ax bmod p a b GF p 4a3 27b2 0modp 例 p 23 a b 1 4a3 27b2 8 0 mod23 方程为y2 x3 x 1mod p 图形为连续图形 我们感兴趣的是在第一象限的整数点 设Ep a b 表示ECC上点集 x y 0 x p 0 y p 且x y均为整数 并上O 2020 2 16 34 有限域上的椭圆曲线点集产生方法 对每一x 0 x p且x为整数 计算x3 ax bmodp决定求出的值在模p下是否有平方根 如果没有则椭圆曲线上没有与这一x对应的点 如果有 则求出两个平方根 2020 2 16 35 Ep a b 上加法 如果P Q Ep a b P O P如果P x y 则 x y x y OP x1 y1 Q x2 y2 P Q P Q x3 y3 x3 2 x1 x2 modp y3 x1 x3 y1 modp 2020 2 16 36 例 E23 1 1 P 3 10 Q 9 7 2020 2 16 37 4 7 4明文消息到椭圆曲线上的嵌入 取k在30 50之间的值不妨取k 30 x mk j j 0 1 2 30m 30m 1 30m 2 直到x3 ax b modp 是平方根 即得到椭圆曲线上的点 x sqrt x3 ax b 2020 2 16 38 ECC上的密码 ECC上的离散对数问题在ECC构成的交换群Ep a b 上考虑方程Q kP P Q Ep a b k p 由k和P求Q容易 由P Q求k则是困难的 由ECC上离散对数问题可以构造Diffie Hellman密钥交换和Elgamal密码体制 2020 2 16 39 Diffie Hellman密钥交换 取一素数p 2180 两个参数a b 得到Ep a b 取Ep a b 的一个生成元G x1 y1 要求G的阶是一个非常大的素数 阶是满足nG O的最小正整数n Ep a b 和G公开 A和B密钥交换过程如下 A选小于n的整数nA作为秘密钥 并有PA nAG作为公钥B类似选取自己的秘密钥nB和公开钥PBA和B分别由K nAPB和K nBPA产生共享的秘密钥攻击者如想获得K 必须由PA和G求出nA或PB和G求出nB 2020 2 16 40 Elgamal密码体制 密钥产生
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 小学六年级劳动《活字印刷:刻字与印字》教学设计
- 高中政治逻辑与思维选择性必修三第五单元第三课正确运用复合判断教学设计
- 高中信息技术必修一《抽象数据类型》教学设计
- 高三化学教学设计:化学反应速率与化学平衡核心考点突破与模型构建
- 小学四年级语文梅兰芳蓄须创新教案设计与深度教学实践
- 初中地理八年级《中国的工业》同步冲刺复习教学设计
- 高中地理必修一 教学设计:大气组成与垂直分层核心素养导学
- 小学二年级美术教学设计《今天我当家》
- 高中二年级德育教学设计:全民消防视域下校园火灾风险隐患排查与应急处突核心素养培育
- 中考科学备考教学设计初中九年级科学复习策略与心理调适专题
- 医院供应室去污区操作规范
- 进线柜保护培训课件
- 低压线损管理办法
- GB/T 45743-2025生物样本细胞运输通用要求
- JG/T 158-2013胶粉聚苯颗粒外墙外保温系统材料
- 鞍区肿瘤护理
- T-NXJX-028控制阀检维修规范
- 海口市地下综合管廊试点工程终稿
- 中医护理小组工作总结
- 病理科运用PDCA提高免疫组化切片优良率
- 【MOOC】航天、人文与艺术-南京航空航天大学 中国大学慕课MOOC答案
评论
0/150
提交评论