5 ms·
>> Unfortunately, if you don't know how to factor p then you can't easily do that. The link says they don't know where p came from. Presumably someone construc
by phkahler 11y ago
>> Unfortunately, if you don't know how to factor p then you can't easily do that.
The link says they don't know where p came from. Presumably someone constructed it as a product of primes known only to them. I don't recall the state of the art in factorization, but if 1024 bits can be factored easily that's news to me. So the weakness would only be exploitable to whomever created p.
Why nobody checked the primality of it IDK.
- pbsd 11y agoOne of the factors is 3684787 = 271 x 13597, so I suspect this is more accidental than malicious. The generator, 2, does not seem to have pathologically small order, but I didn't check very far.
- 21 11y agoWow. 271 is a factor. Why not try dividing by all 32 bit numbers, to at least filter easy cases. Shouldn't take more than a few seconds.
- qwerty1793 11y agoThe following Sage script shows that p has no prime factors less than 2^32 other than 271 and 13597: p_list = [0xCC, 0x17, 0xF2, 0xDC, 0x96, 0xDF, 0x59, 0xA4, 0x46, 0xC5, 0x3E, 0x0E, 0xB8, 0x26, 0x55, 0x0C, 0xE3, 0x88, 0xC1, 0xCE, 0xA7, 0xBC, 0xB3, 0xBF, 0x16, 0x94, 0xD8, 0xA9, 0x45, 0xA2, 0xCE, 0xA9, 0x5B, 0x22, 0x25, 0x5F, 0x92, 0x59, 0x94, 0x1C, 0x22, 0xBF, 0xCB, 0xC8, 0xC8, 0x57, 0xCB, 0xBF, 0xBC, 0x0E, 0xE8, 0x40, 0xF9, 0x87, 0x03, 0xBF, 0x60, 0x9B, 0x08, 0xC6, 0x8E, 0x99, 0xC6, 0x05, 0xFC, 0x00, 0xD6, 0x6D, 0x90, 0xA8, 0xF5, 0xF8, 0xD3, 0x8D, 0x43, 0xC8, 0x8F, 0x7A, 0xBD, 0xBB, 0x28, 0xAC, 0x04, 0x69, 0x4A, 0x0B, 0x86, 0x73, 0x37, 0xF0, 0x6D, 0x4F, 0x04, 0xF6, 0xF5, 0xAF, 0xBF, 0xAB, 0x8E, 0xCE, 0x75, 0x53, 0x4D, 0x7F, 0x7D, 0x17, 0x78, 0x0E, 0x12, 0x46, 0x4A, 0xAF, 0x95, 0x99, 0xEF, 0xBC, 0xA6, 0xC5, 0x41, 0x77, 0x43, 0x7A, 0xB9, 0xEC, 0x8E, 0x07, 0x3C, 0x6D] p = 0 for num in p_list: p = (p << 8) + num for i, prime in enumerate(primes(2^32)): if i % 100 == 0: print str(prime) + '\r', if p % prime == 0: print('\n')
- williamstein 11y agoSage also has an is_prime function, which provably show that p is not prime: "is_prime(p)". This takes less than 1ms to run. Proving primality of a 1024 bit prime in Sage takes a few seconds, and for a 2048 bit prime about a minute. Sage uses PARI for this, with sophisticated elliptic curve based algorithms called ECPP("=elliptic curve primality proving"), which are non-deterministic (unlike AKS) but fast in practice and provably correct. https://goo.gl/34uxJl https://goo.gl/34uxJl
- baby 11y agoHave you tried dividing the order by 271 and 13597 and search again on that?
- deleted 11y ago[deleted]
- orthopteroid 11y agoCoincidentally, 13597 base 10 is 351d hex, which in unicode is defined as 'strong resistance'. http://www.charbase.com/351d-unicode-cjk-unified-ideograph http://www.charbase.com/351d-unicode-cjk-unified-ideograph
- tika 11y ago271 is rather small. Which means this fake prime was quite easy to generate.
- jibalt 11y ago"Presumably someone constructed it as a product of primes known only to them" It would be foolish to presume that. And knowing the factors of the Diffie-Hellman parameter isn't all that important.