computing field inverses without EGCD()
saw this nice "trick" in black-eye's solution to "howl"

file history:
------------
oct15_2009 added Giuliano Bertoletti's email
oct08_2009 created


+-------------------------------------------------------------------------------
|Pinvers PROC poly_a:DWORD
|	; calculate a^(-1) mod X^31+X^3+1
|	; uses the square and multiply algo
|	; it's based on the fact in any GF(2^n) a^(-1)= a^(n-2) mod poly 
|	; in our case n-2=2^31-2=0x7FFFFFFE
|	; very little optimized
|	
|	pushad
|	mov ecx,7FFFFFFEh
|	xor ebx,ebx
|	inc ebx
|	mov edx,poly_a
|	.while ecx!=0
|		shr ecx,1
|		.if CARRY?
|			invoke Pmul,ebx,edx
|			mov ebx,eax
|		.endif
|		jecxz @F
|		invoke Pmul,edx,edx
|		mov edx,eax
|		@@:
|	.endw
|	mov dword ptr [esp+01Ch],ebx	
|	popad		
|	ret
+-------------------------------------------------------------------------------

think there is small typo, or "n" is used two different ways, should read:

+-------------------------------------------------------------------------------
|	; it's based on the fact in any GF(2^n) a^(-1)= a^((2^n)-2) mod poly 
+-------------------------------------------------------------------------------

didn't get many hits searching for this trick, except one mention of fermat's little theorem
does it really work? why?
does it work in other extension fields, not just GF(2^n) ?

came up with two arguments why it works:

first way:
GF(2^n) has mult cyclic group with 2^n-1 elems (zero not a member)
let g be a generator, the elems can be represented {1,g,g^2,...,g^(2^n-2)}
two elems g^x and g^y are inverses iff g^x*g^y=g^0 in this group 
-> two elems g^x and g^y are inverses iff x + y = 0 (mod 2^n-1) !!MAIN CONDITION!!

watch what happens when g^x is exponentiated by 2^n-2:
  (g^x)^(2^n-2)
= g^(x*(2^n-2))
= g^(x*(2^n-1-1))
= g^(x*(2^n-1)-x)

now we can test if this exponet satisfies the main condition:
x*(2^n-1)-x = y (mod 2^n-1)
         -x = y (mod 2^n-1)
        y+x = 0 (mod 2^n-1) yes!

second way:
fermat's theorem is:

   a^(p-1) = 1 (mod p)
 a*a^(p-2) = 1 (mod p)

i think fermat's condition that p be prime was just to enforce that the numbers
from [1,p] formed a group... here 2^n-1 (the size of the mult group) is not
prime, but since we know the elems are a group, maybe this theorem still works...
if it does then the elements a and a^(p-2) are inverses

...so this should really work for any field, not just binary extension fields, right?

let us try extension field GF(3^3) and irreducible p(x) = x^3 + 2*x + 1

here are the elements:

0
1
2
x
x + 1
x + 2
2*x
2*x + 1
2*x + 2
x^2
x^2 + 1
x^2 + 2
x^2 + x
x^2 + x + 1
x^2 + x + 2
x^2 + 2*x
x^2 + 2*x + 1
x^2 + 2*x + 2
2*x^2
2*x^2 + 1
2*x^2 + 2
2*x^2 + x
2*x^2 + x + 1
2*x^2 + x + 2
2*x^2 + 2*x
2*x^2 + 2*x + 1
2*x^2 + 2*x + 2

the mult group has all these except 0, and let us choose generator g = x, then {x^0, x^1, ..., x^(3^3-2)} =

g^00 = 1
g^01 = x
g^02 = x^2
g^03 = x + 2
g^04 = x^2 + 2*x
g^05 = 2*x^2 + x + 2
g^06 = x^2 + x + 1
g^07 = x^2 + 2*x + 2
g^08 = 2*x^2 + 2
g^09 = x + 1
g^11 = x^2 + x
g^12 = x^2 + x + 2
g^13 = x^2 + 2
g^14 = 2
g^15 = 2*x
g^16 = 2*x^2
g^17 = 2*x + 1
g^18 = 2*x^2 + x
g^19 = x^2 + 2*x + 1
g^20 = 2*x^2 + 2*x + 2
g^21 = 2*x^2 + x + 1
g^22 = x^2 + 1
g^23 = 2*x + 2
g^24 = 2*x^2 + 2*x
g^25 = 2*x^2 + 2*x + 1
g^26 = 2*x^2 + 1

with 3^3 elements total in the field, the mult group here has 3^3-1 (this is the "p" in fermat theorem)
thus any element exponentiatiated to the 3^3-2 = 25 should be its inverse

we test... 

example:
g^05 = 2*x^2 + x + 2
(2*x^2 + x + 2)^25 = x^2 + 1 = g^22
we can verify by seeing that g^05 * g^22 = g^00 = 1
or just enter it into pari:
(2*x^2 + x + 2)*(x^2 + 1) = 1
it works!

example:
g^01 = x
(x)^25 = 2x^2 + 1 = g^26
we can verify by seeing that g^01 * g^26 = g^00 = 1
or just enter it into pari:
x*(2x^2 + 1) = 1
it works!

the last example makes it seem almost obvious...
x * x^25 = x^26 and x^26 = 1 (mod 27)

and the method is very efficient - because even for large field like GF(2^128), you don't have to
multiply 2^128-2 times when using methods like exponentiation by squaring... you only need about
2*log(n) mults 

PARI NOTES:
p = Mod(1, 2)*x^3 + Mod(1, 2)*x + Mod(1, 2)
forvec(v=[[0,2],[0,2],[0,2]],print(lift((v[1]*x^2 + v[2]*x + v[3])*Mod(1,3)) % p))
for(i=0,26,print( lift( (((x)^i)*Mod(1,3) % p) )))


Update! Giuliano Bertoletti has another angle at explaining it, in this email from Oct12_2009:

+-------------------------------------------------------------------------------
| This hinges on the fact that for any finite field  F=GF(q), the order of any
| element x of the multiplicative | group F* = F \ { 0 }, divides q - 1.
| More specifially this follows from Lagrange's theorem that states that for any
| 
| subgroup H of a group G, the order of H divides the order or G.
| So, if t is the order of x in F*, by definition x^t = 1 and so does x^(s*t) =
| 1^s = 1, where s = (q - 1) / t is a positive integer.
| 
| Notice that unless q-1 is a prime, not all elements of F* are generators,
| still the inverse is unique and x^-1 = x^(q-2) because 
| x^(q-2) * x = x^(q-1) = 1.
| 
| If q-1 is not a prime however, for some x there exist a t < q-1, t divides q-1,
| for which x^(t-1) = x^-1, which basically means that for some x you could stop
| computing powers earlier (but this is clearly unusable since we do not know
| the order of an element in advance).
| 
| Cheers,
| Giulio.
+-------------------------------------------------------------------------------

~~~~~~~~~~~~~~
andrewl
oct09_2009
crackmes.de