If my plaintext alphabet is {0,1,2} has three characters, I understand why I cannot use a modulus less than 3 (decryption won't work).

My key has 100 different values, {0,1,2 .....99} . So key length is not an issue.

I do not see why I cannot use a modulus greater than three. Why can't I use a modulus greater than 3?

I ask because the modulus also limits the upper value seen in the ciphertext.

Therefore, if my modulus = my plaintext space, the size of my alphabet is easily known by the attacker.

So, in my example case where plaintext space = 3, why not use mod10 math instead of mod3 math? If I use mod10 math, my ciphertext values can be anywhere from 0 to 9 instead of only 0 to 2.

This seems an advantage to me, because the ciphertext reveals the modulus, and therefore reveals an upper boundary of my possible alphabet size, but does not reveal the exact alphabet size up to that boundary.

So, unless 'perfect secrecy' is somehow lost by using a modulus greater than the alphabet size, I should always use a modulus not equal to my plaintext size but higher than that value.

I am looking for either a hard flaw (why I cannot do it) or a weakness (why I should not do it) in my reasoning.

Edit September 13, to clarify the question:

My alphabet has only three characters: {0,1,2}. The only secret message I can send to my comrade can consist only of combinations of these three characters.

The physical (printed) one-time pad contains 100,000 characters, it is truly randomly generated. It consists of capital letters (26 values), lower case letters (26 more values), and the digits 0 through 9 (10 more values). Therefore, my keyspace is 62 characters, represented by the numeric values {0,1,2......59,60,61}.

So the physical pad is 100,000 characters long, values zero to 61, truly randomly generated.


I understand that if I use modular math, my modulus must be at least equal to my alphabet size. In my case, my alphabet size is three characters, so my plaintext space is 3. So, I must use at least mod 3, not less (If I use a modulus less than the alphabet size, decryption will not work, as regardless of key, the final character of my alphabet will always decode to the same as the first character of my alphabet).

So my question is, why not use mod 10 instead of mod 3?

Because: if I use a modulus equal to my plaintext size, then the highest possible value of my ciphertext will always equal my plaintext/alphabet size.

So you see, my ciphertext can reveal the upper bound of my alphabet size.

But if I use (arbitrarily) mod 30, then my ciphertext (overtime, after hundreds of messages) can show an upper bound much higher than my actual alphabet size, in the case of a modulus of 30, the ciphertext can show a max value of 30. Therefore the attacker cannot know that my alphabet is only 3 characters long; the best he can know is that my alphabet can be at maximum 30 characters long.

The idea being that alphabet size is critical information worth hiding.

And if the ciphertext reveals alphabet size, that is an advantage for the cryptanalyst.

I hope this edit makes my question clearer.

When describing the one-time pad as computationally secret when, if modular math is used, the system is easy to break because the modulus is revealed, in every case, by the ciphertext. How can the one-time pad continue to be presented as computationally secure when it's very modulus is revealed by its own ciphertext? When the one-time pad uses modular math, the ciphertext reveals the modulus, opening up a vector for attack by the adversary (because the adversary knows the modulus). Once the modulus is known (from observing the ciphertext), cracking the system becomes TRIVIAL as I see it.

  • 1
    $\begingroup$ Yes, true about Ye Olde Days! But my very first post was about " why use modular math at all in OTP?" or something to that effect, and from the answers there, I came to understand the value of using modular math in OTP even when using OTP with only pencil and paper. i.e. that using modular math greatly expands the range of plaintext that can be expressed by any value of key, and thereby makes cryptanalysis that much more difficult (if I understand it all correctly). in other words, OTP without mod math is much easier to crack. $\endgroup$ – EncryptThis Sep 9 '18 at 23:09
  • 4
    $\begingroup$ No! Sorry but absolutely not. The perfect secrecy of a OTP comes from the masking entropy of a truly random key that is the same length as the plaintext. That's it. Modular math, bijections, XORing or using a random lookup table are all exactly the same. With respect, you've misunderstood the fundamental nature of a OTP. It's all in the key and how it's generated using lasers, typewriters or sprockets. History confirms this. $\endgroup$ – Paul Uszak Sep 9 '18 at 23:26
  • 1
    $\begingroup$ I'm referring to your "OTP without mod math is much easier to crack". This is very, very wrong. As long as you have some wonderfully magical function $f[m_i, k_i]$ that returns a single unique character for every possible combination of message character $m_i$ and key character $k_i$, your encryption is perfectly secret. What $f$ does internally is irrelevant. Modular arithmetic is not a requirement. It's an option. As is XOR or a random look up table as done historically. They are all equally secure. $\endgroup$ – Paul Uszak Sep 10 '18 at 22:13
  • 1
    $\begingroup$ What makes you believe, it is any easier to break OTP when the modulus is known compared to it being not known? Also, if the message is sufficiently long, the message will contain every symbol of the ciphertext space at least once with high probability. $\endgroup$ – tylo Sep 14 '18 at 18:43
  • 1
    $\begingroup$ This post is a cautionary tale--and a display of restrained, skilled moderation. $\endgroup$ – Patriot Oct 5 at 13:49

What you are proposing is a larger key space and therefore ciphertext alphabet than the plaintext alphabet. This is fine and it is easy to prove why this is fine.

Let's assume that the plaintext alphabet, the key space and ciphertext alphabet are of the same size $n$: a normal OTP. In that case no information about the plaintext - other than the alphabet and plaintext size - is leaked. This is also true the if all messages contain just the first $x$ characters of the alphabet. If an attacker could even distinguish this fact then it would not be aan OTP. However having only messages of the first $x$ characters is indistinguishable from using a plain text alphabet of $x$ characters.

The key space does need to be as large as the modulus. Just imagine that you have a plaintext message consisting of just the letter 'a'. Then it is clear that some ciphertext characters cannot even be reached if the key space is smaller than the modulus. If the key space is larger than the modulus then you have bias on the ciphertext unless the key space is a multiple of the modulus. If it is a multiple then you have equivalent key values.

It is a misconception that knowing the size or the modulus threatens confidentiality. Neither the size of the message nor the size of the alphabet is required to be kept secret. Only the contents of the encrypted values need to be protected. If you want to keep the alphabet or size of the plaintext unknown then you need to take measures outside the one-time-pad, e.g. by adding more symbols to the alphabet or by padding the plaintext beforehand.

  • $\begingroup$ Maarten Bodewes thank you for you comment but no, I am not talking about keyspace in my original post. I am talking instead about the value of the modulus in relation to the value of the plaintext space. Please read my post again in order to understand the nature of my question. Thank you. I answer your comment because you said " What you are proposing is a larger key space", but that is not correct. Therefore your post is of no value to the discussion. You did not understand my Original Post. Thank you. $\endgroup$ – EncryptThis Sep 10 '18 at 3:16
  • 5
    $\begingroup$ @EncryptThis, the modulus has to be the same size as the keyspace. (Or if the key size is a multiple of the modulus, then the effective key size is just the modulus.) Otherwise some values are more likely than others. $\endgroup$ – otus Sep 10 '18 at 4:07
  • $\begingroup$ otus thank you for your comment but your comment speaks of keyspace, please read my original post again you will see that I am asking about the modulus in relation to the plaintext space, not the keyspace. To emphasize again, the keyspace has nothing to do with my question. Thank you for your time to comment here, but if you would like to comment again, please at least take the time to read my original post carefully. Thank you. $\endgroup$ – EncryptThis Sep 10 '18 at 6:43
  • 5
    $\begingroup$ EncryptThis please consider that maybe you are the one that doesn't grasp things rather than the experts here. I'm pretty sure that we've read your post correctly and fully. $\endgroup$ – Maarten - reinstate Monica Sep 10 '18 at 8:33
  • 1
    $\begingroup$ OK Maarten I accept your admonition and I will edit my question. It would not be the first time in life that I was the only one who didn't even understand what I was asking :) Thank you. $\endgroup$ – EncryptThis Sep 13 '18 at 19:02

There are three relevant numbers: the size of the plaintext alphabet $p$, the size of the key alphabet $k$ and the modulus $m$. There is also the size of the ciphertext alphabet, but that is by definition equal to the modulus.

Let's look at this with some explicit examples to make it clear.

In your example $p = 3$, $k = 62$ and you are considering $m = 3$ and $m = 10$. Both of these are insecure. To see why, let's simplify to $p=3$, $k=5$ and $m = 3$, so there are even fewer options. The possible ciphertexts are not equally likely:

$0$ will encrypt to $k \bmod 3$, which is $0$ if $k=0$ or $3$, $1$ if $k=1$ or $4$ and $2$ if and only if $k=3$.

So $2$ is an unlikely ciphertext if you are encrypting a plaintext zero. Similarly, if you work through the options, you will find that each ciphertext value is less likely for one plaintext value. This means that an adversary seeing a ciphertext $2$ knows that the plaintext is more likely to be $1$ or $2$, so you lack perfect secrecy.

The values $k=62, m=3$ and $k=62, m=10$ are similarly insecure, because the key is not a multiple of the modulus. If $k = lm$, where $l$ is an integer, then it is secure, but the effective key alphabet size is just $m$. E.g. with $k=6, m=3$ it does not matter if the key is $1$ or $4$ – you get the same result for any plaintext.

So it only makes sense to use $k=m$.

Now the initial question was about whether the modulus can be larger than the plaintext alphabet and to that the answer is yes, like Maarten Bodewes already explained. When $k=m$ the ciphertexts are all equally likely even if you only use smaller plaintexts.


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.