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
0
votes
0answers
110 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^...
2
votes
0answers
77 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 ...
11
votes
5answers
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 ...
3
votes
1answer
121 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? ...
0
votes
1answer
61 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 ...
2
votes
0answers
39 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$ ...
0
votes
0answers
36 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$ ...
2
votes
1answer
82 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 ...
2
votes
0answers
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 ...
3
votes
2answers
197 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 ...
0
votes
0answers
35 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 ...
2
votes
1answer
337 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
2answers
110 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 ...
0
votes
1answer
74 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 ...
0
votes
1answer
43 views

Multiple COA-security (IND-EAV-Mult security) cipher

Be this the Experiment for multiple COA-security: $PrivK_{\mathcal{A},\Pi}^{mult}(n)$: $(m_0^1 , ... , m_0^t,m_1^1 , ... , m_1^t) \leftarrow \mathcal{A}(1^n), |m_0^i|=|m_1^i| \forall i \in [1,t]$ $...
1
vote
1answer
81 views

"Infinite" (crpytographic) pseudorandom sequence

This is mainly for math purposes although it would be good for cryptographic purposes too, are there any known algorithms for generating an infinitely long (pseudo)random sequence of numbers (say bits)...
1
vote
0answers
94 views

How to build a lsfr based on sequence $s_i = s_{i-1} + s_{i-4}$? [closed]

How do I know where my XOR gates go? What does the F2 stand for here? Also the next task is to generate the sequence (with initialisation vector $s_0 = 1, s_1 = s_2 = s_3 = 0$) until it becomes ...
2
votes
0answers
69 views

Hash function based cryptographically secure pseudo random number generator

I once read/heard that one could generate a cryptographically secure pseudo random number generator based on two cryptographically secure hash functions. The algorithm goes this way: Let $f$ and $g$ ...
1
vote
1answer
51 views

Generate unique random values for unqiue input values

I'm going to generate unique random values based per a range of unique input values. In other words I have range of input values which these numbers are part of a series (like a range of serial ...
0
votes
0answers
26 views

Adding Weyl sequence to random mapping - expected cycle size

In order to improve the quality of random generators, Weyl sequences have been added to the Middle Square (Widynski) and Xorshift (Marsaglia) generators: https://arxiv.org/abs/1704.00358 https://www....
2
votes
2answers
299 views

What is wrong with Middle Square PRNG?

According to article: https://www.pcg-random.org/posts/too-big-to-fail.html When N of Middle Square is $2^{128}$ we can expect to produce $2^{64.3}$ numbers before we start to see repeats in generator....
2
votes
4answers
187 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
2answers
92 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
1answer
55 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 ...
0
votes
0answers
35 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?
-1
votes
1answer
62 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
0answers
53 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
1answer
159 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 ...
0
votes
0answers
68 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 ...
0
votes
1answer
32 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
0answers
31 views

How to reproduce seeds in Random Number Generator like WELL, KISS etc

I am curious about Padding the seeds of Random Number Generator. (I am sure that terminology, padding the seeds, is not correct. If someone knows the proper word, please let me know :) ) What is ...
1
vote
1answer
62 views

Getting the plaintext encrypting the ciphertext

Context: an encryption game from overthewire (the link to it: https://overthewire.org/wargames/krypton/krypton6.html, also good for more info) where given the ciphertext, one must obtain the plaintext....
0
votes
2answers
58 views

PRNG based on GF?

Are there any pseudo random number generator based on Galois fields? The source of the AES randomness lies in the GF, so GF should be capable of generating random bits. Why are there no such ...
6
votes
4answers
463 views

A source of randomness that anyone can independently, conveniently and robustly access?

Does there exist a source of randomness that anyone in the world can independently, conveniently and robustly access? For example, the 10th decimal place of the temperature in Mexico City is ...
0
votes
2answers
187 views

What are the fastest algorithms that sample from the uniform distribution?

Lots of cryptography algorithms rely on pseudorandom number generators. Sometimes, given a plaintext, you need to generate a pseudorandom number from it. What are some fast algorithms that do so? I've ...
0
votes
1answer
26 views

Non-overlapping seeded numbers generator for small output range

Seen this, but it's sort of useless as it allows for trivial solutions by increasing the size of the output's space up to a point any hashing function will achieve non-collision. This question is ...
1
vote
1answer
56 views

PRNG generator which could repeats blocks

Let's use AES as stream cipher, and let's use as an input numbers $1,2,3,...$. This way we should get the random blocks and every block will be different from each other. But I have a pseudorandom ...
0
votes
0answers
111 views

How can I recover mersenne twister when only the part of the bits?

https://github.com/tna0y/Python-random-module-cracker Here, when we get 32*624 bits of outputs from Mersenne-twister we can recover Mersenne twister. My question is when we get the parts of the bits, ...
2
votes
3answers
161 views

Can we combine two true random generators to obtain a new one?

It is well known that a true random generator exploits the randomness occurs in some physical phenomena. Also, the output of a true random generators can be either biased or correlated. Therefore, de-...
0
votes
0answers
123 views

Determine if a function is a PRG when PRG concatenated with Seed?

I am a newbie in Cryptography and have trouble to solve the following question. Let $G: \{0,1 \}^n \rightarrow \{0,1 \}^{l(n)}$ be a PRG and $x \epsilon \{0,1 \}^n$. Determine if the function $Z: \{...
1
vote
0answers
32 views

composition of RLWE distributions

Assume we have the polynomial space $R_q$ defined as $R_q = Z_q/(X^n + 1)$. Additionally, we define the error distribution $\chi$ as a discrete centred Gaussian bounded by $B$. Let $s,t \in R_q$ be ...
0
votes
0answers
23 views

Construction PRG with expansion factor from a length preserving PRF [duplicate]

How can I prove that $F:\{0,1\}^n\to\{0,1\}^n$ is a length-preserving pseudorandom function, then $$G:G(s)= F_s(1)\mathbin\|F_s(2)\mathbin\|\cdots\mathbin\| F_s(l)$$ is a pseudorandom generator with ...
2
votes
1answer
47 views

How to prove the pseudorandomness of CryptoPAn

in my cryptography course, we are learning about pseudo randomness and the prefix-preserving function known as CryptoPAn invented in 2002. It is said that the scheme is highly insecure. So in that ...
0
votes
0answers
53 views

Am I applying Hybrid lemma and proof by contradiction correctly?

In the following scenario, I am trying to apply proof by contradiction. My idea is to use a Hybrid lemma. So if I am able to distinguish $G'$, this implies we are able to distinguish $G$. But we ...
1
vote
2answers
110 views

Rigorous practical pseudorandom generators

It is known that existence of pseudorandom generators (PRGs) is equivalent to the existence of one-way functions. In turn, the latter is an open problem. I am curious if someone developed kind of &...
4
votes
2answers
413 views

Is a LFSR sufficient for post-processing a biased TRNG?

I am building a TRNG on a FPGA based on ring oscillators. I found out that Linear Feedback Shift Registers (LFSRs) are commonly used for the post-processing of TRNGs. Here is my initial design: Let's ...
2
votes
1answer
77 views

Question about IETF RFC6979 determinisitc (EC)DSA document section 3.6 additional data k'

In RFC6979, on page 14, Section 3.6 "Variants": o. Additional data may be added to the input of HMAC, concatenated after bits2octets(H(m)): ...
8
votes
4answers
178 views

Why are $\lceil 1/\operatorname{entropy-per-bit} \rceil$ number of bits not sufficient to generate an unbiased bit?

Consider a biased RNG badrand() generating 1 with probability $0.9$ and 0 with probability $...
2
votes
2answers
293 views

Is Fibonacci-XOR-rotate one-way-ish?

Fix $n\in\mathbb{N}$ with $n > 2$ and consider the following method. Pick relatively prime seeds $x_1, x_2 \in \{0,1\}^n$ (where $x_1, x_2$ are interpreted as binary numbers. Then proceed with the ...
4
votes
1answer
235 views

What is the NIST recommended maximum bias for random number generators?

What is the maximum bias recommended by NIST for random number generators? This answer says that it is $2^{-64}$. Is it same for all applications? Does NIST have a publication with more information? I ...

1
2 3 4 5
9