# 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.

370 questions
Filter by
Sorted by
Tagged with
167 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 ...
52 views

87 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_{...
15 views

### Building Key Streams from PRNGs [duplicate]

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; ...
176 views

### Pseudo Random Generator (PRG) not deterministic

Usually a Pseudo Random Generator is supposed to be IND-CPA secure. But apparently, it is not in some cases such as the following: A PseudoRandom Generator $G$ has expansion factor $n + 2$. Encrypt ...
116 views

### What is the most secure/reliable CSPRNG currently available? [closed]

In terms of period length, uniformity/distribution, what is the most secure/reliable CSPRNG currently available?
141 views

### Is there something wrong with using a hash function as a PRG?

I need to create cryptographically secure pseudorandomness in JavaScript. However, when I googled for PRGs, all I found was very sketchy. My idea is as follows (in pseudocode): ...
44 views

### Output a pad (un-keyed, variable length) from an input seed (fixed value for same seed)

I want a function $y = f(x, len)$: $x$ is the seed. $y$ is the output. $len \in \mathbb{Z^+}$ is the length (bytes) of $y$ Select a seed string $x$ to generate a string $y$. For each same pair of $x$ ...
103 views

### Are there any practical differences between running a PRNG on a subset of bits from an RNG compared to running the RNG?

Given an RNG and a PRNG. We define RNG(k) to mean that the RNG produces k random bits. We define PRNG(k, seed) to mean that the PRNG uses seed to produce k pseudo-...
80 views

### Dependence of a Pseudorandom Function's Security on its Input/Output Spaces

Let $n$ be a security parameter and $F:\{0,1\}^{\ell_{key}(n)} \times \{0,1\}^{\ell_{in}(n)} \rightarrow \{0,1\}^{\ell_{out}(n)}$ be a keyed function which forms a family of Pseudorandom Functions (...
46 views

### Are there any signature algorithms with pseudorandom signatures?

As the title says. My reference point for the "pseudorandom ciphertext" concept is this paper by Möller, which introduces a public-key encryption algorithm with this property. I want to know the ...
131 views

### A hash-based pseudorandom function

Let $H()$ be a cryptographic hash function. Question: Can we consider $c= H(r||i)$ as a pseudorandom value, where $i$ is a public value, $1\leq i\leq n$, and $r$ is a large uniformly random value/...
190 views

### Interpretation of certain results of NIST Test Suite

I am using NIST Test suite on a PRNG and have a confusion regarding some specific results. Following is the part of the results: ...
330 views

### Can future Bitcoin hashes be considered a good source to generate random numbers?

There are a lot of miners trying to calculate the next valid SHA-256 hash using random strings, so can I consider that generated hashes have good randomness? How can I prove it? For example, use the ...
59 views

### How to shuffle a number between a range in a reversible manner

I have to generate identification number plates from a database ID. These ID are composed of three letters and three numbers e.g. BAC 212, I already have a function ...
425 views

### Alternatives to Mersenne Twister

We have Mersenne Twister pseudorandom number generator. It has several variants, CryptMT among them, that is of cryptographic grade. There are alternatives to Mersenne Twister, like Xorshift or ...
95 views

### How does changing input size affect The Goldreich-Goldwasser-Micali Construction?

If we want to construct a PRF that is length preserving, it is easy to show with hybrid proof that the resulting construction is a PRF. But what happens when we have longer input. Supose that the ...
109 views

### Construction PRF from PRG

As discussed here, a classic and secure construction of PRF from PRG is: $F_k(x_1x_2\cdots x_n) = G_{x_n}(\cdots(G_{x_2}(G_{x_1}(k)))\cdots)$ where $G$ is a secure pseudorandom generator. I was ...
144 views

### Does a regularly reseeded PRNG provide backtracking resistance?

I'm currently discussing a security topic with some of my classmates. A cryptographic PRNG typically provides backtracking resistance if an adversary that compromises the internal PRNG state cannot ...
79 views

### Simple but secure hand cipher for a computerless world [closed]

this is my first time posting here, so please be gentle! As may be obvious, I'm an amateur who knows very little cryptanalysis. The goal I've been playing around trying to make a simple but strong-...
259 views

### Why is LCG PRNG chosen to be as c++ rand() function?

The C++ rand() function is an Linear Congruential Generator (LCG) PRNG. my questions are: Why was this algorithm chosen? What are the pros and cons? Is it good for cryptography?
125 views

### How to symmetrically encrypt 64bit values?

I'm curious about an algorithm that would be good for the following scenario: 32-bit "plaintext" input, taken from a counter 32 or 64-bit "ciphertext" output It should be possible to decrypt the ...
132 views

### Constructions of PRF (Pseudo Random Function)

I was taught only GGM based PRF construction in class. It's very inefficient. I am just curious about various PRF constructions from standard assumptions. Please provide a few PRF constructions from ...
172 views

### Meaning of epsilon in proving a PRG is predictable/ un predictable

I am quite confused, I have been following a course on crypto provided by Dan Boneh, this is the lecture I am confused with - https://www.youtube.com/watch?v=EjWap3szsPk time stamp 8:58 - 11:00 I don'...
117 views

### How to make a hypothesis test for a simple statistical test for a certain RNG?

I'm self-studying about hypothesis test in the context of RNGs. I'm building a hypothesis test from scratch. I'm taking the simplest statistical test I can think of: how many $1$s are there in the ...
85 views

### What SALT value will be used in HKDF_EXTRACT in TLS1.3?

What SALT value will be used in HKDF_EXTRACT while generating the Handshake Secret (when there will not be any PSK)?
45 views

### Showing the non-pseudorandomness of a generator

I'm sorry if this question is too novice. It comes from a practice midterm in a cryptography course which I'm taking, and my confusion here is really that I don't know the "tools" that one uses in ...
114 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-...
447 views

### Which 'info' and 'salt' parameters to use in HKDF for TLS 1.3?

all the following discussion is for HKDF in TLS1.3: Regarding the 'salt' parameter in - HKDF-Extract(salt, IKM) as written in RFC 5869: HKDF without having to protect the secrecy of the salt. In ...
459 views

### How many bits are needed for an LFSR to generate a specific number of sequences?

I need to generate 64-bit data sequences 16 times pseudorandomly. How many bits should the linear-feedback shift register (LFSR) have in order to do so? That is, what is the number of bits for the ...
577 views

### Golomb's Randomness postulates

In Handbook of applied cryptography, Golomb's randomness postulates are given: Let $s$ be a periodic sequence of period $N$. Golomb’s randomness postulates are the following. R1: In the cycle $s_N$ ...
245 views

### show that G' is not a secure PRG even if G is

Hello I'm trying to show that the function G'(s) = G(s) || G(G(s)) is not a secure PRG even if G is. My first question is that in this case, how do I know what G ...
4k views

### Using a hash function as a random number generator

Using MD5 or SHA1 for instance, and applying integers (as seed so to speak) to the hash function, in sequence, and only keeping, say, the first 64 bits of the resulting hash, do we always have a ...
123 views

### A modification of the Blum-Micalli construction

Consider the following modification of the Blum-Micalli construction (denoted by BM): $G_l(x) = f^l(x) || BM^l(x)$ I am asked the following questions about it: Show it is a PRG of fixed stretch ...
587 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 ...
39 views

152 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 ...
72 views

### PRGs exist if computationally secret encryption schemes exist

I have understood the "equivalences" between PRP, PRF and PRG. Now, I just read an statement in my lecture notes that made me think that there has to be a conversion between PRG and computationally ...
147 views

### $G_f(x) = x \|f(x)$ is not a PRG with $\operatorname{DPT}$-computable function $f$

Let $f:\{0,1\}^* \rightarrow \{0,1\}$ be any $\operatorname{DPT}$-computable function. Show that $G_f(x) = x \|f(x)$ is not a PRG. Can anyone help me on understand how to prove this?
257 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 ...
This is Pierre L'Ecuyer's PRNG. I know its period is $2^{191}$, but I don't know what is its internal state size. What is it?
Consider the following oracle-based game: $O_0$: Init: $1^n$; Query: output $y \stackrel{u}{\in} \{0,1\}^{l(n)}$ $O_1$: Init: $1^n$; Query: output $G(x)$ with \$x \stackrel{u}{\in} \{0,1\}^{n}...