Cryptography-Digest Digest #218, Volume #10 Fri, 10 Sep 99 19:13:02 EDT
Contents:
Re: some information theory (Anton Stiglic)
Re: Neal Stephenson's Cryptonomicon: Crypto Cop-Out (Brad Johnson)
Re: NSAKEY as an upgrade key (Was: NSA and MS windows) ("Thomas J. Boschloo")
Re: Looking for an asymmetric system (Jerry Coffin)
Creation of Tokens ! (Robert Depenbrock)
Re: Looking for an asymmetric system (Enterrottacher Andreas)
Re: compression and encryption (SCOTT19U.ZIP_GUY)
Re: Looking for Completely-Free Strong Algorithms ("Daniel Roethlisberger")
Re: Looking for Completely-Free Strong Algorithms (Paul Koning)
Re: Looking for Completely-Free Strong Algorithms (Paul Koning)
Re: unix clippers that implement strong crypto. (SCOTT19U.ZIP_GUY)
Re: compression and encryption ("karl malbrain")
Re: Looking for an asymmetric system (DJohn37050)
Re: Looking for Completely-Free Strong Algorithms (John Myre)
Re: some information theory (Anton Stiglic)
NSAKEY as an upgrade key (Was: NSA and MS windows) (Larry Lee)
Re: Looking for Completely-Free Strong Algorithms ("Joseph Ashwood")
Re: Digital Certificates and Authentication ("ME")
Re: Double encryption is patented (mabey) (John Savard)
Re: 512 bit number factored ("Trevor Jackson, III")
----------------------------------------------------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: some information theory
Date: Fri, 10 Sep 1999 14:34:44 -0400
karl malbrain wrote:
>
> No, only the TOTAL is squared with reality. Karl M
If you don't have anything good to say, go to some "gossip
want to be a philosophe" news group.
------------------------------
From: Brad Johnson <[EMAIL PROTECTED]>
Crossposted-To: rec.arts.sf.written,alt.cyberpunk
Subject: Re: Neal Stephenson's Cryptonomicon: Crypto Cop-Out
Date: 10 Sep 1999 15:23:06 -0500
In rec.arts.sf.written Tom Knight <[EMAIL PROTECTED]> wrote:
:>
: Hmm. IMHO, You seem to be confusing the ideas of the protagonist with
: the ideas of the author. I didn't know whether Stephenson himself
: supported e-cash before I read Cryptonomicon, and I don't now. However,
: anyone could argue that someone can write a tract without actually
: believing what it says. A more important point is that I don't really
: think that Cryptomomicon, as a book, had any kind of an agenda. I'd
: say that Stephenson is far too good an author to fall into the trap of
: prolatising(?). The main protagonists favor the system, but the book
: makes them all out as, at the very least, mildly unbalanced. Randy is,
: in a way, seen as a sane person commenting on an insane situation, but
: we are shown his idosincracies(?) as well. I don't think many people
: would regard it as promoting some kind of political cause, and I
: certainly don't.
I'd be surprised if most of the attitudes expressed in Cryptonomicon
aren't Stephenson. Check out this earlier bit of fiction by Neal, from
Time in 1995:
The Great Simoleon Caper
http://kuoi.asui.uidaho.edu/~kamikaze/documents/simoleon.html
It's the crypto cash scenario of Cryptonomicon, effectively.
It's interesting how Stephenson used essays and short fiction
to write Cryptonomicon; his Wired pieces and the "In the beginning"
essay were both incorporated into Cryptonomicon as well.
-- bradj.
========================Nullus Oppidenda Est==========================
brad johnson ([EMAIL PROTECTED]) 'Disc, God, Country, Pork'
http://www.amherst.edu/~bgjohnso/ 'Chickens! No Cynics!'
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
------------------------------
From: "Thomas J. Boschloo" <[EMAIL PROTECTED]>
Subject: Re: NSAKEY as an upgrade key (Was: NSA and MS windows)
Date: Fri, 10 Sep 1999 17:18:53 +0200
Bill Unruh wrote:
>
> In <[EMAIL PROTECTED]> "Thomas J. Boschloo" <[EMAIL PROTECTED]> writes:
>
> >MS could issue a patch that disabled the first key in Windows. They can
> >do anything. Allowing controls signed with the first key would not be an
> >option, since the key was compromised.
>
> Would be hard since all of the CryptoAPI programs are signed with it,
> and if it were invalidated, nothing in the base system would load.
I know nothing about CryptoAPI, but how large would this 'patch' be?
Would you need a whole new Windows, would if affect user programs (or
need they only have their crypto-modules re-signed)? Are all ActiveX
controls signed by the same microsoft key? Just what needs to be
'upgraded' and what not?
Maybe the _NSAKEY would only be useful for a whole new Windows version
users would need to upgrade to for security. New programs and add-ons
would run on both this new Windows and Win95ORS2 - Win2000.
Thomas
--
AMD K7 Athlon 650 Mhz! <http://www.bigbrotherinside.com/#help>
PGP key: http://x11.dejanews.com/getdoc.xp?AN=453727376
Email: boschloo_at_multiweb_dot_nl
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: Looking for an asymmetric system
Date: Fri, 10 Sep 1999 15:06:53 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> The best methods to break IF, DL, or EC methods are complex. Just because one
> can understand what it means to factor a number does not mean much in terms of
> what it means to be able to factor a large number.
True. Factoring reminds me a bit of the first time I saw a Rubik's
cube (giving away something about my age). It _looked_ simple enough
that you started looking at in the first place, and ended up more or
less obsessed with it for quite a while.
Of course, only a TINY percentage of people who bought Rubik's cubes
ever figured out their own solutions to it, but even at that, one
hundredth of a percent (say) of millions is still quite a few people.
If the problem LOOKED hard enough that a lot fewer people had started
out looking at it, even if a much higher percentage succeeded in
solving it, there'd undoubtedly be a lot less known about the problem
in general.
--
Later,
Jerry.
The Universe is a figment of its own imagination.
------------------------------
From: Robert Depenbrock <[EMAIL PROTECTED]>
Subject: Creation of Tokens !
Date: Fri, 10 Sep 1999 19:34:55 +0200
Hi !
is ther somewhere a documentation, how to get Tokens ?
I have some experience with the use of the SecurID Token Cards, and i
wonder, if there are
any Freeware Token Creation Hardware, or Software available ?
Greetings
Robert Depenbrock
------------------------------
From: Enterrottacher Andreas <[EMAIL PROTECTED]>
Subject: Re: Looking for an asymmetric system
Date: Fri, 10 Sep 1999 22:18:37 +0200
Emmanuel Drouet schrieb:
>
> Hello !
>
> 1/ I would like to know what is the strongest asymetric cryptosystem
> 2/ What do you think about :
> RSA, elgamal, McEliece, elliptic curves, Merkle-hellman
RSA and ElGamal are strong algorithms if you are using more than 1024
bit
keysize. RSA is patented, ElGamal isn't. ElGamal is slower and expands
the ciphertext.
McEliece seems to be strong but needs really huge keys.
I don't know the Merkle-Hellman algorithm.
There are lots of algorithms based on elliptic curves.
The keysize is much smaller for elliptic curves, but I don't know if
they
are stronger as long as the neccessary keysizes are used (ElGamal with
2048
bit keysize should be comparable to ECEG with 256 bit keysize).
> 3/ Do you know another asymetric cryptosystem ?
Rabin was used as long as the patent on the Diffie-Hellman/ElGamal
algorithm
was valid.
Common algorithms for key exchange are the Diffie-Hellman algorithm
and KEA and their counterparts based on elliptic curves.
For digital signatures DSA and ECDSA and the GOST signature algorithm
are
interesting.
>
> Thanks
> Manu :o)
Enterrottacher Andreas
[EMAIL PROTECTED]
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: compression and encryption
Date: Fri, 10 Sep 1999 21:39:06 GMT
In article <7rbafg$[EMAIL PROTECTED]>, "Shaun Wilde"
<[EMAIL PROTECTED]> wrote:
>Okay
>
>I gather from the general consensus that compression is better done before
>as long as the compressor leaves no known header information that could then
>be exploited after an attacker has tried a key.
You have to be very careful the information that the cmpression can leave
is more than just a HEADER you should check if the method is one to one.
If it is then it the compression is not adding information that an attacker
can use.
>
>Why did originally I ask this question?
>
>Well I am a MFC/ATL developer and I am currently learning on how to make
>context-menu handlers and I thought wouldn't it be nice to make a DLL that
>would
>compress and encrypt any file or group of files and folders of the
>context-menu. I
>know it has probably been done before - but hey I am learning. This then led
>me onto,
>should I use the MS supplied stuff such as CryptoAPI and LZxxx or CAB
>(compression)
CHeck ther compression to see if it is one to one.
>routines or should I use non MS stuff.
>
>For a first pass I intend to use the MS stuff (don't flame me) as I am still
>learning
>and it has plenty of documentation. However I would then like to improve it
>by adding
>other encyption systems (and compression) as time goes by (and as time
>permits).
>
>My problem
>
>What I do find is a lot of source code but no real explanation on how to
>implement it.
>What comments are in there are too technical (in the crypto sense) and do
>not help
>the beginner to this field to implement the code. I have the twofish source
>code but
>I am still struggling on how to encrypt and decrypt a file. What is needed
>is such examples.
>
>I hear you all say - 'but if you do not understand it then you might
>implement it badly and
>thus make bad encryption'. And I say as a developer who has lots of other
>things on his
>plate as well as trying to keep up with everything else that MS is
>changing - 'I will use the
>crypto that has the best defined how to implement documentation and (even
>better if it
>has what to look out pitfalls)'.
>
>I have as yet to find such sites - they may exist I just haven't found them
>yet. As you know
>MS has plenty of documentation and plenty of examples. When you are a
>developer and
>asked to put encryption into the product you will take the easier options
>and unfortunately
>MS (and the NSA - hehehe) knows that.
>
Odds are you will not understand my encyrotion methods from the code
unless you know C. But the adaptive huffman compression is very easy to
follow and I have several examples and working code at
http://members.xoom.com/ecil/compress.htm
h2com.exe is the one to one adaptive huffman compression.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
Reply-To: "Daniel Roethlisberger" <[EMAIL PROTECTED]>
From: "Daniel Roethlisberger" <[EMAIL PROTECTED]>
Subject: Re: Looking for Completely-Free Strong Algorithms
Date: Fri, 10 Sep 1999 22:30:01 +0200
This Block Cypher Lounge is fairly out of date I'd say...
No AES canditates to be found there.
/Dan
--
[EMAIL PROTECTED]
PGP Key ID 0x326DA8BA
virus scanners, eat eicar.com:
X5O!P%@AP[4\PZX54(P^)7CC)7}$EICAR-STANDARD-ANTIVIRUS-TEST-FILE!$H+H*
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Looking for Completely-Free Strong Algorithms
Date: Fri, 10 Sep 1999 16:14:36 -0400
Reini Urban wrote:
>
> sorry off topic, but patents are such a mess.
> and largely an american phenomenon only.
Not true, consider IDEA.
paul
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Looking for Completely-Free Strong Algorithms
Date: Fri, 10 Sep 1999 16:15:03 -0400
Paul Crowley wrote:
>
> Underspecified error! What *other* characteristics would you like the
> algorithm to have?
>
> * completely-free (stated)
>
> * strong (of course)
>
> * free source code available (I'll assume)
>
> * fast (I assume - how important is this?)
>
> It sounds like you're encrypting streams of data. How long do the
> streams tend to be? Do you mind if it's a native stream cipher (like
> RC4)
I don't think RC4 is unencumbered.
paul
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: comp.security.unix
Subject: Re: unix clippers that implement strong crypto.
Date: Fri, 10 Sep 1999 21:51:54 GMT
In article <[EMAIL PROTECTED]>, Armin Ollig <[EMAIL PROTECTED]>
wrote:
>Martin Pauley wrote:
>>
>> Armin Ollig <[EMAIL PROTECTED]> wrote:
>> > AFAIK it is better to first encrypt and then compress the data.
>> > This means more cpu cycles but better security, because the compression
>> > may leave a characteristic pattern that may be usefull for
>> > crytpanalysis. ?!
>>
>> I compress first and then encrypt, for two reasons:
>> 1. an encrypted file does not compress well; quite often an encrypted
>> file will increase in size when you try to compress it.
>
>Agreed, but we do not care for increased sized or wasted CPU cycles.
>We have plenty of CPUs :-)
>
>> 2. compressed files contain less of a pattern than most plain files.
>> This is by design, since most (all?) compression algorithms work by
>> detecting and removing patterns. In contrast, plain files tend to
>> have well-defined patterns, which is why they compress.
>
>Lets discuss that in detail.
>Text files e.g. have patterns that are very easy to spott.
>While binary files can be random or have patterns too. That depends on
>the structur of the content (well obviously :-).
>
>So imho the problem with compressing first is the cryptoanalysis would
>exactly know what is behind the encrypted stream. Knowing the first few
>bytes behind the encryption is a lot already.
>
>To make that clear, here's an example of what i mean:
>
>1. Make 3 files of random data, 512 bytes each
> dd if=/dev/urandom of=random1 count=1 bs=512
> dd if=/dev/urandom of=random2 count=1 bs=512
> dd if=/etc/passwd of=text1 count=1 bs=512
>
>2. Compress all of them
> gzip random* text1
>
>3. Take the first few (4) bytes of each compressed file
> dd if=random1.gz of=firstbytes1 bs=4 count=1
> dd if=random2.gz of=firstbytes2 bs=4 count=1
> dd if=text1.gz of=firstbytes3 bs=4 count=1
>
>4. Compare:
>$ diff firstbytes1 firstbytes2
>$ diff firstbytes1 firstbytes3
What you have is a problem that is common with most compression methods
They leave information that makes the job easier for the attacker. Some have
the info in the first few bytes. But if you use a method that is one to one no
information is added. By one to one it should have the 2 following propertes.
1) if you compress any file "A" and then decompress you should get "A" back.
All compression methods out there do this.
2) if you decompress any file "A" and then compress the result you should get
"A" back. My adapative huffman compressors are the only ones that I know of
that do that.
However if you compress 2 filles that are exactly the same in the front. You
still have common front ends on the files when you do a one pass compress.
I have code that uses a less aggressive pass over the file in the reverse
direction so that if 2 files and identical and only a small change exits in
the center of the file. There is a good chance the how file when compressed
the way I show will be totally different.
Take a look and check example source code is there for all
http://members.xoom.com/ecil/compress.htm
>
>
>If i use gzip first, the crypto analysis knows exactly the first 4 bytes
>of my clear text stream. 4 bytes are a lot of bits already. And the gzip
>pattern (iam sure it *does* make one...) is constant among the complete
>data stream, whereas the patterns of different files may vary every X
>bytes.
>
>> I'm not an encryption expert, but I met one once! :-)
>
>....needless to say: nor am i :-)
>
>best regards,
>--Armin
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
Reply-To: "karl malbrain" <[EMAIL PROTECTED]>
From: "karl malbrain" <[EMAIL PROTECTED]>
Subject: Re: compression and encryption
Date: Fri, 10 Sep 1999 14:24:49 -0700
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote in message
news:7rbq9n$1qh2$[EMAIL PROTECTED]...
> In article <7rbafg$[EMAIL PROTECTED]>, "Shaun Wilde"
<[EMAIL PROTECTED]> wrote:
> >Okay
> >
> >I gather from the general consensus that compression is better done
before
> >as long as the compressor leaves no known header information that could
then
> >be exploited after an attacker has tried a key.
> You have to be very careful the information that the cmpression can
leave
> is more than just a HEADER you should check if the method is one to one.
> If it is then it the compression is not adding information that an
attacker
> can use.
> >has what to look out pitfalls)'.
The difficulty started with an attempted to value assets at the glass plant.
We were supposed to differentiate tokens from tickets. What's the
difference??? Karl M
> >I have as yet to find such sites - they may exist I just haven't found
them
> >yet. As you know
> >MS has plenty of documentation and plenty of examples. When you are a
> >developer and
> >asked to put encryption into the product you will take the easier options
> >and unfortunately
> >MS (and the NSA - hehehe) knows that.
> >
> Odds are you will not understand my encyrotion methods from the code
> unless you know C. But the adaptive huffman compression is very easy to
> follow and I have several examples and working code at
> http://members.xoom.com/ecil/compress.htm
> h2com.exe is the one to one adaptive huffman compression.
>
>
>
> David A. Scott
> --
> SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
> http://www.jim.com/jamesd/Kong/scott19u.zip
> http://members.xoom.com/ecil/index.htm
> NOTE EMAIL address is for SPAMERS
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Looking for an asymmetric system
Date: 10 Sep 1999 21:29:15 GMT
Actually, according to NIST, 256 bit ECC (or slightly more) is appropriate for
128-bit AES. For DSA, the appropriate keysize for 128-bit AES is 3072, again
according to NIST.
Don Johnson
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Looking for Completely-Free Strong Algorithms
Date: Fri, 10 Sep 1999 15:22:40 -0600
Daniel Roethlisberger wrote:
>
> This Block Cypher Lounge is fairly out of date I'd say...
> No AES canditates to be found there.
At least not on the page cited in the earlier post. But see
http://www.ii.uib.no/~larsr/aes.html
which is at the same site.
John M.
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: some information theory
Date: Fri, 10 Sep 1999 14:33:08 -0400
>
> Since you are going to talk entropy. In a one to one compression scheme
> entropy will be the same before compression and after compression. But
> the entropy density ( entropy per bit ) will increase if the file gets
> smaller. However if the compression method sucks you may be helping
In cryptography, you are not concerned with the enctropy of a supposed source
spitting out the next bit of your clear text, you are concerned with the entropy
of a source spitting out whole clear text. The important mesure is the entropy
of a message (the plaintexts), not the entropy of the bits of a message...
------------------------------
From: [EMAIL PROTECTED] (Larry Lee)
Subject: NSAKEY as an upgrade key (Was: NSA and MS windows)
Date: 10 Sep 1999 22:26:58 GMT
"Thomas J. Boschloo" <[EMAIL PROTECTED]> writes:
>Larry Lee wrote:
>>
>> What is of interest though, is that if a 512 bit composite number
>> can be factored, then factoring Microsoft's 128 bit composite number
>> ought to be much simplier perhaps on the order of days or weeks.
>You are confusing asymmetric key length with symmetric key length.
>A 512 bit asymmetric key is about as strong as a 64 bit symmetric key
>(source: <http://axion.physics.ubc.ca/pgp-attack.html>) but it also
>assumed that a 512 bit key would require 30000 mips, while in reality it
>took 8000 mips. So it is probably a few (like 2) bits less.
>Thomas
>--
Well I read and reread the webpage and I'm still not clear on what is meant
by asymetric. If I understand that page correctly, the terms symetric
and asymetric would seem to denote a difference in the algorithm, not
in the keys.
Please tell me where I went wrong.
I assumed that Microsoft is using the RSA algorithm.
I assumed that both the 512 bit key and the Microsoft's 128 key are
the composite number part of the public keys.
I assume that in this case 'breaking the cypher' means to factor the
composite number so that the private exponent may be computed.
I assume (for no good reason) that the factors of the 512 bit number
would both be roughly 256 bits long, and certainly not 64 and 446 bits.
Is ths what you mean by asymetric?
Does the exponent in the RSA algorithm give some clue to the size
of the smaller factor or was this information provided separately?
Did the people who factored the 512 bit number get lucky or is this
a realistic expectation of what it takes to factor this size number.
I don't understand why it is only slightly less difficult (2 bits?)
to factor a 128 bit than it is to factor a 512 bit number.
Can this be explained in simple terms.
I very much appreciate your patience with a beginner.
Larry
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Looking for Completely-Free Strong Algorithms
Date: Fri, 10 Sep 1999 15:55:14 -0700
[response inline]
> * free source code available (I'll assume)
Preferably, I'm trying to wean my employer off of BSAFE, because they
insist on chosing the weakest algorithms, I suggested that we switch from
RC2, and they suggested DES. I figure if I package it up for them I can
chose to only add good systems.
> * fast (I assume - how important is this?)
Not overly, but it is a consideration. Mostly I'm looking to build a sizable
list of good, royalty-free ciphers (see above). Speed would only be a
consideration for a few customers, for all others they wouldn't notice a 50%
cut in overall speed. The most time critical stream needs to be able to
handle 1KB in under 1/2 second, but this is only done a few hundred times a
day (at most). These figures are for what we expect to be a Pentium-2 300 to
be the normal minimum system.
> How long do the streams tend to be?
In one session there are several different streams, ranging from one <1KB to
one that I've seen at slightly over 1GB, the average though can be expected
at about 1MB
> Do you mind if it's a native stream cipher (like
> RC4) or a block cipher (eg Blowfish) in a chaining mode?
I tend to trust chained ciphers more (longer tradition to understand them
fully), but I wouldn't mind a proven stream cipher.
> Do you carehow much memory the cipher uses in its normal operation?
Encryption I'd like to come in at under 6MB and decryption under 2MB, not a
big issue, security is the primary issue
>Does it make a difference if that memory stays the same for all keys (like
> Rijndael) or has to be re-written for a new key (like Twofish)?
Due to our product all the information would be kept seperated regardless of
key (at least for the time being) so it's not an issue
------------------------------
From: "ME" <[EMAIL PROTECTED]>
Subject: Re: Digital Certificates and Authentication
Date: Fri, 10 Sep 1999 07:29:23 +1000
Yes, you do.
Either :
a. the certificate becomes the token, implying logical possession of the
Public/private key pair gives access to the full level of the user's
privileges.
b. The certificate is protected on the user's machine by the user managed
password
c. The user password is verified at a trusted location - which is far more
likely to be the server than the workstation.
d. The certificate is accessed by presentation of password or biometric
controlled smartcard using secure input devices, bypassing the user's
operating system for certificate access.
Most people are building systems around model b and C to day.
We'll need to get to d before there is any user control over their on-line
identity, once that is acheived, there will be recipient confidence (maybe
even trust) in identities supplied by server access.
Lyal
[EMAIL PROTECTED] wrote in message <7r8h6a$f29$[EMAIL PROTECTED]>...
>This may be a dumb question, but let's say you have a system that server
>that requires authentication to access. My question is, if the
>authentication process uses Digital Certificates, do you need to deal
>with passwords? Since you can verify a Digital Certificate for
>authenticity, why bother with a password?
>
>Casey
>
>
>Sent via Deja.com http://www.deja.com/
>Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Double encryption is patented (mabey)
Date: Fri, 10 Sep 1999 21:49:30 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote, in part:
>(Length preserving is the
>main point of the patent, isn't it?)
It lets you do without a "good source of randomness", which is a hard
thing to obtain on a PC.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
Date: Fri, 10 Sep 1999 17:59:54 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: 512 bit number factored
Bob Silverman wrote:
> In article <[EMAIL PROTECTED]>,
> Dylan Thurston <[EMAIL PROTECTED]> wrote:
> > Bob Silverman <[EMAIL PROTECTED]> writes:
> >
> > > I'd also like to address one more issue. Everyone keeps harping on
> > > the fact that computers are getting faster all the time. Current
> claims
> > > are 2x every 18 months. Even if * this* can be sustained for 20
> years
> > > (and I don't know either way), I must point out that NFS depends
>
> <snip>
>
> >
> > This confuses me a little. From earlier comments (about the
> > impossibility of paging) I had understood that the access pattern for
> > solving the matrix was essentially flat
>
> The comments above were aimed at the *sieving* phase. Faster
> computers don't help sieving as much as they should.
>
> Most primes in the factor base are large relative to cache size.
> Sieving on them generates a cache miss. One needs to add a value
> to a byte in memory which is not cache-resident. The latency to do this
> becomes quite important. Careful sieve interval partitioning can
> alleviate this problem somewhat, but it can't eliminate it completely.
>
> If you want to add 1 to locations x, x+p, x+2p, x+3p etc.
> and p > cache-size you generate cache misses and this slows down the
> CPU.
This is precisely the kind of predictability needed to eliminate the
latency problem. A simple-minded cache controller might not notice your
access pattern, but this is not hard to fix. Also, the 686 and 786
generations of processors allow control of the cache via PREFETCH
instructions. Essentially you can move cache pipelining into your higher
level code. Thus while processing X+NP one requests the loading of
X+(N+1)P.
Like blocking IO this kind of incremental refinement can yeild dramatic
performance improvements; perhaps eliminating main memory latency
completely from that phase of the operation.
>
>
> ; that it was impossible to
> > predict where future references would be. But now you ask for bigger
> > caches, which are useful exactly when you do have locality of
> > reference. Can you explain this a little?
>
> See above. Sieving does not have good locality of reference except
> for the small primes.
Locality is not critical. It is a crude substitute for predictability. If
you _have_ predictability there is no need to settle for mere locality.
>
>
> >
> > Also, is it really memory _latency_ that matters so much?
>
> Yes, it is.
>
> --
> Bob Silverman
> "You can lead a horse's ass to knowledge, but you can't make him think"
>
> 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
******************************
