×

Public key identification process using two hash functions

  • US 6,125,445 A
  • Filed: 05/13/1998
  • Issued: 09/26/2000
  • Est. Priority Date: 05/13/1997
  • Status: Expired due to Fees
First Claim
Patent Images

1. A process for an identification of a calculation and storage means claimant by a verifier, the claimant and verifier having calculation and storage mechanisms,wherein the claimant and verifier have the following in common:

  • a first integer n, which is the product of two prime numbers (p, q),a second integer g between 0 and n-1 and of high order k, the order k being defined as the smaller of the numbers such that gk =1 mod n,a parameter m determining the interval in which are drawn the random exponents,first and second separate hash functions H1, H2 and which are independent of one another,wherein the claimant further includes a secret number S equal to the modulo n cubic root of a number I deduced from its identity, so that the number S verifies;

    S3 =I mod n,wherein the claimant and verifier utilize their calculation and storage mechanisms for performing the following, successive operations;

    phase A;

    the claimant;

    Aa) draws at random a first integral exponent α

    between 0 and m-1,Ab) calculates a number r equal to the power α

    of the modulo n number g, namely;

    r=g.sup.α

    mod n,Ac) calculates a number R equal to the cube of r modulo n, namely;

    R=r3 mod n=g3α

    mod n, andAd) transmits the number R to the verifier;

    phase B;

    the verifier;

    Ba) draws at random a second integral exponent β

    between 0 and m-1,Bb) calculates a number t equal to the power β

    of the g modulo n number, namely;

    t=g.sup.β

    mod n,Bc) calculates a number T equal to the cube of t modulo n, namely;

    T=t3 mod n=g3β

    mod n,Bd) calculates a number Z equal to the power β

    of R modulo n, namely;

    Z=R.sup.β

    mod n,Be) applies the first hash function H1 to Z for obtaining a number h;

    h=H1 (Z), andBf) transmits to the claimant the numbers T and h;

    phase C;

    the claimant;

    Ca) calculates a number Y equal to the power α

    of the number T modulo n, namely;

    Y=T.sup.α

    mod n,Cb) applies to the number Y the first hash function H1 and obtains the result H1 (Y) and verifies whether this result is equal to the number h received from the verifier,Cc) applies to the number Y the second hash function H2 for obtaining a result H;

    H=H2 (Y),Cd) calculates a number z equal to the product of the number r by the secret S modulo n, namely;

    z=rS mod n, andCe) transmits the numbers z and H to the verifier;

    phase D;

    the verifier;

    Da) applies to the number Z the second hash function H2 and verifies whether the result obtained H2 (Z) is equal to the number H received from the claimant, namely;

    H=H2 (Z) and Z3 mod n=RI mod n, andDb) calculates the product of R by I modulo n and the cube of z modulo n and checks whether the two results are equal, andwherein the identification of the claimant by the verifier is made if the three verifications determined in steps Cb), Da), and Db) are performed.

View all claims
  • 4 Assignments
Timeline View
Assignment View
    ×
    ×