版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第五章重点5.2背包算法背包问题:已知M1,M2,…,Mn和S,求b1,b2,…,bn,bi{0,1},使S=b1M1+b2M2+…+bnMn
(1:表示物体放入背包,0:表示物体不放入背包)背包算法的思想:明文作为背包问题的解,对应于bi,密文为重量和。例:明文:011010背包:25781317密文:5+7+13=25算法的关键:两个不同的背包问题,一个在线性时间内求解,一个不能在线性时间内求解。超递增序列:其中每个元素都大于前面所有元素的和例:1,3,6,13,27,52……超递增背包:重量列表为一个超递增序列超递增背包的解法:对于i=n,n-1,…,1
bi=0当1当秘密密钥:超递增背包问题的重量序列公开密钥:有相同解的一个一般背包问题的重量序列从秘密密钥建立公开密钥:选择一个超递增序列作为秘密密钥,如:{2,3,6,13,27,52};将其中每个值都乘以一个数n,对m求余,例如:n=31,m=105;得到的序列作为公开密钥:{62,93,81,88,102,37}。加密:将明文分成长度与背包序列相同的块,计算背包总重量。例如:背包{62,93,81,88,102,37},明文011000,密文为:93+81=174解密:先计算n-1,为n关于模m的乘法逆元。将密文的值与n-1模m相乘用秘密的背包求解,得到明文例:n=31,m=105,n-1=61,174*61mod105=9=3+6,明文为011000例1:n=31,m=105,秘密密钥为{2,3,6,13,27,52},公开密钥:{62,93,81,88,102,37},密文C=280,求明文。解:n-1=61C*
n-1mod105=280*61mod105=7070=2+3+13+52根据秘密密钥{2,3,6,13,27,52}明文:110101例2:设背包公开密钥算法的公开密钥为向量{17,34,2,21,41},某消息M被加密后生成密文C=22,已知系统中模m=50,n=17,试对C解密求出M。解:根据公开密钥{17,34,2,21,41},求秘密密钥1*17mod50=172*17mod50=346*17mod50=213*17mod50=2123*17mod50=41秘密密钥为{1,2,6,13,23}n-1=3,C*
n-1mod50=22*3mod50=16=1+2+13明文为:110105.3RSA算法第一个成熟的公开密钥算法,可以用作加密和数字签名算法描述:RSA的安全性基于大整数的因数分解的困难性首先随机选择两个大素数p和q,计算n=pq然后随机选择加密密钥e,满足e与(p-1)(q-1)互素。用扩展的Euclid算法计算解密密钥d,使得ed
1mod(p-1)(q-1)公开密钥:e和n秘密密钥:d
所有出现ed的地方都可以用1表示加密:C=Memodn解密:M=Cdmodn例:已知n=3337,e=79,M=6882326879666683求C=?解:n=pq=3337=47*71p=47q=71(p-1)(q-1)=46*70=3220d=e-1mod3220=79-1mod3220=1019将明文3位一组,m1=688,m2=232,m3=687,m4=966,m5=668,m6=003加密:c1=m1emodn=68879mod3337=1570同理:c2=2756,c3=2091,c4=2276,c5=2423,c6=158C=15702756209122762423158解密:m1=c1dmodn=15701019mod3337=688Feige-Fiat-Shamir身份验证体制:产生模n,为两个大素数的乘积。产生密钥:选择k个不同的数v1,v2,…,vk,其中各个vi为一个模n的二次剩余即x2v(modn),且vi-1存在。这串v1,v2,…,vk为公开密钥。计算满足si=sqrt(vi-1)modn的最小的si,这一串s1,s2,…,sk为秘密密钥。协议:甲选择一个随机数r,r<n。计算x=r2modn,将x发送给乙;乙向甲发送一个随机的k位串:b1,b2,…,bk;甲计算y=r*(s1b1*s2b2*…*skbk)modn,将y发送给乙;乙验证是否有x=y2*(v1b1*v2b2*…*vkbk)modn。甲乙将这个协议重复t次,每次用一个不同的随机值r直到乙相信甲知道s1,s2,…,sk为止。甲能欺骗乙的机会为1/2kt。建议至少取k=5和t=4。举例:设模n=35,k=4。公开密钥:{4,11,16,29},秘密密钥:{3,4,9,8}。练习1.已知RSA密码体制的公开密钥为n=51,e=11,试加密明文M1=3。通过分解n破译该密码,并对密文C2=6解密。答案:
C1=24,
M2=12
51=3×17
(p-1)(q-1)=2×16=32
e=
11,
d
=
11-1
mod
32
=
3
C1=
311
mod
51
=
24
M2=
63
mod
51
=
122.设n=35,公开密钥为{9,4,11,29},秘密密钥为{2,3,4,8},补充用Feige-Fiat-Shamir协议进行一圈身份验证的过程。(1)甲选择一个随机数r=11,计算
112mod35=16
,并发送给乙;(2)乙向甲发送一个随机的二进制串:{1,0,1,0};(3)甲计算
11*21*30*41*80mod35=18
发送给乙;(4)乙验证是否有
182*91*40*111*290mod35=16
3.设n=11,g=2,x=3,y=2,写出甲乙双方用Diffie-Hellman算法约定密钥的过程。4.设p=11,甲的加密密钥e1=3,乙的加密密钥e2=9,写出甲乙双方用shamir的三次通过协议传输明文M=4的过程。5.已知:超递增序列为{2,3,6,13,27,52}m=105,n=31,密文C=333,求明文。6.设背包公开密钥算法的公开密钥为向量(27,54,35,97,21),某消息M被加密后生成密文C=10,已知系统中模m=100,n=27,试对C解密求出M。解:根据公开密钥{27,54,
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026-2027学年上学期单元测试高一地理测试卷及答案
- 2026-2027学年上学期单元测试七年级化学专题训练卷及答案
- 2025法律职业资格商经法考前模拟及答案
- 2025大学英语四级词汇语法经典例题及答案
- 2025叉车司机场内机动车辆基础易混辨析题及答案
- 数据中心冷冻水二次泵变频调试方案
- 航空客户满意度实施评估表
- 特别管控危险化学品目录(第一版)及管控措施
- 酒店与度假村经理战略执行评估表
- 服务器硬件故障诊断与维修操作手册
- 2026秋小学人教版数学五年级上册第五单元学情测试练习卷含参考答案
- 大专护理专业毕业综合考试题(含详细答案)
- 工程力学 第2版 课件 第7章-扭转
- 消毒供应室降低纸塑包装物品灭菌后水迹发生率品管圈PDCA案例所有图表均可以直接点击编辑修改
- 银行对公业务分配制度
- 乡镇卫生院人员招聘制度
- DB11∕T 498-2021 南美白对虾淡水养殖技术规范
- 林草工程技术人员法律法规与职业道德试题库
- 难点解析-山东省海阳市中考数学真题分类(二元一次方程组)汇编必考点解析试题(含答案及解析)
- 内容电商运营(AIGC版 微课版 第2版)-课程标准、课程整体设计
- 20kV及以下配电网建设项目扩大工程量清单(2025年版)
评论
0/150
提交评论