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!!!! 4 12894
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
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;
}
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
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!!!!!!!! This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Conax |
last post by:
Hello,
This is actually a general programming question but I don't know which
newsgroup best to put it so please pardon me.
I've always been looking for the best way to get an accurate...
|
by: firewoodtim |
last post by:
What is the impact of software patents on a developer's plans to
market, or even use, his/her work? I have a set of my own PHP scripts
that I want to use for building my clients' sites, but I am...
|
by: isladogs |
last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM).
In this month's session, we are pleased to welcome back...
|
by: Vimpel783 |
last post by:
Hello!
Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
|
by: jfyes |
last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
|
by: ArrayDB |
last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
|
by: CloudSolutions |
last post by:
Introduction:
For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
|
by: Defcon1945 |
last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
|
by: af34tf |
last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
|
by: Faith0G |
last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome former...
| |