Initial secret key establishment including facilities for verification of identity

Abstract

An issuer offers any type of service secured with a secret cryptographic key assigned to an applicant according to the present invention, which includes a secret key registration process. Usually, the secret key will be loaded on a portable memory device or other secret key store of the applicant. As preliminary steps, the issuer sets up its public key for the Probabilistic Encryption Key Exchange (PEKE) cryptosystem, and the applicant obtains a copy of a secret key registration software, a copy of the issuer's public key, and an uninitialized portable memory device. Once initiated by the applicant, the registration software generates an internal PEKE secret key. The applicant chooses a registration pass query and pass reply that the registration software MACs and encrypts with a key derived from the PEKE secret key. The registration software derives the key assigned to the applicant from the PEKE secret key, and loads it into the secret key store. A message is sent to the issuer data processing center where the cryptographic processing (PEKE, MAC, encryption) is reversed. Using an alternate channel (e.g. telephone conversation) an issuer agent verifies the identity of the applicano: the agent asks the pass query, the applicant replies with the pass reply, and the issuer verifies the applicant's knowledge of some relevant personal data. The issuer agent can approve the applicant's registration in the issuer database. There is no need for the issuer to personalize either the software or the secret key store before delivery to the applicant, and there is a single personal contact between the applicant and the issuer agent.

Claims

I claim:

1. A method of establishing a secret cryptographic key shared between an applicant and an issuer comprising the steps of:

providing said applicant with a registration computer program means, said registration computer program means having a public key of said issuer and public key encryption capability;

generating said secret key using at least some random information at an applicant end;

generating a pass reply message using at least some arbitrary information at said applicant end;

encrypting said secret key and said pass reply using said public key to form at least one encryption message, said message including information allowing said issuer to identify said applicant;

sending said encryption message to said issuer by telecommunications means;

decrypting said encryption message at an issuer end to retrieve said secret key and said pass reply using a private key of said issuer;

receiving a second communication from said applicant at said issuer end separate from said encryption message over a channel that enables said issuer to ascertain said second communication to be genuinely from said applicant, said second communication containing said pass reply;

confirming a validity of said secret key at least with said issuer if said pass reply received during said second communication matches said pass reply decrypted, whereby said secret key may be confirmed for use in future transactions.

2. The method according to claim 1, wherein said step of confirming comprises displaying said pass reply decrypted to an agent at said issuer end.

3. The method according to claim 1, wherein said step of receiving a communication from said applicant comprises establishing telephonic communication with an agent at said issuer end and said applicant.

4. The method according to claim 3, further comprising a step of generating a pass query, wherein said step of encrypting comprises encrypting said pass query, said step of decrypting comprises decrypting said pass query, and further comprising a step of communicating said pass query to said applicant from said issuer end prior to receiving said pass reply in said communication, whereby said applicant is reassured that said issuer is genuine as a result of hearing said pass query, and feels safe to proceed with giving said pass reply.

5. The method according to claim 4, wherein said step of communicating comprises displaying said pass query decrypted to said agent.

6. The method according to claim 3, wherein said agent is provided with some personal indentification information about said applicant, said step of confirming further comprising said agent asking a personal identification question to said applicant and listening for a correct response.

7. The method according to claim 5, wherein said agent is provided with some personal indentification information about said applicant, said step of confirming further comprising said agent asking a personal identification question to said applicant and listening for a correct response.

8. The method according to claim 1, wherein said pass reply is input by said applicant.

9. The method according to claim 1, wherein said pass reply is displayed to said applicant.

10. The method according to claim 1, further comprising a step of selecting a personal identification number (PIN) for said applicant, wherein said step of encrypting further comprises encrypting said PIN, said step of decrypting further comprises decrypting said PIN, said PIN being stored at said issuer end for use in verification of future transactions.

11. The method according to claim 1, wherein said applicant possesses a smart card device and uses a smart card device interface connected to said program means, said secret key being loaded into said smart card device.

12. A method of applying for approval of a secret cryptographic key to be shared between an applicant and an issuer comprising the steps of:

obtaining a registration computer program means, said registration computer program means having a public key of said issuer and public key encryption capability;

generating said secret key using at least some random information;

generating a pass reply message using at least some arbitrary information;

encrypting said secret key and said pass reply using said public key to form at least one encryption message, said message including information allowing said issuer to identify said applicant;

sending said encryption message to said issuer by telecommunications means;

communicating said pass reply to said issuer end separately from said encryption message over a channel that enables said issuer to ascertain said pass reply to be genuinely from said applicant, said communication containing said pass reply.

13. The method according to claim 12, wherein said applicant possesses a smart card device and uses a smart card device interface connected to said program means, said secret key being loaded into said smart card device.

14. A method of approving a secret cryptographic key to be shared between an applicant and an issuer comprising the steps of:

receiving at least one encryption message from said applicant by telecommunications means, said message including an encryption of a secret key and a pass reply using public key encryption with a public key of said issuer, said message including information allowing said issuer to identify said applicant;;

decrypting said encryption message to retrieve said secret key and said pass reply using a private key of said issuer;

receiving a second communication from said applicant separate from said encryption message over a channel that enables said issuer to ascertain said second communication to be genuinely from said applicant, said second communication containing said pass reply;

confirming a validity of said secret key at least with said issuer if said pass reply received during said second communication matches said pass reply decrypted, whereby said secret key may be confirmed for use in future transactions.

15. A system for establishing a secret cryptographic key shared between an applicant and an issuer comprising:

applicant registration means having a public key of said issuer and public key encryption capability for generating said secret key using at least some random information at an applicant end, for generating a pass reply message using at least some arbitrary information at said applicant end, and for encrypting said secret key and said pass reply using said public key to form at least one encryption message, said message including information allowing said issuer to identify said applicant;

means for sending said encryption message to said issuer by telecommunications means;

means for decrypting said encryption message at an issuer end to retrieve said secret key and said pass reply using a private key of said issuer;

means for receiving a second communication from said applicant at said issuer end separate from said encryption message over a channel that enables said issuer to ascertain said second communication to be genuinely from said applicant, said second communication containing said pass reply;

means for confirming a validity of said secret key at least with said issuer if said pass reply received during said second communication matches said pass reply decrypted, whereby said secret key may be confirmed for use in future transactions.

Description

FIELD OF THE INVENTION

The present invention generally relates to cryptographic key management that is required for the implementation of secure data communications or transaction processing. More specifically, it addresses the need to establish, or renew (e.g. after security breach), the very first shared secret key between two parties (e.g. a client and a financial institution in an on-line banking service arrangement). This registration process encompasses human activities by the parties' agents for the verification of identity. The present invention facilitates these human activities by a novel and unique arrangement of automated operations, notably cryptographic transformations. The present invention also relates to the secure loading of cryptographic key material in hand held memories in the form of smart cards, security tokens, and the like. Although the present invention uses public key cryptography primitives, it does not assist the establishment of a private/public key pair of the type used for digital signatures or public key encryption. The present invention does not deal with the derivation of a session key or a one-time password from either a preset shared secret key, or a preset secret password.

BACKGROUND OF THE INVENTION

For the deployment of electronic commerce and on-line banking services, information security techniques are of paramount importance. As will be seen from the prior art cited hereafter, they are also important for the protection of computer networks and the authentication of subscribers of mobile telephone service. A general scheme emerges for the organization of such electronic authentication applications, despite the diversified vocabulary used in different application areas. There is first a central database under the operational control of a service organization whose trustworthiness is commensurate with the issues at stake. Then, there are the potential clients, individuals or organizations. The general function of a registration process is to make a given client known by the service organization in such a way that the subsequent routine processing of transactions is automated and efficient. The clients have access to electronic apparatus through which they conduct their ordinary activities. A registration process provides the client with secret authentication information. This secret can be a Personal Identification Number (PIN), a private key for a digital signature algorithm, or a secret cryptographic key shared between the client and the service organization. While a PIN can be remembered by a normal person, the two other forms of authentication secret require a digital memory of some sort. The present invention is mainly concerned with the registration process when a shared secret authentication key is used.

Ultimately, transaction authentication is effective if it secures the legal tie or bind between a bank account withdrawal and the account holder's liability, while barring access to the funds by defrauders. Since the account holder is a legal person rather than a digital apparatus, the required chain of evidence is a two-tiered authentication bind: 1) the logical bind between the account holder (or the account holder agent) and a cryptographic operation performed by a digital apparatus, and 2) the bind between this said cryptographic operation and the transaction historic records of the financial institution. Within its scope of a registration process, the present invention addresses these two aspects of transaction authentication.

The distinction between "secret key cryptography" and "public key cryptography" is well known in the prior art. In the present disclosure, we reserve the term "secret" to data shared in confidence between parties in a secret key cryptography arrangement, and respectively the terms "private" and "public" to the private and public components of a private/public key pair of the type used for digital signatures or public key encryption from the field of public key cryptography.

The elementary cryptographic operation used in transaction authentication can be DES encryption of a secret Personal Identification Number (PIN) entered at a Point of Sale terminal (POS terminal), with cryptographic integrity protection applied to the whole transaction (typically with a Message Authentication Code based on DES and a secret key). In that case, a long-term secret key has to be established initially between the POS terminal and the data processing center responsible for transactions initiated from this POS terminal (normally under the control of the merchant's financial institution). This long-term secret key is of the type that can be established with the present invention. U.S. Pat. No. 4,771,461 discloses a procedure for this secret key establishment.

This prior art of U.S. Pat. No. 4,771,461 suffers from a number of intrinsic limitations. First and foremost, there is the following explicit security weakness (column 16 lines 1 to 6): "The general exposure of the procedure is that an opponent can always initiate a successful sign-on from his location with his terminal, provided that the real terminal never signs on before T2 and does not report this to the KDC [Key Distribution Center]. In that case, the fake terminal can continue to operate indefinitely."

More generally, the procedure of U.S. Pat. No. 4,771,461 appears outdated when one considers the level of sophistication reached by adversaries of actual cryptosystems. See for instance the article by Ross J. Anderson, Liability and Computer Security: Nine Principles (in Computer Security--Esorics '94, Third European Symposium on Research in Computer Security, November 1994, LNCS 875, Springer Verlag, PP 231-245), the article by Martin Abadi, and Roger Needham, Prudent Engineering Practice for Cryptographic Protocols (in 1994 IEEE Symposium on Research in Security and Privacy, IEEE, 1994, PP 122-136), and the article by Ross J. Anderson, and Roger Needham, Robustness Principles for Public Key Protocols (in Advances in Cryptology, CRYPTO'95, LNCS 963, Springer Verlag, 1995, PP 236-247). Nonetheless, U.S. Pat. No. 4,771,461 has the merit of stressing the importance of data integrity protection for the initial establishment of cryptographic keys.

There are also operational limitations in the procedure of U.S. Pat. No. 4,771,461. Despite the acknowledgment that courier services for secret key distribution are expensive and burdensome, it is not clear how courier services can be avoided altogether. They may be required because the POS terminals can be loaded with a terminal identifier and/or a public key at a central location. Courier services or another form of alternate secure channel may also be required for some instructions to a person because these instructions may contain sensitive information specific to each POS terminal. Moreover, the explicit operational delays introduced by this prior art have a negative impact on the value of the procedures.

The U.S. Pat. No. 5,784,463 uses public key cryptography to establish some long term cryptographic keys in a manner analogue to U.S. Pat. No. 4,771,461, but it lacks facilities for verification of identity such as the time windows in U.S. Pat. No. 4,771,461. In other words, the U.S. Pat. No. 5,784,463 embeds no procedural countermeasure against the threat of theft of identity. Without any such countermeasure, a would-be defrauder simply needs the electronic version of identification information needed for registration in order to attempt an impersonation attack.

The U.S. Pat. No. 5,216,715 on lines 14 to 18 on column 5 (and on lines 16 to 23 on column 6) refers to a known procedural protection used for remote user authentication at the outset of a telephone call, just after some session key establishment protocol, that is the verbal confirmation that some check value agree on both ends of the telephone call. The assurance provided by this procedural authentication step is valid for the duration of the telephone call only. For a security system to be as unintrusive as possible, routine operations such as a telephone call setup should use fully automated security mechanisms; procedural steps should be used sparingly, e.g. to the initial registration of legitimate users of the system. Indeed, the procedural step for remote telephone operator identification as in U.S. Pat. No. 5,216,715 is typical of very high security telephone sets. In addition, the procedural verification of identity in U.S. Pat. No. 5,216,715 does not work if the call is established with a voice mailbox.

In the field of wireless subscriber registration, the U.S. Pat. No. 5,077,790 discloses a procedure based on the establishment of a "key code" that is a secret key shared between a portable telephone and the network controller. Upon verification of the applicant's credit, an help desk agent provides a "link identification number" that binds the credit approval to the subsequent download of the definitive "subscriber identification number", this download being cryptographically protected with the initial "keycode". This procedure is inconvenient due to the manual operations involved in the establishment of the "key code" and might be vulnerable to eavesdropping because every security critical information is transmitted over the air and while no public key cryptography is involved.

In many cases, security systems features create more inconvenience to the users than effective protection. This is the case in the U.S. Pat. No. 5,386,468 that discloses an electronic identification registration procedure where the typing of user application information on a communication terminal keyboard is duplicated by filling a user application form and mailing it. This duplicate work is inconvenient because the paper processing actually delays the reply in the query/reply protocol used for registration. One can assume that U.S. Pat. No. 5,386,468 is practiced without the procedural step (paper processing) for which no clear purpose is disclosed. In any event, the key management burden in the manufacturing and distribution of terminals is significantly higher in U.S. Pat. No. 5,386,468 than in U.S. Pat. No. 4,771,461.

The elementary cryptographic operation used in transaction authentication can also be a digital signature from the field of public key cryptography, in which case a representative description of the prior art may be found in the Working Draft ANSI standard X9.30-199x Public Key Cryptography Using Irreversible Algorithms for the Financial Services Industry: Part 3: Certificate Management for DSA (by the Accredited Standards Committee X9-Financial Services, ANSI ASC X9, American Bankers Association, Washington, D.C., Nov. 19, 1994 document N24-94). The present invention alleviates the traditional burden of secret key distribution, and thus suggests the avoidance of the public key infrastructure described in the mentioned Working Draft ANSI standard X9.30-199x. Indeed, the financial industry has been operating on a centralized trust model for decades, and the adoption of public key paradigms may be expected to remain low.

Turning now to the logical bind between the account holder (or the account holder agent) and a cryptographic operation performed by a digital apparatus, one way to let the account holder control the use of a cryptographic key is to store it on a hand held memory device in credit card format, or in a format suitable for attachment on a key ring, or any other small size format. Thus, the account holder is relieved from the obligation to control the access to a fixed apparatus like a computer system, or a luggage-size apparatus like a portable personal computer. When the hand-held memory device contains intrinsic data access control features, it falls into the smart card category. This usually requires a rudimentary microprocessor along with the memory device. With further sophistication, a hand held electronic device may embed sufficient processing power and/or memory to be perform complete cryptographic operations. In the latter case, the security is enhanced by avoiding the threat of malignant software modifications. The present invention facilitates the establishment of the secret key to be loaded on hand held devices where the prior art required the use of centralized key loading facilities, and/or secure transmission of secret keys using trusted courier services. The present invention may allow the avoidance of centralized smart card personalization operation.

The centralized trust model typical of the financial industry is assumed by the United States regulatory environment for consumer protection in the case of electronic fund transfers. The field of the present invention is more specifically covered by EFTA, Electronic Fund Transfer Act, Title IX of the Customer Credit Protection Act, (15 U.S.C. .sctn.1601 et seq.) and Regulation E. Electronic Fund Transfers, (12 C.F.R. .sctn.205) Section 205.5 which deals with the issuance of access devices used for customer-initiated EFT. In some circumstances and according to these rules, a secret key (established with the help of cryptographic protocols) may fall under the legal definition of an access device. In such a case, a verification of the customer identity is prescribed as a condition for the final validation of the secret key for EFT transactions. An object of the present invention is to facilitate the issuance (of access devices) complying with the EFTA Regulation E or similar rules.

A difficulty with key management methods that require centralized configuration or personalization is the implied restrictions on the channels of distribution. For consumer electronics, computer products, and software devoid of security functions, a myriad of channels are possible: catalog sales, retail stores, large discounters, and the like, the list being endless. If an item (like an access device for an EFT service) has to be prepared for a specific customer by trusted personnel according to procedures dictated by a financial institution, the possible channels of distribution are very few, if any, besides courier shipment by the financial institution. U.S. Pat. No. 5,557,679 is an attempt to use retail outlets for the distribution of subscriber identity modules (portable memories used for mobile telephone subscriber authentication). The present invention broadens the choices of acceptable channels of distribution for authentication devices.

In U.S. Pat. No. 5,557,679, secret keys are pre-established to secure a network of retail locations where the key loading operation is performed. There is no capability for the fully distributed scenario where the target electronic devices are remotely located from any (already) secured system. Secret key schemes that avoid the use of courier services in a fully distributed scenario are conceivable if the target electronic devices are already loaded with a common, fixed key "hidden by being included in the [device] programmable read only memory (PROM) at manufacturing level", as in U.S. Pat. No. 5,539,824. Such a scheme is generally considered not so secure, except perhaps when offered by a very reputable supplier.

The famous Diffie-Hellman cryptosystem described in U.S. Pat. 4,200,770, and the recent similar proposals found in U.S. Pat. Nos. 5,583,939 and 5,375,169 do not provide remote party authentication and secret key freshness simultaneously. Indeed the "public key" of a Diffie-Hellman exchange is usually considered a short-lived cryptographic value, and the authentication potential of the Diffie-Hellman exchange is not used. For instance, U.S. Pat. No. 5,020,105 applies Diffie-Hellman to the task of establishing a secret authentication key, but does not provide facilities for verification of account holder identity. Moreover, the processing load implied by the original Diffie-Hellman cryptosystem is large, while the security of U.S. Pat. Nos. 5,583,939 and 5,375,169 is questionable or uncertain. The recent article by Lein Ham, Digital signature for Diffie-Hellman keys without using a one-way function (in Electronics Letters, Jan. 16, 1997, Vol. 33, No. 2, pp. 25-126) discloses a noteworthy attempt at enhancing the Diffie-Hellman scheme with authentication properties.

It is logical that the disclosure in U.S. Pat. No. 4,771,461 stresses the need for data integrity in the key loading operation, and at the same time uses a public key cryptosystem, RSA, with a long-term public key assigned to the financial institution. This public key participates in the authentication of the financial institution to the benefit of the client-side of the secret key establishment. The security of this prior art depends on the unpredictability of the random number source on the client-side. The use of random sources for cryptographic key material has been recognized as a potential source of security flaws.

Any scheme where the client-side of the session key establishment already has a long term public key is likely to address a need different from the present invention, based on the premises of public key cryptography. U.S. Pat. No. 5,406,628 may be a good example.

Last, but not least, is the disclosure by the present Applicant, of the Probabilistic Encryption Key Exchange (PEKE) cryptosystem in Canadian patent application 2,156,780 (entitled Apparatus and Method for Cryptographic System Users to Obtain a Jointly Determined, Secret, Shared, and Unique Bit String, filed on Aug. 23, 1995, laid-open to the public on Sep. 23, 1995), in an article by Thierry Moreau, Probabilistic Encryption Key Exchange (in Electronics Letters, Vol. 31, number 25, Dec. 17, 1995, pp 2166-2168), and in a technical report by Thierry Moreau, Automated Data Protection for Telecommunications, Electronic Transactions and Messaging using PEKE Secret Key Exchange and Other Cryptographic Algorithms, Technology Licensing Opportunity (revision 1.1, CONNOTECH Experts-Conseils Inc., Montreal, Canada, March 1996, with legal deposits in the National Library of Canada, where it was not available to the public before April 1997, and in the National Library of Quebec, where it was made available to the public some time between November 1996 and January 1997). The PEKE cryptosystem is based on the Blum-Goldwasser probabilistic encryption scheme explained in an article by Manuel Blum and Shafi Goldwasser, An Efficient Probabilistic Public-key Encryption Scheme which Hides All Partial Information (in Advances in Cryptology: Proceedings of Crypto'84, Springer-Verlag, 1985, pp 289-299). The PEKE cryptosystem has been disclosed so far for session key establishment with no facilities for the verification of identity. Indeed, transaction authentication using PEKE is suggested in the mentioned technical report by Thierry Moreau, but using a preset shared secret password as the basis for authentication, and PEKE for session key establishment. For the present invention, the PEKE cryptosystem is one of three alternate cryptosystems, the other two being conventional public key encryption (e.g. RSA, in U.S. Pat. No. 4,405,829), and the Lein Harn's improvement to the Diffie-Hellman key exchange in the mentioned article by Lein Harn.

The commonly used public key cryptosystems use arithmetic operations on large integers and especially the modulus (the remainder of an integer division). To make these computations relatively efficient, the use of the Montgomery modulo reduction algorithm is relatively known in the prior art, see the original article by Peter L. Montgomery, Modular Multiplication Without Trial Division (in Mathemetics of computations, Vol. 44, no. 170, April 1985, pp 519-522). Two implementations are disclosed in the article by Stephen R. Dusse and Burton S. Kaliski Jr., A Cryptographic Library for the Motorola DSP56000 (in Advances in Cryptology, Eurocrypt'90, Lecture Notes In Computer Science no. 473, pp 230-244, Springer-Verlag, 1990) and in the article by S. E. Eldridge and Colin D. Walter, Hardware Implementation of Montgomery's Modular Multiplication Algorithm (in IEEE Transactions on Computers, Vol. 46, no. 6, June 1993, pp 693-699). These two detailed accounts of the Montgomery algorithm implementation are targeted, respectively, at digital signal processors with peculiar instruction sets, and at dedicated integrated circuit design. Adaptations of this prior art are useful when the Montgomery algorithm is implemented on a general purpose digital processor.

SUMMARY OF THE INVENTION

According to the present invention, there is an "issuer", that is a service organization that registers "applicants". For the issuer, it is reasonable and economically justified to maintain a computerized "database" of its customers, account holders, clients or subscribers, where this database contains sensitive information, and to train personnel, or "issuer agents", to provide customer services with a relevant degree of integrity and loyalty. The issuer database is secured using the known art of data processing security where a single organization may exert effective control of the system security. Typically, this will include cryptographic processing capabilities closely associated with the database in such a way that secret keys are not accessible to issuer personnel. At the same time, the issuer agents are typically provided with relevant customer data needed to respond to specific customer requests. The issuer agents typically access this data on a need-to-know basis through on-line terminals with controlled access to software functions, and with auditing to deter or sanction frauds that agents might conceive or commit.

The present invention is an improved method for the establishment of a secret key shared in confidence between a digital memory possessed by an applicant and the issuer database, where no prior secret is available from which the desired secret key could be derived. The present invention may obviously be used to establish a secret key when a choice is made to ignore any prior secret, e.g. due to a suspected security breach.

The following table shows the preliminary steps needed for the present invention. The issuer arranges his own private/public key pair for a Public Key Cryptosystem (PKC) that is later used, in any number of secret key establishment instances, to protect a message transmission from the applicant's digital processor to the issuer data processing center where the issuer's private key may be used. At least three PKCs are acceptable: 1) conventional public key encryption, 2) the PEKE cryptosystem, and 3) the Lein Ham's improvement to the Diffie-Hellman key exchange. Each PKC has intrinsic properties that can lead to variations of the present invention.

    ______________________________________
    Issuer       Distributor   Applicant
    ______________________________________
    Set up private/
    public key pair
    Package public
                 Distribute software
                               Obtain application
    key with application       software
    software
                 Distribute hardware
                               Obtain portable
                               memory device
    ______________________________________

    ______________________________________
    Portable            Applicant's   Issuer data
    memory              digital       processing
    device   Applicant  processor     center
    ______________________________________
             Start applicant
                        Preferably receive
             registration
                        message according
             program    to cryptosystem in
                        use
                        Generate a secrete
                        key, variant-
                        dependent rules
    Receive secret      Load secret key into
    key                 portable memory
                        device
             Type secret
                        Seal and encrypt e.g.
             pass query using issuer public
             and        key
             pass reply
                        Send message  Receive
                                      message
                                      Decrypt and
                                      check, store
                                      secret key, pass
                                      query, and pass
                                      reply
    ______________________________________

    ______________________________________
    Issuer data processing
    center       Issuer agent  Applicant
    ______________________________________
    Communicate applicant's
                 Establish realtime,
                               Establish realtime,
    data         2-way contact 2-way contact
    Communicate pass query
                 Pronounce pass query
                               Listen and verify
    and pass reply             query
                 Listen and verify reply
                               Pronounce pass reply
                 Verify applicant's
                               Answer questions
                 identity
    Validate secrete key
                 Accept applicant's
    registration identity
    ______________________________________

                  TABLE 4
    ______________________________________
    The PKC specification table.
    RSA (PK-Encr)  PEKE          DH-Harn
    ______________________________________
    Public key
            N = P .times. Q, e
                       N = P .times. Q
                                     y = a.sup.x mod p
    Private key
            P, Q, d, where
                       P, Q, where P random x, x < p
            P and Q are
                       and Q are large
            large random
                       random primes
            primes, and
                       congruent to 3
            d .times. e mod
                       modulo 4
            (P-1)(Q-1) = 1
                       (note 1)
    Other Para-
            none       S, C, k, t, where
                                     p, a, where p is
    meters             O < C .times. S < N,
                                     a large prime
                       k < In(N)/In(2)
                                     number and a is
                                     a "generator"
    First   none       random x.sub.A- > B,
                                     r, s, where
    message            where x.sub.A- > B < C
                                     r = a.sup.k mod p
                                     from private
                                     random k, s
                                     from signature
                                     equation (note 5)
    Verification
            n/a        none          Signature
    of first                         verification
    message                          equation (note 5)
    Internal
            Secret random
                       w = B.sub.o .linevert split.B.sub.1 .linevert split..
                       . ..linevert split.B.sub.t - 1,
                                     r.sup.e mod p,
    secret key
            number k   from secret   from private
                       random X.sub.B.linevert split.,
                                     random e
                       where X.sub.B.linevert split. < N/C
                       (note 2)
    Length of
            <In(N)/In(2)
                       k .times. t   In(p)/In(2)
    internal key
    Second  c = k.sup.e mod N
                       x.sub.t       f = a.sup.e mod p
    message
    Verification
            none       (note 3)      none
    of second
    message
    Recovery of
            k = c.sup.d mod N
                       w = B.sub.o .linevert split.B.sub.1 .linevert split..
                       . . .linevert split.B.sub.t - 1,
                                     f.sup.k mod p
    internal           from secret e,
    secret key         (note 4)
    ______________________________________
     Note 1: Preferably perform the precomputation of integers a and b such
     that a .times. P + b .times. Q = 1, and alpha = ((P + 1)/4).sup.(t+1) mod
     (P - 1), and beta = ((Q + 1)/4).sup.(t+1) mod (Q - 1).
     Note 2: Compute x = (x.sub.B - (x.sub.B mod S)) .times. C + x.sub.A ->B
     .times. S + (x.sub.B mod S), x.sub.0 = x.sup.2 mod N, x.sub.i+1 =
     x.sub.i.sup.2 mod N, where i runs from 0 to t - 1, and B.sub.i = x.sub.i
     mod 2.sup.k, where i runs from 0 to t -1.
     Note 3: Compute mu = (xt mod P).sup.alpha mod P, nu = (xt mod Q).sup.beta
     mod Q, e = (b .times. Q .times. mu + a .times. P .times. nu) mod N, f = (
     .times. Q .times. (P - mu) + a .times. P .times. nu) mod N, g = (b .times
     Q .times. mu + a .times. P .times. (Q - nu)) mod N, h = (b .times. Q
     .times. (P - mu) + a .times. P .times. (Q - nu)) mod N, and then verify
     that one of e, f, g, or h satisfies x.sub.A->B .times. S = #(? mod (S
     .times. C)) - (? mod S).
     Note 4: Compute x.sub.0 = e.sup.2 mod N, x.sub.i+1 = x.sub.i.sup.2 mod N,
     where i runs from 0 to t-1, and B.sub.i = x.sub.i mod 2.sup.k, where i
     runs from 0 to t - 1.
     Note 5: Lein Harn proposes four possible equation pairs for signature
     generation/verification, as indicated below:


______________________________________
    Signature Generation Signature Verification
    ______________________________________
    (1)     r .times. x = k + s mod (p-1)
                             y.sup.r = r .times. a.sup.s mod p
    (2)     s .times. x = k + r mod (p-1))
                             y.sup.s = r .times. a.sup.r mod p
    (3)     x = r .times. k + s mod (p-1)
                             y = r.sup.r .times. a.sup.s mod p
    (4)     x = s .times. k + r mod (p-1)
                             y = r.sup.s .times. a.sup.r mod
    ______________________________________
                             p

    ______________________________________
    modular.sub.-- inverse(N,b)
    Let k be such that b=2.sup.k
    t:= 1;
    for i.rarw.2 to k do
    if (N.sub.0 .times. t mod 2.sup.i).gtoreq.2.sup.i-1
    t:= t+2.sup.i-1 ;
    return b - t;
    ______________________________________

    ______________________________________
    M.sub.N,b,n (X,Y)
           N.sub.0 ':= b-(N.sub.0.sup.-1 mod b);
           c := 0;
           for k.rarw.0 to n-1 do
             c := c+.SIGMA..sub.0.ltoreq.i<k (X.sub.i .times. Y.sub.k-i
             +Q.sub.i .times. N.sub.k-i);
             c := c + X.sub.k .times. Y.sub.0
             Q.sub.k := c .times. N.sub.0 ' mod b;
             c := c
                   +Q.sub.k xN.sub.0 ;
             c := c/b;
           for k.rarw.0 to n-1 do
             c := c+.SIGMA..sub.k<i<n (X.sub.i .times. Y.sub.n+k-i +Q.sub.i
             .times. N.sub.n+k-i);
             R.sub.k := c mod b;
             c := .left brkt-bot.c/b.right brkt-bot.;
           R.sub.n := c;
           if R.gtoreq.N then
             R := R-N;
           return R;
    ______________________________________

• Inventors
  Moreau, Thierry;
• Assignee
  Connotech Experts-Conseils Inc. (Montreal, CA)
• Published
  May-9-2000
• Current US Classes:
  380/283
  713/171
• Application #
  296378
• International Classes
  H04L 009/08
• Field of Search
  380/283 380/285 713/168 713/169 713/171
• Examiner
  Barron, Jr.; Gilberto
• Agent
  Anglehart; James Swabey, Ogilvy, Renault
• US Patent References:
  4200770
  4405829
  4771461
  5020105
  5142578
  5179591
  5216715
  5288978
  5375159
  5386468
  5535276
  5539824
  5557679
  5583939
  5680458
  5745571
  5748739
  5768373
  5784463
  5875394