PUBLIC KEY CRYPTOSYSTEM METHOD AND APPARATUS

摘要

This public-key cryptosystem endocing technique uses a mixing system based on polynomial algebra and recuction modulo two numbers while the decoding technique uses an unmixing system whose validity depends on elementary probability theory. A method for encoding and decoding a digital message comprises the steps: selecting ideals p and q of a ring R (305); generating elements f and g of the ring R (325), and generating an element F sub q which is an inverse of f (mod q), and generating F sub p which is an inverse of f (mod p) (340); producing a public key that includes h (350), where h is congruent, mod q, to a product that can be derived using g and F sub q; producing a private key from which f and F sub p can be derived; producing an encoded message by encoding the message using the public key and a random element; and producing a decoded message by decoding the encoded message using the private key.