Алиса не знает алгебру (Alice doesn't know algebra)

Platform: hackerlab | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-04-04 | Status: Solved Techniques: extended_euclidean_algorithm, modular_inverse_for_negative_exponents, rsa_common_modulus_attack

Summary

Task: RSA service encrypts a secret key with two different prime exponents under the same modulus N, providing both ciphertexts. Solution: Classic RSA Common Modulus Attack using Extended Euclidean Algorithm to find Bézout coefficients and recover plaintext from two ciphertexts.

Алиса не знает алгебру (Alice doesn't know algebra) — Hackerlab

Description

Алиса очень долго собиралась, так как не могла выбрать - какую же экспоненту выбрать при шифровании ключа. В итоге решила использовать сразу обе...

English summary: Alice couldn't decide which RSA exponent to use for encrypting a key, so she used both. We connect to an RSA service at 62.173.140.174:11002 that generates a 512-bit RSA modulus N with two 256-bit prime exponents e1 and e2. The service encrypts a secret KEY under both exponents and provides both ciphertexts. We must recover the KEY to obtain the flag. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Analysis

Source code review (cipher.py)

The server implements an RSA-based encryption service:

1. Key generation: N = p*q where p, q are getPrime(256) (so N is ~512 bits). Two independent 256-bit prime exponents e_1 and e_2 are generated.

2. Server prints N, e_1, e_2 at connection start.

3. Menu options:

   • Option 1 (Encrypt): Takes hex input m, returns (m^e1 mod N, m^e2 mod N)
   • Option 2 (Decrypt): Calls encrypt() internally — this is NOT real decryption, it's a red herring
   • Option 3 (Get flag): Asks for KEY in plaintext; if correct, prints the flag
   • Option 4 (Get encrypted key): Returns (KEY^e1 mod N, KEY^e2 mod N) ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Vulnerability identification

This is a textbook RSA Common Modulus Attack. The same plaintext (KEY) is encrypted with two different public exponents (e1, e2) under the same modulus N. Since both exponents are distinct primes, gcd(e1, e2) = 1 is guaranteed, which means we can recover the plaintext without knowing the private key or factoring N.

The "decrypt" function being fake (just calls encrypt again) is a deliberate trap — the real attack doesn't need decryption at all.

Mathematical basis

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Given:

• c1 = KEY^e1 mod N
• c2 = KEY^e2 mod N
• gcd(e1, e2) = 1

By the Extended Euclidean Algorithm, find integers a, b such that:

a*e1 + b*e2 = 1

Then:

c1^a * c2^b ≡ KEY^(a*e1) * KEY^(b*e2) ≡ KEY^(a*e1 + b*e2) ≡ KEY^1 ≡ KEY (mod N)

For negative exponents (one of a or b will be negative), we use modular inverse: c^(-k) mod N = (c^(-1))^k mod N.

Solution

Step 1: Connect and collect parameters

Connect to the server and parse N, e1, e2 (printed at connection). Then use option 4 to get the encrypted key (c1, c2). ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Step 2: Apply Common Modulus Attack

Use Extended GCD to find Bézout coefficients a, b where a*e1 + b*e2 = 1, then compute KEY = c1^a * c2^b mod N, handling negative exponents via modular inverse.

Step 3: Submit key and get flag

The recovered key was: it'5_v3ry_5tr0ng_5ecr3t_k3y

Submit via option 3 to receive the flag.

Full solve script

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""
RSA Common Modulus Attack - Final Solver
Server prints N, e_1, e_2. We get encrypted key and use common modulus attack.
"""
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

from pwn import *
from Crypto.Util.number import bytes_to_long, long_to_bytes
import gmpy2

HOST = "62.173.140.174"
PORT = 11002
context.log_level = "info"

r = remote(HOST, PORT)

# Read until N
r.recvuntil(b"N: ")
N = int(r.recvline().decode().strip())
print(f"[+] N = {N}")

# Read e_1
r.recvuntil(b"e_1: ")
e1 = int(r.recvline().decode().strip())
print(f"[+] e1 = {e1}")

# Read e_2
r.recvuntil(b"e_2: ")
e2 = int(r.recvline().decode().strip())
print(f"[+] e2 = {e2}")

# Wait for menu
r.recvuntil("действие: ".encode())
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Get encrypted key (option 4)
r.sendline(b"4")
r.recvuntil("Ключ:\n".encode())
c1_hex = r.recvline().decode().strip()
c1 = int(c1_hex, 16)
r.recvuntil("Ну или...\n".encode())
c2_hex = r.recvline().decode().strip()
c2 = int(c2_hex, 16)

print(f"[+] c1 = KEY^e1 mod N = {c1}")
print(f"[+] c2 = KEY^e2 mod N = {c2}")


# Common Modulus Attack
# Find a, b such that a*e1 + b*e2 = gcd(e1, e2) = 1
def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    gcd_val, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return gcd_val, x, y
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍


g, a, b = extended_gcd(e1, e2)
print(f"[+] gcd(e1, e2) = {g}")
assert g == 1, "e1 and e2 must be coprime!"

# KEY = c1^a * c2^b mod N
# Handle negative exponents via modular inverse
if a < 0:
    c1_inv = int(gmpy2.invert(c1, N))
    part1 = pow(c1_inv, -a, N)
else:
    part1 = pow(c1, a, N)

if b < 0:
    c2_inv = int(gmpy2.invert(c2, N))
    part2 = pow(c2_inv, -b, N)
else:
    part2 = pow(c2, b, N)

KEY_int = (part1 * part2) % N
KEY_bytes = long_to_bytes(KEY_int)

print(f"[+] KEY (bytes) = {KEY_bytes}")
print(f"[+] KEY (str) = {KEY_bytes.decode()}")
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Submit key (option 3)
r.recvuntil("действие: ".encode())
r.sendline(b"3")
r.recvuntil("ключ: ".encode())
r.sendline(KEY_bytes)

# Read flag
response = r.recvline(timeout=5)
print(f"[+] Response: {response}")

r.close()

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍