六、密鑰生成的步驟

前面我介紹了一些數(shù)論知識。
有了這些知識，我們就可以看懂RSA算法。這是目前地球上最重要的加密算法。

我們通過一個例子，來理解RSA算法。假設(shè)愛麗絲要與鮑勃進行加密通信，她該怎么生成公鑰和私鑰呢？

第一步，隨機選擇兩個不相等的質(zhì)數(shù)p和q。

愛麗絲選擇了61和53。（實際應(yīng)用中，這兩個質(zhì)數(shù)越大，就越難破解。）

第二步，計算p和q的乘積n。

愛麗絲就把61和53相乘。

　　n = 61×53 = 3233

n的長度就是密鑰長度。3233寫成二進制是110010100001，一共有12位，所以這個密鑰就是12位。實際應(yīng)用中，RSA密鑰一般是1024位，重要場合則為2048位。

第三步，計算n的歐拉函數(shù)φ(n)。

根據(jù)公式：

　　φ(n) = (p-1)(q-1)

愛麗絲算出φ(3233)等于60×52，即3120。

第四步，隨機選擇一個整數(shù)e，條件是1

愛麗絲就在1到3120之間，隨機選擇了17。（實際應(yīng)用中，常常選擇65537。）

第五步，計算e對于φ(n)的模反元素d。

所謂"模反元素"就是指有一個整數(shù)d，可以使得ed被φ(n)除的余數(shù)為1。

　　ed ≡ 1 (mod φ(n))

這個式子等價于

　　ed - 1 = kφ(n)

于是，找到模反元素d，實質(zhì)上就是對下面這個二元一次方程求解。

　　ex + φ(n)y = 1

已知 e=17, φ(n)=3120，

　　17x + 3120y = 1

這個方程可以用"擴展歐幾里得算法"求解，此處省略具體過程。總之，愛麗絲算出一組整數(shù)解為 (x,y)=(2753,-15)，即 d=2753。

至此所有計算完成。

第六步，將n和e封裝成公鑰，n和d封裝成私鑰。

在愛麗絲的例子中，n=3233，e=17，d=2753，所以公鑰就是 (3233,17)，私鑰就是（3233, 2753）。

實際應(yīng)用中，公鑰和私鑰的數(shù)據(jù)都采用ASN.1格式表達（實例）。