Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Not looking like a fool
37 views
Skip to first unread message
Earl_Colby_Pottinger
Jan 24, 2012, 10:52:04 AM1/24/12
to
Help, I looked at WIKI but can't see the difference between a s-box vs
p-box?
I am looking at the idea of using a series of s-boxes(?) that has an
eight(8) bit input that gives a 23 bit value that is exculsive-ored
with the output of the other s-boxes(?).
There are separate s-boxes(?) for every byte position in the string to
be hashed.
The idea is the resulting hashed value will spread the hits evenly
across the hash_table.
Is this a s-box or p-box?
Yes, it may be a dumb question, but for some reason when I think about
it the answer just seems to skip off my brain.
p-box?
I am looking at the idea of using a series of s-boxes(?) that has an
eight(8) bit input that gives a 23 bit value that is exculsive-ored
with the output of the other s-boxes(?).
There are separate s-boxes(?) for every byte position in the string to
be hashed.
The idea is the resulting hashed value will spread the hits evenly
across the hash_table.
Is this a s-box or p-box?
Yes, it may be a dumb question, but for some reason when I think about
it the answer just seems to skip off my brain.
kg
Jan 24, 2012, 12:33:53 PM1/24/12
to
Earl_Colby_Pottinger <earlcolby...@sympatico.ca> wrote:
>Help, I looked at WIKI but can't see the difference between a s-box vs
>p-box?
I think a permutation box just shuffles the bits around. There is some
>Help, I looked at WIKI but can't see the difference between a s-box vs
>p-box?
function f such that bit j in the output comes from bit f(j) in the input.
A substitution box is just a function, output = f(input).
--
kg
Earl_Colby_Pottinger
Jan 24, 2012, 4:08:01 PM1/24/12
to
On Jan 24, 12:33 pm, kg <kristiag+n...@math.ntnu.no> wrote:
I also get the impression that permutation boxes are fully reversible
as in:
b = permutation(a); c = permutation(b);
At this point a==c. Is this right.
> Earl_Colby_Pottinger <earlcolby.pottin...@sympatico.ca> wrote:
> >Help, I looked at WIKI but can't see the difference between a s-box vs
> >p-box?
>
> I think a permutation box just shuffles the bits around. There is some
> function f such that bit j in the output comes from bit f(j) in the input.
> A substitution box is just a function, output = f(input).
So an input with x bits set will return a result with x bits set?
> >Help, I looked at WIKI but can't see the difference between a s-box vs
> >p-box?
>
> I think a permutation box just shuffles the bits around. There is some
> function f such that bit j in the output comes from bit f(j) in the input.
> A substitution box is just a function, output = f(input).
I also get the impression that permutation boxes are fully reversible
as in:
b = permutation(a); c = permutation(b);
At this point a==c. Is this right.
Greg Rose
Jan 24, 2012, 4:51:16 PM1/24/12
to
In article <4ffdeef7-dd48-42a2...@f14g2000yqe.googlegroups.com>,
Not in general, no. Not all permutations are
self-inverse.
Greg.
--
self-inverse.
Greg.
--
Earl_Colby_Pottinger
Jan 24, 2012, 6:41:43 PM1/24/12
to
So is what I am talking about in the first post a s-box?
Basicly, I am trying to find a fast hash system that distributes the
hash pointers very evenly across the hash entries.
I am trying to think about how best to describe what I want to do.
Basicly, I am trying to find a fast hash system that distributes the
hash pointers very evenly across the hash entries.
I am trying to think about how best to describe what I want to do.
AwlSome Auger
Jan 25, 2012, 2:09:35 AM1/25/12
to
kg
Jan 25, 2012, 4:01:33 AM1/25/12
to
Earl_Colby_Pottinger <earlcolby...@sympatico.ca> wrote:
>On Jan 24, 12:33 pm, kg <kristiag+n...@math.ntnu.no> wrote:
>> Earl_Colby_Pottinger <earlcolby.pottin...@sympatico.ca> wrote:
>> >Help, I looked at WIKI but can't see the difference between a s-box vs
>> >p-box?
>>
>> I think a permutation box just shuffles the bits around. There is some
>> function f such that bit j in the output comes from bit f(j) in the input.
>> A substitution box is just a function, output = f(input).
>
>So an input with x bits set will return a result with x bits set?
My impression is that the number of inputs and outputs can differ
>On Jan 24, 12:33 pm, kg <kristiag+n...@math.ntnu.no> wrote:
>> Earl_Colby_Pottinger <earlcolby.pottin...@sympatico.ca> wrote:
>> >Help, I looked at WIKI but can't see the difference between a s-box vs
>> >p-box?
>>
>> I think a permutation box just shuffles the bits around. There is some
>> function f such that bit j in the output comes from bit f(j) in the input.
>> A substitution box is just a function, output = f(input).
>
>So an input with x bits set will return a result with x bits set?
on a p-box. (Caveat: I don't really do symmetric crypto. Probably,
I should have written p-box and s-box above, not permutation and
substitution box.))
>I also get the impression that permutation boxes are fully reversible
>as in:
>b = permutation(a); c = permutation(b);
>
>At this point a==c. Is this right.
p-boxes can be non-invertible, in which case permutation^-1 does not
exist.
--
kg
tom st denis
Jan 25, 2012, 7:34:18 AM1/25/12
to
On Jan 24, 4:51 pm, g...@nope.ucsd.edu (Greg Rose) wrote:
> In article <4ffdeef7-dd48-42a2-b383-972a289eb...@f14g2000yqe.googlegroups.com>,
you're googling for papers and see that term that's what it means.
Tom
> In article <4ffdeef7-dd48-42a2-b383-972a289eb...@f14g2000yqe.googlegroups.com>,
>
>
>
>
>
>
>
>
>
> Earl_Colby_Pottinger <earlcolby.pottin...@sympatico.ca> wrote:
> >On Jan 24, 12:33 pm, kg <kristiag+n...@math.ntnu.no> wrote:
> >> Earl_Colby_Pottinger <earlcolby.pottin...@sympatico.ca> wrote:
> >> >Help, I looked at WIKI but can't see the difference between a s-box vs
> >> >p-box?
>
> >> I think a permutation box just shuffles the bits around. There is some
> >> function f such that bit j in the output comes from bit f(j) in the input.
> >> A substitution box is just a function, output = f(input).
>
> >So an input with x bits set will return a result with x bits set?
>
> >I also get the impression that permutation boxes are fully reversible
> >as in:
> >b = permutation(a); c = permutation(b);
>
> >At this point a==c. Is this right.
>
> Not in general, no. Not all permutations are
> self-inverse.
Tip for the OP, usually self-inverse is called an "involution." So if
>
>
>
>
>
>
>
>
> Earl_Colby_Pottinger <earlcolby.pottin...@sympatico.ca> wrote:
> >On Jan 24, 12:33 pm, kg <kristiag+n...@math.ntnu.no> wrote:
> >> Earl_Colby_Pottinger <earlcolby.pottin...@sympatico.ca> wrote:
> >> >Help, I looked at WIKI but can't see the difference between a s-box vs
> >> >p-box?
>
> >> I think a permutation box just shuffles the bits around. There is some
> >> function f such that bit j in the output comes from bit f(j) in the input.
> >> A substitution box is just a function, output = f(input).
>
> >So an input with x bits set will return a result with x bits set?
>
> >I also get the impression that permutation boxes are fully reversible
> >as in:
> >b = permutation(a); c = permutation(b);
>
> >At this point a==c. Is this right.
>
> Not in general, no. Not all permutations are
> self-inverse.
you're googling for papers and see that term that's what it means.
Tom
Earl_Colby_Pottinger
Jan 25, 2012, 8:27:11 AM1/25/12
to
On Jan 25, 7:34 am, tom st denis <t...@iahu.ca> wrote:
> Tip for the OP, usually self-inverse is called an "involution." So if
> you're googling for papers and see that term that's what it means.
Thank you. Here I am at 55, semi-retired and I still find I have to
> Tip for the OP, usually self-inverse is called an "involution." So if
> you're googling for papers and see that term that's what it means.
keep learning simple things because there is so much to learn.
Globemaker
Jan 25, 2012, 9:19:24 AM1/25/12
to
On Jan 25, 8:27 am, Earl_Colby_Pottinger
The p-box is a wire crossing.
For DES, the p-box and s-boxes provided "diffusion and confusion". The
p-box is a permutation where a string of bits has its bit values
unchanged but it moves the positions of the bits within the string.
The input size is the same as the output size. The diffusion is
provided so a single bit change will permute over to an s-box that is
different than the s-box being used by adjacent input bits.
For DES, the p-box and s-boxes provided "diffusion and confusion". The
p-box is a permutation where a string of bits has its bit values
unchanged but it moves the positions of the bits within the string.
The input size is the same as the output size. The diffusion is
provided so a single bit change will permute over to an s-box that is
different than the s-box being used by adjacent input bits.
unruh
Jan 25, 2012, 12:06:37 PM1/25/12
to
On 2012-01-25, Globemaker <alanfo...@cabanova.com> wrote:
> On Jan 25, 8:27?am, Earl_Colby_Pottinger
><earlcolby.pottin...@sympatico.ca> wrote:
>> On Jan 25, 7:34?am, tom st denis <t...@iahu.ca> wrote:
>>
>> > Tip for the OP, usually self-inverse is called an "involution." ?So if
does not work. It is a many to 1 non-linear mapping.
> On Jan 25, 8:27?am, Earl_Colby_Pottinger
><earlcolby.pottin...@sympatico.ca> wrote:
>> On Jan 25, 7:34?am, tom st denis <t...@iahu.ca> wrote:
>>
>> > Tip for the OP, usually self-inverse is called an "involution." ?So if
>> > you're googling for papers and see that term that's what it means.
>>
>> Thank you. Here I am at 55, semi-retired and I still find I have to
>> keep learning simple things because there is so much to learn.
>
> The p-box is a wire crossing.
> For DES, the p-box and s-boxes provided "diffusion and confusion". The
> p-box is a permutation where a string of bits has its bit values
> unchanged but it moves the positions of the bits within the string.
> The input size is the same as the output size. The diffusion is
> provided so a single bit change will permute over to an s-box that is
> different than the s-box being used by adjacent input bits.
The s boxes also provide the non-linear element so that linear crypto
>>
>> Thank you. Here I am at 55, semi-retired and I still find I have to
>> keep learning simple things because there is so much to learn.
>
> The p-box is a wire crossing.
> For DES, the p-box and s-boxes provided "diffusion and confusion". The
> p-box is a permutation where a string of bits has its bit values
> unchanged but it moves the positions of the bits within the string.
> The input size is the same as the output size. The diffusion is
> provided so a single bit change will permute over to an s-box that is
> different than the s-box being used by adjacent input bits.
does not work. It is a many to 1 non-linear mapping.
Greg Rose
Jan 25, 2012, 12:59:33 PM1/25/12
to
that's unusual. Most designs, eg AES, the s-boxes
are 1-1. Feistel networks can get away with them
not being invertible, but S-P networks decrypt
using the inverses.
Greg.
--
Joe keane
Jan 30, 2012, 4:08:29 PM1/30/12
to
In article <b999164d-6981-4d38...@c21g2000yqi.googlegroups.com>,
What is needed for a decent-performing hash function is vastly different
from what is needed for a cryptographically secure hash function.
Time for hash table is roughly:
sum[buc = 0..NBUC-1] triangle(size[buc])
I'm almost sure that many more people f--- up by not having a good
resize algorithm than by using a 'not good enough' hash function.
#define FOO_HASH(FOO) ((FOO) >> 7 ^ (FOO) >> 2)
And done, next question please.
Earl_Colby_Pottinger <earlcolby...@sympatico.ca> wrote:
>Basicly, I am trying to find a fast hash system that distributes the
>hash pointers very evenly across the hash entries.
You are in the wrong froup.
>Basicly, I am trying to find a fast hash system that distributes the
>hash pointers very evenly across the hash entries.
What is needed for a decent-performing hash function is vastly different
from what is needed for a cryptographically secure hash function.
Time for hash table is roughly:
sum[buc = 0..NBUC-1] triangle(size[buc])
I'm almost sure that many more people f--- up by not having a good
resize algorithm than by using a 'not good enough' hash function.
#define FOO_HASH(FOO) ((FOO) >> 7 ^ (FOO) >> 2)
And done, next question please.
Greg Rose
Jan 30, 2012, 9:17:04 PM1/30/12
to
bits of FOO, so with very high probability FOO and
FOO+1 will hash to the same bucket.
Greg.
--
Earl_Colby_Pottinger
Feb 1, 2012, 11:26:07 AM2/1/12
to
On Jan 30, 9:17 pm, g...@nope.ucsd.edu (Greg Rose) wrote:
> In article <jg70sc$eh...@reader1.panix.com>, Joe keane <j...@panix.com> wrote:
> >In article <b999164d-6981-4d38-a570-bf1ef3c5b...@c21g2000yqi.googlegroups.com>,
short hand for forum-group? Just asking because either makes sense but
the second one means I am still learning again.
> >What is needed for a decent-performing hash function is vastly different
> >from what is needed for a cryptographically secure hash function.
Depends of what 'decent-performing' means to the person working on the
hash function. In my case to process 160GB of data, the reduction in
collisions is far more important than the speed. I know how to make
very fast hashes including some rolling hash method that keep the
speed up you pay in the number of collisions and under-use of the hash
table space.
> >Time for hash table is roughly:
> > sum[buc = 0..NBUC-1] triangle(size[buc])
triangle = delta? I don't follow. HELP!
> >I'm almost sure that many more people f--- up by not having a good
> >resize algorithm than by using a 'not good enough' hash function.
> > #define FOO_HASH(FOO) ((FOO) >> 7 ^ (FOO) >> 2)
That can't be right, for small valve of FOO it converges to zero.
> >And done, next question please.
Did you leave out anything by chance?
> This seems to discard the two least significant
> bits of FOO, so with very high probability FOO and
> FOO+1 will hash to the same bucket.
I have to agree that this does not look good after looking at it. For
a start if I give a 32 bit value to be hashed, I only get back a 30
bit hashed value. And if I view it as hashing bytes the lowest byte
does not effect the hashed value as much the other bytes. In a good
hash function all input bytes (and bits even) should have equal
effects on the resulting hashed output. Or am I wrong on this too?
> In article <jg70sc$eh...@reader1.panix.com>, Joe keane <j...@panix.com> wrote:
> >In article <b999164d-6981-4d38-a570-bf1ef3c5b...@c21g2000yqi.googlegroups.com>,
> >Earl_Colby_Pottinger <earlcolby.pottin...@sympatico.ca> wrote:
> >>Basicly, I am trying to find a fast hash system that distributes the
> >>hash pointers very evenly across the hash entries.
> >You are in the wrong froup.
Pardon, a question. What is a froup? Is this a simple mistake, or a
> >>Basicly, I am trying to find a fast hash system that distributes the
> >>hash pointers very evenly across the hash entries.
> >You are in the wrong froup.
short hand for forum-group? Just asking because either makes sense but
the second one means I am still learning again.
> >What is needed for a decent-performing hash function is vastly different
> >from what is needed for a cryptographically secure hash function.
hash function. In my case to process 160GB of data, the reduction in
collisions is far more important than the speed. I know how to make
very fast hashes including some rolling hash method that keep the
speed up you pay in the number of collisions and under-use of the hash
table space.
> >Time for hash table is roughly:
> > sum[buc = 0..NBUC-1] triangle(size[buc])
> >I'm almost sure that many more people f--- up by not having a good
> >resize algorithm than by using a 'not good enough' hash function.
> > #define FOO_HASH(FOO) ((FOO) >> 7 ^ (FOO) >> 2)
> >And done, next question please.
> This seems to discard the two least significant
> bits of FOO, so with very high probability FOO and
> FOO+1 will hash to the same bucket.
a start if I give a 32 bit value to be hashed, I only get back a 30
bit hashed value. And if I view it as hashing bytes the lowest byte
does not effect the hashed value as much the other bytes. In a good
hash function all input bytes (and bits even) should have equal
effects on the resulting hashed output. Or am I wrong on this too?
Joe keane
Feb 1, 2012, 11:46:14 AM2/1/12
to
In article <jg7iv0$ouq$1...@ihnp4.ucsd.edu>, Greg Rose <g...@nope.ucsd.edu> wrote:
>This seems to discard the two least significant
>bits of FOO, so with very high probability FOO and
>FOO+1 will hash to the same bucket.
Change to:
>This seems to discard the two least significant
>bits of FOO, so with very high probability FOO and
>FOO+1 will hash to the same bucket.
#define FOO_HASH(FOO) ((FOO) >> 5 ^ (FOO))
The other version is for a pointer, where we know the lowest two bits
are zero and useless. I should have explained that.
Earl_Colby_Pottinger
Feb 1, 2012, 6:17:23 PM2/1/12
to
On Feb 1, 11:46 am, j...@panix.com (Joe keane) wrote:
> Change to: #define FOO_HASH(FOO) ((FOO) >> 5 ^ (FOO))
> The other version is for a pointer, where we know the lowest two bits
> are zero and useless. I should have explained that.
Ok, thanks. I see your idea but hashing to create directly a pointer
> Change to: #define FOO_HASH(FOO) ((FOO) >> 5 ^ (FOO))
> The other version is for a pointer, where we know the lowest two bits
> are zero and useless. I should have explained that.
would not had been my first guess.
Anyway, I am not processing lots of text in the 160GB (probably 10-15%
is text) so I don't expect this to be a good mixer.
Please don't take this wrong, I plan to test a number of hashing
methods and I will include your's too. And face it you may end up
with the last laugh if your's works out best or near best anyway.
I promise to post the results by the end of next month (feb.) or tell
you why not,
VelCrowPhly
Feb 2, 2012, 12:16:50 AM2/2/12
to
On Tue, 31 Jan 2012 02:17:04 +0000 (UTC), g...@nope.ucsd.edu (Greg Rose)
wrote:
So, does that mean that he FOOked up?
wrote:
Mycelium
Feb 2, 2012, 12:26:23 AM2/2/12
to
FigureItOut
Feb 2, 2012, 12:38:24 AM2/2/12
to
Earl_Colby_Pottinger
Feb 2, 2012, 9:50:43 AM2/2/12
to
On Feb 2, 12:38 am, FigureItOut <LocusPo...@magicregion.org> wrote:
> On Wed, 01 Feb 2012 21:26:23 -0800, Mycelium
> <mycel...@thematrixattheendofthemushroomstem.org> wrote:
> >On Wed, 01 Feb 2012 21:16:50 -0800, VelCrowPhly
> ><VelCrowP...@thetiethatbindsUall.org> wrote:
> >> So, does that mean that he FOOked up?
weird side, or a lot older than me ie nursing home old! :)
I mean, cartoons from the 1930's I was not even born till 1956, my
brain can't handle how they thought that far back in time. :)
Did you guys grow up reading this stuff? It would explain a lot. :)
> On Wed, 01 Feb 2012 21:26:23 -0800, Mycelium
> <mycel...@thematrixattheendofthemushroomstem.org> wrote:
> >On Wed, 01 Feb 2012 21:16:50 -0800, VelCrowPhly
> ><VelCrowP...@thetiethatbindsUall.org> wrote:
> >> So, does that mean that he FOOked up?
> He FOOked around a lot!
Okay, I am trying to figure out if you guys are just a little on the
weird side, or a lot older than me ie nursing home old! :)
I mean, cartoons from the 1930's I was not even born till 1956, my
brain can't handle how they thought that far back in time. :)
Did you guys grow up reading this stuff? It would explain a lot. :)
FigureItOut
Feb 2, 2012, 9:08:34 PM2/2/12
to
and the comic strip is one of the earliest uses of the term.
Modern times it gets used as it was here, as a non-descript variable
name, etc.
Then, there is Mr. T.
WTShaw
Feb 2, 2012, 11:29:42 PM2/2/12
to
On Jan 25, 7:27 am, Earl_Colby_Pottinger
Involution can have different meanings, like if the enigma you are
dealing with has a uterus.
Self-solving would be a good term for a process that after
recursion(s) goes home again on its own. While self-solving would be
fine as a description of a simple reflexive processing like used with
ROT13, recursion suggests to me something likely to have many
intermediate values. Having a certain number of stages involved in
true recursion would depend on the algorithm and perhaps the nature of
the beginning seed itself whereas an attempt at recursion that fails
might result in a trailing off of variations of the data or entry into
a closed loop that short-circuits attempts to return to the original
data. Maybe reflexive is a good word for the most simple recursions/
involution, etc.
Sharing meanings sometimes can be tautological or even result in
ambiguous interpretations especially when customized jargon is used or
short-cut truncations of essential adjective modifiers helps create a
muddle. Being succinct is desirable if clarity is assured but the
lazy way is to be neither succinct nor definitive. Lots of luck
rolling your own or forcing others to adopt your preferences. I have
to coin some expressions sometimes when at a loss for obvious terms.
Remember, the most basic concept of entropy can have opposite meanings
in different disciplines. As an umpire, Google itself is usually my
most useful aid.
dealing with has a uterus.
Self-solving would be a good term for a process that after
recursion(s) goes home again on its own. While self-solving would be
fine as a description of a simple reflexive processing like used with
ROT13, recursion suggests to me something likely to have many
intermediate values. Having a certain number of stages involved in
true recursion would depend on the algorithm and perhaps the nature of
the beginning seed itself whereas an attempt at recursion that fails
might result in a trailing off of variations of the data or entry into
a closed loop that short-circuits attempts to return to the original
data. Maybe reflexive is a good word for the most simple recursions/
involution, etc.
Sharing meanings sometimes can be tautological or even result in
ambiguous interpretations especially when customized jargon is used or
short-cut truncations of essential adjective modifiers helps create a
muddle. Being succinct is desirable if clarity is assured but the
lazy way is to be neither succinct nor definitive. Lots of luck
rolling your own or forcing others to adopt your preferences. I have
to coin some expressions sometimes when at a loss for obvious terms.
Remember, the most basic concept of entropy can have opposite meanings
in different disciplines. As an umpire, Google itself is usually my
most useful aid.
0 new messages