Crypto- Symmetric RSA

Who needs public keys? - w0152

Challenge

#!/usr/bin/env python3
from Crypto.Util.number import long_to_bytes as ltb, bytes_to_long as btl, getPrime

p = getPrime(1024)
q = getPrime(1024)

n = p*q

e = p

with open("flag.txt", "rb") as f:
	PT = btl(f.read())

CT = pow(PT, e, n)
print(f"{CT = }")

for _ in range(4):
	CT = pow(int(input("Plaintext: ")), e, n)
	print(f"{CT = }")

We are given the ciphertext and 4 chances to encrypt by the server, but no modulus. Additionally, they use e=p instead of 65537 which allows for some interesting exploits.

First, we need to find the modulus, which we can do by simply giving -1 as input and adding 1

$$-1^{e} \ mod \ n \ = n-1$$

We actually have enough information to decrypt using univariate coppersmith. This approach is used to solve the next part, however in this part, we opt for the simpler method of finding p instead

From Fermat's Little Theorem, we have

$$a^{p-1} \equiv 1 \pmod p \\ a^{p-1} - 1 \equiv 0 \pmod p \\ a^{p-1} -1 = k_1*p$$

for some arbitrary k1

If we can find k*p, then gcd(k*p,n) yields p

The server outputs a^p (mod n), so we multiply by a^-1 which gives is a^p-1 (mod n)

$$i_1 \equiv a^{p} \pmod n \\ i_1 * a^{-1} \equiv a^{p-1} \pmod n \\ i_2 = i_i * a^{-1} \ \ \ \\ i_2 -1 \equiv a^{p-1} - 1 \pmod n \\ i_2 -1 = k_1*p \ + k_2*p*q \\ i_2 - 1 = p*(k1+k2*q)$$

for some arbitrary k2

We can find p by gcd(i2-1,n) and find phi(n)

from Crypto.Util.number import inverse,long_to_bytes
from math import gcd
CT = 8600052584828896293689528788660115926954817514756700234193557515051119246391141667530886827423762722222929279563730585619613828404284349766630563892582406134473915910695147187174473272471246544807215245597474424833196157670160958609148125372687153032481755150271452820809958433131848203974160017219429195156316457405992253147011109396288957384096858991327737943098435403458631779520674744643494568759929457679813170334625629844980498522680202730653114069228167814696453150462483324995634672976824443210910132209185714581521691933590630040631733122165738455567548860036556926096750957744232570113792325485857693408344
#Sending -1 as pt to server and adding 1
n = 9543628815243070755355071260040900189425351476909065564570370313920190529276375981036789991963639259596583725814937315568459293013310902324534181148621330699995115406056267279656498468894159895916619125904180250520570709826518349783011307114593267665888764572815071642673765047913260604984017990531185726692741941165175093088509849363644416313154282802312510993932980195121194775764228315144978548633628631710269194828282750344161109355136657724261008150813026452726252084053055384516252381896908689680584819578860300032168738734210102809569769688893881065199891300510941174606594717769803609741491040147465036635159
#Sending 2 as pt to server
l1 = 5095307214428350591244769760064619737230355406629244103243240624273761700147272606544324488310345957439377255280616629328248706160838267513854585535648052703301988848650099940356004737946643573781851389509279778046176563081137567053120299032315700185941020892528390544152990764923264265068874969744337828046577084860906262129050537906142836512020393314142468257292576450634825582134055005056347675539087554247527228854741777435279342557554794312937643237541012576706805276290833209660630274862464083662247921874446378568409677856481298594239886873851596874695876371870638334338004467783058618009141463020878765113795
p = gcd(inverse(2,n)*l1-1,n)
q = n//p
print(long_to_bytes(pow(CT,inverse(p,(p-1)*(q-1)),n)))
b'LITCTF{ju57_u53_e=65537_00a144ca}'