2
$\begingroup$

I would like to know what is the real purpose of using a modulus in the equivalent of a Vernam cipher:

Data $d$, large number $M$.
Assume the key length is $\lambda$ bits. Then $M$ could be $2^\lambda$. $k$ is picked from $\{0,1\}^\lambda$ using a pseudo random function (PRF)

Encryption: $C = k + d \pmod{M}$
Decryption: $d = C - k \pmod{M}$

What's the purpose of using $M$?

$\endgroup$
  • $\begingroup$ 1) What would you use instead? It's correct and it's convenient. What more do you want? 2) Nowadays we typically use xor (addition modulo 2) which is fast in software and encryption/decryption are the same function. 3) why do you claim M is a large number? It's often 2 or 256 and very rarely larger than 64 bits or so. $\endgroup$ – CodesInChaos Sep 22 '14 at 13:02
3
$\begingroup$

It depends on what you think of as an alternative.

If you think of the scheme where you do not use $M$ as a modulus, but the keys a picked as: $$ k \leftarrow \{1, \ldots, M-1\} $$ Encryption: $$ C = d + k $$ Decryption: $$ d = C - k $$ Then the scheme is insecure. One way to see this is to note that we have $C \geq d$. So the ciphertext communicates the information that $d \leq C$.

You could also think of a scheme where there is no $M$ at all: $$ k \leftarrow \mathbb{Z} $$ Encryption: $$ C = d + k $$ Decryption: $$ d = C - k $$ This would be secure, however, it would be impossible to implement because there is no way to sample $\mathbb{Z}$ (the integers) uniformly at random (think about it, how would you do that?).

So you see $M$ is really quite essential to the scheme.

$\endgroup$
  • $\begingroup$ So, for security reason, we must use the modulus ??? $\endgroup$ – zof Sep 22 '14 at 14:28
  • $\begingroup$ You could say that, yes. $\endgroup$ – Guut Boy Sep 22 '14 at 14:35
  • $\begingroup$ @zof In addition to this answer, maybe this page about “modulo encryption” can help you grasp it completely. (That “modulo encryption” also represents a nice string to throw at search engines btw.) $\endgroup$ – e-sushi Sep 22 '14 at 14:59
  • $\begingroup$ Yes, but in terms of security, what is the role of M !? $\endgroup$ – zof Sep 22 '14 at 15:36
  • $\begingroup$ @zof: it is there in order to make the +/- an operation over a finite group; OTP needs to be performed over a finite group (or, at least, a finite latin square) in order to be secure. $\endgroup$ – poncho Sep 22 '14 at 15:39

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.