Johnny's a math whiz and figured out a method to encrypt his messages securely.
He's a bad programmer though, and his program seems to be leaking some important bits.
Can you decrypt the flag?
We are given the code to a python program and a container we can start which runs it
from Crypto.Util.number import getPrime, inverse, bytes_to_long
from string import ascii_letters, digits
from random import choice
m = open("flag.txt", "rb").read()
p = getPrime(128)
q = getPrime(128)
n = p * q
e = 65537
l = (p-1)*(q-1)
d = inverse(e, l)
m = pow(bytes_to_long(m), e, n)
print(m)
print(n)
p = "{0:b}".format(p)
for i in range(0,108):
print(p[i], end="")
From what we can see in the code, this is a simple RSA chall.
What the code does is it generates the variables for an RSA encryption algorithm, but then leaks the first 108 bits of p.
What we need to do is loop over every number between the leaked number and the max 128 bit int and see if the number can divide n with a remainder of 0, if it can, we have p and can therefore decrypt
n = 89358184202614965204420695146909335852005489047728546708159364802496567543947
m = 57583133716223196764829907538392384917220505289840156337867348531239043124010
leak = int('111001001010000101001011001010111111100011100000110011011100000101001001011001100110001100010010100001111011' + '0'*20,2)
#Add 20 zeros since p is a 128 bit number and we are only given 108 of them
for i in range(2**20): #Loop over every possibility of p between leak and the max 128 bit int
if n % leak == 0:
break
else:
leak +=1
print(leak)
print(n//leak)
This script finds p, prints it and also prints q afterward.
Using these variables we can now easily decode the RSA. I personally used https://www.dcode.fr/rsa-cipher, it's my favorite.
