JarvisOJ: Medium RSA
你没看错，这还真是密码学系列了，相信你已经解出前两题了，那么继续看这题吧。
【附件】
可以直接分解掉 $n$. 因此本题暴力即可。
➜ RsaCtfTool-master python3 RsaCtfTool.py --publickey /mnt/c/Users/blue/Desktop/workspace/pubkey.pem --uncipherfile /mnt/c/Users/blue/Desktop/workspace/flag.enc
[+] Clear text : b'\x00\x02\xc0\xfe\x04\xe3&\x0e[\x87\x00PCTF{256b_i5_m3dium}\n'JarvisOJ: hard RSA
相信你已经做出了medium RSA，这题的pubkey在medium RSA的基础上我做了点手脚，继续挑战吧。
Hint1: 1.不需要爆破。2.用你的数学知识解决此题。3.难道大家都不会开根号吗？
【附件】
先来看给出的$(N, e)$.
➜ RsaCtfTool-master python3 RsaCtfTool.py --dumpkey --key /mnt/c/Users/blue/Desktop/workspace/pubkey.pem
[*] n: 87924348264132406875276140514499937145050893665602592992418171647042491658461
[*] e: 2
➜ RsaCtfTool-master cat /mnt/c/Users/blue/Desktop/workspace/flag.enc
9╚m'WiK?GxC7H%这里 $e=2$，是非常特殊的公钥。$\varphi(n) = (p-1)(q-1)$显然是个偶数，常理来讲 $e=2$ 时不存在私钥（因为2针对一个偶数不可能有逆元）。现在我们只知道 $c=m^2 \pmod n$，需要还原出$c$.
此时的加密算法称为Rabin算法。它由 Michael O. Rabin 于1979年提出。它的过程如下：
- 选取两个大质数$p, q$，需要保证$p, q$模4得3.
- 计算$n=pq$作为公钥。$(p, q)$作为私钥。
- 加密：$c = m^2 \mod n$，此时需要保证$m < n$.
Rabin算法的解密原理是：假设我们知道$m\%p $ 和 $m\%q $，那么拿着中国剩余定理立刻可以知道 $m \% n$的值。又有$m<n$，则$m$的值就直接拿到了，岂不美哉？
下面的讨论基于这样一个例子：$p=7, q=11, m=20, c=m^2\%77 = 15$.
首先，$m^2 \equiv c \pmod n$等价于$\begin{cases}m^ 2 \equiv c \pmod p \\ m^2\equiv c \pmod q\end{cases}$，现在试着求出$\sqrt c \pmod p$, 也就是$\sqrt {15} \pmod 7$. 枚举$0,1,2\cdots 6$可以得到：$1^ 2 \equiv 6 ^2 \equiv 15 \pmod 7$.
但是现实上，$p$ 是非常大的，无法逐一枚举 $p$ 以内的所有整数。此时我们该如何求出模 $p$ 意义下 $\sqrt c$ 的值——也就是使得$x^2 \equiv c \pmod p$的 $x$ 呢？ 有断言：$$x = c^ \frac{p+1}{4} ~ 使得 ~ x^2 \equiv c \pmod p$$
验证一下。$x^2 \equiv c^{\frac{p+1}{2}} \equiv c \cdot c^{\frac{p-1}2} \pmod p$. 由于我们已经知道 $c$ 是模 $p$ 意义下的二次剩余，故必然有 $c^ {\frac{p-1}2} \equiv 1 \pmod p$，这称为欧拉准则。从而 $x^2 \equiv c \pmod p$ 得证。但 $x$ 不是唯一使得$x^2\equiv c \pmod p$的数：显然我们有$(p-x)^2 \equiv p^2 - 2px + x^2 \equiv c \pmod p$. 从而 $(p-x)$ 也是一个解。综上，我们得到了模$p$意义下给$c$开方的手段：
$$m^2 \equiv c\pmod p \qquad \Rightarrow \qquad m\equiv c^{\frac{p+1}{4}}\quad\text{or}\quad p-c^{\frac{p+1}{4}} \pmod p $$
为什么Rabin算法生成密钥时，要求 $p, q$ 模4余3呢？就是为了使得$\frac{p+1}{4}$是一个整数，方便解密（否则我们为了求出$c^{\frac{p+1}{4}}$，就得继续在模意义下开方了）。验证一下例子：$c^{\frac{p+1}{4}} \equiv 15 ^ {\frac{8}{4}} \equiv 1 \pmod 7$，故 1 和 7-1=6 满足 $x ^ 2 \equiv 15 \pmod 7$.
现在手上有了 $m \mod p$ 的两个可能值（1, 6） ，相似地可以求出 $m \mod q$ 的两个可能值 （2, 9）. 因此我们现在有了 $m\%p, q$ 的四组可能值。它们里面一定有一组是正确的，所以我们直接把这四组解都尝试一下，然后再看哪个解出来的 $m$ 长得像明文。
目前的任务很清楚： 已知$\begin{cases}m \equiv x \pmod p \\ m \equiv y \pmod q \end{cases}$，需要求出$m$. 这是中国剩余定理的典型应用：$$\begin{cases}m \equiv x \pmod p \\ m \equiv y \pmod q \end{cases} \quad \Rightarrow \quad m \equiv x \cdot q \cdot \text{inv}(q, p) + y\cdot p \cdot \text{inv}(p, q) \pmod n$$
一共有4组可能的$(x,y)$，全都代进去试试。它们是：
- $x=1, y=2$，此时$1\times 11\times 2 + 2\times 7 \times 8 \equiv 57 \pmod {77}$
- $x=6, y=2$，此时$6\times 11\times 2 + 2\times 7\times 8 \equiv 13 \pmod {77}$
- $x=1, y=9$，此时$1\times 11\times 2 + 9\times 7 \times 8 \equiv 64 \pmod {77}$
- $x=6, y=9$，此时$6\times 11\times 2 + 9\times 7\times 8 \equiv 20 \pmod {77}$ 恰好是明文！
如上所述，Rabin算法的解密会得到四个结果。理论上，如果没有其他信息，我们就无法判断哪个是明文了。不过日常生活中，当然会有方法来知道应该取哪个结果——本题中，明文里面有个子串“CTF”。
本题中，$n$ 可以直接分解，从而 $p, q$ 已知. 代码如下：
import gmpy2
import codecs
def squareMod(c, mod): # 模意义下开根，找到 x, 使得 x^2 % mod = c
assert(mod % 4 == 3)
res = gmpy2.powmod(c, (mod+1)//4, mod)
return res, mod - res
def getPlaintext(x, y, p, q): # 假设 m%p=x, m%q=y, 求明文
res = x*q*gmpy2.invert(q, p) + y*p*gmpy2.invert(p, q)
return res % (p*q)
def solve(c, p, q): # 已知 p,q, 解密 c
px = squareMod(c, p)
py = squareMod(c, q)
for x in px:
for y in py:
yield getPlaintext(x, y, p, q)
c = open('flag.enc', 'rb').read()
c = int(codecs.encode(c, 'hex'), base=16)
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
for msg in solve(c, p, q):
res = hex(msg)[2:]
if len(res) % 2 == 1:
res = '0' + res
print(codecs.decode(res, 'hex'))
# b'D\xac\x11#\x05\xd8\x00\xec\x0f\xccP\x92\xde\x9a\x10e\xc7cb\x90\x19`\xde\x86\xcaP\xd4/\x8cV\xbf\xa0'
# b'\x02\xdb2\x8b\xcc\xbb`\xd7?\x1e\xec\xc2\x00PCTF{sp3ci4l_rsa}\n'
# b'\xc2`\x8f\xb38\x0c(\xdf$X\x8c\x1c@\x8e\xcai\x17\xc5{Y\xcd=\x88`\xf3\xaf\xa0w\x0c\\\xb3\xd3'
# b'}\xb7Y\xc2\xbe\x00\xe3S\xeb\xcbZv#\xf5\nF\xa4\xa8\x94=$\x10\rC]\xcb+\xb9\xf3gq=' 于是得到flag: PCTF{sp3ci4l_rsa} .
BUUCTF: RSA1
【附件】
（给定了 $p,q,dp,dq,c$）
查阅资料，知$dp \equiv d \pmod{p−1}$. 本题没有给出 $e$ 或 $d$.
由欧拉定理，不难注意到$c^{dp} \equiv c ^ {d\%\varphi(p)} \equiv c ^ d \pmod p$, 同理$c ^ {dq} \equiv c^d \pmod q$. 现在 $c ^ d$ 模 $p,q$ 的结果已经知道，那么用中国剩余定理就可以得到 $c ^ d \% n$. 即为明文。
import gmpy2, libnum
from functools import reduce
def CRT(r, mod):
M = reduce(lambda x,y:x*y, mod)
ans = 0
for i in range(len(r)):
m = M // mod[i]
ans += r[i] * m * gmpy2.invert(m, mod[i])
return ans % M
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
cdModP = gmpy2.powmod(c, dp, p)
cdModQ = gmpy2.powmod(c, dq, q)
m = CRT([cdModP, cdModQ], [p, q])
print(libnum.n2s(m))BUUCTF: RSA2
【附件】
（给出了 $e, n, dp, c$）
一道转化很巧妙的题目。首先有 $dp \equiv d \pmod {\varphi(p)}$, 两边乘上 $e$ 有$$e\cdot dp \equiv e\cdot d \pmod {\varphi(p)} \quad \Rightarrow \quad e\cdot d = k \cdot (p-1) + e \cdot dp$$ 而又由 $e\cdot d\equiv 1 \pmod {\varphi(n)}$知 $$e\cdot d = k \cdot (p-1) + e \cdot dp = 1 + t(p-1)(q-1)$$ 移项可得 $$e\cdot dp = 1 + (r-k)(p-1)$$ 其中 $r$ 是个常数 $t(q-1)$.
来观察这个等式，左边$e \cdot dp$是已知的，右边 $p-1$ 比$dp$要大，则 $(r-k)$ 必然比 $e$ 小。我们从1到 $e$ 枚举 $(r-k)=x$，然后看$e\cdot dp - 1$能否被$x$整除。如果能，则我们可以得到$p-1 = \frac{e\cdot dp - 1}{x}$. 接下来就可以把 $p, q$ 都求出来，从而解密。
import gmpy2, libnum
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
for x in range(1, e):
if (e*dp-1) % x == 0:
p = (e*dp-1) // x + 1
if n%p != 0: continue
q = n // p
d = gmpy2.invert(e, (p-1)*(q-1))
print(libnum.n2s(gmpy2.powmod(c, d, n)))BUUCTF: RSA3
【附件】
给定 $n, e_1, c_1, e_2, c_2$
这是共模数攻击。通过扩展欧几里得算法，可以找到整数 $a, b$ 使得 $ae_1 + be_2 = 1$. 那么$$c_1^a c_2 ^ b \equiv m^{ae_1+be_2} \equiv m \pmod n$$
import gmpy2, libnum
def exgcd(a, b):
if b==0: return 1, 0
x, y = exgcd(b, a%b)
return y, x-a//b*y
n = 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1 = 11187289
c1 = 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
e2 = 9647291
c2 = 18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
a, b = exgcd(e1, e2)
m = gmpy2.powmod(c1, a, n) * gmpy2.powmod(c2, b, n) % n
print(libnum.n2s(m))BUUCTF: rsa2
听说这题是rsa的续集 注意：得到的 flag 请包上 flag{} 提交
【附件】
给了 $n,e$，要去找 $d$. 注意到 $e$ 极大，采用低解密指数攻击（Wiener attack）. 工具：
pablocelayes/rsa-wiener-attack
A Python implementation of the Wiener attack on RSA public-key encryption scheme. - pablocelayes/rsa-wiener-attack
import RSAwienerHacker
N = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471
e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085
d = RSAwienerHacker.hack_RSA(e,N)
if d:
print(d)BUUCTF: Dangerous RSA
littlE littlE RSA Big Big Dangerous 注意：得到的 flag 请包上 flag{} 提交
【附件】
这里 $e=3$, 一般采用小指数攻击：$$m^3 \equiv c \pmod N \quad \Rightarrow \quad m = \sqrt[3]{c+kN} $$
从小到大枚举 $k$，如果 $c+kN$ 能开三次方就找到了 $m$. 我觉得这是一个非常投机取巧的办法，成败全看 $m$ 的规模。
import gmpy2, libnum
N = 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793
e = 0x3
c = 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
for k in range(100000):
res, flag = gmpy2.iroot(c + k*N, 3)
if flag:
print(libnum.n2s(res))
exit(0)BUUCTF: RSA5
【附件】
给了一个 $e=65537$, 然后给了一大批 $n$ 和 $c$. 写个脚本看了一下这些 $n$, 发现这些 $n$ 里面存在不互质的数对。从而这题就是模不互质攻击。
import gmpy2, libnum
e = 65537
n1 = 19591441383958529435598729113936346657001352578357909347657257239777540424811749817783061233235817916560689138344041497732749011519736303038986277394036718790971374656832741054547056417771501234494768509780369075443550907847298246275717420562375114406055733620258777905222169702036494045086017381084272496162770259955811174440490126514747876661317750649488774992348005044389081101686016446219264069971370646319546429782904810063020324704138495608761532563310699753322444871060383693044481932265801505819646998535192083036872551683405766123968487907648980900712118052346174533513978009131757167547595857552370586353973
c1 = 3834917098887202931981968704659119341624432294759361919553937551053499607440333234018189141970246302299385742548278589896033282894981200353270637127213483172182529890495903425649116755901631101665876301799865612717750360089085179142750664603454193642053016384714515855868368723508922271767190285521137785688075622832924829248362774476456232826885801046969384519549385428259591566716890844604696258783639390854153039329480726205147199247183621535172450825979047132495439603840806501254997167051142427157381799890725323765558803808030109468048682252028720241357478614704610089120810367192414352034177484688502364022887
n2 = 22822039733049388110936778173014765663663303811791283234361230649775805923902173438553927805407463106104699773994158375704033093471761387799852168337898526980521753614307899669015931387819927421875316304591521901592823814417756447695701045846773508629371397013053684553042185725059996791532391626429712416994990889693732805181947970071429309599614973772736556299404246424791660679253884940021728846906344198854779191951739719342908761330661910477119933428550774242910420952496929605686154799487839923424336353747442153571678064520763149793294360787821751703543288696726923909670396821551053048035619499706391118145067
c2 = 15406498580761780108625891878008526815145372096234083936681442225155097299264808624358826686906535594853622687379268969468433072388149786607395396424104318820879443743112358706546753935215756078345959375299650718555759698887852318017597503074317356745122514481807843745626429797861463012940172797612589031686718185390345389295851075279278516147076602270178540690147808314172798987497259330037810328523464851895621851859027823681655934104713689539848047163088666896473665500158179046196538210778897730209572708430067658411755959866033531700460551556380993982706171848970460224304996455600503982223448904878212849412357
p = gmpy2.gcd(n1, n2)
q = n1 // p
m = gmpy2.powmod(c1, gmpy2.invert(e, (p-1)*(q-1)), n1)
print(libnum.n2s(m))BUUCTF: [HDCTF2019]bbbbbbrsa
【附件】
给出了 $n, p$ 和密钥的生成器。$e$ 在 $70000$以下，故直接爆破即可。
n = 37421829509887796274897162249367329400988647145613325367337968063341372726061
p = 177077389675257695042507998165006460849
assert(n%p==0)
q = n//p
c = 2373740699529364991763589324200093466206785561836101840381622237225512234632
phi = (p-1)*(q-1)
import gmpy2, libnum, codecs
for e in range(70000, 0, -1):
try:
m = gmpy2.powmod(c, gmpy2.invert(e, phi), n)
m = hex(m)[2:].encode()
m = m if len(m)%2==0 else '0' + m
m = codecs.decode(m, 'hex')
if b'flag' in m:
print(m)
except Exception:
pass
BUUCTF: [GUET-CTF2019]BabyRSA
【附件】
给出了 $p+q, (p+1)(q+1), e, d$. 所以现在问题是 $N$ 不知道。由$$(p+1)(q+1) = pq + (p+q) + 1$$可以直接推出 $N$.
import gmpy2, libnum
pAddq = 0x1232fecb92adead91613e7d9ae5e36fe6bb765317d6ed38ad890b4073539a6231a6620584cea5730b5af83a3e80cf30141282c97be4400e33307573af6b25e2ea
p1q1 = 0x5248becef1d925d45705a7302700d6a0ffe5877fddf9451a9c1181c4d82365806085fd86fbaab08b6fc66a967b2566d743c626547203b34ea3fdb1bc06dd3bb765fd8b919e3bd2cb15bc175c9498f9d9a0e216c2dde64d81255fa4c05a1ee619fc1fc505285a239e7bc655ec6605d9693078b800ee80931a7a0c84f33c851740
e = 0xe6b1bee47bd63f615c7d0a43c529d219
d = 0x2dde7fbaed477f6d62838d55b0d0964868cf6efb2c282a5f13e6008ce7317a24cb57aec49ef0d738919f47cdcd9677cd52ac2293ec5938aa198f962678b5cd0da344453f521a69b2ac03647cdd8339f4e38cec452d54e60698833d67f9315c02ddaa4c79ebaa902c605d7bda32ce970541b2d9a17d62b52df813b2fb0c5ab1a5
enc_flag = 0x50ae00623211ba6089ddfae21e204ab616f6c9d294e913550af3d66e85d0c0693ed53ed55c46d8cca1d7c2ad44839030df26b70f22a8567171a759b76fe5f07b3c5a6ec89117ed0a36c0950956b9cde880c575737f779143f921d745ac3bb0e379c05d9a3cc6bf0bea8aa91e4d5e752c7eb46b2e023edbc07d24a7c460a34a9a
N = p1q1 - pAddq - 1
res = gmpy2.powmod(enc_flag, d, N)
print(libnum.n2s(res))BUUCTF: [NCTF2019]childRSA
【附件】
给了一个程序：
from random import choice
from Crypto.Util.number import isPrime, sieve_base as primes
from flag import flag
def getPrime(bits):
while True:
n = 2
while n.bit_length() < bits:
n *= choice(primes)
if isPrime(n + 1):
return n + 1
e = 0x10001
m = int.from_bytes(flag.encode(), 'big')
p, q = [getPrime(2048) for _ in range(2)]
n = p * q
c = pow(m, e, n)
# n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
# c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108注意到生成质数的过程，是在质数库里面选一堆质数乘起来，最后加上 1。这会导致 $(p-1)$ 拥有小因子。采用 Pollard's p-1 攻击：
python -m primefac -vs -m=p-1 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
Z1241 = P621 x P621 = 178449493212694205742332078583256205058672290603652616240227340638730811945224947826121772642204629335108873832781921390308501763661154638696935732709724016546955977529088135995838497476350749621442719690722226913635772410880516639651363626821442456779009699333452616953193799328647446968707045304702547915799734431818800374360377292309248361548868909066895474518333089446581763425755389837072166970684877011663234978631869703859541876049132713490090720408351108387971577438951727337962368478059295446047962510687695047494480605473377173021467764495541590394732685140829152761532035790187269724703444386838656193674253139 x 184084121540115307597161367011014142898823526027674354555037785878481711602257307508985022577801782788769786800015984410443717799994642236194840684557538917849420967360121509675348296203886340264385224150964642958965438801864306187503790100281099130863977710204660546799128755418521327290719635075221585824217487386227004673527292281536221958961760681032293340099395863194031788435142296085219594866635192464353365034089592414809332183882423461536123972873871477755949082223830049594561329457349537703926325152949582123419049073013144325689632055433283354999265193117288252918515308767016885678802217366700376654365502867成功分解，可以拿flag了。
import gmpy2, libnum
c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108
p = 178449493212694205742332078583256205058672290603652616240227340638730811945224947826121772642204629335108873832781921390308501763661154638696935732709724016546955977529088135995838497476350749621442719690722226913635772410880516639651363626821442456779009699333452616953193799328647446968707045304702547915799734431818800374360377292309248361548868909066895474518333089446581763425755389837072166970684877011663234978631869703859541876049132713490090720408351108387971577438951727337962368478059295446047962510687695047494480605473377173021467764495541590394732685140829152761532035790187269724703444386838656193674253139
q = 184084121540115307597161367011014142898823526027674354555037785878481711602257307508985022577801782788769786800015984410443717799994642236194840684557538917849420967360121509675348296203886340264385224150964642958965438801864306187503790100281099130863977710204660546799128755418521327290719635075221585824217487386227004673527292281536221958961760681032293340099395863194031788435142296085219594866635192464353365034089592414809332183882423461536123972873871477755949082223830049594561329457349537703926325152949582123419049073013144325689632055433283354999265193117288252918515308767016885678802217366700376654365502867
e = 0x10001
d = gmpy2.invert(e, (p-1)*(q-1))
m = pow(c, d, p*q)
print(libnum.n2s(m))BUUCTF: RSA & what
素数生成算法太麻烦了，有没有取巧的方法呢？
诶，这里好像有个不错的想法哟。
看起来节约了不少时间呢，嘿嘿嘿……
顺便问问，应该大家都知道base64吧，用来编码还是很方便的呢！
【附件】
datagen 是这样的：
from Crypto.Util.number import bytes_to_long, getPrime
from random import randint
from gmpy2 import powmod
p = getPrime(2048)
q = getPrime(2048)
N = p*q
Phi = (p-1)*(q-1)
def get_enc_key(N,Phi):
e = getPrime(N)
if Phi % e == 0:
return get_enc_key(N, Phi)
else:
return e
e1 = get_enc_key(randint(10, 12), Phi)
e2 = get_enc_key(randint(10, 12), Phi)
fr = open(r"./base64", "rb")#flag is in this file
f1 = open(r"./HUB1", "wb")
f2 = open(r"./HUB2", "wb")
base64 = fr.read(255)
f1.write("%d\n%d\n" % (N, e1))
f2.write("%d\n%d\n" % (N, e2))
while len(base64)>0:
pt = bytes_to_long(base64)
ct1 = powmod(pt, e1, N)
ct2 = powmod(pt, e2, N)
f1.write("\n%d" % ct1)
f2.write("\n%d" % ct2)
base64 = fr.read(255)
fr.close()
f1.close()
f2.close()显然可以采用共模数攻击。代码如下：
import gmpy2, libnum, base64
def exgcd(a, b):
if b==0: return 1, 0
x, y = exgcd(b, a%b)
return y, x-a//b*y
n = 785095419718268286866508214304816985447077293766819398728046411166917810820484759314291028976498223661229395009474063173705162627037610993539617751905443039278227583504604808251931083818909467613277587874545761074364427549966555519371913859875313577282243053150056274667798049694695703660313532933165449312949725581708965417273055582216295994587600975970124811496270080896977076946000102701030260990598181466447208054713391526313700681341093922240317428173599031624125155188216489476825606191521182034969120343287691181300399683515414809262700457525876691808180257730351707673660380698973884642306898810000633684878715402823143549139850732982897459698089649561190746850698130299458080255582312696873149210028240898137822888492559957665067936573356367589784593119016624072433872744537432005911668494455733330689385141214653091888017782049043434862620306783436169856564175929871100669913438980899219579329897753233450934770193915434791427728636586218049874617231705308003720066269312729135764175698611068808404054125581540114956463603240222497919384691718744014002554201602395969312999994159599536026359879060218056496345745457493919771337601177449899066579857630036350871090452649830775029695488575574985078428560054253180863725364147
e1 = 1697
C1 = [412629526163150748619328091306742267675740578011800062477174189782151273970783531227579758540364970485350157944321579108232221072397135934034064481497887079641131808838242743811511451355024436983050572020925065644355566434625618133203024215941534926113892937988520918939061441606915556516246057349589921494351383160036280826024605351878408056180907759973804117263002554923041750587548819746346813966673034182913325507826219961923932100526305289894965216608254252188398580139545189681875824089456195044984585824938384521905334289906422454152976834867304693292466676355760173232407753256256317546190171995276258924613533179898467683358934751999655196790168438343198229183747091108262988777659858609744709324571850262293294975336628234767258858873839342596887193772615000676401522431518310648303975593582965021189182246986957349253156736526071639973844039068996404290548474640668851856078201093335425412842295604919065487301340901573809617549185106072798799159726375235125260509158832996701927878713084753334549129580912412168594170659605421750204835970231909591063407612779337478065175988365401590396247576709343727196106058477166945670117868989025903023998142850338956985816131805349549059377047477131270847579095628384569645636821650, 494644347943710545224678831941589086572700792465459558770782213550069709458568349686998660541810166872034041584767487150140111151788221460027897193248273461607411027815984883969396220626358625041781558277804930212654296704055890683796941327712758797770820006623289146990000114915293539639766846910274034245607746230740851938158390562286057002223177609606376329007676845450142537930798148258428701466415483232670659815791064681384406494388237742330786225557303988025468036820082959712050733095860546860468575857084616069132051094882919253745234762029759124776348047587755897123575123506976140900565238840752841856713613368250071926171873213897914794115466890719123299469964019450899291410760762179836946570945555295288184698184555018368687708432612286248476073758067175481771199066581572870175460016017100414479346437034291784837132240891321931601494414908927713208448927221095745802380014441841139882391378410438764884597938773868771896252329517440068673532468372840830510218585255432000690265226016573313570977945083879214961394087065558376158826938257664840570952233832852869328785568175434516247720356520242602299510374317488182738732700078879665745909603766482100138001417023680647717824323143388857817595766172152883484274718248, 152942283599728307168144137370127212672611894072038732126041098102628831053000986759260271210671922070555948023688596575415822984026159010574404359474670428678518262175033880513984372909748992727828381694416776740981021730545374002974037896534944567124543272737618380646771071804878796585983783360553761828325817820260204820004421979881871027255562690952334900616675606524933557440263648233514757200263521499508373975003431306847453046714027687108396945719803444444954079308404947126216395526551292104722047878178373207886033071857277857997932255251315982837892164421298202073945919187779856785892717251746704537315003771369737854896595170485152591013676942418134278534037654467840633528916812275267230155352077736583130992587670941654695382287023971261529987384520843829695778029311786431227409189019205818351911572757145556993606643464336196802350204616056286497246016800105003143046120608673496196758720552776772796609670537056331996894322779267635281472481559819839042424017171718303214059720568484939239370144038161541354254182769979771948759413102933987773401644506930205164891773826513161783736386604783484446345744957119469799231796368324927570694496679453313927562345656690240414624431304646248599226046524702364131095964335, 79717988936247951265489157583697956031893477858854186991051529161879478488281744062318600470906120960002282886511477294555606503083169449335174864424180701080203993329996226566203834693869525797695969610065991941396723959032680019082506816443041598300477625793433080664346470586416385854692124426348587211026568667694805849554780794033764714016521711467557284846737236374990121316809833819996821592832639024026411520407330206281265390130763948165694574512140518775603040182029818771866749548761938870605590174330887949847420877829240131490902432602005681085180807294176837646062568094875766945890382971790015490163385088144673549085079635083262975154206269679142412897438231719704933258660779310737302680265445437771977749959110744959368586293082016067927548564967400845992380076107522755566531760628823374519718763740378295585535591752887339222947397184116326706799921515431185636740825707782742373783475781052674257292910213843986132987466810027275052416774693363446184518901899202502828670309452622347532932678874990809930682575738653876289384151496807194146308614368821006660626870989784697045160231069428458961107751207771093777394616856305293335603892178327520756554333365975114235981173451368131680404850832773147333013716920, 123111353650401158556639983459870663057297871992927053886971224773529636525110628183715748795987525113177540092814119928708272290370336537110381023134637759740716140969662183269370676630325583385284994943164692397459103195434968057377474610500216801375394703781249039351368816958227409657934091741509357152328382960684515093945552479461382281913961956745154260686029997827565075768703774895750561575155143606297116391666385705899138085693913246313778033627210312268959737394553510894720099165193981333775907531107232556909478156441457899797515694348816961762796703443502856101079430585547997496001098926600499728389113862894833789669213630332988693669889340482430613291490613803204484751470676686041002772556117213612152322606737150858116122936539131795111263513114569794532805886643087299918196635113037777138666914296986040549274559835214505300618256105508764026461518876579387159881983544667258537064954616097750399839661065797883103731694314852301848272092388637114950059216922969842082648527035538090054093890365647676119748995243416337805666557501345234056968476142608491830438065401219751688687373709390057521910942736632126729711606256158399963682990881473178216060827021373776598901281958527655543318413664277921492723185984, 36869806815936046911848195817405817350259890871483063184373728397968909458432625046025376290214729914038387534731762237978339011724858818860181178811639468996206294711495853807311240013786226884265118119546377272154555615363105236192878292703331473547623021744317034819416624562896226194523639793573028006666236271812390759036235867495803255905843636447252225413871038762657801345647584493917576263471587347202664391908570140389126903204602391093990827188675090199750617303773574821926387194478875191828814971296674530519321530805302667925998711835019806761133078403281404889374663875077339168901297819436499920958268483684335998301056068380228873524800383911402490807139268964095165069610454677558808756444381542173782815227920906224931028457073652453777424387873533280455944646592996920617956675786286711447540353883400282402551158169958389450168079568459656526911857835375748015814860506707921852997096156275804955989964215077733621769938075413007804223217091604613132253046399456747595300404564172224333936405545921819654435437072133387523533568472443532200069133022979195685683508297337961701169394794966256415112246587706103819620428258245999539040721929317130088874161577093962579487428358736401687123174207198251449851429295]
e2 = 599
C2 = [592169079372093727306100216011395857825646323934289480976073629037543922902098120901138454462177159996376654176248238979132528728327590301098966139983157980612320563496546128644967731000716697705104079039156276714872147463350811303393260622707024952543509891692246246277965823414460326811240048060543656588688604452353899779068825120910282167004715339763187734797180326976132213325054697165320479166356562518029805927741656605174809726397565772271562066078076105491745903986597877400370206718954975288721072048333678609055008135809089304229015364348490924974097403734627265297637171818849461766523691595241613878709865506436588268999163342945070495338153600520537498539457396582804692959296612715752573140296135784933206146091436617979599749774330699946637591406356289409716084034451049094715202196203486088368791744107629271647320273259836915312794297246589501008666299165717722507702866033454215783240025504356157664454861755286285777763585177751796252655008206383024707883077513745863312079349790275094080707502392866946325796914450602264462588722052297430827681750827349094323968337670311272933785838850649376115667223821665435911506351891489985627506615492005617098615432522564204152887767244129985681083657783356557756654335186, 373940646416832740878733255707567753033716583448402000789202767511920210382830343955553654111486728333980557319799362514960627879016797491389812007768832730979916230647641872759001906846747977631675704310179448857128160385701185892914523053669366534408863734305635222625590986006420486092550427301086984563126480814987024980594613542978310129247678826691418335300577577527951623696426435497835228167084738007750914270251001921329521479047662848650808989996085600197309361410863238526802127877523767262921515150984998560136647154865791163316503073285223966216441025637452229043510097323724381056976302288136843260163922706692913035222445496716008888946581535004546355744211680390731257309941902587303353139951102244865270295414474488798335404630458489706639805186573874814586736746232358849677477533671968344154242963289415569487579895910660999043578737461300406937828924818002658292769882181668784501439254131996848948120781562158861495883827848139425862249576454689133681009549361314460818658995959098228995702202268649635363105549975932395335076521137604288520082040121286614922986554652700056148966514178935952363036963217619879899671383604638416567950421350546204434902113156720006282720889591288850271076074941927715678306057176, 527630926460622936571385649841758214453416849039412401087443444317101857090904711485538107058823056085840539073345920792871368232355475394571098380596835468509997340505604333730547799560998822989747473780307779717715522787724471724766494090783971030594671013168209717686720448579582618378459567979027822271918653169622428153856198907810040224340270362413432495029672123261375400927159831537760709974778708160583252613784358234858583174544777979242887938827573604837766801998381379999076416444683891078093889686055482709838668356120916040352123019019255084513769603803814947774554028717814638951416291274696771515474086351482107953150253616922787262398450376249126999644026382478413080973933173079111305142716133389111399235545279259017424722601848670061556859163943895466553927946412523750166582734005733378328468250568944945912238495877929717101722314678120172228493787964904072583905721074766711732215815561012960394537195757832959268603775112932862105945720853959285187521763557915356428113876893276879775603217718981852114599706699524551973934242045743122744146361596971245034059345915315495232135483464496114770357536576200511490922413208178149869347802988786513451486411409887164516065062084917556120712465074206435831498113605, 8786437178698940322877889807009957616777351844979869726962356553244050911283984280960665761649310895230455072977431415102053987735969326553978994853162483051544656873294555116009995592043183070208706258164840540599577072097104139505857517663273929851202628854185356185647194933800084230503413037858893307713037149307477830536758283681093517617820169181420796105338681582230788318108428132051793761014952837330456262272828627355701464740578197966332613127307037255647286823496355917642353327912440019621838870388091824748629637425759125214639885130163183752378908729773517053259212525494555880921052679512582051516604297098204363525081039382358483926727008679327719083138865969291911863630382097160230960738043575559330264018212774424527719153248563876760067931499029384228993253862501939337758514377472011933279273181144830381169849387893799390755052093069179605579485710343655570028592595882436632426527654452895431758715126580164902410286422637215098476316042367916779431052267545769495994723721129943616294879642305545894912914632980455031755879087401575310699765408473606166727137934224515998416625122213056208800095077933103150699272650116151674702438463062734472714004926103668378506804002740045547964716693536349447660850580, 205314962204511500352858372254132533167549960825498949618514841570703199264867431580754674275990554478140637041427842111391746883257447120035947621456863890934062044010795443059281736346976175772415034838334682726635263432655537852942177334888025283748611576171534251461847349566505628290587224150869640386437623371249743165260396675220683302142805646368906930575140628610003919131999295855501215111393294818218799982703289304596989070475000081175510085432290264502023736899104746316830742226946395027029820825791831870857382647221322734605026210073093918331247494307555600335550942340526536281372036612138713881098866303169425501998978400008829873080965592009371176208668290074288903681417933657472279670688597862835627506340169978450918788539270346340385928840299573889292189531738082166408734046381423516467694328971385421907314814283489322619386570046183556572383980777277173349209330683424343658179781015072259378576130442222984963071166207642585589822061597282467850868050737957726423713761694231879497037175627546427449730638216214828463003483408928375620315193290871300316930139260521382533279767663839278693750409419493280753368451508802658272220767624766390639285308433607255253282702383762149755935518922075584637512494819, 271453634732502613378948161256470991260052778799128789839624515809143527363206813219580098196957510291648493698144497567392065251244844074992734669490296293997386198359280316655904691639367482203210051809125904410431506925238374843856343243276508280641059690938930957474434518308646618959004216831130099873532714372402117796666560677624822509159287675432413016478948594640872091688482149004426363946048517480052906306290126242866034249478040406351940088231081456109195799442996799641647167552689564613346415247906852055588498305665928450828756152103096629274760601528737639415361467941349982213641454967962723875032638267311935042334584913897338553953961877439389588793074211502597238465542889335363559052368180212013206172712561221352833891640659020253527584706465205486408990762759230842192028381048563437724528409174790022752557512795782713125166158329880702730769957185428522011430144840232256419113631679343171680631630775266488738173707357123139368825087043785842169049943237537188129367275730984789479909103397937113837824575137021012333461552176687570010445744268373840742899299977372834041925102853718964831225250407279578465008537542659673685686242773379131904890865110699190451534445434533919127658976874721029586168106207]
a, b = exgcd(e1, e2)
with open('out', 'w') as f:
for c1, c2 in zip(C1, C2):
m = gmpy2.powmod(c1, a, n) * gmpy2.powmod(c2, b, n) % n
f.write(libnum.n2s(m))
with open('out', 'r') as f:
c = f.readlines()
with open('out', 'w') as f:
f.write('IA==\n'.join(c))
THIS FLAG IS HIDDEN. CAN YOU FIND IT OUT? DO YOU KNOW BASE64? YoungC THINK YOU ARE NOT THAT FAMILIAR WITH BASE64. Base64 is a group of similar binary-to-text encoding schemes that represent binary data in an ASCII string format by translating it into a radix-64 representation. The term Base64 originates from a specific MIME content transfer encoding. The particular set of 64 characters chosen to represent the 64 place-values for the base varies between implementations. The general strategy is to choose 64 characters that are both members of a subset common to most encodings, and also printable. This combination leaves the data unlikely to be modified in transit through information systems, such as E-mail, that were traditionally not 8-bit clean.[1] For example, MIME's Base64 implementation uses A¨CZ, a¨Cz, and 0¨C9 for the first 62 values. Other variations share this property but differ in the symbols chosen for the last two values; an example is UTF-7.
看了半天没看懂这段话里面藏了什么flag。弃疗。
BUUCTF: [HDCTF2019]together
【附件】
给了两个 .pem 和flag文件。先读取pem：
➜ workspace rsa_solve --dumpkey --key pubkey1.pem --private
[*] n: 14853081277902411240991719582265437298941606850989432655928075747449227799832389574251190347654658701773951599098366248661597113015221566041305501996451638624389417055956926238595947885740084994809382932733556986107653499144588614105694518150594105711438983069306254763078820574239989253573144558449346681620784979079971559976102366527270867527423001083169127402157598183442923364480383742653117285643026319914244072975557200353546060352744263637867557162046429886176035616570590229646013789737629785488326501654202429466891022723268768841320111152381619260637023031430545168618446134188815113100443559425057634959299
[*] e: 2333
➜ workspace rsa_solve --dumpkey --key pubkey2.pem --private
[*] n: 14853081277902411240991719582265437298941606850989432655928075747449227799832389574251190347654658701773951599098366248661597113015221566041305501996451638624389417055956926238595947885740084994809382932733556986107653499144588614105694518150594105711438983069306254763078820574239989253573144558449346681620784979079971559976102366527270867527423001083169127402157598183442923364480383742653117285643026319914244072975557200353546060352744263637867557162046429886176035616570590229646013789737629785488326501654202429466891022723268768841320111152381619260637023031430545168618446134188815113100443559425057634959299
[*] e: 23333又是共模数攻击。
import gmpy2, libnum, base64
def exgcd(a, b):
if b==0: return 1, 0
x, y = exgcd(b, a%b)
return y, x-a//b*y
n = 14853081277902411240991719582265437298941606850989432655928075747449227799832389574251190347654658701773951599098366248661597113015221566041305501996451638624389417055956926238595947885740084994809382932733556986107653499144588614105694518150594105711438983069306254763078820574239989253573144558449346681620784979079971559976102366527270867527423001083169127402157598183442923364480383742653117285643026319914244072975557200353546060352744263637867557162046429886176035616570590229646013789737629785488326501654202429466891022723268768841320111152381619260637023031430545168618446134188815113100443559425057634959299
e1 = 2333
c1 = int.from_bytes(base64.b64decode(open('myflag1', 'rb').read()), 'big')
e2 = 23333
c2 = int.from_bytes(base64.b64decode(open('myflag2', 'rb').read()), 'big')
a, b = exgcd(e1, e2)
m = gmpy2.powmod(c1, a, n) * gmpy2.powmod(c2, b, n) % n
print(libnum.n2s(m))BUUCTF: [RoarCTF2019]babyRSA
【附件】
attachment.py 如下：
import sympy
import random
def myGetPrime():
A= getPrime(513)
print(A)
B=A-random.randint(1e3,1e5)
print(B)
return sympy.nextPrime((B!)%A)
p=myGetPrime()
#A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
#B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
q=myGetPrime()
#A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
#B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
r=myGetPrime()
n=p*q*r
#n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
c=pow(flag,e,n)
#e=0x1001
#c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
#so,what is the flag?由于 A1, B1 已知，我们尝试利用 A1, B1 推出 $p$.
威尔逊定理：$ p $为质数的充分必要条件是 $(p-1)! \equiv -1 \pmod p$.
于是 $(A-1)!\%A$ 是已知的，为 $(A-1)$. 故 $$ B! \equiv \frac{(A-1)!}{(B+1)\cdot (B+2)\cdots (A-1)} \equiv \frac{A-1}{(B+1)\cdot (B+2)\cdots (A-1)} \pmod a$$
$B$ 与 $A$ 的差距只有$10^5$，故分子、分母都是可以计算的。不难写出脚本：
from Crypto.Util.number import *
from functools import reduce
from sympy import nextprime
from libnum import n2s
def getFactor(x, mod):
return (mod-1) * reduce(lambda x,y: x*inverse(y, mod)%mod, [1] + [x for x in range(x+1, mod)]) % mod
A1 = 21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
B1 = 21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
p = nextprime(getFactor(B1, A1))
A2 = 16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
B2 = 16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
q = nextprime(getFactor(B2, A2))
n = 85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
assert(n%p == 0)
assert(n%q == 0)
r = n // p // q
e = 0x1001
c = 75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
m = pow(c, inverse(e, (p-1)*(q-1)*(r-1)), n)
print(n2s(m))BUUCTF: [GWCTF 2019]BabyRSA
【附件】
给出了加密脚本和 $N, m1, m2$. 加密脚本如下：
import hashlib
import sympy
from Crypto.Util.number import *
flag = 'GWHT{******}'
secret = '******'
assert(len(flag) == 38)
half = len(flag) / 2
flag1 = flag[:half]
flag2 = flag[half:]
secret_num = getPrime(1024) * bytes_to_long(secret)
p = sympy.nextprime(secret_num)
q = sympy.nextprime(p)
N = p * q
e = 0x10001
F1 = bytes_to_long(flag1)
F2 = bytes_to_long(flag2)
c1 = F1 + F2
c2 = pow(F1, 3) + pow(F2, 3)
assert(c2 < N)
m1 = pow(c1, e, N)
m2 = pow(c2, e, N)
output = open('secret', 'w')
output.write('N=' + str(N) + '\n')
output.write('m1=' + str(m1) + '\n')
output.write('m2=' + str(m2) + '\n')
output.close()
注意到 $p,q$ 是相邻的质数。由质数定理，它们的距离大约是 $\ln N \approx 1505$, 是可以爆破的。脚本如下：
import gmpy2, itertools
N = 636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
for q in itertools.count(gmpy2.iroot(N, 2)[0]-1):
if N % q == 0:
p = N // q
break
print(p)
print(q)
# p = 797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377747699
# q = 797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377748737它们的距离果然只有1038. 侧面印证了质数定理比较靠谱。既然现在 $p,q$ 都知道了，我们接着看 m1, m2 是如何生成的：
e = 0x10001
F1 = bytes_to_long(flag[:half])
F2 = bytes_to_long(flag[half:])
c1 = F1 + F2
c2 = pow(F1, 3) + pow(F2, 3)
assert(c2 < N)
m1 = pow(c1, e, N)
m2 = pow(c2, e, N)先解密出 $c1, c2$. 脚本如下：
e = 0x10001
d = gmpy2.invert(e, (p-1)*(q-1))
m1 = 90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
m2 = 487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546
c1 = pow(m1, d, N)
c2 = pow(m2, d, N)
print(c1) # 2732509502629189160482346120094198557857912754
print(c2) # 5514544075236012543362261483183657422998274674127032311399076783844902086865451355210243586349132992563718009577051164928513093068525554所以有了一个方程组：$$\begin{cases}c_1 = F_1 + F_2 \\ c_2 = F_1^3 + F_2^3 \end{cases}$$
逆用立方和公式，马上有$$\begin{cases}c_2 / c_1 = F_1^2 + F_2 ^ 2 - F_1F_2 \\ c_1^2 = F_1 ^ 2+F_2 ^ 2 + 2F_1F_2\end{cases} \quad \Rightarrow \quad R = F_1F_2 = \frac{c_1^2 - c_2/c_1 }{3} $$
既然 $F_1+F_2, F_1F_2$ 均已知，则直接构造 $$Q = F_1 - F_2 = \sqrt{(F_1-F_2)^2} = \sqrt{c_1^ 2 - 4R}$$
于是 $F_1+F_2, F_1-F_2$ 都知道了，可以得到 $F_1, F_2$. 最后完整的解题脚本如下：
import gmpy2, itertools, libnum
N = 636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
for q in itertools.count(gmpy2.iroot(N, 2)[0]-1):
if N % q == 0:
p = N // q
break
e = 0x10001
d = gmpy2.invert(e, (p-1)*(q-1))
m1 = 90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
m2 = 487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546
c1 = pow(m1, d, N)
c2 = pow(m2, d, N)
assert(c2 % c1 == 0)
assert((c1*c1 - c2//c1) % 3 == 0)
R = (c1*c1 - c2//c1) // 3
assert(gmpy2.iroot(c1*c1 - 4*R, 2)[1] == True)
Q = gmpy2.iroot(c1*c1 - 4*R, 2)[0]
assert((c1+Q) % 2 == 0)
F1 = (c1+Q) // 2
F2 = (c1-Q) // 2
print(libnum.n2s(F1) + libnum.n2s(F2))BUUCTF: RSA4
【附件】
给了三组 $N, c$. 出题人是个铁憨憨，$N, c$ 都是由五进制给出的，而题目中竟然不注明。是在比谁想象力好🐴？现在手上有三组$N, c$，其中 $N$ 两两互质。猜测它们用同一个 $e$ 加密、猜测这个 $e$ 非常小，就猜它恰好为 3 罢。在这么多猜测的基础上，有了下面的方程组：$$\begin{cases} m^3 \equiv c_1 \pmod {N_1} \\ m^3 \equiv c_2 \pmod {N_2} \\ m^3 \equiv c_2 \pmod {N_2} \end{cases}$$
用中国剩余定理得到 $m^3 \bmod (N_1N_2N_3)$，由于$m < N$，故直接开三次方即可。这称为低加密指数广播攻击。
import gmpy2, itertools, libnum
from functools import reduce
N1 = '331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004'
c1 = '310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243'
N1, c1 = map(lambda x:int(x, base=5), (N1, c1))
N2 = '302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114'
c2 = '112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344'
N2, c2 = map(lambda x:int(x, base=5), (N2, c2))
N3 = '332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323'
c3 = '10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242'
N3, c3 = map(lambda x:int(x, base=5), (N3, c3))
def CRT(r, mod):
M = reduce(lambda x,y:x*y, mod)
ans = 0
for i in range(len(r)):
ans += r[i] * M//mod[i] * gmpy2.invert(M//mod[i], mod[i])
return ans % M
m = gmpy2.iroot(CRT([c1, c2, c3], [N1, N2, N3]), 3)
assert m[1] == True
print(libnum.n2s(m[0]))BUUCTF [BJDCTF2020]rsa_output
得到的 flag 请包上 flag{} 提交。来源：https://github.com/BjdsecCA/BJDCTF2020
【附件】
共模数攻击。
import gmpy2, libnum
def exgcd(a, b):
if b==0: return 1, 0
x, y = exgcd(b, a%b)
return y, x-a//b*y
N = 21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111
e1 = 2767
e2 = 3659
message1 = 20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599
message2 = 11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227
x, y = exgcd(e1, e2)
assert x*e1 + y*e2 == 1
m = gmpy2.powmod(message1, x, N) * gmpy2.powmod(message2, y, N) % N
print(libnum.n2s(m))BUUCTF: [BJDCTF2020]easyrsa
得到的 flag 请包上 flag{} 提交。来源：https://github.com/BjdsecCA/BJDCTF2020
【附件】
给出了 $c, z, n$. 生成方式是：
p=getPrime(1024)
q=getPrime(1024)
e=65537
n=p*q
z=Fraction(1,Derivative(arctan(p),p))-Fraction(1,Derivative(arth(q),q))
m=bytes_to_long(flag)
c=pow(m,e,n)主要问题在 $z$ 上。我们需要前置技能：$$\frac{d}{dx} \arctan(x) = \frac1{1+x^2} \qquad \frac{d}{dx}\text{artanh}(x) = \frac1{1-x^ 2}$$
从而 $z$ 就是 $p^2 + q^ 2$. 于是可以算出 $p, q$.
import gmpy2, libnum, codecs
c = 7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035
z = 32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482
n = 15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441
assert gmpy2.iroot(z + 2*n, 2)[1] == True
x = gmpy2.iroot(z + 2*n, 2)[0]
assert gmpy2.iroot(z - 2*n, 2)[1] == True
y = gmpy2.iroot(z - 2*n, 2)[0]
assert (x+y)%2 == 0
p = (x+y) // 2
q = (x-y) // 2
m = gmpy2.powmod(c, gmpy2.invert(65537, (p-1)*(q-1)), p*q)
print(libnum.n2s(m))BUUCTF: [NCTF2019]babyRSA
【附件】
给出了 $d, c$, 加密脚本如下：
p = getPrime(1024)
q = nextPrime(p)
n = p * q
e = 0x10001
d = inverse(e, (p-1) * (q-1))
c = pow(bytes_to_long(flag.encode()), e, n)与前一道 $|p-q|$ 极小的题不同，这题没有给 $n$，但是给了 $d$. 那我们现在考虑 $e\cdot d - 1$，它一定是 $\varphi(n)$ 的倍数。来看其分解结果：
$p, q$ 都是 $1024$ 位，所以 $(p-1)(q-1)$ 是 2048 位。现在计算出来的 $e\cdot d - 1$ 是2064位，相差约为65536倍。换句话讲：$$e\cdot d - 1 = k\varphi(n)\quad k \approx 65536$$
直接枚举 $k$，然后看得到的 $\frac{ed-1}{k}$ 是不是2048位。脚本如下：
G = d*e - 1
maybe = []
for k in range(2**15, 2**17):
if G % k == 0 and (G//k).bit_length() == 2048:
maybe.append(G//k)
print(k)最后得到了71个可能的 $\varphi(n)$. 于是现在考虑的问题是：已知 $(p-1)(q-1)$, 如何得到 $n$?
既然 $p\approx q$，那么 $(p-1) \approx (q-1)$，从而 $\varphi(n)$ 应该能拆成两个极为接近的数之乘积。于是可以爆破。
def fact(n):
for x in range(gmpy2.iroot(n, 2)[0], gmpy2.iroot(n, 2)[0]+2000):
if n%x == 0:
y = n // x
if gmpy2.is_prime(x+1) and gmpy2.is_prime(y+1):
return (y, x)
print(len(maybe))
pq = []
for x in maybe:
res = fact(x)
if res: pq.append(res)
print(pq)得到了唯一的 $(p,q)$. 现在可以直接解密了。完整脚本：
import gmpy2, libnum, codecs
c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804
d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
e = 0x10001
G = d*e - 1
maybe = []
for k in range(2**15, 2**17):
if G % k == 0 and (G//k).bit_length() == 2048:
maybe.append(G//k)
# print(k)
def fact(n):
for x in range(gmpy2.iroot(n, 2)[0], gmpy2.iroot(n, 2)[0]+2000):
if n%x == 0:
y = n // x
if gmpy2.is_prime(x+1) and gmpy2.is_prime(y+1):
return (y+1, x+1)
pq = []
for x in maybe:
res = fact(x)
if res: pq.append(res)
p, q = pq[0]
assert(q == gmpy2.next_prime(p))
m = gmpy2.powmod(c, d, p*q)
print(libnum.n2s(m))BUUCTF: [RoarCTF2019]RSA
【附件】
给定了 $A,n,c$ 且有 $$ A = [(y\% x)^{5} \% (x\%y)] ^ {2019} + y^{316} + \frac{y+1}{x} $$
注意到 $x|(y+1)$, 即 $y\equiv -1 \pmod x$. 由于 $y+1$ 比 $x$ 大，故如果不出意外，应该有$x\% y = x$. 于是 $[(y\% x) ^ 5 \% (x\%y)]^{2019} = (x-1) ^ {2019}$. 从而$$A = (x-1)^{2019} + y ^ {316} + \frac{y+1}{x}$$
观察 $A$ 的值，它是一个2015个bit的数。而 $A \geq (x-1)^{2019}$, 显然只有 $x\leq 2$ 才能实现。讨论 $x=1$ 和 $x=2$ 这两种情况，发现有唯一解 $(x, y) = (2, 83)$. 回过头看 $p, q$ 的生成方式：
p = next_prime(z*166)
q = next_prime(z) $n = p\cdot q$是知道的。$p$ 大约是 $q$ 的166倍，那么 $p/166, q$ 一定在 $\sqrt{n/166}$ 附近。于是可以爆破出 $p,q$. 但是这题没说 $e$ 等于多少，猜测 e=0x10001, 拿到了flag. 应该是题面忘记写了。完整脚本如下：
import gmpy2, libnum, codecs, itertools
x, y = 2, 83
A=(((y%x)**5)%(x%y))**2019+y**316+(y+1)//x
assert A == 2683349182678714524247469512793476009861014781004924905484127480308161377768192868061561886577048646432382128960881487463427414176114486885830693959404989743229103516924432512724195654425703453612710310587164417035878308390676612592848750287387318129424195208623440294647817367740878211949147526287091298307480502897462279102572556822231669438279317474828479089719046386411971105448723910594710418093977044179949800373224354729179833393219827789389078869290217569511230868967647963089430594258815146362187250855166897553056073744582946148472068334167445499314471518357535261186318756327890016183228412253724
n = 117930806043507374325982291823027285148807239117987369609583515353889814856088099671454394340816761242974462268435911765045576377767711593100416932019831889059333166946263184861287975722954992219766493089630810876984781113645362450398009234556085330943125568377741065242183073882558834603430862598066786475299918395341014877416901185392905676043795425126968745185649565106322336954427505104906770493155723995382318346714944184577894150229037758434597242564815299174950147754426950251419204917376517360505024549691723683358170823416757973059354784142601436519500811159036795034676360028928301979780528294114933347127
c = 41971850275428383625653350824107291609587853887037624239544762751558838294718672159979929266922528917912189124713273673948051464226519605803745171340724343705832198554680196798623263806617998072496026019940476324971696928551159371970207365741517064295956376809297272541800647747885170905737868568000101029143923792003486793278197051326716680212726111099439262589341050943913401067673851885114314709706016622157285023272496793595281054074260451116213815934843317894898883215362289599366101018081513215120728297131352439066930452281829446586562062242527329672575620261776042653626411730955819001674118193293313612128
for q in itertools.count(gmpy2.iroot(n//166,2)[0]):
if n%q == 0:
break
p = n // q
e = 65537
m = gmpy2.powmod(c, gmpy2.invert(e, (p-1)*(q-1)), n)
print(libnum.n2s(m))BUUCTF: [BJDCTF2020]RSA
得到的 flag 请包上 flag{} 提交。来源：https://github.com/BjdsecCA/BJDCTF2020
【附件】
给了生成程序和程序输出。
from Crypto.Util.number import getPrime,bytes_to_long
flag=open("flag","rb").read()
p=getPrime(1024)
q=getPrime(1024)
assert(e<100000)
n=p*q
m=bytes_to_long(flag)
c=pow(m,e,n)
print c,n
print pow(294,e,n)
p=getPrime(1024)
n=p*q
m=bytes_to_long("BJD"*32)
c=pow(m,e,n)
print c,n注意到最后输出的 $c,n$，我们已知明文，但不知道 $e$. 考虑到 $e < 100000$, 故直接枚举$e$，用最后那组 $(c, n)$ 来检验。爆破出 $e=52361$.
c = 979153370552535153498477459720877329811204688208387543826122582132404214848454954722487086658061408795223805022202997613522014736983452121073860054851302343517756732701026667062765906277626879215457936330799698812755973057557620930172778859116538571207100424990838508255127616637334499680058645411786925302368790414768248611809358160197554369255458675450109457987698749584630551177577492043403656419968285163536823819817573531356497236154342689914525321673807925458651854768512396355389740863270148775362744448115581639629326362342160548500035000156097215446881251055505465713854173913142040976382500435185442521721
n = 12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047
m = int.from_bytes(b'BJD'*32, 'big')
for e in range(100000):
if c == gmpy2.powmod(m, e, n):
break
print(e)现在我们知道了第一组的 $n, e, c$. 还知道一个信息：294的编码，不过这个没有什么用，只能用来检验一下我们的 $e$ 是否正确。但是有一个至关重要的信息：$n_1 = p_1 * q, n_2 = p_2* q$, 这里的 $q$ 是没有变的。那么对两个 $n$ 求gcd，得到的显然就是$q$；从而也可以推出$p_1$了，于是可以拿到flag. 最终脚本如下：
import gmpy2, libnum, codecs, itertools
c = 979153370552535153498477459720877329811204688208387543826122582132404214848454954722487086658061408795223805022202997613522014736983452121073860054851302343517756732701026667062765906277626879215457936330799698812755973057557620930172778859116538571207100424990838508255127616637334499680058645411786925302368790414768248611809358160197554369255458675450109457987698749584630551177577492043403656419968285163536823819817573531356497236154342689914525321673807925458651854768512396355389740863270148775362744448115581639629326362342160548500035000156097215446881251055505465713854173913142040976382500435185442521721
n2 = 12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047
m = int.from_bytes(b'BJD'*32, 'big')
for e in range(100000):
if c == gmpy2.powmod(m, e, n2):
break
R = 381631268825806469518166370387352035475775677163615730759454343913563615970881967332407709901235637718936184198930226303761876517101208677107311006065728014220477966000620964056616058676999878976943319063836649085085377577273214792371548775204594097887078898598463892440141577974544939268247818937936607013100808169758675042264568547764031628431414727922168580998494695800403043312406643527637667466318473669542326169218665366423043579003388486634167642663495896607282155808331902351188500197960905672207046579647052764579411814305689137519860880916467272056778641442758940135016400808740387144508156358067955215018
c = 12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120
n1 = 13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037
assert pow(294, e, n1) == R
q = gmpy2.gcd(n1, n2)
p = n1 // q
assert p * q == n1
m = gmpy2.powmod(c, gmpy2.invert(e, (p-1)*(q-1)), n1)
print(libnum.n2s(m))BUUCTF: [V&N2020 公开赛]easy_RSA
【附件】
注意到 $p, q, r$ 加上1均有一大堆小因子，故采用 William's p+1 算法来分解掉 $ n $.
In [1]: import primefac
In [2]: primefac.williams_pp1(n=794137173995657728016066441938374096751691893878130661081714974498837928056135 ...: 903901650867936580610872219815719905880789270383755828067871142041124291405965805536634812310647333518 ...: 650561741895663078064989494523334598527947110688863517725601146897908332060510325617844699323032044379 ...: 024028515826023692651904241337820429851471489072532583176928150553078773992200736702688395954423956888 ...: 6349070557272869042275528961483412544495589811933856131557221673534170105409)
Out[2]: mpz(102634610559478918970860957918259981057327949366949344137104804864768237961662136189827166317524151288799657758536256924609797810164397005081733039415393L)现在知道了 $p$， 又有 $q^d \equiv 1 \pmod {p ^ 2}$，故$ q^2 \bmod {p^ 2}$ 可以求出来。而 $p, q$ 差不多大，因此可以直接爆破出 $q$.
有了 $p, q$，于是也可以得到 $r$. 解密掉 $cipher$ 得到 $c$，有 $c = m^2 \bmod r$. 这是一个二次剩余，用现成的脚本就行了。
from libnum import *
from gmpy2 import *
import itertools
p = 102634610559478918970860957918259981057327949366949344137104804864768237961662136189827166317524151288799657758536256924609797810164397005081733039415393
n = 7941371739956577280160664419383740967516918938781306610817149744988379280561359039016508679365806108722198157199058807892703837558280678711420411242914059658055366348123106473335186505617418956630780649894945233345985279471106888635177256011468979083320605103256178446993230320443790240285158260236926519042413378204298514714890725325831769281505530787739922007367026883959544239568886349070557272869042275528961483412544495589811933856131557221673534170105409
d = 7515987842794170949444517202158067021118454558360145030399453487603693522695746732547224100845570119375977629070702308991221388721952258969752305904378724402002545947182529859604584400048983091861594720299791743887521228492714135449584003054386457751933095902983841246048952155097668245322664318518861440
q2 = invert(d, p*p)
for k in itertools.count(0):
res = iroot(q2+k*p*p, 2)
if res[1] == True:
break
q = res[0]
r = n // (p*q)
assert n == p*q*r
cip = 1618155233923718966393124032999431934705026408748451436388483012584983753140040289666712916510617403356206112730613485227084128314043665913357106301736817062412927135716281544348612150328867226515184078966397180771624148797528036548243343316501503364783092550480439749404301122277056732857399413805293899249313045684662146333448668209567898831091274930053147799756622844119463942087160062353526056879436998061803187343431081504474584816590199768034450005448200
phi = (p-1)*(q-1)*(r-1)
inv = invert(0x10001, phi)
c = powmod(cip, inv, n)
assert (p.bit_length(),q.bit_length(), r.bit_length()) == (505, 512, 512)
assert powmod(c, (r-1)//2, r) == 1
def modular_sqrt(a, p):
""" Find a quadratic residue (mod p) of 'a'. p
must be an odd prime.
Solve the congruence of the form:
x^2 = a (mod p)
And returns x. Note that p - x is also a root.
0 is returned is no square root exists for
these a and p.
The Tonelli-Shanks algorithm is used (except
for some simple cases in which the solution
is known from an identity). This algorithm
runs in polynomial time (unless the
generalized Riemann hypothesis is false).
"""
# Simple cases
#
if legendre_symbol(a, p) != 1:
return 0
elif a == 0:
return 0
elif p == 2:
return 0
elif p % 4 == 3:
return pow(a, (p + 1) // 4, p)
# Partition p-1 to s * 2^e for an odd s (i.e.
# reduce all the powers of 2 from p-1)
#
s = p - 1
e = 0
while s % 2 == 0:
s //= 2
e += 1
# Find some 'n' with a legendre symbol n|p = -1.
# Shouldn't take long.
#
n = 2
while legendre_symbol(n, p) != -1:
n += 1
# Here be dragons!
# Read the paper "Square roots from 1; 24, 51,
# 10 to Dan Shanks" by Ezra Brown for more
# information
#
# x is a guess of the square root that gets better
# with each iteration.
# b is the "fudge factor" - by how much we're off
# with the guess. The invariant x^2 = ab (mod p)
# is maintained throughout the loop.
# g is used for successive powers of n to update
# both a and b
# r is the exponent - decreases with each update
#
x = pow(a, (s + 1) // 2, p)
b = pow(a, s, p)
g = pow(n, s, p)
r = e
while True:
t = b
m = 0
for m in range(r):
if t == 1:
break
t = pow(t, 2, p)
if m == 0:
return x
gs = pow(g, 2 ** (r - m - 1), p)
g = (gs * gs) % p
x = (x * gs) % p
b = (b * g) % p
r = m
def legendre_symbol(a, p):
""" Compute the Legendre symbol a|p using
Euler's criterion. p is a prime, a is
relatively prime to p (if p divides
a, then a|p = 0)
Returns 1 if a has a square root modulo
p, -1 otherwise.
"""
ls = pow(a, (p - 1) // 2, p)
return -1 if ls == p - 1 else ls
m = modular_sqrt(c, r)
n2s(m)