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 ...

learn more… | top users | synonyms

5
votes
1answer
43 views

How distinct are the meanings of the terms “CSPRNG,” “DRBG” and “stream cipher”?

Are there universal, consensus definitions for the following terms? Cryptographically secure pseudo-random number generator ("CSPRNG") Deterministic random bit generator ("DRBG") Stream cipher ...
4
votes
2answers
615 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 = ...
0
votes
0answers
26 views

Security of $(k, 2k)$-bit generator for small seeds

Here is the problem I am working on for context. I have $\epsilon \le 1 - 2^{-k}$ and $\epsilon$ approaches 1 as $k \to \infty$ but I'm stuck on part c). The $f$ is secure iff there does not ...
0
votes
0answers
25 views

generate unpredictable value with a shared key

Is there any function that taek a key to generate (un)predictable value ? I hope you will more understand more what I mean with this example f take in input an array, a key and a round number ...
0
votes
1answer
92 views

Combining multiple PRGs together

Got some theoretical questions about PRGs to solve (given by lecturer for self-learning, no score involved). Tried to find on the internet but couldn't figure out how to solve them, so I will mention ...
1
vote
1answer
54 views

Is there a password hash function with a human component?

Sort of Related: Is there a cryptographic hash function that can be performed with pencil and paper? One problem with hashing passwords is that the attacker has more of everything it seems. More ...
1
vote
1answer
65 views

Determine whether a given function is a pseudorandom generator/function

I am trying to solve the following three tasks (for exam practice, not as a homework): Define $𝐺 : \{0,1\}^* \rightarrow \{0,1\}^*$ by $G(x_1,...,x_n) = 𝑥_1 \oplus 𝑥_2,𝑥_1,⋅⋅⋅,x_n.$ Prove that ...
0
votes
2answers
80 views

Understanding the distinguisher for a PRG

Given the following definition of a psuedorandom generator, I'm having trouble understanding what exactly the "distinguisher" D is outputting, and when?
3
votes
1answer
159 views

How to clock a linear feedback shift register?

I have some trouble understanding what happens when a LFSR is clocked. I have tried many examples but I do not get the correct result. Can anyone point out my errors? I have the following polynomial: ...
0
votes
0answers
39 views

Symmetric encryption vulnerable when encrypting and decrypting are the same?

To my understanding, symmetric encryption is where encrypting and decrypting data can occur with the same key. It's possible for symmetric encryption that the encrypting and decrypting algorithms are ...
0
votes
0answers
26 views

Uniformly distributed sub-sequences of a main PRG sequence

Let $ g_s $ be a pseudo-random generator that generates uniform distributions of numbers ($s$ : seed) of a fixed bit-size. One wants to compare the pseudo-randomness of certain subsets of elements ...
0
votes
0answers
55 views

Proving pseudorandom generators

Can anyone please help me on how to prove or disprove (by counterexample) whether the following function $G'$ is a PRG (Pseudorandom Generator) given that $G$ is a PRG. $$G'(s) = ...
5
votes
0answers
68 views

Rule 30 Cellular Automaton for Cryptography

Steven Wolfram of Mathematica uses a pseudorandom number generator based on Rule 30 for applications in Mathematica software but I would like to know if a pseudorandom generator based on Rule 30 is ...
3
votes
1answer
510 views

How to prove that a function is not pseudorandom?

I am currently enrolled in a cryptography course, which uses the book by Katz and Lindell. I'm struggling with the exercies which ask for proofs, like the following one: Let G(k) be a PRG with ...
1
vote
2answers
78 views

Continuous stream of strong randomness from limited entropy?

I need a continuous (infinite) strong random generator, but I've only got limited entropy as seed. I know there's already a contradiction there, but I'm looking for a practical approach. Suppose I ...
1
vote
1answer
35 views
2
votes
1answer
152 views

Do any (non-hardware) RNGs exist which could be used to create an OTP for crypto purposes?

I've stumbled (jobwise) over a system where small messages (512 Bytes or less) are encrypted and decrypted using a simple XOR using a OTP. That OTP is created using a seed based on the individual user ...
2
votes
2answers
174 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 ...
3
votes
2answers
110 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 ...
2
votes
2answers
110 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 ...
0
votes
1answer
58 views

What Does This Symbol Mean? (Hardcore Predicates for One-Way Functions)

I am studying Pseudorandom Number Generators and when reading the discussion on One-Way Functions and Hardcore Predicates, I came upon this equation. $$b(x,r)=\displaystyle \bigoplus_jx_jr_j$$ I ...
1
vote
0answers
63 views

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

Say we construct a pseudo-random number 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 ...
5
votes
1answer
414 views

Pseudo random generator vs block encryption, which is faster?

If one wishes to encrypt one can either use a pseudo random generator to generate a long sequence and then xor it with plaintext, similarly he can use the seed as key to encrypt the plaintext using ...
1
vote
1answer
37 views

Deriving a Set of Seeds from a Seed

I need a set of seeds $S=\{s_1,..., s_n\}$, for pseudo-random function where seed $s_i$ is used to generate a set of pseudo-random values. Obviously I need to be able to regenerate the sets of ...
6
votes
1answer
180 views

Can it ever be impossible to invert a PRNG?

I've read about the possibility of inverting the Mersenne Twister after 624 numbers of output. 624 matches the state size of my implementation of the Twister. Coincidence? If the generator only ...
0
votes
3answers
84 views

Computational indistinguishability: are function parameters known?

I would like to clarify something about the definition of computational indistinguishability and pseudorandom number generators. Suppose we wanted to show that linear congruential generators of the ...
0
votes
3answers
110 views

Let $G$ be a PRG. Are the following $G'$ constructions based on $G$ necessarily PRGs?

$G$ is a PRG where $|G(s)| > 2 \cdot |s|$. $G'(s) = G(s0^{|s|})$. $G'(s) = G(s_1...s_{n/2})$, where $s = s_1...s_n$. My question here is whether my own proposed solutions are correct and do ...
-2
votes
1answer
83 views

Shuffleless PRNG function with non-repeating values?

I need a simple PRNG function of type: Integer = PRNG(n, maxval) as I would like to count from 0 to maxval, not in a linear manner, but in a pseudorandom manner where I still use every value, but ...
4
votes
1answer
169 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 ...
1
vote
2answers
104 views

Let $F$ be a PRF, is the following $G(x)=F_{0…0}(x)∥F_{0…1}(x)|| … ||F_{1…1}(x)$ a PRG?

$F$ is a PRF with $n$ bit key, input, and output length. I know the answer is "NO it isn't!", but I can't understand why. Is that because on any input $x$, the keys for every $F$ in the concatenation ...
3
votes
2answers
280 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'$ ...
1
vote
1answer
116 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 ...
2
votes
1answer
75 views

Permuting Small Sized Set in Practice

Imagine we have a set $S$ of $m$ elements and we wants to permutes the set elements. Thus the original position of each element should be unknown after permuting. If we define a permutation function ...
1
vote
1answer
169 views

Where I can find a list of certified software / hardware RNGs compliant to NIST SP 800-22?

I need to use NIST SP 800-22 approved software / hardware to generate RSA key pair. Where I can find a list of certified software / hardware RNGs compliant to NIST SP 800-22? And how is the SP ...
2
votes
1answer
98 views

Are pseudorandom permutation really permutation in mathematical sense?

In security, and specifically Block Cipher (AES, DES, etc), when we talk about pseudo random permutations, is the term "permutation" refer to the same meaning as in discrete mathematics. That is, the ...
1
vote
2answers
82 views

Fortuna: why are source ID and data length added together with entropy data into the pools

Section 9.5.6 of Cryptography Engineering states that The concatenation [of source number, length of data, and data itself] is then appended to the pool. Why are we including source number and ...
0
votes
1answer
25 views

Blinding value of particular form

I'm working with an implementation that creates a blinding value for RW signatures with the following C++ code: ...
-1
votes
2answers
81 views

Improving on a clocked PRNG

I recently developed a PRNG from scratch with a little inspiration from the initialization function used in the HC stream cipher. The state ($S$) of the basic version is an array of 5 bytes and uses ...
1
vote
1answer
113 views

Turning data into seemingly random noise

I am currently working on a python script that does image steganography, altering the least significant bit on each channel of the image. Now imagine encrypting a file with a bunch of null bytes, or ...
1
vote
1answer
78 views

Can a cryptographic hash be used as a cryptographic RNG?

Say I roll a six sided die 200 times (6^200 = ~2^517) and string all the results together into a long string of numbers and hash then result with SHA-512. Can I use that result for cryptographic ...
0
votes
1answer
81 views

Swap $x$ and $k$ in GGM construction

I'm studying the Goldreich-Goldwasser-Micali construction from pseudo-random generators to pseudo-random functions. In this specific construction, assume $G:\{0,1\}^n\rightarrow \{0,1\}^{2n}$ is a ...
1
vote
1answer
88 views

Prove there is PRG that is not necessarily one-to-one

We assume that there is at least one PRG .Now prove there is a PRG like $G:\{0,1\}^{n} \rightarrow \{0,1\}^{l(n)} $ such that it is not necessarily one-to-one.
0
votes
0answers
76 views

Making PRFs out of PRGs

Is it possible that we take a $PRG$ $G(k)$ of stretch $n\cdot2^n$, and read its output as the table of a $PRF$ $F(K)$ with input and output size of $n$? Intuitively it sounds possible however I read ...
2
votes
1answer
178 views

Crypto++: How to re-generate pseurandom integers in Crypto++

I'm using Crypto++ to implement my protocol to mask a value $y_i$ by a seudorandom value $r_i$ such that $m_i=y_i \cdot r_i$. Since there are many $r_i$'s I want to generate them using PRG and then ...
1
vote
1answer
94 views

Pseudorandom function library [closed]

I'm wondering if there is any library supporting pseudo-random function, so I can specify the key length and output domain. Is it correct that I need to use a block cipher for this purpose? Any ...
1
vote
1answer
190 views

PRF based on the GGM construction

What's the differences between the concepts “pseudorandom generator” and “pseudorandom number generator”? In fact, I want to implement a pseudorandom function based on GGM's construction at ...
1
vote
1answer
556 views

Is there a kind of OS entropy pool on Windows systems? [closed]

I am wondering if Windows provides an equivalent of /dev/urandom from linux ? Or any kind of system entropy pool ?
1
vote
3answers
333 views

Can you help me with this Random Number Generator function?

By someone's suggestion, I am posting this question from math.stackexchange.com. I want to find out a suitable function or algorithm, which can provide a random sequence like this… Input: $3$ ...
2
votes
0answers
250 views

Difference between statistical PRNG and cryptographic PRNG? [duplicate]

What's the difference between a statistical pseudorandom number generator (PRNG) and a cryptographic-strength PRNG? I've seen a lot of PRNGs that are proposed for statistical uses -- e.g., ...