RSA Key Generation using Javascript
Part 1 of “Learning Blockchain from the Ground Up”
I have set out to gain a deep understanding of many secure data storage methods.
I find that I gain this deep understanding with software when I implement it. So I will be implementing many things. The list is yet to be defined, but the first on the docket is Blockchain.
I think I already have a basic understanding of Blockchain and how it works. But, I definitely couldn’t explain it to my Mum, so I need to know it better.
To do this I did what anyone does this days, I googled “blockchain” and clicked on the wikipedia result. From here, the first term used that I didn’t feel like I have complete understanding of was “cryptography”. So I clicked through to it’s wikipedia page.
I saw cryptography included things I had seen before: shared-key and public-key encryption. But, I didn’t feel like I had a deep unedrstanding of public-key encryption. As I was reading this section of the article, I saw something familiar: RSA. But how did it work?
From here, I decided I would implement my own RSA encryption system. This article is dedicated to the key generation part only. I will continue my journey in follow-up articles.
1. Choose two distinct prime numbers p and q
This is not a crypto-safe way of generating random primes, it’s a proof of concept.
2. Compute n = pq
3. Compute λ(n)
λ(n) = lcm(λ(p), λ(q)) = lcm(p − 1, q − 1), where λ is Carmichael’s totient function
Understanding of Carmichael’s totient function is not actually required here. This is thanks to primes always resulting in themselves minus one. I struggled to understand this function. I would appreciate anyone who would be able to explain to me in lamen’s terms.
4. Choose an integer e
Such that 1 < e < λ(n) and gcd(e, λ(n)) = 1; i.e., e and λ(n) are coprime
5. Determine d as d ≡ e−1 (mod λ(n))
d is the modular multiplicative inverse of e (modulo λ(n)).
This is more clearly stated as: solve for d given d⋅e ≡ 1 (mod λ(n)).
Resorted to copying code for this step. I was unable to understand how I could calculate the modular multiplicative inverse.
6. Keys complete
The public key consists of the modulus n and the public (or encryption) exponent e. The private key consists of the private (or decryption) exponent d, which must be kept secret. p, q, and λ(n) must also be kept secret because they can be used to calculate d.
I hope this article helps others gain the same understanding I’m looking to achieve.
From here, I will implement the encryption and decryption with these keys. In doing so, I am also planning to implement padding, likely with OAEP.
Don’t forget to applaud if you found this article helpful!
Please comment with any questions or feedback you have.
