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.
3
votes
2answers
74 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 ...
-1
votes
0answers
31 views
What do you mean when we say that a pseudorandom number generator is cryptographically secure? [duplicate]
I didn't get any good answers for this question
0
votes
1answer
39 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
36 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
78 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
81 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
0answers
73 views
How many bits needed for the LFSR to generate a specific number of sequences
I need to generate 64bit data sequences for 16 times pseudo randomly. How many bits should the linear feedback shift register have to be able to do so? I mean what is the number of bits for the ...
3
votes
1answer
122 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
103 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
966 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
80 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 ...
5
votes
1answer
229 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
31 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
75 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
137 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
56 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
88 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
101 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
198 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
76 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
128 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
56 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
59 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
132 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
48 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
83 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
109 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
132 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. ...
2
votes
2answers
205 views
Does there exist a CSPRNG that does not require generating prime numbers, but also does not depend on any other cryptographic primitives?
The following excerpt is taken from the “Cryptographically secure pseudorandom number generator” article on Wikipedia:
CSPRNG designs are divided into three classes:
those based on ...
2
votes
1answer
113 views
Making PRNG cryptographically secure thru shuffling?
Is it practical to make a PRNG cryptographically secure if I shuffle the randomly generated numbers (say 256-bit) several times before hashing it, even if a hacker knows when I generate the numbers?
...
2
votes
1answer
132 views
Problems understanding the applications of pseudo random number generators
I am trying to explore different methods used to generate pseudo-random numbers for my project in maths and I would be very grateful for some help or references to valuable sources as it is very hard ...
6
votes
1answer
746 views
What does “seed” mean in cryptography?
I have come across "seed" many times, and at each time, it confuses me more and more. I think it has a well-known meaning in cryptography, so what is it?
They can usually use the limited number of ...
1
vote
1answer
46 views
Instead of sending a set of random values, send a key for a PRF
Some Protocols require one party to send $n$ random challenges (or random values) to another party. For communication efficiency purpose, one can pick a random key for a pseudorandom function, and ...
-1
votes
1answer
96 views
Can there be a PRG $G(x)$ where at most half the output bits are 1?
Can there exist a pseduorandom generator, $G(x)$, with input length $|x|=n$ and output length $|G(x)|=2n$, where $\leq n$ bits of $G(x)$ are equal to 1 for every possible input $x$? (I.e. no more than ...
-1
votes
1answer
224 views
If $G$ is a PRG, is $F(s)=G(S)||G(\bar{s})$ necessarily a PRG?
Let $G$ be a pseudorandom generator, and $F(s)=G(s)||G(\bar{s})$ (where $\bar{s}$ denotes the bitwise complement of $s$), is $F$ necessarily a PRG?
My intuition says that it is a PRG, as clearly $G(s)...
3
votes
1answer
272 views
Attack of the Middle Square Weyl Sequence PRNG
The Middle Square Weyl Sequence PRNG was proposed as illustration of properties of CSPRNGs in this answer (now deleted). This PRNG was introduced (without claim of cryptographic security) by Bernard ...
7
votes
2answers
764 views
How fast does a pseudorandom number generator have to be in order to be competitive?
Let $\{x_n\}_{n}$ be the pseudorandom sequence produced by a cryptographically secure pseudorandom number generator $G$. What is the cost of computing a term in the sequence for a competitive ...
1
vote
1answer
86 views
Pseudo-random generators and pitfalls
I've read the Chapter "Randomness" from the Serious Cryptography book and it raised some questions. Namely:
It is written that Mersenne Twister is proved to be cryptographically irreliable. And that ...
0
votes
1answer
117 views
Does hashing a PRNG by a cryptographically secure hashing algorithm result in a CSPRNG?
Or specifically, does ChaCha20 hashing of the xoroshiro128+ random number generator result in a cryptographically secure random number generator?
4
votes
1answer
286 views
Is a one-way function pseudorandom?
For one-way function $f$ I understand that $g(x)=0^{n}\mathbin\|f(x)$ is a one- way function with respect to $2n$, where there is $n$ bits of $0$ in the beginning and the output of $f$ in the second ...
1
vote
0answers
54 views
Mersenne Twister's vulnerabilty with small-size distributions
C++ rookie here, trying to wrap his head around (CS)PRNGs.
I (assume that I) already understand the concept of the Mersenne Twister being "broken" (i.e. not cryptographically secure) due to its ...
2
votes
1answer
170 views
Is the XOR of PRGs sharing the same input a PRG?
I have question in learning PRG. Given that $f$ and $f_1$ are PRGs, both $\{0,1\}^n \to \{0,1\}^{2n}$.
Is $g(x) = f(x)$ xor $f_1(x)$ a PRG?
Someone told me that in this case, $g(x)$ is not a PRG, ...
0
votes
1answer
104 views
Oblivious Encryption: Oblivious Transfer Based Encryption
I’m aware of a couple of OT protocols, most of which use Public Key Cryptography, Key Establishment (or similar constructs) as the base. I don’t really have specific knowledge on other OT protocols, ...
2
votes
1answer
265 views
PRNG with a truly random seed?
PRNG (Wikipedia):
"The PRNG-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG's seed (which may include truly random values)."
My ...
3
votes
2answers
124 views
Inversive Congruential Generator
The inversive congruential generator over the prime field $k=Z/pZ$ is given by the iterations of the map $x\mapsto a/x+b$ if $x\neq 0$ or $b$ if $x=0$.
One can choose $a,b$ in $k$ such that the orbit ...
1
vote
2answers
292 views
How is a ciphertext encrypted using random numbers decrypted using a symmetric key algorithm
We use true random number generators as a source of keys for encryption. What I can not wrap my head around is: How is this cipher text decrypted in case of symmetric key algorithm as we need the same ...
1
vote
1answer
111 views
repeatedly hashing result and using reverse sequence as RNG secure?
I want to have a source of randomness for which:
no one but me can predict the next number in the sequence.
I know the entire sequence in advance, but I have no way of manipulating it once the first ...
0
votes
1answer
76 views
Expected Linear Complexity of a sequence
Let (s) be a sequence of length n. What are the expected linear complexities of (s) and $(s)^{\infty}$ (meaning that the periodic version of s)?
I have no idea of the answer to this question? What ...
