Robert McEliece, in 1978, outlined the McEliece cryptosystem [here]. Overall it is asymmetric encryption method (with a public key and a private key), and, at the time, looked to be a serious contender. Unfortuantely for the method, RSA became the King of the Hill, and the McEliece method was pushed to the end of the queue for designers. It has basically drifted in the 38 years since. But, as an era of quantum computers is dawning, it is now being reconsidered, as it is seen to be immune to attacks using Shor's algorithm.
McEliece |
Coding
The following is an outline:
public static string mce_key(string message) { string outmce=""; MPKCParameters mpar = (MPKCParameters)MPKCParamSets.MPKCFM11T40S256.DeepCopy(); MPKCKeyGenerator mkgen = new MPKCKeyGenerator(mpar); IAsymmetricKeyPair akp = mkgen.GenerateKeyPair(); MPKCPublicKey pub = (MPKCPublicKey)akp.PublicKey; MPKCPrivateKey pri = (MPKCPrivateKey)akp.PrivateKey; outmce += String.Format("Public key: K: {0}, N: {1}, T:{2}, Name:{3}\n", pub.K, pub.N, pub.T,pub.Name); outmce += String.Format("Private key: K: {0}, N: {1}, T:{2}, Name:{3}\n", pri.K, pri.N, pri.T, pri.Name); MPKCParameters encParams = (MPKCParameters)MPKCParamSets.MPKCFM11T40S256.DeepCopy(); MPKCKeyGenerator keyGen = new MPKCKeyGenerator(encParams); IAsymmetricKeyPair keyPair = keyGen.GenerateKeyPair(); byte[] enc, dec, data; //// encrypt using (MPKCEncrypt cipher = new MPKCEncrypt(encParams)) { cipher.Initialize(keyPair.PublicKey); data = Encoding.ASCII.GetBytes(message); outmce += "Message: "+message+"\n"; enc = cipher.Encrypt(data); outmce += "Cipher: " + ByteArrayToHexString(enc)+ "\n"; } //// decrypt using (MPKCEncrypt cipher = new MPKCEncrypt(encParams)) { cipher.Initialize(keyPair.PrivateKey); dec = cipher.Decrypt(enc); string s = System.Text.Encoding.UTF8.GetString(dec, 0, dec.Length); outmce += "Decrypt: " + s+ "\n"; } /// Signing using (MPKCSign sgn = new MPKCSign(mpar)) { sgn.Initialize(akp.PublicKey); int sz = sgn.MaxPlainText - 1; new VTDev.Libraries.CEXEngine.Crypto.Prng.CSPRng().GetBytes(data); byte[] code = sgn.Sign(data, 0, data.Length); string sig = ByteArrayToHexString(code); outmce += "Signing (only first 50 hex chars shown): " + Truncate(sig, 50)+"\n"; sgn.Initialize(akp.PrivateKey); if (sgn.Verify(data, 0, data.Length, code)) { outmce += "- Sign and verify test worked.\n"; } sgn.Initialize(akp.PublicKey); code = sgn.Sign(new MemoryStream(data)); sgn.Initialize(akp.PrivateKey); if (sgn.Verify(new MemoryStream(data), code)) { outmce += "- Private key comparison works.\n"; } } string pub_str = ByteArrayToHexString(pub.ToBytes()); string pri_str = ByteArrayToHexString(pri.ToBytes()); outmce += "\n Length of public key: " + pub_str.Length/2+" Bytes"; outmce += "\n Length of private key: " + pri_str.Length/2 + " Bytes"; outmce += "\n Public key Hex (only first 50 hex chars shown): " + Truncate(pub_str,50); outmce += "\n Private key Hex (only first 50 hex chars shown): " + Truncate(pri_str, 50); pri.Dispose(); pub.Dispose(); return (outmce); }
Outline
In a lesson for any modern researcher, in just two pages, Robert McEliece, in 1978, outlined the McEliece cryptosystem [paper]. Overall it is asymmetric encryption method (with a public key and a private key), and, at the time, looked to be a serious contender. Unfortuantely for the method, RSA became the King of the Hill, and the McEliece method was pushed to the end of the queue for designers.
It has basically drifted in the 38 years since. But, as an era of quantum computers is dawning, it is now being considered as it is immune to attacks using Shor's algorithm. In this page, I've avoided going into detail on the actual method, but have provided the code for you to test it out.
NIST has now started to move with a paper outlining the requirement for new cryptography methods [here], as a large-scale quantum computer will break most of the currently available public key systems, including RSA. Overall public key is now most often used to protect secret keys using in symmetric encryption, and to prove identity. A large-scale breach of public key would lead to a complete lack of trust on the Internet.
The main contenders for quantum robust methods are:
- Lattice-based cryptography – This classification shows great potential and is leading to new cryptography, such as for fully homomorphic encryption [here] and code obfuscation. An example is given in the following section.
- Code-based cryptography – This method was created in 1978 with the McEliece cryptosystem but has barely been using in real applications. The McEliece method uses linear codes that are used in error correcting codes, and involves matrix-vector multiplication. An example of a linear code is Hamming code [here]
- Multivariate polynomial cryptography – These focus on the difficulty of solving systems of multivariate polynomials over finite fields. Unfortunately, many of the methods that have been proposed have already been broken.
- Hash-based signatures – This would involve created digital signatures using hashing methods. The drawback is that a signer needs to keep a track of all of the messages that have been signed, and that there is a limit to the number of signatures that can be produced.
The McEliece method uses code-based cryptography. Its foundation is based on the difficulty in decoding a general linear code, and is generally faster than RSA for encryption and decryption. Within it we have a probabistic key generation method, which is then used to produce the public and the private key. The keys are generated with the parameters of n, k and T.
The keys are generated with the parameters of n, k and t. With this we created an [n,k] matrix of codes, and which is able to correct t errors. In his paper, McEliece defines defines n=1024, k=524, t=50, and which gives a public key size of 524x(1024-524) = 262,000 bits. In example above we use k=1608, N=2048 and T=40, which gives a public key size of 1608x(2048-40) - 3,228,864 bits. For quantum robustness it is recommended that N is 6960, k is 5,412 and t is 119 (giving a large key size of 8,373,911 bits [key generation].