./Challenge_09_Answer_Cheat_Sheet

Important things you need to know:

• W is a superincreasing sequence.
• q is larger than sum(W).
• r is relatively prime to q.

Step 1 — Find the modular inverse

The first step is to find the modular inverse of r:

(r * r⁻¹) mod q = 1

This allows you to undo the multiplication used to create the public key.

Reminder:
q > sum(W), So first add all the values in W together.

Step 2 — Decrypt each ciphertext number

For each ciphertext number C, calculate:

S = (C × r⁻¹) mod q

This gives you the value that needs to be solved using the private sequence:

W = [w1, w2, w3, w4, w5, w6, w7, w8]

Step 3 — Solve the subset-sum

Use the values in W to determine which numbers were used to create S.

Each value in W produces either:

• 1 = used
• 0 = not used

This gives you an 8-bit binary value.

Step 4 — Convert to ASCII

Convert the resulting binary value into a number, then convert that number to its ASCII character.

For example:

01000001 → 65 → A

Step 5 — Repeat

Repeat the process for every cipher text number until you have recovered the entire message.

Flag format:

Once you have the plaintext:

• Wrap the entire message in ctf{}