# Weak Hybrid Encryption

Geben ist eine verschlüsselte Nachricht,
für die wir unseren Schlüssel verloren haben.
Wir sollen die Nachricht trotzdem entschlüsseln.

## Lösung

### Brechen des öffentlichen Schlüssels

Geben ist der öffentliche Schlüssel
```python
In [1]: e = 313949
   ...: n = 965225095240772501
```
Der Modulo `n` wurde schon von auf [FactorDB](http://factordb.com/index.php?query=965225095240772501) faktorisiert.
Das gibt uns die Primzahlen
```python
In [2]: p = 982458689
   ...: q = 982458709
```
Wir können `φ(n)` und damit den geheimen Teil des privaten Schlüsseln d berechnen,
mit dem die RSA-Eigenschaft gilt:
```
e * d mod φ(n) = 1
```
Dafür nehmen wir den erweiterten euklidischen Algorithmus und lösen
```
e*d + φ(n)*y = 1
```
wobei
```
(1, d, y) = euclid(e, φ(n))
```
gilt.
Wir erhalten `d` mittels [`modmath.py`](modmath.py):
```python
In [3]: phi = (p-1) * (q-1)

In [4]: d = modinv(e, phi)

In [5]: d
Out[5]: 949988046614533877
```

### Entschlüsseln des RSA-Teils 

Hier brachen wir nur die RSA-Gleichung zum entschlüsseln anwenden:
```
m = c^d mod n
```
Im Code müssen wir das nur für je 8 Byte des RSA-Teils machen:
```python
In [1]: c = [0x0215305e729ca8d3, 0x0cf8673b18795e9d, 0x02d9612fd611b485, 0x0b0c776db41af05f]

In [2]: [hex(pow(x, d, n)) for x in c]
Out[2]: ['0x6b644b4f', '0x3245664b', '0x3068306e', '0x7a6f7563']
```
Damit haben wir den AES-Schlüssel:
```python
In [1]: k = 0x6b644b4f3245664b3068306e7a6f7563
```

### Entschlüsseln des AES-Teils

Hier wird nur noch entsprechend des gegebenen Formats entschlüsselt

```python
In [1]: with open('data.bin', 'rb') as f:
   ...: _, content = f.read().split(b'|')
   ...:

In [2]: data = base64.b64decode(content)

In [3]: iv = data[:16]

In [4]: enc = data[16:]

In [5]: aes = AES.new(k, AES.MODE_CBC, iv=iv)

In [6]: dec = aes.decrypt(enc)

In [7]: with open("decrypt.bin", "wb") as f:
   ...:     f.write(dec)
```
Mit dem Programm [`file`](https://manpage.me/?q=file) können wir dann herausfinden,
was für eine Nachricht das ist:
```bash
$ file decrypt.bin
decrypt.bin: ASCII text, with very long lines (5552), with no line terminators

$ head -c 20 decrypt.bin
/9j/4AAQSkZJRgABAQEA

$ base64 -d decrypt.bin > decrypt.nob64

$ file decrypt.nob64
decrypt.nob64: JPEG image data, JFIF standard 1.01, resolution (DPI), density 96x96, segment length 16, comment: "CREATOR: gd-jpeg v1
.0 (using IJG JPEG v80), quality = 80", baseline, precision 8, 200x60, components 3

$ mv decrypt.nob64 message.jpg
```