DEFKTHON CTF 2014 - Find the FLAG! - Crypto 400 Write-up

HI!

We were given a lot of description this time :D and here they are:

Alice and Bob went a long way in crypto. They designed a super secure crypto system to encrypt their messages. We managed to steal the source and some other information. Find the FLAG!  

File 

We also got this: Download 

Mirror
File 

We also got this: Download

In the first file we had an example of the algorithm and the cipher we needed to decrypt and from the second file which is an archive we get 3 files 2 keys and the encryption script but script was obfuscated and names in the script were not readable to human, so lets start with de-obfuscating it - we did it by hand- and here is the a bit more readable script:
http://www.codesend.com/view/addce89369568510c33ff3154bf6dd89/

Basically it was reading four keys, and processing an asymmetric encryption on its first argument according to those keys.
The argument string is converted into a base256 number by those lines:

a, bb = argv[1], 0
for ccc in a: bb = (bb*256) + ord(ccc)

So what the encryption doing by mathematically is something like this:

$$T \equiv C^{A} \pmod{B}\\
P \equiv C^{S} \pmod{B}\\
Q \equiv M \cdot T^{S} \pmod{B}$$

where A,B,C and D are values in the keyfiles respectively and S is the random seed generated from D.

We know the values of B and C from the zip archive and P and Q from the message text that is containing an example and the cipher we need to find a way to get the value of M with those guys. Let's examine the $T^{S}$ actually it is equal to $(C^{A})^{S}$ and which is $P^{A}$ we just swapped the exponents. and last line became:

$$Q \equiv M \cdot P^{A}\pmod{B}$$

And besides those things we actually got one more very important data, the EXAMPLE! The example's P value and the P value of the cipher we need to decrypt are equal, also we know that A is equal for both of them so we can get the value of $P^{A}$ from the example -as we know Q and M for it. and then just multiply both sides of our equations with the inverse of the $P^{A}$ modulo B and then get the decrypted cipher lets do it now!

There's our python code for geting the flag:
http://www.codesend.com/view/7d97576bb77a0cc1ca33a717b6c8ed4d/