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_longfrom string import ascii_letters, digitsfrom random import choicem =open("flag.txt", "rb").read()p =getPrime(128)q =getPrime(128)n = p * qe =65537l = (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 inrange(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 =89358184202614965204420695146909335852005489047728546708159364802496567543947m =57583133716223196764829907538392384917220505289840156337867348531239043124010leak = int('111001001010000101001011001010111111100011100000110011011100000101001001011001100110001100010010100001111011' + '0'*20,2)
#Add 20 zeros since p is a 128 bit number and we are only given 108 of themfor i inrange(2**20):#Loop over every possibility of p between leak and the max 128 bit intif n % leak ==0:breakelse: leak +=1print(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.