Cryptography-Digest Digest #709, Volume #12 Mon, 18 Sep 00 14:13:01 EDT
Contents:
Re: Hamming weight (SCOTT19U.ZIP_GUY)
Re: QUESTION ABOUT ALGORITHMS (SCOTT19U.ZIP_GUY)
Re: Disappearing Email redux ("Richard Bristow")
Re: QUESTION ABOUT ALGORITHMS (Runu Knips)
Re: non-linear decorrelation? (Mike Rosing)
Re: Optimization for speed question. ("Dann Corbit")
Re: Chosen and known attacks - are they possible ?? (Mok-Kong Shen)
Re: wince encryption algorithm (Mok-Kong Shen)
Re: On secret Huffman compression (Mok-Kong Shen)
Re: Double Encryption Illegal? (Mok-Kong Shen)
Re: Intel's 1.13 MHZ chip (Mok-Kong Shen)
Re: QUESTION ABOUT ALGORITHMS (Terry Ritter)
Re: Dangers of using same public key for encryption and signatures? (Mike Rosing)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Hamming weight
Date: 18 Sep 2000 17:01:50 GMT
[EMAIL PROTECTED] (Francois Grieu) wrote in <fgrieu-
[EMAIL PROTECTED]>:
>"kihdip" <[EMAIL PROTECTED]> asked
>
>> an exact definition of 'Hamming weight' ??
>
>The Hamming weight of a bit string (or non-negative integer) is the
>number of bits set in the string (or in the binary representation of the
>non-negative integer).
>
>The Hamming weight of the string 10001 is 2.
>The Hamming weight of the integer 19 is 3.
>
>The Hamming distance of two bit strings is the Hamming weight of their
>exclusive-OR. This verifies the usual distance properties.
>
>A fast, one-line C implementation (find how it works !)
>
>int h(unsigned long x){int w;for(w=0;x;x&=x-1)w++;return w;}
>
>
>Francois Grieu
Francois I liked your C code implimentation. But I was wondering
when you talk about hamming weight and a string of bits. Are you
limiting your self to only strings that have 8bit length units or
are your talking about any string of bits.
If one is talking in the abstract of "any string" of bits.
is that a finite sting of bits or a bit string of an infinite
number of bits the trailing being all zero.
The reason I ask is if one assigns the Hamming weight to sting
of all bits in an infinite finitly odd file. And since one can
easily describe a transform from the finitely odd file state to
any bit size block file system one chooses. It might have a wider
use than if only applied to 8 bit block length files. This is
especailly ture now that encryption block lenght seems to be getting
longer.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: QUESTION ABOUT ALGORITHMS
Date: 18 Sep 2000 17:08:37 GMT
[EMAIL PROTECTED] (Terry Ritter) wrote in <[EMAIL PROTECTED]>:
>
>On Mon, 18 Sep 2000 13:39:05 +0200, in <[EMAIL PROTECTED]>, in
>sci.crypt Runu Knips <[EMAIL PROTECTED]> wrote:
>
>>Melinda Harris wrote:
>>> Can anyone tell me how to patent an algorithm. Where to go.
>>
>>Guess what - patent office.
>>
>>> What to sign and how much it costs???
>>
>>Well their formulas and it costs AFAIK much. I've heard
>>60.000 deutschmarks for a europe-wide patent for a year.
>>
>>But if you want to patent a cryptographic algorithm, you're
>>either a moron or an idiot. A moron if you want to sell
>>to people what you know they can get for free, or an idiot
>>if you think there are not already enough free algorithms.
>>
>>> Any response would be greatly appreciated
>>
>>Hardly. I've insulted you.
>
>You may have insulted more than you know. For example, I currently
>hold three (3) US patents on fundamental cryptographic technology.
>Presumably others have patents as well.
>
>---
>Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
>Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
>
Terry I realize your are most likely better at crypto than
Mr BS. But he is the media darling and unfortunutly you are
not. But a question that might be in most people's mind is how
much did the three of these patents cost. And in the long run
did you make more money with these methods than if you did not
patent them. Did you even possibly lose money since maybe the
methods were not blessed by some media made phony crypto guru.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: "Richard Bristow" <[EMAIL PROTECTED]>
Crossposted-To: alt.privacy,uk.legal
Subject: Re: Disappearing Email redux
Date: Mon, 18 Sep 2000 15:14:12 +0100
Where is the legal content in this?
"David Rush" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tommy the Terrorist <[EMAIL PROTECTED]> writes:
> > In other words, when an NSA listening post or CIA tap on the Internet
> > (such as the one across the street from the AOL Reston facility that all
> > AOL traffic passes through)
>
> Do you have evidence of this, or are you just speaking from a healthy
> sense of paranoia about a 'media' provider which believes that
> centralized servers provide the best 'internet' service?
>
> I am a more than slightly interested party, but can't say more in an
> open forum.
>
> david rush
> -----BEGIN GEEK CODE BLOCK-----
> Version 3.12
> GCS d? s-: a C++$ ULSAH+++$ P+(---) L++ E+++ W+(--) N++ K w(---) O++@
> PS+++(--) PE(++) Y+ PGP !tv b+++ DI++ D+(--) e*(+++>+++) h---- r+++
> z++++
> -----END GEEK CODE BLOCK-----
------------------------------
Date: Mon, 18 Sep 2000 19:36:53 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: QUESTION ABOUT ALGORITHMS
Terry Ritter wrote:
> On Mon, 18 Sep 2000 13:39:05 +0200, in <[EMAIL PROTECTED]>, in
> sci.crypt Runu Knips <[EMAIL PROTECTED]> wrote:
> >Melinda Harris wrote:
> >> What to sign and how much it costs???
> >
> >But if you want to patent a cryptographic algorithm, you're
> >either a moron or an idiot. A moron if you want to sell
> >to people what you know they can get for free, or an idiot
> >if you think there are not already enough free algorithms.
> >
> >> Any response would be greatly appreciated
> >
> >Hardly. I've insulted you.
>
> You may have insulted more than you know. For example, I currently
> hold three (3) US patents on fundamental cryptographic technology.
> Presumably others have patents as well.
Yep. Patents make me furious.
Sorry, I hate the idea that one can own thoughts. And the
patent issue is becoming more and more absurd, see the
human genome. Patenting DNA ! What a braindamaged idea !!!
I'm gonna get a patent on breathing and soon will be
richer than Bill Gates ;-(((
Fortunately I neither live in USA nor need your patents.
As I've already stated in my original posting :-)
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: non-linear decorrelation?
Date: Mon, 18 Sep 2000 12:38:20 -0500
Tom St Denis wrote:
>
> Change that simply to F(x) = a/x + b and we are all set (a!=0 1/0 = 0).
>
> Similarly if the inversion was precomputed as S[] then the function
> would resemble
>
> y = (a * S[x]) + b
Now you've got something interesting :-) S[x] can be any non-linear function.
1/x is one possibility. If you can precompute the table, you can make it as
complicated as you like, or have time for. 1/x^3 + x^5 for example.
You still need a way of checking the possible attack methods and some idea
of input vs. output distributions. It would be very interesting to see which
non-linear functions are easy to attack (so everybody will know to avoid them!)
Patience, persistence, truth,
Dr. mike
------------------------------
From: "Dann Corbit" <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.c
Subject: Re: Optimization for speed question.
Date: Mon, 18 Sep 2000 10:49:04 -0700
"Tor Rustad" <[EMAIL PROTECTED]> wrote in message
news:tssx5.3062$[EMAIL PROTECTED]...
> "Dik T. Winter" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> > In article <RFIw5.1529$[EMAIL PROTECTED]> "Tor Rustad"
> <[EMAIL PROTECTED]> writes:
> > > "Dik T. Winter" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > > > Indeed. But sometimes you have to be sure you have indeed primes,
say
> when
> > > > you prepare parts of the Cunningham tables that contain
factorisations of
> > > > some special numbers.
> > >
> > > I think you missed my point, a computer is a very deterministic piece
of
> HW,
> > > but there is a non-zero probability that it will produce incorrect
results
> > > due to i.e. HW failures. In addition even CPU's has bugs!
> >
> > Do you think I did not know that? That program detected a bug in one of
the
> > Cray instructions (half precision rounded multiply). See also further
down.
>
> There are a lot of things I don't know, one of them for shure is what you
know
> ;-)
>
> Fine achivement to locate a CPU bug!
>
>
> > > IMHO, if we have an algorithm which produce a yes/no answer with
2^{-80}
> > > error probability, then this figure is so low that even a provable
> > > algorithm can't clame any better proofs.
> >
> > You are wrong. The output makes the proof reproducible and verifiable.
>
> In what part am I wrong? I tought you agreed that computers have a
non-zero
> error probability in running a program correct. IMHO, then it follows that
even
> if you run the program multiple times, the error propability is still
non-zero.
>
> Therefore, it does not qualify as a mathematical proof with zero error
> probability, e.g. no more than a probabilistic algorithm (with sufficient
> security parameter) does. Even a probabilistic algorithm can be run
multiple
> times, I simply don't see the big difference here.
The probability of an undetected computer error in a mathematical proof
(e.g. a primality certificate issued by an algorithm like APR-CL or ECPP)
will be trillions of times smaller than a carefully peer-reviewed
hand-written mathematical proof.
> Is it the figure 2^{-80} you argue about? I don't know how many times
your
> program can be run without giving the wrong answer on todays HW. However,
2^{80}
> is a *very* big number, IIRC the number of microseconds since Big Bang is
> approx. the same magnitude as this figure!
>
> I simply don't beleave that your program could have been run anywhere near
this
> figure, without giving the wrong answer...
Miller-Rabin does not issue a certificate of primality. Only a
"probably-prime" status with a margin of error. It is a good "first test"
to see if you want to waste time trying to prove a number prime or not, but
it cannot be used to show that a number is prime. Only that it might be
prime.
>
> > > Sounds like you have implemented the Jacobi sum test, I have no
expierence
> > > with it myself, but my intuition tells me that Miller-Rabin (even
with a
> > > high security parameter), would give you the answer faster.
> >
> > Good deduction (the names Lenstra and Cohen should indeed provide a
pointer
> > in that direction) but a wrong conclusion. Miller-Rabin will *not*
provide
> > a verifiable proof, which Jacobi does do.
>
> Neither method provide any strict conclusive proof. In the real world we
are
> confronted with failures, even Jacobi sum test does not escape the laws of
> nature.
>
> Since you have choosen a more complex algorithm, you have exposed your
> calculations more to failures compared to a simpler algorithm...
APR-CL [Cohen-Lenstra, obviously] and ECPP will generate a provable
primality certificate. Miller-Rabin issues forth nothing of the sort.
> > A CDC 205 was not exactly a normal PC CPU. And because the loop I
optimized
> > out did vectorize extremely well and used nearly exclusively
floating-point
> > math, it was very wel suited for that machine. And was faster on that
> > machine than it would have been on a Cray. So spending two weeks to
> > reduce running time from 1 CPU year to 1 CPU month for a machine that
cost
> > around $1000 per second was well spent.
>
> How big was this prime really, it doesn't sound like a 500 bit number...
>
> You did 2 weeks of optimization work, I would instead choosen to drop
> Lucas-Lehmer and Jacobi sum test and settled for probable primes...
Nonsense. If you want to prove something, Miller-Rabin is simply the wrong
way to go about it. That is because it *DOES NOT* accomplish the task at
hand.
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. Newsgroup http://www.dejanews.com/~c_a_p
C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Chosen and known attacks - are they possible ??
Date: Mon, 18 Sep 2000 20:07:06 +0200
kihdip wrote:
>
> The models are frequently used to describe an attack form:
> - Ciphertext only
> - Known plaintext
> - Chosen plaintext
> - Chosen ciphertext
>
> Forgive my ignorance, but are the known and chosen attacks only teoretical
What I believe is difficult is to determine from the
measures of difficulty resp. ease of attack in the
four cases the factor of safety (or an equivalent
quantity) of employment of a given cipher in a given
environment or to determine from these measures the
relative merits of two ciphers, since there may not
be a proportionality among these. Perhaps experts
would be kind enough to say something on this point.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: wince encryption algorithm
Date: Mon, 18 Sep 2000 20:07:11 +0200
Runu Knips wrote:
>
> But I miss all the ';', '{', '}', '^' etc characters ???
>
> It is very hard to read this way.
>
> Why have they be deleted ???
I think we should wait first for an English description
from the author before attempting to unravel the
meaning from the C-code with much effort.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On secret Huffman compression
Date: Mon, 18 Sep 2000 20:07:18 +0200
Benjamin Goldberg wrote:
>
> SCOTT19U.ZIP_GUY wrote:
> > [EMAIL PROTECTED] wrote:
> >
> > >A Huffman tree for compression is built according to the
> > >frequncy distribution in the manner that is well-known.
> > >We assume that the opponent can build the same tree.
> > >Now we do modifications to the coding as follows such
> > >that the opponent cannot decompress to obtain the
> > >original message:
> > >
> > >Use a secret key as seed of a PRNG. At each non-terminal
> > >node of the given Huffman tree, use a psudo-random number
> > >to determine whether the two branches are to be flipped,
> > >i.e. whether their markings of 0/1 are to be exchanged.
> > >Use the modified tree to do compression.
> > >
> > >We note that in order to cater for the byte/word boundary
> > >issue of the output file, one can include an end-of-file
> > >symbol (with the least frequency) in the Huffman tree
> > >and after output of that symbol use random bits to fill
> > >to the desired byte/word boundary.
> >
> > Yes do that if it makes you happy.
> >
> > but why not use my focused huffman its does the same thing
> > if you look at the code. You can supply the 0/1 switching and
> > padding as a function or you can modify it was random stuff.
> > But you already know that. However again I must point out with
> > mine you don't need to waste space with a useless EOF symbol
> Unless I'm mistaken, Mok-Kong Shen's code does not do the same thing as
> your huffman code; Your code is an adaptive huffman code, his is a
> static code. Also, with his code, you don't need an EOF either, in most
> cases... if the tree was based on 8-bit symbols, and we need 1..7 bits
> to fill out the last 8-bit byte, we can simply choose some symbol whose
> huffman code is longer than 8 bits, and write out part of it. Also, the
> huffman tree is probably small enough that, for PK encryption, we can
> encrypt it along with a symmetric key inside the PK block.
Thank you for your comments. The description I gave in the
original post is indeed for the static Huffman scheme,
while Scott uses the adaptive Huffman scheme (modified to
realize his 1-1 property). The observation you made that
in cases, where the tree has a symbol with code of at
least 8 bits, the eof-symbol is not necessary for dealing
with the byte boundary issue is valuable.
If one uses a pre-pass to determine the frequency distribution
of a given message, then the tree (before the 0/1 marking
modification via the PRNG), being unknown to the partner,
could be sent as you indicated or else encrypted in separate
blocks and sent together with the encrpyted compressed
message. I think that the total message length is even
in the second case generally not longer than that of the
adaptive scheme.
On the other hand, the 0/1 marking modification I described
can evidently also be applied to the adaptive scheme. The
adaptive scheme uses a clever update method of the tree
to avoid having it built up from scratch according to the
current frequency distribution as each plaintext symbol
is input. Similarly, we have to avoid applying marking
modification at all nodes of the tree each time the tree
gets changed, i.e. we want to economize with our operations.
This can be done as follows:
1. When a new node is created, use a pseudo-random number
to determine the markings of the two new branches that
appear.
2. When a switching of two nodes takes place, use a pseudo-
random number to determine the markings of the branches
that lead to these nodes.
This apparently could be easily incorporated into the
adaptive Huffman scheme.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: comp.databases.oracle
Subject: Re: Double Encryption Illegal?
Date: Mon, 18 Sep 2000 20:07:24 +0200
Runu Knips wrote:
>
> Mok-Kong Shen wrote:
> > Tom St Denis wrote:
> > > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > > > Tom St Denis wrote:
> > > > > [EMAIL PROTECTED] (Paul Schlyter) wrote:
> > > >
> > > > > > So you're claiming that triple-DES is no more secure than single-
> > > > > DES ???
> > > > >
> > > > > Read my message. Geez. I said "double" encryption is not the way
> > > to
> > > > > go about added security.
> > > >
> > > > Could you be more explicit and explain why? Are you
> > > > saying that superencipherment is always nonsense?
> > > > Is 2-DES not better than DES?
> > >
> > > Given sufficient memory 2-des is not better then des.
> >
> > Please exlpain your claim or refer to literature.
>
> That is the reason why people use 3DES, and never 2DES.
>
> Well this has been explained, for example, in Bruce Schneiers
> Applied Crypto. At least I think so ;-), I don't have it at
> hand in the moment. There is an attack which requires masses
> of memory, but then you can attack 2DES by attacking it from
> both ends (meet-in-the-middle-attack).
Do you really mean that a 2-DES (with two independent
keys) is not an jota stronger than DES??
>
> It is also explained in my other crypto book, "Abendteuer
> Kryptologie" (Adventure Cryptology), by Reinhard Wobst,
> Addison Wesley, ISBN 3-8273-1413-5, page 192ff.
It is strange that I found p.192 of this book (1997
edition) deals with RC5 and not DES or 2-DES. I suppose
you erred. Could you give the correct page number?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Intel's 1.13 MHZ chip
Date: Mon, 18 Sep 2000 20:07:29 +0200
Mok-Kong Shen wrote:
>
> The advantages/disadvantages of different architectures
> continue to be discussed in CS literatures since long time.
[snip]
In this connection the following new book might be of
some interest:
B. Falasafi, M. Lauria (Ed.), Network-Based Parallel
Computing. LNCS 1797. Springer, 2000.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: QUESTION ABOUT ALGORITHMS
Date: Mon, 18 Sep 2000 17:56:56 GMT
On Mon, 18 Sep 2000 19:36:53 +0200, in
<[EMAIL PROTECTED]>, in sci.crypt Runu Knips
<[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>> On Mon, 18 Sep 2000 13:39:05 +0200, in <[EMAIL PROTECTED]>, in
>> sci.crypt Runu Knips <[EMAIL PROTECTED]> wrote:
>> >Melinda Harris wrote:
>> >> What to sign and how much it costs???
>> >
>> >But if you want to patent a cryptographic algorithm, you're
>> >either a moron or an idiot. A moron if you want to sell
>> >to people what you know they can get for free, or an idiot
>> >if you think there are not already enough free algorithms.
>> >
>> >> Any response would be greatly appreciated
>> >
>> >Hardly. I've insulted you.
>>
>> You may have insulted more than you know. For example, I currently
>> hold three (3) US patents on fundamental cryptographic technology.
>> Presumably others have patents as well.
>
>Yep. Patents make me furious.
Too bad. Get over it.
>Sorry, I hate the idea that one can own thoughts.
Nonsense. Patents are about exposing information. Nobody can own
thoughts. What is owned is only the application of thoughts to actual
use. More than that, patents are economic tools, and rarely affect
individuals anyway.
>And the
>patent issue is becoming more and more absurd, see the
>human genome. Patenting DNA ! What a braindamaged idea !!!
Research costs money, and that money has to come from somewhere.
Perhaps you would feel better if it came out of state funds. Well,
patent royalties may be called a "tax," but they only have a cost when
the results are valuable and actually used in commerce. This seems
lots better for society than having the state pay whatever happens.
As always, patents provide a limited-term monopoly which -- if the
inventor is lucky -- might pay for the research.
>I'm gonna get a patent on breathing and soon will be
>richer than Bill Gates ;-(((
Let's see you get that patent first.
>Fortunately I neither live in USA nor need your patents.
>As I've already stated in my original posting :-)
As far as I am aware the European patents for the IDEA cipher do in
fact cover software implementations.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Dangers of using same public key for encryption and signatures?
Date: Mon, 18 Sep 2000 12:57:54 -0500
Paul Rubin wrote:
>
> Current practice seems to prefer using two separate keys, though some
> systems (PGP 2.x, and effectively SSL) use the same public key for
> both encryption and authentication. I have an application where space
> for keys is quite scarce. I'd like to use the same key (point on
> elliptic curve) for both encryption and signing (El-Gamal / ECDSA).
> What kind of trouble am I asking for, aside from the "FBI attack"
> (they make you turn over your decryption key so they can read
> something, and that means they can also sign your name to stuff)?
You are giving up more plaintext-ciphertext pairs with the same key.
Shouldn't be a problem as long as you change keys before you get out
more than 2^(n/8) messages. (or 1/8th large prime factor of your curve
order).
> Also, how long do my keys need to be to satisfy the paranoids in this
> crowd? Assume I'm using some constant (shared) curve over GF(p) for
> some large p. Is 140 bits enough? How about 170? Robert Harley has
> been breaking ECDL over GF(2^n) for n=112 or so, IIRC. But those are
> easier than GF(p) curves.
Not much easier. Your security goes as the square root of the largest
prime factor because your base point has the order of that large prime
factor. 140 bits will give you less than 70 bits "symmetric" equivelent.
170 bits gives you about 2^85 operations to crack. And so on.
140 is kind of marginal now, 170 is classed as "secure", and the paranoid
pick about 200.
Patience, persistence, truth,
Dr. mike
------------------------------
** 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
******************************
