RSA, part 2: encryption and decryption

Hi there! It's second part about RSA alorithm. We'll talk about encryption of messages and their decryption. For encyption and decryption we use the same operation: modular exponention. So, basically what we need to do is to create pow_mod function. We can implement it with 2 different approaches: recursion and iterative realizations.

But firstly we need to define some conditions. Let's define f function. It should get x^y mod n values and result value.

1. if y = 0, then return result
2. if the smallest bit of y is 0 (y is even number) , then f(x^2 mod n, y >> 1, n, result)
3. if the smallest bit of y is 1 (y is odd number), then f(x^2 mod n, y >> 1, n, result * x mod n)

That's all, simple and smart.

Implementation

Let's try to implement it. First will be implementation with recursion.

long f(long x, long y, long n, long res){ 
    if (y == 0) 
        return res; 
    // if the smallest (last from right side) bit is 1, if so, then number is odd 
    else if (y & 0x01) 
        return f((x * x) % n, y >> 1, n, (res * x) % n); 
    // if the smallest (last from right side) bit is 0, then number is even 
    return f((x * x) % n, y >> 1, n, res);
} 
long pow_mod(long x, long y, long n){ 
    return f(x, y, n, 1);
}

Now some explanations, why I check if number is even or odd (y & 0x01 or y & 1 or y & 0x1) in this unclear way. It's just simply faster to use bit operations. Why it still works right? If we represent number in binary view, then we'll get interesting refularity: each even's number smallest bit is always 0 and each odd's number smallest bit is always 1. If you have time, you can convert any number to binary view and check. The same idea with using y >> 1 instead of y / 2. It works faster because it's a bit operation and bit operations always work fast.

Now iterative realization. It's better to use this implementation because you won't have any problems with call stack which of course has limits.

long pow_mod(long x, long y, long n){ 
    long res = 1; 
    // while y != 0 
    while (y){ 
        // if the smallest bit is 1 then number is odd 
        if (y & 0x01) 
            res = (res * x) % n; 
        x = (x * x) % n; 
        y >>= 1; 
    } 
    return res;
}

Time complexety, auxiliary space

• Implementation with recursion: O(log n), O(log n)
• Iterative iImplementation: O(log n), O(1) - constant time

Encryption and decryption

For encryption data we'll use this formula: m^e mod n. For decription data we'll use c^d mod n formula.

// encrypted text (c) = m^e mod n 
long long c = pow_mod(m, e, n); 
std::cout << "encrypted text: " << c << std::endl; 0
// decrypted text (m) = c^d mod n 
m = pow_mod(c, d, n); 
std::cout << "decrypted text: " << m;

Full code: https://github.com/rastr-0/Simple_algorithms/blob/master/RSA/rsa.cpp

see ya soon

@rastr