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
1
vote
0answers
90 views

How to build a lsfr based on sequence $s_i = s_{i-1} + s_{i-4}$? [closed]

How do I know where my XOR gates go? What does the F2 stand for here? Also the next task is to generate the sequence (with initialisation vector $s_0 = 1, s_1 = s_2 = s_3 = 0$) until it becomes ...
2
votes
0answers
60 views

Hash function based cryptographically secure pseudo random number generator

I once read/heard that one could generate a cryptographically secure pseudo random number generator based on two cryptographically secure hash functions. The algorithm goes this way: Let $f$ and $g$ ...
1
vote
1answer
46 views

Generate unique random values for unqiue input values

I'm going to generate unique random values based per a range of unique input values. In other words I have range of input values which these numbers are part of a series (like a range of serial ...
2
votes
2answers
280 views

What is wrong with Middle Square PRNG?

According to article: https://www.pcg-random.org/posts/too-big-to-fail.html When N of Middle Square is $2^{128}$ we can expect to produce $2^{64.3}$ numbers before we start to see repeats in generator....
0
votes
0answers
25 views

Adding Weyl sequence to random mapping - expected cycle size

In order to improve the quality of random generators, Weyl sequences have been added to the Middle Square (Widynski) and Xorshift (Marsaglia) generators: https://arxiv.org/abs/1704.00358 https://www....
2
votes
4answers
175 views

What can chaos provide to cryptography?

Chaos-based cryptography is facing a lot of criticism, however, some people argue that it can provide many cryptographic primitives, such as stream ciphers, block ciphers, hash functions, public-key ...
3
votes
1answer
741 views

What is the G function of FIPS-186-2?

We are trying to follow FIPS 186-2 for creating a pseudo random number generator for EAP AKA AT_MAC Calculation in SIM Authentication: Choose a new, secret value for the seed-key, XKEY In ...
1
vote
2answers
79 views

Does Endianness matter in NIST SP800-22 test?

I am curious about Randomness test suite. One of the famous randomness test suite, DIEHARDER, said that Endianness does not matter for a "GOOD" random generator. Note that this is not the ...
1
vote
1answer
51 views

How to measure the length of the 128-bit PRNG cycle?

I have keyed 128-bit PRNG. It passed PractRand and Dieharder tests, but I have no idea what is expected cycle lengh of it (for different keys and different seeds). Is there way to estimate it, through ...
-1
votes
1answer
55 views

Neural Network based on pseudorandom number

Recently, I read this paper NEURAL NETWORK BASED CRYPTOGRAPHY. Under the section 3.1 it said: The aim is to improve the randomness of the random numbers generated by any algorithm using an NN. In ...
0
votes
0answers
28 views

Mersenne twister word size and degree of recurrence combination

For a 32-Bit variant of Mersenne twister, if the outputs Should be a 5-Bit integer(word size) then what is the value of recurrence according to the k-distribution?
1
vote
0answers
39 views

Program to predict a 5-bit output from mersenne Twister random module from python

Is there a program to predict the mersenne twister random module in python for a 5-bit integer output, provided the consecutive 3994 outputs are available? The random module is not seeded so i guess, ...
5
votes
0answers
573 views

How can we formally define a Pseudo-Random Shuffle function?

My question is related to: When we turn Random shuffle to Pseudorandom Shuffle The idea is to permute the elements in vector $\mathbf{v}$ pseudorandomly, where $|\mathbf{v}|=n$; I am aware that we ...
0
votes
0answers
64 views

Prove a function G is not a pseudo random generator

A function G(x) = x || x (where “||” denotes string concatenation). It is given that G is not s pseudo random generator. Can someone describe how can we prove this. I am getting a bit confused in the ...
1
vote
1answer
85 views

Pseudo Random Generators

G is a PRG and takes in a seed s. Is G'(s) = [G(s)]' (i.e. the complement of G(s)) a PRG as well? My proof by contradiction: Suppose G' is not a PRG, then G''(s) = [[G(s)]']' = G(s) is also not a PRG ...
0
votes
1answer
22 views

Relationship between LCGs and LFSRs

Here: https://en.wikipedia.org/wiki/Linear-feedback_shift_register they wrote: The linear feedback shift register has a strong relationship to linear congruential generators What this relationship ...
1
vote
0answers
29 views

How to reproduce seeds in Random Number Generator like WELL, KISS etc

I am curious about Padding the seeds of Random Number Generator. (I am sure that terminology, padding the seeds, is not correct. If someone knows the proper word, please let me know :) ) What is ...
1
vote
1answer
59 views

Getting the plaintext encrypting the ciphertext

Context: an encryption game from overthewire (the link to it: https://overthewire.org/wargames/krypton/krypton6.html, also good for more info) where given the ciphertext, one must obtain the plaintext....
0
votes
2answers
57 views

PRNG based on GF?

Are there any pseudo random number generator based on Galois fields? The source of the AES randomness lies in the GF, so GF should be capable of generating random bits. Why are there no such ...
2
votes
2answers
169 views

Understanding definition of secure pseudo random number generator

From my reading, a secure pseudo random number generator is called secure if, given a sequence of numbers generated by the PRNG, then if any one of those numbers from the sequence is removed an ...
6
votes
4answers
452 views

A source of randomness that anyone can independently, conveniently and robustly access?

Does there exist a source of randomness that anyone in the world can independently, conveniently and robustly access? For example, the 10th decimal place of the temperature in Mexico City is ...
0
votes
2answers
175 views

What are the fastest algorithms that sample from the uniform distribution?

Lots of cryptography algorithms rely on pseudorandom number generators. Sometimes, given a plaintext, you need to generate a pseudorandom number from it. What are some fast algorithms that do so? I've ...
0
votes
1answer
24 views

Non-overlapping seeded numbers generator for small output range

Seen this, but it's sort of useless as it allows for trivial solutions by increasing the size of the output's space up to a point any hashing function will achieve non-collision. This question is ...
0
votes
1answer
73 views

In the reduction proof below, where OWF exists only if is a PRG. I am not able to understand the highlighted part

I am able to understand how G(x) id generated. But then what is the use of variable z. Also if the probability is >1/2 + e then the distinguisher wins! Then how is this still a OWF
1
vote
1answer
55 views

PRNG generator which could repeats blocks

Let's use AES as stream cipher, and let's use as an input numbers $1,2,3,...$. This way we should get the random blocks and every block will be different from each other. But I have a pseudorandom ...
3
votes
1answer
1k 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: ...
2
votes
1answer
68 views

Question about IETF RFC6979 determinisitc (EC)DSA document section 3.6 additional data k'

In RFC6979, on page 14, Section 3.6 "Variants": o. Additional data may be added to the input of HMAC, concatenated after bits2octets(H(m)): ...
2
votes
3answers
146 views

Can we combine two true random generators to obtain a new one?

It is well known that a true random generator exploits the randomness occurs in some physical phenomena. Also, the output of a true random generators can be either biased or correlated. Therefore, de-...
1
vote
2answers
2k views

Is it possible to compress a random sequence with high entropy?

I have an algorithm that generates a pseudorandom sequence with a length of 100k and high entropy. I would like to check the quality of its randomness. So, I used a popular software program to ...
0
votes
0answers
36 views

How can I recover mersenne twister when only the part of the bits?

https://github.com/tna0y/Python-random-module-cracker Here, when we get 32*624 bits of outputs from Mersenne-twister we can recover Mersenne twister. My question is when we get the parts of the bits, ...
1
vote
1answer
149 views

A modification of the Blum-Micalli construction

Consider the following modification of the Blum-Micalli construction (denoted by BM): $G_l(x) = f^l(x) || BM^l(x)$ I am asked the following questions about it: Show it is a PRG of fixed stretch ...
2
votes
1answer
406 views

Breaking a Mersenne-twister RNG with unsequential outputs

Pardon me for this newbie-ish question. I'm still a novice in cryptography . I have an application that outputs random numbers from 0 - 12 (endpoints inclusive) unsequentially (some outputs are thrown ...
7
votes
1answer
984 views

Galois LFSR Subsequence Periodicity

I had the following questions - Concerning generating sequences of bits $\textbf{x} = ( x_{0},x_{1}, ... , x_{n-1})$ where the $x_{i} \in \{0,1\}$ are considered coefficients of a polynomial in $\...
4
votes
1answer
914 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 ...
9
votes
3answers
891 views

Perfect shuffle possible with limited raw entropy?

I am trying to shuffle a standard 52-card deck in a perfect way (every outcome should be possible at an equal chance). I am not, at this point, concerned with cryptanalysis attacks against it. I have ...
3
votes
3answers
411 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 ...
10
votes
3answers
613 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 ...
0
votes
0answers
102 views

Determine if a function is a PRG when PRG concatenated with Seed?

I am a newbie in Cryptography and have trouble to solve the following question. Let $G: \{0,1 \}^n \rightarrow \{0,1 \}^{l(n)}$ be a PRG and $x \epsilon \{0,1 \}^n$. Determine if the function $Z: \{...
1
vote
1answer
40 views

How to prove the pseudorandomness of CryptoPAn

in my cryptography course, we are learning about pseudo randomness and the prefix-preserving function known as CryptoPAn invented in 2002. It is said that the scheme is highly insecure. So in that ...
1
vote
0answers
27 views

composition of RLWE distributions

Assume we have the polynomial space $R_q$ defined as $R_q = Z_q/(X^n + 1)$. Additionally, we define the error distribution $\chi$ as a discrete centred Gaussian bounded by $B$. Let $s,t \in R_q$ be ...
0
votes
0answers
23 views

Construction PRG with expansion factor from a length preserving PRF [duplicate]

How can I prove that $F:\{0,1\}^n\to\{0,1\}^n$ is a length-preserving pseudorandom function, then $$G:G(s)= F_s(1)\mathbin\|F_s(2)\mathbin\|\cdots\mathbin\| F_s(l)$$ is a pseudorandom generator with ...
0
votes
0answers
51 views

Am I applying Hybrid lemma and proof by contradiction correctly?

In the following scenario, I am trying to apply proof by contradiction. My idea is to use a Hybrid lemma. So if I am able to distinguish $G'$, this implies we are able to distinguish $G$. But we ...
0
votes
2answers
101 views

Rigorous practical pseudorandom generators

It is known that existence of pseudorandom generators (PRGs) is equivalent to the existence of one-way functions. In turn, the latter is an open problem. I am curious if someone developed kind of &...
4
votes
2answers
364 views

Is a LFSR sufficient for post-processing a biased TRNG?

I am building a TRNG on a FPGA based on ring oscillators. I found out that Linear Feedback Shift Registers (LFSRs) are commonly used for the post-processing of TRNGs. Here is my initial design: Let's ...
1
vote
1answer
216 views

Construct a specific length-doubling pseudorandom generator from a length-doubling pseudorandom

Let $G$ be a length-doubling pseudorandom generator (i.e., for any $n\in \mathbb{N}$ and for any $s\in\{0, 1\}^n$ it holds that $G(s)\in\{0, 1\}^{2n}$). Can you construct a length-doubling ...
8
votes
4answers
168 views

Why are $\lceil 1/\operatorname{entropy-per-bit} \rceil$ number of bits not sufficient to generate an unbiased bit?

Consider a biased RNG badrand() generating 1 with probability $0.9$ and 0 with probability $...
7
votes
1answer
7k views

Using a hash function as a random number generator

Using MD5 or SHA1 for instance, and applying integers (as seed so to speak) to the hash function, in sequence, and only keeping, say, the first 64 bits of the resulting hash, do we always have a ...
2
votes
2answers
275 views

Is Fibonacci-XOR-rotate one-way-ish?

Fix $n\in\mathbb{N}$ with $n > 2$ and consider the following method. Pick relatively prime seeds $x_1, x_2 \in \{0,1\}^n$ (where $x_1, x_2$ are interpreted as binary numbers. Then proceed with the ...
5
votes
3answers
273 views

How to combine $n$ 'less random' bits to generate one 'more random' bit?

Suppose we have a random number generator badrand() generating 1 with probability $0.9$ and 0...
4
votes
1answer
228 views

What is the NIST recommended maximum bias for random number generators?

What is the maximum bias recommended by NIST for random number generators? This answer says that it is $2^{-64}$. Is it same for all applications? Does NIST have a publication with more information? I ...

1
2 3 4 5
9