Public key cryptosystem method and apparatus

A method for encoding and decoding a digital message m, comprising the steps of:

• selecting integers p and q;
• generating polynomials f and g;
• determining inverses F.sub.q and F.sub.p, where
• F.sub.q *f.ident.1(mod q)
• F.sub.p *f.ident.1(mod p);
• producing a public key that includes p, q, h, where
• h.ident.F.sub.q *g(mod q);
• producing a private key that includes f and F.sub.p ;
• producing an encoded message e by encoding the message m in the form of a polynomial using the public key and a random polynomial .o slashed.;
• and
• producing a decoded message by decoding the encoded message e using the private key.

A method for encoding and decoding a digital message, comprising the steps of:

• selecting relatively prime integers p and q;
• selecting a non-zero integer K;
• producing K+2 matrices, f,g,w.sub.1,w.sub.2, . . . w.sub.K from a ring of matrices with integer coefficients, with w.sub.i .ident.0 (mod p) for i=1,2, . . . ,K,
• producing inverse matrices F.sub.p, F.sub.q, G.sub.p and G.sub.q, from said ring of matrices where
• fF.sub.p .ident.I (mod p)
• fF.sub.q .ident.I (mod q)
• gG.sub.p .ident.I (mod p)
• gG.sub.q .ident.I (mod q)
• where I is an identity matrix;
• producing a public key as a list of K matrices (h.sub.1,h.sub.2, . . . h.sub.K) where
• h.sub.i .ident.F.sub.q w.sub.i G.sub.q (mod q), i=1,2, . . . ,K;
• producing a private key as the matrices (f, g, F.sub.p, G.sub.p);
• producing an encoded message e by encoding the message m using the private key and random integers .o slashed..sub.1, .o slashed..sub.2, . . . ,.o slashed..sub.K as
• e.ident..o slashed..sub.1 h.sub.1 +.o slashed..sub.2 h.sub.2 + . . . +.o slashed..sub.K h.sub.K +m(mod q);
• and
• producing a decoded message m' by computing
• a.ident.feg(mod q)
• and
• b.ident.a(mod p)
• and then computing the decoded message m' as
• m'.ident.F.sub.p bG.sub.p (mod p).

A system for encoding and decoding a digital message m, comprising:

• means for selecting ideals p and q;
• means for generating elements f and g of a ring R, and generating element F.sub.q which is an inverse of f (mod q), and generating element F.sub.p which is an inverse of f (mod p);
• means for producing a public key that includes h, where h is congruent, mod q, to a product that can be derived using g and F.sub.q ;
• means for producing a private key from which f and F.sub.p can be derived;
• means for producing an encoded message e by encoding the message m using the public key and a random element .o slashed.;
• and
• means for producing a decoded message by decoding the encoded message e using the private key.