I am implementing a protocol for authentication where parameters need to be selected with $gcd(\mu,\phi)=1$ where $\phi=(p−1)(q−1)$. What is the best way to select the parameters while implementing
$\begingroup$
$\endgroup$
4
-
$\begingroup$ In the context, do you know $\phi$? If yes, one way could be to select (odd) $\mu$ at random until $\gcd(\mu,\phi)=1$ is satisfied. Or if that fits, just $\mu=1$. $\endgroup$– fgrieu ♦Dec 28, 2013 at 16:45
-
$\begingroup$ Random is the accepted method? Whether RSA uses random method? $\endgroup$– user5507Dec 28, 2013 at 16:49
-
$\begingroup$ When there is nothing else specified, random can be an accepted method. In particular, it is fine to choose an RSA exponent at random that is coprime with $\phi=(p−1)(q−1)$. If that needs to be done for unknown $\phi$, one option is to select primes $p$ and $q$ of same bit size such that $(p-1)/2$ and $(q-1)/2$ are primes, making an overwhelming majority of odd $\mu$ with $3\le\mu<N-3\sqrt N$ suitable. $\endgroup$– fgrieu ♦Dec 28, 2013 at 17:00
-
$\begingroup$ @fgrieu, would you mind answering this question so it can get off our "unanswered questions" statistique? $\endgroup$– SEJPMJun 28, 2015 at 18:51
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I'll first assume $\phi$ is known, which would be the situation in RSA at key selection.
A common method could be to select (odd) $\mu$ at random in some appropriate interval until $\gcd(\mu,\phi)=1$ is satisfied. In the context of RSA, it is fine (if we ignore performance an interoperability issues) to choose an RSA exponent at random in $[3\dots\phi-3]$ that is coprime with $\phi=(p−1)(q−1)$.
Another option would to restrict to prime $\mu$, which increases the odds that $\gcd(\mu,\phi)=1$: for random choice of large primes $p$ and $q$, a moderate prime $\mu$ has odds $({\mu-2\over\mu-1})^2$ to be acceptable. For example, $\mu=65537$ (the most common choice for RSA) would likely be fine.
When candidates for $\mu$ are examined in prescribed order, from the choice of $\mu$ a little information leaks about $\phi$; this is usually a non-issue.
If we somewhat must arrange that $\mu$ be chosen without knowledge of $\phi=(p-1)\cdot(q-1)$, one option is to select distinct primes $p$ and $q$ of some bit size $b$ such that $(p−1)/2$ and $(q−1)/2$ are primes; in this way, any odd $\mu$ less than $b-1$ bits verifies $\gcd(\mu,\phi)=1$.
