I have a two set of key {36,77} and {50,117},
How can validate if it is a valid RSA public keys? Is there any simple method?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Do you only have the public key, or do you know the factorization of n? In your examples n is so small that factoring is trivial. $\endgroup$ – CodesInChaos Aug 1 '12 at 18:32
Add a comment
|
$\begingroup$
$\endgroup$
4
That depends on exactly what you mean by a "valid RSA public key"; in general, it is difficult to validate a public key without the corresponding private key (unless the public key is obviously bad).
If you mean that there is a corresponding private key $d$ such that $(M^e)^d = M \mod N$ for all messages $M$, then there are two conditions; if both are met, then there will always be such a $d$:
$e$ is relatively prime to $\phi(N)$; if $N$ has k distinct prime factors $p_1$, $p_2$, ..., $p_k$ then $\phi(N) = (p_1-1)(p_2-1)...(p_k-1)$
$N$ is squarefree; that is, there is no integer $n > 1$ such that $n^2$ is a divisor of $N$. Or, in other words, all the prime factors of $N$ must be distinct.
Note that there are varients of RSA for which a public key might not meet these assumptions; they deal with the fact that $M^e$ might not have a unique inverse in various ways.
As for how to determine whether a public key meets these criteria, well, neither critieria is feasible to verify for a large key. On the other hand, it is easy to note by inspection that your examples do not; they both have an even value of $e$, and even numbers are never relatively prime to $\phi(N)$ (which is also even). In addition, your second example has $N=117$, which is not square-free (as it has a divisor of $3^2$).
On the other hand, a "valid RSA public key" might mean a key that meets the above constraints, and is secure. This implies that $e>1$ (easy to validate), and $N$ is hard to factor. If $N$ is large enough to be not easily factored, this also is hard to validate.
Thirdly, by a "valid RSA public key", you might mean "all of the above, and in addition, someone knows the private key". The only way you can accertain that is to work with the person who is supposed to know the private key (and, for example, have a Zero Knowledge Proof that they do indeed know the factorization of $N$).
-
$\begingroup$ thx for your answer. i didn't get what this mean "e is relatively prime to ϕ(N)" can you illustrate by a simple example? $\endgroup$ – Kit Ho Aug 2 '12 at 2:01
-
$\begingroup$ @KitHo: well, let us consider the modulus from your first example, 77. $\phi(77) = (7-1)(11-1) = 60$. If e is not relatively prime to 60 (that is, is divisible by either 2, 3 or 5, the prime factors of 60), then the operation $M^e \mod 77$ will have collisions, and hence not be invertible. For example, if $e=36$ (which has both 2 and 3 as factors), then we see that $5^{36} \mod 77 = 6^{36} \mod 77 = 71$, and hence if we get an encrypted message of 71, we cannot determine if 5 or 6 (or a number of other values) was the original message. $\endgroup$ – poncho Aug 2 '12 at 2:23
-
$\begingroup$ that's cool! spending some time, finally understand what do you mean, may i have one more follow up, why Euler toient function of N, must be even number? $\endgroup$ – Kit Ho Aug 4 '12 at 6:46
-
1$\begingroup$ @KitHo: well, if N is not a power of two, then $\phi(N)$ will be even, because $N$ will then have an odd prime factor $p$, and so $\phi(N)$ will be divisible by $p-1$, and $p-1$ is even. $\endgroup$ – poncho Aug 4 '12 at 14:02
