A very compact Rijundael S-box
Authors
Canright, David
Subjects
cryptography
encryption
AES
Rijndael
Galois fields
FPGA
ASIC
encryption
AES
Rijndael
Galois fields
FPGA
ASIC
Advisors
Date of Issue
2005-05-17
Date
Publisher
Monterey, CA; Naval Postgraduate School
Language
Abstract
One key step in the Advanced Encryption Standard (AES), or Rijndael, algorithm is called the "S-box", the only nonlinear step in each round of encryption/decryption. A wide variety of implementations of AES have been proposed, for various desiderata, that effect the S-box in various ways. In particular, the most compact implementation to date of Satoh et al. performs the 8-bit Galois field inversion of the S-box using subfields of 4 bits and of 2 bits. This work describes a refinement of this approach that minimizes the circuitry, and hence the chip area, required for the S-box. While Satoh used polynomial bases at each level, we consider also normal bases, with arithmetic optimizations; altogether, 432 different cases were considered. The isomorphism bit matrices are fully optimized, improving on the "greedy algorithm." The best case reduces the number of gates in the S-box by 20%. This decrease in chip area could be important for area-limited hardware implementations, e.g., smart cards. And for applications using larger chips, this approach could allow more copies of the S-box, for parallelism and/or pipelining in non-feedback modes of AES.
Type
Technical Report
Description
Revised version
Series/Report No
Department
Identifiers
NPS Report Number
NPS-MA-05-001
Sponsors
National Security Agency
Funding
Format
[68] p. ; 28 cm.