Re: Looking for algorithm

From: Vedat Hallac (vman_at_black.hole.com)
Date: 02/27/05 

Date: Sun, 27 Feb 2005 18:12:27 +1000

On Tue, 22 Feb 2005 01:32:08 +0000, David Wagner wrote:

I didn't want to start a new thread, so I'm reusing this for the
method I came up with for 6 bits. This is following up on the idea of
using an intermediate field, where multiplication by X is not rotation,
with a few changes: first, I am no longer in GF(2^m), as it proved to be
too hard for me; and second, multiplication by 2 (since I am back to the
trusted GF(97)) is rotation in the first field, but not in the second.

The idea is to first calculate the value of D||C in GF(97), then move the
result into GF(53). If I could find a value, \beta in GF(53) such that
both \beta*2^j mod 97 mod 53 and (53+\beta)*2^j mod 97 mod 53 is \beta
only for j=0,48 or 96, I'm in business. A quick loop in PARI printed a
whole heap of numbers that have this property, the lowest of which was 2.

So, the claim is, if we calculate a checksum, C, such that bin2val(D||C)
mod 97 mod 53 is 2, bin2val(rol(D||C,i)) mod 97 mod 53 is 2 only if i is
either 0, or a multiple of 48. bin2val() is a shorthand notation that says
treat the binary D||C as a big endian 48-bit number, and calculate its
value.

Of course, we need to make sure such a C can be found for all D. I am not
able to think things throughly for some reason, the brain is probably in
Sunday mood, so I'll just post my algorithm for calculating C, and ask if
there is something I am missing. Sorry about that. If we set C to 0, and
calculate DC=bin2val(D||000000) mod 97, and calculate C1=(2-DC) mod 97,
and C2=(2+53-DC) mod 97, first either C1 or C2 would fit in 6 bits,
and second both (DC+C1) mod 97 mod 53, and (DC+C2) mod 97 mod 53 would be
2. So we can use the six bit value as our checksum, C.

I am working in PARI, and it is a bit cumbersome to go through the test
cases, so I validated the above algorithm for only three sets of data
values. I wouldn't trust it enough until it had a good bashing.

Interestingly enough, the smallest prime for which such a \beta value
exists is 37, with \beta=28. I would have expected GF(53) to
be the smallest field in which such a \beta exists (for the obvious
reasons). Since it is not quite 5 bits, I thought it safe to keep things
in GF(53).

I am sure there would be a generalization of this for GF(2^k), but I am
not in any shape to work out the code to find the values for GF(2^6)
today.

Ah, the lengths we go to just to reclaim 1 bit. :-)

Cheers,
vedaT

Relevant Pages

  • =?iso-8859-1?q?Re:_What_does_G=F6dels_Incompleteness_mean_for_the_Working_Mathematician=3F?=
    ... > Axiomatic languages do not lead to contradiction unless we have reason ... > There is no reason to believe that either is the case in Peano ... > algorithm computes an arithmetical relation R, ... theorems, theorems about dimension). ...
    (sci.math)
  • Re: "PenTest" a container file
    ... I consider the fact they are using a private encryption type as a giant red flag for the system. ... There is no reason to use a proprietary system when there are many free algorithms that have been thoroughly examined by the crypto community. ... If I used a slight modification of DES the odds of cracking it in a few weeks without knowledge of the algorithm is pretty slim. ... If you just have the container file and not the app and any associated files, I don't think there is much chance of cracking it, unless they used something horrible like ROT13. ...
    (Pen-Test)
  • Re: An Interesting Problem
    ... But I guess "provenance" will sort it all out. ... modulo 100 checksum does not constitute "derived" work. ... subjective measurements of "originality" of "works" because the true ... either the whole body of logic and reason has to be destroyed in order ...
    (sci.math)
  • RE: System Failure Stop Error
    ... unexpected shutdown of this computer is: System Failure: Stop error ... Reason Code: 0x805000f ... | Timestamp: unavailable ...
    (microsoft.public.windows.server.sbs)
  • Re: how to find rotation angle?
    ... If u got any idea or algorithm, ... The most accurate method of rotation detection is by Fourier ... Yet another good algorithm for estimating rotation angle can be found ...
    (sci.image.processing)