Score:1

RSA Algorithm: What are the maximal possible locks that your friend can have so that he/she can secretly share that to you?

sa flag

I found this question while preparing for exam. The question is

Q)Suppose, you and your friends have a few numbers of locks and you all want to share that numbers among yourselves securely using RSA based cryptosystem. You are using the private key as (5,27) and your friends are using the public key as (13,27). One of your friends wants to share the exact amount of locks only to you. What are the maximal possible locks that your friend can have so that he/she can secretly share that to you?

The answer for the question is 26. But I don't understand how answer came. So can anyone explain the question and answer to me?

meshcollider avatar
gb flag
Hint: try encrypting and then decrypting a number that is bigger than 26. What do you notice goes wrong? What step goes wrong specifically?
Score:0
ng flag

CAUTION: There's is something so wrong in the question that it's reasonable to dismiss it, see second section. But first let's try to answer it as if we didn't notice.

In one of several slightly different definitions of textbook RSA,

  • the private key (used for decryption by the key holder) is $(d,n)$
  • the public key (used for encryption by anyone) is $(e,n)$,
  • plaintext $m$ and ciphertext $c$ are integers in the interval $[0,n-1]$,
  • $n$, $d$ and $e$ are chosen such¹ that for all $m$ in said interval we can compute
    • $c:=m^e\bmod n$ for encryption, then
    • $m':=c^d\bmod n$ for decryption, yielding $m'=m$.

In the above$\bmod$is an operator with two arguments, such that $x\bmod n$ is the uniquely defined integer $y$ with $0\le y<n$ and $x-y$ a multiple of $n$. When $x\ge0$ and $n>0$, that $y$ is the remainder of the Euclidean division of $x$ by $n$. The interval $[0,n-1]$ in the above definition of RSA is because it's the interval for the remainder in Euclidean division.

The question asks for the highest integer $m$ that yields itself when encrypted then decrypted. The given keys show that $n=27$; thus the answer (at most) is $m=n-1=27-1=26$. It makes sense to verify that this $m$ is correctly encrypted and decrypted for the question's $d=5$ and $e=13$ by the above definition of RSA. That proof is easy: we have $m\equiv-1\pmod n$, and $e$ and $d$ are odd, thus $c\equiv(-1)^e\equiv-1\pmod n$, thus $m'\equiv(-1)^d\equiv-1\pmod n$, thus $m'=c=m=n-1$ since that's the only integer $y$ in $[0,n-1]$ with $y\equiv-1\pmod n$.

Note: in the above $y\equiv x\pmod n$ means: $x-y$ is a multiple of non-zero $n$. In this use$\bmod$is not an operator with two arguments, as shown by the left parenthesis immediately on its left; rather,$\pmod n$ qualifies the $\equiv$ sign(s) on the left, which is/are equivalence modulo $n$.


There's at least one serious problem in the question: most integers $m$ in interval $[0,26]$ will not decipher correctly after encryption! If one cares to try, only $0$, $1$ and $26$ do so (they do whatever odd $e$ and $d$ are chosen). Further, all $m$ multiple of $3$ encipher to the same $c=0$, thus among these at most one can decipher correctly.

The issue is not only that $e$ and $d$ are not matching for that $n$. Problem is that for RSA to work for all $m$ in range $[0,n-1]$ it's necessary that $n$ is square-free, that is not divisible by the square of any prime; otherwise said, no prime shall appear twice in the factorization of $n$. But here $27$ is divisible by $3^2$. Without that square-free condition, for odd $n$, it's still possible to choose $e$ and $d$ such that decryption works for most $m$. But in the case at hand, $e$ and $d$ do not even match the condition¹ for that. One possibility is that the question was initially asked for $n=51$, which makes $d=5$, $e=13$ working; then carelessly changed to $n=27$.

It goes worse than the $(d,n)$ and $(e,n)$ parameters in the question being invalid for RSA: any RSA parameter of similar size does not allow to secretly share anything.

RSA can be secure only if $n$ is hard to factor, which requires it to be hundreds of decimal digits. Therefore any exercise with smaller $n$ is about an unsafe instantiation of RSA when facing competent adversaries with a computer. My point of view is that in pedagogical RSA examples $n$ should be large enough that there's some difficulty to factor it by hand. Also it should be stressed that deterministic RSA encryption with plaintext in a small set (e.g. a small interval, or name on the class roll) is unsafe, because one can try all plaintexts to decipher.

Also, "RSA based cryptosystem" is so loosely specified that assuming textbook RSA as in the first part is pure speculation. That problem statement is just wrong!


¹ The necessary and sufficient condition for textbook RSA to correctly decipher, for all plaintext integers $m$ in $[0,n-1]$ when $n$ is square-free, and at least for all such $m$ coprime with $n$ otherwise, is: $e\,d\equiv1\pmod{\lambda(n)}$, where $\lambda$ is the Carmichael function. It's often taught one of several slightly different conditions, which are sufficient but not necessary. Popular ones include $e\,d\equiv1\pmod{\varphi(n)}$, where $\varphi$ is Euler's totient; $d=e^{-1}\bmod{\varphi(n)}$, additionally meaning $0\le d<\varphi(n)$; $e=d^{-1}\bmod{\varphi(n)}$, used in the original RSA article; $d=e^{-1}\bmod{\lambda(n)}$, which yields the smallest positive valid $d$ for a given $e$.

Anantashayana Hegde avatar
sa flag
Thank you very much brother, I never thought someone else spend their time just to clear some stranger's doubt. I am very much grateful for this community and I will too spend my free time in clearing the doubts I know. Sorry I can't upvote your answer as I don't have enough reputation. Also I got many new things from your answer.
fgrieu avatar
ng flag
@Anantashayana Hegde : Glad it helped! On the left of the answer there's a tick mark. Clicking it accepts the answer, showing that the question is solved. It also increases reputation of both who asked and answered the question.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.