# A Bit Weird
**Category**: Crypto \**Points**: 986 (39 solves) \**Author**: oops
## Challenge
I found this weird RSA looking thing somewhere. Can you break it for me? Imanaged to find x for you, but I don't know how to solve it without d...
Attachments: `msg.txt`, `main.py`
## Overview
We're given a pretty simplistic challenge:
```pythonfrom Crypto.Util import numberfrom secret import flagimport os
length = 2048p, q = number.getPrime(length // 2), number.getPrime(length // 2)N = p * qe = 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)```
And we have a bunch of values, including `x`:```N = 13876129555781460073002089038351520612247655754841714940325194761154811715694900213267064079029042442997358889794972854389557630367771777876508793474170741947269348292776484727853353467216624504502363412563718921205109890927597601496686803975210884730367005708579251258930365320553408690272909557812147058458101934416094961654819292033675534518433169541534918719715858981571188058387655828559632455020249603990658414972550914448303438265789951615868454921813881331283621117678174520240951067354671343645161030847894042795249824975975123293970250188757622530156083354425897120362794296499989540418235408089516991225649e = 3c = 6581985633799906892057438125576915919729685289065773835188688336898671475090397283236146369846971577536055404744552000913009436345090659234890289251210725630126240983696894267667325908895755610921151796076651419491871249815427670907081328324660532079703528042745484899868019846050803531065674821086527587813490634542863407667629281865859168224431930971680966013847327545587494254199639534463557869211251870726331441006052480498353072578366929904335644501242811360758566122007864009155945266316460389696089058959764212987491632905588143831831973272715981653196928234595155023233235134284082645872266135170511490429493m&x = 947571396785487533546146461810836349016633316292485079213681708490477178328756478620234135446017364353903883460574081324427546739724
x = 15581107453382746363421172426030468550126181195076252322042322859748260918197659408344673747013982937921433767135271108413165955808652424700637809308565928462367274272294975755415573706749109706624868830430686443947948537923430882747239965780990192617072654390726447304728671150888061906213977961981340995242772304458476566590730032592047868074968609272272687908019911741096824092090512588043445300077973100189180460193467125092550001098696240395535375456357081981657552860000358049631730893603020057137233513015505547751597823505590900290756694837641762534009330797696018713622218806608741753325137365900124739257740```
However, even with `x` and `m & x`, we can't directly recover`m`. Looks like we'll have to decrypt `c` to get `m | x`.
## Solution
What do we know about `m | x`?1. `m` is 440 bits, based on the length of `m & x`2. `x` is 16384 bits, which is much longer than `m`3. This means the upper 15944 bits of `m | x` will match `x`
Finally:```Let a = m | x (lower 440 bits)- We want to find this value
Let b = x (upper 15944 bits, lower 440 bits being zeros)- We know this value
Then (m | x) == a + bThen c === (a + b)**e  (mod N)```
This sounds like a case of stereotyped messages. We can recover `b` usingCoppersmith.
I used [this implementation](https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/README.md#stereotyped-messages)—specifically, `coppersmith.sage`
```sageimport Crypto.Util.number as cun
# Coppersmith implementation omitted# ...
def lower_bytes(x, nbytes):    return cun.bytes_to_long(cun.long_to_bytes(x)[-nbytes:])
# Public keyN = 13876129555781460073002089038351520612247655754841714940325194761154811715694900213267064079029042442997358889794972854389557630367771777876508793474170741947269348292776484727853353467216624504502363412563718921205109890927597601496686803975210884730367005708579251258930365320553408690272909557812147058458101934416094961654819292033675534518433169541534918719715858981571188058387655828559632455020249603990658414972550914448303438265789951615868454921813881331283621117678174520240951067354671343645161030847894042795249824975975123293970250188757622530156083354425897120362794296499989540418235408089516991225649length_N = 2048ZmodN = Zmod(N);e = 3
# Obscuring term (was called `x` previously)obs = 15581107453382746363421172426030468550126181195076252322042322859748260918197659408344673747013982937921433767135271108413165955808652424700637809308565928462367274272294975755415573706749109706624868830430686443947948537923430882747239965780990192617072654390726447304728671150888061906213977961981340995242772304458476566590730032592047868074968609272272687908019911741096824092090512588043445300077973100189180460193467125092550001098696240395535375456357081981657552860000358049631730893603020057137233513015505547751597823505590900290756694837641762534009330797696018713622218806608741753325137365900124739257740length_obs = 440
# CiphertextC = 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 - Cdd = pol.degree()
beta = 1                                # b = Nepsilon = beta / 7                      # <= beta / 7mm = ceil(beta**2 / (dd * epsilon))     # optimized valuett = floor(dd * mm * ((1/beta) - 1))    # optimized valueXX = ceil(N**((beta**2/dd) - epsilon))  # optimized value
# Coppersmithroots = coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX)
print()print("Solutions")print("We found:", str(roots))```
Output:```$ sage coppersmith.sage
# 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?
(e 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 004 0 X X X X 0 0 0 005 0 0 X X X X 0 0 006 X X X X X X X 0 007 0 X X X X X X X 008 0 0 X X X X X X Xpotential roots: [(2722393138562666557007231734043804673010965247853655886232567981247025605356740318867235245940388712958024648376448739432029199788029, 1)]
SolutionsWe found: [2722393138562666557007231734043804673010965247853655886232567981247025605356740318867235245940388712958024648376448739432029199788029]```
Now that we have `m | x`, we can recover `m`:```pythondef recover(x, m_and_x, m_or_x):    ans = []
    while m_and_x > 0:        a = x & 1        b = m_and_x & 1        c = m_or_x & 1
        if a == 0:            assert b == 0            ans.append(str(c))        else:            ans.append(str(b))
        m_or_x >>= 1        m_and_x >>= 1        x >>= 1
    ans = ans[::-1]    ans = "".join(ans)    return ans```
Output:```$ python3 solve.pyb'utflag{C0u1dNt_c0m3_uP_w1tH_A_Cl3veR_f1aG_b61a2defc55f}'```