1. A method for communicating securely over an insecure communication channel between a pair of correspondents who perform shared key cryptographic operations by implementing respective ones of a pair of complimentary mathematical operations utilizing the scalar multiplication of a shared key represented as a value and a base point, said method comprising the steps of:
assembling a data string including information to be transferred from a sending correspondent to a receiving corresponding;
performing a complimentary mathematical operation using points that satisfy an elliptic polynomial equation with more than one quadratic variable that are termed y-coordinates wherein all the corresponding coordinates of such points are elements of a finite field, F, and wherein the addition of any two of these elliptic points is defined over an extended dimensional that incorporates the additional y-coordinates, and wherein this point addition is computed using arithmetic over a finite field, F; and
forwarding the defined set of points over a communication channel to the receiving correspondent and performing the other of the corresponding mathematical cryptographic operations to decrypt the data.
2. A method for communicating securely over an insecure communication channel between a pair of correspondents according to claim 1 using an elliptic polynomial equation which includes the sum of many monomials and wherein the equation has more than two independent variables such that:
(a) the maximum total degree of any monomial in the polynomial is three,
(b) at least two variables, termed the y-coordinates, have a maximum degree of two, and at least one must appear in one of monomial on its own with a degree of two,
(c) at least one variable, termed the x-coordinate, has a maximum degree of three, and must appear in one of the monomials with a degree of three.
3. A method of encrypting and decrypting a message bit string in an information processing system by implementing respective ones of a pair of complimentary mathematical operations using the scalar multiplication of a shared key represented as a scalar value and a base point, said method comprising the steps of:
assembling a data string including information to be transferred from a sending correspondent to a receive correspondent;
performing a complimentary mathematical operation using points that satisfy an elliptic polynomial equation with more than one quadratic variable termed y-coordinates wherein all the corresponding coordinates of such points are elements of a finite field, F, and wherein the addition of any two of these elliptic points is defined over an extended dimensional space that incorporates the additional y-coordinates, and wherever the point addition is computed using arithmetic over a finite field, F; and
using an elliptic polynomial equation which includes the sum of many monomials and wherein the equation has more than two independent variable such that;
(a) the maximum total degree of any monomial in the polynomial is three,
(b) at least two variables, termed by y-coordinates, have a maximum degree of two, and at least one must appear in one of monomial on its own with a degree of two,
(c) at least one variable, termed the x-coordinate, has a maximum degree of three, and must appear in one of the monomials with a degree of three;
wherein the representation of the corresponding elliptic points includes more than one y-coordinate, wherein all the corresponding coordinates of such points are elements of F represented in N-bit strings, and which includes a step where extra message bits are embedded in the additional y-coordinates;
forwarding the defined set of points over a communication channel to the receiving correspondent and performing the other of the correspondents mathematical cryptography operations to decrypt the data.
4. A method of encrypting and decrypting a message bit string in an information processing system in accordance with claim 3 wherein predetermined mappings are used to indicate that an elliptic point that has more than one y-coordinate is equivalent to one or more elliptic points that satisfy the same elliptic polynomial equation with more than one y-coordinate, wherein the elliptic points that are equivalent to each other can be substituted for each other at random or according to certain rules during point addition and point doubling operations, and wherein mappings that indicate that an elliptic point is equivalent to itself are also referenced.
5. A method of encrypting and decrypting a message bit string in an information processing system in accordance with claim 4, wherein ny additional y-coordinates are used and wherein ny is greater than or equal to one, said method comprising the steps of:
embedding a message bit string into the appropriate coordinates including the additional ny y-coordinates, y1, . . . . . . . , & yny, of an elliptic point which is designated as the message point, (\u02dc,y0,m,y1,m, . . . . . . . ,yny,m) where \u02dc denotes coordinates that represent non-quadratic variables of the same point;
providing shared keys, kil for i=1, . . , I, and l=1, . . , L where I & L are greater or equal to one, base points (\u02dc,y0,B(i), y1,B(i), . . . . . . . ,yny,B(i)) for i=1, . . ,I where I is greater or equal to one, compute the point (\u02dc,y0,bk,yl,bk, . . . . . . . ,yny,bk) using,
(
\u223c
,
y
0
,
bk
,
y
1
,
bk
,
\u2026
\u2062
,
y
ny
,
bk
)
=
\u2211
i
=
1
I
\u2062
\u2062
(
k
iL
(
k
iL
–
1
\u2062
\u2062
\u2026
\u2062
\u2062
(
k
il
\u2061
(
\u223c
,
y
0
,
B
\u2061
(
i
)
,
y
1
,
B
\u2061
(
i
)
,
\u2026
\u2062
,
y
ny
,
B
\u2061
(
i
)
)
)
\u2062
\u2062
\u2026
\u2062
)
)
;
computing a cipher point (\u02dc, y0,c, y1,c, . . . . . . . ,yny,c) using (\u02dc,y0,c,y1,c, . . . . . . . ,ymy,c)=(\u02dc,y0,m,y1,m, . . . . . . . ,yny,m)+(\u02dc,y0,bk,y1,bk, . . . . . . . ,yny,bk);
sending appropriate bits of the coordinates of the cipher point including its additional ny y-coordinates, y1,c, . . . . . . . ,& yny,c, and any additional information needed to help the receiving correspondent recover the message bit string without compromising security;
using the shared keys, kil for i=1, . . I and l=1, . . , L where I & L are greater or equal to one, the base points (\u02dc,y0,B(i),y1,B(i), . . . . . . . , yny,B(i)) for i=1, . . ,I where I is greater or equal to one, and if need be any additional information received from the sending correspondent, compute the point (\u02dc, y0,bk,yl,hk, . . . . . . . ,yny,bk) using,
(
\u223c
,
y
0
,
bk
,
y
1
,
bk
,
\u2026
\u2062
,
y
ny
,
bk
)
=
\u2211
i
=
1
I
\u2062
\u2062
(
k
iL
(
k
iL
–
1
\u2062
\u2062
\u2026
\u2062
\u2062
(
k
il
\u2061
(
\u223c
,
y
0
,
B
\u2061
(
i
)
,
y
1
,
B
\u2061
(
i
)
,
\u2026
\u2062
,
y
ny
,
B
\u2061
(
i
)
)
)
\u2062
\u2062
\u2026
\u2062
)
)
;
computing the message point (\u02dc,y0,m,y1,m. . . . . . . ,yny,m) using (\u02dc,y0,m,y1,m, . . . . . . . ,yny,m)=(\u02dc,y0,c,y1,c, . . . . . . . ,yny,c)\u2212(\u02dc,y0,bk,y1,bk, . . . . . . . ,yny,bk) and if need be any additional information received from the sending correspondent;
recovering the message bit string from the appropriate coordinates of the message point including its additional ny y-coordinates, y1,m, . . . . . . . & yny,m, and any additional information received from the sending correspondent.
6. A method of encrypting and decrypting a message bit string in an information processing system in accordance with claim 5 wherein each point operation used to compute the point (\u02dc,y0,bk,y1,bk, . . . . . . . ,yny,bk) is defined over a designated sub-space that contains at least one y-coordinate and one x-coordinate, wherein the variables that denote other coordinates not contained in a designated sub-space are considered as constants, and wherein the designated sub-spaces of different point operations is completely disjoined from each other, or can be shared partially or completely.
7. A method for encrypting and decrypting a message bit string in an information processing system according to claim 6 wherein embedding of the message bit string into an elliptic point with one x-coordinate, x, and (ny+1) y-coordinates, y0,y1, . . . . . . . & yny, comprising the steps of:
dividing a message bit string into M-bit strings where ((ny+1)N-L)>M>(N-L),
dividing each M-bit string into (ny+1) strings mx, my1, . . . , & myny, wherein the length of string mix must be no more than (N-L) bits, while the length of each of the other \u201cny\u201d strings my1, . . . , & myny must be no more than N bits, and wherein each one of the (ny+1) bit strings must have an equivalent value which is element of the underlying finite field F,
assigning the value of the bit strings of my1, . . . , & myny to y1, . . . . . . . & yny,
assigning the value of the bit string of mx to x
substituting the values of x and y1, . . . . . . . & yny in a selected elliptic polynomial equation with one x-coordinate and (ny+1) y-coordinates to form a quadratic equation in y0,
y02+Ay0+B=0
if the quadratic equation in y0 has solutions for y0 wherein the solutions are elements of the finite field, F, assign one of the solutions to y0 at random or according to a predetermined rule, otherwise, continue incrementing x until a quadratic equation of y0 is formed that has solutions in the finite field F, once such solutions are obtained, assign one of the solutions to y0 at random or according to a preselected rule, and in the case of a quadratic equation with A+0, the Legendre symbol is used as an efficient test for the existence of a solution of a quadratic equation.
8. A method of encrypting and decrypting a message bit string in an information processing system according to claim 7 in which a projective coordinate is used by the sending correspondent and the receiving correspond to eliminate the inversion or division during each point addition and doubling operation of a scalar multiplication, and for randomizing the computation in order to provide a counter measure against differential power analysis.
9. A system for encrypting and decrypting a bit string used in information processing, storage, and transmission, implementing respective ones of a pair of complementary mathematical operations using scalar multiplication of a shared key represented as a scalar value and a base point, said system comprising:
means for assembling a data string including information to be transferred from a sending correspondent to a receiving correspondent;
means for performing a complimentary mathematical operation using points that satisfy an elliptic polynomial equation with more than one quadratic variable termed y-coordinates wherein all the corresponding coordinates of such points are elements of a finite field F, and wherein the addition of any two of these elliptic points is defined over an extended dimensional space that incorporates the additional y-coordinates, and wherein a point addition is computed using arithmetic over a finite field, F; and
means for forwarding the defined set of points over a communication channel to a receiving correspondent for performing the other of the corresponding mathematical crytographic operations to decrypt the data, and
which is implemented as pure hardware unit or as a program stored on a computer readable storage device and executed as a digital computer or a combination of both.
10. A method for communicating securely over an insecure communication channel between a pair of correspondents who perform shared key cryptographic operations by implementing respective ones of a pair of complimentary mathematical operations utilizing the scalar multiplication of a shared key represented as a scalar value and a base point, said method comprising the steps of:
assembling a data string including information to be transferred from a sending correspondent to a receiving correspondent;
performing a complementary mathematical operation using points that satisfy an elliptic polynomial equation in projective coordinate with more than one quadratic variable that are termed Y-coordinates, wherein all the corresponding coordinates of such point are elements of a finite field, F, and wherein the addition of any two of these elliptic points is defined over an extended dimensional space that incorporates the additional Y-coordinates, as well as a projective coordinate and wherein this point addition is computed using arithmetic over a finite field, F; and
forwarding the defined set of points over a communication channel to the receiving correspondent and performing the other of the corresponding mathematical cryptographic operations to decrypt the data.
11. A method for communicating securely over an insecure communication channel between a pair of correspondents according to claim 10 using an elliptic polynomial equation in projective coordinate which consists of the sum of many terms known as monomials and wherein the equation before it is projected using the projective coordinate has more than two independent variables such that:
(a) the maximum total degree of any monomial in the polynomial is three,
(b) at least two variables, termed the y-coordinates, have a maximum degree of two, and at least one must appear in one of monomial on its own with a degree of two,
(c) at least one variable, termed the x-coordinate, has a maximum degree of three, and must appear in one of the monomials with a degree of three.
12. A method of encrypting and decrypting a message bit string in an information processing system by implementing respective ones of a pair of complimentary mathematical operations using the scalar multiplication of a shared key represented as a scalar value and a base point, said method comprising the steps of:
assembling a data string including information to be transferred from a sending correspondent to a receiving correspondent;
performing a complimentary mathematical operation using points that satisfy an elliptic polynomial equation with more than one quadratic variable termed Y-coordinates wherein the elliptic polynomial equation is represented in projective coordinate, wherein all coordinates of such points are elements of a finite field, F, and wherein the addition of any two of these elliptic points is defined over an extended dimensional space that incorporates the additional Y-coordinates as well as a projective coordinate, and wherever the point addition is computed using arithmetic over a finite field, F; and
using an elliptic polynomial equation, which includes the sum of many monomials and wherein the equation before it is projected using a projective coordinate has more than two independent variables such that;
(a) the maximum total degree of any monomial in the polynomial is three,
(b) at least two variables, termed the y-coordinates, have a maximum degree of two, and at least one must appear in one of monomial on its own with a degree of two,
(c) at least one variable, termed the x-coordinate, has a maximum degree of three, and must appear in one of the monomials with a degree of three,
wherein the representation of the corresponding elliptic points includes more than one Y-coordinate, and a projective coordinate wherein all the corresponding coordinates of such points are elements of F represented in N-bit strings, and which includes a step where extra message bits are embedded in the additional Y-coordinates, and the projective coordinate;
forwarding the defined set of points over a communication channel to the receiving correspondent and performing the other of the correspondents mathematical cryptography operations to decrypt the data.
13. A method of encrypting and decrypting a message bit string in an information processing system in accordance with claim 12 wherein predetermined mappings are used to indicate that an elliptic point that has more than one Y-coordinate and a projective coordinate is equivalent to one or more elliptic points that satisfy the same elliptic polynomial equation in projective coordinate and with more than one Y-coordinate, wherein the elliptic points that are equivalent to each other can be substituted for each other at random or according to certain rules during point addition and points doubling operations, and wherein mappings that indicate that an elliptic point is equivalent to itself are also referenced in this claim.
14. A method of encrypting and decrypting a message bit string in an information processing system in accordance with claim 13 wherein ny additional Y-coordinates are used and wherein ny is greater than or equal to one, said method comprising the steps of:
embedding a message bit string into the appropriate coordinates including the additional ny Y-coordinates, Y1, . . . . . . . ,& Yny, and a projective coordinate, Z, of an elliptic point which is designated as the message point, (\u02dc,Y0,m,Y1,m, . . . . . . ,Yny,m,Zm) where \u02dc denotes coordinates that represent non-quadratic variables of the same point;
providing shared keys, kil for i=1, . . , I, and l=1, . . , L where I & L are greater or equal to one, base points (\u02dc,Y0,B(i),Y1,B(i), . . . . . . . ,Yny,B(i),ZB(i)) for i=1,. . ,I where I is greater or equal to one, compute the point (\u02dc, Y1,bk, . . . . . . . ,Yny,bk,Zbk) using,
(
\u223c
,
Y
0
,
bk
,
Y
1
,
bk
,
\u2026
\u2062
,
Y
ny
,
bk
,
Z
bk
)
=
\u2211
i
=
1
I
\u2062
\u2062
(
k
iL
(
k
iL
–
1
\u2062
\u2062
\u2026
\u2062
\u2062
(
k
i1
\u2061
(
\u223c
,
Y
0
,
B
\u2061
(
i
)
,
Y
1
,
B
\u2061
(
i
)
,
\u2026
\u2062
,
Y
ny
,
B
\u2061
(
i
)
,
Z
B
\u2061
(
i
)
)
)
\u2062
\u2062
\u2026
\u2062
)
)
;
computing a cipher point (\u02dc,Y0,c,Y1,c, . . . . . . . ,Yny,c,Zc) using (\u02dc,Y0,c,Y1,c, . . . . . . . ,Yny,c,Zc)=(\u02dc,Y0,m,Y1,m,Y1,m, . . . . . . . ,Yny,m,Zm)+(\u02dc,Y0,bk,Y1,bk, . . . . . . . ,Yny,bk,Zbk);
sending appropriate bits of the coordinates of the cipher point including its additional ny Y-coordinates, Y1,c, . . . . . . . ,& Yny,c, and the Z-coordinate, Zc, and if need be any additional information needed to help the receiving correspondent recover the message bit string without compromising security;
using the shared keys, kil for i=1, . . I and l=1, . . , L where I & L are greater or equal to one, the base points (\u02dc, Y0,B(i), Y1,b(i), . . . . . . . ,Yny,B(i),ZB(i)) for i=1, . . ,I where I is greater or equal to one, and if need be any additional information received from the sending correspondent, compute the point (\u02dc,Y0,bk,Y1,bk, . . . . . . . ,Yny,bk, Zbk) using,
(
\u223c
,
Y
0
,
bk
,
Y
1
,
bk
,
\u2026
\u2062
,
Y
ny
,
bk
,
Z
bk
)
=
\u2211
i
=
1
I
\u2062
\u2062
(
k
iL
(
k
iL
–
1
\u2062
\u2062
\u2026
\u2062
\u2062
(
k
i1
\u2061
(
\u223c
,
Y
0
,
B
\u2061
(
i
)
,
Y
1
,
B
\u2061
(
i
)
,
\u2026
\u2062
,
Y
ny
,
B
\u2061
(
i
)
,
Z
B
\u2061
(
i
)
)
)
\u2062
\u2062
\u2026
\u2062
)
)
;
computing the message point (\u02dc,Y0,m,Y1,m, . . . . . . . ,Yny,m,Zm) using (\u02dc,Y0,m,Y1,m. . . . . . . ,Yny,m,Zm)=(\u02dc,Y0,c,Y1,c, . . . . . . . , Yny,c,Zc)\u2212(\u02dc,Y0,bk,Y1,bk, . . . . . . . ,Yny,bk,Zbk) and if need be any additional information received from the sending correspondent;
recovering the message bit string from the appropriate coordinates of the message point including its additional ny Y-coordinates, Y1,m, . . . . . . . & Yny,m, and Z-coordinate, Zm, and if need be any additional information received from the sending correspondent.
15. A method of encrypting and decrypting a message bit string in an information processing system in accordance with claim 14 wherein each point operation used to compute the point (\u02dc,Y0,bk,Y1,bk, . . . . . . . ,Yny,bk,Zbk) is defined over a designated sub-space that contains at least one X-coordinate andor the Z-coordinate, and at least one Y-coordinate, wherein the variables that denote other coordinates not contained in a designated sub-space are considered as constants, and wherein the designated sub-spaces of different point operations can be completely disjointed from each other, or can be shared partially or completely.
16. A method for encrypting and decrypting a message bit string in an information processing system according to claim 15 wherein embedding of the message bit string into an elliptic point with a projecting coordinate, Z, one X-coordinate, X and (ny+1) Y-coordinates, Y0,Y1, . . . . . . . & Yny compriseing the steps of:
dividing a message bit string into M-bit strings where ((ny+2)N-L)>M>(N-L),
dividing each M-bit string into (ny+2) strings mX, mY1, . . . , mYny, and mZ wherein the length of string mX must be no more than (N-L) bits, while the length of the each of the other \u201cny+1\u201d strings mY1. . . , mYny and mZ must be no more than N bits, and wherein each one of the (ny+2) bit strings must have an equivalent value which is an element of the underlying finite field F,
assigning the value of the bit strings of mY1, . . . , & mYny to Y1, . . . . . . . & Yny,
assigning the value of the bit strings of mZ to Z,
assigning the value of the bit string of mX to X,
substituting the values of Z, X, Y1, . . . . . . . & Yny in a selected elliptic polynomial equation in projective coordinate, Z, with one X-coordinate and (ny+1) Y-coordinates to form a quadratic equation in Y0,
Y02+AY0+B=0
if the quadratic equation in Y0 has solutions for Y0 wherein the solutions are elements of the finite field F, assign one of the solutions to Y0 at random or according to a predetermined rule, otherwise, continue incrementing X until a quadratic equation of Y0 is formed that has solutions in the finite field F. Once such solution are obtained, assign one of the solutions to Y0 at random or according to a predetermining rule, and in the case of a quadratic equation with A=0, the Legendre symbol can be used as an efficient test for the existence of a solution of a quadratic equation.
17. A method for encrypting and decrypting a message bit string in an information processing system according to claim 16 in which a projective coordinate is used by the sending correspondent and the receiving correspondent to eliminate the inversion or division during each point addition and doubling operation of a scalar multiplication, and for randomizing the computation in order to provide a counter measure against differential power analysis.
18. A system for encrypting and decrypting a bit string used in information processing, storage, and transmission, implementing respective ones of a pair of complimentary mathematical operations using scalar multiplication of a shared key represented as a scalar value and a base point, said system comprising:
means for assembling a data string including information to be transferred from a sending correspondent to a receiving correspondent;
means for performing a complimentary mathematical operation using points that satisfy an elliptic polynomial equation in projective coordinate with more than one quadratic variable that are termed Y-coordinates, wherein all the corresponding coordinates of such points are elements of a finite field, F, and wherein the addition of any two of these elliptic points is defined over an extended dimensional space that incorporates the additional Y-coordinates, and a projective coordinate and wherein a point addition is computed using arithmetic over a finite field, F; and
means for forwarding the defined set of points over a communication channel to a receiving correspondent for performing the other of the corresponding mathematical cryptographic operations to decrypt the data, and
which is implemented as a pure hardware unit or as a program stored on a computer readable storage device and executed as a digital computer or a combination of both.
19. A method for transferring data over a communication channel between a pair of correspondents who perform public key cryptographic operations by implementing respective ones of a pair of complimentary mathematical operations utilizing a private key of one of the correspondents represented as scalar value, and a public key of the other correspondent represented as an elliptic point, said method comprising the steps of:
assembling a data string including information to be transferred from a sending correspondent to a receiving correspondent;
performing a complementary mathematical operation using points that satisfy an elliptic polynomial equation with more than one quadratic variable that are termed y-coordinates wherein all the corresponding coordinates of such points are elements of a finite field, F, and wherein the addition of any two of these elliptic points is defined over an extended dimensional that incorporates the additional y-coordinates, and wherein this point addition is computed using arithmetic over a finite field, F; and
forwarding the defined set of points over a communication channel to the receiving correspondent and performing the other of the corresponding mathematical operations of the public key and the private key cryptographic operation to decrypt the data.
20. A method for transferring data over a communication channel between a pair of correspondents according to claim 19 using an elliptic polynomial equation which consists of many monomials and wherein the equation has more than two independent variables such that:
(a) the maximum total degree of any monomial in the polynomial is three,
(b) at least two variables, termed the y-coordinates, have a maximum degree of two, and at least one must appear in one of monomial on its own with a degree of two,
(c) at least one variable, termed the x-coordinate, has a maximum degree of three, and must appear in one of the monomials with a degree of three.
21. A method of encrypting and decrypting a message bit string in an information processing system by implementing respective ones of a pair of complimentary mathematical operations using the scalar multiplication of a private key of one of the correspondent represented as a scalar value and the public key of the other correspondent represented as an elliptic point, said method comprising the steps of:
assembling a data string including information to be transferred from a sending correspondent to a receiving correspondent;
performing a complementary mathematical operation using points that satisfy an elliptic polynomial equation with more than one quadratic variable termed y-coordinates wherein all the corresponding coordinates of such points are elements of a finite field, F, and wherein the addition of any two of these elliptic points is defined over an extended dimensional space that incorporates the additional y-coordinates, and wherever the point addition is computed using arithmetic over a finite field, F; and
using an elliptic polynomial equation which includes the sum of many monomials and wherein the equation has more than two independent variables such that;
(a) the maximum total degree of any monomial in the polynomial is three,
(b) at least two variables, termed the y-coordinates, have a maximum degree of two, and at least one must appear in one of monomial on its own with a degree of two,
(c) at least one variable, termed the x-coordinate, has a maximum degree of three, and must appear in one of the monomials with a degree of three,
wherein the representation of the corresponding elliptic points include more than one y-coordinate, wherein all the corresponding coordinates of such points are elements of F represented in N-bit strings, and which includes a step where extra message bits are embedded in the additional y-coordinates;
forwarding the defined set of points over a communication channel to the receiving correspondent and performing the other of the corresponding mathematical operations of the public key and the private key crytographic operation to decrypt the data.
22. A method of encrypting and decrypting a message bit string in an information processing system in accordance with claim 21 wherein predetermined mappings are used to indicate that an elliptic point that has more than one y-coordinate is equivalent to one or more elliptic points that satisfy the same elliptic polynomial equation with more than one y-coordinate, wherein the elliptic points that are equivalent to each other can be substituted for each other at random or according to certain rules during point addition and point doubling operations, and wherein mappings that indicate that an elliptic point is equivalent to itself are also referenced.
23. A method of encrypting and decrypting a message bit string in an information processing system in accordance with claim 22, wherein ny additional y-coordinates are uses, wherein ny is greater than or equal to one, said method comprising the steps of:
embedding a message bit string into the appropriate coordinates including the additional ny y-coordinates, y1, . . . . . . . , & yny, of an elliptic point which is designated as the message point, (\u02dc,y0,m,y1,m, . . . . . . . ,yny,m) where \u02dc denotes coordinates that represent non-quadratic variables of the same point;
using the private keys of the sending correspondent, kSP(i,l) for i=1, . . ,I, and l=1, . . ,LS where I & LS are greater or equal to one, and the public keys of the receiving correspondent (\u02dc,yO,PuR(i), y1,PuR(i), . . . . . . . , yny,PuR(i)) for i=1, . . ,I where I is greater or equal to one, compute the point (\u02dc, y0,bk, yl,bk, . . . . . . . , yny,bk) using,
(
~
,
y
0
,
bk
,
y
1
,
bk
,
\u2026
\u2062
,
y
ny
,
bk
)
=
\u2211
i
=
1
I
\u2062
(
k
SP
\u2061
(
i
,
L
S
)
(
\u2062
k
SP
\u2061
(
i
,
L
S
–
1
)
\u2062
\u2062
\u2026
\u2061
(
k
SP
\u2061
(
i
,
1
)
\u2062
(
~
,
y
0
,
PuR
\u2061
(
i
)
,
y
1
,
PuR
\u2061
(
i
)
,
\u2026
\u2062
,
y
ny
,
PuR
\u2061
(
i
)
)
)
\u2062
\u2062
\u2026
\u2062
)
)
;
computing a cipher point (\u02dc,y0,c,y1,c, . . . . . . . ,yny,c) using (\u02dc,y0,c,y1,c, . . . . . . . ,yny,c)=(\u02dc,y0,m,y1,m, . . . . . . . ,ymy,m)+(\u02dc,y0,bk,y1,bk, . . . . . . ,yny,bk);
sending appropriate bits of the coordinates of the cipher point including its additional ny y-coordinates, yl,c, . . . . . . . & yny,c, and any additional information needed to help the receiving correspondent recover the message bit string without compromising security;
using the private keys of the receiving correspondent, kRP(i,l) for i=1, . . ,I, and I=1, . . , LR where I & LR are greater or equal to one, and the public keys of the sending correspondent (\u02dc, y0,PuS(i),y1,PuS(i), . . . . . . . ,yny,PuS(i)) for i=1,. . ,I where I is greater or equal to one, and if need be any additional information received from the sending correspondent, compute the point (\u02dc,y0,bk,y1,bk, . . . . . . . ,yny,bk) or its equivalent using,
(
~
,
y
0
,
bke
,
y
1
,
bke
,
\u2026
\u2062
,
y
ny
,
bke
)
=
\u2211
i
=
1
I
\u2062
(
k
RP
\u2061
(
i
,
L
R
)
\u2061
(
k
RP
\u2061
(
i
,
1
)
\u2062
\u2062
\u2026
\u2061
(
~
,
y
0
,
PuS
\u2061
(
i
)
,
y
1
,
PuS
\u2061
(
i
)
,
\u2026
\u2062
,
y
ny
,
PuS
\u2061
(
i
)
)
)
\u2062
\u2062
\u2026
\u2062
)
)
and wherein (\u02dc,y0,bke,y1,bke, . . . . . . . ,yny,bke) is equivalent to (y0,bk,y1,bk, . . . . . . . ,yny,bk,\u02dc);
computing the message point (\u02dc,y0,m,y1,m, . . . . . . . ,yny,m) using (\u02dc,y0,m,y1,m, . . . . . . . ,yny,m)=(\u02dc,y0,c,y1,c, . . . . . . . ,yny,c)\u2212(\u02dc,y0,bk,y1,bk, . . . . . . . ,yny,bk) and if need be any additional information received from the sending correspondent;
recovering the message bit string from the appropriate coordinates of the message point including its additional ny y-coordinates, y1,m, . . . . . . . & yny,m, and if need by any additional information received from the sending correspondent.
24. A method of encrypting and decrypting a message bit string in an information processing system in accordance with claim 23 wherein the private keys of a correspondent entity kP(i,l)(j) for i=1,. . ,I, J=1, . . . ,J and l=1, . . , L where I, J & L are greater or equal to one, and the base points (\u02dc, y0,B(i),y1,B(i), . . . . . . . , yny,B(i)) for i=1, . . , I where I is greater or equal to one, are used to compute the public keys of the same correspondent entity, (\u02dc,y0,Pu(i),Y1,Pu(i), . . . . . . . ,yny,Pu(i)) for i=1, . . , I where I is greater or equal to one.
(
~
,
y
0
,
Pu
\u2061
(
i
)
,
y
1
,
Pu
\u2061
(
i
)
,
\u2026
\u2062
,
y
ny
,
Pu
\u2061
(
i
)
)
=
\u2211
j
=
1
J
\u2062
(
k
P
\u2061
(
i
,
L
)
(
j
)
\u2061
(
k
P
\u2061
(
i
,
L
–
1
)
(
j
)
\u2062
\u2062
\u2026
\u2062
\u2062
k
P
\u2061
(
i
,
1
)
(
j
)
\u2061
(
~
,
y
0
,
B
\u2061
(
i
)
,
y
1
,
B
\u2061
(
i
)
,
\u2026
\u2062
,
y
ny
,
B
\u2061
(
i
)
)
)
\u2062
\u2062
\u2026
\u2062
)
)
;
25. A method of encrypting and decrypting a message bit string in an information processing system in accordance with claim 24 wherein each point operation used to compute the point (\u02dc, y0,bk,y1,bk, . . . . . . . ,yny,bk), its equivalent, or the public key points (\u02dc,y0,Pu(i),y1,Pu(i), . . . . . . . ,yny,Pu(i)) for i=1, . . ,I where I is greater or equal to one, is defined over a designated sub-space that contains at least one y-coordinate and one x-coordinate, wherein the variables that denote other coordinates not contained in a designated sub-space are considered as constants, and wherein the designated sub-spaces of different point operations is completely disjoined from each other, or can be shared partially or completely.
26. A method for encrypting and decrypting a message bit string in an information processing system according to claim 25 wherein embedding of the message bit string into an elliptic point with one x-coordinate, x, and (ny+1) y-coordinates, y0,y1, . . . . . . .& yny, comprising the steps of:
dividing a message bit string into M-bit strings where ((ny+1)N-L)>M>(N-L),
dividing each M-bit string into (ny+1) strings mx, my1, . . . , & myny, wherein the length of string mx must be no more than (N-L) bits, while the length of each of the other \u201cny\u201d strings my1, . . . , & myny must be no more than N bits, and wherein each one of the (ny+1) bit strings must have an equivalent value which is an element of the underlying finite field F,
assigning the value of the bit strings of my1, . . . , & myny to y1, . . . . . . . & yny,
assigning the value of the bit string of mx to x
substituting the values of x and y1, . . . . . . . & yny in selected polynomial equation with
one x-coordinate and (ny+1) y-coordinates to form a quadratic equation in y0,
y02+Ay0+B=0
if the quadratic equation in y0 has solutions for y0 wherein the solutions are elements of the finite field, F, assign one of the solutions to y0 at random or according to a predetermined rule, otherwise, continue incrementing x until a quadratic equation of y0 is formed that has solutions in the finite field F; once such solutions are obtained, assign one of the solutions to y0 at random or according to a preselected rule, and in the case of a quadratic equation with A+0, the Legendre symbol is used as an efficient test for the existence of a solution of a quadratic equation.
27. In a method for communicating securely over an insecure communication channel using elliptic polynomial cryptography according to claim 26 in which a projective coordinate is used by the sending correspondent and the receiving correspondent to eliminate the inversion or division during each point addition and doubling operation of a scalar multiplication, and for randomizing the computation in order to provide a counter measure against differential power analysis.
28. A system for encrypting and decrypting a bit string used in information processing, storage, and transmission, implementing respective ones of a pair of complimentary mathematical operations utilizing a private key of one of the correspondents represented as a scalar value, and a public key of the other correspondent represented as an elliptic point, said system comprising:
means for assembling a data string including information to be transferred from a sending correspondent to a receiving correspondent;
means for performing a complementary mathematical operation using points that satisfy an elliptic polynomial equation with more than one quadratic variable termed y-coordinates wherein all the corresponding coordinates of such points are elements of a finite field F, and wherein the addition of any two of these elliptic points is defined over an extended dimensional space that incorporates the additional y-coordinates, and wherein a point addition is computed using arithmetic over a finite field, F; and
means for forwarding the defined set of points over a communication channel to a receiving correspondent for performing the other of the corresponding mathematical cryptographic operations to decrypt the data, and
which is implemented as a pure hardwire unit or as a program stored on a computer readable storage device and executed as a digital computer or a combination of both.
29. A method of encrypting and decrypting a message bit string in an information processing system by implementing respective ones of a pair of complimentary mathematical operations using the scalar multiplication of a private key of one of the correspondent represented as a scalar value, and a public key of the other correspondent represented as an elliptic point, said method comprising the steps of:
assembling a data string including information to be transferred from a sending correspondent to a receiving correspondent;
performing a complimentary mathematical operation using points that satisfy an elliptic polynomial equation with more than one quadratic variable termed Y-coordinates wherein the elliptic polynomial equation is represented in projective coordinate, wherein all the corresponding coordinates of such points are elements of a finite field, F, and wherein the addition of any two of the elliptic points is defined over an extended dimensional space that incorporates the additional Y-coordinates and a projective coordinate and wherever the point addition is computed using arithmetic over a finite field, F; and
using an elliptic polynomial equation which includes the sun of many monomials and wherein the equation before it is projected using the projective coordinate has more than two independent variables such that;
(a) the maximum total degree of any monomial in the polynomial is three,
(b) at least two variables, termed the y-coordinates, have a maximum degree of two, and at least one must appear in one of monomial on its own with a degree of two,
(c) at least one variable, termed the x-coordinate, has a maximum degree of three, and must appear in one of the monomials with a degree of three.
wherein the representation of the corresponding elliptic points include more than one Y-coordinate, and a projective coordinate wherein all the corresponding coordinates of such points are elements of F represented in N-bit strings, and which includes a step where extra message bits are embedded in the additional Y-coordinates and the projective coordinate;
forwarding the defined set of points over a communication channel to the receiving correspondent and performing the other of the corresponds mathematical cryptography operations to decrypt the data.
The claims below are in addition to those above.
All refrences to claim(s) which appear below refer to the numbering after this setence.
1. A method comprising:
measuring an acceleration of an asset to obtain an acceleration value using a tracking device;
adjusting, using the tracking device, the acceleration value based on accelerometer-calibration factors to obtain an adjusted-acceleration value;
determining, using the tracking device, a position of the asset based on the adjusted-acceleration value and a transformation matrix, wherein the transformation matrix allows transformation from a computational frame of reference to a user frame of reference;
updating, using the tracking device, the transformation matrix based on a manual alignment fixture; and
transmitting the position of the asset from tracking device.
2. The method of claim 1, wherein measuring the acceleration of the asset comprises measuring a linear acceleration of the asset.
3. The method of claim 1, wherein measuring the acceleration of the asset comprises measuring the acceleration of the asset along at least one axis.
4. The method of claim 1, wherein the user frame of reference is fixed to a stable structure, and wherein the computational frame of reference is associated with a tracking device.
5. The method of claim 1, wherein updating the transformation matrix further comprises updating the transformation matrix based on a contact with a homing station.
6. The method of claim 1, wherein updating the transformation matrix further comprises updating the transformation matrix periodically to account for planetary rotation.
7. The method of claim 1, wherein adjusting the acceleration value comprises aligning an axis of the computational frame to a gravity vector.
8. The method of claim 1, further comprising:
measuring a rotation of the asset about at least one axis to obtain a rotation value.
9. The method of claim 8, further comprising:
adjusting the rotation value of the asset to obtain an adjusted-rotation value; and
wherein determining the position of the asset comprises determining the position of the asset based on the adjusted-acceleration value and the adjusted-rotation value.
10. The method of claim 1, wherein determining the position of the asset comprises determining a reported asset path of the asset.
11. The method of claim 10, wherein determining the reported asset path of the asset comprises determining a likelihood of the reported asset path.
12. The method of claim 11, wherein determining the likelihood of the reported asset path comprises determining the likelihood of the reported asset path based on one or more physical building constraints.
13. The method of claim 1, wherein measuring the acceleration of the asset comprises measuring the acceleration of the asset with a tracking device, and wherein at least some of the accelerometer-calibration factors are determined at a time of manufacture of the tracking device.
14. The method of claim 13, wherein the at least some of the accelerometer calibration factors determined at the time of manufacture correct for offset, scale, and misalignment errors.
15. The method of claim 13, wherein the accelerometer calibration factors are stored in a non-volatile memory of the tracking device.
16. An apparatus comprising:
means for measuring an acceleration of an asset to obtain an acceleration value;
means for adjusting the acceleration value based on accelerometer-calibration factors to obtain an adjusted-acceleration value;
means for determining a position of the asset based on the adjusted-acceleration value and a transformation matrix, wherein the transformation matrix allows transformation from a computational frame of reference to a user frame of reference;
means for updating the transformation matrix based on a manual alignment fixture; and
means for transmitting the position of the asset.
17. The apparatus of claim 16, wherein the means for measuring the acceleration of the asset comprise means for measuring the acceleration of the asset along at least one axis.
18. The apparatus of claim 16, further comprising:
means for measuring a rotation of the asset about at least one axis to obtain a rotation value.
19. The apparatus of claim 16, wherein the accelerometer-calibration factors are determined at a time of manufacture of the apparatus.
20. The apparatus of claim 19, wherein the at least some accelerometer calibration factors determined at the time of manufacture correct for offset, scale, and misalignment errors.
21. The apparatus of claim 19, further comprising means for storing the accelerometer-calibration factors.
22. A computer-readable storage device having instructions thereon, the instructions comprising:
instructions to measure an acceleration of an asset to obtain an acceleration value;
instructions to adjust the acceleration value based on accelerometer-calibration factors to obtain an adjusted-acceleration value;
instructions to determine a position of the asset based on the adjusted-acceleration value and a transformation matrix, wherein the transformation matrix allows transformation from a computational frame of reference to a user frame of reference;
instructions to update the transformation matrix based on a manual alignment fixture; and
instructions to transmit the position of the asset.
23. The computer-readable storage device of claim 22, wherein the instructions to measure the acceleration of the asset comprise instructions to measure a linear acceleration of the asset.
24. The computer-readable storage device of claim 22, wherein the user frame of reference is fixed to a stable structure, and wherein the computational frame of reference is associated with a tracking device.
25. The computer-readable storage device of claim 22, wherein the instructions to update the transformation matrix comprise instructions to update the transformation matrix based on a contact with a homing station.
26. The computer-readable storage device of claim 22, wherein the instructions to update the transformation matrix comprise instructions to update the transformation matrix periodically to account for planetary rotation.
27. The computer-readable storage device of claim 22, wherein the instructions to adjust the acceleration value comprise instructions to align an axis of the computational frame to a gravity vector.
28. The computer-readable storage device of claim 22, further comprising instructions to measure a rotation of the asset about at least one axis to obtain a rotation value.
29. The computer-readable storage device of claim 28, further comprising instructions to adjust the rotation value of the asset to obtain an adjusted-rotation value, and wherein the instructions to determine the position of the asset comprise instructions to determine the position of the asset based on the adjusted-acceleration value and the adjusted rotation value.
30. The computer-readable storage device of claim 22, further comprising instructions to determine a reported asset path of the asset and a likelihood of the reported asset path.
31. The computer-readable storage device of claim 30, wherein the instructions to determine the likelihood of the reported asset path comprise instructions to determine the likelihood of the reported asset path based on one or more physical building constraints.