Yes, RSA itself is as simple, you probably just need to know what a prime is, what is greatest common divisor (gcd) and what coprime means (gcd(a, b) = 1) and how Chinese Remainder Theorem (that Chinese nephew of Bézout's Identity) works, and know a little bit of Euler's totient theorem (also known as Euler's Phi function) which can be optimized to Carmichael function (no need to know the proof just yet), then you should be able to understand RSA real good.<p>The reason RSA works because to crack RSA you need to solve the integer factorization problem which is sufficiently hard until lately (as it is a NP-intermediate problem, which is somewhere between NP-Complete and P-complete, and we don't know whether P=NP yet...), but the key generation is pretty easy (as it can be done in polytime), and so this represents a trapdoor function [1].<p>Really it is just year 3 uni stuff that everyone has to exam with. I still remember having to do RSA manually on an exam paper and it sucked to be honest.<p>Mind you: RSA primes may not be unique if you have faulty implementation, because you can do semiprime by squaring a prime. Then you can get another pairs that are effectively the same that can spoof yours, although in reality this shouldn't happen.<p>Alas, the problem is, RSA is not really invincible, as processing power doubled every few years thanks to Moore's law, the problem of integer factorization is not that hard lately, so much so the RSA challenge was declared dead [2].<p>So, what did people do? They just turned to using bigger and bigger primes to mitigate this, but another problem is, finding primes that are big enough are also getting harder and harder, it takes more space as the bit size expands from RSA-1536 to RSA-8192.<p>Maybe it is fine for a Ryzen PC to do it with fine-tuned AVX2 vectorization to get instant prime generations (I think OpenSSL did that), for MCUs, smartphones and most importantly, smartcards (yes, RSA Security formed just to sell smartcards), that's a no-go.<p>Do you want to see your RSA key goes into the range of Kilobytes and even Megabytes? Clearly not. And the gist is that this can't go on forever and ever, not only that, it has been proven that by using a quantum computer, the problem of integer factorization was reducible to polytime [3], that also means you can crack RSA in polytime! All in theory of course, as quantum computers they are still in its infancy and it can crack no more than 128-bit for now, but the math tells the fact, many people bet it would catch up lately, and in order to get future proofed, RSA is considered a no-can-do now.<p>And instead, people started moving on to Elliptic Curve Cryptography (ECC) which I clearly lacked the fundamental knowledge to know, but you may need to know Group Theory, know what is finite field arithmetic, and what the heck is an Edwards curve. To this day, even Group Theory looked like a mindfuck to me. But I heard that's what Math major students have to suffer along, packaged together with Abstract Algebra.<p>As I'm just a computer science John Doe who can barely navigate through the abstract algebra textbook, I can tell the pain.<p>N.B. Shor's algorithm also spawned a whole slew of Post-Quantum Cryptography such as McEliece cryptosystem, and we are slowly turning into mindfuck category for crypto now. Wish it can be easier and simpler to understand and implement.<p>[1]: <a href="https://en.wikipedia.org/wiki/Trapdoor_function" rel="nofollow">https://en.wikipedia.org/wiki/Trapdoor_function</a><p>[2]: <a href="https://en.wikipedia.org/wiki/RSA_Factoring_Challenge" rel="nofollow">https://en.wikipedia.org/wiki/RSA_Factoring_Challenge</a><p>[3]: <a href="https://en.wikipedia.org/wiki/Shor%27s_algorithm" rel="nofollow">https://en.wikipedia.org/wiki/Shor%27s_algorithm</a>