Sign Easy

Platform: spbctf | Category: Crypto | Type: Challenge | Difficulty: Easy | OS: NA | Author: XESXOR | Date: 2026-03-09 | Status: Solved Techniques: rsa_multiplicative_homomorphism, signature_forgery

Summary

Task: RSA signature oracle where you need to sign message 2000 but can only request signatures for other messages. Solution: Exploit RSA multiplicative homomorphism by getting signatures for 2 and 1000, then multiplying them to forge signature for 2000.

Sign Easy — CryptoKids 2.0

Description

RSA signature oracle. Need to get signature for message 2000, but can only request signatures for other messages.

Analysis

• RSA signature: s = m^d mod n
• Multiplicative homomorphism: (m1 * m2)^d = m1^d * m2^d mod n
• Target message 2000 = 2 * 1000
• Get signatures for 2 and 1000, multiply them to forge signature for 2000

Solution

RSA signatures are multiplicatively homomorphic. If we have:

• s1 = sign(2) = 2^d mod n
• s2 = sign(1000) = 1000^d mod n ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Then:

• s3 = s1 * s2 mod n = 2^d * 1000^d mod n = (2*1000)^d mod n = 2000^d mod n = sign(2000)

 python read-only • copy allowed Copy
#!/usr/bin/env python3
# RSA signature forgery via multiplicative homomorphism

from pwn import *

# Connect to server
r = remote('challenge.ctf', 1337)

# Get n from server
r.recvuntil(b'n = ')
n = int(r.recvline().strip())

# Request signature for 2
r.sendlineafter(b'message: ', b'2')
r.recvuntil(b'signature: ')
s1 = int(r.recvline().strip())

# Request signature for 1000
r.sendlineafter(b'message: ', b'1000')
r.recvuntil(b'signature: ')
s2 = int(r.recvline().strip())
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Forge signature for 2000 = 2 * 1000
s3 = (s1 * s2) % n
print(f"Forged signature for 2000: {s3}")

# Submit forged signature
r.sendlineafter(b'signature for 2000: ', str(s3).encode())
print(r.recvall().decode())

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