Declaration of Rachel J. Watters on Authentication of Publication
`
`I, Rachel J. Watters, am a librarian, and the Director of Wisconsin TechSearch
`
`("WTS"), located at 728 State Street, Madison, Wisconsin, 53706. WTS is an
`
`interlibrary loan department at the University of Wisconsin-Madison. I have worked as
`
`a librarian at the University of Wisconsin library system since 1998. I have been
`
`employed at WTS since 2002, first as a librarian and, beginning in 2011, as the Director.
`
`Through the course of my employment, I have become well informed about the
`
`operations of the University of Wisconsin library system, which follows standard library
`
`practices.
`
`This Declaration relates to the dates of receipt and availability of the following:
`
`Davida, G.I. and Danes, F. B. (1988). A crypto-engine. In
`Pomerance, C. (Ed.) Advances in Cryptology- CRYPTO '87.
`Springer-Verlag. pp. 257-268.
`
`Standard operating procedures for materials at the University of Wisconsin-
`
`Madison Libraries. When a volume was received by the Library, it would be checked
`
`in, stamped with the date of receipt, added to library holdings records, and made
`
`available to readers as soon after its arrival as possible. The procedure normally took a
`
`few days or at most 2 to 3 weeks.
`
`Exhibit A to this Declaration is a true and accurate copy of the cover with library
`
`date stamp of Advances in Cryptology- CRYPTO '87 (1988), from the University of
`
`Wisconsin-Madison Library collection. Exhibit A also includes an excerpt of pages 257
`
`to 268 of that volume, showing the article entitled A crypto-engine (1988). Based on
`
`1
`
`Oracle-1037 p. 1
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`Declaration of Rachel J. Watters on Authentication of Publication
`
`this information, the date stamp on the journal title page indicates A crypto-engine
`
`(1988) was received by the University of Wisconsin-Madison Libraries in 1990.
`
`Members of the interested public could locate the Advances in Cryptology -
`
`CRYPTO '87 (1988) publication after it was cataloged by searching the public library
`
`catalog or requesting a search through WTS. The search could be done by title and/or
`
`subject key words. Members of the interested public could access the publication by
`
`locating it on the library's shelves or requesting it from WTS.
`
`I declare that all statements made herein of my own knowledge are true and that
`
`all statements made on information and belief are believed to be true; and further that
`
`these statements were made with the knowledge that willful false statements and the like
`
`so made are punishable by fine or imprisonment, or both, under Section 1001 of Title 18
`
`of the United States Code.
`
`Date: September 24, 2020
`
`Wisconsin TechSearch
`Memorial Library
`728 State Street
`Madison, Wisconsin 53706
`
`Director
`
`2
`
`Oracle-1037 p. 2
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`
`
`Oracle-1037 p. 3
`Oracle v. Teleputers
`|PR2021-00078
`
`Oracle-1037 p. 3
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`• CLASS SEP •.
`Lecture Notes In sER\Al
`Computer Science
`
`Edited by G. Goos and J. Hartmanis
`
`293
`
`Carl Pomerance (Ed.)
`
`Advances in Cryptology -
`CRYPTO '87
`
`Proceedings
`
`kbkf ?. WtNDI EIBRARI
`COLLEGE OF ENGINE~R1NG
`UNIVERSITY OF WISCONSIN
`MADISON, WI 53706
`
`i
`
`Springer-Verlag
`Berlin Heidelberg New York London Paris Tokyo
`
`Oracle-1037 p. 4
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`Editorial Board
`D. Barstow W. Brauer P. Brinch Hansen D. Gries D. Luckham
`C . Moler A. Pnueli G. Seegmuller J. Stoer N. Wirth
`
`Editor
`Carl Pomerance
`Department of Mathematics, The University of Georgia
`Athens, Georgia 30602, USA
`
`CR Subject Classification (1987): E.3
`
`ISBN 3-540-18796-0 Springer-Verlag Berlin Heidelberg New York
`ISBN 0-387-18796-0 Springer-Verlag New York Berlin Heidelberg
`
`This work is subject to copyright. All rights are reserved, whether the whole or part of the material
`is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation,
`broadcasting, reproduction on microfilms or in other ways, and storage in data banks. Duplication
`of this publication or parts thereof is only permitted under the provisions of the German Copyright
`Law of September 9, 1965, in its version of June 24, 1985, and a copyright fee must always be
`paid. Violations fall under the prosecution act of the German Copyright Law.
`CC> Springer-Verlag Berlin Heidelberg 1988
`Printed in Germany
`Printing and binding: Druckhaus Beltz, Hemsbach/Bergstr.
`2145/3140-543210
`
`Oracle-1037 p. 5
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`TABLE OF CONTENTS
`
`SECT.ION l: COMMUNICATION NETWORKS AND STANDARDS
`
`Standards for data security -
`W. L. Price
`
`a change of direction
`
`Integrating. cryptography in ISDN
`K. Presttun
`
`SECTION 2:
`
`PROTOCOLS
`
`Special uses and abuses of the Fiat-Shamir passport protocol
`(Extended abstract)
`. . • . . • • • . . • • . •
`Y. Desmedt, C. Goutier, and S. Bengio
`
`Direct minimum-knowledge computations (Extended abstract)
`R. Impagliazzo and M. Yung
`
`Non-interactive zero-knowledge proof systems .
`A. De Santis, S. Micali, and G. Persiano
`
`How to solve any protocol problem - an efficiency improvement
`(Extended abstract)
`.
`.
`.
`.
`. . . . • • . . • . . •
`O. Goldrei.ch and R. Vainish
`
`Multiparty computations ensuring privacy of each party's input and
`correctness of the result
`. . . • •
`D. Chaum, I. B. Damg!rd, and J. van de Graaf
`
`3
`
`9
`
`21
`
`40
`
`52
`
`73
`
`87
`
`Society and group oriented cryptography: A new concept • • . . • • . . . 120
`Y. Desmedt
`
`A simple and s.ecure way to show the validity of you1· public key • • . • . 128 '
`J. van de Graaf and R. Peralta
`
`Cryptographic computation: Secure fault-tolerant protocols
`and the public-key model (Extended abstract) • • • • . . . • • • • • . . • 135
`z. Galil, S. Haber, and M. Yung
`
`Oracle-1037 p. 6
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`VIII
`
`Gradual and verifiable release of a secret (Extended abstract) • • • • • . 156
`E. F. Brickell, D. Chaum, I. B. Damglrd, and J. van de Graaf
`
`, Strong practical protocols • •
`J. H. Moore
`
`. • • • 167
`
`SECTION 3: KEY DISTRIBUTION SYSTEMS
`
`Identity-based conference key distribution systems . . . •
`K. Koyama and K. Ohta
`
`.
`
`• 175
`
`On the key predistribution system:
`distribution problem ••
`T. Matsumoto and H. Imai
`
`A practical solution to the key
`
`• . • 185
`
`Key distribution systems based on identification information . . . • • . • 194
`E. Okamoto
`
`Secret distribution of keys for public-key systems (Extended abstract) . • 203
`J.-J. Quisquater
`
`SECTION 4: PUBLIC KEY SYSTEMS
`
`An impersonation-proof identity verification scheme
`G. J. Simmons
`
`• • . . . . . . . . 211
`
`Arbitration in tamper proof systems (If DES~ RSA then what's the
`difference between true signature and arbitrated signature schemea1) • • • 216
`G. I: Davida and B. J. Matt
`
`Efficient digital public-key signatures with shadow (Abstract) . • . . . . 223
`L. Guillou and J.-J. Quisquater
`
`Security-related comments regarding McEliece's public-key
`cryptosystem .
`.
`.
`.
`.
`.
`.
`C. M. Adams and H. Meijer
`
`. . . . . . . . 224
`
`SECTION 5: DESIGN AND ANALYSIS OF CRYPTOGRAPHIC SYSTEMS
`
`Components and cycles of a random function
`J.M. DeLaurentis
`
`. • • 231
`
`Fast spectral tests for measuring nonrandomness and the DES . . . . . . . 243
`F. A. Feldman
`
`Other cycling tests for DES (Abstract) • • . . • . . . . . • • . . . . . . 255
`J.-J. Quisquater and J.-P. Delescaille
`
`Oracle-1037 p. 7
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`IX
`
`.
`.
`.
`• • • •
`.
`•
`A crypto-engine
`G. I. Davida and F. B. Danes
`
`•
`
`.
`
`.
`
`.
`
`• • • • • • • • • • • • • • • • 257
`
`A natural taxonomy for digital information authentication schemes
`G. J. Simmons
`
`. •. • • • 269
`
`Analyzing encryption pr.otocols using formal verification techniques
`(Extended abstract)
`.
`•
`.
`•
`.
`• •
`.
`•
`.
`.
`.
`.
`.
`.
`.
`•
`.
`• • • •
`R. A. Kemmerer
`
`.
`
`• 289
`
`Cryptosystems based on an analog of heat flow
`G. R. Blakley and W. Rundell
`
`.
`
`.
`
`• • • • •
`
`.
`
`• •
`
`.
`
`• • • 306
`
`A combinatorial approach to threshold schemes . . . . • • • • . • • • . • 330
`D.R. Stinson and S. A. Vanstone
`
`A realization scheme for the identity-based cryptosystem . . • • • • . • • 340
`H. Tanaka
`
`Equivalence between two flavours .. of oblivious transfers • • . • • • • • . 350
`C. Crepeau
`
`A constr.uction for authentication/ secrecy codes from. certain
`combinatorial designs
`.
`.
`.
`.
`.
`.
`.
`•
`.
`•
`.
`.
`.
`.
`.
`.
`.
`.
`.
`D.R. Stinson
`
`.
`
`•
`
`.
`
`• • •
`
`. 355
`
`SECTION 6: APPLICATIONS
`
`A digital signature based on a conventional encryption function . . . . • 369
`R. C. Merkle
`
`How to make replicated data secure
`M. P. Herlihy and J. D. Tygar
`
`A study of password security
`M. Luby and C. Rackoff
`
`. . . . . . . . . . • . . • • • 379
`
`. . . . . . . . . . • . . . . . . . . . 392
`
`A video scrambling technique based on space filling curves
`(Extended abstract)
`.
`.
`.
`.
`.
`•
`.
`.
`.
`•
`.
`.
`.
`.
`.
`.
`Y. Matias and A. Shamir
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`• 398
`
`Secure audio teleconference . . . . . . . . . . . . . . . . . . . . . . • 418
`E. F. Brickell, P. J. Lee, and Y. Yacobi
`
`SECTION 7:
`
`INFORMAL CONTRIBUTIONS
`
`Attack on the Koyama-Ohta identity based key distribution scheme . . • • • 429
`Y. Yacobi
`
`On the F-function of FEAL . . . . . . . . . . . . . . . • • . . • • • • • 434
`W. Fumy
`
`Oracle-1037 p. 8
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`X
`
`Patterns of entropy drop of the key in an S-box of the DES
`(Extended abstract)
`• • • •
`K. C. Zeng, J. H. Yang, and z. T. Dai
`
`. • • . • • • • 438
`
`The Rao-Nam scheme is insecure against a chosen-plaintext attack • • • • • 445
`R. Struik and J. van .Tilburg
`
`On Struik-Tilburg cryptanalysis of Rao-Nam scheme • . • • • • • • • • • • 458
`T. R. N. Rao
`
`A generalization of Hellman's extension of Shannon's approach to
`cryptography (Abstract) . . • . . • . • . • . • . . • • . • • . . • • • • 461
`P. Beauchemin and G. Brassard
`
`Multiparty unconditionally secure protocols (Abstract) • . . • • . . . • • 462
`D. Chaum, C. Crepeau, and I. Damgird
`
`'I
`
`AUTHOR INDEX . . • • . • . . . . • • • . . . . . . . . . • • . . • • . • • 463
`
`Oracle-1037 p. 9
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`A Crypto-Engine
`
`George I. Davida
`Frank B. Danes
`
`University of Wisconsin-Milwaukee
`Milwaukee.WI 53201
`
`Abstract
`
`In this paper we present a design for a crypto-engine. We shall discuss the design
`and show the instruction set of this coprocessor and then show how this could be used
`to implement most of the known encryption algorithms. We will discuss why a copro(cid:173)
`cessor approach may be a better solution than adoption of specific encryption algorithms
`which can be broken or decertified.
`
`L Introduction
`
`With the ever increasing use of encryption techniques to safeguard data, a need has
`become apparent for special hardware to implement these schemes due to the ineffl.ciency
`of software methods. Special hardware such as DES chips have the draw back of being
`useful for only one encryption technique. Many have discussed the week.ness of the
`method and site potential problems with the sboxs. Furthermore, if DES is not certified
`as the standard for encryption, many existing chips will become obsolete.
`Taking this into consideration, a hardware design that could increase the effl.ciency
`of computation while allowing versatility for many existing encryption algorithms and
`possibly future ones has been considered. Much like a floating point coprocessor, we
`have designed an encryption coprocessor. With basic instructions common to the variety
`of algorithms used today, the design presented in this paper facilitates implementing of
`most encryption algorithms.
`The design of this coprocessor has been based on the Motorola 680001 coprocessor
`protocol. It has been implemented in software for testing purposes. Implementation de(cid:173)
`tails will also be discussed later in the paper.
`
`ssol'Cio:esearch reported in this paper was supported in part by NSF grant OCR-
`
`Oracle-1037 p. 10
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`II. Need For a Coprocessor
`
`258
`
`With chip prices coming down, replacing software tools with hardware tools has be(cid:173)
`come more practical. The problem with hardware is that it may not always be as flexi(cid:173)
`ble as one would want. Take for example the DES chips that are on the market.
`Although they are excellent for preforming their assigned tasks, they can only preform
`one task and that is encrypting data with the DES standard. If this standard is broken
`or decertified as the standard, these chips would be obsolete. Replacement costs for this
`specialized hardware could be expensive.
`Unlike other types of hardware, encryption hardware has the drawback of poten(cid:173)
`tially becoming useless with the ever possible chance that the algorithm the hardware
`implements is broken. Other types of hardware could become obsolete with the advent
`of a new and better device, however; the old hardware is still useful.
`The other disadvantage of a standard encryption chip is that standards can be
`changed. A specialized chip can only implement one encryption technique. If the stan(cid:173)
`dard would change then those using the standard would not be able to communicate
`with those using the old standard. Since reprogramming is not possible, this desired ver(cid:173)
`satility cannot be achieved by these specialized chips. After all, what is the difference
`between a calculator and a computer? It is not the greater capability of the computer or
`its faster processing. It is the versatility of the computer brought about by the ability
`to be programmed for many different applications.
`With this in mind a coprocessor with special instructions that would be useful for
`encryption appears to be a better solution. If a standard encryption technique is
`decertified a coprocessor could easily be reprogrammed. A new technique could easily be
`installed. Not only could a new standard be adopted without any hardware changes,
`different techniques could be used simultaneously for different applications. Further(cid:173)
`more, techniques could be altered to meet specific requirements of local environments.
`The advantage over just pure software implementations of the encryption techniques is,
`of course, special instructions implemented in hardware would bring about a speed ad(cid:173)
`vantage.
`
`IIL Coprocessor Design
`
`To make a hardware device that can implement most of the known algorithms of
`today and still leave room for tomorrows, we need to consider what are the basic opera(cid:173)
`tions of encryption algorithms. There are two basic operations that are used for encryp(cid:173)
`tion. They are substitution and transposition 2• Most crytographic techniques use a
`combination of both.
`Substitution operations can be table lookup, many types of arithmetic operations
`such as multiplication, exponentiation, etc. Transposition operations on the other hand
`are of the form, permutation on the bits of a word, shift registers, and modular arith(cid:173)
`metic, where the permutation is of the entire message space.
`With this in mind, we propose a set of encryption primitives. The substitution in(cid:173)
`structions include all arithmetic in large register form, an actual table lookup and its
`supporting instructions, and three of the boolean operators, and, or, and xor. For the
`permutation operations, we included a bit permuter, three different shift operations, and
`the modular arithmetic operation.
`
`Oracle-1037 p. 11
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`IV. Design Details
`
`259
`
`The registers, illustrated below, that will be needed to support these instructions
`must be of a larger than normal size. For example, RSA uses numbers approximately of
`200 decimal digits large. For this type of arithmetic, there are four large registers, 1024
`bits each. This will allow for roughly 300 decimal digits. These registers will support
`all the arithmetic instructions. There will also be the need for smaller registers for sub(cid:173)
`stitution and permutation operations. There are five 128 bit registers. One of these re(cid:173)
`gisters, the general register, can be addressed as four 32 bit registers, two 64 bit registers,
`or the entire 128 bit register. Finally, there are 16 tables consisting of 256 bytes each
`supporting the table lookup operation.
`
`Register Layout of the Encryption Copr~r
`
`The larger register layout
`1024 bits L1 Large Purpose register
`1024 bits L2 Large Purpose register
`1024 bits L3 Large Purpose register
`1024 bits L4 Large Purpose register (ML) Modules constant
`
`General register, key register and modular constant layout (128 bits)
`Ghl(high.left) I Ghr(high.right) I Gll(low.left) I Glr(low.right)
`128 bits KO key register
`128 bits Kt key register
`128 bits K2 key register
`128 bits MS Small Modular constant register
`
`. Sbox Array
`Array For Slice 1
`
`Array For Slice 2
`
`Array For Slice 16
`
`The instructions listed in Appendix A are the instructions that we have considered
`necessary to fulfill the requirements of our list of basic operations. The instructions
`listed in the Appendix follow these rules of use. Those that have <reg>, <greg>, or
`<lreg> can support the register direct addressing mode on any register, the general re-
`
`Oracle-1037 p. 12
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`260
`
`gister only, and one of the large registers only, respectively. The instructions that have
`<regl> or <reg2> as their operands have the following addressing modes: register
`direct, register indirect, memory immediate, and memory indirect. Furthermore, the in(cid:173)
`direct addressing mode using the main processors registers a{), a6, and a7 has the follow(cid:173)
`ing subdivisions: register indirect, register indirect with au~increment, register indirect
`with au~ecrement, and register indirect with index.
`
`V. Detailed Description Of Some Selected Instructions
`
`The brief description of each instruction presented in the Appendix may not give
`enough information on some of the more complex instructions, and may not completely
`show the versatility of them.
`The sbox substitution is probably the most complex operation. The esbox instruc(cid:173)
`tion can do substitution on a number of bit combinations. The programmer can choose
`from 8, 6, or 4 bits into the substitution and 8, 6, or 4 bits out of the substitution. The
`number of input bits does not have to be the same as the number of output bits. To ini(cid:173)
`tialiu this we will need the .einitsbox instruction. This will set up the esbox instruction
`for operation with one of these combinations of input bits and output bits. We will
`refer to a string of bits that will be used for one atomic substitution, either 8, 6, or 4
`bits in si7.C, as a substitution word.
`As seen by the register layout diagram, there are 16 sbox arrays, each having 256
`bytes of storage. Each of these arrays are to be used for one substitution. That is, one
`substitution word will be an index to one of these sbox arrays. When the substitution
`· word indexs one of the bytes in the array, 8 bits, 6 bits, or 4 bits will be used depending
`on the number of bits that has been set up by the einitsbox instruction for output.
`All of the memory in the sbox array will not be utilized for every substitution
`· combination. For example, if a programmer where to initialiu this operation to 4 bits in
`and 8 bits out with a 64 bit register, all of the 16 sbox arrays would be used, however,
`only 16 bytes out of each array would be used.
`To load the sbox arrays the el.dsbox instruction will be used. The number of the ar(cid:173)
`ray will be needed as well as the number of bytes in that array. In the example above,
`there will be 16 el.dsbox instructions needed to load all of the arrays. Each of these in(cid:173)
`struction will specify n-1 as the number of bytes to load and m for the slice number.
`The only address mode that will be allowed is memory indirect. This will allow the
`programmer to initialiu their sbox arrays somewhere in memory with a label, and use
`that label with the instruction.
`There are two permutation instructions, eperms and epermd, representing control
`from the source and control for the destination. These will be used for two different
`types of permutations. The eperms instruction will allow permutation of one bit to
`multiple bits, while, the epermd instruction, will allow multiple bits to be permuted to
`one bit. Below is a diagram that should clear up the two different permutation instruc(cid:173)
`ti.ons. Note, only four bits of the general register is used, and the first four bytes of the
`l1 registers are used. In the ll registers we will store the following first four control
`bytes, these will control the first four bits in the general register signified by a letter in
`the alphabet.
`14 1 1 1 2 1 4 I
`
`Oracle-1037 p. 13
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`261
`
`This is what is stored in the first four bits of the original general register, g.
`IA I BI CID I
`Permuting the original with the instruction: e-perms ll ,g
`ID I A IBID I
`Permuting the original with the instruction: epermd ll ,g
`IBICIOIAEBDI
`The example above points out the situation for the epermd instruction where no bit was
`assigned to destination of the third bit location. In this case, the third location obtains
`the value zero. Furthermore, if two or more bits go to the same destination, the values
`of those two or more bits are xored together.
`The e-perms instruction would be used in something like the sbox expansion of DE$,
`and the epermd instruction would be used in something like a linear shift register with a
`finite state machine.
`
`VL Details Qf Various Algorithm Implementation
`
`The following implementations are written in the high level language of C and the
`program listings are found in Appendix B. The asm is a construct that allows a pro(cid:173)
`grammer to give an instruction directly to the assembler. After compiling this code the
`modified assembler can translate the coprocessor instructions into machine language. All
`of the coprocessors instructions are noted by italics. Note, some parts of main line,
`functions, and array initia117.ations are omitted to conserve space.
`DES3 was an important consideration in the design of the coprocessor. As long as
`DES is the standard there will be a need to implement it.
`A few points need to be noted for clarity. First, the sbox expansion is done like a
`standard DES sbox expansion. However, after the xor with the key, the bits must be
`permuted again to facilitate the b5b0b4b3b2bl pattern. In other words, since the sbox
`substitution instruction of the coprocessor does a direct table look.up on the address that
`the six given bits generate, they must be permuted to follow the pattern that is neces(cid:173)
`sary to follow the DES algorithm. This is because the algorithm calls for the first and
`last bit of the six bit substitution word be the index to the row and the middle bits be
`the index to the column. In the coprocessor the data is layed out continuously instead
`of having a row and column; thus, the last bit needs to be moved to the second bit. Since
`the large registers are capable of holding a 128 bit permutation, the sbox_expansion ar(cid:173)
`ray will hold both permutations, which in tum is moved to the l4 register.
`The RSA implementation is pretty straight forward since the algorithm is nothing
`more than:
`(encrypt)
`C • ~ mod n
`M - CC1 mod n
`(decrypt)
`where e is the encryption key and d is the decryption key. This means that the only
`steps that need to be done are load one of the large registers with the data, do an ex(cid:173)
`ponential instruction with an automatic modular arithmetic with the ml. register, and
`move the data from the large register back into memory.
`The Pohlig-Hellman scheme is another exponential encryption technique; however,
`it could be implemented in two different ways. The basic algorithm is 4
`c-~modp
`
`Oracle-1037 p. 14
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`262
`
`M-c1modp
`where e is the enciphering key and d is the deciphering key. The p could either be a
`prime or a GF(2m) irreducible polynomial. Either way, it could be implemented quick.ly
`and easily.
`The first implementation, where p is a prime, could be done exactly like the RSA
`listed in Appendix B, except ml would receive the prime value. To do the next imple(cid:173)
`mentation, do the exact implementation as the RSA example with these two changes.
`Put a irreducible polynomial in ml, and replare the following line:
`asmc■ eexpml
`ll,l2•);
`
`with
`
`VII. Remarks
`
`Many other algorithms could be implemented. For example, the Shamir 5 Lagrange
`Interpolating Polynomial Scheme could be done with the arithmetic under Galois Fields
`instructions. All the neassary instructions are available to implement this scheme: ad(cid:173)
`dition, division and multiplication all in GF(2m). Consider the irreducible polynomial
`p(x) - x3 + x + 1; the corresponding binary representation would be 1011. This number
`would be put in the ml or ms register depending on the siu of the integer arithmetic.
`This would then mean that all the arithmetic would be done under the Galois Field
`GF(23) with 1011 as the irreducible polynomial.
`Another method for encryption could be implemented just as easily. The Block. Ci(cid:173)
`phers with Subkeys 6 could be implemented with the basic arithmetic mod instructions.
`In this scheme the basic operations are inverse (edivml), multiplication (emultml), and
`addition (eaddml).
`The software implementation was done on a Motorola 68010 based system. The
`68000 protocol for coprocessor instruction identification is what is referred to as an P(cid:173)
`line instruction. This F-line instruction will precede any coprocessor instruction. It will
`have the coprocessor identification number as well as other information. If the coproces(cid:173)
`sor doesn't exist in hardware, the processor will invoke a F-line emulation trap (vector
`11). With this, we can trap the instruction in the kernel and start the emulation pro(cid:173)
`cess. On a UNIX bsd 4.2 system this is just a quick. addition in the trap.c code to cap(cid:173)
`ture the interrupt and a function call to the emulation routines. In the emulation rou(cid:173)
`tines, the first step is to check. what the instruction is and call the appropriate emulation
`function.
`The implementation of the Galois fields followed the Scott, Stafford and Peppard7
`algorithm for multiplication and the Davida and Litow8 algorithm for inverse. Other
`implementations of arithmetic were done by methods that made the software easiest to
`write, not considering hardware problems.
`
`Appendix A
`
`Instruction Set
`
`eadd <regl>,<reg2>
`
`The eadd instruction adds the source < regl >
`to
`the destination < reg2> and stores the result in the
`
`Oracle-1037 p. 15
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`eaddms <regl> ,<reg2>
`eaddml < regl > , < reg2 >
`
`eaddgfms < regl >, < reg2 >
`eaddgfml < regl >, < reg2 >
`
`esub < regl >, < reg2 >
`
`esubms <regl>,<reg2>
`esubml < regl >, < reg2 >
`
`esubgfms < regl >, < reg2 >
`esubgfml < regl >, < reg2 >
`
`emult <regl>,<reg2>
`
`emultms <regl>,<reg2>
`emultml <regl>,<reg2>
`
`emultgfms <regl>,<reg2>
`emultgfml < regl >, <reg2>
`
`ediv <regl>,<reg2>
`
`edivms <regl> ,<reg2>
`edivml < regl > , < reg2 >
`
`edivgfms < regl >, < reg2 >
`edivgfml <regl>,<reg2>
`
`eexp <regl> ,<reg2>
`
`eexpms <regl> ,<reg2>
`
`263
`
`destination < reg2>.
`
`The eaddms and eaddml instructions do the same
`addition mod the (ms) and (ml) registers respec(cid:173)
`tively.
`
`The eaddgf ms and eaddgfml instructions do the ad(cid:173)
`dition in the Galios Field GF(2m) using the (ms)
`and (ml) registers respectively to store tlie irreduci(cid:173)
`ble polynomial P(x).
`
`The esub instruction subtracts the source < regl >
`from the destination <reg2> and stores the result
`in the destination < reg2>.
`
`The esubms and esubml instructions do the same
`subtraction mod the (ms) and (ml) registers respec(cid:173)
`tively.
`
`The esubgfms and esubgfml instructions do the
`subtraction in the Galios Field GF(2m) using the
`(ms) and (ml) r e~ i:espectively to store tlie ir(cid:173)
`reducible polynomial P(x).
`
`The emult
`the source
`instruction multiplies
`to the destination(reg2) and stores the
`< regl >
`result in the destination <reg2::>.
`
`The emultms and emultml instructions do the same
`multiplication mod the (ms) · and (ml) registers
`respectively.
`
`The emultgf ms and emultgfml instructions do the
`multiplication in the Galios Field GF(2m) using the
`(ms) and (ml) ~ i:espectively to store tlie ir(cid:173)
`reducible polynomial P(x).
`
`The ediv instruction divides the source < regl >
`into the destination < ~2> and stores the result
`in the destination <reg2>.
`
`The edivms and edivml instructions do the same
`division mod the (ms) and (ml) registers respec(cid:173)
`tively.
`
`The edivgfms and edivrlml instructions do the
`division in the Galios Field GF(2m) using the (ms)
`and (ml) r e~ ,;:espectively to store the irreduci(cid:173)
`ble polynomial P(xJ.
`
`The eexp instruction takes destination < reg2> to
`the power of the source <regl> and stores the
`result in the destination < reg2>.
`
`Oracle-1037 p. 16
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`ccxpml < rcgl >, < rcg2 >
`
`ccxpgf ms < regl >, < reg2 >
`ccxpgfml <rcgl> ,<rcg2>
`
`cunsetsign
`csctsign~
`
`cmod <regl>,<rcg2>
`
`cmov <regl>,<rcg2>
`
`264
`
`The eexpms and eexpml instructions do the same
`exponentiation mod the (ms) and (ml) registers
`respectively.
`
`The eexJ>gf ms and eexP2f ml instructions do the ex(cid:173)
`ponentiation in the Galios Field GF(2m) usin.ng the
`lms) and (ml) r e~ r_espectivcly to store tlie ir(cid:173)
`reducible polynomial P(x).
`
`These two instructions will set all arithmetic in an
`unsigned mode and set all arithmetic in a signed
`mode, ~vely.
`
`The emod instruction will do a modular arithmetic
`operation. The destination < ~2> mod source
`<regl> and place the results in the destination
`<reg2>.
`
`instruction will move <i:egl>
`to
`The emov
`< rq2>. This can also be used to load registers
`witli the different address modes available.
`
`cldsbox #array ,#bytcs,_mcmory _location
`Tne eldsbox instruction will load one of the 16
`sbox arrays. It will load the amount of b~ in
`that table that is specified by the #bytes field. The
`only ~ mode allowed is memory indirect,
`thus the Pf!)gl'am will have to give the location of
`where the sbox array is stored in memory.
`
`cinitsbox #cl,#c2
`
`cs box < greg>
`
`cperms <lrcg>,'<rcg>
`
`cpcnnd <lreg>,<rcg>
`
`cand < rcgl >, < reg2 >
`
`cor <rcgl>,<rcg2>
`
`The einitsbox instruction will initialize the control
`for the sbox instruction. The #cl will be the
`number of bits inputed for each substitution in the
`sbox ~ation and #c2 will be the number of bits
`output for each substitution. These bits can have
`the values four, six and eight.
`
`The esbox instruction does a sbox array look.up
`with the < greg> and stores the result in the same
`register.
`
`The epenn instruction will do a permutation on a
`the destination < reg> with the large control regi.!1-
`ter <~>. Each oyte in the control r:egister will
`control where each bit in the destination <reg>
`will come from.
`
`The epenn instruction will do a permutation on a
`the destination < reg> with the large control reglll-:(cid:173)
`ter <lre2>. Each 6yte in the control revster will
`control the destination of corresponding "bit in the
`destination <reg>.
`
`The eand instruction will do a bitwise and on the
`two ~ given and stores the result in the des(cid:173)
`tination <reg2>.
`
`The eor instruction will do a bitwise or on the two
`registers given and stores the result in the destina(cid:173)
`tion <reg2>.
`
`Oracle-1037 p. 17
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`265
`
`exor <regl>,<reg2>
`
`The exor instruction will do a bitwise xor on the
`two registers given and stores the result in the des(cid:173)
`tination <reg2>.
`
`elshiftl #mnn of bits,<reg>
`ershiftl #num of bits, <reg> The elshiftl and ershiftl will do a left or right
`respectively logical shift on the register specified l>y
`the number of bits given.
`
`elshiftc #num of bits,<reg>
`ershiftc #num of bits,< reg> The elshiftc and ershiftc will do a left or r!gh!
`respectively circular shift on the register specified
`by the number of bits given.
`
`elshifta #num of bits,< reg>
`ershifta #num of bits,< reg> The elshifta and ershifta will do a left or r!ght
`respectively arithmetic shift on the register specified
`by the number of bits given.
`
`A