Cryptography-Digest Digest #774, Volume #12 Mon, 25 Sep 00 20:13:00 EDT
Contents:
Re: Tying Up Loose Ends - Correction (Tim Tyler)
Re: What make a cipher resistent to Differential Cryptanalysis? (Tom St Denis)
Re: What make a cipher resistent to Differential Cryptanalysis? (Tom St Denis)
A Different Kind of Quantum Computer ("A. Melon")
nonlinear decorrelation idea... (tom's learning calculus :)) (Tom St Denis)
Re: On block encrpytion processing with intermediate permutations (Mok-Kong Shen)
Re: What make a cipher resistent to Differential Cryptanalysis? (Mok-Kong Shen)
Re: Question on biases in random-numbers & decompression (Tom St Denis)
Re: What make a cipher resistent to Differential Cryptanalysis? (Mok-Kong Shen)
differnetials... (Tom St Denis)
Re: differnetials... (Tom St Denis)
Re: Question on biases in random-numbers & decompression (Bob Harris)
Re: Question on biases in random-numbers & decompression (Benjamin Goldberg)
Re: Tying Up Loose Ends - Correction (Mok-Kong Shen)
FREEFONE,NO LIMITS (Free service)
Re: rc4 -- repetition length ([EMAIL PROTECTED])
Re: Question on biases in random numbers & decompression (Benjamin Goldberg)
Re: What make a cipher resistent to Differential Cryptanalysis? (Tom St Denis)
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Tying Up Loose Ends - Correction
Reply-To: [EMAIL PROTECTED]
Date: Mon, 25 Sep 2000 22:01:55 GMT
Bryan Olson <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Bryan Olson wrote:
:> : With no attack better than exhaustive
:> : search you have no way to rapidly eliminate any large class of keys.
:>
:> You might well have a method that works much faster than decrypting
:> blocks and analysing the plaintext for known characteristics.
:> The latter might require a number of blocks and take a non-trivial
:> volume of processing.
: Yes, you can work on reducing that constant. The mistake is
: pretending it does something to the keyspace.
It doesn't do anything to the keyspace. This was the point of my attempts
to distinguish the "effective keyspace" from the actual keyspace.
The "effective keyspace" contains the keys that can't be dismissed out
of hand on a priori grounds - and may need further consideration.
I've said if this is likely to rub people up the wrong way then they are
invited to present an alternative concise way of saying operation X
"reduces the effective keyspace by five bits".
To clarify, the "operation X" in question in this instance is something
that allows 31/32 keys to be rapidly rejected on a-priori grounds, without
consideration of the text of the message sent.
I'm reasonably happy with my usage. Yes, one can discuss how much
and what sort of "effect" something needs to be to be described as
"effective" - but this sort of issue seems likely to crop up regardless
of what terminology is used.
:> : The problem is a conceptual error and cannot be fixed by adjusting
:> : terminology.
:>
:> I don't think so - the issue appears to be purely terminological.
: No. The effect of the keyspace is still there. [...]
I don't think I ever said that these keys could be discarded without doing
any work at all.
In fact, *if* the cypher has been broken, being supplied with known
plaintext can sometimes rule out keys en mass, with practically no work.
This would be a case of the "ineffective keyspace" being *extremely*
ineffective ;-)
Of course, normally, one would hope that this is not the case.
: If I give you a thousand bits of Blowfish (448-bit key) ciphertext and
: corresponding plaintext, what's the "effective keyspace"?
Probably very small, to the point of being practically non-existent.
The work required to reject each key is about as small as it can
ever be expected to be, and - in all liklihood - enough information is
supplied to be able to reject all but the correct key.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: What make a cipher resistent to Differential Cryptanalysis?
Date: Mon, 25 Sep 2000 22:18:33 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> Tom St Denis wrote:
> >
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > >
> > > Tom St Denis wrote:
> > > >
> > > > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > > > >
> > > > >
> > > > > "Paul L. Hodgkinson" wrote:
> > > > > >
> > > > > > "Mok-Kong Shen" wrote
> > > > > >
> > > > > > > No practical cipher is absolutely secure.
> > > > > >
> > > > > > Which isn't entirely true.
> > > > > > A one-time pad can be shown to be theoretically unbreakable,
> > which
> > > > requires
> > > > > > a random key of the same length as the message.
> > > > > > Such a pad was used in the Cold War to encrypt
communications
> > > > between Moscow
> > > > > > and Washington, sent by secure courier.
> > > > >
> > > > > The ideal OTP is 'theoretical' and, as you said,
> > > > > 'theoretically' unbreakable. No practical 'ideal' OTP
> > > > > exists (or knowable to be ideal, if given one),
> > > > > however.
> > > >
> > > > Actually an OTP is unconditionally secure if you can't guess my
> > secret
> > > > pad better then a prob of 1/2. If I make a CDROM full of random
> > bits
> > > > (or two, one for either direction) and the CDs *are not*
compromised
> > > > then the communication is *provably* secure until the pads run
out.
> > >
> > > The catch is with the term 'random'. The randomness
> > > required by an ideal OTP, i.e. the exact theoretical
> > > assumptions of it, cannot be absulutely verified for
> > > any given sequence pretended to be an ideal OTP.
> > > That's why an ideal OTP can't be obtained in practice,
> > > even it could exist in the world according to theory.
> >
> > Are you sure about that?
> >
> > In the series "111111111111111" what is the next bit?
>
> I am not sure of whether we are talking about the
> same thing. Given a a source in practice, we have no
> way of absolutely confirming that it satisfies the
> assumptions for generating an ideal OTP. One can
> tell that something does not satisfy being OTP,
> e.g. a code that emits alternatingly O and 1. That
> is, you could give negative answers but never positive
> answers.
It's sufficient to say that YOU cannot guess the next bit then the
cipher is secure.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: What make a cipher resistent to Differential Cryptanalysis?
Date: Mon, 25 Sep 2000 22:19:14 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> Tom St Denis wrote:
> >
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > >
> > > Tom St Denis wrote:
> > > >
> > > > Oh sorry, yes you're right. Let's consider DES with ultra weak
> > sboxes,
> > > > at most you add 8! work to the attack (or 16(8!) if you use
round
> > > > independent reorderings) which is not a heck of alot)
> > >
> > > But how LARGE would be the figure, if each round has a
> > > different ordering? And if one has 16 S-boxes available
> > > for choice?
> >
> > 16! is only 2^44 still not large enough. Plus you need sufficient
> > diffusion to make the cipher work.
>
> The implicit assumption is of course that you have some
> not too bad S-boxes.
Then why reorder them?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: Mon, 25 Sep 2000 15:37:42 -0700
From: "A. Melon" <[EMAIL PROTECTED]>
Subject: A Different Kind of Quantum Computer
Quantum computers can only solve problems in BQP, which is not thought to include
NP-complete problems. Now there is a new type of quantum computer being proposed:
http://xxx.lanl.gov/abs/quant-ph/9910073
The paper claims this could solve NP-complete and sharp-P-complete problems.
No, this isnt the End Of Cryptography As We Know It (EOCAWKI). Even if the claims are
true, it may be impossible to actually build. Even if it is possible to build, it
will be easy to make ciphers that defeat it.
For example, make a random, public, invertible, 27x27 sbox, and distribute it on
CD-ROM. Encrypt a block by applying AES, then passing it through the sbox (in groups
of 27 bits), then applying AES again. The sbox is only 432MB, so it is easy to
distribute. The quantum computer would need millions of qbits to crack it. If
quantum computers reach that size, switch to a bigger sbox on DVD. Mass storage
should easily grow faster than quantum computers.
This new quantum computer would actually be of great benefit to cryptography. Given a
set of axioms and a theorem, such a machine could always find a proof of the theorem,
if a proof exists that fits into the number of qbits you have. We might use it to
prove P!=NP. We might use it to prove that AES+sbox really is secure against quantum
computers. We might use it to discover new cryptosystems with provable security and
efficiency, along with their proof.
Does anyone know whether the claims in that paper are valid?
======================
Brad Parks
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: nonlinear decorrelation idea... (tom's learning calculus :))
Date: Mon, 25 Sep 2000 22:29:37 GMT
Given F(x) = (a/(x+b)) + c in a finite field where n/0 = 0, a != 0 we
have F'(x) = a/(x+b)(x+b) which means the function is differentiated
depending on a and b.
Does this mean that in terms of differential cryptanalysis one must
attack both a and b?
Wouldn't this function be a tad better then the std F(x) = ax + b?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On block encrpytion processing with intermediate permutations
Date: Tue, 26 Sep 2000 00:56:35 +0200
Tom St Denis wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> >I should very much appreciate comments on the following idea:
.............
[snip]
>
> This only will work when
>
> 1) You both have the same PRNG, possibly key derivied, thus the PRNG
> must be salted, or something
If PRNG is used (i.e. instead of using sorting), there
is only one PRNG. In this case I would prefer a secret
seed that is independent of the key of the block cipher.
This of course means that one employs more secret
informations, i.e. using a longer 'effective' key.
> 2) The messages are over several blocks long.
Yes.
> Still you have to consider the possibilty that some halves are not
> mixed as well with the others (i.e disjoint cycles in the shuffling).
> Consider the halves (paired means they go thru a cycle together)
>
> R1: ab cd ef gh
>
> R2: ac be df gh
>
> R3: ae cf db gh
>
> ...gh is never moved...
I understand that gh forms a block. In this case the
gh block is not profited by the permutation, i.e. the
block is processed by the original block algorithm
through all its cycles.
>
> Obviously that's not likely but low diffusion is a probable consequence
> over the entire message with this scheme. It gets worse as the message
> size increases... (more chance that two halves never interact, or
> interact an equal amount of times).
I don't think so. If the message is large, the number
of the parts a, b, etc. become large. In that case
the chance of a pair remain sticking together at the
same location should be lower. If a block consists of
4 words instead of 2 words, there would be a similar
favourable effect.
> It's a neat idea, but not terribly secure I would think.
What would interest me is the question whether employing
permutation could in general be better than block chaining
or not. If not, then the scheme would have no value.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: What make a cipher resistent to Differential Cryptanalysis?
Date: Tue, 26 Sep 2000 01:01:24 +0200
Tom St Denis wrote:
>
> In article <[EMAIL PROTECTED]>,
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> >
> > Tom St Denis wrote:
> > >
> > > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > > >
> > > > Tom St Denis wrote:
> > > > >
> > > > > Oh sorry, yes you're right. Let's consider DES with ultra weak
> > > sboxes,
> > > > > at most you add 8! work to the attack (or 16(8!) if you use
> round
> > > > > independent reorderings) which is not a heck of alot)
> > > >
> > > > But how LARGE would be the figure, if each round has a
> > > > different ordering? And if one has 16 S-boxes available
> > > > for choice?
> > >
> > > 16! is only 2^44 still not large enough. Plus you need sufficient
> > > diffusion to make the cipher work.
> >
> > The implicit assumption is of course that you have some
> > not too bad S-boxes.
>
> Then why reorder them?
With reordered S-boxes, the algorithm is not identical
to the one with the standard ordering. So the opponent
does not 'exactly' know which algorithm he is dealing
with.
M. K. Shen
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Crossposted-To: comp.compression
Subject: Re: Question on biases in random-numbers & decompression
Date: Mon, 25 Sep 2000 22:52:36 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Trevor L. Jackson, III wrote:
> >
> > Bruno Wolff III wrote:
> <snip>
> > >
> > > Since random bits are fairly valuable compared to a few cpu
cycles,
> > > you want to try to extract as much of the randomness as possible
out of
> > > the random bits you get.
> >
> > hrubin has posted on this topic several times. His generator
consumes the the random
> > stream one bit at a time capturing almost all of the entropy of
source in the resulting
> > stream of numbers. I'm sure you can find this on a usenet archive.
>
> Why not just take enough bits from the random bitstream to get a max-
min,
> and add any remainder to the next chunk. E.G., for numbers in the
range 6-10
> take 3 bits modulo 5 and add 6. If the bits were 111 that would give
8 with
> remainder 5 to be added to the next 1 bit chunk.
> Isn't it that simple? What am I missing?
The problem is hte numerical range (6, 7, 8, 9, 10) has five choices,
and three bits gives you eight choices.... so you have to either get
log2(5) bits from the stream or ignore the three bits when their
decimal value is 5 <= x < 8.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: What make a cipher resistent to Differential Cryptanalysis?
Date: Tue, 26 Sep 2000 01:24:29 +0200
Tom St Denis schrieb:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> > Tom St Denis wrote:
> > >
> > > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > > >
> > > > The catch is with the term 'random'. The randomness
> > > > required by an ideal OTP, i.e. the exact theoretical
> > > > assumptions of it, cannot be absulutely verified for
> > > > any given sequence pretended to be an ideal OTP.
> > > > That's why an ideal OTP can't be obtained in practice,
> > > > even it could exist in the world according to theory.
> > >
> > > Are you sure about that?
> > >
> > > In the series "111111111111111" what is the next bit?
> >
> > I am not sure of whether we are talking about the
> > same thing. Given a a source in practice, we have no
> > way of absolutely confirming that it satisfies the
> > assumptions for generating an ideal OTP. One can
> > tell that something does not satisfy being OTP,
> > e.g. a code that emits alternatingly O and 1. That
> > is, you could give negative answers but never positive
> > answers.
>
> It's sufficient to say that YOU cannot guess the next bit then the
> cipher is secure.
Whether I can guess or not doesn't matter much. The
opponent may be able to guess, if the source is not
perfectly random. There is no way to prove perfect
randomness in practice, as discussed often times in
the group.
M. K. Shen
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: differnetials...
Date: Mon, 25 Sep 2000 23:06:39 GMT
Is it true that unless the derivative function is a bijection in the
given field (or ring) that the distribution of differences can never be
ideally low?
Say given (1/x) in GF(2)^8, we have the derivative F'(x) = -1/x^2,
which is not a bijection (I think) in the field. Which is why they
have a DPmax of 4...
Consider F(x) = 2x + c, the derivative is F'(x) = 2, which is clearly
not a bijection and has a very high DPmax...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: differnetials...
Date: Mon, 25 Sep 2000 23:12:51 GMT
In article <8qolpi$oho$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> Is it true that unless the derivative function is a bijection in the
> given field (or ring) that the distribution of differences can never
be
> ideally low?
>
> Say given (1/x) in GF(2)^8, we have the derivative F'(x) = -1/x^2,
> which is not a bijection (I think) in the field. Which is why they
> have a DPmax of 4...
>
> Consider F(x) = 2x + c, the derivative is F'(x) = 2, which is clearly
> not a bijection and has a very high DPmax...
Ok I spelt "Differentials" terribly... but watch this...
x^2 mod 257 is not a bijection since 1^2 = 256^2 (mod 257). which
means different pairs of inputs have the same output differnece (i.e a
difference of '1' is the same as a diff '256') or am I just nuts?
Which of course is hard to tie into the def of DPmax...
Arrg... calculus is all new to me... please help!
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Bob Harris <[EMAIL PROTECTED]>
Crossposted-To: comp.compression,sci.crypt.random-numbers
Subject: Re: Question on biases in random-numbers & decompression
Date: Mon, 25 Sep 2000 19:19:15 -0400
[EMAIL PROTECTED] (Bruno Wolff III) said (among other things):
> To generate a 6 sided roll I generate a number from 0 to 7 by fetching 3 bits
> from /dev/random. If the result is in the range 2 to 7, I return that number
> minus 1. If the result is 0 or 1, I treat that number as the first random bit
> for the next try, and fetch 2 more bits from /dev/random and repeat the
> process.
>
> Since random bits are fairly valuable compared to a few cpu cycles,
> you want to try to extract as much of the randomness as possible out of
> the random bits you get.
This type of process was discussed a few months ago at
http://boards.straightdope.com/sdmb/showthread.php?threadid=25283
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Question on biases in random-numbers & decompression
Date: Mon, 25 Sep 2000 23:25:39 GMT
Terry Ritter wrote:
>
> On Sun, 24 Sep 2000 21:26:07 GMT, in
> <[EMAIL PROTECTED]>, in sci.crypt Benjamin Goldberg
> <[EMAIL PROTECTED]> wrote:
>
> >[...]
> >Does anyone know if this is right, or close to right? And if it
> >isn't, is using an arithmetic (de)coder on the right track to get an
> >unbiased distribution while discarding a minimum amount of random
> >data from the bit stream?
>
> For cryptographic use, I think there is some advantage to simply
> discarding parts of the stream at random, and if that is the way the
> stream is used, so much the better.
If I'm using a TRNG, especially a slow one, it's better to use as much
of the stream as possible. Decimation of the stream is good for making
a PRNG less predictable, but the premise is that I've already got a
stream that's perfectly unpredictable.
--
... perfection has been reached not when there is nothing left to
add, but when there is nothing left to take away. (from RFC 1925)
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Tying Up Loose Ends - Correction
Date: Tue, 26 Sep 2000 01:47:00 +0200
Tim Tyler wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> : Tim Tyler wrote:
>
> :> I was trying to talk about arbitrary-length padding - not just the case of
> :> < 8 bits.
> :>
> :> The more padding there is, the more potential information you're giving
> :> the attacker by using an "inefficient" representation of the length of the
> :> padding.
>
> : For padding to 64 bit block boundary, one needs only
> : maximal 63 bits padding (per message).
>
> I was still wanting to talk about adding "arbitrary" lemngths of padding
> - with the idea being to hide the location of the message, and to conceal
> the length of the message as far as is possible.
>
> A 64-bit block boundary requires 6 bits of length specifier - I'd agree
> that again, this isn't terribly much - even being able to reject 63/64
> keys (which is a very pessimistic worst case) shouldn't normally be the
> end of the world.
>
> : I don't think there is sufficient amount there for predicting the
> : pseudo-random source of the padding [...]
>
> Ah, I was hypothesizing a genuinely random source, and asking what the
> be way of using information from this as padding was, while retaining the
> ability to distinguish the message from the padding.
I am confused. Do you mean you append to some bit sequence
certain number of genuinely random bits and ask whether
the opponent can exactly identify these additional bits?
I guess that he could at least easily miss by one bit
either way.
M. K. Shen
------------------------------
From: Free service <[EMAIL PROTECTED]>
Crossposted-To: sci.electronics.design
Subject: FREEFONE,NO LIMITS
Date: Tue, 26 Sep 2000 02:10:47 +0300
==============6E95325C23151F085BD5C3E4
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
THE BEST PROGRAM PAY NOW 0.80 $ PER HOUR FOR HEAR RADIO,SURF,E-MAILS,
LOOK STOCK AND BETS,PLAY VIDEO AND LIVECAM,HEAR MP3,PLAY GAMES.
HELLO, did you need money ?????????
>clik here to begin to take money <
==============6E95325C23151F085BD5C3E4
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
<i><font size=+1>THE BEST PROGRAM PAY NOW 0.80 $ PER HOUR FOR HEAR
<b><u>RADIO,SURF,E-MAILS,</u></b></font></i>
<br><b><i><u><font size=+1>LOOK STOCK AND BETS,PLAY VIDEO AND LIVECAM,HEAR
MP3,PLAY GAMES.</font></u></i></b>
<p><i><font size=+1>HELLO, did you need money ?????????</font></i>
<br><i><font size=+1></font></i>
<br><i><font size=+1></font></i>
<br>
<p> <a href="http://www.epayvalue.freeservers.com/">>clik here to
begin to take money <</a></html>
==============6E95325C23151F085BD5C3E4==
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: rc4 -- repetition length
Date: Mon, 25 Sep 2000 23:41:00 GMT
In article <8pm8ug$jfk$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> There are cycles in 3-bit rc4 that are of length 2*8. That's shorter
> than the cycles of size 7*8 that are avoided by avoiding i=j, m[i]=1.
>
> I'm looking at 4-bit rc4 now, but its state is too big to search, so I
> probably won't find anything.
Here are some short cycles in 4-bit rc4 other than the 15*16 value
cycles avoided by initialization. They have 5*16 and 6*16 values
respectively.
length = 5 i = 0 j = 10
m = 4 10 1 6 15 2 3 8 11 5 13 12 14 9 0 7
length = 6 i = 0 j = 1
m = 8 2 11 14 1 10 0 13 6 4 12 7 5 3 15 9
I see my code is incrementing i after each step, while I think the
official RC4 increments i before each step. That means i should be 15
in both states above, not 0.
I won't bother searching 5-bit RC4. The set of states is too big
for me to have a reasonable hope of hitting the short cycles.
- Bob Jenkins
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Crossposted-To: com.compression
Subject: Re: Question on biases in random numbers & decompression
Date: Mon, 25 Sep 2000 23:55:55 GMT
SCOTT19U.ZIP_GUY wrote:
>
> [EMAIL PROTECTED] (Tim Tyler) wrote in <[EMAIL PROTECTED]>:
>
> >Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> >
> >: I've GOT a random bitstream, which means random 0s and 1s. What I
> >: want from this get random 0s, 1s, and 2s. I want the arithmetic
> >: encoder to convert from one form to the other.
> >
> >: Since I think that if I were *starting out* with random
> >: (equiprobable) 0s, 1s, and 2s, and *en*coded them with an
> >: arithmetic coder, I *should* get a random bitstream (with 0 and 1
> >: equiprobable), I think that using an arithmetic *de*coder on a
> >: random bitstream should let me producde random 0s, 1s, and 2s.
> >
> >: The reason I want to try this, is that if I take my random
> >: bitstream, and take two bits at a time, getting a number in the
> >: range 0, 1, 2, 3, and discard all 3s to get a number in the desired
> >: (0, 1, 2) range, I'm WASTING 25% of my random bits, AND I might end
> >: up taking an arbitrarily long time to get a single trit. Bleh.
> >: [...]
> >
> >It sounds like using arithemetic decompression routine will do
> >much of what you want.
> >
> >I think you will find you might still wind up taking an arbitrarily
> >long time to get a single trit, though - I don't think there's any
> >way around that without introducing bias.
> >
> >I suspect that your arithmetic compressor will need access to an
> >unbounded quantity of RAM as well in order to be guaranteed to
> >operate correctly.
> >
> >In all, the idea sounds a bit like converting a binary number to base
> >3 (or base n), with the MSBs coming first.
> >
> >If thinking about it this way, consider treating the stream as binary
> >and tertiary (or n-ary) expansions of real numbers between zero and
> >one.
>
> This is ture you have to make some trade off if you want to get
> exactly a random 33% chance at each symbol. You can as I sugguest
> take 2 bits. and use only the first 3 states tossinge the fourth
> state.
Everyone seems to be telling me to take two bits and discard the value
3, and COMPLETELY ignoring the fact that I want to discard as little of
the bitstream as possible.
> Or if you want take 4 bits. then you have 16 states. You can assign
> 15 of them easily since 3*5 = 15 put toss the 16th state and get 4
> bits more.
Hmm:
Method a: use 2 bits at a time, discard 25% of bitstream.
3 trits uses 3*2 bits minimum, 4*2 bits on average.
Method b: use 4 bits at a time, discard 6.25% of bitstream.
3 trits uses 3*4 bits minimum, more on average (but I'm not going to
bother to calculate how much more).
Since I want to discard as little of the stream as possible, why the
HELL would I want to use method b?
> Using an arithmetic coder involves these kind of trade offs
> if you need exactly 33% likelyhood from each symbol. If you don't want
> 33% random but want close use an arithmetic coder where one symbol
> slightly heaver than the other 2. And when the heaver symbol comes up
> shift the weight of it so the next symbol weighs more. This way you
> can get close to 33% random and you don't have to wait forever to get
> a symbol out.
Ugh. That sounds like an especially stupid statement, even for you. I
said I wanted 33% each, and you're telling me how to get something other
than 33% each. I AM willing to take an arbitrarily long time (and use
an arbitrarily large amount of memory) to get a symbol.
> To do this with 2 bit pairs. Assign "0" to 00 "1" to 01 "2" to 10 and
> 11 when a two comes up assign the 11 to symbol "1" you can to this
> with more bits but thought I would explain the idea. You could
> also leave the 11 assigned to the value it was last shifted too
> that when whenever you restart the program you wont get a biasis
> for the first trit being a "2" in case some one is analysising
> the ouputs.
>
> David A. Scott
Obviously you have trouble reading, or perhaps memory problems, since I
said, way back at the start of the thread <sarcasm>TWO whole messages
ago</sarcasm>:
> One way of avoiding wasting my hard-earned random bits would be to use
> a huffman decompressor. The problem with that is that I would get
> something like 50% 0s, 25% 1s, and 25% 2s. NOT what I want. What I
> *WANT* is 33% 0s, 33% 1s, and 33% 2s.
--
... perfection has been reached not when there is nothing left to
add, but when there is nothing left to take away. (from RFC 1925)
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: What make a cipher resistent to Differential Cryptanalysis?
Date: Mon, 25 Sep 2000 23:47:46 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> Tom St Denis wrote:
> >
> > In article <[EMAIL PROTECTED]>,
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > >
> > >
> > > Tom St Denis wrote:
> > > >
> > > > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > > > >
> > > > > Tom St Denis wrote:
> > > > > >
> > > > > > Oh sorry, yes you're right. Let's consider DES with ultra
weak
> > > > sboxes,
> > > > > > at most you add 8! work to the attack (or 16(8!) if you use
> > round
> > > > > > independent reorderings) which is not a heck of alot)
> > > > >
> > > > > But how LARGE would be the figure, if each round has a
> > > > > different ordering? And if one has 16 S-boxes available
> > > > > for choice?
> > > >
> > > > 16! is only 2^44 still not large enough. Plus you need
sufficient
> > > > diffusion to make the cipher work.
> > >
> > > The implicit assumption is of course that you have some
> > > not too bad S-boxes.
> >
> > Then why reorder them?
>
> With reordered S-boxes, the algorithm is not identical
> to the one with the standard ordering. So the opponent
> does not 'exactly' know which algorithm he is dealing
> with.
True, but in DES you would have to use round independent swappings to
make it worth while and it would slow it down considerably.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
