Skip to content

Problem 182 – RSA encryption

May 31, 2010

The 182nd Euler problem was definitely very interesting to solve. At first, the problem description looks very complicated and with a lot of information. But after some reading I was able to disregard some of the information. I will try to put my line of thoughts into words.

The RSA encryption is base on the following procedure:

  • Generate two distinct primes p and q.
  • Compute n = p q and phi = (p-1) (q-1).
  • Find an integer e, 1 < e < phi, such that gcd(e,phi) = 1.

The e is used to encrypt a message. So, for a message m, we need to calculate c = me mod n. However, some messages are unconcealed, i.e. there exist messages m such that me mod n = m.

The problem aims to find the sum of all values of e, 1 < e < phi (1009,3643) and gcp(e,phi) = 1 so that the number of unconcealed messages is at a minimum.

As a starting point, phi is easily calculated:

phi = (p-1)*(q-1)

In the same way, the problem description describes the range of values in which one should pick e:

e <- [2..phi-1]

Until now it is easy. The big issue is how to find out how to make sure that the number of unconcealed messages is at a minimum. After some reading, I found out that the number of unconcealed messages is given by:

(1 + gcd (e-1) (p-1)) * (1 + gcd (e-1) (q-1))

Furthermore, it is also true (page 290 of Handbook of applied cryptography) that since e-1, p-1 and q-1 are all even, the number of unconcealed messages is always at least 9. So if we want to make sure that we sum the values of e so that the number of unconcealed messages are at a minimum:

(1 + gcd (e-1) (p-1)) * (1 + gcd (e-1) (q-1)) == 9

From this formula we can derive that in order to have 9 as a result:

(gcd (e-1) (p-1)) +1 == 3

and

(gcd (e-1) (q-1)) +1 == 3

Since now we have all the pieces of the puzzle, here is the complete solution:

f p q = let phi = (p-1)*(q-1)
        in sum [e | e <- [2..phi-1],
                gcd e phi == 1,
                (gcd (e-1) (p-1)) +1 == 3,
                (gcd (e-1) (q-1)) +1 == 3
               ]

main = print $ f 1009 3643

The execution is also quite fast, as you can see:

real 0m2.067s
user 0m2.034s
sys 0m0.032s
Advertisements
Leave a Comment

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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: