Lynn Margaret Batten - Public key cryptography: applications and attacks

IEEE Press

445 Hoes Lane

Piscataway, NJ 08854

IEEE Press Editorial Board 2012

John B. Anderson, Editor in Chief

Kenneth Moore, Director of IEEE Book and Information Services (BIS)

Technical Reviewer

Lejla Batina, Radboud University Nijmegen, The Netherlands

Copyright 2013 by The Institute of Electrical and Electronics Engineers, Inc.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey.

Published simultaneously in Canada.

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 Section 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, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 750-4470, or on the web at www.copyright.com . Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permission .

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

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

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com .

Library of Congress Cataloging-in-Publication Data:

Batten, Lynn Margaret.

Public key cryptography: applications and attacks / Lynn Margaret Batten.

p. cm.

Includes bibliographical references and index.

ISBN 978-1-118-31712-9 (cloth)

1. Public key cryptography. 2. Cryptography-Mathematics. I. Title.

TK5102.94.B38 2012

005.8'2dc23

2012025411

For Glenn

In the margin of his copy of Arithmetica, Pierre de Fermat had jotted the words I have a truly marvelous demonstration of this proposition which this margin is too narrow to contain ... And all of a sudden she understood. The answer was disarmingly simple.

(From The Girl Who Played with Fire by Stieg Larsson. Translated into English from the Swedish by Reg Keeland. Maclehose Press, Quercus, London, 2009, p. 536)

Preface

There are now many texts available giving an overview of both public key and symmetric key cryptography. The focus of this text is only the former. The objective is to give a complete description of the current major public key cryptosystems, the underlying mathematics, and the most common techniques used in attacking them.

It is assumed throughout that the reader has access to an algebraic software system such as Maple [65] or a sophisticated calculator supporting computation of large numbers and moduli. The reason for this is to emphasize the fact that, while the mathematical schemes are well designed, they supply no security unless they are implemented on sufficiently large values; thus, it is important to examine the complexity of the computations for small numbers as opposed to large ones. In each section of this book, we have provided computer-assisted examples.

The first chapters of this book cover the theory of public key systems in current use, including ElGamal, RSA, Elliptic Curve, and digital signature schemes. The underlying mathematics needed to build and study these schemes is provided as needed through the book. The latter half of the book examines attacks on these schemes via mathematical problems on which they are based fundamentally, the discrete logarithm problem and the difficulty of factoring integers.

The book is suitable for one or two semester courses for students with some discrete mathematics background including a knowledge of algorithms, computational complexity, and binary arithmetic. It is aimed at students studying cryptography in the context of information technology security and is designed to cover thoroughly the public key cryptography material needed for the writing of the CISSP exam [57]. It is equally aimed at mathematics students in the context of applications of groups and fields. Each chapter contains 4050 problems and full solutions for the odd-numbered questions are provided in the appendix. To obtain the full solutions manual please send an email to: .

Lynn Margaret Batten

Acknowledgments

I would like to thank Judy Chow for her considerable effort and skill in producing a LaTeX, version of this document. Bernard Colbert read and commented on several drafts, Martin Schulz assisted with Maple while Lei Pan produced elliptic curve graphics; I thank all of these people. In addition, I wish to thank Wiley representative Mary Hatcher and anonymous referees for their support and suggested improvements of the original manuscript.

List of Figures

The M-209 encryption machine sold by Hagelin

Transmitting encrypted data over an insecure channel

Alice signs a message for Bob

A sequence cycle

The RSA challenge

An elliptic curve with real coefficients

Adding two distinct points

Adding a point to its negative

Doubling the point P

Doubling a point with tangent infinity

The graph of a finite elliptic curve

Cipher-block-chaining of an iterative hash function

The SHA-1 operations

The MD5 operations

Atul sends data to Antonio

Feena sends a document to Miriam

HashCalc

Factoring n

Introduction

This book is designed for use as a university text for year three, four, or honors level students. It is intended as a first approach to public key cryptographyno background in cryptography is needed. However, a basic understanding of discrete mathematics and algorithms and of the concept of computational complexity is assumed.

The major public key systems are presented in detail, both from the point of view of their design and their levels of security. Since all are based on a computationally difficult mathematical problem, the mathematics needed to construct and to analyze them is developed as needed along the way.

Each concept presented in the book comes with examples and problems, some of which can be done with limited computational capacity (a calculator for example) and some of which need major computational resources such as a mathematics-based software package or some independently written algorithms. Mathematica, Matlab, Magma [64], and Maple [65] are examples of packaged software that can be used easily to perform the necessary computations. For those who prefer open source software, see [28] where Sage is used for algorithms and examples. The book can be used without additional software resources by avoiding those problems which require them.