密码学——RSA算法

一、对称加密and非对称加密

对称加密是密码学中的一类加密算法。这类算法在加密和解密时使用相同的密钥,或是使用两个可以简单地相互推算的密钥。实务上,这组密钥成为在两个或多个成员间的共同秘密,以便维持专属的通讯联系。与公开密钥加密相比,要求双方取得相同的密钥是对称密钥加密的主要缺点之一。
非对称加密,一种密码学算法类型,在这种密码学方法中,需要一对密钥(其实这里密钥说法不好,就是“钥”),一个是私人密钥,另一个则是公开密钥。这两个密钥是数学相关,用某用户密钥加密后所得的信息,只能用该用户的解密密钥才能解密。如果知道了其中一个,并不能计算出另外一个。因此如果公开了一对密钥中的一个,并不会危害到另外一个的秘密性质。称公开的密钥为公钥;不公开的密钥为私钥。

二、RSA简介

RSA算法是非对称加密算法,这种算法非常可靠,密钥越长,它就越难破解(本质上是对大数的质因数分解很难)。根据已经披露的文献,目前被破解的最长RSA密钥是768个二进制位。也就是说,长度超过768位的密钥,还无法破解(至少没人公开宣布)。因此可以认为,1024位的RSA密钥基本安全,2048位的密钥极其安全。

三、相关数学概念

1.素数

素数又称质数,指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数。 如:2,3,5,7,11,13…

2.互素

互质,又称互素。若N个整数的最大公因子是1,则称这N个整数互质。

3.欧拉函数

欧拉函数 φ(n)是小于或等于n的正整数中与n互质的数的数目 如果n = 1, φ(1) = 1;(小于等于1的正整数中唯一和1互质的数就是1本身); 如果n为质数,φ(n) = n - 1;因为质数和每一个比它小的数字都互质。比如5,比它小的正整数1,2,3,4都和他互质; 若m,n互质,则φ(mn) = φ(m)φ(n)

4.模运算

模运算即求余运算。“模”是“Mod”的音译。和模运算紧密相关的一个概念是“同余”。数学上,当两个整数除以同一个正整数,若得相同余数,则二整数同余。
两个整数a,b,若它们除以正整数m所得的余数相等,则称a,b对于模m同余,记作: a ≡ b (mod m);读作:a同余于b模m,或者,a与b关于模m同余。例如:26 ≡ 14 (mod 12)。

5.模逆元(模反元素)

一整数a对同余n之模逆元是指满足以下公式的整数b:
ab ≡ 1 (mod n)
整数 a 对模数 n 之模逆元存在的充分必要条件是 a 和 n 互素。

6.欧拉定理

如果两个正整数a和n互质,则n的欧拉函数 φ(n) 可以让下面的等式成立:
a^φ(n) ≡ 1(mod n)
根据这个定理以及模逆元的概念,可得a的φ(n)-1次方肯定是a关于n的模反元素。
所以a关于n的模反元素必然存在。 比如,3和5互质,而5的欧拉函数φ(5)等于4,所以3的4次方*(81)减去1,可以被5整除(80/5=16)。

四、算法过程

1.公钥与密钥的产生

假设A想要通过一个不可靠的媒体接收B的一条私人讯息。她可以用以下的方式来产生一个公钥和一个私钥:
获取N: 随意选择两个大的质数p和q,p不等于q,计算N=pq;
获取r: 根据欧拉函数r = φ(N) = φ(p)φ(q) = (p-1)(q-1);
选择一个小于 r 的整数 e,求得 e 关于模 r 的模反元素,命名为d。(模反元素存在,当且仅当e与r互质,即求 e^(φ(r)-1) )。
(N,e)是公钥,(N,d)是私钥。A将她的公钥(N,e)传给B,私钥(N,d)自己保存。

2.加密消息

假设B想给A送一个消息message,他知道A产生的公钥(N,e)。 于是B先将message转换为一个小于N的整数m。(如果是字符串可以取ascii值或unicode值;假如信息非常长,可以将分为几段,然后将每一段转换为m) 用下面这个公式他可以将m加密为c:
m^e ≡ c (mod N)
B算出c后就可以将它传递给A。

3.解密消息

A得到B的消息c后就可以利用她的密钥(N, d)来解码。她可以用以下这个公式来将c转换为m:
c^d ≡ m (mod N)
得到m后,她就可以将原来的信息message重新复原。

4.安全性

即使是在用户已经获取到公钥(N, e)的情况下,需要解开密文需要哪些步骤:
如果想知道 d 需要知道欧拉函数 φ(n)的结果(即上文中提到的r = φ(N));
如果想知道欧拉函数 φ(n) 需要知道 p 和 q;
要知道 p 和 q 需要对 N 进行质因数分解。

五、RSA相关练习


题目提示RSA,求出私钥即可:
φ(N)=φ( p )φ( q )=(p-1)(q-1)
ed ≡ 1 (mod φ(N))

所以ed=φ(N)+1,即17d=(p-1)(q-1)+1=473398607160*4511490+1

计算机拿出来,计算一下即可:


  Reprint please specify: clam 密码学——RSA算法

 Previous
实验吧——密码学(二) 实验吧——密码学(二)
1.变异凯撒拿到题目,对比格式和密文发现对应的前5个字符ASCII是有规律的,依次是97+5,102+6,90+7,95+8,114+9,按此规律将密文所有的ASCII码转换,就是答案: 2.传统知识+古典密码 从题目可以知道是 “干支数
2019-09-01 yxld
Next 
SQLI-LABS(Basic Challenges 1-10) SQLI-LABS(Basic Challenges 1-10)
最近学习一下sql注入,领教一下Sqli-labs的魅力。Sqli-labs下载 Less-1GET-Error based-Single quotes-String(基于错误的GET单引号字符型注入)打开界面:尝试?id=1:闭合符号一般
2019-08-02 yxld
  TOC