Public Key Cryptography E-Book

Lynn Margaret Batten

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Serie: IEEE Press Series on Information and Communication Networks Security
• Sprache: Englisch

Seitenzahl: 432

Veröffentlichungsjahr: 2013

Beschreibung

Complete coverage of the current major public key cryptosystems their underlying mathematics and the most common techniques used in attacking them Public Key Cryptography: Applications and Attacks introduces and explains the fundamentals of public key cryptography and explores its application in all major public key cryptosystems in current use, including ElGamal, RSA, Elliptic Curve, and digital signature schemes. It provides the underlying mathematics needed to build and study these schemes as needed, and examines attacks on said schemes via the mathematical problems on which they are based – such as the discrete logarithm problem and the difficulty of factoring integers.

The book contains approximately ten examples with detailed solutions, while each chapter includes forty to fifty problems with full solutions for odd-numbered problems provided in the Appendix. Public Key Cryptography:

• Explains fundamentals of public key cryptography

• Offers numerous examples and exercises

• Provides excellent study tools for those preparing to take the Certified Information Systems Security Professional (CISSP) exam

• Provides solutions to the end-of-chapter problems

Public Key Cryptography provides a solid background for anyone who is employed by or seeking employment with a government organization, cloud service provider, or any large enterprise that uses public key systems to secure data.

Leseprobe

Contents

Cover

Title Page

Series Page

Copyright

Dedication

Preface

Acknowledgments

List of Figures

Chapter 1: Introduction

1.1 The Meaning of the Word Cryptography

1.2 Symmetric Key Cryptography

1.3 Public Key (Asymmetric) Cryptography

1.4 Key Establishment

1.5 Cryptography—More than Just Hiding Secrets

1.6 Standards

1.7 Attacks

Chapter 2: Congruence Equations

2.1 Congruence Arithmetic

2.2 The Euclidean Algorithm—Finding Inverses

2.3 Discrete Logarithms and Diffie–Hellman Key Exchange

2.4 Attacking the Discrete Logarithm

Chapter 3: The ElGamal Scheme

3.1 Primitive Roots

3.2 The ElGamal Scheme

3.3 Security of the ElGamal Scheme

Chapter 4: The RSA Scheme

4.1 Euler's Theorem

4.2 The RSA Algorithm

4.3 RSA Security

4.4 Implementing RSA

Chapter 5: Elliptic Curve Cryptography

5.1 Elliptic Curves and Elliptic Curve Groups

5.2 Elliptic Curve Cryptography

5.3 The Elliptic Curve Factoring Scheme

Chapter 6: Digital Signatures

6.1 Hash Functions

6.2 Digital Signature Schemes

6.3 Attacks on Digital Signatures

Chapter 7: Primality Testing

7.1 Fermat's Approach and Wilson's Theorem

7.2 The Miller–Selfridge–Rabin Primality Test

7.3 True Primality Tests

7.4 Mersenne Primes and the Lucas–Lehmer Test

7.5 Primes is in P

Chapter 8: Factoring Methods

8.1 Fermat Again

8.2 The Quadratic Sieve

8.3 Pollard's p − 1 and Rho Methods

8.4 Continued Fractions and Factoring

Appendix: Solutions to Problems

Notation

Bibliography

Index

Books in the IEEE Press Series on: Information and Communication Networks Security

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, [phone], fax [phone], 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, [phone], fax [phone], 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 [phone], outside the United States at [phone] or fax [phone].

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'2–dc23

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 40–50 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: [email protected].

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

1.1 The M-209 encryption machine sold by Hagelin

1.2 Transmitting encrypted data over an insecure channel

1.3 Alice signs a message for Bob

2.1 A sequence cycle

4.1 The RSA challenge

5.1 An elliptic curve with real coefficients

5.2 Adding two distinct points

5.3 Adding a point to its negative

5.4 Doubling the point P

5.5 Doubling a point with tangent infinity

5.6 The graph of a finite elliptic curve

6.1 Cipher-block-chaining of an iterative hash function

6.2 The SHA-1 operations

6.3 The MD5 operations

6.4 Atul sends data to Antonio

6.5 Feena sends a document to Miriam

6.6 HashCalc

8.1 Factoring n

2

Congruence Equations

In this chapter, we introduce three areas of mathematics needed for the development of the theory and implementation of the public key cryptographic systems discussed in this book. Mathematical systems of most use in developing cryptographic algorithms are finite systems, as computers are by nature finite. Thus, we deal with finite or discrete number systems. The three topics we cover are first congruence arithmetic, second the Euclidean algorithm, and finally, the dual concepts of exponential and logarithmic equations in the discrete setting of congruence arithmetics.

Congruence arithmetic is essentially arithmetic in discrete number systems. The standard arithmetic operations of addition, subtraction, multiplication, and division are needed. The first three of these are easy enough to define, but division is a little more complex, and not always available! The Euclidean Algorithm, presented in Section 2.2, is a very efficient method of enabling division in discrete systems. Perhaps surprisingly, this algorithm will be useful in every chapter of the book.