Swenson - Modern Cryptanalysis

Contents

Modern Cryptanalysis: Techniques for Advanced Code Breaking

Published by

Wiley Publishing, Inc.

10475 Crosspoint Boulevard

Indianapolis, IN 46256

Copyright 2008 by Christopher Swenson

Published by Wiley Publishing, Inc., Indianapolis, Indiana

Published simultaneously in Canada

ISBN: 978-0-470-13593-8

Manufactured in the United States of America

10 9 8 7 6 5 4 3 2 1

No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 646-8600. Requests to the Publisher for permission should be addressed to the Legal Department, Wiley Publishing, Inc., 10475 Crosspoint Blvd., Indianapolis, IN 46256, (317) 572-3447, fax (317) 572-4355, or online at http://www.wiley.com/go/permissions .

Limit of Liability/Disclaimer of Warranty: The publisher and the author make no representations or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including without limitation warranties of fitness for a particular purpose. No warranty may be created or extended by sales or promotional materials. The advice and strategies contained herein may not be suitable for every situation. This work is sold with the understanding that the publisher is not engaged in rendering legal, accounting, or other professional services. If professional assistance is required, the services of a competent professional person should be sought. Neither the publisher nor the author shall be liable for damages arising herefrom. The fact that an organization or Website is referred to in this work as a citation and/or a potential source of further information does not mean that the author or the publisher endorses the information the organization or Website may provide or recommendations it may make. Further, readers should be aware that Internet Websites listed in this work may have changed or disappeared between when this work was written and when it is read.

For general information on our other products and services or to obtain technical support, please contact our Customer Care Department within the U.S. at (800) 762-2974, outside the U.S. at (317) 572-3993 or fax (317) 572-4002.

Library of Congress Cataloging-in-Publication Data is available from the publisher.

Trademarks: Wiley, the Wiley logo, and are related trade dress are trademarks or registered trademarks of John Wiley & Sons, Inc. and/or its affiliates in the United States and other countries, and may not be used without written permission. All other trademarks are the property of their respective owners. Wiley Publishing, Inc., is not associated with any product or vendor mentioned in this book.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books.

The views and opinions expressed in this book do not reflect those of the United States Department of Defense.

To Sra

About the Author

Christopher Swenson ( www.caswenson.com ) is currently completing his PhD in computer science at The University of Tulsa, where he has assisted with and taught courses in security, telecommunications, and cryptanalysis. He is an active researcher and has published many papers in the security field. He was the recipient of a scholarship in the Information Assurance Scholarship Program, also known as the Department of Defense Cyber Corps program.

Credits

Executive Editor

Carol Long

Development Editor

John Sleeva

Production Editor

Debra Banninger

Copy Editor

Cate Caffrey

Editorial Manager

Mary Beth Wakefield

Production Manager

Tim Tate

Vice President and Executive Group Publisher

Richard Swadley

Vice President and Executive Publisher

Joseph B. Wikert

Project Coordinator, Cover

Lynsey Stanford

Proofreader

Nancy Carrasco

Indexer

Melanie Belkin

Cover Image

Yamada Taro/Digital Vision/Getty Images

Acknowledgments

I thank the many people who helped me shape this book. First and foremost, I thank my fiance, Thursday Bram, for her support throughout the writing of this book. I thank Sujeet Shenoi and The University of Tulsa for providing me with the venue to teach the original class (as well as all of the students in that original class). I thank John Hale, Gavin Manes, and Mauricio Papa for being great mentors over the years. And of course, I thank my mother, Glenda, and my father, Roger, as well as my sisters, Rikki and Jessi, and my step-father, Richard, for all of their continued support throughout the years.

I could not have written the book without Carol Long and John Sleevas support at Wiley. Also, a great many thanks to Donald Knuth, Leslie Lamport, John D. Hobby, and the hundreds of other individuals who have given their support in TeX, LaTeX, MetaPost, and related typesetting projects.

Introduction

This book, like many things, was developed in response to a problem: There is no text that explains modern advancements in the field of cryptanalysis. The field of cryptanalysis has developed significantly in the last several hundred years, and for the most part, cryptanalysis has been well-studied and documented throughout this time.

However, when we move into the 20th century, the documentation of cryptanalysis has come to a near standstill. Almost every book published on the topic of cryptanalysis is stuck nearly 100 years in the past, idling around the area of breaking some of the simplest ciphers, by todays standards.

The field itself has not stopped developing. On the contrary, it has been moving incredibly rapidly, especially in the past 30 years, with the rise of ever more powerful computers. While all of this research into cryptanalysis has been documented and presented at various conferences throughout the world, nobody had bothered to create a simple resource with which to learn cryptanalysis from scratch. Bruce Schneier [5] stated that such a resource would not be worthwhile, because the field changes so much, and he has a point. But, the current roads on which cryptanalysis travels are built on the same foundations, and the amount of background material needed to understand current research or participate is becoming very large and complicated. Furthermore, the important papers are written by many different individuals with many diverse goals and audiences, which can make the papers difficult to understand.

I must reiterate what Schneier says [5], though: There is only one way to become a good cryptanalyst to practice breaking codes. However, it is my hope that this book will be a good outline of many important topics to a new or veteran cryptanalyst.

While teaching at The University of Tulsa, I had many students express their interest in learning cryptanalysis, knowing that I enjoyed the field. As I began to prepare to teach a class, I discovered that there was definitely no textbook for what I wanted to teach, although I did prepare the students mathematically using the material in Reference [7].