Cryptography-Digest Digest #504, Volume #9 Wed, 5 May 99 17:13:03 EDT
Contents:
Re: BEST ADAPTIVE HUFFMAN COMPRESSION FOR CRYPTO (Mok-Kong Shen)
Re: small modular exponentiation routine wanted (Medical Electronics Lab)
Re: Shamir's Announcement (Bruce Schneier)
Re: Shamir's Discover: to those in the know (Patrick Juola)
Re: Shamir's Discover: to those in the know (DJohn37050)
Re: Shamir's Announcement (Mok-Kong Shen)
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(D. J. Bernstein)
Re: Shamir's Discover: to those in the know (DJohn37050)
Re: Fast random number generator (Mok-Kong Shen)
Re: Factoring breakthrough? (Mike McCarty)
Re: RSA-Myth (Mike McCarty)
Re: Fast random number generator (John Savard)
Re: AES (wtshaw)
Shamir's TWINKLE Factoring Machine (Bruce Schneier)
Books (John Savard)
Re: Discrete Logarithm Question (Bill Unruh)
Re: Books (Bruce Schneier)
Re: Compact look-up table - weak? ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: BEST ADAPTIVE HUFFMAN COMPRESSION FOR CRYPTO
Date: Wed, 05 May 1999 19:01:16 +0200
SCOTT19U.ZIP_GUY wrote:
>
> In article <[EMAIL PROTECTED]>,
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> > > You Mr SHen was the one to USE YES OR NO but fine lets drop that.
> >
> > This is a straight reversal of truth!!! I challenge you to give
> > the date and time of my posting to show that I first used 'YES or NO'.
> > I never use such a phrase in a question, because I personally don't
> > like that, considering it to be a bit not very polite (but this
> > could be simply my misunderstanding due to my poor knowledge of the
> > English language).
> >
>
> Do you really want me to find the reference. And would it shut you
> up or just piss you off more?
Do you think that I am joking????? Let's see who is the liar!!
>
> > >
> > > > Now you said 'seperate compression from encryption'. Isn't the
> > > > 'key' in your 'the enemy tries various keys' an issue of encryption?
> > > > Clearly it is. So, following your suggestion of seperating compression
> > >
> > > No it is not so CLEAR. Your adding random bits to me was part
> > > encryption. What this whole thread is about is compression that
> > > would be suitable for a file to undergo before it is encrypted.
> > > Most compression use headers of one formor another. Or a EOF
> > > symbol. However it is possible to compress a file to a shorter
> > > lenght if one can drop the use of an EOF symbol. IF you bother
> > > to look at my code. Or even look at test cases you can see that
> > > sometimes there is a EOF symbol of sorts. Sometimes there is not
> > > and some times the last symbol that would have been written by
> > > the adaptive huffman compression is truncated and not fully
> > > written to the file. To understand why one must think!
> > > To test the 3 alternate ending I came up with the fact that any
> > > random pattern in a finite number of bytes. When decompressed to
> > > a file. And then compressed back to a file. Would be identical.
> > > I am not GOD ( or the devil) but I may have made a mistake if
> > > any one can find a short file of a few million bytes or less that
> > > does not have this property when using my program then either I
> > > made an error. Or maybe I also am trying to do something that is
> > > not possible. But I think it is possible and have tested many cases.
> > > Now the whole KEY POINT in my mind is that you want a compression
> > > routine that leaves no information to the attacker. After you
> > > compress a file you then "seperately encrypt the file". It would
> > > be nice from a mathematicaly point of view. That if an attacker
> > > tryes a key ( block of keys ) that the resulting file from the
> > > decryption is of a form. That it could have come from a "actual
> > > compression". Look I am talking about all files. Not just ascii
> > > though I suspect some people may only encrypt ascii. If the file
> > > can be decompressed to a file and then recompressed to same file
> > > then the attacker has to dig deeper to find the message. But if
> > > the compression method always used a EOF or the like. Then the
> > > attacker has to look no farther and can reject imediately files
> > > of certain forms. Yes you could have a secret deal with you buddy
> > > that you will make last set of symbols garbage or whatever and
> > > that in specail messages to him you may drop the EOF but that
> > > is an encryption issue seperate from this thread.
> >
> > There are different sort of files in practice. Some files need
> > whole words, some need whole bytes (e.g. UNIX). There are ones that can
> > have length of any number of bits. For the third sort of files there
> > is no problem with Hufmann compression at all. For the first two sorts
> > the Hufmann compression has a high probability of not ending
> > at the word/byte boundary. (This has nothing to do whether the
> > input file is ASCII or not!!) So what should an implementation do?
> > Put in all 0's (or all 1's)? Well, you can do that. But on decompression
> > the algorithm will pick up these and try to decode and the chance is
> Only a typically coded huffman would get confused on the last token.
> But with clever thought there is no problem. COULD YOU LOOK AT THE
> DAMN CODE AND/OR EXAMPLES????
>
> ...snip..
>
> Well if you bothered to look at my code or examples then you can
> see what the method does. But your mind up to this point is to closed
> and to lazy to look. The point is you don't have to put all zeros
> or ones in. It just seems that most people who code sompression routines
> never give much thought about how to end the file in a nice way.
I wrote (or didn't real my post carefully??) that, among others
it is illegal for me to fetch crypto-code from US. Any if you have
any good method, it is certainly possible to express that in
a good pseudo-code, which is usually akin to sort of Pascal. I am not
very sure, but very probably it isn't illegal for you to put the
pseudo-code here in this thread so that all people can discuss that.
(A pseudo-code can be argued to be non-executable, hence not subject
to export restrictions.) Or else you can explain your idea in plain
English. Now WHO is lazy?????
M. K. Shen
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: small modular exponentiation routine wanted
Date: Wed, 05 May 1999 12:07:32 -0500
Paul Rubin wrote:
> Thanks. I don't care about ram consumption; I care about code size
> (i.e. the size of the stored file containing the compiled code).
> Where can I find "Implementing Elliptic Curve Crypto" and how slow is it?
http://www.manning.com/Rosing
How slow is it? Well, it's about 10 times slower than freelip as
far as I can tell looking at a stop watch. Part of the reason is
that it uses half a register instead of the full register and the
carry bit. If you rewrite the core routines of add and multiply
to use the carry bit it'll go twice as fast and not waste any
RAM. Since all the code is explained in gory detail, that shouldn't
be too hard. Good luck!
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: Shamir's Announcement
Date: Wed, 05 May 1999 17:28:25 GMT
There's a Wired News article on the subject:
http://www.wired.com/news/news/technology/story/19493.html
Bruce
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Shamir's Discover: to those in the know
Date: 5 May 1999 13:07:53 -0400
In article <[EMAIL PROTECTED]>,
DJohn37050 <[EMAIL PROTECTED]> wrote:
>P=NP destroys any symmetric key system as well. Almost all researchers do not
>think that P = NP.
"Destroys" is putting it too strongly. If I can find an n^1000 algorithm
to solve the Travelling Salesman Problem, that won't necessarily have
a significant effect on modern cryptography; it will still in many
cases be faster to brute-force search the keyspace than it will to
solve directly.
-kitten
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Shamir's Discover: to those in the know
Date: 5 May 1999 16:58:24 GMT
P=NP destroys any symmetric key system as well. Almost all researchers do not
think that P = NP.
Don Johnson
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Shamir's Announcement
Date: Wed, 05 May 1999 19:51:45 +0200
Shamir's paper is available at John Young's site. A post from
Young is attached below.
M. K. Shen
===============================================
From: Adi Shamir <[EMAIL PROTECTED]>
Date: Wed, 5 May 1999 09:57:33 +0300
To: [EMAIL PROTECTED]
Subject: Re: TWINKLE
Hi,
The early version of the paper was quietly circulated to a small
number of factoring experts and colleagues to get their comments.
I'll probably write an expanded version soon, but in the meantime
I am enclosing in the next email the current version, which is now in
the public domain and can be circulated freely.
Best personal wishes,
Adi.
=====
The 12-page paper:
http://jya.com/twinkle.eps (370K)
Zipped:
http://jya.com/twinkle.zip (79K)
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: 5 May 1999 17:50:22 GMT
Terry Ritter <[EMAIL PROTECTED]> wrote:
> In the original context, the many-cipher system simply does not
> support a catastrophe of the same extent as the single-cipher system.
I don't believe you.
Once again: What do you do when the attacker notices that most of the
amateur designs incorporated into your system are vulnerable to simple,
easily automated differential attacks?
---Dan
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Shamir's Discover: to those in the know
Date: 5 May 1999 18:49:11 GMT
Schoof's algorithm to count points on an elliptic curve is an eighth order
algorithm and is one of the most complicated I have ever come across in
practice. I do not pretend to understand it. RSA enc. with a small exponent is
a quadratic, RSA dec. is a cubic, RSA key gen is a quartic, etc. So for
essentially all purposes (like crypto) polynomial means small polynomial.
Don Johnson
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Fast random number generator
Date: Wed, 05 May 1999 20:24:28 +0200
John Savard wrote:
>
> My algorithm, though, only requires random bytes, and doesn't need to
> do multiplication or division to convert them to other ranges.
Where do you obtain these random bytes?
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Mike McCarty)
Subject: Re: Factoring breakthrough?
Date: 5 May 1999 14:37:21 GMT
In article <7g6voq$2j$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
)In article <[EMAIL PROTECTED]>,
) lcs Mixmaster Remailer <[EMAIL PROTECTED]> wrote:
)> Rumor has it Adi Shamir will announce factoring breakthrough soon.
)> Increasing efficiency by orders of magnitude and breaking keys 100-200
)> bits longer than current state of the art.
)>
)> Anybody confirm/deny?
)
)The proof is always in the pudding.
That should be
The proof of the pudding is in the eating.
--
----
char *p="char *p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}
This message made from 100% recycled bits.
I don't speak for Alcatel <- They make me say that.
------------------------------
From: [EMAIL PROTECTED] (Mike McCarty)
Subject: Re: RSA-Myth
Date: 5 May 1999 14:30:08 GMT
No, God does love cockroaches, but SPAMMERs made themselves.
In article <[EMAIL PROTECTED]>,
Steve Rush <[EMAIL PROTECTED]> wrote:
)>Matthew Skala Ansuz BBS (250) 472-3169 http://www.islandnet.com/~mskala/
)>
)> GOD HATES SPAM
)>
)>
)
)To the contrary. God must LOVE spammers; and cockroaches; He made so many of
)them.
)
)**********************************************************************
)If it's spam, it's a scam. Don't do business with Net abusers.
)
--
----
char *p="char *p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}
This message made from 100% recycled bits.
I don't speak for Alcatel <- They make me say that.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Fast random number generator
Date: Wed, 05 May 1999 17:56:55 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote, in part:
>>The classical shuffling algorithm depends on a good random number
>generator to produce small random numbers in the range [0, size-1].
No, it needs more than that.
It needs one random number in the range {0, 1, 2, ... size-1 }, and
then it needs one random number in the range {0, 1, 2, ... size-2 },
and then one in the range {0, 1, 2, ... size-3 }.
Usually, the classical shuffling algorithm is implemented using a
generator of random numbers in the range [0,1), which cnn then be
converted easily to random integers from any range desired.
My algorithm, though, only requires random bytes, and doesn't need to
do multiplication or division to convert them to other ranges.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: AES
Date: Wed, 05 May 1999 09:49:31 -0600
In article <7goppr$lt6$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
wrote:
> [EMAIL PROTECTED] (Terry Ritter) writes:
> >
> >Sorry. There is NO proof of strength for Triple-DES or any other
> >cipher in cryptography.
>
> There are two different meanings of the word "prove." One is the mathemtical
> sense, and one is the empirical sense. I assume the poster was making an
> empirical statement, in which case it is true that through extensive use
> and analysis, Triple-DES has proven to be very secure. It has not, however,
> been proved to be secure. Different uses of the verb "to prove."
>
This is the reason that claims by anyone that you disagree with are easily
classed as snake oil, because you define who you accept by empirical or by
strict definition. Then, what this means is that defining snake oil can
be taken as snake oil in itself.
--
FUD--fear, uncertainty, doubt
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Shamir's TWINKLE Factoring Machine
Date: Wed, 05 May 1999 20:12:24 GMT
At Eurocrypt this week, Adi Shamir presented a new machine that could
increase our factoring speed by about 100-1000 times. Called TWINKLE
(The Weizmann INstitute Key Locating Engine), this device brings
512-bit keys within the realm of our ability to factor.
The best factoring algorithms known to date all work on similar
principles. First, there is a massive parallel search for equations
with a certain relation. This is known as the sieving step. Then,
after a certain number of relations are found, there is a massive
matrix operation to solve a linear equation and produce the prime
factors. The first step can easily be paralleled--recently, 200
computers worked in parallel for about four weeks to find relations to
help factor RSA-140--but the second has to be done on a single
supercomputer: it took a large Cray about 100 hours and 810 Mbytes of
memory to factor RSA-140.
Shamir conceptualized a special hardware device that uses
electro-optical techniques to sieve at speeds much faster than normal
computers. He encodes various LEDs with values corresponding prime
numbers, and then uses it to factor numbers. The machine reminds me
of the famous Difference Engine of the 1800s. Once the engineering
kinks are worked out--and there are considerable ones--this machine
will be as powerful as 100-1000 PCs for about $5000. The basic idea
is not new; a mechanical-optical machine built by D.H. Lehmer in the
1930s did much the same thing (although quite a bit slower).
As far as we know, Shamir's machine is never been built. (I can't
speak for secret organizations.) As I said, Shamir presented a
conceptualization and a sketch of a design, not a full set of
engineering blueprints. There are all sorts of details still to be
figured out, but none of them seem impossible. If I were running a
multi-billion dollar intelligence organization, I would turn my
boffins loose at the problem.
The important thing to note is that this new machine does not affect
the matrix step at all. And this step explodes in complexity for
large factoring problems; its complexity grows much faster than the
complexity of the sieving step. And it's not just the time, it's the
memory requirements. With a 1024-bit number, for example, the matrix
step requires something like ten terrabytes of memory: not off-line
storage, but real computer memory. No one has a clue how to solve
that kind of problem.
This technique works just as well for discrete-logarithm public-key
algorithms (Diffie-Hellman, ElGamal, DSA, etc.) as it does for RSA.
(Although it is worth noting that the matrix problem is harder for
discrete-log problems than it is for factoring.) The technique does
not apply to elliptic-curve-based algorithms, as we don't know how to
use the sieving-based algorithms to solve elliptic-curve problems.
In Applied Cryptography I talked about advances in factoring coming
from four different directions. One, faster computers. Two, better
networking. Three, optimizations and tweaks of existing factoring
algorithms. And four, fundamental advances in the science of
factoring. TWINKLE falls in one and three; there is no new
mathematics in this machine, it's just a much faster way of doing
existing mathematics.
Shamir's contribution is obvious once you understand it (the hallmark
of a brilliant contribution, in my opinion), and definitely changes
the landscape of what public-key key sizes are considered secure. The
moral is that it is prudent to be conservative--all well-designed
security products have gone beyond 512-bit moduli years ago--and that
advances in cryptography can come from the strangest places.
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Books
Date: Wed, 05 May 1999 20:29:23 GMT
I noticed that "Cryptonomicon" is on the shelves at a local bookstore.
While I like the topic, I fear the genre may make it difficult for me
to read...my "light reading" budget may also be affected by the
Episode I comic book (I won't go for the hardcover of the novel) also
out recently...
Also, I visited Cryptome today (at http://jya.com/), and in one of the
stories there, found that the book "Top Secret Intranet" about the
development of Intelink, which I saw some time back at a local
bookstore of computer-related books, may be more interesting than I
thought; a book review in the Baltimore Sun notes that it is by a
senior NSA official, and offers an inside look in the "old NSA" versus
the "new NSA".
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Discrete Logarithm Question
Date: 5 May 1999 20:43:29 GMT
In <7gor1g$s1r$[EMAIL PROTECTED]> "Antoine Joux" <[EMAIL PROTECTED]> writes:
>Vedat Hallac a crit dans le message
>>I wanted to know if there is a method to find x in
>>a_i^x == b_i ( mod N )
>>if I can calculate b_i for *every* 1 < a_i < N. And N is not a prime
>number.
>In order to solve the discrete logarithm mod N, the only solution is to
>factor N,
>to solve the problem modulo each factor p_i, and finally to glue the partial
>solutions
>modulo Phi(p_i)=p_i-1, using the chinese remainder theorem .
But his is not the discrete logarithm problem. The discrete log problem
is if you know a and a^x, (mod N) find x. But this is for a single value
of a. He is asking if you know a^x and a for all possible values of a,
can you find x.
Of course how you find a^x without knowing x has not been specified
(lets say table lookup).
If x can be found in polynomial time given all a, then you must need
only a polynomial subset of a to do it. What is the minimum number of a
you need to be able to find x in poly time and can they be characterised
somehow.
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: Books
Date: Wed, 05 May 1999 20:38:54 GMT
On Wed, 05 May 1999 20:29:23 GMT, [EMAIL PROTECTED]
(John Savard) wrote:
>I noticed that "Cryptonomicon" is on the shelves at a local bookstore.
>While I like the topic, I fear the genre may make it difficult for me
>to read...my "light reading" budget may also be affected by the
>Episode I comic book (I won't go for the hardcover of the novel) also
>out recently...
>
>Also, I visited Cryptome today (at http://jya.com/), and in one of the
>stories there, found that the book "Top Secret Intranet" about the
>development of Intelink, which I saw some time back at a local
>bookstore of computer-related books, may be more interesting than I
>thought; a book review in the Baltimore Sun notes that it is by a
>senior NSA official, and offers an inside look in the "old NSA" versus
>the "new NSA".
I found this book interesting. No earth-shattering revelations,
though.
Bruce
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Compact look-up table - weak?
Date: Wed, 05 May 1999 19:55:07 GMT
<snip>
It's almost to easy to say:
A smaller s-box has less complexity of a larger s-box given the proportional
amounts of entropy each. So if a large table is made with one bit of entropy
and a small box with 64 bits, the small box is gonna be a winner.
Let's not forget it's how you use the s-box which can make the difference.
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
** 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
******************************
