# US 2003/0208518 A1 · Generic implementations of ellipitic curve cryptography using partial reduction

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2003/0208518 A1
- Document ID: US20030208518A1
- Status: Published application
- Kind: A1
- Application number: 10/387,104
- Filed: 2003-03-11
- Published: 2003-11-06
- Earliest claimed: 2002-05-01
- Assignees: Sun Microsystems, Inc.
- Inventors: Nils Gura; Hans Eberle; Edouard Goupy
- Web page: https://patentgrep.com/patent/US20030208518A1

## CPC

- G06F 7/724: {Finite field arithmetic (for error detection or correction in general H03M13/00, in computers G06F11/10)}
- G06F 7/527: in serial-parallel fashion, i.e. one operand being entered serially and the other in parallel (G06F7/533 takes precedence)
- G06F 7/725: {over elliptic curves}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A reduction operation is utilized in an arithmetic operation on two binary polynomials X(t) and Y(t) over GF(2), where an irreducible polynomial Mm(t)=tm+am−1tm−1+am−2tm−2+ . . . +a1t+a0, where the coefficients as are equal to either 1 or 0, and m is a field degree. The reduction operation includes partially reducing a result of the arithmetic operation on the two binary polynomials to produce a congruent polynomial of degree less than a chosen integer n, with m≦n. The partial reduction includes using a polynomial M′=(Mm(t)−tm)*tn−m, or a polynomial M″=Mm(t)*tn−m as part of reducing the result to the degree less than n and greater than or equal to m. The integer n can be the data path width of an arithmetic unit performing the arithmetic operation, a multiple of a digit size of a multiplier performing the arithmetic operation, a word size of a storage location, such as a register, or a maximum operand size of a functional unit in which the arithmetic operation is performed.

## Claims

### Claim 1

A method for performing an arithmetic operation on two binary polynomials X(t) and Y(t) over GF(2), where an irreducible polynomial Mm(t)=tm+am−1tm−1+am−2tm−2+ . . . +a1t+a0, where the coefficients ai are equal to either 1 or 0, and m is a field degree, comprising:
partially reducing a result of the arithmetic operation on the two binary polynomials to produce a congruent polynomial of degree less than a chosen integer n, with m≦n.

### Claim 2 (depends on 1)

The method as recited in claim 1 further comprising using at least one of a first and second polynomial M′ and M″, respectively, as part of reducing the result to the degree less than n and greater than or equal to m, M′=(Mm(t)−tm)*tn−m and M″=(Mm(t)*tn−m).

### Claim 3 (depends on 2)

The method as recited in claim 2 wherein n is a data path width of an arithmetic unit performing the arithmetic operation.

### Claim 4 (depends on 2)

The method as recited in claim 2 wherein the arithmetic operation is a multiplication and n is a multiple of a digit size of a multiplier performing the multiplication.

### Claim 5 (depends on 2)

The method as recited in claim 2 wherein n is a multiple of a word size of a storage location.

### Claim 6 (depends on 5)

The method as recited in claim 5 wherein the storage location is a register.

### Claim 7 (depends on 2)

The method as recited in claim 2 where n is a maximum operand size of an functional unit in which the arithmetic operation is performed.

### Claim 8

A method for performing a multiplication on two binary polynomials X(t) and Y(t) over GF(2), where an irreducible polynomial Mm(t)=tm+am−1tm−1+am−2tm−2+ . . . +a1t+a0, where the coefficients ai are equal to either 1 or 0, and m is a field degree, comprising:
splitting a result co from the multiplication of X(t) and Y(t) into a low portion c0,1 and a high portion c0,h such that c0=c0,h* tn+c0,1, where n is greater than or equal to the field degree m; and
partially reducing the result co of the multiplication by executing a series of polynomial multiplications and additions to produce a polynomial of degree less than n and congruent to co modulo Mm(t).

### Claim 9 (depends on 8)

The method as recited in claim 8 wherein partially reducing the result comprises:
iteratively determining successive congruent polynomials cj+1=cj,h* tn−m*(Mm(t)−tm)+cj,l,=cj+1,h*tn+cj+1,l, until cj,h=0, where initially j=0.

### Claim 10 (depends on 8)

The method as recited in claim 8 wherein partially reducing the result comprises:
iteratively determining successive congruent polynomials cj+1=cj,h*tn−m*Mm(t)+cj=cj+1,h*tn+cj+1,l, until cj,h=0, where initially j=0.

### Claim 11 (depends on 8)

The method as recited in claim 8 wherein n is a maximum operand size of a multiplier in which the multiplication is performed.

### Claim 12 (depends on 8)

The method as recited in claim 8 wherein n is a data path width of the multiplier.

### Claim 13 (depends on 8)

The method as recited in claim 8 wherein n is a multiple of a digit size of the multiplier.

### Claim 14 (depends on 8)

The method as recited in claim 8 wherein n is a multiple of a word size of a memory.

### Claim 15

An elliptic curve processing apparatus for performing a multiplication of two elements X(t) and Y(t), over GF(2), where m is a field degree, and Mm(t) is an irreducible polynomial for GF(2m), Mm(t)=tm+am−1tm−1+am−2tm−2+ . . . +a1t+a0, where the coefficients ai are equal to either 1 or 0, and m is a field degree, comprising:
means for multiplying a first register (X) storing an initial value of X(t) and a second register Y storing an initial value of Y(t) and generating a result c0=X(t)*Y(t);
means for providing c0 as a low portion c0,l and a high portion c0,h such that c0=c0,h*tn+c0,l, where n is greater than or equal to the field degree m; and
means for partially reducing the result co of the multiplication by executing a series of polynomial multiplications and additions to produce a polynomial of degree less than n and congruent to c0 modulo Mm(t).

### Claim 16 (depends on 15)

The elliptic curve processing apparatus as recited in claim 15 wherein the means for partially reducing comprises:
means for iteratively determining successive congruent polynomials cj+1=cj,h*tn−m*(Mm(t)−tm)+cj,l,=cj+1,h*tn+cj+1,l, until cj,h=0, where j initially=0.

### Claim 17 (depends on 15)

The elliptic curve processing apparatus as recited in claim 15 wherein the means for partially reducing comprises:
means for iteratively determining successive congruent polynomials cj+1=cj,h*tn−m*Mm(t)+cj=cj+1,h*tn+cj+1,l, until cj,h=0, where j initially=0.

### Claim 18 (depends on 15)

The elliptic curve processing apparatus as recited in claim 15 wherein n is at least one of a maximum operand size, a data path width, a multiple of a digit size, a multiple of a word size of memory, and a register size in the elliptic curve processing apparatus.

### Claim 19

An elliptic curve processing apparatus for performing a squaring operation of an element X(t), over GF(2), where m is a field degree, and Mm(t) is an irreducible polynomial for GF(2m), comprising:
means for squaring X(t) to generate a result c0=X(t)*X(t);
means for providing c0 as a low portion c0,l and a high portion c0,h such that c0=c0,h*tn+c0,l, where n is greater than or equal to the field degree m; and
means for partially reducing the result c0 of the multiplication by executing a series of polynomial multiplications and additions to produce a polynomial of degree less than n and congruent to c0 modulo Mm(t).

### Claim 20

A computer program product encoded on computer readable media comprising:
a first instruction sequence for multiplying a first polynomial X(t) and a second polynomial Y(t), both over GF(2), to generate a result c0;
a second instruction sequence for partially reducing the result c0 of the multiplication by executing a series of polynomial multiplications and additions to produce a polynomial of degree less than n, the polynomial of degree less than n, being congruent to c0 modulo Mm(t), Mm(t)=tm+am−1tm−1+am−2tm−2+ . . . +a1t+a0, where the coefficients ai are equal to either 1 or 0, and m is a field degree, and
where n is at least one of a maximum operand size, a data path width, a multiple of a digit size, and a multiple of a word size of memory, and a multiple of a register size available in a processor in which the computer program product is executed.

### Claim 21 (depends on 20)

The computer program product as recited in claim 20 wherein the second instruction sequence generates a polynomial c1, congruent to c0 modulo M(t), c1 being equal to c0,h*tn−m*(Mm(t)−tm)+c0,l, where c0,l is a low portion and c0,h is a high portion such that c0=c0,h*tn+c0,l, where n is greater than or equal to the field degree m and for iteratively determining successive congruent polynomials cj+1=cj,h*tn−m*(Mm(t)−tm)+cj,l,=cj+1,h*tn+cj+1,l, until cj,h=0, where initially j=0, the successive congruent polynomials being congruent to co modulo Mm(t).

### Claim 22

A computer program product encoded on computer readable media comprising:
a first instruction sequence for performing an arithmetic operation on two binary polynomials X(t) and Y(t) over GF(2) to generate a result c0, where an irreducible polynomial Mm(t)=tm+am−1tm−1+am−2tm−2+ . . . +a1t+a0, and where the coefficients as are equal to either 1 or 0, and m is a field degree, the result co being of a degree greater than or equal to n;
a second instruction sequence for partially reducing the result of the arithmetic operation on the two binary polynomials to produce a congruent polynomial of degree less than an integer n, with m being less than or equal to n, the second instruction sequence using one of a first and second polynomial M′ and M″, as part of partially reducing the result c0, M′=(Mm(t)−tm)*tn−m and M″=(Mm(t)*tn−m).

### Claim 23

A method for performing an arithmetic operation on a first and second binary polynomial X(t) and Y(t) over GF(2), where an irreducible polynomial Mm(t)=tm+am−1tm−1+am−2tm−2+ . . . +a1t+a0, and where the coefficients ai are equal to either 1 or 0, and m is a field degree, the first and second binary polynomials being of degree less than m, the method comprising:
multiplying one of the polynomials and tn−m to left align the first binary polynomial in an n bit register;
multiplying the left-aligned first binary polynomial and the second binary polynomial to generate a result of 2n bits with a high order portion of the result being n most significant bits and a low portion of the result being n least significant bits; and
reducing the result until the high order portion is zero, thereby providing a reduced result in the low order portion.

### Claim 24 (depends on 23)

The method as recited in claim 23 further comprising aligning the result in the low order portion.

### Claim 25 (depends on 24)

The method as recited in claim 24 wherein aligning the result comprises multiplying the reduced result by tm to align the reduced result in the high order portion.

### Claim 26 (depends on 23)

The method as recited in claim 23 wherein reducing the result comprises multiplying the high order portion and one of a first and second polynomial M′ and M″, M′=(Mm(t)−tm)*tn−m and M″=(Mm(t))*tn−m.

### Claim 27

An apparatus for performing an arithmetic operation on a first and second binary polynomial X(t) and Y(t) over GF(2), where an irreducible polynomial Mm(t)=tm+am−1tm−1+am−2tm−2+ . . . +a1t+a0, and where the coefficients ai are equal to either 1 or 0, and m is a field degree, the first and second binary polynomials being of degree less than m, the apparatus comprising:
means for multiplying one of the polynomials and tn−m to left align the first binary polynomial in an n bit register;
means for multiplying the left-aligned first binary polynomial and the second binary polynomial to generate a result of 2n bits with a high order portion of the result being n most significant bits and a low portion of the result being n least significant bits; and
means for reducing the result until the high order portion is zero, thereby providing a reduced result in the low order portion.

### Claim 28 (depends on 27)

The apparatus as recited in claim 27 further comprising means for aligning the reduced result.
