这篇文章是帮助对RSA不熟悉的朋友且需要较为快速、深入的了解RSA而写的

不涉及非常晦涩难懂的数学知识和算法(不过最简单的原理说明还是有的)

攻击方法也是最容易遇到的(RSA的进阶篇除外)

并且所有的例题都是比较新的,甚至还有刚刚结束的比赛的题目

公钥与私钥的产生：

(1)进行加密之前，首先找出2个不同的大质数p和q

(2)计算n=p*q

(3)根据欧拉函数，求得φ(n)=φ(p)φ(q)=(p−1)(q−1)

(4)找出一个公钥e，e要满足: 1<e<φ(n) 的整数，且使e和φ(N)互质。

(5)根据e*d除以φ(n)余数为1，找到私钥d。

(6)所以,公钥就是(n,e) 私钥就是(n,d)

消息加密:

m^e除以n求余数即为c(密文)

消息解密:

c^d除以n求余数即为m(明文)

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

模运算与基本四则运算有些相似，但是除法例外。其规则如下:

在数论，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目（因此φ(1)=1）

例如φ(8)= 4，因为1,3,5,7均和8互质

若N是质数p的k次幂(即N=p^k)，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)。

设n为正整数，以φ(n)表示不超过n且与n互素的正整数的个数，称为n的欧拉函数值。

若m,n互质，φ(mn)=(m-1)(n-1)=φ(m)φ(n)。

在一次RSA密钥对生成中，假设p=473398607161，q=4511491，e=17
求解出d作为flag提交

题目:

解题:

倒数第二行的gmpy2.powmod也可以用pow函数替代,不过前者比后者的计算速度快很多,之后有道题可以体现出来

自此,我们已经了解了rsa的原理,现在开始进入学习rsa的一些攻击方式

用于已知e,c,m,不是很大的n(小于等于1024),或者n具有缺陷,q和p相差过大或过小

常用分解方法:

如果第一项,和第二项都无法分解,就应该考虑换一种思路了,题目考点应该不是暴力分解

已知一段RSA加密的信息为：0xdc2eeeb2782c且已知加密所用的公钥：

(N=322831561921859 e = 23)

请解密出明文，提交时请将数字转化为ascii码提交

比如你解出的明文是0x6162，那么请提交字符串ab

提交格式:PCTF{明文字符串}

首先整理一下已知条件:

我们已知公钥:

n和e,以及密文c

想要通过密文c来解得明文m需要私钥d

而私钥d需要通过e和phi求出,其中e已知,所以我们只需要知道phi

而phi = (q-1) * (p-1),幸运的是我们知道n = q*p,且q和p都是素数,如果我们能通过n分解出p和q则可以解出这道题目了

得到p = 13574881 , q = 23781539(q和p不涉及其他关系时,p和q的顺序无所谓)

可以从这两句代码看出:

可以知道,q和p相差很小,所以这个n是具有缺陷的,通常有两种攻击方式

分解出来后,是一个简单是数学等式,用z3约束器可以快速求解

(使用yafu分解的攻击方法比较简单,这里就不写了)

openssl genrsa -out prikey

openssl rsa -in prikey -text -modulus

openssl rsa -in prikey -pubout -out pubkey

openssl rsa -in pubkey -text -modulus -pubin

openssl rsautl -encrypt -in filename -inkey pubkey -pubin -out filename

rsautl -decrypt -inkey prikey -in filename

RsaCtfTool.py --createpub -n number -e number > pubkey

RsaCtfTool.py --dumpkey --filename pub.pem

RsaCtfTool.py --publickey pubkey --private

RsaCtfTool.py --publickey pubkey --uncipherfile filename

给了两个文件,message 和 public.key

以及加密脚本

首先打开公钥看看

可以看到e和n非常大,应该考虑Wiener攻击(后面会介绍到)

不过这里主要是介绍和公钥、私钥的交互

所以我们用RsaCtfTool来爆破出私钥

得到了私钥,尝试用openssl解密

却报错了,为什么呢

我们观察题目给出的加密脚本第二行"from Crypto.Cipher import PKCS1_OAEP"

说明这里是用的使用OAEP的填充方式,而解密是也必须指明对应的填充模式

这类题核心解法大体相同,出题人给出有唯一解的q和p的方程,通过解出q,p来解题

大多数简单的数学方程可以用z3约束器快速解出

这道题挺有意思的,在给出的脚本第10行

有两个没见过的函数,通过搜索资料,可以查到相关资料

Derivative，返回参数1函数在参数2点的导数

联系这两点

可以知道

z = Fraction(1,Derivative(arctan(p),p))-Fraction(1,Derivative(arth(q),q))

= 1/(1/(1+p^2)) - 1/(1/(1-q^2))

= 1+p^2 + q^2 -1

= p^2 + q^2

又把本题转化成简单的数学问题了

在 RSA 中 e 也称为加密指数。由于 e 是可以随意选取的，选取小一点的 e 可以缩短加密时间（比如 e=2,e=3），但是选取不当的话，就会造成安全问题

由于e很小,当n很大时,m^e也比n小很多.尝试把c开根号看能否得到明文.

题目描述:

When you need really secure communications, you use RSA with a 4096 bit key.

I want really really really secure communications to transmit the nuclear launch codes (yeah IoT is everywhere man) so I used RSA with a 16777216 bit key. Surely russians will not be able to factor that one !

File md5 : 1049a0c83a2e34760363b4ad9778753f

题目给出了n和c,e,不过这个文本文件的大小高达7.4m,要是常规分解的话,估计量子计算机也够呛

不过由于n是16777216 bit的数字,e只有0x10001,所以m^e << n,符合低加密指数分解攻击的条件

这里我们也应该理解到,低加密指数并非指e == 2或e == 3这类,e的数值很小,而是m^e和n的相对大小

公钥e很小，明文m也不大的话，于是m^e=k*n+m 中的的k值很小甚至为0(k==0时,和上一种攻击方式差别不大)，爆破k或直接开e次方即可。

我们拿到两个类似rsa加密的式子:

本质上,第一种、第二种攻击方式都是因为e选取的较小而造成的缺陷,那么e选取的非常大是不是就很安全呢？

实际上也不是,当e很大时,就会造成d非常的小,也具有相当大的危险

顾名思义,这是一种针对d很小时的攻击方式

此种攻击方法由Micheal j.Wiener于1989提出,所以也被称为Wiener's attack,该方法基于连分数

该方法在github已有完整可用的代码,之后所有的低解密指数也是利用以上脚本进行的

把大数分解成两个素数很困难,但是求两个大数的公因子很容易

当:

我们可以通过求gcd(n1,n2)来得到a,再通过除法分别求得b和c,从而达到了分解大素数的目的

可以通过gcd(n1,n2)快速求得p1

对同一明文的多次加密使用相同的模数和不同的公钥指数可能导致共模攻击

证明:

当n不变，知道n,e1,e2,c1,c2 可以在不知道d1,d2情况下，解出m。

这道题解出来后是base64加密后的字符串,实际上没有看上去那么简单,这里涉及到base64隐写,不过不是本文的主题,先暂且不管

对于相同的明文,使用相同的指数e和不同的模数n1,n2...ni加密得到i组密文(i>=e),可以使用中国剩余定理解出明文

当已知e,n,可以通过算法快速求得p和q

详细算法见:

https://www.di-mgt.com.au/rsa_factorize_n.html

可以看到,这里的p和q都高达1024bit,基本可以排除暴力分解

这时我们知道e*d,和n,可以尝试已知该算法

rsa加密基本原理

需要严格按照欧拉函数的定义来求解phi

n = p * q * r

那么φ(n) = (q-1) * (p-1) * (r-1)

dp本来是为了加速rsa加解密效率的,不过由于dp和p的关系相当密切,所以当dp泄漏也有相当大的危害

题目给出了密文文件,公钥和破损的私钥文件(这里就不放上来了)

首先读出公钥信息和破损的私钥信息填入以下脚本即可恢复出完整的私钥

解出私钥后,写入到文件中,用openssl解密即可(不过需要注意的是这依然是用oaep的填充方式,需要指明)

这道题e的大致范围已经给出,可以尝试爆破

不过加密脚本的第一行有点坑

(应该是出题人故意)把人误导成base32解密

也是对e爆破,不过我们可以通过这道题来对比pow()函数和gmpy2.powmod()的速度
pow:

3.03s user 0.01s system 99% cpu 3.050 total

gmpy2.powmod

1.30s user 0.00s system 99% cpu 1.310 total

可以看到,gmpy2中的powmod()函数用时不到pow()函数的二分之一,所以以后优先使用gmpy2.powmod()函数

题目给出了A和p,q的关系,一通花里胡哨的运算之后得到A

以我已知的知识想不到什么好的算法

不过可以直接分解n得到p和q

当我们做完这些后,发现题目并没有告知e,盲猜e = 65537,结果正好是

当然平时做题我们还是严谨一点,尝试爆破e

NIST SP800-78 Rev 1 (2007) 曾强调“不允许使用比65537更低的公钥指数e”，但PKCS#1却从未有过类似的建议。e=65537=(2^16+1)，其签名/加密运算只需要17次模乘，性能也算不错。65537可以在安全上和性能上做出一个很好的平衡,因此大多数加密的e都默认为65537

可以优先尝试e == 65537,不行再爆破

已知n = q

gift = lcm(q-1,p-1)
= (q-1)*(p-1) // gcd(q-1,p-1)

又因为(q-1)*(p-1) 约等于 q*p = n

gift 约等于 n // gcd(q-1,p-1)

于是可以得出gcd(q-1,p-1) 约等于 n // gift

于是得出gcd(q-1,p-1)约等于8

设k = gcd(q-1,p-1) ( k 约等于8,于是爆破k的取值范围为0<k<10)

最后得到q,p,e,又由于gcd(e,phi) != 1

于是:
new_e = e//2
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)
m = gmpy2.iroot(m,2)[0]
m = long_to_bytes(m)

可以求出明文

本题过程大致可以分为三部分:

解得e1和e3

解得hint和q1

解得flag

通过这两句断言:

可以建立两个方程,由于两个e都很小,考虑低加密指数攻击:

解的e1,e2

一个常规的rsa加密,没有明显的缺陷,尝试分解n

得到两个质数

常规的分解

得到完全没用的hint,但是得到了对第三步很有用的q1

乍一看似乎很简单,连n都已经分解好了(这让我想起了NCTF的easyRSA)

一测试,果然gcd(e1,phi1) == gcd(e2,phi2) == 14

既然到这里了,就总结一下e和phi不互素时的解法(下次)

从密文形式可以看出是用的python编写的加密脚本,不过这个脚本又被再次加密,猜想应该是纺射加密,从中挑选了两端话来对比得出a和b

得出a = 3, b = 17

纺射解密后得到加密脚本,如下

进入了rsa解题过程,我们先看最后一个加密,相同的明文,相同的n,不同的e

用共模攻击解出n1来

对于倒数第二段加密,通过这两句代码

解出两组明文,最后通过栅栏解密得到flag

[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)