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?

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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