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.
369
questions
2
votes
0answers
31 views
RNG and Mersenne twister learning resources for the amateur
I am a complete amateur in the area of random number generators. I would appreciate resources to begin learning.
Also I would also like to learn about Mersenne twister. Resources that are easy on the ...
1
vote
1answer
52 views
Is it possible to create a 128-bit UUID from a weak entropy source?
I am looking at a seemingly popular piece of JavaScript code to generate a UUID which is supposed to be a 128-bit number:
...
1
vote
0answers
46 views
Is $f(g)$ a PRG if $f$ is a OWF and $g$ a PRG?
If we have a PRG $g$ and a OWF $f$, can we say that $g' = f(g)$ is a PRG?
And what if $g$ stretches its input by a factor of 2?
2
votes
1answer
77 views
Breaking a Mersenne-twister RNG with unsequential outputs
Pardon me for this newbie-ish question. I'm still a novice in cryptography . I have an application that outputs random numbers from 0 - 12 (endpoints inclusive) unsequentially (some outputs are thrown ...
0
votes
2answers
85 views
How to construct a prg?
Does the adversary know the random seed s? If he does not, isn't one possible construction simply the random seed itself? if the output needs to be bigger than random seed s cant I just add a hardcore ...
0
votes
1answer
74 views
How many 12 bit integers output are required to reverse the Mersenne Twister?
I am creating a web app that applies Python's random algorithm (Mersenne Twister) to generate random 12-bit integers. I am concerned as to how a user can predict ...
0
votes
1answer
75 views
Would knowing the random seed help to break AES or similar?
Consider I knew the seed of the random number generator that Bob uses to send encrypted emails to Alice. Would I have an advantage in deciphering the message? Also, how does, for example, openssl ...
0
votes
1answer
54 views
Stretching definition of pseudo random number generator
I am wondering if someone can say if the following qualifies as a PRNG. Input a random bit seed of length $n$ into the generator, and over $k$ steps the generator uses $k$ publicly known integers to ...
1
vote
1answer
44 views
One-time pad with public key changes
Let $k$ by a randomly generated $n$ bit string, and $m$ a $n$ bit message. Then putting $c = m \oplus k$ is the one-time pad and is perfectly secure. Now assume the transmitter and receiver wanted ...
0
votes
0answers
27 views
When will the random bit sequence start to repeat in pseudo random number generator
Let's say we have the Blum-Micali pseudorandom number generator.
from wikipedia:
Let $p$ be an odd prime, and let $g$ be a primitive root modulo $p$.
Let $x_0$ be a seed, and let $x_{i+1} = g^{x_i}\ ...
0
votes
1answer
52 views
Attacks on LCG with “self-XOR” output function?
Consider an ordinary LCG modulo $2^n$ with an internal state of $n$ bits and an output of $n/2$ bits, with the twist that instead of simply truncating the state to produce an output, we take the upper ...
0
votes
0answers
42 views
Is it possible to compute permutations of a sequence of bytes by using exactly one pseudo-random number?
Suppose I have a certain sequence of bytes, for example 0102F4829hex, and I can pick from a pseudo-random number generator exactly one number.
Is it possible, by using exactly one pseudo-random number ...
2
votes
3answers
131 views
How to derive a passphrase from a hash?
I'd like to generate a passphrase derived from a hash fingerprint. The passphrase consists of short and human-pronounceable words from a phonetically-distinct wordlist. The derivation is a one-way ...
0
votes
1answer
22 views
PRNG with onto state update function
Consider a (hypothetical) PRNG where the state update function is onto, but it is easy to find the set of preimages (so not one-way). That is, if an attacker is given the internal state of the system,...
1
vote
1answer
86 views
Construct a specific length-doubling pseudorandom generator from a length-doubling pseudorandom
Let $G$ be a length-doubling pseudorandom generator (i.e., for any $n\in \mathbb{N}$ and for
any $s\in\{0, 1\}^n$ it holds that $G(s)\in\{0, 1\}^{2n}$). Can you construct a length-doubling ...
2
votes
2answers
55 views
Proper method of writing pseudo random sequences into binary files?
I am working in Python and created a B.B.S. implementation that outputs a sequence of pseudo random positive integers into a Python list. I would like to write this data to a binary file and pass it ...
2
votes
2answers
89 views
Does cryptographically-secure pseudo random generators require a secure seed?
For any cryptographically-secure pseudo random generators, do we need a secure random seed for those?
If the seed is predictable, then everything is broken due to the deterministic propetry of the ...
0
votes
1answer
35 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 ...
18
votes
2answers
4k 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 ...
3
votes
1answer
77 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
26 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
365 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
20 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
35 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
72 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
87 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
64 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
212 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
111 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
133 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
22 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
45 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
241 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
746 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
182 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
35 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
214 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
70 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
76 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
47 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 Lemma ...
4
votes
2answers
268 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
159 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
49 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
100 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
390 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
54 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
69 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
108 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
87 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
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 ...
