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.
336
questions
8
votes
2answers
692 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
177 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
26 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
172 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
64 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
68 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
234 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
132 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
35 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
66 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
131 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
45 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
67 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 ...
0
votes
1answer
59 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
44 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
118 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
48 views
2
votes
1answer
69 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
110 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
95 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
123 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
39 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$ ...
3
votes
2answers
94 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
71 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
40 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
96 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
107 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
305 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
53 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
268 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
77 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
86 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 ...
3
votes
2answers
107 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 ...
1
vote
0answers
65 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-...
1
vote
1answer
116 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?
2
votes
1answer
77 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 ...
2
votes
1answer
122 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 ...
2
votes
2answers
109 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'...
3
votes
2answers
99 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 ...
0
votes
1answer
61 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)?
0
votes
1answer
41 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 ...
2
votes
1answer
91 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-...
1
vote
0answers
249 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 ...
0
votes
1answer
315 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 ...
3
votes
1answer
361 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$ ...
1
vote
0answers
186 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 ...
6
votes
2answers
2k 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 ...
1
vote
1answer
105 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 ...
