Cryptography-Digest Digest #898, Volume #11 Tue, 30 May 00 18:13:01 EDT
Contents:
Re: list of prime numbers ("Dann Corbit")
Re: No-Key Encryption (Michael Pellaton)
Re: Crypto patentability (ritter)
Re: NSA hardware evaluation of AES finalists ("Douglas A. Gwyn")
Re: Retail distributors of DES chips? (zapzing)
Re: Comments requested: One way function blast() (zapzing)
Re: Math problem (P=NP) prize and breaking encryption ("Axel Lindholm")
Re: Retail distributors of DES chips? (Mark Wooding)
Re: Note on the Hill cipher (II) (Mark Wooding)
Re: Retail distributors of DES chips? (ritter)
Re: list of prime numbers ("Axel Lindholm")
Re: driving me and friends nuts (Paul Koning)
----------------------------------------------------------------------------
From: "Dann Corbit" <[EMAIL PROTECTED]>
Subject: Re: list of prime numbers
Date: Tue, 30 May 2000 14:22:46 -0700
"Daniel" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Thu, 25 May 2000 21:50:00 GMT, [EMAIL PROTECTED] (Dan Day) wrote:
>
>
> >Daniel, what were you hoping to do with the list? If you'll
> >explain your application, we can help you address your problem
> >more directly, since keeping a "list" of primes is likely to
> >be a poor way to get the job done, whatever it is.
> >
> >
> Thanks for all the replies.
>
> I'm trying to understand RSA and want to be able to factor a given
> 'public modulus'. Or try it at least ;-)
>
> If one has a large number (say 150 digits), what are the ways to try
> and break this up into its factors? Where does one start?
Certainly not with a list of primes. Others have described why, so I won't
beat that dead horse any more. A good place to learn about factorization is
Chris Caldwell's prime pages:
http://www.utm.edu/research/primes/
You might also look at the neat stuff on the RSA labs commercial site.
[snip]
--
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
------------------------------
Date: Tue, 30 May 2000 22:04:04 +0200
From: Michael Pellaton <[EMAIL PROTECTED]>
Subject: Re: No-Key Encryption
Mok-Kong Shen wrote:
>
> Michael Pellaton wrote:
>
> > It seems to me that I used the wrong name of a method of encryption.
> > Maybe it's an error that occurred during translation from and to
> > German (I have seen the word "no-key encryption" in at least two
> > German books).
>
> Could you please give the German word and, in particular, name the
> two books?
There is a web site that uses the word at:
http://www.uni-mainz.de/~pommeren/DSVorlesung/KryptoProt/NoKey.html
There is a book called "Informationssysteme" (internal release of
University of Applied Sciences, Zurich) that uses the Word
"No-Key-Verschl�sselung"
In the papers distributed by our professor the word
"No-Key-Verschl�sselung" appears again (unfortunately one of the
professors who does not publish his papers on line).
Other professors and sources (I recently found) use the epressein
"Shamirs Dreiweg-Algotithmus (ohne Schl�sselaustausch)"
Another professor of my University has his nice papers on line (but does
not use the word - in English):
http://fbi.zhwin.ch/KSy/Block09/Crypto_Unterlagen.htm
> [snip]
>
> > It allows two people or systems to communicate safely without knowing
> > anything about eachother except for the fact that it uses the
> > same encryption system.
> >
> > I know that XOR is a very weak encryption methode and I just used it
> > to show what I mean with "No-Key encryption" in an easy way.
> >
> > Now, what's the proper English name for what I described above?
> > Where is it used?
> > Are there any well-known implementations?
>
> The scheme is probably what initiated the idea of current public key
> systems. It apparently has no specific name and is described on p.63 of
>
> A. Salomaa, Public-Key Crpytography. Springer-Verlag, 1990.
I think the word I was looking for was "Shamir Three-Pass-Alorithm".
(If I look at all the responses I start to understand why we have to
take so much math when studying Information Technology ...)
------------------------------
Subject: Re: Crypto patentability
From: ritter <[EMAIL PROTECTED]>
Date: Tue, 30 May 2000 14:37:50 -0700
In article <8h0rk7$9lj$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Bill Unruh) wrote:
>[...]
> Patents are an agreement that in return for making the
>invention public, the state will grant a monopoly.
>Software is already, by its nature, public.
I strongly disagree with this. We now have massive
experience with vast numbers of software packages,
and rather few commercial programs come with source
code. Any patentable techniques in most software are
*hidden* and *not* disclosed to the ordinary worker
in the field. We simply cannot expect that every
worker will disassemble and then understand every
program having new techniques. It is to the benefit
of society that more be required for "publication"
than the simple release of executable object code.
>You do not need the monopoly bribe to have it
>made public. Society gets a very very bad deal out
>of software patents.
As far as I know there are no software patents.
There are patents which do cover software
implementation, if that is what is meant.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: NSA hardware evaluation of AES finalists
Date: Tue, 30 May 2000 20:45:55 GMT
Jaap-Henk Hoepman wrote:
> I can very well conceive Intel including the AES finalist into its CPU core,
> especially if the extra space requirements are not too high. It would, for one
> thing, enable software copy protection...
So would *not* embedding AES directly in the silicon.
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Retail distributors of DES chips?
Date: Tue, 30 May 2000 21:35:14 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
>
> Mark Wooding wrote:
> > Tom St Denis <[EMAIL PROTECTED]> wrote:
> >
> > > That's not true. This cipher could simply be
> > >
> > > Ek(P) = P xor K
> > >
> > > unless you test it.
> >
> > Yes, but the point is that, in theory, DES is completely
deterministic.
> > If you have a DES chip, you can feed known keys and plaintexts in
it,
> > and verify that you get the right answers against some other known
and
> > trusted implementation. You can even give it `trick questions'
every
> > now and then while it's in production use, checking its results, to
make
> > sure it's not randomly deciding to emit leaked key material instead
of
> > giving the right answers every now and then. I'd hope that most
serious
> > users of black-box cryptography hardware or software did something
like
> > this.
>
> Testing isn't sufficient. Consider:
>
> DES'[K](P) = DES[K](P), if P != backdoor
> = K, if P == backdoor
>
> Then with a single chosen plaintext, the key is revealed. Assuming the
> backdoor plaintext is chosen randomly, no amount of testing that takes
> less than 2^63 expected work will find it.
>
That vulnerability is admitted, but I believe I have
a way around that. I plan on using the chips in
something similar to what I described in another
thread, "Another Possible DES Mode" (or something
like that). It consists basically in breaking the
plaintext into "superblocks" the size of, say, four
normal DES blocks. This goes through a hardware
permutation. Then each DES sized block is encrypted
using a different chip that has a different key.
do that a few times and end up with another hardware
permutation. Do the hardware permutation on a
breadboerd and rip it out when you're through.
The keys in the chips, even if they can be disclosed,
are no good. The permutations are the real "key" to
this method.
Vulnerable to chose plaintext, perhaps,
but I am not planning on giving the opponent that
opportunity. Known plaintext attach will be difficult
but not impossible, but the amount of info I will be
encrypting is relatively small (under 25MB for this
application) so that is pretty much out too.
> > With DSA, if you don't trust the hardware, you're stuffed.
>
> Indeed, but that's just as true for any other algorithm - it's just a
> little bit more involved for someone to work out how to stuff you.
Feeding the chips "trick questions" was an excellent
idea that someone in this thread pointed out. You would
just have to make sure the little guys coudn't tell what
kind of "environment" they were in. But that wouldn't be
*too* difficult. Just set up a similar system and
have it encode shakespear or something.Perhaps we could
set up another newsgroup sci.crypt.des.trick-questions ?
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Comments requested: One way function blast()
Date: Tue, 30 May 2000 21:38:02 GMT
I may have misread the source code.
I'll examine it more carefully.
Please stand by.
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Axel Lindholm" <[EMAIL PROTECTED]>
Subject: Re: Math problem (P=NP) prize and breaking encryption
Date: Tue, 30 May 2000 23:54:59 +0200
Even though your program doesn't solve the Hamilton Cycel problem I would
like to obtain a copy of your source, if you feel like sharing it with me.
Also, if it's not too much to ask for, I'd love a small description of the
algorithm itself.
Thanks!
Axel Lindholm
"root" <[EMAIL PROTECTED]> wrote:
>
> I want to thank all the people that responded to this query. I learned
> a lot.
>
> And now I would like to make a further request of you (and a small
> confession).
>
> First the confession. About 4 years ago I developed an algorithm that
> seems to solve the Hamilton Cycle problem. I've only tested it on random
> graphs up to 100 nodes. My exhaustive search algorithm became ineffective
> at approximately 30 to 50 nodes, so I haven't been able to check the
larger
> graphs. It is not perfect. If there is no cycle, it is fast and right
> every time. If there is a unique cycle, it is fast and finds it
immediately.
> The problem is if there are sub cycles or multiple cycles. As the number
> of cycles grows, the solution time grows also (I suspect it grows
> combinatorically). A 100 node graph took approximately 5 minutes to solve
> on an Intel 486DX2 66(or maybe it was an AMD 486DX4 133). The exhaustive
> search would run for days, and would still be running when a killed it.
>
> Now the request. I realize after seeing all of your comments above that
> it must seem unlikely that my claim is true. How would you go about
> the process of verifying and publicizing such an algorithm if you were
> me? Do I just post my (beginners C++) code on the internet or an ftp
> site? Do I write an article (horrors)? I have to confess that once the
> problem was solved, my interest declined quickly. I got a tepid response
> on inquiries as to whether it was important (I didn't ask here).
> Rehashing and improving it or documenting it seemed tedious. I moved on
> to other things. The article in the paper spurred me to investigate
> again, possibly pursue publication.
>
> Thank you for any guidance you can give me.
>
> stan
>
> PS Maybe you will also think this is not significant. In that case I
> guess you can ignore the above questions.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Retail distributors of DES chips?
Date: 30 May 2000 21:08:24 GMT
ritter <[EMAIL PROTECTED]> wrote:
> Or maybe your idea of "trustworthy" is the real hobby-horse ride being
> so rudely interrupted.
I think we're off at a tangent here still...
I intended `trustworthy' to mean that, in the considered opinion of the
security officer using the component, it is worthy of the trust placed
in it. That's a decision for the user to make, based on whatever
criteria he or she wants to use.
> That said, I think we can test a cipher chip to a software
> implementation, using the property that we have a particular 1:1
> transformation, and that no more information comes out than goes in.
Except that, as mentioned upthread, the chip may have been programmed to
yield the key (or some simple function of it) only when a particular
plaintext or sequence of plaintexts is submitted for encryption, or some
other unlikely event occurs. As you quite rightly point out, testing
doesn't help, but this isn't the fault of the cipher this time -- the
cipher could be completely secure and it wouldn't fix the problem -- but
the fact that we can't look inside the implementation means we can't
tell whether it's actually doing what it said on the box.
> But that means the chip cannot pick any "random" system-level values
> (no message keys, no IV's).
Except it might `sometimes', depending on external stimuli.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Note on the Hill cipher (II)
Date: 30 May 2000 21:25:30 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> The Hill cipher
>
> C = H * P mod u
>
> where H is an invertible matrix in Z_u, has the known disadvantage
> that, if a pair of plaintext and ciphertext is available, then H, the
> 'key', can be recovered.
Still wrong. You must have a set of n linearly-independent plaintext/
ciphertext pairs to recover an n x n key matrix.
-- [mdw]
------------------------------
Subject: Re: Retail distributors of DES chips?
From: ritter <[EMAIL PROTECTED]>
Date: Tue, 30 May 2000 14:56:45 -0700
In article <[EMAIL PROTECTED]>, tomstd
<[EMAIL PROTECTED]> wrote:
>In article <[EMAIL PROTECTED]>, ritter
><[EMAIL PROTECTED]> wrote:
>>
>>In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
>>(Mark Wooding) wrote:
>>>Terry Ritter <[EMAIL PROTECTED]> wrote:
>>>
>>>> But how shall we measure this "trustworthy" property so we
>can
>>"make
>>>> sure" that it exists?
>>>>
>>>> There is an alternative, and I have been promoting it for
>>several
>>>> years: Use *scalable* cipher designs, so we can perform an
>>extensive
>>>> or even exhaustive analysis of the tiny scaled-down version.
>>>
>>>Sorry to interrupt while you're on your hobby horse, Terry,
but
>>I was
>>>referring to *implementations* of existing cipher designs.
>>
>>Oh, well, if "implementation" is the distinction,
>>then perhaps you will tell us just how you *test* for
>>the "trustworthy" property in *implementations*.
>>
>>Or maybe your idea of "trustworthy" is the real
>>hobby-horse ride being so rudely interrupted.
>>
>>
>>>The
>>>discussion in hand is about the possibility of hardware
>>implementations
>>>of strong (as a matter of hypothesis) having been deliberately
>>>compromised by the vendor. Cipher design doesn't help here.
>>
>>"Software" is just another name for the
>>customization of hardware digital systems. In
>>general, when we want a complete understanding of
>>what is present in a digital system, we must have
>>exhaustive tests. Such tests are impossible in real
>>size cipher systems, either hardware or software.
>>Only tiny systems allow exhaustive tests, only
>>scalable ciphers allow us to build tiny systems
>>directly related to real ones, and only exhaustive
>>testing allows us to know that nothing else is there.
>>
>>Perhaps that is clearer now.
>
>Yup it's clear you are not answering the question.
>
>His question was the possibility of DES being fudge-up by some
>naughty person. Not whether DES was strong or not, whether the
>CHIP was.
Really? Well, here it is:
>>>>>Well, One of the things I have been considering is the
>>>>>possibility of malicious software.
>>>>>That's why I was considering using a chip.
>>>>>That way there is absolutely no possibility
>>>>>that anythink will be placed in any
>>>>>subliminal channels.
The issue I have addressed is the idea that "there
is absolutely no possibility" of a subliminal
channel on a chip. That is false, thus making the
only real advantage of hardware that new subliminal
channels are unlikely to be added -- unless of course
there is a programmable subsection that we don't know
about.
What we really want is a cipher subsystem -- hardware
or software -- which demonstrably produces no more
data than we send to it. To assure this, we might
send in a buffer of data, and then use that same
buffer with the original length as the result. There
must be (at this level) no subsystem-selected or
produced random values.
>Not like you do bad work, but you are plugging it in the wrong
>spot my friend.
Really? Perhaps you have a deeper insight you
would like to share with us.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: "Axel Lindholm" <[EMAIL PROTECTED]>
Subject: Re: list of prime numbers
Date: Wed, 31 May 2000 00:05:47 +0200
I'd just like to add something that you might have use for. Mr. Molnar
kindly pointed out to me, a nice page having some information on a good
factorisation algorithm. This was mentioned in the replies to "Math problem
(P=NP).....". It's most likely of no practical use if you plan to create
some kind of RSA factorising program, but if you're looking for information
on general factorising it might be fun to read it.
http://www.research.att.com/~bal/papers/crypto/field/node8.html
Thanks!
Axel Lindholm
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: driving me and friends nuts
Date: Tue, 30 May 2000 17:45:20 -0400
[EMAIL PROTECTED] wrote:
> ...
> Yanko, with these notes here, you are well on your way to solving the
> problem -- I suggest a book by Helen Gaines (I think I spelled that
> correctly), _Cryptanalysis_. It covers all sorts of pre-computer ciphers
> such as this one.
>
> I found my copy of Gaines at Powell's Technical Bookstore, perhaps your
> local geek store has a copy too. It is published by Dover, last updated
> in 1955 or something like that. :) ($8 too! :)
Mine came from the local Barnes & Noble store, I think. Certainly it
seems easy to find.
> Until you can find the book, make some frequency counts -- individual
> letters, digrams, and perhaps trigrams, and compare against tables of
> letter frequencies, digrams freqs, and trigram freqs, at which point
> trial and error likely takes over.
>
> The message really isn't long enough for multiple substitution alphabets
> to be easily analyzed...
True. But from the index of coincidence it looks like a simple
substitution (monoalphabetic), and the frequency count distribution
supports that too.
paul
------------------------------
** 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
******************************
