Comment by jasperry
2 days ago
There are a lot of people who learn and teach the RSA algorithm superficially without a sufficient grasp of the number theory to really understand what is going on. I know because I've been one of them (on both sides). The Carmichael vs. Euler totient issue confused me for a long time.
Needless to say, those people should not be implementing RSA for a system that needs actual security. I'm looking for a better way to teach "real" RSA without needing the students to be math majors or to spend a whole semester on it. Does anybody have any suggestions?
Given how much more favored ECDSA and ECDH is these days, i recommend teaching elliptic curves. They're actually quite simple to understand mathematically if you want a shallow comprehension.
The task for teaching is much harder now as these need to be combined into hybrid PQC protocols
Sure, but teaching the original as a fundamental building block would still be just that.
The undergrad lectures I took placed almost equal emphasis on crypto over Zp and crypto over EC. For most students without deep abstract algebra backgrounds, introduction to operations and principles are more friendly and tractable over Zp.
During my 2-year CS degree (in France ) we learned the whole modular algebra with groups, and stuff (don't know the terminology in English sorry) and finally, we learned about RSA using all of this stuff and it really was a wow moment for the whole class!
I don't know how it's taught elsewhere but I feel like I both have "a sufficient grasp of the number theory to really understand what is going on" but also I "should not be implementing RSA for a system that needs actual security" !
> I'm looking for a better way to teach "real" RSA without needing the students to be math majors or to spend a whole semester on it.
RSA is math so it seems like you're trying to shove a square peg into a round hole here.
Yeah, learning maths for 1-2 months and then applying it to RSA in python at the very end was how I learned it and I think it was a great way. Even though it was a CS diploma we learned it with the maths teacher and spent the right amount of time on it.
I wrote an article trying to give a simple overview for teaching. https://rubberduckmaths.com/eulers_theorem
I also added plenty of inline python code blocks students can change and run on the fly.
The reason i wrote this is the hand waving around group theory i saw in other explanations. Namely you shouldn't just say x^y always = x mod m for certain values of y (eg. x^13=x mod 35, even for factors of 35). You should give a detailed, intuitive understanding of why this occurs.
Anyone with an undergraduate CS background should be able to handle Dan Boneh's course:
https://www.coursera.org/learn/crypto
Although there are continuums of teaching delivery from muddled to clear explanations of concepts, there are no student shortcuts to escape the irreducible mental exertion to acquire familiarity towards mastery. Uncurious people shouldn't be in the field (no pun intended).
I use this as a teaching aid: https://github.com/jcalvinowens/toy-rsa
It's an ugly naive implementation, but it's much simpler and more accessible than any real one I've ever seen, and depends on nothing but libc.
Depending on what you're trying to teach, I would think something like these would be nicer to read (but with minimal dependencies): https://github.com/jackkolb/TinyRSA or https://github.com/i404788/tiny-rsa
The point for me is a naive BIGNUM library that somebody who has only had high school level math can easily understand.
> I'm looking for a better way to teach "real" RSA without needing the students to be math majors or to spend a whole semester on it. Does anybody have any suggestions?
Start and end with a reminder to use padding.
Actually if you want to make it not-so-mathy, talking about about how to be compatible with other programs could be nice. How do you import/export public key in pem or der? How do you (de)serialize ciphertext?