Digital message encryption and authentication6396928Abstract A method and system for performing digital message encryption and signature encoding for use in, for example, communications and digital information storage systems, For secure communication of digital messages it is necessary to both encrypt the message and sign the message with a digital signature scheme to allow for authentication by the receiver. In order to the computational efficiency and reduce communications overhead in secure communications, a method and system, referred to as "signcryption", are provided in which the processes of encryption and authentication are combined. The principles of public key cryptography are utilised, although any suitable keyed encryption algorithm can be employed for the message encoding. Examples of signature schemes which can be easily implemented by signcryption include the ElGamal, Schnorr and Digital Signature Standard. Messages to multiple separate recipients can be efficiently dealt with, and because of the low computational and communications overheads the signcryption method is particularly applicable for use in smart cards and for highly secure and authenticated key transport over ATM. Claims What is claimed is: Description This invention relates to a method and system for performing digital message signature and encryption for secure and authenticated communication.
Communication
Scheme Computational cost overhead (in bits)
RSA encryption EXP = 1, ENC = 1 .vertline.n.sub.b.vertline.
[EXP = 1, DEC = 1]
ElGamal encryption EXP = 2, ENC = 1 .vertline.p.vertline.
[EXP = 1, DEC = 1]
RSA signature EXP = 1, HASH = 1 .vertline.n.sub.a.vertline.
[EXP = 1, HASH = 1]
ElGamal signature EXP = 1, MUL = 1, DIV = 1 2.vertline.p.vertline.
ADD = 1, HASH = 1
[EXP = 3, MUL = 1, DIV = 0
ADD = 0, HASH = 1]
Schnorr signature EXP = 1, MUL = 1, .vertline.KH ( .multidot.
).vertline. + .vertline.q.vertline.
ADD = 1, HASH = 1
[EXP = 2, MUL = 1, ADD = 0,
HASH = 1]
DSS EXP = 1, MUL = 1, DIV = 1 2.vertline.q.vertline.
ADD = 1, HASH = 1
[EXP = 2, MUL = 1, DIV = 2
ADD = 0, HASH = 1]
where EXP=the number of modulo exponentiations, MUL=the number of modulo multiplications, DIV=the number of modulo division (inversion), ADD=the number of modulo addition or sub on, HASH=the number of one-way or keyed hash operations, ENC=the number of encryptions using a private key cipher, DEC=the number of decryptions using a private key cipher, Parameters in the brackets indicate the number of operations involved in verification or decryption. Table 1: Cost of RSA, ElGamal, Schnorr, DSS Currently, the standard approach for a user, say Alice, to send a secure and authenticated message to another user Bob is signature-then on. FIG. 1 shows the format of a ciphertext in a signature-then-encryption based on discrete logarithm against that based on RSA. The notation EXP=N.sub.1 +N.sub.2 used in the figure indicates the relative computational expense, where N.sub.1 represents the number of modulo exponentiations carried out by a sender, and N.sub.2 represents the number by a recipient. To compare the efficiency of two different methods for secure and authenticated message delivery, consider first the two types of "cost" involved: (1) computational cost, and (2) communication overhead (or storage overhead for stored messages). The computational cost indicates how much computational effort has to be invested both by the sender and the recipient of a message. An estimate of the computational cost can be obtained by counting the number of dominant operations involved. Typically these operations include private key encryption and decryption, hashing, modulo addition, multiplication, division (inversion), and more importantly, exponentiation. In addition to computational cost digital signature and encryption based on public key cryptography also require extra bits to be appended to a message, which constitute the communication overhead. An embodiment of the present invention, referred to herein as a digital "signcryption" scheme, is a cryptographic method that fulfills both the functions of secure encryption and digital signature, but with a cost smaller than that required by signature then encryption Using the terminology in cryptography, it comprises a pair of (polynomial time) algorithms. (S,U), where S is called the "signcryption" algorithm, while U the "unsigncryption" algorithm. (S, U) should satisfy the following conditions: 1. Unique unsigncryptability--Given message m, the algorithm S signcrypts m and outputs a signcrypted text c. On input c, the algorithm U unsigncrypts c and recovers the original message un-ambiguously. 2. Security--(S, U) fulfills, simultaneously, the properties of a secure encryption scheme and those of a secure digital signature scheme. These properties mainly include: confidentiality of message contents, unforgeability, and non-repudiation. 3. Efficiency The computational cost, which includes the computational time involved both in signcryption and unsigncryption, and the communication overhead or added redundant bits, of the scheme is smaller than that required by known signature-then-encryption schemes. Since its introduction in 1985 [11], the ElGamal signature scheme has been generalized and adapted to numerous different forms (see for instance [15] where an exhaustive survey of some 13000 ElGamal based signatures has been carried out.) For most ElGamal based schemes, the size of the signature (r, s) on a message is 2.vertline.p.vertline., .vertline.q.vertline.+.vertline.p.vertline. or 2.vertline.q.vertline., where p is a large prime and q is a prime factor of p-1. The size of an ElGamal based signature, however, can be reduced by using a modified "seventh generalization" method. In particular, it is possible to change the calculations of r and s as follows: 1. Calculation of r-Let r=hash (k, m), where k=g.sup.x mod q (k=g.sup.x mod p-1 if the original r is calculated modulo (p-1)), x is a random number from [1, . . . , q] (or from [1, . . . , p-1] with x.multidot.(p-1), and hash is a one-way hash function such as Secure Hash Standard or HAVAL. 2. Calculation of s--For an efficient ElGamal based signature scheme the calculation of (the original) s from x.sub.a, x, r and optionally, hash(m) involves only simple arithmetic operations, including modulo addition, subtraction, multiplication and division. Here it is assumed that x.sub.a is the secret key of Alice the message originator. Her matching public key is y.sub.a =g.sup.x.sup..sub.a mod p. The calculation of s can be modified in the following way: (a) If hash(m) is uninvolved in the original s, hash(m) is replaced with a number 1, but r is left intact. The other way may also be used, namely changing r to 1 and then replacing hash(m) with r. (b) If s has the form of s=(.multidot. .multidot. .multidot. )x, then change it to s=x/(.multidot. .multidot. .multidot. ) does not add additional computational cost to signature generation, but may reduce the cost for signature verification. To verify whether (r, s) is Alice's signature on m, the value of k=g.sup.x mod p is recovered from g, y.sub.a, r and s, and then hash(k, m) is compared to r. Table 2 presented below shows two shortened versions of the Digital Signature Standard (DSS) formed by the shortening technique described above, which are denoted by SDSS1 and SDSS2 respectively. The parameter p, q and g are the same as those for standard DSS, x is a random number from [1, . . . , q], x.sub.a is Alice's secret key and y.sub.a =g.sup.x.sup..sub.a mod p is her matching public key, .vertline.t.vertline. denotes the size or length (in bits) of t. SDSS1 is slightly more efficient than SDSS2 in signature generation, as the latter involves an extra modulo multiplication. It can be shown that the shortened signature schemes SDSS1 and SDSS2 are unforgeable under the assumption that the one-way hash function behaves like a random function.
Shortened Signature (r, s) on a Recovery of Length of
schemes message m k = g.sup.x mod p signature
SDSS1 r = hash (g.sup.x mod p, m) k = (y.sub.a .multidot.
g.sup.r).sup.s .vertline.hash ( .multidot. ).vertline. +
.vertline.q.vertline.
s = x/(r + x.sub.a) mod q mod p
SDSS2 r = hash (g.sup.x mod p, m) k = (g .multidot.
y.sub.a.sup.r).sup.s .vertline.hash ( .multidot. ).vertline. +
.vertline.q.vertline.
s = x/(1 + x.sub.a .multidot. r) mod q mod p
p: a large prime (public to all), q: a large prime factor of p-1 (public to all), g: an integer in [1, . . . , p-1] with order q modulo p (public to all), x.sub.a : Alice's secret key, y.sub.a : Alice's public key (y.sub.a =g.sup.xa mod p). Table 2: Examples of Shortened and Efficient Signature Schemes A characteristic of a shortened ElGamal based signature scheme obtained in the method described above is that although g.sup.x mod p is not explicitly contained in a signature (r,s), it can be recovered from r, s and other public parameters. This enables the construction of a signcryption system from a shortened signature scheme such as the two shortened signature schemes SDSS1 and SDSS2, as described in detail hereinbelow. The same construction method is applicable to other shortened signature schemes based on ElGamal. Also, Schnorr's signature scheme, without being further shortened, can be used to construct a signcryption scheme which is slightly more advantageous in computation than other signcryption schemes from the view point of a message originator. The terms E and D are used below to denote the encryption and decryption algorithms of a private key cipher such as DES. Encrypting a message m with a key k, typically in the cipher block chaining or CBC mode, is indicated by E.sub.k (m), while decrypting a ciphertext c with k is denoted by D.sub.k (c). In addition KH.sub.k (m) is used to denote hashing a message m with a key-ed hash algorithm K H under a key k. An important property of a keyed hash function is that, just like a one-way hash function, it is collision-intractable. Therefore it can be used as an efficient message authentication code. Two methods for constructing a cryptographically strong key-ed hash algorithm from a one-way hash algorithm are described, for ample, [1]. For most practical applications, it suffices to define K H.sub.k (m)=hash(k, m,), where hash is a one-way hash algorithm. Assume that Alice also has chosen a secret key x.sub.a from [1, . . . , q], and made public her matching public key y.sub.a =g.sup.x.sup..sub.a mod p. Similarly, Bob's secret key is x.sub.b and his matching public key is y.sub.b =g.sup.x.sup..sub.b mod p. Relevant public and secret parameters are summarized as follows: Parameters public to all: p--a large prime q--a large prime factor of p-1 q--an integer in [1, . . . , p-1] with order q modulo p K H--a keyed one-way hash function (E, D)--the encryption and decryption algorithms of a private key cipher Alice's keys: x.sub.a --Alice's secret key y.sub.a --Alice's public key (y.sub.a =g.sup.x.sup..sub.a mod p) Bob's keys; x.sub.b --Bob's secret key y.sub.b --Bob's public key (y.sub.b =g.sup.x.sup..sub.b mod p) For Alice to signcrypt a message m for Bob, she carries out the following: Signcryption by Alice the Sender 1. Pick x randomly from [1, . . . , q], and let k=y.sup.x.sup..sub.b mod p. Split k into k.sub.1 and k.sub.2 of appropriate length. (Note: one-way hashing, or even simple folding, may be applied to k prior splitting, if k.sub.1 or k.sub.2 is too long to fit in E or K H, or one wishes k.sub.1 and k.sub.2 to be dependent on all bits in k.) 2. r.sub.k.sub..sub.2 (m). 3. s=x/(r+x.sub.a) mod q if SDSS1 is used, or s=x/(1+x.sub.a.multidot.r)mod q if SDSS2 is used instead. 4. c=E.sub.k.sub..sub.1 (m). 5. Send to Bob the signcrypted text (c, r, s). The unsigncryption algorithm takes advantage of the property that g.sup.x mod p can be recovered from r, s, g and y.sub.a by Bob. On receiving (c, r, s) from Alice, Bob unsigncrypts it as follows: Unsigncryption by Bob the Recipient 1. Recover k from r, s, g, p, y.sub.a and x.sub.b ; k=(y.sub.a.multidot.g.sup.r).sup.s'x.sup..sub.b mod p if SDSS1 is used, or k=(g.multidot.y.sub.a.sup.r).sup.s'x.sup..sub.b mod p if SDSS2 is used. 2. Split k into k.sub.1 and k.sub.2. 3. m=D.sub.k.sub..sub.1 (c). 4. accept m as a valid message originated from Alice only if K H.sub.k.sub..sub.2 (m) is identical to r. The format of the signcrypted text of a message m is depicted in FIG. 2, while the table below summarises the two signcryption schemes, denoted by SCS1 and SCS2, which are constructed from SDSS1 and SDSS2 respectively. The two signcryption schemes share the same communication overhead (.vertline.hash(.multidot.).vertline.+.vertline.q.vertline.). Although SCS1 involves one less modulo multiplication in signcryption does SCS2, both have a similar computational cost for unsigncryption.
Signcryption Signcrypted text (c, r, s) Recovery of
schemes of a message m (by Alice) k = g.sup.s.multidot.xb mod p (by
Bob)
SCS1 c = E.sub.k1 (m) k = (y.sub.a .times.
g.sup.r).sup.s.multidot.xb mod p
(from SDSS1) r = KH.sub.k2 (m)
s = x/(r + x.sub.a) mod q
SCS2 c = E.sub.k1 (m) k = (g .times.
y.sub.a.sup.r).sup.s.multidot.xb mod p
(from SDSS2) r = KH.sub.k2 (m)
s = x/(1 + x.sub.a .times. r) mod q
On Alice's side, x is a number chosen independently at random from [1, . . . , q], k is obtained by k=y.sub.b.sup.x mod p, k.sub.1 and k.sub.2 are the left and right halves of k respectively. (One-way hashing or folding may be applied to k prior splitting.) Bob can recover k from x.sub.b b, r, s, g and y.sub.a, and decipher c by m=D.sub.k.sub..sub.1 (c). He accepts m as a valid message from Alice only if r can be reconstructed from KH.sub.k.sub..sub.2 (m). A significant advantage of signcryption over signature-then-encryption lies in the dramatic reduction of computational cost and communication overhead which can be symbolize by the following inequality: Cost(signcryption)<Cost(signature)+Cost(encryption). The table below illustrates the major computations and resulting communications overhead for three prior art signature-then-encryption schemes, and for the two examples of signcryption described above.
Communication
Various schemes Computational cost overhead (in bits)
signature-then- EXP = 2, HASH = 1, ENC = 1 .vertline.n.sub.a.vertline. +
.vertline.n.sub.b.vertline.
encryption based [EXP = 2, HASH = 1, DEC = 1]
on RSA
signature-then- EXP = 3, MUL = 1, DIV = 1 2.vertline.q.vertline. +
.vertline.p.vertline.
encryption based ADD = 1, HASH = 1, ENC = 1
on DSS + [EXP = 3, MUL = 1, DIV = 2
ElGamal ADD = 0, HASH = 1, DEC = 1]
encryption
signature-then- EXP = 3, MUL = 1, DIV = 0 .vertline.KH ( .multidot.
).vertline. + .vertline.q.vertline. + .vertline.p.vertline.
encryption based ADD = 1, HASH = 1, ENC = 1
on Schnorr [EXP = 3, MUL = 1, DIV = 0
signature + ADD = 0, HASH = 1, DEC = 1]
ElGamal
encryption
signcryption EXP = 1, MUL = 0, DIV = 1 .vertline.KH ( .multidot.
).vertline. + .vertline.q.vertline.
SCS1 ADD = 1, HASH = 1, ENC = 1
[EXP = 2, MUL = 2, DIV = 0
ADD = 0, HASH = 1, DEC = 1]
signcryption EXP = 1, MUL = 1, DIV = 1 .vertline.KH ( .multidot.
).vertline. + .vertline.q.vertline.
SCS2 ADD = 1, HASH = 1, ENC = 1
[EXP = 2, MUL = 2, DIV = 0
ADD = 0, HASH = 1, DEC = 1]
where EXP=the number of modulo exponentiations, MUL=the number of modulo multiplications, DIV=the number of modulo division (inversion), ADD=the number of modulo addition or subtraction, HASH=the number of one-way or key-ed hash operations, ENC=the number of encryptions using a private key cipher, DEC the number of decryptions using a private key cipher, Parameters in the brackets indicate the number of operations involved in "decryption-then-verification" or "unsigncryption". An example of the savings in computation and communication overhead which can be achieved by an embodiment of the present invention is illustrated in the table below, where a signcryption scheme is compared with a signature-then-encryption procedure using Schnorr signature and ElGamal encryption, for various sizes of security parameters.
security parameters saving in saving in
.vertline.p.vertline., .vertline.q.vertline., computational
communications
.vertline.KH ( .multidot. ).vertline.( = .vertline.hash ( .multidot.
).vertline.) cost overhead
512, 144, 72 50% 70.3%
768, 152, 80 50% 76.8%
1024, 160, 80 50% 81.0%
1280, 168, 88 50% 83.3%
1536, 176, 88 50% 85.3%
1792, 184, 96 50% 86.5%
2048, 192, 96 50% 87.7%
2560, 208, 104 50% 89.1%
3072, 224, 112 50% 90.1%
4096, 256, 128 50% 91.0%
5120, 288, 144 50% 92.0%
8192, 320, 160 50% 94.0%
10240, 320, 160 50% 96.0%
In order to handle repudiation with a signature-then-encryption scheme, if Alice denies the fact that she has sent to Bob a message, all Bob has to do is to present to a judge (say Julie) the message together with its associated signature by Alice, based on which the judge will be able to settle a dispute, with digital signcryption, however, the verifiability of a signcryption is in normal situations limited to Bob the recipient, as his secret key is required for unsigncryption. Now consider a situation where Alice attempts to deny the fact that she has signcrypted and sent to Bob a message m, As in signature-then-encryption, Bob would first present the following relevant data items to a judge (Julie): q, p, g y.sub.a, y.sub.b, m, r and s. It is immediately apparent however, that the judge cannot make a decision using these data alone. Thus a repudiation settlement procedure different from the one for a digital signature scheme is required. In particular, the judge would need Bob's cooperation in order to correctly decide the origin of the message. To help the judge with her decision, Bob can choose to present to the judge either x.sub.b or k. Since x.sub.b is Bob's secret key, he may not wish to reveal it to the judge even if she is trusted. So the only choice for Bob would be to present k to the judge. Then, in conjunction with other data from Bob, the judge would be able to decide the origin of the message by: (1) spiting k into k.sub.1 and k.sub.2 and (2) checking whether r=KH.sub.k.sub..sub.2 (m). However, this still does not allow the judge to check whether k satisfies the condition k=u.sup.x.sup..sub.b mod p, where u=(y.sub.a.multidot.g.sup.r).sup.s mod p for SCS1, and u=(g.multidot.y.sub.a.sup.r).sup.s mod p for SCS2. In order to preclude Bob from acting dishonestly, it is necessary for the judge to be convinced by Bob that k has the right form, namely k=u.sup.x.sup..sub.b mod p, where x.sub.b is Bob's secret key satisfying the condition y.sub.b =g.sup.x.sup..sub.b mod p, and u=(y.multidot.g.sup.r).sup.s mod p for SCS1, and u=(g.multidot.y.sub.a.sup.r).sup.s mod p for SCS2. On the other hand, although Bob should be willing to answer the judge's request for proving k=u.sup.x.sup..sub.b mod p, he may not wish to leak to the judge any information on his secret key x.sub.b. These two seemingly conflicting goals can be simultaneously achieved by the use of a zero-knowledge interactive proof protocol as described below. Bob first presents to the judge q, p, g, y.sub.a, y.sub.b, m, r, s, and k Upon receiving the numbers, the judge calculates u=(y.sub.a.multidot.g.sup.r).sup.s =g.sup.x mod p if SCS1 is used, or u=(g.multidot.y.sub.a.sup.r).sup.a =g.sup.x mod p if SCS2 is used instead. Bob wishes to convince the judge that k=u.sup.x.sup..sub.b mod p, where x.sub.b is Bob's secret key satisfying y.sub.b =g.sup.x.sup..sub.b mod p. Note that in practice, certificates associated with y.sub.a and y.sub.b should also be submitted to the judge so that she can check their authenticity. Also note that m is not directly used in this convincing protocol. Instead, it will be used by the judge in deciding the origin of the message immediately after tis protocol is successfully completed. Convincing the Judge ##EQU1## The judge picks two random numbers j.sub.1 and j.sub.2 from [1, . . . , q]calculates J=u.sup.j.sup..sub.1 .multidot.g.sup.i.sup..sub.2 mod p, and sends the result J to Bob. ##EQU2## Upon receiving J from the judge, Bob picks a random number w from [1, . . . , q] calculates B.sub.1 =J.multidot.g.sup.w mod p and B.sub.2 =B.sub.1.sup.x.sup..sub.b mod p, sends the two resulting numbers to the judge. ##EQU3## Upon receiving B.sub.1, and B.sub.2, the judge sends j.sub.1, and j.sub.2 to Bob. ##EQU4## Bob checks whether u.sup.j.sup..sub.i .multidot.g.sup.j.sup..sub.2 mod p is identical to the number J received from the judge in the first move. If it is, Bob sends w to the judge. Otherwise chewing by the judge is detected, and the protocol is aborted. If the judge receives w from Bob, she checks whether B.sub.1 can be recovered from J.multidot.g.sup.w w mod p, and B.sub.2 recovered from K.sup.j.sup..sub.1 .multidot.y.sub.b.sup.j.sup..sub.2+w mod p. The judge is convinced that k.sub.1.sup.x.sup..sub.b mod p only if both J.multidot.g.sup.w mod p=B.sub.1 and k.sup.j.sup..sub.1 .multidot.y.sub.b.sup.j.sup..sub.2+w mod p=B.sub.2 hold. Using this protocol, the following three results can be proven: 1. completeness--if k is indeed identical to u.sup.x.sup..sub.b mod p, then by following the protocol Bob can always convince the judge of the fact. 2. soundness--the probability for Bob to supply a "wrong" k' with k' .noteq. k, and cheat the judge into believing that k'=u.sup.x.sup..sub.b mod p is at most 1/q, a vanishingly small probability for q>=2.sup.144. 3. zero-knowledge--no information on x.sub.b is leaked to the judge. Once being convinced that k=u.sup.x.sup..sub.b mod p, the judge would split k into k.sub.1 and k.sub.2, decipher c by m=D.sub.k.sub..sub.1 (c), and check whether r can be re-constructed from KH.sub.k.sub..sub.2 (m). (m, r, s) will be ruled as being originated from Alice if r=KH.sub.k.sub..sub.2 (m) holds. The foregoing description relates to the case of a message which is directed to only a single recipient. In practice, broadcasting a message to multiple users in a secure and authenticated manner is a useful facility, to enable a group of people who are jointly working on the same project to communicate with one another. In this scenario, a message is broadcast tough a so-called multi cast channel, one of whose properties is that all recipients will receive an identical copy of a broadcast message. Some concerns with encryption and authentication of a message broadcast to multiple recipients include security, unforgeability, non-repudiation and consistency of a message. Consistency means that all recipients recover an identical message from their copies of a broadcast message, and its aim is to prevent a particular recipient from being excluded from the group by a dishonest message originator. With the traditional signature-then-encryption, a common practice has been to encrypt the message-encryption key using each recipient's public key and attach the resulting ciphertext to the signed and also encrypted message. FIG. 3 illustrates the format of a multiple recipient message signed and encrypted based on RSA, and another using a discrete logarithm based approach such as Schnorr signature and ElGamal encryption. Embodiments of the present invention can also be adapted for multiple recipients. The basic idea is to use two types of keys: the first type consists of only a single randomly chosen key (a message-encryption key) and the second type of keys include a key chosen independently at random for each recipient (called a recipient specific key). The message-encryption key is used to encrypt a message with a private key cipher, while a recipient specific key is used to encrypt the message-encryption key. A multiple recipient signcryption procedure based on SCS is detailed below, referred to as SCSM. The output format of the multiple recipient signcryption is shown in FIG. 4. Signcryption by the Sender for Multi-Recipients An input to this signcryption algorithm for multi-recipients consists of a message m to be sent to 1 recipients R.sub.1, . . . , R.sub.4, Alice's secret key x.sub.a, R.sub.i 's public key y.sub.i for all 1.ltoreq.i.ltoreq.l, q and p. 1. Pick a random message-encryption key k, calculate h=KH.sub.k (m), and encrypt m by c=E.sub.k (m.vertline..vertline.h), where .vertline..vertline.denotes concatenation. 2. Create a signcrypted text of k for each recipient i=1, . . . , l: (a) Pick a random number v.sub.i from [1, . . . , q] and calculate t.sub.i =y.sub.i.sup.v.sup..sub.i mod p. Then split t.sub.i into t.sub.i,1 and t.sub.i,2 of appropriate length. (One-way hashing or folding may be applied to k prior splitting.) (b) d.sub.i =E.sub.ti,1 (k). (c) r.sub.i =KH.sub.ti,2 (m,h). (d) s.sub.i =v.sub.i /(r.sub.i +x.sub.a) mod p. Alice then broadcast to all the recipients (c, d.sub.1, r.sub.1, s.sub.1, . . . , d.sub.l, r.sub.l, s.sub.l. Unsigncryption by Each Recipient An input to this unsigncryption algorithm consists of a signcrypted at (c, d.sub.1, r.sub.1, s.sub.1, . . . , d.sub.1, r.sub.1, s.sub.1) received through a broadcast channel, together with a recipient R.sub.i 's secret key x.sub.i where 1.ltoreq.i .ltoreq.l, Alice's public key, y.sub.a, g, q and p. 1. Find out (c, d.sub.i, r.sub.i, s.sub.i) in (c, d.sub.1, r.sub.1, s.sub.1, . . . , d.sub.l, r.sub.l, s.sub.l). 2. t.sub.i =(y.sub.a.multidot.g.sup.r.sup..sub.i ).sup.s.sup..sub.i .sup..multidot.x.sup..sub.i mod p. Split t.sub.i into t.sub.i,1 and t.sub.i,2. 3. k=D.sub.t.sub..sub.i,l (d.sub.i). 4. w=D.sub.k (c). Split w into m and h. 5. check if h can be recovered from KH.sub.k (m) and r, recovered from KH.sub.t.sub..sub.i,2 (w). R accepts m as a valid message originated from Alice only if both h=KH.sub.k (m) and r.sub.i =KH.sub.t.sub..sub.i,2 (w) hold. As discussed earlier, a message delivery scheme for multiple recipients is said to be consistent if messages recovered by the recipients are identical. Such a requirement is important in the case of multiple recipients, as otherwise the sender may be able to exclude a particular recipient from the group of recipients by deliberately causing the recipient to recover a message different from the one recovered by other recipients. With SCS1M message consistency is achieved through the use of two Piques; (1) a message m is encrypted together with the hashed value h=KH.sub.k (m), namely c=E.sub.k (m.vertline..vertline.h); (2) m and k are both involved in the formation of r, and s.sub.i through r.sub.i =KH.sub.t.sub..sub.1,2 (m, h). These two techniques effectively prevent a recipient from being excluded from the group by a dishonest message originator. The confidentiality, unforgeability and non-repudiation of multiple recipient signcryption is similar to the case of a single recipient as discussed above. Further, the multiple recipient signcryption scheme described, as with the single recipient methods, provides significant advantages in computational cost and communications overhead as compared to known signature-then-encryption methods for multiple recipients. The embodiments of the present invention described herein are compact in both execution and communications requirements, and are particularly well suited for smart card based applications, such as digital cash payment systems, personal health cards and the like. For example the encryption and authentication method of the present invention may be embodied in a series of computer program instructions stored in a memory circuit for execution by a microprocessor or the like. Alternatively, the instructions embodying the invention may be incorporated into a custom made integrated circuit or programmable logic circuit. Another useful property of the described signcryption schemes is that it enables highly secure and authenticated key transport in a single block whose size is smaller than .vertline.p.vertline.. In particular, using the two described signcryption schemes, it is possible to transport highly secure and authenticated keys in a single ATM cell (48 byte payload+5 byte header). In a similar way, a multi-recipient signcryption scheme can be used as a very economic method for distributing conference keys among a group of user;. It will be readily recognised by those skilled in the art that various modifications can be made to the described signcryption schemes without departing from the spirit and scope of the present invention. For example, although the calculations described here have been presented in terms of modular arithmetic, any suitable form of finite field calculations may be employed, such as calculations based on elliptic curves over a finite field. Obviously variations in the actual algorithm employed to implement the signcryption will also fall within the scope of the invention where the algorithm still utilises the principles of the present invention as hereinbefore described and as defined in the claims. Throughout this specification and the claims which follow, unless the contact requires otherwise, the word "comprise", or variations such as "comprises" or "comprising", will be understood to imply the inclusion of a stated integer or group of integers but not the exclusion of any other integer or group of integers. The foregoing detailed description of embodiments of the invention has been presented by way of example only, and is not intended to be considered limiting to the invention defined in the claims appended hereto.
|
Same subclass Same class Consider this |
||||||||||