Prev: Dynamic Hill cipher
Next: PE Scrambler
From: J.D. on 27 Apr 2010 18:22
Maaartin,

I am still evaluating your new code. In the interim...

On Apr 27, 5:56 pm, Maaartin <grajc...(a)seznam.cz> wrote:
>
> > You don't want the instances to appear in an easy to determine place
> > (e.g. at the very top or bottom of the stack), because then it is
> > trivial to recover the input by just looking at the first or last
> > card.  A deal step would help in that regard, but not as much as you'd
> > think.  e.g. assume an instance of the input always appears at the top
> > or bottom of the deck after the shuffle.  If the hash uses an input-
> > dependent deal like in my program above, then the first card will be
> > moved to within a narrow range.  Look at the cards in that range, and
> > --for each card at position i within the range-- if the amount moved
> > from the start to i is equal to the distance the first card would be
> > moved had that card at i been an instance of the input, then the card
> > at i is probably an instance of the input.
>
> > Your idea of using the card below the first instance to determine deal
> > amounts would (I think) cure that weakness...
>
> I'm not sure if I understand.

OK. Assume that we have a shuffle step that moves an instance of the
input to the top of the deck. If the shuffle step is the only thing
performed, then to determine the input you just look at the first card
of the digest. For example, if you look at the digest and the first
card is the ace of hearts (which is an instance of 'a'), then you can
determine the input (i.e. 'a'). This result holds if the instances
have easily determined places in the resulting digest (whether at the
start or the end or whatever).

Now assume that there is a simple shuffle step that moves an instance
to a determined position (e.g. the top of the deck), but then after
that there is a simple input-dependent deal step (like in my previous
algorithm). In that case, the instance will with certainty be moved
to one of 13 different places in the deck (assuming the deal amounts
vary in the range 2 to 14). Look at all 13 places -- if any card in
one of those positions is "self-justifying" then that is probably the
instance (and hence the input can be determined). A card is "self-
justifying" if it is in the position one would expect it to be had it
been the instance of the input at the top of the deck.

Is that sufficiently clear?
From: Maaartin on 27 Apr 2010 18:37
On Apr 28, 12:03 am, "J.D." <degolyer...(a)yahoo.com> wrote:

> How are you measuring the 'bits change per input'?

He's using a factoradic number system, which is IMHO wrong.

> With an ideal hash function (that outputs a digest in the form of a
> permutation of a deck of cards), changing a single letter of the
> message (at any position in the message) should cause every card to
> change with a probability of --I think-- 0.96 (i.e. 25/26).

I agree. It means that after the step the probability of A in the 1st
position shoulbe be 1/26. It also means that the probability of M
following immediatelly X should be 1/26 as well.

> Also you could look at the average _relative_
> distance between two output characters -- i.e. over many digests, how
> far apart are the ace of spades and the ace of clubs, and is that
> average distance different from what you'd expect given a random
> permutation?

The average distance is fine, and the probability of each distance
(with wrap around) must be 1/26, too.

> How does shuffle_2 compare to a simple shuffle (like my improved
> shuffle in the above response to Maaartin) plus a simple input-
> dependent deal step? That is comparing not just the statistical
> results, but also the efficiency -- moving every other card of the
> interval doesn't seem like it should be that much easier and faster
> than an input dependent deal step.

I'm very curious about the results for mg_shuffle1, I only looked at
it seems to work very well. But a statistical test may come out
differently.


On Apr 28, 12:22 am, "J.D." <degolyer...(a)yahoo.com> wrote:
> > I'm not sure if I understand.
>
> OK. Assume that we have a shuffle step that moves an instance of the
> input to the top of the deck. If the shuffle step is the only thing
> performed, then to determine the input you just look at the first card
> of the digest. For example, if you look at the digest and the first
> card is the ace of hearts (which is an instance of 'a'), then you can
> determine the input (i.e. 'a'). This result holds if the instances
> have easily determined places in the resulting digest (whether at the
> start or the end or whatever).

Right. Unfortunatelly, this problem applies to mg_shuffle1, too.
There's only a final deal (not data-dependent), so the last input
letter always ends in position 17 (counting from 0). A final bury (or
my output procedure) solves the problem. Because of what you write
below, single bury is not sufficient, so I'd suggest multiple buries,
maybe interleaved with deal. Or the output procedure, which is similar
to bury.

> Now assume that there is a simple shuffle step that moves an instance
> to a determined position (e.g. the top of the deck), but then after
> that there is a simple input-dependent deal step (like in my previous
> algorithm). In that case, the instance will with certainty be moved
> to one of 13 different places in the deck (assuming the deal amounts
> vary in the range 2 to 14). Look at all 13 places -- if any card in
> one of those positions is "self-justifying" then that is probably the
> instance (and hence the input can be determined). A card is "self-
> justifying" if it is in the position one would expect it to be had it
> been the instance of the input at the top of the deck.
>
> Is that sufficiently clear?

I think so. Neither in my output procedure nor in bury the position of
a card depends on the card itself (it always depends on another card),
so there;s no self-justifying card, right?
From: J.D. on 27 Apr 2010 18:49
OK, I think I understand Maaartin's new algorithm now (maybe). I am
going to conduct 'field tests' tonight (and maybe tomorrow, depending
on how long it takes to practice and then get enough data) with a pack
of cards to see if I can't get some empirical data with which to
compare the various algorithms. I will be looking at operating speed
(after a bit of practice), as well as accuracy. Is there anything
else I should be looking for?

The three algorithms that I want to test are:
i) bmearn's "shuffle_2" alone -- i.e. where the interval between the
instances is split on an every-other-card basis;
ii) Maaartin's new find_shuffle-bury-find_shuffle + deal algorithm;
iii) and my improved_shuffle + deal algorithm (with the improved
shuffle results in the order: interval-first-tail-second-head)

Are these the versions you guys want tested? Is there something else
you want tested? Also, do you have suggestions for messages to test
the functions with?
From: J.D. on 27 Apr 2010 18:57
On Apr 27, 6:37 pm, Maaartin <grajc...(a)seznam.cz> wrote:
>
> I think so. Neither in my output procedure nor in bury the position of
> a card depends on the card itself (it always depends on another card),
> so there;s no self-justifying card, right?

Hmmm, let me see.

1) find_shuffle results in the first instance being on the top of the
deck,
2) bury moves that instance to the bottom of the deck,
3) results in the second instance at the top of the deck, and the
first instance is no longer at a determinate position.

It seems like the find_shuffle + bury + find_shuffle step should
result in an instance being in a determinate position (the top of the
deck). Maybe I am misunderstanding your algorithm... (in which case
please correct me before I spend a lot of time doing something wrong
by hand)
From: J.D. on 27 Apr 2010 18:58
On Apr 27, 6:57 pm, "J.D." <degolyer...(a)yahoo.com> wrote:
> On Apr 27, 6:37 pm, Maaartin <grajc...(a)seznam.cz> wrote:
>
>
>
> > I think so. Neither in my output procedure nor in bury the position of
> > a card depends on the card itself (it always depends on another card),
> > so there;s no self-justifying card, right?
>
> Hmmm, let me see.
>
> 1) find_shuffle results in the first instance being on the top of the
> deck,
> 2) bury moves that instance to the bottom of the deck,
> 3) results in the second instance at the top of the deck, and the
> first instance is no longer at a determinate position.
>
> It seems like the find_shuffle + bury + find_shuffle step should
> result in an instance being in a determinate position (the top of the
> deck).  Maybe I am misunderstanding your algorithm... (in which case
> please correct me before I spend a lot of time doing something wrong
> by hand)

Er, (3) should start out with "the second find_shuffle results in the
second instance..."
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Prev: Dynamic Hill cipher
Next: PE Scrambler