~/ctf/TAMU/RSAaaaa.txt

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
    1. Our first character, by itself (3 digits)
    2. Two 2-digit ascii characters (4 digits)
    3. A 2-digit character and a 3-digit character (5 digits)
      • 2+3 or 3+2
    4. 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):
    if pow(906851, d, n) == ord(‘g’):
        break

c = [906851,
    991083,
    1780304,
    2380434,
    438490,
    356019,
    921472,
    822283,
    817856,
    556932,
    2102538,
    2501908,
    2211404,
    991083,
    1562919,
    38268]

for value in c:
    # Decode to string
    m = str(pow(value,d,n))

    if len(m) == 3:
        # First Character
        print(chr(int(m)),end=””)
    elif len(m) == 4:
        # Two 2-digit characters
        print(chr(int(m[:2])) + chr(int(m[2:])),end=””)
    elif len(m) == 5:
        # 2-digit and 3-digit
        f = int(m[:2])
        s = int(m[2:])

        if f > 64 and f < 126 and s > 64 and s < 126:
            # See if 2+3 is in ascii range
            print(chr(f) + chr(s),end=””)
        else:
            # Otherwise use the other way
            print(chr(int(m[:3])) + chr(int(m[3:])),end=””)
    else:
        # Two 3-digit characters
        print(chr(int(m[:3])) + chr(int(m[3:])),end=””)
print() # gigem{Savage_Six_Flying_Tigers}

 

Advertisements