Re: Paper & pencil password algorithm

On 2009-02-26, James Taylor <usenet@xxxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:
Maaartin <grajcar1@xxxxxxxxx> wrote:

Sure, addition alone is linear. Even multiplication alone is (a kind
of) linear (in a different group).

Really? This non-linear quality must be something a bit deeper than I
thought. That's fascinating, I wish I could see how that linear
multiplication works. Seeing that might help me understand the essential
property required for non-linearity.

Okay, let's start with a basic definition: a linear equation is one
that can be written like

a0 + a1*x1 + a2*x2 + a3*x3 + ... = 0,

where the a0, a1, a2, etc. are (scalar) constants, the x1, x2, x3,
etc. are unknown values (which may be scalars or vectors), + denotes
addition and * denotes multiplication.

Problems that can be expressed as systems of such linear equations can
be easily solved, using methods like the one you used in your post, or
more general ones such as Gaussian elimination.

The important point, however, is that + and * don't have to mean the
usual kinds of addition and multiplication -- they just have to obey
the same manipulation rules as normal vector addition and scalar
multiplication do (like the rules that x+y = y+x, x+(y+z) = (x+y)+z,
a*(x+y) = a*x+a*y, a*(b*x) = (ab)*x, x+(-x) = 0 and so on). In
mathematical terms, we want the unknowns to reside in a vector space
over what's called a field, or at least a module over a ring.

For example, instead of treating the unknowns as ordinary numbers and
using ordinary addition and multiplication, we might decide to view
them as vectors of bits and use + to mean XOR. (The constants will
then all have to be just 0 or 1, so multiplication is trivial.) Or we
might treat them as elements of a Galois field, and use that field's
definition of + and *, of which the former, for Galois fields of
characteristic 2, again just happens to correspond to XOR. Or we
might stick to ordinary real numbers after all, but decide that +
actually means multiplication and a*x means x raised to the a-th
power.

Now the point is that we first need to pick definitions for + and *
and then try express the problem we want to solve as a system of
linear equations using them. But if the problem happens to involve,
say, _both_ addition and XOR, then this suddenly gets much harder,
since the fields involved are different and so you can't combine it
all into a single linear system.

(However, for that particular example, do keep in mind that XOR and
normal addition are quite similar operations: for example, 1 XOR 2 = 3
= 1 + 2, and more generally, x + y = x XOR y whenever x AND y = 0.
Thus, it may sometimes be possible to obtain partial, approximate or
probabilistic solutions simply by ignoring the difference -- and in
cryptography, that's often all that's needed.)

--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
.

Relevant Pages

  • Re: Help me sort though some complex math
    ... Such an operation on bytes is called linear mixing and its goal is ... What is a liner map between two GFvector spaces of 128 dimensions? ... again with addition corresponding to XOR. ... bitstrings to other 128-bit bitstrings which is compatible with vector ...
    (sci.math)
  • Re: 8 Bit Random Numbers
    ... "A linear feedback shift register is a shift ... register whose input bit is a linear function of its ... and extra xor. ...
    (sci.electronics.basics)
  • Re: building boolean gates
    ... linear gate is 1 with probability 1/2 whereas the output of a non-linear ... the logic function looks like this: w = OR AND s) ... It is not possible to implement it with XOR and NOT, ...
    (sci.electronics.design)
  • Re: AES Galois Field Inverse
    ... Since the problem statement said "the Galois field used for the AES sbox", ... of expression nesting, then all one needs is a full decoding/mapping ... by using a binary search instead of linear ...
    (sci.crypt)
Quantcast