Teaching RSA
Barry S. Fagin · 2019
Once you introduce RSA and probabilistic primality testing to your cryptography class, one of your brighter students will ask "What happens if the test is wrong?" It turns out the answer can vary from "You'll find out immediately" to "It makes no difference" to "It depends". We explain the mathematics that determine where the answer lies, and illustrate with examples suitable for use in the undergraduate classroom. We conclude by showing how to construct a key pair that produces correct RSA results from composite numbers p and q, and thus whose composite nature is not detectable through RSA encryption and decryption alone.