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
2
votes
1answer
307 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$. But what ...
2
votes
2answers
294 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 ...
2
votes
1answer
392 views

Can you help me understand this pseudo random generator example?

I'm new to crypto. I'm learning according to the book "Introduction to Modern Cryptography". I'm having troubles with understanding of PRG and how to prove if some function is PRG or not. I'm trying ...
2
votes
2answers
192 views

How to contruct a pseudorandom with a specific property

How to construct a pseudorandom function $PRF$ with the following property: Probability that $PRF(k_1,i)=PRF(k_2,i)$ is negligible, for all keys $k_1,k_2$ such that $k_1\neq k_2$ Does the PRF with ...
2
votes
1answer
232 views

Can I make a PRNG that is secure even when state can be modified by user?

I am interested in making a PRNG which, after being initially seeded, can accept and incorporate client data as the only ongoing source of "entropy". It is not directly for a cryptographic purpose, ...
2
votes
1answer
254 views

Do any (non-hardware) RNGs exist which could be used to create an OTP for crypto purposes?

I've stumbled (jobwise) over a system where small messages (512 Bytes or less) are encrypted and decrypted using a simple XOR using a OTP. That OTP is created using a seed based on the individual user ...
2
votes
1answer
2k views

Prove that a function is not PRF?

Let $G$ $PRG$ and $G'(s)$ equal to the first $n$-bits of $G(s)$, where $|s| = n$. Show that $F_k(x) = G'(k) ⊕ x$ is not a $PRF$. My attempt: Lets assume a $k$ and 2 messages $x_1$ and $x_2$. So, for $...
2
votes
1answer
224 views

A confusion on the proof of Yao's theorem (Yao 82)

I'm reading the proof of Yao's theorem on Boaz Barak's lecture, the main part of the proof is the following claim: My question is: How can we say "without loss of generality" here? Since $H^i$ ...
2
votes
1answer
386 views

ARC4random – ChaCha-based LibreSSL PRG

Here is arc4random.c from the LibreSSL pseudorandom generator as used in OpenBSD. It works as follows: Take 40 "truly random" bytes from OS (PRG seed); Use the seed as key and IV to generate 1024 ...
2
votes
1answer
504 views

Understanding Pseudo Random Generators

I've been taking a crypto course online. I have a good idea how PRG's and Stream Ciphers work, but I'd love to get some input to help visualize what is actually happening. I understand a seed is used, ...
2
votes
1answer
462 views

CTR mode encryption using PRG

In CTR mode encryption, the encryption block is not required to be invertible. Thus, a PRF can be used instead of a PRP. However most of the implementations of CTR mode are based on AES which is a PRP....
2
votes
1answer
668 views

How do I prove that this PRNG is easily distinguished from a random sequence of numbers (modulo m)?

I was studying Crypto, and this question came up. Using a PRG like the multiplicative congruence generator: $b_{i+1} = a \cdot b_i \mod m$ How do I prove that the output of this PRG, or any PRG's ...
2
votes
1answer
91 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
235 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 ...
2
votes
2answers
708 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?
2
votes
1answer
90 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_{...
2
votes
2answers
214 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'...
2
votes
1answer
533 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)$ ...
2
votes
1answer
81 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?
2
votes
1answer
190 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
272 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 ...
2
votes
1answer
242 views

prove PRG is secure assuming DDH holds

Let $\Bbb{G}$ be a cyclic group of prime order $q$ generated by $g \in G$. Let $G$ be a PRG defined over $(\Bbb{Z}_q^2, \Bbb{G}^3)$ such that: $G(a, b) = (g^{a}, g^{b}, g^{ab})$ How can I show ...
2
votes
1answer
878 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$, ...
2
votes
2answers
222 views

Does iterative hashing of mouse/keyboard input improve its properties as an entropy source?

In the questions, Are mouse movement coordinates useful as a seed for a RNG? and Is this a good entropy collector and whitening technique? the posters each talk about collecting mouse and keyboard ...
2
votes
1answer
113 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 ...
2
votes
1answer
347 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, ...
2
votes
1answer
222 views

period of the lfsr sequence after some manipulations

Here is the question I am dealing with. I have some sort of a solution but I need more specific results. If someone can help I'd appreciate: Given 3 maximum length (max period) LFSR's of lengths L1,...
2
votes
1answer
79 views

Unbalanced Feistel network only generates complete permutations with square lengths

I'm generating permutations with a generalized Feistel network which will output integer values $r_j$ in a specified range $[0,period]$ pseudo-randomly, according to the counter input, which will then ...
2
votes
1answer
203 views

Breaking variations of Linear Congruential Generators

So I have been trying to learn a bit of cryptanalysis and breaking pseudorandom generators as of recently, but I have run into a roadblock in my learning as I cannot crack this one problem. Basically ...
2
votes
1answer
697 views

Given a PRF $F$ , is $G(s) = F_s(1)\|F_s(2)\|\cdots \|F_s(n+1)$ a PRG?

If $F$ a PRF, and we construct $G$ using $F$ in the following way: $$G(s) = F_s(1)\|F_s(2)\|\cdots \|F_s(n+1)$$ where $|s|= n$. Is $G$ then a PRG? If so how can I prove this? If not how can $G(s)$ ...
2
votes
1answer
145 views

Generating shared secret random permutation

There are three blind card game players. Each player does not trust any other, even prejudicing other two players may not be blind, or there may be others in the room, peeking at their cards. In ...
2
votes
1answer
418 views

The Goldreich-Goldwasser-Micali Construction with bad PRGS

I understand that if we have a secure PRG then the Goldreich-Goldwasser-Micali construction gives us a secure PRF. However, what I've not been able to find much material on is how will the GGM ...
2
votes
0answers
35 views

Proof that PRG of itself is a PRG (composition)

I have this question and I am struggling to find a formal answer to this: Given $G$ is a PRG, show that $H(s)=G(G(s))$ is also a PRG. I know that a proof for this would assume that there exists a p....
2
votes
0answers
92 views

How does a hybrid argument work relating to PRG's?

How does a hybrid argument work relating to PRG's? I am working on a homework assignment where the problems say to use a hybrid argument to prove/disprove that something is a secure PRG, and I can't ...
2
votes
0answers
33 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 ...
2
votes
1answer
129 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 ...
2
votes
2answers
61 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
109 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 ...
2
votes
0answers
82 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$)...
2
votes
0answers
217 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 ...
2
votes
0answers
253 views

Showing a generator based to pseudorandom function is also pseudorandom

First of all sorry for the bad title, this is an exercise I'm struggling with: Let $F_k$ be a pseudorandom keyed function (abbreviated to PRF) with key, input and output of length $n$. Define the ...
2
votes
0answers
64 views

Is the number still a CSPRN if we only allow an interval from a CSPRNG?

tr -dc 0-9 < /dev/urandom | fold -w 3 | awk '$0>=100 && $0<=200' What this line does: /dev/urandom (Linux) is proven to be a CSPRNG, that is ...
2
votes
0answers
96 views

Polynomial restriction for PRG

Say we have a PRG $G(l,x)$ that expands a random string $x$ to length $l$ and is pseudorandom for any $l$ polynomial in $n$ (where $n = |x|$). Is $G$ pseudorandom for any $x$ of arbitrary length? I'm ...
2
votes
0answers
288 views

Difference between statistical PRNG and cryptographic PRNG? [duplicate]

What's the difference between a statistical pseudorandom number generator (PRNG) and a cryptographic-strength PRNG? I've seen a lot of PRNGs that are proposed for statistical uses -- e.g., ...
2
votes
0answers
280 views

How can I construct a distinguisher given an inverter?

Let $ PRG: \{ 0, 1\}^n \rightarrow \{ 0, 1\}^{n+s}$ be a pseudo random generator and let $A$ be an inverter that runs in polynomial time, specifically: $\large \mathbb P_{d \leftarrow PRG(U_n)}[ A(d) ...
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
3answers
711 views

Extracting only the entropy

(I cleaned up the question a bit, It was previously titled "extracting entropy without hashing" .. thus some of the comments / answers) I'd like to extract the entropy of data without injecting "...
1
vote
3answers
811 views

Can you help me with this Random Number Generator function?

By someone's suggestion, I am posting this question from math.stackexchange.com. I want to find out a suitable function or algorithm, which can provide a random sequence like this… Input: $3$ Output:...
1
vote
2answers
517 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 ...
1
vote
2answers
392 views

Why is the rand() function in C not a cryptographic pseudo-random generator?

For example, one of the possible rand() implementations: ...

1 2 3
4
5
8