Encryption for Multiple Recipients

The sender's computer will generate a random 160 bit key, which it uses to symmetrically encrypt the message using RC4.  Call this key m, the message key.  This key will become known to all the recipients.  This key is of course only used once, for this message, and is then thrown away.

For each recipient, it will generate a random 240 bit number, uniformly distributed in the range between 1 and the order of G.  This secret number is known only to the sender, and will be immediately thrown away.  Call this secret number r.  It is different for each recipient

The sender generates a shared secret elliptic curve point, by multiplying the recipients public key by that number.  This secret will become known to the intended recipient, but not to any other recipients.

Call this shared secret elliptic point R

Call the recipients public key B

The sender calculates the shared secrete elliptic curve point r*B.

The sender then takes the SHA hash of that shared secret elliptic curve point, to obtain a random 160 bit number. This random number will become known to the recipient.  Any recipient will be able to discover this value, but only the particular recipient for whom it is intended will be interested in discovering it.

Call this number p

p =Hash(r*B)

The sender's computer then calcates the exclusive-or of that number, with the shared secret key m.

It then prefixes the message with the recipients public key, the elliptic point constructed by multiplying the generator by r, and the exclusive-or of the hash of the shared secret and mm^p

For each recipient, the message is prefixed with
       B
       r*G
       m^p

Each recipient, or rather his computer, then calculates his shared secret elliptic curve point by multiplying (r*G) by
his secret key b.

Remember the recipients public key B = b*G

Thus by associativity b*(r*G) = r*B

He then hashes the resulting elliptic point, to discover p, and then can discover m by
m = (m^p)^p

He now has the same secret as all the recipients, which he then uses to decrypt the message using RC4.
 

A document encrypted to multiple recipients will look something like this:
    --ManyKeys
9Xjp1N+QDtXR9Mw1S0gJTnwliGM3rQpuzdogeqOLqii
aV23RlHXoLkd5slji39nXSp7dhBg4jkxpI3JVnGJeq
CkcGZ1ME8F1XB8lnA6hM1N8aRYk 

F9KBGIfyizpoyo8i8NS/Dqe/eP4WVNcXcRJuS14QPXn
6qYWJQJyziwMCPnL3GGPsb5N+JQ0HRYDNDmhJqVizIH 
3W165eyH3wYrd7SPKgRIRH5JaKY 

8hka+J2LaM6chAuRTWz+jXw6JXv2WR1jGi/CuuZr41X
85PCQXHXhKNN9Ftcq+t3Vh/gMifcgg7wudJObXT9ffC 
TR9EHgQtqIZ32Slg/OMWblsg3c 

    --Cryptotext
W3Vpd9EF4/3F60/6QBdsyOTPjNLCfmTthLKAIU3yWN0NMDPW1pulozTeTJTW
P1I4i7VvEDguh/bWhGZwDCyFhXinRl18HgQ4PJ29FzDX4Yhb/798kNzvCbB9
6ICSIcwrch7cNr4O4JOJcYDkxx5rAn9R3UBfH7+G0pHc0GWDpmF8hcbwd/0N
TJJ/6xDD4qYTYqutyKFRdcdMlLKr4QNl7XdnvYKsLWpa8i3wttM7b0pg4Zvw
q/fGShraQXhMWoly8UAHsqECUR6dgj9SzS0dge10/n+dqkszwAi8hn9aHFpn
MSODtBQ17iDmN9HGtc73NKGHUzc5uTNtxWsi 

Each group of three lines following the line "--ManyKeys" corresponds to a single recipient.  The first line in the group is same as the first line in the recipients signature, it is the recipients public key B.  The three lines in each group are the three values:

       B
       r*G
       m^p
 


by jamesd@echeque.com

Back to main CryptoKong page