tag:blogger.com,1999:blog-19303585.post8417860176490562716..comments2019-06-07T23:00:27.316+00:00Comments on John Graham-Cumming: Why is the fifth part of the GCHQ "Can you find it?" challenge so easyUnknownnoreply@blogger.comBlogger2125tag:blogger.com,1999:blog-19303585.post-29045947580053377912013-09-19T11:41:04.874+00:002013-09-19T11:41:04.874+00:00Phil:
That makes a lot of sense. So the GCHQ folk...Phil:<br /><br />That makes a lot of sense. So the GCHQ folks probably encoded the URL in a 512 bit number and then found two primes that were close to it (prime1a and prime2) and got the modulus from it. <br /><br />They then decided to mess with prime1 to break the key itself so that OpenSSL etc. couldn't read it. Since modulus, prime1a and prime2 are all odd the +1 makes sense because it makes prime1 even (i.e. definitely not prime)<br /><br />That also, as you say, explains the repeated patterns appearing in the modulus (artifact of multiplication).<br /><br />Also if you calculate the totient value from prime1a and prime2 then you find that the privateExponent in the RSA key file is good (i.e. privateExponent * publicExponent mod totient = 1). Further evidence of the validity of your prime1a.<br /><br />And, further, the values for exponent1 and exponent2 have patterns (as you suggest) because they are the remainder after doing mod prime1a-1 and prime2-1. I've checked them and that's where the pattern comes from.<br /><br />So, I think this gets to the bottom of it. Thanks for the comment!<br /><br />That only leaves me wondering why they set prime1 to modulus - prime1a - prime2 + 1.<br /><br />John Graham-Cumminghttps://www.blogger.com/profile/12998100764952319513noreply@blogger.comtag:blogger.com,1999:blog-19303585.post-43977094365458349752013-09-19T11:14:29.307+00:002013-09-19T11:14:29.307+00:00Yes, it was a bit of an anticlimax. I got stuck on...Yes, it was a bit of an anticlimax. I got stuck on this for a while because openssl kept choking on the private key.<br /><br />We know <b>prime1</b> is bogus because it's even. But if we assume the modulus value to be correct, then we can calculate the "proper" value of <b>prime1</b> as <b>(modulus / prime2)</b>. This turns out to be very close to the value of <b>prime2</b>:<br /><br />(bc:)<br /><b>prime1a = modulus / prime2<br />prime1a<br />77772E776874736973696C67756F656374737265687372692E656F63752E2F6B6C62\<br />74656863656C207920202020202020202020202020202020202120200A7F</b><br /><br />Both <b>prime1a</b> and <b>prime2</b> are probable primes according to GMP, which is encouraging.<br /><br />And apparently the original (i.e., faked) value of <b>prime1</b> is <b>{modulus - prime1a - prime2 + 1)</b><br /><br />(bc:)<br /><b>prime1 - (modulus - prime1a - prime2)<br />1</b><br /><br />My hunch is that the repeating patterns followed by 'random' bytes in the exponent values are just a reflection of the repeated <b>0x20</b> bytes in the two primes (followed by the additional digits needed to make them prime).Phil Ronanhttps://www.blogger.com/profile/00560909228122424164noreply@blogger.com