MEC

MEC: Modular Matrix Exponentiation Cryptography

Douglas Crockford douglas@crockford.com

dec64.com 2017-04-16 Public Domain

NO WARRANTY EXPRESSED OR IMPLIED.
USE AT YOUR OWN RISK.
SUBJECT TO CHANGE WITHOUT NOTICE.
YOU HAVE BEEN WARNED.

MEC is a new, untested, unproven system for public key cryptography. Its security depends on the difficulty of the discrete logarithm problem for modular matrixes. It has not been determined that this problem is sufficiently hard.

This MEC implementation is in C and is delivered as three files:

mec.h
mec.c
mec.x64.asm

This MEC implementation assumes the availability of 64 bit arithmetic.

This MEC implementation provides a single function, mec_generate, which takes a private key in the form of an array of random bytes, and a 5x5 matrix in the form of an array of 25 unsigned 32 bit ints. The array of random bytes can be of any length, but a length of at least 64 bytes is recommended. mec_generate returns a 5x5 matrix as an array of 25 unsigned 32 bit ints.

mec_generate does matrix exponentiation by matrix squaring and matrix multiplication. The squaring and multiplication operations are done modulo 4294967291 = 2**32 - 5.

This implementation also provides a read-only data structure called mec_base, the base matrix. The design of mec_base was derived from the Mars magic square. Each element was multiplied by 160000000 and then advanced to the next prime number.

Two versions of mec_generate are provided here:

In C.

In x64 assembly language.

Here is an example of its use:

Bob makes an array of random bytes that will be used as his private key.

mec8 bobs_private_key[64];
your_random_generator(bobs_private_key, 64);

Bob passes his private key and mec_base to mec_generate, which will generate Bob's public key. Bob then publishes Bob's public key.

mec32 bobs_public_key[25];
mec_generate(bobs_public_key, mec_base, bobs_private_key, 64);

Alice finds Bob's public key. She makes her own private key. She passes her private key and mec_base to mec_generate, which will generate Alice's public key. Alice sends Alice's public key to Bob.

mec8 alices_private_key[64];
your_random_generator(alices_private_key, 64);
mec32 alices_public_key[25];
mec_generate(alices_public_key, mec_base, alices_private_key, 64);

Alice then passes her private key and Bob's public key to mec_generate, which generates a shared secret that Alice can use to secure her communications with Bob.

mec32 shared_secret[25];
mec_generate(shared_secret, bobs_public_key, alices_private_key, 64);

Bob then passes his private key and Alice's public key to mec_generate, which generates the same shared secret.

mec_generate(shared_secret, alices_public_key, bobs_private_key, 64);