CODEWITHSUNDEEP
c++algorithmcryptographyrsamodulo
nurtul
nurtul

Reputation: 408

C++ Pseudo-RSA solving for d (decryption key) quickly with large numbers

for(d = 0;; d++)
{
    if((d * e) % tn == 1)
        break;
}

the following code is used on my RSA program to find the value for the d variable which will be used as the decryption key (d, N) so far when dealing with large numbers, this function takes quiet a while to cycle. I was wondering if there is a faster algorithm for this because modulo with large integers is always slow.

for example if the e value was 8161 and the tn value was 656316480 then it would take more than 4 seconds to fully calculate for d. The program works correctly, it's just that this part is very slow.

I've tried using the Extended Euclidean algorithm to calculate for d but for some reason it always gives me trouble. 

uint64_t extended_gcd(uint64_t a, uint64_t b)
{
uint64_t x = 0, lastx = 1, y = 1, lasty = 0, temp, quotient;
    while(b != 0)
    {
        temp = b;
        quotient = a / b;
        b = a % b;
        a = temp;
        temp = x;
        x = lastx - quotient * x;
        lastx = temp;
        temp = y;
        y = lasty - quotient * y;
        lasty = temp;
   }
   return lasty;
}

Bundled with;

d = extended_gcd(tn, e)
if(d < 0) //d CAN be negative
    d += tn;

Ive copied the above function (extended_gcd) from an old forum post I saw when I searched and it does in fact work, but only with small numbers. When the numbers get too extreme the return value is unexpectedly big, messing up the whole decryption key. Im not sure where exactly the problem is and I cant find a reliable function elsewhere with the same algorithm. Like I said I want to find a better algorithm for the first for loop Ive posted but I'm all out of ideas.

Upvotes: 0

Views: 1941

Answers (2)

nurtul
nurtul

Reputation: 408

Alright I found an answer that solved my problems. The following function is the modular inverse which is apparently a modified Extended Euclidean Algorithm and it solves correctly.

uint64_t modinv(uint64_t u, uint64_t v)
{
    uint64_t inv, u1, u3, v1, v3, t1, t3, q;
    int64_t iter;
    u1 = 1;
    u3 = u;
    v1 = 0;
    v3 = v;
    iter = 1;
    while(v3 != 0)
    {
        q = u3 / v3;
        t3 = u3 % v3;
        t1 = u1 + q * v1;
        u1 = v1;
        v1 = t1;
        u3 = v3;
        v3 = t3;
        iter = -iter;
    }
    if(u3 != 1)
        return  0;
    if(iter < 0)
        inv = v - u1;
    else
        inv = u1;
    return inv;
}

where "u" is set equal to "e" and "v" is set equal to "tn"

Example

P = 31
Q = 7
TN = (P - 1) * (Q - 1) = 180
N = P * Q = 217
E = 1 < E < TN and coprime with N so... 53
D = Calculated using function above... 17

Value to be encrypted with public key (E, N) = 32
32^(E) % N = 32^7 % 217 = 156
Value to be decrypted with private key (D, N) = 156
156^(D) % N = 156^17 % 217 = 32

I assume above math has been done correctly because it's a straight copy paste from my program. And I tried it with larger numbers, a prime reaching ~90000 and the result was instant and correct. I hope I am not deceived by something here.

Upvotes: 1

DarkSquirrel42
DarkSquirrel42

Reputation: 10267

the problem you are running into is: your integers are too small and will overflow when the values get larger ...

fixed size integers for things like RSA ... no good idea unless you happen to have integers with a few thousand bits length... instead of normal ints or even uint64_t, try an arbitrary precision integer library like GMP ...

your extended_gcd looks right ... it's the extended euclidean algorithm and should work for real world RSA key generation

Upvotes: 1

Related Questions