Wikipedia:Reference desk/Archives/Mathematics/2020 March 27

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 27

RSA encryption

I have been working on understanding RSA encryption recently, and I think I have got it. I now want to try to explain the concepts to some not particularly mathsy folk. The starting point I am using is Clock-arithmetic encryption where (say) the public key is (12,3) and the private kay is (12,9) so message 4 encrypts to 4+3 = 7 and 7 decrypts to 7+9 = 16 clock 12 = 4 the original. However despite this being "valid", it is TOO simple and folk won't decrypt by adding 9, they will decrypt by subtracting 3. So is there any other simple function out there that can work like that without going to the complexities of RSA itself? -- SGBailey (talk) 09:52, 27 March 2020 (UTC)

The scheme you are rejecting, for good reasons, is known as a Caesar cipher, the oldest and simplest of the class of substitution ciphers, and the first any amateur cryptologist will try when attempting to decode a ciphertext. Not only is it simple, it is also blindingly obvious to anyone who knows the public encryption method how to compute its inverse, the supposedly secret decryption method. This applies not only to the Caesar ciphers, but to all substitution ciphers. The whole point of public key cryptography is in the difficulty of inverting the public encryption method. Coming up with a method that is not trivially invertible is not a simple matter. The basic RSA encryption–decryption algorithms are actually very simple. Can we assume that your not very mathsy folk might understand "raising to a power" (repeated multiplication) in clock arithmetic, as well as generalize the latter from the modulus 12 to the modulus 22? Then the public key can be 3 and the private (secret) key 7. For example, encrypting the message 13 gives 13³ modulo 22 = 2197 modulo 22 = 19. To decrypt the message, compute 19⁷ modulo 22 = 893871739 modulo 22 = 13. (In practice one would use a fast exponentiation method.) The only suspension of disbelief required is that it is hard to find the secret key given the public one. In this toy version of RSA it is very easy, but only because the key length is ridiculously small: less than 4.5 bits, so it is almost effortless to bruteforce this. If the key is long enough, bruteforcing becomes infeasible.  --Lambiam 16:28, 27 March 2020 (UTC)

I think the first thing is to explain the difference between symmetric and asymmetric encryption, which can be done without any math. (Based on the axiom that if something can be explained to the general public, then it will have already been done on YouTube with cartoons, I found "Asymmetric encryption - Simply explained" which does so by comparing it to a mailbox.) Regardless of how simple it is, the Caesar cipher is an example of symmetric encryption while RSA is asymmetric, and so yes, it does kind of miss the point. The main feature of RSA is not that it's difficult to crack, that's a given for any encryption method, but that it remains difficult to crack even if you know the encryption key. I think there is a reason that, despite encryption being in use for millennia, the RSA scheme didn't appear until the 1970's. (Fun fact, the R(ivest), S(hamir) and A(dleman) of RSA are all still living.) Partly it's computers, but the main takeaway for me is that it depends on the existence of mathematical operations that are easy to perform but difficult to undo; for RSA it's the fact that multiplication of large integers is relatively easy while undoing that operation (i.e. factoring) is difficult. Such operations are not very common, and even if you have found one it take quite a bit of cleverness to turn it into an encyption method. --RDBury (talk) 09:34, 28 March 2020 (UTC)

Thanks L & RDB. I think the clock powers will do nicely. -- SGBailey (talk) 10:07, 28 March 2020 (UTC)

I don't see how to explain RSA without actually explaining RSA. But the old puzzle with lockboxes and keys that inspired the Shamir three-pass protocol is a good way to explain what RSA tries to do. See the "double lock" scheme at b:Cryptography/Public_Key_Overview for explanation. 2601:648:8202:96B0:E0CB:579B:1F5:84ED (talk)` —Preceding undated comment added 01:40, 29 March 2020 (UTC)

• If you just want to demonstrate that using a math function that is hard to inverse can be useful for cryptography, I would think the Diffie–Hellman key exchange is (slightly) simpler to explain than RSA. It also avoids having to discussing public/private key pairs etc. Of course, if you want to explain RSA, explain RSA! Tigraan^{Click here to contact me} 15:57, 2 April 2020 (UTC)