phc-discussions - RE: [PHC] multiply-hardening (Re: NoelKDF ready for submission)

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date: Mon, 10 Feb 2014 23:44:03 -0800
From: "Dennis E. Hamilton" <dennis.hamilton@....org>
To: <discussions@...sword-hashing.net>
Subject: RE: [PHC] multiply-hardening (Re: NoelKDF ready for submission)

Many, many years ago, Knuth published a paper about exponentiation by integers.  The speed-up he got beyond the standard version (working on bits of the exponent and squarings of the base) was in places where divisions were used instead of multiplications into the growing product for the result.  

I would be surprised if this wasn't in volume 2 of The Art of Computer Programming, probably in one or more of the problems.

I published a Pascal version (without the division speedups) for arbitrary integer exponents in Dr. Dobbs too many years ago.  While I was developing it, Knuth and I had a minor disagreement over what 0 to the power 0 should be.  (He voted for 1, I resolved it by returning 0/0 (by identity with 0 to the power 1-1) and letting the arithmetic of the given compiler and platform decide how to handle it.)

If you like, I'll see if I can track the Knuth paper and/or the TAoCP location.

 - Dennis

-----Original Message-----
From: Bill Cox [mailto:waywardgeek@...il.com] 
Sent: Monday, February 10, 2014 20:11
To: discussions@...sword-hashing.net
Subject: Re: [PHC] multiply-hardening (Re: NoelKDF ready for submission)

On Sat, Feb 8, 2014 at 10:16 PM, Samuel Neves <sneves@....uc.pt> wrote:
> On 09-02-2014 02:52, Bill Cox wrote:
> This is a well-known variant of the addition-chain problem. SPIRAL [1]
> generates the following code sequence, using 7 additions:

In 1984, I was infatuated with the president of the math club at
Berkeley (who was female - no, not Eve), where I hung out with a few
guys who were a lot like SolarDesigner, in that they were simply
smarter than me.  In some comp sci class the prof asked us to compute
x^n, for x and n integers, and of course we all came up with the
power-of-two standard solution, but I was a wise-ass and for the
specific constant the prof asked for, I gave a slightly improved
answer.  My super-genius friends and I grabbed this problem and
couldn't sleep for days.  We had asymptotic lower bounds on the number
of required multiplies, and a formula for increasing sized integers
that converged to it.  We wanted to talk with an expert, and Donald
Knuth was the guy, so one friend of mine who you might know from Junk
Yard Wars as Geo the Guestimator and I dropped by Stanford to see if
we could chat with Donald Knuth about it, but he was out for the
summer on sabbatical.  Thinking to call first was not the sort of
brilliant idea we would have come up with :-)

Geo and I were both from Palo Alto, so we were on our way home for the
weekend anyway.  I loved seeing this related problem, and had to write
some a quick hack to find optimal solutions.  I miss hanging out with
super-geeks who are way smarter than me... they are rare here in NC.
Thus the alter ego waywardgeek...

Bill