Diffie-Hellman-Merkle Key Exchange Program

[Protoman]

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!!!!

 

[Kai-Uwe Bux]

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

 

[Protoman]

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.



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.


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;
}

 

[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

 

[Protoman]

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).



Best

Kai-Uwe

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