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: Tue, 11 Feb 2014 07:53:38 -0500
From: Bill Cox <waywardgeek@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] multiply-hardening (Re: NoelKDF ready for submission)

On Tue, Feb 11, 2014 at 2:44 AM, Dennis E. Hamilton
<dennis.hamilton@....org> wrote:
> 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.

It is in volume 2.  I got the full set as a birthday present while in
college, and it's one of the few dead-tree books I still keep.  That's
why we knew Knuth would know about the problem.  I only remember my
own lame contribution to the mathematical work on the problem while we
were hacking it for days: the 2X possible speedup and proving that
some values of n approach it.  That's probably like 30 minutes of work
for a decent mathematician.  The other geeks went off and practically
invented a branch of mathematics based on the problem, with mind
boggling theorems I can no longer recall.

> 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

That would be awesome, but don't go to too much trouble.

Bill