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
13
votes
2answers
7k views

Is it possible to recover the seed used by Python's pseudo-random number generator?

I generated some random numbers using a Python script. I have the first 40 numbers of the sequence. Is there a way to recover the seed or find the next 460 numbers in the sequence? The numbers were ...
1
vote
1answer
627 views

is the XOR of PRG outputs a PRG?

I am going through the course http://u.cs.biu.ac.il/~lindell/89-856/main-89-856.html, as it has a good lecture notes. I found exercise 2 solution a puzzling statement: it says that $G^\prime (x_1 , ...
1
vote
1answer
732 views

Prove that pseudorandom generator is a one way function

Suppose the following PRG $G : \{0,1\}^n \rightarrow \{0,1\}^{n +l}$, I want to prove that $G$ is one way function (and not building one), for: $l = \omega (\log n)$ $l = 1$ For $l = \log n$, ...
1
vote
0answers
238 views

Pseudo-random function where the output is inverted using XOR

I'm looking to know whether or not this PRF is secure : $$F'(k, x) = F(k, x) ⊕ 1^n$$ knowing that $F$ is already a secure PRF for $$\{0, 1\}^n × \{0, 1\}^n → \{0, 1\}^n$$ with, for example, $n= ...
1
vote
1answer
185 views

How should k2 be produced in the RC4A stream cipher (A modification of RC4)?

RC4A is a slight modification of the simple RC4 stream cipher designed to strengthen it against a number of attacks. Here's that paper. However in the paper, the second key ...
1
vote
1answer
98 views

Figuring out seed/internal state from HMAC-MD5 output

Here is the scenario i'm imagining, I use the python random library to generate x-bit key that I use to generate a HMAC-MD5 output. Every HMAC-MD5 has uses a different random number as its key. My ...
1
vote
0answers
1k views

Assume $G$ is a PRG. Proof that $G'$ is PRG?

Let $G: \{0,1\}^s \rightarrow \{0,1\}^n$ be a pseudorandom generator (PRG). Are the following PRGs? $G'(x) = G(x)_{0,\ldots,n-2}$ ($G'(x)$ drops the last bit of $G(x)$) $G'(x) = G(x) \oplus ...
0
votes
1answer
85 views

need to develop CSPRNG. can i use ANSI X9.31 generator

need to create secure PRNG. can i use ANSI X9.31 generator and modify its entropy rather using DT use something else >?
3
votes
1answer
568 views

Is the following a PRG?

Let $G: \{0, 1\}^n → \{0, 1\}^m$ be a PRG. We construct a function $G': \{0, 1\}^{m + n} → \{0, 1\}^{2m}$ defined as follows $G'(x || y) = x || (G(y) ⊕ x)$ for all $x ∊ \{0, 1\}^m$ and $y ∊ \...
13
votes
1answer
636 views

Overview of relations between cryptographic primitives?

Is there a web page that gives a graphical (or, alternatively, a textual) overview of known implications and separations between cryptographic primitives? More specifically, I am looking for ...
2
votes
1answer
270 views

Why can't we construct a PRG from a one-way function and hc, but only one-way permutation

From Katz & Lindell's book, theorem 7.19: Let f be a one way permutation with hard-core predicate hc. Then the algorithm $G(s)=f(s)||hc(s)$ is a PRG with expansion factor $\ell(n)=n+1$. ...
0
votes
1answer
451 views

Katz/Lindell Problem 7.6

Let $f$ be a length-preserving one-way function, and let $\text{hc}$ be a hard-core predicate of $f$. Define $G$ as $G(x)=f(x)\|\text{hc}(x)$. Is $G$ necessarily a pseudorandom generator? The answer ...
1
vote
1answer
130 views

RNG Source Combining

I'm planning on combining RNGs from several sources (Windows, Linux, OpenBSD, etc.) for generating one time pads but I have some questions that I don't know how to answer regarding xoring the outputs ...
16
votes
4answers
10k views

How can C rand() be exploited if a secure seed is used?

I've just started doing a research project on CSPRNGs and I would like to know what kind of vulnerabilities a regular PRNG has with a secure seed. For example, if I generate a random number using ...
1
vote
2answers
2k views

Is it possible to compress random sequence with high entropy

I have an algorithm that generates pseudo random sequence with length of 100k and high entropy. I would like to check the quality of randomness. So, I used a popular software to compress the generated ...
1
vote
1answer
788 views

ANSI X9.31 AES pseudocode or algorithm explanation

I want to write a program that will generate random data by using ANSI X9.31 with AES 128 bit, however I could find the standart only with cryptographic notation, and I did not understand it clearly. ...
1
vote
1answer
813 views

Definition of a distinguisher

In Introduction to Modern Cryptography by Katz and Lindell, p. 70, they define a pseudorandom generator by: Let $l(\cdot)$ be a polynomial and let $G$ be a deterministic poly-time alg. s.t. for ...
3
votes
1answer
719 views

Existence of PRF $\implies$ existence of PRG

Let $F:\{0,1\}^n\times \{0,1\}^m \to \{0,1\}^l$ be a PRF. I want to show that $G(-)=F(-,x_0)$ is a PRG for every $x_0\in \{0,1\}^m$. Proof attempt: Let $D$ be an efficient distinguisher against $G$...
-2
votes
2answers
180 views

Is this scheme multi-message secure? [closed]

Let $G$ be a pseudorandom generator. Is the scheme with encryption $$\text{Enc}_k(m) = s \| \left( m\oplus G(k) \oplus s \right),\quad s\in\{0,1\}^n \text{ uniformly sampled},$$ and decryption $$\...
2
votes
2answers
378 views

Cryptographically strong seeded pseudo random number generator

Why is the following not cryptographically secure? Seed the algorithm with 32 random bytes S[0]. ...
0
votes
1answer
119 views

Question about CTR_DRBG Instantiation specification

NIST SP 800-90a defines the CTR_DRBG in section 10.2. There is a comment within the document that I don't understand. Let's assume we want to achieve a security strength of 256 bits, using as ...
2
votes
0answers
216 views

Decentralized consent over a random number

Maybe, some of you remember having to pick one person during playing as kids. That person would than have to catch the others for example. The methods to pick given person often would either depend on ...
1
vote
2answers
687 views

Practical way to generate random numbers from PRNG which are indistinguishable from true random

I am working on a project where I want the user to be able to create random data. For that I use a cryptographically random generator (Java's SecureRandom, which uses OS entropy source if available). ...
0
votes
1answer
128 views

Index in PRNG output sequence

We have some simple PRNG, like a LCG or LFSR. Easiest is one that follows a output state, transform state cycle. Let's call that cycle an "iteration", and one of these outputs a "word". Knowing the ...
0
votes
1answer
141 views

Explanation of the EPC Gen2 randomness standard's first rule

When we read PRNG requirements of the EPC standard, first rule (page 57 in this link) in the documentation; Probability of a single RN16: The probability that any RN16 drawn from the RNG has ...
7
votes
4answers
375 views

Are there flaws in (cryptographic) science/engineering/software/research due to pseudo random generators?

I am trying to see if there were any incidents in the past where using PRNG or not actual random scheme leaded to wrong conclusion in research. For example, a lot of fields today use simulations to ...
3
votes
2answers
120 views

Efficient way to combine collection of hashes into a single hash?

I have a system where each user will submit a set of data. The data will be hashed and their hash will be submitted to the server. My plan is to combine each users hash (converted to bytes XOR'd with ...
-2
votes
2answers
582 views

Relationship between a key stream having a high entropy and whether it is cryptically secure in a stream cipher

Hi i am trying to build a key stream generator for my homemade stream cipher.The key stream output has a close to maximum entropy value and a large periodicity. What does it take for this generator to ...
1
vote
1answer
357 views

How to prove a pseudo-random function has certain expansion factor

How should I answer the following problem: Let $F = F0 \times F1$ be a pseudorandom generator with expansion factor $2n$ such that for all $x \in \{0, 1\}^n$ $$F(x) = (F_0 (x) || F_1 (x))$$ ...
3
votes
1answer
264 views

Fortuna: Reseeding

It is recommended that a new seed file be generated approximately every ten minutes by seed file manager in FORTUNA,though it depends on the application and on the rate of the accumulation of entropy. ...
2
votes
1answer
273 views

Can I truncate a CSPRNG psuedorandom number?

This might be too broad to apply for all CSPRNG, but it might apply for the general case, I'm not sure. I need this specifically for python os.urandom() and ...
2
votes
2answers
286 views

Creating a k bit random string

My goal is to create a random $k$ bit string. My question can be divided in two parts. If a $n$ bit string $s$ is computationally indistinguishable from a random $n$ bit string, can we say that the ...
5
votes
3answers
1k views

What are the dangers of using CPU clock drift for generating random data?

From what I understand, a physical source of true randomness could be achieved with a multi-core processor, by using clock drift between two or more cores. However, a processor is easier to ...
4
votes
1answer
206 views

Self-shrinking generator

A self-shrinking generator is a LFSR sequence processed with an algorithm that is different from von Neumann unbiasing. Does this imply that using von Neumann unbiasing instead would lead to an ...
2
votes
3answers
108 views

Security of stream cipher with a priori knowledge of message

I am generating a ciphertext by XORing the message bits with key stream bits of a stream cipher. But, if I know a priori that message bits contain a predefined number of 0's (say 60%) at unknown ...
2
votes
1answer
206 views

Using a non cryptographic PRNG for randomized algorithms

I want to use randomized algorithms (quicksort, ect...) on a server, but secure pseudorandom generators use a lot of cpu time. But if I use a non-secure one, and the clients figure out the seed, they ...
1
vote
1answer
154 views

Pseudo-random generator explanation by Bruce Schneier

I am reading about Pseudo-Random Sequences in Applied Cryptography book by Bruce Schneier. Description is provided below. A pseudo-random sequence is one that looks random. The sequence's period ...
2
votes
1answer
767 views

Pseudo-random permutation of a range

I have this set: {0,1,2,3,...,15}. I would like to create a pseudo-random permutation from elements of this set, for example ...
3
votes
0answers
276 views

Is a PRG that reveals the first bit of the input secure

Let $G:(0,1)^n \rightarrow (0,1)^{n+1}$ be a secure PRG. Define $G'(s):=s_1 ||G(s)_{2,...,n+1} $. ($||$ is concatenation, and the subscript $ _{2,...,n+1}$ means the last $n$ bits of $G$) I claim ...
1
vote
2answers
341 views

Is fixed key AES in counter mode a PRG?

I want to implement a PRG (Pseudorandom Generator). As AES is implemented in hardware, I am planning to use AES for efficiency. I am planning to use: $(AES_k(seed) \| AES_k(seed+1) \| AES_k(seed+2) \|...
3
votes
2answers
527 views

Is the following construction of a secure PRG is also a secure PRG?

Given a secure PRG $G :\text{{0,1}}^n \rightarrow \text{{0,1}}^{2n}$, I've constructed the following PRG: $$ G'(x) = \begin{cases} 0^{2n} & \text{if x is palindrome;}\\ G(x) & \text{...
4
votes
0answers
199 views

is a MAC defined by a pseudo random generator secure?

Let $ G:\{0,1\}^*\rightarrow\{0,1\}^*$ be a length doubling PRG, and let $ \Pi=(Gen,Mac,Vrfy)$ be the following MAC scheme: $ Gen $ on input $ 1^n$ uniformly samples and outputs $ k\leftarrow \{0,1\...
3
votes
1answer
616 views

Is this a secure PRG?

Suppose that we have a secure PRG $$G:\{0,1\}^{n} \rightarrow \{0,1\}^{l(n)}$$ I want to construct a secure PRG $G'$ that when we select its seed $s \in \lbrace 0,1 \rbrace^n$ that $parity(s)=0$, it ...
1
vote
1answer
378 views

PRG is Injective

I read this: Prove there is PRG that is not necessarily one-to-one. Now my question is: is there such PRG that is injective?
4
votes
2answers
674 views

Is a function defind by PRF with given key is a PRG

Let $G(s)=F_{0^n}(s)$ ($ 0^n $ is a fixed key given to the PRF F) for any $n∈\mathbb{N}$ and $s∈\{0,1\}^n$. Is G, defined via PRF as above, necessarily a pseudorandom generator? I presume that it is ...
3
votes
1answer
796 views

Fast crytographically secure Pseudo-Random number generator in software

What are the methods for generating pseudo-random numbers in software? I have seen methods where people use SHA implementations from openssl to hash a random message as source of entropy, or using AES ...
4
votes
2answers
334 views

identify if the functions are pseudorandom generator?

Given a pseudorandom generator (PRG) with $G(x) = y_{1} || y_{2}$, where $y_{1}$ and $y_{2}$ are n-bit strings. $G'(x) := G(y_{1}) || G(y_{2})$. Is $G'(.)$ still a PRG? I am guessing it's a No because ...
1
vote
1answer
385 views

Cracking linear congruential generator knowing a, b, m and scaled numbers

I was reading the book "Cryptographic engineering", one of the variation of linear congruential formula is as follow: $X_n = a_1X_{n-1} + a_2X_{n-2} \pmod {2^{31}-1}$ $a_1$ and $a_2$ are two prime ...
6
votes
1answer
805 views

Galois LSFR Subsequence Periodicity

I had the following questions - Concerning generating sequences of bits $\textbf{x} = ( x_{0},x_{1}, ... , x_{n-1})$ where the $x_{i} \in \{0,1\}$ are considered coefficients of a polynomial in $\...
3
votes
2answers
416 views

A questions about SP 800-90A DRBG additional input

There is four inputs in SP 800-90A DRBG that is entropy sources, nonce, personailisation string, additional input. I noticed the soundness of entropy_sources is most important thing for DRBG security ...

1 2 3
4
5
8