`
`Mathematical
`
`Cryptology
`
`for
`
`Computer Scientists and
`
`Mathematicians
`
`WAYNEjATTERSON
`Departmenm'omputer Science
`University of New Orleans
`
`
`
`_____._.-.Fl11:-
`
`ROWMAN & LITTLEFIELD
`Publishers
`
`Petitioner Apple - Ex. 1028, p. 1
`
`

`

`ROWMAN 8: LITTLEFIELD
`
`Published in the United States of America in 1987
`by Rowman & Littlefield, Publishers
`(a division of Littlefield, Adams & Company)
`81 Adams Drive, Totowa, New Jersey 07512
`
`Copyright © I987 by Rowman & Littlefield
`
`All rights reserved. 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, or otherwise,
`without the prior permission
`of the publisher.
`
`Library of Congress Cataloging-in-Publication Data
`
`Patterson, Wayne, I945—
`Mathematical cryptology.
`
`Bibliography: p. 287
`Includes index.
`i. Cryptography.
`Zl03.P35
`I987
`ISBN 0-84767438-X
`
`X. Title.
`652'.8
`
`86-l3ll7
`
`American Mathematical Society categories:
`94A60 (Cryptography); llT7l (Coding Theory)
`
`8789919088
`
`[3542
`
`Printed in the United States of America
`
`Petitioner Apple - Ex. 1028, p. 2
`
`

`

`Cryptography Before 1970
`
`15
`
`be sent --- of course, by another channel, since if the attacker were to
`intercept the pad, then the system would be useless.
`
`Rotor Machines
`
`To mechanize the production of ciphertext, various devices were
`invented which speed the process. One important family of such devices
`were the rotor machines, invented in the 1920’s, to implement Vigenere-
`type ciphers with very long periods.
`A rotor machine has a keyboard, and a series of rotors. A rotor is a
`rotating wheel with 26 positions. Each position completes an electric
`contact, and depending on the position. determines a different Caesar shift.
`When a key on the keyboard is depressed, a letter is generated depending
`upon the position of the rotors.
`Two of the best-known of these devices are the Hagelin and the
`Enigma machines. Both were invented in the 1920’s; the Enigma machine,
`the German code machine, was actually patented in the United States by
`Arthur Scherbius in 1923.
`In general, the period of a rotor machine with k rotors is 26‘. (Think of
`the odometer in your automobile.) Consequently, the rotor machine is a
`simple way to implement a VigenEre cipher with very long period.
`The Enigma machine consisted of a plugboard or Steckerboard, which
`simply perrnutes the message text, thence a sequence of rotors (usually 3 or
`5), and a reflecting rotor; it connects letters of the alphabet in pairs.
`The Enigma cryptosystem is xmw = « K, MM”, MR0“, T», where K
`is a space parametrized by the Steckerboard permutation, by the initial
`positions of the rotors, and by the reflecting rotor. The transformation t“ is a
`composition of the following transformations:
`=
`STECIKER'1 ° Rcao‘l ° Ti'l ° RC“) °
`
`. The breaking of the German Enigma machine is probably the most
`
`Petitioner Apple - Ex. 1028, p. 3
`
`

`

`16
`
`Mathematical Cryptology
`
`Cover for the Rotors
`and Lamps
`
`.
`
`I
`
`Reflector
`
`Rotors
`
`
`
`
`
`Steckerboard/ .
`
`
`Figure 1 .4
`The Enigma Machine
`
`Alan Turing, resulted in the saving of thousands of allied lives and the
`shortening of the war. [DEAV 80], [HODG 83], [KAHN 67], [WELC 82].
`However, based on all published material on the efforts at Bletchley
`Park, it would have required only a very simple modification of the Enigma
`machine to have defeated the best efforts of the British cryptographers.
`
`Petitioner Apple - Ex. 1028, p. 4
`
`

`

`Cryptography Before 1970
`
`17
`
`Indeed, the subject of the techniques developed by this group, and the
`devices they invented, could be the subject of a course by itself. And still to
`this day, many of the techniques developed are considered classified by the
`British government.
`
`Final Comments
`
`Cryptosystems based on the Caesar shift and the Vigenere cipher
`formed the basis for most of the successful cryptosystems of the early
`history of the subject, up through the end of the Second World War (and
`beyond).
`Methods such as those implemented by the Enigma machine are
`essentially secure from paper-and-pencil attacks. It is only the development
`of the computer that has rendered further methods necessary.
`
`Hints for Some Exercises
`
`EXERCISE 1.3. The number of permutations possible is 100! A good
`estimate of the size of n! is given by Stirling’s formula:
`11! z (210% e-n nn+'/2
`
`There are 105 microseconds in a second, thus 6 x 107 microseconds in a
`minute.
`
`EXERCISE 1.4. Are there any words or patterns of words which tend to
`appear more often in this text than they might in some other sample of
`English text?
`EXERCISE 1.5. What happens when a “Q” shows up in the message
`text? What must follow it (in English)?
`
`
`
`;.
`i:‘5
`i'.:
`
`.»a-.—w-—-¢w.--.-v.
`
`
`
`Petitioner Apple - Ex. 1028, p. 5
`
`

`

`36
`
`Authentication
`
`Mathematical Cryptology
`
`Consider a cryptosystem based on the traditional “secret-key” approach.
`Consider also that it is used for funds transfer in a banking network. One
`day the system manager receives a message from X. The manager decrypts
`the message using the secret key agreed upon by X and the manager. The
`message reads, “transfer $1,000,000 from my account to the system
`manager’s account”. The manager dutifully does so.
`X complains to the authorities, saying that the message was a forgery,
`sent by the manager himself(herselt). The system manager, when reached
`for comment by long distance telephone from Tahiti, says that the message
`was authentic and that X had recanted his desire to make the transfer.
`Since both X and the manager had to know the secret key, there is no
`way, using the cryptosystem, to resolve the disPute.
`However, a public-key cryptosystem could have resolved the issue.
`Suppose that, in addition to the message, every transmission in the network
`is required to be “signed”, that is, to contain a trailer encrypted using X’s
`public key. Then, this requirement would carry with it the ability to
`authenticate X’s message, since only X, knowing the rest of the key, would
`be able to decrypt the trailer.
`Therefore, if we could devise a PKC, it would certainly have most
`desirable features. But many questions remain to be asked First of all, can
`we devise a PKC? What should we look for? Second, if we can find one,
`will it be secure? Will it be efficient?
`These questions will, of course, be addressed in the succeeding
`chapters. For now, we will consider only the general parameters offinding
`PKCs.
`
`From the earlier description, we need to find functions that are “one-
`way”, that is, that enable an efficient computation sufficient for encryption,
`but whose inverses are cryptanalytically very difficult to find
`It is interesting that the two examples we will study next are analogous
`in some sense: one involves the ease of adding numbers together combined
`with the diffiCulty (or impossibility) of determining the original addends,
`given a sum; the other involves the ease of multiplying numbers together
`combined with the difficulty of finding the original factors, given a product.
`
`Petitioner Apple - Ex. 1028, p. 6
`
`

`

`
`
`..__. 8 __
`
`Other Security Problems
`
`In addition to the classic problem of cryptography, as represented
`throughout the monograph by the cryptosystem x = « K, M, C, T », there
`are some closely related problems which lend themselves to similar
`analyses.
`
`The Authentication Problem
`
`In an earlier chapter, the authentication problem was mentioned briefly.
`It differs from the encryption problem in that the message, or at least part of
`il. must be transformed in a way that only the sender can authenticate.
`As we saw in the earlier chapter, no secret-key cryptosystem can
`Provide authentication -—- since the secret key is always shared between the
`authentic sender and at least one other person, that other person could
`
`always “forge” the message.
`0f the public-key encryption systems described, only the RSA
`cryptosystem can be adapted for authenticafion as well as for secrecy (not at
`the same time, however).
`Consider using the RSA algorithm for authentication alone. As with the
`use of the RSA for secrecy, each user, i, generates a secret key pi, qi of
`loo-digit primes, and di; and publishes ni = piqi and ei = d;1 (mod uni».
`Recall that the enciphering transformation is E,(m) = mei
`(mod ni), and
`the (secret) deciphering transformation is Di(m) = mdi (mod 11,).
`In order to provide a message that can be authenticated, user i applies
`the transformation Di(m) and sends this message. The receiver of the
`message, in order to authenticate that the message came from i, consults the
`Public directory and applies the transformation Ei. Consequently, the
`receiver obtains
`
`Engm»
`
`= mdi (mod ni)
`
`Petitioner Apple - Ex. 1028, p. 7
`
`

`

`116
`
`Mathematical Cryptology
`
`= mdi-ei
`= 111.
`
`(modni)
`
`Furthermore, only i could have generated the message, since only i
`knows the transformation Di. There is, however, no secrecy involved, since
`any user of the network can attempt the decryption by trying the public key
`E.
`
`However, RSA can simultaneously provide secrecy and authentication
`by using a double transformation. Namely, when user i wants to send a
`message to user j, and to authenticate it (this is often called signing the
`message), useri uses the decryption transformation D,, and then uses user
`j’s public key to encrypt the message for secrecy. Consequently the
`transformation is:
`
`E,- (Di (m) ).
`
`When the message is received by j, j applies his/her decryption
`transformation, which only j knows, followed by i’s public encryption
`transformation for authentication. Thus:
`
`Ej(Di(m)) —9
`
`Ei(Dj(Ej(Di(m))))
`=Ei(Di(m)) = m
`
`The Merkle—Hellman and Graham-Shamir knapsacks carmot be used for
`authentication, since the enciphering transformation maps the message space
`not onto itself but rather to the integers; consequently, it cannot be inverted
`However, there is a Shamir “signature~only” knapsack algorithm. It is
`based on the knapsack-like problem:
`Given n, S e Z, and W = (W1, wz,
`such that
`
`...w2k ), find C = (c1, c2,
`
`cu )
`
`S=CW=Zciwi
`
`(modn)
`
`where each c,- e [0, log n].
`
`n is chosen to be a (say, 100-bit) random prime number, and the pair
`(W,n) is the public key.
`It is a message of [log n] bits so that in binary form, it represents an
`integer in the range [0, n- l].
`The sender constructs a k x 2k binary matrix H at random. A set of
`knapsack numbers are chosen to satisfy:
`
`Petitioner Apple - Ex. 1028, p. 8
`
`

`

`Standardization ofPublic-Key Encryption
`
`145
`
`messages, but can be an option (OSIScon) of open
`communications systems, as e.g. Teletex.
`Signatures are effected by the OSIS token, a credit card
`sized device issued by a bank, similar to a chipcard. but In
`addition providing a foil key input and display. The token is
`carried by Its owner. He keys in the payment message and his
`PIN (Personal Identification Number). The token authenticates
`him by his PIN. A positive authentication result activates the
`token to sign the (payment) message. After signing the message
`the token is deactivated.
`
`The signature is effected in the token by an asymmetric
`encipherment algorithm and the token's secret key,
`the
`(condensed) payment message being the cleartext input and the
`signature the ciphertext output. The token concatenates the
`message, the signature, and its own identifier. consisting of a
`token's public key, PKtoken, the latter's signature by the issuing
`bank's secret key, the bank's public key PKbank, and the latters
`signature by the OSIS central bank's secret key. For
`authentication purposes every token stores the bank‘s public
`key PKbank, which in turn authenticates the signing token's
`public key, PKtoken, which in turn authenticates the signature.
`For the encipherment algorithm the RSA scheme is being used
`at present.
`
`The token must be tamper-resistant and prevent exhaustive
`PIN search. It must give warning of attempts at intrusion. After
`three wrong PIN inputs, it must destroy its secret information.
`
`Key Management for Symmetric Ciphers:
`
`Whatever the sophistication of a key managemem system for
`data encipherment using a symmetric cipher, the fundamental
`problem is usually one of establishing master keys at the
`communications parties to allow for the secure exchange of
`session keys. The general solution to this problem involves a
`physical action to install the master keys; a secure key transport
`module may be used or the keys can be transported in printed
`form. In large networks the setting up of master keys operating
`between many pairs of communicating parties can be a very
`onerous task. In all cases, the master key must be kept secret.
`If a public key cryptosystem is also available to the system
`designer, the key management task can be transformed. What is
`then needed is a reliable source of public keys for each
`participating user. Given such a reliable source, it is possible to
`encipher master keys for symmetric ciphers using public keys.
`
`Petitioner Apple - Ex. 1028, p. 9
`
`

`

`146
`
`Mathematical Cryptology
`
`This enables a hybrid cipher system to be operated - using public
`keys for master key protection (with the simplified key
`management thereby available) and a symmetric cipher for the
`exchange of session keys and for data enclpherment (with the
`higher operating efficiency of the symmetric cipher). The vital
`issue in such a system is the need for absolute integrity of the
`source of public keys.
`
`Technical Properties
`
`Technical properties of public-key cryptosystems that may, in the
`future, match legal requirements are:
`
`The limiting factor is the perpetuation of
`Permanance:
`magnetically recorded information. The problem has been solved
`for data processing in general.
`Immutabllity: Quality A is sufficient for lmrnutability of the text
`signed. lmmutability of the document signed requires also quality
`E.
`
`Identification: The signing key must not be determinable by
`public information; its owner must keep it secret and must not
`make It available to anyone else. Quality C (including qualities A-
`B) is sufficient for identification.
`Negotiability: This property is provided by quality C. Partners
`must not conspire. Quality F provides for the negotiabllity
`(against conspiring partners) of a signature witnessed by a
`notary.
`A signature must be significant enough to
`Significance:
`change a legal situation; it must promote a warning to the signer
`that he is about to commit something important. Effectlng an
`electronic signature requires attention, e.g.
`it may only be
`achieved if one activates one‘s signing device (by putting in a
`PIN) and presses a key to sign and another key to transmit the
`message.
`Immediate trust: The receiver must be able to trust the
`
`signature prima facie. The digital signature not only can be pn'ma
`facie
`authenticated with the attached public key;
`full
`authentication with a trusted third party's authentic public key
`need not take much longer; for this purpose the attached public
`key can be authenticated by the trusted third party.
`Quality D cannot be provided by a handwritten signature, and
`therefore. neither may be required for its substitute. Quality F is
`
`Petitioner Apple - Ex. 1028, p. 10
`
`