P: n/a

I'm writing a DiffieHellmanMerkle 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/DiffieHellman
Thanks!!!!  
Share this Question
P: n/a

Protoman wrote:
I'm writing a DiffieHellmanMerkle 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
KaiUwe Bux  
P: n/a

KaiUwe Bux wrote:
Protoman wrote:
I'm writing a DiffieHellmanMerkle 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
KaiUwe 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;
}  
P: n/a

Protoman wrote:
>
KaiUwe Bux wrote:
>Protoman wrote:
I'm writing a DiffieHellmanMerkle 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
KaiUwe 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
KaiUwe  
P: n/a

KaiUwe Bux wrote:
Protoman wrote:
KaiUwe Bux wrote:
Protoman wrote:
I'm writing a DiffieHellmanMerkle 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
KaiUwe 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
KaiUwe
It works!!!!! Praise God, you did it!!!!!! Thank you so much!!!!!!!!   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 12020
 replies: 4
 date asked: Jul 30 '06
