前面我介紹了一些數論知識。 有了這些知識，我們就可以看懂RSA算法。這是目前地球上最重要的加密算法。 我們通過一個例子，來理解RSA算法。假設[愛麗絲](http://zh.wikipedia.org/wiki/%E7%88%B1%E4%B8%BD%E4%B8%9D%E4%B8%8E%E9%B2%8D%E4%BC%AF)要與鮑勃進行加密通信，她該怎么生成公鑰和私鑰呢？  第一步，隨機選擇兩個不相等的質數p和q。 愛麗絲選擇了61和53。（實際應用中，這兩個質數越大，就越難破解。） 第二步，計算p和q的乘積n。 愛麗絲就把61和53相乘。 > 　　n = 61×53 = 3233 n的長度就是密鑰長度。3233寫成二進制是110010100001，一共有12位，所以這個密鑰就是12位。實際應用中，RSA密鑰一般是1024位，重要場合則為2048位。 第三步，計算n的歐拉函數φ(n)。 根據公式： > 　　φ(n) = (p-1)(q-1) 愛麗絲算出φ(3233)等于60×52，即3120。 第四步，隨機選擇一個整數e，條件是1 愛麗絲就在1到3120之間，隨機選擇了17。（實際應用中，常常選擇65537。） 第五步，計算e對于φ(n)的模反元素d。 所謂["模反元素"](http://zh.wikipedia.org/wiki/%E6%A8%A1%E5%8F%8D%E5%85%83%E7%B4%A0)就是指有一個整數d，可以使得ed被φ(n)除的余數為1。 > 　　ed ≡ 1 (mod φ(n)) 這個式子等價于 > 　　ed - 1 = kφ(n) 于是，找到模反元素d，實質上就是對下面這個二元一次方程求解。 > 　　ex + φ(n)y = 1 已知 e=17, φ(n)=3120， > 　　17x + 3120y = 1 這個方程可以用["擴展歐幾里得算法"](http://zh.wikipedia.org/wiki/%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95)求解，此處省略具體過程。總之，愛麗絲算出一組整數解為 (x,y)=(2753,-15)，即 d=2753。 至此所有計算完成。 第六步，將n和e封裝成公鑰，n和d封裝成私鑰。 在愛麗絲的例子中，n=3233，e=17，d=2753，所以公鑰就是 (3233,17)，私鑰就是（3233, 2753）。 實際應用中，公鑰和私鑰的數據都采用[ASN.1](http://zh.wikipedia.org/zh-cn/ASN.1)格式表達（[實例](http://hi.baidu.com/mathack/item/d0ad4cc1514a3663f7c95da2)）。