> For the complete documentation index, see [llms.txt](https://book.onosh.ovh/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://book.onosh.ovh/ctf/hacktheshields-2026/crypto-common-modulus-attack.md).

# Crypto - Common Modulus Attack

### 1. Énoncé

> Deux agents d'Orion, sous couverture, communiquent via des canaux RSA distincts. Nous avons intercepté leurs messages chiffrés (`msg1.enc`, `msg2.enc`) ainsi que leurs clés publiques respectives (`agent1_pub.pem`, `agent2_pub.pem`). Déchiffrez le message d'origine pour intercepter leur échange.
>
> **Format du flag :** `HTS{...}`

#### Fichiers fournis

| Fichier          | Taille     | Description                              |
| ---------------- | ---------- | ---------------------------------------- |
| `agent1_pub.pem` | 451 octets | Clé publique RSA de l'agent 1            |
| `agent2_pub.pem` | 451 octets | Clé publique RSA de l'agent 2            |
| `msg1.enc`       | 256 octets | Message chiffré avec la clé de l'agent 1 |
| `msg2.enc`       | 256 octets | Message chiffré avec la clé de l'agent 2 |

{% file src="/files/gMmWxPPF5HJ5otme0lgc" %}

{% file src="/files/wlMauXipvOY8mcrnKxNZ" %}

{% file src="/files/wog0mSUaDZ9ol8Hc2xjT" %}

{% file src="/files/A9Bg4X8HktzskjUrhTcO" %}

***

### 2. Analyse des clés publiques

La première étape consiste à inspecter les deux clés publiques :

```bash
openssl rsa -pubin -in agent1_pub.pem -text -noout
openssl rsa -pubin -in agent2_pub.pem -text -noout
```

**Résultat :**

| Paramètre    | agent1\_pub.pem           | agent2\_pub.pem   |
| ------------ | ------------------------- | ----------------- |
| Taille       | 2048 bits                 | 2048 bits         |
| Modulus `n`  | `0xac84e669be0a...f2f3d7` | **identique**     |
| Exposant `e` | `65537` (0x10001)         | `65539` (0x10003) |

#### Observation

Les deux agents partagent **exactement le même modulus `n`** (2048 bits), mais utilisent des exposants publics différents :

* `e₁ = 65537` (exposant RSA standard)
* `e₂ = 65539` (exposant RSA non standard)

Cette configuration est la condition exacte d'une **attaque Common Modulus**.

***

### 3. La vulnérabilité : Common Modulus Attack

#### Principe

L'attaque Common Modulus exploite le scénario où le **même message `m`** est chiffré deux fois avec le **même modulus `n`** mais deux exposants différents `e₁` et `e₂` :

```
c₁ = m^e₁ mod n
c₂ = m^e₂ mod n
```

#### Condition nécessaire

L'attaque fonctionne si et seulement si :

```
gcd(e₁, e₂) = 1
```

Vérifions :

```
gcd(65537, 65539) = gcd(65537, 2) = 1
```

#### Démonstration mathématique

Par le **théorème de Bézout**, puisque `gcd(e₁, e₂) = 1`, il existe des entiers `a` et `b` tels que :

```
a·e₁ + b·e₂ = 1
```

En appliquant l'algorithme d'Euclide étendu sur `e₁=65537` et `e₂=65539` :

```
65539 = 1·65537 + 2
65537 = 32768·2 + 1
```

En remontant :

```
1 = 65537 − 32768·2
1 = 65537 − 32768·(65539 − 65537)
1 = 32769·65537 − 32768·65539
```

Donc : **`a = 32769`** et **`b = −32768`**

#### Récupération du message

On calcule :

```
m = c₁^a · c₂^b mod n
  = c₁^32769 · c₂^(−32768) mod n
  = c₁^32769 · (c₂^(−1))^32768 mod n
```

Avec `c₂^(−1)` = inverse modulaire de `c₂` mod `n`.

Cela fonctionne car :

```
c₁^a · c₂^b = (m^e₁)^a · (m^e₂)^b
             = m^(a·e₁) · m^(b·e₂)
             = m^(a·e₁ + b·e₂)
             = m^1
             = m (mod n)
```

***

### 4. Exploitation

#### Script Python

```python
import math, re

def parse_pem_pubkey(filename):
    import base64
    with open(filename) as f:
        data = f.read()
    b64 = ''.join(data.strip().split('\n')[1:-1])
    der = base64.b64decode(b64)

    def parse_len(data, pos):
        l = data[pos]; pos += 1
        if l & 0x80:
            nb = l & 0x7f
            l = int.from_bytes(data[pos:pos+nb], 'big')
            pos += nb
        return l, pos

    def parse_int(data, pos):
        assert data[pos] == 0x02; pos += 1
        l, pos = parse_len(data, pos)
        return int.from_bytes(data[pos:pos+l], 'big'), pos + l

    i = 0
    while der[i] != 0x03: i += 1
    i += 1; l, i = parse_len(der, i); i += 1
    assert der[i] == 0x30; i += 1; l, i = parse_len(der, i)
    n, i = parse_int(der, i)
    e, i = parse_int(der, i)
    return n, e

n, e1 = parse_pem_pubkey('agent1_pub.pem')
_, e2 = parse_pem_pubkey('agent2_pub.pem')

c1 = int.from_bytes(open('msg1.enc', 'rb').read(), 'big')
c2 = int.from_bytes(open('msg2.enc', 'rb').read(), 'big')

def egcd(a, b):
    old_r, r = a, b
    old_s, s = 1, 0
    while r != 0:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s
    return old_r, old_s, (old_r - old_s * a) // b if b else 0

def modinv(x, m):
    _, inv, _ = egcd(x % m, m)
    return inv % m

g, a, b = egcd(e1, e2)

if a < 0:
    c1u = modinv(c1, n); au = -a
else:
    c1u = c1; au = a

if b < 0:
    c2u = modinv(c2, n); bu = -b
else:
    c2u = c2; bu = b

m = (pow(c1u, au, n) * pow(c2u, bu, n)) % n
m_bytes = m.to_bytes(256, 'big')

if m_bytes[0] == 0x00 and m_bytes[1] == 0x02:
    idx = m_bytes.index(0x00, 2)
    print("Flag (PKCS#1):", m_bytes[idx+1:].decode('utf-8'))
else:
    printable = re.findall(b'[ -~]{4,}', m_bytes)
    for s in printable:
        print("Trouvé:", s.decode())

```

#### Exécution et résultat

```
$ python3 exploit.py
Flag : HTS{S4M3_M0DULUS_TW1C3_TH3_FUN}
```

***

### 5. Conclusion

La **Common Modulus Attack** illustre une règle fondamentale en cryptographie RSA :

> **Ne jamais utiliser le même modulus `n` pour deux paires de clés distinctes.**

Même si les exposants `e₁` et `e₂` sont différents, partager `n` permet à un attaquant de retrouver le message original sans jamais connaître les clés privées, à condition que `gcd(e₁, e₂) = 1`. Cette attaque ne nécessite que les deux chiffrés et les deux clés publiques.