选取两个大质数p和q。算出n=pq。算出φ(n)=(p-1)(q-1)。找一个数小于φ(n)的数e，使得e与φ(n)互质。n和e就可以作为公钥公开了。假设明文m是一个小于n的数。只要拥有公钥n和e，任何人都可以根据公式c=m^e mod n算出密文c（可以二分加速）。但是呢，你会发现你解不回去了……因为只知道n、e和c，你是不能反过来求出m的。
那我们该怎么算m的值呢？只需要求出一个满足ed≡1 (mod φ(n))的d后，我们就可以直接用公式m=c^d mod n求得明文。利用扩展的辗转相除，我们可以很容易求出满足要求的d。但是φ(n)的值只有我才知道，别人是不知道的（如果想要破解出来必须得把n分解成p 和q），因此这个d值就是一个只有我自己才知道的解密钥匙。下面我们来说明上述解密算法的正确性。由于ed-1能被(p-1)(q-1)整除，它必然也能被(p-1)整除，因此m^ed可以表示成m^(k(p-1)+1)，其中k是某个适当的整数。现在，假设m是p的倍数，那直接就有 m^(ed)≡0^(ed)≡0≡m (mod p)；否则，m和p一定互质，根据Fermat小定理有m^(p-1)≡1(mod p)，于是m^(ed) = m^(k(p-1)+1) = [m^(p-1)]^k * m ≡ 1^k * m ≡ m (mod p)。同理，当模数为q时也总有m^(ed)≡m。既然p整除m^(ed)-m，q也整除m^(ed)-m，并且p和q都是质数，那么一定有 m^(ed)≡m (mod pq)，即m^(ed)≡m (mod n)。这个m^(ed)就等于我们前面的c^d。
数字签名还有一些其它的特殊变化。考虑这样一种情况，我有一份秘密文件需要签名，但我不希望签名者看到这份文件的内容。这种看似很不合理的情况确有发生。例如在证人保护计划中，我是一个特工，我需要保护一个非常可爱的无辜小MM。为了把她安置到一个偏远的安全地，我需要让上级签署各种通行证明文件；但为了安全起见，我不希望把安全地的位置泄露给任何人。为此，我希望我的上级对文件进行签名，但保证他们完全不知道文件内容是什么。满足这种要求的签名协议叫做“盲签名”。为了得到一种“盲签名”算法，考虑用RSA进行签名的本质：假设待签名的文本为（不超过模数n的）t，则我们实质上希望得到t^d mod n，其中n是模数，d是签名者的私人钥匙。我们的目的是，对文本t进行干扰（例如在t上面加一个大数，或者乘一个大数，或者取t的倒数的正弦值的-π次方的自然对数），让签名者不知道t是什么；但签名者签名之后，我们还能除去刚才的干扰因子，还原为t^d mod n。因此，我们需要想一个奇妙的办法，让被干扰的文本签名后，干扰因子头上的“d”正好消失了。回忆之前讲过的结论m^(ed)≡m (mod n)，我们立即想到了盲签名算法：我把明文t乘上一个随机数k的e次方（e是公开钥匙），把t*(k^e)传给签名人。注意我们选取的k一定要与n互质，否则k是大质数p或q的倍数，“干扰”的结果必然为0。这下，签名人当然不可能知道t是什么，因为他不知道随机数k是多少。他对t*(k^e)进行签名，传回来的结果即为t^d * k^(ed) mod n。但k^(ed)模n就等于k，于是这个签名结果实际上就是t^d * k mod n。现在，我只需要把该结果除以只有我才知道的k（即乘以它在模n剩余类环中的逆元，这个逆元保证存在，因为k和n互质），即得到了我需要的签名文件 t^d mod n。
