Tag Info

Perhaps you are thinking of the Micali-Schnorr PRNG, as described in Algorithm 5.37 of the Handbook of Applied Cryptography? Algorithm 5.37 in HAC never states that $e$ is known to the adversary, or even that $n$ is known. Also, Algorithm 5.37 outputs only the least significant bits of the number, on each iteration. So I think you are confusing RSA as ...

Contrary to what's stated in the question and its comments, extracting any $m\le n$ bits from the sequence of the states of an $n$-bit LFSR still result in a sequence with period $2^n-1$, assuming the state of the $n$-bit LFSR is not zero and its generating polynomial is primitive. Proof sketch: by a fundamental property of LFSR with primitive feedback ...

I'm not a hundred percent certain on your definition of "AE-Secure", but I would have to say yes. Existence of a PRG implies existence of one-way functions, which in turn implies existence of both, symmetric encryption and message authentication codes. From those two primitives you should be able to construct authenticated encryption.

I will add a few points worth considering to @fgrieu's answer. The output sequence of period $2^n-1$ from a $n$-bit maximal length LFSR has the property that it contains runs of zeroes and ones in (close to) the correct proportions. In particular, there is one run of $n$ consecutive ones (no run of $n$ consecutive zeroes, but there is one run of $n-1$ ...

Well, successive calls rand() just produce numbers that "look random". Now, rand() doesn't take a seed; that means that everytime the program runs, calls to rand() will generate the exact same sequence of numbers. This is a deliberate design decision; that means that the program behavior is reproducible (which can be important if you're debugging). If you ...

Since this looks like homework, I'm not going to answer the question directly (and I hope others won't either), but I'll just give some hints: You're on a good direction. If you want to prove that $G'$ is a secure PRG, then your general approach (trying to show that a distinguisher for $G'$ implies a distinguisher for $G$) is a good strategy. Keep at it. ...

If you're trying to describe the Micali-Schnorr PRNG (Algorithm 5.37 in HAC), you have not accurately described the Micali-Schnorr PRNG. The Micali-Schnorr PRNG is cryptographically secure, but yours is not. Where did you get the PRNG you described, and why do you think your PRNG is secure? The PRNG you described is not secure, if each $x_i$ is output on ...

The security claim on page 5 of the Linear Cramer-Shoup paper is that their modified scheme is CCA secure, which is weaker than the IND-CCA2 security of the original DDH based Cramer-Shoup scheme. However, from the outline of the security proof, it seems the author actually means the LCS scheme is CCA2 secure. Also note the first sentence on page 6: ...

If you are using this for cryptographic purposes, do not use a LFSR. Using a LFSR for pseudo random number generation is highly insecure. Instead, you should use a standard cryptographic PRNG, such a /dev/urandom. You can just repeatedly read bytes from /dev/urandom and keep just the low 5 bits. This will provide a very large period (essentially ...

Multi-prime RSA (also known as RSA-MP) is supported by PKCS#1v2. This standard supports a public key $(n,e)$ where the modulus $n$ is the product of $u≥2$ distinct odd primes: $n=\prod_{i=1}^u{r_i}$, with $1<e<n$ and $\gcd(r_i-1,e)=1$ (implying $e$ odd). The private exponent $d$ is such that $1<d<n$, and ...