8
$\begingroup$

I've started learning cryptography in class and we've come across One-Time-Pads, in which the key (uniformally agreed upon) is as long as the message itself. Then you turn the message into bits, do $XOR$ and get the cipher text. This encrypts the message and to decrypt the message you'd do $XOR$ with the cipher and key bits.

Now to make a more efficient One-Time-Pad you'd use a pseudo-random number generator, where the original key is $n$-bits long (and doesn't have to be as long as the message). Then you'd put the key in the generator and get a pseudo random number. But since it's pseudo random, wouldn't the sender and receiver get different keys? Then how can the receiver decrypt the message if they don't have the same key?

Improve this question
$\endgroup$
4
  • $\begingroup$ If your core problem is about PRNG, the key may be used as seed (not really good for OTP). If both parties use the same seed (to the same generator) then generated sequences are the same. $\endgroup$ – Evil Mar 19 '18 at 15:19
  • $\begingroup$ Both parties use the same key. Using a PRNG, they extend it to a much longer random-looking common string, which serves as a one-time pad. $\endgroup$ – Yuval Filmus Mar 19 '18 at 17:25
  • $\begingroup$ Do you know how PRNGs work? $\endgroup$ – user253751 Mar 19 '18 at 22:58
  • 11
    $\begingroup$ Just as a hint for future questions, there is a whole Stack exchange site specialized on Cryptography. $\endgroup$ – Paŭlo Ebermann Mar 19 '18 at 23:07
17
$\begingroup$

You seem to have misunderstood what the key is.

In the context of symmetric encryption, the key is a shared secret: something that is known to both the sender and receiver. For OTP, the key is the entire pad and, if two people wish to encrypt some message using OTP, they must ensure beforehand that they have a long enough pad to do that.

For your proposed "efficient" OTP, the key is the PRNG seed: both parties must ensure beforehand that they know it. Then, they both initialize the PRNG with the same seed and it is guaranteed to produce the same sequence of "random" numbers for each of them.

However, note that this is a massive, massive weakening of OTP. An actual OTP gives perfect security, as long as the pad is kept secret. If you intercept the 17-character message

nsmklmfmwnfmngner

you have zero knowledge of whether it is

maketrumpthepotus

encoded with one pad, or

ensureclintonwins

encoded with a different pad. Or

kittensarethebest

or literally anything else. However, using a pseudorandom pad means that only certain pads are possible (maybe there's no key at all that encrypts the kitten message to "nsmklmfmwnfmngner", so you can rule that out). Anybody who knows the PRNG algorithm can start guessing keys to try to decrypt messages. Anyone who captures some pad material can start trying to reverse engineer the PRNG. Anyone who captures encrypted messages can start trying the same.

You really shouldn't call it OTP unless the key material is as long as the message. Your proposal for using a PRNG is just a generic stream cypher.

Improve this answer
$\endgroup$
6
  • 4
    $\begingroup$ I think it worth mentioning that OTP is effective and workable in the scenario where you have a secure high-bandwidth channel of communication (e.g. personal contact), but it is temporary—and you wish to send low-bandwidth communications securely later on. Example: give your one-time pad to your spy before his deployment; then he can use it to securely send brief messages as long as the pad lasts. $\endgroup$ – Wildcard Mar 19 '18 at 21:39
  • $\begingroup$ @Wildcard one should still combine it with a MAC to make sure the message is not modified in transit. $\endgroup$ – Paŭlo Ebermann Mar 19 '18 at 23:11
  • 8
    $\begingroup$ "You really shouldn't call it OTP unless the key material is as long as the message." and never ever reused. Hence, One-Time. The other thing (with the PRNG) is btw. just called a stream cipher. $\endgroup$ – Jonas Schäfer Mar 20 '18 at 9:27
  • $\begingroup$ @JonasWielicki "The other thing (with the PRNG) is btw. just called a stream cipher." Er, I said that in sentence after the one you quoted! $\endgroup$ – David Richerby Mar 20 '18 at 9:41
  • $\begingroup$ @DavidRicherby Ha. How did I miss that. $\endgroup$ – Jonas Schäfer Mar 20 '18 at 15:50
11
$\begingroup$

Now to make a more efficient One-Time-Pad you'd use a pseudo-random number generator

No, no and once again no. I'm concerned that this is what you're being taught. The absolutely fundamental concept of a one time pad and the notion of mathematically provable perfect secrecy is that the pad material is truly random. And it must never ever be reused, even once. It cannot be generated by any form of algorithm. The random numbers must come from a physical process such as dice throws, electrical noise or photon interference in a split laser beam. If you make them with any sort of algorithm /code then that's just a stream cipher like RC4 or an AES construct.

Browse through the one time pad tagged questions over at crypto.se. That will tell you everything. More importantly, you'll read many attempts at improving or making the one time pad more efficient. All of them are snake oil, no matter how enticing they might appear.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Reg. “cannot be generated by any form of algorithm” – technically speaking, even if you use a physical process as the entropy source, the actual key will in general still be generated by an algorithm: one that makes a uniform distribution out of the raw measurements, else it's not perfectly secure either. Just, that algorithm must start with more random bits than the key will have. $\endgroup$ – leftaroundabout Mar 20 '18 at 11:58
  • $\begingroup$ @leftaroundabout Of course you're right. I didn't want to muddy the already cloudy water with discussion of randomness extractors. $\endgroup$ – Paul Uszak Mar 20 '18 at 22:27
7
$\begingroup$

A pseudorandom generator is a deterministic algorithm, which given a short random seed returns a pseudorandom string fooling certain adversaries (i.e. such adversaries will not be able to distinguish the generator's output from a truly random string). Note that allowing the generator to toss coins makes the whole thing uninteresting, as you could simply return a truly random output.

In that case, the key can be the seed $s$, and the receiver can compute $G(s)$ to decipher the message (since $G$ is deterministic, this computation yields the same result for both parties).

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Note that many "random number generators" in computers use a mixture of real randomness and pseudorandomness, and thus neither work for this "short key" pseudo-one-time-pad nor for creating a proven-secure real one-time-pad. $\endgroup$ – Paŭlo Ebermann Mar 19 '18 at 23:10

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.