Cryptography-Digest Digest #749, Volume #9 Tue, 22 Jun 99 14:13:03 EDT
Contents:
Re: Question related to letter frequencies... (Mike Keith)
Re: A different method of encryption ([EMAIL PROTECTED])
Blowfish Variant ([EMAIL PROTECTED])
Re: Arbitrary Huffman tree and weights distribution (was: huffman code length) (Alex
Vinokur)
Re: DES versus Blowfish (Patrick Juola)
Re: Kryptos article ("Renegade")
Re: Why Elliptic Curve Cryptosystem is stronger with shorter key length? (DJohn37050)
Re: DES versus Blowfish ([EMAIL PROTECTED])
Re: Why Elliptic Curve Cryptosystem is stronger with shorter key length? (Medical
Electronics Lab)
Re: Secure broadcast (Medical Electronics Lab)
Re: News Group Folder Empty (Medical Electronics Lab)
Re: Phone scrambler : what encryption used ? (sb5309)
Re: authentication wish list (Medical Electronics Lab)
Re: A different method of encryption ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Mike Keith)
Subject: Re: Question related to letter frequencies...
Date: 22 Jun 1999 16:22:05 GMT
>> It's easy to find a table of letter frequencies for, say, English
>> text. What this is really giving is, for each of the 26 letters,
>> the mean value of the probability density function for that letter.
>
>No. It is an *estimate* of the probabilities of occurrence of each
>letter at a given position in English plaintext *with all context
>disregarded*.
Yes, I understand about "all context disregarded" (so
your statements about digraphs, trigraphs, etc. below are not
relevant to my problem). If I'm given a 10000-letter English text, how
many E's will there be? The letter freq. gives me an
estimate of this, but it will not always be exactly right -
that's where variance comes into play. "Estimate of the prob
of occurrence of each letter" is a synonym for
"mean value of a pdf". So I don't see what's so wrong
about what I wrote up to this point...
In reality, if (for example) you know that a Q has
>just occurred, the likelihood of U being next is very high. And
>there are higher-order correlations. In fact, at the trigraph level
>the distribution is vastly farther from uniformly flat than is the
>case for the individual letter frequencies.
>
>> What I want to know is...what is the actual pdf? Presumably
>> (but I'm just guessing) each of them is Gaussian (or close enough
>> that that's a good approximation) with some mean and variance.
>> 1) Is this true?
>
>No, you're working from the wrong premises here.
>
Then how come Dave Smith e-mailed me the message below?
----
Check "Statistical Methods in Cryptanalysis" by Solomon Kullback. He has lots
of
formulas, charts and graphs (almost 200 pages) discussing the distributions and
how to use them. He shows normal distributions, binomial distributions, Poisson
distributions, multinomial distributions etc. with modifications and
experimental results. Many of his results are approximately Gaussian. There are
charts of expected value and standard deviation of ICs, expected number of
blanks in English text vs. random text, cross correlation values of various
distributions etc.
----
You asked for my application; it is simply this: given an N-letter
unencrypted English text, I want to know what I can say
about how many E's there are (and same for the other 25
letters). Surely I must be able to say more than "well, on
average, there will be so many", mustn't I??
Sounds like the book above has all the answers, but any
further comments are welcome.
Mike Keith
Web site: http://users.aol.com/s6sj7gt/mikehome.htm
(remove post-w letters from e-mail address)
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: A different method of encryption
Date: Tue, 22 Jun 1999 15:09:47 GMT
In article <7ko24e$lht$[EMAIL PROTECTED]>,
"Gene Sokolov" <[EMAIL PROTECTED]> wrote:
> Congratulations! You just reinvented a "one time pad" encryption.
> It really does pay to read books sometimes.
Well actually OTPs are covered in the sci.crypt faq. That's where I
learnt about them anyways. You don't need to buy books to learn about
simple things like OTPs. A book on practical implementations of OTPS
would be a cool seller.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Blowfish Variant
Date: Tue, 22 Jun 1999 15:15:48 GMT
Inspired by the neatoness of the Twofish team I decided to rework
Blowfish into a leaner meaner 64-bit block cipher. I changed the sbox
so it is 4 times smaller, the key setup requires only 9 encryption
steps (plus the time to create the sboxes). The algorithm uses a
bijective F function inspired by Twofish (I don't use a MDS though).
Check it out if you want at
http://mypage.goplay.com/tomstdenis/bv.c
The cipher accepts keys upto 210 bytes (1680 bits). It doesn't occupy
much of the cache so even 486 DX chips should run nice and fast.
Any comments?
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Alex Vinokur <[EMAIL PROTECTED]>
Crossposted-To: comp.compression,alt.comp.compression,sci.math
Subject: Re: Arbitrary Huffman tree and weights distribution (was: huffman code length)
Date: Tue, 22 Jun 1999 14:44:06 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> Alex Vinokur wrote:
>
> >
> > Let W = {w1, w2, ..., w#n} be
> > a non-decreasing sequence of positive numbers:
> > w1 <= w2 <= w3 <= ... <= w#n.
> > The W sequence is called normalized
> > if w1 + w2 + ... + w#n = 1.
> > The W sequence of integers is called 100-normalized
> > if w1 + w2 + ... + w#n = 100.
> >
> > Let T be a Huffman tree for the W sequence.
> >
> > * Level#0
> > /\
> > / \
> > * * Level#1
> > ............
> >
> > * * * * ... * Level#k
> >
> > ............
> >
> > * * * ... * Level#n (Last)
> >
> > (I think) The following conditions must take place for Huffman tree:
> >
> > ---------------------------------------------
> > A-conditions : for each level of Huffman tree
> > ---------------------------------------------
> > Let a1, a2, a3, ..., a#m be nodes of Level#k
> > (a1 is the leftest node on this level,
> > a#m is the rightest node on this level).
> > ---> A-Conditions are : a1 <= a2 <= a3 <= ... <= a#m.
> > ---------------------------------------------
> >
> > ---------------------------------------------
> > B-conditions : for each level of Huffman tree
> > ---------------------------------------------
> > Let Q be a such piece of Huffman tree :
> >
> > * Level#(k-2)
> > /\
> > / \
> > * * Level#(k-1)
> > /\ /\
> > / \ / \
> > a b c d Level#k
> >
> > ---> B-Condition is : (a + b) >= d.
> > ---------------------------------------------
>
> For a Huffman tree that is for a W-sequence of your definition
> than your A-Condition holds (via definition if the nodes are
> ordered that way). But how about an arbitrarily given Huffman tree?
>
> M. K. Shen
>
> M. K. Shen
>
Hi,
Let W be the following sequence : 10 11 15 20
Here are Huffman algorithm stages :
(I think) If the sequences are sorted on each stage
of the Huffman algorithm
then A-Conditions take place.
=======================================================
Example 1.
=========
Stage#0 : 10 11 15 20
Stage#1 : 15 20 (21)
Stage#2 : (21) (35)
Stage#3 : (66)
Note! The sequences are sorted on each stage.
So, A-Conditions take place for this tree.
66
/\
/ \
21 35
/\ /\
/ \ / \
10 11 15 20
###############################################
We can "desort" first two weight
on some (or all) stages of Huffman algorithm.
In this case A-conditions don't take place for Huffman tree.
###############################################
=======================================================
Example 2.
=========
Stage#0 : 11 10 15 20 The sequence isn't sorted
Stage#1 : 20 15 (21) The sequence isn't sorted
Stage#2 : (21) (35) The sequence is sorted
Stage#3 : (66)
Note! There are "desorted" sequences.
So, A-Conditions don't take place for this tree.
66
/\
/ \
21 35
/\ /\
/ \ / \
11 10 20 15
###############################################
(I think) If we use Huffman algorithm with "desorting",
apparently we need to use the weights permutations
on each level to build Conditions like A-Conditions.
By the way, is there any reason to use Huffman algorithm with
"desorting"?
Alex
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: DES versus Blowfish
Date: 22 Jun 1999 12:09:04 -0400
In article <[EMAIL PROTECTED]>,
Bruce Schneier <[EMAIL PROTECTED]> wrote:
>On Tue, 22 Jun 1999 12:25:19 GMT, [EMAIL PROTECTED] wrote:
>>Doesn't Twofish itself have weak (?) whitening keys? Has that been
>>addressed? Is it actually a weakness?
>
>No. There are no weak Twofish keys. Mizra and Murphy published a
>paper showing a property of the whitening keys, but there is no way to
>turn that into an attack. And there are no "weak" keys that cause
>that property to arise.
Does this read "there are no known weak keys," or does it mean
that someone has proven that all keys are equivalently strong?
If the latter, I'd like a reference to the proof for my library.
-kitten
------------------------------
From: "Renegade" <[EMAIL PROTECTED]>
Subject: Re: Kryptos article
Date: Tue, 22 Jun 1999 11:07:26 -0500
> I just got the OK from the NSA Public Affairs Office to mention that,
> by the way: a team of NSA cryppies working in their off hours spent
> most of 1992 on it, finally getting all but the famous final 97 characters
> near the end of the year. There names are still shrouded in mystery, as
> you might guess.
This is another example of how the NSA/IC is years ahead of the private
sector, and operates in complete silence about their accomplishments
(granted, this was a private accomplishment, which only makes it more
interesting that they could have come public and still chose not to).
-Mike
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Why Elliptic Curve Cryptosystem is stronger with shorter key length?
Date: 22 Jun 1999 17:10:56 GMT
Yes, finding that darn mapping is the difficulty. In fact, since ECC using a
cyclic generator, the mapping can be to the intergers under addition mod p, a
prime, where solving the problem is doing a division. The reason the ECDLP is
hard is that it is discrete, not that it is a logarithm.
Recall that NIST has just announced a set of elliptic curves for use within the
US federal government. I really do not think they would do that unless they
thought that ECC was good, they even give a suggested mapping to symmetric key
size, which agrees (broadly) with the known theory, that the known best attack
is a square root attack, that is, fully exponential.
Don Johnson
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: DES versus Blowfish
Date: Tue, 22 Jun 1999 17:03:27 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Bruce Schneier) wrote:
> No. There are no weak Twofish keys. Mizra and Murphy published a
> paper showing a property of the whitening keys, but there is no way to
> turn that into an attack. And there are no "weak" keys that cause
> that property to arise.
No doubt. Thanks for clearing that up.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: Why Elliptic Curve Cryptosystem is stronger with shorter key length?
Date: Tue, 22 Jun 1999 12:04:15 -0500
Teh Yong Wei wrote:
>
> I just started to study ECC recently. Many articles, whitepapers
> mentioned that ECC is much more stronger with shorter key length,
> compare with RSA and DSA. But, I could hardly get any explanation why it
> is lilke this?
>
> Can anyone provide me such information, explanation or website?
You can find an explanation in the book "Implementing Elliptic Curve
Cryptography" which is probably at the level you want. The short
answer is that elliptic curve math is harder than integer math. So
far anyway, that might change someday :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: Secure broadcast
Date: Tue, 22 Jun 1999 12:18:27 -0500
Gene Sokolov wrote:
>
> I have a task of setting up a system to broadcast real time data to the
> clients:
>
> I. Description:
> 1. The data is sold on subscription basis at about US$500/month. A
> 20-minutes delay would cut the value of the data 10 fold. A 2 hour delay
> would make this data nearly worthless.
What about for the attacker? If it takes longer than 2 hours, is the
data worthless to them as well?
> 2. The data is sent through one-way medium (pager), one server -> multiple
> clients. The same data stream is sent to all clients. Clients cannot send
> anything back to the server.
> 3. All clients obtain individual user id/password combination once (for
> example when they sign the contract). Password is about 52 bit long
> (36**10). We assume that our way of distibuting passwords is secure. We also
> assume the password distribution procedure to be difficult/expensive to
> repeat often.
56 bit keys can be cracked in days. Call it 32 hours. A 52 bit key
can be cracked by brute force in 32/16 = 2 hours. You're already
at a marginal limit here, if it's possible you should increase this
key length!!
> II. Goal:
> 1. The data stream should be encrypted in such a way, that brute-force
> decryption is too expensive (I.1).
Is US$250,000 too expensive? If you have 52 bit keys, you're in
trouble here.
> 2. There should be a way to add/remove clients easily. We don't want to
> distribute new passwords every time a client is dropped.
Not a problem, but you'll have to send a session key encrypted with
every possible client's secret key. How many clients will you have
to broadcast to? How much time between broadcasts and how many
broadcasts per hour? You may need multiple channels, but that shouldn't
be too much of a problem (I bet you'd like to have that problem!).
Patience, persistence, truth,
Dr. mike
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: News Group Folder Empty
Date: Tue, 22 Jun 1999 12:34:56 -0500
P&J wrote:
>
> I have never seen this news group without messages. I suspect that
> there is something wrong with my new ISP's news server. Can anybody
> tell me which it is?
>
> Thank you for your help.
Ask your ISP. I suspect nobody has requested
it so far, so they don't store any messages.
Now that you want to see 'em, they may store more.
It also depends on how long they store messages.
Hopefully it's more than 24 hours so you'll have
a chance to read 'em!
Patience, persistence, truth,
Dr. mike
------------------------------
From: sb5309 <[EMAIL PROTECTED]>
Subject: Re: Phone scrambler : what encryption used ?
Date: Wed, 23 Jun 1999 01:05:35 +0800
Hi, thank you.
Lassi Hippeläinen wrote:
> I'm not Dan, but I might help a bit...
>
> A5 is a stream cipher that xors the data with output from a PRNG. Sort
> of pseudo-OTP. The exact algorithm has never been published officially.
> Naturally somebody eventually leaked the information, and soon enough A5
> was found to be less secure than promised.
>
> A5 is not only popular, it is THE algorithm used in GSM and its
> derivatives. Most likely also in the 1900 MHz variant in America.
>
> More information at http://jya.com/crack-a5.htm
>
> -- Lassi
>
> sb5309 wrote:
> >
> > Hi Dan, are you still reading this thread ?
> >
> > Any web link to a description of A5 algorithm ?
> >
> > Thanks.
> >
> > Dan Moschuk wrote:
> >
> > > Last I checked A5 was a popular algorithm in cellular phones (I know it was
> > > quite popular in Europe at least, I don't know if North America uses it).
> > >
> > > Dan
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: authentication wish list
Date: Tue, 22 Jun 1999 12:31:21 -0500
Eric Boesch wrote:
>
> Can one achieve all of these goals simultaneously? All the
> methods I know of fall short.
>
> Shortness: My password is short and easily memorized (a weak secret).
>
> Trustlessness: I need trust no one and no machine, except possibly
> the machine I type my password into. No other person or machine
> knows my password or can otherwise assume my identity.
>
> Transportability: I need only my password in order to authenticate
> myself, as long as I have access to the network and to client
> programs that implement this protocol.
>
> Globality: I can use my password to prove my identity to anyone on the
> network (this may be via the authority of a certifying authority,
> key server, etc.).
>
> Uncrackability: I can detect and stop dictionary/brute-force attacks
> on the password before it becomes compromised. (Brute-force attacks
> on strong secrets, such as random 128-bit keys, are not a problem.)
>
Make it an easily remembered pass phrase, or at least make the
password *not* found in a dictionary! Then, hash that. Use
the hash as your private key. You can do this with elliptic
curve crypto.
In the client program you store all the public key parameters
as well as your own public key. You can recreate your public
key from the generated private key and prove you are the only
one who could know that private key. The calculations are
simple and not too time consuming and there is no need to save
the private key in any non-volitol memory in any form.
I don't know how you'd prevent someone from taking your public
key off line and attempting to brute force find your private key.
You can make the problem intractable, but you can't detect or
stop it.
I'll be happy to explain the math details if you like, but
it's pretty easy to do just about everything you want!
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: A different method of encryption
Date: Tue, 22 Jun 1999 17:06:50 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
> I can think of a good name for the cipher you have invented: we can
> call it the "One-Time Pad". The weaker version could be called the
> "Vigenere cipher".
>
> This reminds me of some ideas I've recently had.
>
> Radio frequencies are in short supply, and thus only a limited number
> of licenses can be issued for the use of frequencies. This has meant
> that mobile phones are expensive, and only used by people in a limited
> number of circumstances.
>
> With today's microchips, I've thought of a clever way to solve this
> problem by using the regular telephone system. People could carry with
> them short-range radio phones that communicate by radio to the nearest
> of a network of automated stations that tie into the phone system.
> When they move out of the range of one station, they are switched over
> to a different frequency to continue their call with the next one.
>
> Since this system divides the area where these phones can be used into
> little areas, one for each automated radio station, we could call
> these devices "cellular phones".
>
> Then, there's the other bright idea I had one day when pushing some
> heavy loads along the floor: instead of just making it easier by
> having the load roll on solid cylinders, which have to be picked up
> from the back and put back in in the front, why not use a larger
> sturdy round thing that can be placed on a pivot to hold it in place?
> I think I'll call this the "wheel".
With the patents on these ideas you would have to be a millionaire!!!
Maybe we could be a little less critical?
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
** 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
******************************
