Archistar/archistar-smc — pull request #23 by jcflack (2014-11-02 16:29:58+00:00)
Title: More thorough GF256 tests and one resulting fix.

I was reading over the hand-cranked GF256 code and I could not trivially convince myself of the LOG_TABLE/ALOG_TABLE indexing, so I decided to add a more thorough test to work straight from algebraic definitions and verify the properties of a finite field (and then test pow, inverse, and div against the tested mult operation).

That did in fact turn up one problem with pow, only for the edge case a=0. mult handles zero factors cleverly by having LOG_TABLE[0] (which isn't truly a log) be greater than any sum of two true logs, and therefore point into a second half of ALOG_TABLE that is all zeros. But that trick doesn't survive in pow, where a log gets multiplied by p and then reduced mod 255 ... it just produces very strange values for 0^p.

I didn't think of any better way to fix pow than by adding a conditional.

Perhaps it doesn't really matter much if pow is broken for a=0, as (at least in ShamirPSS) it would not be expected to be called with a=0 as that would correspond to the secret itself. But it seemed safer to correct it. If that makes it too slow, then maybe it could be left unfixed but with the javadoc changed to define it only for a != 0.

As an aside, when I first noticed it failed the test, I added TestBCGF256Algebra to run the same tests on the BouncyCastle implementation, and that _also_ has a problem at a=0 (but only for p=0; they forgot that anything^0 is unity, even though 0^anythingelse is of course 0).