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
vote
1answer
28 views
Problems understanding the applications of pseudo random number generators
I am trying to explore different methods used to generate pseudo-random numbers for my project in maths and I would be very grateful for some help or references to valuable sources as it is very hard ...
6
votes
1answer
564 views
What does “seed” mean in cryptography?
I have come across "seed" many times, and at each time, it confuses me more and more. I think it has a well-known meaning in cryptography, so what is it?
They can usually use the limited number of ...
1
vote
1answer
40 views
Instead of sending a set of random values, send a key for a PRF
Some Protocols require one party to send $n$ random challenges (or random values) to another party. For communication efficiency purpose, one can pick a random key for a pseudorandom function, and ...
-1
votes
1answer
67 views
Can there be a PRG $G(x)$ where at most half the output bits are 1?
Can there exist a pseduorandom generator, $G(x)$, with input length $|x|=n$ and output length $|G(x)|=2n$, where $\leq n$ bits of $G(x)$ are equal to 1 for every possible input $x$? (I.e. no more than ...
-2
votes
0answers
47 views
Is $G(s)=G_{1}(s) \oplus G_{2}(s)$ guaranteed to be a PRG where $G_{1}$ and $G_{2}$ are efficiently computable?
Let $G_{1}$ and $G_{2}$ be efficiently computable functions, each with expansion $\ell(n)=3n$ (that is, $|G_{1}(s)|=|G_{2}(s)|=3n$, for inputs of length $|s|=n$), and we know that at least one (but ...
-1
votes
1answer
102 views
If $G$ is a PRG, is $F(s)=G(S)||G(\bar{s})$ necessarily a PRG?
Let $G$ be a pseudorandom generator, and $F(s)=G(s)||G(\bar{s})$ (where $\bar{s}$ denotes the bitwise complement of $s$), is $F$ necessarily a PRG?
My intuition says that it is a PRG, as clearly $G(s)...
-4
votes
0answers
108 views
Prove if it is a PRF
I've two questions:
Let $F : \{0, 1\}^n \times \{0, 1\}^n → \{0, 1\}^n$ be a pseudorandom function mapping n-bit input to n-bit output with a n-bit key. Consider a function $F ′ : \{0, 1\}^{2n} × \{...
3
votes
1answer
203 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 (without claim of cryptographic security) by Bernard ...
7
votes
2answers
697 views
How fast does a pseudorandom number generator have to be in order to be competitive?
Let $\{x_n\}_{n}$ be the pseudorandom sequence produced by a cryptographically secure pseudorandom number generator $G$. What is the cost of computing a term in the sequence for a competitive ...
1
vote
1answer
76 views
Pseudo-random generators and pitfalls
I've read the Chapter "Randomness" from the Serious Cryptography book and it raised some questions. Namely:
It is written that Mersenne Twister is proved to be cryptographically irreliable. And that ...
0
votes
1answer
75 views
Does hashing a PRNG by a cryptographically secure hashing algorithm result in a CSPRNG?
Or specifically, does ChaCha20 hashing of the xoroshiro128+ random number generator result in a cryptographically secure random number generator?
0
votes
0answers
19 views
Pseudo random point (non floating and perfect square)
Hy, sorry I'm still learning Elliptic Curve Crypto. Recently I'm studying a paper ECC in a dynamic way, which we can generate the key. in this paper, they mention about generating a pseudorandom point ...
4
votes
1answer
169 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 ...
0
votes
0answers
83 views
Is PRG xor it's input(concatenate) a PRG
If $f: \{0,1\}^n -> \{0,1\}^{2n}$ is a PRG, then is $g(x) = f(x)⊕(x||x)$ a PRG?
Edit:
I think $g(x)$ is a PRG(I have diffcult in finding the counterexample). And we can assume that $g(x)$ is not ...
1
vote
0answers
39 views
Mersenne Twister's vulnerabilty with small-size distributions
C++ rookie here, trying to wrap his head around (CS)PRNGs.
I (assume that I) already understand the concept of the Mersenne Twister being "broken" (i.e. not cryptographically secure) due to its ...
2
votes
1answer
100 views
Is the XOR of PRGs sharing the same input a PRG?
I have question in learning PRG. Given that $f$ and $f_1$ are PRGs, both $\{0,1\}^n \to \{0,1\}^{2n}$.
Is $g(x) = f(x)$ xor $f_1(x)$ a PRG?
Someone told me that in this case, $g(x)$ is not a PRG, ...
0
votes
1answer
50 views
Oblivious Encryption: Oblivious Transfer Based Encryption
I’m aware of a couple of OT protocols, most of which use Public Key Cryptography, Key Establishment (or similar constructs) as the base. I don’t really have specific knowledge on other OT protocols, ...
2
votes
1answer
77 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 ...
2
votes
2answers
89 views
Inversive Congruential Generator
The inversive congruential generator over the prime field $k=Z/pZ$ is given by the iterations of the map $x\mapsto a/x+b$ if $x\neq 0$ or $b$ if $x=0$.
One can choose $a,b$ in $k$ such that the orbit ...
1
vote
2answers
71 views
How is a ciphertext encrypted using random numbers decrypted using a symmetric key algorithm
We use true random number generators as a source of keys for encryption. What I can not wrap my head around is: How is this cipher text decrypted in case of symmetric key algorithm as we need the same ...
1
vote
1answer
87 views
repeatedly hashing result and using reverse sequence as RNG secure?
I want to have a source of randomness for which:
no one but me can predict the next number in the sequence.
I know the entire sequence in advance, but I have no way of manipulating it once the first ...
0
votes
1answer
51 views
Expected Linear Complexity of a sequence
Let (s) be a sequence of length n. What are the expected linear complexities of (s) and $(s)^{\infty}$ (meaning that the periodic version of s)?
I have no idea of the answer to this question? What ...
2
votes
1answer
78 views
period of the lfsr sequence after some manipulations
Here is the question I am dealing with. I have some sort of a solution but I need more specific results. If someone can help I'd appreciate:
Given 3 maximum length (max period) LFSR's of lengths L1,...
1
vote
1answer
35 views
Random semantic security and bijective PRGs
I'm working through Boneh and Shoup's "Graduate Course in Applied Cryptography", and have just finished reading the chapter on stream ciphers and PRGs.
The first exercise for this chapter introduces ...
4
votes
1answer
173 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
11 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
161 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
83 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
86 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
137 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
147 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
51 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
68 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
61 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 ...
1
vote
1answer
137 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
162 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
126 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
105 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
101 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
364 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
128 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
102 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
79 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
52 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
112 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
258 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
248 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
114 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 ...
1
vote
0answers
103 views
