# US 2010/0169657 A1 · Message authentication code with blind factorization and randomization

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

- Number: US 2010/0169657 A1
- Document ID: US20100169657A1
- Status: Published application
- Kind: A1
- Application number: 12/318,404
- Filed: 2008-12-29
- Published: 2010-07-01
- Earliest claimed: 2008-12-29
- Assignees: King Fahd University of Petroleum and Minerals
- Inventors: Lahouari Ghouti; Mohammad K. Ibrahim
- Web page: https://patentgrep.com/patent/US20100169657A1

## CPC

- H04L 9/0643: {Hash functions, e.g. MD5, SHA, HMAC or f9 MAC}
- H04L 2209/046: of operations, operands or results of the operations
- H04L 2209/08: Randomization, e.g. dummy operations or using noise
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

The message authentication code with blind factorization and randomization is a computational method for improving the security of existing Message Authentication Code (MAC) methods through the use of blind integer factorization. Further, blind randomization is used as a countermeasure to minimize collision attacks where different plaintexts produce the same MAC.

## Claims

### Claim 1

A method of generating a message authentication code, comprising the steps of:
a) a pair of sending and receiving correspondents agreeing upon on a set of elements {p1, p2, . . . , pL} which are relatively prime with respect to one another, which are further considered as a shared secret and which are further used to form a basis β={p1, p2, . . . , pL} the sending and receiving correspondents further agreeing upon an integer g, E Zp for each element pl, l=1, . . . , L, wherein Zp denotes the set {0, . . . , p} and L is an integer which denotes the number of prime numbers used in the basis β, and wherein N is a maximum number of bits of a message data block, wherein the value of N is dependent on a data embedding method that is also agreed upon by the sending and receiving correspondents, wherein N is an integer defined such that a message data bit string length is a multiple of N, wherein u is an integer, the sending and receiving correspondents further agreeing upon an upper limit for the number of bits to be used to represent the message authentication code and an initial vector for a set of message authentication code elements c−1,l, l=1, . . . , L;
the sending correspondent then performing the following steps:
b) initializing an integer i as i=0, the following steps c) to d) then being repeated until all of the message data blocks are processed, and incrementing i at each step:
c) generating L integer values kl, where l=1, . . . , L, such that 0≦kl<pl from the lth block of the message bit string using the data embedding method;
d) computing the message authentication code elements ci,l modulo pl as ci,l=fl(ci-1,l, gl, ki,l) for l=1, . . . , L, wherein fl(,) represents a modulo p function;
e) combining the integer values cu,l for l=1, . . . , L to form a single integer vector {cu,1, cu,2, . . . , cu,L};
f) converting the integer vector {cu,1, cu,2, . . . , cu,L} into an integer value C using the basis β and the Chinese Remainder Theorem, the integer value C being the message authentication code value,
g) appending the bit string of the message authentication code integer value, C, to the message bit string and sending the concatenated bit string to the receiving correspondent;
the receiving correspondent then performs the following steps:
h) obtaining the message authentication code integer value C from the received message bit string;
i) computing the message authentication code elements cu,l modulo pl as cu,l=C mod pl for l=1, . . . , L;
j) initializing the integer i as i=0, the following steps k) to l) then being repeated until all the received message data blocks are processed, and incrementing i at each step:
k) generating L integer values kl, where l=1, . . . , L, such that 0≦kl<pl from the lth block of the received message bit string using the data embedding method;
l) computing the message authentication code elements rci,l modulo p, as rci,l=fl(rci-1,l, gl, ki,l) for l=1, . . . , L; and
m) if cu,l=rcu,l for all l, then the received message is authenticated.

### Claim 2 (depends on 1)

The method of generating a message authentication code as recited in claim 1, wherein the integers gl are part of the shared secret key.

### Claim 3 (depends on 1)

The method of generating a message authentication code as recited in claim 1, wherein the integers gl are made public.

### Claim 4 (depends on 1)

The method of generating a message authentication code as recited in claim 1, wherein the modulo p function of said step d) is computed as ci,l=ci-1,lglki,l.

### Claim 5 (depends on 1)

The method of generating a message authentication code as recited in claim 1, wherein the modulo p function of said step d) is computed as ci,l=g·ci-1,lki,l.

### Claim 6 (depends on 1)

The method of generating a message authentication code as recited in claim 1, wherein the modulo p function of said step d) is computed as ci,l=ci-1,l⊕gl⊕ki,l.

### Claim 7 (depends on 1)

The method of generating a message authentication code as recited in claim 1, wherein the data embedding method compromises the steps of:
a) defining M as an integer value of a bit string of a block of a message;
b) defining (N+1) as a number of bits needed to represent an integer
M
max
=
∏
l
=
1
L


p
l
;
c) setting a limit on the length of the bit string of the message block to be N; and
d) generating from the integer value M, L integer values kl, such that 0≦kl<pl, where l=1, . . . , L using, kl=M mod pl, for l=1, . . . , L.

### Claim 8 (depends on 1)

The method of generating a message authentication code as recited in claim 1, wherein the data embedding method compromises the steps of:
a) defining Nl as a number of bits needed to represent a value of a prime number pl for l=1, . . . , L;
b) defining Nml as the message bit strings that are embedded into the residue number kl mod pl with the condition Nml<Nl;
c) setting a limit on the length of the bit string of the message data block N to be
N
≤
∑
l
=
1
L


Nm
l
;
d) repeating the following steps e) to g) for l=1, . . . , L;
e) reading the next Nml bits of the message bit string;
f) using the Nml bits of the message data string to generate the Nml bits of the integer kl mod pl; and
g) setting the remaining (Nl−Nml) bits of the integer kl mod pl at random.

### Claim 9

A method of generating a message authentication code using blind randomization, comprising the steps of:
a) a pair of sending and receiving correspondents agreeing upon on a set of elements {p1′, p2′, . . . , pL′,} which are relatively prime with respect to one another and which are further considered as a shared secret, the sending and receiving correspondents further agreeing upon an integer glεZpl, for each element pl, wherein Zp denotes the set {0, . . . , p} and L is an integer that denotes the number of prime numbers used in a basis β, and wherein N is a maximum number of bits of a message data block, where the value of N is dependent on a data embedding method that is also agreed upon by the sending and receiving correspondents, and wherein the message data bit string is a multiple of N, the sending and receiving correspondents further agreeing upon an upper limit for the number of bits to be used to represent the message authentication code and an initial vector for a set of message authentication code elements c−1,l, l=1, . . . , L, the sending and receiving correspondents further agreeing on a list of codes, wherein each code identifies a different sub-set of (L−1)elements out of a set of L′ shared secret elements, the sending and receiving correspondents further agreeing upon an element pL of the set {p1′, p2′, . . . , pL′,}, the element being used to carry information about the code used by the sending correspondent to select a sub-set of the elements {p1′, p2′, . . . , pL′,} which are used to form a basis, wherein the number of codes is (pL−1);
the sending correspondent then performing the following steps:
b) selecting a code at random from the list of agreed upon to select (L−1) elements {p1, p2, . . . , pL-1} from the elements {p1′, p2′, . . . , pL′,} to form the basis β={p1, p2, . . . , pL-1, pL};
c) initializing an integer i as i=0, the following steps d) to e) then being repeated until all the message data blocks are processed, and incrementing l at each step:
d) generating (L−1) integer values ki,l, where l=1, . . . , (L−1) such that 0≦ki,l<pl, from the i-th block of the message bit string using a data embedding method;
e) computing the message authentication code elements ci,l modulo pl as ci,l=fl(ci-1,l, gl, ki,l) for l=1, . . . , (L−1), where fl(,) represents a modulo p function;
f) embedding the bit strings of the code used by the sending correspondent to select the (L−1) elements {p1, p2, . . . , pL-1} into the integer value cu,L, such that 0≦cu,L≦pL using the data embedding method;
g) combining the integer values cu,l for l=1, . . . , L to form a single integer vector {cu,1, cu,2, . . . , cu,L};
h) converting the integer vector {cu,1, cu,2, . . . , cu,L} into an integer value C using the basis β and the Chinese Remainder Theorem, the integer value C being the message authentication code value;
i) appending the bit string of the message authentication code integer value, C, to the message bit string and sending the concatenated bit string to the receiving correspondent;
the receiving correspondent then performs the following steps:
j) obtaining the message authentication code integer value C from the received message bit string;
k) computing the message authentication code elements cu,L, modulo pl as cu,L=C mod pl for l=1, . . . , L;
l) recovering the code used to define the set {p1, p2, . . . , pL-1} from the value cu,L;
m) computing the message authentication code elements cu,l modulo pl as cu,l=C mod pl for l=1, . . . , (L−1);
n) initializing the integer i as i=0, the following steps o) to p) then being repeated until all the received message data blocks are processed, and incrementing i at each step:
o) generating (L−1) integer values ki,l, where l=1, . . . , (L−1), such that 0≦ki,l<pl, from the i-th block of the message bit string using the data embedding method;
p) computing the message authentication code elements rci,l modulo pl as rci,l=fl(rci-1,l, gl, ki,l) for l=1, . . . , (L−1); and
q) if Cu,l=rcu,l for l=1, . . . , (L−1), then the received message is authenticated.

### Claim 10 (depends on 9)

The method of generating a message authentication code as recited in claim 9, wherein the data embedding method comprises the steps of:
a) defining Nl as a number of bits needed to represent the value of the prime number pl for l=1, . . . , (L−1);
b) defining Nml as the message bit strings that are embedded into the residue number kl mod pl with the condition Nml<Nl;
c) setting a limit on the length of the bit string of the message data block N to be
N
≤
∑
l
=
1
L


Nm
l
;
d) repeating the steps e) to g) for l=1, . . . , (L−1);
e) reading the next Nml bits of the message bit string;
f) using the Nml bits of the message data string to generate the Nml bits of the integer kl mod pl; and
g) setting the remaining (Nl−Nml) bits of the integer kl mod pl at random.

### Claim 11 (depends on 9)

The method of generating a message authentication code using blind randomization as recited in claim 9, wherein the integers gl are part of the shared secret key.

### Claim 12 (depends on 11)

The method of generating a message authentication code using blind randomization as recited in claim 11, wherein the integers gl are made public.

### Claim 13 (depends on 9)

The method of generating a message authentication code using blind randomization as recited in claim 9, wherein the data embedding method comprises the steps of:
a) defining M as an integer value of a bit string of a block of a message;
b) defining (N+1) as a number of bits needed to represent an integer
M
max
=
∏
l
=
1
L
-
1


p
l
;
c) setting a limit on the length of the bit string of the message block to be N; and
d) generating from the integer value M, (L−1) integer values kl, such that 0≦kl<pl where l=1, . . . , (L−1) using, kl=M mod pl, for l=1, . . . , (L−1).

### Claim 14

A method of generating a message authentication code using blind randomization, comprising the steps of:
a) sending and receiving correspondents agreeing upon on a set of elements {p1, p2, . . . , pL} which are relatively prime with respect to one another, the set of elements further being considered as a shared secret and which are further used to form a basis βs={p1, p2, . . . , pL}, the sending and receiving correspondents further agreeing upon an integer glεZpl for each element pl, where l=1, . . . , L, the sending and receiving correspondents further agreeing upon a data embedding method and an upper limit for the number of bits to be used to represent the message authentication code and an initial vector for the message authentication code elements c−1,l, l=1, . . . , L
the sending correspondent then performing the following steps:
b) selecting elements {q1′, q2′, . . . , qJ′,} wherein is an integer and J′>0, the elements being relatively prime with respect to one another and further being relatively prime with respect to the secret elements {p1, p2, . . . , pL}, the elements {q1′, q2′, . . . , qJ′,} being known to the sending correspondent only;
c) selecting a random sub-set of elements from the set {qi,1, qi,2, . . . , qi,l}, wherein the number of bits needed to represent
∏
l
=
1
L


p
l

∏
j
=
1
J


q
j
is within the upper limit agreed upon by the sending and receiving correspondents;
d) forming the basis β={p1, p2, . . . , pL, q1, q2, . . . , qJ} using the elements {p1, p2, . . . , pL-1} and the elements {q1, q2, . . . , qJ};
e) initializing an integer i as i=0, then repeating the following steps f) to g) until all of the message data blocks are processed, and incrementing at each step:
f) generating L integer values kl, where l=1, . . . , L, such that 0≦kl<pl from the lth block of the received message bit string using the data embedding method;
g) computing the message authentication code elements ci,l modulo pl as ci,l=fl(ci-1,l, gl, ki,l) for l=1, . . . , L, wherein fl(,) represents a modulo p function;
h) generating random values rj, where j=1, . . . , J, such that 0≦rj<qj for j=1, J;
i) combining the integer values Cu,l for l=1, . . . , L and the values rj for j=1, . . . , J to form a single integer vector {cu,1, cu,2, . . . , cu,L, r1, r2, . . . , rJ};
j) converting the integer vector {cu,1, cu,2, . . . , cu,L, r1, r2, . . . , rJ} into an integer value C using the basis β and the Chinese Remainder Theorem, the integer value C being the message authentication code value;
k) appending the bit string of the message authentication code integer value, C, to the message bit string and sending the concatenated bit string to the receiving correspondent;
the receiving correspondent then performing the following steps:
l) obtaining the message authentication code integer value C from the received message bit string;
m) computing the message authentication code elements cu,l modulo pl as cu,l=C mod pl for l=1, . . . , L;
n) initializing the integer i as i=0, then repeating the following steps o) to p) until all of the received message data blocks are processed, and incrementing fat each step:
o) generating L integer values kl, where l=1, . . . , L, such that 0≦kl<pl from the lth block of the received message bit string using the data embedding method;
p) computing the message authentication code elements rci,l modulo pl as rci,l=fl(rci-1,l, gl, ki,l) for l=1, . . . , L; and
q) if cu,l=rcu,l for all l, then the received message is authenticated.

### Claim 15 (depends on 14)

The method of generating a message authentication code as recited in claim 14, wherein the integers gl are part of the shared secret key.

### Claim 16 (depends on 14)

The method of generating a message authentication code as recited in claim 14, wherein the integers gl are made public.

### Claim 17 (depends on 14)

The method of generating a message authentication code as recited in claim 14, wherein the modulo p function of said step d) is computed as ci,l=ci-1,lglki,l.

### Claim 18 (depends on 14)

The method of generating a message authentication code as recited in claim 14, wherein the modulo p function of said step d) is computed as ci,l=g·ci-1,lki,l.

### Claim 19 (depends on 14)

The method of generating a message authentication code as recited in claim 14, wherein the modulo p function of said step d) is computed as ci,l=ci-1,l⊕gl⊕ki,l.

### Claim 20 (depends on 14)

The method of generating a message authentication code using blind randomization as recited in claim 14, wherein the data embedding method comprises the steps of:
a) defining M as an integer value of a bit string of a block of a message;
b) defining (N+1) as a number of bits needed to represent an integer
M
max
=
∏
l
=
1
L
-
1


p
l
;
c) setting a limit on the length of the bit string of the message block to be N; and
d) generating from the integer value M, (L−1) integer values kl, such that 0≦kl<pl where l=1, . . . , (L−1) using, kl=M mod pl, for l=1, . . . , (L−1).