Cryptography-Digest Digest #318, Volume #13 Wed, 13 Dec 00 00:13:01 EST
Contents:
Re: On using larger substitutions (Tom St Denis)
Re: Request: A Compiled Rijndael DLL Pretty Please :) (Tom St Denis)
Re: What's better CAST in PGP or Blowfish 128bit? (Tom St Denis)
Re: Newbie (Tom St Denis)
Re: What's better CAST in PGP or Blowfish 128bit? (Mathew Hendry)
Re: How to embed a key in executable code? ([EMAIL PROTECTED])
Re: How to embed a key in executable code? (AllanW)
Re: Encrypting messages in images?? (Tim May)
Re: Array shuffling (lcs Mixmaster Remailer)
Security ([EMAIL PROTECTED])
Re: What's better CAST in PGP or Blowfish 128bit? (Tom St Denis)
Re: Security (Tom St Denis)
Re: How to embed a key in executable code? ("Matt Timmermans")
Re: Encrypting messages in images?? (Michael Erskine)
Re: Array shuffling (Benjamin Goldberg)
Re: important programming languages (Allen Ethridge)
Re: important programming languages ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: On using larger substitutions
Date: Wed, 13 Dec 2000 00:05:32 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> Tom St Denis wrote:
> >
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > >
> > > A general 16-bit substitution table is commonly considered
> > > impractical because of the large storage space required,
> > > not to say using a number of such tables. On the other
> > > hand, the technique of Playfair offers extremely compact
> > > storage, though with the trade-off of realizing only very
> > > special substitutions. One could help a bit through using
> > > a version employing two matrices. Further one could
> > > concatenate several Playfairs. In situations where one
> > > could be satisfied with the quality of such substitutions,
> > > the following scheme, which requires some more storage but
> > > is more flexible and straightforward to code, may be of
> > > interest:
> > >
> > > One generates four 8-bit substitution tables. The two
> > > bytes of the given 16 bits are first transformed by the
> > > first two tables respectively. The result is circularly
> > > shifted 4 bits and the remaining two substitution tables
> > > are applied in the same manner.
> >
> > This is vulnerable to differential cryptanalysis very easily if you
are
> > not carefull. Again I would look for 4bit->4bit differences that
state
> > in the same word after the rotate of four bits. That way the
number of
> > active sboxes is minimized.
> >
> > A better idea is todo a MDS where the substitution is done on the
> > input. This way the diffusion is optimal and is less vulnerable to
> > differential cryptanalysis.
>
> Do you want to dynamically choose from the different
> candidate MDS matrices, since the substitution is to
> be a variable one? In the scheme described the 8-bit
> substitution tables can be arbitrarily generated via random
> permutations and all techniques involved are primitive (no
> knowledge of GF required). As said, the underlying goal is
> simplicity rather than achieving an S-box of superb quality.
If it's not the best we know how todo then what's the point?
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Request: A Compiled Rijndael DLL Pretty Please :)
Date: Wed, 13 Dec 2000 00:07:30 GMT
In article <[EMAIL PROTECTED]>,
David Schwartz <[EMAIL PROTECTED]> wrote:
>
> Tom St Denis wrote:
>
> > Well you could take the current Rijndael C source strap a DLLMain
on it
> > and make your own DLL. I could do it in about 30 mins if nobody
else
> > has one handy let me know.
>
> The only reason it would take 30 minutes is because Visual C++
takes 10
> minutes just to fire up.
Well I use LCCwin32 anyways not VC. It takes 10 seconds to compile a
new DLL assuming the source is under 10k lines...
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: What's better CAST in PGP or Blowfish 128bit?
Date: Wed, 13 Dec 2000 00:09:05 GMT
In article <2%tZ5.548$[EMAIL PROTECTED]>,
Ray Dillinger <[EMAIL PROTECTED]> wrote:
>
> Oh yeah, some other stuff I forgot to mention.... When you erase
> cleartext or keys from a hard drive, you have to write over it
> with random data about 20 times so that if someone blackbags the
> hard drive, he can't reconstruct it later from the traces that
> overwritten dox leave on your hard drive. What the digital head
> reads as a 1 or 0, an analog head will read as 0.79947, and someone
> can deduce what was written there up to ten generations before.
This is pure nonsense. If you could in fact retrieve wiped information
then the hard drive is inefficient.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Newbie
Date: Wed, 13 Dec 2000 00:10:22 GMT
In article <LJxZ5.9048$[EMAIL PROTECTED]>,
"Chris" <[EMAIL PROTECTED]> wrote:
> I am also new to cryptography, where and what should I start with (I
have
> done most of the simple ciphers and stuff like that from books)?
Read a few books, read as many previous papers as possible. Get
familar with a programming language preferably C and just keep trying
new ideas.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Mathew Hendry <[EMAIL PROTECTED]>
Subject: Re: What's better CAST in PGP or Blowfish 128bit?
Date: Wed, 13 Dec 2000 01:34:13 +0000
On Wed, 13 Dec 2000 00:09:05 GMT, Tom St Denis <[EMAIL PROTECTED]> wrote:
>If you could in fact retrieve wiped information then the hard drive is
>inefficient.
Are you sure that it isn't?
-- Mat.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: How to embed a key in executable code?
Date: Wed, 13 Dec 2000 02:09:42 GMT
In article <XhhZ5.61647$[EMAIL PROTECTED]>,
"Matt Timmermans" <[EMAIL PROTECTED]> wrote:
[snip Alice figures out what is happening]
> You have not established that this part is feasible. "enough" could
be a
> lot. You have also ommitted the step of isolating the verification
code
> from application functionality, which is not necessarily feasible
either.
It's trivial to prove that Alice knows what the computer did, it's
sitting in front of her. She may need to be very good at reading
assembly to understand it, but she knows wha the computer did. No
matter what was done it can be determined what was done. Given the most
obscure code possible (reference obfuscated code contest), there is
someone who can parse what is happening, if nothing else that person
wrote the program. For every compiled program there is a person that
can take that list of statements, arrange them into a serial order and
tell what was happening. Claims about no algorithm being known that is
polynomial time make no difference to possible/impossible, the presence
of an algorithm proves possible, regardless of the running time.
Reverse engineering is very possible, the engineer is unlikely to
attain an exact copy of the starting code, however a functional
equivalent is all that is necessary.
The trust model is totally screwed, in order to maintain security you
must trust something, the user is corrupted, the computer is controlled
by the user, the disk is controlled by the computer, you long-term
expression of a program is controlled by the disk, the short-term by
the computer. Basically there's a 4 letter word for the condition of
security in this situation, and it's spelled d-e-a-d. With nothing to
trust there is no security.
Joe
Sent via Deja.com
http://www.deja.com/
------------------------------
From: AllanW <[EMAIL PROTECTED]>
Subject: Re: How to embed a key in executable code?
Date: Wed, 13 Dec 2000 02:18:37 GMT
Exactly!
There are only a handful of companies that I will allow to see my
credit card number, and only a very few of them do business through
the Internet. For your demo program -- which I may, or may not
like -- I'm not going to authorize even a 1-cent charge. It's not
that I can't afford 1 cent. But just as you have no reason to trust
me not to give away or sell copies of your program, I have
absolutely no reason to trust you -- and all of your employees, and
everyone at the company that you use to redeem credit card charges,
and so on -- with my personal information.
And that's even before the SPAM issue!
If you want me to buy your product, you'll have to let me find out
how great it is BEFORE you get anything from me. For small vendors
that usually means giving me a demo version, hopefully not very
crippled. And then, IF I like the program, I'll pay for it, but I
still won't give out my E-mail address. I'll send a money order to
your P.O. Box. Even then, if you demand a credit card number, I'm
probably not going to register.
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Okay, Matt, I hear what you are saying "as a technologist," but now
let
> me show you the other side of the coin. I mean this, not to refute
what
> you are saying, but to show the "hidden cost" of this approach.
>
> Each time someone buys software from you, you have to get involved.
You
> have to embed information and upload the file -- then I have to
> laboriously download it over my puny 28.8K modem connection -- and
> already I'm wondering to myself if this product is really good enough
to
> justify all this. Furthermore, all your warnings of the dire things
> that you could (indeed...) do to me if I steal your software -- are
> smacking of the fact that you are openly "calling me a thief and a
> liar." As a fellow-human-being that rubs me the wrong way. It raises
> the fur on my back; it gives me a bottle-brush tail. It makes me spit
> and hiss instead of purr.
>
> And, it's raising the cost and duration of each sale enormously. What
> -if- you sold 20 or 50 or 100 copies per day of your
> suddenly-wildly-successful product? What -if- you discovered a bug
(oh
> my!) and had to re-issue individually-encrypted products to 3,500
> customers at one time? {That's about the number of licensees we have
> today.}
>
> Suddenly your cost-of-sales is going sky-high, and you're annoying
your
> customers which is -never- a good thing to do.
>
> This is one of the reasons why retail stores have this thing called
> "shrink." It's a fancy name for the losses that they incur, and plan
> for, as a result of "the customer is stealing you blind." They know
> that a certain amount of product is -going- to walk out the door.
They
> have a pretty good idea of what percentage of their inventory is going
> to do that. (Obviously software plays by different rules.) There
might
> be more aggressive loss-prevention steps that they -could- take, like
> posting an armed guard at the door to check your receipt as some
> electronics stores in-fact *do*, but there's a cost for that.
>
> >Matt Timmermans wrote:
> > Let's say I sell software over the Web. When you purchase my
software, you
> > give me your name, address, and credit card number. Before
uploading it to
> > you, I will embed your information in the executable. I could use
common
> > optimization techniques to find alternate representations for many
thousands
> > of little bits of code. I could encrypt your information with my
private
> > key, and use secret sharing to expand the result to many thousands
of bits
> > (but I only need a few of them to recover your information). I
then use
> > these bits to select alternate representations for all those little
code
> > bits. I will also write plaintext into the software that gives
your name
> > and address and tells you what I've done.
> >
> > Now, if you copy and distribute my software, I can always tell
where the
> > illegal copies came from. Because I tell you this, it should be
sufficient
> > to dissuade you. If it isn't, and you distribute my software
widely,
> > chances are that I will be able to find a copy, extract your
information,
> > and take you to court.
>
> --
> ------------------------------------------------------------------
> Sundial Services :: Scottsdale, AZ (USA) :: (480) 946-8259
> mailto:[EMAIL PROTECTED] (PGP public key available.)
> > Fast(!), automatic table-repair with two clicks of the mouse!
> > ChimneySweep(R): "Click click, it's fixed!" {tm}
> > http://www.sundialservices.com/products/chimneysweep
>
--
[EMAIL PROTECTED] is a "Spam Magnet," never read.
Please reply in newsgroups only, sorry.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tim May <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc,alt.2600.hacker,alt.security
Subject: Re: Encrypting messages in images??
Date: Tue, 12 Dec 2000 18:53:10 -0800
> [EMAIL PROTECTED] wrote:
>
> > I saw this on a documentary on my plane flight and I cant
> >
> > find my notes on it.
> >
> > A model created a method of embedding messages (like PGP)
> >
> > inside an image so its not obvious the message is encrypted.
> >
> > I remember she is from England and posed nude earlier in her
> >
> > career and she invented this technique I believe.
> >
> > Does anyone have any ideas who she is or where I can
> >
> > find her software, etc.........
Sounds like this poster is talking about Romana Machado, who implemented
a stegonography tool she called "Stego," circa 1993. She had a small
photo in one of the "Girls of the Pac Ten" pictorials, circa the mid-80s.
She based her program on my work on embedding messages in .GIF images,
first outlined here in sci.crypt in around 1990-91.
(www.deja.com has never gone back this far, so I can't confirm this. If
I have a copy of my message archived, it's probably sitting on some 800K
Mac floppy in the bottom of a box somewhere)
I can't prove that others had not done similar work, but I think I was
one of the first. Kevin Kelly, who wrote "Out of Control," has a
description of the idea--and why it was motivated--in his book.
For current programs, do a Web search on "steganography."
Hope this helps.
--Tim May
--
=========:=========:=========:=========:=========:=========:=========:====
Timothy C. May | Crypto Anarchy: encryption, digital money,
ComSec 3DES: 831-728-0152 | anonymous networks, digital pseudonyms, zero
W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets,
"Cyphernomicon" | black markets, collapse of governments.
------------------------------
Date: 13 Dec 2000 03:00:03 -0000
From: lcs Mixmaster Remailer <[EMAIL PROTECTED]>
Subject: Re: Array shuffling
Here is a modran function based on the principles of arithmetic decoding.
It is modified from an article in CACM in 1987, and the code doesn't
look quite right, frankly, but it will give an idea of the basic concepts.
The algorithm is "greedy" and calls next_bit to keep its internal 16 bit
register full, so it tends to be wasteful to that degree. However using
the conventional algorithm to do a 256 element shuffle 100 times it uses
168414 bits, the same as the "perfect" one plus 14 bits for its internal
"read-ahead".
The conventional algorithm looks like:
for( i=0; i<n-1; ++i )
{
int j = i + modran(n-i);
int t = a[i];
a[i] = a[j];
a[j] = t;
}
Here is modran.c:
/* Pseudo Random Number Generator based on Arithmetic Decoding */
/* Based on CACM 1987 */
#define Code_value_bits 16 /* Number of bits in a code value */
#define Top_value (((long)1<<Code_value_bits)-1) /* Largest code value */
#define First_qtr (Top_value/4+1) /* Point after first quarter */
#define Half (2*First_qtr) /* Point after first half */
#define Third_qtr (3*First_qtr) /* Point after third quarter */
/* CURRENT STATE OF THE DECODING. */
static long low, high; /* Ends of current code region */
static long value; /* Current random value, low..high */
/* START DECODING A STREAM OF SYMBOLS. */
init_modran()
{ int i;
value = 0; /* Input bits to fill the */
for (i = 1; i<=Code_value_bits; i++) { /* code value. */
value = 2*value+input_bit();
}
low = 0; /* Full code range. */
high = Top_value;
}
/* Return a value from 0 to n-1 */
int modran(int n)
{ long range; /* Size of current code region */
int ran; /* Value returned */
range = (long)(high-low)+1;
ran = (((long)(value-low)+1)*n-1)/range; /* Find ran in 0..(n-1) */
high = low + (range*(ran+1))/n - 1; /* Narrow the code region */
low = low + (range*ran)/n; /* to that allotted to ran */
for (;;) { /* Loop to get rid of bits. */
if (high<Half) {
/* nothing */ /* Expand low half. */
}
else if (low>=Half) { /* Expand high half. */
value -= Half;
low -= Half; /* Subtract offset to top. */
high -= Half;
}
else if (low>=First_qtr /* Expand middle half. */
&& high<Third_qtr) {
value -= First_qtr;
low -= First_qtr; /* Subtract offset to middle*/
high -= First_qtr;
}
else break; /* Otherwise exit loop. */
low = 2*low;
high = 2*high+1; /* Scale up code range. */
value = 2*value+input_bit(); /* Move in next input bit. */
}
return ran;
}
------------------------------
From: [EMAIL PROTECTED]
Subject: Security
Date: Wed, 13 Dec 2000 03:45:38 GMT
Reply-To: [EMAIL PROTECTED]
1.could u suggest a method in which data can be encrypted & stored in
the database & retrieved by decrypting it...
2.could u propose an architecture(security model) for the following
situation?
say,u have a file(for eg.. )...consider 3 people a,b,c are given access
(credentials vary) to it...
there are 2 people s1,s2 who give the rights to them..
s1 gives half the rights & s2 the remaining.....so for any
transaction,both s1&s2 must agree...it's something like double
locking...
(i.e)say a symmetric key has to be provided to A ,which is of length 50
bits...s1 provides 25 bits & s2 the other 25...only when both s1 & s2
provide the total bits,A can perform any operation..
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: What's better CAST in PGP or Blowfish 128bit?
Date: Wed, 13 Dec 2000 03:58:46 GMT
In article <[EMAIL PROTECTED]>,
Mathew Hendry <[EMAIL PROTECTED]> wrote:
> On Wed, 13 Dec 2000 00:09:05 GMT, Tom St Denis <[EMAIL PROTECTED]>
wrote:
>
> >If you could in fact retrieve wiped information then the hard drive
is
> >inefficient.
>
> Are you sure that it isn't?
If the information is intact despite being overwritten means the
density is not as high as possible. When information is placed to
closely together noise from one cell to another can cause problems.
SImilar ideas revolve around high frequency DC signals on copper wires
(i.e processors).
While I am not a physist (or a good speller) the idea is sound. If
after overwritting the disk you can get the original data the disk is
inefficient.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Security
Date: Wed, 13 Dec 2000 04:00:09 GMT
In article <916rd2$mhu$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> 1.could u suggest a method in which data can be encrypted & stored in
> the database & retrieved by decrypting it...
Who is doing both operations? What platform? What requirements?
> 2.could u propose an architecture(security model) for the following
> situation?
> say,u have a file(for eg.. )...consider 3 people a,b,c are given
access
> (credentials vary) to it...
> there are 2 people s1,s2 who give the rights to them..
> s1 gives half the rights & s2 the remaining.....so for any
> transaction,both s1&s2 must agree...it's something like double
> locking...
> (i.e)say a symmetric key has to be provided to A ,which is of length
50
> bits...s1 provides 25 bits & s2 the other 25...only when both s1 & s2
> provide the total bits,A can perform any operation..
Why not try looking various secret sharing schemes. Threshold
schemes... etc..
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: How to embed a key in executable code?
Date: Wed, 13 Dec 2000 04:14:13 GMT
<[EMAIL PROTECTED]> wrote in message
news:916lp2$i6k$[EMAIL PROTECTED]...
> It's trivial to prove that Alice knows what the computer did, it's
> sitting in front of her.
Yes
> She may need to be very good at reading
> assembly to understand it, but she knows wha the computer did. No
> matter what was done it can be determined what was done.
She knows what the computer did, but it can take a lot more than skill at
reading assembly to understand it. To have the kind of power you attribute
to her, she needs to be able to do things like solve stopping problems --
another thing which is common in practice, even though the problem is known
to be undecidable in general.
This is the crux of our disagreement. My argument is "it is not proven, in
theory, that Alice can do this". You keep saying "yes she can". "yes she
can" does not constitute a proof, and so it does not refute my argument,
even though you have lots of empirical evidence to back you up.
> Given the most
> obscure code possible (reference obfuscated code contest), there is
> someone who can parse what is happening, if nothing else that person
> wrote the program.
No. In my reckless youth I wrote programs that I cannot understand Today
(in programming, too, power accrues more quickly than wisdom ;-). Code that
is well obfuscated by a keyed process that is designed to obfuscate might
very well be incomprehensible to anyone who doesn't have the key.
> Claims about no algorithm being known that is
> polynomial time make no difference to possible/impossible, the presence
> of an algorithm proves possible, regardless of the running time.
P-time matters, because I said "feasible", not "possible" -- reverse
engineering can be infeasible in the same way that finding SHA collisions is
infeasible (It certainly is algorithmically possible, even though noone
could do it). P-time is simply the best working definition of "feasible"
that we have.
> Reverse engineering is very possible, the engineer is unlikely to
> attain an exact copy of the starting code, however a functional
> equivalent is all that is necessary.
Comparing programs for equivalence is also undecidable.
> The trust model is totally screwed, in order to maintain security you
> must trust something, the user is corrupted, the computer is controlled
> by the user, the disk is controlled by the computer, you long-term
> expression of a program is controlled by the disk, the short-term by
> the computer. Basically there's a 4 letter word for the condition of
> security in this situation, and it's spelled d-e-a-d. With nothing to
> trust there is no security.
The trust model is a different question, but that works too. With the
method of embedding personal information, it works because Alice doesn't
want to release the software in its original form. You have to trust the
process that gets you Alice's personal information, but that's outside the
scope of this discussion, and you must trust that Alice doesn't want to go
to jail, which is required for _all_ of our legal protection. We do not
need to trust alice or her computer or her disk -- she can redistribute the
software in its original form if she likes, but that makes it likely that
she will get caught.
We _do_ need to trust that, even with ICE et cetera, and all of the code
available to her, Alice cannot modify the software in such a way that will
preserve its functionality while removing her personal information. There
is no reason, in principle, to dismiss this as impossible.
------------------------------
From: Michael Erskine <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc,alt.2600.hacker,alt.security
Subject: Re: Encrypting messages in images??
Date: Tue, 12 Dec 2000 23:06:17 -0500
David Minodier wrote:
>
> [EMAIL PROTECTED] wrote:
>
> > I saw this on a documentary on my plane flight and I cant
> >
> > find my notes on it.
> >
> > A model created a method of embedding messages (like PGP)
> >
> > inside an image so its not obvious the message is encrypted.
> >
> > I remember she is from England and posed nude earlier in her
> >
> > career and she invented this technique I believe.
> >
> > Does anyone have any ideas who she is or where I can
> >
> > find her software, etc.........
> >
> > thanks in advance!!!!
> >
> > george
> >
> > ====================From the mind of George Lewycky==========
> >
> > http://georgenet.net
> >
> > Sent via Deja.com http://www.deja.com/
> > Before you buy.
>
> Have a look at:
>
> http://www.innovatools.com/software/isecrets/index.htm
>
> You actually hide some text into an image file and encode your text
> with a 5 characters key
> (free download version). Can be quite useful !!!
>
> david.
All you really have to do is write something on the back of a photo
graph with a ball point and then scan it. Instant steganography IF
you have the right graphics processing software and know how to use
it. Start with GIMP.
--
Complexity sux; KISS works. Tim Haynes
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Array shuffling
Date: Wed, 13 Dec 2000 04:51:36 GMT
Mok-Kong Shen wrote:
>
> Benjamin Goldberg wrote:
> >
> > Nondeterministic amount of time to complete means that we cannot
> > garuntee that the number of bits used will have any particular
> > bound, and that the amount of time used will not have any particular
> > bound.
>
> But that means the user would sometimes wait very very long,
> wondering whether there might have been some other errors
> (hardware malfunction etc.) or whether the algorithm indeed
> doesn't terminate within the period that he can afford to
> wait. (Are there cases of real non-termination?) That
> would lead to an acceptance problem, I am afraid. Is the
> the probability of that occuring negligible? Thanks.
>
> M. K. Shen
The probability of it happening is indeed negligible; it's rather like
the chances of an unbiased ranmod(3) taking overly long to terminate.
An algorithm for unbiased ranmod(3) is:
function rand3() {
int x;
do {
x = rand4(); // get 2 random bits
} while( x == 3 );
// x now is in the range 0..2
return x;
}
This takes an unbounded amount of time (and unbounded number of bits),
but *on average* it uses 8/3 bits to get a result. Similarly, a random
2 bucket radix sort takes unbounded time (and number of bits) to
complete, but on average, it takes N*log2(N).
Where do I get the number 8/3 bits? Let n be the average number of
bits.
n = 3/4 * (2) + 1/4 * (2 + n)
// 3/4 of the time, it takes 2 bits.
// 1/4 of the time, it takes 2+n bits.
4n = 3*2 + 2+n
3n = 8
n = 8/3 = 2+2/3
Actually, my algorithm takes somewhat over N*log2(N) bits, because at
any level of the recursion, there is a 2**-M (where M is the size of the
subproblem) chance of partitioning failing, and needing to be redone.
I'm not sure how to figure out precisely how many bits on average it
takes, in terms of N, though I make the attempt here:
To use radix sort on N distinct values, it takes:
b(1) = 0
b(2) = 1
b(N) = (N + b((n+1)/2) + b((n-1)/2))
Where b(N) is the number of bits to sort N items. This comes out to
being b(N)=N*log2(N)
To randomly shuffle N values, it takes:
b(1) = 0
b(2) = 1
b(N) = (1-2**-N) * (N + b((n+1)/2) + b((n-1)/2)) +
(2**-N) * (N + b(b))
I don't know how to solve this set of equations.
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: Allen Ethridge <[EMAIL PROTECTED]>
Subject: Re: important programming languages
Date: Wed, 13 Dec 2000 04:56:16 GMT
On Mon, 11 Dec 2000 10:23:09 -0600, [EMAIL PROTECTED] wrote
(in message <Nb7Z5.96081$[EMAIL PROTECTED]>):
> Tuomas Pellonpera <[EMAIL PROTECTED]> wrote:
>> 5.) Did I miss an important language? (I will be switching to Linux so
>> Visual Basic, for example, is out of the question.)
> LISP. Not for any connection at all to cryptography, but because
> either LISP or scheme will illustrate a different way of looking at
> problems than any of the others, which is never a bad thing.
Crypto in Prolog!
Just a thought.
Programming in multiple languages isn't a bad thing, using the right language
for the right part of the application.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: important programming languages
Date: Wed, 13 Dec 2000 05:02:28 GMT
Allen Ethridge <[EMAIL PROTECTED]> wrote:
>> LISP. Not for any connection at all to cryptography, but because
>> either LISP or scheme will illustrate a different way of looking at
>> problems than any of the others, which is never a bad thing.
> Crypto in Prolog!
Well, personally, I consider anything expressed in LISP to be suitably
well-protected to not need additional encryption. However, I would
have felt remiss not pointing out its important contributions to
computing.
--
Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
** 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
******************************
