4
$\begingroup$

The RSA encryption is based on the following procedure:

Generate two distinct primes $p$ and $q$. Compute $n=pq$ and $\phi=(p-1)(q-1)$. Find an integer $e$, $1<e<\phi$, such that $\gcd(e,\phi)=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 \bmod n$ is calculated.

To decrypt the text, the following procedure is needed: calculate $d$ such that $ed\equiv1 \pmod \phi$, then for each encrypted message, $c$, calculate $m=c^d \bmod n$.

There exist values of $e$ and $m$ such that $m^e \bmod n=m$. We call messages $m$ for which $m^e \bmod 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\cdot37=703$ and $\phi=18\cdot36=648$. If we choose $e=181$, then, although $\gcd(181,648)=1$ it turns out that all possible messages $m$ ($0\leq m\leq n-1$) are unconcealed when calculating $m^e \bmod 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<\phi(1009,3643)$ and $\gcd(e,\phi)=1$, so that the number of unconcealed messages for this value of $e$ is at a minimum.

https://projecteuler.net/problem=182

enter image description here

I'm just trying to understand the question, so I can attempt to solve for the actual solution, where $p=1009$ and $q=3643$.

But for the purpose of my clarification take $p=19$ and $q=37$.

My work so far:

def gcd(x,y):
    while y!=0:
        (x,y)=(y,x%y)
    return(x)

def rsa_return(p,q):
    n=p*q
    y=(p-1)*(q-1)
    to_return=[]
    for e in range(2,y+1):
        if gcd(e,y)==1:
            to_return.append(e)
    return(to_return)

Pretty straightforward so far, rsa_return(19,37) should return all possible values of $e$, given the conditions $p$ and $q$.

rsa_return(19,37)  =  [5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97, 101, 103, 107, 109, 113, 115, 119, 121, 125, 127, 131, 133, 137, 139, 143, 145, 149, 151, 155, 157, 161, 163, 167, 169, 173, 175, 179, 181, 185, 187, 191, 193, 197, 199, 203, 205, 209, 211, 215, 217, 221, 223, 227, 229, 233, 235, 239, 241, 245, 247, 251, 253, 257, 259, 263, 265, 269, 271, 275, 277, 281, 283, 287, 289, 293, 295, 299, 301, 305, 307, 311, 313, 317, 319, 323, 325, 329, 331, 335, 337, 341, 343, 347, 349, 353, 355, 359, 361, 365, 367, 371, 373, 377, 379, 383, 385, 389, 391, 395, 397, 401, 403, 407, 409, 413, 415, 419, 421, 425, 427, 431, 433, 437, 439, 443, 445, 449, 451, 455, 457, 461, 463, 467, 469, 473, 475, 479, 481, 485, 487, 491, 493, 497, 499, 503, 505, 509, 511, 515, 517, 521, 523, 527, 529, 533, 535, 539, 541, 545, 547, 551, 553, 557, 559, 563, 565, 569, 571, 575, 577, 581, 583, 587, 589, 593, 595, 599, 601, 605, 607, 611, 613, 617, 619, 623, 625, 629, 631, 635, 637, 641, 643, 647]

Then I build a function that will return the number of "unconcealed" messages given a particular selection of $e$, for all acceptable message values.

def count_check(p,q):
    n=p*q
    e_values = rsa_return(p,q)
    to_return=[]
    for i in range(len(e_values)):
        c=0
        for x in range(0,n):
            if (x**e_values[i])%n==x:
                c+=1
        to_return.append(c)
    return(to_return)

returns

count_check(19,37)=[15, 49, 9, 91, 15, 361, 9, 91, 15, 49, 9, 703, 15, 49, 9, 91, 15, 361, 9, 91, 15, 49, 9, 703, 15, 49, 9, 91, 15, 361, 9, 91, 15, 49, 9, 703, 15, 49, 9, 91, 15, 361, 9, 91, 15, 49, 9, 703, 15, 49, 9, 91, 15, 361, 9, 91, 15, 49, 9, 703, 15, 49, 9, 91, 15, 361, 9, 91, 15, 49, 9, 703, 15, 49, 9, 91, 15, 361, 9, 91, 15, 49, 9, 703, 15, 49, 9, 91, 15, 361, 9, 91, 15, 49, 9, 703, 15, 49, 9, 91, 15, 361, 9, 91, 15, 49, 9, 703, 15, 49, 9, 91, 15, 361, 9, 91, 15, 49, 9, 703, 15, 49, 9, 91, 15, 361, 9, 91, 15, 49, 9, 703, 15, 49, 9, 91, 15, 361, 9, 91, 15, 49, 9, 703, 15, 49, 9, 91, 15, 361, 9, 91, 15, 49, 9, 703, 15, 49, 9, 91, 15, 361, 9, 91, 15, 49, 9, 703, 15, 49, 9, 91, 15, 361, 9, 91, 15, 49, 9, 703, 15, 49, 9, 91, 15, 361, 9, 91, 15, 49, 9, 703, 15, 49, 9, 91, 15, 361, 9, 91, 15, 49, 9, 703, 15, 49, 9, 91, 15, 361, 9, 91, 15, 49, 9]

So each position in count_check(19,37) represents how many unconcealed messages there are for a given choice of $e$.

Then the question:

Find the sum of all values of $e$, so that the number of unconcealed messages for this value of $e$ is at a minimum?

If my understanding is correct, the number of unconcealed messages given a selection of $e$ is a constant. I feel like the question is looking for a path through count_check(19,37) with the minimum sum, but I'm not sure how the question should be bounded past this point.

$\endgroup$
  • 2
    $\begingroup$ As you pointed out, the array returned by count_check(19,37) represent how many unconcealed message there are for each choice of e. Clearly some values are smaller than others in your example. The smallest value ("9" in your example) happens for e=11,23,... Sum all these values (i.e. 11+23+...) $\endgroup$ – SleuthEye Jan 24 '17 at 1:51
7
$\begingroup$

The number of unconcealed messages is $[1+\gcd(e-1,p-1)]\cdot[1+\gcd(e-1,q-1)]$ and is not constant. The smallest number is 9. I would add logic to find the minimums (9), then perhaps identify the unconcealed messages of each to see if these are the same. If so, you can take any of these to get the sum of the unconcealed messages. If not, then you need to do this for all and find the minimum.

$\endgroup$
  • $\begingroup$ Yes, constant with respective to a choice of e,p,q. Thanks for the bit of math, I was unaware of the relationship. My gut says to sum at the index values of rsa_return() that are multiples of 4, but for a random selection of p and q it seems a bit of a stretch. r $\endgroup$ – Q-Club Jan 25 '17 at 20:56
  • $\begingroup$ @back_seat_driver That intuition might not be right in general - in this example you have $(p-1)(q-1) = 2^3 3^4$, and that eliminates a lot of possibilities. $\endgroup$ – tylo Jan 25 '17 at 21:16
  • $\begingroup$ Clearly the selection range for e is going to be much larger for the actual problem. Unless there is significance, to which I'm unaware, to you choosing to use prime factorization is your previous statement? @Carl Knox I'm accepting this answer for the processing time you just saved me! $\endgroup$ – Q-Club Jan 25 '17 at 21:43
  • 1
    $\begingroup$ The solution to Project Euler #182, therefore, is the sum of all e which match the criteria (1<e<φ(N) and gcd(e,φ(N))=1, where quines=9). These 9 quines (which reproduce themselves, therefore unconcealed)are dependent only on p and q and are always the same, regardless of e. In the event that e produces additional quines, these 9 will always be included. $\endgroup$ – Carl Knox Jan 31 '17 at 16:57
  • 1
    $\begingroup$ Another interesting fact is that these 9 always total 4N. I.E. p=47, q=59, N=2773, the 9 base quines are: 0 (0 is always unconcealed) 2772+1=2773 (pair 1, N−1 and N+1mod(n) are always unconcealed) 2538+235=2773 (pair 2) 2537+236=2773 (pair 3) 2302+471=2773 (pair 4) $\endgroup$ – Carl Knox Jan 31 '17 at 17:01
4
$\begingroup$

For the challenge numbers (as so often on Project Euler), the full search will probably run way too long. Very rough estimate:

  • $N$ has 22 bits
  • The number of values for $e$ are not that much less, maybe $2^{20} - 2^{21}$
  • $\phi(N) = 2^5 \cdot 3^3 \cdot 7 \cdot 607$
  • In your algorithm, you would run up to $n$ to find all values for $e$. And then for each $e$ you run through all $m$ up to $n$.
  • So you would do the innermost check x**e_values[i])%n==x around $2^{42}$ times.

As Carl Knox has pointed out, you need to filter your list of values for $e$ without actually doing the count. Here's what happens roughly:

In the count, you run through all possible values for $m$, which fullfill $m^e \equiv m \mod N$. Basically there are two different kinds:

  • $m$ is either coprime to $N$ or it is not.
  • If $m$ is coprime to $N$, then $m$ generates a subgroup of the multiplicative group $(\mathbb{Z}/\mathbb{Z}_N)^*$. And as any group generated by a single element, this is cyclic.
  • If $m$ is not coprime to $N$, e.g. $m = a\cdot p$ for some $a$, then this is different than the other case: There is no integer $x$, such that $m^x \equiv 1 \mod N$. So this does not generate a subgroup (with $1$) at all. Actually this case is irrelevant to the question: If for any $e$ we have $(a p)^e \equiv a p \mod pq$ this means $(ap)^{e-1} \equiv 1 \mod pq$, and that can't happen.

But the other case is quite interesting:

  • First, we note that $m^e \equiv m \mod N$ can be stated as $m^{e-1} \equiv 1 \mod N$. So we want to know those values for $e$, where this happens the least or not at all.
  • As in every finite group, every $m$ has a certain order. And that order is (by Lagrange's theorem) a divisor of the group order. The order of the multiplicative group is $(p-1)(q-1)$. As a side-note: The order of the elements is $\lambda(N) = \operatorname{lcm}(p-1,q-1)$ at most, see Carmichael fucntion. And when you iterate over all values of $m$, you will find elements of all divisors of $\lambda(N)$ as order.
  • Now the interesting step: For a given value $e$, and iterating over all $m$, when is $m^{e-1} \equiv 1 \mod N$ true? This is exactly the case if $e-1 \equiv 0 \mod o_m$, denoting the order of $m$ with $o_m$ (which is a divisor of $\lambda(N)$). To make it more clear: $m^{o_m} \equiv 1 \mod N$, because that's how the order is defined. Then for any value $e-1 = a \cdot o_m$ for an integer $a$, we have that $m^{e-1} \equiv m^{a o_m} \equiv (m^{o_m})^a \equiv 1^a \equiv 1 \mod N$, and thus $m^e \equiv m \mod N$.

So, it is clearly optimal if $e-1$ is coprime to $(p-1)(q-1)$. Additionally, we know that all $e$ are coprime to $(p-1)(q-1)$, so $e-1$ can't be coprime to that as well - both are even. So the optimal case is $\gcd(e-1,(p-1)(q-1)) = 2$. But what does this mean? This attributes actually the constant low number of unconcealed messages. As an example: There are four square roots of $1$, which are $1,75,628,702$ and thus for any odd $e$ you have that $1^e = 1, 75^e = 75, \dots $. The other solutions are probably the fourth roots of unity mod $N$, and since you started with $m=0$, $0^e \equiv 0 \mod N$ as well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.