Asis CTF 2013: "RSAng"

Writeup author: Radu Caragea

Task text:

This message is encrypted using the prime factors of N. Decrypt the message.
 
 
N 	=  136463296143190893248608270448493439350683115492680876168052084053504347848230208722375209906076869052896867483336405778205506777456239889195254751404720423599579856449118314029926341504368322006603240157122006887052352260584975471045726061549619820648607756554188235927302932154082823424745427535138517580059079182622982686168676727690710935334448342460007367100561867135456783067679052102951400317012276135721843672557488711786097028300122487504246207343408690682175135816894247936690735246673985277504237071409859401185555290479154689954442396078547166388871978321863215123445269948324347122830270551854130365741961149443091305418900821360286967705810624380568422193310901491451664233271486835428015602712828527839237760712498204208114606471362410690870710499020885304151928570632315330437235330924071236528549152143092328833484016372976817809299430339752106123272706667690980774118545338761390919046832338928913059106351087015273177895380149217373395580948428521961929052291618261409715145038026920685297885235683434107218249548518659574493203836870070093674704878498465104238178877833471640168999551981025958271865584457582649595664499635489167898398826429084686279399959537724187268210760718340639939389766681703213695409551029265784749153180083564347733676434492122290166926822855552175712346350104533901079605669192289178418165584907326210349152609265563881542151049862642882025360604692084264752182798892702414638180781403398216616666472863758371330058299406233359567750413748257953598843651612399709945608339073191578573877985362619301768016485017815171486743934037935902150228210340093187387036580763941637989511155597643722984057627086517479392172108031663245553269
enc_1	=  4188160662599010174333548247685465532033351297387524815811773992671479977422618764401946893197235449672025865744876037296597803160460212992955058447853841441182903712523202252757870145277159399746160155397483457257039112600007241954480881015445531286192144571027243892228576818168813455375617151017464525723722073042041883791132523658563304417151790917522274493274227303509938514356112988348696023342023166244849691644007515644961926926736453325652075890535919979868708560016357898219876629861540536239279442399338703980029893388678956999727836001676577966276268353521042207752705807265023288374295135365964952512264364926080725284715058320037468560258406119118666475101064017957362872531020909563663753240129681129606122929658571213084198551487539547577409091082469337862305148623288189242930160225020927721422818302835971919402458528934
enc_2	=  6049049661741129561339303988250162617703359741970199356749378099535308799521119296163475813567458644038456685905251522625056377260310087845057811228022836098917570328692580410899852889868960996513905266043335963520913743708134923879544500911079066640658342641576456724637857109609913138972587873848795314132791317122747052648231297078735128282339170389129703582587817548539040826603188468662975329145727078616857156409325283263490433476018586450960082502578543327451065633585123695731081960986876439520499678158646526292218543279767834119677467758578802705169018711527506297869276113561542222807369071584959189923897216079505316482443445467837921144205079761354928950270172051270453170856002545491432278972735662895438668870901370521394906635478044848448535690635490093836659267778026686404695474454443310769209580317339039949689309577128
enc_3	=  9297802808564228678857927735224258610176831223455462482108153962953283311112501933779642540831558523911908205264682548531027493458025348252477502958948277516597689610204247227516319189048436710254675204218913508162139428248916620471317757210444645620644754294112426431692939788347835259617673728076204145049918767636122119264147566892091600628134179775710906591426338082246629946748851355701691716873854064848390273287305765646761438968986164159947841015011854342290060053810459830057357847548324695563067411557873081187572229935066117850179208775004384867270372650455853756560763012162682268812544173997311505136324203900399349629488710197844813293107115270398692552357803651576615589484454781227778727051440858478438251726051391317986762487421941570502251822920317312304622541764818356928105898291743494415190324388360012261032469805293
enc_4	=  713095983409993528016630065648951013409887429450761159296479210782308084847050785300379490902448647458053364322993274237841476340954537003347555548992827654062094884577630320399338426853024680425709980978726290825928571411715417634212022523987025390940108095446209802316068849127107378425087055832984628808129531097287891984529260048649164000341136589805930287941174070455962380115617312855801447326371361475429811263285218112383055283949280091896985779211927696867430269968278138068400828124612158603851472016327854927370226178776190765638542240547246882872033038792494915187774790763271179846203704834184269540668646905004118327597860873987248913148268250014480899515845595580486997925049895214602419037682253683176691877538075243485739730794370764108792093424342949560517002862934953109055108423633725444594683266260073663364732952255
enc_5	=  10309778311674135836145162475142299890445328570998831868156889990227275287204954712195141311549279047953844775828171871944522109110470024787792366772581241453340259883183812924297131077506375091086889140550405275547002202216935333211274901846970064522877611909017778486075399188006657623263902100044828896866180655435221665929435914366779334701622735670714649165956831390471034827078404866534094264914677879030956272977839491780410171625330771079943455183946885337962048237633491024513227027839179415230496573264968451527246966618074421625677382526573096067979952606553854268016651712174361578916100364115941853700612277618158243626702349480460819792765645689509997114148748479096516230468934427015454217368508102362912163051749856763103972010705773880053579573724226945229453471505368052572019992934401394664840254259798167531746190494146
enc_6	=  8939535907261295438433886577386432968291926162277924912979941380189504000322310159787894619015550096747658897136943700072192920334615223423230154197591756541966832740944457435736068401948276698864982347929802551347213730712997519211436818145872722485367264219104124473346589051164722340414948298088909961344463800461486219156960782319672049123860381674970981713865865119998917955886468613202521879160392276542945726096267432761588212550950818569769983241315782390152313705093940640027041352082844550311829177150159737347964813330180325283882516072009654288888676591648012847062527444169352000893928289409020106115561912814987882374652419114381836807085680725260815445689968522849732254659773192714360607196619281714422460754645088867512471482029657153787836396684484646302575186890717770078233479877360251173401000006298555695416782863190

Initial reconnaisance

As usual, the task title gives some insight into what the task is about:

RSA - the algorithm used
ng - unknown, might come from next-generation. I assumed it was RSA using a modulus that has more than 2 prime factors

The modulus itself looks absolutely huge, how many bits does it have? Let's see

Python 2.7.5 (default, Jul  2 2013, 03:32:08) 
[GCC 4.7.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> bin(136463296143190893248608270448493439350683115492680876168052084053504347848230208722375209906076869052896867483336405778205506777456239889195254751404720423599579856449118314029926341504368322006603240157122006887052352260584975471045726061549619820648607756554188235927302932154082823424745427535138517580059079182622982686168676727690710935334448342460007367100561867135456783067679052102951400317012276135721843672557488711786097028300122487504246207343408690682175135816894247936690735246673985277504237071409859401185555290479154689954442396078547166388871978321863215123445269948324347122830270551854130365741961149443091305418900821360286967705810624380568422193310901491451664233271486835428015602712828527839237760712498204208114606471362410690870710499020885304151928570632315330437235330924071236528549152143092328833484016372976817809299430339752106123272706667690980774118545338761390919046832338928913059106351087015273177895380149217373395580948428521961929052291618261409715145038026920685297885235683434107218249548518659574493203836870070093674704878498465104238178877833471640168999551981025958271865584457582649595664499635489167898398826429084686279399959537724187268210760718340639939389766681703213695409551029265784749153180083564347733676434492122290166926822855552175712346350104533901079605669192289178418165584907326210349152609265563881542151049862642882025360604692084264752182798892702414638180781403398216616666472863758371330058299406233359567750413748257953598843651612399709945608339073191578573877985362619301768016485017815171486743934037935902150228210340093187387036580763941637989511155597643722984057627086517479392172108031663245553269)
'0b1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000111000011011110010011111100010011100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011101100101010001000010100111100000101001000101110111001111000110100010101010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000101011110010100110001101110110100000011001101010001000101000110001000011100101001111011101100011001000011001000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011000010011110000010000010000101010000011101100011101110110110011111000000001011001101111100111001111110001100100101101010011011011101110111001110101'

What an unexpected surprise, we can see some structure into the modulus. Let's lay it out a bit more nicely

Modulus factorisation

0b100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
10001110000110111100100111111000100111
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
1110110010101000100001010011110000010100100010111011100111100011010001010101
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
1010111100101001100011011101101000000110011010100010001010001100010000111001010011110111011000110010000110010001
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
11000010011110000010000010000101010000011101100011101110110110011111000000001011001101111100111001111110001100100101101010011011011101110111001110101

This looks like a number of the form $N = (2^M + a)(2^M + b)(2^M + c)(2^M + d)$ .
The log base 2 of the modulus is 5568 so $M=1392$ .
We can now do some math to see what info we can get out of the 4 binary sequences:

$N = (2^M + a)(2^M +b)(2^M +c)(2^M +d)$

$N = 2^{4M} + 2^{3M}(a + b + c + d) + 2^{2M}(ab + ac + ad + bc + bd + cd) + 2^M(bcd + acd + abd + abc) + abcd$

Let:

$p = a + b + c + d$

$q = ab + ac + ad + bc + bd + cd$

$r = bcd + acd + abd + abc$

$s = abcd$

You'd be tempted to think that the 4 binary sequences above correspond directly to $p$ , $q$ , $r$ , $s$ but there is a catch: only $s$ is equal to its respective binary sequence.
The other ones might end in a 0 or more as an even number of odd numbers has an even sum. But we can just bruteforce it, so we'll worry about that later.
How can we find out $a$ , $b$ , $c$ and $d$ given $p$ , $q$ , $r$ and $s$ ? Highschool math to the rescue:

$(X - x_1)(X - x_2)(X - x_3)(X - x_4) = 0$

$X^4 -(x_1 + x_2 + x_3 + x_4)X^3 + (x_1 x_2 + x_1 x_3 + x_1 x_4 + x_2 x_3 + x_2 x_4 + x_3 x_4)X^2 - (x_2 x_3 x_4 + x_1 x_3 x_4 + x_1 x_2 x_4 + x_1 x_2 x_3)X + x_1 x_2 x_3 x_4 = 0$

And this is normally solvable, there are lots of sites on the web with code that implement either Carpenter's solution to the quartic or the standard one. The problem is that the coefficients are huge so precision will most likely suffer. I used the first thing that popped up on a Google search http://adorio-research.org/wordpress/?p=4499 and replaced the math stuff with gmpy2 equivalents.

import math
import gmpy2
 
gmpy2.get_context().precision=5000
 
 
from polycubicroot import *
def Carpenter(p, q,r, s):
	p = gmpy2.mpfr(p)
	q = gmpy2.mpfr(q)
	r = gmpy2.mpfr(r)
	s = gmpy2.mpfr(s)
	"""
	Solves for all roots of the quartic polynomial P(x) = x^4 + px^3 + qx^2 + rx + s.
	"""
	#print "@@@ inside Carpenter", p,q,r,s
	pby4 = p/4.0
	C = ((6 * pby4) - 3*p)*pby4 + q
	D = (((-4*pby4) + 3*p)*pby4 - 2*q)*pby4 + r
	E = (((pby4 - p)* pby4 + q)*pby4 - r)*pby4 + s
	#print "C, D, E=",C, D, E
	root = None
	for zero in polyCubicRoots(2*C, (C**2 - 4*E), -D**2):
		#print "zero = ", zero
		if type(zero)== type(gmpy2.mpfr(1.0)) and zero > 0.0:
		   root = zero
		   #print "found a positive root."
		   break
	if root == None:
		return None
	sqroot = gmpy2.sqrt(root)
	Q1 = -root/4.0 - C/2.0 - D/2.0 / sqroot
	Q2 = -root/4.0 - C/2.0 + D/2.0 / sqroot
	#print "Q1,Q2=", Q1, Q2
	sqy2 = sqroot/2.0
	if Q1 >= 0.0:
	   sqQ1 = gmpy2.sqrt(Q1)
	   z1 = sqy2 + sqQ1 -pby4
	   z2 = sqy2 - sqQ1 -pby4
	else:
	   sqQ1 = gmpy2.sqrt(-Q1)
	   z1 = (sqy2-pby4,   sqQ1)
	   z2 = (sqy2-pby4, - sqQ1)
	if Q2 >= 0.0:
	   sqQ2 = gmpy2.sqrt(Q2)
	   z3 = -sqy2 - sqQ2 -pby4
	   z4 = -sqy2 + sqQ2 -pby4
	else:
	   sqQ2 = gmpy2.sqrt(-Q2)
	   z3 = (-sqy2-pby4, sqQ2)
	   z4 = (-sqy2-pby4, -sqQ2)
	return (z1, z2,z3, z4)

The idea is to get a 4-tuple solution and iterate to the left and to the right of any of the 4 roots to see if we get a divisor of $s$ which should be exactly $a b c d$ . If we get one then the problem is basically solved.
The only remaining issue was that we don't know how many zeroes each of $p$ , $q$ and $r$ have. Let's try all combinations from 0 zeroes to 3 zeroes:

p= 0b10001110000110111100100111111000100111
q= 0b1110110010101000100001010011110000010100100010111011100111100011010001010101
r= 0b1010111100101001100011011101101000000110011010100010001010001100010000111001010011110111011000110010000110010001
s= 0b11000010011110000010000010000101010000011101100011101110110110011111000000001011001101111100111001111110001100100101101010011011011101110111001110101
 
A=[]
B=[]
C=[]
D=[s]
 
for i in range(0,3):
        A.append(p * (2**i))
        B.append(q * (2**i))
        C.append(r * (2**i))
 
for i in A:
        print "===================="
        for j in B:
                for k in C:
                        for l in D:
                                (x1, x2, x3, x4) = Carpenter(-i,j,-k,l)
                                # since sometimes the solution will consist of complex numbers, we'll just disregard those with a try-except
                                try:
                                        #approximate value of x1
                                        aprox = int(x1.__floor__())
                                        for step in range(0,10000):
                                                #try to the right
                                                if s % (aprox + step) == 0:
                                                        print aprox + step
                                                #and to the left
                                                if s % (aprox - step) == 0:
                                                        print aprox - step
                                except:
                                        pass

 $ python -i  /tmp/quart.py 
 
====================
152587894837
152587893565
152587892895
152587895947
====================
====================
152587895947
152587895947
152587894837
152587893565
152587892895
>>> s
542101138623964531063804924003409641945886325L
>>> s - 152587894837 * 152587893565 * 152587892895 * 152587895947
0L
>>>

How about that? We got all four factors! Let's check that these actually make up $N$ .

>>> N - (2**1392 + 152587894837) * (2**1392 + 152587893565) * (2**1392 + 152587892895) * (2**1392 + 152587895947)
0L
>>> N % (2**1392 + 152587894837)
0L
>>> N %  (2**1392 + 152587893565) 
0L
>>> N % (2**1392 + 152587892895)
0L
>>> N % (2**1392 + 152587895947)
0L

Decrypting the ciphertexts

Now that we have factorised the modulus everything should be smooth sailing from here. Let's look at the ciphertexts again:

N 	=  136463296143190893248608270448493439350683115492680876168052084053504347848230208722375209906076869052896867483336405778205506777456239889195254751404720423599579856449118314029926341504368322006603240157122006887052352260584975471045726061549619820648607756554188235927302932154082823424745427535138517580059079182622982686168676727690710935334448342460007367100561867135456783067679052102951400317012276135721843672557488711786097028300122487504246207343408690682175135816894247936690735246673985277504237071409859401185555290479154689954442396078547166388871978321863215123445269948324347122830270551854130365741961149443091305418900821360286967705810624380568422193310901491451664233271486835428015602712828527839237760712498204208114606471362410690870710499020885304151928570632315330437235330924071236528549152143092328833484016372976817809299430339752106123272706667690980774118545338761390919046832338928913059106351087015273177895380149217373395580948428521961929052291618261409715145038026920685297885235683434107218249548518659574493203836870070093674704878498465104238178877833471640168999551981025958271865584457582649595664499635489167898398826429084686279399959537724187268210760718340639939389766681703213695409551029265784749153180083564347733676434492122290166926822855552175712346350104533901079605669192289178418165584907326210349152609265563881542151049862642882025360604692084264752182798892702414638180781403398216616666472863758371330058299406233359567750413748257953598843651612399709945608339073191578573877985362619301768016485017815171486743934037935902150228210340093187387036580763941637989511155597643722984057627086517479392172108031663245553269
enc_1	=  4188160662599010174333548247685465532033351297387524815811773992671479977422618764401946893197235449672025865744876037296597803160460212992955058447853841441182903712523202252757870145277159399746160155397483457257039112600007241954480881015445531286192144571027243892228576818168813455375617151017464525723722073042041883791132523658563304417151790917522274493274227303509938514356112988348696023342023166244849691644007515644961926926736453325652075890535919979868708560016357898219876629861540536239279442399338703980029893388678956999727836001676577966276268353521042207752705807265023288374295135365964952512264364926080725284715058320037468560258406119118666475101064017957362872531020909563663753240129681129606122929658571213084198551487539547577409091082469337862305148623288189242930160225020927721422818302835971919402458528934
enc_2	=  6049049661741129561339303988250162617703359741970199356749378099535308799521119296163475813567458644038456685905251522625056377260310087845057811228022836098917570328692580410899852889868960996513905266043335963520913743708134923879544500911079066640658342641576456724637857109609913138972587873848795314132791317122747052648231297078735128282339170389129703582587817548539040826603188468662975329145727078616857156409325283263490433476018586450960082502578543327451065633585123695731081960986876439520499678158646526292218543279767834119677467758578802705169018711527506297869276113561542222807369071584959189923897216079505316482443445467837921144205079761354928950270172051270453170856002545491432278972735662895438668870901370521394906635478044848448535690635490093836659267778026686404695474454443310769209580317339039949689309577128
enc_3	=  9297802808564228678857927735224258610176831223455462482108153962953283311112501933779642540831558523911908205264682548531027493458025348252477502958948277516597689610204247227516319189048436710254675204218913508162139428248916620471317757210444645620644754294112426431692939788347835259617673728076204145049918767636122119264147566892091600628134179775710906591426338082246629946748851355701691716873854064848390273287305765646761438968986164159947841015011854342290060053810459830057357847548324695563067411557873081187572229935066117850179208775004384867270372650455853756560763012162682268812544173997311505136324203900399349629488710197844813293107115270398692552357803651576615589484454781227778727051440858478438251726051391317986762487421941570502251822920317312304622541764818356928105898291743494415190324388360012261032469805293
enc_4	=  713095983409993528016630065648951013409887429450761159296479210782308084847050785300379490902448647458053364322993274237841476340954537003347555548992827654062094884577630320399338426853024680425709980978726290825928571411715417634212022523987025390940108095446209802316068849127107378425087055832984628808129531097287891984529260048649164000341136589805930287941174070455962380115617312855801447326371361475429811263285218112383055283949280091896985779211927696867430269968278138068400828124612158603851472016327854927370226178776190765638542240547246882872033038792494915187774790763271179846203704834184269540668646905004118327597860873987248913148268250014480899515845595580486997925049895214602419037682253683176691877538075243485739730794370764108792093424342949560517002862934953109055108423633725444594683266260073663364732952255
enc_5	=  10309778311674135836145162475142299890445328570998831868156889990227275287204954712195141311549279047953844775828171871944522109110470024787792366772581241453340259883183812924297131077506375091086889140550405275547002202216935333211274901846970064522877611909017778486075399188006657623263902100044828896866180655435221665929435914366779334701622735670714649165956831390471034827078404866534094264914677879030956272977839491780410171625330771079943455183946885337962048237633491024513227027839179415230496573264968451527246966618074421625677382526573096067979952606553854268016651712174361578916100364115941853700612277618158243626702349480460819792765645689509997114148748479096516230468934427015454217368508102362912163051749856763103972010705773880053579573724226945229453471505368052572019992934401394664840254259798167531746190494146
enc_6	=  8939535907261295438433886577386432968291926162277924912979941380189504000322310159787894619015550096747658897136943700072192920334615223423230154197591756541966832740944457435736068401948276698864982347929802551347213730712997519211436818145872722485367264219104124473346589051164722340414948298088909961344463800461486219156960782319672049123860381674970981713865865119998917955886468613202521879160392276542945726096267432761588212550950818569769983241315782390152313705093940640027041352082844550311829177150159737347964813330180325283882516072009654288888676591648012847062527444169352000893928289409020106115561912814987882374652419114381836807085680725260815445689968522849732254659773192714360607196619281714422460754645088867512471482029657153787836396684484646302575186890717770078233479877360251173401000006298555695416782863190

At first I thought this was RSA with more than two prime factors in the modulus, but I was wrong.
Notice how small the 6 ciphertexts are compared to the modulus! This is a big hint as to what to do next. Normally, ciphertexts have about the same bitlength as the modulus but in this case they don't. This means that either

the exponent is small (say 3) and the message $m$ is really short. But then there's a major problem: the cleartext wouldn't be encrypted at all because $m^3$ would be less than $N$ so $m^3$ is equal to $m^3 \bmod N$ (no encryption == BAD)
the exponent is a decent size (normally 65537) but the modulus isn't $N$ . Then what is it? Hint: the cipher bitlength is approximately half that of modulus.

Since there are 4 prime numbers we can make the following moduli: $ab$ $ac$ $ad$ $bc$ $bd$ $cd$ . Six moduli, six cipher texts!

f1 = 108082147276398906822234149167480016132157014049560913761488880190018027488520386318253742675423286348552334110023434741671427911613197684395221211646299519273129194692306445874938199068586137486874290442314459278649345469626426790676801658394799404284116771456479272808343825651929906737811050557836671896732124546721747709022607151231423494815945385193624295868730390462068156825588342737037490320356361648437686599733
f2 = 108082147276398906822234149167480016132157014049560913761488880190018027488520386318253742675423286348552334110023434741671427911613197684395221211646299519273129194692306445874938199068586137486874290442314459278649345469626426790676801658394799404284116771456479272808343825651929906737811050557836671896732124546721747709022607151231423494815945385193624295868730390462068156825588342737037490320356361648437686598461
f3 = 108082147276398906822234149167480016132157014049560913761488880190018027488520386318253742675423286348552334110023434741671427911613197684395221211646299519273129194692306445874938199068586137486874290442314459278649345469626426790676801658394799404284116771456479272808343825651929906737811050557836671896732124546721747709022607151231423494815945385193624295868730390462068156825588342737037490320356361648437686597791
f4 = 108082147276398906822234149167480016132157014049560913761488880190018027488520386318253742675423286348552334110023434741671427911613197684395221211646299519273129194692306445874938199068586137486874290442314459278649345469626426790676801658394799404284116771456479272808343825651929906737811050557836671896732124546721747709022607151231423494815945385193624295868730390462068156825588342737037490320356361648437686600843
 
import gmpy2
e = 65537
 
 
N = f3 * f4
phi =  (f3-1)*(f4-1)
d = gmpy2.invert(e, phi)
print `hex(pow(enc_1, d, N))`[3:-1].decode('hex')
 
N = f2 * f4
phi =  (f2-1)*(f4-1)
d = gmpy2.invert(e, phi)
print `hex(pow(enc_2, d, N))`[3:-1].decode('hex')
 
N = f1 * f4
phi =  (f1-1)*(f4-1)
d = gmpy2.invert(e, phi)
print `hex(pow(enc_3, d, N))`[3:-1].decode('hex')
N = f1 * f3
phi =  (f1-1)*(f3-1)
d = gmpy2.invert(e, phi)
print `hex(pow(enc_4, d, N))`[3:-1].decode('hex')
 
N = f1 * f2
phi =  (f1-1)*(f2-1)
d = gmpy2.invert(e, phi)
print `hex(pow(enc_5, d, N))`[3:-1].decode('hex')
 
N = f2 * f3
phi =  (f2-1)*(f3-1)
d = gmpy2.invert(e, phi)
print `hex(pow(enc_6, d, N))`[3:-1].decode('hex')

$ python  /tmp/f.py
the first part of flag is: ASIS_13f
the second part of flag is: 1c2154
the third part of flag is: d59e27
the forth part of flag is: b5405b
the fifth part of flag is: c8591
the last part of flag is: 49b970

Asis CTF 2013: "RSAng"

CTF Knowledge base

Res

Weekly sec digests

----------------

writeups/asis_rsang.txt · Last modified: 2014/04/23 07:25 by vladum

Show pagesource

[unknown link type]Back to top