UNDERSTANDING DIFFIE-HELLMAN BASIC 2

[maczen]

I am trying to get a grasp on Diffie-Hellman and would definitely appreciate any assistance as some pertinent areas are currently eluding me... LoL

OK.. Let's say we have a basic DH exchange taking place between to supercomputers.. Let's call them Burt and Clue..

Both Burt and Clue agree on prime number P and integer G (P - 1 mod P)

P = 9
G = 8
B = 2
C = 3
S = SECRET = 3???

Burt chooses a random number B < P
Clue chooses a random number C < P

Burt sends B^G (mod P) to Clue
Clue sends C^G (mod P) to Burt
~This essentially "hides" value G

(OK... THIS IS WHERE I AM UNCERTAIN)
Burt solves: S=G^CB=(G^C)^B (mod P)
Clue solves: S=G^BC=(G^B)^C (mod P)

S=G^CB= 8(2*3)= 48(mod P) = 3
S=G^BC= 8(3*2)= 48(mod P) = 3

Did I do this correctly? Any info or links that you know of or places to go for further study??? And I used Google calc to calculate the modulo but I am guessing the it is the lowest common denominator of the "pre-modded" secret?

B Haines
CCNA R&S, ETA FOI

 

[maczen]

BTW.. If anyone is interested in the material I used for this it is available here..

http://modular.fas.harvard.edu/edu/Fall2001/124/lectures/lecture8/html/node2.html

B Haines
CCNA R&S, ETA FOI

 

[Cluebird]

You've got it. That is DH in a nutshell.

 

[maczen]

Thanks Clue,
I was grocery shopping and thought that I made a mistake here..

Clue solves: S=G^BC=(G^B)^C (mod P)
I resolved 48 mod P = 3 which is..
G*(BC) or 8*6 = 48 but here is my question...

Since BC are exponents would it not be like this:

G^BC = 8^2*3 = 8^5 = 8*8*8*8*8 = 32768

???

Once I have this down I will play with it like I did subnetting until I have a solid grasp and can move on to eliptical curve etc.. (Then maybe one day I will get the CCNA Security book in)!!!

B Haines
CCNA R&S, ETA FOI

 

[Cluebird]

It actually is exponents but the concept is the same. Both sides are using the same process and have the same ingredients, so they are able to mathematically compute the same results. What makes this secure is the large prime numbers that are not easily guessed combined with a limited lifetime combined with a simple, yet effective randomness to generate a key value that is nearly impossible to recreate.

If you look at the math, G being raised to the C raised to the B is identical to G being raised to the B raised to the C. Although you did straight multiplication rather than exponentiation, the final result after the mod function will lead to both devices having the same secret key. The exponentiation adds to the computational difficulty to make the key harder to "guess".

 

[maczen]

Thanks.. Just did it both ways.. 3! Awesome.. I believe that I am going to like the security side.. Voice and Wireless are both interesting in and of themselves but Security seems to be the most interesting in my opinion.

B Haines
CCNA R&S, ETA FOI

 

[maczen]

This is the last area that I am not completely certain of...

Both Burt and Clue agree on prime number P and integer G (P - 1 mod P)

If P = 9 what SHOULD G equal? (P - 1 (mod P))

I went with 8 before (P - 1) but was not sure about the mod P or 8 part.. 9 - 1 = 8 mod 9 = 8

If the algorithm for G is always P - 1 mod P then the result will always be the answer before applying the mod.. if that makes any sense..

IE.
P = 9 so G = 8 then apply mod (8 mod 9 = G = 8)
P = 75 so G = 74 then (74 mod 75 = G = 74)
P = 32768 so G = 32767 then (32767 mod 32768 = G = 32767)

It seems as if this part of the algorithm is useless until later... So why would they include the mod P at this point in the algorithm? Why would you need the mod P in:
G = P - 1 mod P


B Haines
CCNA R&S, ETA FOI

 

[burtsbees]

Dude, I just learned how to count to 20 without my fingers and toes...
what are you trying to do to me???

Burt

 

[Cluebird]

P is a prime number for DH. None of the numbers you're choosing are prime. That's part of your confusion.

 

[Cluebird]

Mac,

Try this link. It's more mathematical but goes into more depth regarding the modulus function and how all related to DH.

http://www.math.ucla.edu/~baker/40.1.99w/handouts/rev_DH/node1.html

Burt,
I still take my shoes off to count. (Clears the room pretty well, too!) LoL

 

[maczen]

Ooops.. LoL

P = 5 (Prime)
G = 4 mod 5 ( P-1 mod P ) = 4
A = 3
B = 2
S = secret

3^4 mod 5 = A^G mod P = 81 mod 5 = 1
2^4 mod 5 = B^G mod P = 16 mod 5 = 1

S = G^AB = 4^3*2 = 1296 mod 5 = 1
S = G^BA = 4^2*3 = 1296 mod 5 = 1

S=1

Thanks Clue... Funny Burt... LoL
I think I have it now!!! Still seems like performing a modulus on G in the beginning is a waste but I have it now...

B Haines
CCNA R&S, ETA FOI

 

[maczen]

Thanks Clue.. Will check that link out now..

B Haines
CCNA R&S, ETA FOI

 

[maczen]

I have not even finished this yet but it is awesome.. Thanks Clue!!!

B Haines
CCNA R&S, ETA FOI

 

[maczen]

Thanks again.. I completely grasp the mod now..

P = 11 (Prime following the 2q+1 rule where q is also prime)
G = 2 (Generator)

1A = 7 (< P) PRIVATE
1B = 6 (< P) KEYS (Random)

2A = 2^7 = 128 mod 11 = 7 PUBLIC
2B = 2^6 = 64 mod 11 = 9 KEYS

3A = 9^7 mod 11 = 4782969 mod 11 = 4 SHARED
3B = 7^6 mod 11 = 117649 mod 11 = 4 SECRET KEYS

SECRET = 4

OK.. This is just plain cool!!! LoL

B Haines
CCNA R&S, ETA FOI

 

[maczen]

P = 11
G = 2

Private
aA = 5
aB = 4

Public
bA = 2^5 mod 11 = 10
bB = 2^4 mod 11 = 5

SHARED SECRET
cA = 5^5 mod 11 = 1
cB = 10^4 mod 11 = 1

Had to make sure.. LoL
Posting in here for the next guy/gal that is trying to figure this out.. LoL

B Haines
CCNA R&S, ETA FOI

 

[MichealC4]

Thanks.. Just did it both ways.. 3! Awesome.. I believe that I am going to like the security side.. Voice and Wireless are both interesting in and of themselves but Security seems to be the most interesting in my opinion.

We have cookies too.



Cryptography is a fascinating subject, isn't it? There is just so much to security, it is hard (for me at least) to be content with just one subject area.

----------------------------
"Will work for bandwidth" - Thinkgeek T-shirt

 

[maczen]

I know what you mean. You should meander over to the CCNA section of this site as we discuss a lot of the CCNA Security stuff over there as well. Good luck with your studies.

B Haines
CCNA R&S, ETA FOI