Cryptography-Digest Digest #63, Volume #11 Mon, 7 Feb 00 12:13:01 EST
Contents:
Re: RSA survey (NorasToy)
Re: Strip Security (Gordon Walker)
Re: Strip Security (Gordon Walker)
Re: Hill Climbing (G Winstanley)
Re: NIST, AES at RSA conference (John Savard)
Re: NSA opens up to US News (John Savard)
Re: NSA opens up to US News (Terje Mathisen)
Re: Court cases on DVD hacking is a problem for all of us (Alan Braggins)
Need help for security program ("etbear")
Re: Court cases on DVD hacking is a problem for all of us (Eric Lee Green)
My very best communication in 1999 - Yeltsin resign - July, 1999 (Markku J.
Saarelainen)
Re: Court cases on DVD hacking is a problem for all of us (Samuel Paik)
Re: Hill Climbing ("Michael Darling")
Re: Factorization ("Tony T. Warnock")
Re: NSA opens up to US News (John Savard)
Re: TLS: What is the purpose of the client certificate request? (Anne & Lynn Wheeler)
Read all my message at alt.politics.org.cia (Markku J. Saarelainen)
Re: Math contest winner from Ireland... (Jean-Jacques Quisquater)
Re: KEA, and XDH (Doug Stell)
----------------------------------------------------------------------------
From: NorasToy <[EMAIL PROTECTED]>
Subject: Re: RSA survey
Date: Mon, 07 Feb 2000 14:19:29 +0100
Tom St Denis schrieb:
> Just a quick survey... What size of RSA key would you feel safe with
> for your crypto needs?
Depends. If I have to send some message which would cause the
destruction of the world if the wrong persons read it I would
state a 4 MB (64 Megabit) Key would be okayish. If I have to
send my mum "hello I'm fine byebye" I would even trust a 1
Kilobit key.
Well because 512 bit has been broken recently, I've no idea
which size is enough. I simply don't know what mathematical
methods have been used to break the 512 bit key, and how
well they operate for larger keys, and how fast someone will
find ways to break 1024, 2048, and 4096 bit keys. I think
4096 might be okayish for the moment.
------------------------------
From: [EMAIL PROTECTED] (Gordon Walker)
Crossposted-To: comp.sys.palmtops.pilot,alt.comp.sys.palmtops.pilot,comp.sys.handhelds
Subject: Re: Strip Security
Date: Mon, 07 Feb 2000 14:18:12 GMT
On Fri, 04 Feb 2000 10:10:33 GMT, [EMAIL PROTECTED] ([EMAIL PROTECTED]) wrote:
>I think he could just look you up, threaten your life, and you spill
>the key. Ever had your fingernails pulled off? In other words, you're
>likely the weakest link, IF you have anything worth looking you up.
Delightful. Thank you for that interesting perspective.
--
Gordon Walker
------------------------------
From: [EMAIL PROTECTED] (Gordon Walker)
Crossposted-To: comp.sys.palmtops.pilot,alt.comp.sys.palmtops.pilot,comp.sys.handhelds
Subject: Re: Strip Security
Date: Mon, 07 Feb 2000 14:18:12 GMT
On Fri, 04 Feb 2000 11:09:28 GMT, [EMAIL PROTECTED]
(Highdesertman) wrote:
>Thanks Gordon for the clarification. I now understand better the
>meaning of your original message.
>
>One of the things that has always nagged at me in my quicken online
>banking, is the fact that the RSA encryption used to secure the
>internet connection with the quicken processing center limits the
>password to a four digit numeric combination. In my way of thinking,
>very easy to crack. Unless of course, there is some magic that quicken
>is doing to exponenetially increase the security of that PIN number.
Frankly I would consider that worrying. Mathemically there is no way
to get more than 10,000 combinations out of four digits. Just cannot
be done. Unless that four digit PIN just unlocks a locally stored key
created by a cryptographically secure random number generator I
personally would not let that thing anywhere near my money.
If they actually front-end RSA with a four digit code it's like having
an army of 10,000 men but only letting one guy shoot.
--
Gordon Walker
------------------------------
From: G Winstanley <[EMAIL PROTECTED]>
Subject: Re: Hill Climbing
Date: Mon, 07 Feb 2000 14:18:47 +0000
Reply-To: [EMAIL PROTECTED]
On Mon, 7 Feb 2000 10:49:29 -0000, the cup of "Michael Darling"
<[EMAIL PROTECTED]> overfloweth with the following:
> Thanks for your reply. This has given me a little bit better understanding
> of the subject.
> I was thinking in terms of 2D graphs - the 3D I hadn't considered. Ideally
> what I would
> like is an example of hill climbing to solve something simple like a
> playfair
> cypher - then I believe the scoring function would be the Index of
> coincidence
> or something similar?
>
> Anyone know of any online tutorials in this area.
>
I'm not aware of any online tutorials, but reading the back postings on the
CipherChallenge website (about Simon Singh's "The Code Book") should give
you some clues.
http://www.onelist.com/community/CipherChallenge
Look for Jim Gillogly's postings, and a good one by Mark VandeWettering in
digest 78 about genetic algorithms. I have written a Playfair solving
program in Java, which combines a GA approach with hill-climbing to approach
a solution quicker. While a hill-climbing algorithm is good for narrowing
down solutions from a fixed starting point, given the problem domain with
Playfair, the "random" element (mutations) of generic algorithms provide the
opportunity to avoid the local maxima and reach an optimal solution, rather
than getting stuck.
As far as scoring goes...Incidence of Coincidence has proven not very
effective in my Playfair solving, and I finally went with trigraph
frequencies. By analysing the trigraph frequencies of an example text and
scoring plaintext attempts based on this. This worked. My solution was based
heavily on Mark VandeWettering's solution, since he gave such a good
description, and all seemed to make sense. I'm sure there are some
fundamental differences, but it's a similar method.
Stan
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: NIST, AES at RSA conference
Date: Mon, 07 Feb 2000 13:57:42 GMT
On 6 Feb 2000 23:45:40 -0800, [EMAIL PROTECTED]
(David Wagner) wrote, in part:
>One might conjecture that this phenomenom only occurs when the cipher
>is a group, but such a claim would remain unproven at best.
Of course it can occur when the two ciphers are only "close" to being
in the same group. However, as a practical matter, it is usually true
that with unrelated ciphers, shortcut attacks are not likely to be
known.
Again, this comes down to multi-ciphering being a _practical_ measure,
but being recommended as a remedy to a problem whose existence is only
shown in _theoretical_ terms.
Either some practical reason for regarding the AES candidates as too
weak is needed, or it is enough to cast the argument in this light:
since no cipher can be proven secure, this is enough reason to want to
take all the precautions one can, and to be particularly suspicious of
a single cipher based on a single round structure. I suppose that does
make the argument weaker, but not unreasonable even so.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/index.html
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: NSA opens up to US News
Date: Mon, 07 Feb 2000 14:01:34 GMT
On Sun, 06 Feb 2000 22:46:50 -0600, [EMAIL PROTECTED] (wtshaw) wrote,
in part:
>Converting binary data to letters is not particularily difficult; I
>already have anounced examples of Onega, 64 to 38, and Santa Maria, 64 to
>27.
Of course, if your cipher machine has only 26 keys...
However, one doesn't need to use my full-blown 47 bit to 10 letter
conversion plan; converting 14 bits to three letters is simpler, and
efficient enough for most practical use.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/index.html
------------------------------
From: Terje Mathisen <[EMAIL PROTECTED]>
Subject: Re: NSA opens up to US News
Date: Mon, 07 Feb 2000 15:59:29 +0100
John Savard wrote:
>
> On Sun, 06 Feb 2000 22:46:50 -0600, [EMAIL PROTECTED] (wtshaw) wrote,
> in part:
>
> >Converting binary data to letters is not particularily difficult; I
> >already have anounced examples of Onega, 64 to 38, and Santa Maria, 64 to
> >27.
>
> Of course, if your cipher machine has only 26 keys...
>
> However, one doesn't need to use my full-blown 47 bit to 10 letter
> conversion plan; converting 14 bits to three letters is simpler, and
> efficient enough for most practical use.
10 characters is a very good match, giving 47.0044 bits of information,
but 47 bits is a very awkward size to work with. You would really have
to split your input into 47-byte blocks to make it work efficiently.
3 chars -> 14.1013 bits, which is also quite good.
I would prefer the much nicer 7 -> 32.9031 conversion (i.e. 7 chars to
encode 4 bytes) though, since this is much simpler to work with, and all
the conversions can be handled in registers, with no need for 64-bit
variables or misaligned bit streams.
If you feel this is wasting too much bandwidth, 12 chars gives 56.4053
bits, i.e. 7 bytes, with less than 0.06 bits wasted per character.
Terje
--
- <[EMAIL PROTECTED]>
Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"
------------------------------
From: Alan Braggins <[EMAIL PROTECTED]>
Subject: Re: Court cases on DVD hacking is a problem for all of us
Date: 07 Feb 2000 15:02:27 +0000
Paul Crowley <[EMAIL PROTECTED]> writes:
> > > o DVD encryption is not there to prevent illegal copying.
[...]
> You're correct AIUI, but there's an even stronger disincentive to the
> pirate using blank DVDs: the blanks are more expensive than
> commmercial DVD pressings!
[...]
> DeCSS was developed for viewing DVDs under Linux.
At the moment, this is true. Large scale pirates with stamping
machines can make bitwise copies without breaking the
encryption. Casual users can not make economic digital copies whether
they break the encryption or not. Casual pirates can make economic
analog copies by using a DVD player as input for a VCR, which
completely bypasses any encryption, but loses quality, and can only be
used for a single generation.
But now assume that in a few years, video compression improves to the
point where more than one DVDs worth of movie can be stored on a
recordable DVD, disk, just as more than one CDs worth of music encoded
as MP3 can be stored on a CD-ROM (with an associated loss of
quality). Assume that, in addition, the price of recordable media and
recording drives falls (as it has with CDs), but the price of
white-market prerecorded media remains similar (as it has with CDs).
At this point, copying movies to a recordable DVD once is as
convenient and as cheap as copying them to VCR, but it does require
breaking the encryption. And the copies can then be copied any number
of further times without generation loss.
This scenario might be a legitimate concern for the copyright holders.
Or they might be bloodsucking leeches attempting to artificially boost
profits by differential regional pricing and blocking fair use of
legally purchased DVDs. (Or they might have a legitimate concern and
be overreacting by attempting to block fair use of purchased DVDs).
------------------------------
From: "etbear" <[EMAIL PROTECTED]>
Subject: Need help for security program
Date: Mon, 7 Feb 2000 23:31:23 +0800
I'm working on a security program for my computing project, and I need a way
in which Windows will alert me when my file is being accessed for reading or
writing. I know there must e some wayto do it...but just couldn't find it.
Can any one give me a brief idea how to do it, so that I can start
researching on that?
Thanks
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: Court cases on DVD hacking is a problem for all of us
Date: Mon, 07 Feb 2000 08:36:45 -0700
Alan Braggins wrote:
> This scenario might be a legitimate concern for the copyright holders.
> Or they might be bloodsucking leeches attempting to artificially boost
> profits by differential regional pricing and blocking fair use of
> legally purchased DVDs. (Or they might have a legitimate concern and
> be overreacting by attempting to block fair use of purchased DVDs).
I suspect the latter. These are the same people who are concerned about casual
copying of VHS movies, despite lack of any evidence that those who would copy
such movies are potential customers in the first place, and despite plentiful
evidence that pirate copies of movies smuggled from overseas factories are a
much larger problem.
--
Eric Lee Green [EMAIL PROTECTED]
Software Engineer Visit our Web page:
Enhanced Software Technologies, Inc. http://www.estinc.com/
(602) 470-1115 voice (602) 470-1116 fax
------------------------------
From: Markku J. Saarelainen <[EMAIL PROTECTED]>
Crossposted-To: alt.politics.org.cia,soc.culture.russian
Subject: My very best communication in 1999 - Yeltsin resign - July, 1999
Date: Mon, 07 Feb 2000 15:35:55 GMT
================ MY MESSAGE IN July, 1999 =============
X-Mozilla-Status: 0001
X-Mozilla-Status2: 00000000
Message-ID: <[EMAIL PROTECTED]>
Date: Tue, 20 Jul 1999 15:07:15 +0000
From: "Markku J. Saarelainen"
<[EMAIL PROTECTED]>
X-Mailer: Mozilla 4.61 [en] (Win95; I)
X-Accept-Language: en
MIME-Version: 1.0
Newsgroups: soc.culture.russian
Subject: Re: A player does exist ... Russia
shall have a new LEADER ...
References: <[EMAIL PROTECTED]>
<[EMAIL PROTECTED]>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
ok .. B'eltsin ... you know what to do ... resign, resign and then
resign ....
all your secrets are out ... " .. in the name of her ... a new flame
shall be
lightened to show the way for the children of the future .. who share
their
dreams ... shall play our guitar to sing the song what your balalaika
likes to
sing ... I follow the Moskva ... the wise man said .. please wlk in
this way
... it is the call of your heart ... " ... Red Hot in Moscow ....
"Markku J. Saarelainen" wrote:
> " ... the leader shall show the light ... show the way for our
visions of
> the future .. this burning desire .. flames of our hearts shall lead
us to
> our common destination .. providing new strength and energy for us
and our
> children ....your .. (her/she) sincerity, beauty, honesty and
intelligence
> .. distant memories from the man ...who opened doors for others to
achieve
> their missions .... who by himself was ignored and neglected ... but
> distant memories ... my dear ...shall remain constant .. to show the
way to
> our common destination ...." Red Hot in Moscow ...
>
> "Markku J. Saarelainen" wrote:
>
> > "And you ask me why I love her .. her beauty .. her sincerity ..she
is
> > the constant .. my land's only border lie around my heart ...my
dear ...
> > you know, you feel and you hear ... once I had dreams .. now they
are
> > obsessions .. I opened doors .. they walked right through them ...
my
> > love ... the player exists .. those who know him... the time shall
show
> > .. my dear ... the wind of change shall blow straight through ...
the
> > children of the future share their dreams .... not for us, but for
them
> > ....."
================ MY MESSAGE IN July, 1999 =============
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Samuel Paik <[EMAIL PROTECTED]>
Subject: Re: Court cases on DVD hacking is a problem for all of us
Date: Mon, 07 Feb 2000 15:51:13 GMT
Eric Lee Green wrote:
> You would need a minimum of a NS-20 tape drive. Nope, that wouldn't
> work, because NS-20 tape drives transfer data at a rate of 1 megabyte
> per second on their best days. Not to mention that NS-20 media costs
> $35, which is about the same that a DVD movie costs in the first place.
DVD has a maximum data rate of 9.8 Mb/s. I believe most movies average
around 5 Mb/s.
Probably the most practical scenario for end-user copying of DVDs is
to transcode a movie down to something that fits on one or more CD-Rs,
which would involve some loss of quality, but not necessarily severe.
2 Mb/s video is quite adequate for broadcast quality video, and you
can strip out foreign language audio tracks.
--
Samuel S. Paik | http://www.webnexus.com/users/paik/
3D and multimedia, architecture and implementation
Solyent Green is kitniyos!
------------------------------
From: "Michael Darling" <[EMAIL PROTECTED]>
Subject: Re: Hill Climbing
Date: Mon, 7 Feb 2000 15:53:38 -0000
Thanks for your reply, I have read Mark's posting and am looking through the
rest of the archives. Have
probably enough info to have a basic stab at a program, and am giving it a
go. Anymore information
would be gratefully received.
Thanks again,
Mike.
> I'm not aware of any online tutorials, but reading the back postings on
the
> CipherChallenge website (about Simon Singh's "The Code Book") should give
> you some clues.
> http://www.onelist.com/community/CipherChallenge
> Look for Jim Gillogly's postings, and a good one by Mark VandeWettering in
> digest 78 about genetic algorithms. I have written a Playfair solving
> program in Java, which combines a GA approach with hill-climbing to
approach
> a solution quicker. While a hill-climbing algorithm is good for narrowing
> down solutions from a fixed starting point, given the problem domain with
> Playfair, the "random" element (mutations) of generic algorithms provide
the
> opportunity to avoid the local maxima and reach an optimal solution,
rather
> than getting stuck.
>
> As far as scoring goes...Incidence of Coincidence has proven not very
> effective in my Playfair solving, and I finally went with trigraph
> frequencies. By analysing the trigraph frequencies of an example text and
> scoring plaintext attempts based on this. This worked. My solution was
based
> heavily on Mark VandeWettering's solution, since he gave such a good
> description, and all seemed to make sense. I'm sure there are some
> fundamental differences, but it's a similar method.
>
> Stan
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Factorization
Date: Mon, 07 Feb 2000 09:09:37 -0700
Reply-To: [EMAIL PROTECTED]
7 seconds on a PII-400 using Pollard Rho. Naive Fortran implementation, no
fancy arithmetic, just a straightforward multiple precision package.
Factors: 96517872943 and 53401798669
JPeschel wrote:
> [EMAIL PROTECTED] writes:
>
> >Would someone please run 5154228018862208512867 through a math package
> >and tell me:
> >- its factors (2 primes roughly the same size - RSA, you guessed it)
> >- the name of the math package (any will do, Mathematica, whatever)
> >- how long the factorization took
> >- what system, roughly, it was run on (P2 400Mhz, say)
>
> PRIME FACTOR 287895462580028491
> PRIME FACTOR 5832864341798915401
>
> Took about a second on P-450 using MPQS
>
> Joe
>
> __________________________________________
>
> Joe Peschel
> D.O.E. SysWorks
> http://members.aol.com/jpeschel/index.htm
> __________________________________________
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: NSA opens up to US News
Date: Mon, 07 Feb 2000 09:11:20 GMT
Terje Mathisen <[EMAIL PROTECTED]> wrote, in part:
>all
>the conversions can be handled in registers, with no need for 64-bit
>variables or misaligned bit streams.
Of course, that's why the scheme for coding 47 bits given on my site
isn't the obvious one of radix conversion, but uses an IBM technique
of bit manipulation to keep the size of what has to be handled at one
time down. But the problem of alignment remains, you are correct.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
Subject: Re: TLS: What is the purpose of the client certificate request?
Reply-To: Anne & Lynn Wheeler <[EMAIL PROTECTED]>
From: Anne & Lynn Wheeler <[EMAIL PROTECTED]>
Date: Mon, 07 Feb 2000 16:23:29 GMT
Anuj Seth <[EMAIL PROTECTED]> writes:
> Hi,
>
> > Yes, the server certificate authenticates the server and the client
> > certificate authenticates the client. I don't understand your final
> > question about authenticating the user.
>
> That's what I thought as well! About, the question you didn't understand
> let me rephrase it -- The server requests the client for the
> certificate. The client sends the certificate across to the server. Now,
> how is the server supposed to authenticate the client? Basically, the
> server should be able to access the CA to get the CA's public key. The
> CA's public key will be used to authenticate the user (If I'm correct).
> I've read the X.509 standard but couldn't figure out how to connect to
> the CA to get the CA's public key. Could someone let me know how it is
> to be done?
at least some of the targets are controlled environments ... where there
is only one (or a few) known CA(s) for client certificates and the
CA's public key is preloaded into the server.
This is somewhat analagous to the reverse ... where the server CA
public keys have been preloaded into the client browswers when the
browsers were manufactored.
The server may only be using the client certificate to validate
membership in the allowed community (client demonstrates that it owns
a valid certificate for access purposes). Validating client membership
just involves validating the certificate and validating that something
the client signs can validate with the public key in the certificate.
Actually validating the client typically would require verifying
something more than membership assertion (like something from the
contents of the signed information) against some local infrastructure
(like an account record).
--
Anne & Lynn Wheeler | [EMAIL PROTECTED], [EMAIL PROTECTED]
http://www.garlic.com/~lynn/ http://www.adcomsys.net/lynn/
------------------------------
From: Markku J. Saarelainen <[EMAIL PROTECTED]>
Crossposted-To: soc.culture.europe,soc.culture.german,soc.culture.russian
Subject: Read all my message at alt.politics.org.cia
Date: Mon, 07 Feb 2000 16:32:45 GMT
Read all my message at alt.politics.org.cia
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Jean-Jacques Quisquater <[EMAIL PROTECTED]>
Subject: Re: Math contest winner from Ireland...
Date: Mon, 07 Feb 2000 17:57:24 +0100
Ho!
See http://www.counterpane.com/crypto-gram-9912.html
It is not at all published on the internet by an unknown source.
Here is the story.
I was invited to give a talk at INRIA (France)
see http://www.inria.fr/Colloques/COLLOQUIUM991116-fra.html
and I wanted to be a little bit interesting with some solved problems.
One problem was: Where is the algorithm of Sarah Flannery?
I did a lot of searches using altavista (and later google) but I didn't
find the solution. I also was an evaluator of the PhD (very good) thesis
by Jean-Francois Misarsky (in Caen ,France) and during the lunch after
the defense I spoke to him about my project. And it was
the solution: Sarah participated to another competition organized
and PAID by the European Commission (EC). She won and thus (because we
paid
for this) the result was public. Misarsky called the EC and received her
text by fax. I also called the EC but finally I received a copy of the
text first by Misarsky. I did a complete scan of the whole thing and
sent it to
jya.com. That's it. I don't understand why it is unknown
(use dejanews to see my early postings in sci.crypt and other ones).
Jean-Jacques Quisquater,
------------------------------
From: [EMAIL PROTECTED] (Doug Stell)
Subject: Re: KEA, and XDH
Date: Mon, 07 Feb 2000 16:44:25 GMT
On Fri, 04 Feb 2000 04:37:43 +0000, David Hopwood
<[EMAIL PROTECTED]> wrote:
>> Incidentally, the CA also checks that YA and YB are elements of the
>> order-q subgroup, before it signs the certificate. This is not in the
>> KEA specification, but is a part of the CA requirements. The KEA
>> specification is simply focused on the two communicants, rather than
>> the CA.
>>
>> The reason for this check can be found in a paper by Lim and Lee.
>
>Do you have a reference for that paper?
"A Key Recovery Attack on Discrete Log-based Schemes Using a Prime
Order Subgroup," Chae Hoon Lim and Pil Joong Lee. If I remember right,
I found it in the P1363 collection of contributed papers.
>> >This is quite similar to some of the MTI* protocols, for example
>> >MTI/A0 [HAC Protocol 12.53] and MTI/C1. It's also similar to a protocol
>> >I designed myself (unpublished, called SID-3-DH),
>
>I've decided to rename it to "XDH" (extended Diffie-Hellman).
>
>> >in which the agreed
>> >value is g^((xA + rA)(xB + rB)), rather than g^(xB.rA) + g^(xA.rB).
>> >
>> >[This is more efficient than KEA, because
>> >
>> > g^((xA + rA)(xB + rB)) = (YB * RB)^(xA + rA)
>> > = (YA * RA)^(xB + rB)
>> >
>> >can be calculated by each side using only one modexp, not two.
>>
>> This is faster than KEA by a factor of about 2.
>
>Not quite, because each side also needs to compute RA or RB, but
>these can be precomputed. (For example, a server would probably
>maintain a pool of g^rB values for incoming connections; in that
>case computing RB values wouldn't contribute to connection setup
>latency, but would contribute to server load. These are only short-
>exponent, fixed-base modexps, anyway.)
OK. The second operation, the actual key agreement calculation is
faster by about a factor of 2. The first calculation, generation of RA
and RB, are the same, but can be precomputed, as you correctly state.
>Note that Alice must check that YB * RB generates a group of
>order q, and similarly for Bob. rA and rB must not be chosen such
>that (xA + rA) mod q or (xB + rB) mod q are zero (although that
>happens with negligable probability). Also, timing and other side
>channel attacks against the modexp calculations must be prevented.
My metrics, done months ago for a hardware math engine, also did not
include these checks.
>========
>
>I said that the security of XDH could be proven (relative to DHP);
>here is the proof:
>
>Let G be a cyclic group or subgroup of known order q generated by
>an element g, and call an integer that is chosen uniformly and
>independently at random from the range [0, q-1], an "R-integer".
>
>(Note that the oracles used in the proof can depend on G, g and q,
>so these do not have to be passed to them as parameters.)
>
>Define a problem XDHP[G, g, q] as follows:
>
> Suppose that a, b, c and d are R-integers.
> Given g^a, g^b, c, and d, find g^(a+c)(b+d).
>
>Proof that XDHP[G, g, q] reduces to DHP[G, g, q]:
>
> Suppose that we have an oracle O, which, when given g^a, g^b,
> c, and d, such that a, b, c, d are R-integers, returns g^(a+c)(b+d)
> with probability p0, in time t0, and using memory m0.
>
> Then when given g^a and g^b, such that a, b are R-integers, we
> can calculate g^ab with probability p0, in time t0 + t1 and using
> memory m0 + m1, where t1 and m1 are the time and memory needed to
> calculate 3 modexps, 3 multiplications, and 1 inverse in G (and
> an integer multiplication), as follows:
>
> 1. Choose two R-integers c and d.
> 2. Let x = O(g^a, g^b, c, d).
> 3. Return x * (g^(cd) * (g^a)^d * (g^b)^c)^-1
> (G is a cyclic group or subgroup, so all elements have an inverse).
>
> This works because:
>
> g^(a+c)(b+d) = g^ab * g^cd * g^ad * g^bc, therefore
> g^ab = g^(a+c)(b+d) * (g^cd * (g^a)^d * (g^b)^c)^-1
>
>Note that the result also holds if the R-integers are chosen with
>a non-uniform distribution, e.g. using an imperfect PRNG, in both
>the XDHP and DHP problems.
>
>[Conversely, XDHP can be solved using an oracle for DHP, since
>g^(a+c)(b+d) = g^ab * g^cd * g^ad * g^bd (actually, this also solves
>the potentially more difficult problem when only g^c and g^d are
>given, instead of c and d).]
>
>An important point is that by symmetry, we could have chosen the
>private value inputs to XDHP as either (a and b), (a and d),
>(c and b), or (c and d).
>
>The security of the XDH protocol can now be expressed in terms
>of XDHP.
>
>There are 5 cases:
>1. The attacker knows xA, xB, RA and RB (known-key passive attack).
>2. The attacker knows YA, xB, rA and RB (attempted
> impersonation of Alice, possibly given Bob's private data).
>3. The attacker knows xA, YB, RA and rB (attempted
> impersonation of Bob, possibly given Alice's private data).
>4. The attacker knows YA, YB, rA and rB (failure of both Alice
> and Bob's RNGs).
>5. For a man-in-the-middle attack, the attacker is assumed not
> to know *both* Alice and Bob's private keys, and therefore this
> is as difficult as either case 2 or case 3.
>
>In all of these cases, finding g^(xA + rA)(xB + rB) is equivalent
>to an instance of XDHP, and therefore is as difficult as solving DHP
>in the same group or subgroup.
>
>- --
>David Hopwood <[EMAIL PROTECTED]>
>PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
>RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
>
>"Attempts to control the use of encryption technology are wrong in principle,
>unworkable in practice, and damaging to the long-term economic value of the
>information networks." -- UK Labour Party pre-election policy document
>
>
>-----BEGIN PGP SIGNATURE-----
>Version: 2.6.3i
>Charset: noconv
>
>iQEVAwUBOJpXhjkCAxeYt5gVAQEyzAgAmUnnq1x4Mp2ixwBAVf7xxuOIBM59mMDb
>0+Um5ONsx8KG9IFEQmLMR0Lj/kjmpXb4V8URQ53a+RE9iSXduLCL3A0/mxcnudqT
>LJ0TxaKwLo3R36G4yRczTCIAOoF6wZzqQk61DujwcbULSW+dAMPStKwIrhDjsO3g
>8r4JRhYWm8/VY0pwTlHhSGCCKDee2p5O73hvf/mOrP6TOk5aaF4xCqjXDqrWbH1y
>yBKID0i0N7qoDtuSanzv0FVEEf+eyIINXigGR4BVnluk3lMlSYg/OcrysCTdA2J1
>b5igg5ypP84fXZ3iKiOCiy8+82EQfehWVcGpDUUePE0oSEPUNB2eMQ==
>=dK6F
>-----END PGP SIGNATURE-----
>
------------------------------
** 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
******************************
