代密码系统AdvancedEncryptionStanda

The McGraw-Hill Companies, Inc., 2005 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 20052 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 20053 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 20054 1997年 元 月 二 日 由 NIST經 由 公 開 程 序 對 外 徵 求 1997年 四 月 十 五 日 舉 辦 AES研 討 會 ， 研 討 制 訂 AES之功 能 需 求 。 NIST於 1997年 九 月 十 二 日 ， 正 式 公 佈 AES功 能 規 格 標 準 需 求 ：- AES為 一 對 稱 性 加 密 演 算 法- AES為 一 區 塊 加 密 演 算 法- AES為 進 行 加 密 之 區 塊 最 小 為 128位 元- AES秘 密 金 鑰 之 長 度 是 變 動 的 ， 可 以 為 128、 192 或 256位 元- 可 以 同 時 由 硬 體 及 軟 體 來 實 作- 沒 有 專 利 的 限 制 ， 可 以 自 由 使 用 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 20055 1998年 8月 20日 NIST舉 行 第 一 屆 AES會 議 ， 會 中 並 宣佈 及 介 紹 15個 獲 AES初 選 之 演 算 法 ： CAST-256、CRYPTON、 DEAL、 DFC、 E2、 FROG、 HPC、LOKI97、 MAGENTA、 MARS、 RC6、 RIJNDAEL、SAFER+、 SERPENT、 TWOFISH。針 對 此 15個 初 選 AES之 安 全 性 、 效 率 及 相 容 性 做 分 析 ，並 於 1999年 3月 22日 第 二 屆 AES會 議 中 提 出 分 析 報 告 。1999年 8月 20日 公 佈 MARS、 RC6、 Rijndael、 Serpent及 Twofish等 5個 演 算 法 可 進 入 第 二 回 合 決 選 。 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 20056 NIST於 2000年 4月 13日 再 舉 行 第 三 屆 AES會 議 ， 對 五個 決 選 AES演 算 法 再 進 行 分 析 。2000年 10月 2日 正 式 宣 佈 由 比 利 時 二 位 密 碼 專 家 Joan Daemen及 Vincent Rijmen二 位 博 士 所 設 計 Rijndael（ 發音 為 Rain Doll） 獲 選 為 AES之 演 算 法 。 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 20057 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 2005 AES加 密 演 算 法 之 架 構AddRoundKey1:SubBytes2:ShiftRows3:MixColumns4:AddRoundKey1:SubBytes2:ShiftRows 3:AddRoundKey密 文 明 文Add ey1:S tes2:S s3: i ns4:Add ey1:S tes2:S s 3:Add ey 初 次Round KeyRound1 Round KeyRound12345678Nr-1 最 後Round Key密 文 明 文 By :施 冠 州 邱 敬 智 許 修 維 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 20059 反 覆 運 算 的 加 密 演 算 法資 料 區 塊 及 金 鑰 可 獨 立 變 動 128, 192, 256 bits: 運 算 過 程 所 產 生 的 中 間 值 ， 用 一 個 以 byte為 單 位 的 長 方型 矩 陣 來 表 示 (4列 ， 行 數 為 資 料 區 塊 除 以 32bits)， 成 為 一 個 4Nb 的 矩 陣 ， 也 就 是 把 資 料 分 割 成 Nb 個 區 塊 或 行 數 。8 bits * 4 = 32 bitsX / 32 = Nb 行 X / 8 = 4 * Nb byte加 解 密 資 料 會 先 被複 製 到 此 state矩 陣 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 2005 AES演 算 法 相 關 參 數 說 明 Nb (明 文 區 塊 數 目 ) 由 資 料 長 度 除 以 32位 元 求 得 Nk (金 鑰 區 塊 數 目 ) 由 金 鑰 長 度 除 以 32位 元 求 得 Nr (回 合 數 ) 由 Nb、 Nk共 同 決 定 State (要 加 密 的 資 料 ) 加 密 的 資 料 會 先 被 複 製 到 此 一 矩 陣 (size:4 * Nb) W(存 放 金 鑰 字 元 的 陣 列 ) 陣 列 中 每 個 元 素 為 32位 元 (size:Nb * (Nr+1) 10 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200511 Cipher K ey: 加 密 金 鑰 ， 一 個 4Nk bytes的 矩 陣 ， 也 就 是 把金 鑰 分 割 成 Nk 個 32位 元 之 子 金 鑰 。 Nb vs. Nk 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200512 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200513 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200514 b 01234567 bbbbbbbb ib216 )01010111()57( 1246 xxxx 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200515 16221616 )()01010011()10101001()53()9( FAA )()1()1( 3456746357 xxxxxxxxxxxx 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200516)1( )1()()()( )1()1()53()9( 35813 35746847911691113 463571616 xxxxx xxxxxxxxxxxxxxx xxxxxxA 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 2005171 )1()1( )(1( )1()1()53()9( 23456 34823456 5348 348358131616 xxxxx xxxx mod xxxxxx xxxxxx xxxx mod xxxxxA )1()( 348 xxxxxm 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 2005 Mathematical Preliminaries Addition XOR operation Multiplication In the polynomial representation, multiplication in GF(28)corresponds with the multiplication of polynomials modulo an irreducible polynomial of degree 8. m(x) = x8+x4+x3+x+1 EX, 57 83 = c1 01010111 10000011=11000001(x6+x4+x2+x+1)(x7+x+1) =x 13+x11+x9+x8+x7+x7+x5+x3+x2+x+x6+x4+x2+x+1=x13+x11+x9+x8+x6+x5+x4+x3+1(x13+x11+x9+x8+x6+x5+x4+x3+1) modulo x8+x4+x3+x+1=x7+x6+1 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200519 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200520 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 2005 原 始 金 鑰 (128bit) Ki= 1 byte = 8 bits Key=ABCDEFGHIJKLMNOP 4word(128bit) Key將 擴 充 成 為 4*11word key 6word(192bit) Key將 擴 充 成 為 4*13word key 8word(256bit) Key將 擴 充 成 為 4*15word key金 鑰 之 擴 充 程 序 (1/4)K1K2K3K4K1K2K3K4K1K2K3K4K1K2K3K44142434445464748494a4b4c4d4e4f50ABCDEFGHIJKLMNOP128 / 8 = 16 By :施 冠 州 邱 敬 智 許 修 維 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 2005 擴 充 程序 (2/4)4142434445464748494a4b4c4d4e4f504d4e 4f504e4f504dRotWordSubBytes4e2f4e2f8453e341424344 01000000=6fc610a7RCON6fc610a7Wi-4 Wi-1 WiIf (i mod 4)=0Wi = Wi-4 SubBytes(RotWord(Wi-1) RCON(i)RCON(i) = 2(i-4)/4 = 1,2,4,8W4 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200523XOR AES Key Schedule 移 動 到 最 下 面 RotWord(經 過 S-Box轉 換 後 )09XOR XOR Cipher key Round key 1 Rcon By: 韋 宜 成 、 劉 伯 伸 、 陳 昱 潭 、 曾 劭 逸 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200524 AES Key Schedule(1/2) XOR 總 共 10個 round Cipher key Round key 1 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 2005 擴 充 程序 (3/4)4142434445464748494a4b4c4d4e4f506fc610a74546 47486fc610a72a80577f494a4b4c2a80577f63ca1ca34d4e4f5063ca1ca32e8453f3322b1d9618ab4a797b6156da55e50529ef40b86af7ebf2138c8aa4c9d96fa1e08821e1dbbf6b9708bb3e3dda9de9b7efWi-4 Wi-1 WiIf (i mod 4) 0Wi = Wi-4 Wi-1If (i mod 4)=0Wi = Wi-4 SubBytes(RotWord(Wi-1) RCON(i)ElseWi = Wi-4 Wi-1128bit的 Key 需 11 回 合 加 解 密 , 因 此 i = 4 - 44 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 2005 擴 充 金 鑰 之 規 則 (4/4)第 二 組 後 擴 充 金 鑰 之 規 則If (i mod kw)=0 thenWi= Wi- kw SubBytes( RotWord(Wi-1) ) 2(i/kw)-1 Else If (kw6) and (i mod 4)=0) thenWi= eKi- kw SubBytes( Wi-1 )ElseWi= eKi- kw Wi-1 kw :key之 word數128bit Key, kw=4, 需 10 次 i = 4 - 43192bit Key, kw=6, 需 8 次 i = 6 - 51256bit Key, kw=8, 需 7 次 i = 8 - 59 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200527 子 金 鑰 的 選 擇 是 由 擴 充 金 鑰 中 所 依 序 給 定 的 ， 即第 i把 回 合 金 鑰 由 WNbi WNb(i+1)-1W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 W11 Round Key 1: W4W7Round Key 2: W8W11Round Key 3: W12W15Round Key 11: W44W47Round Key 0: W0W3Round Key 12: W48W51 Initial RoundStandard RoundFinal Round 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200528 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200529 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200530 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200531 位 元 組 取 代 轉 換 ( ) 位 元 組 轉 換 是 一 個 以 位 元 組 為 單 位 的 線 性 取 代 運 算 ， 取 代 表 (S-Box)是經 過 兩 個 運 算 過 程 而 建 立 ， 並 且 是 可 逆 的 。 55 (95)16 (2a)16 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200532 0110001111111000 01111100 00111110 00011111 10001111 11000111 11100011 11110001 7654321076543210 xxxxxxxxyyyyyyyy 01234567 , xxxxxxxx 01234567 , yyyyyyyy 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200533167654321 0 )2(00101010011000111000101011111000 01111100 00111110 00011111 10001111 11000111 11100011 11110001 Ayyyyyyyy 21610,0 1610,00,0 160,0 )10001010()8( )01()95( Aa aaa 01234567 , xxxxxxxx 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200534 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200535 160,0 )5(Ba 160,0 )5(Db 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200536 01234567 , xxxxxxxx01234567 , yyyyyyyy 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200537 1676543210 )75(000001011101010101010010 00101001 10010100 01001010 00100101 10010010 01001001 10100100 yyyyyyyy 01234567 , yyyyyyyy 2160,0 )11010101()5( Db 16)75( 的 乘 法 反 元 素 為 0,016)5( aB 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200538 160,0 )5(Ba 160,0 )5(Db 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200539 EX 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200540 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200541 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 2005 ShiftRows()： 列 移 位 運 算 Data ShiftRows(Data)3de3e2be2b2819a09ae9f4c6f88d480819a09ae93d3df4c6f8左 旋 1e3e2左 旋 2e3e28d48be2b28左 旋 3be2b2808 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200543 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200544 0,3 0,20,1 0,00,3 0,20,1 0,0 02010103 03020101 01030201 01010302 aaaabbbb )(xc 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 2005 MixColumns()： 混 合 行 運 算 Data MixColumns(Data)d4bf5d30e0b4529eb84111f11e2798e5d4bf5d 30d4bf5d3004d4bf5d30d4bf5d30d4bf5d306681e5046681e5046681e528aed2a6ab87158809cf4f3cFor more details, see next page By 施 冠 州 邱 敬 智 許 修 維 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 2005 AES加 密 運 算 實 例 (5/6 )305)03()402( , dbfdS co混 合 行 運 算 (Mix Column Operation) D4 11010100 02 00000010 00000000 11010100 110101000 超 過 有 限 場 需 以 11B調 整 1348 xxxx x8+x7+x5+ x3x8+ x4+x3+x+1 x7+x5+x4+ x+1 10110011 BF 10111111 03 00000011 10111111 10111111 111000001 超 過 有 限 場 需 以 11B調 整 1348 xxxx x8+x7+x6+ +1x8+ x4+x3+x+1 11 x7+x6+x4+x3+x 11011010 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 2005 AES加 密 運 算 實 例 (6/6 )305)03()402( , dbfdS co混 合 行 運 算 (Mix Column Operation)10110011 02 d4 結 果 11011010 03 bf 結 果01101001 01011101 5d00110100 00110000 3000000100 04 以 此 類 推 ， 求 得 其 他 值 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200548 Final RoundByte SubShift RowAdd Round Key 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200549 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200550 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200551 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200552 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200553 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200554 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200555 Cipher TextInitial RoundAdd Round KeyInv Standard Round Inv Byte Sub Inv Shift RowInv Mix ColumnAdd Round KeyFinal RoundInv Byte SubInv Shift RowAdd Round Key Plain Text Nr-1 Rounds Cipher KeyExpansionExpanded KeySelectionRoundKey 1 RoundKey 2 RoundKey 3 RoundKey Nr-1 RoundKey NrRoundKey 0 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200556 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200557 從 S-Box的 (9,5)座 標 中 找 到 其 對 應 值 2A。從 Inverse S-Box的 (2, A)座 標 找 到 其 對 應 值 為 95 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200558 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200559 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200560 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200561 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200562 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 200563 加 密 與 解 密 的 對 應 關 係 The McGraw-Hill Companies, Inc., 2005 AES的 數 論 基 礎89053302 林 仁 宏2005.01 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 2005 Galois Field F28 AES所 用 到 之 Galois Field F28， 並 非 直 接 從 整 數 Z作 模運 算 可 得 其 中 一 個 典 型 的 做 法 是 先 考 慮 多 項 式 環 , somefor |)(: 202 FaNntatftF ini ii AES的 數 論 基 礎 By:林 仁 宏 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 2005 Fpt (p為 質 數 )的 除 法 考 慮 兩 多 項 式 除 法 p(t)、 m(t) Fpt 可 唯 一 表 達 成p(x) = m(t)q(t) + r(t)其 中 q(t) 為 商 式 ， r(t) 為 餘 式 Fpt /(t) (其 中 (t) 為 首 項 係 數 為 1不 可 約 多 項 式 )代 表 所 有 Fpt 多 項 式 模 (t) 之 同 餘 類 所 形 成 之 集 合 由 於 (t) 為 不 可 約 多 項 式 ， 所 有 非 (t) 倍 數 之 多 項式 ， 都 與 (t) 互 質 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 2005 同 構 所 有 的 Galois Field凡 是 元 素 個 數 (又 稱 秩 (order)相 同 ， 皆 同構 ， 故 F3t / (t2+1) F3t / (t2+t+1)其 中 t2+1與 t2+t+1皆 為 次 數 3之 不 可 約 多 項 式 因 此 在 考 量 Galois Field K之 代 數 結 構 時 ， 只 需 知 道 K之 秩 ，任 何 所 選 取 之 模 型 都 是 同 構 K之 秩 必 然 是 pn ， 其 中 p為 質 數 ， n為 正 整 數 ； 在 考 量 K上 之計 算 ， 一 般 是 考 慮 模 型 K Fpt /(t) (其 中 (t) 為 首 項 係 數為 1 ， 次 數 為 n之 不 可 約 之 F p之 多 項 式 ) 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 2005 Galois Field Fp 與 Fpt /(t) 之 異 同 處 Z Fpt 質 數 q (t) (mod q) (mod (t) | | deg()Zq Fpt /(t) Fq Fpn AES所 用 之 Galois Field F 28 F2t / (t8 + t4 + t3 + t +1)之 元 素 可 很 自 然 地 化成 為 2進 位 數 ， 譬 如t7 + t6 + t3 + t +1(11001011)2 新 一 代 密 碼 系 統 The McGraw-Hill Companies, Inc., 2005 加 法 與 乘 法 F2多 項 式 之 加 法 ， 即 XOR運 算 (t7 + t6 + t3 + t +1)+(t7 + t5 + t2)= t6 + t5 + t3 + t2+ t + 1(01101111)2= (11001011)2 (10100100)2 而 乘 上 t ， 即 左 移 一 位 元 ， 末 位 填 0 ( t5 + t3 +1)t= t6 + t4 + t(01010010)2 = (00101001)2 1 這 些 運 算 ， 包 括 模 運 算 ， 都 非 常 容 易 以 硬 體 實 現 。