By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
432,483 Members | 1,052 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 432,483 IT Pros & Developers. It's quick & easy.

Diffie-Hellman-Merkle Key Exchange Program

P: n/a
I'm writing a Diffie-Hellman-Merkle Key Exchange Program, and,
sometimes (I haven't figured out how to predict it yet), Alice's and
Bob's shared symmetric key are different! This shouldn't happen!

Code:

#include <iostream>
#include <cstdlib>
using std::cout;
using std::cin;
using std::endl;
using std::system;

long long Exp(const long long& base,long long exp)
{
long long i=1;
for(;i<exp;i++)
i*=base;
return i;
}

int main()
{
long long A,B;
long long base,mod;
for(;;)
{
cout << "Base: " << endl;
cin >base;
cout << "Modulus: " << endl;
cin >mod;
cout << "Alice, choose your secret number: " << endl;
cin >A;
cout << "Bob, choose your secret number: " << endl;
cin >B;
long long a=Exp(base,A)%mod;
long long b=Exp(base,B)%mod;
cout << "Alice's value: " << a << endl;
cout << "Bob's value: " << b << endl;
long long akey=Exp(b,A)%mod;
long long bkey=Exp(a,B)%mod;
cout << "Alice's key: " << akey << endl;
cout << "Bob's key: " << bkey << endl;
}
system("PAUSE");
return EXIT_SUCCESS;
}

Here's an link to explain DHM Key Exchange:

http://en.wikipedia.org/wiki/Diffie-Hellman

Thanks!!!!

Jul 30 '06 #1
Share this Question
Share on Google+
4 Replies


P: n/a
Protoman wrote:
I'm writing a Diffie-Hellman-Merkle Key Exchange Program, and,
sometimes (I haven't figured out how to predict it yet), Alice's and
Bob's shared symmetric key are different! This shouldn't happen!

Code:

#include <iostream>
#include <cstdlib>
using std::cout;
using std::cin;
using std::endl;
using std::system;

long long Exp(const long long& base,long long exp)
{
long long i=1;
for(;i<exp;i++)
i*=base;
on topic remarks:
=================

If this loop overflows, you have undefined behavior.

You should use unsigned long long instead. Then it will wrapand give the
correct result mod 2^N where N is the bitlength.

However, even that will not do, for reasons explained below.

return i;
}

int main()
{
long long A,B;
long long base,mod;
for(;;)
{
cout << "Base: " << endl;
cin >base;
cout << "Modulus: " << endl;
cin >mod;
cout << "Alice, choose your secret number: " << endl;
cin >A;
cout << "Bob, choose your secret number: " << endl;
cin >B;
long long a=Exp(base,A)%mod;
more off topic remarks:
=======================

when you take the overflown result from Exp(base,A) and pass it to %mod, you
do not really compute the correct remainder because for x 2^N, in general

x % mod != ( x % 2^N ) % mod

You need to either use a library for arbitrary precision integers or write a
function exp_mod( base, exponent, modulus ) that computes

base**exponent mod modulus

correctly.
long long b=Exp(base,B)%mod;
cout << "Alice's value: " << a << endl;
cout << "Bob's value: " << b << endl;
long long akey=Exp(b,A)%mod;
long long bkey=Exp(a,B)%mod;
cout << "Alice's key: " << akey << endl;
cout << "Bob's key: " << bkey << endl;
}
system("PAUSE");
return EXIT_SUCCESS;
}
Also, your question is on the borderline to purely algorithmic problems. You
might want to ask in comp.programming instead.
Best

Kai-Uwe Bux
Jul 30 '06 #2

P: n/a

Kai-Uwe Bux wrote:
Protoman wrote:
I'm writing a Diffie-Hellman-Merkle Key Exchange Program, and,
sometimes (I haven't figured out how to predict it yet), Alice's and
Bob's shared symmetric key are different! This shouldn't happen!

Code:

#include <iostream>
#include <cstdlib>
using std::cout;
using std::cin;
using std::endl;
using std::system;

long long Exp(const long long& base,long long exp)
{
long long i=1;
for(;i<exp;i++)
i*=base;

on topic remarks:
=================

If this loop overflows, you have undefined behavior.

You should use unsigned long long instead. Then it will wrapand give the
correct result mod 2^N where N is the bitlength.

However, even that will not do, for reasons explained below.

return i;
}

int main()
{
long long A,B;
long long base,mod;
for(;;)
{
cout << "Base: " << endl;
cin >base;
cout << "Modulus: " << endl;
cin >mod;
cout << "Alice, choose your secret number: " << endl;
cin >A;
cout << "Bob, choose your secret number: " << endl;
cin >B;
long long a=Exp(base,A)%mod;

more off topic remarks:
=======================

when you take the overflown result from Exp(base,A) and pass it to %mod, you
do not really compute the correct remainder because for x 2^N, in general

x % mod != ( x % 2^N ) % mod

You need to either use a library for arbitrary precision integers or write a
function exp_mod( base, exponent, modulus ) that computes

base**exponent mod modulus

correctly.
long long b=Exp(base,B)%mod;
cout << "Alice's value: " << a << endl;
cout << "Bob's value: " << b << endl;
long long akey=Exp(b,A)%mod;
long long bkey=Exp(a,B)%mod;
cout << "Alice's key: " << akey << endl;
cout << "Bob's key: " << bkey << endl;
}
system("PAUSE");
return EXIT_SUCCESS;
}

Also, your question is on the borderline to purely algorithmic problems. You
might want to ask in comp.programming instead.
Best

Kai-Uwe Bux
Did what you said, still comes up w/different values.

Code:

#include <iostream>
#include <cstdlib>
using std::cout;
using std::cin;
using std::endl;
using std::system;

unsigned long long ExpMod(const unsigned long long& base,const unsigned
long long& exp,
const unsigned long long& mod)
{
unsigned long long i=1;
for(;i<exp;i++)
i*=base;
return i%mod;
}

int main()
{
unsigned long long A,B;
unsigned long long base,mod;
for(;;)
{
cout << "Base: " << endl;
cin >base;
cout << "Modulus: " << endl;
cin >mod;
cout << "Alice, choose your secret number: " << endl;
cin >A;
cout << "Bob, choose your secret number: " << endl;
cin >B;
unsigned long long a=ExpMod(base,A,mod);
unsigned long long b=ExpMod(base,B,mod);
unsigned long long akey=ExpMod(b,A,mod);
unsigned long long bkey=ExpMod(a,B,mod);
cout << "Alice's key: " << akey << endl;
cout << "Bob's key: " << bkey << endl;
}
system("PAUSE");
return EXIT_SUCCESS;
}

Jul 30 '06 #3

P: n/a
Protoman wrote:
>
Kai-Uwe Bux wrote:
>Protoman wrote:
I'm writing a Diffie-Hellman-Merkle Key Exchange Program, and,
sometimes (I haven't figured out how to predict it yet), Alice's and
Bob's shared symmetric key are different! This shouldn't happen!

Code:

#include <iostream>
#include <cstdlib>
using std::cout;
using std::cin;
using std::endl;
using std::system;

long long Exp(const long long& base,long long exp)
{
long long i=1;
for(;i<exp;i++)
i*=base;

on topic remarks:
=================

If this loop overflows, you have undefined behavior.

You should use unsigned long long instead. Then it will wrapand give the
correct result mod 2^N where N is the bitlength.

However, even that will not do, for reasons explained below.

return i;
}

int main()
{
long long A,B;
long long base,mod;
for(;;)
{
cout << "Base: " << endl;
cin >base;
cout << "Modulus: " << endl;
cin >mod;
cout << "Alice, choose your secret number: " << endl;
cin >A;
cout << "Bob, choose your secret number: " << endl;
cin >B;
long long a=Exp(base,A)%mod;

more off topic remarks:
=======================

when you take the overflown result from Exp(base,A) and pass it to %mod,
you do not really compute the correct remainder because for x 2^N, in
general

x % mod != ( x % 2^N ) % mod

You need to either use a library for arbitrary precision integers or
write a function exp_mod( base, exponent, modulus ) that computes

base**exponent mod modulus

correctly.
long long b=Exp(base,B)%mod;
cout << "Alice's value: " << a << endl;
cout << "Bob's value: " << b << endl;
long long akey=Exp(b,A)%mod;
long long bkey=Exp(a,B)%mod;
cout << "Alice's key: " << akey << endl;
cout << "Bob's key: " << bkey << endl;
}
system("PAUSE");
return EXIT_SUCCESS;
}

Also, your question is on the borderline to purely algorithmic problems.
You might want to ask in comp.programming instead.
Best

Kai-Uwe Bux

Did what you said, still comes up w/different values.

Code:

#include <iostream>
#include <cstdlib>
using std::cout;
using std::cin;
using std::endl;
using std::system;

unsigned long long ExpMod(const unsigned long long& base,const unsigned
long long& exp,
const unsigned long long& mod)
{
unsigned long long i=1;
for(;i<exp;i++)
i*=base;
return i%mod;
}
You have the same problem. You also have a problem that I did not see
before: you are using the same variable i as a running index and to keep
track of the current power. This will not do the expected.
Try:

unsigned long long
ExpMod(const unsigned long long base,
const unsigned long long exp,
const unsigned long long mod)
{
unsigned long long i = 1;
while ( exp 0 ) {
i = ( i * base ) % mod;
-- exp;
}
return i;
}

This has a better chance of working for values of base, exp, and mod up to
2^32 (provided that your long long goes up to 2^64).
>
int main()
{
unsigned long long A,B;
unsigned long long base,mod;
for(;;)
{
cout << "Base: " << endl;
cin >base;
cout << "Modulus: " << endl;
cin >mod;
cout << "Alice, choose your secret number: " << endl;
cin >A;
cout << "Bob, choose your secret number: " << endl;
cin >B;
unsigned long long a=ExpMod(base,A,mod);
unsigned long long b=ExpMod(base,B,mod);
unsigned long long akey=ExpMod(b,A,mod);
unsigned long long bkey=ExpMod(a,B,mod);
cout << "Alice's key: " << akey << endl;
cout << "Bob's key: " << bkey << endl;
}
system("PAUSE");
return EXIT_SUCCESS;
}

Best

Kai-Uwe
Jul 30 '06 #4

P: n/a

Kai-Uwe Bux wrote:
Protoman wrote:

Kai-Uwe Bux wrote:
Protoman wrote:

I'm writing a Diffie-Hellman-Merkle Key Exchange Program, and,
sometimes (I haven't figured out how to predict it yet), Alice's and
Bob's shared symmetric key are different! This shouldn't happen!

Code:

#include <iostream>
#include <cstdlib>
using std::cout;
using std::cin;
using std::endl;
using std::system;

long long Exp(const long long& base,long long exp)
{
long long i=1;
for(;i<exp;i++)
i*=base;

on topic remarks:
=================

If this loop overflows, you have undefined behavior.

You should use unsigned long long instead. Then it will wrapand give the
correct result mod 2^N where N is the bitlength.

However, even that will not do, for reasons explained below.
return i;
}

int main()
{
long long A,B;
long long base,mod;
for(;;)
{
cout << "Base: " << endl;
cin >base;
cout << "Modulus: " << endl;
cin >mod;
cout << "Alice, choose your secret number: " << endl;
cin >A;
cout << "Bob, choose your secret number: " << endl;
cin >B;
long long a=Exp(base,A)%mod;

more off topic remarks:
=======================

when you take the overflown result from Exp(base,A) and pass it to %mod,
you do not really compute the correct remainder because for x 2^N, in
general

x % mod != ( x % 2^N ) % mod

You need to either use a library for arbitrary precision integers or
write a function exp_mod( base, exponent, modulus ) that computes

base**exponent mod modulus

correctly.

long long b=Exp(base,B)%mod;
cout << "Alice's value: " << a << endl;
cout << "Bob's value: " << b << endl;
long long akey=Exp(b,A)%mod;
long long bkey=Exp(a,B)%mod;
cout << "Alice's key: " << akey << endl;
cout << "Bob's key: " << bkey << endl;
}
system("PAUSE");
return EXIT_SUCCESS;
}

Also, your question is on the borderline to purely algorithmic problems.
You might want to ask in comp.programming instead.
Best

Kai-Uwe Bux
Did what you said, still comes up w/different values.

Code:

#include <iostream>
#include <cstdlib>
using std::cout;
using std::cin;
using std::endl;
using std::system;

unsigned long long ExpMod(const unsigned long long& base,const unsigned
long long& exp,
const unsigned long long& mod)
{
unsigned long long i=1;
for(;i<exp;i++)
i*=base;
return i%mod;
}

You have the same problem. You also have a problem that I did not see
before: you are using the same variable i as a running index and to keep
track of the current power. This will not do the expected.
Try:

unsigned long long
ExpMod(const unsigned long long base,
const unsigned long long exp,
const unsigned long long mod)
{
unsigned long long i = 1;
while ( exp 0 ) {
i = ( i * base ) % mod;
-- exp;
}
return i;
}

This has a better chance of working for values of base, exp, and mod up to
2^32 (provided that your long long goes up to 2^64).

int main()
{
unsigned long long A,B;
unsigned long long base,mod;
for(;;)
{
cout << "Base: " << endl;
cin >base;
cout << "Modulus: " << endl;
cin >mod;
cout << "Alice, choose your secret number: " << endl;
cin >A;
cout << "Bob, choose your secret number: " << endl;
cin >B;
unsigned long long a=ExpMod(base,A,mod);
unsigned long long b=ExpMod(base,B,mod);
unsigned long long akey=ExpMod(b,A,mod);
unsigned long long bkey=ExpMod(a,B,mod);
cout << "Alice's key: " << akey << endl;
cout << "Bob's key: " << bkey << endl;
}
system("PAUSE");
return EXIT_SUCCESS;
}


Best

Kai-Uwe
It works!!!!! Praise God, you did it!!!!!! Thank you so much!!!!!!!!

Jul 30 '06 #5

This discussion thread is closed

Replies have been disabled for this discussion.