Maths behind RSA -- where do I turn?

Question

I am a reasonably seasoned software developer (20 years) and am at more or less have year 12 maths. Well, actually, I barely remember limits, derivatives, integrals, etc. I have a good "intuitive" understanding of math-related problems.

I want to know everything about RSA. I don't want to just "more or less" understand how it works. I want to get to the point where I have a very profound understanding of absolutely everything involved, the maths behind both intuitively and practically.

As far as I understand, I need to understand:

• Prime number theory (I am not sure which parts)
• Modular arithmetic
• Fermat's little theorem
• Euler's theorem

I found this PDF but I find it a too hard to follow (I am too many holes in my knowledge).

So... my question is: how shall I proceed forwards? Shall I get to different sources, one for each topic, and master each one? Or is there a "bible" that explains the full range of maths both in terms of formulas and with a "deeper" understanding?

Basically, where do I go?

Answer 1

The core of what you are looking for is number theory. I got obsessed with another topic, so my suggestion is to look at it as a journey. You won't get a map at the start, but find the topics of interest, get books/articles on them, and proceed from there. Work on the stuff you need to know, see where the gaps are, then try to fill those gaps. I would suggest you don't need anything on prime number theory-you just need to know there are lots of primes and that it is easy to test a number to determine whether it is prime, so I would reduce that to primality testing. Next you need to know about groups/rings/fields, which get grouped into abstract algebra. It doesn't take too much of that to understand the whole RSA scheme. I think the hardest part, and I know nothing here, is the special requirements on the primes and exponents you use to make it hard for the enemy to find the primes. I have a suspicion that some of the claimed requirements are lore that is not supported by facts. A good test of your understanding is whether you can argue this one way or the other. Enjoy the quest.

Answer 2

Nowadays, nearly every introductory Number Theory textbook has a chapter on RSA. Pick one and read it, going back as necessary to learn about things covered in earlier chapters.

That won't tell you everything there is to know about RSA, not by a longshot, but it will get you started. Crawl before you walk, walk before you run,....