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.
317
questions
0
votes
1answer
70 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
2answers
68 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?
-2
votes
0answers
54 views
How can I make Math.random more secure? [duplicate]
Since Math.random() is highly insecure, and it isn't cryptographically secure, how can I make it a bit more secure?
I know that ...
1
vote
2answers
110 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
84 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
65 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
36 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
85 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
60 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
292 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
48 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
147 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
55 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
58 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
93 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
56 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
72 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
71 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
98 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
85 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
93 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
54 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
40 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
88 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
149 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
191 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
242 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
151 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 ...
7
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
89 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 ...
6
votes
1answer
340 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 ...
1
vote
0answers
33 views
Pseudorandomness based on homomorphic multiplication property of Paillier cryptosystem
Given the instance $(n, g, \lambda)$ of Paillier cryptosystem with $\text{ord}(g) = n \lambda$ (symbols have their usual meaning), and $c = g^{na}$, is it possible to distinguish (computationally) $c' ...
18
votes
4answers
4k views
Using Tweets as a Random seed
I would like to start by saying I know nothing about Cryptography and was reading up on how to choose a random seed and this link is something that I found. What I basically understood that the seed ...
1
vote
1answer
88 views
Is this MAC correct and secure?
Let $m \in \{0, 1\}^{2n} = m_1 || m_2$. Let's also assume that $F_k$ is a PRF and $G$ is a PRG defined as $G: \{0, 1\}^n \rightarrow \{0, 1\}^n$. Now, Let's define the $MAC$ scheme as follows:
$$MAC(...
2
votes
1answer
214 views
Is PRG On Concatenation of Input a PRG
This is a homework assignment, so I'm not expecting full solutions, just general guidance.
Let a PRG $G:\left\{ 0,1\right\} ^{n}\to\left\{ 0,1\right\} ^{l\left(n\right)}$ (where $l\left(n\right)$ ...
1
vote
0answers
75 views
Indistinguishable encryptions and CPA-secure example
Let $ F $ be a PRF and $ G$ be a PRG with expansion factor $n \to n +1 $ For the following encryption scheme, decide whether it has indistinguishable encryptions and whether it is CPA-secure.
...
1
vote
0answers
90 views
Never design your own crypto…how to design a PRG
As a new learner of cryptography I have learnt from online tutorials and lectures not to design your own crypto.
What I am trying to understand is the fundamental to designing PRGs to a given context ...
1
vote
0answers
105 views
Calculating t and epsilon for a computationally indistinguishable pseudo random generator
I have a PRG $G : \{0, 1\}^n \rightarrow \{0, 1\}^{2n}$.
How would you go about calculating the optimal size of $n$ given that you have
$$\epsilon = \cfrac{1}{2^{80}}$$
and, $t = 2$ years for a ...
3
votes
1answer
209 views
Stronger security definition of PRG
By the standard security definition of a Pseudo Random Generator, if $G$ is a PRG, then $G'$ such that $G'(0\mathbin\|x)=0\mathbin\|G(x)$ and $G'(1\mathbin\|x)=1\mathbin\|G(x)$ is a PRG. We can build ...
-1
votes
1answer
79 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
vote
1answer
135 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 ...
0
votes
1answer
60 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 ...
1
vote
0answers
134 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?
2
votes
1answer
148 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 ...
2
votes
1answer
62 views
What's the internal state size and output range of mrg32k3a?
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?
0
votes
0answers
84 views
Oracle version of the IND-PRG game with q queries
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}...
3
votes
0answers
170 views
Can we construct a PRF directly from a one way permutation function?
In Introduction to Modern Cryptography first a pseudo random generator (PRG) is constructed from a one way function (OWF). After that the PRG is used to to construct pseudorandom functions (PRF). Is ...
2
votes
2answers
1k views
Is this test result sufficient to steer clear from this RNG for cryptographic applications?
I'm not really interested in this PRNG. I'm more interested in understanding what it takes to fail the security threshold for cryptographic applications. I'm taking the C PRNG as an example.
...
0
votes
2answers
143 views
Blockchain cryptography
I'm a high school student doing a project about blockchain. I'm trying to figure out why hashing algorithms are crucial for the existence of blockchain and other types of cryptography wouldn't work. ...
