2
$\begingroup$

According to Wikipedia the One Time Pad Cipher is unbreakable. On the Wikipedia page it explains how to perform this simple encryption process by hand. For the encryption it adds (+) the message and the key and then modulo by 26. For the decryption it subtracts (-) the key and the ciphertext and then modulo by 26 again.

In another source it explains that for the encryption process one should subtract (-) and for the decryption process one should add (+).

Which one of these sources are correct and what will the security difference be between the two order of operations?

$\endgroup$
9
$\begingroup$

There is no difference. In fact, any quasigroup operation will do.

Specifically, the only property we really need is that, for every ciphertext symbol $C$ and every plaintext symbol $P$, there exists one (and only one) key symbol $K$ such that encrypting $P$ with $K$ yields $C$. This implies that, as long as the actual key symbols are chosen uniformly at random (so that each of them is equally likely to be correct), knowing the ciphertext symbol $C$ does not reveal any information about the plaintext symbol $P$ (since each $K$, and therefore each $P$, is equally likely).

In fact, we can generalize further and allow several key symbols to produce the same encryption, as long as the number of key symbols that yield $C$ is the same for every plaintext symbol $P$.

There are several common operations that can satisfy this property. For example, we can use modular addition for encryption, and modular subtraction for decryption, or vice versa. Or we could use e.g. bitwise XOR, which is its own inverse, and can thus be used for both encryption and decryption in the same system. Or, if we wanted, we could use e.g. multiplication in a Galois field for encryption, and multiplication by the group inverse for decryption (or, again, vice versa).

$\endgroup$
1
  • 1
    $\begingroup$ Note that for multiplication in a Galois field to be a secure analogue of the one-time pad, one needs to restrict to non-zero elements. ​ ​ $\endgroup$ – user991 Jun 5 '16 at 13:51
1
$\begingroup$

I only know how the one-time pad works on paper, having used the system when serving in the British SAS back in the 60s and 70s.

So, there are only three ways of doing the math. The commonest method is to add the pad numbers (K) to the plaincode (P) to get the cyphertext (C). To decrypt, subtract K from C to get P. You can also start by subtracting K from P, then decrypting by adding K to C. The third method is slightly counterintuitive. For this you encrypt by subtracting P from K to get C, and to decrypt you subtract again, C from K.

It may help to visualise it. For the first two methods you write your plaincode and the cyphertext above the printed numbers on the pad, and for method three you write P and C underneath the pad numbers.

All three methods are equally secure, and each one results in a completely different cyphertext. No other combination of adding/subtracting works. Incidentally, in WW2 my mother worked in the coding department of the Special Operations Executive (SOE), also using one-time pads.

$\endgroup$
5
  • 1
    $\begingroup$ As Ilmari's answer already states, there are many ways to combine plaintext and key in a way that results in perfect security, not just three. $\endgroup$ – CodesInChaos Dec 15 '17 at 15:46
  • $\begingroup$ I'm afraid you are wrong. Anything else produces garbage. Try it. Shouldn't take you more than 5/10 minutes. There are only 9 potential combinations as far as I know. Six of them don't compute. $\endgroup$ – SF Man Dec 15 '17 at 15:54
  • 2
    $\begingroup$ Only if you restrict yourself to a single modular addition/subtraction. Xor is a very popular choice (on power-of-two alphabet sizes). But even on an alphabet with 26 symbols, you have many other choices. For example, you could use addition/subtraction modulo 13 combined with xor for the remaining bit. $\endgroup$ – CodesInChaos Dec 15 '17 at 16:14
  • $\begingroup$ Doubtless you're right. As I wrote, I was only referring to what happens on paper, as was the original questioner. That said, I can't see the advantage of adding a series of extra calculations - the three I describe are all perfectly secure. Isn't three enough? Then again, I was only a frontline soldier, where we tried to keep things simple. Encoding with a one-time pad after a 12-hour march was quite a pain :-) $\endgroup$ – SF Man Dec 15 '17 at 16:28
  • $\begingroup$ As @CodesInChaos notes, your answer is only correct if you limit the allowed operations to addition and subtraction modulo the alphabet size. (Indeed, this is easy to see mathematically, since there are only three ways of adding or subtracting two numbers $p$ and $k$ – either $p + k$, $p - k$ or $k - p$ – and each of them has a unique inverse decryption formula.) However, if you're using e.g. a cipher table (or a computer) to do the encryption, many more equally correct and secure ways are possible. $\endgroup$ – Ilmari Karonen Dec 15 '17 at 20:52

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.