NOTE: This isn't a formal proof, it's an intro to the witchcraft that is public-private encryption.

Pre-Reqs: A knowledge of modern algebra (aka abstract algebra) is extremely helpful in public key encryption. Knowledge of how RSA works is assumed. If you haven't been exposed to this yet, read the wiki on RSA.

There are two challenges here, first figure out the public key, then execute the RSA Blinding attack.

Part 1, getting n and e

How do you get n and e if you only have plaintext and signatures?

Step 1, get e. For this you have to guess. It is a common e (a hint given), and it is 65535.

Step 2, get n... This is not as trivial and requires an oracle (something that does encryption behind closed doors and gives us the results). You need a few signed messages to get the public key.

I will go over the steps / quasi proof for calculating N by using a small example.

Suppose the following: $$q = 11$$ $$p = 3$$ $$n = qp = 33$$ $$\phi(n) = (q-1)(p-1) = 20$$ $$e = 7$$ $$d = 3$$

Now lets do some encrypting (remember, signing is encrypting something with your private key, so anyone with your public key can decrypt it)

$$m = plaintext$$ $$c = signature$$ $$d = private key$$ $$e = public key$$ $$n = modulus$$ $$\iff = if and only if$$

We know the basic formula to sign a message: $$c = m^d \mod n$$

Now lets take it back to the original (how someone would verify the signature): $$c^e \mod n = (m^d \mod n)^e \mod n = m^{de} \mod n = m$$

Now lets do that again, but take away the last modulus: $$c^e = (m^d \mod n)^e = ? \neq n$$

What does this equal? Since the equation with the modulus was equal to m, when we take away the modulus we are left with the m plus some factor of n: $$c^e = m + kn$$

If we subtract m we are left with: $$c^e - m = kn + m - m = kn$$

How do we factor k out? We use gcd. This is where we need 2 messages: \(m_1\) and \(m_2\).

$$m_1^d \mod n = c_1$$ $$m_2^d \mod n = c_2$$

$$c_1^e-m_1 = k_1n$$ $$c_2^e-m_2 = k_2n$$

$$\gcd(c_1^e-m_1, c_2^e-m_2) = \gcd(k_1n, k_2n) = n$$

Lets give it a shot: $$m_1 = 2$$ $$m_2 = 3$$

$$c_1 = 2^3 \mod 33 = 8$$ $$c_2 = 3^3 \mod 33 = 27$$

$$\gcd(8^7-2, 27^7-3) = \gcd(2097150, 10460353200) = 1650 \neq n$$

Ugh oh... It didn't work... Why? Well lets break down the numbers. We know \(c^e - m = kn\) so: $$2097150 = 63550 \times 33$$ $$10460353200 = 316980400 \times 33$$

$$\gcd(63550, 316980400) = 50$$

$$1650 / 50 = 33 = n$$

So this leads us to a conclusion:

\(\gcd(c_1^e-m_1, c_2^e-m_2) = \gcd(k_1n, k_2n) = n \iff k_1\) and \(k_2\) are coprime

In the challenge we would have not been able to calculate k since we obviously didn't know n, so how do we determine if we got the right answer or not?

We play probabilities. we can keep chaining gcds together until out hearts content (or until we run out of space in mod n). I would just do 3 or 4. The chances of a common factor in 4 Ks is pretty small [source needed].

So lets add another m to the equation: $$m_3 = 4$$

$$c_3 = 4^3 \mod 33 = 31$$

$$\gcd(\gcd(8^7-2, 27^7-3), 31^7-4) = \gcd(1650, 27512614100) = 33$$

We got n! now what?

Part 2, preforming a blinding rsa attack

If you try to send the server the desired message, it kicks you. We need to craft a message such that we can get the signature on our desired message.

Lets do some more math! we have $$c = m^d \mod n$$

m is our message we want signed, but the server wont sign it.

Suppose we pick an arbitrary r that is coprime to n (and not 1) $$r = 2..n$$

With that r, we generate a new m called m' as such: $$m' = m r^e \mod n$$ since \(m'\neq m\), the server will sign it.

$$c' = m'^d \mod n$$

remember \(m' = m r^e \mod n\), so if we substitute and simplify: $$c' = (m r^e \mod n)^d \mod n$$ $$c' = (m r^e)^d \mod n$$ $$c' = (m^d r^{ed}) \mod n$$

Remember \(a^{ed} \mod n = a\) is a primitive fact of rsa.

$$c' = (m^d r) \mod n$$

So now we have to get rid of the r. Since we chose r to be coprime to n, it has an inverse! Now we just calculate \(r^{-1}\) using your favorite method (i.e. Euclidean algorithm)

and thus:

$$c = c' r^{-1} = (m^d r r^{-1}) \mod n = m^d \mod n$$

and we have our signature.