Cryptography Reference
In-Depth Information
done by adding the rows of M corresponding to the non-zero bits of p .Aswe
do not store M but just its compressed representation, only the bits p it for all
0
1) can be encrypted directly by adding the corresponding sig-
natures. To encrypt all other bits of p the corresponding rows of M have to be
reconstructed from K pub first. The components h i,j of a dyadic matrix Δ ( h, t )
are normally computed as h i,j = h i⊕j which is a simple reordering of the ele-
ments of the signature h . Unfortunately, we cannot use this equation directly
because the public key is stored as an array of ( n
i
( l
d
d ) / 8elementsoftype
uint8_t . Furthermore, for every t = 64 bits long substring of the plaintext a
different length-( n
k )( l
k ) signature has to be used for encryption.
Decryption. For decryption we use the equivalent shortened Goppa code Γ ( L ,
G ( x )) defined by the Goppa polynomial G ( x ) and a (permuted) support se-
quence L F 2 16 . The support sequence consists of n = 2304 elements of
F 2 16 and is 4 . 5 KBytes in size. We store the support sequence in an array of
type gf16_t and size 2304. The Goppa polynomial is a monic separable poly-
nomial of degree t = 64. As t is a power of 2, the Goppa polynomial is sparse
and of the form G ( x )= G 0 + 6
i =0 G 2 i x 2 i . Hence, it occupies just 8
16 bits
storage space. We can store both the support sequence and the Goppa polyno-
mial in the SRAM of the microcontroller. Furthermore, we precompute the se-
quence Diag ( G ( L 0 ) 1 ,...,G ( L n− 1 ) 1 ) for the parity-check matrix V t,n ( L ,D ).
·
Due to the construction of the Goppa polynomial G ( x )= t− 1
z i )where
z i =1 /h i + ω with a random offset ω , the following holds for all G ( L jt + i ) 1 .
i =0 ( x
G ( L jt + i ) 1 = t− 1
( L jt + i + z r ) 1 = t− 1
(1 /h jt + i +1 /h r +1 /h 0 ) 1 = t− 1
h jt + r = jt + t− 1
h r
r =0
r =0
r =0
r = jt
h denotes a signature obtained by puncturing and permuting the signature h
for the large code C dyad such that h = h
P where P is the secret permutation
matrix. Hence, the evaluation of the Goppa polynomial on any element of the
support block ( L jt ,...,L jt + t− 1 )where j
·
leads
to the same result. For this reason, only n/t = l =36valuesoftype gf16_t need
to be stored. Another polynomial we need for Patterson's decoding algorithm is
W ( x ) satisfying W ( x ) 2
∈{
0 ,...,l
1
}
, i
∈{
0 ,...,t
1
}
x mod G ( x ). As the Goppa polynomial G ( x )issparse,
the polynomial W ( x ) is also sparse and of the form W ( x )= W 0 + 5
i =0 W 2 i x 2 i .
W ( x ) occupies 7
·
16 bits storage space.
Syndrome Computation. The first step of the decoding algorithm is the syn-
drome computation. Normally, the syndrome computation is performed through
solving the equation S c ( x )= S e ( x )
1
mod G ( x )where E denotes a
L i
x
i∈E
1
x−L i
set of error positions. The polynomial
satisfies the equation
t
1
1
G ( L i )
G j L i j−s− 1
L i
mod G ( x ) ,
0
s
t
1
(1)
x
j = s +1
Search WWH ::




Custom Search