0

My code for encrypting/decrypting message looks like this:

#include <bits/stdc++.h>

using namespace std;

unsigned long long poww(unsigned long long a, unsigned long long k, unsigned long long q)
{
      if (k==1)
      {
        return a%q;
      }

      unsigned long long w = (poww(a,k/2,q)*poww(a,k/2,q))%q;
      if(k%2==1)w=w*a%q;
      return w;
}

unsigned long long private_key(unsigned long long public_key, unsigned long long e) {
    int x = 1;
    while(floor((x*public_key+1)/e) != (x*public_key+1)/e) {
        x++;
    }
    return (x*public_key+1)/e;
}

int main() {
    unsigned long long p,q;
    p = 47917;
    q = 44771;

    unsigned long long n = p*q;
    unsigned long long public_key = (p-1)*(q-1);
    unsigned long long e = 24407;

    unsigned long long d = private_key(public_key, e);

    unsigned long long message = 6382179;
    cout << "Message: " << message << endl;

    unsigned long long int encrypted_message = poww(message, e, n);
    cout << "Encrypted message: " << encrypted_message << endl;


    unsigned long long decrypted_mesage = poww(encrypted_message, d, n);
    cout << "Decrypted message: " << decrypted_mesage << endl;
}

After running this, I get:

Message: 6382179
Encrypted message: 1741171325
Decrypted message: 81343779

Why decrypted messages is different from original messages?

I would like to mention that for small number like 67, this script works fine

dosad
  • 151
  • 7
  • 3
    [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) – Some programmer dude Oct 22 '21 at 13:36
  • 2
    And while it's sometimes considered okay for small and simple examples, `using namespace std;` is [a bad practice](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). – Some programmer dude Oct 22 '21 at 13:37
  • 3
    As for your problem, this seems like the perfect time to learn how to *debug* your programs. For example by using a debugger to step through your code statement by statement while monitoring variables and their values. That should make it easy to see when and where things start to go wrong. – Some programmer dude Oct 22 '21 at 13:40
  • I am searching for the bug for few hours :( – dosad Oct 22 '21 at 13:44
  • sometimes hours are not enough, though if you step through your code with a debugger and compare expected with actual values you will find out at which point the two deviate. Then at least you know where the bug is. Thats the first step in fixing it – 463035818_is_not_an_ai Oct 22 '21 at 13:51
  • *this script works fine* -- You wrote a program, not a "script". – PaulMcKenzie Oct 22 '21 at 13:52
  • Compiler warnings are sometimes useful. For your code, clang-cl gives (among others): *comparing floating point with == or != is unsafe [-Wfloat-equal]* and MSVC gives: *implicit conversion from 'unsigned __int64' to 'double', possible loss of data*. – Adrian Mole Oct 22 '21 at 13:54
  • Try adding a `cout << x << endl;` just before the end of your `private_key` function, to see how many times the loop runs. (Clue: `x` remains less than 2 on my machine.) – Adrian Mole Oct 22 '21 at 13:56
  • 2
    `while (floor` -- The program is supposed to be integer-based. Once you introduced `floor`, the program is now broken. The `floor` function is a floating point function, so has all the issues of floating point. Use an actual big integer library or create your own instead of using floating point functions. – PaulMcKenzie Oct 22 '21 at 13:56
  • 1
    Unsigned integer division in C++ already floors, so if you are okay doing everything with 64-bit numbers (unsigned long long) then you can just drop the `floor()`, which as noted returns `double` and may lose precision. – Nate Eldredge Oct 22 '21 at 14:14
  • 1
    It does *not* work for 67, your calculation of the private exponent is incorrect. As for variable names, `(p-1)*(q-1)` is certainly not a "public key" and in fact must remain secret. – President James K. Polk Oct 22 '21 at 14:38

0 Answers0