Mercurial > yubikey-lua / file comparison
comparison: aeslua/gf.lua
aeslua/gf.lua
- changeset 0
- 598d09faf89c
equal
deleted
inserted
replaced
| -1:000000000000 | 0:598d09faf89c |
|---|---|
| 1 local bit = require("bit"); | |
| 2 | |
| 3 -- finite field with base 2 and modulo irreducible polynom x^8+x^4+x^3+x+1 = 0x11d | |
| 4 local private = {}; | |
| 5 local public = {}; | |
| 6 | |
| 7 local aeslua = require("aeslua"); | |
| 8 aeslua.gf = public; | |
| 9 | |
| 10 -- private data of gf | |
| 11 private.n = 0x100; | |
| 12 private.ord = 0xff; | |
| 13 private.irrPolynom = 0x11b; | |
| 14 private.exp = {}; | |
| 15 private.log = {}; | |
| 16 | |
| 17 -- | |
| 18 -- add two polynoms (its simply xor) | |
| 19 -- | |
| 20 function public.add(operand1, operand2) | |
| 21 return bit.bxor(operand1,operand2); | |
| 22 end | |
| 23 | |
| 24 -- | |
| 25 -- subtract two polynoms (same as addition) | |
| 26 -- | |
| 27 function public.sub(operand1, operand2) | |
| 28 return bit.bxor(operand1,operand2); | |
| 29 end | |
| 30 | |
| 31 -- | |
| 32 -- inverts element | |
| 33 -- a^(-1) = g^(order - log(a)) | |
| 34 -- | |
| 35 function public.invert(operand) | |
| 36 -- special case for 1 | |
| 37 if (operand == 1) then | |
| 38 return 1; | |
| 39 end; | |
| 40 -- normal invert | |
| 41 local exponent = private.ord - private.log[operand]; | |
| 42 return private.exp[exponent]; | |
| 43 end | |
| 44 | |
| 45 -- | |
| 46 -- multiply two elements using a logarithm table | |
| 47 -- a*b = g^(log(a)+log(b)) | |
| 48 -- | |
| 49 function public.mul(operand1, operand2) | |
| 50 if (operand1 == 0 or operand2 == 0) then | |
| 51 return 0; | |
| 52 end | |
| 53 | |
| 54 local exponent = private.log[operand1] + private.log[operand2]; | |
| 55 if (exponent >= private.ord) then | |
| 56 exponent = exponent - private.ord; | |
| 57 end | |
| 58 return private.exp[exponent]; | |
| 59 end | |
| 60 | |
| 61 -- | |
| 62 -- divide two elements | |
| 63 -- a/b = g^(log(a)-log(b)) | |
| 64 -- | |
| 65 function public.div(operand1, operand2) | |
| 66 if (operand1 == 0) then | |
| 67 return 0; | |
| 68 end | |
| 69 -- TODO: exception if operand2 == 0 | |
| 70 local exponent = private.log[operand1] - private.log[operand2]; | |
| 71 if (exponent < 0) then | |
| 72 exponent = exponent + private.ord; | |
| 73 end | |
| 74 return private.exp[exponent]; | |
| 75 end | |
| 76 | |
| 77 -- | |
| 78 -- print logarithmic table | |
| 79 -- | |
| 80 function public.printLog() | |
| 81 for i = 1, private.n do | |
| 82 print("log(", i-1, ")=", private.log[i-1]); | |
| 83 end | |
| 84 end | |
| 85 | |
| 86 -- | |
| 87 -- print exponentiation table | |
| 88 -- | |
| 89 function public.printExp() | |
| 90 for i = 1, private.n do | |
| 91 print("exp(", i-1, ")=", private.exp[i-1]); | |
| 92 end | |
| 93 end | |
| 94 | |
| 95 -- | |
| 96 -- calculate logarithmic and exponentiation table | |
| 97 -- | |
| 98 function private.initMulTable() | |
| 99 local a = 1; | |
| 100 | |
| 101 for i = 0,private.ord-1 do | |
| 102 private.exp[i] = a; | |
| 103 private.log[a] = i; | |
| 104 | |
| 105 -- multiply with generator x+1 -> left shift + 1 | |
| 106 a = bit.bxor(bit.lshift(a, 1), a); | |
| 107 | |
| 108 -- if a gets larger than order, reduce modulo irreducible polynom | |
| 109 if a > private.ord then | |
| 110 a = public.sub(a, private.irrPolynom); | |
| 111 end | |
| 112 end | |
| 113 end | |
| 114 | |
| 115 private.initMulTable(); | |
| 116 | |
| 117 return public; |
