Encoding c++ of the DHM algorithm

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
long long ipow(long long p, unsigned long long e) //pow(p,e)
{ 
  const long long one = 1;
  const long long *lut[2] = {&p,&one};
  long long 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?
Last edited on
I don't understand well this code because I havent' studied soem terms at school.
It is good this?
I wish to remember that p must be prime number:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
using namespace std;

bool primo(int z){
    for(int i = 2; i <= z/2; i++)
{ 
        if(z % i == 0) return false;
    }
    return true;
}


   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);
   
}
Last edited on
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).
Jonnin can you see me the new code with a vector of bool for the primes?
Many thanks!
This can be tweaked, its a quick starting point, or you can google for a highly optimized one.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
int main()
{
  constexpr uint64_t maxp = 10000000;
  vector<bool> pn(maxp+1,true);
  pn[0] = false; //set the odd cases. 
  pn[1] = false;
  
  for(int i = 2; i < sqrt(maxp); i++)
   if(pn[i])    
   for(int j = i*i; j<maxp; j+= i)
     pn[j] = false; 
	 

  // for(int i = 2; i <maxp; i++)  ///test it if you want.  
  //   if(pn[i]) cout << i << endl;
  //use:  if(pn[num]) {then_num_is_prime_here();}
}
Last edited on
Topic archived. No new replies allowed.