Skip to main content
Cryptography

Return to Answer

added 31 characters in body
Source Link
rranjik
rranjik
  • 217
  • 2
  • 8

I had the same question and so I landed here. RSA has two key properties

  1. The mapping $m \to m^e (mod\ N)$ is a bijection
  2. The inverse mapping $(m^e)^d \equiv m\ (mod\ N) $ is easy to compute (given $p$ and $q$ of course)

From what I read, the proof of working (of these two properties of RSA) assumes that $p$ and $q$ primes. So I worked on a few examples that violate this property and I found that it has, in my opinion, a more serious problem.

While all the answers focus on the practical aspect that it is harder for the encrypting party to compute the $totient$ of a large composite number that it chose, I think, allowing $p$ and $q$ to be composite has a fundamental problem that the encryption will lose its bijective property (decryption becomes ambiguous).

For example, if we let $p = 8$ and $q = 9$, then $N = 72$. $\phi(72) = 24$. A possible $e$ is $5$. With this public key $(N, e) = (72, 5)$, there is no bijection. Consider a message $m = 4$, upon encryption, it becomes $16$ while a message $m = 22$ also becomes $16$. ($m = 58,\ 40$ also become $16$ upon encryption).

I don't have a proof of this and I'm also to new to this theory. I would appreciate any suggestions and improvements.

I had the same question and so I landed here. RSA has two key properties

  1. The mapping $m \to m^e (mod\ N)$ is a bijection
  2. The inverse mapping $(m^e)^d \equiv m\ (mod\ N) $ is easy to compute (given $p$ and $q$ of course)

From what I read, the proof of working (of these two properties of RSA) assumes that $p$ and $q$ primes. So I worked on a few examples that violate this property and I found that it has, in my opinion, a more serious problem.

While all the answers focus on the practical aspect that it is harder for the encrypting party to compute the $totient$ of a large composite number that it chose, I think, allowing $p$ and $q$ to be composite has a fundamental problem that the encryption will lose its bijective property.

For example, if we let $p = 8$ and $q = 9$, then $N = 72$. $\phi(72) = 24$. A possible $e$ is $5$. With this public key $(N, e) = (72, 5)$, there is no bijection. Consider a message $m = 4$, upon encryption, it becomes $16$ while a message $m = 22$ also becomes $16$. ($m = 58,\ 40$ also become $16$ upon encryption).

I don't have a proof of this and I'm also to new to this theory. I would appreciate any suggestions and improvements.

I had the same question and so I landed here. RSA has two key properties

  1. The mapping $m \to m^e (mod\ N)$ is a bijection
  2. The inverse mapping $(m^e)^d \equiv m\ (mod\ N) $ is easy to compute (given $p$ and $q$ of course)

From what I read, the proof of working (of these two properties of RSA) assumes that $p$ and $q$ primes. So I worked on a few examples that violate this property and I found that it has, in my opinion, a more serious problem.

While all the answers focus on the practical aspect that it is harder for the encrypting party to compute the $totient$ of a large composite number that it chose, I think, allowing $p$ and $q$ to be composite has a fundamental problem that the encryption will lose its bijective property (decryption becomes ambiguous).

For example, if we let $p = 8$ and $q = 9$, then $N = 72$. $\phi(72) = 24$. A possible $e$ is $5$. With this public key $(N, e) = (72, 5)$, there is no bijection. Consider a message $m = 4$, upon encryption, it becomes $16$ while a message $m = 22$ also becomes $16$. ($m = 58,\ 40$ also become $16$ upon encryption).

I don't have a proof of this and I'm also to new to this theory. I would appreciate any suggestions and improvements.

Source Link
rranjik
rranjik
  • 217
  • 2
  • 8

I had the same question and so I landed here. RSA has two key properties

  1. The mapping $m \to m^e (mod\ N)$ is a bijection
  2. The inverse mapping $(m^e)^d \equiv m\ (mod\ N) $ is easy to compute (given $p$ and $q$ of course)

From what I read, the proof of working (of these two properties of RSA) assumes that $p$ and $q$ primes. So I worked on a few examples that violate this property and I found that it has, in my opinion, a more serious problem.

While all the answers focus on the practical aspect that it is harder for the encrypting party to compute the $totient$ of a large composite number that it chose, I think, allowing $p$ and $q$ to be composite has a fundamental problem that the encryption will lose its bijective property.

For example, if we let $p = 8$ and $q = 9$, then $N = 72$. $\phi(72) = 24$. A possible $e$ is $5$. With this public key $(N, e) = (72, 5)$, there is no bijection. Consider a message $m = 4$, upon encryption, it becomes $16$ while a message $m = 22$ also becomes $16$. ($m = 58,\ 40$ also become $16$ upon encryption).

I don't have a proof of this and I'm also to new to this theory. I would appreciate any suggestions and improvements.