Re: Public Key, Symbolic Calculation

From: Décio Luiz Gazzoni Filho (decio_at_decpp.removethis.net)
Date: 02/04/05 

Date: Fri, 04 Feb 2005 16:06:10 -0200

tomstdenis@gmail.com wrote:

>
> Kiuhnm wrote:
>> tomstdenis@gmail.com wrote:
>> > The problem with this scheme is the set R requires high enough
>> > precision or you will have a lot of messages you can't decrypt.
> You
>> > can mitigate this by limiting the precision or using finite fields
>> > [e.g. GF(p)] but that's about it.
>>
>> No, the precision is *absolute* by using symbolic calculation (like
> in
>> Mathematica or Maple).
>
> The roots won't always be nice numbers. Unless you specifically
> construct the polynomial to have integer roots [or roots with limited
> precision].

If you forego numerical evaluation of roots, precision isn't an issue indeed
(see below for more.) Of course, I'm not sure if that's what the OP meant.

>> > Also factoring polynomials is much easier than factoring integers.
> So
>> > once you factor the polynomial you're done for.
>> >
>> > ...Also you don't say what the trap door is. You find r_i from
> p....
>> > but p is the public key. Can't an attacker just find them as well?
>>
>> The trick is to use "symbolic calculation" in order to prevent the
> use
>> of numerical algorithms (M has "symbolic" coefficients so the
> knowledge
>> of numerical solutions is useless).
>> As you know (Galois-Abel-Ruffini), is very difficult to find the
>> "symbolic" solutions of a polynomial equation of degree greater than
> 4.
>
> What the hell is "symbolic solutions" did sci.crypt just get another
> JSH? A polynomial is just a polynomial. An evaluation of a polynomial
> at a point would be "numerical".

I guess he's referring to this:
http://mathworld.wolfram.com/AbelsImpossibilityTheorem.html

Also, you don't always need to evaluate polynomial roots numerically.
Algorithms from algebraic number theory (such as the number field sieve)
are good examples of this.

> So you're saying your polynomial is then of the form
>
> p(x) = a + bx + cx^2 + dx^3 + ...
>
> ???
>
> That's hardly unique [nor would it have roots without being in terms of
> variables... e.g. everyone would have the same roots].

I would venture to guess that he's dealing with polynomial roots the way one
does in the number field sieve. Perhaps values of a, b, c, d, ... are the
cryptosystem's `key', and the roots are dealt with symbolically, NFS-style.

Note that I'm not defending the OP's ideas -- as far as I can tell, his
scheme still needs some work, and who knows, it may not work at all. It's
just that attacking the system from a numerical point of view will get you
nowhere.

Décio

Relevant Pages

  • Re: Maxima - precision
    ... You are computing the roots of a polynomial in machine precision. ... But maybe your polynomials are not nasty. ...
    (sci.math.symbolic)
  • Re: Maxima - precision
    ... I'm computing complex roots of polynomial: ... How can I set precision? ... Changing fpprec seems to have no effect. ... But maybe your polynomials are not nasty. ...
    (sci.math.symbolic)
  • Re: Maxima - precision
    ... You are computing the roots of a polynomial in machine precision. ... But maybe your polynomials are not nasty. ...
    (sci.math.symbolic)
  • Re: Public Key, Symbolic Calculation
    ... >> precision or you will have a lot of messages you can't decrypt. ... The roots won't always be nice numbers. ... This scheme isn't well thought out because it involves rather ... inefficient storage or generation of polynomials... ...
    (sci.crypt)
  • Re: Are there multiple roots?
    ... via the Winding Number theorem and simply Cauchy integrals? ... double precision a winding number for an appropriately chosen ... at most 20 roots. ... coefficients can't be accurately represented in the precision ...
    (sci.math.num-analysis)