2
$\begingroup$

Background: my question at :

My pencil and paper One Time Pad works fine without modular math ...... or does it?

I am trying to understand, from a layman's point of view, how to make the best one time pad scheme.

From responses to my above referenced question in another post, I understand now why I should use modular math in the scheme, and that the keyspace should be at least as large as the plaintext space.

So, moving beyond those points, I would like to try to understand the best modular base per given plaintext space. For example:

My alphabet's plaintext space is 40 characters, numbered 0 through 39.

So, I am using mod40 math. But I am only using mod40 math because I read elsewhere that my modular base should equal the size of my plaintext space. But I also know that my OTP will still function if my mod base is less than the size of my plaintext space or more than that size. So, in my example, I could use mod30 math or mod50 math just as well as mod40 math.

Therefore, my question is: what is the importance of the mod base in relation to the plaintext space, and, is there an optimal relationship between the two, and, if so, how can I know the optimal ratio of "mod base/plaintext space" in any OTP system?

$\endgroup$
  • $\begingroup$ The "mod base" is effectively irrelevant if you use addition and you pick at least $2$. $\endgroup$ – SEJPM Sep 8 '18 at 10:45
  • $\begingroup$ You should also give the keyspace and ciphertext space. $\endgroup$ – fkraiem Sep 8 '18 at 11:03
  • $\begingroup$ Not sure if those who write answers or comments are notified of OP edits or comments, therefore adding a comment here in addition to the edit in my original post. $\endgroup$ – EncryptThis Sep 9 '18 at 16:33
2
$\begingroup$

I am assuming that your scheme encrypts $x$ to $x + k \bmod N$, where $k$ is the key and $N$ is the modulus.

If your modulus is less than the alphabet size, decryption does not work.

Suppose your alphabet size is $n$ and you work modulo $n-1$; then the plaintexts $0$ and $n-1$ are considered the same, since $0 \equiv n-1 \pmod{n-1}$. Thus, no matter your key, they will be encrypted in the same way, and when you try to decrypt, you cannot tell them apart.

If your modulus is greater than the alphabet size, you do not have perfect secrecy (hence not an OTP).

This was already covered in answers to the referenced question.

$\endgroup$
  • $\begingroup$ I did this on paper with an alphabet size of 3 {0,1,2} using mod2 and could reproduce what you describe as 2mod2 = 0 and regarless of key value will always decode back to zero, which is the same value as the first element of the alphabet set. It is possible that this was already answered for me earlier but in a way that I could not understand. I'm glad to get it now! $\endgroup$ – EncryptThis Sep 9 '18 at 17:20
  • $\begingroup$ Concerning what was covered in answers to the referenced question, I went back and read answers to that question. Those answers explain why modular math is necessary vs not at all (asked and answered), and why the keyspace must be at least as large as the plaintext space (not asked but answered). But the matter of which modulus to use was neither asked nor answered. $\endgroup$ – EncryptThis Sep 9 '18 at 18:18
  • $\begingroup$ Could you please clarify what the alphabet is? If 40 characters are used within standard octets, is the alphabet 40 or 256 characters? $\endgroup$ – Paul Uszak Sep 9 '18 at 22:20
1
$\begingroup$

Let $\Sigma$ be your alphabet, i.e. the set of characters you will be using to encode your message. In your case the size of $\Sigma$, $\left|\Sigma\right|=40$ is 40 with $\Sigma$ then being the set of all the characters you will be using.

Further let $\widetilde\Sigma$ be another alphabet, e.g. $\widetilde \Sigma=\{0,1\}$ and let $f:\Sigma\to\widetilde\Sigma^k$ be a bijection for some fixed $k$. Obviously the minimal choice of $k$ is $6$ for $\left|\widetilde\Sigma\right|=2$. Essentially what $f$ will be doing is to "translate" between your standard set of characters and any chosen other (where you encode one of your standard letters to exactly $k$ others). Note that if you are happy with $\Sigma=\widetilde \Sigma$, then $f(L)=L$.

For the OTP to be secure it is required that you have a so-called group with the following properties:

  • The set of the group is a (non-strict) superset of $\widetilde \Sigma$, this means if you the set of all non-negative integers smaller than $n$ with modular addition as your group that all letters of the encoded alphabet need to be (stricly) smaller than $n$. Also note that this is required because otherwise you have either unencryptable characters or ambigous encryptions.
  • Your key element $K_i$ for each character position is chosen independently and uniformly at random from the full set of the group.

Then you can encrypt every message letter-by-letter as $f(L)$ combined with $k$ key elements. Decryption then simply means you take $k$ ciphertext letters, invert your $k$ key elements (i.e. you compute $-K_i$) and combine them with the ciphertext (i.e. compute $C_i+(-K_i)$) and then apply the inverse of $f$, $f^{-1}$ on the result to recover the original letter $L$.

what is the importance of the mod base in relation to the plaintext space

See above to see that the mod base effectively doesn't matter if it's $\geq \left|\widetilde \Sigma\right|\geq 2$.

is there an optimal relationship between the two?

That depends on your understand of "optimality". If you want to have a particlar modulus (="mod-base") for performance reasons, e.g. if

  • You are doing this by hand and you want your modulus to be a power of $10$ because you can compute faster that way you want $\left|\widetilde \Sigma\right|= 10^l$
  • You are implementing this in actual hardware and you want to use XOR as the group operation, you need $\left|\widetilde \Sigma\right|= 2$
  • You are doing this by hand but want to avoid any conversion overhead at any cost, i.e. you want $\Sigma=\widetilde\Sigma$, then you probably want to use $\left|\Sigma\right|$.
$\endgroup$
  • $\begingroup$ Granted, the term "one-time pad" is ill-defined, but it seems to me that $\Sigma = \tilde\Sigma$ should be a requirement for a scheme to be called thus. Otherwise, it's just a synonym for "encryption scheme". $\endgroup$ – fkraiem Sep 9 '18 at 16:57
  • 1
    $\begingroup$ SEJPM, I appreciate the depth of your response but it was beyond me even after looking up bijunction. My fault for not clarifying in my original post that I needed more of a conceptual answer than a mathematical answer. I cannot accept your answer by clicking on 'accept' because I don't really know how to evaluate your answer. $\endgroup$ – EncryptThis Sep 9 '18 at 17:25

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.