RSA

Now that you know cyclic groups you can learn RSA for free.

Basic School Version:

• Pick two primes p and q (THESE ARE PRIVATE)
• Compute N = p*q (PUBLIC)
• Pick e (PUBLIC if you didn't pick 65537 that's probably the target)
• Computer d = inverse(e, (p-1)*(q-1)) (THIS IS PRIVATE)

Publish: N,e

Protect: p,q,d,(p-1)*(q-1)

ENC(m, N, e) = pow(m, e, N) that is:

$$ c = m^{e} \mod{N} $$

DEC(c, N, d) = pow(c, d, N) that is:

$$ m = c^{d} \mod{N} $$

Number Theory Quick Win:

So why did this work? Well we know:

$$ a^{\phi(N)} \mod{N} \equiv 1 $$

Since the size of the group of numbers mod N under multiplication is the count of all numbers with \( \text{GCD}(N,x) = 1 \)

We also know that \( \phi(N) = (p-1)(q-1) \) if \( N = pq\) both prime.

Now that means, by cycles, that computing:

$$ a^{x} \equiv a^{(x \mod{\phi(N)})} \mod(N) $$

Since everything cycles after \( \phi \) times.

Since \( d \cdot e \equiv 1 \mod{\phi} \) that means \( e \cdot d = 1 + \phi \cdot k \)

$$ c^{d} \equiv m^{e \cdot d} \equiv m^{1 + \phi \cdot k} \equiv m^{1} = m $$

Digital Signatures

You have a document, you produce a random looking signature using your private key. Anyone can verify the signature but no one can forge a signature.

So a digital signature needs to be verifiable by ANYONE with knowledge of a document, and a public key. Also should be unforgeable.

OK imagine you have published a public key N,e

Only you know p,q,d

Here's a simple (not ready for the world) signature scheme:

$$ \text{sig} = x^{d} \mod {N} $$

Now everyone publically knows \( \text{sig}, x, N, e \)

They can validate the signature by just checking that pow(sig, e, N) == x e.g.:

$$ \text{sig}^{e} \equiv x \mod {N} $$

This is the main concept behind bitcoin by the way, a wallet is a public key, transfering bitcoin is just plaintext signed with the private key matching your wallet.

CTF RSA:

Here's a whole RSA workshop in a box.