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
1
vote
0answers
37 views

How does pseudo random generator produce similar distribution to $U_{n}$

According to wikipedia, A function ${\displaystyle G:\{0,1\}^{\ell }\to \{0,1\}^{n}}$ with ${\displaystyle \ell < n}$ is a pseudorandom generator against $\mathcal {A}$ with bias $\epsilon$ if, ...
1
vote
0answers
46 views

Nth term for Linear Congruence Generators

We can get the N+1th term for a Linear Congruence Generator like this: x[n+1] = A * x[n] (mod m) by raising the A to the exponent of n like this: ...
0
votes
0answers
6 views

Finding Java.util.Random seed from bounded nextInt(int bound) results [migrated]

Background I've been reading and trying to wrap my head around various questions/answers that relate to finding the seed from Java.util.Random given its output from ...
2
votes
1answer
67 views

Cryptographically secure linear congruential generator - is it possible?

Let's consider generator: $x_{n+1} = (a \cdot x_{n} + c) \mod m$ And let's assume we will meet three requirements known as Hull–Dobell Theorem. Also consider only $m=2^{i}$ (then $c$ has to be odd). ...
1
vote
1answer
79 views

Questions about using PRF to construct PRG

Let F be a secure pseudorandom function with 128-bit key and 256-bit block length. Which are the following functions G are secure pseudorandom generators? (Select all that apply.) A. $G(x)=F_x(0...0)$...
1
vote
1answer
42 views

Why this example about pseudorandom generators is performed like that?

Suppose Alice wishes to authenticate herself to Bob, by proving she knows a secret that they share. With pseudorandom number generators (PRNGs) they could proceed as follows. They both seed a PRNG ...
1
vote
1answer
40 views

Deterministic Counter Mode with a PRF. What does evaluate at a point mean?

This is from Dan Boneh's Lecture where he talks about operating a PRF (AES, DES) in Deterministic Counter Mode. Dan Boneh says What we could do is we could use what's called a deterministic counter ...
1
vote
1answer
56 views

Unable to understand the concept of a 1-bit PRF

In his lecture on building Block Ciphers from PRGS, Dan Boneh says this Let’s start by finding out if we can build PRF from a PRG? Let $G:\ K \to K^2$ be a secure PRG Define 1-bit PRF $F:\ K \times \{...
2
votes
1answer
164 views

Tests to distinguish between PRNG and a CSPRNG

What are the tests which a regular PRNG would fail but a CSPRNG would succeed? Is it just the next-bit test or are there multiple other tests which a PRNG which is not a CSPRNG would fail? Would a ...
0
votes
1answer
38 views

Understanding the Inner State of a RNG

Based on the BSI evaluation criteria for quality of deterministic random number generators: K4 – It should be impossible, for all practical purposes, for an attacker to calculate, or guess from an ...
1
vote
1answer
53 views

PRG exponential expansion

I am just beginning to read into pseudorandom generators and I came across this definition for a PRG: $G_n : \{0,1\}^n \rightarrow \{0,1\}^{l(n)}, \quad \text{ where $l(n)$ is a polynomial}$ Is there ...
1
vote
1answer
70 views

How to combine a PRG and a non-PRG to design a PRG?

I'm trying to solve the following exercise: Let $G_1, G_2: \{0,1\}^\lambda \to \{0,1\}^{\lambda + l}$ be two deterministic functions mapping $\lambda$ bits into $\lambda + l$ bits (for $l \ge 1$). You ...
2
votes
0answers
41 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....
1
vote
2answers
210 views

Why is breaking the Blum Blum Shub PRNG not an undecidable problem?

The Blum Blum Schub (BBS) pseudo random number generator (PRNG) is defined inductively by $$ x_{i+1} = x_i^2 \mod N $$ to generate the bit sequence $b_0b_1b_2...$ where the bits are taken to be the ...
0
votes
0answers
46 views

Bad pseudo-random number generator — any guesses?

I'm trying to diagnose a badly-implemented pseudo-random number generator. The two key features of the bit streams produced by this PRNG are: significant correlation of consecutive bits (approximately ...
0
votes
0answers
46 views

Concatenation of PRFs is PRG

$F$ be a PRF, is the following $G(x)=F_{0…0}(x)||F_{1…1}(x)$ a PRG?
0
votes
0answers
28 views

What is the advantage of guessing PRG impossible outputs?

Lets say we have a length-tripling PRG $$ G:\{0,1\}^l \to \{0,1\}^{3l}$$ What would the advantage of an adversary to guess one of the impossible outputs of G?
0
votes
0answers
38 views

Are there any universal PRG’s or PRF’s?

Leonid Levin constructed a universal one-way function, i.e. a function $f$ such that if any one-way functions exist, then $f$ is a one-way function. My question is, what universal pseudorandom ...
0
votes
1answer
57 views

Proving G(x)=x||[x^2 mod 2^N] is not a PRG

This was a question from my exam yesterday. We have that $G:\{0, 1\}^n\rightarrow \{0, 1\}^{2n}$ and $$G(x)=x\mathbin\|[x^2 \bmod 2^n]$$ with $x$ is uniform and $|x|=n$, give an efficient ...
0
votes
1answer
49 views

PRF and deterministic polytime function implie PRG

I'm struggling while trying to resolve this exercise. I already read all questions about PRG and PRF here and some proofs around the internet but none of them helped me. let's consider a function $C$ ...
5
votes
2answers
194 views

Fast cryptographic hash function for short inputs

I am looking for a cryptographic hash function optimized for speed on short inputs, in order to implement a pseudorandom generator with expansion factor 2 (e.g. takes 16 bytes of input and outputs 32 ...
6
votes
1answer
481 views

Pseudorandom Generator

In a cryptographic application, two types of (pseudo)random bit streams are needed: a stream $A= a_{1}a_{2}a_{3}\ldots$ in which $\Pr[a_{i}=0]=\Pr[a_{i}=1]= 1/2\ \forall i$ and a stream $B= b_{1}b_{2}...
2
votes
0answers
99 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 ...
0
votes
0answers
14 views

Lehmer random number generator cipher scheme with moving bits

Let's consider linear congruential generator: $X_{k+1} = a \cdot X_{k} \mod 2^{128}$ Such that $a$ is some number which for every 128-bit input $X_{k}$ from $0$ to $2^{128}-1$ will give us different ...
0
votes
1answer
67 views

Cryptographically secure PRBGs and the previous-bit test

I am reading Junod's paper about the Blum-Blum-Shub PRBG (BBS) and I am having trouble following his reasoning at on page 15, where he argues that the next-bit test can also be peformed for the ...
0
votes
1answer
60 views

Lehmer random number generator - cipher?

Let's consider linear congruential generator: $X_{k+1} = a \cdot X_{k} \mod 2^{128}$ Such that $a$ is some number which for every 128-bit input $X_{k}$ from $0$ to $2^{128}-1$ will give us different ...
1
vote
1answer
49 views

How to calculate CPA attack complexity in bits manipulation

The following Forward Errors Correcting FEC is used in our daily devices. But I added a potential security measure. In one of FEC systems the input is $K$ bits and the output code is $M$ bits where $M=...
1
vote
1answer
45 views

Ranking “amount of randomization” in a sequence

I'm facing the problem of implementing pseudo random bit generator (PRBG) on a very low power device. NIST.SP800-22 "Statistical test suite for Pseudo Random Generators" suggests a suite of ...
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 ...
1
vote
1answer
200 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
69 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
199 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
154 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
102 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
94 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
63 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
53 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
38 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
86 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
52 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
149 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
26 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
116 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
63 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
122 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
38 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
81 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
27 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
456 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'':\{...

1
2 3 4 5
8