In order to transmit messages in a secure way, some sort of scrambling or encoding of the message is necessary. Without doing so, sensitive information about intended troop movements or information about troop strength and equipment could be intercepted by the enemy with nasty consequences. Secret codes were used early on by the Romans. Julius Caesar used a simple type code called the “Caesar Cipher” wherein the letters of the alphabet were shifted a fixed number of places. If the letters of the alphabet are numbered from 0 to 25 (A to Z) then each letter in the message would be replaced by itself plus 3 (mod 26). For instance, “A” would go to “D”, “Z would go to “C” and so on. To unscramble the message, the letters in the encrypted message would be replaced by themselves minus 3 (mod 26).
encode the message “Do you think their aim is any good?”
decode the message “ RXFK!”
Various secret codes were used during the revolutionary war and the civil war. As codes became ever more devious, methods to decode become more sophisticated. During the second world war, encryption and decryption techniques were elevated to a high art form, practiced with extreme ingenuity by the Germans as well as the Allies. Nowadays, aside from military communication, huge quantities of sensitive personal and financial data are routinely transmitted. This means we need to be sure unauthorized persons will have a hard time decoding such messages. We come now to a widely used system called the “RSA public-key” (RSA stands for its inventors Rivest, Shamir and Adleman – researchers at M.I.T). The method is based on the following lemma,
Lemma: Suppose that $(k,\phi({m}) )=1$. Let S be the set of the least positive residues (mod m) which are relatively prime to m. Then the function $a \to a^{k} \mod m$ is a permutation of S (i.e. is a 1-1, onto function from S to S). If $\bar{k}$ is such that $k\bar{k} = 1 \mod \phi(m)$ then the function $b \to b^{\bar{k}}$ from S to S is the inverse function.
Proof: Clearly $(a^{k})^{\bar{k}}$ = $ a^{k\bar{k}} \equiv a \mod m$ so the latter function is the inverse of the former. This implies that each function is one-to-one and onto.
The way this is used in practice to encode and decode is to convert text into numerical data and raise to the power k and then reduce (mod m). To decode, $\bar{k}$ must be found.
Here is an example, where we use the simple numerical ordering of the letters of the alphabet, beginning with A as “2”. In practice, the modulus m is the product of several very large primes, so that m might have 200 or more digits. Obviously, here such magnitude is impractical.
Example: For our modulus m we take $m = 29 \cdot 31 = 899$ and we take $k = 11$ (we want $k$ to be relatively prime to $\phi(m)=28 \cdot 30 = 840$ . Our message is “SOS”. Converting to integers we get 20 16 20 . We compute $20^{11} 16^{11} 20^{11}$ and reduce mod 899. We get
7 605 7 and we send 7 605 7.
To decode we need to find $\bar{k}$ (which is the inverse of $k \mod phi(m)$) . Find and check that it works (hint: try to use Fermat’s little Theorem) .
We are given the critical parameters from RSA as:
To find $d$ (the decryption exponent), we need the modular inverse of $k^{-1} \pmod {840}$.
So we get:
$$d = 11^{-1} \pmod {840} = 611$$
Check that decryption works property (only have two characters), where $C_x$ means cleartext characters: