0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – kelalaka Jan 26 at 19:55
  • $\begingroup$ @kelalaka: what you propose won't work. $\endgroup$ – fgrieu Jan 26 at 20:01
  • $\begingroup$ @fgrieu well, I think it is not about the functionality it is about security, right? $\endgroup$ – kelalaka Jan 26 at 20:16
  • 1
    $\begingroup$ @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. $\endgroup$ – fgrieu Jan 26 at 21:35
  • $\begingroup$ @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? $\endgroup$ – SANTHOS KUMAR Jan 27 at 9:23
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ so can I use An encoding such that the values of letters and n (here 100) has no common factors>1 @fgrieu $\endgroup$ – SANTHOS KUMAR Jan 27 at 12:20
  • $\begingroup$ @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$.. $\endgroup$ – fgrieu Jan 27 at 14:48

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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