Re: broken RSA keys

[Alexander Cherepanov <ch3root () openwall com>]

On 05/04/2016 09:01 PM, Solar Designer wrote:
> On Wed, May 04, 2016 at 08:28:03PM +0300, Solar Designer wrote:
> > BTW, had I not realized the above, I would now come up with an even more
> > complex conspiracy theory about 149784613473514443594783892995, which is
> > 0x1E3FAEDA6A4F093A7C0F5A603, so:
> >
> > limb[0] = 0xC0F5A603
> > limb[1] = 0xA4F093A7
> > limb[2] = 0xE3FAEDA6
> > limb[3] = 1
> >
> > which satisfies:
> >
> > limb[1] = limb[0] + limb[2] + 2
> >
> > No idea why it's "+ 2" here
>
> Actually, it's "- 2", not "+ 2".  Sorry.  Not that it matters, but I was
> uncomfortable leaving the error uncorrected in case someone wants to try
> and figure out why exactly this artifact manifests itself like it does.
>
> There's probably an explanation of why the algorithm is likely to hit
> numbers of this form, but this is beside the point for software bugs,
> which is what I want us to discuss further in this thread.

Quoted relationship between limbs holds only mod 2**32 and written 
without wrapping looks like this:

limb[1] = limb[0] + limb[2] - 2 - 2**32

It also means that the original number is a multiple of 2**32 + 1. More 
precisely, it's a product of 2**32 + 1 and a number with limbs (1, 
limb[2] - 2, limb[0]).

--
Alexander Cherepanov