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

0
votes
4answers
29 views

Is XORing a random stream of bytes a secure way to obscure a file?

Long ago I created a very simple program that used the C library's rand method to generate bytes to XOR with the bytes of a file. This was a reversible (just run it through again) method to make a ...
6
votes
1answer
214 views

Is it possible to determine or estimate the period for Blum-Micali PRG?

The Blum-Micali is a cryptographically secure pseudorandom number generator. The construction (from wikipedia): Let $p$ be an odd prime, and let $g$ be a primitive root modulo $p$. Let $x_0$ be a ...
6
votes
1answer
105 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 ...
2
votes
0answers
45 views

Is this PRG secure?

$G$ is a safe PRG in range $\{0,1\}^n\rightarrow\{0,1\}^{n+1}$. Let us define $G'(S)=G(S\oplus G(S)_{1,...,n})$, s.t. $G(S)_{1,...,n}$ is the first n bits of $G(S)$. Is $G'(S)$ a secure PRG? ...
0
votes
0answers
25 views

A question about pseudo random generators with seed that starts with a 0

Given that G is prg, is the following always a prg? G'(s)=G(0•s) I know that if there was a random bit instead of the leading 0 it was a prg, but I don't know about the leading 0. Thanks a lot
6
votes
1answer
65 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
665 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_{...
0
votes
0answers
27 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
29 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 f(...
0
votes
1answer
98 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
67 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
80 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
97 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
176 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: ...
1
vote
0answers
43 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
29 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 ...
1
vote
0answers
61 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) = \operatorname{trunc}...
3
votes
1answer
568 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 |k|...
1
vote
2answers
85 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
46 views
2
votes
1answer
155 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
177 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
113 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
120 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
62 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 ...
2
votes
0answers
71 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 ...
6
votes
1answer
425 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 pseudo-...
6
votes
1answer
182 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
88 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
129 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
84 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
178 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
110 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
289 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
128 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)...
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
182 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 800-...
2
votes
1answer
102 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
84 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
26 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
122 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
79 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
83 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 PRG,...
1
vote
1answer
91 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
201 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
116 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 ...