Cryptography-Digest Digest #627, Volume #13 Sun, 4 Feb 01 11:13:00 EST
Contents:
Re: New checksum algorithm (Mok-Kong Shen)
Re: New checksum algorithm (Benjamin Goldberg)
Re: New checksum algorithm (Benjamin Goldberg)
Re: Tree algorithm (Ned Scholes)
Re: Silly(?) RC4 question (Paul Crowley)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: New checksum algorithm
Date: Sun, 04 Feb 2001 15:27:53 +0100
Benjamin Goldberg wrote:
>
> Mok-Kong Shen wrote:
> >
> > Benjamin Goldberg wrote:
> > >
> > > Mok-Kong Shen wrote:
> > > >
> > > > Benjamin Goldberg wrote:
> > > > >
> > > > > Terry Ritter wrote:
> > > > > >
> > > > > > Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
> > > > > >
> > > > > > >I like to take this opportunity to ask a question of
> > > > > > >ignorance:
> > > > > > >Why does e.g. CRC-16 use a polynomial of degree 16? (I had
> > > > > > >expected one of degree 15, since that can be represented with
> > > > > > >16 bits, while one of degree 16 can't.) Thanks in advance.
> > > > > >
> > > > > > The remainder from a degree 16 poly is a degree 15 poly, and a
> > > > > > mod 2 deg 15 poly has 16 bits: 15, 14, ... 1, 0.
> > > > >
> > > > > Plus, since the x^16 coefficient is always 1, it never needs to
> > > > > be stored in the variable holding the taps.
> > > >
> > > > However, CRC-16 is geared to 16 bit word size, I suppose.
> > > > So it is clumsy to operate with a 16 degree polynomial,
> > > > isn't it? (How do you do subtraction without considering
> > > > the one bit that you do not have in storage representation
> > > > of the polynomial?)
> > >
> > > Think about how CRC works:
> > > crcvalue = ((crcvalue<<1)+newbit) % polynomial;
> > > Since the max crcvalue is just less than the polynomial, % is never
> > > more than a single subtraction -- and since we are working with
> > > polynomials, not integers, we only subtract when the top bit of
> > > crcvalue was 1. This means, we can change it to the following:
> > >
> > > crcvalue = ((crcvalue<<1) & 0x10000) ?
> > > ((crcvalue<<1)+newbit-polynomial) :
> > > ((crcvalue<<1)+newbit);
> > >
> > > Or, better yet,
> > > crcvalue = (crcvalue & 0x8000) ?
> > > ((crcvalue<<1)+newbit-polynomial) :
> > > ((crcvalue<<1)+newbit);
> > >
> > > Or better yet still:
> > > crcvalue = ((crcvalue<<1)+newbit) -
> > > ((crcvalue&0x8000) ? polynomial : 0);
> > >
> > > I think you can see that on any occasion where we shift a 1 bit out
> > > of crcvalue, we are subtracting polynomial from crcvalue -- and the
> > > x^16 coefficient of the poly is 1, too -- thus these cancel out, and
> > > no data is lost.
> >
> > I was not saying that one can't manage to calculate correctly
> > but that it may be easier with a degree 15 polynomial. For
> > one could then work wordwise (16 bits) instead of taking in
> > each new bit at a time, I guess.
>
> Even if we changed to a degree 15 polynomial, we could not work more
> than one bit at a time. We can precompute tables, true, and work a byte
> at a time, but this is doable regardless of the size of the poly.
Maybe I misunderstood. If we work with words and the 'full'
polynomial can be represented in a word, we could compare
a word with polynomial and subtract if it is not less isn't
it? (If not less, we shouldn't subtract. Compare also below.)
> > BTW, in your first version 0x10000 doesn't work with hardware
> > with word size of 16 bits, I suppose.
>
> True. It was done to demonstrate, theoretically, what happens when a
> crc is calculated.
> > In the second version, what happens when (crcvalue<<1)+newbit with the
> > 17th bit (the one omitted) added in is less 'polynomial' with the 17th
> > bit added in?
>
> Let's pretend that we are working with 17 bit words.
> I only subtract 'polynomial' when the 17th bit is set, not otherwise.
> Since the 17th bit of the poly is also set, this means that no matter
> what, the 17th bit of crcvalue after the update is 0. Do you see why?
Let's imagine the 17th bit were there (both in the polynomial
and in the accumulated bits). You want to subtract only when
the accumulated bits gives a value that is not less than
polynomial. That means that in this situation, when we omit
the 17th bit in both cases, we have to check that for the
remaining 16 bits, the accumulated value is no less
than the 'polynomial' (without the 17th bit) before a
subtraction is performed. I repeat: with the 17th bits
the first value may happen to be smaller than the second.
Subtraction would result in an inappropriate negative value.
Chopping the 17th bits, which are on in both cases, the
situation remains the same. You code doesn't do that check
which I suppose is not o.k. Am I right?
>
> > (I understand here 'polynomial' is without the highest 17th bit.
>
> If we are working with 16 bit words, the poly is without the 17th bit.
> If we are working with words >16 bits, the 17th bit is set.
>
> > I mean one should only subtract when the
> > former quantity is not less than the latter.)
>
> All versions are equivilant.
>
> > Sorry, I can't understand your third version at all. For it says that
> > crcvalue is either 'polynomial' or 0, if I don't err.
>
> No, it says that you either subtract polynomial or 0. Here's the
> original 3rd version:
>
> > > crcvalue = ((crcvalue<<1)+newbit) -
> > > ((crcvalue&0x8000) ? polynomial : 0);
Evidently you had printing errors. This was what I found
in your (original) post of 3rd Feb:
Or better yet still:
crcvalue = ((crcvalue<<1)+newbit) - (crcvalue&0x8000) ?
polynomial : 0;
(I made a guess that requires supplying the least number
of missing parentheses, in accordance with common practice
of automatic syntax error correction.)
>
> Here's another way of stating it:
> if( crcvalue&0x8000 )
> temp = polynomial;
> else
> temp = 0;
> crcvalue = ((crcvalue<<1)+newbit) - temp;
The question of subtraction applies here as with the
second version. See my comment there.
[Note: I responded to your earlier follow-up of 11:14, which
was unintentionally sent by you and had no content. From
the (chance) context, I interpreted your (new?) signature
A solution in hand is worth two in the book.
Who cares about birds and bushes?
as something meaningful to the issue and hence responded.
I subsequently logged out and see your follow-ups of 11:26
and 12:00 only right now.]
M. K. Shen
==========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: New checksum algorithm
Date: Sun, 04 Feb 2001 15:05:44 GMT
Mok-Kong Shen wrote:
>
> Benjamin Goldberg wrote:
> >
> > Mok-Kong Shen wrote:
> > >
> > > Benjamin Goldberg wrote:
> > > >
> > > > Mok-Kong Shen wrote:
> > > > >
> > > > > Benjamin Goldberg wrote:
> > > > > >
> > > > > > Terry Ritter wrote:
> > > > > > >
> > > > > > > Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
> > > > > > >
> > > > > > > > I like to take this opportunity to ask a question of
> > > > > > > > ignorance:
> > > > > > > > Why does e.g. CRC-16 use a polynomial of degree 16? (I
> > > > > > > > had expected one of degree 15, since that can be
> > > > > > > > represented with 16 bits, while one of degree 16 can't.)
> > > > > > > > Thanks in advance.
> > > > > > >
> > > > > > > The remainder from a degree 16 poly is a degree 15 poly,
> > > > > > > and a mod 2 deg 15 poly has 16 bits: 15, 14, ... 1, 0.
> > > > > >
> > > > > > Plus, since the x^16 coefficient is always 1, it never needs
> > > > > > to be stored in the variable holding the taps.
> > > > >
> > > > > However, CRC-16 is geared to 16 bit word size, I suppose.
> > > > > So it is clumsy to operate with a 16 degree polynomial,
> > > > > isn't it? (How do you do subtraction without considering
> > > > > the one bit that you do not have in storage representation
> > > > > of the polynomial?)
> > > >
> > > > Think about how CRC works:
> > > > crcvalue = ((crcvalue<<1)+newbit) % polynomial;
> > > > Since the max crcvalue is just less than the polynomial, % is
> > > > never more than a single subtraction -- and since we are working
> > > > with polynomials, not integers, we only subtract when the top
> > > > bit of crcvalue was 1. This means, we can change it to the
> > > > following:
> > > >
> > > > crcvalue = ((crcvalue<<1) & 0x10000) ?
> > > > ((crcvalue<<1)+newbit-polynomial) :
> > > > ((crcvalue<<1)+newbit);
> > > >
> > > > Or, better yet,
> > > > crcvalue = (crcvalue & 0x8000) ?
> > > > ((crcvalue<<1)+newbit-polynomial) :
> > > > ((crcvalue<<1)+newbit);
> > > >
> > > > Or better yet still:
> > > > crcvalue = ((crcvalue<<1)+newbit) -
> > > > ((crcvalue&0x8000) ? polynomial : 0);
> > > >
> > > > I think you can see that on any occasion where we shift a 1 bit
> > > > out of crcvalue, we are subtracting polynomial from crcvalue --
> > > > and the x^16 coefficient of the poly is 1, too -- thus these
> > > > cancel out, and no data is lost.
> > >
> > > I was not saying that one can't manage to calculate correctly
> > > but that it may be easier with a degree 15 polynomial. For
> > > one could then work wordwise (16 bits) instead of taking in
> > > each new bit at a time, I guess.
> >
> > Even if we changed to a degree 15 polynomial, we could not work more
> > than one bit at a time. We can precompute tables, true, and work a
> > byte at a time, but this is doable regardless of the size of the poly.
>
> Maybe I misunderstood. If we work with words and the 'full'
> polynomial can be represented in a word, we could compare
> a word with polynomial and subtract if it is not less isn't
> it? (If not less, we shouldn't subtract. Compare also below.)
>
> > > BTW, in your first version 0x10000 doesn't work with hardware
> > > with word size of 16 bits, I suppose.
> >
> > True. It was done to demonstrate, theoretically, what happens when a
> > crc is calculated.
>
> > > In the second version, what happens when (crcvalue<<1)+newbit with the
> > > 17th bit (the one omitted) added in is less 'polynomial' with the 17th
> > > bit added in?
> >
> > Let's pretend that we are working with 17 bit words.
> > I only subtract 'polynomial' when the 17th bit is set, not otherwise.
> > Since the 17th bit of the poly is also set, this means that no matter
> > what, the 17th bit of crcvalue after the update is 0. Do you see why?
>
> Let's imagine the 17th bit were there (both in the polynomial
> and in the accumulated bits). You want to subtract only when
> the accumulated bits gives a value that is not less than
> polynomial. That means that in this situation, when we omit
> the 17th bit in both cases, we have to check that for the
> remaining 16 bits, the accumulated value is no less
> than the 'polynomial' (without the 17th bit) before a
> subtraction is performed. I repeat: with the 17th bits
> the first value may happen to be smaller than the second.
> Subtraction would result in an inappropriate negative value.
> Chopping the 17th bits, which are on in both cases, the
> situation remains the same. You code doesn't do that check
> which I suppose is not o.k. Am I right?
>
> >
> > > (I understand here 'polynomial' is without the highest 17th bit.
> >
> > If we are working with 16 bit words, the poly is without the 17th bit.
> > If we are working with words >16 bits, the 17th bit is set.
> >
> > > I mean one should only subtract when the
> > > former quantity is not less than the latter.)
> >
> > All versions are equivilant.
> >
> > > Sorry, I can't understand your third version at all. For it says that
> > > crcvalue is either 'polynomial' or 0, if I don't err.
> >
> > No, it says that you either subtract polynomial or 0. Here's the
> > original 3rd version:
> >
> > > > crcvalue = ((crcvalue<<1)+newbit) -
> > > > ((crcvalue&0x8000) ? polynomial : 0);
>
> Evidently you had printing errors. This was what I found
> in your (original) post of 3rd Feb:
>
> Or better yet still:
> crcvalue = ((crcvalue<<1)+newbit) - (crcvalue&0x8000) ?
> polynomial : 0;
>
> (I made a guess that requires supplying the least number
> of missing parentheses, in accordance with common practice
> of automatic syntax error correction.)
>
> >
> > Here's another way of stating it:
> > if( crcvalue&0x8000 )
> > temp = polynomial;
> > else
> > temp = 0;
> > crcvalue = ((crcvalue<<1)+newbit) - temp;
>
> The question of subtraction applies here as with the
> second version. See my comment there.
>
> [Note: I responded to your earlier follow-up of 11:14, which
> was unintentionally sent by you and had no content. From
> the (chance) context, I interpreted your (new?) signature
>
> A solution in hand is worth two in the book.
> Who cares about birds and bushes?
>
> as something meaningful to the issue and hence responded.
> I subsequently logged out and see your follow-ups of 11:26
> and 12:00 only right now.]
>
> M. K. Shen
> --------------------------
> http://home.t-online.de/home/mok-kong.shen
--
A solution in hand is worth two in the book.
Who cares about birds and bushes?
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: New checksum algorithm
Date: Sun, 04 Feb 2001 15:21:10 GMT
Mok-Kong Shen wrote:
>
> Benjamin Goldberg wrote:
> >
> > Mok-Kong Shen wrote:
> > >
> > > Benjamin Goldberg wrote:
> > > >
> > > > Mok-Kong Shen wrote:
> > > > >
> > > > > Benjamin Goldberg wrote:
> > > > > >
> > > > > > Terry Ritter wrote:
> > > > > > >
> > > > > > > Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
> > > > > > >
> > > > > > > > I like to take this opportunity to ask a question of
> > > > > > > > ignorance:
> > > > > > > > Why does e.g. CRC-16 use a polynomial of degree 16? (I
> > > > > > > > had expected one of degree 15, since that can be
> > > > > > > > represented with 16 bits, while one of degree 16 can't.)
> > > > > > > > Thanks in advance.
> > > > > > >
> > > > > > > The remainder from a degree 16 poly is a degree 15 poly,
> > > > > > > and a mod 2 deg 15 poly has 16 bits: 15, 14, ... 1, 0.
> > > > > >
> > > > > > Plus, since the x^16 coefficient is always 1, it never needs
> > > > > > to be stored in the variable holding the taps.
> > > > >
> > > > > However, CRC-16 is geared to 16 bit word size, I suppose.
> > > > > So it is clumsy to operate with a 16 degree polynomial,
> > > > > isn't it? (How do you do subtraction without considering
> > > > > the one bit that you do not have in storage representation
> > > > > of the polynomial?)
> > > >
> > > > Think about how CRC works:
> > > > crcvalue = ((crcvalue<<1)+newbit) % polynomial;
> > > > Since the max crcvalue is just less than the polynomial, % is
> > > > never more than a single subtraction -- and since we are working
> > > > with polynomials, not integers, we only subtract when the top
> > > > bit of crcvalue was 1. This means, we can change it to the
> > > > following:
> > > >
> > > > crcvalue = ((crcvalue<<1) & 0x10000) ?
> > > > ((crcvalue<<1)+newbit-polynomial) :
> > > > ((crcvalue<<1)+newbit);
> > > >
> > > > Or, better yet,
> > > > crcvalue = (crcvalue & 0x8000) ?
> > > > ((crcvalue<<1)+newbit-polynomial) :
> > > > ((crcvalue<<1)+newbit);
> > > >
> > > > Or better yet still:
> > > > crcvalue = ((crcvalue<<1)+newbit) -
> > > > ((crcvalue&0x8000) ? polynomial : 0);
> > > >
> > > > I think you can see that on any occasion where we shift a 1 bit
> > > > out of crcvalue, we are subtracting polynomial from crcvalue --
> > > > and the x^16 coefficient of the poly is 1, too -- thus these
> > > > cancel out, and no data is lost.
> > >
> > > I was not saying that one can't manage to calculate correctly
> > > but that it may be easier with a degree 15 polynomial. For
> > > one could then work wordwise (16 bits) instead of taking in
> > > each new bit at a time, I guess.
> >
> > Even if we changed to a degree 15 polynomial, we could not work more
> > than one bit at a time. We can precompute tables, true, and work a
> > byte at a time, but this is doable regardless of the size of the
> > poly.
>
> Maybe I misunderstood. If we work with words and the 'full'
> polynomial can be represented in a word, we could compare
> a word with polynomial and subtract if it is not less isn't
> it? (If not less, we shouldn't subtract. Compare also below.)
>
> > > BTW, in your first version 0x10000 doesn't work with hardware
> > > with word size of 16 bits, I suppose.
> >
> > True. It was done to demonstrate, theoretically, what happens when
> > a crc is calculated.
>
> > > In the second version, what happens when (crcvalue<<1)+newbit with
> > > the 17th bit (the one omitted) added in is less 'polynomial' with
> > > the 17th bit added in?
> >
> > Let's pretend that we are working with 17 bit words.
> > I only subtract 'polynomial' when the 17th bit is set, not
> > otherwise. Since the 17th bit of the poly is also set, this means
> > that no matter what, the 17th bit of crcvalue after the update is 0.
> > Do you see why?
>
> Let's imagine the 17th bit were there (both in the polynomial
> and in the accumulated bits). You want to subtract only when
> the accumulated bits gives a value that is not less than
> polynomial. That means that in this situation, when we omit
> the 17th bit in both cases, we have to check that for the
> remaining 16 bits, the accumulated value is no less
> than the 'polynomial' (without the 17th bit) before a
> subtraction is performed. I repeat: with the 17th bits
> the first value may happen to be smaller than the second.
> Subtraction would result in an inappropriate negative value.
When we "subtract" the polynomial, we are actually doing an XOR, not an
integer subtraction. Thus, there is no negative value.
> Chopping the 17th bits, which are on in both cases, the
> situation remains the same. You code doesn't do that check
> which I suppose is not o.k. Am I right?
My code doesn't do a check for "greater than" or "less than," on the
values, only on the orders of the polynomials (ie, is the order of
(crcvalue<<1|newbit) less than or equal to 16). However, since
subtraction is XOR, this is perfectly o.k., so you are wrong.
> > > (I understand here 'polynomial' is without the highest 17th bit.
> >
> > If we are working with 16 bit words, the poly is without the 17th
> > If we are working with words >16 bits, the 17th bit is set.
> >
> > > I mean one should only subtract when the
> > > former quantity is not less than the latter.)
> >
> > All versions are equivilant.
> >
> > > Sorry, I can't understand your third version at all. For it says
> > > that crcvalue is either 'polynomial' or 0, if I don't err.
> >
> > No, it says that you either subtract polynomial or 0. Here's the
> > original 3rd version:
> >
> > > > crcvalue = ((crcvalue<<1)+newbit) -
> > > > ((crcvalue&0x8000) ? polynomial : 0);
>
> Evidently you had printing errors. This was what I found
> in your (original) post of 3rd Feb:
>
> Or better yet still:
> crcvalue = ((crcvalue<<1)+newbit) - (crcvalue&0x8000) ?
> polynomial : 0;
>
> (I made a guess that requires supplying the least number
> of missing parentheses, in accordance with common practice
> of automatic syntax error correction.)
I confess, I did change it when I quoted it, to add the parens. Does it
matter? If we use the order of operations precedence of C and C++, the
two things should be equivilant, right? I mean, isn't (a-b?c:d) the
same as (a-(b?c:d))?
> > Here's another way of stating it:
> > if( crcvalue&0x8000 )
> > temp = polynomial;
> > else
> > temp = 0;
> > crcvalue = ((crcvalue<<1)+newbit) - temp;
>
> The question of subtraction applies here as with the
> second version. See my comment there.
As before, "subtracting" the polynomial is done in GF(2)^m. If I had
called the variable "modulo" rather than "polynomial" then you would be
absolutely right about it possibly becoming negative. But since I
didn't, subtraction is XOR, so no negatives need be worried about.
> [Note: I responded to your earlier follow-up of 11:14, which
> was unintentionally sent by you and had no content. From
> the (chance) context, I interpreted your (new?) signature
>
> A solution in hand is worth two in the book.
> Who cares about birds and bushes?
>
> as something meaningful to the issue and hence responded.
> I subsequently logged out and see your follow-ups of 11:26
> and 12:00 only right now.]
Umm, oops? Sorry, my mistake.
--
A solution in hand is worth two in the book.
Who cares about birds and bushes?
------------------------------
From: Ned Scholes <[EMAIL PROTECTED]>
Subject: Re: Tree algorithm
Date: Sun, 04 Feb 2001 15:39:32 GMT
Thank you everybody for tips and help. Makes one think in other directions
which often leads to a solution.
Here is my algorithm. Maybe not of anybody else's interest, but you know, my
girlfriend isn't interested either and I have to tell somebody...
int minSum; //global variable. saves the cheepest way.
tree(int value,int search,int sum){ //value is the current node, search is
what you want to find, sum is the cost to get there.
//the function is invoked
likte this: tree(1,109,0), if 109 is what you're looking for and 1 is the
root.
if(value==search){ //when the value is found the first
time minSum saves it...
if(sum<minSum)
minSum=sum;
}
else{
if(value<search){
tree(value*3,search,sum+10); //if you go "left" in the tree, sum is
increased by 10.
tree(value+4,search,sum+5); //if you go "right" in the tree, sum is
increased by 5.
}
}
}
Stefan Habenschuss wrote:
> > I'm interested in an algorithm which search through a tree for a special
> >
> > value and then returns the "cheepest" way there.
> > The root is 1 and then there is 2 ways to go
>
> So what you have is a binary tree.
>
> > , one (right) increases the
> >
> > value with 4 and the other (left) multiplicates it with 3.
> > It costs 10 to go left and 5 to go right.
> >
> > Tree(int value, int search, int sum){
> >
> > if(display==search)
> > return sum;
> >
> > if(display>search)
> > return 0;
> >
> > Tree(value*3, search, sum+10);
> > Tree(value+4, search, sum+5);
> > }
> >
>
> Why don't you return the value of your recursive calls like that?
>
> int retsum;
>
> if((retsum = Tree(value*3, search, sum+10)) || (retsum = Tree(value+4,
> search, sum+5)))
> return retsum;
>
> > The function can be invoked like this: Tree(1,109,0), then value=1,
> > search=109, sum=0.
> > This function is only going left as long as poosible and then right,
> > what I need to do is test ALL possible ways.
>
> This is what it will do actually. Maybe you want a breadth first search
> algorithm, which first evaluates all the sums in the same depth, so it
> basically runs like this:
>
> 1
> 2 3
> 4 5 6 7
> ...
>
> The implementation of this is a little more complicated than depth first
> search...
>
> > I'm not asking you to solve this, but I'd be happy to get any tips.
> >
> > Thanks in advance.
> >
>
> Hope this helps...
------------------------------
Subject: Re: Silly(?) RC4 question
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Sun, 04 Feb 2001 16:05:16 GMT
B. Wooster <[EMAIL PROTECTED]> writes:
> Ok, then how about a short message, such as 1K in length. Would it be
> significantly easier to "break" than a message encrypted with the full
> algorithm?
It sounds like you have an application in mind and you're looking for
a cipher that fits. Why don't you describe the application and the
constraints on the cipher and we'll see if we can help?
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
