## Project Euler 182: RSA encryption

#### Problem Description

The RSA encryption is based on the following procedure:

Generate two distinct primes *p* and *q*.

Compute *n*=*pq* and φ=(*p*-1)(*q*-1).

Find an integer *e*, 1<*e*<φ, such that gcd(*e*,φ)=1.

A message in this system is a number in the interval [0,*n*-1].

A text to be encrypted is then somehow converted to messages (numbers in the interval [0,*n*-1]).

To encrypt the text, for each message, *m*, *c*=*m ^{e}* mod

*n*is calculated.

To decrypt the text, the following procedure is needed: calculate *d* such that *ed*=1 mod φ, then for each encrypted message, *c*, calculate *m*=*c ^{d}* mod

*n*.

There exist values of *e* and *m* such that *m ^{e}* mod

*n*=

*m*.

We call messages

*m*for which

*m*mod

^{e}*n*=

*m*unconcealed messages.

An issue when choosing *e* is that there should not be too many unconcealed messages.

For instance, let *p*=19 and *q*=37.

Then *n*=19*37=703 and φ=18*36=648.

If we choose *e*=181, then, although gcd(181,648)=1 it turns out that all possible messages

*m* (0≤*m*≤*n*-1) are unconcealed when calculating *m ^{e}* mod

*n*.

For any valid choice of

*e*there exist some unconcealed messages.

It’s important that the number of unconcealed messages is at a minimum.

Choose *p*=1009 and *q*=3643.

Find the sum of all values of *e*, 1<*e*<φ(1009,3643) and gcd(*e*,φ)=1, so that the number of unconcealed messages for this value of *e* is at a minimum.

#### Analysis

At the heart of this problem is the simple formula: [gcd(*e*-1,*p*-1)+1][gcd(*e*-1,*q*-1)+1] as outlined in many texts such as *Recent Advances in RCA Cryptography* in the chapter *Properties of the RSA cryptosystem*. Specifically Lemma 5.1 on page 69 shows a nice proof of this equation.

So encoding this into a program is straightforward and simple. Just sum all values of e where gcd(e,phi) = 1 and gcd(e-1,q-1) and gcd(e-1,p-1) are at a minimum (equal 2).

#### Project Euler 182 Solution

Runs < 1.8 seconds in Python 2.7.Use this link to get the Project Euler 182 Solution Python 2.7 source.

#### Afterthoughts

- Function
`gcd`

is listed in Common Functions and Routines for Project Euler.

*Project Euler 182 Solution last updated*

## Discussion

## No comments yet.