# In RSA, given $n=100$ and $e=13$ ,Encrypt and Decrypt the plain Text “SECRET”

Is this question valid as $$n=100$$ is not a product of two primes, but can be expressed as $$100=2^2 5^2$$, if valid is there any criteria for choosing $$d$$ and other values?

• Welcome to Cryptography. Is this homework question? What you see is multi-prime key RSA.**Hint:** $n$ is already a composite, therefore, same rules apply. You need to find $\varphi(n=100)$ and then you can find $d$. – kelalaka Jan 26 at 19:55
• @kelalaka: what you propose won't work. – fgrieu Jan 26 at 20:01
• @fgrieu well, I think it is not about the functionality it is about security, right? – kelalaka Jan 26 at 20:16
• @kelalaka: problem is, in RSA, when the modulus is not squarefree, some plaintexts encrypt to the same ciphertext. Here, for all standard alphabets, that will prevent decryption. – fgrieu Jan 26 at 21:35
• @kelalaka, yes I found φ(n=100) as 40 and found d as 37.And as fgrieu stated , the encrypted text is not decrypted to same plain text if the values of letters has common factors with n=100, i.e when letter e=5 is used , it is not decrypted to letter e. But letter e=some other number with no common factors with 100, such as 7,11,13,19 .. is used ,this works. this question is not about security .I have to encrypt and decrypt . Is that possible? – SANTHOS KUMAR Jan 27 at 9:23

## 1 Answer

At least, there's an issue with using $$n=100$$ as the public modulus in RSA: that number is not squarefree. This implies that $$m\mapsto m^e\bmod n$$ can't be a bijection of the range $$[0,n)$$. And thus we must restrict the plaintext space to something lesser than $$[0,n)$$ if we want a deterministic decryption procedure.

Proof: if $$n$$ is not squarefree, there exists $$s>1$$ with $$s^2$$ dividing $$n$$. Let $$m$$ be an element of the subset $$\mathcal S$$ of $$[0,n)$$ with multiples of $$s$$. For $$e>2$$, $$m^e$$ is a multiple of $$s^2$$, which divides $$n$$. Therefore $$s^2$$ divides $$m^e\bmod n$$. Therefore $$m^e\bmod n$$ belongs to the subset $$\mathcal T$$ of $$[0,n)$$ with multiples of $$s^2$$. $$|\mathcal S|=n/s$$ and $$|\mathcal T|=n/s^2$$. Thus $$|\mathcal S|>|\mathcal T|$$. Therefore the function $$f:\mathcal S\to\mathcal T, m\mapsto m^e\bmod n$$ is bound to collide. Such collision is also a collision for RSA encryption on $$[0,n)$$.

For example, with $$n=100$$ and $$e=13$$, $$m_A=65$$ and $$m_U=85$$ both encipher to $$25$$. This means we can't even reversibly encipher the uppercase ASCII alphabet. If we try to use $$c\mapsto c^d\bmod n$$ for $$d=e^{-1}\bmod\varphi(n)$$ as a decryption function, it will sometime fail. For example, $$m_R=82$$ enciphers to $$c=32$$ and deciphers to $$32\ne m_R$$.

• so can I use An encoding such that the values of letters and n (here 100) has no common factors>1 @fgrieu – SANTHOS KUMAR Jan 27 at 12:20
• @sumar: indeed, that will work. In fact, it is enough to restrict to messages $m=0$ or $m\in[1,n)$ such that $m$ and $n$ have no common factor which square divides $n$. For $n=300$ that allows $m$ to be $0$, $3$, $9$, $21$, $27$, $33$.. – fgrieu Jan 27 at 14:48