 |
Claims  |
|
|
What is claimed is:
1. A method for preparing an entity to be authenticated by an
authenticating device including:
selecting a modulus N which is a product of two or more prime numbers;
selecting an integer e which is relatively prime to .PHI.(N), where
.PHI.(N) is Euler's totient function of N;
determining an integer d such that e.multidot.d =1 (mod .PHI.(N));
selecting a set of n public factors F.sub.1, . . . , F.sub.n, 0<F.sub.i <N;
calculating S.sub.i =F.sub.i.sup.d (mod N) for i=1, . . , n; and
storing the n values S.sub.i, i=1, . . . , n, and the value N in said
entity.
2. A method according to claim 1 wherein said entity includes a PROM, said
method further comprising:
storing said n values S.sub.i in said PROM.
3. A method according to claim 2 further comprising:
providing said entity with processing means and input/output means.
4. A method according to claim 1 further comprising:
assigning a public factor F.sub.ID unique to said entity;
computing S.sub.ID=F.sub.ID.sup.d (mod N); and
storing the value S.sub.ID in said entity.
5. A method of authenticating an entity by an authentication device
comprising:
(a) selecting a modulus N which is a product of two or more prime numbers;
(b) selecting an integer e which is relatively prime to .PHI.(N), where
.PHI.(N) is Euler's totient function of N;
(c) determining an integer d such that e.multidot.d=1 (mod .PHI.(N));
(d) selecting a set of n public factors F.sub.1, . . . , F.sub.n, 0<F.sub.i
<N;
(e) calculating S.sub.i =F.sub.i.sup.d (mod N) for i=1, . . . , n;
(f) storing the n values S.sub.i, i=1, . . . , n), and the value N in said
entity;
(g) placing said entity in communication with said authentication device;
(h) generating in said authentication device an n bit binary string
v=v.sub.i (i=1, . . . , n);
(i) transmitting said binary string v to said entity;
(h) calculating in said entity
##EQU22##
(k) transmitting Y to said authentication device;
(l) calculating in said authentication device: X.sub.ref
##EQU23##
and
X.sub.act =Y.sup.e (mod N); and
(m) comparing X.sub.ref and X.sub.act.
6. A method according to claim 5, wherein in said step (j) the value of Y
is calculated utilizing selectively an additional predetermined factor
S.sub.p, such that the total number of factors included in the calculation
of Y is even, and wherein in said step (1), the value of X.sub.ref is
correspondingly calculated. utilizing selectively an additional factor
F.sub.p, where S.sub.p =F.sub.p.sup.d.
7. A method according to claim 5 further comprising:
storing said said public factors F.sub.1, . . . , F.sub.n, and the values
of N and e in said authentication device.
8. A method according to claim 7 further comprising:
repeating said steps (h) to (m) a plurality of times, using random values
of v.
9. A method of certifying a message M by an entity comprising:
selecting a modulus N which is a product of two or more prime numbers;
selecting an integer e which is relatively prime to .PHI.(N), where
.PHI.(N) is Euler's totient function of N;
determining an integer d such that e.multidot.d=1 (mod .PHI.(N));
selecting a set of n public factors F.sub.1, . . . , F.sub.n, 0<F.sub.i<N;
calculating S.sub.i=F.sub.i.sup.d (mod N) for i=1, . . . , n;
storing the n values S.sub.i, i=1, . . . , n, and the value N in said
entity
computing a change sensitive transformation H of said message M;
generating an n bit binary string v=v.sub.i, i=1, . . . , n, using the
computed value of H;
computing
##EQU24##
and appending Y as a message authentication code certificate to said
message M.
10. A method according to claim 9 wherein said step of generating an n bit
binary string v includes:
converting H to a binary value J;
segmenting J into subfields of length n; and
adding together the individual subfields modulo 2 to for said n bit binary
string v.
11. A method according to claim 9 wherein said step of computing a change
sensitive transformation H includes:
computing H=M.sup.e (mod N).
12. A method according to claim 11 wherein said step of generating an n bit
binary string v includes:
converting H to a binary value J;
segmenting J into subfields of length n; and
adding together the individual subfields modulo 2 to form said n bit binary
string v.
13. A method of authenticating an entity by an authentication device
comprising:
(a) selecting a modulus N which is a product of two or more prime numbers;
(b) selecting an integer e which is relatively prime to .PHI.(N), where
.PHI.(N) is Euler's totient function of N;
(c) determining an integer d such that e.multidot.d=1 (mod .PHI.(N));
(d) selecting a set of n public factors F.sub.1, . . . , F.sub.n, 0<F.sub.i
<N;
(e) calculating S.sub.i=F.sub.i.sup.d (mod N) for i=1, . . . , n;
(f) storing the n values S.sub.i, i=1, . . . , n, and the value N in said
entity;
(g) placing said entity in communication with said authentication device;
(h) generating in said authentication device an n bit binary string
v=v.sub.i, i=1, . . . , n;
(i) transmitting said binary string v to said entity;
(j) selecting a value S.sub.set in said entity and computing in said entity
F.sub.set =S.sub.set.sup.e ;
(k) calculating in said entity
##EQU25##
(l) transmitting Y and F.sub.set to said authentication device;
(m) calculating in said authentication device:
##EQU26##
and
X.sub.act =Y.sup.e (mod N); and
(n) comparing X.sub.ref and X.sub.act.
14. A method according to claim 13 wherein S.sub.set is selected in
accordance with a count value which is incremented for each Y calculation.
15. A method according to claim 14 wherein S.sub.set is determined by
selecting a set S.sub.si of said factors S.sub.i, said selection being in
accordance with a binary string V.sub.s =v.sub.si generated in said
entity, and wherein Y is calculated according to the formula:
##EQU27##
where the v.sub.ai values correspond to the bits of said n-bit binary
string generated in said authentication device;
wherein step (1) further comprises transmitting V.sub.s to said
authentication device; and
wherein, in step (m), the value of X.sub.ref is calculated according to the
formula:
##EQU28##
16. A system, including an entity for generating an output Y in response to
an input v, said entity comprising:
memory means having stored therein a modulus N which is the product of at
least two prime numbers, and a set of n factors S.sub.i, i=1, . . . , n,
where S.sub.i =F.sub.i.sup.d (mod N), wherein d is the secret key
counterpart of a public key e associated with the modulus N, and F.sub.i,
i=1, . . . , n, are n public factors, 0<F.sub.i <N;
processing means adapted to compute
##EQU29##
where v=v.sub.i is an n bit binary string; and input/output means.
17. A system according to claim 16, wherein the value of Y includes an
additional factor S.sub.set which is dependent on a count value which is
incremented for each Y calculation.
18. A system according to claim 17, wherein said memory means has stored
therein an additional parity factor S.sub.p, and wherein said processing
means is adapted to compute the value of Y by selectively including said
additional parity factor S.sub.p in the expression for Y, such that the
total members of factors included in the calculation of Y is even.
19. A system according to claim 16 wherein:
said memory means has stored therein the value of said public key e; and
said processing means is further adapted (a) to compute H=M.sup.e (mod N),
where M is a message
to be transmitted by said entity;
(b) to convert H to a binary n bit vector v; and
(c) to compute
##EQU30##
using the bits v.sub.i of the computed vector v; and said input/output
means is adapted to transmit Y as a message authentication code associated
with said message.
20. A system according to claim 19, further including an authentication
device which comprises:
further input/output means;
further memory means having stored therein said n public factors F.sub.i
(i=1, . . . , n), said modulus N, and said public key e; and
further processing means adapted to compute
##EQU31##
(mod N); and X.sub.act =Y.sup.3 (mod N) using the stored values of
F.sub.i, N and e, and to compare X.sub.ref with X.sub.act.
21. A system according to claim 16, wherein said memory means has stored
therein a public factor F.sub.ID unique to said entity, and a value
S.sub.ID, where S.sub.ID =F.sub.ID.sup.d (mod N).
22. A system according to claim 21, further including an authentication
device which comprises:
further input/output means;
further memory means having stored therein said n public factors F.sub.i 1
, . . . , n, said modulus N, and said public key e; and
further processing means adapted to compute
##EQU32##
and X.sub.act =Y.sup.e (mod N) using the stored values of F.sub.i, N and
e, and to compare X.sub.ref with X.sub.act.
23. A system according to claim 22 wherein said further processing means is
further adapted to compute
##EQU33##
24. A system according to claim 16, further including an authentication
device which comprises:
further input/output means;
further memory means having stored therein said n public factors F.sub.i,
i=1, . . . , n, said modulus N, and said public key e; and
further processing means adapted to compute
##EQU34##
and X.sub.act =Y.sup.e (mod N) using the stored values of F.sub.i, N and
e, and to compare X.sub.ref with X.sub.act.
25. An entity comprising:
memory means having stored therein
(a) a modulus N which is the product of at least two prime numbers,
(b) a set of n factors S.sub.i, i=1, . . . , n, where S.sub.i =F.sub.i.sup.
(mod N), wherein d is the secret key counterpart of a public key e
associated with the modulus N, and F.sub.i, i=1, . . . , n, are n public
factors 0<F.sub.i <N,
(c) said n public factors F.sub.i, i=1, . . . , n,
(d) said modulus N, and
(e) said public key e;
processing means adapted to compute Y
##EQU35##
where v=v.sub.i is an n bit binary string and further adapted to compute
##EQU36##
and X.sub.act =Y.sup.e (mod N) using the stored values of F.sub.i, N and
e, and to compare X.sub.ref with X.sub.act ; and
input/output means.
26. An entity according to claim 25 wherein:
said memory means has stored therein the value of said public key e;
said processing means is further adapted
(a) to compute H=M.sup.e (mod N), where M is a message
to be transmitted by said entity;
(b) to convert H to a binary n bit vector v; and
(c) to compute
##EQU37##
using the bits v.sub.i of the computed vector v; and said input/output
means is adapted to transmit Y as a message authentication code associated
with said message.
27. An entity according to claim 26, wherein said memory means has stored
therein a public factor F.sub.ID unique to said entity, and a value
S.sub.ID, where S.sub.ID =F.sub.ID.sup.d (mod N).
28. An entity according to claim 27 wherein said processing means is
further adapted to compute
##EQU38##
29. An entity according to claim 28 wherein said processing means is
further adapted to compute
##EQU39##
. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
BACKGROUND OF THE INVENTION
This invention relates to the authentication of entities and messages.
It is a common requirement to verify the authenticity of data which may
represent monetary value or may imply the authenticity of the entity
generating that data. A typical application where authentication is
critical to avoid forgery is found in credit transactions using smart
cards. For example, before a credit transaction is undertaken the
authenticity of the smart card and/or value dispensed therefrom must be
proved to the authentication device (such as data recording or transfer
device) involved in the transaction.
To impede forgery only the entity source (for example, the manufacturer of
a smart card) should possess the means to produce the authentication
elements. This implies that the source must possess some secret. The
difficulty in proving authenticity is in providing the means to the
authenticator to achieve that proof. Many systems employ an algorithm
driven by a secret key such that a data string passed through the
algorithm results in a secret transformation of that data. The data so
transformed is used as an authentication certificate or code which may be
tested by an authenticator. One method of testing involves the
authenticator in performing the same secret transformation of the data to
yield an authentication certificate which is compared for equality with
that provided by the source entity (for example, a smart card).
The problem with this technique is that the authenticator must duplicate
the data manipulation by the source entity so as to compare the result for
equality. This means that an authenticator can forge an authentication
certificate and claim that it emanated from the source entity. Another
problem is that the authenticator must also have knowledge of the key.
This problem is particularly acute if several authenticators need to
authenticate an entity, since each must possess the secret key. Disclosure
of this key by one authenticator therefore compromises all authenticators
and the source entity. Furthermore, the secret key must be securely
distributed to each potential authenticator prior to the event. This
therefore limits the ability to authenticate to only those trusted
authenticators which were anticipated to require the function.
Where it may be necessary for a large number of unpredictable
authenticators to possess the ability to authenticate another entity, the
use of secret key algorithms is somewhat impractical. Further, when it is
desirable that the authenticator be completely denied the ability to forge
an authentication certificate the duplicative equality test method cannot
be employed.
Another known technique employs the art of public key cryptography wherein
an asymmetrical algorithm is used. Public key cryptography is described in
the article: Communications of the ACM, vol. 21, No. 2, February 1978,
pages 120-126, R. L. Rivest et al. "A Method for Obtaining Digital
Signatures and Public Key Crypto-systems". In this known technique, a data
element or a change sensitive compression of a data string is enciphered
using a secret key or procedure. Authenticity is proven by obtaining the
original data element (or change sensitive compression) which is used as a
reference value and then using a public key or procedure to decipher the
data supplied by the source entity. Equality of the deciphered data with
the reference data implies that the secret key or procedure was employed
and thus that the data is authentic.
This technique permits any authenticator to know the public key or
procedure with which to prove the authenticity of data emanating from an
entity possessing the complementary secret key or procedure. Consequently,
the key distribution problem is significantly eased as prior knowledge and
secrecy are not required.
However, the publicly known procedure must not permit the secret key or
procedure to be easily determined. Generally, the algorithms possessing
this property require substantial computing power to perform the secret
procedure. This usually renders them unsuitable for low cost entities
where operational speed is a requirement. If multiple portable entities or
the data emanating from them must be able to be tested for authenticity,
then the secret key and algorithm must be contained in each entity. In
this case, disclosure of the secret key in one entity will compromise all
similar entities.
This technique is therefore not practical for low cost replicated entities.
European Patent Application No. 0 252 499 discloses a method for creating a
unique card identifier in the form of a "smart card" which involves
selecting a modulus which is a product of two primes, preparing a string
of information unique to the card identifier, utilizing a pseudorandom
function to transform such string and a plurality of selected indices to
derive an associated plurality of values which are quadratic residues with
respect to the modulus, computing the square roots of the reciprocals of
the quadratic residues, and recording the information string, such square
roots and the related indices in the card identifier. Such card is
authenticated by transmitting the information string and the selected
indices from the card to a verification device and generating in the
verification device the quadratic residues utilizing the pseudorandom
function, selecting in the card a random number, computing the squared
value of the random number and transmitting such squared value from the
card to the verification device, generating in the verification device a
random vector which is sent to the card, computing in the card the product
of the random number and a selection of the stored square root values
dependent on the random vector, transmitting the product to the
verification device, squaring the transmitted product and multiplying such
squared value by a selection of the computed quadratic residue values
selected in accordance with the random vector, and checking that the
result value is equal to the squared random number. This known method is
complex and in particular involves the selection and utilization of
quadratic residue values.
OBJECTS OF THE INVENTION
It is an object of the present invention to provide a new and improved
method and system for the authentication of entities and messages.
It is another object of the present invention to provide a secure system
and method for authenticating entities and messages contained therein
which require relatively simple computations by the entity.
SUMMARY OF THE INVENTION
Therefore, according to one form of the present invention, there is
provided a method for preparing an entity to be authenticated by an
authentication device including:
selecting a modulus N which is a product of at least two prime numbers;
selecting an integer e which is relatively prime to .PHI.(N), where
.PHI.(N) is Euler's totient function of N;
determining an integer d such that e.multidot.d=1 (mod .PHI.(N));
selecting a set of n public factors F.sub.1, . . . , F.sub.n (0<F.sub.i
<N);
calculating S.sub.i =F.sub.i.sup.d (mod N) for i=1 . . . , n; and
storing the n values S.sub.i (i=1 . . . , n) and the value N in the entity.
According to another form of the present invention, there is provided a
method of authenticating an entity by an authentication device. The steps
include those described above for preparing the entity and further
include:
placing the entity in communication with an authentication device;
generating in the authentication device an n bit binary string v=v.sub.i
(i=1 . . . , n
transmitting the binary string v to the entity;
calculating, in the entity
##EQU1##
transmitting Y to the authentication device; calculating in the
authentication device:
##EQU2##
comparing X.sub.ref and X.sub.act.
According to another form of the present invention there is provided a
method of certifying a message M generated by or presented to an entity.
The steps include those described for the first form of the present
invention, preparing the entity, and further include:
computing a change sensitive transformation H of the message M;
generating an n bit binary string v=v.sub.i (i=1 . . . , n), using the
computed value of H;
computing Y=
##EQU3##
and appending Y as a message authentication code certificate to the
message M.
According to yet another form of the present invention, there is provided
an authentication system, including an entity which comprises processing
means, input/output means and memory means. The memory means has stored
therein a modulus N which is the product of at least two prime numbers,
and a set of n factors S.sub.i (i=1, . . . , n) where S.sub.i
=F.sub.i.sup.d (mod N), wherein d is the secret key counterpart of a
public key e associated with the modulus N, and F.sub.i (i=1, . . . , n)
are n public factors, 0<F.sub.i <N. The processing means is adapted to
compute
##EQU4##
where v=v.sub.i is an n bit binary string.
According to a still another form of the present invention, the
authentication system further includes further processing means, further
input/output means and further memory means. The further memory means has
stored therein the n public factors F.sub.i (i=1, . . . , n), the modulus
N, and the public key e. The further processing means is adapted to
compute
##EQU5##
and X.sub.act =Y.sup.e (mod N) using the stored values of Fi, N and e,
and to compare X.sub.ref with X.sub.act.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a block diagram showing the procedure utilized by a card issuer
in creating a smart card.
FIG. 2 is a block diagram of a card in operative association with a card
acceptor device.
FIG. 3 is a block diagram of a message source unit.
FIG. 4 is a block diagram of a message authentication unit.
FIG. 5 is a diagram showing the map of a memory utilized in an alternative
embodiment of the invention.
DETAIL DESCRIPTION OF THE INVENTION
Firstly, the theoretical basis underlying the invention will be explained,
as an aid to understanding the invention. It is known that, if N is the
product of (at least) two prime numbers P, Q, i.e., if
N=P .multidot.Q,
and if e is relatively prime to .PHI.(N), where
(N)=(P=1).multidot.(Q=1)
is Euler's totient function (the number of integers less than N which are
relatively prime to N), then, in modulus N arithmetic, a value d can be
determined (see for example, the aforementioned article by Rivest et al)
which is the multiplicative inverse of e such that
e .multidot.d=1 (mod .PHI.(N))
The value d is commonly referred to as the secret key counterpart of the
public key e.
Thus, if
X=Y.sup.e (mod N),
then
Y=X.sup.d (mod N)
for all values of Y, 0<Y<N.
Furthermore, if
X=F.sub.1 .multidot.F.sub.2 .multidot.. . . .multidot.F.sub.n (mod N)(1)
where F.sub.i (i=1, . . . , n) are integer values, with 0<F.sub.i <N
then
X.sup.d =F.sub.1.sup.d .multidot.F.sub.2.sup.d .multidot.. . .
.multidot.F.sub.n.sup.d (mod N)
and
X.sup.d (mod N)={F.sub.1.sup.d (mod N).multidot.F.sub.2.sup.d (mod
N).multidot.. . . .multidot.F.sub.n.sup.d (mod N)} (mod N)
Let
S.sub.i =F.sub.i.sup.d (mod N); i=1, . . . , n (2)
Then
X.sup.d (mod N)=S.sub.1 .multidot.S.sub.2 .multidot.. . . .multidot.S.sub.n
(mod N)
Let
Y=X.sup.d (mod N)
Therefore
Y=S.sub.1 .multidot.S.sub.2 .multidot.. . . .multidot.S.sub.n (mod N) (3)
Let v represent a binary string of n bits, v=v.sub.1 . . . v.sub.n such
that each bit v.sub.i of v is a flag indicating the inclusion of the
corresponding F.sub.1, . . . , F.sub.n and S.sub.1, . . . , S.sub.n in the
calculation of X and Y respectively, so that
##EQU6##
(4) From (3)
##EQU7##
(5) Therefore, provided that the N and d values employed in (1) and (2)
satisfy the above requirements, then
##EQU8##
for all values of F.sub.i, 0<F.sub.i <N.
With the above in mind, a first embodiment of the invention will now be
described, wherein multiple low cost entities, which will be referred to
in the descriptions of the preferred embodiments as smart cards, are
prepared by a card issuer and distributed to individuals. The embodiment
enables such issued cards to be expeditiously authenticated by verifying
devices.
Referring first to FIG. 1, a card issuer selects, as shown at box 12, a
plurality of n public factors F.sub.i (i=1, . . . , n), where 0<F.sub.i
<N, and such factors, together with the value of the modulus N and the
value of e are made publicly available to authenticators, that is,
organizations which may wish to authenticate smart cards issued by the
smart card issuer. In a particular application a suitable value for n is
32, and the value of N is in the range 2.sup.512 <N<2.sup.513.
The card issuer computes the n values S.sup.i, where
S.sub.i =F.sub.i.sup.d (mod N) i=1, . . . , n
as shown at box 14, using provided values of N and d (box 16), where d is
maintained secret. These values S.sub.i are also maintained secret. The
card issuer then issues cards which contain n values S.sub.i (i=1, . . . ,
n) stored in a secure manner, for instance in a secure PROM. It should be
understood that by a "secure PROM" herein is meant a PROM the contents of
which are protected from unauthorized read-out, for example, such
protection may involve software protection and hardware protection in the
form of shielding.
When it is desired to authenticate a smart card 30, FIG. 2, the card 30 is
inserted into a card acceptor device 32, whereby a data communication path
34 is established between the smart card 30 and the card acceptor device
32.
The smart card 30 includes a microprocessor 36, a RAM 38, a program PROM 40
which stores the program controlling the operation of the card 30, a
secure PROM 42 containing the n values S.sub.i (i=1, . . . , n) stored in
respective storage locations 102-1 to 102-n and the value N stored in a
storage location 104, and an input/output unit 44. Alternatively, since N
is a public value, it could be stored in the RAM 38. The elements 36, 38,
40, 42 and 44 within the card are interconnected by a communications bus
46.
The card acceptor device 32 includes a microprocessor 50, a RAM 52, a
program PROM 54 which stores the program controlling the operation of the
acceptor device 32, a keyboard 56, a display 58, a printer 60, a random
number generator 62, and an input/output unit 64. The RAM 52 includes
storage locations 112-1 to 112-n storing the n public factors F.sub.1, . .
. , F.sub.n and storage locations 114, 116 storing the values N and e,
respectively. The various units located in the card acceptor device 32 are
interconnected by a communications bus 66.
When a card 30 inserted into the card acceptor device 32 is to be checked
for authenticity, the random number generator 62 generates an n bit random
number v having n bits v.sub.i (i=1, . . . , n). In order to ensure that v
contains at least two bits equal to binary 1, the microprocessor 50 is
controlled, if necessary, to set the least significant bits of v
progressively to binary 1 until at least two binary 1 bits are present in
v. Thus, if the initial value of v is all zero bits, then the two least
significant bits are set to binary 1. The value v is stored in the RAM 52.
The value v is then transmitted from the RAM 52 via the input/output unit
64 over the communication path 34 and the input/output unit 44 and is
stored in the RAM 38 contained in the card 30. The microprocessor 36
checks that v contains at least two binary 1 bits, and if so, computes the
value Y where
##EQU9##
using the values S.sub.i stored in the PROM 42.
The value Y is then transmitted via the input/output unit 44, the
transmission path 34 and the input/output unit 64 and is stored in the RAM
52. Using the values F.sub.i (i=1, . . . , n) v, and e, stored in the RAM
52, the microprocessor 50 then computes
##EQU10##
and
X.sub.act =Y.sup.e (mod N),
and tests whether
X.sub.ref =X.sub.act.
Equality implies the authenticity of the X.sub.act response with
probability of 1:N. The authenticity of the card 30 producing the response
has a probability of 1:2.sup.n -n. By issuing repetitive random challenges
in the form of random values of v, the probability that the card 30 is
authentic increases exponentially by 1:(2.sup.n -n).sup.j where j is the
number of challenges issued.
It will be appreciated that the card 30 needs only to compute
##EQU11##
to respond to a challenge. Since this is at most n-1 multiplications using
modulo N arithmetic, the work factor is significantly less than
Y=X.sub.ref.sup.d (mod N) for any large value of d. In this connection, it
will be appreciated that since d is in effect the secret key associated
with the card 30, and given that
e.multidot.d=1 (mod .PHI.(N))
then d will be in the order of magnitude of 2N/3 for convenient values of
e. Thus, in the described embodiment, authentication security comparable
to that achievable with public key digital signature methods is achieved
with significantly less computational effort. Furthermore, with no secret
key used during the authentication process, it is possible to produce
multiple cards 30 loaded with the S.sub.l, . . . , S.sub.n values which
may be dynamically challenged by a verifying device to achieve similar
confidence levels to those obtained with public key digital signature
authentication methods.
It will be appreciated that the result of the authentication procedure can
be indicated on the display 58 and/or recorded by the printer 60.
In a second embodiment of the invention, a data string forming a message M
is authenticated by appending a certificate thereto. Such message M could,
for example, be a data string representing a legal document, a program
file, or other information. Referring to FIG. 3, there is shown a message
source unit 30A, which includes a message buffer 70 adapted to temporarily
store a message M to be authenticated. The message source unit 30A further
includes a microprocessor 36A, a RAM 38A, a program PROM 40A, a secure
PROM 42A and an input/output unit 44A connected to a communications path
34A. The message source unit 30A also includes a communications bus 46A
interconnecting elements 36A, 38A, 40A, 42A, 44A and 70 therein. It will
be appreciated that the elements having the references with suffix A in
FIG. 3 correspond to similarly referenced elements in the smart card 30
shown in FIG. 2, and in a practical implementation, the message source
unit 30A could be a smart card. Furthermore, the secure PROM 42A stores
the values S.sub.l, S.sub.2, ... S.sub.n in locations 102A-1 to 102A-n,
the value of the modulus N in storage location 104A and the value of e in
storage location 106A. Clearly, the values of N and e, being public
values, could alternatively be stored in the RAM 38a.
A message M stored in the message buffer 70 is authenticated by appending
thereto a message authentication code (MAC) which is computed in the
following manner.
Using the stored values of N and e, the microprocessor 36A first computes a
change sensitive transformation H of the message M. In the preferred
embodiment, this is effected by computing
H=M.sup.e (mod N)
The value H is then converted to a binary value J, which is segmented into
subfields of length n (with padding of an incomplete field with
predetermined binary bits if necessary) and the individual subfields are
added together modulo 2 (Exclusive OR operation) such that the resultant
binary string is used as v=v.sub.i (i=1, . . . , n) in the calculation of
Y, where
##EQU12##
as described in the first embodiment.
This value of Y is then appended as a message authentication code (MAC)
when the message M is transmitted from the message source unit 30A via the
input/output unit 44A to a communication path 34A.
An authentication device 32A, FIG. 4, which is of generally similar
construction to the card acceptor device 32 shown in FIG. 2 may be used to
authenticate the transmitted message M. The authentication device 32A
includes a message buffer 72, a RAM 52A, a program PROM 54A, a keyboard
56A, a display 58A, a printer 60A, an input/output unit 64A and an
interconnecting communications bus 66A.
Stored in the RAM 52A, in locations 112A-1 to 112A-n, 114A and 116A, are
the public factor values F.sub.1, . . . , F.sub.n, together with the
public key e and modulus N.
The message M, received over the communications path 34A is stored in the
message buffer 72, together with the MAC, Y.
Using the received message M, the microprocessor 50A computes H and J to
obtain v as in the message source unit 30A, and then computes
##EQU13##
utilizing the public factors F.sub.i stored in the RAM 52A.
Using the received value Y stored in the message buffer 70, the
microprocessor 50A then computes
X.sub.act =Y.sup.e (mod N).
Finally, the values of X.sub.act and X.sub.ref are compared using the
microprocessor 50A. Equality of X.sub.act and X.sub.ref implies that the
message source unit 30A possessed S.sub.1, . . . , S.sub.n, and thus that
the message M is authentic, within a probability of 1:N. It will be
appreciated that this embodiment has the advantage that a low cost entity
(message source unit 30A) may readily certify data emanating from it with
a probability of 1:N.
It should be understood that in the second embodiment, as in the first
embodiment, in order to protect the S.sub.i values from disclosure, it
must be ensured that v contains at least two binary 1 bits, by
progressively setting the least significant bits of v to binary 1 if
necessary.
The second embodiment of the invention has the further advantage that
several message source units 30A or the data emanating therefrom may be
authenticated without the unit actually being present at the time of
authentication. This ability is particularly useful for authenticating
messages which may have been produced some time earlier by various message
source units 30A, in the form of low cost entities such as smart cards.
Multiple message source units may share the same F.sub.1, . . . , F.sub.n
values which would be standardized for the scheme, with individual
integrity being ensured by various values of e and N.
However, it is preferred to standardize e and F.sub.1, . . . , F.sub.n for
all users of an authentication scheme within a group of users and for the
operator of each message source unit to publish a specific value N to be
used for his message source unit. Should an operator possess several such
units, rather than specifying a unique value of N for each unit, integrity
can be assured in a manner which will now be described with reference to
the third embodiment of the invention.
According to a third embodiment of the invention, a message M may be
authenticated as originating from a unique message source unit among a set
of such message source units sharing the same F.sub.1, . . . , F.sub.n and
N and e values. This has the advantage that it is infeasible for one
member of such a set to masquerade as another member of the set. For this
purpose, the operator of the system allocates to each message source unit
a public factor F.sub.ID which is unique to that source unit. Furthermore,
the operator of the system computes, for each such F.sub.ID value, a
corresponding S.sub.ID value;
S.sub.ID =F.sub.ID.sup.d (mod N),
where d is the system secret key, and stores S.sub.ID in the secure memory
of the relevant message source unit.
Referring to FIG. 5, there is shown a diagram of the secure PROM 42B
included in the message source unit. The PROM 42B contains storage
locations 102B-l to 102B-n storing the n values S.sub.1, . . . , S.sub.n
respectively, storage locations 104B and 106B storing the values N, e,
respectively, and storage locations 108, 110, storing the values F.sub.ID
S.sub.ID respectively.
In the third embodiment, it should be understood that the operation is
generally similar to that described for the second embodiment, except that
the calcula | | |
