### October 27, 2021

# Introduction to Key Encryption

The next few pages discuss some principles of key encryption. I should add that none of this is required learning for M150. However, judging from some of the queries that I received from students, public key encryption, as discussed in M150, still left some rather confused. How does it work?

To gain a full understanding one has to have a good working knowledge of number theory, which is a course in itself. The OU did offer such a course, M381 Number Theory and Mathematical Logic, and maybe it still does. I am certainly not going to delve too deeply, but to gain even a slight foothold one cannot avoid looking at numbers. I will try to provide a simplified explanation of how the Diffie-Hellman key exchange works and with time I may even tackle the RSA algorithm used for public key encryption.

Unerpinning the implementation of the key exchange protocol and asymmetric public key encryption are prime numbers. Both the Diffie-Hellman key exchange protocol and RSA public key encryption employ very large primes.

A number is prime if it is an integer greater than 1 and its only positive
divisors are 1 and itself. In other words a prime number n has just two positive
factors, 1 and n. The first seven primes are 2, 3,
7, 11, 13, 17 and 19. Currently,
i.e. in 2004, the largest known
prime is 2^{24036583}-1, an integer longer then seven and a quarter
million digits. Diffie-Hellman uses primes of the order of 300 digits and
the initial RSA algorithm employed a multiple of two primes, which were each
150 digits in length.

Any other integer greater than 1 with more than two factors is called composite, e.g. 4, which can be divided by the positive integers 1, 2 and 4. The number 1 is regarded as a special case and is no longer considered to be prime.

But what, you may ask, did Diffie-Hellman and RSA actually solve?

Next page » Key Distribution

⇑ Up to top of page