Bread 2

Platform: spbctf | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-03-09 | Status: Solved Techniques: carmichael_vs_euler, modular_inverse

Summary

Task: RSA with p, q, e given directly. Solution: Use Carmichael's function λ(n) instead of Euler's φ(n) to compute d when gcd(p-1, q-1) > 1.

Bread 2 — CryptoKids 2.0

Description

A task about understanding the difference between Euler's totient function φ(n) and Carmichael's function λ(n) in RSA.

Given: p, q, e. Find the secret key d.

Analysis

Standard RSA uses φ(n) = (p-1)(q-1) to compute d. However, mathematically it's more correct to use Carmichael's function λ(n).

The relationship between them:

• φ(n) = (p-1)(q-1)
• λ(n) = lcm(p-1, q-1) = φ(n) / gcd(p-1, q-1)

When gcd(p-1, q-1) > 1, the values of φ(n) and λ(n) differ, and d computed via λ(n) will be smaller. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

In this task:

• gcd(p-1, q-1) = 2
• φ(n) = 2 × λ(n)
• The flag is the value of d itself

Solution

 python read-only • copy allowed Copy
#!/usr/bin/env python3
from math import gcd, lcm

# Parameters from the task
p = ...  # prime number p
q = ...  # prime number q
e = ...  # public exponent

# Compute Euler's totient function
phi_n = (p - 1) * (q - 1)

# Compute Carmichael's function
lambda_n = lcm(p - 1, q - 1)

# Check gcd
g = gcd(p - 1, q - 1)
print(f"gcd(p-1, q-1) = {g}")
print(f"φ(n) = {phi_n}")
print(f"λ(n) = {lambda_n}")
print(f"φ(n) / λ(n) = {phi_n // lambda_n}")
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Compute d via λ(n)
d = pow(e, -1, lambda_n)
print(f"\nd (via λ(n)) = {d}")

# Alternatively via φ(n)
d_phi = pow(e, -1, phi_n)
print(f"d (via φ(n)) = {d_phi}")

# Flag is d
print(f"\nFlag: {d}")

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