# A Vendor-Neutral Unified Core for Cryptographic Operations in GF(p) and GF(2m) Based on Montgomery Arithmetic

Authors: Martin Schramm; Reiner Dojen; Michael Heigl
Journal: Security and Communication Networks
 (2018)

---

## Abstract

In the emerging IoT ecosystem in which the internetworking will reach a totally new dimension the crucial role of efficient security solutions for embedded devices will be without controversy. Typically IoT-enabled devices are equipped with integrated circuits, such as ASICs or FPGAs to achieve highly specific tasks. Such devices must have cryptographic layers implemented and must be able to access cryptographic functions for encrypting/decrypting and signing/verifying data using various algorithms and generate true random numbers, random primes, and cryptographic keys. In the context of a limited amount of resources that typical IoT devices will exhibit, due to energy efficiency requirements, efficient hardware structures in terms of time, area, and power consumption must be deployed. In this paper, we describe a scalable word-based multivendor-capable cryptographic core, being able to perform arithmetic operations in prime and binary extension finite fields based on Montgomery Arithmetic. The functional range comprises the calculation of modular additions and subtractions, the determination of the Montgomery Parameters, and the execution of Montgomery Multiplications and Montgomery Exponentiations. A prototype implementation of the adaptable arithmetic core is detailed. Furthermore, the decomposition of cryptographic algorithms to be used together with the proposed core is stated and a performance analysis is given.


---

## Body

## 1. Introduction

The next generation of embedded systems and IoT devices will exhibit a much higher degree of internetworking which gives rise to security considerations [1]. As a logical consequence, such devices must become cryptographic nodes, besides others, being capable of encrypting/decrypting and signing/verifying data as well as establishing spontaneous secured communications by exchanging common secrets used for secret key calculation. While many embedded chips already have support for hardware-accelerated symmetric algorithms (mainly AES) [2] and hash functions, due to various reasons, such as complexity, space, and costs, they lack in hardware support especially for supporting a wide range of public-key and key exchange algorithms with different precision widths. Besides, many modern cryptographic primitives necessitate the capability for producing true random numbers and random prime numbers. Typical IoT devices furthermore very often only exhibit a limited amount of resources which requires efficient cryptographic hardware structures in terms of area, power consumption, and calculation performance [3]. In general enterprises developing IoT products basically have three options to include application functionalities in high integrated devices, using Application Specific Standard Products (ASSP), Application Specific Integrated Circuits (ASIC), or Field Programmable Gate Arrays (FPGA). Today FPGAs have become promising components for IoT applications [4], compared to ASSP solutions which often cannot provide the required functionality and can provide a better Total Cost of Ownership (TCO) compared to ASIC solutions. Thus for devices which are equipped with a FPGA device, it is valuable to examine how efficient hardware structures for performing cryptographic operations can be included.In matters of algorithm agility an arithmetic engine with minimal hardware footprint, which can handle the arithmetic operations of a great variety of cryptographic algorithms, is of great importance for IoT based devices. Especially the calculability of the individual operations leading to lower and upper calculation time bounds is quite important.This paper proposes a tiny-held vendor-neutral cryptographic arithmetic core exemplarily implemented in FPGA-logic. For efficiency, time-intensive modular operations, such as multiplication and exponentiation operations, Montgomery Arithmetic is used. Without the need of any expensive software precalculations the core is able to perform a high number of cryptographic algorithms and handle various key sizes by simply processing operation lists. Furthermore the core architecture is unified and can perform calculations in both prime finite fields (GF(p)) and binary extension fields (GF(2m)). To illustrate the versatility of the developed core, well-established cryptographic algorithms have been rewritten and fragmented into operation lists to be processed by the arithmetic engine.The paper is organized as follows. Section2 states the related work of this research. In Section 3 the design of the proposed Enhanced Montgomery Multiplication Core is stated; the specified functional range of the core is given in Section 4. In Section 5 some exemplary application descriptions for the core are mentioned and in Section 6 the results of the performance analysis are stated. Finally, Section 7 concludes the paper.


## 2. Related Works

The efficiency of cryptographic algorithms when implemented on reconfigurable hardware is mainly determined by the fact of how the underlying finite field arithmetic operations are realized [5]. Several applications in cryptography such as ciphering and deciphering of asymmetric algorithms, the creation and verification of digital signatures, and secure key exchange mechanisms require excessive use of the basic finite field modular arithmetic operations addition, multiplication, and the calculation of the multiplicative inverse. Especially the field multiplication operation is crucial to the efficiency of a design, since it is the core operation of many cryptographic algorithms [6].In [7] P. L. Montgomery introduced a representation of residue classes in order to speed up modular multiplications without affecting modular additions and subtractions. Over the years numerous designs have been proposed implementing modular multiplications based on Montgomery’s multiplication algorithm [8]. The foundation for these architectures was presented by A. Tenca and Ç. Koç in [9]. The architecture is based on a word-based Montgomery Multiplication algorithm for prime finite fields in which multiplications are performed in a bit-serial fashion. E. Savaş et al. in [10] have proposed an extension which, in addition to the standard integer modulo arithmetic, also allows polynomial computations over binary finite fields. An overview about algorithms and hardware architectures for Montgomery Multiplication can be found in [11]. Optimizations of the original design have been proposed concerning the hardware implementation of the Montgomery Multiplication algorithm [12] as well as by utilizing special arithmetic hardcore extensions of FPGAs to accelerate digital signal processing applications [13]. Some designs only focus on utilizing the Montgomery Multiplication method to accelerate modular exponentiation operations as required by the RSA algorithm [14, 15].However, no publication focuses on how the Montgomery Multiplication architecture can be embedded into a comprehensive solution. In this paper we propose an enhanced version of a bit-serial word-based unified Montgomery Multiplication core based on logic elements only which is controlled by a state machine and offers the functional range to be able to perform complete cryptographic algorithms without additional complex processing required in software.


## 3. Enhanced Montgomery Multiplication Core

### 3.1. Requirements

Today a high number of different public-key algorithms are in use. To ensure compatibility, cryptographic applications must support a large portion of those algorithms. While typical software implementations often can easily be upgraded in order to adapt new algorithms and larger key sizes, the same is not necessarily true for hardware implementations. Therefore following requirements have been identified for the Enhanced Montgomery Multiplication Core:(i)
Use of Montgomery Arithmetic. The design must be able to perform modulo operations in a time-efficient manner by using Montgomery Arithmetic. At least the core must support Montgomery Multiplications and Montgomery Exponentiations. Furthermore the core must support standard modulo additions and modulo subtractions.(ii)
Works on Both Finite FieldsGF(p)andGF(2m). The architecture must exhibit an unified structure supporting both standard integer modulo operations of prime finite fields as well as polynomial calculations of binary finite fields.(iii)
Montgomery Parameter Calculation. In general the Montgomery Parameters (r and r2) can be precomputed for previously known moduli. However, as a requirement the core must be able to handle arbitrary moduli. Therefore it must be capable of calculating the Montgomery Parameters rmodn, r2modn and r-1modn without the need of precalculations done in software.(iv)
Scalable Design. The architecture must be scalable in terms of timing, area, and power consumption. This includes the parametrisation of the word width, the internal storage size, and the amount of processing units within the pipeline.(v)
Multialgorithm Support. The core must be based on a building-block design. The functional range provided by the arithmetic unit should empower algorithm agility, by fragmenting cryptographic algorithms into a list of core operations. At least the core must be capable of performing RSA [16] operations, (safe) prime number generation and primality testing (MR) [17, 18], key exchange operations (DH) [19], and elliptic curve calculations (EC) [20] over both prime and binary finite fields.(vi)
Supporting as Many Precision Widths as Possible. The design must support a wide range of different precision widths determining the security level of the cryptographic algorithm. If a certain security level, due to increased attacking computing power, becomes inadequate, the precision width can be adjusted accordingly which makes the hardware less prone to become obsolete due to higher security demands. The core must support the current recommendations for minimum key sizes [21] and should also support larger key sizes. For RSA algorithm and Diffie-Hellman key exchange support the architecture should be able to handle precisions up to 4096 bit moduli, for elliptic curve cryptography support precisions up to 512 bits for prime finite fields and precisions up to 571 bits for binary finite fields should be possible.(vii)
Time-Invariant Operations. The architecture must be capable of performing its operations in a time-invariant manner. If security sensitive information, such as private keys, will be processed, it must be ensured that all operations exhibit the same execution time to prevent side-channel attacks based on timing analysis.


### 3.2. Overall Core Architecture

Figure1 illustrates the overall architecture of the proposed Enhanced Montgomery Multiplication Core which is capable of meeting all requirements as specified above.Figure 1
Overall architecture of the Enhanced Montgomery Multiplication Core.Besides the pipeline of processing units handling the main part of the word-based Montgomery Multiplication algorithm, the core features an enhanced word-based Carry Look-Ahead adder being responsible for the calculation of the final result after the pipeline has processed all bits of an operand as well as for performing single modular addition and subtraction operations. The register files of the original design have been replaced with an internal dual-ported RAM which holds the operands as well as intermediate results of the core operations. Furthermore a word-based comparator component has been described which is queried during operations to decide if a modular addition or subtraction step must be performed. Two additionalr-bit words for the A operand and the exponent E have been introduced with |r| being the RAM width (|r|=4·|w|) which will be fetched from RAM in case of Montgomery Multiplication and Montgomery Exponentiation operations. An auxiliary w-bit word aux is used for RAM reorganisation operations as well as for the calculation of the Montgomery Parameters r and r2.The intelligence of the core is the controlling state machine which utilizes the defined components to perform standard modular addition and subtraction operations, Montgomery Multiplications, Montgomery Exponentiations, Montgomery Parameter calculation, and RAM reorganisation operations. Therefore it is responsible for controlling the RAM write and read access, the source and destination address signals of RAM, as well as the values passed through to the first processing unit, to the CLA adder, and to the comparator component. Furthermore it controls the assignments ofA operand, E exponent, and aux words.The described core can be parametrised in three ways. The parameter namedMAX_PRECISION_WIDTH specifies the highest supported precision width |p|, whereas the parameterWORD_WIDTH is used to specify the word width |w| of the operands involved in the calculations. These two parameters determine the size and the address space of the internal core RAM. The third parameterMAX_NUM_PUS specifies the maximum number of processing units of the pipeline implemented for a specific core variation mainly affecting the performance and the size in terms of area consumption.


#### 3.2.1. Processing Units

The heart of the core is the pipeline of processing units implementing the multiple word version of the Montgomery Multiplication algorithm. Therefore the processing unit structure has been described from scratch. The processing unit can be held in reset and keeps track of the cycle number according to the number of words to be processed depending on the supplied parameters. This control logic is needed to determine whether the supplied modulus has to be added to the processed words in this cycle or not, depending on the value of the signalpar denoting an odd intermediate result. Note that buffering the output of a processing unit between two processing units is not required in this design. Compared to the original design presented in [10] for a given precision width |p| and a word size |w|, e=⌈|p|/|w|⌉+1 number of words are required for a unified solution and the pipeline must consist of a power of two (2x) number of processing units with a maximum number of 2x<(e-1) in order to avoid pipeline stalls. Figure 2 illustrates the internal architecture of an exemplary processing unit with word size |w|=4.Figure 2
Processing unit with word sizew=|4|.Each processing unit consists of a cascade of two layers of so-called Unified Full Adder (UFA) cells. The Unified Full Adder cells basically consist of simple full adder cells which have been enhanced by an additional finite field selection inputfsel. This allows for the creation of a unified multiplier architecture which can not only be used in prime fields GF(p) (fsel=1) but also in binary fields GF(2m) (fsel=0) in which additions will be simple bitwise XOR calculations without any carry output.


#### 3.2.2. Carry Look-Ahead Adder

Since the pipeline generates the result in carry save form, an additional step is necessary at the end of each calculation to obtain a nonredundant version of the result. For the sake of uniformity a circuit is required that can operate in both finite fieldsGF(p) and GF(2m). Furthermore, since the calculation in GF(p) could require one further subtraction step, the Carry Look-Ahead adder in the design has been formulated to be able to perform word-based modular additions and subtractions. Figure 3 illustrates the logic of the proposed enhanced n-bit wide CLA adder of the core.Figure 3
Enhanced n-bit wide CLA adder.The internal signalb′ of the second operand will be calculated as bi′=bi⊕(aos·fsel) in which aos denotes an add-or-subtract signal (aos=0 means addition, aos=1 represents subtraction by performing an addition in two’s complement representation). The modified CLA adder involves the same common Carry Look-Ahead adder logic for the calculation of the generate (gi=ai·bi′) and propagate (pi=ai+bi′) functions. The output values ci of the CLA adder logic will be calculated as c0=cin for the least-significant bit and ci=gi-1+(pi-1·ci-1) for all further bits. The final sum output bits si will be calculated as si=(ci·fsel)⊕ai⊕bi′ the carry output bit will be determined as cout=cn·fsel. If the selected finite field is GF(2m) (fsel=0), then the add-or-subtract input will be ignored, the final sum will simply be the bitwise modulo-2 addition of the two input values TC and TS and the carry output bit will be forced to zero.


#### 3.2.3. Core RAM Structure

The RAM of the core must be capable of holding all the necessary operands and intermediate values required during the execution of cryptographic algorithms. The basic structure of the described RAM is pictured in Figure4.Figure 4
Enhanced Montgomery Multiplication Core RAM organization.It features four symbolic horizontal RAM operand locations withMAX_PRECISION_WIDTH bit each which are organized as eight pieces ofMAX_PRECISION_WIDTH/8 bit each. The location named B is intended to hold operand B in Montgomery Multiplication and Montgomery Exponentiation operations; the location named P is intended to hold the modulus. The location TS usually holds the temporary sum value during Montgomery Multiplications and Montgomery Exponentiation or the first operand in modular addition or subtraction operations. The location TC usually holds the temporary carry stream during Montgomery Multiplications and Montgomery Exponentiation or the second operand in modular addition or subtraction operations.Besides the horizontal RAM operand locations three symbolic vertical RAM operand locations withMAX_PRECISION_WIDTH bit each have been defined which are organized as eight pieces ofMAX_PRECISION_WIDTH/8 bit each. The locations named A, E, and X for convenience usually are used to hold operand A in Montgomery Multiplication and Montgomery Exponentiation operations as well as the exponent operand E and the auxiliary operand X in Montgomery Exponentiation operations. In addition all RAM slots are intended to hold intermediate values during the execution of cryptographic algorithms.


## 3.1. Requirements

Today a high number of different public-key algorithms are in use. To ensure compatibility, cryptographic applications must support a large portion of those algorithms. While typical software implementations often can easily be upgraded in order to adapt new algorithms and larger key sizes, the same is not necessarily true for hardware implementations. Therefore following requirements have been identified for the Enhanced Montgomery Multiplication Core:(i)
Use of Montgomery Arithmetic. The design must be able to perform modulo operations in a time-efficient manner by using Montgomery Arithmetic. At least the core must support Montgomery Multiplications and Montgomery Exponentiations. Furthermore the core must support standard modulo additions and modulo subtractions.(ii)
Works on Both Finite FieldsGF(p)andGF(2m). The architecture must exhibit an unified structure supporting both standard integer modulo operations of prime finite fields as well as polynomial calculations of binary finite fields.(iii)
Montgomery Parameter Calculation. In general the Montgomery Parameters (r and r2) can be precomputed for previously known moduli. However, as a requirement the core must be able to handle arbitrary moduli. Therefore it must be capable of calculating the Montgomery Parameters rmodn, r2modn and r-1modn without the need of precalculations done in software.(iv)
Scalable Design. The architecture must be scalable in terms of timing, area, and power consumption. This includes the parametrisation of the word width, the internal storage size, and the amount of processing units within the pipeline.(v)
Multialgorithm Support. The core must be based on a building-block design. The functional range provided by the arithmetic unit should empower algorithm agility, by fragmenting cryptographic algorithms into a list of core operations. At least the core must be capable of performing RSA [16] operations, (safe) prime number generation and primality testing (MR) [17, 18], key exchange operations (DH) [19], and elliptic curve calculations (EC) [20] over both prime and binary finite fields.(vi)
Supporting as Many Precision Widths as Possible. The design must support a wide range of different precision widths determining the security level of the cryptographic algorithm. If a certain security level, due to increased attacking computing power, becomes inadequate, the precision width can be adjusted accordingly which makes the hardware less prone to become obsolete due to higher security demands. The core must support the current recommendations for minimum key sizes [21] and should also support larger key sizes. For RSA algorithm and Diffie-Hellman key exchange support the architecture should be able to handle precisions up to 4096 bit moduli, for elliptic curve cryptography support precisions up to 512 bits for prime finite fields and precisions up to 571 bits for binary finite fields should be possible.(vii)
Time-Invariant Operations. The architecture must be capable of performing its operations in a time-invariant manner. If security sensitive information, such as private keys, will be processed, it must be ensured that all operations exhibit the same execution time to prevent side-channel attacks based on timing analysis.


## 3.2. Overall Core Architecture

Figure1 illustrates the overall architecture of the proposed Enhanced Montgomery Multiplication Core which is capable of meeting all requirements as specified above.Figure 1
Overall architecture of the Enhanced Montgomery Multiplication Core.Besides the pipeline of processing units handling the main part of the word-based Montgomery Multiplication algorithm, the core features an enhanced word-based Carry Look-Ahead adder being responsible for the calculation of the final result after the pipeline has processed all bits of an operand as well as for performing single modular addition and subtraction operations. The register files of the original design have been replaced with an internal dual-ported RAM which holds the operands as well as intermediate results of the core operations. Furthermore a word-based comparator component has been described which is queried during operations to decide if a modular addition or subtraction step must be performed. Two additionalr-bit words for the A operand and the exponent E have been introduced with |r| being the RAM width (|r|=4·|w|) which will be fetched from RAM in case of Montgomery Multiplication and Montgomery Exponentiation operations. An auxiliary w-bit word aux is used for RAM reorganisation operations as well as for the calculation of the Montgomery Parameters r and r2.The intelligence of the core is the controlling state machine which utilizes the defined components to perform standard modular addition and subtraction operations, Montgomery Multiplications, Montgomery Exponentiations, Montgomery Parameter calculation, and RAM reorganisation operations. Therefore it is responsible for controlling the RAM write and read access, the source and destination address signals of RAM, as well as the values passed through to the first processing unit, to the CLA adder, and to the comparator component. Furthermore it controls the assignments ofA operand, E exponent, and aux words.The described core can be parametrised in three ways. The parameter namedMAX_PRECISION_WIDTH specifies the highest supported precision width |p|, whereas the parameterWORD_WIDTH is used to specify the word width |w| of the operands involved in the calculations. These two parameters determine the size and the address space of the internal core RAM. The third parameterMAX_NUM_PUS specifies the maximum number of processing units of the pipeline implemented for a specific core variation mainly affecting the performance and the size in terms of area consumption.


### 3.2.1. Processing Units

The heart of the core is the pipeline of processing units implementing the multiple word version of the Montgomery Multiplication algorithm. Therefore the processing unit structure has been described from scratch. The processing unit can be held in reset and keeps track of the cycle number according to the number of words to be processed depending on the supplied parameters. This control logic is needed to determine whether the supplied modulus has to be added to the processed words in this cycle or not, depending on the value of the signalpar denoting an odd intermediate result. Note that buffering the output of a processing unit between two processing units is not required in this design. Compared to the original design presented in [10] for a given precision width |p| and a word size |w|, e=⌈|p|/|w|⌉+1 number of words are required for a unified solution and the pipeline must consist of a power of two (2x) number of processing units with a maximum number of 2x<(e-1) in order to avoid pipeline stalls. Figure 2 illustrates the internal architecture of an exemplary processing unit with word size |w|=4.Figure 2
Processing unit with word sizew=|4|.Each processing unit consists of a cascade of two layers of so-called Unified Full Adder (UFA) cells. The Unified Full Adder cells basically consist of simple full adder cells which have been enhanced by an additional finite field selection inputfsel. This allows for the creation of a unified multiplier architecture which can not only be used in prime fields GF(p) (fsel=1) but also in binary fields GF(2m) (fsel=0) in which additions will be simple bitwise XOR calculations without any carry output.


### 3.2.2. Carry Look-Ahead Adder

Since the pipeline generates the result in carry save form, an additional step is necessary at the end of each calculation to obtain a nonredundant version of the result. For the sake of uniformity a circuit is required that can operate in both finite fieldsGF(p) and GF(2m). Furthermore, since the calculation in GF(p) could require one further subtraction step, the Carry Look-Ahead adder in the design has been formulated to be able to perform word-based modular additions and subtractions. Figure 3 illustrates the logic of the proposed enhanced n-bit wide CLA adder of the core.Figure 3
Enhanced n-bit wide CLA adder.The internal signalb′ of the second operand will be calculated as bi′=bi⊕(aos·fsel) in which aos denotes an add-or-subtract signal (aos=0 means addition, aos=1 represents subtraction by performing an addition in two’s complement representation). The modified CLA adder involves the same common Carry Look-Ahead adder logic for the calculation of the generate (gi=ai·bi′) and propagate (pi=ai+bi′) functions. The output values ci of the CLA adder logic will be calculated as c0=cin for the least-significant bit and ci=gi-1+(pi-1·ci-1) for all further bits. The final sum output bits si will be calculated as si=(ci·fsel)⊕ai⊕bi′ the carry output bit will be determined as cout=cn·fsel. If the selected finite field is GF(2m) (fsel=0), then the add-or-subtract input will be ignored, the final sum will simply be the bitwise modulo-2 addition of the two input values TC and TS and the carry output bit will be forced to zero.


### 3.2.3. Core RAM Structure

The RAM of the core must be capable of holding all the necessary operands and intermediate values required during the execution of cryptographic algorithms. The basic structure of the described RAM is pictured in Figure4.Figure 4
Enhanced Montgomery Multiplication Core RAM organization.It features four symbolic horizontal RAM operand locations withMAX_PRECISION_WIDTH bit each which are organized as eight pieces ofMAX_PRECISION_WIDTH/8 bit each. The location named B is intended to hold operand B in Montgomery Multiplication and Montgomery Exponentiation operations; the location named P is intended to hold the modulus. The location TS usually holds the temporary sum value during Montgomery Multiplications and Montgomery Exponentiation or the first operand in modular addition or subtraction operations. The location TC usually holds the temporary carry stream during Montgomery Multiplications and Montgomery Exponentiation or the second operand in modular addition or subtraction operations.Besides the horizontal RAM operand locations three symbolic vertical RAM operand locations withMAX_PRECISION_WIDTH bit each have been defined which are organized as eight pieces ofMAX_PRECISION_WIDTH/8 bit each. The locations named A, E, and X for convenience usually are used to hold operand A in Montgomery Multiplication and Montgomery Exponentiation operations as well as the exponent operand E and the auxiliary operand X in Montgomery Exponentiation operations. In addition all RAM slots are intended to hold intermediate values during the execution of cryptographic algorithms.


## 3.2.1. Processing Units

The heart of the core is the pipeline of processing units implementing the multiple word version of the Montgomery Multiplication algorithm. Therefore the processing unit structure has been described from scratch. The processing unit can be held in reset and keeps track of the cycle number according to the number of words to be processed depending on the supplied parameters. This control logic is needed to determine whether the supplied modulus has to be added to the processed words in this cycle or not, depending on the value of the signalpar denoting an odd intermediate result. Note that buffering the output of a processing unit between two processing units is not required in this design. Compared to the original design presented in [10] for a given precision width |p| and a word size |w|, e=⌈|p|/|w|⌉+1 number of words are required for a unified solution and the pipeline must consist of a power of two (2x) number of processing units with a maximum number of 2x<(e-1) in order to avoid pipeline stalls. Figure 2 illustrates the internal architecture of an exemplary processing unit with word size |w|=4.Figure 2
Processing unit with word sizew=|4|.Each processing unit consists of a cascade of two layers of so-called Unified Full Adder (UFA) cells. The Unified Full Adder cells basically consist of simple full adder cells which have been enhanced by an additional finite field selection inputfsel. This allows for the creation of a unified multiplier architecture which can not only be used in prime fields GF(p) (fsel=1) but also in binary fields GF(2m) (fsel=0) in which additions will be simple bitwise XOR calculations without any carry output.


## 3.2.2. Carry Look-Ahead Adder

Since the pipeline generates the result in carry save form, an additional step is necessary at the end of each calculation to obtain a nonredundant version of the result. For the sake of uniformity a circuit is required that can operate in both finite fieldsGF(p) and GF(2m). Furthermore, since the calculation in GF(p) could require one further subtraction step, the Carry Look-Ahead adder in the design has been formulated to be able to perform word-based modular additions and subtractions. Figure 3 illustrates the logic of the proposed enhanced n-bit wide CLA adder of the core.Figure 3
Enhanced n-bit wide CLA adder.The internal signalb′ of the second operand will be calculated as bi′=bi⊕(aos·fsel) in which aos denotes an add-or-subtract signal (aos=0 means addition, aos=1 represents subtraction by performing an addition in two’s complement representation). The modified CLA adder involves the same common Carry Look-Ahead adder logic for the calculation of the generate (gi=ai·bi′) and propagate (pi=ai+bi′) functions. The output values ci of the CLA adder logic will be calculated as c0=cin for the least-significant bit and ci=gi-1+(pi-1·ci-1) for all further bits. The final sum output bits si will be calculated as si=(ci·fsel)⊕ai⊕bi′ the carry output bit will be determined as cout=cn·fsel. If the selected finite field is GF(2m) (fsel=0), then the add-or-subtract input will be ignored, the final sum will simply be the bitwise modulo-2 addition of the two input values TC and TS and the carry output bit will be forced to zero.


## 3.2.3. Core RAM Structure

The RAM of the core must be capable of holding all the necessary operands and intermediate values required during the execution of cryptographic algorithms. The basic structure of the described RAM is pictured in Figure4.Figure 4
Enhanced Montgomery Multiplication Core RAM organization.It features four symbolic horizontal RAM operand locations withMAX_PRECISION_WIDTH bit each which are organized as eight pieces ofMAX_PRECISION_WIDTH/8 bit each. The location named B is intended to hold operand B in Montgomery Multiplication and Montgomery Exponentiation operations; the location named P is intended to hold the modulus. The location TS usually holds the temporary sum value during Montgomery Multiplications and Montgomery Exponentiation or the first operand in modular addition or subtraction operations. The location TC usually holds the temporary carry stream during Montgomery Multiplications and Montgomery Exponentiation or the second operand in modular addition or subtraction operations.Besides the horizontal RAM operand locations three symbolic vertical RAM operand locations withMAX_PRECISION_WIDTH bit each have been defined which are organized as eight pieces ofMAX_PRECISION_WIDTH/8 bit each. The locations named A, E, and X for convenience usually are used to hold operand A in Montgomery Multiplication and Montgomery Exponentiation operations as well as the exponent operand E and the auxiliary operand X in Montgomery Exponentiation operations. In addition all RAM slots are intended to hold intermediate values during the execution of cryptographic algorithms.


## 4. Functional Range of the Core

This section provides a description of the functional range of the proposed core. The following precisions (denoted in bit-length) are supported:(i)
EC overGF(p), RSA, MR, DH: 192, 224, 256, 320, 384, 448, 512, 768, 1024, 1536, 2048, 3072, 4096(ii)
EC overGF(2m): 131, 163, 176, 191, 193, 208, 233, 239, 272, 283, 304, 359, 368, 409, 431, 571If further or other precision widths should be supported, the described core can easily be adjusted in an appropriate manner. For the parametrisation and the execution/abortion of an operation a32-bit wide command input word has been defined. Besides the start, abort, and finite field selection signals also the encoded precision width, operation code as well as RAM offsets for the specified operation can be supplied. The following operations have been specified.


### 4.1. MontMult Operation

TheMontMult operation code instructs the core to perform a single Montgomery Multiplication with the supplied elements in the given finite field. A Montgomery Multiplication will start by reading the first r-bit word of operand A from RAM. Afterwards the pipeline will be started and the appropriate bits of A operand will be fed to the individual processing unit. If all bits of the A operand word have been fed to the processing units, a new word will be read from RAM. Once the last bit of A operand has been processed, the temporary sum and temporary carry words will be fed into the CLA adder in order to reunite the two streams. After the last words of temporary sum and temporary carry have been brought together, the carry output bit of the CLA adder will be evaluated. If a carry bit is set the modulus will be subtracted once; otherwise the result will be compared to the given modulus. If the result is equal or greater than the modulus the given modulus will be subtracted once.


### 4.2. MontR Operation

TheMontR operation code instructs the core to calculate the Montgomery Parameter r=2k regarding a supplied modulus in the given finite field, with k being the bit-length of the given precision.In the case of prime field arithmetic the Montgomery Parameterr will be r≡2kmodp, so r can be calculated as two’s complement of p as bitwise inverse of the given modulus plus 1. Therefore the individual words of the modulus will be XOR-ed with a constant word consisting of all-ones. In addition the least-significant bit of the first word will be set to one.In the case of binary field arithmetic the Montgomery Parameterr will be r≡2kmodn(x), so r is equal to binary expression of the irreducible polynomial n(x) with the most significant bit set to zero. Therefore the individual words of the modulus will be scanned and the appropriate most significant bit will be set to zero, depending on the given precision.


### 4.3. MontR2 Operation

TheMontR2 operation code instructs the core to calculate the Montgomery Parameter r2 with r2=22·k for a supplied modulus in the given finite field with k being the bit-length of the given precision.In the case of prime field arithmetic the Montgomery Parameterr2 will be given by r2≡r·r≡2k·2k≡22·kmodp. Therefore in a first step the Montgomery Parameter r≡2kmodp will be calculated for prime fields as described above. In order to calculate r2 one possible way is to calculate 2l·2kmodp with l being a small divider of k. In the given implementation l=1. Therefore the bits of r will be shifted to the left by one bit. If the result is equal or greater than the modulus, p will be subtracted once. By using a square-and-multiply-like algorithm, multiple Montgomery Multiplications will be performed in order to calculate r2≡2k·2kmodp.In the case of binary field arithmetic the Montgomery Parameterr2 will be given by r2≡r·r≡2k·2k≡22·kmodn(x). Therefore in a first step the Montgomery Parameter r≡2kmodn(x) will be calculated for binary fields as described above. In order to calculate r2 the resulting parameter r will be shifted k-times bitwise to the left. After each shift, the most significant bit as given by the precision parameter will be evaluated. If the bit is one, the irreducible polynomial will be added to the intermediate result which represents a modulo reduction with n(x). Once the shift has been performed k-times the result will be r2≡2k·2kmodn(x)


### 4.4. MontExp Operation

TheMontExp operation code instructs the core to perform a Montgomery Exponentiation consisting of multiple Montgomery Multiplication steps in the given finite field. A Montgomery Exponentiation will start by reading the first r-bit word of exponent E from RAM. Afterwards the first appearing one of the exponent word will be searched starting from the most significant bit. If the first word consists of all-zeros then the next word of exponent E will be read and evaluated. Once the highest bit of exponent E has been found, multiple Montgomery Multiplications will be performed until all bits of the exponent have been processed following a square-and-multiply algorithm.


### 4.5. ModAdd Operation

TheModAdd operation code instructs the core to perform a modular addition of the supplied elements in the given finite field. After preparing the core for the addition operation, the CLA adder will add the given operands using the appropriate arithmetic given by the finite field selection input. Once the last words of the given operands have been added the carry output bit of the CLA adder will be evaluated. If a carry bit is set, the modulus will be subtracted once; otherwise the result will be compared to the given modulus. If the result is equal to or greater than the modulus, it will also be subtracted once.


### 4.6. ModSub Operation

TheModSub operation code instructs the core to perform a modular subtraction of the supplied elements in prime fields. After preparing the core for the subtraction operation the CLA adder will be used to perform a word-based subtraction by performing an addition in two’s complement representation with prime field arithmetic. After the last words of the given operands have been processed, the carry output bit of the CLA adder will be evaluated. If the carry bit signals a negative result, the modulus will be added once; otherwise the result will be compared to the given modulus. If the result is equal to or greater than the modulus, it will be subtracted once.


### 4.7. RAM Copy Operations

In order to support cryptographic algorithms which have been disassembled into a list of instructions, RAM copy operations are needed. According to the proposed RAM layout stated above four individual copy operations have been defined.TheCopyH2V operation code instructs the core to copy a number of words, according to the supplied precision parameter, from the horizontal RAM layout starting from the given source address to the vertical RAM layout starting from the given destination address.TheCopyV2V operation code instructs the core to copy a number of words, according to the supplied precision parameter, from the vertical RAM layout starting from the given source address to the vertical RAM layout starting from the given destination address.TheCopyH2H operation code instructs the core to copy a number of words, according to the supplied precision parameter, from the horizontal RAM layout starting from the given source address to the horizontal RAM layout starting from the given destination address.TheCopyV2H operation code instructs the core to copy a number of words, according to the supplied precision parameter, from the vertical RAM layout starting from the given source address to the horizontal RAM layout starting from the given destination address.


### 4.8. MontMult1 Operation

TheMontMult1 operation code instructs the core to perform a single Montgomery Multiplication of the supplied element with the constant 1 in the given finite field. This type of operation is needed when a montgomerized value should be transformed back from the Montgomery Domain and has been implemented as an independent operation since an operand A=1 will unnecessarily occupy a vertical RAM slot. A Montgomery Multiplication with the constant 1 will be executed in an analogous manner as theMontMult operation with the only exception that, instead of the RAM words, constant words will be used for the A operand.


## 4.1. MontMult Operation

TheMontMult operation code instructs the core to perform a single Montgomery Multiplication with the supplied elements in the given finite field. A Montgomery Multiplication will start by reading the first r-bit word of operand A from RAM. Afterwards the pipeline will be started and the appropriate bits of A operand will be fed to the individual processing unit. If all bits of the A operand word have been fed to the processing units, a new word will be read from RAM. Once the last bit of A operand has been processed, the temporary sum and temporary carry words will be fed into the CLA adder in order to reunite the two streams. After the last words of temporary sum and temporary carry have been brought together, the carry output bit of the CLA adder will be evaluated. If a carry bit is set the modulus will be subtracted once; otherwise the result will be compared to the given modulus. If the result is equal or greater than the modulus the given modulus will be subtracted once.


## 4.2. MontR Operation

TheMontR operation code instructs the core to calculate the Montgomery Parameter r=2k regarding a supplied modulus in the given finite field, with k being the bit-length of the given precision.In the case of prime field arithmetic the Montgomery Parameterr will be r≡2kmodp, so r can be calculated as two’s complement of p as bitwise inverse of the given modulus plus 1. Therefore the individual words of the modulus will be XOR-ed with a constant word consisting of all-ones. In addition the least-significant bit of the first word will be set to one.In the case of binary field arithmetic the Montgomery Parameterr will be r≡2kmodn(x), so r is equal to binary expression of the irreducible polynomial n(x) with the most significant bit set to zero. Therefore the individual words of the modulus will be scanned and the appropriate most significant bit will be set to zero, depending on the given precision.


## 4.3. MontR2 Operation

TheMontR2 operation code instructs the core to calculate the Montgomery Parameter r2 with r2=22·k for a supplied modulus in the given finite field with k being the bit-length of the given precision.In the case of prime field arithmetic the Montgomery Parameterr2 will be given by r2≡r·r≡2k·2k≡22·kmodp. Therefore in a first step the Montgomery Parameter r≡2kmodp will be calculated for prime fields as described above. In order to calculate r2 one possible way is to calculate 2l·2kmodp with l being a small divider of k. In the given implementation l=1. Therefore the bits of r will be shifted to the left by one bit. If the result is equal or greater than the modulus, p will be subtracted once. By using a square-and-multiply-like algorithm, multiple Montgomery Multiplications will be performed in order to calculate r2≡2k·2kmodp.In the case of binary field arithmetic the Montgomery Parameterr2 will be given by r2≡r·r≡2k·2k≡22·kmodn(x). Therefore in a first step the Montgomery Parameter r≡2kmodn(x) will be calculated for binary fields as described above. In order to calculate r2 the resulting parameter r will be shifted k-times bitwise to the left. After each shift, the most significant bit as given by the precision parameter will be evaluated. If the bit is one, the irreducible polynomial will be added to the intermediate result which represents a modulo reduction with n(x). Once the shift has been performed k-times the result will be r2≡2k·2kmodn(x)


## 4.4. MontExp Operation

TheMontExp operation code instructs the core to perform a Montgomery Exponentiation consisting of multiple Montgomery Multiplication steps in the given finite field. A Montgomery Exponentiation will start by reading the first r-bit word of exponent E from RAM. Afterwards the first appearing one of the exponent word will be searched starting from the most significant bit. If the first word consists of all-zeros then the next word of exponent E will be read and evaluated. Once the highest bit of exponent E has been found, multiple Montgomery Multiplications will be performed until all bits of the exponent have been processed following a square-and-multiply algorithm.


## 4.5. ModAdd Operation

TheModAdd operation code instructs the core to perform a modular addition of the supplied elements in the given finite field. After preparing the core for the addition operation, the CLA adder will add the given operands using the appropriate arithmetic given by the finite field selection input. Once the last words of the given operands have been added the carry output bit of the CLA adder will be evaluated. If a carry bit is set, the modulus will be subtracted once; otherwise the result will be compared to the given modulus. If the result is equal to or greater than the modulus, it will also be subtracted once.


## 4.6. ModSub Operation

TheModSub operation code instructs the core to perform a modular subtraction of the supplied elements in prime fields. After preparing the core for the subtraction operation the CLA adder will be used to perform a word-based subtraction by performing an addition in two’s complement representation with prime field arithmetic. After the last words of the given operands have been processed, the carry output bit of the CLA adder will be evaluated. If the carry bit signals a negative result, the modulus will be added once; otherwise the result will be compared to the given modulus. If the result is equal to or greater than the modulus, it will be subtracted once.


## 4.7. RAM Copy Operations

In order to support cryptographic algorithms which have been disassembled into a list of instructions, RAM copy operations are needed. According to the proposed RAM layout stated above four individual copy operations have been defined.TheCopyH2V operation code instructs the core to copy a number of words, according to the supplied precision parameter, from the horizontal RAM layout starting from the given source address to the vertical RAM layout starting from the given destination address.TheCopyV2V operation code instructs the core to copy a number of words, according to the supplied precision parameter, from the vertical RAM layout starting from the given source address to the vertical RAM layout starting from the given destination address.TheCopyH2H operation code instructs the core to copy a number of words, according to the supplied precision parameter, from the horizontal RAM layout starting from the given source address to the horizontal RAM layout starting from the given destination address.TheCopyV2H operation code instructs the core to copy a number of words, according to the supplied precision parameter, from the vertical RAM layout starting from the given source address to the horizontal RAM layout starting from the given destination address.


## 4.8. MontMult1 Operation

TheMontMult1 operation code instructs the core to perform a single Montgomery Multiplication of the supplied element with the constant 1 in the given finite field. This type of operation is needed when a montgomerized value should be transformed back from the Montgomery Domain and has been implemented as an independent operation since an operand A=1 will unnecessarily occupy a vertical RAM slot. A Montgomery Multiplication with the constant 1 will be executed in an analogous manner as theMontMult operation with the only exception that, instead of the RAM words, constant words will be used for the A operand.


## 5. Exemplary Core Application Descriptions

This section gives exemplary descriptions of how the specified functional range of the proposed building-block Enhanced Montgomery Multiplication Core design can be utilized to support a wide range of cryptographic algorithms demanding the least possible memory capacity yet at the same time supporting as much precision widths as possible. Information is given of how to perform Chinese Remainder Theorem [22] (CRT) accelerated RSA private key operations and how to use the core in order to test/generate prime numbers.For the support of elliptic curve cryptography over prime and binary finite fields modular functions are given for preparing and conducting point operations for arbitrary elliptic curves for the supported precision widths. For all these algorithms a list of operations and the quantity of different operations is given allowing to perform cryptographic algorithms by simply processing these operation lists.


### 5.1. CRT-Accelerated RSA Operation

In order to speed up RSA private key operations the CRT-accelerated version is also supported by the core. Therefore some operations have to be performed with full precision whereas most of the operations have to be performed with half precision. Algorithm1 lists the necessary steps to utilize the core for CRT-accelerated RSA private key operations.Algorithm 1:CRT-RSA private key operation.
Requires: (c, d, p, q, exp1, exp2, coeff, n) Calculates: (m)  (h)  r q 2 = M o n t R 2 ( q ); (f)  c q = M o n t M u l t ( r q 2 , c , q ); (h)  c q M D = M o n t M u l t r q 2 , c q , q; (h)  m q M D = M o n t E x p ( c q M D , c q M D , e x p 2 , c q M D , q ); (h)  m q = M o n t M u l t 1 ( m q M D , q ); (h)  r p 2 = M o n t R 2 ( p ); (f)  c p = M o n t M u l t ( r p 2 , c , p ); (h)  c p M D = M o n t M u l t ( r p 2 , c p , p ); (h)  m p M D = M o n t E x p ( c p M D , c p M D , e x p 1 , c p M D , p ); (h)  m p = M o n t M u l t 1 ( m p M D , p ); (h)  c o e f f M D = M o n t M u l t ( r p 2 , c p , p ); (h)  t 1 = M o d S u b ( m p , m q , p ); (h)  t 2 = M o n t M u l t c o e f f M D , t 1 , p; (f)  r 2 = M o n t R 2 ( n ); (f)  q M D = M o n t M u l t ( q , r 2 , n ); (f)  t 3 = M o n t M u l t ( t 2 , q M D , n ); (f)  m = M o d A d d ( t 3 , m q , n ); Provides: (m)Table1 illustrates the abstract operations lists of the core for CRT-accelerated RSA application using the private key portion for all supported precision widths (512, 768, 1024, 1536, 2048, 3072, 4096). The number given in the index of the RAM locations denotes the offset given by the corresponding src_addr, dest_addr, src_addr_e, src_addr_x input signals. The width of the processed values depends on the supplied mwmac_precision input signal which depends on the operation. In the table operations requiring full precision (the precision of the RSA modulus) are marked by (f), operations requiring half precision are marked by (h). The mwmac_f_sel signal must be set to GF(p) arithmetic.Table 1
Core operations list CRT-RSA.
Step Nr. Precision Operation 1 - Clear RAM  2 - Writeq↦P1,  exp⁡1↦E1, exp⁡2↦E5, coeff↦X1, p↦X5  3 ( h ) M o n t R 2 ( P 1 , A 1 )  4 ( h ) C o p y H 2 V ( B 1 , A 1 )  5 - Writec↦B1  6 ( f ) M o n t M u l t ( A 1 , B 1 , P 1 )  7 ( h ) M o n t M u l t ( A 1 , B 1 , P 1 )  8-9 ( h ) C o p y H 2 V ( B 1 , A 1 ), CopyV2V(A1,A5)  10 ( h ) M o n t E x p ( A 5 , B 1 , E 5 , A 1 , P 1 )  11 ( h ) M o n t M u l t 1 ( B 1 , P 1 )  12 - 14 ( h ) C o p y H 2 V ( P 1 , E 5 ), CopyV2H(X5,P1), CopyH2V(B1,X5)  15 ( h ) M o n t R 2 ( P 1 , A 1 )  16 ( f ) C o p y H 2 V ( B 1 , A 1 )  17 ( h ) C o p y V 2 H ( X 1 , B 1 )  18 ( h ) M o n t M u l t ( A 1 , B 1 , P 1 )  19 ( h ) C o p y H 2 V ( B 1 , X 1 )  20 - Writec↦B1  21 ( f ) M o n t M u l t ( A 1 , B 1 , P 1 )  22 ( h ) M o n t M u l t ( A 1 , B 1 , P 1 )  23 - 24 ( h ) C o p y H 2 V ( B 1 , A 1 ), CopyV2V(A1,A5)  25 ( h ) M o n t E x p ( A 5 , B 1 , E 1 , A 1 , P 1 )  26 ( h ) M o n t M u l t 1 ( B 1 , P 1 )  27 - 28 ( h ) C o p y H 2 H ( B 1 , T S 1 ), CopyV2H(X5,TC1)  29 ( h ) M o d S u b ( T S 1 , T C 1 , P 1 )  30 ( h ) M o n t M u l t ( X 1 , B 1 , P 1 )  31 - 32 ( h ) C o p y H 2 V ( B 1 , A 1 ), CopyH2V(TS1,X1)  33 - Writen↦P1  34 ( f ) M o n t R 2 ( P 1 , A 5 )  35 ( h ) C o p y V 2 V ( X 1 , A 5 )  36 ( f ) M o n t M u l t ( E 5 , B 1 , P 1 )  37 ( f ) M o n t M u l t ( A 1 , B 1 , P 1 )  38 ( f ) C o p y H 2 H ( B 1 , T S 1 )  39 ( h ) C o p y V 2 H ( X 5 , T C 1 )  40 ( f ) M o d A d d ( T S 1 , T C 1 , P 1 )CRT-accelerated RSA private key operations require2×MontR2, 4×MontMult, 2×MontMult1, 2×MontExp, 1×ModSub, 9×CopyH2V, 4×CopyV2H, 2×CopyV2V and 1×CopyH2H performed on half precision and 1×MontR2, 4×MontMult, 1×ModAdd, 1×CopyH2V and 1×CopyH2H performed on full precision.


### 5.2. Prime Generation/Testing Operation

Algorithm2 lists the necessary steps to utilize the core, in conjunction with a TRNG generator as Miller-Rabin Primality Tester. In the algorithm n denotes the random integer to be tested for primality and k denotes the confidence parameter determining the accuracy of the test, i.e., the amount of Miller-Rabin loops. In a precomputation step the parameters s and d with 2s·d=(n-1) must be calculated which can be done by simple shift operations and counter increments in software. The test furthermore requires an amount of random integers {a1,…,ak} serving as random bases.Algorithm 2:Modified Miller-Rabin Primality Test.
Precomputation: (s, d with 2s⋅d=(n-1)) Input: (n, s, d, k  {a1,…,ak}) Output: (eval, composite or probably prime)  r = M o n t R ( n ); ( n - r ) = M o d S u b ( n , r , n ); for  i   from 1 to  k  do t 1 M D = M o n t E x p ( a i , a i , d , a i , n ); t 2 M D = M o d S u b ( t 1 M D , r , n ); t 3 M D = M o d S u b ( t 1 M D , ( n - r ) , n ); if  t2MD=0  or  t3MD=0  then continue; for j   from  0  to  (s-1)  do t 1 M D = M o n t M u l t ( t 1 M D , t 1 M D , n ); t 2 M D = M o d S u b ( t 1 M D , r , n ); if  t2MD=0  then return (eval= composite); t 3 M D = M o d S u b t 1 M D , n - r , n; if  t3MD=0  then continue; return (eval= composite); return (eval= probably prime)Table2 illustrates the operations list of utilizing the core for Miller-Rabin Primality Test steps for all supported precision widths (192, 224, 256, 320, 384, 512, 768, 1024, 1536, 2048, 3072, 4096). The number given in the index of the RAM locations denotes the offset given by the corresponding src_addr, dest_addr, src_addr_e, src_addr_x input signals. The width of the processed values depends on the supplied mwmac_precision input signal. The mwmac_f_sel signal must be set to GF(p) arithmetic. Note that since the results of the performed operations will be in the Montgomery Domain, they will be checked against the Montgomery Parameter r and (n-r) instead of 1 and (n-1). Also note that the random bases ai that will be checked must not necessarily be transformed into the Montgomery Domain first, they simply will be interpreted as random montgomerized values.Table 2
Core operations list for Miller-Rabin Primality Test.
Step Nr. Operation 1 Clear RAM  2 Writen↦P1, d↦E1  3 Writea↦X1  4-5 C o p y V 2 V ( X 1 , A 1 ),  CopyV2H(X1,B1)  6 M o n t E x p ( X 1 , B 1 , E 1 , A 1 , P 1 )  7 C o p y H 2 V ( B 1 , X 1 )  8 M o n t R ( P 1 , B 1 )  9-11 C o p y H 2 V ( B 1 , A 1 ),  CopyV2H(X1,TS1),  CopyH2H(B1,TC1)  12 M o d S u b ( T S 1 , T C 1 , P 1 )  13 ReadB1, if t2MD=0 continue at Step Nr. 3 else continue at Step Nr. 14  14-15 C o p y H 2 H ( P 1 , T S 1 ),  CopyV2H(A1,TC1)  16 M o d S u b ( T S 1 , T C 1 , P 1 )  17-18 C o p y V 2 H X 1 , T S 1,  CopyH2H(B1,TC1)  19 ModSub(TS1,TC1,P1)  20 ReadB1, if t3MD=0 continue at Step Nr. 3 else if (s-1)=0 stop test with eval= composite else continue at Step Nr. 21  21 C o p y V 2 H ( X 1 , B 1 )  22 M o n t M u l t ( X 1 , B 1 , P 1 )  23-25 C o p y H 2 V B 1 , X 1,  CopyH2H(B1,TS1),  CopyV2H(A1,TC1)  26 M o d S u b ( T S 1 , T C 1 , P 1 )  27 ReadB1, if t2MD=0 stop test with eval= composite else continue at Step Nr. 28  28-29 C o p y H 2 H ( P 1 , T S 1 ),  CopyV2H(A1,TC1)  30 M o d S u b ( T S 1 , T C 1 , P 1 )  31-32 C o p y V 2 H X 1 , T S 1,  CopyH2H(B1,TC1)  33 M o d S u b ( T S 1 , T C 1 , P 1 )  34 ReadB1, if t3MD=0 and i=k stop test with eval= probably prime else if t3MD=0 and i≠k continue at Step Nr. 3 else if j=(s-1) stop test with eval= composite else continue at Step Nr. 21The total number of needed core operations depends on the security parameterk and the value s resulting from the factorization of (n-1). Within the outer for loop from writing a new ai to the RAM until the evaluation of t2MD   1×MontR, 1×MontExp, 1×ModSub, 1×CopyH2V, 2×CopyV2H, 1×CopyV2V and 1×CopyH2H and until evaluation of t3MD   2×ModSub, 2×CopyV2H and 2×CopyH2H operations are required. Within the inner for loop until evaluation of updated t2MD  1×MontMult, 1×ModSub, 1×CopyH2V, 2×CopyV2H and 1×CopyH2H and until evaluation of updated t3MD2×ModSub, 2×CopyV2H and 2×CopyH2H operations is required.


### 5.3. Elliptic Curve Operations

Unlike modular exponentiation which only is based on modular multiplications, elliptic curve Point Addition and Point Doubling operations also in the Jacobian projective coordinate representation [23] involve modular additions, subtractions, and multiplications. The algorithms for prime field elliptic curve Point Addition and Point Doubling using Jacobian coordinates furthermore involve multiplications by some constants. Since the described core performs multiplication operations by using Montgomery Arithmetic, these constants must be transformed into the Montgomery Domain first for the intermediate values to remain montgomerized.In order to utilize the core for elliptic curve operations the following modular functions have been specified for bothGF(p) and GF(2m) support:(i)
EC Preparation.(ii)
EC Montgomery Transformation.(iii)
EC Affine-to-Jacobi Transformation.(iv)
EC Point Validation.(v)
EC Point Doubling.(vi)
EC Point Addition.(vii)
EC Jacobi-to-Affine Transformation.(viii)
EC Montgomery Backtransformation.In the following, algorithms for utilizing the core to perform EC operations inGF(p) are stated. For GF(2m) EC support, similar algorithms have been derived.


#### 5.3.1. GF(p) EC Preparation

The prime field EC Preparation steps include the calculation of the Montgomery Parameterr2modp, the exponent exp=p-2 as well as the montgomerized versions of the constants 2,3,4,8 and the EC Domain Parameters a and b for a given elliptic curve E:y2≡x3+a·x+bmodp over GF(p). Algorithm 3 lists the necessary steps to utilize the core for EC prime field preparation.Algorithm 3:Core GF(p) EC Preparation.
Requires: (2, 3, 4, 8, a, b, p) Calculates: (r2, 2MD, 3MD, 4MD, 8MD, aMD, bMD, exp)  r 2 = M o n t R 2 ( p ); 2 M D = M o n t M u l t ( r 2 , 2 , p ); 3 M D = M o n t M u l t ( r 2 , 3 , p ); 4 M D = M o n t M u l t ( r 2 , 4 , p ); 8 M D = M o n t M u l t ( r 2 , 8 , p ); a M D = M o n t M u l t ( r 2 , a , p ); b M D = M o n t M u l t ( r 2 , b , p ); e x p = M o d S u b ( p , 2 , p ); Provides: (r2, 2MD, 3MD, 4MD, 8MD, aMD, bMD, exp)A core prime field EC preparation operation requires1×MontR2, 6×MontMult, 1×ModSub, 8×CopyH2V, and 8×CopyH2H.


#### 5.3.2. GF(p) EC Montgomery Transformation

The prime field EC Montgomery Transformation steps are responsible for the transformation of the supplied affine point coordinatesxP and yP of a Point P in the case of a Point Doubling or Point Multiplication operation, xP,yP,xQ and yQ of the curve Points P and Q in the case of a Point Addition operation into the Montgomery Domain. Algorithm 4 lists the steps to utilize the core for prime field EC Montgomery Transformation for an arbitrary curve Point P.Algorithm 4:Core GF(p) EC Montgomery Transformation.
Requires: (xP, yP, r2) Calculates: (xPMD, yPMD)  x P M D = M o n t M u l t ( x P , r 2 , p ); y P M D = M o n t M u l t ( y P , r 2 , p ); Provides: (xPMD, yPMD)A core prime field EC Montgomery Transformation operation requires2×MontMult, 2×CopyH2V, and 2×CopyV2V in the case of an intended Point Doubling or Point Multiplication operation and 4×MontMult and 4×CopyH2V in the case of an intended Point Addition operation.


#### 5.3.3. GF(p) EC Affine-to-Jacobi Transformation

The prime field EC Affine-to-Jacobi Transformation steps are responsible for transforming the supplied montgomerized affine point coordinatesxPMD and yPMD of a curve Point P into Jacobian coordinates. Algorithm 5 lists the necessary steps to utilize the core for prime field EC Affine-to-Jacobi Transformation for an arbitrary montgomerized curve Point P.Algorithm 5:Core GF(p) EC Affine-to-Jacobi Transformation.
Requires: (xPMD, yPMD) Calculates: (xPMDj, yPMDj, zPMDj)  x P M D j ≔ x P M D; y P M D j ≔ y P M D; z P M D j = M o n t R ( p ); Provides: (xPMDj, yPMDj, zPMDj)A core prime field EC Affine-to-Jacobi Transformation operation requires1×MontR, 1×CopyH2V, and 1×CopyV2V in the case of an intended Point Addition, Point Doubling, or Point Multiplication operation.


#### 5.3.4. GF(p) EC Point Validation

The prime field EC Point Validation performs a check, if a supplied (or calculated) point indeed is a valid point of the elliptic curve given by the equationy2≡x3+a·x+bmodp. As a requirement the Point Validation must be conducted on montgomerized points in affine coordinate representation. Algorithm 6 lists the necessary steps to utilize the core for prime field EC Point Validation.Algorithm 6:Core GF(p) EC Point Validation.
Requires: (xPMD, yPMD, p, aMD, bMD) Output: (eval, point on curve or point not on curve)  y P M D 2 = M o n t M u l t ( y P M D , y P M D , p ); x P M D 2 = M o n t M u l t ( x P M D , x P M D , p ); a x P M D = M o n t M u l t ( a M D , x P M D , p ); x P M D 3 = M o n t M u l t ( x P M D 2 , x P M D , p ); t 1 M D = M o d A d d ( x P M D 3 , a x P M D , p ); t 2 M D = M o d A d d ( t 1 M D , b M D , p ); t 3 M D = M o d S u b ( y P M D 2 , t 2 M D , p ); if  t3MD=0  then return: (eval= point on curve); else return: (eval= point not on curve);A core prime field EC Point Validation operation requires4×MontMult, 2×ModAdd, 1×ModSub, 4×CopyV2H, and 5×CopyH2H.


#### 5.3.5. GF(p) EC Point Doubling

The prime field EC Point Doubling steps perform a single Point Doubling operation of a PointP with montgomerized Jacobi coordinates, resulting in 2·P=R also represented in montgomerized Jacobi coordinates. The original algorithm for Point Doubling with Jacobi coordinate representation has been modified to be suitable for the proposed core and is given in Algorithm 7.Algorithm 7:Core GF(p) EC Point Doubling.
Requires: (xPMDj, yPMDj, zPMDj, p, 2MD, 3MD, 4MD, 8MD, aMD) Calculates: (xRMDj, yRMDj, zRMDj)  t 1 M D = M o n t M u l t ( 4 M D , x P M D j , p ); y P M D j 2 = M o n t M u l t y P M D j , y P M D j , p; S M D = M o n t M u l t ( t 1 M D , y P M D j 2 , p ); x P M D j 2 = M o n t M u l t ( x P M D j , x P M D j , p ); t 2 M D = M o n t M u l t ( 3 M D , x P M D j 2 , p ); z P M D j 2 = M o n t M u l t ( z P M D j , z P M D j , p ); z P M D j 4 = M o n t M u l t ( z P M D j 2 , z P M D j 2 , p ); t 3 M D = M o n t M u l t ( a M D , z P M D j 4 , p ); M M D = M o d A d d ( t 2 M D , t 3 M D , p ); M M D 2 = M o n t M u l t ( M M D , M M D , p ); t 4 M D = M o n t M u l t ( 2 M D , S M D , p ); x R M D j = M o d S u b ( M M D 2 , t 4 M D , p ); t 5 M D = M o d S u b ( S M D , x R M D j , p ); t 6 M D = M o n t M u l t ( M M D , t 5 M D , p ); y P M D j 4 = M o n t M u l t ( y P M D j 2 , y P M D j 2 , p ); t 7 M D = M o n t M u l t ( 8 M D , y P M D j 4 , p ); y R M D j = M o d S u b ( t 6 M D , t 7 M D , p ); t 8 M D = M o n t M u l t ( y P M D j , z P M D j , p ); z R M D j = M o n t M u l t ( 2 M D , t 8 M D , p ); Provides: (xRMDj, yRMDj, zRMDj)A core prime field EC Point Doubling operation requires15×MontMult, 1×ModAdd, 3×ModSub, 6×CopyH2V, 6×CopyV2H, and 7×CopyH2H.


#### 5.3.6. GF(p) EC Point Addition

The prime field EC Point Addition steps perform a single Point Addition operation of two PointsP and Q with montgomerized Jacobi coordinates, resulting in P+Q=R also represented in montgomerized Jacobi coordinates. The original algorithm for Point Addition with Jacobi coordinate representation has been modified to be suitable for the proposed core and is given in Algorithm 8.Algorithm 8:Core GF(p) EC Point Addition.
Requires: (xPMDj, yPMDj, zPMDj, xQMDj, yQMDj, zQMDj, p, 2MD) Calculates: (xRMDj, yRMDj, zRMDj)  z Q M D j 2 = M o n t M u l t ( z Q M D j , z Q M D j , p ); U 1 M D = M o n t M u l t ( x P M D j , z Q M D j 2 , p ); z P M D j 2 = M o n t M u l t ( z P M D j , z P M D j , p ); U 2 M D = M o n t M u l t ( x Q M D j , z P M D j 2 , p ); z Q M D j 3 = M o n t M u l t ( z Q M D j 2 , z Q M D j , p ); S 1 M D = M o n t M u l t ( y P M D j , z Q M D j 3 , p ); z P M D j 3 = M o n t M u l t ( z P M D j 2 , z P M D j , p ); S 2 M D = M o n t M u l t ( y Q M D j , z P M D j 3 , p ); H M D = M o d S u b ( U 2 M D , U 1 M D , p ); R M D = M o d S u b ( S 2 M D , S 1 M D , p ); if  HMD=0  then i f   R M D ≠ 0  then Notify: ( x R M D j , y R M D j , z R M D j ) = ( 0,1 , 0 ) Point_at_Infinity (O); else Perform: PointDoubling Operation; else R M D 2 = M o n t M u l t ( R M D , R M D , p ); H M D 2 = M o n t M u l t ( H M D , H M D , p ); H M D 3 = M o n t M u l t ( H M D 2 , H M D , p ); t 1 M D = M o n t M u l t ( U 1 M D , H M D 2 , p ); t 2 M D = M o n t M u l t ( 2 M D , t 1 M D , p ); t 3 M D = M o d S u b ( R M D 2 , H M D 3 , p ); x R M D j = M o d S u b ( t 3 M D , t 2 M D , p ); t 4 M D = M o n t M u l t ( S 1 M D , H M D 3 , p ); t 5 M D = M o d S u b ( t 1 M D , x R M D j , p ); t 6 M D = M o n t M u l t ( R M D , t 5 M D , p ); y R M D j = M o d S u b ( t 6 M D , t 4 M D , p ); t 7 M D = M o n t M u l t ( z P M D j , H M D , p ); z R M D j = M o n t M u l t ( z Q M D j , t 7 M D , p ); Provides: (xRMDj, yRMDj, zRMDj)A core prime field EC Point Addition operation requires17×MontMult, 6×ModSub, 9×CopyH2V, 7×CopyV2H, and 12×CopyH2H.


#### 5.3.7. GF(p) EC Jacobi-to-Affine Transformation

The prime field EC Jacobi-to-Affine Transformation steps are responsible for the transformation of the supplied montgomerized Jacobi coordinatesxRMDj, yRMDj, and zRMDj of the curve Point R back into affine coordinate representation. This transformation step requires the calculation of a modular multiplicative inverse element which will be performed by a Montgomery modular exponentiation according to Euler’s theorem since the modulus is a prime number. Algorithm 9 lists the necessary steps to utilize the core for prime field EC Jacobi-to-Affine Transformation.Algorithm 9:Core GF(p) EC Jacobi-to-Affine Transformation.
Requires: (xRMDj, yRMDj, zRMDj, p, exp=p-2) Calculates: (xRMD, yRMD)  t 1 M D = M o n t E x p ( z R M D j , z R M D j , e x p , z R M D j , p ); t 2 M D = M o n t M u l t ( t 1 M D , t 1 M D , p ); t 3 M D = M o n t M u l t ( t 2 M D , t 1 M D , p ); x R M D = M o n t M u l t ( x R M D j , t 2 M D , p ); y R M D = M o n t M u l t ( y R M D j , t 3 M D , p ); Provides: (xRMD, yRMD)A core prime field EC Jacobi-to-Affine Transformation operation requires4×MontMult, 1×MontExp, 3×CopyH2V, 1×CopyV2H, 1×CopyV2V and 1×CopyH2H.


#### 5.3.8. GF(p) EC Montgomery Backtransformation

The prime field EC Montgomery Backtransformation steps are responsible for the transformation of the supplied montgomerized point coordinatesxRMD and yRMD of a Point R out of the Montgomery Domain. Algorithm 10 lists the necessary steps to utilize the core for prime field EC Montgomery Backtransformation for an arbitrary curve Point R.Algorithm 10:Core GF(p) EC Montgomery Backtransformation.
Requires: (xRMD, yRMD) Calculates: (xR, yR)  x R = M o n t M u l t 1 ( x R M D , p ); y R = M o n t M u l t 1 ( y R M D , p ); Provides: (xR, yR)A core prime field EC Montgomery Backtransformation operation requires2×MontMult1 and 2×CopyV2H.


## 5.1. CRT-Accelerated RSA Operation

In order to speed up RSA private key operations the CRT-accelerated version is also supported by the core. Therefore some operations have to be performed with full precision whereas most of the operations have to be performed with half precision. Algorithm1 lists the necessary steps to utilize the core for CRT-accelerated RSA private key operations.Algorithm 1:CRT-RSA private key operation.
Requires: (c, d, p, q, exp1, exp2, coeff, n) Calculates: (m)  (h)  r q 2 = M o n t R 2 ( q ); (f)  c q = M o n t M u l t ( r q 2 , c , q ); (h)  c q M D = M o n t M u l t r q 2 , c q , q; (h)  m q M D = M o n t E x p ( c q M D , c q M D , e x p 2 , c q M D , q ); (h)  m q = M o n t M u l t 1 ( m q M D , q ); (h)  r p 2 = M o n t R 2 ( p ); (f)  c p = M o n t M u l t ( r p 2 , c , p ); (h)  c p M D = M o n t M u l t ( r p 2 , c p , p ); (h)  m p M D = M o n t E x p ( c p M D , c p M D , e x p 1 , c p M D , p ); (h)  m p = M o n t M u l t 1 ( m p M D , p ); (h)  c o e f f M D = M o n t M u l t ( r p 2 , c p , p ); (h)  t 1 = M o d S u b ( m p , m q , p ); (h)  t 2 = M o n t M u l t c o e f f M D , t 1 , p; (f)  r 2 = M o n t R 2 ( n ); (f)  q M D = M o n t M u l t ( q , r 2 , n ); (f)  t 3 = M o n t M u l t ( t 2 , q M D , n ); (f)  m = M o d A d d ( t 3 , m q , n ); Provides: (m)Table1 illustrates the abstract operations lists of the core for CRT-accelerated RSA application using the private key portion for all supported precision widths (512, 768, 1024, 1536, 2048, 3072, 4096). The number given in the index of the RAM locations denotes the offset given by the corresponding src_addr, dest_addr, src_addr_e, src_addr_x input signals. The width of the processed values depends on the supplied mwmac_precision input signal which depends on the operation. In the table operations requiring full precision (the precision of the RSA modulus) are marked by (f), operations requiring half precision are marked by (h). The mwmac_f_sel signal must be set to GF(p) arithmetic.Table 1
Core operations list CRT-RSA.
Step Nr. Precision Operation 1 - Clear RAM  2 - Writeq↦P1,  exp⁡1↦E1, exp⁡2↦E5, coeff↦X1, p↦X5  3 ( h ) M o n t R 2 ( P 1 , A 1 )  4 ( h ) C o p y H 2 V ( B 1 , A 1 )  5 - Writec↦B1  6 ( f ) M o n t M u l t ( A 1 , B 1 , P 1 )  7 ( h ) M o n t M u l t ( A 1 , B 1 , P 1 )  8-9 ( h ) C o p y H 2 V ( B 1 , A 1 ), CopyV2V(A1,A5)  10 ( h ) M o n t E x p ( A 5 , B 1 , E 5 , A 1 , P 1 )  11 ( h ) M o n t M u l t 1 ( B 1 , P 1 )  12 - 14 ( h ) C o p y H 2 V ( P 1 , E 5 ), CopyV2H(X5,P1), CopyH2V(B1,X5)  15 ( h ) M o n t R 2 ( P 1 , A 1 )  16 ( f ) C o p y H 2 V ( B 1 , A 1 )  17 ( h ) C o p y V 2 H ( X 1 , B 1 )  18 ( h ) M o n t M u l t ( A 1 , B 1 , P 1 )  19 ( h ) C o p y H 2 V ( B 1 , X 1 )  20 - Writec↦B1  21 ( f ) M o n t M u l t ( A 1 , B 1 , P 1 )  22 ( h ) M o n t M u l t ( A 1 , B 1 , P 1 )  23 - 24 ( h ) C o p y H 2 V ( B 1 , A 1 ), CopyV2V(A1,A5)  25 ( h ) M o n t E x p ( A 5 , B 1 , E 1 , A 1 , P 1 )  26 ( h ) M o n t M u l t 1 ( B 1 , P 1 )  27 - 28 ( h ) C o p y H 2 H ( B 1 , T S 1 ), CopyV2H(X5,TC1)  29 ( h ) M o d S u b ( T S 1 , T C 1 , P 1 )  30 ( h ) M o n t M u l t ( X 1 , B 1 , P 1 )  31 - 32 ( h ) C o p y H 2 V ( B 1 , A 1 ), CopyH2V(TS1,X1)  33 - Writen↦P1  34 ( f ) M o n t R 2 ( P 1 , A 5 )  35 ( h ) C o p y V 2 V ( X 1 , A 5 )  36 ( f ) M o n t M u l t ( E 5 , B 1 , P 1 )  37 ( f ) M o n t M u l t ( A 1 , B 1 , P 1 )  38 ( f ) C o p y H 2 H ( B 1 , T S 1 )  39 ( h ) C o p y V 2 H ( X 5 , T C 1 )  40 ( f ) M o d A d d ( T S 1 , T C 1 , P 1 )CRT-accelerated RSA private key operations require2×MontR2, 4×MontMult, 2×MontMult1, 2×MontExp, 1×ModSub, 9×CopyH2V, 4×CopyV2H, 2×CopyV2V and 1×CopyH2H performed on half precision and 1×MontR2, 4×MontMult, 1×ModAdd, 1×CopyH2V and 1×CopyH2H performed on full precision.


## 5.2. Prime Generation/Testing Operation

Algorithm2 lists the necessary steps to utilize the core, in conjunction with a TRNG generator as Miller-Rabin Primality Tester. In the algorithm n denotes the random integer to be tested for primality and k denotes the confidence parameter determining the accuracy of the test, i.e., the amount of Miller-Rabin loops. In a precomputation step the parameters s and d with 2s·d=(n-1) must be calculated which can be done by simple shift operations and counter increments in software. The test furthermore requires an amount of random integers {a1,…,ak} serving as random bases.Algorithm 2:Modified Miller-Rabin Primality Test.
Precomputation: (s, d with 2s⋅d=(n-1)) Input: (n, s, d, k  {a1,…,ak}) Output: (eval, composite or probably prime)  r = M o n t R ( n ); ( n - r ) = M o d S u b ( n , r , n ); for  i   from 1 to  k  do t 1 M D = M o n t E x p ( a i , a i , d , a i , n ); t 2 M D = M o d S u b ( t 1 M D , r , n ); t 3 M D = M o d S u b ( t 1 M D , ( n - r ) , n ); if  t2MD=0  or  t3MD=0  then continue; for j   from  0  to  (s-1)  do t 1 M D = M o n t M u l t ( t 1 M D , t 1 M D , n ); t 2 M D = M o d S u b ( t 1 M D , r , n ); if  t2MD=0  then return (eval= composite); t 3 M D = M o d S u b t 1 M D , n - r , n; if  t3MD=0  then continue; return (eval= composite); return (eval= probably prime)Table2 illustrates the operations list of utilizing the core for Miller-Rabin Primality Test steps for all supported precision widths (192, 224, 256, 320, 384, 512, 768, 1024, 1536, 2048, 3072, 4096). The number given in the index of the RAM locations denotes the offset given by the corresponding src_addr, dest_addr, src_addr_e, src_addr_x input signals. The width of the processed values depends on the supplied mwmac_precision input signal. The mwmac_f_sel signal must be set to GF(p) arithmetic. Note that since the results of the performed operations will be in the Montgomery Domain, they will be checked against the Montgomery Parameter r and (n-r) instead of 1 and (n-1). Also note that the random bases ai that will be checked must not necessarily be transformed into the Montgomery Domain first, they simply will be interpreted as random montgomerized values.Table 2
Core operations list for Miller-Rabin Primality Test.
Step Nr. Operation 1 Clear RAM  2 Writen↦P1, d↦E1  3 Writea↦X1  4-5 C o p y V 2 V ( X 1 , A 1 ),  CopyV2H(X1,B1)  6 M o n t E x p ( X 1 , B 1 , E 1 , A 1 , P 1 )  7 C o p y H 2 V ( B 1 , X 1 )  8 M o n t R ( P 1 , B 1 )  9-11 C o p y H 2 V ( B 1 , A 1 ),  CopyV2H(X1,TS1),  CopyH2H(B1,TC1)  12 M o d S u b ( T S 1 , T C 1 , P 1 )  13 ReadB1, if t2MD=0 continue at Step Nr. 3 else continue at Step Nr. 14  14-15 C o p y H 2 H ( P 1 , T S 1 ),  CopyV2H(A1,TC1)  16 M o d S u b ( T S 1 , T C 1 , P 1 )  17-18 C o p y V 2 H X 1 , T S 1,  CopyH2H(B1,TC1)  19 ModSub(TS1,TC1,P1)  20 ReadB1, if t3MD=0 continue at Step Nr. 3 else if (s-1)=0 stop test with eval= composite else continue at Step Nr. 21  21 C o p y V 2 H ( X 1 , B 1 )  22 M o n t M u l t ( X 1 , B 1 , P 1 )  23-25 C o p y H 2 V B 1 , X 1,  CopyH2H(B1,TS1),  CopyV2H(A1,TC1)  26 M o d S u b ( T S 1 , T C 1 , P 1 )  27 ReadB1, if t2MD=0 stop test with eval= composite else continue at Step Nr. 28  28-29 C o p y H 2 H ( P 1 , T S 1 ),  CopyV2H(A1,TC1)  30 M o d S u b ( T S 1 , T C 1 , P 1 )  31-32 C o p y V 2 H X 1 , T S 1,  CopyH2H(B1,TC1)  33 M o d S u b ( T S 1 , T C 1 , P 1 )  34 ReadB1, if t3MD=0 and i=k stop test with eval= probably prime else if t3MD=0 and i≠k continue at Step Nr. 3 else if j=(s-1) stop test with eval= composite else continue at Step Nr. 21The total number of needed core operations depends on the security parameterk and the value s resulting from the factorization of (n-1). Within the outer for loop from writing a new ai to the RAM until the evaluation of t2MD   1×MontR, 1×MontExp, 1×ModSub, 1×CopyH2V, 2×CopyV2H, 1×CopyV2V and 1×CopyH2H and until evaluation of t3MD   2×ModSub, 2×CopyV2H and 2×CopyH2H operations are required. Within the inner for loop until evaluation of updated t2MD  1×MontMult, 1×ModSub, 1×CopyH2V, 2×CopyV2H and 1×CopyH2H and until evaluation of updated t3MD2×ModSub, 2×CopyV2H and 2×CopyH2H operations is required.


## 5.3. Elliptic Curve Operations

Unlike modular exponentiation which only is based on modular multiplications, elliptic curve Point Addition and Point Doubling operations also in the Jacobian projective coordinate representation [23] involve modular additions, subtractions, and multiplications. The algorithms for prime field elliptic curve Point Addition and Point Doubling using Jacobian coordinates furthermore involve multiplications by some constants. Since the described core performs multiplication operations by using Montgomery Arithmetic, these constants must be transformed into the Montgomery Domain first for the intermediate values to remain montgomerized.In order to utilize the core for elliptic curve operations the following modular functions have been specified for bothGF(p) and GF(2m) support:(i)
EC Preparation.(ii)
EC Montgomery Transformation.(iii)
EC Affine-to-Jacobi Transformation.(iv)
EC Point Validation.(v)
EC Point Doubling.(vi)
EC Point Addition.(vii)
EC Jacobi-to-Affine Transformation.(viii)
EC Montgomery Backtransformation.In the following, algorithms for utilizing the core to perform EC operations inGF(p) are stated. For GF(2m) EC support, similar algorithms have been derived.


### 5.3.1. GF(p) EC Preparation

The prime field EC Preparation steps include the calculation of the Montgomery Parameterr2modp, the exponent exp=p-2 as well as the montgomerized versions of the constants 2,3,4,8 and the EC Domain Parameters a and b for a given elliptic curve E:y2≡x3+a·x+bmodp over GF(p). Algorithm 3 lists the necessary steps to utilize the core for EC prime field preparation.Algorithm 3:Core GF(p) EC Preparation.
Requires: (2, 3, 4, 8, a, b, p) Calculates: (r2, 2MD, 3MD, 4MD, 8MD, aMD, bMD, exp)  r 2 = M o n t R 2 ( p ); 2 M D = M o n t M u l t ( r 2 , 2 , p ); 3 M D = M o n t M u l t ( r 2 , 3 , p ); 4 M D = M o n t M u l t ( r 2 , 4 , p ); 8 M D = M o n t M u l t ( r 2 , 8 , p ); a M D = M o n t M u l t ( r 2 , a , p ); b M D = M o n t M u l t ( r 2 , b , p ); e x p = M o d S u b ( p , 2 , p ); Provides: (r2, 2MD, 3MD, 4MD, 8MD, aMD, bMD, exp)A core prime field EC preparation operation requires1×MontR2, 6×MontMult, 1×ModSub, 8×CopyH2V, and 8×CopyH2H.


### 5.3.2. GF(p) EC Montgomery Transformation

The prime field EC Montgomery Transformation steps are responsible for the transformation of the supplied affine point coordinatesxP and yP of a Point P in the case of a Point Doubling or Point Multiplication operation, xP,yP,xQ and yQ of the curve Points P and Q in the case of a Point Addition operation into the Montgomery Domain. Algorithm 4 lists the steps to utilize the core for prime field EC Montgomery Transformation for an arbitrary curve Point P.Algorithm 4:Core GF(p) EC Montgomery Transformation.
Requires: (xP, yP, r2) Calculates: (xPMD, yPMD)  x P M D = M o n t M u l t ( x P , r 2 , p ); y P M D = M o n t M u l t ( y P , r 2 , p ); Provides: (xPMD, yPMD)A core prime field EC Montgomery Transformation operation requires2×MontMult, 2×CopyH2V, and 2×CopyV2V in the case of an intended Point Doubling or Point Multiplication operation and 4×MontMult and 4×CopyH2V in the case of an intended Point Addition operation.


### 5.3.3. GF(p) EC Affine-to-Jacobi Transformation

The prime field EC Affine-to-Jacobi Transformation steps are responsible for transforming the supplied montgomerized affine point coordinatesxPMD and yPMD of a curve Point P into Jacobian coordinates. Algorithm 5 lists the necessary steps to utilize the core for prime field EC Affine-to-Jacobi Transformation for an arbitrary montgomerized curve Point P.Algorithm 5:Core GF(p) EC Affine-to-Jacobi Transformation.
Requires: (xPMD, yPMD) Calculates: (xPMDj, yPMDj, zPMDj)  x P M D j ≔ x P M D; y P M D j ≔ y P M D; z P M D j = M o n t R ( p ); Provides: (xPMDj, yPMDj, zPMDj)A core prime field EC Affine-to-Jacobi Transformation operation requires1×MontR, 1×CopyH2V, and 1×CopyV2V in the case of an intended Point Addition, Point Doubling, or Point Multiplication operation.


### 5.3.4. GF(p) EC Point Validation

The prime field EC Point Validation performs a check, if a supplied (or calculated) point indeed is a valid point of the elliptic curve given by the equationy2≡x3+a·x+bmodp. As a requirement the Point Validation must be conducted on montgomerized points in affine coordinate representation. Algorithm 6 lists the necessary steps to utilize the core for prime field EC Point Validation.Algorithm 6:Core GF(p) EC Point Validation.
Requires: (xPMD, yPMD, p, aMD, bMD) Output: (eval, point on curve or point not on curve)  y P M D 2 = M o n t M u l t ( y P M D , y P M D , p ); x P M D 2 = M o n t M u l t ( x P M D , x P M D , p ); a x P M D = M o n t M u l t ( a M D , x P M D , p ); x P M D 3 = M o n t M u l t ( x P M D 2 , x P M D , p ); t 1 M D = M o d A d d ( x P M D 3 , a x P M D , p ); t 2 M D = M o d A d d ( t 1 M D , b M D , p ); t 3 M D = M o d S u b ( y P M D 2 , t 2 M D , p ); if  t3MD=0  then return: (eval= point on curve); else return: (eval= point not on curve);A core prime field EC Point Validation operation requires4×MontMult, 2×ModAdd, 1×ModSub, 4×CopyV2H, and 5×CopyH2H.


### 5.3.5. GF(p) EC Point Doubling

The prime field EC Point Doubling steps perform a single Point Doubling operation of a PointP with montgomerized Jacobi coordinates, resulting in 2·P=R also represented in montgomerized Jacobi coordinates. The original algorithm for Point Doubling with Jacobi coordinate representation has been modified to be suitable for the proposed core and is given in Algorithm 7.Algorithm 7:Core GF(p) EC Point Doubling.
Requires: (xPMDj, yPMDj, zPMDj, p, 2MD, 3MD, 4MD, 8MD, aMD) Calculates: (xRMDj, yRMDj, zRMDj)  t 1 M D = M o n t M u l t ( 4 M D , x P M D j , p ); y P M D j 2 = M o n t M u l t y P M D j , y P M D j , p; S M D = M o n t M u l t ( t 1 M D , y P M D j 2 , p ); x P M D j 2 = M o n t M u l t ( x P M D j , x P M D j , p ); t 2 M D = M o n t M u l t ( 3 M D , x P M D j 2 , p ); z P M D j 2 = M o n t M u l t ( z P M D j , z P M D j , p ); z P M D j 4 = M o n t M u l t ( z P M D j 2 , z P M D j 2 , p ); t 3 M D = M o n t M u l t ( a M D , z P M D j 4 , p ); M M D = M o d A d d ( t 2 M D , t 3 M D , p ); M M D 2 = M o n t M u l t ( M M D , M M D , p ); t 4 M D = M o n t M u l t ( 2 M D , S M D , p ); x R M D j = M o d S u b ( M M D 2 , t 4 M D , p ); t 5 M D = M o d S u b ( S M D , x R M D j , p ); t 6 M D = M o n t M u l t ( M M D , t 5 M D , p ); y P M D j 4 = M o n t M u l t ( y P M D j 2 , y P M D j 2 , p ); t 7 M D = M o n t M u l t ( 8 M D , y P M D j 4 , p ); y R M D j = M o d S u b ( t 6 M D , t 7 M D , p ); t 8 M D = M o n t M u l t ( y P M D j , z P M D j , p ); z R M D j = M o n t M u l t ( 2 M D , t 8 M D , p ); Provides: (xRMDj, yRMDj, zRMDj)A core prime field EC Point Doubling operation requires15×MontMult, 1×ModAdd, 3×ModSub, 6×CopyH2V, 6×CopyV2H, and 7×CopyH2H.


### 5.3.6. GF(p) EC Point Addition

The prime field EC Point Addition steps perform a single Point Addition operation of two PointsP and Q with montgomerized Jacobi coordinates, resulting in P+Q=R also represented in montgomerized Jacobi coordinates. The original algorithm for Point Addition with Jacobi coordinate representation has been modified to be suitable for the proposed core and is given in Algorithm 8.Algorithm 8:Core GF(p) EC Point Addition.
Requires: (xPMDj, yPMDj, zPMDj, xQMDj, yQMDj, zQMDj, p, 2MD) Calculates: (xRMDj, yRMDj, zRMDj)  z Q M D j 2 = M o n t M u l t ( z Q M D j , z Q M D j , p ); U 1 M D = M o n t M u l t ( x P M D j , z Q M D j 2 , p ); z P M D j 2 = M o n t M u l t ( z P M D j , z P M D j , p ); U 2 M D = M o n t M u l t ( x Q M D j , z P M D j 2 , p ); z Q M D j 3 = M o n t M u l t ( z Q M D j 2 , z Q M D j , p ); S 1 M D = M o n t M u l t ( y P M D j , z Q M D j 3 , p ); z P M D j 3 = M o n t M u l t ( z P M D j 2 , z P M D j , p ); S 2 M D = M o n t M u l t ( y Q M D j , z P M D j 3 , p ); H M D = M o d S u b ( U 2 M D , U 1 M D , p ); R M D = M o d S u b ( S 2 M D , S 1 M D , p ); if  HMD=0  then i f   R M D ≠ 0  then Notify: ( x R M D j , y R M D j , z R M D j ) = ( 0,1 , 0 ) Point_at_Infinity (O); else Perform: PointDoubling Operation; else R M D 2 = M o n t M u l t ( R M D , R M D , p ); H M D 2 = M o n t M u l t ( H M D , H M D , p ); H M D 3 = M o n t M u l t ( H M D 2 , H M D , p ); t 1 M D = M o n t M u l t ( U 1 M D , H M D 2 , p ); t 2 M D = M o n t M u l t ( 2 M D , t 1 M D , p ); t 3 M D = M o d S u b ( R M D 2 , H M D 3 , p ); x R M D j = M o d S u b ( t 3 M D , t 2 M D , p ); t 4 M D = M o n t M u l t ( S 1 M D , H M D 3 , p ); t 5 M D = M o d S u b ( t 1 M D , x R M D j , p ); t 6 M D = M o n t M u l t ( R M D , t 5 M D , p ); y R M D j = M o d S u b ( t 6 M D , t 4 M D , p ); t 7 M D = M o n t M u l t ( z P M D j , H M D , p ); z R M D j = M o n t M u l t ( z Q M D j , t 7 M D , p ); Provides: (xRMDj, yRMDj, zRMDj)A core prime field EC Point Addition operation requires17×MontMult, 6×ModSub, 9×CopyH2V, 7×CopyV2H, and 12×CopyH2H.


### 5.3.7. GF(p) EC Jacobi-to-Affine Transformation

The prime field EC Jacobi-to-Affine Transformation steps are responsible for the transformation of the supplied montgomerized Jacobi coordinatesxRMDj, yRMDj, and zRMDj of the curve Point R back into affine coordinate representation. This transformation step requires the calculation of a modular multiplicative inverse element which will be performed by a Montgomery modular exponentiation according to Euler’s theorem since the modulus is a prime number. Algorithm 9 lists the necessary steps to utilize the core for prime field EC Jacobi-to-Affine Transformation.Algorithm 9:Core GF(p) EC Jacobi-to-Affine Transformation.
Requires: (xRMDj, yRMDj, zRMDj, p, exp=p-2) Calculates: (xRMD, yRMD)  t 1 M D = M o n t E x p ( z R M D j , z R M D j , e x p , z R M D j , p ); t 2 M D = M o n t M u l t ( t 1 M D , t 1 M D , p ); t 3 M D = M o n t M u l t ( t 2 M D , t 1 M D , p ); x R M D = M o n t M u l t ( x R M D j , t 2 M D , p ); y R M D = M o n t M u l t ( y R M D j , t 3 M D , p ); Provides: (xRMD, yRMD)A core prime field EC Jacobi-to-Affine Transformation operation requires4×MontMult, 1×MontExp, 3×CopyH2V, 1×CopyV2H, 1×CopyV2V and 1×CopyH2H.


### 5.3.8. GF(p) EC Montgomery Backtransformation

The prime field EC Montgomery Backtransformation steps are responsible for the transformation of the supplied montgomerized point coordinatesxRMD and yRMD of a Point R out of the Montgomery Domain. Algorithm 10 lists the necessary steps to utilize the core for prime field EC Montgomery Backtransformation for an arbitrary curve Point R.Algorithm 10:Core GF(p) EC Montgomery Backtransformation.
Requires: (xRMD, yRMD) Calculates: (xR, yR)  x R = M o n t M u l t 1 ( x R M D , p ); y R = M o n t M u l t 1 ( y R M D , p ); Provides: (xR, yR)A core prime field EC Montgomery Backtransformation operation requires2×MontMult1 and 2×CopyV2H.


## 5.3.1. GF(p) EC Preparation

The prime field EC Preparation steps include the calculation of the Montgomery Parameterr2modp, the exponent exp=p-2 as well as the montgomerized versions of the constants 2,3,4,8 and the EC Domain Parameters a and b for a given elliptic curve E:y2≡x3+a·x+bmodp over GF(p). Algorithm 3 lists the necessary steps to utilize the core for EC prime field preparation.Algorithm 3:Core GF(p) EC Preparation.
Requires: (2, 3, 4, 8, a, b, p) Calculates: (r2, 2MD, 3MD, 4MD, 8MD, aMD, bMD, exp)  r 2 = M o n t R 2 ( p ); 2 M D = M o n t M u l t ( r 2 , 2 , p ); 3 M D = M o n t M u l t ( r 2 , 3 , p ); 4 M D = M o n t M u l t ( r 2 , 4 , p ); 8 M D = M o n t M u l t ( r 2 , 8 , p ); a M D = M o n t M u l t ( r 2 , a , p ); b M D = M o n t M u l t ( r 2 , b , p ); e x p = M o d S u b ( p , 2 , p ); Provides: (r2, 2MD, 3MD, 4MD, 8MD, aMD, bMD, exp)A core prime field EC preparation operation requires1×MontR2, 6×MontMult, 1×ModSub, 8×CopyH2V, and 8×CopyH2H.


## 5.3.2. GF(p) EC Montgomery Transformation

The prime field EC Montgomery Transformation steps are responsible for the transformation of the supplied affine point coordinatesxP and yP of a Point P in the case of a Point Doubling or Point Multiplication operation, xP,yP,xQ and yQ of the curve Points P and Q in the case of a Point Addition operation into the Montgomery Domain. Algorithm 4 lists the steps to utilize the core for prime field EC Montgomery Transformation for an arbitrary curve Point P.Algorithm 4:Core GF(p) EC Montgomery Transformation.
Requires: (xP, yP, r2) Calculates: (xPMD, yPMD)  x P M D = M o n t M u l t ( x P , r 2 , p ); y P M D = M o n t M u l t ( y P , r 2 , p ); Provides: (xPMD, yPMD)A core prime field EC Montgomery Transformation operation requires2×MontMult, 2×CopyH2V, and 2×CopyV2V in the case of an intended Point Doubling or Point Multiplication operation and 4×MontMult and 4×CopyH2V in the case of an intended Point Addition operation.


## 5.3.3. GF(p) EC Affine-to-Jacobi Transformation

The prime field EC Affine-to-Jacobi Transformation steps are responsible for transforming the supplied montgomerized affine point coordinatesxPMD and yPMD of a curve Point P into Jacobian coordinates. Algorithm 5 lists the necessary steps to utilize the core for prime field EC Affine-to-Jacobi Transformation for an arbitrary montgomerized curve Point P.Algorithm 5:Core GF(p) EC Affine-to-Jacobi Transformation.
Requires: (xPMD, yPMD) Calculates: (xPMDj, yPMDj, zPMDj)  x P M D j ≔ x P M D; y P M D j ≔ y P M D; z P M D j = M o n t R ( p ); Provides: (xPMDj, yPMDj, zPMDj)A core prime field EC Affine-to-Jacobi Transformation operation requires1×MontR, 1×CopyH2V, and 1×CopyV2V in the case of an intended Point Addition, Point Doubling, or Point Multiplication operation.


## 5.3.4. GF(p) EC Point Validation

The prime field EC Point Validation performs a check, if a supplied (or calculated) point indeed is a valid point of the elliptic curve given by the equationy2≡x3+a·x+bmodp. As a requirement the Point Validation must be conducted on montgomerized points in affine coordinate representation. Algorithm 6 lists the necessary steps to utilize the core for prime field EC Point Validation.Algorithm 6:Core GF(p) EC Point Validation.
Requires: (xPMD, yPMD, p, aMD, bMD) Output: (eval, point on curve or point not on curve)  y P M D 2 = M o n t M u l t ( y P M D , y P M D , p ); x P M D 2 = M o n t M u l t ( x P M D , x P M D , p ); a x P M D = M o n t M u l t ( a M D , x P M D , p ); x P M D 3 = M o n t M u l t ( x P M D 2 , x P M D , p ); t 1 M D = M o d A d d ( x P M D 3 , a x P M D , p ); t 2 M D = M o d A d d ( t 1 M D , b M D , p ); t 3 M D = M o d S u b ( y P M D 2 , t 2 M D , p ); if  t3MD=0  then return: (eval= point on curve); else return: (eval= point not on curve);A core prime field EC Point Validation operation requires4×MontMult, 2×ModAdd, 1×ModSub, 4×CopyV2H, and 5×CopyH2H.


## 5.3.5. GF(p) EC Point Doubling

The prime field EC Point Doubling steps perform a single Point Doubling operation of a PointP with montgomerized Jacobi coordinates, resulting in 2·P=R also represented in montgomerized Jacobi coordinates. The original algorithm for Point Doubling with Jacobi coordinate representation has been modified to be suitable for the proposed core and is given in Algorithm 7.Algorithm 7:Core GF(p) EC Point Doubling.
Requires: (xPMDj, yPMDj, zPMDj, p, 2MD, 3MD, 4MD, 8MD, aMD) Calculates: (xRMDj, yRMDj, zRMDj)  t 1 M D = M o n t M u l t ( 4 M D , x P M D j , p ); y P M D j 2 = M o n t M u l t y P M D j , y P M D j , p; S M D = M o n t M u l t ( t 1 M D , y P M D j 2 , p ); x P M D j 2 = M o n t M u l t ( x P M D j , x P M D j , p ); t 2 M D = M o n t M u l t ( 3 M D , x P M D j 2 , p ); z P M D j 2 = M o n t M u l t ( z P M D j , z P M D j , p ); z P M D j 4 = M o n t M u l t ( z P M D j 2 , z P M D j 2 , p ); t 3 M D = M o n t M u l t ( a M D , z P M D j 4 , p ); M M D = M o d A d d ( t 2 M D , t 3 M D , p ); M M D 2 = M o n t M u l t ( M M D , M M D , p ); t 4 M D = M o n t M u l t ( 2 M D , S M D , p ); x R M D j = M o d S u b ( M M D 2 , t 4 M D , p ); t 5 M D = M o d S u b ( S M D , x R M D j , p ); t 6 M D = M o n t M u l t ( M M D , t 5 M D , p ); y P M D j 4 = M o n t M u l t ( y P M D j 2 , y P M D j 2 , p ); t 7 M D = M o n t M u l t ( 8 M D , y P M D j 4 , p ); y R M D j = M o d S u b ( t 6 M D , t 7 M D , p ); t 8 M D = M o n t M u l t ( y P M D j , z P M D j , p ); z R M D j = M o n t M u l t ( 2 M D , t 8 M D , p ); Provides: (xRMDj, yRMDj, zRMDj)A core prime field EC Point Doubling operation requires15×MontMult, 1×ModAdd, 3×ModSub, 6×CopyH2V, 6×CopyV2H, and 7×CopyH2H.


## 5.3.6. GF(p) EC Point Addition

The prime field EC Point Addition steps perform a single Point Addition operation of two PointsP and Q with montgomerized Jacobi coordinates, resulting in P+Q=R also represented in montgomerized Jacobi coordinates. The original algorithm for Point Addition with Jacobi coordinate representation has been modified to be suitable for the proposed core and is given in Algorithm 8.Algorithm 8:Core GF(p) EC Point Addition.
Requires: (xPMDj, yPMDj, zPMDj, xQMDj, yQMDj, zQMDj, p, 2MD) Calculates: (xRMDj, yRMDj, zRMDj)  z Q M D j 2 = M o n t M u l t ( z Q M D j , z Q M D j , p ); U 1 M D = M o n t M u l t ( x P M D j , z Q M D j 2 , p ); z P M D j 2 = M o n t M u l t ( z P M D j , z P M D j , p ); U 2 M D = M o n t M u l t ( x Q M D j , z P M D j 2 , p ); z Q M D j 3 = M o n t M u l t ( z Q M D j 2 , z Q M D j , p ); S 1 M D = M o n t M u l t ( y P M D j , z Q M D j 3 , p ); z P M D j 3 = M o n t M u l t ( z P M D j 2 , z P M D j , p ); S 2 M D = M o n t M u l t ( y Q M D j , z P M D j 3 , p ); H M D = M o d S u b ( U 2 M D , U 1 M D , p ); R M D = M o d S u b ( S 2 M D , S 1 M D , p ); if  HMD=0  then i f   R M D ≠ 0  then Notify: ( x R M D j , y R M D j , z R M D j ) = ( 0,1 , 0 ) Point_at_Infinity (O); else Perform: PointDoubling Operation; else R M D 2 = M o n t M u l t ( R M D , R M D , p ); H M D 2 = M o n t M u l t ( H M D , H M D , p ); H M D 3 = M o n t M u l t ( H M D 2 , H M D , p ); t 1 M D = M o n t M u l t ( U 1 M D , H M D 2 , p ); t 2 M D = M o n t M u l t ( 2 M D , t 1 M D , p ); t 3 M D = M o d S u b ( R M D 2 , H M D 3 , p ); x R M D j = M o d S u b ( t 3 M D , t 2 M D , p ); t 4 M D = M o n t M u l t ( S 1 M D , H M D 3 , p ); t 5 M D = M o d S u b ( t 1 M D , x R M D j , p ); t 6 M D = M o n t M u l t ( R M D , t 5 M D , p ); y R M D j = M o d S u b ( t 6 M D , t 4 M D , p ); t 7 M D = M o n t M u l t ( z P M D j , H M D , p ); z R M D j = M o n t M u l t ( z Q M D j , t 7 M D , p ); Provides: (xRMDj, yRMDj, zRMDj)A core prime field EC Point Addition operation requires17×MontMult, 6×ModSub, 9×CopyH2V, 7×CopyV2H, and 12×CopyH2H.


## 5.3.7. GF(p) EC Jacobi-to-Affine Transformation

The prime field EC Jacobi-to-Affine Transformation steps are responsible for the transformation of the supplied montgomerized Jacobi coordinatesxRMDj, yRMDj, and zRMDj of the curve Point R back into affine coordinate representation. This transformation step requires the calculation of a modular multiplicative inverse element which will be performed by a Montgomery modular exponentiation according to Euler’s theorem since the modulus is a prime number. Algorithm 9 lists the necessary steps to utilize the core for prime field EC Jacobi-to-Affine Transformation.Algorithm 9:Core GF(p) EC Jacobi-to-Affine Transformation.
Requires: (xRMDj, yRMDj, zRMDj, p, exp=p-2) Calculates: (xRMD, yRMD)  t 1 M D = M o n t E x p ( z R M D j , z R M D j , e x p , z R M D j , p ); t 2 M D = M o n t M u l t ( t 1 M D , t 1 M D , p ); t 3 M D = M o n t M u l t ( t 2 M D , t 1 M D , p ); x R M D = M o n t M u l t ( x R M D j , t 2 M D , p ); y R M D = M o n t M u l t ( y R M D j , t 3 M D , p ); Provides: (xRMD, yRMD)A core prime field EC Jacobi-to-Affine Transformation operation requires4×MontMult, 1×MontExp, 3×CopyH2V, 1×CopyV2H, 1×CopyV2V and 1×CopyH2H.


## 5.3.8. GF(p) EC Montgomery Backtransformation

The prime field EC Montgomery Backtransformation steps are responsible for the transformation of the supplied montgomerized point coordinatesxRMD and yRMD of a Point R out of the Montgomery Domain. Algorithm 10 lists the necessary steps to utilize the core for prime field EC Montgomery Backtransformation for an arbitrary curve Point R.Algorithm 10:Core GF(p) EC Montgomery Backtransformation.
Requires: (xRMD, yRMD) Calculates: (xR, yR)  x R = M o n t M u l t 1 ( x R M D , p ); y R = M o n t M u l t 1 ( y R M D , p ); Provides: (xR, yR)A core prime field EC Montgomery Backtransformation operation requires2×MontMult1 and 2×CopyV2H.


## 6. Performance Analysis

In this section parameter-dependent formulas for the calculation of the computation times in clock cycles of the described basic core operations are given which allows specifying upper and lower calculation boundaries. Furthermore for the supported precision widths in both finite fields the number of words to be processed and the possible numbers of processing units is given. In order to estimate the size ratio of different core variations the number of logic elements and dedicated logic registers for exemplary Altera and Xilinx FPGAs is stated. Furthermore results of power estimation are given. Depending on the resulting clock cycle times of core variations a reference implementation exhibiting a balance of performance and area consumption has been defined. For this reference implementation the computation times in clock cycles for the described exemplary cryptographic algorithms are given.


### 6.1. Core Computation Time Formulas

Table3 lists the RAM copy operations computation time formulas in clock cycles of the proposed core. Note that the resulting calculation times of RAM reorganisation operations are only dependent on the specified precision (|p| for GF(p) and m for GF(2m)), the word width |w| parameter for which the core variation has been generated and the resulting RAM width parameter |r| with |r|=4·|w|. The operations CopyH2V, CopyH2H, and CopyV2H exhibit the same computation time, whereas the operation CopyV2V will be performed in less clock cycles.Table 3
Core RAM copy operations computation time in clock cycles (CC).
G F ( p ) G F ( 2 m ) CCCopyH2V ( | p | / | w | ) + 3 ( m / | w | ) + 3  CCCopyV2V ( | p | / | r | ) + 2 ( m / | r | ) + 2  CCCopyH2H ( | p | / | w | ) + 3 ( m / | w | ) + 3  CCCopyV2H ( | p | / | w | ) + 3 ( m / | w | ) + 3The computing time formulas of prime field core operations given in clock cycles are listed in Table4.Table 4
CoreGF(p) operations computation time in clock cycles (CC).
G F ( p ) CCMontMult_bGF(p) | p | - k k ⋅ e + k + e + 4  CCMontMult_wGF(p) | p | - k k ⋅ e + k + 3 ⋅ e + 4  CCMontRGF(p) ( | p | / | w | ) + 3  CCMontR2_bGF(p) 2 ⋅ ( ( | p | / | w | ) + 2 ) + 1 + x ⋅ ( C C C o p y H 2 V - 1 ) + y ⋅ ( C C M o n t M u l t _ b G F ( p ) - 1 ) + 1  CCMontR2_wGF(p) 2 ⋅ ( ( | p | / | w | ) + 2 ) + 2 ⋅ ( | p | / | w | ) + 3 + x ⋅ ( C C C o p y H 2 V - 1 ) + y ⋅ ( C C M o n t M u l t _ w G F ( p ) - 1 ) + 1  CCMontExp_bGF(p) [ ( | p | / | w | ) ⋅ ( | w | + 2 ) ] + ( C C C o p y V 2 V - 1 ) + [ 2 ⋅ ( C C M o n t M u l t _ b G F ( p ) - 1 ) ]  CCMontExp_wGF(p) [ ( | p | / | w | ) ] + [ ( | p | / | w | ) ⋅ | w | - | p | + 3 ] + [ 2 ⋅ ( | p | - 2 ) ⋅ ( C C M o n t M u l t _ w G F ( p ) - 1 ) ] + [ ( | p | - 2 ) ⋅ ( C C C o p y V 2 V - 1 ) ] + [ ( | p | - 3 ) ⋅ ( C C C o p y H 2 V - 1 ) ] + 1  CCModAdd_bGF(p) ( | p | / | w | ) + 4  CCModAdd_wGF(p) 3 ⋅ ( | p | / | w | ) + 6  CCModSub_bGF(p) ( | p | / | w | ) + 4  CCModSub_wGF(p) 2 ⋅ ( | p | / | w | ) + 4  CCModSub_awGF(p) 3 ⋅ ( | p | / | w | ) + 6The computation time of theMontMult operation in GF(p) depends on the specified precision |p|, the number of active processing units k as well as the number of words e=⌈(|p|/|w|)⌉+1 running through the pipeline. In order to specify lower and upper computation times a best case and worst case formula is given. In the best case the carry-out bit of the CLA adder after reuniting TS and TC words is not set, the comparator only has to evaluate the most significant word, and a modular subtraction is not necessary. In the worst case the carry-out bit of the CLA adder is also not set but the comparator has to evaluate all words and a reduction of the resulting value is necessary.TheMontR operation in GF(p) only depends on the chosen precision |p| and specified word width |w| parameters.For theMontR2 operation computation time a best case and worst case formula is given. In the best case, after the shift operation, the comparator will only evaluate one word and an initial modular subtraction operation is not necessary. For the involved Montgomery Multiplication operations the best case formula is used. In the worst case, after the shift operation the comparator has to evaluate all words and decide that an initial modular subtraction operation is needed. For the involved Montgomery Multiplication operations the worst case formula is used. The amount x of CopyH2V and y of MontMult operations depends on the chosen precision. Table 5 lists the values for all supported GF(p) precisions.Table 5
Precision-dependent values ofx and y for GF(p)MontR2 operation.
192 224 256 320 384 448 512 x 7 6 8 7 8 7 9 y 8 11 8 10 9 12 9  768 1024 1536 2048 3072 4096  x 9 10 10 11 11 12 y 10 10 11 11 12 12For theMontExp operation, computation time in a best case and worst case formula is given. In the best case the exponent operand is 3; therefore only two Montgomery Multiplications and one CopyV2V operation is necessary. For the involved Montgomery Multiplication operations the best case formula is used. In the worst case the exponent is assumed to be 2(|p|-1); therefore 2·(|p|-2)×MontMult, (|p|-2)×CopyV2V and (|p|-3)×CopyH2V operations have to be performed. For the involved Montgomery Multiplication operations the worst case formula is used.For theModAdd operation computation time a best case and worst case formula is given. In the best case, after the modular addition the CLA adder carry-out bit will not be set, the comparator will only have to evaluate one word and an additional modular subtraction is not needed. In the worst case the CLA adder carry-out bit will also not be set, but the comparator will have to evaluate all words to decide that an additional modular subtraction is necessary.For theModSub operation computation time a best case, worst case, and absolute worst case formula is given. In the best case, after the modular subtraction the CLA adder carry-out bit will not be set, the comparator will only have to evaluate one word and an additional modular subtraction is not needed. In the worst case, after the modular subtraction the CLA adder carry-out bit will be set and a modular addition must be performed. In the absolute worst case after the modular subtraction the CLA adder carry-out bit will not be set, the comparator will evaluate all words, and an additional modular subtraction step is necessary. Note that this will only occur if the resulting value after the first subtraction operation will be identical to the modulus, which under normal operation conditions will not be the case.The prime fieldMontMult1 operation is identical to the GF(p)MontMult operation; therefore the same best and worst case formulas apply.The computing time formulas of binary field core operations given in clock cycles are listed in Table6.Table 6
CoreGF(2m) operations computation time in clock cycles (CC).
Operation G F ( 2 m ) CCMontMultGF(2m) m - ( m  m o d  k ) k ⋅ e + ( m  m o d  k ) + e + 4  CCMontRGF(2m) ( m / | w | ) + 3  CCMontR2_bGF(2m) ( m + 1 ) ⋅ ( ( m / | w | ) + 2 ) + m + 1  CCMontR2_wGF(2m) ( m + 1 ) ⋅ ( ( m / | w | ) + 2 ) + m ⋅ ( m / | w | ) + m + 1  CCMontExp_bGF(2m) [ ( m / | w | ) ⋅ ( | w | + 2 ) ] + ( C C C o p y V 2 V - 1 ) + [ 2 ⋅ ( C C M o n t M u l t G F ( 2 m ) ) ]  CCMontExp_wGF(2m) [ ( m / | w | ) ] + [ ( m / | w | ) ⋅ | w | - m + 3 ] + [ 2 ⋅ ( m - 2 ) ⋅ ( C C M o n t M u l t G F ( 2 m ) - 1 ) ] + [ ( m - 2 ) ⋅ ( C C C o p y V 2 V - 1 ) ] + [ ( m - 3 ) ⋅ ( C C C o p y H 2 V - 1 ) ] + 1  CCModAdd_bGF(2m) ( m / | w | ) + 4  CCModAdd_awGF(2m) 3 ⋅ ( m / | w | ) + 6The computation time of theMontMult operation in GF(2m) depends on the specified precision parameter m, the number of active processing units k, and the number of words e=⌈(m/|w|)⌉+1 running through the pipeline. Since the additions in GF(2m) are simple XOR-operations and the most significant bit of the resulting value will never be set after calculation only one formula is given.While the determination of the Montgomery Parameterr in GF(2m) differs from the calculation rule for GF(p) it also only depends on the chosen precision m and specified word width |w| parameters.TheMontR2 operation in GF(2m) is based on shifts and possible modular additions whenever the most significant bit of the intermediate value will be set after a shift. The amount of modular additions depends on the Montgomery Parameter r which itself depends on the irreducible polynomial. In order to specify lower and upper computation times a best case and worst case formula is given. The best case assumes that no modular addition operation is required at all, whereas the worst case assumes that a modular addition operation is required after each shift operation.For theMontExp operation computation time a best case and worst case formula is given. In the best case the exponent operand is 3 therefore only two Montgomery Multiplications and one CopyV2V operation is necessary. In the worst case the exponent is assumed to be 2(m-1) therefore 2·(m-2)×MontMult, (m-2)×CopyV2V and (m-3)×CopyH2V operations are required.For theModAdd operation computation time a best case and absolute worst case formula is given. In the best case the comparator will only have to evaluate one word. In the absolute worst case the comparator will have to evaluate all words to decide that an additional modular addition is necessary. Note that this will only occur if the resulting value after the first addition operation will be identical to the modulus polynomial, which under normal operation conditions will not be the case.The binary fieldMontMult1 operation is identical to the GF(2m)MontMult operation; therefore the same formula applies.


### 6.2. Core Variations

Depending on the needs, in terms of performance, area consumption, supported precisions, and the interfacing structure, different variations of the core can be generated by defining the parametersMAX_PRECISION_WIDTH,WORD_WIDTH andMAX_NUM_PUS. Table 7 lists the resulting number of words e and the possible number of processing units k for the supported prime field precisions |p| and typical word widths |w| of 16, 32 and 64 bit.Table 7
Number of wordse and amount of possible processing units k depending on precision |p| and word width |w| for GF(p).
GF(p) | w | = 16 | w | = 32 | w | = 64 |p|=192 e = 13  k=2,4,8 e = 7  k=2,4 e = 4  k=2  |p|=224 e = 15  k=2,4,8 e = 8  k=2,4 e = 5  k=2  |p|=256 e = 17  k=2,4,8 e = 9  k=2,4 e = 5  k=2  |p|=320 e = 21  k=2,4,  8,16 e = 11  k=2,4,8 e = 6  k=2,4  |p|=384 e = 25  k=2,4,  8,16 e = 13  k=2,4,8 e = 7  k=2,4  |p|=448 e = 29  k=2,4,  8,16 e = 15  k=2,4,8 e = 8  k=2,4  |p|=512 e = 33  k=2,4,  8,16 e = 17  k=2,4,8 e = 9  k=2,4  |p|=768 e = 49  k=2,4,8,  16,32 e = 25  k=2,4,  8,16 e = 13  k=2,4,8  |p|=1024 e = 65  k=2,4,8,  16,32 e = 33  k=2,4,8,16 e = 17  k=2,4,8  |p|=1536 e = 97  k=2,4,8,  16,32,64 e = 49  k=2,4,8,  16,32 e = 25  k=2,4,  8,16  |p|=2048 e = 129  k=2,4,8,  16,32,64 e = 65  k=2,4,8,  16,32 e = 33  k=2,4,  8,16  |p|=3072 e = 193  k=2,4,8,  16,32,64 e = 97  k=2,4,8,  16,32,64 e = 49  k=2,4,8,  16,32  |p|=4096 e = 257  k=2,4,8,  16,32,64 e = 129  k=2,4,8,  16,32,64 e = 65  k=2,4,8,  16,32In contrast, Table8 lists the resulting number of words e and the number of possible processing units k for the supported binary field precisions m and typical word widths |w| of 16, 32, and 64 bits. Note that the number of possible processing units for binary fields within the defined core is subjected to a further constraint. Once all bits of A operand have been processed the remaining processing units in the pipeline must be bypassed and the TS and TC words must be directly fed into the CLA adder. Since the result of the CLA adder will be written back to RAM but remaining words must still be read from RAM and fed into the first processing unit, the RAM source and destination signals must never address the same memory location at one time. Therefore the equation (k-(mmodk))modk must hold true to (k-(mmodk))≡0modk, meaning that no processing unit will be bypassed, or (k-(mmodk))≡1modk, meaning that the very last processing unit will be bypassed at the last cycle of A operand bits.Table 8
Number of wordse and amount of possible processing units k depending on precision m and word width |w| for GF(2m).
GF(2m) | w | = 16 | w | = 32 | w | = 64 m=131 e = 10 e=6 e = 4 k=2,4 k=2,4 k = 2  m=163 e = 12 e=7 e = 4 k=2,4 k=2,4 k = 2  m=176 e = 12 e=7 e=4 k=2,4,8 k=2,4 k=2  m=191 e = 13 e = 7 e = 4 k = 2,4 , 8 k=2,4 k = 2  m=193 e = 14 e=8 e = 5 k=2 k=2 k = 2  m=208 e = 14 e=8 e = 5 k=2,4,8 k=2,4 k = 2  m=233 e=16 e=9 e = 5 k=2 k=2 k = 2  m=239 e = 16 e=9 e=5 k=2,4,8 k=2,4 k = 2  m=272 e = 18 e = 10 e = 6 k = 2,4 , 8,16 k = 2,4 , 8 k = 2,4  m=283 e = 19 e = 10 e = 6 k=2,4 k=2,4 k=2,4  m=304 e = 20 e = 11 e = 6 k=2,4,8,16 k=2,4,8 k=2,4  m=359 e = 24 e = 13 e = 7 k=2,4,8 k=2,4,8 k=2,4  m=368 e = 24 e = 13 e = 7 k=2,4,8,16 k=2,4,8 k=2,4  m=409 e = 27 e = 14 e = 8 k=2 k=2 k = 2  m=431 e = 28 e = 15 e = 8 k = 2,4 , 8,16 k = 2,4 , 8 k = 2,4  m=571 e = 37 e = 19 e = 10 k = 2,4 k = 2,4 k = 2,4


### 6.3. Core Hardware Footprint

Since all components of the design consist of simple logic elements, the proposed arithmetic core is vendor-neutral. In order to estimate the hardware footprint of different core implementations the design variations have been compiled on Altera and Xilinx FPGAs. Table9 lists the amount of total logic elements and comprised logic registers for varied values ofWORD_WIDTH (|w|) andMAX_NUM_PUS generated for an Altera Cyclone IV (EP4CE115F29C9L) device featuring 114,480 logic elements and 3,981,312 memory bits.Table 9
Amount of logic elements and logic registers for different core variations (Altera Cyclone IV).
|w| MAX_NUM_PUS Logic Elements Registers 16 2 3,128 706 16 4 3,523 904 16 8 4,344 1,300 16 16 5,960 2,092 16 32 9,198 3,676 16 64 15,568 6,844  32 2 4,086 988 32 4 4,721 1,314 32 8 5,935 1,966 32 16 8,473 3,270 32 32 13,498 5,878 32 64 23,484 11,094  64 2 6,114 1,557 64 4 7,151 2,139 64 8 9,346 3,303 64 16 13,624 5,631 64 32 22,113 10,287Table10 lists the amount of total logic elements and comprised logic registers for varied values ofWORD_WIDTH (|w|) andMAX_NUM_PUS generated for an Xilinx XC7Z020 (xc7z020clg484-1) device featuring 53,200 logic elements and 106,400 registers. The resulting values demonstrate that the design can compete with other proposed designs, for instance, the one compared in [14, 15]. Furthermore instead of being restricted to only one cryptographic application, the core can handle various algorithms. According to the needs, in terms of area, a suitable solution for a specific implementation can be chosen. The choice will have an impact on power consumption and computing time.Table 10
Amount of logic elements and logic registers for different core variations (Xilinx XC7Z020).
|w| MAX_NUM_PUS Logic Elements Registers 16 2 2,587 755 16 4 2,874 956 16 8 3,467 1,352 16 16 4,623 2,146 16 32 7,208 3,724 16 64 11,934 6,895  32 2 3,367 1,114 32 4 4,014 1,429 32 8 4,694 2,082 32 16 6,645 3,386 32 32 10,177 5,999 32 64 17,770 11,222  64 2 5,098 1,833 64 4 5,869 2,421 64 8 7,585 3,591 64 16 10,654 5,928 64 32 16,871 10,624


### 6.4. Core Power Estimation

In order to evaluate the suitability of the proposed core for the application in the IoT area, a power estimation has been conducted using two common frequencies of 100 MHz and 200 MHz for various core variations. Timing analysis yields that the design can reliably be operated with these frequencies. The power consumption characteristics have been derived by applying the PowerPlay Power Analyzer Tool of the Quartus Prime IDE to the final design using default settings of a power toggle rate as well as a power input I/O toggle rate of12.5%, using a vectorless estimation and a board temperature of 25°C. Table 11 lists the Total Thermal Power Dissipation values for variedWORD_WIDTH (|w|) andMAX_NUM_PUS parameters generated for the Altera Cyclone IV (EP4CE115F29C9L) device. The values are comparable to the ones given in [24] for RSA calculation.Table 11
Total Thermal Power Dissipation (TTPD) values for different core variations (Altera Cyclone IV).
|w| MAX_NUM_PUS TTPD 100 MHz TTPD 200 MHz 16 2 237.36 m W 266.38 m W 16 4 239.72 m W 297.73 m W 16 8 245.97 m W 304.40 m W 16 16 261.07 m W 358.22 m W 16 32 289.61 m W 389.32 m W 16 64 358.76 m W 549.60 m W  32 2 287.18 m W 362.94 m W 32 4 294.21 m W 375.02 m W 32 8 311.36 m W 401.65 m W 32 16 343.68 m W 454.94 m W 32 32 398.65 m W 568.00 m W 32 64 490.90 m W 760.71 m WFurthermore it has to be mentioned that the optimization mode in the compiler settings was set to balanced and no specific compiler optimizations regarding power have been turned on. The results show that the core is quite suitable for applications which have special constraints regarding power consumption. According to such needs as well as the desired clock frequency a suitable variation can be implemented. The choice will have an impact on computing time and hardware footprint.


### 6.5. Core Reference Implementation

For the reference implementation a word width ofWORD_WIDTH = 32 bit was chosen and the maximum number of processing units of the pipeline was set toMAX_NUM_PUS = 32. The maximum supported precision width parameterMAX_PRECISION_WIDTH was set to 4096 leading to a RAM consisting of 28,672 bits. Table 12 lists the computation time in clock cycles of the reference implementation for RSA application. For RSA public-key operations best case and worst case computation times are given under the assumption that the public exponent is e=0x10001. Therefore during the MontExp operation a total of 17×MontMult, 15×CopyH2V and 1×CopyV2V operations will be performed. Since the private exponent is different for varied RSA keys only worst case computation times for the supported precision widths are given. The worst case RSA private key and CRT-accelerated private key computation times assume the worst case clock cycle times of the underlying operations given in previous section.Table 12
Core reference implementation RSA computation times.
| p | = 2048 | p | = 3072 | p | = 4096 CCRSA_pub 134,128 302,309 529,783  CCRSA_priv 17,925,156 59,094,721 138,504,443  CCCRT-RSA 9,194,091 15,667,698 36,131,248Table13 lists the worst computation times in clock cycles of the reference implementation for Miller-Rabin prime testing application for one iteration. Note that the most time consuming operation is part one of the outer loop of Algorithm 2 which will always be performed for each iteration. Depending on the evaluation of the result it might be necessary to execute part two of the outer loop. Furthermore depending on the structure of the prime in question it might be necessary to execute part one and two of the inner loop multiple times.Table 13
Core reference implementation Miller-Rabin computation times.
| p | = 512 | p | = 768 | p | = 1024 CCMR_o1 1,167,529 1,969,583 4,534,869 CCMR_o2 148 212 276 CCMR_i1 1,246 1,430 2,406 CCMR_i2 148 212 276  | p | = 1536 | p | = 2048 | p | = 3072  CCMR_o1 7,720,993 17,868,205 58,960,069 CCMR_o2 404 532 788 CCMR_i1 2,790 4,726 10,134 CCMR_i2 404 532 788  | p | = 4096  CCMR_o1 138,267,613 CCMR_o2 1,044 CCMR_i1 17,590 CCMR_i2 1,044Table14 lists the computation time in clock cycles of the reference implementation for prime field EC operations for all supported precision widths. The Affine-to-Jacobi Transformation step requires a precision dependent number of clock cycles. For the remaining steps worst case clock cycle times are given. For the Point Multiplication operation an absolute worst case computation time is stated in which a theoretical scalar is hypothesized to be 2p-1, therefore a maximum of (p-1) Point Doubling and (p-1) Point Addition operations would be necessary assuming a simple double and add algorithm.Table 14
Core reference implementation prime field EC computation times.
| p | = 192 | p | = 224 | p | = 256 CCEC_prep 5,252 8,281 8,736 CCEC_mont_doub 742 972 1,234 CCEC_mont_add 1,468 1,928 2,452 CCEC_a2j 22 24 26 CCEC_point_val 1,577 2,050 2,587 CCEC_point_doub 5,613 7,351 9,329 CCEC_point_add 6,434 8,412 10,662 CCEC_point_mult 2,288,930 3,499,386 5,077,714 CCEC_j2a 139,233 213,732 311,079 CCEC_demont 734 964 1,226  | p | = 320 | p | = 384 | p | = 512  CCEC_prep 7,938 10,357 17,575 CCEC_mont_doub 984 1,364 2,318 CCEC_mont_add 1,948 2,708 4,612 CCEC_a2j 31 35 44 CCEC_point_val 2,109 2,895 4,851 CCEC_point_doub 7,465 10,341 17,533 CCEC_point_add 8,566 11,842 20,026 CCEC_point_mult 5,097,858 8,473,906 19,155,090 CCEC_j2a 307,884 514,610 1,172,029 CCEC_demont 974 1,354 2,306


## 6.1. Core Computation Time Formulas

Table3 lists the RAM copy operations computation time formulas in clock cycles of the proposed core. Note that the resulting calculation times of RAM reorganisation operations are only dependent on the specified precision (|p| for GF(p) and m for GF(2m)), the word width |w| parameter for which the core variation has been generated and the resulting RAM width parameter |r| with |r|=4·|w|. The operations CopyH2V, CopyH2H, and CopyV2H exhibit the same computation time, whereas the operation CopyV2V will be performed in less clock cycles.Table 3
Core RAM copy operations computation time in clock cycles (CC).
G F ( p ) G F ( 2 m ) CCCopyH2V ( | p | / | w | ) + 3 ( m / | w | ) + 3  CCCopyV2V ( | p | / | r | ) + 2 ( m / | r | ) + 2  CCCopyH2H ( | p | / | w | ) + 3 ( m / | w | ) + 3  CCCopyV2H ( | p | / | w | ) + 3 ( m / | w | ) + 3The computing time formulas of prime field core operations given in clock cycles are listed in Table4.Table 4
CoreGF(p) operations computation time in clock cycles (CC).
G F ( p ) CCMontMult_bGF(p) | p | - k k ⋅ e + k + e + 4  CCMontMult_wGF(p) | p | - k k ⋅ e + k + 3 ⋅ e + 4  CCMontRGF(p) ( | p | / | w | ) + 3  CCMontR2_bGF(p) 2 ⋅ ( ( | p | / | w | ) + 2 ) + 1 + x ⋅ ( C C C o p y H 2 V - 1 ) + y ⋅ ( C C M o n t M u l t _ b G F ( p ) - 1 ) + 1  CCMontR2_wGF(p) 2 ⋅ ( ( | p | / | w | ) + 2 ) + 2 ⋅ ( | p | / | w | ) + 3 + x ⋅ ( C C C o p y H 2 V - 1 ) + y ⋅ ( C C M o n t M u l t _ w G F ( p ) - 1 ) + 1  CCMontExp_bGF(p) [ ( | p | / | w | ) ⋅ ( | w | + 2 ) ] + ( C C C o p y V 2 V - 1 ) + [ 2 ⋅ ( C C M o n t M u l t _ b G F ( p ) - 1 ) ]  CCMontExp_wGF(p) [ ( | p | / | w | ) ] + [ ( | p | / | w | ) ⋅ | w | - | p | + 3 ] + [ 2 ⋅ ( | p | - 2 ) ⋅ ( C C M o n t M u l t _ w G F ( p ) - 1 ) ] + [ ( | p | - 2 ) ⋅ ( C C C o p y V 2 V - 1 ) ] + [ ( | p | - 3 ) ⋅ ( C C C o p y H 2 V - 1 ) ] + 1  CCModAdd_bGF(p) ( | p | / | w | ) + 4  CCModAdd_wGF(p) 3 ⋅ ( | p | / | w | ) + 6  CCModSub_bGF(p) ( | p | / | w | ) + 4  CCModSub_wGF(p) 2 ⋅ ( | p | / | w | ) + 4  CCModSub_awGF(p) 3 ⋅ ( | p | / | w | ) + 6The computation time of theMontMult operation in GF(p) depends on the specified precision |p|, the number of active processing units k as well as the number of words e=⌈(|p|/|w|)⌉+1 running through the pipeline. In order to specify lower and upper computation times a best case and worst case formula is given. In the best case the carry-out bit of the CLA adder after reuniting TS and TC words is not set, the comparator only has to evaluate the most significant word, and a modular subtraction is not necessary. In the worst case the carry-out bit of the CLA adder is also not set but the comparator has to evaluate all words and a reduction of the resulting value is necessary.TheMontR operation in GF(p) only depends on the chosen precision |p| and specified word width |w| parameters.For theMontR2 operation computation time a best case and worst case formula is given. In the best case, after the shift operation, the comparator will only evaluate one word and an initial modular subtraction operation is not necessary. For the involved Montgomery Multiplication operations the best case formula is used. In the worst case, after the shift operation the comparator has to evaluate all words and decide that an initial modular subtraction operation is needed. For the involved Montgomery Multiplication operations the worst case formula is used. The amount x of CopyH2V and y of MontMult operations depends on the chosen precision. Table 5 lists the values for all supported GF(p) precisions.Table 5
Precision-dependent values ofx and y for GF(p)MontR2 operation.
192 224 256 320 384 448 512 x 7 6 8 7 8 7 9 y 8 11 8 10 9 12 9  768 1024 1536 2048 3072 4096  x 9 10 10 11 11 12 y 10 10 11 11 12 12For theMontExp operation, computation time in a best case and worst case formula is given. In the best case the exponent operand is 3; therefore only two Montgomery Multiplications and one CopyV2V operation is necessary. For the involved Montgomery Multiplication operations the best case formula is used. In the worst case the exponent is assumed to be 2(|p|-1); therefore 2·(|p|-2)×MontMult, (|p|-2)×CopyV2V and (|p|-3)×CopyH2V operations have to be performed. For the involved Montgomery Multiplication operations the worst case formula is used.For theModAdd operation computation time a best case and worst case formula is given. In the best case, after the modular addition the CLA adder carry-out bit will not be set, the comparator will only have to evaluate one word and an additional modular subtraction is not needed. In the worst case the CLA adder carry-out bit will also not be set, but the comparator will have to evaluate all words to decide that an additional modular subtraction is necessary.For theModSub operation computation time a best case, worst case, and absolute worst case formula is given. In the best case, after the modular subtraction the CLA adder carry-out bit will not be set, the comparator will only have to evaluate one word and an additional modular subtraction is not needed. In the worst case, after the modular subtraction the CLA adder carry-out bit will be set and a modular addition must be performed. In the absolute worst case after the modular subtraction the CLA adder carry-out bit will not be set, the comparator will evaluate all words, and an additional modular subtraction step is necessary. Note that this will only occur if the resulting value after the first subtraction operation will be identical to the modulus, which under normal operation conditions will not be the case.The prime fieldMontMult1 operation is identical to the GF(p)MontMult operation; therefore the same best and worst case formulas apply.The computing time formulas of binary field core operations given in clock cycles are listed in Table6.Table 6
CoreGF(2m) operations computation time in clock cycles (CC).
Operation G F ( 2 m ) CCMontMultGF(2m) m - ( m  m o d  k ) k ⋅ e + ( m  m o d  k ) + e + 4  CCMontRGF(2m) ( m / | w | ) + 3  CCMontR2_bGF(2m) ( m + 1 ) ⋅ ( ( m / | w | ) + 2 ) + m + 1  CCMontR2_wGF(2m) ( m + 1 ) ⋅ ( ( m / | w | ) + 2 ) + m ⋅ ( m / | w | ) + m + 1  CCMontExp_bGF(2m) [ ( m / | w | ) ⋅ ( | w | + 2 ) ] + ( C C C o p y V 2 V - 1 ) + [ 2 ⋅ ( C C M o n t M u l t G F ( 2 m ) ) ]  CCMontExp_wGF(2m) [ ( m / | w | ) ] + [ ( m / | w | ) ⋅ | w | - m + 3 ] + [ 2 ⋅ ( m - 2 ) ⋅ ( C C M o n t M u l t G F ( 2 m ) - 1 ) ] + [ ( m - 2 ) ⋅ ( C C C o p y V 2 V - 1 ) ] + [ ( m - 3 ) ⋅ ( C C C o p y H 2 V - 1 ) ] + 1  CCModAdd_bGF(2m) ( m / | w | ) + 4  CCModAdd_awGF(2m) 3 ⋅ ( m / | w | ) + 6The computation time of theMontMult operation in GF(2m) depends on the specified precision parameter m, the number of active processing units k, and the number of words e=⌈(m/|w|)⌉+1 running through the pipeline. Since the additions in GF(2m) are simple XOR-operations and the most significant bit of the resulting value will never be set after calculation only one formula is given.While the determination of the Montgomery Parameterr in GF(2m) differs from the calculation rule for GF(p) it also only depends on the chosen precision m and specified word width |w| parameters.TheMontR2 operation in GF(2m) is based on shifts and possible modular additions whenever the most significant bit of the intermediate value will be set after a shift. The amount of modular additions depends on the Montgomery Parameter r which itself depends on the irreducible polynomial. In order to specify lower and upper computation times a best case and worst case formula is given. The best case assumes that no modular addition operation is required at all, whereas the worst case assumes that a modular addition operation is required after each shift operation.For theMontExp operation computation time a best case and worst case formula is given. In the best case the exponent operand is 3 therefore only two Montgomery Multiplications and one CopyV2V operation is necessary. In the worst case the exponent is assumed to be 2(m-1) therefore 2·(m-2)×MontMult, (m-2)×CopyV2V and (m-3)×CopyH2V operations are required.For theModAdd operation computation time a best case and absolute worst case formula is given. In the best case the comparator will only have to evaluate one word. In the absolute worst case the comparator will have to evaluate all words to decide that an additional modular addition is necessary. Note that this will only occur if the resulting value after the first addition operation will be identical to the modulus polynomial, which under normal operation conditions will not be the case.The binary fieldMontMult1 operation is identical to the GF(2m)MontMult operation; therefore the same formula applies.


## 6.2. Core Variations

Depending on the needs, in terms of performance, area consumption, supported precisions, and the interfacing structure, different variations of the core can be generated by defining the parametersMAX_PRECISION_WIDTH,WORD_WIDTH andMAX_NUM_PUS. Table 7 lists the resulting number of words e and the possible number of processing units k for the supported prime field precisions |p| and typical word widths |w| of 16, 32 and 64 bit.Table 7
Number of wordse and amount of possible processing units k depending on precision |p| and word width |w| for GF(p).
GF(p) | w | = 16 | w | = 32 | w | = 64 |p|=192 e = 13  k=2,4,8 e = 7  k=2,4 e = 4  k=2  |p|=224 e = 15  k=2,4,8 e = 8  k=2,4 e = 5  k=2  |p|=256 e = 17  k=2,4,8 e = 9  k=2,4 e = 5  k=2  |p|=320 e = 21  k=2,4,  8,16 e = 11  k=2,4,8 e = 6  k=2,4  |p|=384 e = 25  k=2,4,  8,16 e = 13  k=2,4,8 e = 7  k=2,4  |p|=448 e = 29  k=2,4,  8,16 e = 15  k=2,4,8 e = 8  k=2,4  |p|=512 e = 33  k=2,4,  8,16 e = 17  k=2,4,8 e = 9  k=2,4  |p|=768 e = 49  k=2,4,8,  16,32 e = 25  k=2,4,  8,16 e = 13  k=2,4,8  |p|=1024 e = 65  k=2,4,8,  16,32 e = 33  k=2,4,8,16 e = 17  k=2,4,8  |p|=1536 e = 97  k=2,4,8,  16,32,64 e = 49  k=2,4,8,  16,32 e = 25  k=2,4,  8,16  |p|=2048 e = 129  k=2,4,8,  16,32,64 e = 65  k=2,4,8,  16,32 e = 33  k=2,4,  8,16  |p|=3072 e = 193  k=2,4,8,  16,32,64 e = 97  k=2,4,8,  16,32,64 e = 49  k=2,4,8,  16,32  |p|=4096 e = 257  k=2,4,8,  16,32,64 e = 129  k=2,4,8,  16,32,64 e = 65  k=2,4,8,  16,32In contrast, Table8 lists the resulting number of words e and the number of possible processing units k for the supported binary field precisions m and typical word widths |w| of 16, 32, and 64 bits. Note that the number of possible processing units for binary fields within the defined core is subjected to a further constraint. Once all bits of A operand have been processed the remaining processing units in the pipeline must be bypassed and the TS and TC words must be directly fed into the CLA adder. Since the result of the CLA adder will be written back to RAM but remaining words must still be read from RAM and fed into the first processing unit, the RAM source and destination signals must never address the same memory location at one time. Therefore the equation (k-(mmodk))modk must hold true to (k-(mmodk))≡0modk, meaning that no processing unit will be bypassed, or (k-(mmodk))≡1modk, meaning that the very last processing unit will be bypassed at the last cycle of A operand bits.Table 8
Number of wordse and amount of possible processing units k depending on precision m and word width |w| for GF(2m).
GF(2m) | w | = 16 | w | = 32 | w | = 64 m=131 e = 10 e=6 e = 4 k=2,4 k=2,4 k = 2  m=163 e = 12 e=7 e = 4 k=2,4 k=2,4 k = 2  m=176 e = 12 e=7 e=4 k=2,4,8 k=2,4 k=2  m=191 e = 13 e = 7 e = 4 k = 2,4 , 8 k=2,4 k = 2  m=193 e = 14 e=8 e = 5 k=2 k=2 k = 2  m=208 e = 14 e=8 e = 5 k=2,4,8 k=2,4 k = 2  m=233 e=16 e=9 e = 5 k=2 k=2 k = 2  m=239 e = 16 e=9 e=5 k=2,4,8 k=2,4 k = 2  m=272 e = 18 e = 10 e = 6 k = 2,4 , 8,16 k = 2,4 , 8 k = 2,4  m=283 e = 19 e = 10 e = 6 k=2,4 k=2,4 k=2,4  m=304 e = 20 e = 11 e = 6 k=2,4,8,16 k=2,4,8 k=2,4  m=359 e = 24 e = 13 e = 7 k=2,4,8 k=2,4,8 k=2,4  m=368 e = 24 e = 13 e = 7 k=2,4,8,16 k=2,4,8 k=2,4  m=409 e = 27 e = 14 e = 8 k=2 k=2 k = 2  m=431 e = 28 e = 15 e = 8 k = 2,4 , 8,16 k = 2,4 , 8 k = 2,4  m=571 e = 37 e = 19 e = 10 k = 2,4 k = 2,4 k = 2,4


## 6.3. Core Hardware Footprint

Since all components of the design consist of simple logic elements, the proposed arithmetic core is vendor-neutral. In order to estimate the hardware footprint of different core implementations the design variations have been compiled on Altera and Xilinx FPGAs. Table9 lists the amount of total logic elements and comprised logic registers for varied values ofWORD_WIDTH (|w|) andMAX_NUM_PUS generated for an Altera Cyclone IV (EP4CE115F29C9L) device featuring 114,480 logic elements and 3,981,312 memory bits.Table 9
Amount of logic elements and logic registers for different core variations (Altera Cyclone IV).
|w| MAX_NUM_PUS Logic Elements Registers 16 2 3,128 706 16 4 3,523 904 16 8 4,344 1,300 16 16 5,960 2,092 16 32 9,198 3,676 16 64 15,568 6,844  32 2 4,086 988 32 4 4,721 1,314 32 8 5,935 1,966 32 16 8,473 3,270 32 32 13,498 5,878 32 64 23,484 11,094  64 2 6,114 1,557 64 4 7,151 2,139 64 8 9,346 3,303 64 16 13,624 5,631 64 32 22,113 10,287Table10 lists the amount of total logic elements and comprised logic registers for varied values ofWORD_WIDTH (|w|) andMAX_NUM_PUS generated for an Xilinx XC7Z020 (xc7z020clg484-1) device featuring 53,200 logic elements and 106,400 registers. The resulting values demonstrate that the design can compete with other proposed designs, for instance, the one compared in [14, 15]. Furthermore instead of being restricted to only one cryptographic application, the core can handle various algorithms. According to the needs, in terms of area, a suitable solution for a specific implementation can be chosen. The choice will have an impact on power consumption and computing time.Table 10
Amount of logic elements and logic registers for different core variations (Xilinx XC7Z020).
|w| MAX_NUM_PUS Logic Elements Registers 16 2 2,587 755 16 4 2,874 956 16 8 3,467 1,352 16 16 4,623 2,146 16 32 7,208 3,724 16 64 11,934 6,895  32 2 3,367 1,114 32 4 4,014 1,429 32 8 4,694 2,082 32 16 6,645 3,386 32 32 10,177 5,999 32 64 17,770 11,222  64 2 5,098 1,833 64 4 5,869 2,421 64 8 7,585 3,591 64 16 10,654 5,928 64 32 16,871 10,624


## 6.4. Core Power Estimation

In order to evaluate the suitability of the proposed core for the application in the IoT area, a power estimation has been conducted using two common frequencies of 100 MHz and 200 MHz for various core variations. Timing analysis yields that the design can reliably be operated with these frequencies. The power consumption characteristics have been derived by applying the PowerPlay Power Analyzer Tool of the Quartus Prime IDE to the final design using default settings of a power toggle rate as well as a power input I/O toggle rate of12.5%, using a vectorless estimation and a board temperature of 25°C. Table 11 lists the Total Thermal Power Dissipation values for variedWORD_WIDTH (|w|) andMAX_NUM_PUS parameters generated for the Altera Cyclone IV (EP4CE115F29C9L) device. The values are comparable to the ones given in [24] for RSA calculation.Table 11
Total Thermal Power Dissipation (TTPD) values for different core variations (Altera Cyclone IV).
|w| MAX_NUM_PUS TTPD 100 MHz TTPD 200 MHz 16 2 237.36 m W 266.38 m W 16 4 239.72 m W 297.73 m W 16 8 245.97 m W 304.40 m W 16 16 261.07 m W 358.22 m W 16 32 289.61 m W 389.32 m W 16 64 358.76 m W 549.60 m W  32 2 287.18 m W 362.94 m W 32 4 294.21 m W 375.02 m W 32 8 311.36 m W 401.65 m W 32 16 343.68 m W 454.94 m W 32 32 398.65 m W 568.00 m W 32 64 490.90 m W 760.71 m WFurthermore it has to be mentioned that the optimization mode in the compiler settings was set to balanced and no specific compiler optimizations regarding power have been turned on. The results show that the core is quite suitable for applications which have special constraints regarding power consumption. According to such needs as well as the desired clock frequency a suitable variation can be implemented. The choice will have an impact on computing time and hardware footprint.


## 6.5. Core Reference Implementation

For the reference implementation a word width ofWORD_WIDTH = 32 bit was chosen and the maximum number of processing units of the pipeline was set toMAX_NUM_PUS = 32. The maximum supported precision width parameterMAX_PRECISION_WIDTH was set to 4096 leading to a RAM consisting of 28,672 bits. Table 12 lists the computation time in clock cycles of the reference implementation for RSA application. For RSA public-key operations best case and worst case computation times are given under the assumption that the public exponent is e=0x10001. Therefore during the MontExp operation a total of 17×MontMult, 15×CopyH2V and 1×CopyV2V operations will be performed. Since the private exponent is different for varied RSA keys only worst case computation times for the supported precision widths are given. The worst case RSA private key and CRT-accelerated private key computation times assume the worst case clock cycle times of the underlying operations given in previous section.Table 12
Core reference implementation RSA computation times.
| p | = 2048 | p | = 3072 | p | = 4096 CCRSA_pub 134,128 302,309 529,783  CCRSA_priv 17,925,156 59,094,721 138,504,443  CCCRT-RSA 9,194,091 15,667,698 36,131,248Table13 lists the worst computation times in clock cycles of the reference implementation for Miller-Rabin prime testing application for one iteration. Note that the most time consuming operation is part one of the outer loop of Algorithm 2 which will always be performed for each iteration. Depending on the evaluation of the result it might be necessary to execute part two of the outer loop. Furthermore depending on the structure of the prime in question it might be necessary to execute part one and two of the inner loop multiple times.Table 13
Core reference implementation Miller-Rabin computation times.
| p | = 512 | p | = 768 | p | = 1024 CCMR_o1 1,167,529 1,969,583 4,534,869 CCMR_o2 148 212 276 CCMR_i1 1,246 1,430 2,406 CCMR_i2 148 212 276  | p | = 1536 | p | = 2048 | p | = 3072  CCMR_o1 7,720,993 17,868,205 58,960,069 CCMR_o2 404 532 788 CCMR_i1 2,790 4,726 10,134 CCMR_i2 404 532 788  | p | = 4096  CCMR_o1 138,267,613 CCMR_o2 1,044 CCMR_i1 17,590 CCMR_i2 1,044Table14 lists the computation time in clock cycles of the reference implementation for prime field EC operations for all supported precision widths. The Affine-to-Jacobi Transformation step requires a precision dependent number of clock cycles. For the remaining steps worst case clock cycle times are given. For the Point Multiplication operation an absolute worst case computation time is stated in which a theoretical scalar is hypothesized to be 2p-1, therefore a maximum of (p-1) Point Doubling and (p-1) Point Addition operations would be necessary assuming a simple double and add algorithm.Table 14
Core reference implementation prime field EC computation times.
| p | = 192 | p | = 224 | p | = 256 CCEC_prep 5,252 8,281 8,736 CCEC_mont_doub 742 972 1,234 CCEC_mont_add 1,468 1,928 2,452 CCEC_a2j 22 24 26 CCEC_point_val 1,577 2,050 2,587 CCEC_point_doub 5,613 7,351 9,329 CCEC_point_add 6,434 8,412 10,662 CCEC_point_mult 2,288,930 3,499,386 5,077,714 CCEC_j2a 139,233 213,732 311,079 CCEC_demont 734 964 1,226  | p | = 320 | p | = 384 | p | = 512  CCEC_prep 7,938 10,357 17,575 CCEC_mont_doub 984 1,364 2,318 CCEC_mont_add 1,948 2,708 4,612 CCEC_a2j 31 35 44 CCEC_point_val 2,109 2,895 4,851 CCEC_point_doub 7,465 10,341 17,533 CCEC_point_add 8,566 11,842 20,026 CCEC_point_mult 5,097,858 8,473,906 19,155,090 CCEC_j2a 307,884 514,610 1,172,029 CCEC_demont 974 1,354 2,306


## 7. Conclusion and Future Work

A comprehensive adaptable hardware structure for efficient prime finite field and binary finite field arithmetic operations that expand the capabilities of single Montgomery Multiplier hardware designs has been proposed which allows carrying out cryptographic calculations for a large range of different algorithms all based on the same arithmetic unit operations with arbitrary parameters. The approach taken by the proposed core is to combine standard modulo addition / subtraction support with the capability of performing Montgomery Multiplications, full Montgomery Exponentiations, and the calculation of Montgomery Parametersr and r2 for arbitrary moduli, bringing together all required arithmetic operations for carrying out a wide range of cryptographic algorithms used today. Through the breakdown of these algorithms individual operation lists have been derived for the arithmetic unit rendering extra precomputations in software unnecessary.The given values of possible hardware footprint and power consumption for specific core variations allow choosing the proper configuration for a specific implementation. The reference implementation showed that with an internal RAM of merely 3.5 kB the core is capable of performing complete prime field and binary field EC operations for various precision widths of standardised curves. Furthermore the same core configuration is capable of performing (CRT-accelerated) RSA operations for typical precision widths required today, (safe) prime testing/generation, and Diffie-Hellman key exchange operations up to4096 bit precision widths. The design should further be optimized in terms of power consumption.However the type of implementation of some core operations, such as the Montgomery Multiplication and especially the Montgomery Exponentiation operation, necessitates additional security considerations, since the calculation times depend on the structure of the processed operands. This makes the design prone to side-channel attacks if security sensitive information, such as private keys, will be processed. But not all operations are critical and must be secured, such as the calculation of the Montgomery Parameters. Therefore during the writing of this article the core will be enhanced to provide a secure calculation bit within the command input word, which, if set, instructs the core to perform the specified arithmetic operation in a time-invariant fashion. In addition, special care has to be taken when defining core operation lists, for instance, for performing elliptic curve Point Multiplication operations. Descriptions performing in a fixed amount of time, e.g., the Montgomery ladder [25], mitigating the risk of timing, and power analysis attacks must be chosen.



---

*Source: 4983404-2018-06-21.xml*