Cryptography-Digest Digest #510, Volume #11 Fri, 7 Apr 00 18:13:00 EDT
Contents:
Re: Sunday People 26/3/2000: "FORGET YOUR PASSWORD... END UP IN JAIL" (Stephen
Houchen)
Re: Public|Private key cryptography? (lordcow77)
Re: Public|Private key cryptography? (Tom St Denis)
Re: Public|Private key cryptography? (lordcow77)
Re: Schoof's Algorithm (lordcow77)
Re: Schoof's Algorithm (kmchan)
Re: Is AES necessary? ([EMAIL PROTECTED])
Re: Crypto API for C ("Joseph Ashwood")
Re: [Q] Insecurity ("Joseph Ashwood")
Re: Q: Entropy (Bryan Olson)
Re: Public|Private key cryptography? (James Felling)
Re: Schoof's Algorithm ("Michael Scott")
Re: GSM A5/1 Encryption (Paul Koning)
Re: introductory books suggestion (Paul Koning)
Re: Crypto API for C (Tom St Denis)
Re: Public|Private key cryptography? (Jerry Coffin)
----------------------------------------------------------------------------
From: Stephen Houchen <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,uk.politics.censorship
Subject: Re: Sunday People 26/3/2000: "FORGET YOUR PASSWORD... END UP IN JAIL"
Date: Fri, 07 Apr 2000 14:18:27 -0500
> >I the US there is a box left blank for voters to write in their preferred
> >choice if none of the above.
> >The press are required by law to publish the full list of results which as
> >you can imagine runs to many thousand.
> >Mickey Mouse usually comes third in US elections.
>
> I don't know about third, but he usually does show up. Third place has gone
> to the Reform party the past few years, with various other groups like the
> Green Party, Libertarian, etc. etc. showing up way down the list...
>
> But Mickey Mouse does seem to be a popular write-in candidate with somewhere
> around 100 or so votes each presidential election. :) He's been known to get
> more votes than certain other non-animated candidates anyway...
"Non-animated"? You mean like Al Gore....? ;)
S
[EMAIL PROTECTED]
------------------------------
Subject: Re: Public|Private key cryptography?
From: lordcow77 <[EMAIL PROTECTED]>
Date: Fri, 07 Apr 2000 12:51:57 -0700
In article <[EMAIL PROTECTED]>, Tom St Denis
<[EMAIL PROTECTED]> wrote:
>
>>You can't solve a matrix in distributed model since the
required data
>transfer rate would be too high. And alot of steps are
inherantly
>sequential.
>
The assertion that the memory space holding a very large matrix
must be continuous in order for it to be reduced must be
considered in its proper context. Algorithms already exist that
can block the matrix into smaller partitions that can be solved
individually. While there are limits to the parallelism that can
be exploited it would not be a sustainable statement that
the "data transfer rate would be too high." About six or seven
years ago, SGI (then Silicon Graphics) was asked to spec a
system that would be able to compute a (1024)^4 point FFT in
memory. Assuming that each data element was a standard double,
this would imply about 8 terabytes of memory in a single, cache-
coherent NUMA machine. I don't recall the pricing, but I'm sure
that somebody on comp.arch would have more details on this.
* 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: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Public|Private key cryptography?
Date: Fri, 07 Apr 2000 20:06:37 GMT
lordcow77 wrote:
>
> In article <[EMAIL PROTECTED]>, Tom St Denis
> <[EMAIL PROTECTED]> wrote:
> >
> >>You can't solve a matrix in distributed model since the
> required data
> >transfer rate would be too high. And alot of steps are
> inherantly
> >sequential.
> >
>
> The assertion that the memory space holding a very large matrix
> must be continuous in order for it to be reduced must be
> considered in its proper context. Algorithms already exist that
> can block the matrix into smaller partitions that can be solved
> individually. While there are limits to the parallelism that can
> be exploited it would not be a sustainable statement that
> the "data transfer rate would be too high." About six or seven
> years ago, SGI (then Silicon Graphics) was asked to spec a
> system that would be able to compute a (1024)^4 point FFT in
> memory. Assuming that each data element was a standard double,
> this would imply about 8 terabytes of memory in a single, cache-
> coherent NUMA machine. I don't recall the pricing, but I'm sure
> that somebody on comp.arch would have more details on this.
But the problem is even if I could block a portion of the matrix to
solve [or to bring to REF] I would need a high data transfer rate to
share it. You couldn't [for example] do it over the net like
distributed.net does, and a LAN [10-baseT] is too slow as well.
Tom
------------------------------
Subject: Re: Public|Private key cryptography?
From: lordcow77 <[EMAIL PROTECTED]>
Date: Fri, 07 Apr 2000 13:11:17 -0700
In article <[EMAIL PROTECTED]>, Tom St Denis
<[EMAIL PROTECTED]> wrote:
>And unless we make some 'quantum' leap [excuse the pun] in
either they
>will not be solvable. I cannot forsee in the near future [20
years] any
>computer with more then say a couple gigs of high speed ram.
ASCI Red (Intel)? ASCI Blue Mountain(SGI)? ASCI Blue Pacific
(IBM)? I know that each of these machines has multiple terabytes
of memory. I believe that ASCI White (awarded to IBM) is
scheduled for completion around summer or fall of this year and
should have even more memory. Then we have the T3E installations
throughout the world, with a potential memory capacity also in
the terabyte range and memory I/O bandwidths sustainable in the
hundreds of gigabytes range. By 2010, I would not be surprised
to see ASCI machines with tens or even hundreds of terabytes of
memory (and operating in the tens and hundreds teraflops range).
Still not enough to factor a 1024-bit composite, but I wouldn't
discount progress as much as you do.
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: Schoof's Algorithm
From: lordcow77 <[EMAIL PROTECTED]>
Date: Fri, 07 Apr 2000 13:16:32 -0700
In article <[EMAIL PROTECTED]>, Robert Harley
<[EMAIL PROTECTED]> wrote:
>Point counting, in characteristic 2, is a solved problem: it's
just
>that nobody knows it yet. =:-)
Are there any possibilities for the algorithm to be extended to
eliptic curves defined modulo arbitrary prime numbers?
* 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: kmchan <[EMAIL PROTECTED]>
Subject: Re: Schoof's Algorithm
Date: Sat, 08 Apr 2000 04:02:50 +0800
I'm interest to learn too. Please add me on the mailing list too.
Thanks a lot !
-- kmchan
Mike Rosing wrote:
> Robert Harley wrote:
> > The algorithms involved are fairly complicated so it hardly makes
> > sense to attempt a summary here! Two colleagues and I have only just
> > started work on a tech-report describing the method we use, so it will
> > be quite a while before that is ready. However my implementation is
> > well advanced and is a lot faster than what has been done before.
> > Point counting, in characteristic 2, is a solved problem: it's just
> > that nobody knows it yet. =:-)
>
> Very cool. Put me on the mailing list for a copy of that report!
> I've almost figured out how to compute a j-invariant polynomial, so
> it'll
> be nice to find out I don't actually have to :-)
>
> Patience, persistence, truth,
> Dr. mike
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Is AES necessary?
Date: Fri, 07 Apr 2000 20:18:52 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> The speed argument is relevant for some applications, but for the
> majority not, in my humble opinion. If the processing time is
> longer, the opponent needs correspondingly more time to brute force,
> and that increase of time could under circumstances change his
> cracking from feasible to infeasible. For hardware implementation
> I conjecture that one could use some kind of pipelining to
> essentially reduce the time factor.
I doubt this very much. If I had to guess, I'd say mass storage
devices and high-speed links are going to be the fastest growing
encryption market for some time to come. In particular, encrypted
private networks over public ones.
With the amount of data being stored almost everywhere steadily
increasing, and the speed of the average network approaching
staggering, speed will most likely be one of the top two
considerations for most people chosing a cipher.
--
Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Crypto API for C
Date: Fri, 7 Apr 2000 12:51:38 -0700
> P.s.: Hmm no ElGamal yet ... RSA is still patented, isn't
it ?
Actually RSA is only the beginning of the problems, IIRC
IDEA is also patented, and RC5 and RC6 are still under
various reservations.
Joe
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: [Q] Insecurity
Date: Fri, 7 Apr 2000 12:49:50 -0700
It may be cryptographically secure, but there is no
guarentee that it is from just that. A quick example is:
01001100011100001111....
which is simply n-0's n-1's repeat after incrementing n.
This is a clear example that it is certainly not suitable
for cryptography, but meets those criteria. Try putting it
through DIEHARD, it gives a good estimate to the randomness,
a cryptographically secure rng should have p-values
distributed across [0,1] almost equally.
Joe
"David C. Oshel" <[EMAIL PROTECTED]> wrote
in message
news:[EMAIL PROTECTED]...
> If a bytestream never repeats itself in a universe bounded
by proton decay,
> and produces 1 and 0 in every bit position in the ratio
1:1 on average, and
> passes Chi-square, why is it still not cryptographically
secure?
>
> --
> David C. Oshel mailto:[EMAIL PROTECTED]
> Cedar Rapids, Iowa http://pobox.com/~dcoshel
> ``Tension, apprehension, and dissension have begun!" -
Duffy Wyg&, in Alfred
> Bester's _The Demolished Man_
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: Fri, 07 Apr 2000 20:06:54 GMT
Mok-Kong Shen wrote:
> Bryan Olson wrote:
[...]
> > Suppose Alice will shuffle a deck of 52 cards, and choose
> > one at random. She will not look at it, but will show it to
> > Bob, who will then give her one of two (truthful) messages:
> > either "the card is an ace" or "the card is not an ace."
[...]
> > The entropy of the message space, in bits is
> >
> > 48/52 * log_2(52/48)
> > + 4/52 * log_2(52/4)
> > = 0.391
[...]
> Could you please explain a bit how you derived the formula for 0.391?
Probability of "the card is not an ace" = 48/52
Probability of "the card is an ace" = 4/52
The entropy of a message space is,
sum over all possible messages x:
probability(x) * log(1/probability(x))
You will more commonly see this written as the equivalent:
sum over all possible messages x:
- probability(x) * log(probability(x))
> What would be the entropy of the alternative message 'the card is not
> an ace'?
log_2(52/48) = 0.115 bits
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Subject: Re: Public|Private key cryptography?
Date: Fri, 07 Apr 2000 15:33:26 -0500
100Base is cheap and gigabit ethernet is not priced ridiculously high
though.
Tom St Denis wrote:
> lordcow77 wrote:
> >
> > In article <[EMAIL PROTECTED]>, Tom St Denis
> > <[EMAIL PROTECTED]> wrote:
> > >
> > >>You can't solve a matrix in distributed model since the
> > required data
> > >transfer rate would be too high. And alot of steps are
> > inherantly
> > >sequential.
> > >
> >
> > The assertion that the memory space holding a very large matrix
> > must be continuous in order for it to be reduced must be
> > considered in its proper context. Algorithms already exist that
> > can block the matrix into smaller partitions that can be solved
> > individually. While there are limits to the parallelism that can
> > be exploited it would not be a sustainable statement that
> > the "data transfer rate would be too high." About six or seven
> > years ago, SGI (then Silicon Graphics) was asked to spec a
> > system that would be able to compute a (1024)^4 point FFT in
> > memory. Assuming that each data element was a standard double,
> > this would imply about 8 terabytes of memory in a single, cache-
> > coherent NUMA machine. I don't recall the pricing, but I'm sure
> > that somebody on comp.arch would have more details on this.
>
> But the problem is even if I could block a portion of the matrix to
> solve [or to bring to REF] I would need a high data transfer rate to
> share it. You couldn't [for example] do it over the net like
> distributed.net does, and a LAN [10-baseT] is too slow as well.
>
> Tom
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: Schoof's Algorithm
Date: Fri, 7 Apr 2000 22:01:20 +0100
"lordcow77" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <[EMAIL PROTECTED]>, Robert Harley
> <[EMAIL PROTECTED]> wrote:
> >Point counting, in characteristic 2, is a solved problem: it's
> just
> >that nobody knows it yet. =:-)
>
> Are there any possibilities for the algorithm to be extended to
> eliptic curves defined modulo arbitrary prime numbers?
>
That's a done deal as well. See http://indigo.ie/~mscott for a free
implementation of the Schoof-Elkies-Atkin algorithm.
Mike Scott
> * 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: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: GSM A5/1 Encryption
Date: Fri, 07 Apr 2000 16:09:08 -0400
Paul Schlyter wrote:
> ...
> Remember one thing though: a scanner where merely the analog
> demodulator is replaced by some suitable digital decoder won't help
> you that much here. GSM implements time multiplexing as well as
> frequency hopping. ...
>
> If/when digital scanners get readily available, I would guess that
> the GSM operators counter this by letting the frequencies hop more
> often. To successfully intercept a phone call, one scanner wouldn't
> be enough -- you'd need a whole array of scanners, each intercepting
> one frequency sub-band.
No, all you need is a few hundred dollars of high speed A/D and
DSP stuff. No big deal. Oh yes, and appropriate software.
Take a look at the Analog Devices website some time. It's
impressive what you can do these days.
After all, you're just duplication the function of the base
station receiver, and lots of companies are working very hard
to drive the cost of that technology to very small numbers.
I have a software radio for amateur radio purposes in the works.
The back end interface isn't suitable for doing the sort of thing
we're talking about (too slow, it's a printer port...) and the
analog front end mixer is missing, but apart from that it's
the same kind of hardware we're talking about here. Some of
the chips were samples, which helped -- the most expensive part
was the PC board. If I'd paid list price for everything, it
would have been $500 at the very most.
Finally, it's all well and good to talk about whether A5 is good
enough to keep Radio Shack at bay. So? When people worry about
their privacy, is that all they worry about? I don't think so.
paul, ni1d
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: introductory books suggestion
Date: Fri, 07 Apr 2000 16:10:47 -0400
[EMAIL PROTECTED] wrote:
>
> I am an Electrical Engg. graduate, starting out on cryptography &
> cryptology. I need some references to introductory books on
> cryptography, bearing in mind I have a good background in algebra &
> introductory coding theory, hence I would prefer a mathematically-neat
> book with theorems, lemmas & proofs. Suggestions, kind senors &
> senoritas?
Handbook of Applied Cryptography, Menezes et al., CRC press.
Also, less theoretical: Applied Cryptography, Schneier, Wiley.
paul
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Crypto API for C
Date: Fri, 07 Apr 2000 21:08:54 GMT
Joseph Ashwood wrote:
>
> > P.s.: Hmm no ElGamal yet ... RSA is still patented, isn't
> it ?
> Actually RSA is only the beginning of the problems, IIRC
> IDEA is also patented, and RC5 and RC6 are still under
> various reservations.
Bah who cares, I give credit where it's due.
Tom
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Public|Private key cryptography?
Date: Fri, 7 Apr 2000 16:03:42 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> I don't think you actually read the paragraph. A 1ghz cpu is *not*
> double the *throughput* of a 500mhz cpu.
Yes I did and yes it IS! You're just ignoring reality.
> Internally it may be, but you
> can't store 100's of MB/tb/etc.. of required data in a 128 kb cache...
Which is why they've gone from PC100 memory to PC133, RDRAM, dual
data rate RAM, etc.
> And unless we make some 'quantum' leap [excuse the pun] in either they
> will not be solvable. I cannot forsee in the near future [20 years] any
> computer with more then say a couple gigs of high speed ram.
Tom, your ability to ignore reality is simply astounding. you say
you don't foresee "any computer" having more than a couple gigs of
high speed RAM in the next 20 years.
The reality is that supercomputers typically had around 32 Gig of RAM
somewhere around 8 to 10 years ago.
In fact, machines with a couple gigs of RAM, or so, have existed for
the LAST 20 years (speaking in round numbers). 20 years AGO they
were quite rare, but a few existed.
At the _PRESENT_ time there are a number of research level
supercomputers with over a terabyte of RAM apiece. IOW, RIGHT NOW a
high-end machine has roughly 500 times as much memory as you're
saying won't happen in the next 20 years.
Again, speaking only of the present, a machine with a couple gigs of
RAM is NOT a supercomputer at all. It's more likely a fairly common
web search engine, mail server, or perhaps helping run a bank or
handling airline reservations.
The machines you're saying won't exist yet 20 years from now have
already existed for the LAST 20 years or so. High end machines right
now have a LOT more memory than you're predicting for 20 years into
the future.
I'll give my prediction for 20 years from now: if you look carefully,
you'll be able to find a machine with at least a 10 Ghz processor and
at least 2 Gig. of RAM in a dumpster behind a grade school even
though it still works perfectly. It was donated to the school when
it was too old for the original owner to use it for real business
applications anymore. The school put it to use for a few years, but
it's now become so thoroughly obsolete that even a grade school can't
find a use for it anymore, so it's being thrown away even though it
still works just as well as it did when it was new.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
** 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
******************************
