Summary of Secret Codes

• Codes such as “I love you” = “J mpwf zpv” have two characteristics which are distinct from the characteristics of modern codes used for secret communications today.

1. They are easy to break.

2. If you know how the message was coded, you automatically know how to decode it.

• Modern codes are based on a few ideas from the mathematical area called “number theory”, an area that deals with properties of integers.

1. Fermat's Little Theorem:

   a^p-1≡1 mod p

2. Factoring is very hard. Even computers can't do it rapidly.

The next item require us to know the number of seconds in a year. This is:

60∙60∙24∙365=31536000≈3∙10⁷

• To see how impossible factoring is, consider two numbers with 100 digits each. The product will have about 200 digits and the number of possible factors (if we don't know them) will be 10¹⁰⁰ . Suppose we have a computer which can test 1,000,000,000,000,000 factors per second. That's 10¹⁵ factors/second. Thus in one year a computer can check about: 3∙10²² factors/year, which means it would take many thousands of years to test all of the 10¹⁰⁰ possible factors. (There are some techniques that would actually speed up factoring, but the essence of this argument will still hold – factoring can't be done rapidly.)

• The situation with calculating a^b where a and b each have 200 digits is even worse. We can't even hope to store such a number in a computer as it would have more digits then there are atoms in the universe. The key idea that lets us use Fermat's Little Theorem is that “modulo arithmetic” can be done without storing the entire number.

  For example consider this computation of 23³⁰ mod 7

  23³⁰ mod 7 =

(3∙7+2)³⁰ mod 7 =

2³⁰ mod 7 =

2^5∙6 mod 7 =

(2⁵)⁶ mod 7 =

(32)⁶ mod 7 =

(4∙7+4)mod 7 =

(4)⁶ mod 7 =

(16)³ mod 7 =

(2)³ mod 7 =

8 mod 7 = 1

Notice that I didn't do any big computations; in particular I have no idea what is the actual value of 23³⁰ . And I didn't use anything but the basic definition of modulo.