导航:首页 > 文档加密 > rsa加密解密转换证明

rsa加密解密转换证明

发布时间:2023-01-03 23:03:39

㈠ rsa加密和解密的理论依据是什么

以前也接触过RSA加密算法,感觉这个东西太神秘了,是数学家的事,和我无关。但是,看了很多关于RSA加密算法原理的资料之后,我发现其实原理并不是我们想象中那么复杂,弄懂之后发现原来就只是这样而已..
学过算法的朋友都知道,计算机中的算法其实就是数学运算。所以,再讲解RSA加密算法之前,有必要了解一下一些必备的数学知识。我们就从数学知识开始讲解。
必备数学知识
RSA加密算法中,只用到素数、互质数、指数运算、模运算等几个简单的数学知识。所以,我们也需要了解这几个概念即可。
素数
素数又称质数,指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数。这个概念,我们在上初中,甚至小学的时候都学过了,这里就不再过多解释了。
互质数
网络上的解释是:公因数只有1的两个数,叫做互质数。;维基网络上的解释是:互质,又称互素。若N个整数的最大公因子是1,则称这N个整数互质。
常见的互质数判断方法主要有以下几种:
两个不同的质数一定是互质数。例如,2与7、13与19。
一个质数,另一个不为它的倍数,这两个数为互质数。例如,3与10、5与 26。
相邻的两个自然数是互质数。如 15与 16。
相邻的两个奇数是互质数。如 49与 51。
较大数是质数的两个数是互质数。如97与88。
小数是质数,大数不是小数的倍数的两个数是互质数。例如 7和 16。
2和任何奇数是互质数。例如2和87。
1不是质数也不是合数,它和任何一个自然数在一起都是互质数。如1和9908。
辗转相除法。
指数运算
指数运算又称乘方计算,计算结果称为幂。nm指将n自乘m次。把nm看作乘方的结果,叫做”n的m次幂”或”n的m次方”。其中,n称为“底数”,m称为“指数”。
模运算
模运算即求余运算。“模”是“Mod”的音译。和模运算紧密相关的一个概念是“同余”。数学上,当两个整数除以同一个正整数,若得相同余数,则二整数同余。
两个整数a,b,若它们除以正整数m所得的余数相等,则称a,b对于模m同余,记作: a ≡ b (mod m);读作:a同余于b模m,或者,a与b关于模m同余。例如:26 ≡ 14 (mod 12)。
RSA加密算法
RSA加密算法简史
RSA是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。
公钥与密钥的产生
假设Alice想要通过一个不可靠的媒体接收Bob的一条私人讯息。她可以用以下的方式来产生一个公钥和一个私钥:
随意选择两个大的质数p和q,p不等于q,计算N=pq。
根据欧拉函数,求得r = (p-1)(q-1)
选择一个小于 r 的整数 e,求得 e 关于模 r 的模反元素,命名为d。(模反元素存在,当且仅当e与r互质)
将 p 和 q 的记录销毁。
(N,e)是公钥,(N,d)是私钥。Alice将她的公钥(N,e)传给Bob,而将她的私钥(N,d)藏起来。
加密消息
假设Bob想给Alice送一个消息m,他知道Alice产生的N和e。他使用起先与Alice约好的格式将m转换为一个小于N的整数n,比如他可以将每一个字转换为这个字的Unicode码,然后将这些数字连在一起组成一个数字。假如他的信息非常长的话,他可以将这个信息分为几段,然后将每一段转换为n。用下面这个公式他可以将n加密为c:

ne ≡ c (mod N)
计算c并不复杂。Bob算出c后就可以将它传递给Alice。
解密消息
Alice得到Bob的消息c后就可以利用她的密钥d来解码。她可以用以下这个公式来将c转换为n:
cd ≡ n (mod N)
得到n后,她可以将原来的信息m重新复原。
解码的原理是:
cd ≡ n e·d(mod N)
以及ed ≡ 1 (mod p-1)和ed ≡ 1 (mod q-1)。由费马小定理可证明(因为p和q是质数)
n e·d ≡ n (mod p) 和 n e·d ≡ n (mod q)
这说明(因为p和q是不同的质数,所以p和q互质)
n e·d ≡ n (mod pq)
签名消息
RSA也可以用来为一个消息署名。假如甲想给乙传递一个署名的消息的话,那么她可以为她的消息计算一个散列值(Message digest),然后用她的密钥(private key)加密这个散列值并将这个“署名”加在消息的后面。这个消息只有用她的公钥才能被解密。乙获得这个消息后可以用甲的公钥解密这个散列值,然后将这个数据与他自己为这个消息计算的散列值相比较。假如两者相符的话,那么他就可以知道发信人持有甲的密钥,以及这个消息在传播路径上没有被篡改过。

RSA加密算法的安全性

当p和q是一个大素数的时候,从它们的积pq去分解因子p和q,这是一个公认的数学难题。然而,虽然RSA的安全性依赖于大数的因子分解,但并没有从理论上证明破译RSA的难度与大数分解难度等价。
1994年彼得·秀尔(Peter Shor)证明一台量子计算机可以在多项式时间内进行因数分解。假如量子计算机有朝一日可以成为一种可行的技术的话,那么秀尔的算法可以淘汰RSA和相关的衍生算法。(即依赖于分解大整数困难性的加密算法)
另外,假如N的长度小于或等于256位,那么用一台个人电脑在几个小时内就可以分解它的因子了。1999年,数百台电脑合作分解了一个512位长的N。1997年后开发的系统,用户应使用1024位密钥,证书认证机构应用2048位或以上。
RSA加密算法的缺点

虽然RSA加密算法作为目前最优秀的公钥方案之一,在发表三十多年的时间里,经历了各种攻击的考验,逐渐为人们接受。但是,也不是说RSA没有任何缺点。由于没有从理论上证明破译RSA的难度与大数分解难度的等价性。所以,RSA的重大缺陷是无法从理论上把握它的保密性能如何。在实践上,RSA也有一些缺点:
产生密钥很麻烦,受到素数产生技术的限制,因而难以做到一次一密;
分组长度太大,为保证安全性,n 至少也要 600 bits 以上,使运算代价很高,尤其是速度较慢,。

㈡ 理论分析和举例说明RSA的加密和解密是互逆的

由于没有办法打出fai这个希腊字母 n的欧拉函数我用@(n)来表示
^ 代表幂的意思
e*d=1(mod @(n))
m为明文 c为密文
加密:c=m^e(mod n)
解密:m=c^d(mod n)
证明加密解密互逆也就是证明:
m=(m^e)^d(mod n) //把加密式子过程的c 带到解密过程那个式子中
也就是证明 m=m^(e*d) (mod n)

因为 e*d=1(mod @(n)) 可以推导出 e*d=k*@(n)+1
所以m=m*(k*@(n)+1) (mod n)
也就可以写出m=m*m^(k*@(n)) (mod n)
因为根据费马定理 m^(@(n))=1 (mod n)
所以m^(k*@(n)) =1^k(mod n)=1(mod n)
m*m^(k*@(n)) (mod n)=m*1 (mod n)=m(mod n)证明就ok了

主要把握2点: 费马定理
公私钥关于@(n)互逆 就松松搞定

㈢ rsa加密算法

rsa加密算法如下:

算法原理:

RSA公开密钥密码体制的原理是:根据数论,寻求两个大素数比较简单,而将它们的乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥

㈣ RSA加密解密算法的证明

1. 选择两个质数 p, q

2. 设 n =p * q

3. 求出n的欧拉函数 f = (p-1)*(q-1)

4. 在[2, f)的范围内随机找一个与f互质的数 e 作为公钥的指数

5. 算出私钥指数d,d为公钥指数e对 f 的一个模反元素,即 ed = kf +1 (k为正整数)

6. 将(n, e)封装成公钥,将(n, d)封装成私钥

1. 设被加密的数为m, m为小于n的非负整数

2. 算出 c = (m^e) % n ,则 c 即为密文

算出 (c^d)%n , 即为被加密的数m,证明如下。

因为  c=m^e - n*g,其中g为非负整数,

所以  (c^d)%n = [ (m^e - n*g) ^ d ] % n

展开多项式后将n的整数倍的项去除,得到

[( m^e )^d] % n

=[ m^(e*d) ] % n

=[ m^(k*f+1) ] % n

=[ m * m^(k*f) ] % n

={ m * [ (m^f) ^ k] } % n

接下来分三种情况讨论:

第一种情况:m=0或者m=1

则 { m * [ (m^f) ^ k] } % n = m

第二种情况:m>1,且m与n互质

根据  欧拉定理   ,m^f = h*n+1,其中h为正整数

则 { m * [ (m^f) ^ k] } % n

={ m * [ ( h*n+1 ) ^ k] } % n

={ m * [ i*n + 1 ] } % n    (其中i为展开指数多项式后合并n的同类项得到的正整数)

=m%n 

=m  (因为m<n)

第三种情况:m>1,且m与n不互质

因为n=p*q, 且p, q均为质数,则 m=j*p或者j*q, 其中j为正整数

当m=j*p时, 因为m<n, 所以m与q互质

(证明:如果m, q不互质,则m含有质因数q,因为p与q互质, 所以 j 含有质因数p, 这与m<n矛盾)

根据欧拉定理 m^(q-1)=x*q+1 ,其中x为正整数

则 { m * [ (m^f) ^ k] } % n

= { m * [ ( m^[(p-1)*(q-1)] ) ^ k] } % n

={ m * [ m^(q-1)^(p-1)^k ] } % n

={ j * p * [ ( x*q+1 )^ (p-1)^k ] } % n

={ j * p * [ y*q + 1 ] } % n    (其中y为展开指数多项式后合并q的同类项得到的正整数)

=(j*p*y*q + m ) %n

=(j*y*n+m) % n

=m

同理,当m=j*q时也成立。

证明完毕。

RSA解密正确性证明_国科大网安二班的博客-CSDN博客

https://blog.csdn.net/weixin_46395886/article/details/114700012#:~:text=RSA%E8%A7%A3%E5%AF%86%E6%AD%A3%E7%A1%AE%E6%80%A7%E8%AF%81%E6%98%8E%20%E5%85%88%E6%8F%8F%E8%BF%B0%E4%B8%80%E4%B8%8BRSA%E5%AF%86%E7%A0%81%E4%BD%93%E5%88%B6%EF%BC%9A%20RSA%E5%AF%86%E7%A0%81%E4%BD%93%E5%88%B6%EF%BC%9A%20%E5%A4%A7%E7%B4%A0%E6%95%B0%20p%2Cq%20%EF%BC%8C%E6%A8%A1%E6%95%B0,n%20%3D%20pq%20%EF%BC%8C%E5%8A%A0%E5%AF%86%E6%8C%87%E6%95%B0%20b%20%EF%BC%8C%E8%A7%A3%E5%AF%86%E6%8C%87%E6%95%B0

RSA算法原理 - 知乎 (hu.com)

https://zhuanlan.hu.com/p/48249182#:~:text=RSA%E7%AE%97%E6%B3%95%E5%8E%9F%E7%90%86%201%20%EF%BC%881%EF%BC%89%E4%B9%99%E6%96%B9%E7%94%9F%E6%88%90%E4%B8%A4%E6%8A%8A%E5%AF%86%E9%92%A5%20%28%E5%85%AC%E9%92%A5%E5%92%8C%E7%A7%81%E9%92%A5%29%E3%80%82...,2%20%EF%BC%882%EF%BC%89%E7%94%B2%E6%96%B9%E8%8E%B7%E5%8F%96%E4%B9%99%E6%96%B9%E7%9A%84%E5%85%AC%E9%92%A5%EF%BC%8C%E7%84%B6%E5%90%8E%E7%94%A8%E5%AE%83%E5%AF%B9%E4%BF%A1%E6%81%AF%E5%8A%A0%E5%AF%86%E3%80%82%203%20%EF%BC%883%EF%BC%89%E4%B9%99%E6%96%B9%E5%BE%97%E5%88%B0%E5%8A%A0%E5%AF%86%E5%90%8E%E7%9A%84%E4%BF%A1%E6%81%AF%EF%BC%8C%E7%94%A8%E7%A7%81%E9%92%A5%E8%A7%A3%E5%AF%86%E3%80%82

㈤ 密码学基础(三):非对称加密(RSA算法原理)

加密和解密使用的是两个不同的秘钥,这种算法叫做非对称加密。非对称加密又称为公钥加密,RSA只是公钥加密的一种。

现实生活中有签名,互联网中也存在签名。签名的作用有两个,一个是身份验证,一个是数据完整性验证。数字签名通过摘要算法来确保接收到的数据没有被篡改,再通过签名者的私钥加密,只能使用对应的公钥解密,以此来保证身份的一致性。

数字证书是将个人信息和数字签名放到一起,经由CA机构的私钥加密之后生成。当然,不经过CA机构,由自己完成签名的证书称为自签名证书。CA机构作为互联网密码体系中的基础机构,拥有相当高级的安全防范能力,所有的证书体系中的基本假设或者前提就是CA机构的私钥不被窃取,一旦 CA J机构出事,整个信息链将不再安全。

CA证书的生成过程如下:

证书参与信息传递完成加密和解密的过程如下:

互质关系:互质是公约数只有1的两个整数,1和1互质,13和13就不互质了。
欧拉函数:表示任意给定正整数 n,在小于等于n的正整数之中,有多少个与 n 构成互质关系,其表达式为:

其中,若P为质数,则其表达式可以简写为:

情况一:φ(1)=1
1和任何数都互质,所以φ(1)=1;

情况二:n 是质数, φ(n)=n-1
因为 n 是质数,所以和小于自己的所有数都是互质关系,所以φ(n)=n-1;

情况三:如果 n 是质数的某一个次方,即 n = p^k ( p 为质数,k 为大于等于1的整数),则φ(n)=(p-1)p^(k-1)
因为 p 为质数,所以除了 p 的倍数之外,小于 n 的所有数都是 n 的质数;

情况四:如果 n 可以分解成两个互质的整数之积,n = p1 × p2,则φ(n) = φ(p1p2) = φ(p1)φ(p2)

情况五:基于情况四,如果 p1 和 p2 都是质数,且 n=p1 × p2,则φ(n) = φ(p1p2) = φ(p1)φ(p2)=(p1-1)(p2-1)

而 RSA 算法的基本原理就是欧拉函数中的第五种情况,即: φ(n)=(p1-1)(p2-1);

如果两个正整数 a 和 n 互质,那么一定可以找到整数 b,使得 ab-1 被 n 整除,或者说ab被n除的余数是1。这时,b就叫做a的“模反元素”。欧拉定理可以用来证明模反元素必然存在。

可以看到,a的 φ(n)-1 次方,就是a对模数n的模反元素。

n=p x q = 3233,3233写成二进制是110010100001,一共有12位,所以这个密钥就是12位。

在实际使用中,一般场景下选择1024位长度的数字,更高安全要求的场景下,选择2048位的数字,这里作为演示,选取p=61和q=53;

因为n、p、q都为质数,所以φ(n) = (p-1)(q-1)=60×52= 3120

注意,这里是和φ(n) 互互质而不是n!假设选择的值是17,即 e=17;

模反元素就是指有一个整数 d,可以使得 ed 被 φ(n) 除的余数为1。表示为:(ed-1)=φ(n) y --> 17d=3120y+1,算出一组解为(2753,15),即 d=2753,y=-15,也就是(17 2753-1)/3120=15。

注意,这里不能选择3119,否则公私钥相同??

公钥:(n,e)=(3233,2753)
私钥:(n,d)=(3233,17)

公钥是公开的,也就是说m=p*q=3233是公开的,那么怎么求e被?e是通过模反函数求得,17d=3120y+1,e是公开的等于17,这时候想要求d就要知道3120,也就是φ(n),也就是φ(3233),说白了,3233是公开的,你能对3233进行因数分解,你就能知道d,也就能破解私钥。

正常情况下,3233我们可以因数分解为61*53,但是对于很大的数字,人类只能通过枚举的方法来因数分解,所以RSA安全性的本质就是:对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。

人类已经分解的最大整数是:

这个人类已经分解的最大整数为232个十进制位,768个二进制位,比它更大的因数分解,还没有被报道过,因此目前被破解的最长RSA密钥就是768位。所以实际使用中的1024位秘钥基本安全,2048位秘钥绝对安全。

网上有个段子:

已经得出公私钥的组成:
公钥:(n,e)=(3233,2753)
私钥:(n,d)=(3233,17)
加密的过程就是

解密过程如下:

其中 m 是要被加密的数字,c 是加密之后输出的结果,且 m < n ,其中解密过程一定成立可以证明的,这里省略证明过程。

总而言之,RSA的加密就是使用模反函数对数字进行加密和求解过程,在实际使用中因为 m < n必须成立,所以就有两种加密方法:

对称加密存在虽然快速,但是存在致命的缺点就是秘钥需要传递。非对称加密虽然不需要传递秘钥就可以完成加密和解密,但是其致命缺点是速度不够快,不能用于高频率,高容量的加密场景。所以才有了两者的互补关系,在传递对称加密的秘钥时采用非对称加密,完成秘钥传送之后采用对称加密,如此就可以完美互补。

㈥ rsa加密解密算法

1978年就出现了这种算法,它是第一个既能用于数据加密
也能用于数字签名的算法。它易于理解和操作,也很流行。算
法的名字以发明者的名字命名:Ron Rivest, AdiShamir 和
Leonard Adleman。但RSA的安全性一直未能得到理论上的证明。

RSA的安全性依赖于大数分解。公钥和私钥都是两个大素数
( 大于 100个十进制位)的函数。据猜测,从一个密钥和密文
推断出明文的难度等同于分解两个大素数的积。

密钥对的产生:选择两个大素数,p 和q 。计算:
n = p * q
然后随机选择加密密钥e,要求 e 和 ( p - 1 ) * ( q - 1 )
互质。最后,利用Euclid 算法计算解密密钥d, 满足

e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )

其中n和d也要互质。数e和
n是公钥,d是私钥。两个素数p和q不再需要,应该丢弃,不要让任
何人知道。 加密信息 m(二进制表示)时,首先把m分成等长数据
块 m1 ,m2,..., mi ,块长s,其中 2^s <= n, s 尽可能的大。对
应的密文是:

ci = mi^e ( mod n ) ( a )

解密时作如下计算:

mi = ci^d ( mod n ) ( b )

RSA 可用于数字签名,方案是用 ( a ) 式签名, ( b )
式验证。具体操作时考虑到安全性和 m信息量较大等因素,一般是先
作 HASH 运算。

RSA 的安全性。
RSA的安全性依赖于大数分解,但是否等同于大数分解一直未能得到理
论上的证明,因为没有证明破解RSA就一定需要作大数分解。假设存在
一种无须分解大数的算法,那它肯定可以修改成为大数分解算法。目前,
RSA的一些变种算法已被证明等价于大数分解。不管怎样,分解n是最显
然的攻击方法。现在,人们已能分解140多个十进制位的大素数。因此,
模数n必须选大一些,因具体适用情况而定。

RSA的速度:
由于进行的都是大数计算,使得RSA最快的情况也比DES慢上100倍,无论
是软件还是硬件实现。速度一直是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 n

C2 = 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采用2048比特长
的密钥,其他实体使用1024比特的密钥。

阅读全文

与rsa加密解密转换证明相关的资料

热点内容
程序员特殊招数是什么意思 浏览:351
描述加密过程 浏览:844
我的世界如何开mod服务器 浏览:904
人体写生pdf 浏览:317
android短信验证码倒计时 浏览:641
排课走班源码 浏览:222
程序员刚毕业去了小公司有发展吗 浏览:90
速腾怎么安装安卓手机互联 浏览:143
linux设备驱动程序代码 浏览:301
服务器的功耗怎么看 浏览:651
app组件哪里找 浏览:87
androidqq红包 浏览:412
服务器如何传输 浏览:456
如何快速将多个文件夹快速解压缩 浏览:114
程序员睡前都在想什么 浏览:37
少儿编程技能培训心得 浏览:458
白命令 浏览:816
headfirstjavapdf 浏览:552
广数980t怎么编程 浏览:592
无邪app在哪里下载 浏览:462