# I think I'm trying to find the C in an RSA cipher to find the key for an aes_128_ecb cipher, can anyone tell me if I'm on the right track?

And if I am on the right track, how do I reach the solution from here?

I'm doing a CS game and I've hit a wall (I'm a rank beginner when it comes to encryption) on the encryption portion. I've been given the encrypted output and what I think (from my research) is an encoded version of the key using this:

For me, C is what I'm looking for, d = 7, N = 98286183916580532129117891164396375520832348985166654489180704043300879122347 and P = 89511674269883781051088511817946305647658886680759682801944853433540569894936.

p and q for N are 294156383975755063828794349953398256143 and 334129018681034197306379539716603659429

C was created randomly and is known to be 16 bytes. P is known because it was the first 32 bytes of the encrypted file (that I ripped out using a hex editor and turned into base 10) and d and N were both hardcoded.

I tried reversing it manually (using modular arithmetic, since a = b mod n then b = a mod n so C = root7(PmodN) ) but I got a 37 byte number that I know must be incorrect. Can someone please tell me where I'm going wrong?

I can post the source if it's necessary.

I think you should review how RSA encryption and decryption work.

You are given all the elements you need:

$P = C^d \mod N$

You know $d$, you know $p$, $q$, and thus $pq = N$. Usually people use $e$ to the encryption exponent and $d$ for the decryption exponent, but from what you said, $d$ is being used to encrypt.

You can recover $C$ with $P^u \mod N$, where $u$ solves:

$ud = 1 \mod (p-1)(q-1)$

Can you figure it out from there? (Hint: The Extended Euclidean algorithm will help.)

• You keep editing the post so I'm a little bit confused. Just what is that second equation supposed to be? – Engie May 17 '17 at 23:36
• You want to find the modular inverse of d, modulo (p-1)(q-1). The Extended Euclidean algorithm will do this. – user47922 May 17 '17 at 23:38
• Looking over it – Engie May 17 '17 at 23:43
• Your implementation may be wrong--you can test it by multiplying it by 7, taking the answer mod N and seeing if you get 1. If not, then the implementation is wrong. Rosetta Code may have something you can use too. – user47922 May 18 '17 at 0:11
• As much as I hate to say it you were 100% correct. I searched around for an already written algorithm and used that and it gave me exactly what I was looking for. Thanks very much I feel like I've learned a lot today. – Engie May 18 '17 at 0:50