date
solved in time of CTF
web category

Description

No one can break my rsa encryption, prove me wrong !!

Flag

cybergrabs{r481n_cryp70sy5t3m_15_1nt3r35t1n6_8ut_num83r_sy5t3m_15_3v3n_m0r3_1nt3r35t1n6}

Detailled Solution

Challenge - Unbr34k4bl3 - 942 points - 7 solves

Flag Format: cybergrabs{}

Author: Mritunjya

output.txt source.py

Here the content of the output.txt

n:267362205744654830055585746250317245125479735269853713372687604676608285629127977574310510441358104169652444917329986129098240750401425257601282268733834091593200445244725460613298199140690597119199763970064359847666802255456013592631532853951273286284878230893809080250386646832110506402289378691079462364884899662707502858007857457806853302449695351229004051902617728418480990341155900565542195318206284041182555579388392863474548687784403795738945489219689610881075059037192656116884269582257788959555951074322245033492165406470004019896763472332962300128378758934128374039937693688718317737657946435827745981009467876838127075176808098467305627394472135213533754815713468369763665632168616054982745256773112537152292099369137072982289095951236065885648588670059655452986720063260146952425798150221407866669449837430999779776718047668562687216933053536759554900663226163021145439386115076821161003965334731127329486856711654741683760749336235855319144478194501034662638054193682000283319917096796971
ip:65491313526527942082900846848440586365393305192439699810712229312474732937502934334921061033822729150056656630858908294464249602368303871630644420585085642204592189073314730233318796675949142968346807766087775542461078648703191450221286915401606901781524237580646760734493950360267230729125514156671619347616
iq:97034409222811998555255396847918439343239825222504093225438959283117395075159811973044380473862026342866489725039905931430797650466599952795602909181290621103197493223080488468216279214006070950393096075839913101687588555346523517436421698916141195686143520143972735534402754157166545851899187305574703394138
c1:103687839591259628532585171241634220321003599759860095236990117623065664975385083122971507015385215246948744078816596026772744294701233346732383214113445480056584639282712898073542520168025667980980057512174927564196375256682206601425714094930670415979638437119896258396784978194294581076901000507291277729888015413204446158926865037965291316577726275211006619643531704449499845352147547986667837681877488120093302675775792115380914560935989896453159186176952126083066619414338359303033325593504442257083571002878083287293828310810483726711816109297046925744157605591270761804522735216774801135342322479770391505911100485259078064775709124730966391629468398187269096529671187877954443617005248499140455160589093379715757808387108825458007733207099871941497372539249357162437077379731766825184301649010270921003130776410066972952756983157217280397531412843118202051922048479332111760976091302376602674590153876045380552746826056547929265785960676415919260117136285580971488670143947003566230254837742519
c2:171159809874438596904787534111610260851529969068192878049771299710688449419966698428704180474774734112617652498954998301185232279153644173070897800123538474930545720934844727376637921072749901149514789723141795042182408704214998390482343965532559149095934231081729041402598776401575561653660624208366051273601230345754361771067242657825194926706328336322383296953817730346429591680463526267530372572332663327157636745578067246913529155120642276894180354494816411827468256127607558873938451944866168777913756913920336763454881108023708284527878322162463081091624350220308273550298342755582044860337692076513609120342318151660103532559583052954725303030103413034880155621982581677423267299780543045375467310718078800411397780269409147558121862038983169509828944551199620508493589091401498720419409158373805529997911655270528589050795214164221299581104149954423726171539700223299445034347915430838395255700425648686205603925507474877720680274914513203566997846945579395522000899007446797091893230195801607

Here the content of source.py

from Crypto.Util.number import *
from secret import *


assert (x>2 and x%2 == 0)
assert (isPrime(e1) and isPrime(e2))

def functor():
	val1 , val2 = 0,0
	for i in range(x+1):
		val1 += pow(e1,i)
	for j in range(3):
		val2 += pow(e2,j)
	assert (val1 == val2)

def keygen():
	while True:
		p,q = [getStrongPrime(1024) for _ in range(2)]
		if p%4==3 and q%4==3:
			break

	r = 2
	while True:
		r = r*x
		if r.bit_length()>1024 and isPrime(r-1):
			r = r-1
			break

	return p,q,r


functor()
p,q,r = keygen()
n = p*q*r
print(f"p:{p}")
print(f"q:{q}")
ip = inverse(p,q)
iq = inverse(q,p)
c1 = pow(bytes_to_long(flag[0:len(flag)//2].encode('utf-8')),e1,n)
c2 = pow(bytes_to_long(flag[len(flag)//2:].encode('utf-8')),e2,n)
print(f"n:{n}",f"ip:{ip}",f"iq:{iq}",f"c1:{c1}",f"c2:{c2}",sep="\n")

For solving this challenge, two ressources have been used:

and here the full and commented solution:

from Crypto.Util.number import *
from sympy import Symbol,Eq,solve
from sympy.crypto.crypto import rsa_private_key


# Challenge Data
n=267362205744654830055585746250317245125479735269853713372687604676608285629127977574310510441358104169652444917329986129098240750401425257601282268733834091593200445244725460613298199140690597119199763970064359847666802255456013592631532853951273286284878230893809080250386646832110506402289378691079462364884899662707502858007857457806853302449695351229004051902617728418480990341155900565542195318206284041182555579388392863474548687784403795738945489219689610881075059037192656116884269582257788959555951074322245033492165406470004019896763472332962300128378758934128374039937693688718317737657946435827745981009467876838127075176808098467305627394472135213533754815713468369763665632168616054982745256773112537152292099369137072982289095951236065885648588670059655452986720063260146952425798150221407866669449837430999779776718047668562687216933053536759554900663226163021145439386115076821161003965334731127329486856711654741683760749336235855319144478194501034662638054193682000283319917096796971
ip=65491313526527942082900846848440586365393305192439699810712229312474732937502934334921061033822729150056656630858908294464249602368303871630644420585085642204592189073314730233318796675949142968346807766087775542461078648703191450221286915401606901781524237580646760734493950360267230729125514156671619347616
iq=97034409222811998555255396847918439343239825222504093225438959283117395075159811973044380473862026342866489725039905931430797650466599952795602909181290621103197493223080488468216279214006070950393096075839913101687588555346523517436421698916141195686143520143972735534402754157166545851899187305574703394138
c1=103687839591259628532585171241634220321003599759860095236990117623065664975385083122971507015385215246948744078816596026772744294701233346732383214113445480056584639282712898073542520168025667980980057512174927564196375256682206601425714094930670415979638437119896258396784978194294581076901000507291277729888015413204446158926865037965291316577726275211006619643531704449499845352147547986667837681877488120093302675775792115380914560935989896453159186176952126083066619414338359303033325593504442257083571002878083287293828310810483726711816109297046925744157605591270761804522735216774801135342322479770391505911100485259078064775709124730966391629468398187269096529671187877954443617005248499140455160589093379715757808387108825458007733207099871941497372539249357162437077379731766825184301649010270921003130776410066972952756983157217280397531412843118202051922048479332111760976091302376602674590153876045380552746826056547929265785960676415919260117136285580971488670143947003566230254837742519
c2=171159809874438596904787534111610260851529969068192878049771299710688449419966698428704180474774734112617652498954998301185232279153644173070897800123538474930545720934844727376637921072749901149514789723141795042182408704214998390482343965532559149095934231081729041402598776401575561653660624208366051273601230345754361771067242657825194926706328336322383296953817730346429591680463526267530372572332663327157636745578067246913529155120642276894180354494816411827468256127607558873938451944866168777913756913920336763454881108023708284527878322162463081091624350220308273550298342755582044860337692076513609120342318151660103532559583052954725303030103413034880155621982581677423267299780543045375467310718078800411397780269409147558121862038983169509828944551199620508493589091401498720419409158373805529997911655270528589050795214164221299581104149954423726171539700223299445034347915430838395255700425648686205603925507474877720680274914513203566997846945579395522000899007446797091893230195801607

# n = p*q*r
print("[+] n = p * q * r ")

# Step One finding x
print("[+] Finding r ...")
r = 2
x = 2
while True:
	r = pow(2,x)
	if r.bit_length()>1024 and isPrime(r-1) and n % (r-1) == 0:
		r = r-1
		break
	x+=1
x = x -1

# Sanity Check for x
print("[-] Guessing x = 4")
x = 4

# r prime
print("r =",r)

# pq
print("[+] pq found ...")
pq = n //r
print("pq = ",pq)

# Sanity check for pq
assert n == pq * r


# Finding e1 and e2
for e1 in range(2,10):
	for e2 in range(2,10):
		if (pow(e1,x+1)-1) // (e1-1) == (pow(e2,3)-1)// (e2-1):
			_e1=e1
			_e2=e2
			break

e1=_e1
e2=_e2
print("[+] e1 = ",e1)
print("[+] e2 = ",e2)

# Factoring p*q
print("[+] Factoring pq with https://ctftime.org/writeup/16770")
p=Symbol('p')
q=Symbol('q')
equation1 = Eq(ip*p+iq*q-pq-1,0)
equation2 = Eq(p*q-pq,0)
solution = solve((equation1,equation2),(p,q))
for p,q in solution:
	if pq %p == 0:
		p=int(p)
		q=int(q)
		break
print("p = ",p)
print("q = ",q)

# H-Rabin
print("[+] Solving H-Rabin cryptosystem")
print("[+] Hayder Raheem Hashim / Journal of Mathematics and Statistics 10 (3): 304-308, 2014")

mp = pow(c1,(p+1)//4,p)
mq = pow(c1,(q+1)//4,q)
mr = pow(c1,(r+1)//4,r)

_mp = -mp % p
_mq = -mq % q
_mr = -mr % r

b1 = pow((q*r ) % p,-1,p)*1
b2 = pow((p*r ) % q,-1,q)*1
b3 = pow((p*q ) % r,-1,r)*1

x1 = (mp*b1*(q*r)+mq*b2*p*r +mr*b3*p*q)%(p*q*r)
x2 = (_mp*b1*(q*r)+mq*b2*p*r +mr*b3*p*q)%(p*q*r)
x3 = (mp*b1*(q*r)+_mq*b2*p*r +mr*b3*p*q)%(p*q*r)
x4 = (mp*b1*(q*r)+mq*b2*p*r +_mr*b3*p*q)%(p*q*r)
x5 = p*q*r-x1
x6 = p*q*r-x2
x7 = p*q*r-x3
x8 = p*q*r-x4


#print(long_to_bytes(x1))
print("[-] After looking at all values, we keep only the second one ...")
print(long_to_bytes(x2))
#print(long_to_bytes(x3))
#print(long_to_bytes(x4))
#print(long_to_bytes(x5))
#print(long_to_bytes(x6))
#print(long_to_bytes(x7))
#print(long_to_bytes(x8))

print("[+] Multi-prime rsa")
primes=[p,q,r]
args = primes+[e2]
d=rsa_private_key(*args)[1]
pt=long_to_bytes(pow(c2,d,n))
print(pt)

That’s all Electro !