[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <572A4BF8.9010303@openwall.com>
Date: Wed, 4 May 2016 22:22:32 +0300
From: Alexander Cherepanov <ch3root@...nwall.com>
To: oss-security@...ts.openwall.com
Subject: Re: broken RSA keys
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
Powered by blists - more mailing lists
Please check out the
Open Source Software Security Wiki, which is counterpart to this
mailing list.
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
