> For the complete documentation index, see [llms.txt](https://youssefsahnoun.gitbook.io/youssefsahnoun/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://youssefsahnoun.gitbook.io/youssefsahnoun/cryptohack-writeups/rsa/bespoke-padding.md).

# Bespoke Padding

SECTION : PADDING

<figure><img src="https://900490735-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkFkdoZ9Zx4nBg7cvLHlR%2Fuploads%2F9Wi7MtHguLs51hSFpIfw%2Fimage_2025-09-23_155015262.png?alt=media&amp;token=d7386de7-865b-4116-8983-d324b29b3b8d" alt=""><figcaption></figcaption></figure>

## Challenge Script:

```python
#!/usr/bin/env python3

from utils import listener
from Crypto.Util.number import bytes_to_long, getPrime
import random

FLAG = b'crypto{???????????????????????????}'


class Challenge():
    def __init__(self):
        self.before_input = "Come back as much as you want! You'll never get my flag.\n"
        self.p = getPrime(1024)
        self.q = getPrime(1024)
        self.N = self.p * self.q
        self.e = 11

    def pad(self, flag):
        m = bytes_to_long(flag)
        a = random.randint(2, self.N)
        b = random.randint(2, self.N)
        return (a, b), a*m+b

    def encrypt(self, flag):
        pad_var, pad_msg = self.pad(flag)
        encrypted = (pow(pad_msg, self.e, self.N), self.N)
        return pad_var, encrypted

    def challenge(self, your_input):
        if not 'option' in your_input:
            return {"error": "You must send an option to this server"}

        elif your_input['option'] == 'get_flag':
            pad_var, encrypted = self.encrypt(FLAG)
            return {"encrypted_flag": encrypted[0], "modulus": encrypted[1], "padding": pad_var}

        else:
            return {"error": "Invalid option"}


import builtins; builtins.Challenge = Challenge # hack to enable challenge to be run locally, see https://cryptohack.org/faq/#listener
"""
When you connect, the 'challenge' function will be called on your JSON
input.
"""
listener.start_server(port=13386)
```

## Explanation:

The server generates a 2048-bit RSA modulus `N = p*q` and sets `e = 11`.\
On each `get_flag` request the server:

1. chooses random integers `a` and `b` in `[2, N]`
2. generates a linear padding with the flag `pad_msg = a * flag + b`&#x20;
3. computes `encrypted = pad_msg^e mod N`
4. returns `(encrypted, N, padding=(a, b))` ( it returns a and b to us).

So the response is `c = (a*flag + b)^e mod N`  , N and the pair `(a,b)`.

## Exploit:

In order to retrieve the flag we simply can receive 2 different encrypted messages c1 and c2.

We'll have `c1 = (a1*flag + b1)^e mod N` and `c2=(a2*flag + b2)^e mod N`.

We can solve this by setting 2 polynomials `f1(x)=a1*x+b1 - c1` and `f2(x)=a2*x+b2 - c2`  .

Note that for both polynomials the root is our `flag` which means `f1(flag)=0` and `f2(flag)=0` therefore `(x - flag)` is a common factor of `f1` and `f2`. Computing the polynomial GCD of `f1` and `f2` over `Z/NZ` therefore isolates the linear factor whose root is `flag`.<br>

```python
from pwn import remote
import json
from sympy import symbols, Poly, gcd
from Crypto.Util.number import long_to_bytes

# Remote server details
HOST = 'socket.cryptohack.org'
PORT = 13386


def get_two_encryptions():

    io = remote(HOST, PORT)

    io.recvline()

    request = {"option": "get_flag"}


    io.sendline(json.dumps(request).encode())
    resp1 = json.loads(io.recvline().strip().decode())
    a1, b1 = resp1['padding']
    c1     = resp1['encrypted_flag']
    N      = resp1['modulus']

    io.sendline(json.dumps(request).encode())
    resp2 = json.loads(io.recvline().strip().decode())
    a2, b2 = resp2['padding']
    c2     = resp2['encrypted_flag']

    io.close()
    return (a1, b1, c1, a2, b2, c2, N)


if __name__ == '__main__':
  
    a1, b1, c1, a2, b2, c2, N = get_two_encryptions()

    x  = symbols('x')
    g1 = Poly((a1*x + b1)**11 - c1, x, modulus=N)
    g2 = Poly((a2*x + b2)**11 - c2, x, modulus=N)

    G = gcd(g1, g2)
    coeffs = G.all_coeffs() 
    m = (-coeffs[1]) % N

    flag = long_to_bytes(m)
    print(flag.decode())
```

## Execution:

```bash
python3 solve.py 
[+] Opening connection to socket.cryptohack.org on port 13386: Done
[*] Closed connection to socket.cryptohack.org port 13386
Poly(x - 75465982370528093742668469354354515773178988899796332530821581088082*************, x, modulus=23895069525228689457356041748409570276743031558111788646107286962297129459348486132247630067915491559435175322202389578422893917533238549650479437418808496167021227019832174298843525687997635049080634901636310655471001465858347858749917578852436490452741022782622351677683362789123404537546358622839605520031153923912394416061190542761304668151703018708609036019696454671880423635713882100539644463429623171594130097010313271384341818847990188920441653222987388129042680538866391820588886773063633482749054511330876771424726871941105772648449037953837776693773390454911149548662345748131337676748308335839974196279999)
crypto{linear*********}

```