攻击阐述
我们用b'\x00'替换消息中的x这样就有了(m+x)^e mod n=c
m知道一部分x是b'\x00\x00******'未知的(e,n)是公钥,c是密文
问题变为如何找到x
Coppersmith可以解决了这个问题
(这种题本质上就是已知m高位Coppersmith求小根的变体)
攻击成功条件
- $e = 3$
- $x < N^{1/e}$
题目-1
- ! squ1rrel CTF 2024
#Hmm? What's wrong with using the same flag format again? Whisper it in my ear so they don't hear.
n=103805634552377307340975059685101156977551733461056876355507089800229924640064014138267791875318149345634740763575673979991819014964446415505372251293888861031929442007781059010889724977253624216086442025183181157463661838779892334251775663309103173737456991687046799675461756638965663330282714035731741912263
e=3
ct=24734873977910637709237800614545622279880260333085506891667302143041484966318230317192234785987158021463825782079898979505470029030138730760671563038827274105816021371073990041986605112686349050253522070137824687322227491501626342218176173909258627357031402590581822729585520702978374712113860530427142416062思路
- 我们可能第一时间想到是小明文攻击,但是尝试解题发现求不出来
from Crypto.Util.number import *
from gmpy2 import iroot
n = 103805634552377307340975059685101156977551733461056876355507089800229924640064014138267791875318149345634740763575673979991819014964446415505372251293888861031929442007781059010889724977253624216086442025183181157463661838779892334251775663309103173737456991687046799675461756638965663330282714035731741912263
e = 3
ct = 24734873977910637709237800614545622279880260333085506891667302143041484966318230317192234785987158021463825782079898979505470029030138730760671563038827274105816021371073990041986605112686349050253522070137824687322227491501626342218176173909258627357031402590581822729585520702978374712113860530427142416062
m = iroot(ct,3)[0]
print(long_to_bytes(m))
# b"\x14\xd0j\x13\x18\xfe\xfc\x8d\x81.\xcf\xda\xf2)\x81'\xf4G\x95\xf1\xa3Y\xbe\x07\x98B\x86W\x12\xc0\x08\xb0\x87\x82:\xbb\xca\x81h\x9e\xc0\x8a}"- 但我们可以根据描述:用相同的标志?我们不难知道$flag$前缀
squ1rrel{ - 这道题其实是另一种标准的RSA攻击,具体来说的,其实是Coppersmith的一种变体,称为刻板消息攻击(Stereotyped messages attack)或者说已知明文高位攻击
- 从本质上讲,这个攻击是在我们知道明文的形式是
squ1rrel{XX...XX} - 而Coppersmith的攻击使我们能够解密它
i用于穷举$flag$的长度,如果给了可以直接填进去用
解答
- !! 解法-1
n = 103805634552377307340975059685101156977551733461056876355507089800229924640064014138267791875318149345634740763575673979991819014964446415505372251293888861031929442007781059010889724977253624216086442025183181157463661838779892334251775663309103173737456991687046799675461756638965663330282714035731741912263
e = 3
c = 24734873977910637709237800614545622279880260333085506891667302143041484966318230317192234785987158021463825782079898979505470029030138730760671563038827274105816021371073990041986605112686349050253522070137824687322227491501626342218176173909258627357031402590581822729585520702978374712113860530427142416062
prfx = b'squ1rrel{'
for i in range(100):
t = prfx + b'\x00'*i + + b'}'
m = int.from_bytes(t, byteorder='big')
P.<x> = PolynomialRing(Zmod(n), implementation='NTL')
pol = (m + x)^e - c
roots = pol.small_roots(epsilon=1/30)
print(i, "Potential solutions:")
for root in roots:
print(root)
print(bytes.fromhex(hex(m+int(root)%n)[2:]))
#squ1rrel{wow_i_was_betrayed_by_my_own_friend}- !! 解法-2
from sage.all import *
n = 103805634552377307340975059685101156977551733461056876355507089800229924640064014138267791875318149345634740763575673979991819014964446415505372251293888861031929442007781059010889724977253624216086442025183181157463661838779892334251775663309103173737456991687046799675461756638965663330282714035731741912263
exp = 3
c = 24734873977910637709237800614545622279880260333085506891667302143041484966318230317192234785987158021463825782079898979505470029030138730760671563038827274105816021371073990041986605112686349050253522070137824687322227491501626342218176173909258627357031402590581822729585520702978374712113860530427142416062
known = b"squ1rrel{"
known_int = int.from_bytes(known, byteorder='big')
for i in range(100):
try:
x = PolynomialRing(Zmod(n), 'x').gen()
f = (known_int * 2**(i * 8) + x)**exp - c
roots = f.small_roots(X=2**(i * 8), beta=0.5)
if roots:
ans = roots[0]
unknown_part = int(ans).to_bytes((i + 1), byteorder='big')
print(known.decode() + unknown_part.decode())
break
except:
continue
#squ1rrel{wow_i_was_betrayed_by_my_own_friend}题目-2
from Crypto.Util.number import *
from secret import flag
flag_start = b'flag{t'
flag_end = b'}'
p = getPrime(456)
q = getPrime(456)
e = 3
n = p * q
flag = b'flag{t****************}'
flag_int = bytes_to_long(flag)
m = flag[6:-1]
assert flag_int ** e > n # 不给这个条件你也应该知道
t = b'\x00' * (len(m))
pad = bytes_to_long(t)
c = pow((flag_int+pad),e,n)
print(f'n = {n}')
print(f'c = {c}')
'''
n = 15198997803601307326483182753401553751107030400663919854381663609601066220459849413924313482180354810070491802144431035961020221185817362006013303785963614208654863928227963717321258650220354346657611711515631415979360341600648357039818518380073738588049931038623009355815437
c = 13372780607812687832430575693779681742524553489911373152395085032375134765008965073417747041590968756237889308887046493756435743737100866647029135622665354398233971261261078947167452569261788042034543984545405209320829950091369679478346674657183902385231489619055114151016899
'''思路
- 看上去很像小明文攻击,但是根据
assert flag_int ** e > n显然小明文攻击无效 - 因为必须确保密文不会超过模数
c=m^e mod n才可以直接开方 - 这是典型的RSA Attack: Stereotyped message attack
- 假如我在这里明确了$flag$的长度(40),我们可以直接通过已知m高位Coppersmith方法求小根,不过由于没说$flag$的长度,而且还用了
m = flag[6:-1]裁切以确定t的大小,所以可以通过遍历字节数来求 - 这里的
\x00相当于占位符,用于穷举$flag$的长度
解答
n = 15198997803601307326483182753401553751107030400663919854381663609601066220459849413924313482180354810070491802144431035961020221185817362006013303785963614208654863928227963717321258650220354346657611711515631415979360341600648357039818518380073738588049931038623009355815437
c = 13372780607812687832430575693779681742524553489911373152395085032375134765008965073417747041590968756237889308887046493756435743737100866647029135622665354398233971261261078947167452569261788042034543984545405209320829950091369679478346674657183902385231489619055114151016899
e = 3
flag_start = b'flag{t'
flag_end = b'}'
for i in range(100):
t = flag_start + b'\x00'*i + flag_end
m = int.from_bytes(t, byteorder='big')
P.<x> = PolynomialRing(Zmod(n), implementation='NTL')
pol = (m + x)^e - c
roots = pol.small_roots(epsilon=1/30)
print(i, "Potential solutions:")
for root in roots:
print(root)
print(bytes.fromhex(hex(m+int(root)%n)[2:]))
'''
33 Potential solutions:
3091325547141372540146599315252335874790320352118005219426376315454979073888185088
b'flag{thI5_1s_Stere0typed_mes5age_att4ck}'
'''- 验证一下
m = 3091325547141372540146599315252335874790320352118005219426376315454979073888185088
print(long_to_bytes(m))
#hI5_1s_Stere0typed_mes5age_att4ck\x00
题目-3
from Crypto.Util.number import *
p = getPrime(1024)
q = getPrime(1024)
n = p * q
flag = b'***'
plaintext = b"The road ahead may be rough, but I'll press on steadfastly, here's a flag for you: " + flag
assert len(flag) == 25
m = bytes_to_long(plaintext)
e = 3
c = pow(m, e, n)
assert pow(m, e) > n
assert m < n
print(f'n = {n}')
print(f'c = {c}')
'''
n = 13753503447046065029509142443098989474010695868671990564407354927280690645587401431807677112738436484457108668416659068807784631150481268253992114172319115625707272198539655802326295745940436229292702809623955977155019039183583174500110954771942715231442852718065625775273782752375231030909832757945909289881176535836072878800140633054948137810448872463052522854389581769817022004130978006426091756594316525571539819885198468430587473672554968707089604543813691493813999251307157726571938369747084210783827415769991815947261236505594845947772467893971510811187290011359630531055493687176490832704611004715607395726889
c = 11526821636096359638765771500888242701853208620089351243160495858906910818518053426626886354269903699300146718469408756695557956058548324449833792134199517886895642768904412616597593228737783391269525226960960218352815387642155365295940870001530748395677331897952881711998501078177880473062101044122275710538840449433613084421479355052565786751049842800941785460733554461280093464252453285411787983456223041894188782235762314576217172507295869659832863550431360288515931541495383984211053164516830388353627820404597561257710290589690861462966355031285263594224925086307198592019420441107811476469565610459713241689827
'''思路
- $flag$的长度已知,直接通过已知$m$高位Coppersmith方法求小根
解答
from Crypto.Util.number import *
e = 3
n = 13753503447046065029509142443098989474010695868671990564407354927280690645587401431807677112738436484457108668416659068807784631150481268253992114172319115625707272198539655802326295745940436229292702809623955977155019039183583174500110954771942715231442852718065625775273782752375231030909832757945909289881176535836072878800140633054948137810448872463052522854389581769817022004130978006426091756594316525571539819885198468430587473672554968707089604543813691493813999251307157726571938369747084210783827415769991815947261236505594845947772467893971510811187290011359630531055493687176490832704611004715607395726889
c = 11526821636096359638765771500888242701853208620089351243160495858906910818518053426626886354269903699300146718469408756695557956058548324449833792134199517886895642768904412616597593228737783391269525226960960218352815387642155365295940870001530748395677331897952881711998501078177880473062101044122275710538840449433613084421479355052565786751049842800941785460733554461280093464252453285411787983456223041894188782235762314576217172507295869659832863550431360288515931541495383984211053164516830388353627820404597561257710290589690861462966355031285263594224925086307198592019420441107811476469565610459713241689827
known = b"The road ahead may be rough, but I'll press on steadfastly, here's a flag for you: "
known_int = bytes_to_long(known)
x = PolynomialRing(Zmod(n), 'x').gen()
f = (known_int * 2**(25 * 8) + x)**e - c
ans = f.small_roots(X = 2**(25 * 8), beta = 0.5)[0]
print(long_to_bytes(int(ans)))
#flag{Stop_stereotype_ill}题目-4
from Crypto.Util.number import *
p = getPrime(1024)
q = getPrime(1024)
n = p * q
flag = b'******ften_fue1_5uch_4ttacks'
plaintext = f'The flag consists of two parts: the first is {flag[:22].decode()}, and the second is ften_fue1_5uch_4ttacks'.encode()
# plaintext = b"The flag consists of two parts: the first is " + flag[:22] + b", and the second is ften_fue1_5uch_4ttacks"
assert len(flag) == 44
m = bytes_to_long(plaintext)
e = 5
c = pow(m, e, n)
assert pow(m, e) > n
assert m < n
print(f'n = {n}')
print(f'c = {c}')
'''
n = 21944248383651135341209617432262811785307027354844733084963337857863570116303233844276884833465321315744618383057831373372064553693262191922037777058029445922224763570412434570581066337047843876962415663915805920948230009197556645316969362503278562387231189287300738896863456079461274224716566527835434538744998835260400874850133804760436770281794695323337463480690657742981406330284459812945299969110107135676237830478011486566496218466380901024579113928673388923500999096662950956114303342267817730872966337538684534727919203253060620407309505645164080525147632143412033558140394210142848568869041328698740141539331
c = 19967997138870734232686786035435982912695094507873041120428863873115143815640415746380323717105159765799283460514312054607016294096377042588764095455627626510123033918874381473375462415260574783730221567367021338531617095069097444313564081563370315703326177544282393212071591601331383828040933896841799973016594931424971632357475377674840942277460294789622577111824328363989360243040922837292083468238159515565019230324871699508729048164816393303057220084358014881054108092881199675525593538848030027024026167946620077429569004735727575503605622600565854060413234627883619114574472893474347973778934575874767804951706
'''思路
- 已知明文前半段加后半段,要求中间的未知明文
- 用CopperSmith来解,相当于知道了 $m$ 的部分高位低位
- 字节串 $AB$ 转换为整数时
- $A$ 的ASCII码是 $65$ (二进制
01000001) - $B$ 的ASCII码是 $66$ (二进制
01000010) - 整数表示为 $65 << 8 + 66 = 0x4142 = 16706$
- 二进制形式为
01000001 01000010,高位字节 $A$ 在左,低位字节 $B$ 在右
- $A$ 的ASCII码是 $65$ (二进制
- 这相当于将字节串视为大端序整数: 左边字节是高位,右边字节是低位
- 如各部分字节内容为
- m_high = b’AB'(2 字节)
- unknown = b’C'(1 字节)
- m_low = b’DEF'(3 字节)
- 则各部分对应的整数
- m_high_int = 0x4142 (二进制
01000001 01000010) - unknown_int = 0x43 (二进制
01000011) - m_low_int = 0x444546 (二进制
01000100 01000101 01000110)
- m_high_int = 0x4142 (二进制
- 位移量计算
- len(m_low) = 3 , k_unknown = 1
- m_high 的位移量 = 8×(3+1) = 32 位
- unknown 的位移量 = 8×3 = 24 位
- 位移后的二进制表示
m_high左移32位: 01000001 01000010 00000000 00000000 00000000 00000000
unknown左移24位: 00000000 00000000 01000011 00000000 00000000 00000000
m_low不位移: 00000000 00000000 00000000 01000100 01000101 01000110- 三部分相加后的整数二进制
01000001 01000010 01000011 01000100 01000101 01000110- 对应字节串为 b’AB’ + b’C’ + b’DEF’ ,即 b’ABCDEF’ (该过程类似IEEE754中各部分的组合逻辑)
- 所以可知
bytes_to_long得到的m_high_默认是低位(右边),要把它推到明文的高位位置,就要乘以一个2的幂,这个幂就是8 * (len(m_low)+k_unknown),因为在m_high后面还有22字节未知块和42字节的m_low,m_low占len(m_low)字节,每个字节8位,因此unknown需要左移8*len(m_low)位,才能放在m_low的左侧(高位方向),避免覆盖m_low的二进制位 - 相当于如下表达式
m = m_high << (8*(len(m_low)+k_unknown)) + unknown << (8*len(m_low)) + m_low解答
from Crypto.Util.number import *
e = 5
n = 21944248383651135341209617432262811785307027354844733084963337857863570116303233844276884833465321315744618383057831373372064553693262191922037777058029445922224763570412434570581066337047843876962415663915805920948230009197556645316969362503278562387231189287300738896863456079461274224716566527835434538744998835260400874850133804760436770281794695323337463480690657742981406330284459812945299969110107135676237830478011486566496218466380901024579113928673388923500999096662950956114303342267817730872966337538684534727919203253060620407309505645164080525147632143412033558140394210142848568869041328698740141539331
c = 19967997138870734232686786035435982912695094507873041120428863873115143815640415746380323717105159765799283460514312054607016294096377042588764095455627626510123033918874381473375462415260574783730221567367021338531617095069097444313564081563370315703326177544282393212071591601331383828040933896841799973016594931424971632357475377674840942277460294789622577111824328363989360243040922837292083468238159515565019230324871699508729048164816393303057220084358014881054108092881199675525593538848030027024026167946620077429569004735727575503605622600565854060413234627883619114574472893474347973778934575874767804951706
m_high = b"The flag consists of two parts: the first is "
m_low = b", and the second is ften_fue1_5uch_4ttacks"
k_unknown = 22
m_high_ = bytes_to_long(m_high)
m_low_int = bytes_to_long(m_low)
l = 8 * len(m_low) # 336
s = 2 ** (8 * (len(m_low)+k_unknown)) # 2^512
m_high_int = m_high_ * s
# m_high_int = bytes_to_long(m_high+b'\x00'*64)
PR.<x> = PolynomialRing(Zmod(n))
f = (m_high_int + m_low_int + x*2**l)^e - c
f = f.monic()
roots = f.small_roots(X=2**(k_unknown*8), beta=0.5)
if roots:
ans = int(roots[0])
unknown = int(ans).to_bytes(k_unknown, 'big')
recovered = unknown + b"ften_fue1_5uch_4ttacks"
print(recovered)
else:
print("No root found")
#sTere0typed_Me5saGes_0ften_fue1_5uch_4ttacks题目-5
- ! UCTF2021-a bit weird
from Crypto.Util import number
from secret import flag
import os
length = 2048
p, q = number.getPrime(length//2), number.getPrime(length//2)
N = p*q
e = 3
m = number.bytes_to_long(flag)
x = number.bytes_to_long(os.urandom(length//8))
c = pow(m|x, e, N)
print('N =', N)
print('e =', e)
print('c =', c)
print('m&x =', m&x)
'''
N = 13876129555781460073002089038351520612247655754841714940325194761154811715694900213267064079029042442997358889794972854389557630367771777876508793474170741947269348292776484727853353467216624504502363412563718921205109890927597601496686803975210884730367005708579251258930365320553408690272909557812147058458101934416094961654819292033675534518433169541534918719715858981571188058387655828559632455020249603990658414972550914448303438265789951615868454921813881331283621117678174520240951067354671343645161030847894042795249824975975123293970250188757622530156083354425897120362794296499989540418235408089516991225649
e = 3
c = 6581985633799906892057438125576915919729685289065773835188688336898671475090397283236146369846971577536055404744552000913009436345090659234890289251210725630126240983696894267667325908895755610921151796076651419491871249815427670907081328324660532079703528042745484899868019846050803531065674821086527587813490634542863407667629281865859168224431930971680966013847327545587494254199639534463557869211251870726331441006052480498353072578366929904335644501242811360758566122007864009155945266316460389696089058959764212987491632905588143831831973272715981653196928234595155023233235134284082645872266135170511490429493
#m&x
m_x = 947571396785487533546146461810836349016633316292485079213681708490477178328756478620234135446017364353903883460574081324427546739724
x = 15581107453382746363421172426030468550126181195076252322042322859748260918197659408344673747013982937921433767135271108413165955808652424700637809308565928462367274272294975755415573706749109706624868830430686443947948537923430882747239965780990192617072654390726447304728671150888061906213977961981340995242772304458476566590730032592047868074968609272272687908019911741096824092090512588043445300077973100189180460193467125092550001098696240395535375456357081981657552860000358049631730893603020057137233513015505547751597823505590900290756694837641762534009330797696018713622218806608741753325137365900124739257740
'''思路
- 我们知道
m&x,x但并恢复不了m,看来我们必须解密c才能得到m|x - 简单统计一下,
m&x和x的位数len(bin(m_x)[2:]),len(bin(x)[2:]) x比m多的位数2048-440- 由
m&x和x知m为440位,x为2048位 - 也就意味着
m|x的高1608位对应x的高位 - 故有以下已知信息:
a=m|x(取低440位)b=x(取x高1680位,低440位赋值为0)- 则
m|x==b+a,有c==(b+a)^e (mod N)
- 这可以归为RSA中stereotyped messages类型攻击,我们能使用Coppersmith恢复
a - 多项式为
f(x)=(m+x)^e-c想发现模N的一个根
代码实现
dd = f.degree()
beta = 1
epsilon = beta / 7
mm = ceil(beta**2 / (dd * epsilon))
tt = floor(dd * mm * ((1/beta) - 1))
XX = ceil(N**((beta**2/dd) - epsilon))
roots = coppersmith_howgrave_univariate(f, N, beta, mm, tt, XX)解答
- @@ sage 脚本获取 x
# Coppersmith implementation
import time
debug = True
# display matrix picture with 0 and X
def matrix_overview(BB, bound):
for ii in range(BB.dimensions()[0]):
a = ('%02d ' % ii)
for jj in range(BB.dimensions()[1]):
a += '0' if BB[ii,jj] == 0 else 'X'
a += ' '
if BB[ii, ii] >= bound:
a += '~'
print(a)
def coppersmith_howgrave_univariate(pol, modulus, beta, mm, tt, XX):
"""
Coppersmith revisited by Howgrave-Graham
finds a solution if:
* b|modulus, b >= modulus^beta , 0 < beta <= 1
* |x| < XX
"""
#
# init
#
dd = pol.degree()
nn = dd * mm + tt
#
# checks
#
if not 0 < beta <= 1:
raise ValueError("beta should belongs in (0, 1]")
if not pol.is_monic():
raise ArithmeticError("Polynomial must be monic.")
#
# calculate bounds and display them
#
"""
* we want to find g(x) such that ||g(xX)|| <= b^m / sqrt(n)
* we know LLL will give us a short vector v such that:
||v|| <= 2^((n - 1)/4) * det(L)^(1/n)
* we will use that vector as a coefficient vector for our g(x)
* so we want to satisfy:
2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)
so we can obtain ||v|| < N^(beta*m) / sqrt(n) <= b^m / sqrt(n)
(it's important to use N because we might not know b)
"""
if debug:
# t optimized?
print("\n# Optimized t?\n")
print("we want X^(n-1) < N^(beta*m) so that each vector is helpful")
cond1 = RR(XX^(nn-1))
print ("* X^(n-1) = ", cond1)
cond2 = pow(modulus, beta*mm)
print("* N^(beta*m) = ", cond2)
print("* X^(n-1) < N^(beta*m) \n-> GOOD" if cond1 < cond2 else "* X^(n-1) >= N^(beta*m) \n-> NOT GOOD")
# bound for X
print("\n# X bound respected?\n")
print("we want X <= N^(((2*beta*m)/(n-1)) - ((delta*m*(m+1))/(n*(n-1)))) / 2 = M")
print("* X =", XX)
cond2 = RR(modulus^(((2*beta*mm)/(nn-1)) - ((dd*mm*(mm+1))/(nn*(nn-1)))) / 2)
print("* M =", cond2)
print("* X <= M \n-> GOOD" if XX <= cond2 else "* X > M \n-> NOT GOOD")
# solution possible?
print("\n# Solutions possible?\n")
detL = RR(modulus^(dd * mm * (mm + 1) / 2) * XX^(nn * (nn - 1) / 2))
print("we can find a solution if 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)")
cond1 = RR(2^((nn - 1)/4) * detL^(1/nn))
print("* 2^((n - 1)/4) * det(L)^(1/n) = ", cond1)
cond2 = RR(modulus^(beta*mm) / sqrt(nn))
print("* N^(beta*m) / sqrt(n) = ", cond2)
print("* 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n) \n-> SOLUTION WILL BE FOUND" if cond1 < cond2 else "* 2^((n - 1)/4) * det(L)^(1/n) >= N^(beta*m) / sqroot(n) \n-> NO SOLUTIONS MIGHT BE FOUND (but we never know)")
# warning about X
print("\n# Note that no solutions will be found _for sure_ if you don't respect:\n* |root| < X \n* b >= modulus^beta\n")
#
# Coppersmith revisited algo for univariate
#
# change ring of pol and x
polZ = pol.change_ring(ZZ)
x = polZ.parent().gen()
# compute polynomials
gg = []
for ii in range(mm):
for jj in range(dd):
gg.append((x * XX)**jj * modulus**(mm - ii) * polZ(x * XX)**ii)
for ii in range(tt):
gg.append((x * XX)**ii * polZ(x * XX)**mm)
# construct lattice B
BB = Matrix(ZZ, nn)
for ii in range(nn):
for jj in range(ii+1):
BB[ii, jj] = gg[ii][jj]
# display basis matrix
if debug:
matrix_overview(BB, modulus^mm)
# LLL
BB = BB.LLL()
# transform shortest vector in polynomial
new_pol = 0
for ii in range(nn):
new_pol += x**ii * BB[0, ii] / XX**ii
# factor polynomial
potential_roots = new_pol.roots()
print("potential roots:", potential_roots)
# test roots
roots = []
for root in potential_roots:
if root[0].is_integer():
result = polZ(ZZ(root[0]))
if gcd(modulus, result) >= modulus^beta:
roots.append(ZZ(root[0]))
#
return roots
# Public key
N = 13876129555781460073002089038351520612247655754841714940325194761154811715694900213267064079029042442997358889794972854389557630367771777876508793474170741947269348292776484727853353467216624504502363412563718921205109890927597601496686803975210884730367005708579251258930365320553408690272909557812147058458101934416094961654819292033675534518433169541534918719715858981571188058387655828559632455020249603990658414972550914448303438265789951615868454921813881331283621117678174520240951067354671343645161030847894042795249824975975123293970250188757622530156083354425897120362794296499989540418235408089516991225649
length_N = 2048
ZmodN = Zmod(N);
e = 3
# Obscuring term (was called `x` previously)
obs = 15581107453382746363421172426030468550126181195076252322042322859748260918197659408344673747013982937921433767135271108413165955808652424700637809308565928462367274272294975755415573706749109706624868830430686443947948537923430882747239965780990192617072654390726447304728671150888061906213977961981340995242772304458476566590730032592047868074968609272272687908019911741096824092090512588043445300077973100189180460193467125092550001098696240395535375456357081981657552860000358049631730893603020057137233513015505547751597823505590900290756694837641762534009330797696018713622218806608741753325137365900124739257740
length_obs = 440
# Ciphertext
C = 6581985633799906892057438125576915919729685289065773835188688336898671475090397283236146369846971577536055404744552000913009436345090659234890289251210725630126240983696894267667325908895755610921151796076651419491871249815427670907081328324660532079703528042745484899868019846050803531065674821086527587813490634542863407667629281865859168224431930971680966013847327545587494254199639534463557869211251870726331441006052480498353072578366929904335644501242811360758566122007864009155945266316460389696089058959764212987491632905588143831831973272715981653196928234595155023233235134284082645872266135170511490429493
# Obsuring term with lower 440 bits zero'd (was called 'b' previously)
obs_clean = (obs >> length_obs) << length_obs
# Problem to equation.
# The `x` here was called `a` previously, which we are now solving for.
P.<x> = PolynomialRing(ZmodN)
pol = (obs_clean + x)^e - C
dd = pol.degree()
beta = 1 # b = N
epsilon = beta / 7 # <= beta / 7
mm = ceil(beta**2 / (dd * epsilon)) # optimized value
tt = floor(dd * mm * ((1/beta) - 1)) # optimized value
XX = ceil(N**((beta**2/dd) - epsilon)) # optimized value
# Coppersmith
roots = coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX)
print()
print("Solutions")
print("We found:", str(roots))
'''
# Optimized t?
we want X^(n-1) < N^(beta*m) so that each vector is helpful
* X^(n-1) = 7.64639144486953e938
* N^(beta*m) = 2671806721397343609369125721689846363846823887595317169259208269410807613515138193272735950395342600354585884618596837138454312445763723886601166952043062748009505139217794681937611360645445444140769994643446818754534866298130651329433014724715889837444867182984191620190905818803588933562722223328979700923934070485221893022649172511067198019458620445165662776678908770872500383557396520873649954695933963393304148547194098533517769688355801169062583949901346704912994207653877424119826970416572728246446525108981742453007188018279798743202379750534406784078069421672055702384012232185139872186089443647992149818358893834997950425662042050549158210414590239894415499371752895019920281114015215479652534190130397775610338712743962931327219145055957487978233015931879293485628652795746982880303598514651118264609343317354096189644231871614967872526120966984276731281546669197245726209804436508113354381914315232435894150854988195962920941429615473853382836785869279384612192426076678623082066854288934520774307146911493350318344271370346300740624871491708331236066262479670355346647414096649266862487754904950869424292066310431256633985253697575515680033391453124985988988670191902111914051233299493877035782843638962398086115700226338455677786300225885984533601124871244669214214105103887099092767042659106858007541232363169127153863660502490389037875332835859504268824420222360070871822883878805542227544448876610761790896706106782074035914998714448926799887557941643969590869586865208655191892111098282289241597413702345534627562696456765064323919706870792491286590311106687866963980133668858578681546024445557042142046310271577884977392878357234252136015344414426228232128893808200127782962118800708442012306882529157602730015548081294901794784475069861171020927127171831672885720955503939986515276832850113174993877171846111637519924505032034449
* X^(n-1) < N^(beta*m)
-> GOOD
# X bound respected?
we want X <= N^(((2*beta*m)/(n-1)) - ((delta*m*(m+1))/(n*(n-1)))) / 2 = M
* X = 2293147898964117288808008000805061598361990209625542167130389100774470198047923394475218668318195962237962277248056358
* M = 5.42671596118645e153
* X <= M
-> GOOD
# Solutions possible?
we can find a solution if 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)
* 2^((n - 1)/4) * det(L)^(1/n) = 2.12973195403260e1702
* N^(beta*m) / sqrt(n) = 8.90602240465781e1847
* 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)
-> SOLUTION WILL BE FOUND
# Note that no solutions will be found _for sure_ if you don't respect:
* |root| < X
* b >= modulus^beta
00 X 0 0 0 0 0 0 0 0 ~
01 0 X 0 0 0 0 0 0 0 ~
02 0 0 X 0 0 0 0 0 0 ~
03 X X X X 0 0 0 0 0
04 0 X X X X 0 0 0 0
05 0 0 X X X X 0 0 0
06 X X X X X X X 0 0
07 0 X X X X X X X 0
08 0 0 X X X X X X X
potential roots: [(2722393138562666557007231734043804673010965247853655886232567981247025605356740318867235245940388712958024648376448739432029199788029, 1)]
Solutions
We found: [2722393138562666557007231734043804673010965247853655886232567981247025605356740318867235245940388712958024648376448739432029199788029]
'''- @@ 现在知道 $m \mid x$ 的低 $440$ 位,可恢复 $m$
import libnum
def recover(x, m_and_x, m_or_x):
ans = []
while m_and_x > 0:
a = x & 1 #取x的最低一位
b = m_and_x & 1
c = m_or_x & 1
if a == 0: # 若a=0，0 and (0 或1)=0 故看 0 or c=c
assert b == 0
ans.append(str(c))
else: # 若a=1,则 1 or (1 or 0)=1 ，故看1 and b=b
ans.append(str(b))
# 都右移看下一位
m_or_x >>= 1
m_and_x >>= 1
x >>= 1
ans = ans[::-1]
ans = "".join(ans)
return libnum.n2s(int('0b'+ans,2))
m_or_x=2722393138562666557007231734043804673010965247853655886232567981247025605356740318867235245940388712958024648376448739432029199788029
# m_and_x为m|x低440位
m_and_x = 947571396785487533546146461810836349016633316292485079213681708490477178328756478620234135446017364353903883460574081324427546739724
x = 15581107453382746363421172426030468550126181195076252322042322859748260918197659408344673747013982937921433767135271108413165955808652424700637809308565928462367274272294975755415573706749109706624868830430686443947948537923430882747239965780990192617072654390726447304728671150888061906213977961981340995242772304458476566590730032592047868074968609272272687908019911741096824092090512588043445300077973100189180460193467125092550001098696240395535375456357081981657552860000358049631730893603020057137233513015505547751597823505590900290756694837641762534009330797696018713622218806608741753325137365900124739257740
m=recover(x,m_and_x,m_or_x)
print(m)
#utflag{C0u1dNt_c0m3_uP_w1tH_A_Cl3veR_f1aG_b61a2defc55f}
