加密算法之RSA算法

它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作,也很流行。算法的名字以发明者的名字命名:Ron Rivest, Adi Shamir 和Leonard Adleman。但RSA的安全性一直未能得到理论上的证明。它经历了各种攻击,至今未被完
全攻破。一、RSA算法 :
首先,找出三个数,p,q,r,其中p,q是两个相异的质数,r是与(p-1)(q-1)互质的数......p,q,r这三个数便是privatekey接著,找出m,使得rm==1mod(p-1)(q-1).....这个m一定存在,因为r与(p-1)(q-1)互质,用辗转相除法就可以得到了.....再来,计算n=pq.......m,n这两个数便是publickey编码过程是,若资料为a,将其看成是一个大整数,假设a<n....如果a>=n的话,就将a表成s进位(s<=n,通常取s=2^t),则每一位数均小於n,然後分段编码......接下来,计算b==a^mmodn,(0<=b<n),b就是编码後的资料......解码的过程是,计算c==b^rmodpq(0<=c<pq),於是乎,解码完毕......等会会证明c和a
其实是相等的:)如果第三者进行窃听时,他会得到几个数:m,n(=pq),b......他如果要解码的话,必须想办法得到r......所以,他必须先对n作质因数分解.........要
防止他分解,最有效的方法是找两个非常的大质数p,q,使第三者作因数分解时发生困难.........<定理>若p,q是相异质数,rm==1mod(p-1)(q-1),a是任意一个正整数,b==a^mmodpq,c==b^rmodpq,则c==amodpq证明的过程,会用到费马小定理,叙述如下:m是任一质数,n是任一整数,则n^m==nmodm(换另一句话说,如果n和m互质,则n^(m-1)==1modm)运用一些基本的群论的知识,就可以很容易地证出费马小定理的........<证明>因为rm==1mod(p-1)(q-1),所以rm=k(p-1)(q-1)+1,其中k是整数因为在modulo中是preserve乘法的(x==ymodzandu==vmodz=>xu==yvmodz),所以,c==b^r==(a^m)^r==a^(rm)==a^(k(p-1)(q-1)+1)modpq1.如果a不是p的倍数,也不是q的倍数时,则a^(p-1)==1modp(费马小定理)=>a^(k(p-1)(q-1))==1modpa^(q-1)==1modq(费马小定理)=>a^(k(p-1)(q-1))==1modq所以p,q均能整除a^(k(p-1)(q-1))-1=>pq|a^(k(p-1)(q-1))-1即a^(k(p-1)(q-1))==1modpq=>c==a^(k(p-1)(q-1)+1)==amodpq2.如果a是p的倍数,但不是q的倍数时,则a^(q-1)==1modq(费马小定理)=>a^(k(p-1)(q-1))==1modq=>c==a^(k(p-1)(q-1)+1)==amodq=>q|c-a因p|a=>c==a^(k(p-1)(q-1)+1)==0modp=>p|c-a所以,pq|c-a=>c==amodpq3.如果a是q的倍数,但不是p的倍数时,证明同上4.如果a同时是p和q的倍数时,则pq|a=>c==a^(k(p-1)(q-1)+1)==0modpq=>pq|c-a=>c==amodpqQ.E.D.这个定理说明a经过编码为b再经过解码为c时,a==cmodn(n=pq)....但我们在做编码解码时,限制0<=a<n,0<=c<n,所以这就是说a等於c,所以这个过程确实能做到编码解码的功能.....二、RSA 的安全性RSA的安全性依赖于大数分解,
但是否等同于大数分解一直未能得到理论上的证明,因为没有证明破解 RSA就一定需要作大数分解。假设存在一种无须分解大数的算法,那它
肯定可以修改成为大数分解算法。目前, RSA 的一些变种算法已被证明等价于大数分解。不管怎样,分解n是最显然的攻击方法。现在,人们已能分解多个十进制位的大素数。因此,模数n 必须选大一些,因具体适用情况而定。三、RSA的速度由于进行的都是大数计算,使得RSA最快的情况也比DES慢上倍,无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。四、RSA的选择密文攻击RSA在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装( Blind),让拥有私钥的实体签署。然后,经过计算就可得到它所想要的信息。实际上,攻击利用的都是同一个弱点,即存在这样一个事实:乘幂保留了输入的乘法结构: ( XM )^d = X^d *M^d mod n前面已经提到,这个固
有的问题来自于公钥密码系统的最有用的特征--每个人都能使用公钥。但从算法上无法解决这一问题,主要措施有两条:一条是采用好的公钥协议,保证工作过程中实体不对其他实体任意产生的信息解密,不对自己一无所知的信息签名;另一条是决不对陌生人送来的随机文档签名,签名时首先使用One-Way HashFunction 对文档作HASH处理,或同时使用不同的签名算法。在中提到了几种不同类型的攻击方法。五、RSA的公共模数攻击若系统中共有一个模数,只是不同的人拥有不同的e和d,系统将是危险的。最
普遍的情况是同一信息用不同的公钥加密,这些公钥共模而且互质,那末该信息无需私钥就可得到恢复。设P为信息明文,两个加密密钥为e1和e2,公共模数是n,则:C1 = P^e1 mod nC2 = P^e2 mod n密码分析者知道n、e1、e2、C1和C2,就能得到P。因为e1和e2互质,故用Euclidean算法能找到r和s,满足:r * e1 + s * e2 = 1假设r为负数,需再用Euclidean算法计算C1^(-1),则( C1^(-1) )^(-r) * C2^s = P mod n另外,还有其它几种利用公共模数攻击的方法。总之,如果知道给定模数的一对e和d,一是有利于攻击者分解模数,一是有利于攻击者计算出其它成对的e’和d’,而无需分解模数。解决办法只有一个,那就是不要共享模数n。RSA的小指数攻击。 有一种提高 RSA速度的建议是使公钥e取较小的值,这样会使加密变得易于实现,速度有所提高。但这样作是不安全的,对付办法就是e和d都取较大的值。RSA算法是第一个能同时用于加密和数字签名的算法,也易于理解和操作。RSA是被研究得最广泛的公钥算法,从提出到现在已近二十年,经历了各种攻击的考验,逐渐为人们接受,普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解,但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何,而且密码学界多数人士倾向于因子分解不是NPC问题。 RSA的缺点主要有:A)产生密钥很麻烦,受到素数产生技术的限制,因而难以做到一次一密。B)分组长度太大,为保证安全性,n 至少也要 600 bits 以上,使运算代价很高,尤其是速度较慢,较对称密码算法慢几个数量级;且随着大数分解技术的发展,这个长度还在增加,不利于数据格式的标准化。目前,SET( Secure Electronic Transaction )协议中要求CA采用比特长的密钥,其他实体使用比特的密钥。 给力(0票)动心(0票)废话(0票)专业(0票)标题党(0票)路过(0票) 原文:加密算法之RSA算法 返回网络安全首页

时间: 2024-10-14 02:54:34

加密算法之RSA算法的相关文章

非对称加密算法-RSA算法

一.概述  1.RSA是基于大数因子分解难题.目前各种主流计算机语言都支持RSA算法的实现  2.java6支持RSA算法  3.RSA算法可以用于数据加密和数字签名  4.RSA算法相对于DES/AES等对称加密算法,他的速度要慢的多  5.总原则:公钥加密,私钥解密  /   私钥加密,公钥解密   二.模型分析 RSA算法构建密钥对简单的很,这里我们还是以甲乙双方发送数据为模型 1.甲方在本地构建密钥对(公钥+私钥),并将公钥公布给乙方 2.甲方将数据用私钥进行加密,发送给乙方 3.乙方用

数据传输加密非对称加密算法以及对称算法-RSA+AES

转载:http://blog.csdn.net/chay_chan/article/details/58605605 源码:https://github.com/Javen205/IJPay 数据传输加密   在开发应用过程中,客户端与服务端经常需要进行数据传输,涉及到重要隐私信息时,开发者自然会想到对其进行加密,即使传输过程中被"有心人"截取,也不会将信息泄露.对于加密算法,相信不少开发者也有所耳闻,比如MD5加密,Base64加密,DES加密,AES加密,RSA加密等等.在这里我主

RSA算法原理(二)

上一次,我介绍了一些数论知识. 有了这些知识,我们就可以看懂RSA算法.这是目前地球上最重要的加密算法. 六.密钥生成的步骤 我们通过一个例子,来理解RSA算法.假设爱丽丝要与鲍勃进行加密通信,她该怎么生成公钥和私钥呢? 第一步,随机选择两个不相等的质数p和q. 爱丽丝选择了61和53.(实际应用中,这两个质数越大,就越难破解.) 第二步,计算p和q的乘积n. 爱丽丝就把61和53相乘. n = 61×53 = 3233 n的长度就是密钥长度.3233写成二进制是110010100001,一共有

RSA算法原理(一)

如果你问我,哪一种算法最重要? 我可能会回答"公钥加密算法". 因为它是计算机通信安全的基石,保证了加密数据不会被破解.你可以想象一下,信用卡交易被破解的后果. 进入正题之前,我先简单介绍一下,什么是"公钥加密算法". 一.一点历史 1976年以前,所有的加密方法都是同一种模式: (1)甲方选择某一种加密规则,对信息进行加密: (2)乙方使用同一种规则,对信息进行解密. 由于加密和解密使用同样规则(简称"密钥"),这被称为"对称加密算法

RSA算法使用介绍

原文地址: http://www.devdiv.com/rsa_-blog-20-11254.html RSA是目前最有影响力的公钥加密算法,该算法基于一个十分简单的数论事实:将两个大素数相乘十分容易,但那时想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥,即公钥,而两个大素数组合成私钥.公钥是可发布的供任何人使用,私钥则为自己所有,供解密之用.         解密者拥有私钥,并且将由私钥计算生成的公钥发布给加密者.加密都使用公钥进行加密,并将密文发送到解密者,解密者用私钥解

JAVA加密解密之RSA算法

RSA公钥加密算法是1977年由罗纳德·李维斯特(Ron Rivest).阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的.1987年首次公布,当时他们三人都在麻省理工学院工作.RSA就是他们三人姓氏开头字母拼在一起组成的. RSA是目前最有影响力的公钥加密算法,它能够抵抗到目前为止已知的绝大多数密码攻击,已被ISO推荐为公钥数据加密标准. 今天只有短的RSA钥匙才可能被强力方式解破.到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式.只

RSA算法

先说下这个算法,RSA公钥加密算法是1977年由Ron Rivest.Adi Shamirh和LenAdleman在(美国麻省理工学院)开发的. 这个算法的名字也是他们三个人名字首字母,RSA算法基于一个十分简单的数论事实:将两个大素数相乘十分容易,但想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥. package rsa; import java.math.BigInteger; public class RSA { private long p,q,e,d,n; publ

Swift 使用RSA算法进行数据加密,解密以及数字签名

RSA算法是一种非对称加密算法,要了解RSA算法,首先要知道什么是对称加密算法,什么是非对称加密算法. 1,对称加密算法 密钥只有一个,发收信双方都使用这个密钥对数据进行加密和解密. 特点:算法公开.计算量小.加密速度快.加密效率高特点.但交易双方都使用同样钥匙,安全性得不到保证. 具体算法有:DES算法,3DES算法,TDEA算法,Blowfish算法,RC5算法,IDEA算法. 2,非对称加密算法 非对称加密算法需要两个密钥:公开密钥(publickey)和私有密钥(privatekey).

Node.js与PHP之间通过RSA算法实现签名验证

Node.js与PHP之间通过RSA算法实现签名验证 做过web开发的同学都知道我们经常在接口间交互的时候为了防止数据伪造并 且保证安全性我们会采用签名的方式进行验证, 签名的算法我们一般选择RSA非对称加密算法.想了解更多签名与RSA算法知识可以去查阅PKCS#1.PKCS#7相关资料. 笔者在做利用Node.js做单点登录的时候涉及到了Node.js项目中产生的签名,然后需要到PHP项目中去验签,具体实现如下. 首先准备RSA公钥和私钥,格式均为PEM openssl产生pem格式私钥 op