Can you do RSA encryption with Carmichael number?

By Phuong Anh (Han) Nguyen

Carmichael number plot

I was introduced to Carmichael numbers in CSCI462, a Carmichael number is a composite number n that follows this congruence relation:

for all b that is relatively prime to n.

So what is significant or important about this number that we should know? Carmichael numbers are also called pseudoprimes or Fermat pseudoprimes, in which they will pass the Fermat primality test even though they are not actually prime. If we use Carmichael numbers in RSA encryption, it will very likely make the cryptosystem vulnerable, and from this blog, I see that Pseudoprimes can mess up the decryption process. So in this blog, I want to test 2 aspects of RSA using Carmichael numbers: Functionality and Security, I will also talk about the frequency of Carmichael numbers.

Functionality

These are my codes for each part of the RSA encryption process and the testing function:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def check_prime(n):
    if n == 2:
        return True
    elif n % 2 == 0 or n <= 1:
        return False
    stop_point = int(math.sqrt(n)) + 1
    for prime_test in range(3, stop_point, 2):
        if n % prime_test == 0:
            return False
    return True
def fermat_test(n, times):
    if n == 2 or n == 3:
        return True
    elif n % 2 == 0 or n <= 1:
        return False
    else:
        for _ in range(times):
            a = random.randint(2, n - 1)
            while gcd(a, n) != 1:
                a = random.randint(2, n - 1)
            if square_multi.square_multi(a, n - 1, n) != 1:
                return False
        return True

Check Prime function is the brute force way to do it, buy checking every single number that is smaller than the square root of n, we can check if n is a prime or not, this method is very slow but will always produce the correct result. The Fermat test function is based on Fermat’s little theorem and the Fermat primality test, stating that: “If p is a prime number, then for any integer a the number ap – a is an integer multiple of p“, this is expressed as:

These are the steps to encrypt using RSA and testing. I use 50 as plain text and e= 257 for the consistency:

def calculate_rsa(p, q, e, original):
    n = p * q
    c = square_multi(original, e, n)
    return c


def decrypt_rsa(p, q, e, cipher):
    n = p * q
    euler_totient = (p - 1) * (q - 1)
    d = inverseMod(e, euler_totient)
    plain_text = square_multi(cipher, d, n)
    return plain_text
def test(p, q):
    plain = 50
    print("Plaintext: ", plain)
    e = 257
    cipher = calculate_rsa(p, q, e, plain)
    print("Cipher text: ", cipher)
    print("Decrypt: ", decrypt_rsa(p, q, e, cipher))

The square and multiply algorithm helps with the large exponent multiplication and modding. Given an exponent with t+1 bits, the complexity of Square and multiply is 1.5*t. Here is the code for it:

def square_multi(num, power, mod):
    result = 1
    power = bin(power)
    for i in power[2:]:
        result = result ** 2
        if i == "1":
            result = result * num
        result = result % mod
    return result

To generate the Carmichael number that is smaller than a certain limit:

def get_carmichael(limit, amount):
    limit -= 1
    return_list = []
    while len(return_list) < amount:
        if fermat_test(limit, SECURITY_INT):
            if not check_prime(limit):
                return_list.append(limit)
        limit -= 1
        if limit == 0:
            break
    return return_list

This function takes in a limit of how big the number should be and an amount of how any number should be looked for. It will go backward from the highest number, check if it passed the Fermat test, and then check again if it’s actually a prime number. If it passes the Fermat test but does not pass the prime test, it is a Carmichael number. The SECURITY_INT by default is 15, it determines how many times we run the Fermat test on a number before deciding if it’s a possible prime or not.

After testing using 2 Carmichael numbers 561 and 8911 with some 3 digits and 4 digits prime, we got these results:

Testing for 561
Testing for 8911

As we can see, even though the Carmichael number works for some cases, 2/5 of the case we tested did not pass. This can be explained because of the wrong calculation of the φ(n) since we assume φ(n)= (p-1)(q-1) because p and q are prime, since one of them is not prime, the calculation of φ(n) is different.

Security

Carmichael numbers, being primes that makeup n in RSA cryptosystem, will make it less secure and vulnerable. We know that the security of RSA relies upon the computational difficulty of the factoring of big integers and big primes, hence, the best attack against RSA itself is brute force to find out p and q. Let’s say we have the length of n = 256 with the length of p=120 and length of q=126, it would be computationally impossible to figure out p or q. If p is a Carmichael number that can be factorized into some smaller number with the length of 50, 30, 40, it will drastically shorten the time for the attack to find the right combination of p*q=n. So even though I don’t have the resource to actually test how fast we can break RSA with Carmichael number, theoretically, it is possible to brute force the cryptosystem.

Frequency

So how many Carmichael numbers are there you might ask? Unfortunately, there is an infinite amount of Carmichael numbers. A study by Alford et al have shown that there are infinitely many Carmichael numbers. R.G.E Pinch also proved the upper bound of Carmichael number as:

R.G.E. Pinch formula of Carmichael bound

Here is an example I found on the chance of getting a Carmichael number in generating prime for 512- bit number:

Example by Dan Ma (2014)

We can see that the chance of getting a Carmichael number when selecting an odd number under 10154 is less than the 1 in 1046 chance.

Conclusion

It is not recommended to use Carmichael numbers in RSA as it is not reliable functionally and definitely not secure theoretically. While the chances of getting Carmichael numbers are pretty low we can say that the Fermat test is still safe to use when checking the primes, but, it is advised that you also use the Miller-Rabin primality test to check for possible pseudoprime numbers.

Sources

Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s