Re: Magic Flight: A New Public Key Algorithm stronger? than factoring

From: Francois Grieu (fgrieu_at_micronet.fr)
Date: 07/16/03

  • Next message: Tom St Denis: "Re: CryptaFlix beta testers needed" 
    Date: Wed, 16 Jul 2003 18:17:45 +0200

    In article <oprschp4a5dwdye5@news.rcn.com>,
     Jim Steuert <pjsteuert@rcn.com> wrote:

    > As to the original commute.c, and the alleged break.
    > I just tried the original commute.c with (..)
    > #define NUMPRIMES 16
    > #define NUMTERMS 65536
    >
    > It works fine, but is slow (a minute). But still usable
    > in an off-line form.
    > And breaks would still take 2^48 work.

    This work factor is a proven MAXIMUM, for a MF variant
    that requires 2^32 work for the legitimate user. Not only
    is that unspectacularly hard, but the work required for
    straight Gaussian elimination tells us nothing of the work
    for a break by better means. Again, Gaussian elimination is
    NOT the best known method to solve a system of linear
    equations.

    [And the problem required to break MF may be even weaker
    than a system of linear equations: knowing
    pa=ka#c, pb=kb#c, and c, we want ka#kb#c, which conceivably
    could be found without explicitly finding one solution to
    the linear system x#c = pa]

    > I don't think that even the original commute.c can be
    > considered broken.

    This version was proven breakable in about 2^36
    operations. This does qualify as a total break.

    At least another thing proven in
    <fgrieu-FE4B71.08313011072003@news.fu-berlin.de>
    is that multiple layers reduce to one, with a
    REDUCED keyspace, thus LESS security than a single
    layer version. This observation applies to tabular.c
    as well.
    May I strongly suggest to drop multiple layers entirely?

      François Grieu

  • Next message: Tom St Denis: "Re: CryptaFlix beta testers needed"

    Relevant Pages

    • Re: Simplest equivalent linear system?
      ... > gaussian elimination with row and column pivoting gives ... are three of the linear dependency equations for a finite set of vectors X = ... Their mutual dependencies (the linear ... is there an algorithm for simplifying linear equations, ...
      (sci.math.num-analysis)
    • Re: Motivation for matrix algebra
      ... > and represents that system of linear equations, ... If S and T are linear translations and v is a vector, ... chain of linear operations and reduce it to a single linear operation. ... > Matrix algebra is quite an interesting subject, ...
      (sci.math)
    • Re: How to solve a system of linear equations with conditions?
      ... How to solve a system of linear equations with the following ... An LP package will either ... no feasible solution exists. ...
      (sci.math)
    • Re: inverse of sparse matrix
      ... anticipated, namely, that solving systems of linear equations is what you ... the inverse of sparse matrix is not ... Type HELP MEMORY for your options. ...
      (comp.soft-sys.matlab)
    • Re: after beginners algebra, where to?
      ... linear applications ... precalculus you'll be learning in calculus anyway, ... In parallel with learning calculus, take a look at Linear Algebra. ... solving the system of linear equations in some systematic way, ...
      (sci.math)