# 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.

464 questions
Filter by
Sorted by
Tagged with
1 vote
32 views

### Finding a specific word in a substitution cipher

Rand48 is a pseudo-random generator which produces a sequence of any given integer using the following rule: $a_n=(25214903917 \cdot a_{n-1})\bmod 2^{48}$. If $b_n=\lfloor a_n/2^{16} \rfloor \bmod 52$,...
100 views

### Is this pseudo random function any good and/or original? [closed]

I designed this pseudo-random function algorithm that takes a uint64 and returns a uint64. I'd like to know if it is any good ...
260 views

### What is an output symbol?

I'm reading Understanding Cryptography by Christof Paar and Jan Pelzl. In chapter 2 (Stream Ciphers). There is a section talking about "Bulding Key Streams from PRNGs". They assume a PRNG ...
1 vote
54 views

### A security issue of a Bit commitment scheme constructed by Naor in 1990

In the Section 3.12 of book writen by Boneh and Shoup, a Bit commitment from secure PRGs is presented as follow: Bob commits to bit $b_0\in_R\{0,1\}$: Step 1: Alice chooses a random $r\in R$ and sends ...
1 vote
61 views

### Minimum cycle length for Rule 30 automaton with bit-toggle

A rule 30 cellular automaton produces chaotic output from a very simple rule and therefore can be used as a pseudo-random generator (but not a cryptographically secure one). One of the problems is ...
47 views

### Implementation of the chaotic map to produce (pseudo)-random number

For my project I used Henon map to generate (pseudo)-random number. I used the following code to generate the matrix of (pseudo)-random number. ...
45 views

### Mapping number into number with big algorithmic entropy - how to do it?

I need to parameterize some PRNG, let's assume I need 32-bit numbers. But when numbers doesn't look very random it gives bad results. The creators of SplitMix had similar problem (note that from what ...
1 vote
70 views

### Can we apply the Pseudo Random Number (PRNG) as post processing method for True Random Number (TRNG)?

From the NIST SP 800-90B, we can use these cryptographic algorithms (HMAC, AES, Hash function) as a post-processing technique for TRNG. Besides that, can we apply the Pseudo Random Number (PRNG) as a ...
139 views

### Majority-based feedback shift register

Linear feedback shift registers (LFSR's) work by taking a fixed-length bit-string $b\in\{0,1\}^n$, as well as fixed "taps" (bit positions) and applying XOR to the taps, giving one output bit,...
132 views

### Are pseudorandom generators, pseudorandom permutations and hash functions all keyless?

In Katz's Introduction to Modern Cryptography, Chapter 7 Practical Constructions of Symmetric-Key Primitives In previous chapters we have demonstrated how secure encryption schemes and message ...
1 vote
45 views

### Is F' = G(F)) a secure PRF given F and G are secure? [closed]

If we have a secure PRF 𝐹(𝑘, 𝑥) and a PRG G where 𝐺 : 𝒴 → 𝒴 × 𝒴 is a secure PRG. Is the PRF F'(k, x) = = 𝐺(𝐹(𝑘, 𝑥)) also secure?
40 views

### Is this property implied by a pseudorandom function?

Given a keyed pseudorandom function $f: S \times X \rightarrow Y$, where $S$ is the space of secret keys, $X$ is the input domain, and $Y$ is the range, the pseudorandom property says that given any ...
85 views

### Does xoshiro/xoroshiro PRNGs provide uniform distribution?

It's not clear from the documentation if the sequence of integers produced by these PRNGs belongs to the uniform distribution. Also it's look like there is a whole family of RNG algorithms called in a ...
33 views

### Is block-wise locality pseudorandom generator standard assumption?

To my best knowledge, the Goldreich's pseudorandom generator (PRG) with locality 5 has been considered as one of standard assumptions. On the other hand, Lin and Tessaro (Crypto'17) provides a new ...
60 views

### Standard way to generate pseudorandom bytes on demand

I considered Extendable-Output Function (XOF) with a random seed but it seems I would have to specify the output length at the start and store the entire output. I don't know how many bytes I will ...
58 views

### OWF from PRG and OWF

Let $f : \mathcal{U}_{2\lambda} \to \mathcal{U}_{2\lambda}$ be a OWF, and $G : \mathcal{U}_{\lambda} \to \mathcal{U}_{2\lambda}$ be a PRG with $\lambda$-bit stretch. Establish whether the following ...
54 views

### Can a security parameter be used in a function that combines pseudorandom generators?

I am really stuck with the following question: $G: \{0,1\}^\lambda \to \{0,1\}^{2\lambda}$ is a secure pseudorandom generator, and $\lambda$ is a security parameter. Is the following a secure ...
37 views

### Wha is a security parameter in a pseudorandom generator? [duplicate]

F: {0,1}^λ → {0,1}^2λ is a secure pseudorandom generator, it says that λ is a security parameter, what does that mean?
124 views

### Is this construction a OWF?

Given the OWF function $f: \{0,1\}^{2\lambda} \rightarrow \{0,1\}^{2\lambda}$ and the PRG $G: \{0,1\}^{\lambda} \rightarrow \{0,1\}^{2\lambda}$, is the following function $f^*$ a OWF? \begin{align} f^...
96 views

### How to exploit Java's RNG to find clusters?

In the above image, you can see a coordinate grid containing some random green points. Each point has a pseudorandom 1/10 chance of being green. What I'm looking for are clusters of these green points ...
3k views

### What is wrong with XOR encryption with secure PRNG?

Suppose I want to encrypt a message with a password. Couldn't I just XOR the bytes with bytes from a cryptographically secure pseudorandom number generator (CSPRNG) with seed being the password, or a ...
139 views

### Do there exists PRNGs that provably pass the next bit test?

I am wondering if there are any results in literature which construct a PRNG that is proved to pass the next bit test? If so, can you state what the PRNG is and where I can find more details on it? ...
80 views

### Why do we need to use PRGs to generate random numbers for a one-time-pad? [duplicate]

I'm looking at the following idea for using a symmetric key to encrypt multiple messages (back & forth communication between Alice & Bob). It can be summarized as follows: Both sides agree ...
47 views

### Does the PRG game allow for bad randomness picks?

In the game-based definition, we say that $G: \{ 0, 1 \}^n \rightarrow \{ 0, 1 \}^{\ell(n)}$ is a pseudorandom generator if For all ppt distinguishers $D$, there exists a negligible function $\nu$ ...
41 views

### PRGs from OW functions

Given a OW function $f:\{0,1\}^n\to\{0,1\}^n$ with hardcore predicate $h(x)$, you can build a PRG $G$ by setting $$G(s):=f(s)\Vert h(s), \quad s\leftarrow\{0,1\}^n.$$ The expansion condition for $G$ ...
97 views

### Existence of algorithm predicting next bit in output sequence

Let $X = [0, 1]\cap \mathbb{Q}$, and let $f:X \rightarrow X$ be a chaotic map (i.e. the logistic map with rational parameter). My question is as follows, and is purely theoretical in nature. Pick ...
36 views

### Cyclical Redundancy Check and bijections [closed]

Let $F_M(n)=\operatorname{CRC32}(M|n)$, where $M$ is an arbitrary length prefix message, $n$ is a 32 bit integer (whether little or big-endian encoded is unimportant) and "|" is simply ...
226 views

### Are PRNGs Key Derivation Functions?

PRNG is a mechanism to produce randomness from an initial random seed, so basically a way to derive more secrets from one secret. Looking at the Wikipedia entry for KDF you find In cryptography, a ...
133 views

### PRG implies OWF Proof

I got the idea of this proof, that since PRG expands from n to 2n, it cannot project to all {0,1}^{2n}, only to a neglible part which we can abuse to make a good distinguisher just by telling if A ...
341 views

### Linear Complexity of two dimensional finite patterns such as QR codes

Two dimensional patters are omnipresent in information transactions. QR codes, images are most common. I want to know if there is a concept analogous to the well known concept of Linear Complexity of ...
1 vote
193 views

### When are PRNG used and when are CSPRNG used

I understand that PRNG are Random Number Generators that uses a deterministic algorithm based off of a seed. I also understand that CSRNG are PRNG that are cryptographic-ally safe to use for ...
92 views

### Is hashing random numbers generated from a TRNG enough to create a key? [duplicate]

Is hashing random numbers generated from a TRNG enough to create a key? Basically taking the output of something like a Lavarand and pass that through a hash function like sha-2. I guess at the end of ...
78 views

202 views

### What can chaos provide to cryptography?

Chaos-based cryptography is facing a lot of criticism, however, some people argue that it can provide many cryptographic primitives, such as stream ciphers, block ciphers, hash functions, public-key ...
1 vote
111 views

### Does Endianness matter in NIST SP800-22 test?

I am curious about Randomness test suite. One of the famous randomness test suite, DIEHARDER, said that Endianness does not matter for a "GOOD" random generator. Note that this is not the ...
1 vote
64 views

### How to measure the length of the 128-bit PRNG cycle?

I have keyed 128-bit PRNG. It passed PractRand and Dieharder tests, but I have no idea what is expected cycle lengh of it (for different keys and different seeds). Is there way to estimate it, through ...
41 views

### Mersenne twister word size and degree of recurrence combination

For a 32-Bit variant of Mersenne twister, if the outputs Should be a 5-Bit integer(word size) then what is the value of recurrence according to the k-distribution?
79 views

### Neural Network based on pseudorandom number

Recently, I read this paper NEURAL NETWORK BASED CRYPTOGRAPHY. Under the section 3.1 it said: The aim is to improve the randomness of the random numbers generated by any algorithm using an NN. In ...
1 vote
79 views

### Program to predict a 5-bit output from mersenne Twister random module from python

Is there a program to predict the mersenne twister random module in python for a 5-bit integer output, provided the consecutive 3994 outputs are available? The random module is not seeded so i guess, ...
1 vote
225 views

### Pseudo Random Generators

G is a PRG and takes in a seed s. Is G'(s) = [G(s)]' (i.e. the complement of G(s)) a PRG as well? My proof by contradiction: Suppose G' is not a PRG, then G''(s) = [[G(s)]']' = G(s) is also not a PRG ...
93 views

### Prove a function G is not a pseudo random generator

A function G(x) = x || x (where “||” denotes string concatenation). It is given that G is not s pseudo random generator. Can someone describe how can we prove this. I am getting a bit confused in the ...
56 views

### Relationship between LCGs and LFSRs

Here: https://en.wikipedia.org/wiki/Linear-feedback_shift_register they wrote: The linear feedback shift register has a strong relationship to linear congruential generators What this relationship ...
1 vote