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
0
votes
0answers
16 views

Proving uniform output of CSPRNG

I have a question concerning the paper by Blum, Blum, and Shub introducing the $x^2 \mod N$ Generator. It is clear that the outputs of the generator pass statistical tests for randomness: the larger ...
4
votes
2answers
210 views

A website that identifies an RNG from its output

This happened during a discussion of RNG entropy, and the difficulty of verifying the level of entropy in a long sequence of bits (e.g. a private key.) A colleague of mine told me about a website ...
2
votes
1answer
31 views

CSPRNG Unique Seeds

Are there conditions on the definition of cryptographically secure pseudo random number generators that require distinct seeds to generate distinct (periodic) sequences? What if a generator has the ...
1
vote
0answers
23 views

CSPRNG unique seeds and proving uniform output [closed]

I have two related questions concerning cryptographically secure pseudo random number generators. My first question is as follows: are there conditions on the definition of cryptographically secure ...
1
vote
1answer
338 views

Prove that function G is not a pseudo-random generator

I'm trying to do the following assignment: Let $G:\{0,1\}^n \rightarrow \{0,1\}^{n+1}$ and $G':\{0,1\}^n \rightarrow \{0,1\}^{n+2}$ be two pseudorandom generators. Prove that the function $G'':\{...
0
votes
0answers
15 views

How to save an encryption key to a binary file to be used in NIST STS

I wrote a simple logistics function that i use for my pesudo random number generator.I want to test it's randomness so i downloaded a custom windows version of NIST STS. the program rqeuires you to ...
0
votes
0answers
30 views

Any formal proof or reference that pseudorandom permutation can be used as pseudorandom function

Assume that a DRBG passes all statistical tests. We use that DRBG to shuffle(Fisher-Yates) an array that contains $\{0,1,\ldots,2^n-1\}$. Now get a pseudorandom permutation $\{0,1\}^n\rightarrow \{0,1\...
2
votes
1answer
64 views

Understanding definition of secure pseudo random number generator

From my reading, a secure pseudo random number generator is called secure if, given a sequence of numbers generated by the PRNG, then if any one of those numbers from the sequence is removed an ...
2
votes
1answer
80 views

Mathematical proof or any reference of “Deterministic random bit generator cannot produce more randomness than the randomness of seed”

The heading tells everything. Any proof or any kind of reference is welcome regarding this: Can we get more randomness from a deterministic random bit generator than the entropy that we feed to the ...
3
votes
1answer
57 views

Can the input to a one way function be pseudorandom?

I know that normally a one-way function takes in a completely random input, but can a one-way function take in something pseudorandom instead of completely random? Will it still be a one-way function? ...
3
votes
1answer
157 views

Is this a PRF? Fk(x) = G(k⊕x) where G is a PRG

This is not homework, but a random thought. Let $G(x)$ be a PRG. We define the following function: $$F_k(x) = G(k\oplus x)$$ My intuition is that it shouldn't be a PRF but I couldn't come with an ...
0
votes
3answers
96 views

Is a PRG concatenation using the same input still a PRG?

Suppose we have a secure PRG $G: \{0,1\}^s→ \{0,1\}^n$ and we define a $G'(k)$ as: $$ G'(k) = G(k) \| G(k) $$ So if $G(k)=\mathbf{i}$, $G'(k) = \mathbf{i} \| \mathbf{i}$ Is $G'$ still a secure PRG? ...
4
votes
1answer
126 views

Is this a prg: G'(x) = G(x) ⊕ (x || 0^(l(|x|)-|x|))

This is not homework, but a question from an exam. Let $G(x)$ be a PRG with expansion parameter $\ell(n)$. $$G'(x) = G(x) \oplus (x \mathbin\| 0^{\ell(|x|)-|x|})$$ where $\ell(|x|) = |G(x)|$ My ...
0
votes
0answers
20 views

safe concating PRP and PRG

Suppose it is necessary to build a safe PRG. You have one PRP with $\epsilon = \frac{1}{2} ^ {45}$, and one PRF with $\epsilon = \frac{1}{2} ^ {55}$. There is no mathematical relationship in the PRP ...
1
vote
0answers
36 views

Would the result of encrypting weak random data via AES-128 with a CSPRNG-generated key be considered strong/secure random data?

I am trying to understand the security implications of using a well known block (or stream but in this example block) cipher like AES-128 to produce pseudo-random data. My specific question is would ...
4
votes
1answer
163 views

Reverse Java random seed using 81 calls to nextInt with a bound of 4?

I'm trying to reverse the Java random seed using 81 calls to nextInt(bound) with a bound of 4. I am wondering if it is at all ...
8
votes
2answers
716 views

Perfect shuffle possible with limited raw entropy?

I am trying to shuffle a standard 52-card deck in a perfect way (every outcome should be possible at an equal chance). I am not, at this point, concerned with cryptanalysis attacks against it. I have ...
0
votes
1answer
179 views

Is there a method to encrypt relations in between values of a cyclic value set and generate values out of this set with pseudo RNG? (all at user PC)

Is there a pseudo RNG and function $f$ with 1.) The RNG produces a value $v_0$ out of $N$ different values (set $S$). 2.) Independent of the RNG the function $f$ generates $v_{i+1}=f(v_i)$ ...
0
votes
0answers
29 views

How are implementations of PRF and PRG via AES-CTR different?

I heard that AES-CTR can be used for implementation of PRF and PRG. What is the difference between these implementations?
2
votes
1answer
181 views

Is 1D Perlin noise cryptographically secure

As the title, if I have: A stream of 1D noise And I know: The noise is generated using the Perlin method with a known number of octaves > 1. (as implemented here) The random numbers used in each ...
1
vote
1answer
66 views

Do 'nonsequential' PRNGs exist?

It is my understanding that PRNGs typically use a seed and can then generate random values one after the other. This is what I mean by being 'sequential'. How about a PRNG which allows me to retrieve ...
2
votes
0answers
71 views

How many bits of cryptographic security do these XOR Mid-Square random numbers have?

This pseudo-random number generator uses only XOR and Mid-Square operations: Get one secret 128-bit truly random seed $R_0$ Generate a million secret $R_j$ by the recurrences (for $1\le j\le 1000000$)...
0
votes
1answer
46 views

Question about a proof in Junod's paper about the Blum-Blum-Shub generator

I am reading Junod's paper about the Blum-Blum-Shub generator. There is one thing I just do not understand about his proof of Lemma 4. On page 17 he writes: We conclude that $x=-x_0$ and from ...
4
votes
2answers
246 views

What are usable entropy sources in a headless machine without /dev/random or any cryptography API?

If I have a headless machine (no mouse movements, no keyboard presses, or user input), without any cryptography CSPRNG APIs, where can I collect entropy from?
4
votes
1answer
154 views

Necessary conditions for construction of $n$ to $p(n)$ pseudorandom generators from $n$ to $n+1$ generators?

Given a polynomial time deterministic algorithm $G_1:\{0,1\}^n \rightarrow \{0,1\}^{n+1}$, consider the function $G:\{0,1\}^n \rightarrow \{0,1\}^{p(n)}$ constructed as follows: Let $s \in \{0,1\}^n$ ...
1
vote
0answers
45 views

Alternative AES key expansion for CTR based random number generator

Daniel J. Bernstein proposes an alternative to NIST AES-CTR based deterministic random number generator (AES-CTR-DRBG). Instead of a less performant complex construction, he uses an standard AES-CRT ...
0
votes
1answer
75 views

How to use SHA-1 as a PRNG?

Is there any special parameters for using SHA-1 for generating pseudo-random numbers? What are the differences between SHA-1 as a PRNG and original SHA-1?
1
vote
2answers
193 views

What is the difference between pseudorandom permutation/pseudorandom function/block cipher?

What is the difference between; pseudorandom permutation pseudorandom function block cipher? Very confused with the 3 terms and I am not good at advanced math. Can someone explain in plain word?
3
votes
1answer
51 views

Is it possible to sample HE ciphertexts using pseudo-random generator?

I'm trying to sample HE ciphertexts which serve as ciphertexts encrypting some random values. I have realized a example program using Microsoft SEAL, which implements a variant of BFV scheme. ...
1
vote
1answer
68 views

Is a bit string pseudorandom if it starts with predictable bits?

Assume we have $k = n + m$ bits string $S$ where the first $n$ bits are predictable, and the last $m$ bits are pseudorandom (the HMAC of the first $n$ bits + IV). Can we say $S$ is a pseudorandom ...
1
vote
1answer
81 views

Question about the Proof of “Pseudorandom generators imply one-way functions” in “Foundations of Cryptography”

In "Foundations of Cryptography, Volume 1" by Oded Goldreich, chapter 3.3.6 states the following theorem: Let $G$ be a pseudorandom generator with expansion factor $l(n) = 2n$. Then the function $f\...
0
votes
1answer
77 views

What PRG expansion factors are safe?

I'm trying to better understand the "cost" of randomness usage/generation in practice. I understand that generally, some (small) amount of "true" randomness is generated, and then a CSPRNG is applied ...
1
vote
3answers
140 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
votes
1answer
49 views

Please help with this question [closed]

Please help with this question.
2
votes
1answer
80 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_{...
0
votes
0answers
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; ...
0
votes
1answer
145 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 ...
1
vote
1answer
104 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?
1
vote
2answers
128 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): ...
0
votes
1answer
40 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$ ...
2
votes
2answers
95 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-...
1
vote
0answers
76 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 (...
1
vote
1answer
43 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 ...
4
votes
1answer
106 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/...
1
vote
1answer
141 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: ...
4
votes
1answer
313 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 ...
0
votes
0answers
57 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 ...
1
vote
2answers
327 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 ...
2
votes
1answer
83 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 ...
1
vote
0answers
101 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 ...

1
2 3 4 5
8