0
$\begingroup$

I am self studying MIT's Mathematics for Computer Scientists (link) There is a chapter in the readings on Number Theory, and it goes through the math involved in the cryptography methods used around the second world war. Specifically it goes through "Turing's code" and variations on this. One of the versions is the following:

Sender and Receiver agree on a large prime $p$, which can be made public.

They also agree on a secret key $k \in {1, 2, ... p -1}$

The unencrypted message $m$ can be any integer in set ${0, 1, ..., p-1}$

The encrypted message is defined as $m^* = remainder(mk, p)$

My doubt is how decryption works:

If we know the multiplicative inverse of the secret key $k$ then we can do:

$m^* \cdot k^{-1} = remainder(mk, p)\cdot k^{-1} \equiv (mk) \cdot k^{-1} \pmod p \equiv m \pmod p$

Therefore, the encrypted message multiplied by the multiplicative inverse of the secret key is congruent to the unencrypted message mod p. Since the unencrypted message is in ${0,1,...,p-1}$ we can easily find it doing:

$m = remainder(m^*k^{-1}, p)$

The reading says that to find the multiplicative inverse you simply use the extended euclidean algorithm (called the Pulverizer in the reading, on pages 12 and 13) to find the coefficients on the linear combination of p and k that gives their greatest common divisor.

The coefficient on k will be k's multiplicative inverse (Lemma 4.6.1 on page 24).

I'm confused because to use the extended euclidean algorithm and find a multiplicative inverse for k, you need k. But k is secret.

I would just like to confirm that to be able to decrypt a message as described above, you would in fact need the secret key?

I came up with a numerical example just to illustrate:

$p = 100000969$

$k = 50287$

$m = 14090305$ which I got simply by mapping the alphabet to {01, 02, ... 26}. The message in english is thus "NICE".

$m^* = remainder(mk, p) = 52302170$

So if someone intercepts $m^*$ and wants to decrypt it:

Using a Python function for extended euclidean algorithm, I get that $-22011 \cdot p + 43771180 \cdot k = gcd(p, k) = 1$

Therefore, $k^{-1} = 43771180$

So we can decrypt the message by doing:

$m = remainder(m^*k^{-1}, p) = 14090305$

Note: I don't have enough reputation to give more than one link in this post, but I can link to the Python function used for extended euclidean algorithm, and also the MIT reading on Number Theory that I am following.

$\endgroup$
  • $\begingroup$ In the reading it is also mentioned that if you happen to have both an unencrypted and an encrypted version of a message, then you can find the secret key (using Fermat's Little Theorem). Was this the way people obtained secret keys? Was it prevalent to actually get both an unencrypted and encrypted message? Apparently the nazis didn't bother to encrypt their weather reports sometimes, but some of the U-boats did, so the allies did get this pair of encrypted/unencrypted messages and could find the secret key. $\endgroup$ – evianpring Apr 22 '16 at 22:00
1
$\begingroup$

Yes, if there is no known plaintext, and just a single cipher text $m^\ast$, you do need $k$ even if $p$ is known to everyone. In this case the plaintexts are numbers of a special form (because they're built up from smaller alphabet numbers in your case), so there might be a weakness there, and there are some other issues, but essentially yes.

But as said, one known plain text kills the system, because then $k$ can be computed. So it's basically useless.

As to the question in the comment: I skimmed the text of your handout and it sort of suggests that the Turing cipher (it's not really known under that name, though) was actually used or even a candidate for use. This is not the case. The Enigma (the German cipher that was one of those that Turing broke and was used by submarines, among others) was a rotor machine, no number theory involved. The attack did assume known plaintext to break it. This was from stereotyped messages or parts of messages (fixed greetings, fixed starts, the date, etc.) and indeed also from weather messages from metereological ships. These messages were encrypted using a special weather code book, and then for the submarines they were also encrypted (after that code had been applied). But the weather is quite guessable and the code messages were very standard (like 3 letters code for temperature, 3 for air pressure, 3 for wind etc.) Just flying and measuring in the neighbourhood of that ship narrowed the messages down to a handful of options, and the weather code books were known (captured from other ships before they sank) to the allies. So indirectly they did provide a pretty important source of known "plain text" for the Enigma. Especially since the submarines used better discipline (fewer messages, less stereotypes) and a stronger variant of Enigma as well.

So known plain texts (or guessed/assumed text), so called "cribs" that also had special properties w.r.t. the machine settings, were the way the code was broken, using specially built brute forcing machines ("bombes"). It was never really easy, but very useful when it did work.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.