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.

Filter by
Sorted by
Tagged with
27
votes
4answers
23k 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 ...
-2
votes
2answers
545 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 ...
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?
25
votes
6answers
10k 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 ...
13
votes
1answer
591 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 ...
8
votes
3answers
4k 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
561 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
1answer
78 views

Building Key Streams from PRNGs

I am reading an intro book about cryptography and the author tries to explain why using pseudo random number generators is vulnerable. Given PRNG equation; \begin{align} S_0 &= \text{seed}\\ S_{...
2
votes
2answers
182 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
144 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
819 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
305 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). ...
5
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
956 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 ...
2
votes
1answer
265 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 ...
5
votes
1answer
431 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 ...
5
votes
1answer
2k 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
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 ...
4
votes
2answers
982 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'$ ...
3
votes
2answers
847 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 \{...
4
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 ...
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
1k 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
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
199 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
349 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
271 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
2answers
281 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 ...
2
votes
1answer
230 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 ...
1
vote
3answers
128 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 ...
1
vote
1answer
523 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
1answer
594 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 , ...
0
votes
1answer
418 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
1answer
90 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} \...
-1
votes
2answers
622 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 ...