2
$\begingroup$

I want to encrypt a message that contains a fixed length random number and a long mod. i.e. 1234564284 (created like this 123456 + (123456 mod 9931))

I assume that reusing the same key is not a problem if the message is purely random but is the fact that the message is always given with a mod is opening a hole to find the key?

$\endgroup$
  • 1
    $\begingroup$ I don't understand your question. You have 2 numbers and a modulus. You cannot add by the mod operator, that doesn't make any sense. $\endgroup$ – mikeazo Mar 25 '16 at 23:42
  • 1
    $\begingroup$ Reusing a one time pad's key is very much a problem. $\endgroup$ – Bardi Harborow Mar 26 '16 at 9:27
  • $\begingroup$ @mikeazo: the message i want to encrypt is : "1234564284". this number is composed of a random number "123456" concatenated with 123456 mod 9931 = "4284". $\endgroup$ – hey_monkey Mar 26 '16 at 12:06
  • $\begingroup$ Let me make sure I understand, the algorithm for encryption of $m$ is to take $m+(m\bmod{n})$ where $n$ is the secret key. How do you then decrypt, given only a ciphertext $c$ and $n$? $\endgroup$ – mikeazo Mar 26 '16 at 12:29
  • $\begingroup$ not exactly. Alice want to send m (a random number) to Bob. To make sure that after decryption bob can verify that it is a valid number Alice add to m the m mod n. So the complete message is m+(m mod n). The secret key is a random key fixed and known by alice and bob. $\endgroup$ – hey_monkey Mar 26 '16 at 12:43
3
$\begingroup$

Here's my understanding of the encryption process you're talking about:

  • You take a random number $r$, and compute $t = r \bmod n$

  • You concatinate the two numbers $r$ and $t$, and express the concatination as a bitstring $u$

  • You then xor that bitstring $u$ with a secret bitstring $s$

You do the same for two different random numbers $r$ and $r'$, using the same values for $n$ and $s$.

If that is correct, then here is one way that someone with the two encrypted strings can recover a short list of possible $r, r'$ values:

  • Consider all possible $r$ values (in your example, $r$ was a 6 digit number, so that would be trivial; I don't know how long you would make $r$ in the real case)

  • For each such $r$, compute the corresponding $t = r \bmod n$, and combine them to form the bitstring $u$.

  • Exclusive-or $u$ with the first ciphertext to create the corresponding bitstring $s$.

  • Validate that guess on $s$ by attempting to decrypt the second ciphertext with it; recovering the corresponding $r'$, $t'$ values. If $t' = r' \bmod n$, then add $r, r'$ to the list of plausible values.

In the simple example you gave (and depending somewhat on how you encode the numbers as bitstrings), that would give you a list of approximately 100 $r, r'$ values, one of which are the correct one. It would be possible to list this to only the correct value given 1 or 2 more ciphertexts.

One time pad (where you use the secret bitstring $s$ only once) is safe because, while can reconstruct the possible values of $s$ (based on what the original message might be), you have no way to verify any possible $s$ value. By reusing $s$, you provide such a way, and thus lose the security guarantees that you have when you use $s$ only once.

It is likely possible to design a more efficient attack method; however that method would likely depend on the details of how you encode an integer as a bitstring

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you, very helpfull. In my real case "r" will be a 36bits string and "t" a 13bits string. And actually my main problem is if the key "s" is found but finding the right r,r' is finding the right s. $\endgroup$ – hey_monkey Mar 26 '16 at 20:54
  • $\begingroup$ @hey_monkey: in that case, I would advise you to either use a conventional nondetermanistic encryption method (say, GCM with a random nonce; if this case, you can drop the mod checksum), or (if you are limited in the size of the ciphertext you can handle) you use a Format Preserving Encryption method (in which case you can simply replace the mod with a fixed 0000 sequence) $\endgroup$ – poncho Mar 26 '16 at 20:59
1
$\begingroup$

Re-encrypting with the same pad is insecure, unless what your encrypting is already encrypted with a non-used pad or other system.

| improve this answer | |
$\endgroup$

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.