RSA and number of decryption exponents

May 2010
7
0
We must prove that in the RSA cryptographic system for the primes \(\displaystyle p, q\) and the encryption exponent \(\displaystyle e\bot\phi(pq)\) in set \(\displaystyle \{0,\dots,\phi(pq)-1\}\) is exactly \(\displaystyle gcd(p-1,q-1)\) elements that
you can use as the decryption exponent \(\displaystyle d\).
(That is for every \(\displaystyle M\in\{0,\dots,pq-1\}\), after encryption \(\displaystyle M\) using encryption exponent \(\displaystyle e\), and then by using the decryption exponent \(\displaystyle d\) we get back the \(\displaystyle M\)).

Thank you for all helpful answers. (Wink)
 
May 2010
7
0
I forgot to say that what \(\displaystyle \phi\) means. (Itwasntme)
\(\displaystyle \phi(n)=|\{1\leq k\leq n : k\bot n \}|\)
In this situation (\(\displaystyle p,q\)-primes) we have:
\(\displaystyle \phi(pq)=(p-1)(q-1)\)