Skip to main content
Cryptography

Return to Answer

added 173 characters in body
Source Link
user25578
user25578

$\varphi(n)$ is a multiplicative function: it is computed by the formula

$$ \varphi(n) = n \prod_{p \mid n} \frac{p-1}{p} $$

or something equivalent. This is basically the only method of computation known that remains feasible when $n$ is not small.

Thus, if $N$ is the modulus you want to use for RSA, you need to know its prime factorization so that you can compute $\varphi(N)$. And you don't want anyone else to know it's prime factorization, otherwise they could compute $\varphi(N)$.

Also, note that $N=pq$ is not chosen because that's what RSA needs to work:all RSA just needscares about is that it has some $N$ and $\varphi(N)$. We chooseThe only reason we talk about $p$ and $q$ is because choosing $N=pq$ because it is the best way to satisfy the previous paragraph.

$\varphi(n)$ is a multiplicative function: it is computed by the formula

$$ \varphi(n) = n \prod_{p \mid n} \frac{p-1}{p} $$

or something equivalent. This is basically the only method of computation known that remains feasible when $n$ is not small.

Thus, if $N$ is the modulus you want to use for RSA, you need to know its prime factorization so that you can compute $\varphi(N)$. And you don't want anyone else to know it's prime factorization, otherwise they could compute $\varphi(N)$.

Also, note that $N=pq$ is not chosen because that's what RSA needs to work: RSA just needs $N$ and $\varphi(N)$. We choose $N=pq$ because it is the best way to satisfy the previous paragraph.

$\varphi(n)$ is a multiplicative function: it is computed by the formula

$$ \varphi(n) = n \prod_{p \mid n} \frac{p-1}{p} $$

or something equivalent. This is basically the only method of computation known that remains feasible when $n$ is not small.

Thus, if $N$ is the modulus you want to use for RSA, you need to know its prime factorization so that you can compute $\varphi(N)$. And you don't want anyone else to know it's prime factorization, otherwise they could compute $\varphi(N)$.

Also, all RSA cares about is that it has some $N$ and $\varphi(N)$. The only reason we talk about $p$ and $q$ is because choosing $N=pq$ because it is the best way to satisfy the previous paragraph.

added 173 characters in body
Source Link
user25578
user25578

$\varphi(n)$ is a multiplicative function: it is computed by the formula

$$ \varphi(n) = n \prod_{p \mid n} \frac{p-1}{p} $$

or something equivalent. This is basically the only method of computation known that remains feasible when $n$ is not small.

Thus, if $N$ is the modulus you want to use for RSA, you need to know its prime factorization so that you can compute $\varphi(N)$. And you don't want anyone else to know it's prime factorization, otherwise they could compute $\varphi(N)$.

Also, note that $N=pq$ is not chosen because that's what RSA needs to work: RSA just needs $N$ and $\varphi(N)$. We choose $N=pq$ because it is the best way to satisfy the previous paragraph.

$\varphi(n)$ is a multiplicative function: it is computed by the formula

$$ \varphi(n) = n \prod_{p \mid n} \frac{p-1}{p} $$

or something equivalent. This is basically the only method of computation known that remains feasible when $n$ is not small.

Thus, if $N$ is the modulus you want to use for RSA, you need to know its prime factorization so that you can compute $\varphi(N)$. And you don't want anyone else to know it's prime factorization, otherwise they could compute $\varphi(N)$.

$\varphi(n)$ is a multiplicative function: it is computed by the formula

$$ \varphi(n) = n \prod_{p \mid n} \frac{p-1}{p} $$

or something equivalent. This is basically the only method of computation known that remains feasible when $n$ is not small.

Thus, if $N$ is the modulus you want to use for RSA, you need to know its prime factorization so that you can compute $\varphi(N)$. And you don't want anyone else to know it's prime factorization, otherwise they could compute $\varphi(N)$.

Also, note that $N=pq$ is not chosen because that's what RSA needs to work: RSA just needs $N$ and $\varphi(N)$. We choose $N=pq$ because it is the best way to satisfy the previous paragraph.

Source Link
user25578
user25578

$\varphi(n)$ is a multiplicative function: it is computed by the formula

$$ \varphi(n) = n \prod_{p \mid n} \frac{p-1}{p} $$

or something equivalent. This is basically the only method of computation known that remains feasible when $n$ is not small.

Thus, if $N$ is the modulus you want to use for RSA, you need to know its prime factorization so that you can compute $\varphi(N)$. And you don't want anyone else to know it's prime factorization, otherwise they could compute $\varphi(N)$.