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

4096 RSA key in the strongset factored?

trilema.com

Post reply on HN
Print view View original

101–110 of 114 posts

Re: 4096 RSA key in the strongset factored?

#101

Post by jugad »

ColinWright wrote: post #34
monochromatic wrote: post #26

> And the first factor - get a load of this - is 231. Which... yes, 231 = 3 * 77. Why isn't the first factor just 3 then?

When you use factoring algorithms other than simple trial division - things like Pollard rho and its ilk - you are not guaranteed to get the smallest factor(s) first. Sometimes you get bigger factors, or combinations of factors, because those are what happen to pop out of the algebraic structure you're running over. But any "primes" being used should have some serious factorisation algorithms run over them before bei…

Large pseudo prime generators usually check for divisibility by numbers upto a million or so, then follow it with Rabin-Miller or more sophisticated non-deterministic tests to verify primes.

These primes could not have been generated by any reputable prime generation algos that I can imagine.

Re: 4096 RSA key in the strongset factored?

#102

Post by dragontamer »

arenaninja wrote: post #5
dragontamer wrote: post #2

This is kind of hilarious. I think the article might be a bit dense for those who aren't aware of RSA's algorithm though.

I agree. I've rolled OpenSSL certs for servers, but crypto isn't really a forte of mine. A generic rundown of implications would be nice.

In essence, RSA is a crypto-algorithm that relies on the fact that "Factorization" is a very very hard mathematical problem for standard computers to solve.

For example, what are the factors of 143?? Answer: 13 x 11. Factoring is hardest when the number is made up of two prime numbers. Public Key cryptography is basically a giant puzzle based on the difficulty of factoring numbers.

Now, instead of small numbers that we humans use, what is typically done is two 2000+ bit prime numbers are chosen and then the resulting 4000+ bit number is used as the "encryption puzzle".

This 4096 bit number happened to be 231, which is 3 x 77. Huzzzahh! I guess 231 is a 4096-bit number... but generally speaking, you'd hope that the number at the center of your "encryption puzzle" would be a bit... larger. So that it'd be harder to factor it.

Re: 4096 RSA key in the strongset factored?

#103

Post by dfox »

contravariant wrote: post #65
detaro wrote: post #52

Earlier quoted context omitted.

Should . Obviously something went very wrong and the "primes" weren't properly checked to actually be primes.

Well, obviously something went wrong. But the way I understand it RSA shouldn't work at all if you used a composite factor, decrypting a message will just give a wrong result. Unless, by some incredible fluke, they managed to find a carmichael number.

RSA without CRT optimization of private operations will work regardless of how many factors modulus has, if key was generated correctly. With "correctly" meaning using correct value of phi(n), which is not (p-1)*(q-1) when either of p or q are composite (which in effect means that it will not work at all with essentially all interesting implementations).

IIRC PKCS#1 even supports more than two modulus factors in it's private key format (not that it is particularly useful for anything).

Re: 4096 RSA key in the strongset factored?

#104

Post by jugad »

monochromatic wrote: post #26

> And the first factor - get a load of this - is 231. Which... yes, 231 = 3 * 77. Why isn't the first factor just 3 then?

They used the GCD (greatest common divisor) algo to find any common divisors between 2 large keys. 231 was such a number.

This signals to me that both the keys are corrupted/bad to have really small prime factors (3, 7 and 11).

I have taken courses on discrete math, cryptography and read a few prime generation algos. Its a standard first step to check numbers against primes upto a million or so (nowadays, a billion). No prime generation algo I can imagine generated these keys.

Re: 4096 RSA key in the strongset factored?

#105

Post by nacs »

userbinator wrote: post #37

We think properly created RSA keys couldn't possibly have such tiny factors because they were created by sophisticated algorithms, presumably would be two very large primes, and yet... this happens. Dumb-and-stupid trial division by the first 1000 or so primes wouldn't take much time and could've easily caught this. I see this as a nice precautionary tale that we may sometimes think too highly of sophisticated algori…

> If I deliberately generated a public key that was divisible by 3

This is already well known:

> When encrypting with low encryption exponents (e.g., e = 3) and small values of the m, (i.e., m https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Attacks_aga...

Re: 4096 RSA key in the strongset factored?

#106

Post by wfn »

asciilifeform wrote: post #95

Aaaand we found another two. One of which belongs to a GNU dev with some public presence... Still think it was 'cosmic rays' on SKS's machines? Do cosmic rays preferentially strike public keys belonging to major Open Source figures?

> Still think it was 'cosmic rays' on SKS's machines?

Just FYI, this kind of stuff seems to have been done before, with vulnerable keys found:

https://eprint.iacr.org/2012/064.pdf (2012),

https://factorable.net/

(these two are mentioned and linked to from https://blog.hboeck.de/archives/872-About-the-supposed-facto...)

And (off-topic) if you are wondering why some of your recent comments are being downvoted so much, it's probably because of the tone (saying things such as "good job repeating my research" when work of the same kind with results of the same kind had been done before (see above.))

Still an interesting result and curious re. SKS servers (not) checking subkeys etc...

also https://news.ycombinator.com/item?id=9562170

Re: 4096 RSA key in the strongset factored?

#107

Post by cramplet »

throwaway2391 wrote: post #80

I was extremely surprised to see the source of this at the top of HN, as I am familiar with this web site and its operator from an an extremely toxic online forum, which I won't mention or elaborate on. I am careful not to share negative remarks, but I will firmly state that I believe that this: >Consequently, the originally intended, civilised process of emailing the victim, keeping things quiet for a while to give…

The forum you are referring to is 8chan (http://8ch.net/), yes? Are you sure you are not trolling?

Re: 4096 RSA key in the strongset factored?

#108

Post by cramplet »

throwaway2391 wrote: post #98
rewqfdsa wrote: post #41

You shouldn't be surprised to see blatant lies from Mircea Popescu, who also claims that he's a billionare, that English literature literally does not exist, that bitcoin literally makes states and laws obsolete, and that nuclear weapons are ineffective.

In time for him to edit, I sent asciilifeform (the author of 'phuctor') mail on how I thought he could improve his comments here, just some suggestions to clean up the language so it's more civil for HN, rather than ad-hominem, antagonistic, etc. (As you can see below, I suggested only three deletions, and highlighted seven paragraphs as being very positive.) He published it on his blog called it "hate mail" and name…

More trolling by your antagonistic throwaway account, I see.

Re: 4096 RSA key in the strongset factored?

#109

Post by [deleted] »

cramplet wrote: post #108
throwaway2391 wrote: post #98

Earlier quoted context omitted.

In time for him to edit, I sent asciilifeform (the author of 'phuctor') mail on how I thought he could improve his comments here, just some suggestions to clean up the language so it's more civil for HN, rather than ad-hominem, antagonistic, etc. (As you can see below, I suggested only three deletions, and highlighted seven paragraphs as being very positive.) He published it on his blog called it "hate mail" and name…

More trolling by your antagonistic throwaway account, I see.

[deleted]

Re: 4096 RSA key in the strongset factored?

#110

Post by [deleted] »

asciilifeform wrote: post #90
throwaway2391 wrote: post #80

I was extremely surprised to see the source of this at the top of HN, as I am familiar with this web site and its operator from an an extremely toxic online forum, which I won't mention or elaborate on. I am careful not to share negative remarks, but I will firmly state that I believe that this: >Consequently, the originally intended, civilised process of emailing the victim, keeping things quiet for a while to give…

You are just the man to expose the sham, perhaps? Where did we cheat? Who and why placed the key on SKS? Or is Mircea's pact with Satan spiffy enough to enable him to alter the laws of arithmetic?

[deleted]
Post reply on HN