Schneier on Security

Clive Robinson • December 3, 2019 3:04 PM

@ Bruce,

So RSA-240 has been broken and another “squeamish osifrage” (or how ever you spell it 😉 message revealed.

Also not done by “Crown Sterling” and their magic crystal machine.

That as they say “Are the facts”…

So how about some interpretation and broader scope analysis?

Clive Robinson • December 4, 2019 8:20 AM

@ Curious,

Is there perhaps a best practise rule in cryptography or for anyone relying on the use of cryptographic solutions, that sets of prime numbers must always be chosen randomly as opposed to using numbers from a list or provided to them from some other source?

Yes there is and unfortunately it is broken way way more often than it should be as I’m sure the NSA, GCHQ, et al know and advantageously exploit.

The first thing you have to realise is that what you call a “list” has a broader meaning than something printed in a book or put in a computer file, it includes problematic Random Number/bit Generators (RNG) as well.

As you’ve no doubt heard anyone using a fully determanistic system for generating random number sequences has for some time been considered to be “living in a state of sin”[1]. But at the end of the day computers are –or should be– fully determanistic systems. So important is the point about what some call “True Random Number Generators” (TRNGs) that Alan Turing put the design for such circuits into the fundemental design of computers[2] though few ever did untill this century.

The problem is “true entropy” is a very very rare beast, most TRNG sources are heavily contaminated not just with “faux entropy” but various types of bias as well. Cleaning up and extracting the true entropy is a complex and involved process so most people don’t bother doing so. Instead they use some kind of Computer Secure (CS-) algorithm as “magic pixie dust” to mix things up and make them look sufficiently unbiased to meet the original Diehard Tests[3] and subsequent test suites.

Unfortunatly most CS-algorithms although fully determanistic also pass these same test suites which gives you an indication of where problems arise.

Our host @Bruce has designed a number of RNG sources such as Yarro, importantly part of the design is an “entropy pool” which in effect captures and holds the very very rare bits of True Entropy and by a mixing process spread them across all bits in the pool.

However there is a problem in that it takes a very long time to build up sufficient true entropy in the pool. And unless the pool is saved at “power down” and reloaded at “power up” you will have to wait that period of time each time a computer is powered up.

Whilst this is done in OS’s like BSD and some Linux varients, it’s usually not done in “embedded systems” used for communications and security.

Worse even when it is done, the initial power up after a factory reset starts with an empty pool, and almost immediately goes into the process of generating random numbers for security purposes such as for crypto key generation (KeyGen). This of course includes those used for “finding primes” for not just asymmetric PubKeys but also those primes used for other CS-DRNGs.

As the entropy pool is in effect empty at power up, and embedded systems don’t get much in the way of true entropy sources, the result is that a very very small subset of the potential random numbers generated are actually produced. Small enough to in effect give the SigInt agencies a “list” of likely random numbers to use… When found from the PubKey the SigInt agencies can then go on and work out the likely values used for any CS-DRNGs…

So you can see why using TRNG’s correctly is so important, which when you find out few embedded system designers actually do things correctly should make you think rather carefully about which products you purchase and use.

[1] Back in 1951 according to various Internet sources, John von Neumann first gave voice to,

Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin

[2] Also in 1951, randomness was finally formalized into a real comercial computer, designed by Alan Turing. The Ferranti Mark 1, wAS shipped with a built-in random number device using termal / electrical noise that generated 20 random bits when called via a specific instruction.

[3] The diehard tests were developed by George Marsaglia over several years and they measure the quality of a RNG via a battery of statistical tests. First published in 1995 on suprise suprise a CD-ROM of random numbers, that had 650 megabytes of random numbers that passed the tests. Importantly they were generated by combining a noise-diode circuit output with a deterministic but chaotic looking source from “rap music”. George Marsaglia called the result “white and black noise”. In essence the result was like the ciphertext output from a One Time Pad.

Clive Robinson • December 4, 2019 12:07 PM

@ Curious,

The problem is checking a prime realy is prime, and it’s a slow process to do regardless of if it’s a computer or pencil and paper.

Thus various tricks are used to reduce the candidates down. Back last century the first was a simple sieve (look at the controversy with Crown Sterling to see a fairly simple one). Then the next was to do a series of probabalistic tests such as the “Miller–Rabin” or similar “primality test” which rule out large swathes of non primes fairly efficiently. Then the hard grind of “Trial division” effectively dividing by every prime below the square root of the number, or similar only slightly more efficient methods, which as they take a very long time for obvious reasons they were very rarely done in practice for primes over 128bits.

Then in August 2002 three computer scientists in India came up with a new way more efficient way of proving primality. Known as the “Agrawal–Kayal–Saxena primality test”, it had a number of estimates on runing time, which was a que for mathmeticians to “dog-pile” on it. Within a year there were a large number of papers and the term “AKS-Class Primality tests” was coined.

However they all fall in the “galactic algorithm” class, which is basically algorithms that are more efficient than others, but only after some point so large –greater than all the atoms in the galaxy– the algorithm will never be used in practice.

But the thing about “primes” is they are not all the same they in effect have personalities where they fall into classes. “2” is obvious because it’s the only even prime, most know about Mersenne primes that are a subset of Mersenne numbers. The thing is that these classes have properties that might or might not be good news depending on your application.

Thus picking primes that don’t fall in some classes but do in others is a quite important consideration in certain applications or domains (cryptography being just one).

One obvious class to avoid is “twin primes” because they fall either side of primordials (think factorials but only with successive primes not integers). These primes are very easy to find because they not only have known points they also reflect around these points making other nearby primes almost as easy to find.

To see this draw up a number line from 1-210 and look around the primordials like 30 and it’s images at 60, 90, 120, and 180. You can use this to build a more efficient sieve than others.

Clive Robinson • December 4, 2019 12:54 PM

@ MikeA,

say a nice hot cup of tea

I could kill for one right now…

I’ve ended up in Accident and Emergancy this morning and it’s now,18:50UK time… Thus I have not had anything other than water or eaten either.

Hence I am now staring at a blank white wall and starting to have hallucinations of roast chicken and potatoes, carrots, peas, and a nice side order of cabbage on low flying plates chased by silverware.

Before anyone asks, it’s not serious only extreamly painful, which now the pain killer is wearing off that chicken is looking more illusory by the minute 🙁

Clive Robinson • December 7, 2019 6:45 AM

@ Weather,

Would it make sense to say every one million prime put one in a file

What is infinity over a million?

It would be an infinite size file.

But you don’t need to do that. As I’ve mentioned you want to avoid “twin primes” as the usually sit astride a primorial[1] which makes them “Primorial Primes” which are fairly easy to find without needing a lookup table in a file.

But the problem stretches out from Primorial Primes, as I’ve also mentioned their pattern of location reflects around not just the main primorials but what are the sub primorials.

So 30 (2x3x5) and 210 (2x3x5x7) are primorials and “29,31” and “209,211” are their Primorial Primes that are also “Twin Primes”

However 210/30 is 7 and thus there are 7-2 sub primorials or reflection points of 60, 90, 120, 150, 180. The numbers either side of these also tend to be primes or twin primes.

If you make a number line from zero to 420 and mark the primes off you will see that the reflect around the primorials and their multiples. Thus if you work up from 210 you will find the primes match location wise as you move down from 210. If you do the same with 30 you will see a reflection around it, but you will then see another reflection around 60.

Obviously you loose a few primes along the way, but when you get into realy big primorials of the first fifty or a hundred primes (which you can store in a file) you can then build a “location” file of the locations around a reflection and use this to build a fairly fast sieve around primorials and their sub reflections and sub sub reflections etc.

Whilst it makes finding “probable primes” much faster than simpler sieves[2] it makes an adversaries job simpler as well thus it’s best to avoid the “close in” primes to the primorial points.

[1] The term “primorial” was thought up by Harvey Dubner[3] akin to the more common factorial which is formed by multiplying each positive integer in succession and is something all K12 students should be aware of. The Primorial works the same way, except instead of using the first n natural numbers it uses the first n primes in succession. It is sometimes written as P_n# for convenience. Thus more formally the nth prime number pn, the primorial p_n# is defined as the product of the first n primes.

[2] Like all sieves they are conceptually simple, and at low values around either factorials or primorials they are faster, but the advantage quickly slips behind just random number guessing and probability tests.

[3]who sadly dird on 23rd Oct this year. He had quite a number of claims to fame including writing up the first “card counting” method, and at one time holding the record for finding the most primes over 2000 digits. He has also come up with a number of “number sequences” of which primorials are one (see sequence A002110 in the OEIS)