GPGPUによる RSA 暗 号 ふるいの 性 能 評 価 2011 年 6 月 20 日 後 保 範 ( 早 稲 田 大 学 ) 1
目 次 1. はじめに 2. ふるい 法 3. ふるい 処 理 4. GPUにおけるふるい 処 理 5. ふるい 処 理 高 速 化 の 評 価 法 6. ふるい 測 定 結 果 の 比 較 7. GNFSふるいでの 考 察 8. おわりに 2
1. はじめに (1) 現 在 の 暗 号 (RSA 暗 号 )や 認 証 システム は 多 数 桁 数 (1024ビット,10 進 309 桁 )の 因 数 分 解 の 困 難 さを 利 用 している (2) 現 在 の 多 数 桁 数 の 因 数 分 解 の 世 界 記 録 は RSA-768(10 進 232 桁 ) 2010 年 1 月 NTTを 含 め5カ 国 共 同 GNFSを 使 用 (3) 暗 号 の2010 年 問 題 :RSA 暗 号 を 含 む 現 在 の 暗 号 システムの 変 更 が 必 要 3
1.1 暗 号 化 方 式 (1) 公 開 鍵 暗 号 方 式 ( 非 対 称 鍵 ) 公 開 鍵 で 暗 号 化 秘 密 鍵 で 復 号 化 認 証 やネットワーク 通 信 に 都 合 が 良 い RSA 暗 号 : 多 数 桁 数 因 数 分 解 の 難 しさを 利 用 (2) 秘 密 鍵 暗 号 方 式 ( 共 通 鍵 対 称 鍵 ) 暗 号 化 と 復 号 化 で 共 通 の 秘 密 鍵 を 使 用 代 表 暗 号 例 :AES, RC4(Netscape ) 4
1.2 インターネットの 暗 号 例 暗 号 化 なし(http) 暗 号 化 あり(https) 5
1.3 RSA 暗 号 の 仕 組 み RSA 暗 号 鍵 の 作 成 ( 数 学 的 な 方 法 ) (1) ランダムに 素 数 p, qを 選 ぶ (2) n = p q 及 びf = (p-1) (q-1)を 計 算 (3) 素 数 eを 選 ぶ (4) d = 1/e (mod f)となるdを 計 算 する (e,n)が 公 開 暗 号 化 鍵 (d,n)が 復 号 鍵 となる 6
1.4 RSA 暗 号 化 と 復 号 化 RSA 暗 号 化 (1) 情 報 をn 以 下 の 数 Mに 変 換 ( 公 開 方 法 ) (2) C=M e (mod n)で 暗 号 Cを 作 成 RSA 復 号 化 (n=pxq,f=(p-1)x(q-1)) オイラーの 定 理 (M f 1 (mod n)) (1) M=C d (mod n)で 元 の 数 Mに 復 号 (2) 数 Mを 元 の 情 報 に 変 換 ( 公 開 方 法 ) 7
1.5 因 数 分 解 の 方 法 (1) ふるい(Sieve) 系 解 法 計 算 量 は 合 成 数 の 桁 数 に 依 存 RSA 暗 号 の 解 読 に 都 合 が 良 い MPQS GNFSが 代 表 的 解 法 (2) 楕 円 曲 線 法 (Elliptic Curve Method, ECM) 計 算 量 は 小 さい 因 数 の 桁 数 に 依 存 RSA 暗 号 の 解 読 には 不 向 き 8
2. ふるい 法 (1) A 2 -B 2 =(A-B)(A+B) 0 (mod N)の 関 係 を 使 用 し Nを 因 数 分 解 (2) A 1 l1 A 2 l2 A k lk B 1 m1 B 2 m2 B j mj (mod N) なる 関 係 を 基 底 の 数 より 多 く 集 める (3) 0-1 行 列 を 計 算 し 両 辺 が 平 方 になるもの ( 従 属 関 係 )のデータを 探 す (4) MPQS,GNFS 等 が 代 表 的 なふるい 法 9
2.1 代 表 的 なふるい 法 (1) QS (Quadratic Sieve 2 次 ふるい 法 ) MPQS (Multiple Polynomial QS, 複 数 多 項 式 2 次 ふるい 法 )が 代 表 的 解 法 100 桁 以 下 ではGNFSより 高 速 な 解 法 (2) GNFS (General Number Field Sieve 一 般 数 体 ふるい 法 ) 現 在 100 桁 程 度 以 上 で 最 も 高 速 な 解 法 と 言 われている 10
2.2 QS(2 次 ふるい 法 ) (1) QS (Quadratic Sieve, 2 次 ふるい 法 ) Nを 分 解 XはN 1/2 に 最 も 近 い 整 数 (X+k) 2 - N=A k, k=0,1,2, 素 数 基 底 で 分 解 できるA k を 集 める (2) MPQS (Multiple Polynomial QS) 複 数 の2 次 多 項 式 を 使 用 代 表 例 : d 2 -N 0 (mod c)なる(c,d)の 組 で (c x+d) 2 -N=c f(x) と 変 換 しf(x)を 分 解 11
2.3 NFS( 数 体 ふるい 法 ) (1) 分 解 の 違 いを 利 用 (SNFS, 特 殊 数 体 ふるい 法 ) Nを 分 解 f(m) 0 (mod N)なる 多 項 式 f(x)=0の 根 の 一 つをθとする a+bmを 素 数 基 底 で 分 解 a+bθを 生 成 元 ( 素 元 と 単 元 )で 分 解 (2) N=1333の 例 (f(x)=x 3 +2, M=11, θ 3 =-2) 2+M=13, 2+θ=θ(1-θ)(1+θ)=θ-θ 3-10 11 12 13 (mod N) 12
2.4 GNFS( 一 般 数 体 ふるい 法 ) (1) SNFS GNFS f(x) (x-s)g(x) (mod p) 一 般 には 素 元 が 求 まらない 素 元 の 代 わりに 素 イデアルを 使 用 問 題 点 : 平 方 の 形 が 明 示 的 に 現 れない イデアルの 積 が 平 方 となるようにする (2) GNFSで 新 たに 必 要 なこと (a) 平 方 剰 余 の 追 加 : 平 方 の 確 率 を 高 める (b) イデアルの 平 方 根 ( 代 数 平 方 根 )を 求 める 13
3. ふるい 処 理 ( 多 数 桁 因 数 分 解 の) ふるい 用 4~7 次 関 数 の 探 査 (GNFSだけ) 分 解 基 底 ( 素 数 素 イデアル)の 選 定 ふるい 処 理 で 基 底 数 以 上 のデータ 収 集 基 底 ベキを 要 素 とする 行 列 ( 基 底 数 xデータ 数 ) 作 成 基 底 ベキを(mod 2)して0-1 行 列 に 変 更 0-1 行 列 から 従 属 となる 行 (データ)を 計 算 代 数 平 方 根 の 計 算 (GNFSだけ) A 2 - B 2 0 (mod N)を 構 成 し 因 数 分 解 14
3.1 RSA-768(232 桁 )の 計 算 時 間 項 目 台 数 年 比 率 (%) ふるい 処 理 1500 90 0-1 行 列 計 算 155 9 利 用 関 数 の 探 査 20 1 代 数 平 方 根 の 計 算 1 0 その 他 1 0 注 ) AMD64 (2.2Ghz, 1コア 換 算 ) 行 列 サイズ:192,796,550 * 192,795,550 15
3.2 ふるいプログラム( 中 心 部 ) for (k=0; k<n; k++) : 基 底 の 素 数 の 数 { for (i=start[k]; i<lp; i+=prime[k]) { V[i] += LogP[k]; } : 元 は 乗 算 ( 対 数 化 で 加 算 ) } LPは 一 回 のふるいサイズ for (i=0; i<lp; i++) : ふるいデータの 採 取 { if(v[i] >= PS[i]) { Sive[No] = Pointer + i; No++; } } Noはふるいで 得 られたデータの 数 次 のふるいのためStart[0]~Start[N-1]を 更 新 16
4. ふるい 処 理 の 特 徴 PC(キャッシュ 処 理 のパソコン) 高 速 化 のためにはキャッシュ 内 処 理 が 必 須 LPのサイズはGPUより 約 千 倍 短 い 少 し 大 きな 素 数 ( 基 底 )ではLPをはみ 出 す GPU(GTX480) LPのサイズはPCの 約 千 倍 長 く 取 れる 本 質 的 に 非 連 続 アクセスで 連 続 化 は 不 可 注 ) LP: 1 回 のふるい 処 理 での 配 列 長 17
4.1 GPUプログラム( 対 策 前 ) no = gn*bn; bn=512, gn=40を 使 用 for (k=0; k<lp; k+= no) LP=250*1024 2 を 使 用 { i = (bn * blockidx.x + threadidx.x) + k; V[i] = 0; } Vの 初 期 化 syncthreads(); for (k=0; k<n; k++) 区 間 LPで20480 並 列 { for (i=start[k]; i<lp; i+=prime[k]*no) { ii = (bn*blockidx.x+threadidx.x)*prime[k]+i; if(ii < LP) V[ii] += LogP[k]; } syncthreads(); } 18
4.2 GPU 並 列 化 問 題 点 LPのサイズはPCに 比 較 して 約 1000 倍 大 きく できるが 20480のスレッドで 並 列 化 すると 1スレッド 当 たりではPCよりLPは 小 さくなる このためk 番 目 の 素 数 の 値 Prime[k]が 大 きく なると iiはprime[k]のスレッド 倍 より 大 きくな り 下 記 のif 文 は 空 振 りが 多 くなる if(ii < LP) V[ii] += LogP[k]; 19
4.3 GPU 並 列 化 対 策 スレッド 並 列 化 を 区 間 LPから 上 位 のN 個 の 素 数 に 変 更 する データの 依 存 性 が 発 生 し V[ii]+=LogP[k]; の 加 算 処 理 が 正 しく 動 作 しない ふるい 処 理 (1/1000 以 下 のふるいデータの 取 得 漏 れはOK)なら 許 される 並 列 化 N 個 の 素 数 を3 区 分 ( 小 中 大 - 特 大 )に 分 けて 異 なるスレッド 並 列 化 を 行 う 20
4.4 GPUプログラム( 対 策 後 ) for (k=0; k<n1; k++) 1~5120(5K) 番 素 数 のふるい { for (i=start[k]; i<lp; i+=prime[k]*gn*bn) { ii = (bn*blockidx.x + threadidx.x)*prime[k] + i; if(ii < LP) V[ii] += LogP[k]; syncthreads(); } } for (k=n1; k<n2; k+=gn) 5K+1~40K 番 素 数 のふるい { kk = blockidx.x + k; for (i=start[kk]; i<lp; i+=prime[kk]*bn) { ii = threadidx.x*prime[k] + i; if(ii < LP) V[ii] += LogP[kk]; syncthreads(); } } for (k=n2; k<n; k+=gn*bn) 40K+1 番 素 数 以 降 のふるい { kk =(bn*blockidx.x + threadidx.x) + k; for (i=start[kk]; i<lp; i+=prime[kk]) { if(i < LP) V[i] += LogP[kk]; syncthreads(); } } 21
5. ふるい 処 理 高 速 化 の 評 価 法 10 進 m 桁 からの 値 を 小 さい 方 からN 個 の 素 数 基 底 でのふるい 処 理 で 評 価 MPQS: 平 方 剰 余 となる 素 数 を 基 底 に 使 用 ( 半 分 ) GNFS:イデアル 分 解 ( 処 理 の 基 本 は 素 数 基 底 と 同 じ)と10 進 s 桁 程 度 の 素 数 基 底 分 解 ふるいでN 個 のデータが 得 られるまでの 時 間 を 測 定 通 常 のふるい 処 理 では 同 じ 素 数 (イデアル)のデー タが2 件 得 られたら 基 底 に 追 加 し 処 理 を 短 縮 評 価 を 単 純 化 するため 基 底 の 追 加 はしない 22
5.1 並 列 化 対 策 によるふるい 採 取 データ 数 の 変 動 10 進 60 桁 LP=250*1024 2 利 用 素 数 の 数 N=10000*1024 反 復 数 =5000で 測 定 ふるいで 採 取 されたデータ 数 (M) (1) 未 対 策 : M=448425 (2) 並 列 化 対 策 後 (12 回 測 定 ) NAS2011 2011/6/20~6/22 M=[448338, 448367], 平 均 M=448350 未 対 策 との 最 大 差 M= 87 = 0.02% 23
6. ふるい 測 定 結 果 の 比 較 PC(1コア)とGPU(1 台 )で 比 較 PC Dell Vostro 200 (Intel Core 2, 2.33Ghz, 2GB) Windows Vista, gcc, -O3オプション GPU NVIDIA GeForce GTX580 (1.544hz, 1.5GB) Unix, CUDA 3.2, -O3オプション 24
6.1 ふるい 対 策 効 果 (10 進 45 桁 ) 25
6.2 ふるい 計 算 時 間 (10 進 45 桁 ) 26
6.3 ふるい 計 算 時 間 (10 進 60 桁 ) 27
6.4 ふるいの 性 能 比 較 NAS2011 2011/6/20~6/22 28
7. GNFSふるいでの 考 察 GPUではPCより 最 速 となる 基 底 の 素 数 ( 素 イデア ル)の 数 は5~10 倍 多 く 使 用 できる GNFSのふるいは 素 数 と 素 イデアルの 両 基 底 で 共 に 分 解 できるものを 採 取 する GNFSでは 数 値 実 験 (MPQSを 想 定 )よりGPUがPC に 比 較 して 更 に 有 利 になる 可 能 性 大 ( 基 底 だけ 大 きく) 素 数 ふるい 素 イデアルふるい 採 取 データ 100,000,000 100,000,000 100,000 200,000,000 200,000,000 400,000 400,000,000 400,000,000 1,600,000 29
8. おわりに ふるい 処 理 においてGPU(GXT580)の 性 能 は PC(2.33Ghz)の5 倍 ~60 倍 程 度 GPUの 性 能 は140 桁 のMPQSで 約 40 倍 RSA 暗 号 解 読 の 規 模 で 約 60 倍 と 推 定 される GNFSでは GPUの 効 果 はより 大 きいと 予 想 スレッド 並 列 化 は 基 底 の 素 数 の 大 きさで3 段 階 に 分 け 大 きい 素 数 は 素 数 で 並 列 化 対 策 後 は データ 依 存 性 で 約 0.02%の 採 取 不 足 があるが ふるい 処 理 では 十 分 である 30
謝 辞 GPU (NVIDIA GeForce GTX580)の 利 用 環 境 をご 用 意 頂 いた 筑 波 大 学 長 谷 川 秀 彦 教 授 に 謹 んで 感 謝 の 意 を 表 します 31