【正文】 將對涉及到的數(shù)學(xué)知識，進行部分重點介紹。 Fermat 定理與 Euler 定理前面簡單的介紹了一下模同余以及模 n 剩余類和完全剩余系的概念，根據(jù)這些定義和性質(zhì)，可以進一步引出 Euler 函數(shù)、Euler 定理以及 Fermat 定理。Fermat 定理：設(shè) n 為素數(shù)，且 ，則 ；(,)1a?(1)modna??Euler 函數(shù) [26]：設(shè) n 是一個正整數(shù)，則 n 個整數(shù) 0，1，…，n1 中與 n 互素的整數(shù)的個數(shù)，記作 ?(n)；Euler 定理：用一個函數(shù) f(m)，它表示小于 m 的正整數(shù)中有多少個數(shù)和 m 互素（兩個數(shù)只有公約數(shù) 1 稱為互素） 。為了方便，我們通常用記號 φ(m)來表示這個函數(shù)（即 Euler 函數(shù)） 。Euler 指出，如果 a 和 m 互素，那么 aφ(m) ≡ 1 (mod m)?？梢钥吹?，當(dāng) m 為素數(shù)時，φ(m)就等于 m1（所有小于 m 的正整數(shù)都與 m 互素） ，因此它是Fermat 小定理的推廣。定理的證明和 Fermat 小定理幾乎相同。根據(jù)上節(jié)既約剩余系的定義， 即為模 n 的既約剩余系中所有元素的個數(shù)。關(guān)于 Euler 函數(shù)，有以下幾個()?性質(zhì)：(1) 若 p 是素數(shù)，則 反之亦成立，即若 p 為合數(shù)，則有 ；()2p??()2np???(2) 若 p 是素數(shù)，k 是任一正整數(shù)，則 ；12()()m??(3) 若 且 ，則有 ；12m?12(,)?結(jié)合既約剩余系與 Euler 函數(shù)的概念，可以得出既約剩余系的一個性質(zhì)如下：令{， ，…， }為模 n 的一個既約剩余系。若 則{ ， ，…， }也1r2()nr? (,)1an?r2a()nr?為模 n 的一個既約剩余系。根據(jù)上述性質(zhì)，我們可以進一步總結(jié)出 Euler 定理：若 ，則 。(,)()1modn? MillerRabin 素數(shù)檢測算法素數(shù)是整數(shù)中乘法運算的最小單位，在 RSA 公鑰密碼體制研究起著重要的作用，因此素數(shù)的生成也很重要。 第 23 頁 共 47 頁很長一段時間里，人們都認為 Fermat 小定理的逆命題是正確的，并且有人親自驗證了 a=2, p300 的所有情況。直到 1819 年有人發(fā)現(xiàn)了 Fermat 小定理逆命題的第一個反例：雖然 2 的 340 次方除以 341 余 1，但 341=11*31。后來，人們又發(fā)現(xiàn)了 561, 645, 1105 等數(shù)都表明 a=2 時 Fermat 小定理的逆命題不成立。雖然這樣的數(shù)不多，但不能忽視它們的存在。于是，人們把所有能整除 2(n1)1 的合數(shù) n 叫做偽素數(shù)(pseudoprime) ，意思就是告訴人們這個素數(shù)是假的。二次探測定理：如果 p 是一個素數(shù)，0xp,則方程 的解為 x=1 或 p21(mod)xp?1。生成素數(shù)的一般方法是先隨機生成一個整數(shù)，然后根據(jù)算法進行判斷該數(shù)是否為素數(shù)。下面介紹基于 Fermat 定理和二次探測定理的 MillerRabin 素數(shù)檢測算法。設(shè)待測數(shù) n2 是一個奇數(shù)，一定可以寫成 的形式，其中 k 是非負整數(shù)，12knm??m0 是奇數(shù)。設(shè) 0bn。如果 ，或者存在一個 r (0 r k)使得1(od)mb?，則稱 n 通過以 b 為基 MillerRabin 的檢測。21(mod)rb??MillerRabin 素數(shù)檢測算法并不是一個確定的算法。若 n 是奇合數(shù)，則 n 通過以 a為基的 MillerRabin 素數(shù)檢測算法測試的數(shù)目最多為 。若選 k 個數(shù)作為基為基的(1)4?MillerRabin 素數(shù)檢測算法進行測試，若 n 是合數(shù)， k 次測試全部通過是概率為 。14()k若取 k = 100，則 n 為合數(shù)，且通過測試的概率就很小很小了 [27]。 歐氏算法歐幾里德（Euclidean ）算法又稱 輾轉(zhuǎn)相除法，用于計算兩個正整數(shù) a，b 的最大公約數(shù)。歐幾里德定理：gcd(a,b) = gcd(b,a mod b) (ab 且 a mod b 不為 0)。 利用歐幾里德算來確定兩個正整數(shù) a 和 b 的最大公因子可總結(jié)為： (1) 若 r 是 a 247。 b 的余數(shù),且 r 不為 0， 則 gcd(a,b) = gcd(b,r) ；(2) a 和其倍數(shù)之最大公因子為 a ；另一種寫法是：(1) 令 r 為 a/b 所得余數(shù)（0≤rb ）若 r= 0，算法結(jié)束； b 即為答案；(2) 互換：置 a←b ，b←r ，并返回第一步；擴展歐幾里德算法是用來在已知 a, b 求解一組 x， y 使得 ax+by = gcd(a, b) =d(解一 第 24 頁 共 47 頁定存在，根據(jù)數(shù)論中的相關(guān)定理)。擴展歐幾里德常用在求解模線性方程及方程組中。擴展歐幾里德定理：對于不完全為 0 的非負整數(shù) a，b，gcd（a ，b）表示 a，b 的最大公約數(shù)，必然存在整數(shù)對 x，y ，使得 gcd（a，b）=ax+by。對于求解 x，y 的方法的理解可總結(jié)為(設(shè) ab)：(1) 顯然當(dāng) b=0，gcd （a，b）=a 。此時 x=1，y=0； (2) ab！=0 時，設(shè) ax1+by1=gcd(a,b)。 (3) bx2+(a mod b)y2=gcd(b,a mod b)。 (4) 根據(jù)樸素的歐幾里德原理有 gcd(a,b)=gcd(b,a mod b)。 (5) 則:ax1+by1=bx2+(a mod b)y2。 (6) 即:ax1+by1=bx2+(a(a/b)*b)y2=ay2+bx2(a/b)*by2。 (7) 根據(jù)恒等定理得：x1=y2。 y1=x2(a/b)*y2。 這樣我們就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2. 上面的思想是以遞歸定義的，因為 gcd 不斷的遞歸求解一定會有個時候 b=0，所以遞歸可以結(jié)束。 SHA1 算法分析SHA1 對明文的處理和 MD5 相同，可以對長度不超過 2^64 比特的消息進行計算，輸入以 512 位數(shù)據(jù)塊為單位處理，產(chǎn)生 160 比特的消息摘要作為輸出。首先對輸入的數(shù)據(jù)進行填充，使得數(shù)據(jù)位長度對 512 求余的結(jié)果為 448。填充比特串的最高位補一個1，其余位補 0。附加填充總是要進行的，即使消息的長度滿足所要求的長度。然后將64 比特加在報文后表示報文的原始長度，使報文長度為 512 比特的倍數(shù)。填充完畢后，明文被按照 512bits 分組(Block)。另外 SHA 還有四種變體, 由美國國家標準與技術(shù)研究院 (NIST)發(fā)布以提升輸出的范圍和變更一些細微設(shè)計: SHA224, SHA256, SHA384 和 SHA512 (這些有時候也被稱做 SHA2)。下表 給出 SHA 家族的部分參數(shù)：表 SHA 家族參數(shù)算法 消息長度 2^(bits)分組長度(bites)字長(bits)消息摘要長度(bits)安全性 2^(bits)SHA1 64 512 32 160 80SHA256 64 512 32 256 128SHA384 128 1024 64 384 192SHA512 128 1024 64 512 256SHA1操 作 的 循 環(huán) 次 數(shù) 為 明 文 的 分 組 數(shù) ， 對 每 一 個 明 文 分 組 的 操 作 有 4 輪 ， 每 輪 20 第 25 頁 共 47 頁個 步 驟 共 80個 步 驟 。 每 一 步 操 作 對 5個 32bits 的 寄 存 器 (記 錄 單 元 )進 行 。 這 5個 工 作變 量 (記 錄 單 元 、 鏈 接 變 量 )的 給 定 初 始 值 為 : 0674201Hx?89Hxefcda?2098Hxbadcfe? 35431SHA1 中 使 用 了 一 組 邏 輯 函 數(shù) ft(t 表 示 操 作 的 步 驟 數(shù) ， 0≤ t≤ 79)。 每 個 邏 輯 函 數(shù)均 對 三 個 32bits 的 變 量 B、 C、 D 進 行 操 作 ， 產(chǎn) 生 一 個 32bits 的 輸 出 。 邏 輯 函 數(shù) ft(B,C,D)定 義 如 下 ：ft(B,C,D) = (B and C) or(not(B) and D) ( 0≤ t≤ 19) ft(B,C,D) = B xor C xor D (20≤ t≤ 39) ft(B,C,D) = (B and C) or (B and D) or (C and D) (40≤ t≤ 59) ft(B,C,D) = B xor C xor D (60≤ t≤ 79)SHA1 中 同 時 用 到 了 一 組 常 數(shù) K t(t 表 示 操 作 的 步 驟 數(shù) ， 0≤ t≤ 79)， 每 個 步 驟 使用 一 個 。 這 一 組 常 數(shù) 的 定 義 為 ：Kt =0x5A827999( 0≤ t≤ 19) Kt =0x6ED9EBA1(20≤ t≤ 39)Kt =0x8F1BBCDC(40≤ t≤ 59) Kt =0xCA62C1D6(60≤ t≤ 79)將 明 文 按 照 規(guī) 則 填 充 ， 然 后 按 照 512bits 分組為 M(1), M(2), ... , M(n)， 對 每個 512bits的 明 文 分 組 M(i)操 作 的 步 驟 的 操 作 如 下 （ 以下“ +”均 指 mod232 的加運算）：(1) 將 512bits 的 一 個 明 文 分 組 又 分 成 16 個 32bits 的 子 分 組 ， M0,M1,… ,M15， M0 為最 左 邊 的 一 個 子 分 組 ；(2) 再 按 照 以 下 法 則 將 16 個 子 分 組 變 換 成 80 個 32bits 的 分 組 W0,W1,… ,W79:Wt= Mt, 0≤ t≤ 15,Wt= Wt3 xor Wt8 xor Wt14 xor Wt16 , 16≤ t≤ 79 ；(3) 將 五 個 工 作 變 量 中 的 數(shù) 據(jù) 復(fù) 制 到 另 外 五 個 記 錄 單 元 中 ： 令 A = H0, B = H1, C = H2, D = H3, E = H4；(4) 進 行 20個 步 驟 一 輪 ， 共 4 輪 80 個 步 驟 的 操 作 ， t 表 示 操 作 的 步 驟 數(shù) ， 0≤ t≤ 79：TEMP =A5 + ft(B,C,D) + E + Wt + KtE = D D = C C = B 30 B = A A = TEMP (5) 第 4 輪 的 最 后 一 步 完 成 后 ， 再 作 運 算 ： 第 26 頁 共 47 頁H0= H0 + A H1= H1 + B H2= H2 + C H3= H3 + D H4= H4 + E所 得 到 的 五 個 記 錄 單 元 中 的 H0， H1， H2， H3， H4， 成 為 下 一 個 分 組 處 理 時 的 初始 值 。 最 后 一 個 明 文 分 組 處 理 完 畢 時 ， 五 個 工 作 中 的 數(shù) 值 級 聯(lián) 成 為 最 終 的 散 列 值 [27]。4 信息安全性實現(xiàn) 開發(fā)環(huán)境和工具的選擇本設(shè)計采用開源,免費,安全,穩(wěn)定,高性能的 linux 系統(tǒng)下的 vim 為開發(fā)環(huán)境。Vim 具有快速、跨平臺、高效、專業(yè)等優(yōu)點，是軟件開發(fā)的理想選擇。（有關(guān) liunx 系統(tǒng)下的vim 的詳細介紹這里就不做講解，感興趣的讀者可自行查看相關(guān)的資料）。開發(fā)語言采用語法簡潔、功能強大的 C 語言進行開發(fā) [28]。 AES 加解密的實現(xiàn)下圖 為所要設(shè)計的 AES 加解密流程圖，左邊為加密右邊為解密流程。密鑰長度可變，可指定為 1219256 比特，這里指定為 128 位。不同密鑰長度決定了加解密算法的輪數(shù)（128 位：10 輪，192 位：12 輪，256 位：14 輪），算法征集之初，6 第 27 頁 共 47 頁輪迭代便可抵抗當(dāng)時世界上已知的所有攻擊，AES 標準中至少留了 4 輪余量。解密為加密的逆過程，這里就不在重復(fù)。圖 AES 加/解密流程? 加密函數(shù)： AESEncrypt (State, ExpandedKey) { AddRoundKey (State, ExpandedKey)。 //種子密鑰加，實際已經(jīng)進行過子密鑰擴展 for (i=1。 i