Identification scheme single or multi-digital signature scheme giving message recovery single or multi-digital signature scheme with appendix key exchange scheme and blind digital signature scheme

A computer implemented method for generating and verifying a digital signature for a message m, when system coefficients are g, q and p, a digital signature scheme giving message recovery comprising the steps of:

• for a signer selecting an arbitrary number r, obtaining g.sup.-r, and calculating a remainder x (.ident.mg.sup.-r mod p) obtained by dividing by p the product of g.sup.-r by message m;
• applying said remainder x and said signer identification ID to a hash function to yield h(x,ID), and calculating a remainder y (.ident.r+ah(x,ID) mod q) obtained by dividing by q said arbitrary number r used in calculation of x and added to the product of h(x,ID) by secret key a to thereby generate a digital signature (x, y);
• and
• for a verifier, receiving said digital signature (x, y) and said identificaiton ID, applying said remainder x and said signer identification ID to said hash function to yield h(x,ID), recovering said message m contained in said remainder x by calculating a remainder xg.sup.y v.sup.h(x,ID) mod p obtained by dividing, by p, the product of said remainder x by the y.sup.th power of g and by the {h(x,ID)}.sup.th power of said signer's public key v, and verifying the validity of said digital signature for said message m by confirming the contents of the recovered message m.

A computer implemented method for generating and verifying a digital signature for message m, when system coefficients are g, q and p, a digital signature scheme comprising the steps of:

• (1) for a signer, applying said message in and identification ID to a hash function to obtain h (ID,m) , selecting an arbitrary number r, obtaining g.sup.-r, and calculating a remainder x (.ident.h(ID,m)g.sup.-r mod p) obtained by dividing by p the product of g.sup.-r by h(ID,m);
• (2) applying said remainder x and said message in to the hash function to yield h(x,in), and calculating a remainder y (.ident.r+ah(x,m) mod q) obtained by dividing by q said arbitrary number r used in calculation of x and added to the product of h(x,m) by secret key a to thereby generate a digital signature (x,y);
• and
• (3) for a verifier, receiving said digital signature (x,y) and said message in, applying said remainder x and said message m to said hash function to yield h(x,m), recovering a hash function value h(ID,m) of said message in contained in said remainder x by calculating a remainder xg.sup.y v.sup.h(x,m) mod p) obtained by dividing, by p, the product of said remainder x by the y.sup.th power of g and by the {h(x,m)}.sup.th power of said signer's public key v;
• and
• (4) verifying the validity of said digital signature for said message m by confirming whether said hash function value of said message is equal to h(ID,m) obtained by applying the signer's ID and message m to the hash function.

A computer implemented method for key exchange when two users A and B of prover and verifier generate a common session key with their public keys v.sub.A (.ident.g.sup.-a mod p) and v.sub.B (.ident.g.sup.-b mod p) respectively, comprising the steps of:

• for user A, generating arbitrary numbers R and r, obtaining the R.sup.th power of g, and calculating a remainder x (.ident.g.sup.R g.sup.-r mod p) obtained by dividing by p the product of g.sup.R by the -r.sup.th power of g;
• for user A, calculating a remainder k (.ident.v.sub.B.sup.a .ident.g.sup.-ab mod p) obtained by dividing the a.sup.th power of user B's public key v.sub.B by p, applying x and k to a hash function to obtain h(x,k), and calculating a remainder y (.ident.r+ah(x,k) mod q) obtained by dividing by q arbitrary number r added to the product of h(x,k) by secret key a to transmit the result to user B;
• for user A, calculating as a session key a remainder K (.ident.v.sub.B.sup.R .ident.(g.sup.-b).sup.R mod p) obtained by dividing the R.sup.th power of user B's public key v.sub.B by p, and (for user B) calculating a remainder k (.ident.v.sub.A.sup.b .ident.g.sup.-ab mod p) obtained by dividing the b.sup.th power of user A's public key v.sub.A by p;
• and
• for user B, from (x,y) received from user A, calculating a remainder g.sup.R (.ident.xg.sup.Y v.sub.A.sup.h(x,k) mod p) obtained by dividing by p the product of the y.sup.th power of g by the h(x,k).sup.th power of user A's public key v.sub.A and by x, and for user B calculating a remainder K (.ident.(g.sup.R).sup.-b mod p)) obtained by dividing the -b.sup.th power of g.sup.R by p to obtain a session key.

A computer implemented method for generating and verifying digital signature when multiple signers'generating a series of digital signatures for a message m, a multi-digital signature scheme giving message recovery comprising the steps of;

• (1) for an initial signer of multiple signers, selecting an arbitrary number r.sub.1 and calculating a remainder x.sub.1 (.ident.mg.sup.-r.sbsp.1 mod p) obtained by dividing by p the product of g.sup.-r.sbsp.1 by message m;
• (2) applying x.sub.1 and the first signer's identification ID.sub.1 to a hash function to obtain h(x.sub.1,ID.sub.1), and calculating a remainder y.sub.1 (.ident.r.sub.1 +a.sub.1.sup.h(x1,ID.sbsp.1.sup.) mod q) obtained by dividing by q arbitrary number r.sub.1 added to the product of h(x.sub.1,ID.sub.1) by secret key a.sub.1 to thereby make a digital signature (x.sub.1 y.sub.1) for message m;
• (3) for ith signer, wherein i.gtoreq.2, receiving said message m and said (x.sub.i-1,y.sub.i-1 ), selecting an arbitrary number r.sub.i and calculating a remainder x.sub.i (.ident.x.sub.i-1 g.sup.-r.sbsp.i mod p) obtained by dividing by p the product of g.sup.-r.sbsp.i by x.sub.i-1, applying x.sub.i and ID.sub.i to a hash function to obtain h(x.sub.i,ID.sub.i), and calculating a remainder y.sub.i (.ident.r.sub.i +a.sub.i h(x.sub.i,ID.sub.i) mod q) obtained by dividing by q arbitrary number r.sub.i added to the product of h(x.sub.i,ID.sub.i) by secret key a.sub.i to thereby make a digital signature (x.sub.i,y.sub.i) for message m, and send said digital signature (x.sub.i,y.sub.i) to the next signer;
• and
• (4) confirming whether the multiple signers all generate their respective digital signatures, if there is any person who does not sign, returning to the step (3), and if not, generating a final digital signature (y.sub.1, y.sub.2, y.sub.3, . . . , y.sub.n-1, y.sub.n, x.sub.n) ;
• and
• for a verifier receiving said multi digital signature (y.sub.1, y.sub.2, . . . , y.sub.n-1, y.sub.n, x.sub.n) and the signer's identifications ID.sub.i recovering the initial digital signature (x.sub.1,y.sub.1) starting from x.sub.n-1 recovered from (x.sub.n,y.sub.n) using x.sub.i g.sup.y.sbsp.i v.sub.i.sup.h(x.sbsp.i.sup.,ID.sbsp.i.sup.) mod p , recovering message m from (x.sub.1,y.sub.1), to verify the validity of digital signature.

A computer implemented method for generating and verifying signature when multiple signers'generating a series of digital signatures for a message m, a multi-digital signature scheme with appendix comprising the steps of:

• (1) (for an initial signer of multiple signers, applying message m and identification ID.sub.1 to a hash function to obtain h(ID.sub.1,m), and making I.sub.1 (=h (ID.sub.1, m), description phrase, current time) including h(ID.sub.1,m), description phrase for message m, current time;
• (2) selecting arbitrary number r.sub.1, and calculating x.sub.1 (.ident.I.sub.1 g.sup.-r.sbsp.1 mod p) and y.sub.1 (.ident.r.sub.1 +a.sub.1 h(x.sub.1, m) mod q) to thereby bgenerate a digital signature (x.sub.1,y.sub.1);
• (3) for ith signer, wherein, i.gtoreq.2 receiving said digital signature (x.sub.i,y.sub.i) and said message m, making I.sub.i (=y.sub.i-1, description phrase, current time) including y.sub.i-1, ith description phrase for message m, current time, selecting arbitrary number r.sub.i, and calculating x.sub.i (.ident.I.sub.i g.sup.-ri mod p) and y.sub.i (.ident.r.sub.i +a.sub.i (x.sub.i, m) mod q) to thereby generate an ith digital signature (x.sub.i,y.sub.i);
• (4) confirming whether the multiple signers all generate their respective digital signatures, if there is any person who does not sign, returning to the step (3), and if not, generating a final digital signature (x.sub.1, x.sub.2, x.sub.3 , . . . , x.sub.n-1, x.sub.n, y.sub.n) ;
• and
• for a verifier receving said multi digital signature (x.sub.1, x.sub.2, x.sub.3, . . . , x.sub.n-l, x.sub.n, y.sub.n), said message m and the first signer's identification ID.sub.1, recovering the initial digital signature (x.sub.1, y.sub.1) starting from y.sub.n-1 recovered from (x.sub.n,y.sub.n) x.sub.i g.sup.y.sbsp.i v.sub.i.sup.h(x.sbsp.i.sup., m) mod p, to verify the validity of the multi digital signature confirming to verify whether hash(ID,m) of I.sub.1 recovered from (x.sub.1,y.sub.1) is equal to h(ID.sub.1, m) obtained by the verifier's computation.

A computer implemented method for generating and verifying digital signature for an electronic message m, when system coefficients are g, q, and p and a signer's public key is v.sub.A (.ident.g.sup.-a.sbsp.A mod p), a blind digital signature scheme comprising the steps of:

• for a verifiers, selecting an arbitrary number r.sub.B, calculating a remainder x.sub.B (.ident.mv.sub.A.sup.r.sbsp.B mod p) obtained by dividing by p the product of the r.sub.B.sup.th power of the signer's public key v.sub.A (.ident.g.sup.-aA mod p) by message m, and transmitting x.sub.B to the signer;
• for the signer, selecting an arbitrary number r.sub.A, calculating a remainder x.sub.A (.ident.mv.sub.A.sup.r.sbsp.B g.sup.-r.sbsp.A mod p) obtained by dividing by p the product of the -r.sub.A.sup.th power of g by x.sub.B received, and transmitting x.sub.A to the verifier;
• for said verifier, applying x.sub.A received from said signer and message m to the hash function to obtain h(x.sub.A, m), and calculating a remainder y.sub.B (.ident.h(x.sub.A, m) +r.sub.B mod q) obtained by dividing by q arbitrary number r.sub.B added to h(x.sub.A, m), and transmitting y.sub.B to the signer;
• for said signer, calculating a remainder y.sub.A (.ident.r.sub.A +y.sub.B a.sub.A mod q) obtained by dividing by q arbitrary number r.sub.A added to the product of received y.sub.B by secret key a.sub.A to thereby transmit y.sub.A to the verifier, and for said verifier, receiving a blind signature (x.sub.A,y.sub.A) for message m;
• and
• in order to verify the generated digital signature, for said verifiers, calculating a remainder x.sub.A g.sup.y.sbsp.A v.sub.A.sup.h(x.sbsp.A.sup., m) mod p obtained by dividing by p the product of the h(x.sub.A, m).sup.th power of v.sub.A by the y.sub.A.sup.th power of g and by x.sub.A, to thereby verify the validity of signer A's digital signature (x.sub.A,y.sub.A) by recovering message m and confirming its contents.