Algebraic cryptanalysis

E E Algebraic Cryptanalysis

Gregory V. Bard

Algebraic Cryptanalysis

All rights reserved.

or dissimilar methodology now known or hereafter developed is forbidden.

to proprietary rights.

Library of Congress Control Number: 200992

Springer Dordrecht Heidelberg London New York

© Springer Science+Business Media, LLC 2009

Department of Mathematics

ISBN 978-0-387-88756-2 e-ISBN 978-0-387-88757-9

Printed on acid-free paper

This work may not be translated or copied in whole or in part without the written

permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY

The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are

not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject

10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection

DOI 10.1007/978-0-387-88757-9

Springer is part of Springer Science+Business Media (www.springer.com)

with any form of information storage and retrieval, electronic adaptation, computer software, or by similar

Gregory V. Bard

Fordham University

Bronx, NY 10458

USA

[email protected]

9845

Preface

Algebraic Cryptanalysis is the process of breaking codes by solving polynomial

systems of equations. In some ways this book began when the author began to ex￾plore cryptanalysis as a beginning graduate student, and realized with frustration

that no book whatsoever existed on the topic. Since that time, some books have

been written about Linear Cryptanalysis or Differential Cryptanalysis (e.g. [211]

and [214] cover both), but none on Algebraic Cryptanalysis, which is a rich and

growing field.

The author had some difficulty entering the field of Algebraic Cryptanalysis. Of

course step one is a solid background in Abstract Algebra, and a solid background

in cryptography1

. But after these twin foundations, one is not quite ready to read

research papers. This book is intended to be that stepping stone for graduate students

wishing to do their dissertation in Algebraic Cryptanalysis, or any other part of

cryptanalysis. Furthermore, researchers in other areas of Applied Abstract Algebra

or cryptography might benefit from seeing what is going on in cryptanalysis.

The nucleus for the book was my dissertation, under the title “Algorithms for the

Solution of Linear and Polynomial Systems of Equations over Finite Fields, with

Applications to Cryptanalysis”, submitted for the degree Doctor of Philosophy of

Applied Mathematics and Scientific Computation, defended in the Summer of 2007,

under the guidance of Professor Lawrence C. Washington. The author is extremely

grateful for Prof. Washington’s time, help and assistance at all stages.

In addition to being a text for graduate students, the author hopes the book will

be also useful for those currently working in the field as well. The pressures of page

counts often require that the internals or variants of algorithms cannot be published

in exhaustive detail in the standard scientific literature. Here, we have explained

and expanded upon several algorithms previously published by myself and by oth￾ers. Often the details left out of a published paper are those required to make an

algorithm work efficiently.

1

If these subjects are not yet ones that the reader is comfortable with, the author recommends

[216] for cryptography, and [119] for undergraduate Abstract Algebra.

v

vi

The backbone of the theory of polynomial systems of equations, over any field,

is algebraic geometry. This topic is exquisitely covered in Ideals, Varieties, and

Algorithms by Cox, Little and O’Shea [86], also published by Springer-Verlag. The

author therefore strongly encourages the reader to read [86] along with this text,

but note that [86] is not, by any means, a prerequisite for this book. The topic of

Grobner Bases, in particular, is deferred to [86], because they do an exquisite job ¨

there.

Last but not least, a handy desk-reference for finite fields is the encyclopedia

[165] by Lidl and Niederreiter. The previous edition of it, [164], was referred to as

“the Bible” at several finite field conferences.

Why this Book was Written

Tradition in Applied Mathematics, particularly in the USA, dictates that the re￾search of a doctoral dissertation be divided into journal articles, and published in the

years immediately following the defense. However, there is an interesting category

of work that is left in limbo. Original research can, of course, be published by normal

means. But work that is “dug out of the dust”, published but mostly forgotten, cannot

be published again. For example, the proofs of the equi-complexity of matrix opera￾tions, have been known for a long time, but not published together in one place; the

“degree dropper algorithm” (See Section 11.4 on Page 192) must have been known

for decades, but the author could not find a proof of it anywhere; the Method of

Four Russians for Multiplication was known anecdotally, but the original paper was

in Russian [21] and the most recent textbook version found was from 1974 [13, Ch.

6]; much work has been published on SAT-solvers, and how they work, but there

is no consolidated elementary introduction for those ignorant of the subject, as the

author found himself at the start of this work; many of the algorithms of Nicolas

Courtois, including ElimLin, are never fully and explicitly defined anywhere. The

author only wishes to see these techniques and algorithms used. While the author is

no master of exposition (as the reader is about to discover), he hopes that the space

which a book affords has allowed him to render this topic more comprehensible,

particularly to a graduate student audience, or even motivated undergraduates.

The author believes SAT-solvers, in particular, are a very underestimated tool.

Other communities rely upon them as a computational engine of great power. It

is hoped that the chapter on how SAT-solvers work will encourage scholars not to

consider them as black-boxes. Furthermore, the author hopes that the two chapters

on how to adapt polynomial systems of equations to be solved by SAT-solvers will

stimulate research into new and unrelated applications for these techniques, such

as solving combinatorial problems outside of cryptography such as graph-coloring.

Toward this end we include an appendix introducing this connection.

Preface

vii

Advice for Graduate Students

This book is primarily intended for those who are to embark on study in the field

of algebraic cryptanalysis, particularly graduate students about to begin a disserta￾tion or a masters thesis in that topic. The author therefore will present the following

piece of advice: Read as many papers as possible.

Be sure to include some that are old, as old papers often have excellent ideas.

Some of these are not electronically available. Reading a very long paper, in detail,

verifying all the small steps with your pencil, is slow but important. There may be

some papers which you cannot give this magnitude of time to. If so, it is better to

read the first 4 pages of 10 papers than to only read the abstracts of 20 or 30.

With hope for the future,

Gregory V. Bard,

Visiting Assistant Professor,

Department of Mathematics,

Fordham University,

Bronx, New York, USA.

May 4th, 2009

Preface

Dedication

With pleasure, I dedicate this dissertation to my family. To my father, who taught

me much in mathematics, most especially calculus, years earlier than I would have

been permitted to see it. And to my mother and brother, who have encouraged me

in every endeavor.

ix

Acknowledgements

I am deeply indebted to my advisor, Professor Lawrence C. Washington, who has

read and re-read many versions of this document, and almost every research paper

I have written to date, provided me with countless hours of his time, and given me

sound advice, on matters technical, professional and personal. He has had many

students, and all I have spoken to are in agreement that he is a phenomenal advisor,

and it is humbling to know that we can never possibly equal him. He is that rare type

of scholar, who is both outstanding in teaching and in research.

I have been very fortunate to work with Dr. Nicolas T. Courtois, currently Senior

Lecturer at the University College of London. It suffices to say that the field of alge￾braic cryptanalysis has been revolutionized by his work. He permitted me to study

with him for four months in Paris, and later even to stay at his home in England,

after his move there. Much of my work is joint work with him, including everything

I have done with Keeloq and ElimLin, as well as my first paper on SAT-solvers. He

has always given very freely of his ideas.

The SAGE community has been a true inspiration for me. The fact that so many

highly-talented volunteers surrender so much of their free time to work unpaid on

a non-for-profit project is heart warming. Knowing that my work is part of SAGE

makes me know that my effort was not wasted. This is primarily due to William

Stein, who created SAGE and guides the project. Furthermore, he has given me

access to certain high-performance computing systems, without which my research

would have been essentially impossible. I publicly thank him in particular, and all

SAGE volunteers in general.

I would like to particularly thank Michael Abshoff (University of Washington,

Seattle) for help with SAGE, and forgiving two unfortunate computational episodes;

William Adams (University of Maryland at College Park, Ret.) for introducing me

to Grobner Bases, and for an excellent class in abstract algebra; Martin Albrecht ¨

(Royal Holloway College, University of London) for endless support in SAGE as

well as finite field linear algebra; Bill Arbaugh (University of Maryland at Col￾lege Park) for an excellent computer security class; Kostas Arkoudas (Rensselaer

Polytechnic Institute) for suggesting I consider SAT-solvers; Shaun Ault (Fordham

University) for helping me with analytic combinatorics; Joe Barth (now US Census

xi

xii

Bureau) for help in graduate school, especially with the Algebra Qualifier; Lynn

Batten (Deakin University, Australia) for challenging me to prove Theorem 74 on

Page 196 during a coffee break on July 10, 2007, at the conference Fq

8 , in Mel￾bourne; Paul Bello (now Department of Defense) for inspiration, good conversations

and career advice; Daniel Bernstein (Univerisity of Illinois at Chicago) for profuse

and frequent technical as well as career advice, and numerous useful ideas; Mark

Binfield (now Booz-Allen Hamilton) for many long conversations about math and

economics; Michael Black (American University) for help with distributed systems,

BOINC, SAT-solvers, and teaching advice; Melkana Brakalova (Fordham Univer￾sity) for teaching advice; Selmar Bringsjord (Rensselaer Polytechnic Institute) for

teaching two classes in logic, that would turn out to be the foundation of my en￾tire outlook on research and on life; Armand Brumer (Fordham University, Ret.)

for technical advice, encouragement, and for reminding me how important com￾puter algebra can be to working pure mathematicians; Ed Casimiro (University of

Pheonix) for help with Chapter 6; Carlos Cid (Royal Holloway College, University

of London) for career advice, and his excellent book on the AES which inspired

this text; Abram Claycomb (now United States Air Force) for much help at RPI and

later encouragement as well; Blandine Debraize (Gemalto) for her work in break￾ing SNOW with SAT-solvers; Theodore Faticoni (Fordham University) for helping

me decide to publish this book in the first place; William Randolph Franklin (Rens￾selaer Polytechnic Institute) for being my undergraduate advisor and supervising

my first cryptographic research project—on passwords; William Gasarch (Univer￾sity of Maryland at College Park) for algorithms advice and background on Gray

Codes; Theresa Girardi (Fordham University) for much proofreading and guidance

in number theory as well as teaching; Alex Golec (Fordham University) for help

with programming and compilers; Janusz Golec (Fordham University) for technical

advice relating to probability, and guidance in teaching; Virgil D. Gligor (Univer￾sity of Maryland at College Park) for encouraging my switch from engineering to

mathematics; Michael Gray (American University) for hiring me, and guidance in

matters of teaching; Carmi Gressel (Fortress) for introducing me to the world of

patents, and ZK-Crypt; William Hart (University of Warwick) for help with lin￾ear algebra and advice related to publishing papers; Michael Headley (American

University) for proofreading; Tanja Lange (Technische Universiteit Eindhoven) for

practical and professional advice; Bill and Maryam Hastings (Fordham University)

for career advice and encouragement; Sebastiaan Indesteege (Katholieke Univer￾siteit Leuven in Belgium) for comments on Keeloq; Peter Jeavons (St Anne’s Col￾lege, Oxford University) for help with SAT problems and polynomials; Chris Jef￾ferson (Oxford University Computing Laboratory) for much help with SAT-solvers;

Antoine Joux (Universite de Versailles) for help with Gray Codes and Butterfly ´

Transposes; W. David Joyner (United States Naval Academy) for help with SAGE

and career advice; Haig Kafafian† for introducing me to cryptography and to ma￾trices; Igor Khalatian (now LiveLOOK, Inc.) for teaching me how to program in

C, so many years ago; Jon Katz (University of Maryland at College Park) for two

excellent cryptography classes, and guidance in my first cryptographic paper; Kyle

Kloster (Fordham University) for proofreading and help with the quadratic sieve;

Acknowledgements

xiii

Susan Lagerstrom-Fife (Springer-Verlag) for patience and guidance in the last stages

of the development of this manuscript; Godfrey H. L. Le May (Worcester College,

Oxford University, Ret.) for encouragement; David Levermore (University of Mary￾land at College Park) for career guidance, linear algebra advice, and for admitting

me to the PhD program in the first place; Michael Levin (American University)

for proofreading and help with Darwinian Gradient Descent; Robert Lewis (Ford￾ham University) for guidance in matters ranging from resultants to teaching, from

the role of polynomial systems in chemistry to the role of the college instructor in

setting standards; Robert Miller (University of Washington, Seattle) for help with

graph theory and linear algebra; Ilya Mironov (Microsoft Research) for discussions

about SAT-solvers; Leonard Nissim (Fordham University) for advice in teaching

abstract algebra, and on the job hunt; Andrew Novocin (University of Montpel￾lier) for many interesting discussions; Brennan O’Donnell (Fordham University)

for vital funding; Sean O’Neil (The VEST Corporation) for help with generating

algebraic normal forms, and advice on other topics; Jacques Patarin (Universite de ´

Versailles) for encouragement in my studies of both SAT-solvers and the French

language; Kenneth Patterson (Royal Holloway College, University of London) for

career advice and whose questions at the 2008 Workshop on Mathematical Cryp￾tography in Santander, Spain, that encouraged me to rigorously describe the attack

in Section 4.6 on Page 49; Clement Pernet (Universit ´ e Joseph Fourier, Grenoble) ´

for much useful advice on linear algebra over finite fields, and thinking up the pro￾nunciation “Mary” for M4RI, a mercy to all francophones who will ever mention

the library; Carl Pomerance (now Dartmouth University) for encouragement and

help with sparse linear algebra; Cris Poor (Fordham University) for many conversa￾tions related to NP-Completeness and to teaching; Bill Singer (Fordham University)

for advice in matters ranging from teaching to negotiation of the book publishing

contract; Simon Schur (now University of Toronto) for letting me use his office;

Richard Schwartz (now Brown University) for teaching me abstract algebra, way

back when; Yana Shabaev (American University) for tender advice; Harold Snider

(National Federation of the Blind, Ret.) for much encouragement, especially re￾lated to Oxford; Mate Soos (INRIA Rhone-Alpes) for information about MINISAT

internals, and for proofreading Chapter 14; Albert Studdard (University of North

Carolina at Pembroke, Ret.) for career advice, and guidance in matters of teaching;

Buck Surdu (US Army) for many interesting conversations; Mark Tilmes (Univer￾sity of Maryland at College Park) for assistance, enthusiasm for parallel comput￾ing, and forgiving an unfortunate computational episode; Steven Tretter (University

of Maryland at College Park) for introducing me to finite fields and their applica￾tions; Mak Trifkovic (now University of Victoria) for teaching and career advice;

Seena Vali (Fordham University) for proofreading and help with sparse matrices;

Christopher Wolf (now University of Bochum) for much advice; Kris Wolff (Ford￾ham University) for help in writing grants; Koon Ho “Kenneth” Wong (University

of Queensland Univeristy of Technology) for help with graph theory and partition￾ing polynomial systems; Angela Wu (American University) for guidance in matters

of teaching; and Patrick Studdard, for everything.

Acknowledgements

xiv

The National Security Agency was my first full-time permanent job and I remain

very grateful to them not only for the opportunity to serve my country but also for

the training and exposure to new ideas that I had there. It was a happy four years for

me, and I particularly fondly remember the awe-inspiring dedication its employees

had for pushing ahead with agency’s mission, even before September 11, 2001. It

is a true “puzzle palace” where math nerds can congregate with their own kind and

work on deep problems. Both tradition and law forbid me from naming specific

individuals who have helped me or guided me, but there were several.

Several texts by Steven D. Krantz were consulted during this project. Princi￾pally they are A Primer on Mathematical Writing [150], Mathematical Publishing:

A Guidebook [153], but also A Mathematician’s Survival Guide [152]. Without his

guidance my writing would be even worse than the reader is about to discover it to

be. I strongly suggest any graduate student or recent PhD read those books, and also

How to Teach Mathematics [151]. Note, the vast majority of the contents of these

books apply well to Computer Science as well.

Several governmental agencies have contributed financial to my eduction or to

my research. They are the National Science Foundation (Division of Mathematical

Sciences2

), the United States Navy (Naval Sea Systems Command), the National

Security Agency, and ECRYPT, the European Union’s Cryptographic research or￾ganization. They have my unending gratitude. I am also happy to thank Fordham

University for two faculty research grants and an interdisciplinary seminar grant.

2 The SAGE grants DMS-0555776 and DMS-0821725, and the University of Maryland at College

Park VIGRE grant.

Acknowledgements

xv

If you Find Any Errors. . .

Wherfore I trust thei that be learned, and happen to reade this worke, wil beare the moare

with me, if thei finde any thyng, that thei doe mislike: Wherein if thei will use this curtesie,

either by writynge to admonishe me thereof, either theim selfes to sette forthe a moare

perfecter woorke, I will thynke them praise worthie.

Robert Recorde, 1557, quoted from [121, last page]. See also Appendix E on

Page 337.

Acknowledgements

Contents

List of Tables

List of Figures

List of Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

List of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxxi i i

1 Introduction: How to Use this Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

Part I Cryptanalysis

2 The Block Cipher Keeloq and Algebraic Attacks. . . . . . . . . . . . . . . . . . . 9

2.1 What is Algebraic Cryptanalysis? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.1.1 The CSP Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2 The Keeloq Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.3 Modeling the Non-linear Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.3.1 I/O Relations and the NLF . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.4 Describing the Shift-Registers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.4.1 Disposing of the Secret Key Shift-Register . . . . . . . . . . . . . . . 13

2.4.2 Disposing of the Plaintext Shift-Register . . . . . . . . . . . . . . . . . 13

2.5 The Polynomial System of Equations . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.6 Variable and Equation Count . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.7 Dropping the Degree to Quadratic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.8 Fixing or Guessing Bits in Advance . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.9 The Failure of a Frontal Assault . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3 The Fixed-Point Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.1.1 Notational Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.1.2 The Two-Function Representation . . . . . . . . . . . . . . . . . . . . . . 17

3.1.3 Acquiring an f

(8)

k

-oracle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

xvii

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxvii

xxix

xxxi

xviii Contents

3.2 The Consequences of Fixed Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.3 How to Find Fixed Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.4 How far must we search? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.4.1 With Analytic Combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.4.2 Without Analytic Combinatorics . . . . . . . . . . . . . . . . . . . . . . . 23

3.5 Comparison to Brute Force . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.7 Other Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.7.1 A Note about Keeloq’s Utilization . . . . . . . . . . . . . . . . . . . . . . 25

3.7.2 RPA vs KPA vs CPA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.8 Wagner’s Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.8.1 Later Work on Keeloq . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4 Iterated Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.1 Applications to Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.2.1 Combinatorial Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.2.2 Ordinary and Exponential Generating Functions . . . . . . . . . . 30

4.2.3 Operations on OGFs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.2.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.2.5 Operations on EGFs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4.2.6 Notation and Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.3 Strong and Weak Cycle Structure Theorems . . . . . . . . . . . . . . . . . . . . 40

4.3.1 Expected Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.4 Corollaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.4.1 On Cycles in Iterated Permutations . . . . . . . . . . . . . . . . . . . . . 45

4.4.2 Limited Cycle Counts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.4.3 Monomial Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.5 Of Pure Mathematical Interest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.5.1 The Sigma Divisor Function . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.5.2 The Zeta Function and Apery’s Constant. . . . . . . . . . . . . . . . . 48 ´

4.5.3 Greatest Common Divisors and Cycle Length . . . . . . . . . . . . 49

4.6 Highly Iterated Ciphers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4.6.1 Distinguishing Iterated Ciphers . . . . . . . . . . . . . . . . . . . . . . . . 50

4.6.2 A Key Recovery Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5 Stream Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5.1 The Stream Ciphers Bivium and Trivium . . . . . . . . . . . . . . . . . . . . . . . 55

5.1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5.1.2 Bivium as Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

5.1.3 An Excellent Trick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

5.1.4 Bivium-A. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

5.1.5 A Notational Issue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

5.1.6 For Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

5.2 The Stream Cipher QUAD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

Contents xix

5.2.1 How QUAD Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

5.2.2 Proof of Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

5.2.3 The Yang-Chen-Bernstein-Chen Attack against QUAD . . . . 72

5.2.4 Extending to GF(16) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

5.2.5 For Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

5.3 Conclusions for QUAD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

Part II Linear Systems Mod 2

6 Some Basic Facts about Linear Algebra over GF(2) . . . . . . . . . . . . . . . . 81

6.1 Sources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

6.2 Boolean Matrices vs GF(2) Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 81

6.2.1 Implementing with the Integers . . . . . . . . . . . . . . . . . . . . . . . . 82

6.3 Why is GF(2) Different? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

6.3.1 There are Self-Orthogonal Vectors . . . . . . . . . . . . . . . . . . . . . . 82

6.3.2 Something that Fails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

6.3.3 The Probability a Random Square Matrix Singular or

Invertible . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

6.4 Null Space from the RREF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

6.5 The Number of Solutions to a Linear System . . . . . . . . . . . . . . . . . . . 86

7 The Complexity of GF(2)-Matrix Operations. . . . . . . . . . . . . . . . . . . . . . 89

7.1 The Cost Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

7.1.1 A Word on Architecture and Cross-Over . . . . . . . . . . . . . . . . . 90

7.1.2 Is the Model Trivial? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

7.1.3 Counting Field Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

7.1.4 Success and Failure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

7.2 Notational Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

7.3 To Invert or to Solve? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

7.4 Data Structure Choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

7.4.1 Dense Form: An Array with Swaps . . . . . . . . . . . . . . . . . . . . . 94

7.4.2 Permutation Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

7.5 Analysis of Classical Techniques with our Model . . . . . . . . . . . . . . . . 96

7.5.1 Na¨ıve Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

7.5.2 Matrix Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

7.5.3 Dense Gaussian Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

7.5.4 Back-Solving a Triangulated Linear System . . . . . . . . . . . . . . 98

7.6 Strassen’s Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

7.6.1 Strassen’s Algorithm for Matrix Multiplication . . . . . . . . . . . 100

7.6.2 Misunderstanding Strassen’s Matrix Inversion Formula . . . . 101

7.7 The Unsuitability of Strassen’s Algorithm for Inversion . . . . . . . . . . . 101

7.7.1 Strassen’s Approach to Matrix Inversion . . . . . . . . . . . . . . . . . 102

7.7.2 Bunch and Hopcroft’s Solution . . . . . . . . . . . . . . . . . . . . . . . . . 103

7.7.3 Ibara, Moran, and Hui’s Solution . . . . . . . . . . . . . . . . . . . . . . . 103