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.
538
questions
-1
votes
0
answers
37
views
Suppose G1(s), G2(s) are PRGs that output elements in {0, 1}n. Then show that G1(s1) ⊕ G2(s2) is a secure PRG if either G1 or G2 is secure
I am trying to solve this numerical but I have difficulty to solve.
I search every where but I didn’t any solution related to it.
Can anyone write me the solution for this?
3
votes
1
answer
217
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 ...
- 51
0
votes
0
answers
56
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.
1
vote
2
answers
59
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. ...
- 13
1
vote
1
answer
89
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{...
- 13
1
vote
2
answers
142
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 ...
- 11
0
votes
0
answers
53
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 ...
0
votes
0
answers
104
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\}^{...
- 11
1
vote
0
answers
141
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 \...
- 11
1
vote
0
answers
80
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.
"...
0
votes
1
answer
86
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 ...
2
votes
0
answers
48
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 ...
1
vote
0
answers
67
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).
...
- 23
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?
- 409
0
votes
1
answer
63
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)?...
- 1
0
votes
0
answers
64
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
96
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.
...
- 13
0
votes
2
answers
131
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 ...
- 153
5
votes
1
answer
122
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, ...
- 138k
2
votes
2
answers
1k
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 ...
2
votes
2
answers
489
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 ...
- 289
2
votes
0
answers
42
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 ...
- 161
0
votes
0
answers
47
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?
- 1
0
votes
1
answer
63
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/...
- 1
0
votes
1
answer
52
views
Regarding: Pseudorandomness, Pseudorandomgenerators and Padding
Hey there guys and gals,
so I am right now studying topics regarding pseudorandomness.
I was wondering why, for example with CBC-MAC oder a regular CBC blockcipher, we use padding instead of a PRG. ...
- 15
0
votes
0
answers
34
views
PRFs with long outputs and short keys
Assume I have a PRF $F$, with polynomial key length $s_{F}(n)\geq n$, and output length $l(n)$.
I need to construct a PRF $F'$, with key length $s_{F'}(n)=n$ and output length $l(n)$.
I thought about ...
2
votes
1
answer
135
views
Is Python secrets module using a unsafe RNG on Windows?
The Python secrets module claims to produce cryptographically secure random numbers. I did some research on which random number generator is used when you call the secrets module on Windows. I found ...
- 221
2
votes
0
answers
49
views
Is it possible to craft a valid AES-CBC cipher-text that will decrypt (to random) with any possible key?
I am mainly looking to perform this trick for fun. I have access to an API that uses WebCrypto under the hood for encrypt and ...
- 21
4
votes
2
answers
119
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 ...
- 91
1
vote
1
answer
54
views
Existence of PRGs satisfying the following weaker definition
Consider the following definition. Let $p(n) > n$ be a polynomial, and $G_n: \{0, 1\}^n \rightarrow \{0, 1\}^{p(n)}$ a PRG. Moreover, given $x \leftarrow \{0, 1\}^n$, we say $S$ is a length $n-1$ ...
- 526
1
vote
1
answer
87
views
Use of PRNG's vulnerability for attacking a cryptographic system
I am investigating a PRNG which fails some of NIST tests (FFT, ApproximateEntropy and Serial). If such a generator is used in cryptography for any purpose, what consequences can it has? How this ...
- 11
1
vote
1
answer
124
views
Increasing the stretch of a PRG
Consider a function $G:\{0,1\}^*\to\{0,1\}^*$ with output size double it's input size, that is $\forall x\in\{0,1\}^n,\ |G(x)|=\ell(n)=2n$. Assume $G$ is a PRG in the sense of Jonathan Katz and Yehuda ...
- 138k
1
vote
0
answers
103
views
Can a one-way permutation be used to stretch a pseudorandom generator?
Consider a secure PRG $G:\{0,1\}^\lambda \to \{0,1\}^n$ and a one-way permutation $f:\{0,1\}^{n-\lambda} \to \{0,1\}^{n-\lambda}$. I'm wondering if the following construction $G': \{0,1\}^\lambda \to \...
- 11
1
vote
2
answers
159
views
State recovery algorithm for Xorshift128 given modular outputs
I am researching the Xorshift128 PRNG. I am particularly interested in recovering the state given a set of outputs that have the remainder taken with different values.
A common way to take a unsigned ...
- 11
6
votes
1
answer
143
views
What's the current status of development of hedged ECDSA and EdDSA?
In the IETF Draft Deterministic ECDSA and EdDSA Signatures with Additional Randomness, methods had been specified to seed RNG deterministically with external input, to securely obtain a nonce for use ...
- 9,001
1
vote
0
answers
38
views
How did the VB6 PRNG generate a byte output from a specific seed, and how to replicate in C? [closed]
I'm hoping to get some help regarding an old problem that has eluded me. I'm trying to figure out how the VB6 PRNG was used to generate a byte output from the two byte seed that the Randomize() ...
- 11
1
vote
1
answer
71
views
Can the last n bitcoin blocks (including transactions) be reliable enough to be used as a seed for a PRNG or an input to a crypto hash-function?
Suggested by u/HolgerBier on reddit
Is it unpredictable enough or too difficult to manipulate (as in more than a few hundred million USD) to have a sequence of blocks?
1
vote
0
answers
51
views
What are some ways to produce a pre-determined sequence of a large number of dice rolls? [closed]
What are some ways to produce a pre-determined sequence of a large number of dice rolls (on the order of 100-1000 times) using biased dice or a biased human roller given the constraints that multiple ...
27
votes
10
answers
11k
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.
...
- 381
3
votes
1
answer
116
views
What is the result of not connecting the 1st register to the xor gate in LFSR?
I designed 8 bit lfsr in vhdl. According to mathematical theory, I xor processed the outputs of registers 1, 4, 5, 6 and 8 and connected them to the input of register 1. theory says that if I give the ...
1
vote
0
answers
105
views
Is every pseudorandom generator a one-way function, even if the output length has no extra restrictions?
Intuitively, if we can invert a PRG, then we can easily distinguish it with random distribution by checking g(inverse(y)) = y. So every PRG is a OWF?
Unlike the problem "Is every pseudorandom ...
- 21
3
votes
1
answer
281
views
Fast and secure pseudo random generator with Linux tools
The conventional and simple wisdom is to combine head with /dev/urandom to create the amount of pseudo-random data that is ...
- 131
3
votes
0
answers
75
views
Proving that a PRG is predictable
I am attending the video lectures from Prof Dan Boneh. He gives the following example.
Let $G:\mathcal K\longrightarrow \Bbb Z_2^n$ be a PRG with the property that from the last $\frac{n}{2}$ digits ...
- 206
3
votes
0
answers
147
views
Why: $G'(s) = G(s_1, \ldots, s_{\lfloor{n/2}\rfloor})$, where $s = s_1, \ldots, s_n$ is PRG?
I'm a novice reader of Introduction to Modern Cryptography, where it states:
Let $G$ be a pseudorandom generator with expansion factor $\ell(n) > 2n$.
In each of the following cases, say whether $...
- 43
0
votes
1
answer
67
views
Is there a way to make a pseudorandom function to generate decimal numbers in a specified range and not only producing big ones?
When I try to generate decimal numbers in the range 0-18446744073709551616 using a hash function I always get big numbers like this:
...
- 379
3
votes
0
answers
80
views
Hybrid Argument proof
I am trying to understand what the Hybrid Argument is in cryptography and why is it useful.
By the definition of the Hybrid Argument we know that to prove that if two distributions $D = D_1, D_2, ...,...
- 103
1
vote
0
answers
48
views
Public seed expansion for uniform reference strings
Many cryptographic protocols are parameterized by a uniformly random reference string (e.g. the commitment key for Pedersen commitments).
Our goal is to publicly generate the random values of this ...
- 357
2
votes
1
answer
49
views
A random access machine with lots of random data on its tape is a stronger assumption than the existence of OWFs
Suppose we have a random access machine with $(n+1)2^n$ random bits on its tape. This assumption is weaker than assuming the existence of a random oracle, but using this assumption we can construct a ...
- 526
2
votes
1
answer
123
views
Any simple, cryptographically secure AES-based DRNG?
I am looking for a DRNG/DRBG (cryptographically secure) algorithm/function (which I can program into js). I am looking to use a DRNG as a seed generator for generating multiple, identical AES keys on ...
- 45
2
votes
1
answer
175
views
Let $G$ be a PRG. Establish whether the following PRG candidates $G^{'},G^{''}$ are secure or not
Let $G:\{0,1\}^n \leftarrow \{0,1\}^{2n}$ be a PRG. Establish whether the following PRG candidates $$G^{'},G^{''}:\{0,1\}^n \leftarrow \{0,1\}^{3n}$$ are secure or not:
$G^{'}(s)=(x⊕y,u,v)$ where $(x,...
- 33