下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 密码学RSA

密码学RSA.doc

密码学RSA

rachel
2018-09-06 0人阅读 举报 0 0 暂无简介

简介:本文档为《密码学RSAdoc》,可适用于IT/计算机领域

公开密钥密码体制公开密钥密码体制概论一、公钥密码体制公开密码体制具有以下的特征:()用户必须能够有效地计算公开的和秘密的密钥对PK和SK。()如果不知道SK那么即使知道PK算法E和D以及密文Y确定明文X的计算也是不可行的。()继加密之后再脱密应还原出原来的明文X即DSK(EPK(X))=X(*)上式对EPK域中的全部X都成立。EPK(DSK(X))=X(**)公钥密码体制有以下特点:⑴密钥分发简单。⑵秘密保存的密钥量减少。⑶可以满足互不相识的人之间的私人谈话的保密性要求。⑷可以完成数字签名。(以后解释)二、两种密码体制的差异、算法:公钥密码体制的算法容易用精确的数学术语描述。它建立在特定的已知数学问题上安全性依赖于这种数学问题的求解是计算上不可能的。与此相对传统密码体制的算法以复杂紊乱的数学方程为基础。虽然求解单个方程并不困难但由于它被多次迭代和搅乱以至无法用解析法求解。、密钥:这两种密码体制的密钥产生方式也不同。在传统密码体制中加密密钥和解密密钥可以简单的互相推导因此它们是以简单的方法随机选择的。在公开密钥密码体制中由公开密钥不能简单地推出秘密密钥。秘密密钥是按照特定的要求选择的而公开密钥又是由秘密密钥利用确定的步骤有效地计算出来的。RSA密码体制和预备知识RSA密码体制是由美国的Rivest(里夫斯特)Shamir(沙米尔)和Adleman(艾德勒曼)发明的并以他们的名字命名这种体制的保密性是建立在大素数因子的合数进行因子分解是一个非常困难的问题上的。一、数论的基本性质:定义:只能被和它自身整除而不能被其它正整数整除的大于的正整数称为素数(质数)。定理:设a和r是两个整数r≠则必有二整数q及i存在使得a=qri≤i<∣r∣定理:设a和b是两个整数且(a,b)=d(d是a与b的最大公因数)则存在整数s和t使得d=satb。定理(素因数分解定理):每个大于的正整数恰有一种方法表示成素数的乘积(不计素数因子出现的先后次序)。二、同余的概念及基本性质:定义:如果两个整数a和b的差ab能被另一个整数r整除即r∣ab,则称a,b关于模r同余用符号a≡b(modr)表示。(即a和b有相同的余数)。若a≡b(modr)即ab=mr即a=bmr也就是说a,b被r除时余数相同。显然同余关系是一个等价关系即自反的:a≡a(modr)对称的:若a≡b(modr),则b≡a(modr)可传递的:如果a≡b,b≡c(modr),则a≡c(modr)定理:如果a≡b(modr),a≡b(modr),……,an≡bn(modr)则a·a……an≡b·b……bn(modr)推论:如果a≡b(modr),则对于任意正整数n,an≡bn(modr)推论:如果a≡b(modr),则对于任意整数cac≡bc(modr)定理:对于任意的整数a和m及任意的正整数n有an≡(amr)n(modr)命题:若ca≡cb(modr)且(c,r)=,则a≡b(modr)定理(按模计算原理):设a和a为整数op表示二元操作符+,-,×则(aopa)modr=(amodr)op(amodr)modr其中amodr表示a被r除后的余数,amodr=resr(a)定理:若(a,r)=则同余式ax≡(modr)有唯一解。三、欧拉函数为了讨论的方便以下均假设模r是正整数。按模r将整数集I分成r个子集每一个子集称为模r的一个同余类同一个同余类中的任意两个整数被r除后的余数相同而不同同余类中的数被r除后的余数不相同。定义:从模r的每一个同余类(即等价类中)取出一个数这r个数构成的集合称为r的完全剩余系。命题:()若a与r互质则a所在的同余类中所有的数都与r互质()若a不与r互质则a所在的同余类中所有的数而都不与r互质。定义:在r的一个完全剩余系中所有与r互素的数构成的系称为r的简化剩余系。定义:r的一个完全剩余系中与r互质的数的个数称为r的欧拉函数用(r)表示((r)表示r的简化剩余系中数的个数)。定义(欧拉函数):(r)表示……r这r个数中与r互质的数的个数称为r的欧拉函数。例()=()={,,,}一般来说①若r是质数则(r)=r②若r是合数则(r)<r③当r=时所有的整数都与互质(α,)=由于所有的整数与的最大公约数均为所以这个类是与互质的类∴()=命题:若(xr)=,(xr)=,……,(xnr)=则(xx……xnr)=命题:若(a,b)=,则(ab)=(a)(b)定理:设r=EMBEDEquation……p(其中每一pi均为素数)则(r)=r()()……()定理:(Euler定理)若(ar)=,则aφ(r)≡(modr)定理:设r=pq是两个素数因子的乘积a是小于r的任一非负整数(即a∈{,,,……,r}),m是任一正整数则amφ(r)≡a(modr)四、欧几里得算法()如何求a,b的最大公因数(a,b)=gcd(a,b)()如何判断a,b是否互质。按方法()求出gcd(a,b)若gcd(a,b)=则a,b互质否则不互质。()再回过来看定理。若(a,r)=,则同余式ax≡(modr)的解如何求。.RSA算法介绍一、密钥的选择和计算、随机地选择两个素数p和q。选取原则:⑴p和q都要足够大⑵p≠q⑶p和q要是秘密的⑷和不能相差太大(否则小的可用穷举法)。、计算出r=p•q(r可公开)。、计算欧拉函数(r)=r()()=(p)(q)、选取一个与(r)互素(质)的正整数K,将k定义为公开密钥PK(或将K定义为秘密密钥SK)。、由公开密钥PK求秘密密钥SK(或由秘密密钥SK计算公开密钥)。(因为(PK,(r))=所以由定理知PK•X≡mod((r))有唯一的解其解可作秘密密钥SK。)二、加密变换用RSA加密前先将明文数字化。、将要保护的明文信息分成一连串十进制数的数据块每个数据块的值不超过r。、分别对每一个数据块进行加密产生相应的密文块。方法是:将明文块Xi自乘PK次后用r去除取其余数。设X=XXX……Xn,对明文块Xi进行加密所得的密文块用Yi表示则密文Y=YY……Yn每个密文块Yi用下述方法计算产生:Yi=EPK(Xi)Yi≡(modr)要求≤Yi<r(实际上要求yi的值也不超过r-)、解密变换:对每一个密文块Yi进行解密还原出相应的明文方法是:将密文块Yi自乘SK次后用r去除取其余数(≤余数<r)。因此还原出的明文满足≤Xi<r。若不限制则可还原为多个明文使之不能正确还原。Xi=DSK(Yi)Xi≡(modr)≤Xi<r四、使用RSA算法的注意事项、r必须选取得相当大比如位十进制数以上。、在RSA中还应要求所用素为数p和q的长度相差比较少使敌手难以估计p,q的大致范围。、p和q都应含有大的素数因子以增加敌手猜出(r)的难度。PAGEunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknown

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/4

密码学RSA

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利