22
The solution is simply to make sure that you have good randomness. At the size of the numbers we are considering, the probability of a repeat when using good randomness is extremely small. To make this clear, there are well over $2^{1000}$ prime numbers of length 1024. The probability of a repeat at any reasonable number of primes chosen, when using true ...
11
Obviously, good entropy is the Right Solution, however there is a mitigation possible that would help somewhat even with marginal entropy.
The issue occurs if we have two different keys with the same $p$ but different $q$s; if that happens, then a third party with both public keys can factor both. What we can do is try to avoid this situation (even if ...
10
Is it possible to generate all shuffles with a PRNG that has 64, 128 or 160 bit internal state?
No, for restriction of "possible .. with" to a deterministic procedure using the Pseudo RNG output as sole input, and:
Bound to output a single shuffled sequence per run. To generate all shuffles, $\lceil\log_2(52!)\rceil=226$ bits of PRNG internal state are ...
6
(Comments to Yehuda Lindell's answer turned to answer per request)
The option to "write a fresh random 256-bit seed in every device during production" is good, in that it avoids the need for a reliable TRNG in the device. But it is not entirely without drawbacks: how do we make sure that no one knows that value, and convince others of that? Perhaps we ...
6
GCD only works if you have multiple different keys that share a prime. If the entire key is identical then GCD doesn't help you.
The duplicate primes problem is normally a result of a random number generator with two characteristics.
The random number is initially poorly seeded.
During the key generation process the random number generator is subject to ...
3
I would like to know whether a specific PRNG satisfy the next-bit test or not.
That requires analyzing the design of the PRNG.
Will satisfying all of NIST statistical tests on PRNG guarantees passing the next-bit test?
No. The NIST statistical tests are intended to test an implementation of a RNG. They are next to useless to tell if a PRNG is good or ...
2
When humans generate random key, there is some bias. For instance, in your example "93298762" there are only 2 turning points where as normally there should be 4 (you can argue that it is a single sequence and it is not long enough to seriously speak about statistics, but nevertheless...)
Even if an attacker does not know what generator you used, it makes ...
2
The source of confusion may be the following. Theoretically, since the work of Andrew Yao, it has been known that the next bit test is equivalent to pseudorandomness. Informally, a sequence generator is pseudorandom if and only if no polynomial time probabilistic algorithm can predict its next bit with probability strictly greater than $1/2.$
See the notes ...
1
Clearly the installation of health tests must come after the development of the entropy source. As part of that development, you'd need to assess the min.entropy of your new system under whatever sampling methodology you choose. And Min Entropy H comes out of that assessment. It is "the min-entropy of the samples from a (digitized) noise source or of the ...
1
Yes it most certainly is, on the assumption that the hashing algorithm used is cryptographically secure and uniform in its output.
As a thought experiment, consider that after Elliptic Curve Diffie Hellman, the shared secret's (curve point) x co-ordinate is recommended by good practice to be passed through a hashing algorithm to derive a key.
This is ...
1
I will take a different take vs previous answers. Let's say we really have only 128 bits of entropy at our disposal does that prevent us from applying a determinstic algorithm on shuffling a deck of cards?
From a pure counting perspective surely, a determinstic function on 128 bits of input can not have 52! different possible outputs.
But If we use ...
1
As a stream cipher I don't think there is any direct way to break the cipher.
First of all, it is extremely inefficient, as Richie already mentions. SHA-256 has an input block size of 512 bits, and you're only propagating 128 out of 256 output bits. So you're wasting a lot of input space. In other words, it won't be twice as slow as just SHA-256 due to the ...
Only top voted, non community-wiki answers of a minimum length are eligible
