# Cryptography finding $\bar{k}$

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) .

-
what is the question here? –  user48900 Aug 8 '13 at 4:06
To find $\bar{k}$. The rest is background info or extra. –  Kathy Aug 8 '13 at 4:09
But its seems from the way you ask the question that you know the answer already. –  user48900 Aug 8 '13 at 4:10
I don't. I am new at this. Just trying to give what I know. –  Kathy Aug 8 '13 at 4:18
Note that this way of encrypting gives no real security. The public key is known, and we encipher one letter at the time. So 26 encryptions (as $e$ and $n$ are known) gives us the complete cipher space, for this mode... We need of course way bigger $n$ and we must not encrypt the message without using bigger blocks and randomization (to ensure that twice encrypting the same gives 2 different results with very high probability). –  Henno Brandsma Aug 10 '13 at 15:16
add comment

## 1 Answer

We are given the critical parameters from RSA as:

• $n = 899$
• $k = 11$

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:

• $C_1 = 7^{611} \pmod {899} = 20 = S$
• $C_2 = 605^{611} \pmod {899} = 16 = O$
-
@Kathy: does this make sense? –  Amzoti Aug 8 '13 at 4:18
well let me rephrase that. I new it was supposed to be sos but I did not know how to get there. –  Kathy Aug 8 '13 at 4:19
Yes. Much more than I was understanding previously. Thank you. –  Kathy Aug 8 '13 at 4:20
@Kathy: You are very welcome. Regards –  Amzoti Aug 8 '13 at 4:21
POETS Day is almost here. Take heart! ;-) –  amWhy Aug 9 '13 at 0:05
show 1 more comment