MODULAR SQUARING IN BINARY FIELD ARITHMETIC

• US 20090157788A1
• Filed: 10/31/2008
• Published: 06/18/2009
• Est. Priority Date: 10/31/2007
• Status: Abandoned Application

• Current Assignee: Research In Motion Limited (Blackberry Limited)
• Original Assignee: Research In Motion Limited (Blackberry Limited)
• Inventors: EBEID, Nevine Maurice Nassif
• Application Number:
  US12/262,595
• Publication Number:
  US 20090157788A1
• Time in Patent Office: Days
• US Class Current: 708/606
• CPC Class Codes: G06F 7/724 Finite field arithmetic for error detection or correction in general H03M13/00, in computers G06F11/10

Abstract

After squaring an element of a binary field, the squaring result may be reduced modulo the field-defining polynomial g bits at a time. To this end, a lookup table may be employed, where the lookup table stores entries corresponding to reducing g-bit-long polynomials modulo the field-defining polynomial. Such a reducing strategy may be shown to be more efficient than a bit-by-bit reducing strategy.

Claims

1. A method of obtaining a modular product of a n-bit polynomial and itself in a field defined by a field polynomial, said method comprising:

receiving, from a requester, said n-bit polynomial and a request for a square of said n-bit polynomial;

representing a squaring result of said n-bit polynomial as a (2n−

1)-bit polynomial having;

a first portion that is the most significant g bits of said squaring result;

a second portion that is the next most significant n bits of said squaring result after said most significant g bits; and

a third portion that is the remaining bits of said squaring result after removal of said first portion and said second portion;

reducing said first portion modulo said field polynomial, thereby producing a (g+d)-bit reduction, where d is a second highest degree of said field polynomial;

forming a sum of said reduction and said second portion with least significant bits aligned;

assigning, to said squaring result, a concatenation of said third portion to said sum;

repeating said representing, said reducing, said forming and said assigning until said squaring result has a length of n bits; and

returning said squaring result.

2. The method of claim 1 further comprising defining a table of reductions of g-bit-long polynomials modulo said field polynomial.

3. The method of claim 2 wherein said reducing comprises performing a look-up in said table with said first portion of said squaring result as an index.

4. The method of claim 1 further comprising padding said (2n−

1)-bit squaring result polynomial with g−

(n−

1) mod g zeros on the left.

5. The method of claim 1 further comprising selecting g such that a word size, w, of a processor carrying out said method is an integer multiple of g.

6. A mobile communication device for cryptographically securing a message, said mobile communication device comprising:

a processor adapted to;

receive, from a requester, an n-bit polynomial and a request for a square of said n-bit polynomial in a field defined by a field polynomial;

represent a squaring result of said n-bit polynomial having;

a first portion that is the most significant g bits of said squaring result;

a second portion that is the next most significant n bits of said squaring result after said most significant g bits; and

a third portion that is the remaining bits of said squaring result after removal of said first portion and said second portion;

reduce said first portion modulo said field polynomial, thereby producing a (g+d)-bit reduction, where d is a second highest degree of said field polynomial;

form a sum of said reduction and said second portion with least significant bits aligned;

assign, to said squaring result, a concatenation of said third portion to said sum;

repeat said representing, said reducing, said forming and said assigning until said squaring result has a length of n bits; and

return said squaring result.

7. A computer readable medium containing computer-executable instructions that, when performed by processor, cause said processor to:

receive, from a requester, an n-bit polynomial and a request for a square of said n-bit polynomial in a field defined by a field polynomial;

represent a squaring result of said n-bit polynomial as a (2n−

1)-bit polynomial having;

a first portion that is the most significant g bits of said squaring result;

a second portion that is the next most significant n bits of said squaring result after said most significant g bits; and

a third portion that is the remaining bits of said squaring result after removal of said first portion and said second portion;

reduce said first portion modulo said field polynomial, thereby producing a (g+d)-bit reduction, where d is a second highest degree of said field polynomial;

form a sum of said reduction and said second portion with least significant bits aligned;

assign, to said squaring result, a concatenation of said third portion to said sum;

repeat said representing, said reducing, said forming and said assigning until said squaring result has a length of n bits; and

return said squaring result.