RE: Please Review a Diffie Hellman diagram

[Sanjay Rawat <sanjayr () intoto com>]

Hi Mrinal: see my response under the respective lines.
At 03:49 AM 1/10/2006, Mrinal Biswas wrote:
> Excuse me if my question is stupid.
>
> 1. How does peers (alice and bob) agree on Prime number and Generator? I
> thought (speciffically in IKE) peers exchange just one number (public
> numbers).



> Sanjay> They can exchange them in public. There need not to have any 
> privacy, as far as the leakage of these nmbers is concerned.



> Please refer to RFC 2409 section 6.1
> http://www.networksorcery.com/enp/rfc/rfc2409.txt
>
> Does it mean if you use DH group I g is always  2 and p is "2^768 - 2
> ^704 - 1 + 2^64 * { [2^638 pi] + 149686 }" ?



> Sanjay> I think, if it is a general practise to use a predefined group, 
> you can follow the above specifications. But i am not sure on this.



> 2. "Finally, Alice computes g^(ab) = (g^b)^a mod p, and Bob computes
> g^(ba) = (g^a)^b mod p. Since g^(ab) = g^(ba) = k, Alice and Bob now
> have a shared secret key k."
>
> I am wondering how Alice determines g^b and Bob g^a ?

Sanjay> They need not to determine g^b or g^a. you whole calculations are 
under mod p. therefore one always needs g^a mod p or g^b mod p.

> They exchange
> public numbers that is "g^b mod p" and "g^a mod p". The daigram says it
> computes (g^b mod p)^a mod p and (g^a mod p)^b mod p. And the example
> shows both the values are same.
>
> I read somewhere it's simple high school math to prove (g^b mod p)^a mod
> p = (g^a mod p)^b mod p . Can someone give explain a little more how to
> prove this mathmatically. I am hopping it's not too complex for me to
> understand.

Sanjay> multiplication in commutative and distributive, even under modular 
mathematics (i.e. finite group or Galois field). You can do your 
calculation in either of two ways-
1). reduce the result of some operations, under mod p, for each step and 
proceed for next operations.
2). calculate the final result of a series of operations and then reduce 
the result under mod p.

Note: you "can't" reduce the power to any number under mod p. If you want 
to reduce the power for each step, use mod (Euler Fn (p)),also called 
totient function.

If you need to go more deep into the topic, I suggest some good text books 
on Number system and cryptography, like

N. Koblitz, A course in Number theory and Cryptography

Gallon, A course in Abstract Algebra

Menezes, A Hand book of Cryptography

G.Hardy,

Regards
Sanjay


> Thanks
>
>
>
>
>
>
>
> -----Original Message-----
> From: Sanjay Rawat [mailto:sanjayr () intoto com]
> Sent: Tuesday, 10 January 2006 12:01 a.m.
> To: Saqib Ali; webappsec () securityfocus com
> Subject: Re: Please Review a Diffie Hellman diagram
>
> Hi Saqib:
>
> The diagram is nice, but content wise, its not (esp. from Mathematics
> point of view). The chosen number R & T are not just any number (or just
> any prime numbers). please see the description below (I was lazy enough
> to write, so I stole it from a site!!!!):
> ----------------------------------------
>
> The protocol has two system parameters p and g. They are both public and
> may be used by all the users in a system. Parameter p is a prime number
> and parameter g (usually called a generator) is an integer less than p,
> with the following property: for every number n between 1 and p-1
> inclusive, there is a power k of g such that n = g^k mod p.
>
> Suppose Alice and Bob want to agree on a shared secret key using the
> Diffie-Hellman key agreement protocol. They proceed as follows: First,
> Alice generates a random private value a and Bob generates a random
> private value b. Both a and b are drawn from the set of integers . Then
> they derive their public values using parameters p and g and their
> private values.
> Alice's public value is g^a mod p and Bob's public value is g^b mod p.
> They then exchange their public values. Finally, Alice computes g^(ab) =
> (g^b)^a mod p, and Bob computes g^(ba) = (g^a)^b mod p. Since g^(ab) =
> g^(ba) = k, Alice and Bob now have a shared secret key k.
> ----------------------------------------
>
> Also, it your diagram under "step 4", it will be nice if you show the
> commutative law of multiplication to make the point (ie why both Alice
> and Bob would have the same number at the end of the protocol) more
> clear. this point is described in above paragraph -- "Finally, Alice
> computes.........."
>
> Regards
> Sanjay
>
> At 07:01 AM 1/7/2006, Saqib Ali wrote:
> >Please review the following visual depiction of Diffie Hellman Key
> Exchange:
> >
> >http://www.xml-dev.com/blog/index.php?action=viewtopic&id=196
> >
> >I would like to recieve corrections, or ideas on how to improve the
> >diagram so it is self-explanatory.
> >
> >--
> >Saqib Ali, CISSP
> >http://www.xml-dev.com/blog/
> >"I fear, if I rebel against my Lord, the retribution of an Awful Day
> >(The Day of Resurrection)" Al-Quran 6:15
> >
> >-----------------------------------------------------------------------
> >-------- Watchfire's AppScan is the industry's first and leading web
> >application security testing suite, and the only solution to provide
> >comprehensive remediation tasks at every level of the application. See
> >for yourself.
> >Download AppScan 6.0 today.
> >
> >https://www.watchfire.com/securearea/appscansix.aspx?id=701300000003Ssh
>
>
>
> ------------------------------------------------------------------------
> -------
> Watchfire's AppScan is the industry's first and leading web application
> security testing suite, and the only solution to provide comprehensive
> remediation tasks at every level of the application. See for yourself.
> Download AppScan 6.0 today.
>
> https://www.watchfire.com/securearea/appscansix.aspx?id=701300000003Ssh
> ------------------------------------------------------------------------
> -------

Sanjay Rawat
Senior Software Engineer
INTOTO Software (India) Private Limited
Uma Plaza, Above HSBC Bank, Nagarjuna Hills
PunjaGutta,Hyderabad 500082 | India
Office: + 91 40 23358927/28 Extn 422
Website : www.intoto.com
  Homepage: http://sanjay-rawat.tripod.com






-------------------------------------------------------------------------------
Watchfire's AppScan is the industry's first and leading web application 
security testing suite, and the only solution to provide comprehensive 
remediation tasks at every level of the application. See for yourself. 
Download AppScan 6.0 today.

https://www.watchfire.com/securearea/appscansix.aspx?id=701300000003Ssh
-------------------------------------------------------------------------------