RSAisEasy

Technical Walkthrough

Writeup

Challenge

• Name: RSAisEasy
• Category: Crypto
• Difficulty: Easy
• Mode: file

Summary

The provided script uses two RSA moduli that share a prime: n1 = pq and n2 = qz. It does not print n2 directly, but it prints (n1 * E) + n2. Reducing this leak modulo n1 leaves n2 mod n1, which still shares the factor q with n1. From there, n1 can be factored, the first ciphertext can be decrypted, and the second modulus can be reconstructed enough to decrypt the second ciphertext.

Artifact Inventory

Reference analysis/artifact-inventory.json and summarize the relevant files or remote surface.

• files/a12c734a-6ff7-4e31-8204-6d990803d383.zip: HTB ZIP archive.
• analysis/extracted/RSAisEasy.py: RSA parameter generation script.
• analysis/extracted/output.txt: public values n1, c1, c2, and (n1 * E) + n2.
• solve/solve.py: reproducible offline solver.

Analysis

1. The script generates three 512-bit primes p, q, and z.
2. It builds n1 = pq and n2 = qz, so both moduli share q.
3. Instead of printing n2, it prints leak = (n1 * E) + n2.
4. leak % n1 removes the unknown multiple of n1 and leaves n2 mod n1.
5. Since n2 is a multiple of q, gcd(n1, leak % n1) recovers q.
6. p = n1 / q, so c1 decrypts normally with phi(n1) = (p-1)(q-1).
7. Dividing the leak by q gives p * E + z. The remainder modulo p gives z, or z - p if z > p, so the solver tests remainder and remainder + p.
8. Once z is recovered, n2 = q*z and c2 decrypts normally.

Solve

Run:

python3 Crypto/RSAisEasy/solve/solve.py

The script parses output.txt, recovers q with gcd, reconstructs z, decrypts both RSA ciphertexts, joins both plaintext fragments, and prints the flag for harness capture.

Flag

Raw flag is stored in loot/flag.txt and intentionally not reproduced here.

Lessons

• Shared-prime RSA failures are immediately exploitable with gcd.
• Hiding one modulus as (known_modulus * random) + hidden_modulus does not protect the shared factor because modular reduction removes the random multiple.
• When a hidden prime is added to a known-prime multiple, simple division/remainder reasoning can recover the missing prime with only one small candidate adjustment.

Source-Backed Dossier

The sections below are merged from companion Markdown notes for the same case. They are rendered after sanitization so the article stays precise without publishing raw flags, credentials, or target-specific secrets.

Notes

Scope

• Challenge: RSAisEasy
• Category: Crypto
• Difficulty: Easy
• Mode: file
• Remote instance: none
• Start time: 2026-06-10T10:33:14Z
• Operator: harness
• State file: challenge-state.json

Harness Status

• Current phase: see challenge-state.json
• Next allowed actions: see next-action.json
• Raw flags and sensitive material stay in loot/ only. Do not paste them here.

Artifact Inventory

Evidence Ledger

Key Findings

• RSAisEasy.py generates n1 = pq and n2 = qz, so the moduli share prime q.
• output.txt leaks (n1 * E) + n2 instead of n2 directly.
• gcd(n1, leak % n1) recovers the shared prime q.
• p = n1 / q decrypts c1.
• leak / q = p * E + z; testing the remainder modulo p and remainder + p recovers z.
• n2 = q*z decrypts c2.
• solve/solve.py reproduces the full offline solve and the harness captured the flag into loot/flag.txt.

RAG / Advisory Memory

RAG output is advisory only. Record evaluated retrievals with:

scripts/challenge_harness.py rag-record <workspace> --query "..." --tag MATCHED|PARTIAL|MISSING|<secret redacted>|GENERIC --validation "..."

Secrets/Flags

Raw flags and sensitive material stay in loot/ only. Use scripts/challenge_harness.py capture-flag to validate and record flag capture without printing the value.

Memory Summary

Metadata

• Platform: HackTheBox Challenges
• Category: Crypto
• Challenge: RSAisEasy
• Difficulty: Easy
• Source workspace: <local workspace>

Validated Solve Chain

Concepts only. Do not include raw flags, reusable credentials, tokens, cookies, private keys, or live secrets.

1. Read the provided RSA generation script and identify that two moduli share a prime: n1 = pq, n2 = qz.
2. Observe that the output leaks (n1 * E) + n2.
3. Compute gcd(n1, leak % n1) to recover the shared prime q.
4. Compute p = n1 / q and decrypt the first ciphertext.
5. Divide the leak by q to get p * E + z.
6. Recover z by testing the quotient remainder modulo p and remainder + p.
7. Reconstruct n2 = q*z and decrypt the second ciphertext.
8. Join both plaintext fragments.

Reusable Lessons

• Shared-prime RSA challenges should start with gcd checks across any visible or partially visible modulus relationship.
• A masked value of the form (known_modulus * random) + hidden_modulus still leaks the hidden modulus modulo the known one.
• When primes have similar bit lengths, quotient/remainder relationships often leave only one or two candidates to test.

Dead Ends

• No external research, Sage, Sympy, or CTF RSA tooling was required.
• Brute force was unnecessary; the leak is algebraic.

Tool Quirks

• PyCryptodome was available and sufficient for inverse, isPrime, and long_to_bytes.
• Local sympy and sage were unavailable, but not needed.

Evidence Paths

• analysis/extracted/RSAisEasy.py
• analysis/extracted/output.txt
• analysis/checkpoint-analysis-20260610T103452480975Z-80251ba6.md
• solve/solve.py
• loot/flag.txt

Ingestion Decision

• Proposed for LightRAG: yes
• Requires user approval before ingestion: yes

Hypothesis Board

Keep no more than 3 active hypotheses on Easy/Medium and 5 on Hard unless the user explicitly asks for breadth.

Closed Branches

Memory Summary

approval_required: true

Sanitized Memory Summary

Metadata

• Platform: HackTheBox Challenges
• Category: Crypto
• Challenge: RSAisEasy
• Difficulty: Easy
• Source workspace: <local workspace>

Validated Solve Chain

Concepts only. Do not include raw flags, reusable credentials, tokens, cookies, private keys, or live secrets.

1. Read the provided RSA generation script and identify that two moduli share a prime: n1 = pq, n2 = qz.
2. Observe that the output leaks (n1 * E) + n2.
3. Compute gcd(n1, leak % n1) to recover the shared prime q.
4. Compute p = n1 / q and decrypt the first ciphertext.
5. Divide the leak by q to get p * E + z.
6. Recover z by testing the quotient remainder modulo p and remainder + p.
7. Reconstruct n2 = q*z and decrypt the second ciphertext.
8. Join both plaintext fragments.

Reusable Lessons

• Shared-prime RSA challenges should start with gcd checks across any visible or partially visible modulus relationship.
• A masked value of the form (known_modulus * random) + hidden_modulus still leaks the hidden modulus modulo the known one.
• When primes have similar bit lengths, quotient/remainder relationships often leave only one or two candidates to test.

Dead Ends

• No external research, Sage, Sympy, or CTF RSA tooling was required.
• Brute force was unnecessary; the leak is algebraic.

Tool Quirks

• PyCryptodome was available and sufficient for inverse, isPrime, and long_to_bytes.
• Local sympy and sage were unavailable, but not needed.

Evidence Paths

• analysis/extracted/RSAisEasy.py
• analysis/extracted/output.txt
• analysis/checkpoint-analysis-20260610T103452480975Z-80251ba6.md
• solve/solve.py
• loot/flag.txt

Ingestion Decision

• Proposed for LightRAG: yes
• Requires user approval before ingestion: yes

Notes

Notes

Scope

• Challenge: RSAisEasy
• Category: Crypto
• Difficulty: Easy
• Mode: file
• Remote instance: none
• Start time: 2026-06-10T10:33:14Z
• Operator: harness
• State file: challenge-state.json

Harness Status

• Current phase: see challenge-state.json
• Next allowed actions: see next-action.json
• Raw flags and sensitive material stay in loot/ only. Do not paste them here.

Artifact Inventory

Evidence Ledger

Key Findings

• RSAisEasy.py generates n1 = pq and n2 = qz, so the moduli share prime q.
• output.txt leaks (n1 * E) + n2 instead of n2 directly.
• gcd(n1, leak % n1) recovers the shared prime q.
• p = n1 / q decrypts c1.
• leak / q = p * E + z; testing the remainder modulo p and remainder + p recovers z.
• n2 = q*z decrypts c2.
• solve/solve.py reproduces the full offline solve and the harness captured the flag into loot/flag.txt.

RAG / Advisory Memory

RAG output is advisory only. Record evaluated retrievals with:

scripts/challenge_harness.py rag-record <workspace> --query "..." --tag MATCHED|PARTIAL|MISSING|<secret redacted>|GENERIC --validation "..."

Secrets/Flags

Raw flags and sensitive material stay in loot/ only. Use scripts/challenge_harness.py capture-flag to validate and record flag capture without printing the value.