RSA加密解密原理

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


RSA算法简介:

  • RSA加密算法是一种 非对称加密 算法,RSA算法相比别的算法思路非常清晰,但是想要破解的难度非常大。

    • RSA算法基于一个非常简单的数论事实:两个素数相乘得到一个大数很容易,但是由一个大数分解为两个素数相乘却非常难。

1、什么是非对称加密算法:

  • 对称加密 算法使用同一个密钥进行加密解密的方式不同,非对称加密 算法是使用不同密钥进行加密和解密的算法,也称为公私钥加密。

非对称加密算法实现机密信息交换的基本过程:

  • 甲方生成 一对密钥 并将其中的一把作为 公钥 向其它方公开,得到该公钥的乙方使用该密钥对机密信息进行加密后再发送给甲方,甲方再用自己保存的另一把 私钥 对加密后的信息进行解密。

图解:

2、RSA 加密原理:

了解了非对称加密算法的原理,我们再来说说 RSA 加密算法的基本流程。

如图:

3、RSA加密算法过程详解:

先来了解一下什么是 互质数:

  • 两个或多个整数的公因数只有1的非0自然数,则两个非0自然数叫做互质数。例如 2 和 3,公因数只有1,所以为互质数。
1、找出质数 :

随机找两个质数 p 和 q ,p 与 q 越大,越安全。

2、计算公共模数:
 n = p * q 

假设 p = 65 ,q = 71。计算他们的乘积 n = p * q = 4615 ,转化为二进制为 1001000000111,即该加密算法即为 13 位。位数越长,算法则越难被破解。实际应用中,RSA密钥一般是1024位,重要场合则为2048位。

3、计算欧拉函数 φ(n):
φ(n) = φ(p*q) = (p-1)(q-1)

φ(n) 表示:在小于等于 n 的正整数之中,与 n 构成互质关系的数的个数。

例:

在 1 到 8 之中,与 8 形成互质关系的是1、3、5、7,所以 φ(n) = 4。

计算公式(即欧拉函数)为

前提:P 与 Q 均为质数

φ(n) = φ(P*Q)= (P-1)(Q-1) 

设:

P = 65 ,Q = 71

φ(n) = 64 * 70 = 4480 

即有4480 个数与 n(4615)互质。

4、计算公钥 e:
1 < e < φ(n)

要求:

  • e 的取值必须是整数
  • e 和 φ(n) 必须是互质数
5、计算私钥 d:

计算公式:

e * d % m = 1  其中(φ(n) = m)

即找一个整数 d,使得 (e * d ) % m = 1,等价于 e * d - 1 = y * m ( y 为整数)

得到 d ,实质就是对下面二元一次方程求解:

e * x - m * y = 1 e,m为已知量,求 x,y。

这个方程可以用 扩展欧几里得算法 求解,此处就不详细介绍了,可以看这个了解下: 扩展欧几里得算法

得到:

  • 公钥=(e,n)

  • 私钥=(d,n)

对外,只暴露公钥。

6、加密生成密文:

C = $M^e$ mod n

C:密文 M:明文

7、解密生成明文:

M =$C^d$ mod n

C:密文 M:明文


下面举一个完整的例子

4、示例:

1、找出质数 p 、q :

p = 3  
q = 11

2、计算公共模数 n:

n = p * q = 3 * 11 = 33
n = 33

3、计算欧拉函数 φ(n):

φ(n) = (p-1)(q-1) = 2 * 10 = 20
φ(n) = 20

4、计算公钥 e:

1 < e < φ(n)
1 < e < 20

e 的取值范围为: { 3, 7, 9, 11, 13, 17, 19 }

为了方便测试,我们取最小的值 e =3,3 和 φ(n) = 20 互为质数,满足条件。

5、计算私钥 d:

e * d % φ(n) = 1
3 * d % 20 = 1   

计算出 d = 7

6、公钥加密:

公式:C = $M^e$ mod n

随便拿一个数字,这里方便演示 取 M = 2

C = $3^3$ % 33 = 8

“ M = 3 “ 经过RSA加密后变成了 “ C = 8 “

7、私钥解密:

M =$C^d$ mod n

C = 8
d = 7
n = 33

计算:

M = $8^7$ % 33

解得: M = 2


🆗,简单了解 RSA的基本原理之后,来看几个CTF中的RSA例题。

5、例题:

1、easy_RSA:


打开附件:

这题很简单,就是求参数d 的值,那么如何计算d 呢?也就是如何求 e * x - m * y =1 式子中的 x ?

步骤:

1、先计算欧拉函数:

得到 φ(n) = 2135733082216268400

2、求 d:

根据加密原理,解密的方法就是:把欧拉函数的值 +1,再除以17 * n(这里 n 先取1)

得到 d = 125631357777427553,尝试提交flag: cyberpeace{125631357777427553} 正确,看来 n 的值确实为 1 。( ̄▽ ̄)”

提供一个求私钥脚本:

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

p = 473398607161
q = 4511491
e = 17

m = (p-1)*(q-1)
d = int(gmpy2.invert(e,m)) //invert: 求逆元,返回值是一个 mpz 对象
print('私钥为:',d)

运行结果(我的python出了点小问题):

得到 d = 125631357777427553

2、i春秋 RSA :


打开附件:

可以看到题目给出了 n,e,c 三个值 ,求明文的值。

首先先对 n 进行因式分解,使用在线网站:大数分解网站

得到 p ,q :

p = 310935513029228809998830208036655366162721470228774287453148308675193510132489142448801010943658159980501154153084396100667001391643762749806500051502679498536716532334917842894939889468693960937309663256592497965458780801192062835123429808
544757340971089756707788360038227894054989413747980167536893779923551227744017809301855984582408943622461942486239113822841696775958645014753081946441406022729616992302829930205076689399802050792392219242304302303180769915076199603301447453
07022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928797450473
q = 310935513029228809998830208036655366162721470228774287453148308675193510132489142448801010943658159980501154153084396100667001391643762749806500051502679498536716532334917842894939889468693960937309663256592497965458780801192062835123429808
544757340971089756707788360038227894054989413747980167536893779923551227744017809301855984582408943622461942486239113822841696775958645014753081946441406022729616992302829930205076689399802050792392219242304302303180769915076199603301447453
07022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928997877221

2、相关参数都已得到,就可以编写脚本求明文信息了:

#!/usr/bin/env python
# coding:utf-8
import gmpy2   

p = gmpy2.mpz(31093551302922880999883020803665536616272147022877428745314830867519351013248914244880101094365815998050115415308439610066700139164376274980650005150267949853671653233491784289493988946869396093730966325659249796545878080119206283512342980854475734097108975670778836003822789405498941374798016753689377992355122774401780930185598458240894362246194248623911382284169677595864501475308194644140602272961699230282993020507668939980205079239221924230430230318076991507619960330144745307022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928997877221)
q = gmpy2.mpz(31093551302922880999883020803665536616272147022877428745314830867519351013248914244880101094365815998050115415308439610066700139164376274980650005150267949853671653233491784289493988946869396093730966325659249796545878080119206283512342980854475734097108975670778836003822789405498941374798016753689377992355122774401780930185598458240894362246194248623911382284169677595864501475308194644140602272961699230282993020507668939980205079239221924230430230318076991507619960330144745307022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928797450473)
e = gmpy2.mpz(65537)

#计算私钥d
m = (p - 1) * (q - 1)
d = gmpy2.invert(e, m)
print "private key:",d

#求密文M
c = gmpy2.mpz(168502910088858295634315070244377409556567637139736308082186369003227771936407321783557795624279162162305200436446903976385948677897665466290852769877562167487142385308027341639816401055081820497002018908896202860342391029082581621987305533097386652183849657065952062433988387640990383623264405525144003500286531262674315900537001845043225363148359766771033899680111076181672797077410584747509581932045540801777738548872747597899965366950827505529432483779821158152928899947837196391555666165486441878183288008753561108995715961920472927844877569855940505148843530998878113722830427807926679324241141182238903567682042410145345551889442158895157875798990903715105782682083886461661307063583447696168828687126956147955886493383805513557604179029050981678755054945607866353195793654108403939242723861651919152369923904002966873994811826391080318146260416978499377182540684409790357257490816203138499369634490897553227763563553981246891677613446390134477832143175248992161641698011195968792105201847976082322786623390242470226740685822218140263182024226228692159380557661591633072091945077334191987860262448385123599459647228562137369178069072804498049463136233856337817385977990145571042231795332995523988174895432819872832170029690848)
print "明文:"
M  =  pow(c,d,p*q)
print '10进制: '+str(M)
flag = str(hex(M))[2:]# 从第3位为往后截取
print '16进制: '+flag
print 'ASCII码: '+flag.decode('hex')

注释:

  • gmpy2.mpz(x): 初始化一个大整数x
  • pow( x, y, z): 计算 $x^y$ mod z

得到 flag:

🆗,关与RSA的总结暂时就到这里了,以后发现好用的方法或解题技巧会接着更新。╰( ̄ω ̄o)


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

×

喜欢就点赞,疼爱就打赏