0
$\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?

Improve this question
$\endgroup$
7
  • $\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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 22:57

2 Answers 2

Reset to default
11
$\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).

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ But how will his agency know how to decode the message? $\endgroup$
    – JonTheMon
    Oct 26, 2015 at 19:15
  • 3
    $\begingroup$ @JonTheMon Probably a Diffie-Hellman key exchange. $\endgroup$
    – Rob Watts
    Oct 26, 2015 at 19:17
  • $\begingroup$ What is 'XOR two numbers'? Isn't XOR a logical operation? $\endgroup$
    – Fimpellizzeri
    Oct 27, 2015 at 0:43
  • 1
    $\begingroup$ @Fimpellizieri en.wikipedia.org/wiki/Bitwise_operation#XOR $\endgroup$
    – Rob Watts
    Oct 27, 2015 at 4:34
  • $\begingroup$ This answer depends on destroying the pattern (which is the only reason you'd ever use a PRNG instead of an actual RNG) either PRNG gives, so an equally valid approach is to go downstairs to the reception desk, get change for a fiver, and use 1 for heads and 0 for tails. $\endgroup$
    – Bass
    Feb 23, 2021 at 22:25
-1
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.