Computer programs for use with the book "Multivariate Public Key Cryptosystems".
Please send all comments to dieter.schmidt @ uc.edu
The first group of programs are written in the Computational Algebra System
MAGMA
All programs are regular text files and can be executed in Magma by entering
on the command level 'magma MI.txt' or within Magma via 'load "MI.txt";' assuming that the
name of the file is as given and in the current directory.
To chapter 2: Matsumoto Imai
MI.txt Program demonstrates the original idea of Matsumoto Imai. It uses a plaintext
finds the cipher and recovers the plaintext by two method: via Groebner bases and via the private key.
The section on Groebner basis is only there for verification and will take too long for larger values of n and q.
To chapter 2: Linearization equations Matsumoto Imai
The program MI-LINEQ.txt is set up to compute the linearzation equations for a Matsumoto Imai system. The values of the parameters are those used in the book. The program shows how the linearization equations can be used to recover the plaintext, when only the public key and the cipher is given.
The program uses the file MI0.txt and also writes to the disk two files with the names lin.txt and public_key.txt.
To chapter 3: Oil Vinegar Signature Systems
The program ovodd.txt generates an oil vinegar signature system and shows how
to sign a document. To verify the signature the public key is used and evaluated with the given signature. It has to
reproduce the document in order to be valid. The program then identifies the oil space and constructs an equivalent set of functions which can be used to sign another
document as if one had the original secrete key.
The program oveven.txt does the same for a field with even characteristic.
Both programs need the function xtndbss.txt for extending a basis and ovsignverifydocument.txt a program with the functions for signing and verifying a signature.
To chapter 4: Hidden Field Equations
The program HFE.txt sets up the public key for HFE. It then checks for each possible
plaintext how many different solutions exist, when solving the corresponding polynomial in the extension field.
When a new version of Magma is used the results do not agree with what is listed in the book.
The reason is that Magma now uses a different algorithm to produce the irreducible polynomial g and it does not
agree with the one which was used in the book.
To chapter 5: Internal Perturbations
The program PMI.txt adds perturbations to the Matsumoto Imai system. It uses a plaintext
finds the cipher and shows how to recover the plaintext. The parameters correspond to those in the book on pages 117-119. The program was not designed to be efficient.
The second group of programs is written in C++ and was written for Visual C++ Version 7.1
To section 3.3: Rainbow
The following files make up the project:
The format is as requested by Ecrypt for eBats, but uses the
parameters mentioned in the book.
The file submitted to eBats is also available as a tar file compressed under UNIX at
http://www.cs.uc.edu/~dschmidt/rainbow.tar.gz.
It uses different parameters and random numbers, which are supplied by eBats via getchar().