一、前言

​ CTF（Capture The Flag），中文一般译作夺旗赛，在网络安全领域中指的是网络安全技术人员之间进行技术竞技的一种比赛形式。CTF 起源于 1996 年 DEFCON 全球黑客大会，以代替之前黑客们通过相发起真实攻击进行技术比拼的方式；这一比赛将安全相关的知识点抽象出来并加入到题目中，我们通过对知识点的理解认知，具体地进行实践来攻克题目并获得Flag。CTF主要分为五大方向：WEB（网络攻防）、Pwn（二进制漏洞利用）、Reverse（逆向工程）、Crypto（密码学）和Misc（杂项），博主也是两个月前才开始学习CTF的Crypto方向，如今也做了一些密码方向的题，积累了一些经验，本文是关于RSA的一些题型总结，有问题欢迎大家指正。

CTF入门网站：https://hello-ctf.com/ 简介 - CTF Wiki CTF题库：https://www.nssctf.cn/

二、RSA基本介绍

​ RSA加密算法是一种非对称加密算法，在公开密钥加密和电子商业中被广泛使用。RSA是由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在1977年一起提出的。当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的。RSA中涉及公钥对（N,e）和私钥对（N,d），所谓公钥对就是可以公开的数据，而私钥对是要严格保存的，否则就会被破解消息。

公钥和私钥的产生

1.选择两个大素数p,q

​ 首先随机选取两个大素数p和q，为保证其安全性，这两个大素数应当具有一定的长度，一般是512或者1024比特位。

2.计算模数N和欧拉函数φ（N）

​ N作为模数，其大小决定了RSA加密算法的安全性和加密长度。一般来说N越大，破解难度就越高，因而素因子p,q需要具有一定 的长度，才能保证N不被轻易分解。

3.选取公钥e和私钥d

​ 从(1,φ(N))中任意选取一个与φ(N)互素的整数e作为公钥，一般e取65537(可以了解一下费马素数)，这样可以提高加密解密的计算 效率。

加密原理

解密原理

数学证明

三、CTF中RSA题型总结

​ RSA作为CTF中最常见也是比较基础的一类题型，经常单独出现或者和其他类型的加密方式一起出现，下面博主总结一下目前见到的RSA的一些题型。

1.已知p,q,e，求d

1
2
3
4
5
6
7
8
//最简单的题型，用RSA的私钥生成方法即可得到答案
from Crypto.Util.number import *
p = 3487583947589437589237958723892346254777 
q = 8767867843568934765983476584376578389
e = 65537
phi = (p-1)*(q-1)
d = inverse(e,phi) //求逆元的函数
print(d)

2.已知n,e,c，求明文m

题目如下：

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

flag = '**********'

p = getPrime(512)
q = getPrime(512)
m1 = bytes_to_long(bytes(flag.encode()))
e = 0x10001
n = p*q
flag1 = pow(m1,e,n)
print('flag= '+str(flag1))
print('n= '+str(n))

flag= 10227915341268619536932290456122384969242151167487654201363877568935534996454863939953106193665663567559506242151019201314446286458150141991211233219320700112533775367958964780047682920839507351492644735811096995884754664899221842470772096509258104067131614630939533042322095150722344048082688772981180270243
n= 52147017298260357180329101776864095134806848020663558064141648200366079331962132411967917697877875277103045755972006084078559453777291403087575061382674872573336431876500128247133861957730154418461680506403680189755399752882558438393107151815794295272358955300914752523377417192504702798450787430403387076153

直接尝试分解n(大数分解网站：factordb.com非常好用的工具)，然后得到了p和q，之后按照正常的解密步骤来即可得到flag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from gmpy2 import *
from Crypto.Util.number import *
# flag = '**********'
# p = getPrime(512)
# q = getPrime(512)
# m1 = bytes_to_long(bytes(flag.encode()))
# e = 0x10001
# n = p*q
# flag1 = pow(m1,e,n)
# print('flag= '+str(flag1))
# print('n= '+str(n))

e = 0x10001
flag= 10227915341268619536932290456122384969242151167487654201363877568935534996454863939953106193665663567559506242151019201314446286458150141991211233219320700112533775367958964780047682920839507351492644735811096995884754664899221842470772096509258104067131614630939533042322095150722344048082688772981180270243
n= 52147017298260357180329101776864095134806848020663558064141648200366079331962132411967917697877875277103045755972006084078559453777291403087575061382674872573336431876500128247133861957730154418461680506403680189755399752882558438393107151815794295272358955300914752523377417192504702798450787430403387076153
p = 7221289171488727827673517139597844534869368289455419695964957239047692699919030405800116133805855968123601433247022090070114331842771417566928809956044421
q = 7221289171488727827673517139597844534869368289455419695964957239047692699919030405800116133805855968123601433247022090070114331842771417566928809956045093
phi = (p-1)*(q-1)
d = inverse(e,phi)
# gcd(e,phi)=1
flag = long_to_bytes(pow(flag,d,n))
print(flag)

3.小明文攻击

题目如下：

1
2
3
4
5
6
7
8
9
10
11
12
from gmpy2 import iroot
from secret import flag
from Crypto.Util.number import*
m = long_to_bytes(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 3
c = pow(m,e,n)
c = 150409620528288093947185249913242033500530715593845912018225648212915478065982806112747164334970339684262757
e = 3
n = 20279309983698966932589436610174513524888616098014944133902125993694471293062261713076591251054086174169670848598415548609375570643330808663804049384020949389856831520202461767497906977295453545771698220639545101966866003886108320987081153619862170206953817850993602202650467676163476075276351519648193219850062278314841385459627485588891326899019745457679891867632849975694274064320723175687748633644074614068978098629566677125696150343248924059801632081514235975357906763251498042129457546586971828204136347260818828746304688911632041538714834683709493303900837361850396599138626509382069186433843547745480160634787

​ 从题目中可以发现，n很大，e=3，加密后的密文c相较于n也很小，所以直接对c开e次根即可(建议使用gmpy2库中的iroot函数，注意返回的是元组，第一个元素是开根的结果)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot
# from secret import flag
# from Crypto.Util.number import*
# m = long_to_bytes(flag)
# p = getPrime(1024)
# q = getPrime(1024)
# n = p*q
# e = 3
# c = pow(m,e,n)
c = 150409620528288093947185249913242033500530715593845912018225648212915478065982806112747164334970339684262757
e = 3
n = 20279309983698966932589436610174513524888616098014944133902125993694471293062261713076591251054086174169670848598415548609375570643330808663804049384020949389856831520202461767497906977295453545771698220639545101966866003886108320987081153619862170206953817850993602202650467676163476075276351519648193219850062278314841385459627485588891326899019745457679891867632849975694274064320723175687748633644074614068978098629566677125696150343248924059801632081514235975357906763251498042129457546586971828204136347260818828746304688911632041538714834683709493303900837361850396599138626509382069186433843547745480160634787
# 由于e很小，p,q很大，所以即使m的e次幂也没有n大
# 因此直接对c进行开e次根处理即可得到m
m = iroot(c,e) # iroot返回的是(mpz(),True)
print(long_to_bytes(m[0]))

4.共模攻击

该类题目因有一定难度，详情请参见此文章RSA共模攻击 | 米大大的Blog

5.dp,dq泄露

题目如下：

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

p = getPrime(1024)
q = getPrime(1024)
d = inverse(65537,(p-1)*(q-1))
dp = d % (p-1)
dq = d % (q-1)
print(f'c={pow(bytes_to_long(flag),e,p*q)}')
print(f'p={p}')
print(f'q={q}')
print(f'dp={dp}')
print(f'dq={dq}')


c=312026920216195772014255984174463085443866592575942633449581804171108045852080517840578408476885673600123673447592477875543106559822653280458539889975125069364584140981069913341705738633426978886491359036285144974311751490792757751756044409664421663980721578870582548395096887840688928684149014816557276765747135567714257184475027270111822159712532338590457693333403200971556224662094381891648467959054115723744963414673861964744567056823925630723343002325605154661959863849738333074326769879861280895388423162444746726568892877802824353858845944856881876742211956986853244518521508714633279380808950337611574412909
p=108043725609186781791705090463399988837848128384507136697546885182257613493145758848215714322999196482303958182639388180063206708575175264502030010971971799850889123915580518613554382722069874295016841596099030496486069157061211091761273568631799006187376088457421848367280401857536410610375012371577177832001
q=121590551121540247114817509966135120751936084528211093275386628666641298457070126234836053337681325952068673362753408092990553364818851439157868686131416391201519794244659155411228907897025948436021990520853498462677797392855335364006924106615008646396883330251028071418465977013680888333091554558623089051503
dp=11282958604593959665264348980446305500804623200078838572989469798546944577064705030092746827389207634235443944672230537015008113180165395276742807804632116181385860873677969229460704569172318227491268503039531329141563655811632035522134920788501646372986281785901019732756566066694831838769040155501078857473
dq=46575357360806054039250786123714177813397065260787208532360436486982363496441528434309234218672688812437737096579970959403617066243685956461527617935564293219447837324227893212131933165188205281564552085623483305721400518031651417947568896538797580895484369480168587284879837144688420597737619751280559493857

​ 从题目中我们没有发现模数n和指数e，但是有p、q、dp、dq，因此这是典型的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
from Crypto.Util.number import *
from gmpy2 import *
# from secret import flag
#
# p = getPrime(1024)
# q = getPrime(1024)
# d = inverse(65537,(p-1)*(q-1))
# dp = d % (p-1)
# dq = d % (q-1)
# print(f'c={pow(bytes_to_long(flag),e,p*q)}')
# print(f'p={p}')
# print(f'q={q}')
# print(f'dp={dp}')
# print(f'dq={dq}')

c=312026920216195772014255984174463085443866592575942633449581804171108045852080517840578408476885673600123673447592477875543106559822653280458539889975125069364584140981069913341705738633426978886491359036285144974311751490792757751756044409664421663980721578870582548395096887840688928684149014816557276765747135567714257184475027270111822159712532338590457693333403200971556224662094381891648467959054115723744963414673861964744567056823925630723343002325605154661959863849738333074326769879861280895388423162444746726568892877802824353858845944856881876742211956986853244518521508714633279380808950337611574412909
p=108043725609186781791705090463399988837848128384507136697546885182257613493145758848215714322999196482303958182639388180063206708575175264502030010971971799850889123915580518613554382722069874295016841596099030496486069157061211091761273568631799006187376088457421848367280401857536410610375012371577177832001
q=121590551121540247114817509966135120751936084528211093275386628666641298457070126234836053337681325952068673362753408092990553364818851439157868686131416391201519794244659155411228907897025948436021990520853498462677797392855335364006924106615008646396883330251028071418465977013680888333091554558623089051503
dp=11282958604593959665264348980446305500804623200078838572989469798546944577064705030092746827389207634235443944672230537015008113180165395276742807804632116181385860873677969229460704569172318227491268503039531329141563655811632035522134920788501646372986281785901019732756566066694831838769040155501078857473
dq=46575357360806054039250786123714177813397065260787208532360436486982363496441528434309234218672688812437737096579970959403617066243685956461527617935564293219447837324227893212131933165188205281564552085623483305721400518031651417947568896538797580895484369480168587284879837144688420597737619751280559493857

def rsa(dp,dq,p,q,c):
    m1=pow(c,dp,p)
    m2=pow(c,dq,q)
    p_q=inverse(p,q)
    m=(m1+p_q*((m2-m1)%q)*p)%(p*q)
    print(long_to_bytes(m))

rsa(dp,dq,p,q,c)

数学证明如下：

6.共享素数

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

n1=103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2=115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n1)
c = pow(c, e, n2)

print("c = %d" % c)

c=60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264

从题目中可以发现，进行了两次RSA的加密过程。首先尝试分解n1和n2，分解后发现n1和n2存在共同的素数因子，由此题目就变得简单起来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
from gmpy2 import *
# from flag import *

n1=103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2=115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e = 65537
# m = bytes_to_long(flag)
# c = pow(m, e, n1)
# c = pow(c, e, n2)
#
# print("c = %d" % c)

c=60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264
p = gcd(n1,n2) # 共同素数因子
q1 = n1 // p
q2 = n2 // p
phi1 = (p-1)*(q1-1)
phi2 = (p-1)*(q2-1)
d1 = inverse(e,phi1)
d2 = inverse(e,phi2)
flag = long_to_bytes(pow(pow(c,d2,n2),d1,n1))
print(flag)

7.e和phi不互素

题目一 签到题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
from secret import flag
m=bytes_to_long(flag)
p=getPrime(512)
q=getPrime(512)
print('p=',p)
print('q=',q)
n=p*q
e=65537
c=pow(m,e,n)
print('c=',c)

p = 12408795636519868275579286477747181009018504169827579387457997229774738126230652970860811085539129972962189443268046963335610845404214331426857155412988073
q = 12190036856294802286447270376342375357864587534233715766210874702670724440751066267168907565322961270655972226761426182258587581206888580394726683112820379
c = 68960610962019321576894097705679955071402844421318149418040507036722717269530195000135979777852568744281930839319120003106023209276898286482202725287026853925179071583797231099755287410760748104635674307266042492611618076506037004587354018148812584502385622631122387857218023049204722123597067641896169655595

这道题目乍一看似乎非常简单，p,q都给出了，可以按部就班的做。然而，在计算欧拉函数时，会发现phi和e不互素，公因数为e。按照RSA的条件可知，e和phi不互素，则不存在逆元。

由此就有了e和欧拉函数不互素问题，解题脚本如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
from gmpy2 import *
# from secret import flag
# m=bytes_to_long(flag)
# p=getPrime(512)
# q=getPrime(512)
# print('p=',p)
# print('q=',q)
# n=p*q
# e=65537
# c=pow(m,e,n)
# print('c=',c)

p = 12408795636519868275579286477747181009018504169827579387457997229774738126230652970860811085539129972962189443268046963335610845404214331426857155412988073
q = 12190036856294802286447270376342375357864587534233715766210874702670724440751066267168907565322961270655972226761426182258587581206888580394726683112820379
c = 68960610962019321576894097705679955071402844421318149418040507036722717269530195000135979777852568744281930839319120003106023209276898286482202725287026853925179071583797231099755287410760748104635674307266042492611618076506037004587354018148812584502385622631122387857218023049204722123597067641896169655595
e = 65537
phi = (p-1)*(q-1)
# gcd(e,q-1)==65537
pi = p-1
d = inverse(e,pi)
flag = long_to_bytes(pow(c,d,p))
print(flag)

数学证明如下

题目二 AMM算法——有限域开根

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

e = 4919
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
n = p * q

assert(flag.startswith('NCTF'))
m = int.from_bytes(flag.encode(), 'big')
assert(m.bit_length() > 1337)

c = pow(m, e, n)
print(c)
c = 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359

这道题同样给出了p和q，并且可以发现e和phi依然不互素。然而和上一道题不一样的是，p-1和q-1中均含有e这个因子，所以上面的方法自然就用不成了。从网上看大佬的wp发现这题考的是AMM算法，即有限域开根，脚本如下。