AU721497B2 - Digital message encryption and authentication - Google Patents

Description

Regulation 3.2

AUSTRALIA

Patents Act 1990 COMPLETE SPECIFICATION FOR A STANDARD PATENT

(ORIGINAL)

Name of Applicant: Monash University, of Wellington Road, Clayton, Victoria 3168, Australia r Actual Inventor: Yuliang Zheng Address for Service: DAVIES COLLISON CAVE, Patent Attorneys, of 1 Little Collins Street, Melbourne, Victoria 3000, Australia Invention Title: "Digital message encryption and authentication" Details of Associated Provisional Application No: P03234/96 The following statement is a full description of this invention, including the best method of performing it known to me/us: -1- DIGITAL MESSAGE ENCRYPTION AND AUTHENTICATION This invention relates to a method and system for performing digital message signature and encryption for secure and authenticated communication.

To avoid forgery and ensure confidentiality of a message, for example the contents of a letter, for centuries it has been a common practice for the originator of the letter to sign his/her name on it and then seal it in an envelope, before effecting delivery. More recently, digital messages, communicated telephonically or the like, have become increasingly used, and public key cryptography has been employed to conduct secure and authenticated communications.

It is thereby possible for people who have never met before to communicate with one another in a secure and authenticated way over an open and insecure network such as Internet. In doing so the same two-step approach used for conventional letters has been followed.

Namely, before a message is sent out, the sender of the message would sign it using a digital signature scheme, and then encrypt the message (and the signature) using a private key encryption algorithm under a randomly chosen message encryption key. The random :i message encryption key would then be encrypted using the recipient's public key. This twostep approach is referred to as signature-then-encryption.

Signature generation and encryption consume machine cycles, and also introduce "expanded" S bits to an original message. Hence the cost of a cryptographic operation on a message is typically measured in the message expansion rate and the computational time invested by both the sender and the recipient. With the current standard signature-then-encryption, the cost of delivering a message in a secure and authenticated way is essentially the sum of the cost for digital signature and that for encryption.

-3- The present invention aims to provide a method and system, referred to as "signcryption", in which the processes of encryption and authentication of a message are combined so as to achieve improved improved computational efficiency and reduced message transmission overhead.

In accordance with the present invention, there is provided a method for authenticated encryption of a digital message m for transmission from a sender having a public key ya and a secret key Xa and a receiver having a public key yb and a secret key Xb, comprising: determining a message key k using the receiver public key and a randomly selected number x; calculating a first message parameter r, comprising a message authentication code, from said digital message m and a first portion of said message key k; calculating a second message parameter s from the sender private key, the randomly selected number x and the first message parameter r, such that said message key k is recoverable by the receiver from an arithmetic operation of said first and second message "parameters, the sender public key and the receiver private key; and otiencrypting said digital message m using a second portion of said message key k to oooo obtain cipher text c.

Preferably the cipher text c is transmitted from said sender to said receiver together with said first and second message parameters. The receiver may then recover the message key k from said first and second message parameters with said sender public key and said receiver private key, and decrypt the cipher text c using the second portion of the recovered message key to obtain said digital message. The recovered digital message can then be validated by 25 calculating the first message parameter using the recovered digital message and the first oe i :portion of the recovered message key and making a comparison with the first message parameter received with the cipher text.

-4- In one form of the invention the message key k is calculated according to k y' mod p, where p is a large prime. Before splitting the message key into first and second portions, it is possible to apply a one-way hashing or folding function, for example, in order to obtain first and second message key portions which are of suitable length for calculating said first message parameter and encrypting said digital message, respectively.

Preferably, the first message parameter comprises a keyed hash of the digital message using the first portion of the message key.

Preferably the second message parameter is calculated according to a modified EIGamal signature scheme in which the hashed digital message value is replaced by the value 1 or the first message parameter. A similar modification of the Schnorr signature scheme or Digital signature standard may similarly be used to calculate the second message parameter.

The digital message itself may be encrypted using any suitable keyed encryption algorithm, such as the Digital Encryption Standard (DES), or the like.

Advantageously, the only data required to be transmitted between the sender and receiver to enable secure authenticated message delivery is the cipher text c and the first and second message parameters r and s, because the message key can be recovered from the first and second message parameters, and the message content can be verified using the message key

CS

and the first message parameter r.

The present invention also provides a method of preparing a digital message m for secure and authenticated communication from a sender having a public key Ya and a private key Xa to a receiver having a public key yb and a private key Xb, comprising: determining a message key k based on the receiver public key Yb and a randomly selected number x; splitting the message key k into first and second keys k, and k 2 calculating a first message parameter r as a keyed hash of said digital message using said first key kj; calculating a second message parameter s on the basis of said randomly selected number x, said sender secret key x, and said first message parameter r; encrypting said digital message using said second key k 2 to obtain cipher data c; and appending said cipher data c with said first and second message parameters for transmission to said receiver.

In a system for transmission of digital messages between a sender having a public key y, and a secret key x, and a receiver having a public key Yb and a secret key Xb, and having public parameters p being a prime number, q being a prime factor of and g being an integer in the range 1 to with order modulo p, the present invention also provides a method for authenticated encryption of a digital message m, comprising the steps of selecting a random number x in the range 1 to such that x does not divide determining a message key; i splitting the message key k into first and second keys k, and k 2 calculating a first message parameter r as a keyed hash of said digital message m using said first key kj; calculating a second message parameter s on the basis of modular arithmetic to base q utilising said random number x, said sender private key Xa and said first message parameter r; encrypting said digital message m using said second key k2 to obtain cipher data c; and S appending said cipher data c with said first and second message parameters r and s for transmission to said receiver.

S The present invention further provides a method for secure and authenticated communication of a digital message m from a sender having a public key Ya and a private key xa to a receiver having a public key yb and a private key Xb, comprising: -6determining a message key k based on the receiver public key Yb and a randomly selected number x; splitting the message key k into first and second keys k, and k 2 calculating a first message parameter r as a keyed hash of said digital message using said first key kl; calculating a second message parameter s on the basis of said randomly selected number x, said sender secret key Xa and said first message parameter r; encrypting said digital message using said second key k 2 to obtain cipher data c; transmitting the cipher data c and the first and second message parameters r and s to said receiver; recovering said message key from an operation using said first and second message parameters r and s, said sender public key Ya and said receiver private key xb; recovering said first and second keys k, and k 2 from said message key k; decrypting said cipher data c using the second key k 2 to recover said digital message m; and validating said digital message using said first key k, and said first message parameter r.

Moreover, the present invention provides an apparatus for preparing a digital message m for secure and authenticated communication from a sender having a public key Ya and a private okey xa to a receiver having a public key Yb and a private key Xb, comprising: means for determining a message key k based on the receiver public key yb and a randomly selected number x; means for splitting the message key k into first and second keys k, and k 2 means for calculating a first message parameter r as a keyed hash of said digital message using said first key kj; means for calculating a second message parameter s on the basis of said randomly selected number x, said sender secret key Xa and said first message parameter r; -7means for encrypting said digital message using said second key k 2 to obtain cipher data c; and means for appending said cipher data c with said first and second message parameters for transmission to said receiver.

In the preferred form of the invention, the means for carrying out the functions of the invention are incorporated in digital processing circuitry provided on one or more integrated circuits. The authenticated encryption of the invention may be implemented by a digital processing circuit, such as a microprocessor, operating under control of stored program instructions accessed from a memory circuit or the like. The present invention is particularly suitable for use in sending authenticated and encrypted message data from a smart card or the like.

The invention is described in greater detail hereinafter, by way of example only with reference to several embodiments thereof and the accompanying drawings, wherein: "i Figure 1 is a diagrammatic representation of the authenticated encrypted message format based on discrete logarithm and RSA systems; Figure 2 is a diagrammatic representation of a signcrypted message format; Figure 3 is a diagrammatic representation of a multiple recipient message format based on RSA and discrete logarithm systems; and Figure 4 is a diagrammatic representation of a multiple recipient signcrypted message.

As mentioned above, the use of public key cryptography enables a person to digitally sign a message, and send the message securely to another person with whom no common encryption 25 key has been shared. Several known public key digital signature/encryption schemes are summarised below, these being RSA encryption and signature scheme, ElGamal encryption and signature scheme, and two signature schemes derived from ElGamal, namely Schnorr signature scheme and Digital Signature Standard (DSS).

-8- To assist the description of the various schemes, consider a situation where a user (say Alice) wishes to deliver a message to another user (say Bob) over an open insecure communication network such as Internet. The term hash is used to denote a one-way hash algorithm such as SHS [National Institute of Standards and Technology. Secure hash standard. Federal Information Processing Standards Publication FIPS PUB 180-1, U.S. Department of Commerce, April 1995] and HAVAL Zheng and J. Seberry. Immunizing public key cryptosystems against chosen ciphertext attacks. IEEE Journal on Selected Areas in Communications, 11(5):715-724, June 1993]. The symbols E and D are used to denote the encryption and decryption algorithms of a private key cipher such as DES [National Bureau of Standards. Data encryption standard. Federal Information Processing Standards Publication FIPS PUB 46, U.S. Department of Commerce, January 1977]. Encrypting a message m with a key k, typically in the cipher block chaining or CBC mode, is indicated by Ek(m), while decrypting a ciphertext c with k is denoted by Dk(c).

RSA Signature and Encryption The RSA scheme is based on the difficulty of factoring large composite numbers. To use RSA, Alice first has to choose two large random primes Pa and qa. She then calculates the products n, paqa and j(n) (Pa 1)(qa Next she selects two numbers ea and da from (1, n) such that eada 1 mod(p(n). Finally Alice publishes (ea, n a as her public key in a public key file, while she keeps da as her secret key.

Alice's signature on a message m is defined as s hash(m)da mod na. Other users can verify whether s is Alice's valid signature on m by checking whether hash(m) is identical to sea mod na.

Similarly to Alice, user Bob can create his public key (eb, nb) and secret key db. To send a (long) message m to Bob in a secure way, Alice picks a random message-encryption key k and sends to Bob c, Ek(m) and c 2 keb mod nb. Upon receiving cl and c 2 Bob can retrieve k by calculating c2b mod nb, with which he can decrypt cl.

ElGamal Signature and Encryption ElGamal digital signature and encryption schemes are based on the hardness of computing discrete logarithm over a large finite field. It involves two parameters public to all users: 1. p: a large prime.

2. g: an integer in p 1] with order p 1 modulo p.

User Alice's secret key is an integer xa chosen randomly from p 1] with xa XJ( 1) xa does not divide p and her public key is ya g" mod p.

Alice's signature on a message m is composed of two numbers r and s which are defined as Sr= gx mod p s (hash(m) xa r)/x mod p 1 where x is a random number from p 1] with x X (p It should be noted that for the purposes of security, x should be chosen independently at random every time a message is to be signed by Alice.

Given r, one can verify whether ghash(m) y rs mod p is satisfied. s) is regarded as Alice's signature on m only if the equation holds.

Now assume that Bob has also chosen his secret key Xb randomly from p 1] with Xb X (p and made public the matching public key yb g mod p. By using Bob's public key, Alice can send him messages in a secure way. To do this, Alice chooses, for each message m, a random integer x from p 1] with x I (p calculates k y mod p and sends to Bob cl Ek and c2 g mod p.

Upon receiving cl and c 2 Bob can recover k by k c2 b mod p. He can then use k to decrypt c, and obtain m.

Note that ElGamal encryption can also be achieved using parameters for the Schnorr signature and DSS described below.

Schnorr Signature Scheme The Schnorr signature scheme, together with DSS described below, is a variant of the ElGamal signature scheme. The main idea behind the two variants is to choose g to be an integer in the range p 1] with order q modulo p for a prime factor q of p 1, instead of with order p 1 modulo p.

The Schnorr signature scheme involves the following parameters: 1. Parameters public key to all users: p: a large prime, say p 2512.

q: a prime factor of p 1. The size of q would be at least 21.

g: an integer in p 1] with order q modulo p. In practice, g is obtained by calculating g yq mod p where h is an integer satisfying 1 h p 1 and he l yq mod p 1.

2. Parameters specific to user Alice: Alice's secret key: a number Xa drawn randomly from q 1].

Alice's public key: ya mod p.

11 With the above parameters, Schnorr suggests that Alice sign a digital document m by picking a random x from q 1] and appending to m a pair of numbers which are calculated as follows: r hash (gX mod p,m) S= x Xa r mod q The procedure for other people to verify Alice's signature on m is straightforward: checking whether r is identical to hash x yr mod m).

If Alice publishes Ya gXa mod p, instead of ya g' mod p, then s can be defined as s x x, x r mod q. Signature verification is the same.

Digital Signature Standard (DSS) The public and secret parameters involved in DSS are all the same as those in Schnorr .o signature scheme, except that for DSS, Alice's public key is ya g mod p, but not ya mod p as is the case for Schnorr signature scheme. In addition, the standard suggest that, for current applications, Ipl be between 512 and 1024, Iql 160, and SHS whose output has 160 its be used as the one-way hash function.

Alice's signature on a message m is composed of two numbers r and s which are defined as (gmod p) mod q "s (hash(m) xa r)/x mod q S 25 where x is a random number chosen from q 1].

Given r, one can verify whether is indeed Alice's signature on m by the following steps: 1. calculates v (ghash(m x yS mod p) mod q.

12 2. accepts as valid only if v r.

Table 1 presented below compares the computational cost and communication overhead of the signature and encryption schemes. Note that to use RSA signature in a provably secure way, more extra computational effort (not shown in the table) has to be invested in the signing process. Similarly, to employ RSA and ElGamal encryptions in a provably secure fashion, more computational effort and communication overhead is required.

Scheme Computational cost Communication overhead (in bits) RSA encryption EXP= 1, ENC= I Ind [EXP= 1, DEC=lI] ElGamal encryption EXP=2, ENC=1 1II [EXIP=1, DEC=1] RSA signature EXP=1, HASH1=l Indl [EXP=1, HASH= 1] ElGamal signature EXP=1, MIJL=1, DIV=1 2 1pl ADD=1, HASH=I [EXP=3, MUL=1, DIV=O ADD=O, HASH-= 1] Schnorr signature EXP=1I, MIJL=1, IKH.(-I Iqj ADD=1, HASH=1 [EXP=2, MUL=1, ADD=O, HASH=1] DSS EXP=1, MUL=I, DIV=1 21ql ADD=1, HASH=1 [EXP=2, MUL= 1, DIV=2 ADD=O, HASH= 1]

S

5555.5

S

555555 S S 13where 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 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-encryption. Figure 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 1

N

2 used in the figure indicates the relative computational expense, where N, represents the number of modulo exponentiations carried out by a sender, and N 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: 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 25 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.

14- 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. 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 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 06** 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 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 s) on a message is 2 1p, Iq| Ipl or 21ql, where p is a large prime and q is a prime factor of p 1. The size of an EIGamal 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: 9* 1. Calculation of r Let r hash where k gX mod q (k gX mod p 1 if the original r is calculated modulo (p x is a random number from q] (or from p 15 1] with x (p 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 Xa, x, r and optionally, hash(m) involves only simple arithmetic operations, including modulo addition, subtraction, multiplication and division. Here it is assumed that xa is the secret key of Alice the message originator. Her matching public key is Ya= gXa mod p. The calculation ofs can be modified in the following way: If hash(m) is involved 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.

If s has the form of s then changing it to s does not add additional computational cost to signature generation, but may reduce the cost for signature verification.

To verify whether s) is Alice's signature on m, the value of k gX mod p is recovered from r and s, and then hash(k, m) is compared to r.

090" 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 love* SDSS2 respectively. The parameters p, q and g are the same as those for standard DSS, x is a 9@ random number from xa is Alice's secret key and ya g' mod p is her matching too.

440" public key, Itt denotes the size or length (in bits) of t. SDSSI is slightly more efficient than SDSS2 in signature generation, as the latter involves an extra modulo multiplication. It can be 0900* 25 shown that the shortened signature schemes SDSS1 and SDSS2 are unforgeable under the 0 assumption that the one-way hash function behaves like a random function.

16- Shortened Signature on a Recovery of Length of signature schemes message m k gX mod p SDSS1 r= hash mod p, m) k (ya gr) mod p Ihash ql s x/(r Xa) mod q SDSS2 r= hash (gX mod p, m)s k (g y) modp Ihash Iql Xa- r) mod q p: a large prime (public to all), q: a large prime factor of p 1 (public to all), g: an integer in p 1] with order q modulo p (public to all), i:xi a: Alice's secret key, ya: Alice's public key (ya= g' mod p).

Table 2: Examples of Shortened and Efficient Signature Schemes •A characteristic of a shortened EIGamal based signature scheme obtained in the method described above is that although gX mod p is not explicitly contained in a signature it can be recovered from r, s and other public parameters. This enables the construction of a i 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 Ek(m), while decrypting a ciphertext c with k is denoted by Dk(c). In addition KHk(m) is used 17to denote hashing a message m with a key-ed hash algorithm K H under a key k. An important property of a key-ed 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 oneway hash algorithm are described, for example, For most practical applications, it suffices to define K Hk(m) hash(k,m,), where hash is a one-way hash algorithm.

Assume that Alice also has chosen a secret key x, from and made public her matching public key y, g' mod p. Similarly, Bob's secret key is Xb and his matching public key is yb gb 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 S 15 g an integer in p 1] with order q modulo p S: K H a key-ed one-way hash function D) the encryption and decryption algorithms of a private key cipher Alice's keys: x, Alice's secret key ya Alice's public key ga mod p) Bob's keys: Xb Bob's secret key yb Bob's public key (yb gb mod p) 18 For Alice to signcrypt a message m for Bob, she carries out the following: Signcryption by Alice the Sender 1. Pick x randomly from and let k yXb mod p. Split k into k, and k 2 of appropriate length. (Note: one-way hashing, or even simple folding, may be applied to k prior splitting, if k, or k 2 is too long to fit in E or K H, or one wishes k, and k 2 to be dependent on all bits in k.) 2. r K k 2 3. s x/(r xa) mod q if SDSS is used, or s x/(l xa r) mod q if SDSS2 is used instead.

4. c Ek(m).

Send to Bob the signcrypted text r, s).

The unsigncryption algorithm takes advantage of the property that gX mod p can be recovered from r, s, g and ya by Bob. On receiving r, s) from Alice, Bob unsigncrypts it as follows: Unsigncryption by Bob the Recipient 1. Recover k from r, s, g, p, ya and Xb: k (ya gr)s)xb mod p if SDSS1 is used, or S 20 k= (g ya)s'xb mod p if SDSS2 is used.

2. Split k into ki and k 2 3. m= Dk(c).

4. accept m as a valid message originated from Alice only if K Hk 2 is identical to r.

The format of the signcrypted text of a message m is depicted in Figure 2, while the table below summarises the two signcryption schemes, denoted by SCSI and SCS2, which are constructed from SDSS1 and SDSS2 respectively.

19- The two signcryption schemes share the same communication overhead (Ihash(-)l IqJ).

Although SCSI involves one less modulo multiplication in signcryption than does SCS2, both have a similar computational cost for unsigncryption.

Signcryption schemes Signcrypted text r, s) of a Recovery of message m (by Alice) k gS*xb mod p (by Bob) SCSI c= Ekl(m) (from SDSSI) r K H k2(m) k= (ya x g)s*xb mod p s x/(r Xa) mod q SCS2 c Ekl(m) (from SDSS2) r= K H k 2 k= (g x ya )s mod p s xa x r) mod q On Alice's side, x is a number chosen independently at random from k is obtained by k y' mod p, k, and k 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 Xb, r, s, g and and decipher c by m Dkl(c). He accepts m as a valid message from Alice only if r can be re- 10 constructed from KHk 2 A significant advantage of signcryption over signature-then-encryption lies in the dramatic reduction of computational cost and communication overhead which can be symbolized 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.

20 Various schemes Computational cost Communication overhead (in bits) signature-then-encryption EXP=2, HASH ENC=1 In.l Inbi based on RSA [EXP=2, HASH=l1, DEC= 11 signature-then-encryption EXP=3, M4ULI DIV= I 21j p based on DSS ElGamal ADD=], HASH=1, ENC=I encryption [EXP=3, MUL=1, DIV=2 ADD=O, HASH= 1, DEC=lI] signature-then-encryption EXP=3, MIJL=1, DIV=O I I q I+ I p1 based on Schnorr signature ADD=I, HASH=1, ENC=I ElGamal encryption [EXP=3, MIJL=1, DIV=O ADD=O, HASH=1, DEC=1] signcryption SCSI EXP=1, MUL=O, D1V=1 IKH.(Q)l Iqi ADD=1, HASH=l, ENC=1 [EXP=2, MUL=2, DIV=0 ADD=O, HASH=1, DEC=1] signcryption SCS2 EXP1I, MIJL=l, DLVlI IKHQ()I lql A.DD=1, HASH=l, ENC=1 [EXP=2, MUL=2, DIV=O ADD=0, HASH=I, DEC=l] a

S

S.

where EXP the number of modulo exponentiations, =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, -21r c r u r rr r r DEC the number of decryptions using a private key cipher, Parameters in the brackets indicate the number of operations involved in "decryption-thenverification" 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 computational saving in communications |pI, Iql, 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% r -22- 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, ya, Yb, 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 Xb or k.

Since Xb 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: spiting k into ki and k 2 and checking whether r Kk 2 However, this still does not allow the judge to check whether k satisfies the condition k u" mod p, where u (ya' gr)s mod p for SCSI, and u (g yr)' 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

X

b mod p, where Xb is Bob's secret key satisfying the condition yb gb mod p, and u (ya g) mod p for SCSI, and u (g ya) :mod p for SCS2. On the other hand, although Bob should be willing to answer the judge's request for proving k u mod p, he may not wish to leak to the judge any information on his secret key Xb. 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, ya, Yb, m, r, s, and k. Upon receiving the numbers, the judge calculates u (ya, gr) g mod p if SCS 1 is used, or u (g yi)r gX mod p if SCS2 -23 is used instead. Bob wishes to convince the judge that k u* x mod p, where Xb is Bob's secret key satisfying yb g mod p.

Note that in practice, certificates associated with Ya and Yb 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 this protocol is successfully completed.

Convincing the Judge 1. Bob J= u' gi2 mod p Judge The judge picks two random numbers ji and j 2 from calculates J u 1 g 2 mod p, and sends the result J to Bob.

15 2. Bob B J g" mod p, B 2 B mod p Judge Upon receiving J from the judge, Bob picks a random number w from calculates Bi J g" mod p and B 2 B r mod p, and sends the two resulting numbers to the judge.

S3. Bob ji, j 2 Judge 20 Upon receiving B 1 and B 2 the judge sends jl and j 2 to Bob.

4. Bob w Judge Bob checks whether u i g 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 cheating by the judge is detected, and the protocol is aborted.

If the judge receives w from Bob, she checks whether B 1 can be recovered from J g" mod p, and B 2 recovered from k i y 2 w mod p. The judge is convinced that k mod p only if both J g" mod p BI and k i y 2 mod p B2 hold.

-24- Using this protocol, the following three results can be proven: 1. completeness if k is indeed identical to uxb 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' k k, and cheat the judge into believing that k' uxb mod p is at most l/q, a vanishingly small probability for q 2144 3. zero-knowledge no information on Xb is leaked to the judge.

Once being convinced that k uxb mod p, the judge would split k into k, and k 2 decipher c by m Dkl(c), and check whether r can be re-constructed from KHk 2 r, s) will be 15 ruled as being originated from Alice ifr KHk 2 holds.

The foregoing description relates to the case of a message which is directed to only a single recipient.

20 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 through 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. Figure 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 SCSI is detailed below, referred to as SCS1M. The output format of the multiple recipient signcryption is shown in Figure 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, R1, Alice's secret key x, Ri's public key y; for all 1 i e, q and p.

.o 1. Pick a random message-encryption key k, calculate h= KHk(m), and encrypt m by c= Ek(m Ih), where denotes concatenation.

2. Create a signcrypted text of k for each recipient i 1, Q: Pick a random number v i from q] and calculate ti y'i mod p. Then split ti into t,i and t2 of appropriate length. (One-way hashing or folding may be applied to k prior splitting.) di= Eti,(k).

r i KHt i(mh).

si v/(ri x) mod p.

Alice then broadcasts to all the recipients di, rl, s, dQ, r 0 sp).

-26- Unsigncryption by Each Recipient An input to this unsigncryption algorithm consists of a signcrypted text di, rl, sl, do, rg, so) received through a broadcast channel, together with a recipient Ri's secret key xi where 1 i Q, Alice's public key, ya, g, q and p.

1. Find out di, ri, si) in dl, r 1 do, rp, so).

2. ti (Ya gi)sixi mod p. Split ti into and ti2 3. k Dti,(d).

4. w Dk(c). Split w into m and h.

check if h can be recovered from KHk(m) and r i recovered from KHt 2 Ri accepts m as a valid message originated from Alice only if both h KHI(m) and r i

KH,

2 15 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 20 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 techniques: a message m is encrypted together with the hashed value h KHk(m), namely c Ek(m Ih); m and k are both involved in the formation of r i and si through r i KHi,2(m, These two techniques 25 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.

-27- 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 cricuit 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 Ipl. 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 users.

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 herein 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 context 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.

Claims (23)

1. A method for authenticatable encryption of a digital message m for transmission from a sender having a public key y, and a secret key x. to a receiver having a public key Yb and a secret key xb, comprising: determining a message key k using the receiver public key and a randomly selected number x; calculating a first message parameter r, comprising a message authentication code, from said digital message m and a first portion of said message key k; calculating a second message parameter s from the sender private key, the randomly selected number x and the first message parameter r, such that said message key k is recoverable by the receiver from an arithmetic operation of said first and second message parameters, the sender public key and the receiver private key; and encrypting said digital message m using a second portion of said message key k to obtain 15 ciphertextc. *e.

2. A method for transmission of a digital message m from a sender to a receiver, comprising encrypting the digital message according to the authenticatable encryption method defined in Claim 1, and transmitting the obtained cipher text c from said sender to said receiver together S: 20 with the first and second message parameters.

3. A method for recovering a digital message m transmitted according to the method defined in Claim 2, comprising receiving at said receiver the transmitted cipher text c and first and second message parameters, recovering the message key k from said first and second message parameters with said sender public key and said receiver private key, and decrypting the cipher text c using the second portion of the recovered message key to obtain said digital message m.

4. A method for validating a digital message m recovered according to the method defined in Claim 3, comprising calculating the first message parameter using the recovered digital message and the first portion of the recovered message key and making a comparison with the first message parameter received with the cipher text.

P:\OPERVCM\MONAS-iCLM 17/10/97 -29- A method for authenticatable encryption according to Claim 1, wherein the message key k is according to k yx mod p, where p is a large prime.

6. A method for authenticatable encryption according to Claim 1, wherein a one-way hashing or folding function is applied to the message key k before splitting the message key into first and second portions, in order to obtain first and second message key portions which are of suitable length for calculating said first message parameter and encrypting said digital message, respectively.

7. A method for authenticatable encryption according to Claim 1, wherein the first message parameter comprises a keyed hash of the digital message using the first portion of the message key.

8. A method for authenticatable encryption according to Claim 1, wherein the second 15 message parameter is calculated according to a modified ElGamal signature scheme in which the .*o hashed digital message value is replaced by the value 1 or the first message parameter.

9. A method for authenticatable encryption according to Claim 1, wherein the second message parameter is calculated according to a modified Schnorr signature scheme.

A method for authenticatable encryption according to Claim 1, wherein the second message parameter is calculated according to a modification of the Digital Signature Standard.

11. A method for authenticatable encryption according to Claim 1, wherein the step of 25 encrypting the digital message m is performed utilising the Digital Encryption Standard (DES).

12. A method of preparing a digital message m for secure and authenticatable communication from a sender having a public key y, and a private key x, to a receiver having a public key yb and a private key xb, comprising: determining a message key k based on the receiver public key y, and a randomly selected number x; splitting the message key k into first and second keys k, and k 2 p:\OPER\JCM\MONASH.CLM 17/10/97 calculating a first message parameter r as a keyed hash of said digital message using said first key k,; calculating a second message parameter s on the basis of said randomly selected number x, said sender secret key x, and said first message parameter r; encrypting said digital message using said second key k 2 to obtain cipher data c; and appending said cipher data c with said first and second message parameters for transmission to said receiver.

13. In a system for transmission of digital messages between a sender having a public key y, and a secret key Xa and a receiver having a public key Yb and a secret key and having public parameters p being a prime number, q being a prime factor of and g being an integer in the range 1 to with order modulo p, a method for authenticatable encryption of a digital message m, comprising the steps of: selecting a random number x in the range 1 to such that x does not divide 15 determining a message key; •splitting the message key k into first and second keys k, and k 2 calculating a first message parameter r as a keyed hash of said digital message m using said first key k,; calculating a second message parameter s on the basis of modular arithmetic to base q 20 utilising said random number x, said sender private key xa and said first message parameter r; encrypting said digital message m using said second key k 2 to obtain cipher data c; and appending said cipher data c with said first and second message parameters r and s for transmission to said receiver. 25

14. A method for secure and authenticatable communication of a digital message m from a sender having a public key y, and a private key x, to a receiver having a public key Yb and a private key xb, comprising: determining a message key k based on the receiver public key Yb and a randomly selected number x; splitting the message key k into first and second keys k, and k 2 calculating a first message parameter r as a keyed hash of said digital message using said first key k,; P: \OPER\CM\MONASH.CLM 17/10/97 -31 calculating a second message parameter s on the basis of said randomly selected number x, said sender secret key x, and said first message parameter r; encrypting said digital message using said second key k 2 to obtain cipher data c; transmitting the cipher data c and the first and second message parameters r and s to said receiver; recovering said message key from an operation using said first and second message parameters r and s, said sender public key y, and said receiver private key Xb; recovering said first and second keys k, and k 2 from said message key k; decrypting said cipher data c using the second key k 2 to recover said digital message m; and validating said digital message using said first key k, and said first message parameter r.

An apparatus for preparing a digital message m for secure and authenticatable communication from a sender having a public key y, and a private key x, to a receiver having a 15 public key yb and a private key xb, comprising: means for determining a message key k based on the receiver public key yb and a randomly selected number x; means for splitting the message key k into first and second keys k, and k 2 means for calculating a first message parameter r as a keyed hash of said digital message 20 using said first key k,; means for calculating a second message parameter s on the basis of said randomly selected number x, said sender secret key x, and said first message parameter r; means for encrypting said digital message using said second key k 2 to obtain cipher data c; and 25 means for appending said cipher data c with said first and second message parameters for transmission to said receiver.

16. A smart card containing apparatus as defined in Claim 14 for preparing a digital message for secure and authenticated communication from a sender to a receiver.

17. A smart card containing digital processing means programmed or physically arranged to carry out the method defined in claim 1. P:\OPERVCM\MONASH.CLM 7/10/97 -32-

18. A method for authenticated encryption of a digital message m for transmission from a sender having a public key y, and a secret key x, to a plurality of L receivers each having a public key yi and a secret key x i 1 i L, comprising: selecting a random message-encryption key k; determining a keyed-hash value h for the digital message m using the message-encryption key k; encrypting the digital message m concatenated with the keyed-hash value h according to an encryption algorithm using the message-encryption key k, to obtain a cipher c; and for each receiver: selecting a random number vi and determining a transmission key ti using the random number vi and corresponding receiver public key yi; spitting the transmission key ti into first and second transmission keys til and ti 2 encrypting the message-encryption key k using the first transmission key ti, to obtain an encrypted key di; 15 calculating a keyed-hash value ri of the digital message m together with the .o keyed hash value h, using the second transmission key ti2; and calculating a message parameter s, using the random number vi, the keyed-hash value r i and the sender secret key x,. 20

19. A method for secure and authenticatable broadcast transmission of a digital message m to a plurality of receivers, comprising authenticated encryption of the digital message according to the method as defined in Claim 18, and transmitting to all receivers the cipher c together with each of the encrypted keys di, the keyed hash values r i and the message parameters si.

A method for recovering and authenticating a digital message received at a particular receiver from a broadcast transmission according to the method defined in Claim 19, comprising the steps of: selecting the cipher c and the encrypted key di, the keyed-hash value ri and the message parameter s, corresponding to the particular receiver from the received broadcast transmission; calculating the transmission key ti using the sender public key y, the keyed hash value P:\OPER\JCM\MONASH.CLM 21110197 -33 ri, the message parameter si and the particular receiver secret key x, and splitting the transmission key ti into first and second transmission keys til and ti 2 recovering the message-encryption key k by decrypting the encrypted key di according to a decrypting algorithm using the first transmission key til; recovering the digital message m and keyed-hash value h by decrypting the cipher c using the recovered message-encryption key k; and authenticating the recovered digital message m by comparing the recovered keyed-hash value h with a keyed-hash of the recovered digital message m using the recovered message- encryption key k, and the received keyed-hash value r, with a keyed-hash of the decrypted cipher c.

21. A method authenticatable encryption of a digital message substantially as hereinbefore described with reference to the accompanying drawings. .5 15

22. A method of secure and authentication communication substantially as hereinbefore described with reference to the accompanying drawings.

23. Apparatus for preparing a digital message for communication substantially as hereinbefore described with reference to the accompanying drawings. Dated this 21st day of October MONASH UNIVERSITY 25 By its Patent Attorneys DAVIES COLLISON CAVE