We shall see how number theory plays a major role in encoding information, such as credit card numbers and banking transactions transmitted via the Internet.

INTRODUCTION AND HISTORY

In this chapter, we will examine several applications of number theory to cryptography, the science of encoding information. With the advent of electronic media such as the telephone and computer, it became necessary to encode military, diplomatic, corporate, and financial data. A simple credit card transaction, for example, transmitted from a store or bank to a financial institution must be encoded lest someone intercept the credit card number, expiration date, user name, and password. A more urgent example is afforded by the need to encrypt a message from the Pentagon to a Trident nuclear submarine containing instructions to relocate. The victory of the United States and Britain over Japan and Germany in World War II may be attributed in part to the breaking of the Japanese and German codes by American and British mathematicians and computer scientists such as Alan Turing. The United States used the Navajo language in their radio transmissions in the Pacific Theater—a language unknown to the Japanese.

Here is a bit of standard terminology. The message to be encrypted (the technical term for encoded) is called plaintext, while the encrypted text is called the ciphertext. The ciphertext must be decrypted (the technical term for decoded) in order to be recovered as plaintext.

One of the earliest techniques was used by Julius Caesar in the first century b.c. It was an example of a substitution code, a code in which each letter is replaced by another. The encryption was accomplished, in terms of our alphabet today, by replacing each letter in the first row of the chart in Table 9.1 by the letter beneath it. The recipient decrypted the message by replacing each letter in the second row of the chart by the letter above it.

Notice that the substituted letter can be found without the chart by moving forward three letters. Thus, to find the replacement for G, we start at G and advance three letters: from G to H, from H to I, and from I to J. To encode the last three letters, X, Y and Z, we must “wrap around” the alphabet, that is, the successor of Z is A. Hence, Y, for example, is replaced by B, since we advance from Y to Z, from Z to A, and from A to B. Of course, there is nothing special about the decision to advance three letters.

By assigning the (two-digit) integers 01, 02, 03, …, 24, 25, 26 to the alphabet, that is, A = 01, B = 02, …, Z = 26, we can use modular arithmetic to accomplish the above encryption and decryption as follows. Letting p represent the assigned integer of a plaintext letter and letting c represent the integer of the resulting ciphertext letter, we have

(9.1)

The modular equation automatically does the “wrap around.” Thus, for the plaintext letter X, we have p = 24, since X is the 24th letter of the alphabet. Then Equation 9.1 yields c = 27 (mod 26) = 1 = 01, and the ciphertext letter is A, in agreement with our chart. To decipher the ciphertext, we use the modular equation

(9.2)

Note that we can replace (9.1) by any linear congruence equation c = ap + b (mod 26), provided that gcd(a, 26) = 1. In place of (9.2), we must then use p = a′(c − b) (mod 26), where a′ is the multiplicative inverse of a (mod 26), that is, aa′ = 1 (mod 26).

One can make up one’s own code by assigning a two-digit integer to each letter, punctuation symbol, and digit. A space between words is usually represented by “00.” The example shown in Table 9.2 uses the two-digit numbers from 01 to 40.

Substitution codes are very easy to crack especially when they are used in lengthy messages. One reason is that letters occur with fairly consistent frequencies. The most frequent letter is E, for example, while Q and Z are rare. Substitution codes are, therefore, unsecure and no longer in use.

Recall that every integer can be written in binary form, that is, as a string of 1’s and 0’s representing the powers of 2 in the given integer’s distinct binary partition. The binary complement of a binary number substitutes 0’s for 1’s and 1’s for 0’s. Thus, the binary complement of 11000101 is 00111010.

Now, plaintext (as in the example IS 31 A PRIME?) can be converted into a binary number M. Suppose the sender and receiver have a lengthy binary string N known only to them. Then M can be encrypted into a binary number M′ as follows. If the ith digit (counted from the leftmost digit) of N is 1, let the ith digit of M′ be the complement of the ith digit of M. If the ith digit of N is 0, let the ith digit of M′ be the same as the ith digit of M. The receiver of the message uses the same scheme to decrypt M′ into M, after which the agreed-upon table (say, Table 9.2) is used to recover the plaintext. This scheme works since the complement of the complement yields the original number. Note that we are assuming that N is longer than M. If this is not the case, we must break M into several smaller binary numbers.

PUBLIC-KEY CRYPTOGRAPHY

A public-key cryptosystem is based on modular arithmetic. The idea is that people can send messages to other people by knowing each person’s public key and using it to encrypt the message. The receiver decrypts the message using the private key. This involves a publicly known pair of integers, n and k, for each user chosen as follows. Let n be a large semiprime, that is, let n = pq, where p and q are large primes chosen by the user. (We will soon say just how large these numbers must be.) The user then chooses a so-called encryption exponent, k, such that gcd(k, φ(n)) = 1. Recall from Chapter 7 that φ(n) = φ(pq) = φ(p)φ(q) = (p − 1)(q − 1). While n is public knowledge, p, q, and φ(n) are known only to the user.

Now let M be a plaintext formed using, say, Table 9.2, that is, M is a long string of two-digit numbers, such as 091900333100010016 1809130529, representing a secret message. The sender then encrypts M by looking up the user’s n and k and calculating N = M^k (mod n). The sender then transmits N to the user. The user figures out the so-called decryption exponent, j, from the modular equation jk = 1 (mod φ(n)), which can be solved since gcd(k, φ(n)) = 1. We will use this fact in the equivalent formulation jk = 1 + rφ(n). Note that only the user can calculate j since this requires φ(n) that can’t be found in “real time” without knowing the prime factors, p and q, of n. We are assuming that p and q are large enough to make the task of factoring n require years of running time on state-of-the-art supercomputers.

Knowing the decryption exponent, j, the user recovers M from N using the equation

in which we used Euler’s theorem, M^φ(n) = 1 (mod n). (See Chapter 7.) Of course, this requires gcd(M, n) = 1, which is virtually guaranteed to be the case unless either of the two prime factors of n (p and q) divide M. This cryptosystem was developed in 1977 by Rivest, Shamir, and Adleman (RSA). It is therefore known as the RSA system.

FACTORING LARGE NUMBERS

The RSA system rests on the difficulty of factoring large numbers. Fermat developed the following method of factoring large numbers.

If we wish to factor a large even number, n, we observe that 2 is a factor and therefore divide by 2 and consider . If is even, divide it by 2, note that 4 = 2² is a factor of n, and consider . After k divisions by 2, we will reach an odd number, m, and realize that n = 2^km. If m = 1, we are done. Otherwise, the problem of factoring n boils down to factoring the odd number m. So Fermat dealt exclusively with the problem of factoring a large odd number.

If m = a² − b², where a − b > 1, we have the nontrivial factorization m = (a + b)(a − b). On the other hand, if m can be nontrivially factored as rs, then . Expand this equation and see that the right-hand side indeed reduces to rs. It is easy to see that and are integers, since r and s are both odd. (If r or s were even, m would be even.) Then their sum and difference must be even and, therefore, divisible by 2.

So Fermat developed a way to express m as the difference of two squares. That is, he tried to find a and b such that the given odd number m = a² − b² or a² − m = b². To do this, he found the smallest N for which N² > m. Then he considered the sequence N² − m, (N + 1)² − m, (N + 2)² − m, …, until he found a square. This enabled him to write m = a² − b² = (a + b)(a − b).

Fermat’s sequence N² − m, (N + 1)² − m, (N + 2)² − m, …, must eventually yield a square, since . This ultimately yields the trivial factorization m = 1 × m.

Approximately 100 years after Fermat, Euler developed the following method of factoring odd numbers that can be written as the sum of two squares in two different ways. Let the odd number n satisfy

(9.3)

where a and c are odd and b and d are even. Without loss of generality, assume that a > c, in which case it follows that d > b. Then a² − c² = d² − b², implying that

(9.4)

Now, let k = gcd[(a − c), (d − b)], so

where gcd(r, s) = 1. When these are inserted into (9.4), we obtain r(a + c) = s(d + b). Since r and s are relatively prime, it follows that s | a + c. Then a + c = st. When this is substituted into r(a + c) = s(d + b), we get rst = s(d + b), yielding d + b = rt. So we have

Observe that t = gcd[(a + c), (d + b)]. Since a + c and d + b are even, it follows that t is even. By similar reasoning, k is even.

Euler then obtains the following factorization of n:

(9.5)

To verify this, note that the right side of (9.5) becomes

Much research has been devoted to the problem of factoring large numbers since the seventeenth century, and the current rapid rate of progress in the development of efficient factoring algorithms keeps the designers of cryptosystems on their toes.

THE KNAPSACK PROBLEM

Here is an interesting problem known as the knapsack problem that is used in cryptography. Given a set of distinct positive integers S = {n₁, n₂, …, n_k} and a number N, does N have a distinct partition consisting of members of S? If so, is the solution unique? Let’s look at a few examples.

The knapsack problem is presented as follows. Given the set of distinct positive integers S = {n₁, n₂, …, n_k} and the equation

(9.6)

is there a solution such that each a_i is either 1 or 0? To make this clear, observe that a solution N = n₁ + n₄ + n₇, for example, is equivalent to a₁ = a₄ = a₇ = 1, while all other a_i’s are zero in (9.6).

When S is very large, it is difficult to determine whether a given N has a solution. This is because of the observation that if S has k members, then there are 2^k subsets of members of S. Furthermore, it is difficult to determine how many solutions there are for a given N after one solution has been found. Fortunately, if S is a special kind of sequence, this is not the case, as we shall now see.

SUPERINCREASING SEQUENCES

A sequence S = {n₁, n₂, …, n_k} is called superincreasing if

or, equivalently, if each term strictly exceeds the sum of all of its predecessors. The following algorithm solves the knapsack problem when S is a superincreasing sequence. We will see that for any given N, either (i) there is a unique solution or (ii) there is no solution.

1. Given N, find the largest n_i in S such that n_i ≤ N. If no such n_i exists, the algorithm terminates and there is no solution. If n_i = N, the algorithm terminates and we have a unique solution. If n_i < N, proceed to the next step. Observe that n_i must be included in a solution since the sum of all the predecessors of n_i is strictly less than n_i and, hence, strictly less than N.
2. Find the greatest n_j, where j < i, such that n_j ≤ N − n_i. This implies that n_j + n_i ≤ N. If no such n_j exists, the algorithm terminates and there is no solution. If n_j + n_i = N, the algorithm terminates and we have a unique solution. If n_j + n_i < N, proceed to the next step. n_j must be included in a solution since the sum of all the predecessors of n_j is strictly less than n_j.
3. Continue in this manner until either a solution is found, in which case it is unique, or the algorithm can’t be continued, in which case there is no solution.

Here is a cryptosystem based on the knapsack problem. A user selects a superincreasing sequence n₁, n₂, …, n_r and a modulus m such that m exceeds the sum of the n_i’s. (For convenience, r should be a very large number. We will see why shortly.) Then the user selects a positive number a satisfying gcd(a, m) = 1 and a < m. Let a′ satisfy aa′ = 1 (mod m), that is, a′ is the multiplicative inverse of a (mod m). Such an a′ exists since gcd(a, m) = 1.

Now, the user determines the sequence of positive numbers k₁, k₂, …, k_r by solving the r equations k_i = an_i (mod m), where i = 1, 2, …, r, such that each k_i < m. Finally, the user publishes the sequence k₁, k₂, …, k_r. This new sequence does not have the superincreasing property. (In the incredibly rare event that it does, repeat the above procedure using a different a.)

To send a message to our user, convert the text into a long binary string M of length, say, t, using a binary version of Table 9.2. That is, convert each number in Table 9.2 to its binary equivalent using a fixed number of digits for all entries. The letter C, for example, becomes 0000011 if we use seven digits for each binary number, while an empty space (formerly 00) becomes 0000000. Denoting the t digits of M by a₁, a₂, a₃, …, a_t, calculate the number

(9.7)

where, hopefully t ≤ r, the length of the sequence k₁, k₂, …, k_r. If r > t, break M into smaller numbers. Note that the recovery of M from N involves solving the knapsack problem represented by Equation 9.7.

The sender transmits N to the user. If an unauthorized person intercepts the transmission, he would not be able to recover M from N since the knapsack problem (9.7), involves a sequence that is not superincreasing. The user, knowing m and a′, converts (9.7) into a superincreasing knapsack problem by first multiplying both sides by a′ and reducing mod m as follows:

where N′ < m. This then becomes, using k_i = an_i (mod m) and aa′ = 1 (mod m),

This yields the knapsack problem , which is easy to solve since the sequence is superincreasing. The user readily recovers the string of binary digits a₁a₂a₃… comprising M.

The knapsack cryptosystem was developed in 1978 by Merkle and Hellman. It required modification several years later after Shamir developed an algorithm that solved the “encrypted” knapsack problem, that is, one using a sequence obtained from a superincreasing sequence n₁, n₂, …, n_r using the encryption equation k_i = an_i (mod m) with gcd(a, m) = 1.

EXERCISES

An asterisk (*) indicates that the exercise can be developed into a research project.

Count Letters

<!DOCTYPE HTML>
<html>
<meta charset="UTF-8">
<head>
<title>Count Letters</title>
<script>
var txt;
var counts= new Array();
var notLetters = " .,;?/!()'-";
function countLetters(){
  placeref = document.getElementById("place");
  placeref.innerHTML = "";
  txt = document.f.mytext.value;
  for (var i=0;i<txt.length;i++){
    letter = txt[i];
    if (okletter(letter)){
      if (counts[letter]){
         counts[letter]++;
         }
      else {
         counts[letter]=1;
      }
     }
  }
  message = "";
  for(key in counts) { 
       message += key + ": "+ String(counts[key])+"<br/>";
  } 
  placeref.innerHTML = message;
  return false;
}
 
function okletter(p){
   if (notLetters.indexOf(p)>=0){
     return false;
   }
   else {
     return true;
   }
}
</script>
</head>
<body>
Counting letters: <br/>
 <textarea name="mytext" form="f">Enter text here </textarea>
 <br/>
<form name="f" id="f" onSubmit="return countLetters();">
 
 <input type="submit" value="Submit"/>
</form>
<div id="place">
Answer will go here.
</div>
</body>
</html>

Count Letters and Produce Table in Alphabetical Order

<!DOCTYPE HTML>
<html>
<meta charset="UTF-8">
<head>
<title>Count Letters</title>
 
<script>
var txt;
var counts= new Array();
var letters = "abcdefghijklmnopqrstuvwxyz";
function countLetters(){
  placeref = document.getElementById("place");
  placeref.innerHTML = "";
  txt = document.f.mytext.value;
  txt = txt.toLowerCase();
  //initialize counts for the letters
  for (var i=0;i<letters.length;i++){
     counts[letters[i]] = 0;
  }
  for (var i=0;i<txt.length;i++){


    counts[txt[i]]++;      
  }
  message = "<br/> <table border='1'>";
  for(var i=0;i<letters.length;i++){

message+="<tr><td>"+letters[i]+"</td><td>"+String(counts[letters[i]])+"</td></tr>";
  }
  message+="</table>"; 
  placeref.innerHTML = message;
  return false;
}
 
</script>
</head>
<body>
Counting letters: <br/>
 <textarea name="mytext" form="f">Enter text here </textarea>
 <br/>
<form name="f" id="f" onSubmit="return countLetters();">
 <input type="submit" value="Submit"/>
</form>
<div id="place">
Answer will go here.
</div>
</body>
</html>

Count Letters and Produce Table in Order of Frequency

<!DOCTYPE HTML>
<html>
<meta charset="UTF-8">
<head>
<title>Count Letters &#38; Sort</title>
<script>
var txt;
var counts= new Array();
var letters = "abcdefghijklmnopqrstuvwxyz";
var lettercount = [];
function countLetters(){
  placeref = document.getElementById("place");
  placeref.innerHTML = "";
  txt = document.f.mytext.value;
  txt = txt.toLowerCase();
  //initialize counts for the letters
  for (var i=0;i<letters.length;i++){
     counts[letters[i]] = 0;
  }
  for (var i=0;i<txt.length;i++){
     
    counts[txt[i]]++;      
  }
  
// now create new array with letters and count
  lettercount = [];
  for(var i=0;i<letters.length;i++){
    lettercount.push([letters[i],counts[letters[i]]]);
  }
  //now sort based on the second (1st index) value
  lettercount = lettercount.sort(function(a,b){
      return a[1]<b[1];
  });
  
  message="<br/> <table border='1'>";
  for (var i=0;i<lettercount.length;i++){
message+="<tr><td>"+lettercount[i][0]+"</td><td>"+lettercount[i][1]+"</td></tr>";
  }
  message += "</table>";
  placeref.innerHTML = message;
  return false;
}
 
</script>
</head>
<body>
Counting letters: <br/>
 <textarea name="mytext" form="f">Enter text here </textarea>
 <br/>
<form name="f" id="f" onSubmit="return countLetters();">
 
 <input type="submit" value="Submit"/>
</form>
<div id="place">
Answer will go here.
</div>
</body>
</html>

Fermat Factoring

<!DOCTYPE HTML>
<html>
<meta charset="UTF-8">
<head>
<title>Fermat Factoring</title>
<script>
 
function factor(){
  placeref = document.getElementById("place");
  placeref.innerHTML = "";
  n = Math.abs(parseInt(document.f.num.value));
  if (n<=2) {
    message = "0, 1, 2 have no non-trivial factors";
  }
  else if (isEven(n)){
    message = "A factoring of "+String(n)+" is "+ String(2)+" X "+ String(n/2);
  }
  else {
    t = factorOdd(n);
    message = "A factoring of "+ String(n)+" is "+ t[0] + " X "+ t[1];
  }
  placeref.innerHTML = message;
  return false;
}
function factorOdd(m){
    var a;
    var b;
    var a0 = Math.floor(Math.sqrt(m));
    var as;
    var b;
    var bs;
    var rep = [1,m];
    // need to take care of obvious case of m being a // square itself
    if ((a0*a0)==m) {
      rep = [a0,a0];
    }
    else {
    for (a=a0+1;a<=m;a++){
       //check if a*a bigger than m and then …
       as = a*a;
       if (as>m){
         bs = as-m; 
         if (isaSquare(bs)){
           b = Math.sqrt(bs);
           rep = [a+b,a-b];
           break;
         }
       }
    }
  }
     return rep;
}
      
  
function isEven(n){
  return (0==(n%2));
 
}
 
function isaSquare(n){
   var s = Math.sqrt(n);
   return (s==Math.floor(s));
}
 
</script>
</head>
<body>
Enter number to seek factoring:
<form name="f" onSubmit="return factor();">
 <input type="number" name="num" value=""/>
 <input type="submit" value="Enter positive integer"/>
</form>
<div id="place">
Answer will go here.
</div>
</body>
</html>