本篇介绍RSA的基本原理

小知识

RSA加密算法是一种非对称加密算法。

对称加密指的就是加密和解密使用同一个秘钥，所以叫对称加密。 对称加密只有一个秘钥，作为私钥。
加密：原文+密钥 = 密文
解密：密文-密钥 = 原文

非对称加密指的是加密和解密使用不同的秘钥，一把作为公开的公钥，另一把作为私钥。 公钥加密的信息，只有私钥才能解密，私钥加密的信息，只有公钥才能解密。

RSA基本原理

公钥与私钥

现寻找两个不同的大质数$p,q$。

计算乘积$n$并计算$n$的欧拉函数：

寻找一个公钥$e，1<e<phi$，而且$e$和$phi$互质，即为$gcd(e,phi)=1$

两个正整数，除了$1$以外，没有其他公因子，我们就称这两个数是互质关系。

任何两个质数构成互质。

如何寻找私钥？

这时我们可以得到私钥$d$，这个$d$被称为$e$在模$phi$上的逆元。

在python中，求解d通常使用gmpy2库的公式： d=gmpy2.invert(e,phi)

这样，我们得到公钥是$(n,e)$ 私钥是$(n,d)$

加解密原理

我们定义c为密文，有：

我们定义m为明文，有：

通常在CTF中，RSA题目就是把我们想要获得的flag表示为m，求解m以获得flag。

解密公式证明

1.如果有$gcd(m,n)=1$，根据欧拉定理：

对于同余式左边：

由①②得到$m\equiv c^d(\bmod n)$

2.如果$gcd(m,n)≠1$，由于n的因子只有p和q，所以这意味着m是p或者q的倍数，要继续证明上面的结论成立，可以想办法构造出和mn互质时一样的结论式，设：

此时一定有$gcd(m,q)=1$，否则m就是pq的倍数，出现$m>pq=n$，和加密原理模n下相矛盾。

根据欧拉定理：

我们一开始设了$m=tp$，上式左右分别乘$m$得到：

就又得到了前面探讨得到的公式，化简即可：

RSA解密

在正式开始解密RSA之前，需要先给python安装一些最基本的模块：

终端输入：

1
2
3
4
pip install gmpy2
pip install libnum
pip install pycryptodome
pip install sympy

例题：（新生平台）ezRSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
import gmpy2

flag=b"??????????????????"
m=bytes_to_long(flag)
p=getPrime(1024)
q=gmpy2.next_prime(p)
n=p*q
print(n)
e=65537
c=pow(m,e,n)
print(c)

#n=16444290765812766358045411541972043758507252774922733402779063666741231070051848803596262388656037842384774122623370953835717357292994833086138897316967231932779532066742701825253957718174353161576654267003021633880907529038587200831657439743361393893720984485872371990817328126194530198205130922860459255017808956073618574623643252666919670263828954200552572941584097493158154451750538573929515907904179521184425112562150877600561219439919175034792678805953915082105020914160484723393970487843131880235389809136552508591804757901416435646720738025971378694995189412099375969306739538017331768924489505571620698916541
#c=1284007090394457534559591594595629376699681571664262027316039076071127133553113804312097564534186553286181100295542762054904507160534115459034859529895228266518139889225143801112811652825545423485433717838183378906000090670988933570733287614474386186118182201238405665780330282651740116754494850587336498823593620498503772628476280777662952161833142843139074010273350737764004864124892855357753095590507865064342868432121011721451480068849838063160870299677163798703446178122788747518207483770828599815523899779256838027454254819374562664956652947709575838384379737444889258723770115780426248541188582596648143419009

本题属于最简单的RSA类型，先来研究一下python程序：

1
2
3
4
5
6
7
8
9
10
flag=b"??????????????????"#题目的flag内容（作为bytes显示）
m=bytes_to_long(flag)#字符串转数字，m为所求的数，最后我们求出来的m需要再转回字符串得到flag
p=getPrime(1024)#生成一个很大的质数
q=gmpy2.next_prime(p)#生成p的下一个质数，这点极为关键
#以下为基本的加密程序
n=p*q
print(n)
e=65537
c=pow(m,e,n)
print(c)

最后给的两个大数就是本题的n和c，按照题目来看，我们得到p和q就能得到结果，这里我用 yafu 来直接分解n（p和q的值相差较小，或者较大，都会造成n更容易分解的结果，pq十分接近直接用yafu分解）

1.png

接下来就可以写出一个最简单的解密程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
import gmpy2

p=128235294540203581029047676162247366128839525658441198177720129020350584213274392709067603428263076308036887962218910138038784424416187587894606769170370149162445474355193439948724930611675316254756336226495927881968020301435278378994971503843642245934159260243081588578609535490180200771930999370475784587089
q=128235294540203581029047676162247366128839525658441198177720129020350584213274392709067603428263076308036887962218910138038784424416187587894606769170370149162445474355193439948724930611675316254756336226495927881968020301435278378994971503843642245934159260243081588578609535490180200771930999370475784586669
c=1284007090394457534559591594595629376699681571664262027316039076071127133553113804312097564534186553286181100295542762054904507160534115459034859529895228266518139889225143801112811652825545423485433717838183378906000090670988933570733287614474386186118182201238405665780330282651740116754494850587336498823593620498503772628476280777662952161833142843139074010273350737764004864124892855357753095590507865064342868432121011721451480068849838063160870299677163798703446178122788747518207483770828599815523899779256838027454254819374562664956652947709575838384379737444889258723770115780426248541188582596648143419009
e=65537

n=p*q
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

在sympy库中，如果n很容易分解成p和q，我们可以直接用totient()函数直接求欧拉函数，这题就可以直接跳过求p和q的阶段，进一步简化：

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *
import gmpy2
import sympy

n=16444290765812766358045411541972043758507252774922733402779063666741231070051848803596262388656037842384774122623370953835717357292994833086138897316967231932779532066742701825253957718174353161576654267003021633880907529038587200831657439743361393893720984485872371990817328126194530198205130922860459255017808956073618574623643252666919670263828954200552572941584097493158154451750538573929515907904179521184425112562150877600561219439919175034792678805953915082105020914160484723393970487843131880235389809136552508591804757901416435646720738025971378694995189412099375969306739538017331768924489505571620698916541
c=1284007090394457534559591594595629376699681571664262027316039076071127133553113804312097564534186553286181100295542762054904507160534115459034859529895228266518139889225143801112811652825545423485433717838183378906000090670988933570733287614474386186118182201238405665780330282651740116754494850587336498823593620498503772628476280777662952161833142843139074010273350737764004864124892855357753095590507865064342868432121011721451480068849838063160870299677163798703446178122788747518207483770828599815523899779256838027454254819374562664956652947709575838384379737444889258723770115780426248541188582596648143419009
e=65537

phi=sympy.totient(n)
d=gmpy2.invert(e,int(phi))#这里公式有的时候phi会因为数据格式问题报错，加个int()就能解决
m=pow(c,d,n)
print(long_to_bytes(m))

gmpy2库函数

gmpy2.gcd( )

此函数可以直接用来求两整数的最大公因数。

1
2
import gmpy2
print(gmpy2.gcd(3,12))#3

gmpy2.invert( )

此函数可以求一个数模的逆元，例如在RSA中求d。

gmpy2.powmod( )

此函数可以求一个整数的x次幂模取余。

1
2
import gmpy2
print(gmpy2.powmod(3,3,4))#3

gmpy2.iroot( )

此函数可以求一个数开n次方。

1
2
import gmpy2
print(gmpy2.iroot(8,3))#(mpz(2),true)

gmpy2.is_even/odd/prime( )

可以判断一个数是否为偶数（even）或者奇数（odd）或者质数（prime）。

1
2
3
4
import gmpy2
print(gmpy2.is_prime(13))#true
print(gmpy2.is_odd(13))#true
print(gmpy2.is_even(13))#false

gmpy2.gcdext(e1,e2)

拓展欧几里得算法：

1
2
3
4
5
import gmpy2
e1=11187289
e2=9647291
s,s1,s2=gmpy2.gcdext(e1,e2)#返回三个mpz整数，gcd,s1,s2
print(s1,s2)#-3421980 3968231

libnum库函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import libnum
#生成素数
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
#字节、数字转换
flag="flag"
a=libnum.s2n(flag)
b=libnum.n2s(a)
print(a)
print(b)
#二进制、数字转换
flag="flag"
a=libnum.s2b(flag)
b=libnum.b2s(a)
#求逆元
libnum.invmod(e,phi)
#求最大公约数
libnum.gcd(a,b)
#求最小公倍数
libnum.lcm(a,b)
#开方
libnum.nroot(a,b)
#中国剩余定理
libnum.solve_crt()
#扩展欧几里得算法
libnum.xgcd(a,b)

欧几里得算法

欧几里得算法（辗转相除法求最大公约数）：用除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数。

例：求1997 和 615 两个正整数的最大公约数：
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此，得到最大公约数为1。

在RSA中，我们有的时候会遇到多对公钥n共用同一个因子q（此时q为公约数），可以尝试使用公约数分解直接获得q的值：

1
2
3
4
5
6
p1=getPrime(256)
p2=getPrime(256)
q=getPrime(256)
#n1和n2共用q作为因子
n1=p1*q
n2=p2*q

在 python 中使用辗转相除法，我们可以定义函数：

1
2
3
4
5
6
7
def gcd(a,b):
    if a<b:#我们让a为除数，b为被除数，让a＞b
        a,b=b,a
    while b!=0:
        c=a%b
        a,b=b,c#上一个式子的被除数是下一个的除数，让余数作为下一个式子的被除数，如果余数为0直接输出a
    return a

快速幂算法

在RSA的计算中，经常需要用到一个大整数的整数次幂后取模的操作，如果只是按照数学方式进行计算，中间结果会非常大，可以对其算法进行优化，根据模运算性质：

考虑提高指数运算效率，可以采用以下方式：

为了求$a^m$（$a,m$为正整数），先把m表示为二进制形式$b_kb_{k-1}…b_0$，可以用二进制形式表示原式：

所以，对于$a^m$，有：

例如19的2进制为10011，可得：

以下是两种快速幂运算的代码，两种运算的顺序不一样，但是结果是相同的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def qpow(a, b, m):
    base = a
    exponent = b
    result = 1
    while exponent > 0:
        if exponent & 1:
            result = result * base % m
        base = base * base % m
        exponent >>= 1
    return result

def bpow(a, b, m):
    base = a
    bb=bin(b)[2:]
    for i in range(1,len(bb)):
        if bb[i]=='1':
            base = base * base * a % m
        else:
            base = base * base % m
    return base


print(qpow(7, 560, 561))
print(bpow(7, 560, 561))