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
4
votes
3answers
763 views

Is a function defined as PRF with a given key a PRG?

Let $G(s)=F_{0^n}(s)$ ($ 0^n $ is a fixed key given to the PRF F) for any $n∈\mathbb{N}$ and $s∈\{0,1\}^n$. Is G, defined via PRF as above, necessarily a pseudorandom generator? I presume that it is ...
4
votes
1answer
811 views

Fast crytographically secure Pseudo-Random number generator in software

What are the methods for generating pseudo-random numbers in software? I have seen methods where people use SHA implementations from openssl to hash a random message as source of entropy, or using AES ...
4
votes
2answers
1k 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 ...
4
votes
2answers
914 views

PRG - understanding the definition

Say $G$ is a $PRG$ that expands its input by a single bit, so we define: $$G'(x_1||x_2)=G(x_1)||G(x_2)$$ The exercise states to prove that $G'$ is also a PRG. Now here is my confusion. $PRGs$ are ...
4
votes
1answer
1k views

Attack of the Middle Square Weyl Sequence PRNG

The Middle Square Weyl Sequence PRNG was proposed as illustration of properties of CSPRNGs in this answer (now deleted). This PRNG was introduced by Bernard Widynski in Middle Square Weyl Sequence RNG ...
4
votes
1answer
433 views

How was this Mersenne Twister seed for a 20-character string known a priori found?

Someone generated a seed for the Mersenne Twister, with the intent of that seed producing this string: "9!dlroW ,olleH"ck,@ Which is 20 characters long. Why he ...
4
votes
3answers
384 views

Independent Pseudo Random Generators

Is it sufficient to seed a pseudo-random number generator (PRNG) with two different values to be able to claim that we now have two independent PRNGs? Or is it that we have to use two functionally ...
4
votes
2answers
1k views

Given a pseudorandom function F, is $(F_k(r) \; | \; F_k(r + 1))$ also a PRF?

Given: F is a pseudorandom function, G is a pseudorandom generator with $l(n) = n+1$. The following schemes should be classified as being insecure, IND-COA secure, IND-CPA secure. To encrypt $m \in \{...
4
votes
1answer
2k views

Java's SecureRandom & plaintext attack?

Java's SecureRandom is meant to be cryptographically secure, and I know part of that means that the output should not be usable to predict further output. Though, ...
4
votes
1answer
179 views

Is this a prg: G'(x) = G(x) ⊕ (x || 0^(l(|x|)-|x|))

This is not homework, but a question from an exam. Let $G(x)$ be a PRG with expansion parameter $\ell(n)$. $$G'(x) = G(x) \oplus (x \mathbin\| 0^{\ell(|x|)-|x|})$$ where $\ell(|x|) = |G(x)|$ My ...
4
votes
1answer
382 views

Identifying the type of algorithm for a PRNG that uses modular multiplication and addition

GNU libc uses the following pseudo-random number generator: $$(\mathit{state} \times 1,103,515,245) + 12,345 \pmod {2^{31}}$$ where state is the result of the previous call to the generator. My ...
4
votes
2answers
631 views

Prefix property for variable length pseudo-random generators

I'm currently working through Katz & Lindell's Introduction to Modern Cryptography. In section 3.4.2, they introduce the definition of a variable output-length pseudorandom generator $G$. The ...
4
votes
1answer
3k views

Perfect Secrecy -> One Time Semantic Security -> Secure PRG

I think I have some sense of what Perfect Security means, and even Semantic Security, but I am struggling with randomness, so I'm going to ask a question about CSPRG's (Cryptographically Secure PRG's) ...
4
votes
2answers
282 views

What are usable entropy sources in a headless machine without /dev/random or any cryptography API?

If I have a headless machine (no mouse movements, no keyboard presses, or user input), without any cryptography CSPRNG APIs, where can I collect entropy from?
4
votes
1answer
342 views

Can future Bitcoin hashes be considered a good source to generate random numbers?

There are a lot of miners trying to calculate the next valid SHA-256 hash using random strings, so can I consider that generated hashes have good randomness? How can I prove it? For example, use the ...
4
votes
1answer
1k views

Why is pseudorandom OTP (P-OTP) IND-CPA insecure

My lecture notes state that P-OTP is IND-COA but not IND-CPA insecure. I understand IND-COA secure, assuming PRG is secure, as that is the whole point of a OTP, but why is it IND-CPA insecure? Surely, ...
4
votes
1answer
279 views

Reverse Java random seed using 81 calls to nextInt with a bound of 4?

I'm trying to reverse the Java random seed using 81 calls to nextInt(bound) with a bound of 4. I am wondering if it is at all ...
4
votes
1answer
661 views

Golomb's Randomness postulates

In Handbook of applied cryptography, Golomb's randomness postulates are given: Let $s$ be a periodic sequence of period $N$. Golomb’s randomness postulates are the following. R1: In the cycle $s_N$ ...
4
votes
2answers
379 views

identify if the functions are pseudorandom generator?

Given a pseudorandom generator (PRG) with $G(x) = y_{1} || y_{2}$, where $y_{1}$ and $y_{2}$ are n-bit strings. $G'(x) := G(y_{1}) || G(y_{2})$. Is $G'(.)$ still a PRG? I am guessing it's a No because ...
4
votes
2answers
655 views

MacOS doesn't support PRNG reseeding?

While researching the topic of random number generation, especially practical aspects of using TRNG devices on different platforms, I found this code in MacOS kernel sources. ...
4
votes
2answers
733 views

Pseudorandom function of different keys

Could someone explain to me how they formulated the equation and how it equals to $0^{n}$ (like what F(x, x) equals to or how they cancel each other out?) on the first box and if its related to the ...
4
votes
1answer
158 views

A hash-based pseudorandom function

Let $H()$ be a cryptographic hash function. Question: Can we consider $c= H(r||i)$ as a pseudorandom value, where $i$ is a public value, $1\leq i\leq n$, and $r$ is a large uniformly random value/...
4
votes
1answer
721 views

Is a one-way function pseudorandom?

For one-way function $f$ I understand that $g(x)=0^{n}\mathbin\|f(x)$ is a one- way function with respect to $2n$, where there is $n$ bits of $0$ in the beginning and the output of $f$ in the second ...
4
votes
1answer
215 views

Self-shrinking generator

A self-shrinking generator is a LFSR sequence processed with an algorithm that is different from von Neumann unbiasing. Does this imply that using von Neumann unbiasing instead would lead to an ...
4
votes
1answer
183 views

Cryptographic pseudo-random generation of address subsets

Suppose I have devices which broadcast, on an insecure channel, 32-bit addresses. I want to make these devices untraceable - one way to do so is to allocate for each device a distinct subset of ...
4
votes
2answers
1k views

Is $G$ a secure PRG?

Is the following function a secure PRG? Given $F$ is a secure PRG and $k$ is choosen random from key space $K$. $$G(x) = F(k,x) \oplus F(k,x \oplus 1^s)$$ My solution is $x \oplus 1^s = x'$ ...
4
votes
1answer
176 views

Necessary conditions for construction of $n$ to $p(n)$ pseudorandom generators from $n$ to $n+1$ generators?

Given a polynomial time deterministic algorithm $G_1:\{0,1\}^n \rightarrow \{0,1\}^{n+1}$, consider the function $G:\{0,1\}^n \rightarrow \{0,1\}^{p(n)}$ constructed as follows: Let $s \in \{0,1\}^n$ ...
4
votes
1answer
145 views

Security properties of an encryption scheme built from a PRP and a PRG

Note: This was my in-class problem last week and potentially will be on the exam tomorrow. Thus, I want to reconfirm my thoughts so that I'll be ready to face this type of question (if appear) ...
4
votes
1answer
427 views

If a PRG is constructed by iterating a PRF, is it backtracking-resistant?

Say we construct a pseudo-random generator from a pseudo-random function $f$ (using some constant key $k$ and some initial value $v_0$). We do this by feeding the output block of the PRF back into the ...
4
votes
1answer
677 views

Cryptographic random numbers for key generation

I am trying to understand how a cryptographic library works (for example, one that provides assymetric encryption such as RSA), but I'm running into a few problems about the key-generation. There are ...
4
votes
1answer
167 views

Does Linear Cramer-Shoup have pseudo-random ciphertexts?

"Linear Cramer-Shoup" is defined on pages 4 and 5 of $\:$ eprint.iacr.org/2007/074.pdf . Are the ciphertexts in Linear Cramer-Shoup computationally indistinguishable from uniform under a chosen-...
4
votes
0answers
207 views

is a MAC defined by a pseudo random generator secure?

Let $ G:\{0,1\}^*\rightarrow\{0,1\}^*$ be a length doubling PRG, and let $ \Pi=(Gen,Mac,Vrfy)$ be the following MAC scheme: $ Gen $ on input $ 1^n$ uniformly samples and outputs $ k\leftarrow \{0,1\...
4
votes
0answers
201 views

Feasible way to check n-dimensional equidistribution of PRNGs

I am currently gathering some test methods and test suites for random number generator qualities, and am a bit stuck at finding something feasible to test for n-dimensional equidistribution. As input ...
3
votes
2answers
2k views

Why is ISAAC not a pseudo random number generator?

I have been accused of confusion over the nature of the ISAAC algorithm. The bulk of evidence suggests that it is a cryptographically strong pseudo random number generator. By bulk I mean the number ...
3
votes
2answers
779 views

Is this simple PRNG secure?

$G$ is a PRNG used in a stream cipher and defined in the following way: G receives $s_0$ as an input, which is a random string drawn from a uniform distribution. The output of step $i$ is $s_i = (s_{...
3
votes
3answers
4k views

When to use /dev/random over /dev/urandom in Linux

In my response to my question "what does the letter 'u' mean in /dev/urandom?" the myths about /dev/urandom page was posted in two comments and an answer. The myths about /dev/urandom page is trying ...
3
votes
1answer
440 views

Practical (and secure) PRGs

Does anyone know if there exists a PRG construction which takes as input an (RSA-sized) integer seed and outputs a fixed number of bits? There are number-theoretic PRGs such as the RSA, Micali-Schnorr,...
3
votes
1answer
4k views

How to prove that the concatenation of two secure PRG is secure?

Given $G:\{0,1\}^s \rightarrow \{0, 1\}^n$ a secure PRG, how can one prove that $G'(k_1, k_2) = G(k_1) \cdot G(k_2)$ is secure ($\cdot$ means concatenation)? In other words, I'd like to show that if ...
3
votes
1answer
611 views

PRNG with a truly random seed?

PRNG (Wikipedia): "The PRNG-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG's seed (which may include truly random values)." My ...
3
votes
3answers
290 views

Usage and limitations of sponge functions for PRNG

This HRNG uses SHA3 as a sponge function (in its device driver) to inflate ots raw source output to many MByte/s. They compare this output rate to the output of other HRNG which don't use a sponge ...
3
votes
1answer
1k views

How does Web Cryptography API produce secure PRNG?

How does Web Cryptography API (eg window.crypto.getRandomValues) produce secure PRNG? Specifications: https://dvcs.w3.org/hg/webcrypto-api/raw-file/tip/spec/Overview.html#RandomSource-interface ...
3
votes
2answers
4k views

If G is a secure PRG and G' is a function of G, is G' secure?

For example: for secure PRG G if I have a G' s.t. G'(k) = G(k)||0, is ...
3
votes
1answer
264 views

Is this a PRF? Fk(x) = G(k⊕x) where G is a PRG

This is not homework, but a random thought. Let $G(x)$ be a PRG. We define the following function: $$F_k(x) = G(k\oplus x)$$ My intuition is that it shouldn't be a PRF but I couldn't come with an ...
3
votes
1answer
274 views

Does there exist a CSPRNG that does not require generating prime numbers, but also does not depend on any other cryptographic primitives?

The following excerpt is taken from the “Cryptographically secure pseudorandom number generator” article on Wikipedia: CSPRNG designs are divided into three classes: those based on ...
3
votes
1answer
831 views

Pseudo-random permutation of a range

I have this set: {0,1,2,3,...,15}. I would like to create a pseudo-random permutation from elements of this set, for example ...
3
votes
2answers
298 views

Are parts of a pseudorandom string also a pseudorandom string?

I am working on an exercise that encrypts a message using only the first $n$ bits of a pseudorandom generator's output $G(k)$, i.e. $F_k(m) := G(k)_{0...n−1} \oplus m$. $k$ is chosen uniformly at ...
3
votes
2answers
1k views

Knowing that $G(s)$ is a PRG, is the following construction $G'(s) = G(s||0)$ a PRG?

I know there already is a very similar question. However, I can't understand why $G'(s)$ is not a PRG. If $G(s)$ is a PRG, then why $G(s||0)$ can't also be a PRG? How can the distribution over $G(s||0)...
3
votes
2answers
1k views

Why is the following RSA PRNG cryptographically secure?

One requirement states that the generator has to withstand the next-bit test. Consider the following PRNG, where we calculate next output $x_i$ via the formula $x_i = x_{i-1}^ e\mod n$. I can see ...
3
votes
1answer
67 views

Can the input to a one way function be pseudorandom?

I know that normally a one-way function takes in a completely random input, but can a one-way function take in something pseudorandom instead of completely random? Will it still be a one-way function? ...
3
votes
1answer
301 views

Stronger security definition of PRG

By the standard security definition of a Pseudo Random Generator, if $G$ is a PRG, then $G'$ such that $G'(0\mathbin\|x)=0\mathbin\|G(x)$ and $G'(1\mathbin\|x)=1\mathbin\|G(x)$ is a PRG. We can build ...

1
2
3 4 5
8