0
$\begingroup$

Background:

I've seen that the value of plain text should be lesser than p*q as per this slide. I was reading Tanenbaum's Computer Network book the next night, and I saw this thing that I'm not sure that I understood!

Tanenbaum's example

I feel he's telling that a PlainText should be less than $$p*q$$.

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

Let $$p=11, q=3$$

So, if I choose A,B,C…as plaintext. Then A=8 bits character.

So, let me test this:

$$2^k < n$$

$$2^k=2^8=256 < n=p*q=33$$

So, $$2^k < n$$ isn't true? So, what's Tanenbaum saying here? I feel it's very crucial point.

I'll present few cases of RSA encryption:

$$CT=(PT)^e \, mod\, n$$

$$PT=(CT)^d \, mod\, n$$

$$CT= Cipher Text$$

$$PT=Plain Text$$

$$e*d/m$$ should give remainder $1$, where;

$$m=(p-1)*(q-1);$$ where $p, q \, are \, 2$ prime numbers.

A) Sender takes $p=3, q=11$.

The value of $e=3$, $d=7$ satisfied the $remainder=1$ condition.

So, if sender wants to send "SELL":

$$S=19, CT=28$$

$$E=5. CT=26$$

$$L=12, CT=12$$

$$L=12, CT=12$$

B)$p=2,\, q=11 (since \, 22<26$, maybe this doesn't work as per Tanenbaum?

$e=3,d=7$

I'll only write CT here(i.e S=17 means that 17 is a cipher text for S after RSA encryption):

S=17

E=15

L=12

L=12 (Same here? why? Because of d,e being the same?)

C) $p=13, \, q=11$

$d=13,\, e=37$

So,

$$S=95$$

$$E=93$$

$$L=12$$

$$L=12$$ (Again got the same value, what is this? Even with different values of $p$,$q$,$d$,$e$!)

D) $p=17$,$q=11$

$d=23$,$e=7$

Its example is here.

Questions:

a) Is there any restrictions if among p or q, anyone should be greater?

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

I know e lesser than m and e greater than 1

And e should be relatively prime to m, i.e GCD(e,m)=1.

GCD(13,120)=1

For d,

de mod m=1

c) Would there be any cases, where while decryption, we would not be able to get the plain text due to some reasons even if everything is set alright? I've felt this in the past couple of times and it has got my head confused. I don't remember the cases, but I used to feel that for some value of p,q; the RSA cryptosystem won't decrypt back. My friends didn't agree with me and I failed the exam, so I'm not sure what happened.

I'm aware that encrypting character by character makes this same as "mono-alphabetic cipher" and RSA loses its essence, this is just a dummy example. In real world, maybe you'd convert "SELL" to a base x number and calculate the value of it and only encrypt it.

$\endgroup$
1
  • 2
    $\begingroup$ "In real world, maybe you'd convert "SELL" to a base x number and calculate the value of it and only encrypt it."; actually, what we do is select a random symmetric key, RSA encrypt the symmetric key, and then use the symmetric key to encrypt and integrity protect the actual plaintext $\endgroup$
    – poncho
    Commented Aug 29, 2022 at 14:50

1 Answer 1

2
$\begingroup$

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=(p−1)∗(q−1)$

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.
$\endgroup$

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.