-
Notifications
You must be signed in to change notification settings - Fork 5
/
Copy pathREADME
180 lines (138 loc) · 7.57 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
-----------------------------------------
CONSTANT TIME IMPLEMENTATION OF BCH CODES
-----------------------------------------
1. OVERVIEW
-----------
This is an implementation of binary BCH codes encoding and decoding [1], with
decoding implemented in constant time. Galois fields GF(2^m) with 2 < m < 16
are supported. Primitive BCH codes are supported as well as shortened BCH codes
built by cutting the first coordinates from a primitive BCH code. Three binaries
can be built: 'generate', 'test_*' and 'time_*'. Binary 'generate' generates
parameter files for a chosen BCH code. Binary 'test_*' does a simple test of
encoding followed by decoding with displays. Binary 'time_*' takes time
measurements in CPU cycles of the decoding process.
Files are organized as follows:
- bin/: generated binaries
- doc/: doxygen files
- doc/html/: documentation generated by doxygen
- inc/: header files
- inc/lut/: hardcoded lookup tables
- inc/codes/: files related to specific BCH codes
- obj/: object files generated during compilation
- src/: source code
- Makefile: makefile
2. INSTALLATION INSTRUCTIONS
----------------------------
2.1 Requirements
The following softwares are required: make and gcc.
A machine supporting the CLMUL (Carry-Less MULtiplication) instruction set is
recommended to profit from all the implemented features.
2.2 Compilation step
Three targets yield binaries:
- generate: builds binary 'generate'.
- lutmul: (LookUp Table MULtiplication) This target outputs two binaries:
'test_lutmul_PARAM' and 'time_lutmul_PARAM' where the suffix PARAM defines
the BCH code parameters (see 2.3). Both are compiled using lookup tables
for Galois field multiplication which is ideal for use on Galois field GF(4096)
and smaller.
- pclmul: This target also outputs the two binaries 'test_pclmul_PARAM' and
'time_pclmul_PARAM' where the suffix PARAM defines the BCH code parameters
(see 2.3) but builds them using the pclmulqdq instruction for Galois field
multiplication. This is the recommended choice for Galois fields larger
than GF(4096).
Note that targets lutmul and pclmul both output a third binary
'time_[lutmul|pclmul]_PARAM_once'. This binary is a subprogram of time and
is not meant to be called directly.
2.3 Binaries
- generate: takes two arguments: the parameter m of the Galois field GF(2^m)
from which the BCH code will be built and a targeted correction capacity t.
The program computes, if possible, the maximum dimension k, the correction
capacity delta and the generator polynomial of the BCH code
(2^m-1, k, delta >= t). It then outputs a directory containing the files
necessary to compile the sources with this BCH code parameters. Options are
available to generate a shortened BCH code or to stop at parameter computation
and not output any files. Use 'generate --help' for more information.
- test_*: takes one argument. 1 is assumed if no argument is given. The program
generates that many random messages. Each message is encoded, injected with a
random correctible pattern of errors and decoded. Each decoded message is
matched against the original and the process stops if a decoding error is
encountered. Displays are printed at each stage.
- time_*: This binary measures decoding execution time of a BCH code. By default,
the BCH code (796, 256, 60) is used. To use another code, assuming proper
files have been generated with the binary 'generate', set variable BCHDIR
to the path of the directory containing the files. So, for example, to time
BCH code (1023, 16, 247), run
make generate
bin/generate 10 247
to generate a directory bch_1023_16_247 containing the files for this code.
Then run
make lutmul BCHDIR=bch_1023_16_247
bin/time_lutmul_1023_16_247
to execute measurements.
Some switches are available. See 'time --help' for more information.
- time_*_once: As stated in section 2.2, this is a subprogram of time and is not
meant to be used on its own. It performs and times one decoding.
3. DOCUMENTATION
----------------
3.1 Requirements
The following softwares are required: doxygen and bibtex.
3.2 Generation Step
- Run 'make doxygen' to generate the documentation
- Browse doc/html/index.html to read it
Note that not all documented code appears because of preprocessing,
but all code is documented in the source files.
4. ADDITIONAL INFORMATION
-------------------------
4.1 BCH codes decoding
BCH code decoding consists of three steps:
- Syndromes computation
- Error-locator polynomial computation
- Roots computation
Fore more information, see [2].
4.2 Implementation overview
Roots computation is done with an additive Fast Fourier Tranform (FFT) algorithm
by Gao and Mateer [3]. Syndromes computation uses the transpose of the
additive FFT as suggested by Bernstein, Chou and Swchabe in [4]. Galois field
arithmetic is implemented two ways in gf_lutmul.c and gf_pclmul.c, and used
in targets lutmul and pclmul respectively. The main difference is the underlying
implementation of field multiplication (see 2.2).
4.3 Constant time benchmarking
The times (in CPU cycles) output by the binary 'time_*' are obtained as follows.
Firstly, warmup decodings of random words are executed to heat the system.
Secondly, a distribution of error weights to be decoded is generated with a
spread from 0 to 1.1*delta, where delta is the correction capacity of the code.
Then for each of these weights, data sets are generated, that is random
codewords injected with the adequate number of errors. Each codeword is then
decoded multiple times and the minimum of these times is taken as to be the
measured execution time of decoding that codeword. Finally, minimums, means and
maximums of these (minimum) execution times are computed and displayed.
Note that binary 'time_*' does not perform the measures itself. It limits itself
to generating the data sets and calls binary 'time_*_once' to do measurements.
'time_*_once' takes one measurement and is called as many times as necessary by
'time'. This is done to prevent the cache from hiding leaking arrays.
4.4 Exporting the code
In order to use this implementation of BCH codes in another project, eleven
files need to be exported. First, generate the adequate files for the chosen
BCH code with 'generate' (see 2.3). This produces a BCH code parameters file
bch_PARAM.h and a BCH generator polynomial file bch_PARAM_poly.h. Then choose
an implementation of Galois field multiplication by selecting either gf_lutmul.c
or gf_pclmul.c. Add files optimizations.h, gf.h, gf_lut_1024.h, fft.c, fft.h,
fft_lut_1024_64.h, bch.c and bch.h. Lookup tables (files gf_lut_1024.h and
fft_lut_1024_64.h) are unnecessary if a Galois field other than GF(1024) is used
as long as code lines including these files are deleted. As a last step, include
the file bch_PARAM.h in all files requesting it and include the file
bch_PARAM_poly.h in your main.
5. REFERENCES
-------------
[1] Lin, Shu, and D. Costello. "Error-Correcting Codes." (1983).
[2] Joiner, Laurie L., and John J. Komo. "Decoding binary BCH codes."
Proceedings IEEE Southeastcon'95. Visualize the Future. IEEE, 1995.
[3] Gao, Shuhong, and Todd Mateer. "Additive fast Fourier transforms over finite fields."
IEEE Transactions on Information Theory 56.12 (2010): 6265-6272.
[4] Bernstein, Daniel J., Tung Chou, and Peter Schwabe.
"McBits: fast constant-time code-based cryptography."
International Workshop on Cryptographic Hardware and Embedded Systems.
Springer, Berlin, Heidelberg, 2013.
6. LICENCE
----------
This project is licensed under the GNU Lesser General Public License v3.0 - see the LICENSE file for details.