% RSA tshirt design % by Tom Strong (ts49@andrew.cmu.edu) % with technical assistance from Will Frank (wf08@andrew.cmu.edu) % It's LaTeX, not TeX, dammit. \documentstyle[12pt]{article} \begin{document} \pagestyle{empty} \begin{center} { \Large In the beginning man wished to communicate with his fellow man. And the governments desired to know what the man had to say to his fellow man; and thus they did eavesdrop upon him. And unless the man did exchange a secret key with his fellow man, he had no privacy, and this was not good. And Rivest and Shamir and Adelman said, \vskip 3ex Given $ s \in \aleph, $ choose $ M \in \aleph $ s.t. $ M \le s $ Select primes $ p , q $ s.t. $ p * q > s $ Select $ d \in \aleph $ s.t. $ { \rm gcd } ( d, ( p - 1 ) * ( q - 1 ) ) = 1 $ Compute $ e \in \aleph $ s.t. $ e * d \equiv 1 ( { \rm mod \ } ( p - 1 ) * ( q - 1 ) ) $ Let $ n = p * q $ Make $ ( e , n ) $ public Define $ C , E ( M ) $ and $ D ( C ) $ to be: $ C \equiv E ( M ) \equiv M ^ e ( { \rm mod \ } n ) $ \& $ D ( C ) \equiv C ^ d ( { \rm mod \ } n ) $ Therefore: $ M = D ( E ( M ) ) $ \vskip 3ex And there was privacy. } \end{center} \newpage $ D ( E ( M ) ) = M $ \hfill (1) \hfill $ E ( D ( M ) ) = M $ \hfill (2) We demonstrate the correctness of the deciphering algorithm using an identity due to Euler and Fermat: for any integer (message) $ M $ which is relatively prime to $ n $, $ M ^ { \varphi ( n ) } \equiv 1 ( { \rm mod \ } n ) $ \hfill (3) Here $ \varphi ( n ) $ is the Euler totient function giving the number of positive integers less than $ n $ which are relatively prime to $ n $ . For Prime numbers $ p $, $ \varphi ( p ) = p - 1 $. In our case, we have by elementary properties of the totient function: $ \varphi ( n ) = \varphi ( p ) * \varphi ( q ) = ( p - 1 ) * ( q - 1 ) = n - ( p + q ) + 1 $ \hfill (4) Since $ d $ is relatively prime to $ \varphi ( n ) $, it has a multiplicative inverse $ e $ in the ring of integers modulo $ \varphi ( n ) $ : $ e * d \equiv 1 ( { \rm mod \ } \varphi ( n ) ) $ \hfill (5) We now prove that equations (1) and (2) hold (that is, that deciphering works correctly if $ e $ and $ d $ are chosen as above). Now $ D ( E ( M ) ) \equiv ( E ( M ) ) ^ d \equiv ( M ^ e ) ^ d \equiv M ^ { e * d } ( { \rm mod \ } n ) $ $ E ( D ( M ) ) \equiv ( D ( M ) ) ^ e \equiv ( M ^ d ) ^ e \equiv M ^ { e * d } ( { \rm mod \ } n ) $ and $ M ^ { e * d } \equiv M ^ { k * \varphi ( n ) + 1 } ( { \rm mod \ } n ) $ ( for some integer $ k $ ) From (3) we see that for all $ M $ such that $ p $ does not divide $ M $ $ M ^ { p - 1 } \equiv 1 ( { \rm mod \ } p ) $ and since $ ( p - 1 ) $ divides $ \varphi ( n ) $ $ M ^ { k * \varphi ( n ) + 1 } ( { \rm mod \ } n ) \equiv M ( { \rm mod \ } p ) $. This is trivially true when $ M = 0 ( { \rm mod \ } p ) $ , so that this equality actually holds for {\em all} $ M $. Arguing similarly for $ q $ yields $ M ^ { k * \varphi ( n ) + 1 } ( { \rm mod \ } n ) \equiv M ( { \rm mod \ } q ) $. Together these last two equations imply that for all $ M $, $ M ^ { e * d } \equiv M ^ { k * \varphi ( n ) + 1 } \equiv M ( { \rm mod \ } n ) $. This implies (1) and (2) for all $ M, 0 \le M < n $. Therefore $ E $ and $ D $ are reverse permutations. \begin{center} \small Rivest, Shamir and Adelman, CACM, Feb 1978, p.123 \end{center} \end{document}