Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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

-1
votes
0answers
21 views

Which Approach is Better in Pseudorandomness - Asymptotic or Concrete? [on hold]

When to prefer these 2 approaches over each other and which one is more secure.
4
votes
1answer
132 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 ...
0
votes
0answers
8 views

Pseudonymization (with restoring): Keeping the data format

I want to make a software for pseudonymization of family pedigrees (GEDCOM files in particular). I want to replace the persons names with some other names and certain dates (birth, death) with other ...
0
votes
5answers
142 views

Pseudorandom number generator for which it is impossible to deduce the seed

I'm looking for an RNG that in the case that an attacker would get all or part (most likely part) of the pseudorandom data, there will be no way for them to deduce the original seed more efficiently ...
0
votes
1answer
79 views

Can we use Pohlig-Hellman Exponentiation Cipher with a PRG to achieve an oblivious PRF

The Commutative Cipher Setup Alice and Bob agree on a 2048-bit safe-prime $p$, where $(p-1)/2$ is also a prime. Both parties have an encryption exponent $e$ in the range $(1, p-1)$ with $gcd(e, p-1) =...
3
votes
1answer
74 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 ...
3
votes
3answers
127 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 ...
1
vote
2answers
129 views

mapping a 256 bit random number to a 3 bit number

I am making a 2 player dice game that runs for n rounds. To create random dice roles im using a concept a understood from randao. each user generates n sha3 hashes recursively of a random seed : e.g. ...
1
vote
0answers
35 views

How Are Linear Congruential Generator Multipliers Chosen?

There are several numbers that keep coming up when looking at certain random number generators, for example 6364136223846793005 is used in newer pcg-family algorithms and seems to draw it from ...
1
vote
1answer
59 views

prove PRG is secure assuming DDH holds

Let $\Bbb{G}$ be a cyclic group of prime order $q$ generated by $g \in G$. Let $G$ be a PRG defined over $(\Bbb{Z}_q^2, \Bbb{G}^3)$ such that: $G(a, b) = (g^{a}, g^{b}, g^{ab})$ How can I show ...
2
votes
1answer
58 views

Unbalanced Feistel network only generates complete permutations with square lengths

I'm generating permutations with a generalized Feistel network which will output integer values $r_j$ in a specified range $[0,period]$ pseudo-randomly, according to the counter input, which will then ...
0
votes
2answers
50 views

Technical term for hash value being uncorrelated to input message?

Is there a technical term for the desirable property of hash functions. That a small change to the input message will produce a massive unpredictable and seemingly uncorrelated change to the output ...
0
votes
1answer
78 views

How to prove a function is negligible?

My question essentially concerns how to prove if a function is negligible. As a matter of fact, though this question might seem very basic, it seems that most of the "proofs" of negligible concern ...
3
votes
0answers
158 views

Finding the cycle sets of an LCG

My LCG has the form: $$S_0 = k$$ $$S_{n+1} = S_n \times a + 1 \pmod m$$ Each choice of $k$ generates a different sequence but in some cases a sequence may just be a cyclic shift of another. In this ...
4
votes
1answer
106 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 ...
1
vote
1answer
84 views

Proof that pseudo-random generated key is semantically secure

Let $G: \{0,1\}^s \rightarrow \{0,1\}^r$ where $r > s \;$ be a secure pseudo-random generator. Let $\xi = (E,D)$ a semantically secure cipher whose key space is $\{0,1\}^r$ Let $\xi' = (E',D')$ ...
3
votes
1answer
96 views

Breaking variations of Linear Congruential Generators

So I have been trying to learn a bit of cryptanalysis and breaking pseudorandom generators as of recently, but I have run into a roadblock in my learning as I cannot crack this one problem. Basically ...
0
votes
1answer
250 views

Decryption of a file encrypted by pseudo-random number generator (The Linear Congruence rand()

How to decrypt this file: https://drive.google.com/open?id=1gZCujDYmEL-FZ5o_xBUS-Ng5979HSsZ7 Given that the only information available about it are: It has been created ‎on 21/3/‎2018, ‏‎9:05:15 AM ...
-1
votes
2answers
118 views

Secure pseudo-random generator

Suppose that $G : \{0,1\}^k \rightarrow \{0,1\}^{2k}$ is a secure pseudo-random generator. Describe what is wrong with each of the following attempts to build a pseudo-random generator with $k$-bit ...
1
vote
1answer
90 views

Why is the rand() function in C not a cryptographic pseudo-random generator?

For example, one of the possible rand() implementations: ...
1
vote
1answer
71 views

Stateless and deterministic number generation

I want a stateless deterministic pseudorandom generator. Following number generation is deterministic, whenever I give $constantValue$, and index it will value $A$ $A = Hash(constantValue + index)$ ...
0
votes
1answer
51 views

Does a concatenation of hashes of differently prefixed variations of any chosen message contain all possible finite bitstrings?

Let $A$ denote a sequence of bits. Let $H$ denote a cryptographic hash function that has no limit on the length of its input (for example, SHA-3). Consider the following infinite sequence of ...
-1
votes
1answer
87 views

Random number generator in a 2p2 Network

for my thesis I am trying to develop a system where nodes from a peer to peer network agree in generate a random number every tot seconds. I am stocked in this problem since almost 1 week anyone can ...
1
vote
1answer
173 views

Is there any ECDSA Attack if I have millions of signatures?

I have been given the task to test the security of our company software. Our company software generates ecdsa signed supply order files. One can generate as many files as he wants. so my question is ...
9
votes
2answers
238 views

Which symmetric encryption systems, pseudorandom number generators, and hash functions are best suited for reversible computers?

Reversible computing refers to the type of computing where one minimizes the the amount of data to be deleted usually to save energy (Reversible computing could also thwart side-channel attacks). ...
1
vote
3answers
104 views

What’s the difference between a secret key and a seed?

I always hear that if you have the seed then you can easily obtain the key. So, is the secret key just typically an expanded version of the seed? If so, via some key derivation algorithm? Also, if ...
10
votes
2answers
1k views

What is the relation between the existence of a cryptographic hash function and the existence of a PRG?

Does the existence of a PRF/PRG/one way function imply the existence of a hash function? I did not find a proof of the existence of a cryptographic hash function, so I want to know whether it is based ...
1
vote
0answers
118 views

Assume G(s) is a PRG, is the following also a PRG?

Let s be a n-length binary word and not_s its negation. Let G be a PRNG with expansion 2n. Prove that H1(s) = G(not_s) is also a PRG? Prove that H2(s) = G1(s)||G2(not_s) is also PRG. Given ...
3
votes
3answers
137 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 ...
0
votes
0answers
208 views

how decryption takes place in aes-256-cbc ,where encryption done by random keys?

if encryption takes place by using random keys in CBC then how it will decryption done with a randomly created cipher text
1
vote
1answer
87 views

Pseudorandom Generator Behavior

Assume I have an encryption scheme $E(k,m) = (P(k,r), G(r) ⊕ m) $ and given that $G$ is a PRG , $P$ is a PRP and $r$ is a random n-bit nonce. My question is: If I run this encryption twice with ...
3
votes
1answer
79 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) ...
11
votes
2answers
2k views

Is it possible to recover the seed used by Python's pseudo-random number generator?

I generated some random numbers using a Python script. I have the first 40 numbers of the sequence. Is there a way to recover the seed or find the next 460 numbers in the sequence? The numbers were ...
0
votes
0answers
34 views

Period Calculate in Blum

I looking for help with the question: Let $$p_1=(p-1)/2$$ $$q_1=(q-1)/2$$, and u be the order of 2 modulo $p_1$, v the order of two modulo $q_1$. Set $t=\text{lcm}(u,v)$. Prove the period of Blum-Blum-...
1
vote
1answer
153 views

is the XOR of PRG outputs a PRG?

I am going through the course http://u.cs.biu.ac.il/~lindell/89-856/main-89-856.html, as it has a good lecture notes. I found exercise 2 solution a puzzling statement: it says that $G^\prime (x_1 , ...
1
vote
1answer
308 views

Prove that pseudorandom generator is a one way function

Suppose the following PRG $G : \{0,1\}^n \rightarrow \{0,1\}^{n +l}$, I want to prove that $G$ is one way function (and not building one), for: $l = \omega (\log n)$ $l = 1$ For $l = \log n$, ...
0
votes
0answers
38 views

Chain addition until repeat formula

So using chain addition to produce pseudorandom integers. e.g. 10 produces 11 23 58 another 26 cycles ... 10 Given the above, how do I ...
1
vote
0answers
82 views

Pseudo-random function where the output is inverted using XOR

I'm looking to know whether or not this PRF is secure : $$F'(k, x) = F(k, x) ⊕ 1^n$$ knowing that $F$ is already a secure PRF for $$\{0, 1\}^n × \{0, 1\}^n → \{0, 1\}^n$$ with, for example, $n= ...
1
vote
1answer
91 views

How should k2 be produced in the RC4A stream cipher (A modification of RC4)?

RC4A is a slight modification of the simple RC4 stream cipher designed to strengthen it against a number of attacks. Here's that paper. However in the paper, the second key ...
0
votes
0answers
48 views

Is this pseudo random generator (PRG) secure? [duplicate]

So here is a question that I am unsure about: g(x) is a secure prg (pseudo random generator). If g'(x)=g(x)||g(x+1) is g' a secure prg? (in this case || means concatenate) My argument is that g'(x) ...
1
vote
1answer
61 views

Figuring out seed/internal state from HMAC-MD5 output

Here is the scenario i'm imagining, I use the python random library to generate x-bit key that I use to generate a HMAC-MD5 output. Every HMAC-MD5 has uses a different random number as its key. My ...
1
vote
0answers
259 views

Assume $G$ is a PRG. Proof that $G'$ is PRG?

Let $G: \{0,1\}^s \rightarrow \{0,1\}^n$ be a pseudorandom generator (PRG). Are the following PRGs? $G'(x) = G(x)_{0,\ldots,n-2}$ ($G'(x)$ drops the last bit of $G(x)$) $G'(x) = G(x) \oplus ...
0
votes
1answer
46 views

need to develop CSPRNG. can i use ANSI X9.31 generator

need to create secure PRNG. can i use ANSI X9.31 generator and modify its entropy rather using DT use something else >?
0
votes
0answers
35 views

Different Types of Concatenating a Pseudorandom Generator Value

Assume $G$ and $H$ are PRGs. What is the difference between $$H(X) = G(X_L)|G(X_R)$$ and $$H(X) = G(X_L | X_R)$$ I tried to ask my professor earlier today before I posted here. He said something ...
3
votes
1answer
231 views

Is the following a PRG?

Let $G: \{0, 1\}^n → \{0, 1\}^m$ be a PRG. We construct a function $G': \{0, 1\}^{m + n} → \{0, 1\}^{2m}$ defined as follows $G'(x || y) = x || (G(y) ⊕ x)$ for all $x ∊ \{0, 1\}^m$ and $y ∊ \...
9
votes
1answer
237 views

Overview of relations between cryptographic primitives?

Is there a web page that gives a graphical (or, alternatively, a textual) overview of known implications and separations between cryptographic primitives? More specifically, I am looking for ...
1
vote
1answer
85 views

Why can't construct PRG from one-way function and hc, but only one-way permutation

In Katz & Lindell's book, theorem 7.19 stressed that let f be a one way permutation with hard-core predicate hc. Then algorithm $G(s)=f(s)||hc(s)$ is a PRG with expansion factor $\ell(n)=n+1$. ...
0
votes
1answer
156 views

Katz/Lindell Problem 7.6

Let $f$ be a length-preserving one-way function, and let $\text{hc}$ be a hard-core predicate of $f$. Define $G$ as $G(x)=f(x)\|\text{hc}(x)$. Is $G$ necessarily a pseudorandom generator? The answer ...
1
vote
1answer
66 views

RNG Source Combining

I'm planning on combining RNGs from several sources (Windows, Linux, OpenBSD, etc.) for generating one time pads but I have some questions that I don't know how to answer regarding xoring the outputs ...