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.
450
questions
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
74 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
119 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
81 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
108 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
73 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
42 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
91 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
34 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
61 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
52 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
158 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
110 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
160 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
122 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
409 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
292 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 ...