Public Key Encryption

We indicate here how elementary number theoretic facts can be used to create an extremely secure scheme to encrypt messages.

First, we remark that a block of text can be represented as a string of numeric digits in an elementary way. For example, one can assign a 2 digit number to each letter and punctuation symbol (including invisible ones such as < space >.) One might make the assignment:

< space >=00, a=01, b=02, c=03, d=04,... etc. (Here we don’t distinguish between upper and lower case alphabet, but this could easily be done.) Then, any string of letters and punctuation can be represented as a numeric string; e.g., the string “abc d” becomes “0102030004”.

Next, select two large primes, p and q, (each at least 200 digits long), and set n = pq. The number n is made public, but the factorization of n is not publicly revealed. Each person who is to receive messages is assigned a natural number k with (k, ϕ(n)) = 1 which is also public and a natural number k′ which only he knows for which kk′ ≡ 1 (mod ϕ(n)). A public directory exists listing the pair (k, n) for each person in the message network. (k′ is easy to find if ϕ(n) is known, but not otherwise; ϕ(n) is not publicly known, and is extremely difficult to compute, because the factorization of n is not publicly known.)

Now, suppose someone wishes to send an encrypted message to someone in the network. Suppose the message can be represented as a numeric string, S, which is relatively prime to n. (This will be the case if S is not too long, say less than 200 digits. Longer messages can be broken into blocks of an agreed length and each block processed separately.) The sender looks up the pair (k, n) for the recipient and computes A = S^{k} (mod n). (This is moderately easy to do, as we have discussed in class- at least on a high speed computing device. Repeated squaring or some similar device is employed.) The sender then sends A to the recipient, who then unencrypts the message by computing A^{k′} (mod n). Note that since kk′ ≡ 1 (mod ϕ(n)), or kk′ = 1 + jϕ(n), we have

A^{k′} ≡ S^{kk′} ≡ S^{1+jϕ(n)} ≡ S (mod n)

by Euler’s theorem. Thus the message is easily unencrypted if the recipient has access to the number k′.

Now if someone knew ϕ(n) they could easily find k′ given the (publicly known) values k, n. However, knowing ϕ(n) is essentially the same as knowing the factorization n = pq since ϕ(n) = (p−1)(q−1) = n−(p+q)+1. The fact is that no one knows any especially good algorithm for factoring numbers which is essentially better than just guessing factors. What is meant by ”essentially better”? Trying factors is clearly intractable for large numbers. A number with 400 digits is of the order of 10^{400} and trying factors up to its square root would involve a number of steps of the order of 10^{200}. The number of seconds in a year is < 10^{9}, so even on a computing device which can complete a trillion operations per second trying factors could take of the order of 10^{180} years. (This seems to put a bit of a damper on any such attempt...) The problem is that the number of steps is exponential in the size (400) that it takes to describe the number in usual (decimal) notation. All known algorithms for factoring seem to require an exponential number of steps in the size of the number to be factored (not for all numbers, of course, but for some.) One says such algorithms require ”exponential time”. (By ”size” of a problem, we will always mean the number of symbols requires to state the problem, using “reasonable” notation e.g., decimal notation for numbers.) Problems requiring exponential time to solve are termed “intractable”. In contrast problems requiring time polynomial in the size of the problem are considered “tractable”. We will discuss these notions a bit more later.