Description
(2531257, 43)
My super secret message: 906851 991083 1780304 2380434 438490 356019 921472 822283 817856 556932 2102538 2501908 2211404 991083 1562919 38268 |
Initial Findings
- From the title, we can assume this is some form of RSA.
- There are spaces in the message, so I assumed that the individual characters of the flag were encrypted separately
- The public key is (N,e) = (2531257, 43)
- N is super low and bruteforce-able
- Flags start with ‘gigem{‘
Intro RSA
- Using the public key, data can be encrypted using the procedure C = m^e mod N
- C: Cipher Text, m: message, e: encryption key, N: modulus
- Decryption is similar but with a decryption key – m = C^d mod N
- This is all the RSA you need to know for this challenge
Beginning a Solution
- Thanks to our initial findings, we can assume that the first number, 906851, decodes to the character ‘g’
- We can write a quick program to try decryption keys until one works
n = 2531257 for d in range(2,10000000): if pow(906851, d, n) == ord(‘g’): break |
Wait What?
- Great we have a decryption key, d, that decrypts our first character!
- Let’s try it on our second character to make sure
chr2 = pow(991083, d, n) print(chr2) # Prints 105103 |
- “105103” isn’t the right number, at this point I was stumped. I tried finding another decryption key but to no avail.
- Then I realized that 105 is the decimal equivalent of “i” and 103 for “g”
- The letters are concatenated by twos then encrypted!
Full Decryption
- At this point, you could decode the whole message by hand, but where’s the fun in that?
- For each value, we have to determine which numbers go to which character
- There are four (five) possible states
- Our first character, by itself (3 digits)
- Two 2-digit ascii characters (4 digits)
- A 2-digit character and a 3-digit character (5 digits)
- 2+3 or 3+2
- Two 3-digit characters (6 digits)
- All of the states are simple enough to decode, except for state C
n = 2531257
for d in range(2,10000000): c = [906851, for value in c: if len(m) == 3: if f > 64 and f < 126 and s > 64 and s < 126: |