0
$\begingroup$

I'm implementing an encryption algorithm that requires me to use a random number to mix up the values. However I'm caught in between if I should use quasi-random or pseudorandom.

These are the things I'm thinking about:

  1. quasi-random isn't really a random number generator by definition but it's a good substitute for a uniform random number generator, especially in the area of sampling across a plane and mathematically speaking it's more uniform compared to a uniform number generator.

  2. pseudorandom on the other hand by definition is random. But if the attacker knows the seed its clearly not random also. And because it is less uniform compared to quasi-random it presents a certain bias towards a certain group of numbers.

So is randomness or the uniform distribution more valued when generating a random number? Should I choose a PRNG or a quasi-random number generator?

$\endgroup$
  • $\begingroup$ If this is for crypto purposes (ie you really don't want the numbers to be predicted), you want a CSPRNG, if not, this is the wrong place to ask :p $\endgroup$ – SEJPM Sep 23 '17 at 9:42
  • 1
    $\begingroup$ What do you mean by “quasi-random”? In what way is it an alternative to “pseudorandom”? The opposite of pseudorandom is non-deterministic random, and the difference has nothing to do with uniformity. I think you have a misconception about randomness, but I can't figure out what it is. What are you trying to implement precisely? What led you to think about quasi-random vs pseudorandom? $\endgroup$ – Gilles 'SO- stop being evil' Sep 23 '17 at 12:57
  • 2
    $\begingroup$ @Gilles: the term 'quasirandom' refers to a random generator that is biased, but in a way that we like (for some reason); for example, consecutive outputs may be more spaced out than would be expected with a uniform generator. This may be of use in statistical analysis or monte-carlo simulations; it hasn't been used much in cryptography... $\endgroup$ – poncho Sep 23 '17 at 13:10
  • $\begingroup$ You seem confused with your definitions. Random simply means unpredictable. It implies nothing whatsoever about the distribution of the output. All dice and Poisson generators are random. There is no mathematical definition of quasi random. If you have output distribution s in mind, it might be worth your while rephrasing the question. $\endgroup$ – Paul Uszak Sep 23 '17 at 21:45
2
$\begingroup$

I'm implementing an encryption algorithm that requires me to use a random number to mix up the values. However I'm caught in between if I should use quasi-random or pseudorandom.

It may sound counterintuitive, but what works best within an encryption algorithm does in fact depend on the details of that algorithm. It may be that, for your encryption algorithm, a uniform random distribution has a nonnegligible probability of creating a weak transform, and a tailored nonuniform ("quasirandom") distribution is better.

I assume you have spent a lot of time exhaustively cryptanalyzing your encryption algorithm; what does that analysis say?

And, by the way:

And because it is less uniform compared to quasi-random it presents a certain bias towards a certain group of numbers.

Actually, that's not accurate; the definition of a uniform distribution (which is the name of the distribution that an unbiased random number generator generates) is that it doesn't have a bias. For example, consider the probability that a generator proceduces two consecutive outputs $7, 7$. If the generator was uniform, the probability of those two outputs is precisely the same as the probability of producing any other two specified outputs. However, if the generator is quasirandom, the probability may be significantly smaller (even 0), if the quasirandom generator was biased away from repeating outputs.

$\endgroup$
  • $\begingroup$ thanks for your reply. by the law of large numbers a uniform rng should able to cover a 2D plane however it seems to me, with example codes comparing quasi-random to uniform random numbers, the uniform random number would have an issue covering a 2D plane properly due to its high--discrepancy. But i have realized my mistake and i was looking at the wrong places. it seems that the entropy of the rng is most important for encryption and quasi-random would get increasing predictable as the number of encryption increases. $\endgroup$ – albusSimba Sep 23 '17 at 15:55
  • 1
    $\begingroup$ @albusSimba I guess that feels like you're now thinking in the right direction at least. And yes, the entropy source is very important; once you have about 128 bits of "true" entropy you put it into a CSPRNG and you should be OK for the random number generator (although reseeding the RNG with additional entropy now and then doesn't hurt). $\endgroup$ – Maarten Bodewes Sep 25 '17 at 17: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.