Corpos Binários

Transcrição

Corpos Binários

Algoritmos Criptográficos
Corpos Binários
Corpos Binários:
Implementação em Software
Julio César López Hernández
[email protected]
Instituto de Computación
Universidad de Campinas (UNICAMP)
Brasil
Julio López
2007
Corpos Binários
Parte I
Aritmética em F2m
Julio López
2007
Corpos Binários
Roteiro
1. Motivação
2. Definição de F2m
3. Bases Normais
4. Bases Polinomiais
5. Aritmética em F2m (software)
• Soma
• Quadrado
• Multiplicação
• Divisão (cálculo de inversos)
Julio López
2007
Corpos Binários
Roteiro...
6. Técnicas avançadas
• Os parâmetros NIST (FIPS 186-2)
• Métodos otimizados para multiplicar
• Métodos otimizados para calcular inversos
• Métodos para calcular a trace de um elemento finito
• Métodos para calcular raı́zes quadradas em F2m
• Métodos para resolver equações da forma x2 + x = a
Julio López
2007
Corpos Binários
Motivação
• Os corpos binários F2m têm aplicações em muitas áreas, tais
como a teoria dos códigos e criptografia.
• Criptografia de curvas elı́pticas baseada em corpos binários: 10
curvas NIST.
• Criptografia de curvas hiperelı́pticas baseada em corpos
binários.
• Emparelhamentos bilineares sobre curvas elı́pticas binárias.
• O algoritmo AES é baseado no corpo binário F28
Julio López
2007
Corpos Binários
O corpo finito GF (2) = F2
GF (2) = F2 = {0, 1}
• (F2 , +) é um grupo abeliano (0)
• (F2∗ , ·) é um grupo abeliano (1)
• Para todo a, b, c ∈ F2 , a · (b + c) = a · b + a · c
• a + b = a xor b = a + b mod 2
0 + 0 = 0
Julio López
1 + 0
= 1
0 + 1
= 1
1 + 1
= 0
2007
Corpos Binários
O corpo finito GF (2m ) = F2m
• O corpo finito F2m é um espaço vetorial de dimensão m sobre
GF (2) = {0, 1} chamado corpo binário ou corpo finito de
caracterı́stica dois.
• Seja o conjunto {α0 , α1 , α2 , . . . , αm−1 } uma base de F2m sobre
F2 . Então qualquer elemento a ∈ F2m pode ser representado
Pm−1
como a = i=0 ai αi , onde ai ∈ GF (2).
• O vetor binário associado ao elemento a é (a0 a1 a2 . . . am−1 ).
• Portanto, o corpo binário F2m pode ser visualizado como 2m
cadeias binárias de comprimento m.
F2m = {(a0 a1 . . . am−1 ) : ai ∈ {0, 1}}
Julio López
2007
Corpos Binários
O corpo finito F2m ...
• Para todo a ∈ F2m , a + a = 0 ( 2a = 0)
(caracterı́stica dois)
• Para todo a, b ∈ F2m , (a + b)2 = a2 + b2
F2m é um corpo finito onde:
-=+
2a = 0
√
√
√
a+b= a+ b
Julio López
2007
Corpos Binários
Bases para F2m
• Base Polinomial: {xm−1 , xm−2 , · · · , x, 1},
xi = (0, · · · , 0, 1, 0, · · · , 0)
A multiplicação pode ser implementada de forma eficiente
(hardware/software)
21
22
2m−1
• Base Normal: {β, β , β , . . . , β
}, β ∈ F2m .
O quadrado é eficiente. A multiplicação e uma operação
complexa para alguns valores de m. (hardware/software)
1
2
m−1
• Base Normal Gaussiana: {β, β 2 , β 2 , . . . , β 2
}, β ∈ F2m .
A multiplicação é baseada em permutações (bom para
hardware).
Julio López
2007
Corpos Binários
Base normal
• Teorema: Para todo corpo binário F2m , exite um elemento
β ∈ F2m tal que o conjunto :
21
22
{β, β , β , . . . , β
2m−1
}
forma uma base, chamada base normal.
• O pequeno teorema de Fermat:
m
2
Para todo a ∈ F2m , a = a.
−1
– método para calcular inversos: a
2
2m −1
=a
– método para calcular quadrados a = am−1 +
Julio López
Pm−1
i=1
ai
2007
Corpos Binários
Base normal...
• Seja a = (a0 a1 . . . am−2 am−1 ) um elemento em F2m . Então,
2
a
= (a0 β + a1 β
= a0 β
21
21
+ a1 β
+ . . . + am−1 β
22
= am−1 β + a0 β
2m−1 2
+ . . . + am−1 β
21
)
2m
+ . . . + am−2 β
(β
2m
= β)
2m−2
= (am−1 a0 a1 . . . am−2 )
O quadrado de um elemento finito é uma simples rotação (à
direita) da representação vetorial do elemento. (Operação
rápida em hardware)
• A multiplicação em bases normais é em geral uma operação
complexa. NIST recomenda bases normais Gaussianas, isto é,
bases normais onde a multiplição é mais eficiente que o caso
geral. Em particular, para m = 163, 233, 283, 409 e 571.
Julio López
2007
Corpos Binários
Bases normais: implementação em software
Software Multiplication using Gaussian Normal Bases
R. Dahab, D.Hankerson, F. Hu, M. Long, J. López and A. Menezes.
IEEE Transactions on Computers, vol 55, No. 8, August 2006.
Julio López
2007
Corpos Binários
Base polinomial
• Seja f (x) um polinômio binário irredutı́vel de grau m, então:
F2m = F2 [x]/ < f (x) >
Base : {xm−1 , xm−2 , · · · , x, 1}
• Seja a ∈ F2m . Então,
a =
m−1
X
ai xi
i=0
= am−1 xm−1 + am−2 xm−2 + · · · + ai x + a0
= (am−1 am−2 · · · a1 a0 )
Julio López
2007
Corpos Binários
Exemplo: F28
• f (x) = x8 + x4 + x3 + x + 1 um polinômio irredutı́vel de grau 8
• F28 =
{0x00,
0x01,
0x02,
0x03,
0x04,
0x05,
0x06,
0x07,
0x08,
0x09,
0x0A,
0x0B,
0x0C,
0x0D,
0x0E,
0x0F,
0x10,
0x11,
0x12,
0x13,
0x14,
0x15,
0x16,
0x17,
0x18,
.
.
.
.
.
.
0x19,
.
.
.
.
.
.
0x1A,
.
.
.
.
.
.
0x1B,
.
.
.
.
.
.
0x1C,
.
.
.
.
.
.
0x1D,
...
0x1E,
.
.
.
.
.
.
0x1F,
.
.
.
.
.
.
0xF 0,
0xF 1,
0xF 2,
0xF 3,
0xF 4,
0xF 5,
0xF 6,
0xF 7,
0xF 8,
0xF 9,
0xF A,
0xF B,
0xF C,
0xF D,
0xF E,
0xF F,
...
}
Julio López
2007
Corpos Binários
Exemplo: F28 ...
• f (x) = x8 + x4 + x3 + x + 1 = (1 0001 1011)
• A = x7 + x3 + 1 = (1000 1001) = 0x89
• B = x6 + x5 + x2 = (0110 0100) = 0x64
• Soma: A + B = ?
= x7 + x6 + x5 + x3 + x2 + 1 = (11101101) = 0xED
• Multiplicação: A × B = ?
= x13 + x12 + x8 + x6 + x2 mod f (x)
= x7 + x5 + x4 + x3 + x2 + 1 = 0xBD
• Multiplicação: x · A = ?
Julio López
2007
Corpos Binários
Corpos binários recomendados por SECG
SECG (Standards for Efficient Cryptography Group), 2000.
•
•
•
•
•
•
•
•
•
Julio López
F2113 ,
F2131 ,
F2163 ,
F2193 ,
F2233 ,
F2239 ,
F2283 ,
F2409 ,
F2571 ,
f (x) = x113 + x9 + 1
f (x) = x131 + x8 + x3 + x2 + 1
f (x) = x163 + x7 + x6 + x3 + 1
f (x) = x193 + x15 + 1
f (x) = x233 + x74 + 1
f (x) = x239 + x158 + 1
f (x) = x283 + x12 + x7 + x5 + 1
f (x) = x409 + x87 + 1
f (x) = x571 + x10 + x5 + x2 + 1
2007
Corpos Binários
Operações em F2163
• a, b ∈ F2163 , w = 32 bits
• a = 0x6 645F3CAC F1638E13 9C6CD13E F61734FB C9E3D9FB
• b = 0x7 BC4F3CAC B4338E1C AC6CD13D 00135498 B56C7280
• f (x) = x163 + x7 + x6 + x3 + 1
a+b = ?
a×b = ?
Julio López
2007
Corpos Binários
Base polinomial:
implementação em software
p=
m−1
X
i=0
ai xi , p(x) = At−1 · · · A1 A0
• Ai : w-bits; W = 8, 16, 32, 64, 128, t = ⌈m/W ⌉.
• p=
• Ai << j ,
word<< j
• Ai >> j ,
word>> j
∧
• Ai ⊕ Bj ,
word1
• Ai ⊙ Bj ,
word1 & word2 (AND)
• Ai ∨ Bj ,
word1 || word2 (OR)
Julio López
word2 (XOR)
2007
Corpos Binários
Soma em F2m
a = (am−1 , am−2 , · · · , a1 , a0 )
b = (bm−1 , bm−2 , · · · , b1 , b0 )
a+b =
ai xi +
m−1
X
(ai xor bi ) xi
m−1
X
ci xi
bi xi
i=0
i=0
=
m−1
X
m−1
X
i=0
=
i=0
= (cm−1 cm−2 · · · c1 c0 )
Julio López
2007
Corpos Binários
Soma em F2m
Entrada: a = (At−1 · · · A0 ), b = (Bt−1 · · · B0 ) ∈ F2m
Saı́da: c = a ⊕ b
1. for i = 0 to t − 1 do
1.1 Ci = Ai ⊕ Bi
2. return (c)
Julio López
2007
Corpos Binários
Quadrados em F2m
• a=
Pm−1
• a2 =
i=0
ai xi
Pm−1
i=0
ai x2i
• a = x7 + x5 + x3 + 1 = (10101001)
• a2 = x14 + x10 + x6 + 1 = ( 0100010001000001)
• Para cada b = (b7 b6 · · · b0 ) calcule T [b] = (0b7 0b6 · · · 0b1 0b0 )
Julio López
2007
Corpos Binários
Quadrados em F2m ...
Entrada: a ∈ GF (2m ), a = (At−1 · · · A0 ), t = ⌈m/32⌉.
Saı́da: a2 mod f (x).
1. Precomputação: para cada b = (b7 b6 · · · b0 ) calcule
T [b] = (0b7 0b6 · · · 0b1 0b0 )
2. for i = 0 to t − 1 do
2.1 Ai = (b3 |b2 |b1 |b0 ), bj um byte
2.2 C2i ← (T [b1 ]T [b0 ]), C2i+1 ← (T [b3 ]T [b2 ])
3. Calcule c(x) = (C2t−1 · · · C1 C0 ) mod f (x)
4. return (c(x))
Julio López
2007
Corpos Binários
Quadrados em F2m sem tabela
Algoritmo em C para inserir zeros
em uma palavra (32 bits):
Entrada: x = [000...0x15 x14 ...x1 x0 ]
Saı́da: x = [0x15 0x14 0...0x1 0x0 ]
x
x
x
x
=
=
=
=
((x
((x
((x
((x
& 0xFF00)<<8
<< 4) | x) &
<< 2) | x) &
<< 1) | x) &
| (x & 0x00FF);
0xF0F0F0F0;
0x33333333;
0x55555555;
ver: Hacker’s Delight, Henry S. Warren, Jr.,
Addison-Wesley, 2003.
Julio López
2007
Corpos Binários
Redução modular
• F2163 , f (x) = x163 + x7 + x6 + x3 + 1, w = 32 bits
• f (x) = 0x 8
•
0
0
0
0
c9
c(x) = a(x) · b(x) mod f (x)
• c = c324 x324 + · · · + c1 x + c0
• c = C10 C9 C8 C7 C6 C5 C4 C3 C2 C1 C0
• C10 = c351 x351 + c350 x350 + · · · + c320 x320
• m10 := c351 x188 + c350 x187 + · · · + c320 x157
′
• c = c + m10 · f (x) ≡ c mod f (x)
′
′
′
′′
′′
′′
′
′
′
′
′
′
′
• c ≡ 0 C9 C8 C7 C6 C5 C4 C3 C2 C1 C0 mod f (x)
′′
′′
′′
• · · · c ≡ C5 C4 C3 C2 C1 C0 mod f (x)
Julio López
2007
Corpos Binários
Redução modulo f (x) = x163 + x7 + x6 + x3 + 1
Entrada: Um polinômio binário de grau ≤ 324, f (x).
Saı́da: c(x) mod f (x).
1. for i from 10 downto 6 do
1.1 T ← C[i]
1.2 C[i − 6] ← C[i − 6] ⊕ (T ≪ 29)
1.3 C[i − 5] ← C[i − 5] ⊕ (T ≪ 4) ⊕ (T ≪ 3) ⊕ T ⊕ (T ≫ 3)
1.4 C[i − 4] ← C[i − 4] ⊕ (T ≫ 28) ⊕ (T ≫ 29)
Julio López
2007
Corpos Binários
Redução modulo f (x) = x163 + x7 + x6 + x3 + 1 ...
C[5] = 0xr7 r6 r5 r4 r3 r2 r1 r0 −→ 0x00000007
2. T ← C[5] ≫ 3
3. C[0] ← C[0] ⊕ (T ≪ 7) ⊕ (T ≪ 6) ⊕ (T ≪ 3) ⊕ T
4. C[1] ← C[1] ⊕ (T ≫ 25) ⊕ (T ≫ 26)
5. C[5] ← C[5]& 0x7
6. Return (C[5], C[4], C[3], C[2], C[1], C[0])
Julio López
2007
Corpos Binários
Métodos para multiplicação em F2m
• Método binário
• Método de Karatsuba
• Método de Montgomery (c = a · b · r −1 )
• Método de López-Dahab
Julio López
2007
Corpos Binários
Multiplicação em F2m
a = (am−1 am−2 · · · a1 a0 )
b = (bm−1 bm−2 · · · b1 b0 )
a∗b =
=
m−1
X
i=0
ai xi ∗
2m−2
X
m−1
X
bi xi (mod f (x))
i=0
ri xi (mod f (x))
i=0
= (r2m−2 r2m−1 · · · r1 r0 ) (mod f (x))
= (cm−1 cm−2 · · · c1 c0 )

 Pi a b ,
0 ≤ i ≤ m − 1,
j=0 j i−j
ri =
 Pm−1
j=i−m+1 aj bi−j , m ≤ i ≤ 2m − 2.
Julio López
2007
Corpos Binários
Exemplo: multiplicação em F24
Julio López
r0
= a0 b0
r1
= a0 b1
+ a1 b0
r2
= a0 b2
+ a1 b1
+ a2 b0
r3
= a0 b3
+ a1 b2
+ a2 b1
+ a3 b0
r4
=
a1 b3
+ a2 b2
+ a3 b1
r5
=
a2 b3
+ a3 b2
r6
=
a3 b3
2007
Corpos Binários
Método binário para multiplicar em F2m
a·b =
m−1
X
ai xi b(x) mod f (x)
i=0
= x · [· · · x · [x · am−1 b(x)]f + am−2 b(x) ]f + · · · ]f
+ a0 b(x)
a = am−1
am−2
am−3
···
···
a1
a0
c←0
for i from m − 1 to 0 do
c ← x · c mod f (x)
if ai = 1 then c ← c + b
endfor
Julio López
2007
Corpos Binários
Método binário para multiplicar em F2m ...
x · c mod f (x)
c=
0
cm−1
cm−2
···
c1
c0
x·c=
cm−1
cm−2
cm−3
···
c0
0
f (x) =
1
fm−1
fm−2
···
f1
f0
x · c mod f (x) =
0
cm−1
···
c1
′
c0
′
′
cm−2
′
c←x·c
if cm = 1 then c ← c + f
Julio López
2007
Corpos Binários
Método binário para multiplicar em F2m
a·b =
m−1
X
ai xi b(x) mod f (x)
i=0
= a0 b(x) + a1 [x · b(x)] + . . . + am−1 [x · xm−2 b(x)]
a = am−1
am−2
am−3
···
···
a1
a0
if a0 = 1 then c ← b; else c ← 0
for i from 1 to m − 1 do
b ← x · b mod f (x)
if ai = 1 then c ← c + b
endfor
Julio López
2007
Corpos Binários
Algoritmo López-Dahab (LR)
Indocrypt 2000
c(x) = a(x) · b(x)
a = A5 A4 A3 A2 A1 A0
Ai
=
a32i+31
pcj (x) =
···
5
X
a32i+j
···
a32i+0
a32i+j x32i b(x)
i=0
a(x) · b(x) =
Julio López
31
X
xj pcj (x)
j=0
2007
Corpos Binários
Algoritmo LD ...
c(x) = (A5 A4 A3 A2 A1 A0 ) ∗ b(x)
A5
A4
A3
A2
A1
A0
j
A j0 b(x)
A j4 b(x)
A j3 b(x)
A j1 b(x)
A j2 b(x)
A j5 b(x)
LShift
Julio López
2007
Corpos Binários
Algoritmo LD ...
c(x) = a(x) · b(x)
a = A5 A4 A3 A2 A1 A0
Ai
=
a32i+31
pcj (x) =
···
5
X
i=0
···
a32i+0
a32i+j x32i (xj · b(x))
a(x) · b(x) =
Julio López
a32i+j
31
X
pcj (x)
j=0
2007
Corpos Binários
Algoritmo LD com precomputação(w = 4)
a(x)b(x) = (A5 A4 A3 A2 A1 A0 ) · b(x)
0 ≤ u ≤ 15
pu (x) := (u3 x3 + u2 x2 + u1 x + u0 )b(x)
a(x)b(x) =
7
X
j=0
Julio López
5
X
x32i pAj (x)}
x4j {
i=0
i
2007
Corpos Binários
Algoritmo LD com precomputação(w = 4)...
u b(x)
A5
A4
A3
A2
A1
A0
u
LShift
Julio López
2007
Corpos Binários
O método de Karatsuba
• A0 , A1 , B0 , B1 polinômios de grau (m − 1)/2 − 1
• a(x) = A1 (x)xm/2 + A0 (x), b(x) = B1 (x)xm/2 + B0 (x)
a(x)b(x) =
Julio López
A1 B1 xm
+
[(A1 + A0 )(B1 + B0 ) + A1 B1 + A0 B0 ]xm/2
+
A0 B0
2007
Corpos Binários
Tempos de execução para multiplicar em F2163
Métodos
µsec.
LD (lr) (w = 4)
3.00
LD (lr)
8.40
LD (rl)
6.87
Karatsuba + LD (w = 4)
3.92
Binário
12.36
Pentium II 400 MHz
Julio López
2007
Corpos Binários
Métodos para calcular inversos em F2m
• Algoritmo de Euclides Estendido
• Algoritmo Binário I : (Schroeppel, 1995)
• Algoritmo Binário II: (Chang, 2001)
• Algoritmo Binário III: (Chien-Hsing Wu, 2004)
• Algoritmo de Itoh-Tsujii, 1988
Julio López
2007
Corpos Binários
Algoritmo de Euclides estendido
• a g1 + h1 f = 1; mcd(a, f ) = 1
• a g1 ≡ 1 mod f (x) ⇔ a−1 = g1 mod f (x)
1.
u ← a, v ← f, g1 ← 1, g2 ← 0
2.
while (u 6= 1)
2.1 j ← grau(u) - grau(v)
2.2 if j < 0 then u ↔ v, g1 ↔ g2 , j ← −j.
2.3 u ← u + xj v
2.4 g1 ← g1 + xj g2
3.
Julio López
return (g1 = a−1 )
2007
Corpos Binários
Algoritmo de Euclides estendido
com duplicação de código
• a gi + hi f = 1; mcd(a, f ) = 1
• a gi ≡ 1 mod f (x) ⇔ a−1 = gi mod f (x)
1.
u ← a, v ← f, g1 ← 1, g2 ← 0, gt ← grau(u).
2.
while (gt 6= 0)
2.1 j ← grau(u) - grau(v)
2.2 if j ≥ 0 then
u ← u + xj v,
tg ← grau(u)
g1 ← g1 + xj g2 , r1 ← 1
else
v ← v + x−j u, tg ← grau(v)
g2 ← g2 + x−j g1 , r1 ← 0
3.
Julio López
if (r1 = 1) then return (g1 = a−1 ) else return (g2 = a−1 )
2007
Corpos Binários
Algoritmo binário I
almost inverse algorithm
1.
u ← a, g1 ← 1, v ← f, g2 ← 0
2.
while (u0 = 0)
u ← u/x,
g2 ← xg2 ,
k ←k+1
3.
if (u = 1) then return (g1 , k)
4.
if grau(u) < grau(v) then u ↔ v,
5.
u ← u + v,
6.
goto 2.
g 1 ↔ g2
g 1 ← g1 + g2
Saı́da: k ∈ [0, 2m − 1], g1 · a ≡ xk ( mod f (x))
Julio López
2007
Corpos Binários
Algoritmo binário II
1.
u ← a, v ← f, g1 ← 1, g2 ← 0
2.
while (u 6= 1 and v 6= 1) do
2.1 while (u0 = 0)
u ← u/x,
g1 ← (g1 + g1 (0) · f )/x
2.2 while (v0 = 0)
v ← v/x,
g2 ← (g2 + g2 (0) · f )/x
2.3 if grau(u) ≥ grau(v) then
u←u+v
g1 ← g1 + g2
else
v ←v+u
g2 ← g2 + g1
3.
Julio López
if (u = 1) then return (g1 = a−1 ) else return (g2 = a−1 )
2007
Corpos Binários
Algoritmo binário III
1.
(r, s, u, v, δ) ← (a, f, 1, 0, −1)
2.
for k = 1 to 2m − 1 do
if (r0 = 0)
if (δ < 0)
(r, s, u, v) ← (r + s, r, u + v, u), δ ← −δ
else
(r, u) ← (r + s, u + v)
(r, u) ← (r/x, (u/x)f ), δ ← δ − 1
3.
Julio López
return (v = a−1 )
2007
Corpos Binários
O método de Itoh-Tsujii
• a ∈ F2m , a 6= 0
• a · b = 1, b = a−1 ∈ GF (2m )
m
a2 = a
−1
a
2m −2
=a
2m−1 −1 2
= (a
)
m ı́mpar:
2m−1 − 1 = (2(m−1)/2 − 1)(2(m−1)/2 + 1).
m par:
2m−1 − 1 = 2(2m−2 − 1) + 1 = 2(2(m−2)/2 − 1)(2(m−2)/2 + 1) + 1.
Julio López
2007
Corpos Binários
O Método de Itoh-Tsujii...
2m−1 −1
a
=

2(m−1)/2 −1 2(m−1)/2 +1

)
,

 (a



a2(2
(m−2)/2
−1)(2(m−2)/2 +1)+1
m ı́mpar
, m par
• Número de multiplicações =
número de uns na representação binária de m − 1.
• Número de quadrados = m − 1
Julio López
2007
Corpos Binários
O método de Itoh-Tsujii
Entrada: a ∈ F2m , a 6= 0, m odd.
Saı́da: c = a−1 .
1. A ← a2 , B ← 1, x ← (m − 1)/2.
2. While x 6= 0 do
x
2.1 A ← A · A2 .
2.2 If x is even then x ← x/2
else B ← B · A, A ← A2 , x ← (x − 1)/2
3. Return (B)
Julio López
2007
Corpos Binários
Exemplo: inverso em F2163
2163 − 2 =
281 − 1 =
240 − 1 =
220 − 1 =
210 − 1 =
25 − 1 =
22 − 1 =
2163 − 2 =
2(2162 − 1) = 2(281 − 1)(281 + 1)
2(240 − 1)(240 + 1) + 1
(220 − 1)(220 + 1)
(210 − 1)(210 + 1)
(25 − 1)(25 + 1)
2(22 − 1)(22 + 1) + 1
2+1
2(281 + 1)[2(240 + 1)(220 + 1)(210 + 1)(210 + 1)
(25 + 1)(2(2 + 1)(22 + 1) + 1) + 1]
a−1 requer 9 multiplicações e 162 quadrados.
Julio López
2007
Corpos Binários
Tempos de execução para F2m
Operações
m = 163
m = 233
m = 283
Soma
0.04
0.04
0.05
Redução Modular
0.11
0.13
0.19
Quadrados
0.20
0.23
0.32
Mult-LD (w = 4)
1.30
2.27
2.92
Inverso-AEE
10.5
18.6
28.2
Inverso-AIA
15.2
20.1
-
Inverso-BIN
16.0
28.9
-
Tempos em microsegundos, Pentium III 800 Mhz (icc Intel 6.0)
Julio López
2007
Corpos Binários
Roteiro
6. Técnicas avançadas
• Os parâmetros NIST (FIPS 186-2)
• Métodos otimizados para multiplicar
• Métodos otimizados para calcular inversos
• Métodos para calcular a trace de um elemento finito
• Métodos para calcular raı́zes quadradas em F2m
• Métodos para resolver equações da forma x2 + x = a
Julio López
2007
Corpos Binários
A função trace
A função trace sobre F2m é a função T r : F2m → F2m definida por:
2
T r(c) = c + c + c
22
+c
23
+ ···+ c
2m−1
Propriedades:
1. T r(c) = T r(c2 ) = T r(c)2 , e T r(c) ∈ {0, 1}
2. T r(c + d) = T r(c) + T r(d)
3. Se (x, y) ∈ Ea,b (F2m ) então T r(x) = T r(a)
Julio López
2007
Corpos Binários
A função trace...
Bases polinomias:
T r(c) = T r(
Pm−1
i=0
i
ci x ) =
Pm−1
i=0
ci T r(xi )
For m = 163, T r(xi ) = 1 se e somente se i ∈ {0, 157}
Por tanto, T r(c) = c0 + c157 .
Bases normais:
T r(β) =
Pm−1
i=0
T r(c) = T r(
Julio López
β
2i
Pm−1
i=0
=1
2i
ci β ) =
Pm−1
i=0
ci T r(β)
2i
=
Pm−1
i=0
ci
2007
Corpos Binários
Raı́z quadrada
√
c
v
um−1
m−1
uX
X √
ci xi
ci xi ≡
≡ t
i=0
i=0
(m−1)/2
≡
X
i=0
i=0
(m−1)/2
≡
X
i=0
≡ cpar +
Julio López
(m−3)/2
X
√
√
2i
c2i+1 x2i+1
c2i x +
√
i
c2i x + x ·
√
(m−3)/2
X
c2i+1 xi
i=0
x · cimpar
2007
Corpos Binários
Raı́z quadrada ...
Método rápido para trinômios: f (x) = xm + xk + 1
Quando m ı́mpar e k ı́mpar:
1
x
√
x
≡ xm + xk (mod f (x)
≡ xm+1 + xk+1 (mod f (x)
≡ x
m+1
2
+x
k+1
2
(mod f (x)
Exemplo: f (x) = x409 + x87 + 1
√
c = cpar + x205 · cimpar + x44 · cimpar (mod f (x))
Julio López
2007
Corpos Binários
Raı́z quadrada...
Método rápido para trinômios: f (x) = xm + xk + 1
Quando m ı́mpar e k par:
xm
x
√
x
≡ xk + 1 (mod f (x))
≡ xk−(m−1) + x−(m−1) (mod f (x))
− m−1
2
≡ x
k
2
(x + 1) (mod f (x)
Exemplo: f (x) = x233 + x74 + 1
√
x ≡ x−116 (x37 + 1) (mod f (x))
≡ x−42 · x−74 (x37 + 1) (mod f (x))
√
Julio López
≡ (x32 + x191 )(1 + x159 )(x37 + 1) (mod f (x))
c = cpar + (x32 + x117 + x119 )(x37 + 1) · cimpar (mod f (x))
2007
Corpos Binários
Solução de x2 + x = c
Definição: A função Half-trace H sobre F2m (m ı́mpar) é definida
por:
H(c) = c + c
22
+c
24
+ ···+ c
2m−1
Propriedades:
• H(c + d) = H(c) + H(d) para todo c, d ∈ F2m
• H(c) é uma solução da equação x2 + x = c + T r(c)
• A equação x2 + x = c tem solução se e somente se T r(c) = 0
• Se T r(c) = 0, H(c) e H(c) + 1 são soluções de x2 + x = c
• H(c) = H(c2 ) + c + T r(c) para todo c ∈ F2m
Julio López
2007
Corpos Binários
Métodos para resolver x2 + x = c
Assuma T r(c) = 0
P(m−1)/2 22i
• x = i=0
c (half-trace)
Pm−1
Pm−1
• x = H( i=0 xi ) = i=0 ci H(xi )
Para reduzir o armazenamento, pode-se aplicar a fórmula
H(xi ) = H(xi/2 ) + xi/2 + T r(xi ) para i par.
• Para reduzir ainda mais o armazenamento, pode-se utilizar a
forma do polinômio irredutı́vel f (x) (especialmente trinômios).
Julio López
2007
Corpos Binários
Algoritmo (FHLM, 2004)
Entrada: c ∈ F2m , T r(c) = 0, m ı́mpar.
Saı́da: Uma solução de x2 + x = c.
1. Precalcule H(xi ) para todo ı́mpar i, 1 ≤ i ≤ m − 2
2. s ← 0
3. for i from (m − 1)/2 downto 1 do
3.1 If c2i = 1 then c ← c + xi , s ← s + xi
P(m−1)/2
4. s ← s + i=1
c2i−1 H(x2i−1 )
Para m = 163, o Algoritmo FHLM utiliza 81 elementos finitos de
precomputação. A versão mais otimizada utiliza 21 elementos de
precomputação. (Menos que 21 elementos?)
Julio López
2007
Corpos Binários
Tempos de execução para F2m
Operações
F2163
F2233
Raı́z Quadrada
0.69
0.26
Soluçaõ x2 + x = c
0.89
1.17
Multiplicação
1.32
2.28
Tempos em microsegundos, Pentium III 800 Mhz (icc Intel 6.0)
Julio López
2007
Corpos Binários
Bibliografia
• Software Multiplication using Gaussian Normal Bases, R.
Dahab, D.Hankerson, F. Hu, M. Long, J. López y A. Menezes.
IEEE Transactions on Computers, vol 56, N0. 8, August 2006.
• A Custom Instruction Approach for Hardware and Software
Implementations of Finite Field Arithmetic over F2163 using
Gaussian Normal Bases, Marcio Juliato, Guido Araujo,
Ricardo Dahab e Julio López, FPT-2005.
• Field Inversion and Point Halving Revisited, Kenny Fong,
Darrel Hankerson, Julio López y Alfred Menezes, IEEE
Transactions on Computers, vol 53, No. 8, August 2004.
Julio López
2007
Corpos Binários
Bibliografia...
• Software Implementation of Elliptic Curve Cryptography over
Binary Fields, D. Hankerson, J. López y A. Menezes,
Cryptographic Hardware and Embedded Systems-CHES 2000,
LNCS 1965, pp. 1-24, 2000.
• High-Speed, Low-Complexity Systolic Designs of Novel
Iterative Division Algorithm in GF (2m )., Chien-Hsing Wu,
Chien-Ming Wu, Ming-Der Shieh y Yin-Tsung Hwang, IEEE
Transactions on Computers, Vol. 53, No. 3, 2004.
• Guide to Elliptic Curves Cryptography, Darrel Hankerson,
Alfred Menezes y Scott Vasntone, Springer Verlag, 2004.
• Optimal Irreducible Polynomials for GF (2m ) Arithmetic,
Michael Scott, e-print 192, 2007.
Julio López
2007

Corpos Binários

Transcrição

Documentos relacionados

Untitled

opgpàfgafhàfàcgràmph`segta ugbaàpilloppihsegafiavilolnaoba