Re: [sage-devel] Re: Anyone used SBox.interpolation_polynomial?
On Wed, Mar 13, 2019 at 12:12 PM Friedrich Wiemer
wrote:
>
> I discussed this again with my colleagues and maybe its just not so sure what
> the correct way to do is?
>
> Is it actually clear what the "correct" ordering of finite field elements is?
> The canonical ordering is 0, 1, a^1, a^2, ..., - but then this representation
> and ordering depends on the representation of the actual instance, so which
> polynomial is picked.
I'm not even sure whether a primitive element is always available in a
Sage finite field. A field might be constructed from any irreducible
polynomial, and IMHO
finding a primitive element is not very quick for large fields.
> If instead the elements are ordered after the representing polynomial is
> chosen, we get 0, 1, a, a+1, ... - but for example list(GF(2^3)) is
> differently ordered, depending on the chosen implementation. pari and ntl
> results in 0, 1, a, a+1, ... while givaro gives 0, a, a+1, ..., 1.
>
> Regarding this, it might be ok to work with the output of `sorted(GF(...))`,
> as its done currently. Nevertheless, there remains the problem with different
> polynomials for representing the finite field and thus the resulting S-box
> might be different. Here is an example of what I mean:
>
> sage: F1 = GF(2^3, name='a', modulus=PolynomialRing(GF(2), 'a')('a^3 + a +
> 1'))
> : F2 = GF(2^3, name='a', modulus=PolynomialRing(GF(2), 'a')('a^3 + a^2 +
> 1'))
> : R1 = PolynomialRing(F1, 'x')
> : R2 = PolynomialRing(F2, 'x')
> : inv1 = R1.gen()**(2**3-2)
> : inv2 = R2.gen()**(2**3-2)
> : S1 = SBox([inv1(v) for v in sorted(F1)])
> : S2 = SBox([inv2(v) for v in sorted(F2)])
> : S1, S2
> (0, 1, 5, 6, 7, 2, 3, 4),
> (0, 1, 6, 4, 3, 7, 2, 5)
>
> OK, so not so sure if this all makes sense in the context of the above
> question, but this behaviour should at least be mentioned in the docs, I
> think.
> Regarding the above discussed point, I still think that the current behaviour
> is 'wrong' in the way that one would expect a different result.
>
> --
> You received this message because you are subscribed to the Google Groups
> "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-devel+unsubscr...@googlegroups.com.
> To post to this group, send email to sage-devel@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Anyone used SBox.interpolation_polynomial?
I discussed this again with my colleagues and maybe its just not so sure
what the correct way to do is?
Is it actually clear what the "correct" ordering of finite field elements
is? The canonical ordering is 0, 1, a^1, a^2, ..., - but then this
representation and ordering depends on the representation of the actual
instance, so which polynomial is picked. If instead the elements are
ordered after the representing polynomial is chosen, we get 0, 1, a, a+1,
... - but for example list(GF(2^3)) is differently ordered, depending on
the chosen implementation. pari and ntl results in 0, 1, a, a+1, ... while
givaro gives 0, a, a+1, ..., 1.
Regarding this, it might be ok to work with the output of
`sorted(GF(...))`, as its done currently. Nevertheless, there remains the
problem with different polynomials for representing the finite field and
thus the resulting S-box might be different. Here is an example of what I
mean:
sage: F1 = GF(2^3, name='a', modulus=PolynomialRing(GF(2), 'a')('a^3 + a +
1'))
: F2 = GF(2^3, name='a', modulus=PolynomialRing(GF(2), 'a')('a^3 + a^2
+ 1'))
: R1 = PolynomialRing(F1, 'x')
: R2 = PolynomialRing(F2, 'x')
: inv1 = R1.gen()**(2**3-2)
: inv2 = R2.gen()**(2**3-2)
: S1 = SBox([inv1(v) for v in sorted(F1)])
: S2 = SBox([inv2(v) for v in sorted(F2)])
: S1, S2
(0, 1, 5, 6, 7, 2, 3, 4),
(0, 1, 6, 4, 3, 7, 2, 5)
OK, so not so sure if this all makes sense in the context of the above
question, but this behaviour should at least be mentioned in the docs, I
think.
Regarding the above discussed point, I still think that the current
behaviour is 'wrong' in the way that one would expect a different result.
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Anyone used SBox.interpolation_polynomial?
Hi there, I probably wrote the code and the documentation (?) but I haven’t used either in a while. If it’s all the same, perhaps keeping the current behaviour (and changing the documentation) is the strategy of least surprise? Cheers, Martin Travis Scrimshaw writes: > Anyone have any thoughts on this? If not, then I will assume that the > documentation was the intended behavior. > > Best, > Travis > > > On Sunday, December 23, 2018 at 7:15:00 AM UTC+10, Travis Scrimshaw wrote: >> >> It has to do more specifically with how GF(2^k) elements are interpreted >> by an SBox. The documentation says they are treated differently than the >> code, and I wanted to know which was correct. In particular, it was >> interpreted in the code as a list in opposite order. So I would like to >> know which is the correct behavior, which shows up in the >> interpolation_polynomial doctests. >> >> Best, >> Travis >> >> >> On Thursday, December 20, 2018 at 1:17:38 AM UTC+10, Friedrich Wiemer >> wrote: >>> >>> Is there anyone who used the SBox.interpolation_polynomial? >>> Travis and I found a wird behaviour of the SBox.__call__ regarding >>> finitie field elements as inputs and think that this is a bug.This is fixed >>> in #25633 but it would be nice if someone who used this input (e.g. >>> indirectly with the `interpolation_polynomial` method) could review this >>> change and check if this brakes something? >>> >> -- _pgp: https://keybase.io/martinralbrecht _www: https://martinralbrecht.wordpress.com _jab: martinralbre...@jabber.ccc.de _otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Anyone used SBox.interpolation_polynomial?
Anyone have any thoughts on this? If not, then I will assume that the documentation was the intended behavior. Best, Travis On Sunday, December 23, 2018 at 7:15:00 AM UTC+10, Travis Scrimshaw wrote: > > It has to do more specifically with how GF(2^k) elements are interpreted > by an SBox. The documentation says they are treated differently than the > code, and I wanted to know which was correct. In particular, it was > interpreted in the code as a list in opposite order. So I would like to > know which is the correct behavior, which shows up in the > interpolation_polynomial doctests. > > Best, > Travis > > > On Thursday, December 20, 2018 at 1:17:38 AM UTC+10, Friedrich Wiemer > wrote: >> >> Is there anyone who used the SBox.interpolation_polynomial? >> Travis and I found a wird behaviour of the SBox.__call__ regarding >> finitie field elements as inputs and think that this is a bug.This is fixed >> in #25633 but it would be nice if someone who used this input (e.g. >> indirectly with the `interpolation_polynomial` method) could review this >> change and check if this brakes something? >> > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Anyone used SBox.interpolation_polynomial?
It has to do more specifically with how GF(2^k) elements are interpreted by an SBox. The documentation says they are treated differently than the code, and I wanted to know which was correct. In particular, it was interpreted in the code as a list in opposite order. So I would like to know which is the correct behavior, which shows up in the interpolation_polynomial doctests. Best, Travis On Thursday, December 20, 2018 at 1:17:38 AM UTC+10, Friedrich Wiemer wrote: > > Is there anyone who used the SBox.interpolation_polynomial? > Travis and I found a wird behaviour of the SBox.__call__ regarding > finitie field elements as inputs and think that this is a bug.This is fixed > in #25633 but it would be nice if someone who used this input (e.g. > indirectly with the `interpolation_polynomial` method) could review this > change and check if this brakes something? > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
