Questions tagged [pseudo-random-generator]
In cryptography, a pseudo-random generator (PRG) is a deterministic procedure that maps a random seed to a longer pseudo-random string such that no statistical test can distinguish between the output of the generator and the uniform distribution. Pseudo-random generators have numerous applications in cryptography. For instance, pseudo-random generators provide an efficient analog of one-time pads.
42
questions
31
votes
4answers
27k views
What is difference between PRG, PRF, and PRP
Until what I have gotten is: A PRG is generator is a part of PRF that produces pseudo-random values for the function. PRF is semantically secure and has no worries of being invertible. Fine, then ...
7
votes
2answers
4k views
Are there any standards of multi-prime RSA key generation?
FIPS 186-3 specifies a method to generate DSA parameters.
Is there anything similar (official standard or widely-accepted recommendation) that shows how to generate the primes for multi-prime RSA?
-2
votes
2answers
632 views
Relationship between a key stream having a high entropy and whether it is cryptically secure in a stream cipher
Hi i am trying to build a key stream generator for my homemade stream cipher.The key stream output has a close to maximum entropy value and a large periodicity. What does it take for this generator to ...
14
votes
1answer
732 views
Overview of relations between cryptographic primitives?
Is there a web page that gives a graphical (or, alternatively, a textual) overview of known implications and separations between cryptographic primitives?
More specifically, I am looking for ...
31
votes
6answers
13k views
What does it mean for a random number generator to be cryptographically secure?
I've never heard a good answer. I'd like to hear details about:
What are the criteria that make an RNG cryptographically secure?
Why must your RNG be cryptographically secure? I.e., what are the ...
8
votes
3answers
5k views
How to attack a fixed LCG with partial output?
To show some colleague programmers exactly how broken C's rand() is (at least on Windows) I decided to break it. So everyone knows the exact parameters, MSVC's ...
6
votes
3answers
2k views
How do I produce a stream of secure random numbers from AES-Counter mode?
I have just made my own program to encipher, using AES in counter mode, and have validated it using NIST data. So I know I have done it properly.
I have read that AES-CTR can produce a stream of ...
8
votes
1answer
712 views
How distinct are the meanings of the terms “CSPRNG,” “DRBG” and “stream cipher”?
Are there universal, consensus definitions for the following terms?
Cryptographically secure pseudo-random number generator ("CSPRNG")
Deterministic random bit generator ("DRBG")
Stream cipher
This ...
2
votes
2answers
193 views
How to contruct a pseudorandom with a specific property
How to construct a pseudorandom function $PRF$ with the following property:
Probability that $PRF(k_1,i)=PRF(k_2,i)$ is negligible, for all keys $k_1,k_2$ such that $k_1\neq k_2$
Does the PRF with ...
1
vote
1answer
158 views
Pseudorandom generator designs
When designing pseudorandom generators what should one consider? Here is an example pseudorandom generator $F^t : \{0,1\}^n \rightarrow \{0,1\}^{4n}$. I have no idea what it means, so what does it ...
7
votes
2answers
896 views
How fast does a pseudorandom number generator have to be in order to be competitive?
Let $\{x_n\}_{n}$ be the pseudorandom sequence produced by a cryptographically secure pseudorandom number generator $G$. What is the cost of computing a term in the sequence for a competitive ...
11
votes
2answers
1k views
What is the relation between the existence of a cryptographic hash function and the existence of a PRG?
Does the existence of a PRF/PRG/one way function imply the existence of a hash function? I did not find a proof of the existence of a cryptographic hash function, so I want to know whether it is based ...
10
votes
2answers
314 views
Which symmetric encryption systems, pseudorandom number generators, and hash functions are best suited for reversible computers?
Reversible computing refers to the type of computing where one minimizes the the amount of data to be deleted usually to save energy (Reversible computing could also thwart side-channel attacks). ...
6
votes
1answer
2k views
Are there some problems to use pseudo-random number generator in Smart Card?
A Smart Card is a kind of secure device, with limited storage capacity and
computational resource.
If we use a Pseudo-Random Number Generator to generate random numbers in a Smart Card, then is there ...
7
votes
1answer
1k views
Can it ever be impossible to invert a PRNG?
I've read about the possibility of inverting the Mersenne Twister after 624 numbers of output. 624 matches the state size of my implementation of the Twister. Coincidence? If the generator only ...
6
votes
1answer
521 views
Are pseudorandom permutation really permutation in mathematical sense?
In security, and specifically Block Cipher (AES, DES, etc), when we talk about pseudo random permutations, is the term "permutation" refer to the same meaning as in discrete mathematics. That is, the ...
4
votes
2answers
1k views
Given a pseudorandom function F, is $(F_k(r) \; | \; F_k(r + 1))$ also a PRF?
Given: F is a pseudorandom function, G is a pseudorandom generator with $l(n) = n+1$. The following schemes should be classified as being insecure, IND-COA secure, IND-CPA secure.
To encrypt $m \in \{...
2
votes
1answer
350 views
Is the XOR of PRGs sharing the same input a PRG?
I have question in learning PRG. Given that $f$ and $f_1$ are PRGs, both $\{0,1\}^n \to \{0,1\}^{2n}$.
Is $g(x) = f(x)$ xor $f_1(x)$ a PRG?
Someone told me that in this case, $g(x)$ is not a PRG, ...
6
votes
1answer
1k views
What weaknesses in Hash_DRBG did NIST find and fix?
Matthew Green states in the Practical Kleptography presentation (video, at about 12:15) that Hash_DRBG (from SP800-90A) as originally proposed by NSA had potentially exploitable flaws or bugs and that ...
6
votes
1answer
2k views
Fastest random number generator
I just read High performance physical random number generator by K.H. Tsoi, K.H. Leung and P.H.W. Leong. It proposes a physical RNG of speed 400 Mbps. Is this the fastest random number generator at ...
5
votes
1answer
3k views
Is the concatenation of PRG output still a PRG?
I am puzzled by the following question, since I am not very familiar with proof methods of Pseudo-Random Generators (I only know how to use the inequality from the PRG definition to prove or disprove, ...
4
votes
2answers
1k views
Is $G$ a secure PRG?
Is the following function a secure PRG?
Given $F$ is a secure PRG and $k$ is choosen random from key space $K$.
$$G(x) = F(k,x) \oplus F(k,x \oplus 1^s)$$
My solution is $x \oplus 1^s = x'$ ...
6
votes
1answer
665 views
Does ChaCha20-Poly1305 need random nonce?
RFC 7539 says:
A 96-bit nonce -- different for each invocation with the same key
It doesn't explicitly say whether it has to be random or not. If we use an ever incrementing counter. Would that be ...
5
votes
1answer
3k views
How can I prove/disprove that a construction yields a secure PRG?
Let $G:\{0,1\}^{*} \mapsto \{0,1\}^{*}$ be a secure PRG. Prove or disprove that the following construction also yields a secure PRG.
$$G'(k) = G(k||0),$$
where $||$ denotes the concatenation of two ...
4
votes
3answers
824 views
Is a function defined as PRF with a given key a PRG?
Let $G(s)=F_{0^n}(s)$ ($ 0^n $ is a fixed key given to the PRF F) for any $nā\mathbb{N}$ and $sā\{0,1\}^n$.
Is G, defined via PRF as above, necessarily a pseudorandom generator?
I presume that it is ...
3
votes
2answers
1k views
Why is the following RSA PRNG cryptographically secure?
One requirement states that the generator has to withstand the next-bit test.
Consider the following PRNG, where we calculate next output $x_i$ via the formula
$x_i = x_{i-1}^ e\mod n$.
I can see ...
3
votes
2answers
2k views
Why is ISAAC not a pseudo random number generator?
I have been accused of confusion over the nature of the ISAAC algorithm. The bulk of evidence suggests that it is a cryptographically strong pseudo random number generator. By bulk I mean the number ...
2
votes
1answer
226 views
A confusion on the proof of Yao's theorem (Yao 82)
I'm reading the proof of Yao's theorem on Boaz Barak's lecture, the main part of the proof is the following claim:
My question is:
How can we say "without loss of generality" here? Since $H^i$ ...
2
votes
1answer
325 views
Cryptography Pseudo Random Generator example question - proof
For ii) G2 was proven to be a PRG, and it seems the solution for G5 uses G2.
Can someone try and explain to me the solution that I was given? I specially do not understand how to calculate the given ...
2
votes
1answer
1k views
Is every pseudorandom generator a one way function?
$$\{G:\{0,1\}^n\rightarrow\{0,1\}^{2n+1}\}^\infty_{n=1}$$
If above function is a pseudorandom generator then is the same $G$ a one way function. I tried to prove this but failed a lot of time. Would ...
2
votes
1answer
389 views
ARC4random ā ChaCha-based LibreSSL PRG
Here is arc4random.c from the LibreSSL pseudorandom generator as used in OpenBSD.
It works as follows:
Take 40 "truly random" bytes from OS (PRG seed);
Use the seed as key and IV to generate 1024 ...
2
votes
2answers
342 views
Collision-resistant Pseudorandom function
Assume we have a pseudorandom function: PRF(.)
We want the following property holds with a high probability:
$\forall i, 0\leq i \leq n: PRF(k_1, i)\neq PRF(k_2,i)$
where $k_1$ and $k_2$ are two ...
2
votes
1answer
149 views
Formal definition PRNG
I tried to look for a book that presents cryptographic concepts(specially PRNG) in a formal way but what I find is an intuitive approach. So my question is what is the formal definition of Psuedo-...
2
votes
2answers
297 views
Creating a k bit random string
My goal is to create a random $k$ bit string. My question can be divided in two parts.
If a $n$ bit string $s$ is computationally indistinguishable from a random $n$ bit string, can we say that the ...
1
vote
1answer
53 views
PRG exponential expansion
I am just beginning to read into pseudorandom generators and I came across this definition for a PRG:
$G_n : \{0,1\}^n \rightarrow \{0,1\}^{l(n)}, \quad \text{ where $l(n)$ is a polynomial}$
Is there ...
1
vote
1answer
49 views
How to calculate CPA attack complexity in bits manipulation
The following Forward Errors Correcting FEC is used in our daily devices. But I added a potential security measure.
In one of FEC systems the input is $K$ bits and the output code is $M$ bits where $M=...
1
vote
1answer
740 views
is the XOR of PRG outputs a PRG?
I am going through the course http://u.cs.biu.ac.il/~lindell/89-856/main-89-856.html, as it has a good lecture notes. I found exercise 2 solution a puzzling statement: it says that $G^\prime (x_1 , ...
1
vote
1answer
627 views
Prove there is PRG that is not necessarily one-to-one
We assume that there is at least one PRG .Now prove there is a PRG like $G:\{0,1\}^{n} \rightarrow \{0,1\}^{l(n)} $ such that it is not necessarily one-to-one.
1
vote
4answers
238 views
Why does mt19937 fail the universal test in NIST SP 800-22?
Update: with the help of @SqueamishOssifrage and @PaulUzdak, we discovered that my NIST SP 800-22 has a broken universal test. So this becomes a moot question.
Check this report. It seems to sail ...
0
votes
1answer
545 views
Katz/Lindell Problem 7.6
Let $f$ be a length-preserving one-way function, and let $\text{hc}$ be a hard-core predicate of $f$. Define $G$ as $G(x)=f(x)\|\text{hc}(x)$. Is $G$ necessarily a pseudorandom generator?
The answer ...
-1
votes
2answers
759 views
Are there problems with short pseudo-random mid-square-like sequences?
To improve "mid-square pseudo-random number generation" in generating one million pseudo-random 128-bit
numbers from a 128-bit truly-random seed, I am taking the xor of the mid-square with the ...
-1
votes
1answer
100 views
PRG Theory Design
PRG theory design is something of interest to me at the moment in the security of cryptography.
I am interested in learning how to come with PRGs for random functions such as $\{0,1\}^{2n} \...
