2
$\begingroup$

I know I am not supposed to ask for answers, which I am not. I have the solution but I don't understand how 'e' is selected, pls see my explanation below.

I am doing practice questions for my Cyber Security Paper.

One of the question I came across is: "Using RSA Technology, Alice wants to send Bob the number 10. Alice selected p = 7, q = 3. Generate for Alice.

  1. Private Key
  2. Public Key
  3. Cipher

Based on the above the choices for 'e' can be [5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71]

The solution provided for the question selected 7 for e and 31 for d. Which will make the Cipher = 10 and the Plain Text is also 10.

Is the solution wrong or am i missing something?

I selected 5 for e and 29 for d which will make the Cipher 82 and Plain Text 10.

Beyond asking if the solution is wrong, is there a guideline for how 'e' should be selected?

Below is the code i wrote to figure e & d. It is not perfect, as now I need to manually change the values of the variable. Putting it here as reference for how I am calculating the value for RSA.

#Private Key is (d, n)
#Public key is (e, n)

p = 7
q = 13
m = 10
e = 5
d = 29


n = p*q
print("n = " + str(n) + "\n")

range_n = [i for i in range(1, n + 1)]
print("Range of n")
print(range_n)
print(" ")

co_prime_n = []
for j in range_n:
    if j % p != 0 and j % q != 0:
        co_prime_n.append(j)
print("Co-Prime with n. Share no common factor with n")
print(co_prime_n)
print(" ")

totient = (p-1)*(q-1)
print("totient: " + str(totient) + "\n")

range_e = [i for i in range(2, totient+1)] #1 < e < totient
print("Range for e")
print(range_e)
print(" ")

even = 0
odd = 0
if totient % 2 == 0:
    even = 2
else:
    even = 3

if totient % 3 == 0:
    odd = 3
else:
    odd = 2

print("even: " + str(even))
print("odd: " + str(odd))
print(" ")


choices_for_e = []
for k in range_e:
    if totient % k != 0 and k % even != 0 and k % odd != 0:
        choices_for_e.append(k)
print("n = " + str(n))
print("totient: " + str(totient))
print("Choices for e. e shares no common factor with n and totient")
print(choices_for_e)
print(" ")



#d = 0
#de(mod totient) = 1

multiples_e = [x for x in range(1, 10000) if x % e == 0]

for num in multiples_e:
    if num % totient == 1:
        print(str(num), "d =", str(num/e))
print(" ")




Cipher = 0
Cipher = (m**e)%n
print("Cipher: " + str(Cipher))

PlainText = 0
PlainText = (Cipher**d)%n
print("Plain Text: " + str(PlainText))
$\endgroup$
2
  • 1
    $\begingroup$ I (now) guess it's meant "q = 13" where there is "q = 3" $\endgroup$
    – fgrieu
    Jul 27, 2022 at 12:10
  • $\begingroup$ Yes yes, so sorry!! $\endgroup$
    – Sam Wong
    Jul 28, 2022 at 5:21

2 Answers 2

7
$\begingroup$

RSA can only be secure if it's hard to factor the public modulus $n$, and that requires the individual factors of $n$ to be large (in the order of some hundreds of decimal digits). Thus the choice of $p$ and $q$ (I'll assume: $p=7$, $q=13$) in the problem statement implies that we do not care for security in the context of the question.

Yes, the choice of $e=7$ makes $10$ a so-called "fixed point" for textbook RSA encryption: the ciphertext equal the plaintext. There always are at least $9$ (see Poncho's answer). With $(e,n)=(7,7\times 13)$, there's $49$ out of $91$. There's only somewhat less for $(e,n)=(5,7\times 13)$: $15/91$. That's a sizable proportion, which would be a security concern. Fortunately, that proportion tends to decrease when $n$ grows; e.g. for $(e,n)=(5, 307\times 313)$: $15/96091$.

But again, the problem statement requires that we disregard security. Thus the answer $e=7$ is not "wrong": none of the rules told in class is broken! By this standard even $e=13$ should be acceptable¹, despite it making every value in $[0,91)$ a fixed point.

I selected $5$ for $e$ and $29$ for $d$ which will make the Cipher $82$ and Plain Text $10$.

Yes that's correct; and $e=5$ seems a somewhat better (at least, more pedagogical) choice, especially if the problem statement mentions the plaintext $10$. Some remarks:

  • A cipher is a transformation. You want to write: "make the ciphertext $82$ and plaintext $10$."
  • You may notice that raising to the power $e=5$ or $d=29$ modulo $n=91$ does the exact same thing, because $e\equiv d\pmod{p-1}$ and $e\equiv d\pmod{q-1}$. Thus decryption is the same as encryption, and encryption is public! That's unavoidable with the childishly low $n$ in the question. Hence that $n$ is a poor pedagogical choice to illustrate RSA.
  • If you wonder why the formula $d=e^{-1}\bmod((p-1)(q-1))$ in the course does not yield $d=5$ when $d=5$ would work: this formula yields one of several working private exponents $d$ (assuming $P$ and $q$ are distinct primes). The lowest positive working $d$ is obtained as $d=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)$. With the values of $p$ and $q$ at hand that yields $d=e\bmod12$ for every admissible $e$.

Guideline for how $e$ should be selected?

In such exercises on textbook RSA, it makes sense to select the smallest $e$ that obeys all the prescriptions set by the course (as you did). In your case, these prescriptions are $\gcd(e,p-1)=1$ and $\gcd(e,q-1)=1$ [or something equivalent like $\gcd(e,(p-1)(q-1))=1$ ], with $e>1$ and perhaps some upper limit for $e$ that we don't need to consider when we choose the lowest $e$. That's one of several advantages of choosing the lowest valid $e$. Another includes being often optimum and always near-optimum in term of cost of encryption.

There's no unique mathematically valid range for $e$: the most common standard for acceptance of public keys makes it $[3,n)$; another standard for generation of RSA keys uses $[65537,2^{256})$; the original RSA article indirectly makes it $[1,\varphi(n))$ (it actually computes $e$ from $d$, but that has drawbacks); an early instance of textbook RSA (see link 2s there) uses $e=n$; negative $e$ work, too.

Note: The part of the code that verifies j shares no common factor with $n$ is not needed. Perhaps it's present because you have been given a partial proof of the correctness of RSA, that assumes the plaintext is coprime with $n$. But that condition is not necessary, and a proof can be made replacing that condition with: $n$ is the product of distinct prime factors. That later condition is typically assumed in RSA anyway (in particular, in the computation of the totient).

Don't be fooled: this test is not about RSA as actually usable or used. And if the test is adequate for the course, then the course is not adequate for one attempting to use RSA in real life, or implement it.


Other notes (off-topic since we are not a code review site):
I'm puzzled at the logic of the code that determines the possible values of $e$ (including why odd and even are needed). I would bet it's wrong and won't work for some valid choices of $p$ and $q$.
(Cipher**d)%n won't work with mildly realistic parameters, because Cipher**d will exceed the computer's capacity. Instead you want to perform modular reduction along the computation. In modern Python, pow(Cipher,d,n) does it, per the principles there.
$d$ is found by brute force search and that won't work in acceptable time for more sizable $p$ and $q$. One much more efficient method to find $d$ is computing the multiplicative inverse of $e$ by the (half) Extended Euclidean algorithm. It turns out that in many modern Python, the necessary math is built into pow, which handles negative second parameter.
The code on the left of #1 < e < totient does not match that comment.


¹ I mean acceptable from the perspective of getting the maximum mark in the artificial situation the question sets up, not technically recommendable: nothing in the problem statement is!

$\endgroup$
1
  • 1
    $\begingroup$ I'd consider $e=13$ acceptable for this modulus if-and-only-if $e=1$ is acceptable. $\endgroup$ Jul 27, 2022 at 14:15
6
$\begingroup$

fgrieu's answer is correct; I just wanted to add this note: tiny RSA modulii tend to act oddly; that is, in ways that large modulii do not exhibit.

For example, all RSA modulii (formed by two distinct odd primes) always have at least nine fixed points for any allowed $e$, three of these fixed points are the obvious ones (0, 1, n-1), but there are at least six nonobvious ones. For a large modulus, the probability of hitting such a fixed point is tiny; for a small modulus, the probability of selecting one is pretty good.

And, the modulus you mentioned in the question $n = 3 \times 7$ is even worse; any $e$ that's not a multiple of 2 or 3 works; however for any $e \equiv 1 \bmod 6$, all points are a fixed point (and so for $e=7$, not only 10 is a fixed point as you observed, but all other messages as well). And, if $e \equiv 5 \bmod 6$ (the only other possibility), not all messages are fixed points, but $e=d$ works in this case.

The bottom line: trying to learn RSA with such tiny values can be quite misleading...

$\endgroup$
1
  • $\begingroup$ Yes: smallish numbers (basically, those amenable to easy by-hand computation) tend to behave mildly anomalously for such stuff. Apparently, (!!!) many number-theoretic patterns don't really start up effectively for a little while. And there are more extreme cases, e.g., see Skewes' Number... :) $\endgroup$ Jul 27, 2022 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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