Re: C code of PEARL1, a block encryption algorithm emphasising simplicity

Maaartin wrote:
Mok-Kong Shen wrote:
It is well known that a system of linear equations doesn't have a
determined solution, if the determinant is zero. I am making use
essentially of an akin argument. If one thus can't even find a "path"
to the generation process of a PRNG, how could one start to break it
at all?

There's no established cryptosystem build on a zero-determinant matrix
and I'd say, there can't be any. Given enough input/output pairs you
always get enough equations. When the determinant is zero, it means
there are equivalent keys, and this is a weakness. The attacker can't
determine the key uniquely, but they don't need to; each one of them

I was employing for conveninece an analogy whose name everybody knows.
Actually in the present case the issue is well-known in linear algebra.
If one has less equations than variables, then the system is simply
indeterminate. (It's a consideration of ranks, if my poor math doesn't
betray me.) But see below.

BTW, a historical remark: Actually the idea of exploiting
"indeterminancy" was present in a thread months ago, where I argued
with Maaatin whether a simple scheme of mine could be cracked. Maaartin
wrote a program which he reported to be capable of very speedily
breaking that in some 10 of test cases. There should however be in fact
nonetheless some errors in his work. For there was a negotiation of a
challenge prize between him and me and my challlenge offer was later
not taken up by him.

There were no errors in my program, it just took too long in some
cases. Most instances were solved much faster than you'd imagine. To
my surprise, the hard instances were the ones NOT having the maximum

I never cared about the challlenge, but I'll publish the program some

The challenge is no longer relevant. So you could certainly reveal now,
for the interest of readers, with a couple of lines at least the
"strategy" you employed to attack that scheme, don't you? IMHO, if your
program worked right, that would have been a basic contradiction to the
indeterminancy issue.

M. K. Shen


Relevant Pages

  • Re: help: how to find all zero roots of a non-linear equation in a given interval
    ... certain that this equation has at least one zero root in the interval ... the values of the derivative of the det on subintervals: ... you must evaluate the determinant using a stable matrix decomposition, ... the householder qr-decomposition (each householder reflector introduces a sign ...
  • Re: problem regarding optimization theory
    ... is not my required solution) because the determinant of the solution ... is non zero which means that the only solution could be the all ... IMHO you should look at closing the solution space ...
  • Re: determinant question
    ... >> zero determinant. ... >of both zero and nonzero determinant. ... >> subspace contained in the variety of matrices of determinant zero. ... generated by fewer than n linear polynomials in those variables. ...
  • Re: a big limit of mathematica?
    ... Mathematica's numerical model has been criticized by several people, ... In fact, the determinant of the 10x10, 20x20 etc all come out exactly 0. ... In Matlab the result will ... the 10X10 determinant is exactly zero. ...
  • Re: determinant of magic square in matlab 2010a
    ... Thank you very much for exhaustive explanation of numerical algorithm. ... Why do the previous versions give exact "zero"? ... Is the newest 2010a using a different algorithm for calculating determinant? ... MATLAB uses a better scheme. ...