0

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?

Merc
  • 213
  • 1
    The math behind RSA is very simple. (Of course, since it's a widespread encryption method, there's a lot of research on possible ways of defeating it, and that material can get complicated.) Any standard first course in number theory will cover the details. – anomaly Dec 30 '17 at 03:02
  • @anomaly That would be sufficient to learn Textbook RSA. Actual RSA is a bit more complicated (but not by much). – Mark Schultz-Wu Dec 30 '17 at 03:09
  • You can get a rough idea of RSA from this note on intro number theory. RSA is discussed in Lecture 14 & 15, p. 45-47. – swoopin_swallow Dec 30 '17 at 04:06
  • A very accessible introduction can be found in Paar and Pelzl's Understanding Cryptography. If you are in a hurry, Cormen, Leiserson, Rivest, and Stein's Introduction to Algorithms has a good chapter on RSA, which also covers the necessary background. – Fabio Somenzi Dec 30 '17 at 05:09

2 Answers2

1

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,....

Gerry Myerson
  • 179,216
0

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.

Ross Millikan
  • 374,822