Cryptography – Particular algorithmic function encoding – Public key
Reexamination Certificate
1999-12-29
2004-05-04
Sheikh, Ayaz (Department: 2131)
Cryptography
Particular algorithmic function encoding
Public key
C380S277000, C380S278000, C380S282000, C380S283000
Reexamination Certificate
active
06731755
ABSTRACT:
The present invention relates to asymmetric key-code cryptographic communications systems and methods and in particular to systems and methods involving the co-operative generation of public parameters in such a way that co-operative decryption is required.
With the increase in accessibility to microprocessors, for example in the form of programmable computers or dedicated microprocessors, the transfer of information between microprocessors, over a communications channel, has rapidly increased. There are many applications, for example electronic banking, e-mail systems and subscriber information systems, where it is preferable to encrypt any information which will pass over the communications channel in order to prevent its disclosure to unauthorised recipients.
To implement cryptographic functions in a microprocessor controlled communications system symmetrical or asymmetrical algorithms may be used. Functions based on asymmetrical algorithms are particularly useful since a user, for example a first microprocessor, can generate and make universally available a single “public” encryption key to anyone, for example a second microprocessor, wishing to send the user a message. The user can then retain a “private”, different decryption key which is related in some way to the public key. One such asymmetrical algorithm that is used in cryptographic communications systems is the well known RSA algorithm (U.S. Pat. No. 4,405,829).
The parameters for the well known RSA system consist of a public modulus N which is a product of two primes; P, Q, a public encryption key e; and a secret decryption key d. The factorisation of N is a secret parameter and the keys are related by a formula of the form de=1 mod &phgr;(N), where &phgr;(N) is the order of the multiplicative group of integers modulo N. Then with knowledge of only the public parameters, any message (so called “plaintext” message), x (represented as a positive integer less than N), can be enciphered using a formula of the formy y=x
e
mod N. The secret parameter d is needed to decipher the encrypted message (so called “ciphertext” message), y, via a formula of the form x=y
d
mod N.
Thus, in the known asymmetrical cryptographic systems the user is in possession of the only decryption key and can act autonomously to decrypt any message. This may be a problem, for example in circumstances where a central authority regulates, generates and issues public and private keys then this central authority has the capability to masquerade as any user-microprocessor and decrypt private messages.
A cryptographic method involving a split-key decryption scheme is described by Boneh and Franklin (Efficient Generation of Shared RSA Keys, to be presented at CRYPTO '97, University of California Aug. 17-21, 1997, published by Springer Verlag and currently available at the web site location http://www.cs.princeton.edu/~dabo/publications.html—Lecture Notes in Computer Science vol 1294). However this describes a scheme involving three entities in generating the split-key, any two of which can co-operate to decrypt a message without recourse to the third.
It is the object of the present invention to provide a cryptographic communications system and a cryptographic method for use in such a system that requires the co-operative effort of only two entities but which can be expanded for application by a plurality of entities all of whom must co-operate. The entities will co-operate in a manner according to the claimed invention to generate the public parameter N in such a way that no individual entity knows the factorisation of N, and such that they can each have a share d
1
, d
2
, . . . d
n
respectively of the secret decryption key d where d=(d
1
+d
2
+ . . . d
n
)+c, where c lies between 0 and n−1. Hence no entity will individually possess the ability to recover the plaintext message x from a ciphertext message y. Instead, all the entities must co-operate in a manner according to the claimed invention in order to decrypt the message or to generate verification data for a further entity as part of an identification and signature scheme.
This object is achieved by using the method having the features of independent claim 1 and also by using the system having the features of claim 5. In using this method and system two or more entities, having microprocessors A, B, . . . n must co-operate to generate the RSA public parameter N. Once N is determined in this way the entities can then co-operate to generate and use decryption keys to produce a decrypted output in ways dependent on the application of the communications system.
Further useful embodiments of the invention are provided for in the sub-claims.
Usefully, claim 3 provides a method of generating a high security public modulus N provided that the level of confidence that P and Q are prime is set to a sufficiently high level using primality testing algorithms well known in the art.
Particularly, claim
4
provides a method of operating a cryptographic communications system in which the entities 1, 2 . . . n must co-operate to decrypt a ciphertext message which was encrypted using the RSA type algorithm.
REFERENCES:
patent: 5588061 (1996-12-01), Ganesan et al.
Cocks, “Split knowledge generation of RSA parameters”,Cryptography and Coding. 6thIMA International Conference. Proceedings, Proceedings of Cryptography, Cirencester, UK,Dec. 17-19, 1997, pp. 89-95.
Nixon & Vanderhye P.C.
Sheikh Ayaz
The Director, Government Communications Headquarters
Vaughan Michael
LandOfFree
Split-key cryptographic system and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Split-key cryptographic system and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Split-key cryptographic system and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3249883