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
3
votes
1answer
686 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 ∊ \{0, 1\}^n$...
3
votes
2answers
133 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 ...
3
votes
2answers
443 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 ...
3
votes
3answers
1k views

why can't use only one way function to construct a PRG, and don't use the hard core predicate?

The one-way function can expose some of the input and stay one-way, but still, that doesn't give the input. As I read, we can't just construct a PRG from a OWF, but we need to use the hard core ...
3
votes
1answer
89 views

Permuting Small Sized Set in Practice

Imagine we have a set $S$ of $m$ elements and we wants to permutes the set elements. Thus the original position of each element should be unknown after permuting. If we define a permutation function ...
3
votes
1answer
716 views

Crypto++: How to re-generate pseudo random integers in Crypto++

I'm using Crypto++ to implement my protocol to mask a value $y_i$ by a pseudo-random value $r_i$ such that $m_i=y_i \cdot r_i$. Since there are many $r_i$'s I want to generate them using PRNG and then ...
3
votes
1answer
871 views

Reseeding a PRNG with the generated PRN

Would reseeding a PRNG with the PRN from the previous generation have any effects whatsoever on the quality of the generated numbers; if so, does this depend on the PRNG used, or are the effects ...
3
votes
1answer
827 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$...
3
votes
2answers
607 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{...
3
votes
1answer
2k views

about entropy and random number generator

I am reading an article about cryptography of information and Pseudo Random Number Generator. The article said using 1$28$-bit entropy PRNG is safe in some cases of cryptography. I am not familiar ...
3
votes
1answer
675 views

What is the G function of FIPS-186-2?

We are trying to follow FIPS 186-2 for creating a pseudo random number generator for EAP AKA AT_MAC Calculation in SIM Authentication: Choose a new, secret value for the seed-key, XKEY In ...
3
votes
1answer
102 views

PRNG output with truly random noise

I am considering a situation where an adversary does not have access to the $n$-bit output string of a PRNG, but instead receives a noisy version of it, where each bit of the string is flipped with ...
3
votes
1answer
207 views

What's causing the poor randomness in this program: the LCG, or the program logic itself?

(Crypto Gods, I should begin by stressing that I haven't lost my mind: I'm not doing this in real life, I'm just trying to understand the theory behind what's happening. With your help, hopefully I ...
3
votes
1answer
179 views

Is my implementation of a PRG at least intuitively secure?

I've devised a PRG using Bezier curves , constructed with Bernstein polynomials, and I was wondering if you guys could help me with some suggestions or constructive criticism. Basicly I take a random ...
3
votes
2answers
121 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 ...
3
votes
1answer
308 views

Can we convert a pseudorandom function (PRF) to an Oblivious PRF (OPRF) through an Oblivious Transfer (OT) protocol?

I'm a software engineer, so I generally think in building blocks. And I'm not so familiar with the Math notation in Crytography, so I'll stick with function calls and function blueprints (which I ...
3
votes
1answer
1k views

How to clock a linear feedback shift register?

I have some trouble understanding what happens when a LFSR is clocked. I have tried many examples but I do not get the correct result. Can anyone point out my errors? I have the following polynomial: ...
3
votes
1answer
57 views

Is it possible to sample HE ciphertexts using pseudo-random generator?

I'm trying to sample HE ciphertexts which serve as ciphertexts encrypting some random values. I have realized a example program using Microsoft SEAL, which implements a variant of BFV scheme. ...
3
votes
1answer
282 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. ...
3
votes
1answer
701 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 ...
3
votes
2answers
1k views

Dice rolls as entropy source?

I would like to generate a 128 bit random number with dices, but I have heard that dices are pretty biased, especially low quality (non casino dices). Would it make sense to generate a higher bit ...
3
votes
2answers
338 views

Question about proof of pseudo-random random generators being one way functions

I've been looking over this proposition and proof in the book "Introduction to modern cryptography" and am a little confused. Picture is attached at the bottom). Why is it that we do not multiply the ...
3
votes
1answer
2k views

Generation of N bit prime numbers -> what is the actual range?

Short version: When generating a prime number of N bits, should I draw random numbers from the range $[0 , 2^n]$, or $[2^{(n-1)} , 2^n]$? Context: I'm trying to implement a toy-version of RSA as a ...
3
votes
1answer
80 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 ...
3
votes
0answers
390 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 ...
3
votes
2answers
308 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 ...
3
votes
0answers
186 views

Finding the cycle sets of an LCG

My LCG has the form: $$S_0 = k$$ $$S_{n+1} = S_n \times a + 1 \pmod m$$ Each choice of $k$ generates a different sequence but in some cases a sequence may just be a cyclic shift of another. In this ...
3
votes
0answers
297 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 ...
3
votes
0answers
327 views

On the Definition of a PRG and a CSPRG

I've been looking at the definition of a PRG, here. This is a broader notion than a cryptographically secure PRG ("CSPRG"), which is described here. I am realizing that I am very confused by this ...
3
votes
0answers
235 views

Integer factorization based password authentication

After looking at this security issue at DjangoProject, I started to think in a password-based authentication that places the burden of PBKDF2 (or whatever is the hashing function) on the client. So I ...
3
votes
2answers
163 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 ...
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. ...
2
votes
2answers
325 views

Collision-resistant Pseudorandom function

Assume we have a pseudorandom function: PRF(.) We want the following property holds with a high probability: $\forall i, 0\leq i \leq n: PRF(k_1, i)\neq PRF(k_2,i)$ where $k_1$ and $k_2$ are two ...
2
votes
1answer
217 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 ...
2
votes
3answers
4k views

LFSR for small numbers with large periods

I want to generate a few random numbers using an LFSR. However, the LFSR output depends on the number of taps, so for a large period I use large (relative) number of bits. This causes the numbers to ...
2
votes
2answers
391 views

Cryptographically strong seeded pseudo random number generator

Why is the following not cryptographically secure? Seed the algorithm with 32 random bytes S[0]. ...
2
votes
3answers
114 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
778 views

How Should Fortuna and Yarrow Compare When Tested With Dieharder

I have both Yarrow and Fortuna implemented as number generators. I ran 100 complete DieHarder (entropy tester) tests for each implementation using the same entropy source. The results were surprising: ...
2
votes
1answer
88 views

Mathematical proof or any reference of “Deterministic random bit generator cannot produce more randomness than the randomness of seed”

The heading tells everything. Any proof or any kind of reference is welcome regarding this: Can we get more randomness from a deterministic random bit generator than the entropy that we feed to the ...
2
votes
3answers
701 views

Let $F$ be a PRF, is the following $G(x)=F_{0…0}(x)∥F_{0…1}(x)|| … ||F_{1…1}(x)$ a PRG?

This exercise comes from Coursera's "Cryptography" course. Let $F$ be a PRF, is the following $G(x)=F_{0…0}(x)∥F_{0…1}(x)|| ... ||F_{1…1}(x)$ a PRG? $F$ is a PRF with $n$ bit key, input, and ...
2
votes
2answers
1k views

Random numbers for Rabin-Miller primality tests

I've implemented a Rabin-Miller primality test fuction following Wikipedia and the book Applied Cryptography. Now I'm using it for generating primes with a string seed. The book suggests the following ...
2
votes
3answers
147 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 ...
2
votes
1answer
280 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
1answer
1k views

Is every pseudorandom generator a one way function?

$$\{G:\{0,1\}^n\rightarrow\{0,1\}^{2n+1}\}^\infty_{n=1}$$ If above function is a pseudorandom generator then is the same $G$ a one way function. I tried to prove this but failed a lot of time. Would ...
2
votes
1answer
2k views

random number generator and seed

I'm working with openssl cryptographic libraries, I'm new to all these cryptographic stuffs and slowly I'm learning all these. I have a doubt regarding random number generator, I'm using ...
2
votes
2answers
105 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-...
2
votes
1answer
152 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
146 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
1answer
143 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-...
2
votes
1answer
313 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 ...

1 2
3
4 5
8