CODEWITHSUNDEEP
crecursionmoduloexponentiation
John R
John R

Reputation: 389

C programming to calculate using modular exponentiation

I just had a quick question to verify if my programming and math are correct. Sorry in advance if this is off topic, I don't where else to ask to get quality answers ;) How can I double check that the answer is correct? Thanks

This is my problem:

If a cryptosystem has 2^48 possible keys, and you have 1000 computers, each of which can test 500,000 encryption keys per second, in how many days would you be able to recover the correct key in the worst case, assuming a brute force search and that you can immediately recognize the correct key when you have tried decrypting with it? (Recall, there are 86,400 seconds in a day.)

Here is my program output to solve the problem:

Number of keys: 2^48
Number of computers: 1000
Number of keys/persecond: 500000
Number of days: 647168000

My code is as follows:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int max_power(int base,int exp,int mod);
int main(void)
{
    int num_computers=1000;
    int keys_per_second= 500000;
    int seconds_in_day=86400;
    printf("Number of keys: 2^48\n");
    printf("Number of computers: %d\n",num_computers);
    printf("Number of keys/persecond: %d\n",keys_per_second);
    printf("Number of days: %d\n",max_power(2,48,seconds_in_day)*num_computers*keys_per_second);

    return 0;
}

int max_power(int base,int exp,int mod)
{
    if (exp == 0)
        return 1;
else if (exp%2 == 0) {
        int mysqrt = max_power(base, exp/2, mod);
        return (mysqrt*mysqrt)%mod;
    }
    else
        return (base*max_power(base, exp-1, mod))%mod;
}

Final code (still not completely satisfied but I will ask my professor if this would be acceptable on a test):

int main(void)
{
    double num_computers=1000;
    double keys_per_second= 500000;
    double seconds_in_day=86400;
    long double keys=pow(2.0,48);
    printf("Number of keys: %.0lf\n",keys);
    printf("Number of computers: %.0f\n",num_computers);
    printf("Number of keys/persecond: %.0f\n",keys_per_second);
    printf("============================================\n");
    printf("Time to decrypt all keys: %.2f days\n",keys/(num_computers*keys_per_second*seconds_in_day));

    return 0;
}

Upvotes: 1

Views: 3720

Answers (1)

Adam Burry
Adam Burry

Reputation: 1902

The correct calculation was pointed out in the comments. However, you are still not sure how you went wrong.

Your application of modular exponentiation here is not quite correct. Modular exponentiation only gives you the remainder of x to the y over z, you also need the quotient.

Upvotes: 1

Related Questions