【ctf密码】RAS那些事

​ RSA作为一种非常经典的非对称公开密钥加密体制，属于是CTF密码学题目中的常客。对刚接触密码学的新手来说，一上来看到各种几百上千位的数字难免感到头大，但实际上了解了RSA的原理和常见解题技巧后也没有那么复杂，常规的RSA题目我觉得算是密码学中比较好拿分的部分了。

一、RSA算法概述

概述

RSA是一种非对称加密体制 ，所谓非对称就是加密钥和解密钥不一样，要解决加解密相关问题，我们首先要弄清楚RSA加密解密流程中用到了哪些东西：

明文 m 就是待加密的文本啦，一般也就是我们的flag。
密文C 加密完成后的密文，一般题目会给你，我们要做的就是根据密文解密出明文
公钥 e（加密钥） 用来加密的密钥，是一个整数，是公开
两个大素数 p,q RSA加密的关键部分，一般不会告诉你。我们选取两个大素数并计算它们的乘积，得到n=p*q。**后面会用p,q,n来加密解密。由于p,q非常大，想要对n进行因式分解得到p，q非常困难，这也确保了RSA的安全性
私钥 d（解密钥） 用来解密，一般不会告诉你，d满足e*d mod (p-1)(q-1)=1，所以我们只要知道e和p,q就可以把d算出来。

解密过程：

以上就是一个常规RSA算法的组成部分。通过上面的内容我们可以知道要想解密一段密文，我们需要c,d,n三个值。其中c我们是知道的，而n和d都可以通过p,q,e算出来，e我们一般也是知道的，也就是说常规的rsa题目我们的解题思路就是想想怎样把p和q求出来。并以此进行解密。

公钥 （E，N）
私钥 （D，N）
密钥对 （E，D，N）
加密 密文＝明文^E mod N
解密 明文＝密文^D mod N

脚本公式

常规计算:

已知道p、q 、e 、c 、n 计算明文M

1
2
3
4
5
6
7
8
9
p =
q =
e =
c =
n =
s = (p-1)*(q-1)
d=gmpy2.invert(e,s)
m=pow(c,d,n)
print(str(m))

已知dp 、dq

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
27
28
29
import gmpy2

# 假设已经有的变量（在RSA解密上下文中）
p = ...  # 一个大素数
q = ...  # 另一个大素数
dp = ...  # d mod (p-1) 的结果
dq = ...  # d mod (q-1) 的结果
c = ...  # 密文

# 使用pow函数和CRT进行解密
I = gmpy2.invert(q, p)  # q关于p的模逆元
mp = pow(c, dp, p)  # 在模p下计算c的dp次方
mq = pow(c, dq, q)  # 在模q下计算c的dq次方

# 使用CRT恢复明文m
h = (mp - mq) * I % p  # 计算h
m = h * q + mq  # 使用h和mq恢复m

# 打印明文（假设m是一个整数，并且我们想要以十六进制形式打印它）
print(hex(m))

import gmpy2
I = gmpy2.invert(q,p)
mp = pow(c,dp,p)
mq = pow(c,dq,q)               #求幂取模运算

m = (((mp-mq)*I)%p)*q+mq       #求明文公式

print(hex(m))          #转为十六进制

已经知另一半dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# dp = ... # 私钥的一部分，通常是d mod (p-1) 已知dp
import gmpy2
from Crypto.Util.number import long_to_bytes
e = 
n = 
dp =
c = 
# 假设这些变量已经被定义并正确初始化
# e = ... # 公钥指数
# n = ... # 模数，两个大质数p和q的乘积
# c = ... # 密文
# dp = ... # 私钥的一部分，通常是d mod (p-1)

for i in range(1, e):
    if (dp * e - 1) % i == 0:
        if n % (((dp * e - 1) // i) + 1) == 0:
            p = ((dp * e - 1) // i) + 1
            q = n // (((dp * e - 1) // i) + 1)
            d = gmpy2.invert(e, (p - 1) * (q - 1))
            m = pow(c, d, n)

print(m)
print(long_to_bytes(m))

二、案例分析

BUUCTF-RSA

打开附件发现:

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

给出p``q e 计算d 代入公式:

1
2
3
4
5
6
7
8
9
10
11
# 已知 p ，q，e   求 d
import gmpy2
p=473398607161
q=4511491
e=17

s = (p-1)*(q-1)
d = gmpy2.invert(e,s)
print("dec:"+str(d))
print("hex:"+hex(d))

BUUCTF-Rsarsa

已知p ，q，e ,c、d 求 未知n、d 求M

用工具RAS-tool 工具计算 d、n 值

加解密工具RSATool的使用-CSDN博客

1
2
3
n=114573516752272714750064227635008832737477859608443481000717283425702025029279291376859256856603741797722497252841363753834114679306784379319341824813349417007577541466886971550474580368413974382926969910999462429631003527365143148445405716553105750338796691010126879918594076915709977585368841428779903869581

d=566320475711906605675203410288611948624114284168625070347625872299951386056498369602206199034563927521159432993353851632162337446246238488742353033096363934467363472386277930227252609864669579747530041292106804014323774449841951450098019673911966155

脚本：

1
2
3
4
5
6
7
8
9
10
import gmpy2
p =9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q =11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e =65537
c =83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
n =114573516752272714750064227635008832737477859608443481000717283425702025029279291376859256856603741797722497252841363753834114679306784379319341824813349417007577541466886971550474580368413974382926969910999462429631003527365143148445405716553105750338796691010126879918594076915709977585368841428779903869581
s = (p-1)*(q-1)
d=gmpy2.invert(e,s)
m=pow(c,d,n)
print(str(m))

BUUCTF-RSA2–dp泄露

有时候除了e,n,c之外题目还会给你像dp,dq这样的值，这是为了方便计算产生的，同时也给了我们另一种解题思路。首先，了解dp,dq是什么东西：

给出另一半密钥计算 pq 的值 求M

1
dp=d%(p-1)

进行推导，简单过程如下：

d = dp + k1 * (p-1)

d * e = 1 + k2(p-1)(q-1)

把第二个式子的d代换掉：

e * (dp + k1(p-1)) = 1 + k2(p-1)(q-1)

两边同时对(p-1)取模，消去k

e * dp % (p - 1) = 1

e * dp = 1 + k(p - 1)

因此得到解题脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import gmpy2
from Crypto.Util.number import long_to_bytes

e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657

c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

for i in range(1, e):
    if (dp * e - 1) % i == 0:
        if n % (((dp * e - 1) // i) + 1) == 0:
            p = ((dp * e - 1) // i) + 1
            q = n // (((dp * e - 1) // i) + 1)
            d = gmpy2.invert(e, (p-1)*(q-1))
            m = pow(c, d, n)

print(m)
print(long_to_bytes(m))

BUUCTF-RSA1–dp dq泄露

推导公式:

1
2
3
4
5
I = gmpy2.invert(q,p)
m1 = c^dpmodp
m2 = c^dqmodq
m = (((m1-m2)*I)%p)*q+m2
//其中I为对pq求逆元

就得到脚本:

1
2
3
4
5
6
7
8
9
10
11
12
import gmpy2
from Crypto.Util.number import long_to_bytes
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
I = gmpy2.invert(q,p)
m1 = pow(c,dp,p)
m2 = pow(c,dq,q)
m = (((m1-m2)*I)%p)*q+m2
print(long_to_bytes(m))

BUUCTF-Rsa_output 共模攻击

多组c,e但模数n相同，且e之间最好互质。

当题目给我们很多组c和e，但它们加密使用的模数n相同时，我们可以考虑共模攻击，当e1，e2互质，有gcd(e1,e2)=1，根据扩展欧几里得算法，一定存在整数x,y使得e1x+e2y=1。我们可以调用gmpy2.gcdext()来使用扩展欧几里得算法，以此求出x和y。

化简之后就可以得到：m = (c1^x*c2^y)mod n

例如:

c1,c2;e1,e2以及一个共同的n，尝试共模攻击

1
2
3
4
5
6
7
8
9
10
11
import gmpy2
from Crypto.Util.number import getPrime,long_to_bytes

e1 = 2767
e2 = 3659
n = 1111
c1 = 
c2 = 
_,s1, s2 = gmpy2.gcdext(e1, e2)
m = pow(c1, s1, n) * pow(c2, s2, n) % n
print(long_to_bytes(m))

BUUCTF RSA5-公因数攻击-给出多个C N

题目特征: 给出多组N C

题目中e = 65537，然后给了多达20组的n和c。

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
27
28
import  gmpy2
import libnum
from Crypto.Util.number import long_to_bytes

n1 = 20474918894051778533305262345601880928088284471121823754049725354072477155873778848055073843345820697886641086842612486541250183965966001591342031562953561793332341641334302847996108417466360688139866505179689516589305636902137210185624650854906780037204412206309949199080005576922775773722438863762117750429327585792093447423980002401200613302943834212820909269713876683465817369158585822294675056978970612202885426436071950214538262921077409076160417436699836138801162621314845608796870206834704116707763169847387223307828908570944984416973019427529790029089766264949078038669523465243837675263858062854739083634207
c1 = 974463908243330865728978769213595400782053398596897741316275722596415018912929508637393850919224969271766388710025195039896961956062895570062146947736340342927974992616678893372744261954172873490878805483241196345881721164078651156067119957816422768524442025688079462656755605982104174001635345874022133045402344010045961111720151990412034477755851802769069309069018738541854130183692204758761427121279982002993939745343695671900015296790637464880337375511536424796890996526681200633086841036320395847725935744757993013352804650575068136129295591306569213300156333650910795946800820067494143364885842896291126137320

#...此处省略20组n和c

e = 65537
n=[]
c=[]
p=[]
for i in range(1,20):
	n.append(eval('n'+str(i)))
	c.append(eval('c'+str(i)))
data=list(zip(n,c))
for i in range(len(n)):
	for j in range(i+1,len(n)):
		if gmpy2.gcd(n[i],n[j])!=1:
			print(i,j)#i=4,j=17
			print(gmpy2.gcd(n[i],n[j]))
p=gmpy2.gcd(n5,n18)
q=n5//p
d = gmpy2.invert(e, (p-1)*(q-1))
print(d)
m = pow(c5,d,n5)
print(long_to_bytes(m))

三、总结

RSA作为一种非常经典的非对称公开密钥加密体制，属于是CTF密码学题目中的常客。对刚接触密码学的新手来说，一上来看到各种几百上千位的数字难免感到头大，但实际上了解了RSA的原理和常见解题技巧后也没有那么复杂，常规的RSA题目我觉得算是密码学中比较好拿分的部分了。