A k -th order Carmichael key scheme for shared encryption
Selwyn Russell · ACM SIGSAC Review · 1997
A generalization of a digital multisignature key scheme published by Desmedt and Frankel is presented, with increased protection from line monitors and with a high degree of privacy of message contents. The Desmedt/Frankel paper at Crypto'91 [1] presented the following shared encryption Carmichael scheme: • An RSA cryptosystem with modulus n and private key K Priv. • Separate individual keys K Privi are generated by some unspecified process with the sole requirement that ΣK Privi ≡ (K Priv - 1) mod λ(n), where λ(.) is the Carmichael function. • Individual signatures ("partial results") of a message m are calculated as si ≡ mK Privi mod n. • A "Combiner" produces the final signature S from the partial results and the plain text message as S ≡ m IIsi mod n. The combiner is specified as "not necessarily trusted". Desmedt/Frankel specify that the message m is being signed, not a message digest value derived from the message. The limitation is apparently imposed to meet the requirement that it must be impossible for the combiner to substitute a different message for a given set of partial results. This requirement is met if the plain text message rather a message digest is used in the calculations. This requirement is practical only when the length of the message is less than the length of the RSA modulus. Many users would probably prefer to use the message digest rather than the message as the basis for the signature, for example as specified in the RSA Public Key Cryptographic Standards (PKCS) [2] and Internet Privacy Enhanced Mail [4]. Using the PKCS minimum modulus size of 328 bits and PKCS padding of a minimum of 11 octets limits the message size to 30 bytes. A wire tapper who intercepts the partial results sent to the Combiner will not be able to forge a signature without knowing the original message. The power of this feature depends entirely on the secrecy applied to the message inside the enterprise. If the wire tapper is able to intercept the partial values sent to the Combiner, the wire tapper will presumably be able to intercept the original message sent to the Combiner. The wire tapper will then have sufficient information to produce a signature. Forgery is more likely in the more practical case where a message digest is signed rather than a short message. If a message digest were used, it is possible (but computationally difficult) to substitute a different message which has the same message digest as the original [3], and therefore obtain a verifiable signature for a fraudulent message. For the Desmedt/Frankel system to be secure, the message must be limited to those with high security clearances. Most enterprises limit access to sensitive plain text information on a "need to know" basis. The Combiner in the Desmedt/Frankel scheme does not need to know the contents of the plain text messages to combine the partial values. Moreover, the ("not necessarily trusted") Combiner is not provided with any confidential exponent, but certainly does have access to the plain text message. Thus, the combiner may be considered as not sufficiently trustworthy to be provided with an exponent, but nevertheless does have access to the plain text document. Management may regard this as a security anomaly and wish the document to be unreadable by the Combiner. To meet this requirement, we extend the Desmedt/Frankel key scheme into what we can name a k-th order Carmichael key scheme for RSA: • An RSA cryptosystem with modulus n and private key K Priv. • Individual keys K Privi are generated by some unspecified process with the sole specification that ΣK Privi ≡ (K Priv - k) mod λ(n), where λ(.) is the Carmichael function. • Individual signatures of a message m are calculated as si ≡ mK Privi mod n. • The combiner produces the final signature S as S ≡ mk IIsi mod n. Now the combiner is provided with mk mod n rather than m, and the confidentiality of the document is preserved. Using this terminology, the Desmedt/Frankel scheme is classified as a first order Carmichael key scheme.