I should do a "free" encoding of the DHM algorithm. Input: Y, p, a, b Output: shared key k
I have to code the program in a programming language of choice by structuring the program into functions. The basic program must be able to calculate powers with "small numbers". The "advanced" version (2.0, 3.0, 4.0) must be able to handle "larger" numbers by implementing the properties of the modules.
Can you aid me?
if the exponents are INTEGERS you can use this power function. You can remove the upper terms for small integer exponents -- if you need only say to the 10th power you only need up thru the 8. If you need decimal powers, its a different algorithm. Doubles to integer powers can be done with this algorithm too, just change return type and base type. The only value that fits in a long long for powers of 64 is 2, of course....
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
longlong ipow(longlong p, unsignedlonglong e) //pow(p,e)
{
constlonglong one = 1;
constlonglong *lut[2] = {&p,&one};
longlong result = 1;
result *= lut[!(e&1)][0]; p *= p;
result *= lut[!(e&2)][0]; p *= p;
result *= lut[!(e&4)][0]; p *= p;
result *= lut[!(e&8)][0]; p *= p;
result *= lut[!(e&16)][0]; p *= p;
result *= lut[!(e&32)][0]; p *= p;
result *= lut[!(e&64)][0];
return result;
}
I have only really played with crypto using small numbers, never needed to do it for real. Are you looking for a big-int power and modulus routine? Or the full DHM? Or just hints?
#include<iostream>
usingnamespace std;
bool primo(int z){
for(int i = 2; i <= z/2; i++)
{
if(z % i == 0) returnfalse;
}
returntrue;
}
int potenza(int n, int e, int m)
{
int result = 1;
for (int i = 0; i < e; i++) result = result * n % m;
return result;
}
int main(){
int a,b,p,Y;
cout<<"inserisci mio segreto: ";
cin>>a;
cout<<"inserisci segreto amico: ";
cin>>b;
do{
cout<<"inserisci p: ";
cin>>p;
}
while(primo(p) == false);
do{
cout<<"inserisci Y: ";
cin>>Y;
}
while(Y>p);
int alfa = potenza(Y,a,p);
cout<<"alfa: "<<alfa<<endl;
int beta = potenza(Y,b,p);
cout<<"beta: "<<beta<<endl;
cout<<"mia chiave: "<<potenza(beta,a,p)<<endl;
cout<<"chiave mio amico: "<<potenza(alfa,b,p);
}
you should use the sieve algorithm if you want primes. Your loop is too slow. The best way is a vector of bool or a block of bits (bitset, etc) such that bits[number] is true (prime) or false (not).