Algebraic Aspects of the Advanced Encryption Standard Algebraic Aspects of the Advanced Encryption Standard by Carlos Cid Royal Holloway, University of London United Kingdom Sean Murphy Royal Holloway, University of London United Kingdom Matthew Robshaw France Telecom R&D France Springer Carlos Cid Information Security Group Royal Holloway University of London Egham, Surrey TW20 OEX United Kingdom email:
[email protected] Sean Murphy Information Security Group Royal Holloway University of London Egham, Surrey TW20 OEX United Kingdom email:
[email protected] Matthew Robshaw France Telecom Research and Development 38-40 rue du General-Leclerc 92794 Issy les Moulineaux, France email:
[email protected] Library of Congress Control Number: 2006929676 by Carlos Cid, Sean Murphy and Matthew Robshaw ISBN-10: 0-387-24363-1 ISBN-13: 978-0-387-24363-4 e-ISBN-10: 0-387-36842-6 e-ISBN-13: 978-0-387-36842-9 Printed on acid-free paper. © 2006 Springer Science^-Business Media, LLC. All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science-f-Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now know or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks and similar terms, even if the are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. Printed in the United States of America. 9 8 7 6 5 4 3 2 1 springer.com Contents Preface 1. INTRODUCTION TO THE AES 1 Background 2 Algebraic Perspectives 3 Overview of the Monograpli vii 1 1 3 3 2. MATHEMATICAL BACKGROUND 1 Groups, Rings, and Fields 2 Polynomial Rings 3 Linear Algebra 4 Finite Fields 5 Varieties and Grobner Bases 5 5 11 15 24 29 3. DESCRIPTION OF THE AES 1 Structure 2 Design Rationale 3 Small Scale Variants of the AES 35 35 41 43 4. ALGEBRAIC PROPERTIES OF THE AES 1 Round Structure 2 Algebraic Representations 3 Big Encryption System (BES) 4 Other Representations of the AES 5 Group Theoretic Properties 47 47 53 56 59 63 vi 5. 6.