HackIM Nullcon CTF 2013 write-up

Hint: flag is not a frag: once you've got it, you can get one more...

Crypto 500

We're given the following:
Цитата:
n = 52663327194823108047941861363554667296911056447871 88785127198792390818389767437741043884042697813417 40858276714053716810874389770623503703996736687974 70776186113807376857893834326388369431932515506157 59902933749676883316817097953054649047764645797986 77703632934375663507898357576891627341435121532539 03202593

e = 10662335266334707061416010175090707752184800780484 87199510272395686606199019585683070878871806968902 65830636660853997681894517472390188901902543758517 09269

cipher-text = 10462822375277205946365199641597262713749993739943 57909091506537398272791306618098458481620423392938 70744463265888874276961969971096108086452105647668 82647584743088857818448828460464362997716024535291 28094029803725929915632320170106381959701908835246 76285475884921692502194212799981792187650488093680 64725175
It's obvious that the cipher-text is obtained by RSA algorithm with the modulo n and exponent e.
There're several attacks on RSA which allow to break the cipher given such information.
After some fuzzing around one can realize that an actual weakness of this modulo is that its factors p and q are too close.

Thus, we can use Fermat's factorization method and get the plain-text.

Since python's float->int casting is inaccurate, I used SAGE.
An actual s=(p-q)/2 value was obtained from the very first iteration:
Код:
sage: r=ceil(sqrt(n))
sage: t=r+0 #first iteration
sage: s=sqrt(t**2-n)
sage: s #should be integer
1754844
sage: p=t-s
sage: q=t+s
sage: phi=(p-1)*(q-1)
sage: d=pow(e,-1,phi)
sage: pow(c,d,n)
22424170465
The flag is 22424170465

Crypto 400
We're given the following:
Цитата:
The creator worked for Postal Telegraph Co.

CipherText:
e>qjj0h4qif?:i>)6:nz@nx:kor#).fuo4omj^1:>}lldivx?=p^r9f6x,?0mx:kor*{sqmz8p$:sri>?fqy y$t%s!d#foljo7,xml d>:i]nizhq)2!i>:ojyo?hq:,zx8?.]*vzioqsp8}fgluo4>jq? r<=6ky1?rx}e w9afjy+vim*l!wbdu]:!4?jkjnrx%w9yr@il%wpy$f.e:^xxn{wz8$>wlozy h?dkx=fp^y+@,pffok3>lxyr@ gcsvi1{,k(o4njj{orn+6fj 8xm?{:r2:ojuzwjt%ro bf.enzxmt(2^r3%imho4$t%svinc@] d4h$;pzwc6o]0zrgmc:or,f6i^iwxp-?ii}f81 :4j>:e+i}f8~a#
And there's a hint:

Цитата:
<!-- Hint: The unbreakable cipher is derived from ??? -->
It's obvious that the unbreakable cipher is one-time pad. So, our task is to decrypt the Vernam cipher.
First, I thought of XOR. Using hellman's XORTool, I obtained that the length of XOR key is 13 bytes.

Then I tried to brute force key, using python itertools.permutations on the list of words like 'nullcon', 'hackim', '2013', etc.
But it kept returning some binary rubbish.

After some hours of painful struggling I decided to google "Vernam cipher decrypt online" and got the following tool:
http://www.calcresult.com/misc/cyphers/vernam.html
It doesn't use XOR, so, it's just another Vernam cipher. The decryption key (really 13 bytes long) has been guessed: hackimnullcon.

Decrypt, get the flag:
i speak in the name of the entire german people when i assure the world that we all share the honest wish to eliminate the enmity that brings far more costs than any possible benefits... it would be a wonderful thing for all of humanity if both peoples would renounce force against each other forever. the german people are ready to make such a pledge - adolf hitler 14th october 1933.