1
$\begingroup$

Secret Agent Michael Scarn enters his hotel room, only to find it having been ransacked. He needs to send an encrypted message to his handler notifying them that his cover has been compromised.

In order to send encrypted messages, agents need a Cryptographically Secure Pseudo-Random Number Generator. Agent Scarn has two such generators with him, but through some testing, he can tell that one of them has been tampered with.

He doesn't know which of the two PRNGs have been modified; if he uses the wrong one, the rival spy agency will likely be able to decode the message, putting both him and his hander in danger.

Can Agent Scarn still generate secure random numbers for the encrypted message?

$\endgroup$
  • $\begingroup$ Am I missing something or can't he just get a number from each and perform some operation to them? One mod the other or something? $\endgroup$ – Engineer Toast Oct 26 '15 at 18:35
  • $\begingroup$ @EngineerToast You are on the right track; I don't know if using mod would produce a truly random distribution of values (I'd need to do some testing). $\endgroup$ – IQAndreas Oct 26 '15 at 18:37
  • $\begingroup$ I find the question a bit vague. What are we trying to do, exactly? One way of interpreting it is this: "secure random number" means "number generated according to the distribution of the original PRNG", but it's easy to see that it's impossible to combine the outputs of A and B to get the original distribution. $\endgroup$ – Jack M Oct 26 '15 at 20:17
  • $\begingroup$ @JackM By "secure", I meant as in the cryptographic definition: en.wikipedia.org/wiki/… (uniformly distributed, with no way of predicting the next value either forwards or backwards). $\endgroup$ – IQAndreas Oct 26 '15 at 22:50
  • $\begingroup$ @JackM Even if we need "a number generated according to the distribution of the original PRNG", so long as we know the distribution of the original PRNG (A) and have another PRNG with uniform distribution (B), we can use the output of B to match the distribution of A. $\endgroup$ – IQAndreas Oct 26 '15 at 22:57
10
$\begingroup$

Easy:

Use both PRNGs and XOR the two numbers obtained each time.

How does this guarantee that the message will not be decodable?

Assume that his enemies know exactly what PRNG A will produce, but nothing of what B will produce. We can describe A XOR B as using a one-time pad to encrypt A, which is an unbreakable form of encryption unless the pad is reused or the pad is not generated in a cryptographically secure manner. Because only one of the PNRGs has been tampered with, the other will still generate cryptographically secure numbers. Also, because XOR is symmetric, $a\oplus b=b\oplus a$, making it irrelevant which one is A and which one is B. Thus, $a_i\oplus b_i=c_i$ is a new random number that cannot be obtained without knowing both $a_i$ AND $b_i$ (which requires knowing the output of both A and B).

$\endgroup$
  • 2
    $\begingroup$ But how will his agency know how to decode the message? $\endgroup$ – JonTheMon Oct 26 '15 at 19:15
  • 3
    $\begingroup$ @JonTheMon Probably a Diffie-Hellman key exchange. $\endgroup$ – Rob Watts Oct 26 '15 at 19:17
  • $\begingroup$ What is 'XOR two numbers'? Isn't XOR a logical operation? $\endgroup$ – Fimpellizieri Oct 27 '15 at 0:43
  • 1
    $\begingroup$ @Fimpellizieri en.wikipedia.org/wiki/Bitwise_operation#XOR $\endgroup$ – Rob Watts Oct 27 '15 at 4:34
0
$\begingroup$

My original answer was bad, BUT i have a new answer:

use this code (search polynumcrypt in the search bar above), use one of the key generators, and send the key and the message to the recipient.

$\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.