Modular squaring in binary field arithmetic
AssigneeResearch In Motion Limited
InventorNevine Maurice Nassif EBEID
Life of this patent
Estimating the term…
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.
Claims7
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.
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.
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.
Dependencies are inferred from the claim text.