Is there some restrictions on values of p,q,d,e etc in RSA algorithm while trying to encrypt English Ciphertext?

a PlainText should be less than $n=p*q$

Yes, that's a requirement in textbook RSA (the kind of RSA in the question). Valid textbook RSA plaintext and ciphertext is limited to integers in the interval $[0,n)$. That because for any integer $x$, the quantity $x\bmod n$ (without a parenthesis immediately before$\bmod$) by definition lies in this interval.

I'm not getting $2^k<n$

This relation (or the somewhat lesser $2^k\le n$ ) ensures that any $k$-bit bitstring, when converted to integer per unsigned binary convention, lies in the $[0,n)$ interval of valid RSA plaintext. Indeed, it is not met for $n=3\cdot 11$ and $k>5$. If we use ASCII encoding of characters, we need $n>2^7$.

$e*d/m$ should give remainder 1 where $m=(p1)(q1)$

That condition is equivalently written $e\,d\equiv1\pmod m$. In this, the $\equiv$ sign can be read is equivalent to or is congruent to; and the$\bmod$ with parenthesis immediately before is read modulo (perhaps with a small pause before to mark that it's a qualifier for $\equiv$ rather than an operator). What the question notes $m$ is more often noted $\varphi$ (I'll do this), $\Phi$ or $\phi$ (see Euler's totient). Beside

• This condition $e\,d\equiv1\pmod\varphi$ is not sufficient:
  • It's required that $p$ and $q$ are distinct primes (otherwise the definition of $\varphi$ must be changed, and limitations on plaintext must be set).
  • It's required $d>0$ (otherwise $\operatorname{PT}=\operatorname{CT}^{\,d}\bmod n$ needs a non-standard definition of modular exponentiation).
• This condition $e\,d\equiv1\pmod\varphi$ is not necessary: it can and often is replaced by the less stringent condition that $e\,d\equiv1\pmod{p-1}$ and $e\,d\equiv1\pmod{q-1}$; or equivalently that $e\,d\equiv1\pmod\lambda$ with $\lambda=\operatorname{lcm}(p-1,q-1)$ (see Carmichael function).

Since $22<26$, maybe $p=2$, $q=11$ doesn't work

Indeed this choice of parameters will not allow decryption of plaintext of $22$ and more (letter V and later in the alphabet with the encoding used).

Again plaintext $12$ leads to ciphertext $12$

Textbook RSA with artificially small parameters is ripe with such so-called fixed points: there are always at least three (including $0$, $1$, $n-1$), at least nine for odd $n$ (as customary), and often much more. Thus textbook RSA with artificially small parameters, even with the normally public key made secret, is much less secure than a substitution cipher. However fixed points become vanishingly rare when $p$ and $q$ are large random primes (with hundreds of decimal digits rather than 1 or 2 in the question, which is necessary for security). And in secure RSA, plaintext is made random-like, thus hits the fixed points with vanishing probability.

Is there any restrictions if among $p$ or $q$ anyone should be greater?

No: $p$ and $q$ play symmetric roles. They can be any distinct primes. Customarily, they are odd, even in textbook RSA with artificially low parameters. If we want secure RSA, they need to be large (hundreds of decimal digits) and secret (thus randomly chosen).

Is there any restrictions like which of the $d$ or $e$ should be greater?

No for textbook RSA. For valid $(p,q)$ as above, any $(e,d)$ with $e\,d\equiv1\pmod{(p-1)(q-1)}$ with $e,d\in\mathbb N^*$ works, in the sense of allowing encryption/decryption. It's customarily added $e>1$ (since $e=1$ is among the values of $e$ that make all points fixed). It's customarily chosen a rather small $e$ (almost always $e<n$ and typically $e<n/4$ and $e<2^{256}$, sometime with $2^e>n$ or $e>2^{16}$ though). Often there's an upper limit on $d$, often one of $d<(p-1)(q-1)$ or the slightly more lenient $d<n$ (the former is met when computing $d$ from $e$ as $d=e^{-1}\bmod\varphi$, and implies the later). When $e$ is small and $d$ computed from $e$ (both are customary), typically $e<d$, and that becomes overwhelmingly likely for practical $n$.

In real world, maybe you'd convert "SELL" to a base x number and calculate the value of it and only encrypt it.

That allows encryption/decryption to work and mitigates the increase in plaintext size, but that's not practiced. In real world, one seldom encrypts text directly with RSA (much less with textbook RSA). Rather, one uses a hybrid cryptosystem. And when one does encrypt text with RSA, that's per RSAES-PKCS1-v1_5 or best RSAES-OAEP.

Textbook RSA directly encrypts the plaintext as $\operatorname{CT}=\operatorname{PT}^{\,e}\bmod n$. This allows to verify a guess of the plaintext, thus makes RSA pointless to encrypt a name on the public class roll even if $p$ and $q$ are proper. In the particular textbook discussed, there are further deviations from RSA as practiced:

• Encryption letter by letter.
• Artificially small parameters ($n$ must be several hundreds decimal digits in secure RSA). This is to ease computations without a computer with appropriate software, and allow printign the numbers.
• In encryption (resp. decryption), $\operatorname{PT}^{\,e}$ (resp. $\operatorname{CT}^{\,d}$ ) are evaluated in full before a final modular reduction. This would make it impracticable to print the numbers even for most three-digit $n$. This is not how modular exponentiation is done, or should be taught.
• The private exponent $d$ is actually used. Implementation that do so exist, but for performance reasons most do not, and compute the same quantity in a faster way. There are multiple benefits of teaching RSA this later way:
  • Teach what is actually practiced and works the most efficiently, even making manual calculation practicable with slightly larger parameters.
  • Do without the notions of Euler's totient or Carmichael's function. It's used only the Chinese Remainder Theorem and Fermat's little theorem, which have many applications.
  • Provide a proof that RSA decryption recovers the plaintext that works alongside how the decryption is done.
  • Make that proof valid: many other proofs assume $\gcd(\operatorname{PT},n)=1$, which for artificially small parameters is far from certain.
  • Make it less likely that the condition $p\ne q$ gets forgotten as it often is, since it's an hypothesis required by the Chinese Remainder Theorem. This condition is necessary for correct decryption to be possible when $\gcd(\operatorname{PT},n)\ne1$ (as occurs in the question), and independently for $\varphi(n)=(p-1)(q-1)$ to hold.

Solved by user555 (126,068 )
Aug 29, 2022 at 10:56