Tags: coppersmith crypto rsa 

Rating:

# 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? I
managed 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:

```python
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)
```

And we have a bunch of values, including `x`:
```
N = 13876129555781460073002089038351520612247655754841714940325194761154811715694900213267064079029042442997358889794972854389557630367771777876508793474170741947269348292776484727853353467216624504502363412563718921205109890927597601496686803975210884730367005708579251258930365320553408690272909557812147058458101934416094961654819292033675534518433169541534918719715858981571188058387655828559632455020249603990658414972550914448303438265789951615868454921813881331283621117678174520240951067354671343645161030847894042795249824975975123293970250188757622530156083354425897120362794296499989540418235408089516991225649
e = 3
c = 6581985633799906892057438125576915919729685289065773835188688336898671475090397283236146369846971577536055404744552000913009436345090659234890289251210725630126240983696894267667325908895755610921151796076651419491871249815427670907081328324660532079703528042745484899868019846050803531065674821086527587813490634542863407667629281865859168224431930971680966013847327545587494254199639534463557869211251870726331441006052480498353072578366929904335644501242811360758566122007864009155945266316460389696089058959764212987491632905588143831831973272715981653196928234595155023233235134284082645872266135170511490429493
m&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 + b
Then c === (a + b)**e (mod N)
```

This sounds like a case of stereotyped messages. We can recover `b` using
Coppersmith.

I used [this implementation](https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/README.md#stereotyped-messages)—specifically, `coppersmith.sage`

```sage
import 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 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))
```

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 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]
```

Now that we have `m | x`, we can recover `m`:
```python
def 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.py
b'utflag{C0u1dNt_c0m3_uP_w1tH_A_Cl3veR_f1aG_b61a2defc55f}'
```

Original writeup (https://github.com/cscosu/ctf-writeups/tree/master/2021/utctf/A_Bit_Weird).