HSCTF 9 - Baby-baby-rsa

Shuffled chunks of bits

Description

“You should do this by hand.”

Solution

Ok, so we have a RSA crypto, let’s look at the source code:

from Crypto.Util.number import *
import random
flag = open('flag.txt','rb').read()
pt = bytes_to_long(flag)
bits = 768
p,q = getPrime(bits),getPrime(bits)
n = p*q
e = 0x10001
print(pow(pt,e,n))
bit_p = bin(p)[2:]
bit_q = bin(q)[2:]
parts = [bit_p[0:bits//3],bit_p[bits//3:2*bits//3],bit_p[2*bits//3:bits],bit_q[0:bits//3],bit_q[bits//3:2*bits//3],bit_q[2*bits//3:bits]]
random.shuffle(parts)
print(parts)

q & p are 768 bits long, converted into binary, each split into three pieces and put into a list, which is then shuffled. Great, we need to reassemble the primes to be able to solve the crypto.

I solved it by making a list of all permutations, then trying to solve the crypto with each permutation and checking if the result contains “flag”. Somehow it didn’t work when straight up making the permutations, so I did it by using permutations of the list index, which solved it for me. Now, checking if the permutation actually is a prime would probably have been a good idea instead of looping through all possible permutation, but since there were only six chunks in total it didn’t take a long time anyway.

from Crypto.Util.number import *
import random
from itertools import permutations

e = 0x10001

parts = ['0100101100001100010110110001000001001110010110110011101111100001101100000101000011111000101110011010010100101100011111000000101010011101100101010000101101110100100010101011100110001010001000000001000110000111011110011001101111110000100010000110000001110011', '1100001100001100111110011110110101001100100000000100000100011110110010010101000011111111000100001000111001100110010010010011110110110010010110110100010110100011011100101001100001010111000100000110101010101011011110110110101010110100011110010000101010000111', '1000100010110110010100111010100100111000100111100101100001011111100011000111110011101011011011100000101011000111010110010010011110100100110000001101110111001000000111100111011011000101010001111101000111100111110010011101011111100100111111011011110110101111', '1111001101111101111111111111001010001111100010100000010110011011100000000110010110000011011110101110001000001111110101101101111000000111101111111000011101011010000110111100000110000001001101101010100000010011000100010111100001011000101101111000101101110100', '1100100000100001010111110010000011000010100110101111100100011010111111110100011011111100001011101001010000100111100011100111000101110001001011110000000000000000000110111100000111100000111111010110010011000010011000110111001010000110011011111101011110000101', '0001101000011011010011100100000011010101110110111001111011000001010101101111110100011011010011111010001111011011100011111110101110101101111100100011111110011111010100001100011000111011010111110101000011110101011110110001011110001111011001101100110100000101']
c = 54794426723900547461854843163768660308115034417111329528183606035659639395104723918632912086419836023341428265596988959206660015436864401403237748771765948022232575597127381504670391300908215025163138869313954305720403722718214862988965792884236612959443476803344992121865817757791519151566895512058656532409472494022672998848036223706004788146906885182892250477746430460414866512005225936680732094537985671236900243908114730784290372829952741399684135984046796

print("Creating list of possible primes")

# the method to decrypt RSA
def decr(p,q):
    try:
        n = p * q
        phi = (p-1) * (q-1)
        d = inverse(e, phi)
        m = long_to_bytes(pow(c,d,n))
        return m
    except: pass

indexes = [0,1,2,3,4,5]
primes = []
perm = permutations(indexes,3)
done = False

# creating a list of permutations
for i in perm:
    primes.append(int(parts[i[0]]+parts[i[1]]+parts[i[2]],2))
prinbaby-baby-rsa.t("number of possible primes:", len(primes))

## nested loop to find the correct permutations to solve the crypto
for j in range(len(primes)):
    print("checking prime:",j+1)
    for k in range(j+1,len(primes)):
        try:
            g =decr(primes[j],primes[k])

# when the correct permutations are found, print out the flag, p & q and end the loops
            if "flag" in g.decode("utf8"):
                print(g.decode("utf8"))
                done = True
                print("p:",primes[j])
                print("q:",primes[k])
                break
        except: pass
        if done == True:
            break
    if done == True:
        break

Output from running the code:

Creating list of possible primes
number of possible primes: 120
checking prime: 1
...
checking prime: 77
flag{flbg{flcg{fldg{fleg}}}}
p: 1476664160874961383698738552409979044438151249443411059273265674671939469667177882159708009897960868174616347274301717201586595990726109094557727941451728900706638729618513258111250206236597947629663658989493197202765392977970356339
q: 1213695317515209399293442202449507480764627122584923884879300426388052747155193495297147582145122423245341251507940719305099731776464932426054136582875291784337820689592625289428081478581173862002897259103133246423738999063613128111

Written on June 14, 2022