A variation of the McEliece public key cryptosystem

摘要

This invention provides an improved security variation of the McEliece Public Key encryption system first published in 1978, which uses Goppa codes and contains features which make full use of random number generation for given message and cryptogram parameters. Unlike most other encryption methods, using this invention the encrypted message is a truly random function, not a pseudo-random function of the message so that even with the same message and the same public key, a different, unpredictable cryptogram is produced each time. It is shown that with the knowledge of the private key, the random function may be determined from the cryptogram and the message decrypted. Different embodiments of the invention are described which enable the level of security to be traded-off against cryptogram size and complexity. A number of different applications are given. In comparison to the original McEliece cryptosystem the arrangement described differs as the number of bit errors introduced into each (deliberately) corrupted codeword is not fixed, but is also randomly chosen. In addition a number of bits may be deleted from the codeword in random positions, adding to the security of the cryptogram and reducing the size of the cryptogram, without shortening the message.