Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Unsafe RSA primes conjectured

mathoverflow.net

Post reply on HN
Print view View original

41–50 of 59 posts

Re: Unsafe RSA primes conjectured

#41

Post by jabot »

cobbal wrote: post #11
wybiral wrote: post #4

How many primes within the usual range generated for RSA happen to fit the form 27 a^2 + 27 a + 7?

Assuming at least 768 bits (an RSA number of this size has been factored), the gaps between such numbers are more than 10^232. Even if every number of this form was prime, the prime number theorem tells us we can expect one out of every 10^229 primes to be weak. There could or course be a larger class of such easy primes, but it seems like it's extremely unlikely a prime of this particular form would ever be generate…

Thanks for that answer.

These "weak" primes are perfect for backdoors, however, if you know about them being weak, and noone else does.

Re: Unsafe RSA primes conjectured

#42

Post by jabot »

AlexCoventry wrote: post #10

Why is this significant?

It is... somewhat significant.

If i recall correctly, you need to generate two large prime numbers to get a key. There are already several caveats for the prime generation, so you cannot just take any two primes that are big enough. So for a proper key generation, you generate a lot of random numbers, verify that they are prime and that they are "proper" for RSA.

This discovery "just" means that there are some additional steps for verifying the properness of the prime, that every RSA implementor has to add. So for mitigation, there is work to do for implementors, but similar work has been necessary before...

Of course, this might have been used to generate backdoorable RSA keys, and giving them to people without their knowledge. If that happened, this issue becomes... more significant for all that have been backdoored.

Re: Unsafe RSA primes conjectured

#43

Post by DonbunEf7 »

AlexCoventry wrote: post #10

Why is this significant?

This comment box is too small.

We keep learning about elliptic curves, and the more we learn, the more we glimpse the edges of a massive and deep symmetry which relates primes and polynomials (Fermat's Last Theorem, RSA, AES) with elliptic curves (Birch & Swinnerton–Dyer Conjecture, ECDSA, Ed25519) and modular forms and L-functions (Riemann Zeta Hypothesis). This is known as the Langlands programme [0].

The significance of this result is that it is yet another brick in the wall of the Langlands programme's immense and daunting blueprint; overall, it is only a tiny tiny fragment. The L-function database [1] is far more interesting if you want to get a good look at a collection of stuff that we know about the topic.

[0] https://en.wikipedia.org/wiki/Langlands_program [1] http://www.lmfdb.org/intro

Re: Unsafe RSA primes conjectured

#44

Post by monocasa »

theWatcher37 wrote: post #39
tptacek wrote: post #35

Earlier quoted context omitted.

"The number of true cryptography experts beyond [the walls of the NSA] is a dozen in the world at best"? This kind of logic is super common on HN threads and it's incoherent. If the expertise and capabilities of the NSA with respect to basic cryptographic mathematics is so unknowable that thousands of published academic cryptographers are wasting their time, then what makes you think a random amateur Math Overflow po…

NSA made seemingly bening improvements to crypto standards that the academic community only discovered as valuable over a decade later. They’re the largest single employer of mathmaticians in the world.

> NSA made seemingly bening improvements to crypto standards that the academic community only discovered as valuable over a decade later.

At the same time, they negotiated DES's key length down. It was 64 bits originally, the NSA wanted only 48 bits, IBM and the NSA compromised on 56 bits.

Re: Unsafe RSA primes conjectured

#46

Post by trumpownsyou420 »

EwanToo wrote: post #40
slackingoff2017 wrote: post #33

Earlier quoted context omitted.

Don your shiny crinkly hats, but after https://en.m.wikipedia.org/wiki/Dual_EC_DRBG I started believing that NSA involvement is not subtle in their exploits. They only need to fool laymen, and backdoored primes are an easy way to do so. The number of true cryptography experts beyond their walls is a dozen in the world at best. Case in point https://en.m.wikipedia.org/wiki/Daniel_J._Bernstein . And BTW he's been sued…

Do you honestly believe that China and Russia don't take cryptography seriously, and between them only employ a tiny handful of experts...?

most amercians (you can tell he is) aren't fond of the places you named, chap.

Re: Unsafe RSA primes conjectured

#47

Post by wbhart »

AlexCoventry wrote: post #10

Why is this significant?

It's not really significant for RSA at all. It is likely that no human (as far as we recognise the species) will ever generate RSA primes of this form randomly, if standard tools are used.

It's been known for a very long time that there are many extremely sparse classes of primes which general factoring algorithms will extract as factors very quickly.

For example, some general factoring algorithms will factor numbers of the form (a^m+b)(a^n+c) for small a, b and c and m and n fairly close. But this is an extremely sparse class.

You could generate billions of such sparse classes (and check them all by brute force), but it's still unfathomably unlikely you would find RSA primes in the wild of any of these forms, if they were generated by reasonable implementations.

Re: Unsafe RSA primes conjectured

#49

Post by baby »

tptacek wrote: post #25
tonysdg wrote: post #14

Earlier quoted context omitted.

Because it means that some RSA keys may be weaker than others. Without diving too far into the mathematics of it, the RSA cryptosystem (and indeed, many asymmetric-key cryptosystems) is based on the notion that multiplying two gigantic prime numbers together to get another gigantic non-prime number is easy; but taking a gigantic non-prime number and figuring out which two prime numbers were multiplied together is inc…

He's asking why, if you only have a 2^-730 chance of generating one of these primes at random, would you care about that risk? Single-bit memory or computation faults can devastate the security of cryptographic operations, and they're multiple orders of magnitude more likely to recur in a single computation than generating those particular primes.

In addition to tptacek's comment, we already know a bunch of ways where the RSA primes would be weak. And we don't check for them when generating RSA primes because they have almost no chance of occurring.

Re: Unsafe RSA primes conjectured

#50

Post by cobbal »

cobbal wrote: post #11
wybiral wrote: post #4

How many primes within the usual range generated for RSA happen to fit the form 27 a^2 + 27 a + 7?

Assuming at least 768 bits (an RSA number of this size has been factored), the gaps between such numbers are more than 10^232. Even if every number of this form was prime, the prime number theorem tells us we can expect one out of every 10^229 primes to be weak. There could or course be a larger class of such easy primes, but it seems like it's extremely unlikely a prime of this particular form would ever be generate…

Oops, looks like I made several mistakes in the above calculations.

For a 768 bit number the primes would be 384 bits each, gaps between numbers of the form "27a^2 ..." would be 10^58 apart, and weak primes would be at worst one out of 10^56.

Still extremely unlikely, but not by as much as I thought.

Post reply on HN