A very compact Rijndael S-box
Loading...
Authors
Canright, David
Subjects
Cryptography.
Data encryption (Computer science)
Data encryption (Computer science)
Advisors
Date of Issue
2004
Date
2004
Publisher
Monterey, California. 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 16%. 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
Series/Report No
Department
Organization
National Security Agency (U.S.)
Identifiers
NPS Report Number
NPS-MA-04-001
Sponsors
Funder
Format
63 p.;28 cm.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.