That brings us to now. Moving forward, I'd like to shift my focus toward explaining topics I am interested in as well as continuing to express my concerns and opinions. I am, however, going to try to move more toward opinion articles that require some explanation as to the principles at work.
On to the Maths!
Note: If, at this point, you haven't read my article on public-key cryptography, I would highly suggest that you read it before continuing. You can find it here.
In this article, I will be explaining the mathematics of RSA. RSA is but one example of public-key cryptography and there are many out there, but today we'll only be looking at RSA.
In the RSA cryptosystem, we'll be dealing with modulo-arithmetic quite a lot, so let's get the basics out of the way:
Let $a$, $b$, and $n$ be natural numbers. Then, $a$ is said to be congruent to $b \mod n$ if the remainder after dividing $a$ by $n$ is equal to $b$. This is written as:
$$a \equiv b\ mod\ n$$
You can think of this as a clock with $n$ hours on it's face. To say that $a$ and $b$ are congruent modulo $n$ is equivalent to saying that if you start at the topmost point of the clock and move clockwise $a$ hours, you will land on the same spot as if you had moved $b$ hours.
First, we'll need to generate two prime numbers, $p$ and $q$. We'll multiply those together to get $n$. Next, we calculate the Euler totient of n (written $\phi(n)$). This is as simple as calculating $ (p-1)(q-1) $. We then choose an exponent $e$ such that $e$ and $\phi(n)$ are co-prime. The tuple $(e, n)$ is our public key.
Now, to derive our private key, we need to calculate the multiplicative inverse of $e \mod n$. That is, we need to find some $d$ for which $e \cdot d \equiv 1 \mod \phi(n)$. I won't go into it, but you can accomplish this using the extended euclidean algorithm.
The tuple $(d, n)$ is now our private key.
Now that we have a public and private key, how do we actually encrypt and decrypt messages?
To encrypt a message $M$, we use this simple formula:
$$C=M^e \mod n$$
Where $C$ is the ciphertext and $M$ the message. We can encode our message as a number very easily by just interpreting it's binary representation as a number. There is a bit more complexity to it than that, but for now let's just assume this can be done.
To decrypt some ciphertext $C$, we have an analogous formula utilizing our private key:
$$M = C^d \mod n$$
Now, you might say that, since we could calculate the private key from the public key, this is not a very secure system, but to calculate the private key we had to know the factors of $n$ since we are actually calculating $(p-1)(q-1)$ where $n=p \cdot q$ and $p$ and $q$ are primes. And since we are discarding the totient after deriving the keys, we would need to factor $n$ to recalculate the totient. For small numbers, this doesn't seem like too difficult a task, but for a large enough $n$, it could take longer than the expected lifetime of the universe to calculate. (At least for the moment!) This is simply because we don't really have any better way of factoring a number than simply guessing a factor and checking if it works.
In the public-key cryptography article, I explained how it could be useful to reverse the roles of the keys in this system, and you can see from the two formulas I've given here that you could just as easily encrypt a message using $(d, n)$ as you could using $(e, n)$.
That wraps up this brief explainer of the mathematics of RSA cryptography. In a future article, I hope to dive deeper into the world of public-key cryptography and explain some concepts like digital signatures and certificates, more thoroughly. I'd also like to expand a bit on exactly how RSA and other public-key cryptography is used in practice.
I hope you all enjoyed the article and I hope to write another one soon.
Comments
Post a Comment