Magic Flight: latest version of a public-key algorithm using max-plus algebra

From: Jim Steuert (pjsteuert_at_rcn.com)
Date: 08/04/03 

Date: Sun, 03 Aug 2003 21:03:49 -0400

 
Magic Flight is an algorithm for public key
exchange which is based on a lossy commutative mixer.

This newest implementation of the Magic-Flight
public key algorithm, along with an included text paper with references
and bibliography, is at:
 
<URL: http://users.rcn.com/pjsteuert/maxplus.c>
 
and with random number generator
 
<URL: http://users.rcn.com/pjsteuert/r250j.c>

Magic Flight uses a commutative-distributive algebra with missing additive
and multiplicative inverses. The elimination of additive
inverses (cancellation) is intended to prevent standard algebraic
methods of solution.

Bryan Olson broke the prior version of Magic Flight
which used a home-grown semigroup algebra.
He used an recursive attack to break that particular
version.

This current version uses max-plus algebra, wherein add is
distributive over max, and is provided along with a simple
working program example. This algorithm is related to the
subset-sum problem.

This current algebra should meet the goal of preventing Gaussian
Elimination. This version creates large but low-entropy public
and shared keys due to the max operation.

A earlier practical variant of the original program
(with 2^30 work to create, and 2^60 work to break)
exists which uses Karatsuba multiplication method
to implement the commutative mixer, using a matrix-based
ring with some missing multiplicative inverses.
 
Other commutative and distributive semigroup algebras are
being investigated, including semigroup generation programs, as well as
constructions of distributive lattices.

A program for generating semigroup algebras of order up to
6 is provided at <URL: http://users.rcn.com/pjsteuert/gensemi.c>
It is not, however, used in the current version of MagicFlight.
 
Related work by Chris Monico, and by
Maze, Monico, and Rosenthal, use semirings but
not this mixer operation, and do not
implement this particular rng operation.
 
 -Jim Steuert

Relevant Pages

  • Re: Mark W. Hopkins theory perspective on parser engine technology?
    ... time to have a linear parsing algorithm for a general CFG, ... a context-free expression) by reduction to normal form over the pure ... The Orepresentation is farily clear and trivial. ... bra-ket algebra, forming a highly fluid syntax that allows you to go ...
    (comp.theory)
  • Re: Lisp Driven Genomics in Nucleic Acids Research
    ... A top billing for Lisp (even tho "This algorithm is the central contribution of this work.") calls for a top post! ... "Stand firm in your refusal to remain conscious during algebra." ...
    (comp.lang.lisp)
  • Re: The generality of mathematics
    ... Much of algebra is dominated by the notion that objects can be ... >can be formed using the formalism of modern mathematics? ... scientists have faced with regards to the notion of "algorithm": ...
    (sci.math)
  • Re: calculating an algebraic structure from matrices
    ... be some unique algebra ... There is no algorithm which ... straightforward undecidability proof would be easy given the ... I take the problem of finding all equivalence classes of that ...
    (sci.math)