[MTCTF 2021]hamburgerRSA
task:
from Crypto.Util.number import *
flag = open('flag.txt').read()
nbit = 64
while True:
p, q = getPrime(nbit), getPrime(nbit)
PP = int(str(p) + str(p) + str(q) + str(q))
QQ = int(str(q) + str(q) + str(p) + str(p))
if isPrime(PP) and isPrime(QQ):
break
n = PP * QQ
m = bytes_to_long(flag.encode())
c = pow(m, 65537, n)
print('n =', n)
print('c =', c)
# n = 177269125756508652546242326065138402971542751112423326033880862868822164234452280738170245589798474033047460920552550018968571267978283756742722231922451193
# c = 47718022601324543399078395957095083753201631332808949406927091589044837556469300807728484035581447960954603540348152501053100067139486887367207461593404096
analysis:
这里比较特殊的就是P，Q的生成方式：P = int(str(p) + str(p) + str(q) + str(q));Q = int(str(q) + str(q) + str(p) + str(p)).
由于P，Q的特殊生成方式，数位上出现了密码漏洞.
\[\begin{flalign} &设len(str(p))=x,len(str(q)) = y.则\\ &P=10^{x+2y}p+10^{2y}p+10^yq+q\\ &Q=10^{2x+y}q+10^{2x}q+10^xp+p\\ &n=10^{3x+3y}pq+10^{3x+2y}pq+10^{2x+3y}pq+\cdots+10^xpq+10^ypq+pq& \end{flalign} \]通过比较，我们发现n就是由p*q的10的k次方的和相加而成.
那么这样就会有数学逻辑漏洞了，即n的最高位就会有一部分与p*q的高位相同，而n的一部分最低位就会与p*q的低位相同.
例如：
# -*- coding: utf-8 -*-
# @Author : chen_xing
# @Time : 2024/12/17 下午6:11
# @File : temp.py
# @Software: PyCharm
from Crypto.Util.number import *
p = getPrime(64)
q = getPrime(64)
PP = int(str(p) + str(p) + str(q) + str(q))
QQ = int(str(q) + str(q) + str(p) + str(p))
n = PP * QQ
print(f"p = {p}")
print(f"q = {q}")
print(f"p * q = {p * q}")
print(f"n = {n}")
"""
p = 14972780987766519271
q = 13922756253909237863
p * q = 208462380135839642072844110687912357873
n = 208462380135839642077013358290629150714519531182993170255547970993784850736285903275458756146666228755186392069563289244777284517718311216672844110687912357873
"""
但是由于前后两项有重合，所以我们需要判断能否直接得出这样的p*q.
经实验，getPrime(64)的十进制的长度是19或20.那么p*q的十进制长度就是38或39.n的十进制位数是156.
以下进行理论证明：
现在我们需要做的就是，怎么能通过n的最高位或者最低位成功还原p*q，如果是在进位的最糟糕的情况下，我们需要爆破几位？
如若：x=y=20，则3*x+3*y+len(p*q)至少是159；
x=y=19,则3*x+3*y+len(p*q)最多是153.只有当x=19,y=20或x=20,y=19的时候才能满足题目中len(str(n))=156的情况.
为了避免借位的情况发生，统一解密脚本，我们有如下：
取n前18位，后18位，由于36位一定低于p*q的位数，所以我们一定不会错过正确的解，之后从中由1位向4位进行爆破.
exp
# -*- coding: utf-8 -*-
# @Author : chen_xing
# @Time : 2024/12/17 下午5:33
# @File : [MTCTF 2021]hamburgerRSA.py
# @Software: PyCharm
from Crypto.Util.number import *
from sage.all import *
e = 65537
def decryRSA(c,p,q,e):
return long_to_bytes(pow(c,inverse(e,(p-1)*(q-1)),p*q))
def Decry(n,c):
high = str(n)[:18]
low = str(n)[-18:]
for i in range(10000):
p_q = int(high + str(i) + low)
roots = factor(p_q)
if len(roots) == 2 and roots[0][0].nbits() == 64:
print(f"p = {roots[0][0]}\nq = {roots[1][0]}")
p,q = int(roots[0][0]),int(roots[1][0])
if isPrime(p) and isPrime(q): # 有可能会有多解的情况，所以需要判断p,q是否是素数
P = int(str(p) + str(p) + str(q) + str(q))
Q = int(str(q) + str(q) + str(p) + str(p))
return decryRSA(c,P,Q,e)
n = 177269125756508652546242326065138402971542751112423326033880862868822164234452280738170245589798474033047460920552550018968571267978283756742722231922451193
c = 47718022601324543399078395957095083753201631332808949406927091589044837556469300807728484035581447960954603540348152501053100067139486887367207461593404096
print(Decry(n,c))
"""
p = 9788542938580474429
q = 18109858317913867117
b'flag{f8d8bfa5-6c7f-14cb-908b-abc1e96946c6}'
"""
Hamul Challenge
https://ctftime.org/writeup/29693
task:
#!/usr/bin/env python3
from Crypto.Util.number import *
from flag import flag
nbit = 64
while True:
p, q = getPrime(nbit), getPrime(nbit)
P = int(str(p) + str(q))
Q = int(str(q) + str(p))
PP = int(str(P) + str(Q))
QQ = int(str(Q) + str(P))
if isPrime(PP) and isPrime(QQ):
break
n = PP * QQ
m = bytes_to_long(flag.encode('utf-8'))
if m < n:
c = pow(m, 65537, n)
print('n =', n)
print('c =', c)
# n = 98027132963374134222724984677805364225505454302688777506193468362969111927940238887522916586024601699661401871147674624868439577416387122924526713690754043
# c = 42066148309824022259115963832631631482979698275547113127526245628391950322648581438233116362337008919903556068981108710136599590349195987128718867420453399
analysis:更改一下P，Q的生成方式即可.
exp:
# -*- coding: utf-8 -*-
# @Author : chen_xing
# @Time : 2024/12/17 下午8:00
# @File : Hamul Challenge.py
# @Software: PyCharm
from Crypto.Util.number import *
from sage.all import *
e = 65537
def decryRSA(c,p,q,e):
return long_to_bytes(pow(c,inverse(e,(p-1)*(q-1)),p*q))
def Decry(n,c):
high = str(n)[:18]
low = str(n)[-18:]
for i in range(10000):
p_q = int(high + str(i) + low)
roots = factor(p_q)
if len(roots) == 2 and roots[0][0].nbits() == 64:
print(f"p = {roots[0][0]}\nq = {roots[1][0]}")
p,q = int(roots[0][0]),int(roots[1][0])
if isPrime(p) and isPrime(q): # 有可能会有多解的情况，所以需要判断p,q是否是素数
P = int(str(p) + str(q) + str(q) + str(p))
Q = int(str(q) + str(p) + str(p) + str(q))
return decryRSA(c,P,Q,e)
n = 98027132963374134222724984677805364225505454302688777506193468362969111927940238887522916586024601699661401871147674624868439577416387122924526713690754043
c = 42066148309824022259115963832631631482979698275547113127526245628391950322648581438233116362337008919903556068981108710136599590349195987128718867420453399
print(Decry(n,c))
"""
p = 9324884768249686093
q = 10512422984265378151
b'CCTF{wH3Re_0Ur_Br41N_Iz_5uP3R_4CtIVe_bY_RSA!!}'
"""