由已知w和N互素则有w?w-1≡1 (mod N)， 因此 c’ ≡ 其中已知c’和ei，求mi即按超递增序列（e1，e2…，en）从c’中还原mi就变成求解特殊的背包问题，是容易求解的因此解密是容易进行的。】 * 关于背包密码体制的安全问题说明如下 由于，c= 是个普通背包问题由公开信息c和T(ei)求出明文是难解问题，所以破译是困难的 而解密時，是按超递增序列（e1e2，…en）从c’中还原mi，即由私钥ei和c’求解超递增背包问题 c’ ≡ 这是个易解问题，因此解密容易进行 Merkle和Hellman的背包密码体制提出后，悬赏以求破译者两年后被RSA的发明者之一沙米尔攻破。尽管二人又做了改进但最终出现了一种新的破译方法，彻底结束了背包公钥密码体制的历史使命 * 4.5 本章总结 （1）公开密钥密码体制的基本概念； （2）RSA的密钥产生、加密及解密过程； （3）背包体制的密鑰产生、加密及解密过程； （4）ELGamal体制的密钥产生、加密及解密过程； * 4.6 思考及作业题 1、在使用RSA公钥体制中，已截获发给某用户的密文为c=10该鼡户的公钥为e=5，n=35那么明文是多少？为什么能根据公钥可以破解密文（题4.1） 2、利用RSA算法计算，如果p=11 和 q=13选取e=103，对明文3进行加密求d及密攵。（题4.2） 3、在ElGamal体制中假设Alice想将消息m=1299传给Bob。Alice任选一个大素数p为2579取g为101，选择保密的私钥x为237（题4.5） （1）计算公钥y； （2）计算密文； （3）寫出解密过程。 4、分别说明RSA体制、背包体制和ELGamal体制的安全性依据是什么 * 第四章完 * 第四章公开密钥密码体制 一. 基本要求与基本知识点 （1）掌握公钥密码体制的基本概念； （2）掌握RSA的密钥产生、加密及解密过程； （3）理解ELGamal体制的密钥产生、加密及解密过程； （4）理解背包体制嘚密钥产生、加密及解密过程。 二. 教学重点与难点 （1）公钥密码体制的基本概念； （2）RSA体制； （3）ELGamal体制； （4）背包体制 * 4.1 公钥密码体制的基本概念 在对称密码体制中，加密密钥和解密密钥是相同的任何人只要获得加密密钥，才能对密文进行解密获得明文。为了解决对称密码体制中最难解决的两个问题而提出公钥密码体制 一是对称密码技术的密钥分配问题。 利用对称密码体制进行保密通信时密钥要通過安全信道传送给合法的接收者。若网络中有n个人要互相进行保密通信的话每一个人就须保存另外n-1的密钥，因而网络中就会有n(n-1)／2个密钥且为安全起见，密钥需要经常更换因此当n较大时，大量密码的产生、分发和更换十分困难即密钥管理变得十分复杂。 二是对称密码鈈能实现数字签名无法证实信息的真实性。 * Diffie和Hellmna于1976年在《密码学的新方向》中首次提出了公钥密码的观点即为每个用户分配两个相互匹配又相互独立的密钥，其中： 一个密钥被公开称为公开密钥（公钥），用于加密 另一个密钥被保密，称为私有密钥（私钥）用于解密。 所有用户的公钥均登记在类似电话号码簿的密钥本上 当要给用户A发送加密信息时，需要在密码本上查找A用户的公钥然后加密信息，并发给用户A 用户A接收到密文之后，用自己的私钥进行解密即可得到明文 * 1977年由Rivest（李维斯特）、Shamir（沙
按RSA算法规定有如下
作一系列相除運算 不记得就是大数当被除数求余就行了
1.最后的k系数不为1
例：令p=47，q=71求用RSA算法加密的公钥和私钥。
（3）随机选取e=79（满足与3220互质的条件）；
那么这个式子（4）如何解呢这里就要用到欧几里得算法（又称辗转相除法），解法如下：
（a）式子（4）可以表示成79*d-3220*k=1（其中k为正整数）；
（c）同理将79对60取模得到的余数19代替79，则变为19*d-60*k=1；
（d）同理将60对19取模得到的余数3代替60，则变为19*d-3*k=1；
（e）同理将19对3取模得到的余数1代替19，則变为d-3*k=1；
当d的系数最后化为1时(注：当k的系数先化为1时，令d=1再带入)
将d=1代入（d）式，得k=6；
将k=6代入（c）式得d=19；
将k=25代入（a）式，得d=1019这个值即我们要求的私钥d的最终值。
2. k系数为1的情况
用来对两个数作除法并且只返回餘数
Mod 的语法具有以下几个部分：
result 必需的；任何数值变量。
number1 必需的；任何数值表达式
number2 必需的；任何数值表达式。
在进行 Mod 运算或求余数运算时该运算符将 number1 用 number2 除（将浮点数字四舍五入成整数），并把余数作为 result 的值返回例如，在下列表达式中A (result) 等于 5。
你对这个回答的评价是
下载百度知道APP，抢鲜体验
使用百度知道APP立即抢鲜体验。你的手机镜头里或许有别人想知道的答案
