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.
553
questions
0
votes
0
answers
13
views
Error running dieharder input file for rng output [closed]
I am trying to run a ascii input file but I keep getting the following error:
# file_input(): Error. File type is not recognized.
I'm not able to find out what ...
3
votes
0
answers
69
views
Deriving a cryptographic PRNG from a publicly random sequence
Consider a model of computation where we have a public oracle that provides access to a random sequence $R$. Given an index $i$ the oracle returns either 0 or 1, with the responses being deterministic,...
3
votes
1
answer
857
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
0
answers
37
views
Proof for embedded composition of PRG's
I have two secure pseudorandom generators, $G_1 : S\rightarrow R, G_2 : R\rightarrow T$. Now I need to prove that the PRG $G_3(s) = G_2(G_1(s))$ is secure.
I figured that I would construct two ...
2
votes
0
answers
54
views
Inefficient double-lengthening PRG
I'm trying to prove that an inefficient double-lengthening PRG exists, i.e. construct a PRG $G: \{0,1\}^n \rightarrow \{0,1\}^{2n}$
My current approach is to bound the number of poly-time non-uniform ...
17
votes
5
answers
3k
views
Is a PRG more costly than AES or any other encryption standard?
I know that there are many encryption standards that take a key and sometimes an IV to produce a cipher-text (the most prominent one is AES). These standards usually involve many rounds of addition ...
0
votes
0
answers
53
views
Reversing a Floored Xorshift128+
We suppose that we have N consecutive numbers generated by JavaScript using: math.floor(math.random()*multiple), knowing that ...
1
vote
0
answers
52
views
Let $l' > l > 0$. Construct a PRG that would transform any PRG of stretch $l$ into one of stretch $l'$
The way I understand this question is that we have a secure PRG G: $\{0,1\}^\lambda \rightarrow \{0,1\}^{\lambda + l}$, and we want to use it to make a secure PRG G' : $\{0,1\}^\lambda \rightarrow \{0,...
1
vote
2
answers
96
views
Relation between seed entropy of a CSPRNG and the output entropy
Since Linux 5.18, the internal state of the ChaCha-based CSPRNG is a 256 bits (32 bytes) BLAKE2s hash. There is also a fast key erasure mechanism which reseeds the CSPRNG every minute (source).
I know ...
2
votes
1
answer
57
views
Interpretation of the Result of Dieharder Battrery of Tests: Very High p-value Result in rgb_lagged_sum Test in Dieharder Results in "WEAK" Assesment
I'm currently testing the randomness of using SHA-256 in Hash_DRBG mechanism based on this research. The parameters used in the testing are the default parameters, except for when the PRNG fails a ...
2
votes
1
answer
156
views
How many encrypted messages can we know, so that scheme is secure?
Let $G$ be a secure PRG and let $s$ be a private key. We can define $\mathrm{Enc}(s,m) = G(s)\oplus m$. As long as we know only one encrypted message this scheme is secure, since $G(s)\oplus m \sim r\...
0
votes
1
answer
79
views
Custom linear random number generator
I've made an implementation of a linear RNG. It has two constants: b and p. Every time new value of ...
0
votes
0
answers
75
views
Possible MAC design
The problem
Let the following be a family of PRF functions with key length $2\lambda$
$$\mathbb{F} = \{F_k:\{0,1\}^n\rightarrow\{0,1\}^n\}_{k\in\{0,1\}^{2\lambda}}$$
Assuming one way functions exists, ...
3
votes
3
answers
185
views
Where are TRNGs an absolute need?
Are there situations currently where a PRNG just will not do? Are there current situations where only a TRNG will be useful?
What about if someone uses a cryptographically secure PRNG?
What is the ...
0
votes
0
answers
170
views
Is the following hash function construction collision resistant?
The problem
Let the following function be a collision reisistant hash function
$$H=\{H_s:\{0,1\}^{2n} \rightarrow \{0,1\}^{n} \}$$
Let the following function be a PRG
$$G:\{0,1\}^{n+1} \rightarrow \{0,...
2
votes
2
answers
309
views
Randomized functions cannot increase statistical distance
In these lecture notes instructor Chris Peikert states the following lemma without a proof
Let $f$ be a (randomized) function on the domain of $X$, $Y$. We have
$\triangle (f(X), f(Y)) \leq \...
1
vote
1
answer
123
views
My new PRNG (PaulssonSponge) with dieharder tests
I run an open source project implementing some RipeMD and SHA hashes, one day I got nerdy and threw together my own Sponge function. I have now tested it with the dieharder 3.31.1 test suite. Is it ...
0
votes
1
answer
129
views
Discrete Fourier transform (Spectral) test
I am designing a pseudo random bit generator (PRBG) and I am using the NIST SP 800-22 suite to analyze the random characteristics of my PRBG. It turns out that my PRBG passes 14 out of 15 tests, and ...
9
votes
4
answers
3k
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 ...
0
votes
1
answer
174
views
How do bad actors manipulate game results in real time within 'provably fair' gaming systems?
Ive been assigned research involving online gaming companies and their use of cryptographic algorithms to produce 'provably fair' results. The largest player in the industry uses a method involving a ...
3
votes
1
answer
231
views
RSA/ ECC keygen HW vs SW
i have a pretty straightforward question but i can’t seem to find an answer :
Regardless of the physical protection provided by an HSM or TPM or any hardware cryptographic key storage system, are keys ...
0
votes
0
answers
69
views
Article explaining Fortuna algorithm
Does anyone know an article that explains Fortuna algorithm for people without cryptographical background? If not, I would like to have an explanation because I don't manage to understand it.
4
votes
4
answers
3k
views
Given PRNG $G(s)$, why is $G(s) || G(s+1)$ not a PRNG?
I have given a pseudorandom Generator $G(s)$, $|s|=n$ whose expansion $l(n)$ is $>2n$. I also know that $G^\prime(s) := G(s_1,\ldots,s_{\lfloor\frac{n}{2}\rfloor})$ is a pseudorandom generator. Now ...
1
vote
2
answers
77
views
Should I Test A PRNG Using A Fixed Entropy Source For Its Seed?
I want to test a C implementation of Hash_DRBG—which test_demo.c file I will modify to produce random binaries indefinitely to STDOUT as to be used by piping its output—using DIEHARDER for a research. ...
2
votes
1
answer
92
views
Consecutive ones in a PRG
I'm trying to solve this problem.
I tried this. Consider distinguisher $D$ such that
$D(c) = \begin{cases} 1 & \text{If there is at least $2\log_2n$ consecutive 1's} \\
0 & \text{o.w.} \end{...
1
vote
2
answers
175
views
Suppose $F_s$ is a PRF. Is $F'_s(x)=F_x(s)$ also a PRF?
Suppose $F_s$ be a family of keyed pseudorandom functions. Define $F'_s(x)=F_x(s)$. Is $F'_s$ a family of pseudorandom functions? It seems false but I am able to give a proof assuming $F$ is ...
1
vote
3
answers
3k
views
Is it possible to compress a random sequence with high entropy?
I have an algorithm that generates a pseudorandom sequence with a length of 100k and high entropy. I would like to check the quality of its randomness. So, I used a popular software program to ...
0
votes
1
answer
77
views
KangarooTwelve based Random-Access PRNG
Can the KangarooTwelve Keccak-p[1600,12] be used to create a CSPRNG in which there is random access to an element (or a small group of outputs) of the generated list (instead of sequential generation)?...
0
votes
0
answers
65
views
Security of the trivium stream cipher
So I've been trying to implement a Non-Deterministic RBG based on randomness polling from non-hardware sources (nothing novel, just a side-project). Since collecting entropy and further conditioning ...
4
votes
3
answers
659
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 ...
0
votes
0
answers
143
views
Proving that a PRG is insecure
I'm trying to show that the PRG $G$ defined as below is insecure for any binary matrix $A$.
\begin{align}
A&: m\times n& (n < m)\\
s&: n\times 1\\
G&: \{0, 1\}^n\rightarrow\{0, 1\}^{...
1
vote
0
answers
155
views
If G is a PRG, is G' necessarily a PRG?
Given:
A function $$G: \{0,1\}^{3n} \to \{0,1\}^{6n}$$ which is known to be a secure Pseudorandom Generator (PRG).
A derived function $$G'(x_1 \| x_2) = G_b(x_1\|0^n\|x_2), \text{ where } x_1, x_2 \...
0
votes
1
answer
89
views
Does ISAAC really guarantee a cycle length of at least 2**40?
I just noticed that the FSE 1996 conference paper which defines ISAAC mentions a counter variable cc.
This variable is said to be the reason why ISAAC has a ...
1
vote
0
answers
84
views
Pseudo random generator notation
So I'm reading this article where they talk shortly about pseudo random generators where I'm not quite familiar with some of the notation. They call $\lambda$ the security parameter.
"...
2
votes
0
answers
66
views
Is ISAAC+ actually an improvement over ISAAC?
I just tried to implement ISAAC from scratch, using the Jean-Philippe Aumasson paper from 2007 as a reference.
This paper gives a definition of the original ISAAC algorithm as well as the improved ...
4
votes
1
answer
1k
views
Why do Mersenne Twister use Mersenne prime but not regular prime numbers
I'm trying to figure out why Mersenne Twister use exactly Mersenne prime numbers but not regular primes. What makes Mersenne prime numbers more appropriate for this role than regular primes?
1
vote
0
answers
82
views
Trouble interpreting CTR_DRBG test vector results
I've implemented a CTR_DRBG random number generator according to NIST SP 800-90A Rev. 1 and I am now testing it with test vectors provided in NIST CAVS 14.3 (drbgvectors_no_reseed\CTR_DRBG.txt).
...
0
votes
0
answers
73
views
Distinct sequences in a Fibonacci LFSR
How many distinct sequences can a $128$-bit Fibonacci LFSR (considering $4$ taps set for the maximum period) generate? Will all $2^{128} - 1$ distinct seeds produce distinct sequences?
Also, let's say ...
1
vote
1
answer
105
views
Can this algorithm be called a RNG?
So I developed this algorithm as RNG, although it looks random to me, I wanted to know the opinion of more experienced persons in the topic.
...
0
votes
2
answers
138
views
From Entropy's perspective how Encryption affects a Message?
How Ciphers, specifically, Substitution Ciphers and Transposition Ciphers manipulate the Entropy of Plaintext w/wo the aid of Entropy Source?
Reversely, how Decryption manipulates the entropy of ...
5
votes
1
answer
133
views
Cryptanalysis of the GOC
The GOC (Générateur d'Octets Chiffrants, Ciphering Byte Generator) is a PseudoRandom Generator that was used during the late 20th century for content encryption in pre-internet Videotex terminals, ...
0
votes
1
answer
891
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
2
answers
2k
views
How to generate n unique numbers from the output of a hash function?
What would be an easy way to use the hexadecimal output of a hash function (like md5) to generate n unique numbers from, say 0 to 15. Of course I could generate n ...
27
votes
10
answers
12k
views
Can an AI really generate random numbers?
I asked an AI the following question:
Can you provide me with random numbers of 30 digits in length?
And then the AI has generated these numbers for me.
...
2
votes
2
answers
530
views
What is the difference between a seeded RNG and an XOF hash?
Suppose I have some ZK proofs that were turned non-interactive using Fiat-Shamir heuristic. So I need to generate the challenge value deterministically using some data shared between the prover and ...
0
votes
1
answer
59
views
Output a pad (un-keyed, variable length) from an input seed (fixed value for same seed)
I want a function $y = f(x, len)$:
$x$ is the seed. $y$ is the output. $len \in \mathbb{Z^+}$ is the length (bytes) of $y$
Select a seed string $x$ to generate a string $y$.
For each same pair of $x$ ...
2
votes
0
answers
47
views
Deterministically secure PRG from deterministically secure OWF
Consider the construction of "A Pseudorandom Generator from any One-way Function" [HILL99] in Hastad et al.
One way to proof pseudorandomness of this construction is by contradiction.
That ...
4
votes
2
answers
144
views
Is there a standard for LFSRs to test against for use in a stream cipher?
I am trying to implement a stream cipher that uses an LFSR PRNG. I have found resources online that give good primitive polynomials, but I am struggling to find resources with the initial states as ...
0
votes
0
answers
54
views
Can I skip ahead with a quadratic congruential generator?
I have a congruential generator where
$$
r_{n+1} = r_n^2 - c\;(mod\;p)
$$
known $r_0$, $c$ and $p$ can i get $r_n$ without having to compute all the previous values?
0
votes
1
answer
71
views
RFC: Approach to CSPRNG
I've been experimenting in python with different approaches to cryptographically secure pseudo random number generators, comparing them using the NIST testsuite implemented by https://github.com/...