Cryptography-Digest Digest #638, Volume #11 Wed, 26 Apr 00 14:13:01 EDT
Contents:
Re: factor large composite (Patrik Larsson)
Re: factor large composite ([EMAIL PROTECTED])
Vs: sci.crypt think will be AES? ("Helger Lipmaa")
Re: factor large composite (Johnny Bravo)
Re: new Echelon article (Lincoln Yeoh)
Re: sci.crypt think will be AES? ("Trevor L. Jackson, III")
Re: Requested: update on aes contest (wtshaw)
Re: sboxes for the bored... (Tim Tyler)
Re: U-571 movie ([EMAIL PROTECTED])
Re: new Echelon article (Volker Hetzer)
Re: Regulation of Investigatory Powers Bill ("Trevor L. Jackson, III")
Re: factor large composite (David A Molnar)
Re: Requested: update on aes contest ("Trevor L. Jackson, III")
Re: Magnetic Remenance on hard drives. ("Trevor L. Jackson, III")
[OT] Re: U-571 movie ([EMAIL PROTECTED])
Re: Looking for a *simple* C Twofish source ([EMAIL PROTECTED])
Re: Requested: update on aes contest (lordcow77)
Re: ECC's vulnerability to quantum computing (Mike Rosing)
Re: U-571 movie (Mike Rosing)
----------------------------------------------------------------------------
From: Patrik Larsson <[EMAIL PROTECTED]>
Subject: Re: factor large composite
Date: Wed, 26 Apr 2000 14:12:43 GMT
> > .... and if s/he won't be bribed, or may tell you the wrong answer,
> > you can simply read the factors from the computer storage or
> > reverse-engineer the software that uses them. And then you can be
> > sure you have the right answer. It may be difficult to get at the
> > computer to do this, but it's much easier than factoring the damn
> > thing any other way.
>
> It may be quicker, but it's certainly not easier since it requires
> an active involvement from you.
>
> If you instead decide to let some computer try to factor the number,
> you can just leave the computer alone while it's doing its work, and
> do other things instead.
This would only work if you completely solved the energy consumtion problem,
even if you had a computer that could go on for ever, the computer still would
require
energy and you'd get some pretty hefty bills after some billions of years of
computing.
It would be needed some active involvement from you to get the money for the bills(
stealing, working etc).
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: factor large composite
Date: Wed, 26 Apr 2000 14:10:38 GMT
Jeffrey Williams <[EMAIL PROTECTED]> wrote:
> Your objection applies only to those for whom market economics apply
> (ie: you, me, business, etc). It doesn't apply to government, which does
> not aim to make a profit. A government may feel the need to have a
> large computer (say a Beowulf cluster, for example) to break codes for
> national security. That need may justify dropping <place insane quantity
> of cash here> on such a computer.
On the contrary, they do aim to at least break even. While the US, for
example, certainly has a large number of impressive machines, I
wouldn't count on them routinely factoring keys.
> Therefore, if you wish to keep your information secret from governments,
> etc, 768 bit RSA may be inadequate.
Considering the average home computer, I would think it'd be less
painfull to obtain the key by survailance than spending $10,000,000 on
the latest crack-o-matic. ;)
One thing I wouldn't count out is chemical interogation. Unlike my
skeptasism at the huge, underground caves full of cracking machines, I
suspect that this is a real option. It would undoubtably leave some
sort of "lost time" in the client's memory but I suspect it's now
possible to do it without leaving traces of an actual interview. Alien
abduction and dreams are two possible covers.
> Bottom line is that it really depends upon your adversary.
Indeed. But for most governments what you need to worry about are the
skilled professionals, rather than the large amounts of money. Witness
the Enigma team, the Manhattan project, the Hoover Dam, the Apollo
program, etc. All well funded, but made possible by several key
players.
--
Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: "Helger Lipmaa" <[EMAIL PROTECTED]>
Subject: Vs: sci.crypt think will be AES?
Date: Wed, 26 Apr 2000 14:47:27 +0300
===== Original Message =====
From: Tom St Denis <[EMAIL PROTECTED]>
Newsgroups: sci.crypt
Sent: Monday, April 24, 2000 10:20 PM
Subject: Re: sci.crypt think will be AES?
> Why I like Twofish. It's fast, it's compact, it's versatile (speed/size
> tradeoffs), it's designed sanely. It's also very good choice for
> hardware. It's also secure the best attack breaks (without whitening)
> only 6 rounds and doesn't work against the full algorithm.
>
> While I think Rijndael and Serpent are perfectly secure algorithms, they
> are not as versatile I don't think.
Rijndael is faster than Twofish on most of the platforms (see
http://www.tcm.hut.fi/~helger/aes
). Also, Twofish has _way too_ slow keyschedule (the fastest bulk encryption
mode of Twofish (that is still slower than Rijndael) requires key scheduling
that is at least 40 times slower than the key scheduling of Rijndael. I find
this to be completely unacceptable in many of the applications.
Also the claimed versatility: necessity to have several implementations, one
for bulk encryption, one for encrypting 20 blocks, etc, is _very_ bad. You
increase your system complexity way too much.
A standard algorithm should be simply implementable. RC6 and Rijndael can be
implemented almost in half-sleep. Twofish can't be, especially its key
schedule.
About security... They only algorithm that has security troubles currently
is RC6. Everything else is currently safe. While the best attacks on Twofish
are currently not very good, this is also a sign of complexity: Twofish _is_
very complex. It is not easy to find attacks on it, however it is also not
easy to prove that attacks don't exist. However, for example Rijndael is
very simple. Thanks to that it is easier to analyse it and hence also find
attacks on it. However, we can also be ensured that if there aren't be new
attacks in some years, there won't probably be any also in the next years.
My own preference is Rijndael or Serpent. More precisely, either 16-round
Rijndael or 24-round Serpent :-). RC6 and MARS are two complex to implement
in hardware. About Twofish I already said. Also from the security viewpoint,
Rijndael and Serpent have the best cost per performance...
Helger
http://www.tcm.hut.fi/~helger
------------------------------
From: Johnny Bravo <[EMAIL PROTECTED]>
Subject: Re: factor large composite
Date: Wed, 26 Apr 2000 11:40:17 -0400
On Tue, 25 Apr 2000 19:52:03 -0700, "Dann Corbit"
<[EMAIL PROTECTED]> wrote:
>Also, I think the computer network cooperation approach would not be
>terribly successful if the effort were focused to steal someone's money, so
>the bazillion computers on the net metaphor won't work to solve the problem.
Sure it would, you just don't tell the network what you are really
doing. For example, SETI@Home is running at around 300% computing
power. What if they had the client working on 2/3 of the computers
trying to break Microsoft's bank codes. It would cost them almost
nothing to do so, since the computing power is free and unused anyway.
There isn't much need to check each SETI packet 3 times. :)
Risk vs reward, sure the chances are next to nil that a large RSA
key will be broken, but if the machines are going to be sitting idle
anyway, why not have them trying to crack it? The cost is nothing,
the payoff is huge, and if you get very, very lucky, you succeed.
--
Best Wishes,
Johnny Bravo
"The most merciful thing in the world, I think, is the inability
of the human mind to correlate all it's contents." - HPL
------------------------------
From: [EMAIL PROTECTED] (Lincoln Yeoh)
Crossposted-To:
alt.politics.org.cia,alt.politics.org.nsa,alt.journalism.print,alt.journalism.newspapers
Subject: Re: new Echelon article
Date: Wed, 26 Apr 2000 16:07:55 GMT
Reply-To: [EMAIL PROTECTED]
On Tue, 25 Apr 2000 16:47:04 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>"Trevor L. Jackson, III" wrote:
>> Legality has little or nothing to do with Justice, that's why she wears a
>> blindfold.
>
>The blindfold symbolizes impartial application of the same law
>to everyone, and the scales symbolize weighing the objective
>evidence.
>
>The *ideal* is that the laws *do* promote justice.
Thing is I recall one prominent US judge ( I think New York) saying that
judges trying to achieve justice are dangerous and they should stick to the
law.
That didn't look good to me.
Laws and judges aren't perfect. However laws do not change by themselves,
so if judges just keep following the law there's less hope for improvement.
Good people in the right places promotes justice. Laws help maintain what
they do.
Cheerio,
Link.
****************************
Reply to: @Spam to
lyeoh at @[EMAIL PROTECTED]
pop.jaring.my @
*******************************
------------------------------
Date: Wed, 26 Apr 2000 12:27:18 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: sci.crypt think will be AES?
Richard Parker wrote:
> Terry Ritter <[EMAIL PROTECTED]> wrote:
> >> Each of the authors has stated that to the best of their knowledge their
> >> algorithms do not infringe on any patent rights. Presumably at least some
> >> of those who are aware of the AES process and who hold a patent that they
> >> feel is infringed upon by one of the AES candidates would have contacted the
> >> author by now.
> >
> > Why would the patent holders contact *anybody*? Patents are about
> > money: licenses and use. It is only when things go into production
> > that patent holders would get serious.
>
> Well, I tend to agree. However, NIST seems to think that patent holders
> should be making the effort to contact them. Here is a quote from NISTs
> notice in the Federal Register:
>
> "NIST reminds all interested parties that the adoption of AES is being
> conducted as an open standards-setting activity. Specifically, NIST has
> requested that all interested parties identify to NIST any patents or
> inventions that may be required for the use of AES. NIST hereby gives
> public notice that it may seek redress under the antitrust laws of the
> United States against any party in the future who might seek to exercise
> patent rights against any user of AES that have not been disclosed to NIST
> in response to this request for information."
>
> Perhaps NIST, in an effort to reduce the odds that a patent on the use of
> AES will be overlooked, is talking tough in order to get patent holders to
> do some work that NIST would otherwise have to do.
AFAICT, patents are not subject to antitrust law because the very essence of the
concept of a patent is the temporally limited monopoly it provides. I suspect NIST
is threatening to use it's arbitrarily deep pockets to sue any patent holder into
non-existence. Typical of an administration whose chief instructed a cabinet
officer (HUD) to "find away around the Constitution".
Note that failure to come forward when called has zero bearing on the validity of a
patent. But such inaction may be an adequate excuse for NIST to threaten
contention of the patent. Conceptually, such a threat could be used as the basis
for an antitrust action against _NIST_.
>
>
> >> Second, several of the AES candidates have been included as options in
> >> standards, such as IPsec and OpenPGP, and a number of implementations of
> >> these standards have included implementations of the AES finalists. The
> >> fact that the authors of these implementations of IPsec and OpenPGP have
> >> apparently not been sued is at least anecdotal evidence that the included
> >> implementations of the AES finalists are not infringing on someone's patent.
> >> Of course there are lots of reasons why someone might choose not to sue, so
> >> this isn't terribly compelling.
> >
> > Well *of* *course* this argument "isn't terribly compelling": A
> > patent lawsuit is for *damages*. The appropriate time to sue for
> > damages is when damages occur. It is going to be rather difficult to
> > prevail in a suit for damages when there *are* no damages.
>
> Ah, but in the case of these implementations of IPsec and OpenPGP there
> could well be damages. These are real products that can be purchased today.
> Patent holders who sell licenses of their patents and believe that a license
> of their patent is necessary for the use of the AES candidates in these
> implementations can claim real damages against the authors. For example,
> someone who holds a patent that is infringed upon by the Twofish algorithm
> could sue today against at least two large companies for significant
> damages.
>
> >> Third, presumably NIST themselves will make an announcement if they come to
> >> the conclusion that one or more of the AES finalists infringes on someone's
> >> patent rights. In fact, NIST has indicated that they have lawyers looking
> >> into this very issue. NIST has also made an effort to request holders of
> >> patents rights to identify to NIST any patents that may be required for the
> >> use of AES.
> >
> > I hold cryptographic patent rights, but NIST has not contacted me;
> > that does testify that their effort has not been universal. I don't
> > see much "effort" being made.
>
> Actually, NIST does not appear to be contacting patent holders, instead
> they're asking patent holders to contact them. They're doing this by press
> releases, announcements in the Federal Register, etc.
No such response is required. Failure to respond cannot be use as a legitimate
basis for loss of patent rights.
>
>
> To me NIST's approach seems like a rather novel way to determine patent
> infringement, but then I'm not a lawyer and one would think that NIST, as a
> division of the Department of Commerce, would have access to good patent
> counsel.
The phrase "would have access to good patent counsel" is probably the cause of the
problem.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Requested: update on aes contest
Date: Wed, 26 Apr 2000 09:43:33 -0600
In article <[EMAIL PROTECTED]>, stanislav shalunov
<[EMAIL PROTECTED]> wrote:
> Having one cipher will make interoperability easier. Right now,
> Blowfish is the de facto standard as far as our interaction with
> different companies is concerned. And having one cipher does help
> development: you don't need several ciphers in various libraries.
>
But that is stupid reasoning since the end uses of encryption are highly
varied. In fact, it is an extension of so much nonthink, excuses for not
thinking about anything in crytography except what is desired by the same
folks that bring you the realities of internet insecurity while preaching
that they are the sole holders of solutions for those critical problems.
Competiton, before, during, and after, are the means of allowing good
means rise to notice. Of course, if you push your position, like MS,
asserting that you decide for all others, you deserve wrath against you
for your wrongdoing.
People who cry, "Stop the world, no more changes," are the ones who should
leave. Making things nice and neat for the lucrative benefit of a few is
antiprogressive. Those that want to be all things to all people are
merely pushing the one-size-fits-all Russian-Boot formula; the convenience
is for them, not for you.
--
(x)(r)(d)[d][c] [s]<x>[i]<o>[g] <a><n>
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: sboxes for the bored...
Reply-To: [EMAIL PROTECTED]
Date: Wed, 26 Apr 2000 16:29:03 GMT
Terry Ritter <[EMAIL PROTECTED]> wrote:
: sci.crypt Tom St Denis <[EMAIL PROTECTED]> wrote:
:>50,000 4x4 sboxes... eh why not.
: The reason why not is that an arbitrary 4x4 box has a reasonable
: chance of being actually *linear*. [...]
Fortunately, this can be simply avoided by testing them.
: In contrast, an arbitrary 8-Bit table is quite likely to be very
: nonlinear: [...]
: "The 4-bit invertible substitutions are surprisingly weak: [...]"
: "In contrast, the 8-bit tables have the opportunity to be far more
: complex [...]"
: "Some of the literature asserts that *random* S-Boxes will have
: various good qualities provided the tables are "large enough" [...]"
Large s-boxes take up too much space in hardware, and chew up your cache
in software. It seems to me that using a potentially large number of
small s-boxes seems to have some advantages over it:
It is practical to test them for non-linearity; and offer guaranteed
minimum levels. When creating a single large s-box, real-time testing
is impractical and thus there's still a /chance/ of linearity (and thus
of weak keys).
If you use enough independent small s-boxes in series the resulting system
can still be made quite strong. If you use a small number of them the
system can be made quite small and fast. Use of a single large s-box does
not appear to offer you a simple way to trade-off between strength
and performance.
If you could easily vary the size of the s-box this might be less of an
issue - but if you only have one s-box you can't change its size without
changing the number of inputs or outputs - which typically has knock-on
effects elsewhere in your design.
The disadvantage is probably additional concern over security as a result
of the greater structure involved.
If a block cypher is usually a large permutation constructed from smaller
ones, it seems sensible to ask how large the smaller components should be.
The possible answers seem to be "as small as possible while retaining
non-linearity" - i.e. 3x3 or possibly 4x4 - "as large as possible
without slowing things down to a crawl" - or "of a variety of sizes".
FWIW, I'm quite attracted to the use of large numbers of smaller s-boxes.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/
Microsoft has performed an illegal operation and will be shut down.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: U-571 movie
Date: Wed, 26 Apr 2000 09:42:06 -0700
On Wed, 26 Apr 2000 19:46:55 +1000, "Don H"
<[EMAIL PROTECTED]> wrote:
>This movie is a complete fiction, even though dramatically well acted --
>about capturing an Enigma machine.
>For controversy about it see Newsgroup >> "alt.movies"
>===========================
>
Well, not complete fiction.
The British did in fact capture an Enigma machine from a U-boat.
Helped Bletchly to work out Naval settings on the machine.
IIRC The code books as well as the latest settings were captured.
there by allowing the British to modify the Machine at Bletchly for
upgrading information from the next series of Enigma.
The Americans never did get wise till late in the war.
Although the Purple and Naval dispatch codes were broken early in
1937. Makes you wonder why Pearl Harbor happened. Sort of like getting
the U.S. involved in WW1. Lies told to the masses.........
Liam
Historian at large
Sed Quis Custodiet Ipsos Custodes?
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Crossposted-To:
alt.politics.org.cia,alt.politics.org.nsa,alt.journalism.print,alt.journalism.newspapers
Subject: Re: new Echelon article
Date: Wed, 26 Apr 2000 16:50:11 +0000
Lincoln Yeoh wrote:
> Thing is I recall one prominent US judge ( I think New York) saying that
> judges trying to achieve justice are dangerous and they should stick to the
> law.
>
> That didn't look good to me.
Personally I think, that's a very good thing.
I'd have a really BIG problem if every judge just decides what he thinks is just.
That would mean that the judges own political/moral agenda would enter the judgement
process in a degree that would make me highly uncomfortable.
What's just is not the judge's to decide, it's an ethical question that gets
decided by society.
That ethics is supposed to shaped into law (which, in turn is supposed to
change over time) by some kind of legislative (and elected) commitee.
If people (or judges) don't like the judgement, they can always lobby
for a new law, thereby going through a proper democratic process.
> Laws and judges aren't perfect. However laws do not change by themselves,
> so if judges just keep following the law there's less hope for improvement.
More people decide about laws (by means of elections) than about judgements.
That means IMHO that justice enacted by the few (judges) is less democratic
than judges following the justice put into law (by politicians, and therefore
by voters).
> Good people in the right places promotes justice. Laws help maintain what
> they do.
So, if you want to change laws, don't become a judge.
Greetings!
Volker
--
Hi! I'm a signature virus! Copy me into your signature file to help me spread!
------------------------------
Date: Wed, 26 Apr 2000 12:59:46 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.scramdisk,alt.computer.security
Subject: Re: Regulation of Investigatory Powers Bill
Scotty wrote:
> If there is some algorithm that you can use to decrypt the data then you are
> required to reveal it. If you do something which causes the 'key' to be
> withheld or destroyed, *after* you have been served with a decryption
> notice, then you are guilty of non-disclosure [that's 2 years in prison].
I suspect the non-disclosure provisions are not the only problem, since they are
mostly aimed at passive resistance (failure to perform a required action). If
you actively resist, such as destroying a key, they you are probably also guilty
of obstruction of justice. Specific actions are much harder to defend that
inactions, so OoJ may be the indictment rather than FtD.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: factor large composite
Date: 26 Apr 2000 16:49:22 GMT
Johnny Bravo <[EMAIL PROTECTED]> wrote:
> nothing to do so, since the computing power is free and unused anyway.
> There isn't much need to check each SETI packet 3 times. :)
Remember the thread here a few months ago on evil and modified SETI@Home
clients?
Thanks,
-David
------------------------------
Date: Wed, 26 Apr 2000 13:15:15 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Requested: update on aes contest
Jerry Coffin wrote:
> The fact is, there's only one way AES will become obsolete within 50
> years: that NIST makes a completely bone-headed decision about it
> now.
This raises an interesting question: what decision could NIST make regarding
the five finalists that could be characterized as "bone-headed". Ignoring
priority/preference ordering there appear to be 31 possible decisions and one
possible nondecision. It is not clear to me that any of these 32 outcomes are
obviously bad including the nondecision.
N.B. the figure of 50 years might cover the period in which AES ciphers are
used to encrypt information, but the lifetime of such encrypted information is
probably much longer. I'd guess at least 100 years (50 year lifetime in
2050), and perhaps as much as 150 (100 year lifetime in 2050).
------------------------------
Date: Wed, 26 Apr 2000 13:16:46 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Magnetic Remenance on hard drives.
"NFN NMI L. a.k.a. S.T.L." wrote:
> Symantec offers data recovery services.
Do they recover overwritten data?
Do you have a reference handy?
> The person who posted that such
> services are not commercially available is a [insert flame here].
>
> -*---*-------
> S.T. "andard Mode" L. ***137***
> STL's Wickedly Nifty Quotation Collection: http://quote.cjb.net
------------------------------
From: [EMAIL PROTECTED]
Subject: [OT] Re: U-571 movie
Date: Wed, 26 Apr 2000 17:17:17 GMT
[EMAIL PROTECTED] wrote:
> The Americans never did get wise till late in the war.
> Although the Purple and Naval dispatch codes were broken early in
> 1937. Makes you wonder why Pearl Harbor happened. Sort of like getting
> the U.S. involved in WW1. Lies told to the masses.........
A good portion of the blame for Pearl Harbor rests with the policy of
not manning the new radar installation on the north shore of the
island 24-7 as well as the officer who told the two techs that were
practicing with the equipment past the closing hour that the planes
they were reading were a delivery of new bombers.
Of course, hindsight is always 20/20. On the morning of the raid,
radar was in its infancy (not even standard on ships yet!) and
_everyone_ knew that the Japanese would _never_ attack the US.
--
Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Looking for a *simple* C Twofish source
Date: Wed, 26 Apr 2000 17:07:09 GMT
In article <8e577t$6v9$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hello,
>
> I'll be happy to hear from anyone who knows of a
> freely available, simple, minimal C
> implementation of Twofish.
>
> By simple I mean: not using pointers, or long and
> complex one-line arithmetic expressions. I am
> trying to make it work on a limited and sometimes
> buggy embedded C compiler.
>
> It does not have to be optimized for anything.
>
> Thank you,
> -Al.
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
Thank you all for your help.
I was aware of the all the free sources you've mentioned. I cannot
compile or use things like "u4byte mk_tab[4][256]" (that's a lot of
RAM too!), let alone "q8(q8(q8(q8(x, 4, n), 3 ,n), 2, n), 1, n)" (from
brian gladman's implementation).
The official ANSI C reference code is even worse in that sense (has ->
pointers, a 256-byte array, "*((DWORD *)b) = Bswap(x)" etc).
Unfortunately I am not a cryptologist and going through the Twofish AES
paper does not help me figure out how to implement the algorithm, since
it is missing a much-needed pseudo-code example. One has to deeply
understand all the math details, and closely follow the figures before
going ahead with any coding. Compare with RC6 (or TEA...)
-Al.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Subject: Re: Requested: update on aes contest
From: lordcow77 <[EMAIL PROTECTED]>
Date: Wed, 26 Apr 2000 10:25:23 -0700
In article <[EMAIL PROTECTED]>,
Jerry Coffin <[EMAIL PROTECTED]> wrote:
>now. If you honestly think anybody can accurately predict
computer
>architecures 50 years for now, then I think the rest of the
world (if
>not necessarily you) will forgive me for dismssing your
statements as
>the ravings of a lunatic.
While nobody can make absolutely precise statements about
computer architectures so far into the future, it is possible to
make some general observations about possible trends. I'll start
by listing some of the more important:
*More functional units, registers
*Increased register width (across all platforms, ranging from
smart cards to high-end installations)
*Increased use of parallelism (single instruction-multiple data
vector style instructions)
*Hardware support for multithreading
*Very large data/instruction caches
*Main memory access will become even more expensive
* 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: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: ECC's vulnerability to quantum computing
Date: Wed, 26 Apr 2000 11:31:04 -0500
[EMAIL PROTECTED] wrote:
>
> I've been reading as much as i could lately (and even understanding a
> very small portion) regarding elliptic curve cryptography. However, I
> have been unable to find any information regarding whether or not
> advancements in quantum computing (which will necessarily debilitate
> factoring based encryption ala RSA via Shor's algorithm), will have any
> effect on ECC.
>
> Bruce Schneier's Nov.1999 Crypto-Gram states that ECC's are based on
> discrete logarithms, yet he mentions that most modern factoring
> algorithms are nearly similar to discrete logarithms. Does this hold
> true for reversible quantum algorithms?
It's a discrete log problem, but the groups are different. The main
difference is that ECC requires a full exponential algorithm and IF
can gain a sub-exponential speed up. All that's for "regular"
computers.
>
> Intuitively, I would assume that ECC does not hold up either, but it
> seems that because of its relative strength at the same key size to RSA,
> maybe if it doesn't, it would still last longer at least, although at
> that point it might be like putting the milk back in the bottle. Or is
> there some fundamental difference that prevents a quantum algorithm from
> working in the group of elliptic curves?
Your intuition is correct. ECC's are polytime solvable on a quantum
computer. There was a talk at the ECC '99 conference about this, but I
don't see it posted on their web page (http://cacr.math.uwaterloo.ca/)
> I'm especially curious because I just turned in a paper to my Physical
> Limits of Computing course regarding this, but had to end it with an "I
> don't know..."
Best thing to do! The basic algorithm requires a whole bunch of
guesses,
so on a QC you get to do all the guessing at once. Odds are good after
a several guessing sessions the QC will give the correct answer.
I think it'd be fun to build a QC. But I need some mighty expensive
toys first :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: U-571 movie
Date: Wed, 26 Apr 2000 11:35:04 -0500
Don H wrote:
>
> This movie is a complete fiction, even though dramatically well acted --
> about capturing an Enigma machine.
> For controversy about it see Newsgroup >> "alt.movies"
> ===========================
Speaking of fiction, any one here read "Black Cipher"? It's a bit
overly
dramatic, but it seems to have most of the buzz words correct. I assume
the
descriptions of the insides of NSA and GCHQ are reasonably close to
correct,
but anyone here who can say otherwise?
I got a laugh at one point where the author describes a supercomputer
called
"Paradox" which is a teraflop machine. Used for code breaking.
Hmmmm....
what does floating point have to do with breaking codes?? Otherwise, he
seems to have the buzz words in the right order :-)
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
******************************
