Crypto CTF 2024

Jun 9, 2024

RM2 - Safe Prime and Sophie Germaine Prime

Breaking custom RSA implementation by supplying p and q that are both safe primes and Sophie Germaine primes

The Problem

We need to decrypt encrypted data to retrieve a flag. It operates as follows:

Setup and Prime Validation: The script prompts users to enter two 1024-bit prime numbers, p and q, which must be distinct and valid primes.
Message Encryption: The script generates a random 64-character string, converts it to a long integer, and splits it into two halves, m1 and m2. Each half is encrypted using different modulus calculations:
- c1 is computed as m1^e mod ((p-1) * (q-1)).
- c2 is computed as m2^e mod ((2p + 1) * (2q + 1)).
Flag Retrieval: The script outputs the encrypted values c1 and c2. Participants must submit the original string used for encryption. If the submission is correct, the flag is displayed; otherwise, a failure message is shown.

This script introduces a modified and non-standard RSA encryption process, in which the user can supply their own primes. The encryption result gives 2 parts of encrypted secret. The correct decryption of the secret string results in obtaining the flag. Below is the source code given.

#!/usr/bin/env python3

import sys
from Crypto.Util.number import *
from string import *
from random import *
from flag import flag
	
def die(*args):
	pr(*args)
	quit()
	
def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()
	
def sc(): 
	return sys.stdin.buffer.readline()

def randstr(l):
	return ''.join([printable[randint(0, 90)] for _ in range(l)])

def encrypt(msg, p, q):
	e = 65537
	m1, m2 = msg[:len(msg) >> 1], msg[len(msg) >> 1:]
	m1, m2 = bytes_to_long(m1), bytes_to_long(m2)
	c1, c2 = pow(m1, e, (p - 1) * (q - 1)), pow(m2, e, (2*p + 1) * (2*q + 1))
	return (c1, c2)

def main():
	border = "┃"
	pr(        "┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓")
	pr(border, ".: Welcome to RM2 task! Your mission is break our cryptosystem :. ", border)
	pr(        "┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛")
	nbit, _b = 1024, False
	pr(border, f"Please provide your desired {nbit}-bit prime numbers p, q:")
	inp = sc().decode()
	try:
		p, q = [int(_) for _ in inp.split(',')]
		if p.bit_length() == q.bit_length() == nbit and isPrime(p) and isPrime(q) and p != q:
			_b = True
	except:
		die(border, f"The input you provided is is not valid!")
	if _b:
		e, n =  65537, p * q
		s = randstr(nbit >> 4).encode()
		m = bytes_to_long(s)
		assert m < n >> 2
		c1, c2 = encrypt(s, p, q)
		pr(border, f'c1 = {c1}')
		pr(border, f'c2 = {c2}')
		pr(border, f'Now, send us the secret string to get the flag: ')
		_m = sc().strip()
		if _m == s:
			die(border, f'Congrats, you got the flag: {flag}')
		else:
			die(border, f'The secret string is not correct! Bye!!')
	else:
		die(border, f"Your input does not meet the requirements!!!")

if __name__ == '__main__':
	main()

The Approach

If we were to key in just any random 1024 bit prime, for example with getPrime, for p and q, when the modulus for m1 is calculated using p-1 times q-1, we will be having a hard time to factorize p-1 and q-1. We need to be able to fully factorize the modulus in order to find the private key d1

When trying to generate random prime using getPrime, and pass p-1 and 2p+1 to factordb.com, it was not able to fully factorize. Factorizing locally using ecm.factor() in sage also took to long to complete.

If (p-1)/2 and (q-1)/2 are prime, then we can know that the factors for the modulus are 2 * 2 * (p-1)/2 * (q-1)/2 . This form can be achieve if p and q are safe prime. A safe prime is a prime number that can be written in the form 2k+1, where k is also a prime number.

However, if 2*p + 1 and 2*q + 1 are not prime, we encounter the same problem of not being able to factorize the modulus for m2. o overcome this, we need to have Sophie Germain prime. A Sophie Germain prime is a prime number p for which 2p+1 is also a prime number.

Therefore, our goal is to find prime numbers which exhibit both the properties of safe prime and Sophie Germain prime at the same time.

The Solution

We will be using this python module to generate safe primes efficiently, which utilizes OpenSSL library. Once a safeprime is generated, we will manually check it 2*safeprime + 1 is also a prime. This might take some time, but not too long.

pip install gensafeprime

import gensafeprime

while True:
	q=gensafeprime.generate(1024)
	if(isPrime(2*q+1)):
		print(q)
		break
		
while True:
	q=gensafeprime.generate(1024)
	if(isPrime(2*q+1)):
		print(q)
		break

The value for p,q:

169194620251703858075766787002845117826782728307804112241541460118297294592839800584882431985607581317467148795429884320941043407650495244580290142763342255204639646424792083004834455333121989625428010280368195491460528110022173187250961479792664640176528892927821163498029868502993224699703551060234194136003,178086053588076990370726365945746370167509100523491591032981698822451130074770989110398704889900487505668890200447437395599465343714147010785511521737038970446868266619658036032874035398809496255700351082467224430010500840903667131391176788939702167995481063647081215602275653776272564038256557685746047286319

solver (manual interaction)

from Crypto.Util.number import *

p1=(p-1)//2
q1=(q-1)//2
d1=inverse_mod(65537,(p1-1)*(q1-1)) #phi = (2-1) * (2-1) * (p1-1) * (q1-1)
p2=2*p+1
q2=2*q+1
d2=inverse_mod(65537,(p2-1)*(q2-1))

#output from remote challenge
c1 = 2666405150814882406020869508843979521823711936771508675348373851431360083458929650387111870892332389051072028978363538533019745810391287890214563894362001847104148239051954278213640220920881345285111470092163762871509850653697760159655690385911898285939611459475146567114528716219696052329619769333801742470270961294635339828828755212970003964478434463566322063157829126515859264290838849153463643265076495605490393991218241085054283656488681594567818
7569066336248309604099096263759301684928873069540725060123531066731951289102830176196797961598058322124538820268841711231372544237399086811850903588416865592680024336
c2 = 9899770990649464461536158716323908196237719110660135972171955868688058086919446809023281977200245043905852903067996655400219667722583558326385729030258633834595528047766378994184385884997442379498945710520757861764015762598149862273781378967970605837688660935860165780315994742621521591986123157109364662145556466437768785414552812306075153332179813173388058622551779353654834696655477764766595184158994338622689156787713136095227648931338217236062500
2874949745704914541871646405867846042366066387248683760913799463136248537283410871219561255105515774205475936977667465334871195441457956341234307457631890231954831593

m1=pow(c1,d1,2*p1*2*q1)
m2=pow(c2,d2,p2*q2)
print((long_to_bytes(m1) + long_to_bytes(m2)).decode())
#'gMryPw#bt@m_SYG9!Z$87#a!bTm#6"jHLFCzvIglH6bgp$I%YT%ie<]r7!EA.;E1'

FLAG: CCTF{i_l0v3_5UpeR_S4fE_Pr1m3s!!}

Joe-19

RSA with factorable modulus

The following source code and output were given:

#!/usr/bin/env sage

from GPT import GPT6 # deep fake 
from Crypto.Util.number import *
from flag import flag

P = [GPT6('A 512-bit prime appears in consecutive digits of e') for _ in range(4)]
n, m = prod(P), bytes_to_long(flag)
c = pow(m, 0x10001, n)
print(f'n = {n}')
print(f'c = {c}')

n = 8098851734937207931222242323719278262039311278408396153102939840336549151541408692581651429325092535316359074019383926520363453725271849258924996783681725111665666420297112252565291898169877088446887149672943461236879128453847442584868198963005276340812322871768679441501282681171263391133217373094824601748838255306528243603493400515452224778867670063040337191204276832576625227337670689681430055765023322478267339944312535862682499007423158988134472889946113994555274385595499503495488202251032898470224056637967019786473820952632846823442509236976892995505554046850101313269847925347047514591030406052185186963433
c = 7109666883988892105091816608945789114105575520302872143453259352879355990908149124303310269223886289484842913063773914475282456079383409262649058768777227206800315566373109284537693635270488429501591721126853086090237488579840160957328710017268493911400151764046320861154478494943928510792105098343926542515526432005970840321142196894715037239909959538873866099850417570975505565638622448664580282210383639403173773002795595142150433695880167315674091756597784809792396452578104130341085213443116999368555639128246707794076354522200892568943534878523445909591352323861659891882091917178199085781803940677425823784662

The modulus seems to be generated from 4 512-bit primes, in which the primes are taken from the consecutive digits of e (Euler number), using the help of GPT. This indicates that the modules might factorable.

Using factordb, the modulus can be fully factorized. Although the modulus consists of more than 2 primes, unlike the normal RSA, there is no issue in finding the private key. The phi can still be calculated as (p-1)*(q-1)*(r-1)*(s-1), in which p, q, r, s are all of the prime factors of the modulus. Afterwards, the private key d can be calculated as e modulo inverse phi.

solver

from Crypto.Util.number import *

p=7728751393377105569802455757436190501772466214587592374418657530064998056688376964229825501195065837843125232135309371235243969149662310110328243570065781
q=9688632098638681429535439991332657144752666147923336383829750592576742104399942931057096761773496510622226977570278994077236841491368959008277469453600569
r=10019005372961705640183251650710051163228093250949727357306333102512304273058618645339800283588040423877666492199352609508401454089083503146788384653241593
s=10795109107229646654467923653403055635071360620150038008453082390943756377071343139771120080956310498862485323957447467376538994662280143050510681877597429

d=inverse_mod(65537,(p-1)*(q-1)*(r-1)*(s-1))
long_to_bytes(pow(c,d,n)).decode()

FLAG: CCTF{ASIS_h1r3_7aL3nT5_t0_cO1La8orAt3_!N_Crypto_CTF!}

Alibos

Weak custom cryptosystem

The following source code and output are given.

#!/usr/bin/env python3

from Crypto.Util.number import *
from gmpy2 import *
from secret import d, flag

get_context().precision = 1337

def pad(m, d):
	if len(str(m)) < d:
		m = str(m) + '1' * (d - len(str(m)))
	return int(m)

def genkey(d):
	skey = getRandomRange(10 ** (d - 1), 10 ** d)
	pkey = int(10**d * (sqrt(skey) - floor(sqrt(skey))))
	return pkey, skey

def encrypt(m, pkey):
	m = pad(m, len(str(pkey)))
	d = len(str(pkey))
	c = (pkey + d ** 2 * m) % (10 ** d)
	return c

pkey, skey = genkey(d)

m = bytes_to_long(flag)
c = encrypt(m, pkey)

print(f'pkey = {pkey}')
print(f'enc  = {c}')

pkey = 8582435512564229286688465405009040056856016872134514945016805951785759509953023638490767572236748566493023965794194297026085882082781147026501124183913218900918532638964014591302221504335115379744625749001902791287122243760312557423006862735120339132655680911213722073949690947638446354528576541717311700749946777
enc  = 6314597738211377086770535291073179315279171595861180001679392971498929017818237394074266448467963648845725270238638741470530326527225591470945568628357663345362977083408459035746665948779559824189070193446347235731566688204757001867451307179564783577100125355658166518394135392082890798973020986161756145194380336

The encryption is achieved by modulo 10**d, which is equivalent of taking the last d digits of pkey + d ** 2 * m. d can be derived from the length of pkey, which is found to be 313. d**2 is equal to 97969. Let us refer the product of 97969 and padded_m as t

d = 313
d**2 = 97969
padded_m is 313 digits

97969 * padded_m = t
t is 318 digits

pkey * t = enc mod (10**313)

enc - pkey = negative value

10**d + (enc-pkey) = the last 313 digits of t

therefore, we only have to brute force the first 5 digits of t
once t is recovered, padded_m can be calculated, and the padding consisting of '1' digits can be removed, revealing the original m