セミナー構成 1 部概要 (13:30~14:20) 暗号アルゴリズム実装試験の概要 暗号アルゴリズム及び試験内容の説明 AES 2 部 RSA(14:30~15:30) 暗号アルゴリズム及び試験内容の説明 RSA-OAEP RSA-PSS 3 部擬似乱数生成器 (15:40~16:30) 暗号アル

Transcription

1 暗号モジュールの 暗号アルゴリズム実装試験セミナー 2008 年 2 月 20 日独立行政法人情報処理推進機構セキュリティセンタ - 情報セキュリティ認証室 1

2 セミナー構成 1 部概要 (13:30~14:20) 暗号アルゴリズム実装試験の概要 暗号アルゴリズム及び試験内容の説明 AES 2 部 RSA(14:30~15:30) 暗号アルゴリズム及び試験内容の説明 RSA-OAEP RSA-PSS 3 部擬似乱数生成器 (15:40~16:30) 暗号アルゴリズムの説明 Hash_DRBG (NIST SP800-90) について 質疑応答 2

3 暗号アルゴリズム実装試験の概要 暗号アルゴリズム実装試験とは 試験目的 : 暗号モジュールに承認されたセキュリティ機能が適正に実装されていることを確認 試験対象 : 暗号モジュールに実装された承認されたセキュリティ機能 試験方法 : 暗号アルゴリズム実装試験ツール JCATT を使用 ( ただし,JCATT がサポートしていないセキュリティ機能はベンダによる自己確認 ) JCATT : Japan Cryptographic Algorithm implementation Testing Tool 3

4 JCMVP で承認されたセキュリティ機能 技術分類 暗号名称 公開鍵暗号署名 DSA,ECDSA,RSASSA-PKCS1-v1_5,RSASSA-PSS 守秘 鍵確立 RSA-OAEP,RSAES-PKCS1-v1_5 DH,ECDH,PSEC-KEM 共通鍵暗号 64 ビットブロック暗号 CIPHERUNICORN-E,Hierocrypt-L1,MISTY1,3-keyTripleDES 128 ビットブロック暗号 AES,Camelia,CIPHERUNICORN-A, Hierocrypt-3,SC2000 ストリーム暗号 MUGI,MULTI-S01,128-bitRC4 その他ハッシュ関数 RIPEMD-160,SHA-1,SHA-224,SHA-256,SHA-384,SHA-512 メッセージ認証 擬似乱数生成系 CCM,CMAC,HMAC-SHA-1,HMAC-SHA-224,HMAC-SHA-256, HMAC-SHA-384,HMAC-SHA-512 ISO/IEC18031(Hash_DRBG,CTR_DRBG,OFB_DRBG) NISTSP800-90(Hash_DRBG,HMAC_DRBG,CTR_DRBG) NIST-RecommendedRandomNumberGeneratorBasedonANSI X9.31AppendixA.2.4Usingthe3-keyTripleDESandAESAlgorithms PRNGbasedonSHA-1forgeneralpurposeinFIPS186-2 (+changenotice1)appendix3.1 PRNGbasedonSHA-1forgeneralpurposeinFIPS186-2 (+changenotice1)revisedappendix3.1 PRNGbasedonSHA-1inANSIX AnnexC.1 注 : 電子政府推奨暗号リストに記載されたセキュリティ機能は太字で表示 ただし, 電子政府推奨暗号リストに記載された 3 種類の擬似乱数生成系は, JIS X に基づく暗号モジュール認証では JIS X の規定により承認されない乱数生成系となります 4

5 暗号アルゴリズム実装試験の位置付け 暗号モジュール試験の一部として実施 申請者 暗号モジュールのベンダ, 供給者など 暗号モジュール 認証報告書暗号モジュール認証書 暗号アルゴリズム実装 ソースコード FSM VEドキュメントブロック図セキュリティポリシ 認証機関 独立行政法人情報処理推進機構 暗号アルゴリズム確認 暗号アルゴリズム確認書 暗号アルゴリズム実装試験報告書 暗号アルゴリズム実装試験 JCATT 試験機関 運用ガイダンス 試験方法 セキュリティ要件 暗号モジュール認証 セキュリティポリシ 暗号モジュール試験報告書 暗号モジュール試験 5

6 暗号アルゴリズム実装試験フロー ベンダ 試験機関 認証機関 全ての動作環境 (OS) と暗号アルゴリズム指定 質問ファイル 質問ファイル, 正解ファイル作成 回答ファイル作成 回答ファイル OK/NG 回答ファイルと 正解ファイルの照合 ツールで判定 立会い試験 全て OK 試験報告書作成 暗号アルゴリズム確認書作成 6

7 暗号アルゴリズム実装試験ツール試験項目 1. 署名 DSA, ECDSA ドメインパラメータ生成機能試験, ドメインパラメータ検証機能試験鍵ペア生成機能試験, 署名生成機能試験, 署名検証機能試験 RSASSA-PKCS1-V1_5, RSA-PSS 鍵ペア生成機能試験, 署名生成機能試験, 署名検証機能試験 2. 守秘 RSA-OAEP, RSAES-PKCS1-V1_5 鍵ペア生成機能試験, 暗号化機能試験, 復号機能試験 3. 鍵確立 DH, ECDH ドメインパラメータ生成機能試験, ドメインパラメータ検証機能試験鍵ペア生成機能試験, 公開鍵検証機能試験, 鍵共有機能試験 PSEC-KEM 鍵ペア生成機能試験, セッション鍵暗号化機能試験, セッション鍵復号機能試験 各暗号アルゴリズム確認書を発行する条件は, 下線付きの試験対象機能を少なくとも 1 つ実装し, 暗号アルゴリズム実装試験に合格することとする 7

8 暗号アルゴリズム実装試験ツール試験項目 4. 共通鍵暗号 CIPHERUNICORN-E, Hierocrypt-L1, MISTY1, 3-key Triple DES, AES, Camellia, CIPHERUNICORN-A, Hierocrypt-3, SC2000 種々の平文 ( 暗号文 ) に対する既知入出力試験, 種々の鍵に対する既知入出力試験, マルチブロックメッセージ試験, モンテカルロ試験, Sbox 既知入出力試験 5. ストリーム暗号 MUGI 種々の鍵に対する既知入出力試験, モンテカルロ試験 MULTI-S01, 128-bit RC4 種々の平文 ( 暗号文 ) に対する既知入出力試験, 種々の鍵に対する既知入出力試験, モンテカルロ試験 6. ハッシュ関数 RIPEMD-160, SHA-1, SHA-224, SHA-256, SHA-384, SHA-512 短いメッセージに対する試験, 選択された長いメッセージに対する試験, 擬似ランダムメッセージに対する試験 8

9 暗号アルゴリズム実装試験ツール試験項目 7. メッセージ認証 CCM, CMAC, HMAC-SHA-1, HMAC-SHA-224, HMAC-SHA-256, HMAC-SHA-384, HMAC-SHA-512 短いメッセージに対する試験, 選択された長いメッセージに対する試験, 擬似ランダムメッセージに対する試験 8. 擬似乱数生成関数 PRNG based on SHA-1 for general purpose in FIPS (+ change notice 1) Appendix 3.1, PRNG based on SHA-1 for general purpose in FIPS (+ change notice 1) revised Appendix 3.1, PRNG based on SHA-1 in ANSI X Annex C.1, Hash_DRBG, CTR_DRBG and OFB_DRBG in ISO/IEC 18031, NIST SP800-90(Hash_DRBG, HMAC_DRBG, CTR_DRBG), NIST-Recommended Random Number Generator Based on ANSI X9.31 Appendix A.2.4 Using the 3-key Triple DES and AES Algorithms 種々のシードに対する試験, モンテカルロ試験 参考 : 暗号アルゴリズム試験仕様書 (2006 年度版 ) 試験方法及びファイルフォーマット仕様書が記載されています 9

10 JCATT で現在試験できないセキュリティ機能 1. 共通鍵暗号 CTR モードカウンタが内部インクリメンタルカウンタ以外の実装 ベンダ自己確認 2. 擬似乱数生成器 Hash_DRBG, HMAC_DRBG, CTR_DRBG(NIST SP800-90) ベンダ自己確認 3. 鍵共有 DH ASN.1に基づく鍵導出関数を使用したもの ベンダ自己確認 DRBG: Deterministic Random Bit Generator 決定論的乱数ビット列生成器 DH: Diffie-Hellman ASN.1: Abstract Syntax Notation One, 抽象構文記法 1 情報の構造定義の言語 10

11 共通鍵暗号 :AES AES (Advanced Encryption Standard) 仕様 :FIPS PUB ブロック長 :128-bit 鍵長 :128, 192, 256-bit 11

12 共通鍵暗号 :AES 暗号化 / 復号 入力 平文 / 暗号文 ( ブロック長 :128-bit) 鍵 ( 鍵長 :128, 192, 256-bit) 出力 暗号文 / 平文 ( ブロック長 :128-bit) 処理 128-bit の平文 暗号文を 8-bit の行列要素とした 4*(Nb(=4)) 行列表示して, 演算を行う 拡大鍵 1 ワード =32-bit として, Nb *(Nr+1) ワードの拡大鍵を生成して使用する ここで鍵長 128, 192, 256-bit に対応して, Nr=10,12,14 である (Nr+1) 回の XOR を必要とする 12

13 AES アルゴリズム - 暗号化 - 暗号化処理の流れ Cipher(bytein[4*Nb],byteout[4*Nb],wordw[Nb*(Nr+1)]) begin 平文暗号文拡大鍵 bytestate[4,nb] // 内部変数 (4 行,Nb 列の行列 ) state=in AddRoundKey(state,w[0,Nb-1])// Nb:4, Nr:10,12,14 for 128, 192, 256-bit key, w: 拡大鍵, 要素数 Nb *(Nr+1) SubBytes: 行列要素の置換 end forround=1step1tonr 1 SubBytes(state)// ShiftRows(state)// MixColumns(state)// AddRoundKey(state,w[round*Nb,(round+1)*Nb-1]) endfor SubBytes(state) ShiftRows(state) AddRoundKey(state,w[Nr*Nb,(Nr+1)*Nb-1]) out=state ShiftRows: 行単位の左シフト処理 MixColumns: 列ベクトル単位のデータの変換 AddRoundKey: 列ベクトルと拡大鍵 wとの XOR 演算 13

14 AES アルゴリズム - 復号 - 復号処理の流れ InvCipher(bytein[4*Nb],byteout[4*Nb],wordw[Nb*(Nr+1)]) begin 暗号文平文拡大鍵 bytestate[4,nb] // 内部変数 (4 行,Nb 列の行列 ) end state=in AddRoundKey(state,w[Nr*Nb,(Nr+1)*Nb-1])// forround=nr-1step-1downto1 InvShiftRows(state)// InvSubBytes(state)// AddRoundKey(state,w[round*Nb,(round+1)*Nb-1]) InvMixColumns(state)// endfor InvShiftRows(state) InvSubBytes(state) AddRoundKey(state,w[0,Nb-1]) out=state Nb:4, Nr:10,12,14 for 128, 192, 256-bit key, w: 拡大鍵, 要素数 Nb *(Nr+1) InvShiftRows: 行単位の右シフト処理 InvSubBytes: 行列要素の置換 InvMixColumns: 列ベクトル単位のデータの変換 AddRoundKey: 列ベクトルと拡大鍵 wとの XOR 演算 14

15 共通鍵暗号 : 利用モード 利用モード ブロック長よりも長いメッセージを暗号化する際の メカニズム 仕様 :SP800-38A JCATT で AES と組合わせて試験できる 利用モード ECB (Electronic Codebook) モード CBC (Cipher Block Chaining) モード CFB (Cipher Feedback) モード OFB (Output Feedback) モード CTR (Counter) モード 15

16 ECB モード 動作 : 各ブロックを独立に暗号化又は復号 特徴 : シンプル, 並列処理可能 暗号化 復号 平文ブロック 1 平文ブロック n 暗号文ブロック 1 暗号文ブロック n 暗号化 暗号化 復号 復号 暗号文ブロック 1 暗号文ブロック n 平文ブロック 1 平文ブロック n 16

17 CBC モード 動作 : 直前の暗号文ブロックと平文ブロックとの XORを演算してから暗号化 直前の暗号文ブロックと復号した暗号文ブロックの XORを演算して復号 特徴 : 復号のみ並列処理可能暗号化復号 平文ブロック 1 平文ブロック 2 平文ブロック 3 暗号文ブロック 1 暗号文ブロック 2 暗号文ブロック 3 復号 復号 復号 暗号化 暗号化 暗号化 暗号文ブロック 1 暗号文ブロック 2 暗号文ブロック 3 平文ブロック 1 平文ブロック 2 平文ブロック 3 初期化ベクトル (IV) 初期化ベクトル (IV) 17

18 CFB モード 動作 : 直前の暗号文ブロックを暗号化して入力ブロックとの XORを演算 特徴 : 復号のみ並列処理可能暗号化復号 初期化ベクトル (IV) 初期化ベクトル (IV) 暗号化 暗号化 暗号化 暗号化 暗号化 暗号化 暗号文ブロック 1 暗号文ブロック 2 暗号文ブロック 3 暗号文ブロック 1 暗号文ブロック 2 暗号文ブロック 3 平文ブロック 1 平文ブロック 2 平文ブロック 3 平文ブロック 1 平文ブロック 2 平文ブロック 3 18

19 OFB モード 動作 : 初期化ベクトル (IV) を暗号化して入力ブロックとの XOR を演算 特徴 : 暗号化と復号が同じ構造, 前準備可能 暗号化 復号 初期化ベクトル (IV) 初期化ベクトル (IV) 暗号化 暗号化 暗号化 暗号化 暗号化 暗号化 暗号文ブロック 1 暗号文ブロック 2 暗号文ブロック 3 平文ブロック 1 平文ブロック 2 平文ブロック 3 平文ブロック 1 平文ブロック 2 平文ブロック 3 暗号文ブロック 1 暗号文ブロック 2 暗号文ブロック 3 19

20 CTR モード 動作 : カウンタブロックを暗号化して入力ブロックとの XOR を演算 特徴 : 暗号化と復号が同じ構造, 前準備可能, 並列処理可能 暗号化 復号 外部カウンタ 1 外部カウンタ 2 外部カウンタ 3 外部カウンタ 1 外部カウンタ 2 外部カウンタ 3 内部カウンタ 1 内部カウンタ 2 内部カウンタ 3 内部カウンタ 1 内部カウンタ 2 内部カウンタ 3 カウンタ初期化 暗号化 暗号化 暗号化 カウンタ初期化 暗号化 暗号化 暗号化 暗号文ブロック 1 暗号文ブロック 2 暗号文ブロック 3 平文ブロック 1 平文ブロック 2 平文ブロック 3 平文ブロック 1 平文ブロック 2 平文ブロック 3 暗号文ブロック 1 暗号文ブロック 2 暗号文ブロック 3 20

21 AES 暗号アルゴリズム実装試験項目 既知入出力試験 種々の平文 ( 暗号文 ) に対する既知入出力試験 (KAT-Text) 種々の鍵に対する既知入出力試験 (KAT-key) GFSbox 既知入出力試験 (KAT-GFSbox) KeySbox 既知入出力試験 (KAT-KeySbox) マルチブロックメッセージ試験 (MMT) モンテカルロ試験 (MCT) 参考 :The Advanced Encryption Standard Algorithm Validation Suite 21

22 既知入出力試験 (KAT-Text) 種々の平文 ( 暗号文 ) に対する既知入出力試験 (KAT-Text) 1 個の鍵 平文 ( 又は暗号文 ) を様々に変化させ, 暗号文 ( または平文 ) が期待値と一致するかどうかを試験する 分かりやすくするために空白を追加 質問ファイル抜粋 鍵長 [BitlengthofKey] 128 [KeyforKAT-Text] [PlaintextforKAT-Text] C E F F FC FE FF FF FFC FFE FFF 省略 -- FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 暗号鍵 平文 22

23 既知入出力試験 (KAT-Key) 種々の鍵に対する既知入出力試験 (KAT-Key) 1 個の平文 ( 又は暗号文 ) 鍵を様々に変化させ, 暗号文 ( または平文 ) が期待値と一致するかどうかを試験する 分かりやすくするために空白を追加 質問ファイル抜粋 平文 [PlaintextforKAT-Key] [KeyforKAT-Key] C E F F FC FE FF FF FFC FFE FFF 省略 -- FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 暗号鍵 23

24 既知入出力試験 (KAT-GFSbox) GFSbox に対する既知入出力試験 (KAT-GFSbox) 1 個の鍵 Sbox テーブルのエントリーを全て 1 回以上引くように作成された複数の平文 ( 又は暗号文 ) を使って, 暗号文 ( または平文 ) が期待値と一致するかどうかを試験する 質問ファイル抜粋 [KeyforKAT-GFSbox] [PlaintextforKAT-GFSbox] F34481EC3CC627BACD5DC3FB08F273E6 9798C4640BAD75C7C3227DB910174E72 96AB5C2FF612D9DFAAE8C31F30C A118A874519E64E A503F1D35 CB9FCEEC81286CA3E989BD979B0CB284 B26AEB1874E47CA8358FF22378F C8E00B D54EAB84B91F0ACA1 [IVforKAT-GFSbox] 暗号鍵 平文 初期化ベクトル 分かりやすくするために空白を追加 24

25 既知入出力試験 (KAT-keySbox) KeySbox に対する 既知入出力試験 (KAT-KeySbox) 1 個の平文 ( 又は暗号文 ) Sbox テーブルのエントリーを全て 1 回以上引くように作成された複数の鍵を使って, 暗号文 ( または平文 ) が期待値と一致するかどうかを試験する 質問ファイル抜粋 平文 [PlaintextforKAT-KeySbox] [IVforKAT-KeySbox] [KeyforKAT-KeySbox] 10A58869D74BE5A374CF867CFB CAEA65CDBB75E9169ECD22EBE6E54675 A2E2FA9BAF7D20822CA9F0542F764A41 B6364AC4E1DE1E285EAF144A2415F7A0 64CF9C7ABC50B888AF65F49D521944B2 47D6742EEFCC0465DC96355E851B64D9 3EB C56BEE34BBCDECCF6CDB A924F0743D500CCADAE72C 省略 -- E234CDCA2606B81F29408D5F6DA C49074A3DA078DC1D828BB78C6F 3071A2A48FE6CBD04F1A129098E308F8 90F42EC0F68385F2FFC5DFC03A654DCE FEBD9A24D8B65C1C787D50A4ED3619A9 初期化ベクトル 暗号鍵 25

26 マルチブロックメッセージ試験 (MMT) MMT では, ランダムに与えられた複数ブロック分の平文 ( または暗号文 ),IV, カウンタに対する暗号文 ( または平文 ) が期待値と一致するかどうか検証を行う ただし,MMT ブロック数の規定値は 10 質問ファイル抜粋 [NumberofBlocksforMMT] ブロック数 10 [KeyforMMT] 7ae100eaafe60081b7ccbd1f34d7173b 暗号鍵 [IVforMMT] ECF8A3A30533EF EC782EBA8F7 初期化ベクトル (IV) [PlaintextforMMT] 2807d57da0f660670e65b1fac64ba1b4b912eabd9fc9ddee65cc90ac864649a54cbe4ab 平文 c58531c69b64ca530e68dcf7ad363a328255e0101dccea7e4cbaffae712c e a845a9dce495c8b0bcd8c77b083103d482fdbc7c48d8ca524ec14bc05404a68f35026d7de12e0a e4c853b918dc98db d89e985b412e55af9a850ea11094b64364e41528c3d a 26

27 モンテカルロ試験 (MCT) ランダムに与えられた 1 ブロック分の平文 ( または暗号文 ), 鍵,IV(ECB モードを除く ) に対して, 指定された利用モードで計算される暗号文 ( または平文 ) が期待値と一致するかどうか検証を行う MCT 擬似コード (ECB モード / 暗号化 ) Key[0]=Key// 初期鍵 PT=PT_0// 初期平文 for(i=0;i<outerloop;i++){ for(j=0;j<innerloop;j++){ //ECB モード暗号化 CT[j]=Encryption(Key[i],PT) PT=CT[j] } } OutputCT[innerloop-1] If( 鍵長 ==128 ビット ){ 出力 Key[i+1]=Key[i]xorCT[innerloop-1] } //-- 鍵長が192 及び256 ビットの // 処理については省略 -- 質問ファイル抜粋 [NumberofInner-loopforMCT] 1000 [NumberofOuter-loopforMCT] 100 [InitialKeyforMCT] 08152CDDCEDCBBE8909A0DE520C80D3D [InitialPlaintextforMCT] 2D8A66FDC53DCEE76A50E16B9365EBC0 ブロック長, 各モード, 暗号化 復号, 鍵長によって対応する MCT 擬似コード は異なる 暗号アルゴリズム試験仕様書を参照 27

28 AES 暗号化 : 質問ファイル及び回答ファイルのフォーマット (1/2) 機能 タグ 質問ファイルフォーマットデータ タグ 回答ファイルフォーマットデータ [AlgorithmName] AES( 固定 ) [AlgorithmName] AES( 固定 ) [FunctionName] Encryption( 固定 ) [FunctionName] Encryption( 固定 ) [ModesofOperation] ECB/CBC/OFB/CFB1/CFB8/CFB128/CTR [ModesofOperation] ECB/CBC/OFB/CFB1/CFB8/CFB128/CTR [BitlengthofKey] 鍵のビット長 ;128/192/256 [BitlengthofKey] 鍵のビット長 ;128/192/256 [BitlengthofCounter] カウンタのビット幅 (CTR モードのみ ) [BitlengthofCounter] カウンタのビット幅 (CTR モードのみ ) [KeyforKAT-Text] [PlaintextforKAT-Text] KAT-TEXT 用鍵 KAT-TEXT 用平文 KAT-TEXT [KeyforKAT-Text] [PlaintextforKAT-Text] KAT-TEXT 用鍵 KAT-TEXT 用平文 [IVforKAT-Text] KAT-TEXT 用 IV [IVforKAT-Text] KAT-TEXT 用 IV [CounterforKAT-Text] KAT-TEXT 用カウンタ (CTR モードのみ ) [CounterforKAT-Text] KAT-TEXT 用カウンタ (CTR モードのみ ) 暗号化 [PlaintextforKAT-Key] [IVforKAT-Key] KAT-Key 用平文 KAT-Key 用 IV KAT-Key [CiphertextforKAT-Text] [PlaintextforKAT-Key] [IVforKAT-Key] 上記パラメータに対する暗号文 KAT-Key 用平文 KAT-Key 用 IV [CounterforKAT-Key] KAT-Key 用カウンタ (CTR モードのみ ) [CounterforKAT-Key] KAT-Key 用カウンタ (CTR モードのみ ) [KeyforKAT-Key] KAT-Key 用鍵 [KeyforKAT-Key] KAT-Key 用鍵 [CiphertextforKAT-Key] 上記パラメータに対する暗号文 [KeyforKAT-GFSbox] [PlaintextforKAT-GFSBox] [IVforKAT-GFSbox] KAT-GFSbox 用鍵 KAT-GFSbox 用平文 KAT-GFSbox 用 IV KAT- GFSbox [KeyforKAT-GFSbox] [PlaintextforKAT-GFSBox] [IVforKAT-GFSbox] KAT-GFSbox 用鍵 KAT-GFSbox 用平文 KAT-GFSbox 用 IV [CounterforKAT-GFSbox] KAT-GFSbox 用カウンタ (CTR モードのみ ) [CounterforKAT-GFSbox] KAT-GFSbox 用カウンタ (CTR モードのみ ) [CiphertextforKAT-GFSbox] 上記パラメータに対する暗号文 28

29 AES 暗号化 : 質問ファイル及び回答ファイルのフォーマット (2/2) 機能 タグ 質問ファイルフォーマット データ タグ 回答ファイルフォーマット データ [PlaintextforKAT-KeySBox] [IVforKAT-KeySbox] [CounterforKAT-KeySbox] KAT-KeySbox 用平文 KAT-KeySbox 用 IV KAT- KeySbox KAT-KeySbox 用カウンタ (CTR モードのみ ) [PlaintextforKAT-KeySBox] [IVforKAT-KeySbox] [CounterforKAT-KeySbox] KAT-KeySbox 用平文 KAT-KeySbox 用 IV KAT-KeySbox 用カウンタ (CTR モードのみ ) [KeyforKAT-KeySbox] KAT-KeySbox 用鍵 [KeyforKAT-KeySbox] KAT-KeySbox 用鍵 [CiphertextforKAT-KeySbox] 上記パラメータに対する暗号文 [NumberofBlocksforMMT] [KeyforMMT] MMT のブロック数 MMT 用鍵 MMT [NumberofBlocksforMMT] [KeyforMMT] MMT のブロック数 MMT 用鍵 [IVforMMT] MMT 用 IV [IVforMMT] MMT 用 IV 暗号化 [InitialValueofCounterforMMT] [PlaintextforMMT] MMT 用カウンタ初期値 (CTR モードのみ ) MMT 用平文 [InitialValueofCounterforMMT] [PlaintextforMMT] MMT 用カウンタ初期値 (CTR モードのみ ) MMT 用平文 [CiphertextforMMT] 上記パラメータに対する暗号文 [NumberofInner-loopforMCT] [NumberofOuter-loopforMCT] MCT の内側ループの回数 MCT の外側ループの回数 MCT [NumberofInner-loopforMCT] [NumberofOuter-loopforMCT] MCT の内側ループの回数 MCT の外側ループの回数 [InitialKeyforMCT] MCT 用鍵の初期値 [InitialKeyforMCT] MCT 用鍵の初期値 [InitialPlaintextforMCT] MCT 用平文の初期値 [InitialPlaintextforMCT] MCT 用平文の初期値 [InitialIVforMCT] MCT 用 IV の初期値 [InitialIVforMCT] MCT 用 IV の初期値 [InitialValueofCounterforMCT] MCT 用カウンタ初期値 (CTR モードのみ ) [InitialValueofCounterforMCT] MCT 用カウンタ初期値 (CTR モードのみ ) [CiphertextforMCT] 上記パラメータに対する暗号文 29

30 AES 復号 : 質問ファイル及び回答ファイルのフォーマット (1/2) 機能 タグ 質問ファイルフォーマットデータ タグ 回答ファイルフォーマットデータ [AlgorithmName] AES( 固定 ) [AlgorithmName] AES( 固定 ) [FunctionName] Decryption( 固定 ) [FunctionName] Decryption( 固定 ) [ModesofOperation] ECB/CBC/OFB/CFB1/CFB8/CFB128/CTR [ModesofOperation] ECB/CBC/OFB/CFB1/CFB8/CFB128/CTR [BitlengthofKey] 鍵のビット長 ;128/192/256 [BitlengthofKey] 鍵のビット長 ;128/192/256 [BitlengthofCounter] カウンタのビット幅 (CTR モードのみ ) [BitlengthofCounter] カウンタのビット幅 (CTR モードのみ ) [KeyforKAT-Text] [CiphertextforKAT-Text] KAT-TEXT 用鍵 KAT-TEXT 用暗号文 KAT-TEXT [KeyforKAT-Text] [CiphertextforKAT-Text] KAT-TEXT 用鍵 KAT-TEXT 用暗号文 [IVforKAT-Text] KAT-TEXT 用 IV [IVforKAT-Text] KAT-TEXT 用 IV [CounterforKAT-Text] KAT-TEXT 用カウンタ (CTR モードのみ ) [CounterforKAT-Text] KAT-TEXT 用カウンタ (CTR モードのみ ) 復号 [CiphertextforKAT-Key] [IVforKAT-Key] KAT-Key 用暗号文 KAT-Key 用 IV KAT-Key [PlaintextforKAT-Text] [CiphertextforKAT-Key] [IVforKAT-Key] 上記パラメータに対する平文 KAT-Key 用暗号文 KAT-Key 用 IV [CounterforKAT-Key] KAT-Key 用カウンタ (CTR モードのみ ) [CounterforKAT-Key] KAT-Key 用カウンタ (CTR モードのみ ) [KeyforKAT-Key] KAT-Key 用鍵 [KeyforKAT-Key] KAT-Key 用鍵 [PlaintextforKAT-Key] 上記パラメータに対する平文 [KeyforKAT-GFSbox] [CiphertextforKAT-GFSBox] [IVforKAT-GFSbox] KAT-GFSbox 用鍵 KAT-GFSbox 用暗号文 KAT-GFSbox 用 IV KAT- GFSbox [KeyforKAT-GFSbox] [CiphertextforKAT-GFSBox] [IVforKAT-GFSbox] KAT-GFSbox 用鍵 KAT-GFSbox 用暗号文 KAT-GFSbox 用 IV [CounterforKAT-GFSbox] KAT-GFSbox 用カウンタ (CTR モードのみ ) [CounterforKAT-GFSbox] KAT-GFSbox 用カウンタ (CTR モードのみ ) [PlaintextforKAT-GFSbox] 上記パラメータに対する平文 30

31 AES 復号 : 質問ファイル及び回答ファイルのフォーマット (2/2) 機能 タグ [CiphertextforKAT-KeySBox] [IVforKAT-KeySbox] [CounterforKAT-KeySbox] 質問ファイルフォーマット データ KAT-KeySbox 用暗号文 KAT-KeySbox 用 IV KAT- KeySbox KAT-KeySbox 用カウンタ (CTR モードのみ ) タグ [CiphertextforKAT-KeySBox] [IVforKAT-KeySbox] [CounterforKAT-KeySbox] 回答ファイルフォーマット KAT-KeySbox 用 IV データ KAT-KeySbox 用暗号文 KAT-KeySbox 用カウンタ (CTR モードのみ ) [KeyforKAT-KeySbox] KAT-KeySbox 用鍵 [KeyforKAT-KeySbox] KAT-KeySbox 用鍵 [PlaintextforKAT-KeySbox] 上記パラメータに対する平文 [NumberofBlocksforMMT] [KeyforMMT] MMT のブロック数 MMT 用鍵 MMT [NumberofBlocksforMMT] [KeyforMMT] MMT のブロック数 MMT 用鍵 [IVforMMT] MMT 用 IV [IVforMMT] MMT 用 IV 復号 [InitialValueofCounterforMMT] [CiphertextforMMT] MMT 用カウンタ初期値 (CTR モードのみ ) MMT 用暗号文 [InitialValueofCounterfor MMT] [CiphertextforMMT] MMT 用カウンタ初期値 (CTR モードのみ ) MMT 用暗号文 [PlaintextforMMT] 上記パラメータに対する平文 [NumberofInner-loopforMCT] [NumberofOuter-loopforMCT] MCT の内側ループの回数 MCT の外側ループの回数 MCT [NumberofInner-loopforMCT] [NumberofOuter-loopforMCT] MCT の内側ループの回数 MCT の外側ループの回数 [InitialKeyforMCT] MCT 用鍵の初期値 [InitialKeyforMCT] MCT 用鍵の初期値 [InitialCiphertextforMCT] MCT 用暗号文の初期値 [InitialCiphertextforMCT] MCT 用暗号文の初期値 [InitialIVforMCT] MCT 用 IV の初期値 [InitialIVforMCT] MCT 用 IV の初期値 [InitialValueofCounterforMCT] MCT 用カウンタ初期値 (CTR モードのみ ) [InitialValueofCounterforMCT] MCT 用カウンタ初期値 (CTR モードのみ ) [PlaintextforMCT] 上記パラメータに対する平文 31

32 AES 暗号アルゴリズム実装試験の申し込みに必要な情報 機能 暗号化, 復号 利用モード ECB,CBC,CFB,OFB,CTR 鍵長 128,192,256 カウンタ種別 内部カウンタ, 外部カウンタ 質問ファイル数機能 暗号化 復号 X 利用モード ECB (Electronic Codebook), CBC (Cipher Block Chaining), CFB (Cipher Feedback), OFB (Output Feedback), CTR (Counter) X 鍵長 128-bit 192-bit 256-bit 32

33 暗号アルゴリズム確認書の確認条件記載例 確認条件記載項目 利用モード (ECB/CBC/CFB/OFB/CTR) 機能 (e: 暗号化, d: 復号 ) 鍵長 (128/192/256) その他 CTR モードについては, カウンタ種別 (int: 内部カウンタ, ext: 外部カウンタ ) 確認条件記載例 確認番号 nnn 暗号アルゴリズム AES 確認条件 ECB(e/d;128,192,256),CBC(e/d;128,192,256), CTR(int;128,192,256) 33

34 暗号モジュールの 暗号アルゴリズム実装試験セミナー 第 2 部 :RSA 守秘 : RSA-OAEP 暗号化 / 復号 署名 : RSA-PSS 署名生成 / 署名検証 34

35 公開鍵暗号 :RSA 守秘 公開鍵で暗号化 プライベート鍵で復号 署名 プライベート鍵で署名生成 公開鍵で署名検証 35

36 公開鍵暗号 :RSA RSA パラメータ 素数 p,q 公開鍵 n(=pq): 法 e: 指数 プライベート鍵 CRT なし d: 秘密指数 CRT あり p, q, dp, dq, qinv CRT:Chinese Remainder Theorem gcd:greatest common divisor 性質 オイラーの φ 関数 (n) :1, 2,, nまでの自然数のうち, nと互いに素なものの個数 ( n) ( p) ( q) ( p 1)( q 1) 最大公約数 gcd( e, ( n)) 1 プライベート鍵 CRT なし e d CRT あり 1(mod ( n)) e dp 1(mod( p 1)) e dq 1(mod( q 1)) q qinv 1(mod p) 合同式 a b(modm) a mx b 36

37 公開鍵暗号 :RSA 承認されたセキュリティ機能 守秘 RSA-OAEP こちらについて説明 RSAES-PKCS1-v1_5 署名 RSASSA-PKCS1-v1_5 RSA-PSS こちらについて説明 仕様 PKCS#1 v2.1: RSA Cryptography Standard, June 14, ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-1/pkcs-1v2-1.pdf 37

38 公開鍵暗号 :RSA < 守秘 > 暗号化受信者の公開鍵を用いる メッセージ m n 未満の正の整数 暗号文 c c m e mod n 復号受信者のプライベート鍵を用いて復号する 平文 m d m' c (mod n) 38

39 公開鍵暗号 :RSA-OAEP 暗号化 (1) RSA-OAEP 暗号化 内部で使用する関数 Hash ハッシュ関数 ( ハッシュ関数の出力長は hlen ( バイト )) SHA-1, SHA-256, SHA-384, SHA-512 MGF マスク生成関数 入力 (n, e) 受信者の公開鍵 ( 法 n の長さは k ( バイト )) M 暗号化したいメッセージ ( 長さは mlen ( バイト )) L メッセージに関連したラベル ( デフォルトで空文字 ) 出力 C 暗号文 ( 長さは k ( バイト )) 39

40 公開鍵暗号 :RSA-OAEP 暗号化 (2) 処理概要 公開鍵メッセージラベル (n,e) M L 1. 長さチェック ラベル L の長さ制限 ( ハッシュ関数との関連 ) ならば, エラー表示 mlen k 2hLen 2 2. メッセージの前処理 3. 暗号化処理 4. 暗号文の出力 C 暗号文 Hash MGF ハッシュ関数 マスク生成関数 40

41 公開鍵暗号 :RSA-OAEP 暗号化 (3) 処理概要 2. メッセージの前処理 MGF: 入力文字列とカウンタをハッシュ関数への入力として用いて, 必要な長さのバイト列を生成する 凡例 白背景 入力 緑背景 中間 青字 長さ 丸枠 関数 1 擬似乱数生成器から mlen L M Hash k-mlen-2hlen-2 DB= lhash PS 01 M hlen k-hlen-1 1 seed MGF MGF 0x00で埋める EM= 00 maskedseed maskeddb k 41

42 公開鍵暗号 :RSA-OAEP 暗号化 (4) 処理概要 3. 暗号化処理 公開鍵 : (n,e) 暗号文 : 前頁より EM OS2IP m RSAEP c I2OSP C バイト列 ( 仕様書中では octet strings と表記 ) EM( 長さ k ( バイト )) を整数 m に変換する c m e mod n c を計算する の計算式に従い, 整数 c をバイト列 C ( 長さ k ( バイト ) に変換する 42

43 公開鍵暗号 :RSA - マスク生成関数 (1)- マスク生成関数 (MGF:Mask Generation Function) ANSI X9.44 に記載のものと同様 内部で使用する関数 Hash ハッシュ関数 ( ハッシュ関数の出力長は hlen ( バイト )) SHA-1, SHA-256, SHA-384, SHA-512 入力 mgfseed マスクを生成する元となるシード, バイト列 masklen 生成したいマスクの長さ ( バイト単位 ), 最大 2 32 hlen 出力 mask 生成されたマスク 長さは masklen ( バイト ) 43

44 公開鍵暗号 :RSA - マスク生成関数 (2)- マスク生成関数 (MGF:Mask Generation Function) 処理概要 0 counter 1 1 整数からバイト列への変換 I2OSP I2OSP I2OSP mgfseed mgfseed mgfseed Hash 4 Hash Hash T 0 masklen mask T 1 T m hlen m masklen / hlen 1 44

45 公開鍵暗号 :RSA-OAEP 暗号化機能試験 (1) 試験項目 試験 1 JCATT が与えた公開鍵 (n, e) および平文, ならびに指定されたハッシュ関数およびマスク生成関数 MGF およびラベル L に対して IUT が生成した暗号文を,JCATT が復号した時に, もとの平文に復号されること 同じ平文, 同じ公開鍵, 同じラベル値に対して, 複数 ( 別途規定する数 ) 暗号文を生成させた時, 同じ暗号文が生成されないこと JCATT : Japan Cryptographic Algorithm Implementation Testing Tool, 暗号アルゴリズム実装試験ツール IUT: Implementation Under Test, 試験対象実装 45

46 公開鍵暗号 :RSA-OAEP 暗号化機能試験 (2) 試験項目 試験 2( 任意で実施する試験 ) JCATT が与えた公開鍵 (n, e), 平文およびラベル L, ならびに指定された擬似乱数生成関数, 指定されたハッシュ関数およびマスク生成関数 MGF と, 乱数シードに対して正しい暗号文を IUT が生成すること 試験 3( 任意で実施する試験 ) JCATT が与えた公開鍵 (n, e), 平文およびラベル L, ならびに指定されたハッシュ関数, マスク生成関数 MGF および中間値 seed 対して正しい暗号文を IUT が生成すること 46

47 公開鍵暗号 :RSA-OAEP 暗号化機能試験 (3) 申し込む際に必要な情報 公開鍵 nのビット長 1024, 1536, 2048, 3072, 4096 指数 eのタイプ選択復号と 65537, ランダム異なる部分 関数の選択 使用するハッシュ関数 SHA-1, SHA-256, SHA-384, SHA-512 マスク生成関数 (MGF) ANSI X9.44 SHA-1, ANSI X9.44 SHA-256, ANSI X9.44 SHA-384, ANSI X9.44 SHA-512 試験の選択 試験 1, 試験 2( 擬似乱数生成関数の指定 ), 試験 3 47

48 公開鍵暗号 :RSA-OAEP 暗号化機能試験 (4) 試験 1 の場合 ( 質問ファイル抜粋 ) [BitlengthofModulus] 1024 [Hash] M_Hash_SHA256 [MGF] M_MGF_ANSI944_SHA256 [n] 法 n C110E0F94823D8DAA43AF0E3DBF4264FB634F68E28951F504F B0EF7757F68604D57D78ABB86F0066FA0228B5D2EE4B9E1618 5DAA127B AB4C3AAEB300749A099B1A22449B EDCC6E38EC22F38CA9BC7D3CA21303B6F4F3E9A5877E0C5A33 16A70856B043554F84FDB2A19F22222BEA67DB6F62EB A1671 [e] [L] [BitlengthofL] 0 法 n のビット長 ハッシュ関数 :SHA-256 MGF:ANSIX9.44SHA-256 公開鍵 e=65537 ラベル L, 長さ 0 [SeedS] [BitlengthofSeedS] 0 [BitlengthofPlaintexts] 64 [BitlengthofSs] 0 [NumberofPlaintexts] 10 [Plaintexts] CDE5F494 CA0B B 63D5F4134B4EA3A8 275C6A859A88C972 3B9654EAF30279D2 A77953D4E837BE0E 982D2357B7B658FC BD00584A65368C3C E E89A5C78 AD5C4702C515F57F [Ss] 試験 2 で使う 試験 3 で使う 平文 10 個 64-bit 同じ平文に対して 10 個の暗号文を生成 [NumberofCiphertextsforRGT] 10 48

49 公開鍵暗号 :RSA-OAEP 復号 (1) RSA-OAEP 復号 内部で使用する関数 Hash ハッシュ関数 ( ハッシュ関数の出力長は hlen ( バイト )) SHA-1, SHA-256, SHA-384, SHA-512 MGF マスク生成関数 入力 K 受信者のプライベート鍵 ( 法 n の長さは k ( バイト )) C 復号したい暗号文 ( 長さは k ( バイト )) L メッセージとの関連が検証されるラベル 出力 M メッセージ ( 長さは mlen ( バイト )) 49

50 公開鍵暗号 :RSA-OAEP 復号 (2) 処理概要 ラベルプライベート鍵暗号文 L K C 1. 長さチェック 2. 復号処理 3. メッセージを取り出す処理 Hash MGF ハッシュ関数 マスク生成関数 4. メッセージを出力 メッセージ M 50

51 公開鍵暗号 :RSA-OAEP 復号 (3) 処理概要 2. 復号処理 プライベート鍵 : 暗号文 K C OS2IP c RSADP m I2OSP EM バイト列 C( 長さ k ( バイト )) を整数 c に変換する CRTなしの場合, 計算式 m c d mod n に従い, mを計算する 整数 m をバイト列 EM ( 長さ k ( バイト ) に変換する 51

52 公開鍵暗号 :RSA-OAEP 復号 (4) 処理概要 3. メッセージを取り出す処理 hlen k EM= Y maskedseed maskeddb 1 MGF L seed MGF Hash hlen 1 lhash? DB= lhash PS 01 M k-2hlen-1 k-mlen-2hlen-2 M mlen 52

53 公開鍵暗号 :RSA-OAEP 復号機能試験 (1) 試験項目 与えられたプライベート鍵 (n, d) または (p, q, dp, dq, qinv) と, 与えられたラベル L と, 指定されたハッシュ関数及びマスク生成関数 MGF と, 与えられた暗号文に対して, もとの平文に復号できること 与えられたプライベート鍵 (n, d) または (p, q, dp, dq, qinv) と, 与えられたラベル L と, 指定されたハッシュ関数及びマスク生成関数 MGF と, 改竄された暗号文に対して不正検出を正しく行うこと 53

54 公開鍵暗号 :RSA-OAEP 復号機能試験 (2) 申し込む際に必要な情報 プライベート鍵 n のビット長 1024, 1536, 2048, 3072, 4096 プライベート鍵のタイプ選択 CRT あり, CRT なし 暗号化と異なる部分 関数の選択 使用するハッシュ関数 SHA-1, SHA-256, SHA-384, SHA-512 マスク生成関数 (MGF) ANSI X9.44 SHA-1, ANSI X9.44 SHA-256, ANSI X9.44 SHA-384, ANSI X9.44 SHA

55 公開鍵暗号 :RSA-OAEP 復号機能試験 (3) 質問ファイル抜粋 [BitlengthofModulus] 1024 [Hash] M_Hash_SHA256 [MGF] M_MGF_ANSI944_SHA256 [SecretKeyType] TYPE2 [d] 法 n のビット長 ハッシュ関数 :SHA-256 MGF:ANSIX9.44SHA-256 プライベート鍵 :CRT なし プライベート鍵 d 18DD6DB2FEEA48C616CE353F370C1AE896A0157EC8A817D 40E330D6125E75D80C5F798B0D6E1B313B79331B77BBB1E EC3E6C B5310DA2E7439E6E7D2B26266AEB842 3A73A9AC D747A2C71B4FC419383FB9DE50D31 72A1E525163A0CA447B0C3D50B253499F73B A04 0CA9F7947C [n] 法 n 9BE5A018CE FDDB5EC942BF8CD67CC5EA79C9071 CF37B9DA C8457EB4E5220A3FEB3E4B15928D F1790ED19C1AB945B7513C20CE8C B80BC21DB B4F9C58B0E101427AA45383C4D6BD876CAFBA2A03 D427927BE2903F5996E3D8135AC3C86557DBED55F7D38F7 88B56F5A8AC53FF7F787D [L] [BitlengthofL] 0 [BitlengthofPlaintexts] 64 [NumberofCiphertexts] 10 [Ciphertexts] ラベル L, 長さ 0 10 個の暗号文 F4F9F67DED434A28F02C0CC0796B762B 543D9116B66618C57DD45C91E60C1598D4011D E48A2FE7F71D0878AF1C20205C39A5305A81CE 87AEF1D482AF20B07315D10D7FCF3A48E2E76A 5DC6C1B36A11B9523DABEC75BD4BF0D6E7E80C C9B6295C4859ED7C8DAAE447F97052B5892C5A CC2E3022A5571E83A17D08E90BC7 -- 省略 -- 復号できる場合には, 元の平文を, 復号できない場合には, 平文のビット長 decryption error を回答ファイルに記述 55

56 公開鍵暗号 :RSA < 署名 > 署名生成 署名者のプライベート鍵を用いて 暗号化 する 署名検証 署名者の公開鍵を用いて 復号 する 56

57 公開鍵暗号 :RSA-PSS 署名生成 (1) RSA-PSS 署名生成 内部で使用する関数 Hash ハッシュ関数 ( ハッシュ関数の出力長は hlen ( バイト )) SHA-1, SHA-256, SHA-384, SHA-512 MGF マスク生成関数 入力 K 署名者のプライベート鍵 M 署名したいメッセージ ( バイト列 ) 出力 S 長さ k ( バイト ) の署名 ここで, k は法 n の長さ 57

58 公開鍵暗号 :RSA-PSS 署名生成 (2) 処理概要 プライベート鍵 K メッセージ M 1. 符号化処理 2. 署名生成処理 3. 署名の出力 Hash MGF ハッシュ関数 マスク生成関数 署名 S 58

59 公開鍵暗号 :RSA-PSS 署名生成 (3) 処理概要 1. 符号化処理 0x00 で埋める M 8 Hash slen M = padding 1 mhash salt emlen-slen-hlen-2 1 hlen 8emLen-emBits ビット分は 0 に設定 DB= padding 2 emlen-hlen-1 01 salt MGF Hash EM= maskeddb H bc emlen hlen = embits / 8 ( modbits 1) /

60 公開鍵暗号 :RSA-PSS 署名生成 (4) 処理概要 2. 署名生成処理 プライベート鍵 : K 署名 : 前頁より EM OS2IP m RSASP1 s I2OSP S バイト列 EM( 長さ k ( バイト )) を整数 m に変換する CRT 無しの場合, 計算式 s m d mod n に従い, sを計算する 整数 s をバイト列 S ( 長さ k ( バイト ) に変換する 60

61 公開鍵暗号 :RSA-PSS 署名生成機能試験 (1) 試験項目 試験 1 JCATT が与えたプライベート鍵 (n, d) または (p, q, dp, dq, qinv), 平文に対して IUT が生成した署名を, JCATT が署名検証した時に署名検証合格となること salt 長が 0 でない場合, 同じ平文, 同じプライベート鍵に対して, 複数 ( 別途規定する数 ) 署名を生成させた時,IUT が同じ署名を生成しないこと 61

62 公開鍵暗号 :RSA-PSS 署名生成機能試験 (2) 試験項目 試験 2 ( 任意で実施する試験 ) JCATT が与えたプライベート鍵 (n, d) または (p, q, dp, dq, qinv), 平文, ならびに指定されたハッシュ関数, 擬似乱数生成関数, 乱数シードに対して IUT が正しい署名を生成すること. 試験 3( 任意で実施する試験 ) JCATT が与えたプライベート鍵 (n, d) または (p, q, dp, dq, qinv), 平文, ならびに指定されたハッシュ関数,salt に対して IUT が正しい署名を生成すること. 62

63 公開鍵暗号 :RSA-PSS 署名生成機能試験 (3) 申し込む際に必要な情報 プライベート鍵 n のビット長 1024, 1536, 2048, 3072, 4096 プライベート鍵のタイプ選択 CRT あり, CRT なし 関数の選択 使用するハッシュ関数 SHA-1, SHA-256, SHA-384, SHA-512 マスク生成関数 (MGF) ANSI X9.44 SHA-1, ANSI X9.44 SHA-256, ANSI X9.44 SHA-384, ANSI X9.44 SHA-512 試験の選択 試験 1, 試験 2( 擬似乱数生成関数の指定 ), 試験 3 その他 salt のビット長 署名検証と異なる部分 63

64 公開鍵暗号 :RSA-PSS 署名生成機能試験 (4) 試験 1 の場合 ( 質問ファイルの抜粋 ) [BitlengthofModulus] 法 nのビット長 1024 [Hash] M_Hash_SHA256 ハッシュ関数 :SHA-256 [MGF] M_MGF_ANSI944_SHA256 MGF:ANSIX9.44SHA-256 [SecretKeyType] TYPE2 プライベート鍵 :CRT なし [d] 3709FDD34CAC1BAC88D217A5E43FF0A6AFAD13E0D049 プライベート鍵 d 1190A61FFA5C7E20F5ADD6A C91504CD4EA1C8 93A3D3D9EC9E16AC69D09F861F433F4C43E3574D8DD9 EE B6A6607F36DEDB03A4D2CC2A11D3420E0A9 5FCA6B299FA147E589112C739D51603BDD883C88A515 F9C99E35E2A9883FACB2D878E269231E2229 [n] B E6666BBD534384E9E9082F7C1D3C5F6B42 法 n 334BFBCFDF CB8A63EDF52091BBE0EFDEED82E 400CED062B0EADDFC13F7B4C92C13FBD93445FDC83C3 A4EAB00CF6C68FDA3349CED8A4D221AD12987D8E1E C5470F8CBBB19F48A049F19B6E764EB8DE099D5 4115C72B2B0604C A872BDB8405B13 [SeedSalt] [BitlengthofSeedSalt] 0 [BitlengthofPlaintexts] 1024 [SaltFlag] 0 [BitlengthofSalt] 256 [NumberofPlaintexts] salt 生成のための擬似乱数生成シード salt の入力フラグ 0: 指定なし salt のビット長 10 [Plaintexts] DDB8778F88379BB3602CA8C8D2E6628B E6059AB59CF473FAB7B9A52C1111 2A0890CCF6F37EF F7325D511FB AB83E5148CF9C73FEDECFF8FB3E C D771B2FA5F74F70F71C8 0E28A10487BCA0B61F AD78 署名したいメッセージ 6C7FC3A11C1E0FAC930E7A9F437317A10 同じメッセージ 4A D3C207A99F2BFC02 に対して10 個の署名 -- 省略 を生成 [NumberofSignaturesforRGT] 10 64

65 公開鍵暗号 :RSA-PSS 署名検証 (1) RSA-PSS 署名検証 内部で使用する関数 Hash ハッシュ関数 ( ハッシュ関数の出力長は hlen ( バイト )) SHA-1, SHA-256, SHA-384, SHA-512 MGF マスク生成関数 入力 (n, e) 署名者の公開鍵 M 署名を検証する元になるメッセージ ( バイト列 ) S 検証される署名 長さは k ( バイト ) で, 公開鍵 n の長さに等しい 出力 valid signature or invalid signature 65

66 公開鍵暗号 :RSA-PSS 署名検証 (2) 処理概要 メッセージ 公開鍵 署名 M (n,e) S 1. 長さチェック 署名 S の長さが k バイトでない場合, エラー処理 2. RSA アルゴリズムを使った処理 3. 比較 抽出部分 4. 検証結果出力 検証結果 Hash MGF ハッシュ関数 マスク生成関数 66

67 公開鍵暗号 :RSA-PSS 署名検証 (3) 処理概要 2. RSA アルゴリズムを使った処理 公開鍵 : (n, e) S OS2IP s RSADP m I2OSP EM バイト列 S ( 長さ k ( バイト )) を整数 s に変換する m s e mod n に従い, m を計算する 整数 mをバイト列 EM ( 長さ emlen ( modbits 1) / 8 ( バイト ) に変換する 67

68 公開鍵暗号 :RSA-PSS 署名検証 (4) 処理概要 3. 抽出 比較部分 前頁より emlen EM emlen-hlen-1 hlen 1 M Hash maskeddb H bc MGF 8 hlen salt M = padding 1 mhash salt emlen-hlen-1 slen H? H Hash 68

69 公開鍵暗号 :RSA-PSS 署名検証機能試験 (1) 試験項目 JCATT が与えた公開鍵 (n, e), 平文および署名, ならびに指定されたハッシュ関数に対して,IUT が署名検証合格と判定すること JCATT が改竄した平文, 署名, または公開鍵に対して,IUT が署名検証不合格と判定すること 69

70 公開鍵暗号 :RSA-PSS 署名検証機能試験 (2) 申し込む際に必要な情報 公開鍵 n のビット長 1024, 1536, 2048, 3072, 4096 指数 e のタイプ選択 65537, ランダム 関数の選択 使用するハッシュ関数 SHA-1, SHA-256, SHA-384, SHA-512 マスク生成関数 (MGF) ANSI X9.44 SHA-1, ANSI X9.44 SHA-256, ANSI X9.44 SHA-384, ANSI X9.44 SHA-512 その他 salt のビット長 署名生成と異なる部分 70

71 公開鍵暗号 :RSA-PSS 署名検証機能試験 (3) 質問ファイル抜粋 [BitlengthofModulus] 1024 [Hash] M_Hash_SHA256 [MGF] M_MGF_ANSI944_SHA256 [n] 法 n C E98B59415B D5F79A92FE 48C3E7501C1E D91021D011F4E66A4 1609A80478D D8A7ABEB7CDBD3F9434 DDA680A0078E0B410719FE5CEF0D472CDE9EBB 3E2F527A42E65AFDE0ECA644A86ED6C83CE20D F0ED4F376D6FB E243F40E1282C821F5 7FF2ECA95F633F41849C11261D35 [BitlengthofSalt] 256 [BitlengthofPlaintexts] 1024 [NumberofSignatures] 10 [e] 公開鍵 e 8a c755b4ab205f1dab6cb65bc6ef4a7a26df3524b4f e821c6dd8b5cd6c368f8b9a29c0ec8ca6322f d e1bbf497b6c931f d9b150fa3c54e0144c94b 法 nのビット長 f70b60071fb715a66f14d5c28735ad8a0aa697ee1342b96e73 229cc21e67e8c05ec62b09429c764d5a62ec48734ca1aa1291 ハッシュ関数 :SHA-256 ff83f9 -- 省略 -- MGF:ANSIX9.44SHA-256 [Signatures] 署名 3D99B7D1AA1D0274A8FF64BCEDFAB327D2806E8C A 0C DDB30F2C1F E80D6C182A8DFD6B F A8EF1C4D3A2E6AEB322623D73F62B F13BF92D28E0 324E79B4E1C4B8E5C50DEE55B50D60931CA80CCF6EA9CDBDC5 7B08F657FB13BBFBE2DA86EB8EA3696C5D9892E D C7A8FD -- 省略 -- [Plaintexts] メッセージ 4E DD3DEEFBD767592F70050F253AB3DBA91F4121ACD salt のビット長 90C9990D630A654ED343F94328CBE8594B1A96803DC0579C7D 56FD0DB976984EA529DFE136FDE2AD2DFF6C97657A5EF7664B メッセージ AC46758BF81C96FCF040F89CC5FC192A1DF6F8AC38421B3E0C のビット長 28FFEFD8E49CCFDDD077439A867632E58A25B1DBF1D7CF3071 署名, 0435D2 メッセージの -- 省略 -- 組の数 71

72 暗号モジュールの 暗号アルゴリズム実装試験セミナー 第 3 部 : 擬似乱数生成器 NIST SP Hash_DRBG について 72

73 擬似乱数生成器 承認されたセキュリティ機能 PRNG based on SHA-1 ANSI X Annex C.1 PRNG based on SHA-1 for general purpose in FIPS (+change notice 1) Appendix 3.1 PRNG based on SHA-1 for general purpose in FIPS (+change notice 1) revised Appendix 3.1 Hash_DRBG, CTR_DRBG and OFB_DRBG in ISO/IEC NIST SP800-90(Hash_DRBG, HMAC_DRBG, CTR_DRBG) NIST-Recommended Random Number Generator Based on ANSI X9.31 Appendix A.2.4 Using the 3-key Triple DES and AES Algorithms 2008 年 2 月 18 日に承認 注意事項 JIS X 乱数ビット列生成器 (RBG) RBG 及びその動作モードは,ISO/IEC に適合しなければならない 73

74 擬似乱数生成器 ISO/IEC 適合の取扱い JCMVP 運用ガイダンス, 擬似乱数生成器の仕様 背景 JIS X の細分箇条 には RBG 及びその動作モードは, ISO/IEC に適合しなければなりません と規定されています 質問 ISO/IEC の Hash_DRBG の内部関数 Hashgen() 内の data の取扱いや CTR_DRBG の内部関数 Block_Cipher_df() 内の内部変数 L,N,i の長さの取扱いなど不明確な点が多い そのため, どのように実装したらよいですか? 74

75 擬似乱数生成器 ISO/IEC 適合の取扱い JCMVP 運用ガイダンス, 擬似乱数生成器の仕様 回答 ISO/IEC は ANSI X9.82 の古いドラフト版を元に 2005 年 11 月に作成されていますが, ANSI X9.82 の 2007 年 6 月ドラフト版を元に NIST より SP Recommendation for Random Number Generation Using Deterministic Random Bit Generators (Revised_March 2007) が作成されています そのため, ISO/IEC の不明確な点を詳細に記述した仕様が SP と考えられます そこで, Hash_DRBG と CTR_DRBG に関して ISO/IEC に適合するとは, SP に従ってそれらを実装することと解釈します 補足このガイダンスは JIS X の暗号モジュールセキュリティ要件のみに適用されます 試験用提供物件に規格を明示する場合 ISO/IEC ではなく NIST SP と記載して下さい 75

76 擬似乱数生成器 NIST SP について NIST SP Recommendation for Random Number Generation Using Deterministic Random Bit Generators (Revised) 仕様 擬似乱数生成器 Hash_DRBG HMAC_DRBG CTR_DRBG こちらについて説明 Dual_EC_DRBG JCMVP では承認されていない 76

77 擬似乱数生成器 : DRBG(NIST SP800-90) の基本構成 (1) 基本構成 内部状態擬似乱数を生成するための元データ (Seed 等 ) を格納する エントロピー入力擬似乱数を生成するための Seed を作る元になる nonce エントロピー入力とあわせて Seed を作る元になる その他の入力 additional input reseed 関数及び generate 関数が呼ばれる場合に使用される オプション personalization string DRBG のインスタンスを特徴付ける文字列 関数群 1. Instantiate 関数エントロピー入力から内部状態を生成する 2. Reseed 関数内部状態とエントロピー入力から内部状態を更新する 3. Generate 関数擬似乱数を出力する 4. Uninstantiate 関数内部状態を削除する 5. Health test 関数 DRBG が正しく動いているか診断する 上記 1,2,3 については, それぞれ対応する下位アルゴリズムを呼出す 下位アルゴリズムは Hash_DRBG HMAC_DRBG CTR_DRBG Dual_EC_DRBG のそれぞれで異なる 77

78 擬似乱数生成器 : DRBG(NIST SP800-90) の基本構成 (2) 基本構成 Personalization string Additional input Nonce Entropy Input Instantiate 関数 Instantiate アルゴリズム Reseed 関数 Reseed アルゴリズム Uninstantiate 関数 内部状態 Generate 関数 Generate アルゴリズム Health test 関数エラー状態 DRBG メカニズム Random Bit Generator (RBG) 利用アプリケーション 擬似乱数 78

79 擬似乱数生成器 : Hash_DRBG (NIST SP800-90) (1) 一方向性関数であるハッシュ関数を用いた擬似乱数生成器 使用できるハッシュ関数 SHA-1, SHA-224, SHA-256, SHA-384, SHA-512 条件 SHA-1 SHA-224 SHA-256 SHA-384 SHA-512 サポートされるセキュリティ強度 112, , 128, , 128, 192, , 128, 192, , 128, 192, 256 ハッシュ関数の出力長 (outlen) 要求される最小エントロピー エントロピー入力の長さの最小値 セキュリティ強度と同じ セキュリティ強度と同じ Seed の長さ (seedlen) 一回あたりの最大出力ビット数 <= 2 19 ビット Reseed せずに乱数生成できる回数 <=

80 擬似乱数生成器 : Hash_DRBG (NIST SP800-90) (2) 内部状態 1. 作業状態 V ビット列 ( 長さ :seedlen ビット ) 擬似乱数生成の度に更新される C ビット列 ( 長さ :seedlen ビット ) Instantiate 関数で生成され, Reseed 関数内で更新される reseed_counter 整数 擬似乱数を生成した回数を格納 Reseed 関数を呼出すと 1 に初期化される 2. 管理情報 security_strength セキュリティ強度 prediction_resistance_flag 擬似乱数生成時に, 必要があれば Reseed 関数を呼出せるかどうかのフラグ 80

81 擬似乱数生成器 : Hash_DRBG (NIST SP800-90) (3) 関数の階層構造 Instantiate 関数エントロピー入力を使って内部状態を生成する (a) Instantiate アルゴリズム 入力引数からハッシュ関数を用いて必要な長さのビット列を生成する関数 Reseed 関数内部状態とエントロピー入力から内部状態を 更新する Generate 関数擬似乱数を出力する Uninstantiate 関数内部状態を削除 (c) Reseed アルゴリズム (d) Generate アルゴリズム (b)hash_df (e)hashgen Health Test 関数 DRBG が正しく動いているか診断する Hash 内部状態を使って擬似乱数を生成する 81

82 擬似乱数生成器 :Hash_DRBG (a) Instantiate アルゴリズム (1) Instantiate アルゴリズム Instantiate 関数内で呼出される 初期作業状態を生成する 入力 1. entropy_input エントロピー入力 security_strength 以上のエントロ ピーが必要 2. nonce エントロピー入力とあわせて Seedを作る 3. personalization_string DRBG のインスタンス ( 内部状態 ) を特徴付ける文字列 例えばアプリケーション ID, ユーザ ID など 出力 1. initial_working_state 初期作業状態 V, C, reseed_counter からなる 処理概要次ページ参照 82

83 擬似乱数生成器 :Hash_DRBG (a) Instantiate アルゴリズム (2) Instantiate アルゴリズム 処理概要 entropy_input nonce personalization_string Hash_df C seedlen 8 Hash_df 00 V V seedlen 入力引数からハッシュ関数を用いて必要な長さのビット列を生成する関数 initial_working_state reseed_counter=1 83

84 擬似乱数生成器 :Hash_DRBG (b) Hash_df 関数 (1) Hash_df 関数 Instantiate, Reseed アルゴリズムから呼出される 作業状態の V, C を生成するために使われる 入力 1. input_string ハッシュ関数への入力の一部 2. no_of_bits_to_return 生成したいビット数 出力 1. status 関数の戻り値 2. requested_bits 生成されたビット列 処理概要次頁参照 84

85 擬似乱数生成器 :Hash_DRBG (b) Hash_df 関数 (2) Hash_df 関数 処理概要 no_of_bits_to_return input_string 8-bit 1 1 counter 1 Hash temp 1 Hash temp 2 requested_no_of_bits returned_bits Hash temp Len outlen Len no _ of _ bits _ to _ outlen return 85

86 擬似乱数生成器 :Hash_DRBG (c) Reseed アルゴリズム (1) Reseed アルゴリズム Reseed 関数内で呼出される 現在の作業状態から新しい作業状態を生成する 入力 1. working_state 作業状態 V, C, reseed_counter からなる 2. entropy_input エントロピー入力 3. additional_input DRBGを利用するアプリケーションから渡される オプション 出力 1. new_working_state 新しい作業状態 V, C, reseed_counter を含む 処理概要次頁参照 86

87 擬似乱数生成器 :Hash_DRBG (c) Reseed アルゴリズム (2) Reseed アルゴリズム 処理概要 seedlen C seedlen V working_state reseed_counter 01 V entropy_input additional_input Hash_df C 8-bit Hash_df 00 seed V new_working_state reseed_counter=1 入力引数からハッシュ関数を用いて必要な長さのビット列を生成する関数 seedlen seedlen 87

88 擬似乱数生成器 :Hash_DRBG (d) Generate アルゴリズム (1) Generate アルゴリズム Generate 関数内で呼出される 擬似乱数を生成する 入力 1. working state 作業状態 V, C, reseed_counterからなる 2. requested_number_of_bits 出力したい擬似乱数のビット数 3. additional_input DRBGを利用するアプリケーションから渡される文字列 オプション 出力 1. status 関数の戻り値 成功, 又はReseedが必要な場合にはその旨が, 報告される 2. returned_bits 生成された擬似乱数 3. new_working_state 擬似乱数を生成した後の新しい作業状態 処理概要次頁参照 88

89 擬似乱数生成器 :Hash_DRBG (d) Generate アルゴリズム (2) Generate アルゴリズム 青色枠 additional_input のない場合, この処理は行わない 赤色枠 V, reseed_counter の更新処理 C は, Generate アルゴリズムでは更新されない Hashgen 関数擬似乱数を生成する部分 記号 : 桁上がりのある XOR 足算 Hashgen returned_bits C C V Hash status: reseed_counter>=reseed_interval ならば Reseed 関数呼出しが必要 working_state reseed_counter 02 V additional_input V C V reseed_counter new_working_state reseed_counter 03 V Hash 1 89

90 擬似乱数生成器 :Hash_DRBG (e) Hashgen 関数 Hashgen 関数 V を使って擬似乱数を生成する 入力 1. requested_no_of_bits 出力したい擬似乱数のビット数 2. V 現在の作業状態の V が編集される 出力 1. returned_bits 出力されたビット列 そのまま擬似乱数生成器の出 力になる 処理概要右図参照 V Hash 1 Hash 1 1 m Hash requested _ no _ of outlen _ bits w 1 w 2 requested_no_of_bits returned_bits w m 90

91 擬似乱数生成器 : JCATT の対応状況 NIST SP に記載の擬似乱数生成器 現在 JCATT では, 試験できない JCATT が対応出来るまでは, ベンダ自己確認 ベンダ自己確認とするために NIST SP のテストベクタ 内部状態に関する記述なし (217KB) ectors.zip 内部状態に関する記述あり (13MB) All.pdf 内容 Hash_DRBG HMAC_DRBG CTR_DRBG Dual_EC_DRBG JCMVP では承認されていません 91

92 NIST SP をベンダ自己確認とする際のガイダンス (1) NIST SP の次の各章の要求事項に, 実装が準拠していることをベンダが確認しなければならない 9 章 DRBG Mechanism Functions アルゴリズムの外側の関数 10 章 DRBG Algorithm Specifications アルゴリズム 11 章 Assurance 文書化要求事項 セキュリティ強度 エントロピー入力の取得方法 ヘルステスト既知解テスト (Instantiate, Reseed, Generate, Uninstantiate) 暗号アルゴリズム以外の部分についても一読を 92

93 NIST SP をベンダ自己確認とする際のガイダンス (2) ベンダ情報要件ベンダは, 試験対象実装が上記の章に記載の要求事項を完全かつ正確に実装している証拠資料を提供しなれければならない 試験手順要件試験者は, 証拠資料をレビューし, 試験対象実装が上記の仕様に準拠していることを確認しなければならない これは, 文書レビュー及びソースコードレビューによって行われなければならない 93

94 ご清聴有難うございました お問い合わせは までお願い致します JCMVP ホームページ 94

95 暗号モジュールの 暗号アルゴリズム実装試験セミナー 参考資料 95

96 DSA: 暗号アルゴリズム実装試験判定基準 ドメインパラメータ生成機能試験 IUT が生成した SEED および counter を JCATT に入力し,JCATT は FIPS Appendix 2 のアルゴリズムに従って 2 つの素数 p,q を計算する この p,q と,IUT が生成した p,q がそれぞれ等しいこと g q 1 mod p であること IUT が生成した複数のドメインパラメータ (p; q; g) が全て異なるものであること ドメインパラメータ検証機能試験 JCATT が与えたドメインパラメータ生成機能に対する試験に適合するようなドメインパラメータに対して,IUT が 合格 と判定すること JCATT が与えたドメインパラメータ生成機能に対する試験に違反するようなドメインパラメータに対して,IUT が 不正 と判定すること 鍵ペア生成機能試験 y g x mod p であること 1 < x < q - 1, 2 < y < p - 2 であること y q 1 mod p であること IUT が生成した複数の鍵ペアが全て異なるものであること IUT: Implementation Under Test, 試験対象実装 96

97 DSA: 暗号アルゴリズム実装試験判定基準 署名生成機能試験 JCATT が与えたプライベート鍵 x および平文に対して,IUT が生成した署名を,JCATT が署名検証した時に署名検証合格となること 同じ平文, 同じプライベート鍵に対して複数署名を生成させた時,IUT が同じ署名を生成しないこと 署名検証機能試験 JCATT が与えた正しい公開鍵 y, 平文および署名, ならびに指定されたハッシュ関数に対して,IUT が正しく署名検証合格と判定すること JCATT が改竄した平文, 署名, または公開鍵に対して,IUT が署名検証不合格と判定すること 97

98 暗号アルゴリズム確認書サンプル 98

99 AES:SubBytes の処理 128 ビットのデータを 1 バイト (8 ビット ) ごとに 16 のサブブロックに分割 各ブロックでは 1 バイトの入力データを 1 バイトの出力データへ置換 S 0,0 S 0,1 S 1,0 S 0,3 S 1,1 S r, c S 2,0 S 1,3 S 2,1 S 3,0 S 2,3 S 3,1 S 0,2 S 1,2 S 2,2 S 3,2 S 3,3 S-Box FIPS-197 Figure 7 S 0,0 S 0,1 S 1,0 S 0,3 S 1,1 S r, c S 2,0 S 1,3 S 2,1 S 3,0 S 2,3 S 3,1 S 0,2 S 1,2 S 2,2 S 3,2 S 3,3 99

100 AES:ShiftRows の処理 4 ブロックを 1 行として, 行ごとに左シフト処理 S 0,0 S 0,1 S 1,0 S 0,3 S 1,1 S 2,0 S 1,3 S 2,1 S 3,0 S 2,3 S 3,1 S 0,2 S 1,2 S 2,2 S 3,2 S 3,3 シフトなし左に1つシフト左に2つシフト左に3つシフト S 0,0 S 0,1 S 1,1 S 0,3 S 1,2 S 2,2 S 1,0 S 2,3 S 3,3 S 2,1 S 3,0 S 0,2 S 1,3 S 2,0 S 3,1 S 3,2 100

101 AES:MixColums の処理 4 ブロックを 1 列として, 列ごとに列ベクトルの変換 S 0,c S 0,c S 1,c S 2,c = S 1,c S 2,c S 3,c S 3,c S 0,0 S 0,c 0,1 S 1,c 1,1 S 2,c 2,1 S 1,0 S 0,3 S 2,0 S 1,3 S 3,1 3,c S 0,2 S 1,2 S 2,2 S 3,0 S 2,3 S 3,2 S 3,3 S 0,0 S S 0,c 0,1 S S 1,c 1,1 S S 2,c 2,1 S 1,0 S 0,3 S 2,0 S 1,3 S 3,1 3,c S 0,2 S 1,2 S 2,2 S 3,0 S 2,3 S 3,2 S 3,3 101

102 AES:AddRoundKey の処理 4 ブロックを 1 列として, 列ごとに拡大鍵と XOR 処理 W L W L+c L=round*Nb W l+1 W L+2 W L+3 XOR S 0,0 S 0,c 0,1 S 1,c 1,1 S 2,c 2,1 S 1,0 S 0,3 S 2,0 S 1,3 S 3,1 3,c S 0,2 S 1,2 S 2,2 S 3,0 S 2,3 S 3,2 S 3,3 S 0,0 S S 0,c 0,1 S S 1,c 1,1 S S 2,c 2,1 S 1,0 S 0,3 S 2,0 S 1,3 S 3,1 3,c S 0,2 S 1,2 S 2,2 S 3,0 S 2,3 S 3,2 S 3,3 102

103 AES:InvShiftRows の処理 4 ブロックを 1 行として, 行ごとに右シフト処理 S 0,0 S 0,1 S 1,0 S 0,3 S 1,1 S 2,0 S 1,3 S 2,1 S 3,0 S 2,3 S 3,1 S 0,2 S 1,2 S 2,2 S 3,2 S 3,3 シフトなし右に1つシフト右に2つシフト右に3つシフト S 0,0 S 0,1 S 1,3 S 0,3 S 1,0 S 2,2 S 1,2 S 2,3 S 3,1 S 2,1 S 3,2 S 0,2 S 1,1 S 2,0 S 3,3 S 3,0 103

104 AES:InvSubBytes の処理 128 ビットのデータを 1 バイト (8 ビット ) ごとに 16 のサブブロックに分割 各ブロックでは 1 バイトの入力データを 1 バイトの出力データへ置換 S 0,0 S 0,1 S 1,0 S 0,3 S 1,1 S r, c S 2,0 S 1,3 S 2,1 S 3,0 S 2,3 S 3,1 S 0,2 S 1,2 S 2,2 S 3,2 S 3,3 S-Box FIPS-197 Figure 14 S 0,0 S 0,1 S 1,0 S 0,3 S 1,1 S r, c S 2,0 S 1,3 S 2,1 S 3,0 S 2,3 S 3,1 S 0,2 S 1,2 S 2,2 S 3,2 S 3,3 104

105 AES:InvMixColumns の処理 4 ブロックを 1 列として, 列ごとに列ベクトルの変換 S 0,c 0e 0b 0d 09 S 0,c S 1,c S 2,c = 09 0e 0b 0d 0d 09 0e 0b S 1,c S 2,c S 3,c 0b 0d 09 0e S 3,c S 0,0 S 0,c 0,1 S 1,c 1,1 S 2,c 2,1 S 1,0 S 0,3 S 2,0 S 1,3 S 3,1 3,c S 0,2 S 1,2 S 2,2 S 3,0 S 2,3 S 3,2 S 3,3 S 0,0 S S 0,c 0,1 S S 1,c 1,1 S S 2,c 2,1 S 1,0 S 0,3 S 2,0 S 1,3 S 3,1 3,c S 0,2 S 1,2 S 2,2 S 3,0 S 2,3 S 3,2 S 3,3 105