AU683646B2 - A method and apparatus for generating a digital message authentication code - Google Patents

Description

I

WO 94/21066 PCT/AU94/00101 -1- A METHOD AND APPARATUS FOR GENERATING A DIGITAL MESSAGE AUTHENTICATION CODE This invention relates to a method and apparatus for generating a digital message authentication code.

In digital communication systems, such as broadband integrated systems digital networks (B-ISDN) it is often desirable to prevent the meaning of digital messages transmitted thereon from being intercepted and/or interfered with by an unauthorised person. For this reason, digital messages are often encrypted or enciphered such that a person intercepting the transmitted message is unable to ascertain its meaning. Therefore, at the sending site on the network a plain text message is, under control of an enciphering key, transformed into cipher text which is preferably unintelligible to anyone not having the secret deciphering key. At the legitimate receiving site on the network, the cipher text is, under control of the secret deciphering key, retransformed into the original plain text message. Cryptographic systems which operate in this way are commonly classified into block ciphers and stream ciphers.

Stream ciphers act by dividing the plain text into characters, each of which is enciphered utilising a time varying function whose time dependency is governed by the internal state of the stream cipher. The time varying function is produced by a cipher stream generator, which generates a digital cipher stream in accordance w key data which is kept secret. The cipher stream generator is constructed such that :e cipher stream produced is a pseudo random bit stream which is cyclic, but has a period which is much greater than the length of key data provided. In a stream cipher, after each character is enciphered, the device changes state according to a rule, such that two occurrences of the same character in the plain text message will usually not result in the same cipher text character.

The security or strength of a stream cipher depends on the "randomness" of the generated cipher stream. Assuming an interceptor has knowledge of the plain text III~I~III1 I rr -b~lrl WO 94/21066 PCT/AU94/00101 -2message, full access to the running cipher stream may also be deduced. For the system to be secure, the cipher stream must be unpredictable: regardless of the number of cipher stream digits observed, the subsequent cipher stream digits must not be more easily predictable than by just randomly guessing them. An enciphering system such as this ensures that an unauthorised person is unable to determine the meaning of an intercepted message, but does not address the issue of interference with the message despite its meaning being unknown. For example, a portion of a transmitted message may be intercepted altered or replaced with another message portion even if the interceptor is unable to ascertain the deciphered meaning of the original, altered or replaced message portion.

The immunity of a system to unauthorised and undetected alteration of a transmitted message is referred to as the integrity of the system. Integrity is a factor which is not often considered in relation to stream ciphers. A message authentication code (mac), or integrity check value (icv) determined from the content of the plain text message, may be transmitted with the cipher text to enable the receiver to determine whether the received deciphered plain text corresponds with the plain text originally transmitted, i.e. whether the cipher text has been altered during transmission. The message deciphering and authentication process involves the receiver having access to a cipher stream corresponding to the cipher stream with which the message was enciphered.

Then, upon receiving the message the receiver can decipher it and generate a mac from the deciphered plain text message. A comparison of the received mac and the mac generated by the receiver can then be used as an indication of whether the transmitted mac or message has been altered in transit, since the mac generated by the receiver should be the same as the mac generated at the transmitter. However, in certain cryptographic systems it may be possible for a cryptanalyst to alter both the cipher text message and the enciphered mac in such a way that the change is not apparent to the receiver, even though the cryptanalyst is unable to determine the meaning of the cipher text which has been altered. Therefore, it is also advantageous for cryptographic systems to provide an integrity checking or authentication process which prevents such alterations during transmission from taking place without detection.

I

WO 94/21066 PCT/AU94/00101 -3- A paper entitled "A Fast Cryptographic Checksum Algorithm Based on Stream Ciphers" Lai, R. Reuppel, J. Woollven; AUSCRYPT '92 Abstracts; pp 8-7 to 8-11) describes a cryptographic checksum algorithm for producing a message authentication code with a stream cipher system. The checksum algorithm presented involves demultiplexing the message stream into two subsequences according to the binary state of the cipher stream. The two subsequences are input to respective accumulating feedback shift registers, the outputs of which serve as a pair of message authentication codes. The checksum algorithm is easily implemented, regardless of the cipher stream generator structure. However, the cryptographic checksum algorithm is flawed in so far as the alteration of a single digit in the message stream only requires the alteration of a single digit in the message authentication code to obtain the correct mac value.

Consequently, certain alterations can be made to the message with a high probability of also obtaining the correct message authentication code.

A further integrity checking system is described in International Patent Application No. PCT/AU93/00687 entitled "A method and apparatus for generating a cipher stream".

The algorithms described therein for generating message authentication codes, however, are dependent upon the particular structure of the cipher stream generator. It would be preferable, therefore to provide an integrity checking mechanism for a stream cipher system which is independent from the method used for generating the stream cipher itself.

In accordance with the present invention there is provided a method for generating a message authentication code for a digital message in a telecommunications or computer system comprising: generating a sequence of pseudo random cipher strings; and generating a message authentication code by performing modular arithmetic to a prime modulus including multiplication of the digital message by a first said cipher string and addition of a second said cipher string.

Preferably, the message comprises a sequence of message units which are multiplied by respective powers of said first cipher string in generating the message authentication code.

i: 11- WO 94/21066 PCT/AU94/00101 -4- Preferably, the message comprises a sequence of message blocks each comprising a said sequence of message units, each sequence of message units being multiplied by respective different said first cipher strings and summed with said second cipher string to form the message authentication code.

In accordance with the present invention there is also provided a method for generating a message authentication code in a telecommunications or computmr system for a digital message which comprises a sequence of message blocks each comprising a sequence of message units, including the steps of: generating a sequence of pseudo random cipher strings; generating a non-linear function value for each message block by summing the constituent message units multiplied by respective values derived from said cipher string sequence; and generating the message authentication code by summing the non-linear function values with a said cipher string sequence value to a prime modulus.

Preferably the message units are multiplied by respective powers of a said cipher string sequence value.

In accordance with the present invention there is also provided a method for generating a message authentication code in a telecommunications or computer system for a digital message M which comprises a sequence of message units m i for j=0, 1, r, comprising the steps of: generating a sequence of pseudo random cipher strings z; determining a non-linear function value f according to r f (Mz) L mzr- (mod and x-O generating the message authentication code Q modulus p, where p is prime, according to WO 94121066 PCT/AU94/00101 Q (mod p) In accordance with the present invention there is also provided a method for generating a message authentication code in a telecommunications or computer system for a digital message M which comprises a sequence of message units m i for j=0, r, comprising the steps of: generating a sequence of pseudo random cipher strings z,; determining a non-linear function value f according to r fAM,z) m x (mod and x-C generating the message authentication code Q modulus p, where p is prime, according to Q (mod p) In accordance with the present invention there is also provided a method for generating a message authentication code in a telecommunications or computer system for a digital message M which comprises a sequence of message blocks MN for j=0, s, each message block comprising a sequence of b message units mik for k=O, 1, b-1, comprising the steps of: generating a sequence of cipher strings z 1 zi, z 2 determining a non-linear function value f for each message block according to b-1 A(M z) mj, zx (mod and z-O generating the message authentication code Q modulus p, where p is prime, according to AMz z (mod p).

x-O Preferably the message authentication code effective code size is increased by a it WO 94/21066 PCT/AU94/00101 -6factor of h by generating a modified message authentication code Q' according to: Q' Q(M Z) I I Q(MZ.2,.) I (mod p) where I represents concatenation.

The present invention further provides a method for encoding a digital message comprising generating a sequence of cipher strings, generating a message authentication code acording to a method described above, enciphering the message by combining at least one said cipher string therewith, the at least one cipher string being distinct from the cipher strings utilised for generating the message authentication code, and appending the message authentication code to the enciphered message.

The invention also provides apparatus for generating a message authentication code for a digital message composed of a sequence of message blocks, comprising: a stream cipher for generating a sequence of pseudo-random cipher strings; and computation means for generating a non-linear function value for each message block by combining each message block with at least one said cipher string by way of modular arithmetic to a prime modulus, and generating a message authentication code by stu.rming the non-linear function values together with at least one further said cipher string.

Preferred embodiments of the invention are described in detail hereinafter, by way of example only, with reference to the accompanying drawings, wherein: Figure 1 is a flow chart of a preferred algorithm for generating a message authentication code; and Figure 2 is a block diagram of a system for encoding digital messages for transmission by way of a telecommunications path.

An effective cipher stream generator utilises secret key data to produce an output consisting of a pseudo random bit stream Z. The cipher stream Z is typically used to _i WO 94/21066 PCT/AU94/00101 -7encrypt a stream of message data by logically combining the cipher stream and the message stream. Since the cipher stream is continuously changing, a particular bit sequence repeated in the message stream will be encrypted differently each time, depending on the state of the cipher stream. It is therefore advantageous to exploit the time dependence randomness of the cipher stream not only for encryption of the message, but also to ensure that the integrity of the message is not compromised. Throughout the following description the terms message authenticity and message integrity are used interchangeably to refer to the condition of a digital message reaching its destination unaltered or, ii .red, the alteration being detectable at the destination. In particular, the terms message authentication code (mac) and integrity check value (icv) are used interchangeably throughout the specification to denote a numerical value generated from the numerical value of a message which may be utilised to determine whether the message itself has been altered before reaching its destination. Furthermore, in the following for integers t and u we shall write t[u] to represent the unique positive integer satisfying: t[u] t(mod u) and Ost[u]s(u-l) Consider a stream cipher with output Z (zo, z 1 z2, where each output z is a word of w bits (typically w 16 or 32), such that each z has a value from 0 to 2"-1.

It is assumed that Z is unpredictable in the sense that from any part of the Z stream it should be difficult to predict (either exactly or with high probability) what another part of the Z stream was or will be. The output of the cipher stream may be used to provide message integrity by the construction of an integrity check value (icy) that is generated from the message and appended thereto. A non-linear combination of the message and the stream cipher output is utilised to prevent an attacker from modifying the message and determining the necessary modification to generate a valid icy. Prime power modular arithmetic is also used in generating the icy, which ensures that the values of the icy are uniformly distributed and minimal in number for a given message value. The simplest icy can thus be calculated as follows, for a single message unit m, such as a message word, and a prime modulus p: i WO 94/21066 PCT/AU94/00101 -8icv (m o z o [p] Extending this to generate a single icy for two message units yields: icv ((mooz m z) z 2 [p] The preferred implementation of the integrity check value generation, however, involves generating a single icy for a message which consists of a sequence of message blocks each comprising a sequence of message integer units.

The procedure for generating the icy is as follows: Select a message block length b and prime number p 2'+k (k small). Let a message string M (mo, of integers between 0 and 2'-1 be partitioned into blocks M 0

M

1 M, each containing at most b integers so that: Mo mo, mii M1 mbj, mb(+1)1, j 0, s-1 M, 4 mb, for some t b-1 Use the stream cipher to generate s+2 outputs zi, ziz 2 The icy is calculated as: icV(M, b, p, zp z,,l) (1) where for any message string N (no, and integer x, x (2) (noxr nxrI n 2 X- +nrx) [p] The following example illustrates the procedure for generation of an icy for transmission with a message, such as over a telecommunications network.

Example 1: Let w 32, p 232+15, d 10, b 20. Let the cipher be in state 56 (the i WO 94/21066 PCT/AU94/00101 -9last output produced being z 55 Let M (mo, mls) be a message string of length 109 that requires integrity. M is divided into blocks Mo, M 4 of length 20 where Mi (m2i, M+ 19 i 0, 4, and one block of 9 integers M 5 (m 1 oo, moe). The cipher is used to generate 7 outputs z56, z57, z 8 z62, and the integrity check value is calculated according to and icv(M, 20, 232+15, z5,, z5, ze2) The transmitted message is then Mit, m 1 8, icy.

As mentioned above, the strength of the message integrity or authentication checking system is preferably of the same order as the strength of the accompanying encryption system. In other words, the probability that an attacker is able to alter a message undetected should be comparable to the probability of the attacker successfully deciphering the message. The following Theorem and Corollaries establish a clear link between the strength of the integrity mechanism and the strength of the stream cipher from which it is constructed.

Theorem: Let p 2w+k, and the function f be defined by Let M and M' be any two unequal message strings of length b, and y any fixed integer. Then if x is a uniformly distributed random variable in the range 0 to 2'-1, ProbabiliyU[(M,x)-f(M';) y(mod b 2W Proof: Let M (mo, m-1) and M' m' 1 By expanding (2) m'o)x+(ml m'_)x)(mod p).

Thus AMx) AM'x) y(mod p) if and only if By a standard result of elementary number theory (see, for example, p58 of Ivan Niven WO 94/21066 PCT/AU94/00101 10 (mO m'o)x +(ml 1 m,_l)x y(mod p).

and H.S. Zuckerman, The Theory of Numbers (fourth edition), John Wiley and Sons, 1980) such an equivalence has at most b solutions for x, from which the result follows.

Corollary 1 is an immediate consequence of this theorem.

Corollary 1: Let M and M' be any two unequal message strings, and y any fixed integer. Let the function icv 0 be defined as in and Then if z, zi+2, zi+, are independent and uniformly distributed random variables in the range 0 to 2 W-l, Probability[icv(M, b, p, z. zis) -icv(M', b, p, z, z y(mod 2 Corollary 2 indicates the strength of the integrity mechanism in terms of the likelihood of replacing, in transit, a message and the corresponding icy with a legitimate, but different, message-icy pair.

Corollary 2: Let M and M' be any two unequal message strings, and y, g any fixed integers. Let the function icv 0 be defined as in and Then if zi+, z~i 2 zi+,, are independent and uniformly distributed random variables in the range 0 to 2'-1, Probability [icv(M', b, p, z,+ 1 y(mod p) b I icv(M, b, p, z, g(mod (3) 2W Proof: Expanding the left hand side of the inequality above, Probability[icv(M', b, p, z y(mod p) I icy(M, b, p, z e g(mod p)] However WO 94/21066 PCT/AU94/00101 11 Probability[icv(M, b, z, Z b zi zp ,z ,i) g y(mod p) I icv(M, b, p, z, z,+ 1 E g(mod icy(M, b, p, Zis+)-icy(M', b, p, Zp z,1) S((Mo, z,)+.AM 1 z,)-fAMo, z)+f(MI, z,, 1 z,))(mod p) is independent of while icv(M, b, p, zg, OZi) g (mod p) if and only if za,, zi)-f(MI z)j)(mod p).

Thus the events described in the conditional probability of are independent and so the left hand side of is equal to Probability[icv(M, b, p, z zi .l)-icv(M, b, p, zp z, z,+s+1) (g-y)(mod The result now follows by Corollary 1.

Assume that the stream cipher produces output that are independent and uniformly distributed random variables in the range 0 to 2W-1. It follows from Corollary 2 that if any message and its integrity check value were to be altered in transit (the message being altered in at least one bit position), the new message and integrity check value would register as valid by the receiver with probability at most b/2w. Thus we refer to log 2 as the effective icy size. As an example, with a word size w of 32 bits and a block size b of 20 the resulting effective icy size is approximately 28. Note that the effective icy size indicates the strength of the integrity method used with an idealised stream cipher (with outputs that are uniformly distributed independent random variables). For this to be a meaningful indicator of integrity strength with a practical deterministic stream cipher WO 94/21066 PCT/AU94/00101 12 however, clearly the stream cipher key size must be at least as large as the effective icy size. In this case if there is some way of altering or substituting message-icv pairs that goes undetected with a probability of more than b/2w then this implies some corresponding level of predicability in the stream cipher output.

Figure 1 illustrates a flow chart of the preferred method of generating an integrity check value (icv) or message authentication code (mac). The flow chart 2 begins with an initialisation step 4 in which the icv and indices j and k are initialised such that icy 0, j 0 and k i, where i is the initial state of the stream cipher with output z. In order to determine the icy for a given message according to equations and the flow chart 2 is structured into a dual loop iterative process, wherein steps 6, 8, 12 and 18 are used for the calculation of non linear function y (equation whilst steps 16, and 22 perform the steps necessary for the calculation of the icv according to equation Step 6 acts as an initialisation step for the non linear function value y, such that the first iteration of steps 8 and 12 are effective'to calculate the first term of equation (ie: nox). For each iteration of steps 8 and 12 successive integer values of the message are input from the message stream 10 and values of the stream cipher are input from cipher stream 14 according to the message block counter index k. Following each iteration of step 12 the index j is incremented by one, and a test of the value of index j is applied at step 16 to determine whether or not the last unit of the message has been processed.

Where there remains message units left to process, the procedure continues to step 18 where a test is applied to index j to determine whether or not the end of a message block has been reached. If j+1 is an integer divisor of block size b at step 18, this indicates that the beginning of a new message block has been reached, and the procedure continues to step 20 where the icy is incremented by the value of the non linear function y. The block counter index k is incremented following step 20, and the procedure passes to step 6 where the non linear function y is reset. Where the beginning of a message block has not been reached at step 18 the procedure returns to step 8, so as to perform a further iteration of steps 8, 12 and 16. When the end of the message has been reached, as indicated by the result at step 16, the block counter index k is again incremented and the icy is totalled together with the final stream cipher value zk (step 22). Utilising this method allows the icy to be calculated in a serial manner, which is consistent with the WO 94/21066 PCTAU94/OO101 13 continuous output form of the message stream and cipher stream.

The following describes a modification of the above described integrity system, to enable the effective icy size to be increased by any required factor h. As above, a message string M (mo, is divided into blocks M 0 M, each containing at most b integers. The stream cipher is used to generate h(s+2) outputs z, z, z 1 2, Then the integrity check value icv, is defined as a sequence of h integers between 0 and p calculated according to: icv(M, b, p, zp z z) AM, 1 (Mo, Zi,+2) .AM, z 1 Z2,22) z+ 2 ,1 3 Mo, z_+(h-1+2 z zI~A+2)- 2 where the function f is given by This provides an icy of length hp with an effective icy size of Thus, for example, if b 20, w 32, h 4 then the effective icy size is 4 (32 log 2 20)- 110.7 To provide both integrity and encryption the cipher stream can be used to provide input to the integrity calculation as well as output to be used for message encryption. In order to prevent the integrity mechanism from being undermined by a known plain text attack it is important that cipher stream output that is used in icy calculations by the receiver never be used for message encryption by the sender. Otherwise a known plaintext attack WO 94/21066 PCT/AU94/00101 14 combined with altering the synchronisation of the cipher stream may succeed in making the receiver use cipher data in icy calculations which is known to an attacker. To overcome this problem an integer d b) is chosen such that only those z i for which i is a multiple of d are used in the icy calculation, the remaining z, being used for encryption. This technique is illustrated in the example below.

Example 2: As in Example 1 let w 32, p 2 32 +15, d 10, b 20, M (mo, ms) and the cipher be in state 56. To apply integrity and confidentiality the cipher is used to generate 121 outputs z 5 6 z 7 z 58 z 17 6 and the icy is calculated as, icv(M, 20, 232 +15, z 6 o, z 1 20 where the icy function is defined by and The transmitted message is (mo z (m z 2)[2 2 4 61 )[2 32 (m 1 0 z 1 7 [2 32 icy.

Figure 2 illustrates a simple block diagram of an encryption and integrity system which may be utilised to implement the above described. Message data mn is output from a message source 26, which message data is passed to both an encryption processor and a message authentication code generator 32. A cipher stream generator 28 outputs stream cipher data which also passes to both the encryption processor 30 and mac generator 32. The encryption processor 30 acts to combine the message and cipher stream data so as to encrypt the message for transmission thereof. Meanwhile, the mac generator 32 produces an integrity check value, as described above, utilising the same message data but only one of out every d cipher stream outputs, the other d-1 cipher stream outputs being utilised for encryption by the encryption processor 30. The encrypted message m' and the icv are passed to a transmission source 34 whereat the icv is appended to the encrypted message for transmission on an output 36.

The foregoing detailed description has been put forward merely by way of explanation only, and is not intended to be limiting to the invention, which is defined in the claims appended hereto.

Wo 94/21066 WO 9421066PCT/AV94/00101, zj=

M=

icy t[u] f (N,x) 15

GLOSSARY

pseudo-random cipher stream sequence of cipher strings 7z.; cipher string word of w bits is an integer in the range 1 to digital message (MIn 0 I, Min 2 sequence of integer words in the range 0 to

M

1 y .IMj sequence of message blocks of length such that message length L !r b, where: MI MinM 0

M-

Mj=Mb, inbj+l1... nal- =Mbs, Mn* 1 "Imt*, for t (b-1) integrity check value t(inod u) 2W k (k small) such that p is prime nxr+ nx''l+ n 2 nx[p] nox+ x n 2 x r4) x and itteger word x Z) ONOM, Z f(M 1 zjt 1 1 Ii'] icy b, p,

'N

Claims (20)

1. A method for generating a message authentication code for a digital message in a telecommunications or computer system comprising: generating a sequence of pseudo random cipher strings; and generating a message authentication code by performing modular arithmetic to a prime modulus including multiplication of the digital message by a first said cipher string and addition of a second said cipher string.

2. A method as claimed in claim 1, wherein the message comprises a sequence of message units which are multiplied by respective powers of said first cipher string in generating the message authentication code.

3. A method as claimed in claim 1, wherein the message comprises a sequence of message blocks which are each multiplied by respective different first cipher strings in generating the message authentication code.

4. A method as claimed in claim 2, wherein the message comprises a sequence of message blocks each comprising a said sequence of message units, each sequence of message units being multiplied by respective different said first cipher strings and summed with said second cipher string to form the message authentication code.

A method as claimed in any preceding claim wherein a plurality of message authentication codes are generated for the same message but utilising different cipher strings, and the plurality of message authentication codes combined or concatenated to form a further message authentication code.

6. A method for generating a message authentication code in a telecommunications or computer system for a digital message which comprises a sequence of message blocks each comprising a sequence of message units, including the steps of: generating a sequence of pseudo random cipher strings; generating a non-linear function value for each message block by summing the WO 94/21066 PCT/AU94/00101 17 constituent message units multiplied by respective values derived from said cipher string sequence; and generating the message authentication code by summing the non-linear function values with a said cipher string sequence value to a prime modulus.

7. A method as claimed in claim 6, wherein the message units are multiplied by respective powers of a said cipher string sequence value.

8. A method as claimed in claim 6, wherein in generating each non-linear function value the message units are multiplied by respective powers of a said cipher stream sequence value, a different sequence value being utilised for each non-linear function value.

9. A method as claimed in claim 8, wherein the cipher string sequence value summed with the non-linear function values to generate the message authentication code is a different sequence value from the cipher strings used to generate the non-linear function values.

A method as claimed in any one of claims 6 to 9, wherein the non-linear function values, f, are generated according to: r f(M,z) E mz x (mod p) x0-O where M is a message block comprising r message units m. and z are said cipher string sequence values.

11. A method for generating a message authentication code in a telecommunications or computer system for a digital message M which comprises a sequence of message units mj for j=0, 1, r, comprising the steps of: generating a sequence of pseudo random cipher strings z,; determining a non-linear function value f according to WO 94/21066 PCT/AU94/00101 18 f mz Z (mod and x-O generating the message authentication code Q modulus p, where p is prime, according to Q (f(Mz z. 1 (mod p)

12. A method as claimed in claim 11, wherein the message is composed of a sequence of message blocks Mk which each comprise a said sequence of message units, and wherein the message authentication code Q, modulus p, is generated according to: Q =E f (Mx, z.x) (mod P)

13. A method for generating a message authentication code in a telecommunications or computer system for a digital message M which comprises a sequence of message units mj for j=0, 1, r, comprising the steps of: generating a sequence of pseudo random cipher strings z determining a non-linear function value f according to f(Mz) E mxz (mod and 0-O generating the message authentication code Q modulus p, where p is prime, according to Q (mod p)

14. A method for generating a message authentication code in a telecommunications or computer system for a digital message M which comprises a sequence of message blocks NM for j=0, 1, s, each message block comprising a sequence of b message units mjk for k=0, 1, comprising the steps of: pseudo randorv generating a sequence of cipher strings z, Z 2 WO 94/21066 PCT/AU94/00101 -19 determining a non-linear function value f for each message block according to b-i AM,, z) E m z' (mod and 0-O generating the message authentication code Q modulus p, where p is prime, according to Q(Mzi) (E (AMx., (mod p). 0-O

15. A method as claimed in claim 14, including the step of increasing the effective code size of the message authentication code by a factor of h by generating a modified message authentication code Q' according to: Q' Q(Mz) I Q(IMz, 2 I I (mod p) where I represents concatenation.

16. A method as claimed in any one of claims 1, 6, 11, 13 or 14 wherein the sequence of cipher strings comprises a subset selection of cipher string values from a cipher stream.

17. A method as claimed in claim 16 wherein the remaining cipher string values from the cipher stream are utilised for encrypting the message and/or the message authentication code.

18. A method for encoding a digital message comprising generating a sequence of cipher strings, generating a message authentication code according to any one of claims 1, 6, 11, 13 or 14, enciphering the message by combining at least one said cipher string therewith, the at least one cipher string being distinct from the cipher strings utilised for generating the message authentication code, and appending the message authenticatior code to the enciphered message. i i WO 94/21066 PCT/AU94/001OI 20

19. Apparatus for generating a message authentication code for a digital message composed of a sequence of message blocks, comprising: a stream cipher for generating a sequence of pseudo-random cipher strings; and computation means for generating a non-linear function value for each message block by combining each message block with at least one said cipher string by way of modular arithmetic to a prime modulus, and generating a message authentication code by stunming the non-linear function values together with at least one further said cipher string.

20. Apparatus according to claim 19, including: encryption means for encrypting the message by utilising sequence values of said pseudo-random cipher string sequence which are distinct from the sequence values used to generate the message authentication code; and means for appending the message authentication code to the encrypted message for transmission thereof.