BabyEncryption

Observations

After downloading the file, we extract it and get the following two files:

└─$ cat chall.py                              
import string
from secret import MSG

def encryption(msg):
    ct = []
    for char in msg:
        ct.append((123 * char + 18) % 256)
    return bytes(ct)

ct = encryption(MSG)
f = open('./msg.enc','w')
f.write(ct.hex())
f.close()


                                                                                                                                          
┌──(kali㉿vm-kali)-[~/htb/reversing/babyEncryption]
└─$ cat msg.enc            
6e0a9372ec49a3f6930ed8723f9df6f6720ed8d89dc4937222ec7214d89d1e0e352ce0aa6ec82bf622227bb70e7fb7352249b7d893c493d8539dec8fb7935d490e7f9d22ec89b7a322ec8fd80e7f8921 

The encryption is linear congruential.

Linear Congruential Encryption

A simple symmetric stream-cipher: each plaintext byte p is mapped to ciphertext byte c by the affine transform c ≡ (a·p + b) mod m,

So, how to decrypt it?

We need to figure out the modular inverse of a to (mod m). So, here 123 (mod 256).

What’s a modular inverse?

“A modular inverse of a number ‘a’ (mod m) is another number ‘x’ such that their product is congruent to 1 modulo m. In simpler terms, it’s the number you multiply ‘a’ by (modulo m) to get 1. For example, 3 is the modular inverse of 5 (mod 7) because (3 * 5) mod 7 = 1” ~ Gemini

GCD

We first start by confirming if the modular inverse exists:

1. Divide 256 by 123: 256 = 2 * 123 + 10

2. Divide 123 by the remainder (10): 123 = 12 * 10 + 3

3. Divide 10 by the new remainder (3): 10 = 3 * 3 + 1

4. Divide 3 by the new remainder (1): 3 = 3 * 1 + 0

The last non-zero remainder is 1.

Therefore, the GCD(123, 256) is 1.

Modular Inverse

We can find modular inverse simply by:

print(pow(123,-1,256))

179

Decryption

This is how the encryption happened:

(123 * char + 18) % 256

To decrypt it:

((char - 18) * 179) % 256

msg = "6e0a9372ec49a3f6930ed8723f9df6f6720ed8d89dc4937222ec7214d89d1e0e352ce0aa6ec82bf622227bb70e7fb7352249b7d893c493d8539dec8fb7935d490e7f9d22ec89b7a322ec8fd80e7f8921"

# split into bytes
cipher_bytes = bytes.fromhex(msg)

# decrypt
plain_bytes = bytes(((b - 18) * 179) % 256 for b in cipher_bytes)

print(plain_bytes.decode())