Into the symmetry

See  also Part I and Part II   of this series This is going to be a short blog post about the (in)famous Micali-Schnorr  Random Number Generator (MS-DRBG). See Part I and Part II   of this series  for more information about this topic. WHO: NIST published the specification for Micali-Schnorr  Random Number Generator (MS-DRBG) in NIST Special Publication 800-90 ISO 18031.  Along with the explanation of the core algorithm the documents contains the specification's moduli with the claim to be of the form  n = pq with p = 2p1 + 1 , q = 2q1 + 1 , where p1 and q1 are ( lg(n)/2 – 1 )-bit primes. N.B. a prime of the form p = 2p1 + 1 where p1 is also a prime goes under the name of Safe Prime and they are often used in cryptography for both RSA and DH. WHAT: Now we can look at the NIST Special Publication 800-90 ISO 18031's moduli and simply believe that those modulis are of the claimed form but maybe is not a great ...

See  also Part I and Part III   of this series tl;dr In the previous article of the same series we tried to predict the output of Micali-Schnorr Generator (MS-DRBG) knowing the factorization. In this blog post we continue the effort started in part I showing different strategies.  If you want to skip all my failures and go directly to the (in my humble opinion) most promising approach you can read directly the Solinas Prime and Generalized Mersenne Numbers section below. If you actually wonder what is MS-DRBG and why I am trying to do it I'd suggest to go back and read the first article . What I am NOT claiming in this post though is that there is a NSA's backdoor in the ANSI and ISO standards. Introduction and Failure #1 So let's start from were we actually finished the last post. We focused on an easier version of the problem directly extracted from the original Micali Schnorr paper from Efficient, perfect random number generators where the ...

The article was modified since its publication. Last update was 09/10/2017  See  also Part II and Part III of this series tl;dr in this post we are going to describe how to try predict the output of Micali-Schnorr Generator (MS-DRBG)  knowing the factorization of the n  value. If this sounds like, "why the hell should I care?" , you might want to give a look at this great post from Matthew Green about the backdoor in Dual_EC_DRBG . But In a nutshell, quoting Matthew Green : Dual_EC_DRBG is not the only asymmetric random number generator in the ANSI and ISO standards (see at the bottom).   it’s not obvious from the public literature how one would attack the generator even if one knew the factorization of the n  values above. What I am NOT claiming in this post though is that there is a backdoor in one of this standard. Introduction The first time I heard about this problem is about couple of weeks ago via this Matthew's tweet: A...