`
`
`
`BRUCE SCHNEIER
`
`Page 1 0f 7
`
`PNC-JP MORGAN EXHIBIT 1014
`
`Page 1 of 7
`
`PNC-JP MORGAN EXHIBIT 1014
`
`

`

`Associate Publisher: Katherine Schowalter
`Editor: Paul Farrell
`Managing Editor: Beth Austin
`Editorial Production & Design: Editorial Services of New England. Inc.
`This publication is designed to provide accurate and authoritative information in regard to the subject
`matter covered. It is sold with the understanding that the publisher is not engaged in rendering
`professional services. If legal, accounting, medical. psychological, or any other expert assistance is
`required. the services of a competent professional person should be sought. ADAPTED FROM A
`DECLARATIONS OF PRINCIPLES OF AJOINT COMMITTEE OF THE AMERICAN BAR
`ASSOCIATION AND PUBLISHERS.
`In no event will the publisher or author be liable for any consequential, incidental, or indircct
`damages {including damages for loss of business profits, business interruption, loss of business
`information, and the like) arising from the use or inability to use the protocols and algorithms in this
`book, even if the publisher or author has been advised of the possibility of such damages.
`Some of the protocols and algorithms in this book are protected by patents and copyrights. It is the
`responsibility of the reader to obtain all necessary patent and copyright licenses before implementing
`in software any protocol or algorithm in this book. This book does not contain an exhaustive list of
`all applicable patents and copyrights.
`Some of the protocols and algorithms in this book are regulated under the United States Department
`of State International Traffic in Arms Regulations. It is the responsibility of the reader to obtain all
`necessary export licenses before implementing in software for export any protocol or algorithm in
`this book.
`
`This text is printed on acid—free paper.
`Trademarks
`Designations used by companies to distinguish their products are often claimed as trademarks. In all
`instances where John Wiley 8:. Sons. Inc. is aware of a claim, the product names appear in initial
`capital or all capital letters. Readers, however. should contact the appropriate companies for more
`complete information regarding trademarks and registration.
`Copyright © 1994 John Wiley & Sons, Inc.
`All rights reserved. Published simultaneously in Canada.
`Reproduction or translation of any part of this work beyond that permitted by Section 10? or 108 of
`the 19% United States Copyright Act without the permission of the copyright owner is unlawful.
`Requests for permission or further information should be addressed to the Permissions Department.
`John Wiley 8: Sons. Inc.
`
`Library of Congress Cataloging-in-Publication Data
`Schneier, Bruce
`Applied cryptography : protocols. algorithms. and source code in C
`I Bruce Schneier.
`p. cm.
`Includes bibliographical references and index.
`ISBN 0471597564 (paper)
`1. Computer security. 2. Telecommunicationfisecurity measures. 3. Cryptography. 4. Title
`QA76.9.A25835 1993
`005.8’2—udc20
`93-2139
`C]?
`
`Printed in the United States of America
`10 9 8 7r' 6 5 4
`
`Page 2 of 7
`
`.E
`
`
`
`Page 2 of 7
`
`

`

`12.4
`
`RSA
`
`Page 3 of 7
`
`prudent to trust them.
`
`Patents
`
`The original MerkIe—Hellnian algorithm is patented in the United States [428] and
`worldwide (see Table 12.1). PKP licenses the patent, along with other public-key
`cryptography patents. Anyone interested in obtaining a license should contact:
`
`Robert B. Fougner
`Director of Licensing
`Public Key Partners
`130 B Kifer Court
`
`Sunnyvale, CA 94086
`Tel: (408) 735—6779
`
`The US. patent will expire on August 19, 1997.
`
`TABLE 12.|
`
`Foreign Merkle—Hellman Knapsack Patents
`
`COUNTRY
`NUMBER
`DATE
`
`Belgium
`871039
`5 Apr 1979
`Netherlands
`7810063
`10 Apr 1979
`Great Britain
`2006580
`2 May 1979
`Germany
`2843583
`10 May 1979
`Sweden
`7810478
`14 May 1979
`France
`2405532
`8 Jun 1979
`Germany
`2843583
`3 Jun 1982
`Germany
`2857905
`15 Jul 1982
`Canada
`1128159
`20 Jul 1982
`Great Britain
`2006580
`18 Aug 1982
`Switzerland
`63416114
`14 Jan 1983
`Italy
`1099780
`28 Sep 1985
`
`
`Soon after Merkle’s knapsack algorithm came the first full-fledged public—key
`algorithm, one that works for encryption as well as for digital signatures. Of all
`the public-key algorithms proposed over the years,
`it
`is by far the easiest to
`understand and implement. {Martin Gardnerpublishcd an early description ofth
`algorithm in his “Mathematical Games” column in Scientific American [365].) 11
`
`Page 3 of 7
`
`

`

`282.
`
`Public—Key A1gorithmg
`
`is also the most popular. Named after the three inventors, Ron Rivest, Adi Shamir,
`and Leonard Adleman, who first introduced the algorithm in l978 [?49,?50], it
`has since withstood years of extensive cryptanalysis. Although the cryptanalysig
`neither proved nor disproved RSA’s security, it does suggest a confidence level in
`the theoretical underpinnings of the algorithm.
`RSA gets its security from the difficulty of factoring large numbers. The public
`and private keys are functions of a pair of large (100 to 200 digits or even larger)
`prime numbers. Recovering the piaintext from one of the keys and the ciphcrtex:
`is conjectured to be equivalent to factoring the product of the two primes.
`To generate the two keys, choose two large prime numbers, p and (1. Compute
`the product:
`
`a=qu
`
`Then randomly choose the encryption key, 3, such that e and (p——l) X ((3—1) are
`relatively prime. Finally, use Euclid‘s algorithm to compute the decryption key, d,
`such that
`
`e x a: 1 (mod (p—1)X(q—l))
`
`In other words,
`
`a = e“ (mod (p—l) x (qr—1))
`
`Note that d and rt are also relatively prime. The numbers 8 and n are the public
`key; the uumberd is the private key. The two primes, p and q, are no longer needed.
`They should be discarded, but never revealed.
`To encrypt a message in, first divide it into numerical blocks such that each
`block has a unique representation modulo :1 (with binary data, choose the largest
`power of 2 less than in). That is, if both p and q are IUD-digit primes, then a wili
`have just under 200 digits, and each message block, mi. should be just under 200
`digits long. The encrypted message, (3, will be made up of similarly sized message
`blocks, of, of about the same length. The encryption formula is simply:
`
`c,- = mfg (mod rt)
`
`To decrypt a message, take each encrypted block c; and compute:
`a
`m; = c,- (mod n)
`
`Since:
`
`Cid : (mierl = mied z miMIJ‘I)(q—l)+ 1 2 m; X mikQJ-qu—l) : N1,- X 1 = mia
`all mod n
`
`the formula recovers the message. This is summarized in Table 12.2.
`
`Page 4 of 7
`
`Page 4 of 7
`
`

`

`i 2.4
`
`RSA
`
`TABLE I2.2
`
`283
`
`RSA Encryption
`
`PUBLIC KEY:
`
`rt product of two primes, p and q (p and q must remain secret)
`e
`relatively prime to (32—1) x (q—I)
`PRIVATE KEY:
`
`d e“ (mod (p—l) x (9—1))
`ENCRYPTING:
`
`c = m“ (mod n)
`DECRYP’I‘ING:
`
`m = ed (mod n)
`
`
`The message could just as easily have been encrypted with d and decrypted with
`e; the choice is arbitrary. I am not including the number theory that proves why
`this works; most current texts on cryptography cover the theory in detail.
`A short example will probably go a long way to making this clearer. If p = 47
`and q = 71, then
`
`it = p X q z 3337
`
`The encryption key .9 must have no factors in common with:
`
`(p—1)><(q—1): 46 x 70 = 3220
`
`Choose e (at random) to be 79. In that case:
`
`a = 79" (mod 3220) = 1019
`
`This number was calculated using the extended Euclidean algorithm (see Section 9.3).
`Publish e and a, and keep 0' secret. Discard p and q.
`To encrypt the message
`
`m = 6882326879666683
`
`first break it into small blocks. Three-digit blocks work nicely in this case. The
`message will be encrypted in six blocks, 92,-, in which:
`
`m1 = 688
`
`m2 : 232
`
`M3 = 687
`
`111,; = 966
`
`m5 = 668
`
`m6 = 3
`
`Page 5 of 7
`
`Page 5 of 7
`
`

`

`284
`
`Public—Key Algorithms
`
`The first hiock is encrypted as:
`
`68819 (mod 3337) = 1570 = .2,
`
`Performing the same operation on the subsequent blocks generates an encrypted
`message:
`
`c : [570 23356 2714 2276 2423 158
`
`Decryptin g the message requires performing the same exponentiation using the
`decryption key of 1019. So:
`
`1570”“9 (mod 3337) = 688 2 ml
`
`The rest of the message can be recovered in this manner.
`
`Security of BSA
`
`The security of RSA depends wholly on the problem of factoring large numbers.
`Technically that‘s not true. It is conjectured that the security of RSA depends on
`the problem of factoring large numbers. It has never been mathematically proven
`that you need to factor n to calculate m from c and .9. It is conceivable that an
`entirely different way to cryptanalyze RSA might be discovered. However, if this
`new way allows the cryptanalyst to deduce d, it could also be used as a new way
`to factor large numbers. I wouldn’t worry about it too much.
`For the ultra—skeptical, there are RSA variants that have been proven to be as
`difficult as factoring (see Section 12.6). Also look at [20], which shows that
`recovering even a single bit of information from an RSA—encrypted ciphertext is
`as hard as decrypting the entire message.
`Nevertheless, factoring n is the most obvious means of attack. Adversaries will
`have the public key, 3, and the modulus, :1. To find the decryption key, d, they have
`to factor n. Section 9.4 discusses the current state of factoring technology.
`Currently, 1.10—digit numbers are regularly being factored, and 120-digit numbers
`will be able to be factored soon. So, a must be larger than that. Some hardware
`implementations of RSA use 512—bit (154—digit) values for it. I’ve seen 664—bit
`(ZOO—digit) values for n in some software implementations. The most paranoid use
`RSA with [WA—bit (308—digit) it’s. Also read abOut choosing good primes (Section 9.5).
`Assuming the complexity of factoring given in Section 9.4, the factoring of a
`664—bit number takes 1023 steps. Assuming one computer can perform a million
`steps per second, and that a million—computer network works on the task, it will
`take almost 4000 years to factor the number. If n is a 1024—bit number, that same
`array of computers will take 1010 years to factor the number.
`At a European Institute for System Security workshop, the participants agreed
`that a 1024—bit modulus should be sufficient for long-term secrets for the next ten
`years [93]. However, some speakers warned: “Although the participants of this
`
`Page 6 of 7
`
`Page 6 of 7
`
`

`

`12.4
`
`RSA
`
`2.85
`
`workshop feel best qualified in their respective areas, this statement [with respect
`to lasting security] should be taken with caution." Caveat emptor.
`
`RSA in Hardware
`
`Much has been written on the subject of hardware implementations of RSA
`[739,83l,819,241,840,495,682,46,786,285,753222,801]. Agood survey article is
`[161]. Many different chips that perform RSA encryption have been built
`{737,155,607,742,495,37,439,364,716,86] 302.683].
`
`Apartial list of currently available RSA Chips, from [93,161], is given in Table
`12.3.
`
`TABLE 12.3
`
`Existing RSA Chips
`
`BA UD
`RATE
`CLOCK PER 512
`SPEED
`BITS
`
`CLOCK
`CYCLES PER
`512 BIT
`ENCRYP'HON
`
`BITS
`PER
`TECI-lNOLOGY CHIP
`
`NUMBER OF
`TRANSISTORS
`
`COMPANY
`
`Alpha Techn.
`
`25MHZ 13 K
`
`.98 M
`
`2 micron
`
`1024
`
`180,000
`
`AT&T
`British Telecom.
`
`ISMHz 19 K
`IOMHz 5.1 K
`
`.4 M
`1 M
`
`1.5 micron
`2.5 micron
`
`Business Sim. Ltd. 5MH2
`
`3.8 K
`
`.67 M
`
`Gate Array
`
`Calmos Syst. Inc.
`
`20Ml-Iz '28 K
`
`CNET
`
`Cryptech
`
`Cylink
`
`25MHZ 5.3 K
`
`14MHZ 17 K
`
`.4 M
`
`16MHZ 6.8 K
`
`1.2 M
`
`.36 M
`
`2.3 M
`
`2 micron
`
`1 micron
`
`Gale Array
`
`1.5 micron
`
`Pijnenburg
`
`25MH2 50 K
`
`.256 M
`
`1 micron
`
`Plessy Crypto.
`
`~—
`
`10.2 K -—-
`
`——
`
`298
`256
`
`32
`
`593
`
`1024
`
`120
`
`1024
`
`1024
`
`512
`
`100,000
`——
`
`——
`
`95,000
`
`100,000
`
`33,000
`
`150,000
`
`400,000
`
`——-
`
`Sandia
`
`SMHZ
`
`10 K
`
`
`
`2 micron 272.4 M 86,000
`
`
`
`
`
`Speed of RSA
`At its fastest, RSA is about 1000 times slower than DES. The fastest VLSI
`
`hardware implementation for RSA with a 512—bit moduli has a throughput of 64
`kbps [161]. There are also chips that perform 1024—bit RSA encryption. Currently
`chips are being planned that will approach 1 mbps using a 512~bit modulus; they
`wi1l probably be available in 1994. Some manufacturers have implemented RSA
`in smart cards; these implementations are slower.
`In software, DES is about 100 times faster than RSA. These numbers may
`change slightly as technology changes, but RSA will never approach the speed of
`symmetric algorithms. This is why most practical systems use RSA only to
`exchange DES keys, and then use DES to encrypt everything else.
`
`Page 7 of 7
`
`Page 7 of 7
`
`