Chapter 11 An Introduction to Cryptography
We are now ready for some applications. This chapter introduces cryptography, as well as the prototype for a cool mathematical encryption system and other similar topics. In Chapter 12, we will also discuss practical issues in implementing these – namely, finding huge primes and factoring huge composite numbers.
By ‘huge’ I mean something substantially bigger than the output of the following commands.
Those are peanuts by today's standards. But with the tools we've developed up to this point, we are ready for them.
Summary: An Introduction to Cryptography
A major application of number theory is ensuring privacy of many different types of communication. This chapter introduces the mathematics of cryptography at the level we have reached thus far.
We begin with a brief, non-rigorous introduction to Encoding and decoding, as distinct from encryption.
We then dive into a few mathematically elementary Encryption techniques which using congruence, keeping the mathematics as the main focus.
A first method which helps motivate the mathematics of public-key methods is Diffie-Hellman Encryption.
This is immediately used to show a real application: Diffie-Hellman key exchange.
The next long section gives a lot of detail about the most famous public key method, the RSA encryption algorithm.
In Section 11.6 we then examine some of the mathematical weaknesses of RSA, including the notions of Germain and safe primes.
There are many other interesting topics in the practice of cryptography, but we only cover Secret Sharing for now.
In the Exercises it is worth doing the ones where you create a small encryption and trying to have someone else break it.