Montgomery multiplication with longer operand length

This invention relates generally to the art of performing arithmetic operations, and more particularly to the operation known as Montgomery multiplication. The Montgomery multiplication in the word choice used here is a modular multiplication, the result of which is the product of two factors multiplied by the inverse of a power of two.

The invention is particularly suitable for use in cryptographic calculations, such as those carried out by portable data carriers. As used herein, a portable data carrier may be, for example, a smart card or a chip module in a variety of designs, or any other resource limited system.

In the field of cryptography, modular multiplications are performed, for example, in the RSA method described in U.S. Patent 4,405,829. In this method, a modular power calculation of a value to be encrypted or decrypted takes place with respect to a module which is the product of two large primes. The modular power calculation usually involves a sequence of modular multiplications, eg Montgomery multiplications. Since the security of the RSA method is based on the difficulty of factoring the module into the two primes without additional information, the module should have the largest possible number of digits.

From US Pat. No. 5,961,578 a method for efficient execution of Montgomery multiplications is known which is suitable for use in cryptographic coprocessors. Semiconductor chips for portable data carriers having a coprocessor designed according to this patent are available under the name "AE4" from Hitachi, Ltd., Tokyo, Japan. The hardware support provided by this coprocessor for Montgomery multiplication, however, is limited to operands with a bit length of 1024 bits.

Also in other coprocessors is usually a fixed maximum length for the operands and results. In particular, in the context of modular arithmetic - eg the Montgomery multiplication considered here - it is not easy to overcome such a limitation of length given by the hardware. However, because, as mentioned above, the security of cryptographic methods depends, in particular, on the key length, there is an increasing need to implement modular arithmetic with an operand length that exceeds a maximum length determined by hardware.

The conference contribution <i>"Increasing the bit-length of a crypto-coprocessor"</i> by W. Fischer and J.-P. Seifert, appeared in the proceedings to<i>"Workshop on Cryptographic Hardware and Embedded Systems 2002 (CHES 2002)",</i> Volume 2523 of the <i>Lecture Notes in Computer Science,</i> Springer-Verlag, 2003, pages 71-81, describes several methods for performing a modular multiplication with approximately doubled number of digits. However, these methods are not intended for use in connection with Montgomery multiplications.

According to a first aspect, the invention therefore has the object to provide a technique for performing a Montgomery multiplication, which is particularly suitable for long operands. In preferred embodiments, the proposed technique is to utilize existing hardware support designed for Montgomery multiplications or variants thereof having a predetermined number of digits to provide increased number of Montgomery multiplication.

According to a second aspect, the invention has the object to provide an extended Montgomery multiplication, which can be used as a basis for various other calculations. In preferred embodiments, this extended Montgomery multiplication should use an already existing hardware support of a regular Montgomery multiplication.

According to the invention, these objects are achieved in whole or in part by methods having the features of claim 1 or claim 19, a computer program product according to claim 24 and a portable data carrier according to claim 25. The dependent claims define preferred embodiments of the invention.

The invention in its first aspect is based on the idea of ​​supporting the Montgomery multiplication with long operands on several extended Montgomery multiplications with lower operand length.

According to its second aspect, the invention proceeds from the basic idea of ​​providing a suitably extended Montgomery multiplication, which can also, but not only, be used to implement Montgomery multiplication with long operands. The extended Montgomery multiplication is based on two "usual" Montgomery multiplications of the same bit length. These two Montgomery multiplications use the original factors but two different modules.

By means of Montgomery multiplication with long operands, for example, extensive cryptographic calculations can be carried out. For example, using the invention, an implementation of the RSA method with a maximum key length of 2048 bits suitable for the Hitachi AE4 processor can be provided, although the cryptographic operations of this processor are limited in hardware to operand lengths of 1024 bits.

In the present text, the term "bit length" is always to be understood as the maximum value for the numbers that can be represented with a given bit length-or their absolute value. In other words, leading 0 bits are allowed. The bit length therefore indicates, for example, the register width which is required for a hardware implementation to record the corresponding value. The bit length of the Montgomery multiplication with long operands is shown below<i>L</i> and the bit length of the extended Montgomery multiplication is denoted by <i>l</i> designated. Preferably, it is achieved by the method that the bit length<i>L</i> approximately or exactly twice the bit length <i>l</i> is.

In preferred embodiments, the calculation of an extended Montgomery multiplication involves both a multiplication of two factors and a modular reduction. The necessary calculations can be sequential or completely or partially parallel or completely or partially interlocked (<i>interleaved</i>).

Preferably, the factors of Montgomery multiplication become the bit length <i>L</i> into individual coefficients each with the bit length <i>l</i> split. This splitting may in some embodiments of a 2^<i>l</i>-adischen representation of the factors correspond. In contrast, in other embodiments, a splitting may be provided, in whose position weighting a root of the module modulo 2nd^<i>l</i> received.

In preferred embodiments, to perform the multiplication part of the method, the coefficients are multiplied in pairs as factors of an extended Montgomery multiplication and in each case two values ​​of the bit length <i>l</i> disassembled. In some embodiments, all pair combinations of the coefficients are used here, while in other embodiments some of these partial multiplications are saved, for example by using the Karatsuba method.

The reduction in preferred embodiments comprises several - at least two - steps, wherein each reduction step preferably includes at least one extended Montgomery multiplication.

The extended Montgomery multiplications are performed on both the multiplication part and the reduction part in preferred embodiments of the method with a module having either the value 1 or the value <i>n</i>₀ Has. Here is<i>n</i>₀ in different embodiments either the least significant 2^<i>l</i>-adic part of the long module <i>n</i> or a root - the square root or a higher root - of the long module <i>n</i> modulo 2^<i>l</i> or value -<i>n</i> modulo 2^<i>l</i>.

In preferred embodiments of the extended Montgomery multiplication, in the two underlying "simple" Montgomery multiplications, the original module becomes <i>n</i> and module 2^<i>l</i> - <i>n</i> used. The two Montgomery multiplications can be interleaved in any order or completely or partially in parallel or completely or partially (<i>interleaved</i>). The results are preferably further evaluated in a case distinction.

The computer program product according to the invention has program instructions in order to implement the method according to the invention. Such a computer program product may be a physical medium, for example a semiconductor memory or a floppy disk or a CD-ROM. However, the computer program product may also be a non-physical medium, such as a signal transmitted over a computer network. In particular, such a computer program product may contain program instructions which are transmitted to the latter during the production and / or initialization and / or personalization of a portable data carrier.

In preferred embodiments, the computer program product and / or the portable data carrier are developed with features which correspond to the features described above and / or the features mentioned in the dependent method claims. In particular, the data carrier can have a coprocessor, which supports the Montgomery multiplication in terms of hardware.

Other features, advantages and objects of the invention will be apparent from the following detailed description of several embodiments and alternative embodiments. The following sections contain:<dl id="dl0001"><dt>Section A</dt><dd>an example of a hardware supported Montgomery multiplication according to the prior art,</dd><dt>Section B</dt><dd>an exemplary method as well as several modifications for carrying out an extended Montgomery multiplication,</dd><dt>Section C</dt><dd>an exemplary method and several modifications to perform a Montgomery multiplication with increased operand length, in which a 2^<i>l</i>-adische representation of the operands is used, and</dd><dt>Section D</dt><dd>an exemplary method as well as several modifications for carrying out a Montgomery multiplication with increased operand length, in which the operands are represented as a function of a module root.</dd></dl>

A. Hardware-supported Montgomery multiplication

The methods according to the following sections B to D are provided in the exemplary embodiments of the invention described here by a processor of a portable data carrier, in particular a chip card (<i>smart card</i>) or a chip module to be executed. The methods are implemented in the form of program instructions which are contained in a ROM or an EEPROM or other memory of the data carrier. The data carrier also has a cryptographic or mathematical coprocessor, which supports various operations with a predetermined maximum number of digits, which may be 1024 bits, for example.

One of the operations supported by the coprocessor is Montgomery multiplication. Montgomery multiplication is a modular multiplication in which two factors are multiplied together and with the inverse of an appropriate power of two. This power of two can, for example, correspond to the number of different values ​​which can be represented with the given bit length. The Montgomery multiplication can be implemented much more efficiently than a modular multiplication, which consists of a usual multiplication and a division with remainder. A typical field of application for Montgomery multiplication is the modular exponentiation, which is required for various cryptographic methods, eg RSA methods.

In formula notation, the result of a Montgomery multiplication of two factors <i>a</i> and <i>b</i> concerning a module <i>n</i> as <i>a</i> · <i>b</i> · 2^-<i>l</i> mod <i>n</i> express. Here 0 ≤<i>a</i>, <i>b</i> &lt; <i>n</i> &lt; 2^<i>l</i> and one to 2^<i>l</i> divisional module <i>n</i> provided. The latter condition is met exactly when the module<i>n</i> is odd. An exemplary implementation of this operation is as Algorithm 14.36 in the book<i>Handbook of Applied Cryptography</i> by A. Menzenes, P. van Oorschot and S. Vanstone, CRC Press, Boca Raten, 1997, pages 602-603.

Implementations of Montgomery multiplication used in practice may differ slightly from the mathematical formulation just mentioned. In particular, it can be provided that the result is not completely modulo<i>n</i> reduced, but only in the one with the bit length <i>l</i> representable range of values ​​is brought. In some implementations, weaker conditions may be imposed on the operands, eg<i>a</i>, <i>b</i>, <i>n</i> &lt; 2^<i>l</i> instead of <i>a</i>, <i>b</i> &lt; <i>n</i> &lt; 2^<i>l</i>, The bit length<i>l</i> usually corresponds to the register width of the coprocessor.

An advantageous implementation of the Montgomery multiplication, also described in US Pat. No. 5,961,578, will be discussed below with MM_<i>l</i>(<i>a</i>, <i>b</i>, <i>n</i>) designated. For the operands<i>a</i>, <i>b</i>, <i>n</i> must be 0 ≤ <i>a</i>, <i>b</i>, <i>n</i> &lt; 2^<i>l</i> apply, and <i>n</i> must be odd, that is alien to 2^<i>l</i>, his. Then, for example by the mathematical coprocessor of the data carrier, calculations are carried out which are equivalent to the following calculation steps:<maths id="math0001" num="(A1.1)"><math display="block"><mrow><mtext>SET </mtext><mtext mathvariant="italic">k</mtext><mtext> := -</mtext><mtext mathvariant="italic">a</mtext><mtext> · </mtext><mtext mathvariant="italic">b</mtext><mtext> · </mtext><msup><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>-1</mtext></mrow></msup><msup><mrow><mtext> mod 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup></mrow></math><img file="EP1536320A2_D0001.tif" /></maths><maths id="math0002" num="(A1.2)"><math display="block"><mrow><mtext>SET </mtext><mtext mathvariant="italic">w</mtext><mtext> := (</mtext><mtext mathvariant="italic">a</mtext><mtext> · </mtext><mtext mathvariant="italic">b</mtext><mtext> + </mtext><mtext mathvariant="italic">k</mtext><mtext> · </mtext><mtext mathvariant="italic">n</mtext><msup><mrow><mtext>) / 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup></mrow></math><img file="EP1536320A2_D0002.tif" /></maths><maths id="math0003" num="(A1.3)"><math display="block"><mrow><mtext>IF </mtext><mtext mathvariant="italic">w</mtext><msup><mrow><mtext> ≥ 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> THEN SET </mtext><mtext mathvariant="italic">w</mtext><mtext> := </mtext><mtext mathvariant="italic">w</mtext><mtext> - </mtext><mtext mathvariant="italic">n</mtext></mrow></math><img file="EP1536320A2_D0003.tif" /></maths><maths id="math0004" num="(A1.4)"><math display="block"><mrow><mtext>GIB </mtext><mtext mathvariant="italic">w</mtext><mtext> AS A RESULT OUT</mtext></mrow></math><img file="EP1536320A2_D0004.tif" /></maths>

The result <i>w</i> of the procedure is MM_<i>l</i>(<i>a</i>, <i>b</i>, <i>n</i>). The division in step (A1.2) is always executable without remainder, because<i>k</i> was determined in step (A1.1) that <i>a</i> · <i>b</i> + <i>k</i>. <i>n</i> through 2^<i>l</i> is divisible. After step (A1.2), 0 ≤<i>w</i> &lt; 2^<i>l</i> + <i>n</i> and therefore, after step (A1.3), 0 ≤ <i>w</i> &lt; 2^<i>l</i>, The result value<i>w</i> So is also - like the factors <i>a</i> and <i>b</i> - to the bit length <i>l</i> limited.

The calculation of MM_<i>l</i>(<i>a</i>, <i>b</i>, <i>n</i>) according to steps (A1.1) - (A1.4) is a Montgomery multiplication because:<maths id="math0005" num="(A2)"><math display="block"><mrow><msub><mrow><mtext>MM</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><mtext>(</mtext><mtext mathvariant="italic">a</mtext><mtext>, </mtext><mtext mathvariant="italic">b</mtext><mtext>, </mtext><mtext mathvariant="italic">n</mtext><mtext>) mod </mtext><mtext mathvariant="italic">n</mtext><mtext> = </mtext><mtext mathvariant="italic">a</mtext><mtext> · </mtext><mtext mathvariant="italic">b</mtext><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>-</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> mod </mtext><mtext mathvariant="italic">n</mtext></mrow></math><img file="EP1536320A2_D0005.tif" /></maths>

Equation (A2) can also be written as:<maths id="math0006" num=""><img file="EP1536320A2_D0006.tif" /></maths> In equation (A3) has <i>k</i>'the value on the <i>k</i> in step (A1.1), if after step (A1.2) <i>w</i> &lt; 2^<i>l</i> applies. Otherwise it has<i>k</i>' the value <i>k</i> - 2^<i>l</i>.

B. Advanced Montgomery Multiplication

According to a first embodiment of the invention, an extended Montgomery multiplication is provided which is based on the hardware implemented Montgomery multiplication of the processor or coprocessor as described in section A above. The extended Montgomery multiplication of two factors with respect to a module yields two results, one corresponding to the result of a "normal" Montgomery multiplication of the two factors with respect to the modulus, and the other indicating by which multiple of the module that is the operand bit length left shifted first result differs from the product of the two factors.

The extended Montgomery multiplication of two factors <i>a</i> and <i>b</i> concerning a module <i>n</i> will be referred to as XMM below_<i>l</i>(<i>a</i>, <i>b</i>, <i>n</i>written, where <i>l</i> an upper limit for the bit length of the operands <i>a</i>, <i>b, n</i> indicates. Leading 0-bits are allowed. For<i>l</i> ≥ 2 and integers 0 ≤ <i>a</i>, <i>b, n</i> &lt; 2^<i>l</i> with odd <i>n</i> is defined:<maths id="math0007" num=""><img file="EP1536320A2_D0007.tif" /></maths>

By definition (B1) are for all <i>a</i>, <i>b</i>, <i>n,</i> which meet the above requirements, the values <i>w</i> and <i>k</i> clearly determined. Furthermore, for (<i>w</i>, <i>k</i>) = XMM_<i>l</i>(<i>a</i>, <i>b</i>, <i>n</i>) the relationships:<maths id="math0008" num="(B2)"><math display="block"><mrow><mtext>0 ≥ </mtext><mtext mathvariant="italic">w</mtext><msup><mrow><mtext> &lt;2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> + </mtext><mtext mathvariant="italic">n</mtext><mtext> - 1</mtext></mrow></math><img file="EP1536320A2_D0008.tif" /></maths><maths id="math0009" num="(B3)"><math display="block"><mrow><mtext mathvariant="italic">w</mtext><mtext> ≡ </mtext><mtext mathvariant="italic">a</mtext><mtext> · </mtext><mtext mathvariant="italic">b ·</mtext><msup><mrow><mtext> 2</mtext></mrow><mrow><mtext>-</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">n</mtext><mtext>)</mtext></mrow></math><img file="EP1536320A2_D0009.tif" /></maths>

The calculation of XMM_<i>l</i>(<i>a</i>, <i>b</i>, <i>n</i>) is based on two Montgomery multiplications MM according to the embodiment described here_<i>l</i> with the factors <i>a</i> and <i>b</i> and the bit length <i>l</i> supported. One of these MM_<i>l</i>Operations is done with the module <i>n</i> executed. For the other MM_<i>l</i>Operation becomes module 2^<i>l</i> - <i>n</i> used. The second result value<i>k</i> from XMM_<i>l</i>(<i>a</i>, <i>b</i>, <i>n</i>) can then from the results of the two MM_<i>l</i>Operations are calculated.

Overall, the calculation of XMM_<i>l</i>(<i>a</i>, <i>b</i>, <i>n</i>) For <i>a</i>, <i>b</i>, <i>n</i> ∈ <img file="EP1536320A2_D0010.tif" /> with 0 ≤ <i>a</i>, <i>b</i>, <i>n</i> &lt; 2^<i>l</i> with odd <i>n</i> and <i>l</i> ≥ 2 in the present example, the following steps are carried out:<maths id="math0010" num=""><img file="EP1536320A2_D0011.tif" /></maths><maths id="math0011" num=""><img file="EP1536320A2_D0012.tif" /></maths>

The result (<i>w</i>, <i>k</i>) of the method according to the steps (B5.1) - (B5.16) is XMM_<i>l</i>(<i>a</i>, <i>b, n</i>).

It is understood that in execution alternatives, the order of MM_<i>l</i>Operations and the further calculation steps can be changed. In other alternative embodiments, the calculation of XMM_<i>l</i>(<i>a</i>, <i>b</i>, <i>n</i>) adapted to a coprocessor, which is not exactly the MM_<i>l</i>Operation according to the steps (A1.1) - (A1.4), but performs a slightly modified Montgomery operation. Such an adaptation is definitely possible if the behavior of the coprocessor in terms of value<i>k '</i> from equation (A3).

To those skilled in the art modifications and improvements of the method according to the steps (B5.1) - (B5.16) and the adaptation to a modified MM_<i>l</i>In the following, some basic principles are described on which the method according to steps (B5.1) - (B5.16) is based.

For the value calculated in step (B5.1) <i>w</i>₁ applies according to (B2) and (B4) 0 ≤ <i>w</i>₁ &lt; 2^<i>l</i>, and there are an integer according to (B1) and (B4) <i>k</i>₁ with -2^<i>l</i> &lt; <i>k</i>₁ &lt; 2^<i>l</i>so that<maths id="math0012" num="(B6)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> = </mtext><mtext mathvariant="italic">a</mtext><mtext> · </mtext><mtext mathvariant="italic">b</mtext><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext></mtext><mtext mathvariant="italic">· N</mtext></mrow></math><img file="EP1536320A2_D0013.tif" /></maths>

The same applies to the value calculated in step (B5.2) <i>w</i>₂ the inequality 0 ≤ w₂ &lt; 2^<i>l</i>, and there is an integer <i>k</i>₂ with -2^<i>l</i> &lt; <i>k</i>₂ &lt; 2^<i>l</i>so that<maths id="math0013" num="(B7)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> = </mtext><mtext mathvariant="italic">a</mtext><mtext> · </mtext><mtext mathvariant="italic">b</mtext><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msup><mrow><mtext> · (2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> - </mtext><mtext mathvariant="italic">n</mtext><mtext>)</mtext></mrow></math><img file="EP1536320A2_D0014.tif" /></maths>

By subtracting the equation (B7) from the equation (B6), the result is modulo 2^<i>l</i> the equivalence (<i>k</i>₁ + <i>k</i>₂) <i>· N</i> ≡ 0. Because <i>n</i> odd, it must be an integer δ with <i>k</i>₁ + <i>k</i>₂ = δ · 2^<i>l</i> give. Because of -2^<i>l</i> &lt; <i>k</i>₁ &lt; 2^<i>l</i> and -2^<i>l</i> &lt; <i>k</i>₂ &lt; 2^<i>l</i> follows δ ∈ {-1, 0, 1}, so that the value δ is uniquely defined by its modulus 4 residue. It also applies:<maths id="math0014" num="(B8)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> &gt; 0, if δ&gt; 0</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> &lt;0, if δ &lt;0</mtext></mrow></math><img file="EP1536320A2_D0015.tif" /></maths>

By inserting the relationship <i>k</i>₂ = δ · 2^<i>l</i> - <i>k</i>₁ the difference between equations (B7) and (B6) also yields:<maths id="math0015" num="(B9)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msup><mrow><mtext> + δ · (2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext></mtext><mtext mathvariant="italic">- n</mtext><mtext>)</mtext></mrow></math><img file="EP1536320A2_D0016.tif" /></maths>

From (B9), taking into account the fact that <i>n</i> ≡ <i>n</i>^-1 (mod 4) for odd <i>n</i> applies, derive the following relationship:<maths id="math0016" num="(B10)"><math display="block"><mrow><mtext>δ ≡ (</mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><mtext>) · </mtext><mtext mathvariant="italic">n</mtext><mtext> + </mtext><mtext mathvariant="italic">a</mtext><mtext> · </mtext><mtext mathvariant="italic">b</mtext><mtext> (mod 4)</mtext></mrow></math><img file="EP1536320A2_D0017.tif" /></maths> In step (B5.3) of the method described above, this value δ is calculated according to relation (B10). It is understood that the calculation in step (B5.3) does not have to be carried out with a full number of digits, but that it is sufficient to determine only the two least significant bits of all intermediate results.

The value of <i>k</i>₁ Now follow from (B9). Out<i>w</i>₁ and <i>k</i>₁ can be <i>w</i> and <i>k</i> determine by using the following equivalences derived from (B1), (B4) and (B6):<maths id="math0017" num="(B11)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">w</mtext><mtext> ⇔ </mtext><msub><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext></mtext><mtext mathvariant="italic">= k</mtext><mtext> ⇔ </mtext><mtext mathvariant="italic">w</mtext><msup><mrow><mtext> &lt; 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup></mrow></math><img file="EP1536320A2_D0018.tif" /></maths><maths id="math0018" num="(B12)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">w</mtext><mtext> - </mtext><mtext mathvariant="italic">n</mtext><mtext> ⇔ </mtext><msub><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">k</mtext><msup><mrow><mtext> - 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> ⇔ </mtext><mtext mathvariant="italic">w</mtext><msup><mrow><mtext> ≥ 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup></mrow></math><img file="EP1536320A2_D0019.tif" /></maths>

With regard to the value of <i>w</i> surrendered:<maths id="math0019" num="(B13)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">w</mtext><mtext> ⇔ </mtext><msub><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> ≥ 0</mtext></mrow></math><img file="EP1536320A2_D0020.tif" /></maths>

In the case discrimination according to the steps (B5.4) - (B5.15), relations (B9) and (B11) - (B13) are used to obtain the result values <i>w</i> and <i>k</i> in the different cases with the least possible computational effort to determine. In particular, the three cases δ = 0, δ = 1, and δ = -1 are distinguished to satisfy the summands δ · (2) contained in the relation (B9)^<i>l</i> - <i>n</i>) as far as possible to evaluate. Furthermore, the intermediate value<i>k</i>_<i>1</i> the relationship (B9) is not calculated explicitly, but it is immediately the end result <i>k</i> determined using (B11) and (B12). The relation (B13) is used in the steps (B5.7) - (B5.9). For δ ≠ 0, because of relation (B8) in steps (B5.10) - (B5.15), a case distinction with respect to the sign of<i>k</i>₁.

An advantageous modification of the method according to the steps (B5.1) - (B5.16) results for the special case <i>w</i> &lt; 2^<i>l</i>, As follows from (B1) and (B2), this case is given, for example, if<i>n</i> = 1 or if <i>a</i> · <i>b</i> &lt; 2^<i>l</i> applies. From (B11) follows<i>w</i>₁ = <i>w</i> and <i>k</i>_<i>1</i> = <i>k,</i> and because of (B13) is a negative value of <i>k</i> locked out. Furthermore, due to (B8), either δ = 0 or δ = 1 must apply. The value δ therefore does not need to be calculated modulo 4 as in (B10) but satisfies a calculation modulo 2. The case distinction of steps (B5.4) - (B5.15) then becomes considerably simpler. Overall, the modified method for calculating XMM_<i>l</i>(<i>a</i>, <i>b</i>, <i>n</i>) is defined by the following steps (B14.1) - (B14.9). It was<i>a</i>, <i>b</i>, <i>n</i> ∈ <img file="EP1536320A2_D0021.tif" /> with 0 ≤ <i>a</i>, <i>b</i>, <i>n</i> &lt; 2^<i>l</i> with odd <i>n</i> and <i>l</i> ≥ 2, and it applies <i>w</i> &lt; 2^<i>l</i> :<maths id="math0020" num=""><img file="EP1536320A2_D0022.tif" /></maths>

The XMM_<i>l</i>Not only is operation useful as a building block for the Montgomery multiplications with increased operand length described in Sections C and D below, but also for other applications. One such application is, for example, the calculation of the "normal" product<i>a</i> · <i>b</i> two factors <i>a</i>, <i>b</i>depending on the bit length <i>l</i> respectively. It will be the operation XMM_<i>l</i>(<i>a</i>, <i>b</i>, 1) executed; the result is (<i>w</i>, <i>k</i>). Then according to (B1)<i>a</i> · <i>b</i> = <i>w</i> · 2^<i>l</i> - <i>k</i>, and from (B2) follows <i>w</i> &lt; 2^<i>l</i>, For the XMM_<i>l</i>Therefore, both the method with the steps (B5.1) - (B5.16) and the simplified method with the steps (B14.1) - (B14.9) can be used. If desired, the binary representation of<i>a</i> · <i>b</i> to be obtained by <i>w</i> around <i>l</i> Move positions to the left and then <i>k</i> is subtracted from the result.

Another use case in particular for the simplified method with the steps (B14.1) - (B14.9) are operations of the form XMM_<i>l</i>(<i>a</i>, 1, <i>n</i>). The result of such operations is also valid<i>w</i> &lt; 2^<i>l</i>because out of relationships <i>w</i> = (<i>a</i> · <i>b + k</i> · <i>n</i>) / 2^<i>l</i> &lt; (2^<i>l</i> + 2^<i>l</i> · <i>n</i>) / 2^<i>l</i> &lt; <i>n</i> + 1 the inequality <i>w</i> ≤ <i>n</i> &lt; 2^<i>l</i> follows.

The above-described methods may also be used in a slightly modified form for extended Montgomery multiplication with a bit length that does not exactly correspond to a bit length supported by the processor hardware. Around (<i>w</i>, <i>k</i>) as a result of XMM_<i>l</i>(<i>a</i>, <i>b</i>, <i>n</i>), first becomes the next largest bit length supported by the processor hardware <i>l</i> + <i>l '</i> With <i>l '</i> &gt; 0 determined. The extended Montgomery multiplication XMM_{<i>l</i>+<i>l '</i>} (<i>a</i> · 2^{<i>l '</i>}, <i>b</i>, <i>n</i>) then gives the values ​​(<i>w</i>, <i>k ·</i> 2^<i>l</i>') as a result.

C. Montgomery multiplication with increased bit length (2

<i><b>l</b></i>

-adische representation of the operands)

As mentioned in Section A, the Montgomery multiplication performed by a coprocessor is usually of a given bit length <i>l</i> limited for the factors and the module. However, in particular for cryptographic applications, a Montgomery multiplication with a larger bit length<i>L</i> to be required. In accordance with the embodiments of the invention described herein and in the next section, such an increased bit length Montgomery multiplication is provided by each having a plurality of extended bit length Montgomery multiplications<i>l</i> executed and their results are suitably linked together.

The embodiments of the present section C are based on the basic idea, the binary representation of the two factors <i>a</i> and <i>b</i> with bit length <i>L</i> each in sections of bit length <i>l</i> to process. In other words, a 2^<i>l</i>-adische representation of the operands, so the factors <i>a</i> and <i>b</i> and the module <i>n</i>, used. As a result, the method is composed of a multiplication and a modular reduction, these processes being suitably interlocked by the number of XMMs_<i>l</i>Operations and the space needed for intermediate results.

As a result, the embodiment described below doubles the bit length of the Montgomery multiplication provided by the coprocessor; So it applies<i>L</i> = 2<i>l</i> With <i>l</i> ≥ 2. The factors <i>a</i> and <i>b</i> as well as the odd module <i>n</i>, each the bit length <i>L</i> = 2<i>l</i> each have a higher order section <i>a</i>₁, <i>b</i>₁, <i>n</i>₁ With <i>l</i> Bits and one less significant portion each <i>a</i>₀, <i>b</i>₀, <i>n</i>₀ with likewise <i>l</i> Bits are shown. Overall, therefore, the relationships apply<i>a</i> = <i>a</i>₁ · 2^<i>l</i> + <i>a</i>₀, <i>b</i> = <i>b</i>₁ · 2^<i>l</i> + <i>b</i>₀, <i>n</i> = <i>n</i>₁ · 2^<i>l</i> + <i>n</i>₀ and 0 ≤ <i>a</i>₁, <i>a</i>₀, <i>b</i>₁, <i>b</i>₀, <i>n</i>₁, <i>n</i>₀ &lt; 2^<i>l</i> such as <i>n</i> odd; the latter is synonymous with<i>n</i>₀ odd.

The process requires seven XMMs_<i>l</i>Operations and some more calculations. The following steps are performed with the operands of the XMM_<i>l</i>Operations all non-negative and less than 2^<i>l</i> are:<maths id="math0021" num=""><img file="EP1536320A2_D0023.tif" /></maths><maths id="math0022" num=""><img file="EP1536320A2_D0024.tif" /></maths>

For the result <i>w</i> applies <i>w</i> ≡ <i>a</i> · <i>b</i> · 2^-2<i>l</i> (mod <i>n</i>) with 0 ≤ <i>w</i> &lt; 2^2<i>l</i> + <i>n</i> - 1.

After step (C1.6), (<maths id="math0023" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>2</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0025.tif" /></maths>, <maths id="math0024" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0026.tif" /></maths>, <maths id="math0025" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0027.tif" /></maths>) the 2^<i>l</i>-adische representation of <i>v</i>₁ · 2^<i>l</i> + <i>v</i>₀, It can be shown that the following relationship applies after step (C1.6):<maths id="math0026" num="(C2)"><math display="block"><mrow><mtext>(</mtext><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>2</mtext></mrow></msub></mrow><mo>¯</mo></mover><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>2</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> + </mtext><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow><mo>¯</mo></mover><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> + </mtext><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow><mo>¯</mo></mover><msup><mrow><mtext>) · 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">a · b - a</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> · </mtext><msub><mrow><mtext mathvariant="italic">b</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>2</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext></mtext><mtext mathvariant="italic">· N</mtext></mrow></math><img file="EP1536320A2_D0028.tif" /></maths>

The values <maths id="math0027" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>2</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0029.tif" /></maths> , <maths id="math0028" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0030.tif" /></maths>, <maths id="math0029" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0031.tif" /></maths> can look out with a single addition <i>v</i>₁ and <i>v</i>₀ when the intermediate values ​​of steps (C1.1) - (C1.5) are in two's complement binary representation. Namely, 0 ≤<maths id="math0030" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>2</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0032.tif" /></maths> &lt;3 because of relationship (C2) and 0 ≤ <i>u</i>₀ &lt; 2^<i>l</i>.

As well as the operands <i>a</i>, <i>b</i> and <i>n</i> is also the result of the Montgomery multiplication after step (C1.10) in the form of a higher-order section <i>w</i>₁ and a lower-grade section <i>w</i>₀ in front.

For the total value output in step (C1.12) <i>w</i> can be deduced from equation (C2) that the inequality 0 ≤ <i>w &lt;</i> 2^2<i>l</i> + <i>n</i> - 1 holds, and that it is an integer <i>u</i> with 0 ≤ <i>u</i> &lt; 2^2<i>l</i> there, so that <i>w</i> · 2^2<i>l</i> = <i>a · b</i> + <i>u · n</i> is satisfied. In other words<i>w</i> ≡ <i>a</i> ≡ <i>b</i> · 2^-2<i>l</i> (mod <i>n</i>), so that the method according to the steps (C1.1) - (C1.12) actually performs a Montgomery multiplication.

In a concrete application example, the operand length specified by the coprocessor of the data carrier is doubled by the method according to the steps (C1.1) - (C1.12), for example an RSA method - for example for encryption or decryption or verification or signature generation - with a key length of up to 2048 bits using 1024-bit operations of the coprocessor.

If, instead of a Montgomery multiplication, a Montgomery squaring is to be performed, that is, the factors <i>a</i> and <i>b</i> are the same, then, in a modification of the method described above, one of the steps (C1.3) and (C1.4) can be saved, because then XMM_<i>l</i>(a₁, <i>b</i>_<i>0</i><i>,</i> 1) = XMM_<i>l</i>(<i>a</i>₀, <i>b</i>₁, 1) applies.

In the following, some principles of the above-described method will be presented in more general terms to allow those skilled in the art to adapt the method to changing requirements or conditions - eg, a larger desired bit length or a slightly different calculation of extended Montgomery multiplication. The following notes again concern the Montgomery multiplication of two factors<i>a</i> and <i>b</i> concerning a module <i>n</i>, where the bit length of <i>a, b</i> and <i>n</i> each through <i>L</i> is limited. The result<i>w</i> should modulo <i>n</i> equivalent to <i>a</i> · <i>b</i> · 2^-L his.

As already mentioned, the embodiments of the present section C is a 2^<i>l</i>-adische representation of the factors <i>a</i> and <i>b</i> based. In other words, the factors<i>a</i> and <i>b</i> the bit length <i>L</i> each in <i>m</i> Sections or "posts" with each <i>l</i> Divided bits. These bit groups are with<i>a</i>_i and <i>b</i>_<i>i</i> designated. In formula notation thus arise for<i>L</i> = <i>ml</i> the relationships<maths id="math0031" num=""><img file="EP1536320A2_D0033.tif" /></maths> and<maths id="math0032" num=""><img file="EP1536320A2_D0034.tif" /></maths> where 0 ≤ <i>a</i>_<i>i</i><i>, b</i>_<i>i</i> &lt; 2^<i>l</i> applies. Similar to the factors<i>a</i> and <i>b</i> will also be for the module <i>n</i> the 2^<i>l</i>-adische representation<maths id="math0033" num=""><img file="EP1536320A2_D0035.tif" /></maths> with 0 ≤ <i>n</i>_<i>i</i> &lt; 2^<i>l</i> considered. This is in particular<i>n</i>₀ on the value <i>n</i>₀ = <i>n</i> mod 2^<i>l</i> established.

The product <i>a</i> · <i>b</i> can thus be written in the usual way as:<maths id="math0034" num=""><img file="EP1536320A2_D0036.tif" /></maths>

While the "bodies" <i>a</i>_<i>i</i> and <i>b</i>_<i>i</i> each maximum <i>l</i> Bits are long, the intermediates can <i>a</i>_<i>j</i><i>B</i>_<i>k</i> a maximum of 2<i>l</i> Be bit long. To calculate by a coprocessor with a register width of<i>l</i> It is therefore intended to enable bits, these intermediates in turn by means of XMM_<i>l</i>Operations in two each <i>l</i> Bits to disassemble long sections. For this purpose, two approaches are used in the embodiment described here, namely, first, a decomposition of the form<i>a</i>_<i>j</i> · <i>b</i>_<i>k</i> = <i>p</i>_<i>jk</i> · 2^<i>l</i> + <i>q</i>_<i>jk</i> and second, a decomposition of the <i>Form a</i>_<i>j</i> · <i>b</i>_<i>k</i> = <i>p</i><maths id="math0035" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">jk</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0037.tif" /></maths> · 2^<i>l</i> - <i>q</i><maths id="math0036" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">jk</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0038.tif" /></maths> · <i>n</i>₀, in which <i>n</i>₀ the above-mentioned value <i>n</i>₀ = <i>n</i> mod 2^<i>l</i> is and 0 ≤ <i>p</i>_<i>jk</i><i>q</i>_<i>jk</i>, <i>q</i><maths id="math0037" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">jk</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0039.tif" /></maths> &lt; 2^<i>l</i> and 0 ≤ <i>p</i><maths id="math0038" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext>​</mtext></mrow><mrow><mtext mathvariant="italic">jk</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0040.tif" /></maths> &lt; 2^<i>l</i> + <i>n</i>₀&gt; - 1 apply.

The first decomposition results from the application of XMM_<i>l</i>(<i>a</i>_<i>j</i>, <i>b</i>_<i>k</i>, 1); This decomposition is always used in the embodiment described here when<i>j</i> ≠ 0 or <i>k</i> ≠ 0 applies. The second decomposition results from using XMM_<i>l</i>(<i>a</i>_<i>j</i>, <i>b</i>_<i>k</i>, <i>n</i>₀); this decomposition is used in the present embodiment<i>j</i> = <i>k</i> = 0 used.

In the exemplary embodiment of the method according to the steps (C1.1) - (C1.12) applies <i>m</i> = 2. Here the four intermediate products are calculated according to equation (C3) with the just mentioned decompositions in steps (C1.1), (C1.3), (C1.4) and (C1.9). For the values ​​calculated in these steps, the equation is as follows:<maths id="math0039" num="(C4)"><math display="block"><mrow><mtext mathvariant="italic">a · b</mtext><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">G</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>3</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">G</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>2</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> + (</mtext><msub><mrow><mtext mathvariant="italic">d</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext>) · 2</mtext></mrow><mrow><mtext>2</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> + (</mtext><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">d</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext>) · 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> · </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow></math><img file="EP1536320A2_D0041.tif" /></maths>

The according to (C4) in the form of coefficients of the bit length <i>l</i> expressed product <i>a</i> · <i>b</i> is now to be presented in a modular reduced form. The basic idea for this modular reduction is to have suitable multiples of the module<i>n</i> subtract "from the right". With each reduction step, the effective number of digits of the product is shortened by one digit. This is to be understood that after each reduction step both sides of each resulting equation with 2^-<i>l</i> can be multiplied, so that after <i>m</i> Steps an equation of form <i>a</i> · <i>b</i> · 2^-<i>ml</i> = <i>w</i> yields, where <i>w</i> the bit length <i>ml</i>, ie the "number of digits" <i>m</i>, having.

This reduction process will now be exemplified <i>m</i> = 2 illustrated. Here, each reduction step in the present embodiment includes replacing an expression of the form<i>u</i>_<i>i</i><i>· N</i>₀ by an expression that is a multiple of <i>n</i> and its coefficients through an application of XMM_<i>l</i>(<i>u</i>_i, <i>n</i>₁, 1) are calculable.

In the first reduction step, the basic idea just mentioned is exploited by the following relationship, which holds true for XMM_<i>l</i>(<i>u</i>₀, <i>n</i>₁, 1) = (<i>c</i>₁, <i>c</i>₀) from definition (B1) using the equation <i>n</i> = <i>n</i>₁ · 2^<i>l</i> + <i>n</i>₀ results, is used:<maths id="math0040" num="(C5)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> · </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> · </mtext><msub><mrow><mtext mathvariant="italic">n - c</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>2</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">c</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup></mrow></math><img file="EP1536320A2_D0042.tif" /></maths>

The determination of the coefficients <i>c</i>₁ and <i>c</i>₀ takes place in step (C1.2) of the method described above. Substituting (C5) into equation (C4) yields:<maths id="math0041" num="(C6)"><math display="block"><mrow><mtext mathvariant="italic">a · b</mtext><mtext> = </mtext><mtext mathvariant="italic">G</mtext><msup><mrow><mtext>1 · 2</mtext></mrow><mrow><mtext>3</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> · </mtext><msub><mrow><mtext mathvariant="italic">G</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>2</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> + (</mtext><msub><mrow><mtext mathvariant="italic">c</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">d</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext>) · 2</mtext></mrow><mrow><mtext>2</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mspace linebreak="newline" /><mtext> + (</mtext><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">c</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">d</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext>) · 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> · </mtext><mtext mathvariant="italic">n</mtext></mrow></math><img file="EP1536320A2_D0043.tif" /></maths>

In the case of consideration here modulo <i>n</i> can the addend <i>u</i>₀ · <i>n</i> be omitted. Further, as in step (C1.5) of the method, the terms become<i>c</i>₁ + <i>d</i>₁ + <i>e</i>₁ respectively. <i>x</i>₀ - <i>c</i>₀ - <i>d</i>₀ - <i>e</i>₀ by <i>v</i>₁ respectively. <i>v</i>₀ replaced. Total results:<maths id="math0042" num="(C7)"><math display="block"><mrow><mtext mathvariant="italic">a · b</mtext><mtext> ≡ </mtext><msub><mrow><mtext mathvariant="italic">G</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>3</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">G</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>2</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>2</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">n</mtext><mtext>)</mtext></mrow></math><img file="EP1536320A2_D0044.tif" /></maths>

In step (C1.6) of the method is now still a carry calculation, coefficients <maths id="math0043" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>2</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0045.tif" /></maths>, <maths id="math0044" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0046.tif" /></maths>, <maths id="math0045" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0047.tif" /></maths> in the for the 2^<i>l</i>-adical spelling "correct" value range to determine. From (C7) this results in:<maths id="math0046" num="(C8)"><math display="block"><mrow><mtext mathvariant="italic">a · b</mtext><mtext> ≡ </mtext><msub><mrow><mtext mathvariant="italic">G</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext>· 2</mtext></mrow><mrow><mtext>3</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">G</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>2</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> + </mtext><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>2</mtext></mrow></msub></mrow><mo>¯</mo></mover><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>3</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> + </mtext><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow><mo>¯</mo></mover><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>2</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> + </mtext><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow><mo>¯</mo></mover><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">n</mtext><mtext>)</mtext></mrow></math><img file="EP1536320A2_D0048.tif" /></maths>

To get back a polynomial, its least significant coefficient is a multiple of <i>n</i>₀ has the following relationship applied to XMM_<i>l</i>(<maths id="math0047" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0049.tif" /></maths> 1, <i>n</i>₀) is derived from the definition (B1):<maths id="math0048" num="(C9)"><math display="block"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow><mo>¯</mo></mover><mtext> = </mtext><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow><mo>¯</mo></mover><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> · </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow></math><img file="EP1536320A2_D0050.tif" /></maths>

The values ​​of <i>x</i>₁ and <i>u</i>₁ are calculated in step (C1.7) of the method. Overall, inserting (C9) into (C8) yields the equation:<maths id="math0049" num="(C10)"><math display="block"><mrow><mtext mathvariant="italic">a</mtext><mtext> · </mtext><mtext mathvariant="italic">b</mtext><mtext> ≡ </mtext><msub><mrow><mtext mathvariant="italic">G</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>3</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">G</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>2</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> +</mtext><mspace linebreak="newline" /><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>3</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>2</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>2</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> · </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">n</mtext><mtext>)</mtext></mrow></math><img file="EP1536320A2_D0051.tif" /></maths>

The first reduction step is over. The effective number of digits of the product has been increased by a 2^<i>l</i>-adic point, as shown in the following (C10) derived notation:<maths id="math0050" num="(C11)"><math display="block"><mrow><msup><mrow><mtext mathvariant="italic">a · b ·. 2</mtext></mrow><mrow><mtext mathvariant="italic">-l</mtext></mrow></msup><mtext> ≡ </mtext><msub><mrow><mtext mathvariant="italic">G</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>2</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">G</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> +</mtext><mspace linebreak="newline" /><mtext></mtext><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>2</mtext></mrow></msub></mrow><mo>¯</mo></mover><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>2</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> + </mtext><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow><mo>¯</mo></mover><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> · </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> (mod </mtext><mtext mathvariant="italic">n</mtext><mtext>)</mtext></mrow></math><img file="EP1536320A2_D0052.tif" /></maths>

Overall, therefore, by two XMM_<i>l</i>Operations and some additional computations the degree of polynomial in 2^<i>l</i> on the right side of equation (C11) has been reduced by 1 compared to equations (C6) - (C8). In general, in the case<i>m</i> &gt; 2 the degree of the corresponding polynomials <i>m</i> XMM_<i>l</i>Operations around 1 and through (<i>m</i>-1) <i>· M</i> XMM_<i>l</i>Operations around <i>m</i>-1 reduce. This results in an equivalence of the form:<maths id="math0051" num="(C12)"><math display="block"><mrow><mtext mathvariant="italic">a</mtext><mtext> · </mtext><mtext mathvariant="italic">b</mtext><msup><mrow><mtext> · 2-</mtext></mrow><mrow><mtext>(</mtext><mtext mathvariant="italic">m</mtext><mtext>-1)</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> ≡ </mtext><msub><mrow><mtext mathvariant="italic">z</mtext></mrow><mrow><mtext mathvariant="italic">m</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext mathvariant="italic">ml</mtext></mrow></msup><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">z</mtext></mrow><mrow><mtext mathvariant="italic">m</mtext><mtext>-1</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>(</mtext><mtext mathvariant="italic">m</mtext><mtext>-1</mtext></mrow></msup><mtext>)</mtext><mtext mathvariant="italic">l</mtext><mtext> + ...</mtext><mspace linebreak="newline" /><mtext> ... + </mtext><msub><mrow><mtext mathvariant="italic">z</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">z</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> · </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> (mod </mtext><mtext mathvariant="italic">n</mtext><mtext>)</mtext></mrow></math><img file="EP1536320A2_D0053.tif" /></maths>

A final reduction step is now required, which is carried out analogously to the steps (C5) - (C7). To the example of the special case<i>m</i> = 2, the term should <i>u</i>₁ · <i>n</i>₀ in equation (C11) by an expression that is a multiple of <i>n</i> has to be replaced. To do this, the following relationship applies to XMM_<i>l</i>(<i>u</i>₁, <i>n</i>₁, 1) from definition (B1), uses:<maths id="math0052" num="(C13)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> · </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> · </mtext><mtext mathvariant="italic">n</mtext><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">f</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>2</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">f</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup></mrow></math><img file="EP1536320A2_D0054.tif" /></maths>

The values <i>f</i>₁ and <i>f</i>₀ are calculated in step (C1.8) of the method. From (C11) and (C13) it follows:<maths id="math0053" num="(C14)"><math display="block"><mrow><mtext mathvariant="italic">a</mtext><mtext> · </mtext><mtext mathvariant="italic">b</mtext><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>-</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> ≡ (</mtext><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext mathvariant="italic">2</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">f</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">G</mtext></mrow><mrow><mtext mathvariant="italic">1</mtext></mrow></msub><msup><mrow><mtext>) · 2</mtext></mrow><mrow><mtext>2</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> +</mtext><mspace linebreak="newline" /><mtext> (</mtext><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow><mo>¯</mo></mover><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">f</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">G</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext>) · 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">u</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> · </mtext><mtext mathvariant="italic">n</mtext><mtext> (mod </mtext><mtext mathvariant="italic">n</mtext><mtext>)</mtext></mrow></math><img file="EP1536320A2_D0055.tif" /></maths>

Because of the bill modulo <i>n</i> can the addend <i>u</i>₁<i>· N</i> be omitted. With the naming of the coefficients<maths id="math0054" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>2</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0056.tif" /></maths> + <i>f</i>₁ + <i>G</i>₁ and <maths id="math0055" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">v</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0057.tif" /></maths> + <i>x</i>₁ -<i>f</i>₀ - <i>G</i>₀ as in process step (C1.10) and a multiplication of the equation with 2^-l finally results in the desired result, namely:<maths id="math0056" num="(C15)"><math display="block"><mrow><mtext mathvariant="italic">a · b ·</mtext><msup><mrow><mtext> 2</mtext></mrow><mrow><mtext>2L</mtext></mrow></msup><mtext> ≡ </mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>l</mtext></mrow></msup><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">w</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> (mod </mtext><mtext mathvariant="italic">n</mtext><mtext>)</mtext></mrow></math><img file="EP1536320A2_D0058.tif" /></maths>

This is the last reduction step with a single XMM_<i>l</i>Operation completed. Generally, for bit-by-bit multiplications<i>m</i>² XMM_<i>l</i>Needed operations for the first <i>m</i>-1 reduction steps become (<i>m</i>-1) <i>· M</i> XMM_<i>l</i>Operations are required, and for the final reduction step <i>m</i>-1 XMM_<i>l</i>Operations needed. In total, this results in 2<i>m</i>²-1 XMM_<i>l</i>Operations for a Montgomery multiplication with m-times bit length.

D. Montgomery multiplication with increased bit length (representation of the operands as a function of a module root)

The present section D, like the preceding section C, concerns methods for performing Montgomery multiplications, their factors <i>a, b</i> and module <i>n</i> a big bit length <i>L</i> respectively. Again, the calculation is based on several extended Montgomery multiplications with lower bit length<i>l</i> supported. However, the methods described herein are based on a representation of the operands that are used by the 2^<i>l</i>-adical representation according to Section C deviates.

For the two factors <i>a</i> and <i>b</i> a weighting representation is used, in which the weights from place to place by a factor of 2^<i>l</i>/<i>n</i>₀ distinguish, where <i>n</i>₀ an odd, from an approximated one <i>m</i>-th root of the module <i>n</i> or the negative module -<i>n</i> dependent number is. In formula notation:<maths id="math0057" num=""><img file="EP1536320A2_D0059.tif" /></maths>

For the special case m = 2, the above equations (D1) simplify too <i>a</i> ≡ <i>a</i>₀ · 2^<i>l</i> + <i>a</i>₁ · <i>n</i>₀ (mod <i>n</i>) respectively <i>b</i> ≡ <i>b</i>₀ · 2^<i>l</i> + <i>b</i>₁ · <i>n</i>₀ (mod <i>n</i>).

In the following also the notation μ<i>n</i>₀,<i>l</i>(<i>x</i>₀, <i>x</i>₁) For <i>x</i>₀ · 2^<i>l</i> + <i>x</i>₁ · <i>n</i>₀ used. In the case<i>m</i> = 2 become the factors <i>a</i> and <i>b</i> so that each by a pair (<i>a</i>₀, <i>a</i>₁), (<i>b</i>₀, <i>b</i>₁) with μ<i>n</i>_0,<i>l</i>(<i>a</i>₀, <i>a</i>₁) ≡ <i>a</i> (mod <i>n</i>) and μ<i>n</i>_0,<i>l</i>(<i>b</i>_<i>0</i>, <i>b</i>₁) ≡ <i>b</i> (mod <i>n</i>). The method described here is based on the fact that<i>c</i>₀, <i>c</i>₁) = XMM_<i>l</i>(<i>a</i>, <i>b</i>, <i>n</i>₀) equivalent to μ_{<i>n</i>0,<i>l</i>}(<i>c</i>₀, -<i>c</i>₁) = <i>a</i> · <i>b</i> is.

For the module <i>n</i> In this section D, the following representation is used, which corresponds to the representation of the module <i>n</i> is based on section C:<maths id="math0058" num=""><img file="EP1536320A2_D0060.tif" /></maths>

Again, the position weights differ for the area <i>i</i> = 2, ..., <i>m</i> each by a factor of 2^<i>l</i>/<i>n</i>₀and it is ±<i>n</i>₀^<i>m</i> provided as an additional summand. The sign of<i>n</i>₀^<i>m</i> may be positive in some embodiments but negative in others. In the following description, a negative sign is chosen because it avoids some technical problems.

The following is the special case <i>m</i> = 2 with the summand -<i>n</i>₀^<i>m</i> considered. The equation (D2) is thus simplified<i>n</i> = -<i>n</i>₀² + <i>u ·</i> 2^<i>l</i> where the coefficient <i>u</i>₂ from equation (D2) here for the sake of simplicity <i>u</i> is written. To a given module<i>n</i> the values <i>n</i>₀ and <i>u</i> to determine <i>n</i>₀ as square root of -<i>n</i> modulo 2^<i>l</i> for a <i>l</i> calculated, which is about half the bit length of <i>n</i> having. Such a square root exists only for<i>n</i> ≡ -1 (mod 8). If this condition is not met, then<i>n</i> through 3<i>n</i> or 5<i>n</i> or 7<i>n</i> replaced.

In the present embodiment, for technical reasons, a root - here for <i>m</i> = 2 the square root - the negative module -<i>n</i> used, while in alternative embodiments - with appropriate adaptation of the rest of the procedure - also a root of the module <i>n</i> for the calculation of <i>n</i>₀ can be used.

Is the module lying <i>n</i> With <i>n</i> ≡ -1 (mod 8) before, the bit length becomes <i>l</i> determined by the following relationship:<maths id="math0059" num="(D3)"><math display="block"><mrow><msup><mrow><mtext>16 4</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext><mtext>-1</mtext></mrow></msup><mtext> ≤ </mtext><mfrac><mrow><mtext>16</mtext></mrow><mrow><mtext>15</mtext></mrow></mfrac><mtext> . </mtext><mtext mathvariant="italic">n</mtext><msup><mrow><mtext> &lt; 4</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup></mrow></math><img file="EP1536320A2_D0061.tif" /></maths>

The following will be <i>l</i> ≥ 3 provided. It will now be a natural number<i>n</i>₀ calculated satisfying the following conditions:<maths id="math0060" num="(D4)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext>​</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><mtext> ≡ -</mtext><mtext mathvariant="italic">n</mtext><msup><mrow><mtext> (mod 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext>) and 0 &lt; </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext> &lt; 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext><mtext>-2</mtext></mrow></msup></mrow></math><img file="EP1536320A2_D0062.tif" /></maths>

To calculate a suitable <i>n</i>₀ In the present embodiment, the following method is used for a <i>l</i> With <i>l</i> ≥ 3 and an integer <i>A</i> With <i>A</i> ≡ 1 (mod 8) a sufficiently small square root of <i>A</i> and the inverse <i>Y</i> from <i>X</i> certainly:<maths id="math0061" num=""><img file="EP1536320A2_D0063.tif" /></maths><maths id="math0062" num=""><img file="EP1536320A2_D0064.tif" /></maths>

For the results <i>X</i> and <i>Y</i> After completing this procedure, the following relationships apply:<maths id="math0063" num="(D6)"><math display="block"><mrow><msup><mrow><mtext mathvariant="italic">X</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><mtext> ≡ </mtext><mtext mathvariant="italic">A</mtext><msup><mrow><mtext> (mod 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext>) and </mtext><mtext mathvariant="italic">X</mtext><mtext> · </mtext><mtext mathvariant="italic">Y</mtext><msup><mrow><mtext> ≡ 1 (mod 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext>) and 0 &lt; </mtext><mtext mathvariant="italic">X</mtext><msup><mrow><mtext> &lt; 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext><mtext>-2</mtext></mrow></msup></mrow></math><img file="EP1536320A2_D0065.tif" /></maths>

The validity of the relations (D6) results from the observation that after each loop through the steps (D5.2) - (D5.5) the relations X² ≡ <i>A</i> (mod 2^λ) and <i>X</i> · <i>Y</i> ≡ 1 (mod 2^λ) be valid. After completion of the loop thus apply<i>X</i>² ≡ <i>A</i> (mod 2^<i>l</i>) and <i>X</i> · <i>Y</i> ≡ 1 (mod 2^<i>l</i>), and these equivalences are not affected by the steps (D5.6) - (D5.9).

Overall, it is thus possible by the steps (D5.1) - (D5.10) for the division of the module <i>n</i> needed 2-adic square root <i>n</i>₀ calculate by <i>l</i> is determined according to inequality (D3) and <i>A</i> on -<i>n</i> is set. The result value<i>X</i> is the desired square root <i>n</i>₀, The one for the division of the module<i>n</i> also required parameters <i>u</i> follows from the equation <i>u</i> = (<i>n</i>₀² + <i>n</i>) · 2^-<i>l</i>, For the values ​​calculated in this way<i>n</i>₀ and <i>u</i> then applies:<maths id="math0064" num=""><img file="EP1536320A2_D0066.tif" /></maths>

The method according to the steps (D5.1) - (D5.10) can be characterized as a 2-adic Newton iteration. Here, by "2-adic", it is roughly meant that the bits are processed from "right to left" instead of incrementing the accuracy step by step by processing the digits from "left to right" as in the normal Newton iteration. In this context, Hensel's lemma, which is known per se from number theory, is pertinent.

In the case <i>m</i> &gt; 2 is <i>n</i>₀ as one <i>m</i>-th root of <i>n</i> modulo 2^<i>l</i> or as one <i>m</i>-th root of -<i>n</i> modulo 2^<i>l</i> to calculate.

As already mentioned, in the present embodiment for <i>m</i> = 2 also the factors <i>a</i> and <i>b</i> in each one value pair (<i>a</i>₀, <i>a</i>₁), (<i>b</i>₀<i>,</i> b₁) with μn₀, L (<i>a</i>₀, <i>a</i>₁) ≡ <i>a</i> (mod <i>n</i>) and μn₀, L (<i>b</i>₀, <i>b</i>₁) ≡ <i>b</i> (mod <i>n</i>) divided up. The calculation of<i>a</i>₀, <i>a</i>₁ is done by applying the following relationships:<maths id="math0065" num="(D8)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">a</mtext><mtext> · </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext>​</mtext></mrow><mrow><mtext>-1</mtext></mrow></msup><msup><mrow><mtext> mod 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> and </mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> = (</mtext><mtext mathvariant="italic">a</mtext><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext></mtext><msub><mrow><mtext mathvariant="italic">· N</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext>) · 2</mtext></mrow><mrow><mtext>-</mtext><mtext mathvariant="italic">l</mtext></mrow></msup></mrow></math><img file="EP1536320A2_D0067.tif" /></maths>

The value <i>n</i>₀^-1 mod 2^<i>l</i> is in the division of <i>n</i> in steps (D5.1) - (D5.10) as "by-product", namely as result value <i>Y</i>, calculated. The coefficients<i>b</i>₀ and <i>b</i>₁ will be charged accordingly.

The coefficients calculated according to (D8) <i>a</i>₁ and <i>b</i>₁ may be negative. The XMM still to be performed with these coefficients_<i>l</i>However, operations are defined only for positive arguments, so that a compatible with the μ-representation reduction of the coefficients to the allowable value range 0, ..., 2^<i>l</i>-1 is required.

The procedure described below is for all bit lengths <i>l</i> and values <i>u</i>, <i>n</i>⁰ ∈ <img file="EP1536320A2_D0068.tif" /> applicable to the conditions <i>n</i>₀ &lt; 2^<i>l</i>-2 , <i>u</i> &lt; 2^<i>l</i> and <i>u</i> - <i>n</i>₀ ≥ <maths id="math0066" num=""><math display="inline"><mrow><mfrac><mrow><mtext>3</mtext></mrow><mrow><mtext>64</mtext></mrow></mfrac></mrow></math><img file="EP1536320A2_D0069.tif" /></maths> · 2^<i>l</i> fulfill. The method generally serves to reduce a value pair (<i>x</i>₀, <i>x</i>₁) ∈ <img file="EP1536320A2_D0070.tif" />² to a pair of result values ​​(<maths id="math0067" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0071.tif" /></maths>, <maths id="math0068" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0072.tif" /></maths>) ∈ <img file="EP1536320A2_D0073.tif" /> such that 0 ≤ <maths id="math0069" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0074.tif" /></maths> , <maths id="math0070" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0075.tif" /></maths> &lt; 2^<i>l</i> and μ_{<i>n</i><sub2>0</sub2>,<i>l</i>}(<maths id="math0071" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0076.tif" /></maths>, <maths id="math0072" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0077.tif" /></maths>) ≡ μ_{<i>n</i><sub2>0</sub2>,<i>l</i>}(<maths id="math0073" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0078.tif" /></maths> , <maths id="math0074" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">x</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0079.tif" /></maths>) (mod <i>u</i> · 2^<i>l</i> - <i>n</i>₀²) be valid. The following process steps are carried out:<maths id="math0075" num=""><img file="EP1536320A2_D0080.tif" /></maths>

The correctness of the method results from the fact that none of the assignments in steps (D9.3), (D9.4), (D9.7) and (D9.8) has the value μ_{<i>n</i><sub2>0</sub2>,<i>l</i>}(<i>x</i>₀, <i>x</i>₁) modulo <i>u ·</i> 2^<i>l</i> - <i>n</i>₀² changed. The method terminates because each time the first loop passes, the smaller of the values<i>x</i>₀, <i>x</i>₁ at least <maths id="math0076" num=""><math display="inline"><mrow><mfrac><mrow><mtext>3</mtext></mrow><mrow><mtext>64</mtext></mrow></mfrac></mrow></math><img file="EP1536320A2_D0081.tif" /></maths> . 2^<i>l</i> increases, and because with each pass of the second loop the larger of the values <i>x</i>₀, <i>x</i>₁ at least <maths id="math0077" num=""><math display="inline"><mrow><mfrac><mrow><mtext>3</mtext></mrow><mrow><mtext>64</mtext></mrow></mfrac></mrow></math><img file="EP1536320A2_D0082.tif" /></maths> .2^<i>l</i> decreases.

The method according to steps (D9.1) - (D9.9) is applied both to the coefficients (<i>a</i>₀<i>, a</i>₁) and the coefficients (<i>b</i>₀, <i>b</i>₁), wherein <i>l</i>, <i>u</i> and <i>n</i>₀ according to (D3) and (D7). These parameter values ​​satisfy the preconditions required for the method. After the reduction, the relationships μ apply_{<i>n</i><sub2>0</sub2>,<i>l</i>}(<i>a</i>₀, <i>a</i>₁) ≡ μ_{<i>n</i><sub2>0</sub2>,<i>l</i>}(<maths id="math0078" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0083.tif" /></maths> , <maths id="math0079" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0084.tif" /></maths>) (mod <i>n</i>) and μ_{<i>n</i><sub2>0</sub2>,<i>l</i>}(<i>a</i>₀, <i>a</i>₁) ≡ μ_{<i>n</i><sub2>0,</sub2><i>l</i>}(<maths id="math0080" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">b</mtext></mrow><mrow><mtext mathvariant="italic">0</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0085.tif" /></maths>, <maths id="math0081" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">b</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0086.tif" /></maths>) (mod <i>n</i>). For the sake of simplicity, the result values ​​(<maths id="math0082" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0087.tif" /></maths> , <maths id="math0083" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>1</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0088.tif" /></maths>) and (<maths id="math0084" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">b</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0089.tif" /></maths>, <maths id="math0085" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">b</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>)</mtext></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0090.tif" /></maths> in the following again with (<i>a</i>₀, <i>a</i>₁) respectively. (<i>b</i>₀, <i>b</i>₁) designated.

The following procedure performs Montgomery multiplication for factors <i>a, b</i> the bit length <i>L</i> and a given module <i>n</i> the bit length <i>L</i> out. The method sets precalculated values<i>l</i>, <i>u</i>, <i>n</i>₀ ∈ <img file="EP1536320A2_D0091.tif" /> and <i>a</i>₀, <i>a</i>₁, <i>b</i>₀, <i>b</i>₁ ∈ <img file="EP1536320A2_D0092.tif" /> that have the following properties:<maths id="math0086" num="(D10.1)"><math display="block"><mrow><mtext mathvariant="italic">n</mtext><mtext> = </mtext><mtext mathvariant="italic">u</mtext><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext>​</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><mtext> and 0 &lt; </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext> &lt; 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext><mtext>-2</mtext></mrow></msup></mrow></math><img file="EP1536320A2_D0093.tif" /></maths><maths id="math0087" num="(D10.2)"><math display="block"><mrow><mtext>μ</mtext><msub><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext>,</mtext><mtext mathvariant="italic">l</mtext></mrow></msub><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext>, </mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>) ≡ </mtext><mtext mathvariant="italic">a</mtext><mtext> (mod </mtext><mtext mathvariant="italic">n</mtext><mtext>) and 0 ≤ </mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext>, </mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext> &lt; 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup></mrow></math><img file="EP1536320A2_D0094.tif" /></maths><maths id="math0088" num="(D10.3)"><math display="block"><mrow><mtext>μ</mtext><msub><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext>,</mtext><mtext mathvariant="italic">l</mtext></mrow></msub><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">b</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext>, </mtext><msub><mrow><mtext mathvariant="italic">b</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>) ≡ </mtext><mtext mathvariant="italic">b</mtext><mtext> (mod </mtext><mtext mathvariant="italic">n</mtext><mtext>) and 0 ≤ </mtext><msub><mrow><mtext mathvariant="italic">b</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext>, </mtext><msub><mrow><mtext mathvariant="italic">b</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext> &lt; 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup></mrow></math><img file="EP1536320A2_D0095.tif" /></maths>

In the present embodiment, these values ​​are calculated by the steps already described, namely the bit length <i>l</i> determined according to relationship (D3), <i>n</i>₀ is calculated by the steps (D5.1) - (D5.10), <i>u</i> is determined by relationship (D7), and <i>a</i>₀, <i>a</i>₁ respectively. <i>b</i>₀, <i>b</i>₁ are calculated according to relationship (D8) as well as by a reduction process with the steps (D9.1) - (D9.9).

The multiplication method calculates result values ​​(<i>c</i>₀, <i>c</i>₁) ∈ <img file="EP1536320A2_D0096.tif" /> with 0 ≤ <i>c</i>₀, <i>c</i>₁ &lt; 2^<i>l</i>so that μ_{<i>n</i><sub2>0</sub2>,<i>l</i>}(<i>c</i>₀, <i>c</i>₁) ≡ <i>a · b</i> · 2^-2<i>l</i> (mod <i>n</i>) applies. The following steps are performed:<maths id="math0089" num=""><img file="EP1536320A2_D0097.tif" /></maths><maths id="math0090" num=""><img file="EP1536320A2_D0098.tif" /></maths>

The addition of tuples in step (D11.2) is performed component by component. The operation mentioned in steps (D11.5), (D11.7) and (D11.9)<i>reduce</i> is the compatible with the μ-representation reduction modulo <i>n</i>, which can be done, for example, by the method according to the steps (D9.1) - (D9.9).

Also, the method according to the steps (D11.1) - (D11.10) has a multiplication part and a reduction part. The multiplication takes place in steps (D11.1) - (D11.3). Similar to the procedure described in Section C, the intermediates are prepared by using XMM_<i>l</i>(<i>a</i>_<i>j</i>, <i>b</i>_<i>k</i>, <i>n</i>₀) in two each <i>l</i> Bits decomposed long partial coefficients. In the general case<i>m</i> ≥ 2, this decomposition has the following form, with negative values ​​for <maths id="math0091" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">q</mtext></mrow><mrow><mtext mathvariant="italic">jk</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0099.tif" /></maths> occur:<maths id="math0092" num="(D12)"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext> · </mtext><msub><mrow><mtext mathvariant="italic">b</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub><mtext> = </mtext><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">p</mtext></mrow><mrow><mtext mathvariant="italic">jk</mtext></mrow></msub></mrow><mo>¯</mo></mover><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> + </mtext><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">q</mtext></mrow><mrow><mtext mathvariant="italic">jk</mtext></mrow></msub></mrow><mo>¯</mo></mover><mtext> · </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>0</mtext></mrow></msub></mrow></math><img file="EP1536320A2_D0100.tif" /></maths>

In contrast to the method according to Section C, in the present method no case distinction is required with regard to the decomposition method used, but the splitting according to (D12) is always used. This increased homogeneity has the advantage that, in alternative embodiments, more efficient multiplication techniques can be used. For example, in a variant to be described in more detail below, XMM_<i>l</i>Saving operations by using a known under the name Karatsuba multiplication technique is applied.

In general, the multiplication part of the method can be expressed in the following representation, which is based on (C3), where <maths id="math0093" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">p</mtext></mrow><mrow><mtext mathvariant="italic">jk</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0101.tif" /></maths> and <maths id="math0094" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">q</mtext></mrow><mrow><mtext mathvariant="italic">jk</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1536320A2_D0102.tif" /></maths> the result of the decomposition of <i>a</i>_<i>j</i> · <i>b</i>_<i>k</i> state according to (D12):<maths id="math0095" num=""><img file="EP1536320A2_D0103.tif" /></maths>

The following is again the special case <i>m</i> = 2 according to the procedure (D11.1) - (D11.10). After step (D11.4), the occupancy of the coefficients given by equation (D13)<i>H</i>_<i>i</i> which is advertised by the following formula:<maths id="math0096" num="(D14)"><math display="block"><mrow><mtext mathvariant="italic">a</mtext><mtext> · </mtext><mtext mathvariant="italic">b</mtext><mtext> ≡ </mtext><msub><mrow><mtext mathvariant="italic">H</mtext></mrow><mrow><mtext>3</mtext></mrow></msub><mtext> · </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext>​</mtext></mrow><mrow><mtext>3</mtext></mrow></msup><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">H</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext>. </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext>​</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">H</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext>. 2</mtext></mrow><mrow><mtext>2</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> · </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">H</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>3</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">n</mtext><mtext>)</mtext></mrow></math><img file="EP1536320A2_D0104.tif" /></maths>

Applying the Reduce function to a pair (<i>H</i>_<i>i</i>, <i>H</i>_<i>i</i>+1) modulates its sum modulo <i>n</i> Not.

The leading term of (D14) is now eliminated. This is the relationship<i>H</i>₃<i>· N</i>₀² ≡ <i>k</i>₁ · 2^2<i>l</i> - <i>k</i>₂ · <i>n</i>₀ · 2^<i>l</i> (mod <i>n</i>), which is composed of (D7), a reduction modulo <i>n</i> and (B1) for XMM <i>l</i>(<i>H</i>₃, <i>u</i>, <i>n</i>₀). After the reduction step (D11.7) then:<maths id="math0097" num="(D15)"><math display="block"><mrow><mtext mathvariant="italic">a · b</mtext><mtext> ≡ </mtext><msub><mrow><mtext mathvariant="italic">q</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msup><mtext></mtext><msub><mrow><mtext mathvariant="italic">· N</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext>​</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">q</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>2</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> · </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">H</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>3</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> (mod </mtext><mtext mathvariant="italic">n</mtext><mtext>)</mtext></mrow></math><img file="EP1536320A2_D0105.tif" /></maths>

Similarly, in another reduction step, the leading term of (D15) is eliminated by changing the relationship <i>q</i>₂ · <i>n</i>₀² ≡ <i>m</i>₀ · 2^2<i>l</i> - <i>m</i>₁<i>· N</i>₀ · 2^<i>l</i> (mod <i>n</i>) is applied. To determine the coefficients<i>m</i>₀ and <i>m</i>₁ In step (D11.8), the operation XMM_<i>l</i>(<i>q</i>₂, <i>u</i>, <i>n</i>₀). After the reduction in step (D11.9), the result is:<maths id="math0098" num="(D16)"><math display="block"><mrow><mtext mathvariant="italic">a · b</mtext><mtext> ≡ </mtext><msub><mrow><mtext mathvariant="italic">c</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>2</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> · </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">c</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msup><mrow><mtext> · 2</mtext></mrow><mrow><mtext>3</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><msup><mrow><mtext> ≡ 2</mtext></mrow><mrow><mtext>2</mtext><mtext mathvariant="italic">l</mtext></mrow></msup><mtext> · Μ</mtext><msub><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext>,</mtext><mtext mathvariant="italic">l</mtext></mrow></msub><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">c</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext>, </mtext><msub><mrow><mtext mathvariant="italic">c</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>) (mod </mtext><mtext mathvariant="italic">n</mtext><mtext>)</mtext></mrow></math><img file="EP1536320A2_D0106.tif" /></maths>

The method according to the steps (D11.1) - (D11.10) requires four multiplication parts and two XMM; operations for the reduction part. As already mentioned, the number of XMM can be_<i>l</i>Reduce operations for the multiplication part to three, by instead of the "scholastic" multiplication according to (D13) a Karatsuba multiplication is carried out, for example from the <i>Article "Multiplication of multidigit numbers on automata"</i> by A. Karatsuba and Yu. Ofman, Soviet Physics - Dokladay, 7, 1963, pages 595-596, is known per se.

In an embodiment using the Karatsuba multiplication, step (D11.3) of the method described above is preferred, and step (D11.2) is replaced by the following calculation and assignment:<maths id="math0099" num="(D17)"><math display="block"><mrow><mtext>SET (</mtext><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext>, </mtext><msub><mrow><mtext mathvariant="italic">e</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext>): = XMM</mtext></mrow><mrow><mtext mathvariant="italic">l</mtext></mrow></msub><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>, </mtext><msub><mrow><mtext mathvariant="italic">b</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">b</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext>, </mtext><msub><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext>) + (</mtext><msub><mrow><mtext mathvariant="italic">d</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext>, </mtext><msub><mrow><mtext mathvariant="italic">d</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>) + (</mtext><msub><mrow><mtext mathvariant="italic">f</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext>,</mtext><msub><mrow><mtext mathvariant="italic">f</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP1536320A2_D0107.tif" /></maths>

The definition XMM applies here_<i>l</i>(-<i>x</i>, <i>y</i>, <i>n</i>₀) = XMM_<i>l</i>(<i>x</i>, -<i>y</i>, <i>n</i>₀) = -XMM_<i>l</i>(<i>x</i>(, <i>y</i>, <i>n</i>₀) for positive numbers <i>x</i> and <i>y</i>, In this embodiment, therefore, an XMM_<i>l</i>Saved operation, so that a Montgomery multiplication with doubled bit length can be based on five extended Montgomery multiplications with simple bit length. General is for<i>m</i> = 2^α the computational effort for the multiplication part 3 carried out by the Karatsuba method 3^α instead of 4^α XMM_<i>l</i>Operations.

Even the process according to the steps (D11.1) - (D11.10) already saves XMM compared to the methods described in section C._<i>l</i>Operations, and this saving can be further increased by the just described alternative embodiment. The smaller number of XMM_<i>l</i>However, operations are paid for by additional ancillary calculations, in particular by the calculations that are required to get out of the usual binary representation of <i>a</i> and <i>b</i> the representation with coefficients <i>a</i>₀, <i>a</i>₁, <i>b</i>₀, <i>b</i>₁ according to (D8). Depending on the processor environment in which the extended bit length Montgomery multiplication is to be performed, it may therefore be advisable to use either a method in accordance with Section C or one of the methods described in this Section D.

It should be understood that the details contained in the above description of embodiments should not be construed as limitations on the scope of the invention. Many modifications and other alternative embodiments are possible and obvious to those skilled in the art. Thus, for example, the above-mentioned computation steps can be rearranged or completely or partially parallel or completely or partially interlinked (<i>interleaved</i>). The scope of the invention should therefore be determined not by the above embodiments, but by the following claims.