US 2010/0169644 A1 · Message authentication code with elliptic polynomial hopping

Abstract

The message authentication code with elliptic polynomial hopping provides methods for the generation of message authentication codes (MACs) utilizing elliptic curves, which are based on the elliptic curve discrete logarithm problem. The elliptic curve discrete logarithm problem is well known to be a computationally “difficult” or “hard” problem, thus providing enhanced security for the MACs. Different elliptic polynomials are used for different blocks of the same plaintext, each elliptic polynomial for each message block being selected at random using an initial secret key and a random number generator.

A computerized method of generating a message authentication code with elliptic polynomial hopping, comprising the steps of:

a sending correspondent and a receiving correspondent agreeing upon:
(a) a form of an elliptic polynomial equation by deciding on an underlying finite field F;
a number of x-coordinates, and a set of monomials used;
(b) a random number k0, which is kept as a secret key for generating a message authentication code, and a method for generating the message authentication code given a random number;
(c) a random number generator;
d) a random number kp0 that is a portion of a shared secret key used for communication;
(e) a set of (nx+1) numbers such that xbi ∈ F, wherein i and nx are integers, wherein i=0, . . . , nx, the set being used to find an initial base point, the set being made public;
the sending correspondent then performing the following steps:
(f) generating at least a portion of a set of coefficients b1l(0), b2lk(0) ∈ F of a first elliptic polynomial to be used for a message authentication code of a first message block, from the shared secret key kp0;
(g) embedding the set of (nx+1) numbers xbi ∈ F into an elliptic polynomial point to obtain an initial base point (x0,B(0), x1,b(0), . . . , xnx,B(0), yB(0), αB) using a data embedding method;
(h) embedding the first block of the message bit string into an elliptic polynomial message point (x0,m(0), x1,m(0), . . . , xnx,m(0), ym(0), αm(0)) using the data embedding method;
(i) computing a scalar multiplication of the first block shared key k0 with the base point (x0,B(0), x1,B(0), . . . , xnx,B(0), yB(0), αB) as (x0,kB(0), x1,kB(0), . . . , xnx,kB(0), ykB(0), 1)=k(x0,B(0), x1,B(0), . . . , xnx,B(0), yB(0), αB);
(1) computing the message authentication point of the first data block (x0,c(0), x1,c(0), . . . , xnx,c(0), yc(0), αc(0)) as:
(x0,c(0), x1,c(0), . . . , xnx,c(0), yc(0)αc(0))=, wherein αc(0)=αm(0);
(x0,m(0), x1,m(0), . . . , xnx,m(0), ym(0), αm(0))+(x0,kB(0), x1,kB(0), . . . , xnx,kB(0), ykB(0), 1)
initializing an integer j as j=1 and repeating the following steps (k) to (o), and incrementing j at each step until all of the message data blocks are processed:
(k) generating a random number kpj with the random number generator;
(l) generating at least a portion of the coefficients b1l(j), b2lk(j) ∈ F of the j-th elliptic polynomial from the random number kpj;
(m) embedding the j-th block of the message bit string into a j-th elliptic polynomial message point (x0,m(j), x1,m(j), . . . , xnx,m(j), ym(j), αm(j)) using the data embedding method;
(n) hopping the message authentication code point (x0,c(j-1), x1,c(j-1), . . . , xnx,c(j-1), yc(j-1), αc(j-1));to an equivalent message authentication code point (x′0,c(j), x′1,c(j), . . . , x′nx,c(j), y′c(j), α′c(j)) that satisfies the j-th elliptic polynomial of step (l) using the data embedding method;
(o) computing the message authentication code point of the j-th data block (x0,c(j), x1,c(j), . . . , xnx,c(j), yc(j), αc(j)) as:
(x0,c(j), x1,c(j), . . . , xnx,c(j), yc(j), αc(j))=(x0,m(j), x1,m(j), . . . , xnx,m(j), ym(j), αm(j))+;
(x′0,c(j), x′1,c(j), . . . , xnx,c(j), yc(j), α′c(j))
(p) appropriate bits of the x-coordinates and a bit indicating the value of αc(u) of a cipher point (x0,c(u), x1,c(u), . . . , xnx,c(u), yc(u), αc(j)) are concatenated together to form the message authentication code bit string and are sent to the receiving correspondent;
the receiving correspondent performing the following steps:
(q) generating at least a portion of the coefficients b1l(0), b2lk(0) ∈ F of the first elliptic polynomial to be used for the message authentication code of the first message block from the shared secret key kp0;
(r) embedding the set of (nx+1) numbers xbi ∈ F into an elliptic polynomial point to obtain an initial base point (x0,B(0), x1,B(0), . . . , xnx,B(0), yB(0), αB) using the data embedding method;
(s) embedding the first block of the received message bit string into an elliptic polynomial message point (x0,rm(0), x1,rm(0), . . . , xnx,rm(0), yrm(0), αm(0)) using the data embedding method;
(t) computing the scalar multiplication of the first block shared key k0 with the base point (x0,B(0), x1,B(0), . . . , xnx,B(0), yB(0)) as (x0,kB(0), x1,kB(0), . . . , xnx,kB(0), ykB(0), 1)=k(x0,B(0), x1,B(0), . . . , xnx,B(0), yB(0), αB);
(u) computing the message authentication code point of the first received data block (x0,rc(0), x1,rc(0), . . . , xnx,rc(0), yrc(0)) as:
(x0,rc(0), x1,rc(0), . . . , xnx,rc(0), yrc(0)αrc(0))=(x0,rm(0), x1,rm(0), . . . , xnx,rm(0), yrm(0), αrm(0))+, wherein αrc(0)=αrm(0);
(x0,kB(0), x1,kB(0), . . . , xnx,kB(0), ykB(0), 1)
initializing the integer j as j=1 and repeating the following steps (v) to (aa), and incrementing j at each step until all of the message data blocks are processed:
(v) generating a random number kpj with the random number generator based upon kpj-1;
(w) generating at least a portion of the coefficients b1l(j), b2lk(j) ∈ F of the j-th elliptic polynomial from the random number kpj;
(x) embedding the j-th block of the received message bit string into a j-th elliptic polynomial message point (x0,rm(j), x1,rm(j), . . . , xnx,rm(j), yrm(j), αrm(j)) using the data embedding method;
(y) hopping the message authentication point (x0,rc(j-1), x1,rc(j-1), . . . , xnx,rc(j-1), yrc(j-1), αrc(j-1) to an equivalent message authentication point (x′0,rc(j), x′1,rc(j), . . . , x′nx,rc(j), y′rc(j), α′rc(j)) that satisfies the j-th elliptic polynomial selected in step (l) using the data embedding method;
(z) computing the message authentication code point of the j-th received data block (x0,rc(j), x1,rc(j), . . . , xnx,rc(j), yrc(j), αrc(j)) is computed as:
(x0,rc(j), x1,rc(j), . . . , xnx,rc(j), yo(r), αrc(j))=(x0,rm(j), x1,rm(j), . . . , xnx,rm(j), yrm(j), αrm(j))+;
(x′0,rc(j), x′1,rc(j), . . . , x′nx,rc(j), yrc(j), α′rc(j))
(aa) the appropriate bits of the x-coordinates, and a bit indicating the value of αc(u) of the message authentication point (x0,rc(u), x1,rc(u), . . . , xnx,rc(u), yrc(u), αrc(j)) are concatenated together to form the message authentication code bit string of the received message data;
and
(bb) if the message authentication code bit string of the received message data is the same as the message authentication code bit string sent by the sending correspondent, then the message is authenticated.

40 more elements

Message authentication code with elliptic polynomial hopping

Life of this patent

Message authentication code with elliptic polynomial hopping

Life of this patent

Abstract

Claims8