To decrypt this version of Turing's code, does the decrypter actually need the secret key?

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.

• 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. Apr 22 '16 at 22:00

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.