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

From: Bryan Olson (bryanjugglercryptographer_at_yahoo.com)
Date: 07/12/03 

Date: 12 Jul 2003 13:43:19 -0700

Jim Steuert wrote:
>
> Bryan Olson wrote:
>> | None of the terms divides all the others. Still not a problem:
>> | we simply add the second row into the first to get a pivot with
>> | an inverse.
>
>
> Why do you say, "to get an inverse", when the rings I propose don't have
> any multiplicative inverses at all.

The rings you proposed, including the one coded into "Magic
Flight", do have elements with inverses (units), just as mod 15
arithmetic in my example does.

> If you have a set of, say 32700 of those distinct values like 2,
> (out of 32768), it is possible that a column of 100 rows is not
> reducible as you suggest. And the ring is not trivial in any sense:
> values can be additively "trapped" and still be changed
> by multiplication, or vice-versa.

Show the ring.

> So your "Adding the second row into the first to get a pivot with
> an inverse" is a rather large assumption, which I will happily
> rebut with a concrete example. (To be supplied).

It was an example. In the previous post I offered the general
rule:

>> Gaussian elimination works over a ring iff:
>> for any two non-zero elements of the ring x and y,
>> there are also elements a, b, and c, such that:
>> a*x is not zero
>> a*x + b*y = c*y

So what ring are you proposing?

> By a "singular subset of rows", I mean the exact minimal set
> of rows which are linearly dependent.

Why would you want that? Is that what you meant to write?

> That minimal set of rows is
> needed to invert the cipher in order to create the "set of possible
> valid keys" that refers to just the spanning of that
> vector space constituting the minimal vector space or
> "singular subset of rows".

A smallest subset of rows that spans the row-space will also be
a largest subset of linearly independent rows.
 
> Your use of pivots does not determine that minimal set.

That doesn't make any sense. Don't use the term if you don't
know what it means.

> Bryan Olson said:
>
>> We can
>> efficiently determining a minimal subset of the rows that spans
>> the rowspace (likewise for columns).
>
> How?

See just about any introductory text on linear algebra.

> In a matrix of 4096 rows, and what order is the algorithm
> to determine that minimal set. (I worked on a version of spice 20+ years
> ago,
> but I haven't kept up with the latest algorithms there, but I am curious).

The for an n-by-n matrix, the elementary algorithm is order n^3.

> Bryan Olson wrote:
>
>> Magic Flight is, incidentally, not the first public-key cipher
>> to be broken before the paper appears.
>>
>
> That's good to know, but irrelevant, as you haven't come even
> close to breaking it.

Then you haven't been paying attention. A couple days ago
Francois Grieu and I showed a one-round solution. I wrote:

| It's not yet clear whether it works against multiple rounds.

Yesterday, Grieu completed the attack, by showing that multiple
rounds are always solvable as some single round. 

-- 
--Bryan