密码学—RSA加密解密详解

  1. RSA算法:
  2. 公钥和私钥的生成:
  3. 加密生成密文 :
  4. 解密生成明文:

引言
CTF密码学类题目中,RSA加密可谓是很重要且常见的加密类型,今天就总结下RSA加密的原理及解密方法。

RSA算法:

  • RSA加密算法是一种非对称加密算法,RSA算法相比别的算法思路非常清晰,但是想要破解的难度非常大。
  • RSA算法基于一个非常简单的数论事实:两个素数相乘得到一个大数很容易,但是由一个大数分解为两个素数相乘却非常难。
    在这里插入图片描述

公钥和私钥的生成:

第一步:随机找两个质数 P 和 Q ,P 与 Q 越大,越安全

比如 P = 67 ,Q = 71。计算他们的乘积 n = P * Q = 4757 ,转化为二进为1001010010101,该加密算法即为 13 位,实际算法是 1024 位 或 2048 位,位数越长,算法越难被破解。

第二步:计算 n 的欧拉函数 φ(n)

φ(n) 表示在小于等于 n 的正整数之中,与 n 构成互质关系的数的个数。例如:在 1 到 8 之中,与 8 形成互质关系的是1、3、5、7,所以 φ(n) = 4。 如果 n = P * Q,P 与 Q 均为质数,则 φ(n) = φ(P * Q)= φ(P - 1)φ(Q - 1) = (P - 1)(Q - 1) 。 本例中 φ(n) = 66 * 70 = 4620,这里记为 m, m = φ(n) = 4620

第三步:随机选择一个整数 e,条件是1< e < m,且 e 与 m 互质

公约数只有 1 的两个整数,叫做互质整数,这里我们随机选择 e = 101 请注意不要选择 4619,如果选这个,则公钥和私钥将变得相同。

*第四步:有一个整数 d,可以使得 ed 除以 m 的余数为 1**

即找一个整数 d,使得 (e * d ) % m = 1。 等价于e * d - 1 = y * m ( y 为整数) 找到 d ,实质就是对下面二元一次方程求解。 e * x - m * y =1 ,其中 e = 101,m = 4620; 101x - 4620y =1 这个方程可以用扩展欧几里得算法求解,此处省略具体过程。
总之算出一组整数解 (x,y )= ( 1601,35),即 d = 1601。 到此密钥对生成完毕。不同的 e 生成不同的 d,因此可以生成多个密钥对。 本例中公钥为 (n,e) = (4757 , 101),私钥为 (n,d) = (4757 ,1601) ,仅 (n,e) = (4757 , 101) 是公开的,其余数字均不公开。可以想像如果只有 n 和 e,如何推导出 d,目前只能靠暴力破解,位数越长,暴力破解的时间越长。

加密生成密文 :

比如甲向乙发送汉字“中”,就要使用乙的公钥加密汉字 “中”, 以 utf-8 方式编码为 [e4 b8 ad],转为 10 进制为 [228,184,173]。要想使用公钥(n,e) = (4757 , 101)加密,要求被加密的数字必须小于 n,被加密的数字必须是整数,字符串可以取 ascii 值或unicode值,因此将“中”字折为三个字节 [228,184,173],分别对三个字节加密。

假设 a 为明文,b 为密文,则按下列公式计算出 b

a^e % n = b 

计算 [228,184,173]的密文:

228^101 % 4757 = 4296
184^101 % 4757 = 2458
173^101 % 4757 = 3263

即 [228,184,173]加密后得到密文 [4296,2458,3263] ,如果没有私钥 d ,神仙也无法从 [4296,2458,3263]中恢复 [228,184,173]。

解密生成明文:

乙收到密文 [4296,2458,3263],并用自己的私钥(n,d) = (4757 ,1601) 解密。解密公式如下:
假设 a 为明文,b 为密文,则按下列公式计算出 a

a^d % n = b 

密文 [4296,2458,3263] 的明文如下:

4296^1601% 4757 = 228
2458^1601% 4757 = 184
3263^1601% 4757 = 173

即密文 [4296,2458,3263] 解密后得到 [228,184,173]
将[228,184,173] 再按 utf-8 解码为汉字 “中”,至此解密完毕。

参考blog https://www.jianshu.com/p/fbb8bf7baa97

现在知道了加密解密的基本原理,下面就做几个题展示下。


1.easy_RSA

在这里插入图片描述
打开附件:
在这里插入图片描述
这题很简单,就是求参数d的值
那么如何计算d呢?也就是如何求e * x - m * y =1 式子中的x的值,这个时候就需要了解以下扩展欧几里得算法了,扩展欧几里得算法详解看完应该了解了计算的原理
这里分享一个脚本(需要安装gmpy2):

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

import gmpy2

p = 473398607161
q = 4511491
e = 17

s = (p-1)*(q-1)
d = gmpy2.invert(e,s)
print('flag is :',d)

得到d=125631357777427553 flag为cyberpeace{125631357777427553}
好,关于RSA的加密解密原理,就先总结到这吧,以后发现好用的方法或解题技巧会接着更新。


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 2058751973@qq.com

×

喜欢就点赞,疼爱就打赏