現代暗号 volume2 t-matsu
暗号アルゴリズムの 高速化
素数判定 暗号の世界では素数が重要である 素数の探し方として以下がある 試し割り エラトステネスのふるい フェルマーテスト AKS素数判定法 𝑎 𝑛−1 ≠1 𝑚𝑜𝑑 𝑛 の場合𝑛は合成数と判定 AKS素数判定法 (𝑋+𝑎) 𝑛 ≠ 𝑋 𝑛 +𝑎 𝑚𝑜𝑑 𝑛 の場合𝑛は合成数と判定
ユークリッドの互除法 2つの整数 𝑎 0 , 𝑎 1 の最大公約数gcd( 𝑎 0 , 𝑎 1 ) を求めるアルゴリズム 𝑎 0 =21, 𝑎 1 =12とする 𝑎 0 > 𝑎 1 なので, 𝑎 0 % 𝑎 1 =21%12=9 ( 𝑎 0 =9, 𝑎 1 =12) 𝑎 0 < 𝑎 1 なので, 𝑎 1 % 𝑎 0 =12%9=3 ( 𝑎 0 =9, 𝑎 1 =3) 𝑎 0 > 𝑎 1 なので, 𝑎 0 % 𝑎 1 =0 gcd( 𝑎 0 , 𝑎 1 )=3
拡張ユークリッドの互除法 整数 𝑚, 𝑛 の最大を gcd 𝑚,𝑛 と表すときに, 拡張ユークリッドの互除法を用いて, 𝑎𝑚 + 𝑏𝑛 = gcd(𝑚, 𝑛) の解となる整数 𝑎, 𝑏 の組を見つけることができる 特に、𝑚, 𝑛 が互いに素 最大公約数が 1 である場合, 𝑎𝑚 + 𝑏𝑛 = 𝑐 は任意の整数 𝑐 に対して整数解 (𝑎, 𝑏) をもつ
拡張ユークリッドの互除法 gcd(𝑎 0, 𝑎 1 ) =𝑎 0 𝑥 + 𝑎 1 𝑦となる整数𝑥,𝑦を求めるアルゴリズム 𝑎 0 =10, 𝑎 1 =7とする (𝑥 0 , 𝑦 0 )= 1,0 , 𝑥 1 , 𝑦 1 = 0,1 とする 𝑎 0 ÷ 𝑎 1 =1= 𝑞 2 , 𝑎 0 % 𝑎 1 = 3=𝑎 2 (𝑥 2 , 𝑦 2 )= 𝑥 0 , 𝑦 0 − 𝑞 2 × 𝑥 1 , 𝑦 1 =(1,−1) 𝑎 1 ÷ 𝑎 2 =2= 𝑞 3 , 𝑎 1 % 𝑎 2 =1= 𝑎 3 (𝑥 3 , 𝑦 3 )= 𝑥 1 , 𝑦 1 − 𝑞 3 × 𝑥 2 , 𝑦 2 =(−2,3) 𝑎 2 ÷ 𝑎 3 =3= 𝑞 4 , 𝑎 2 % 𝑎 3 =0= 𝑎 4 (終了条件 𝑎 𝑖 =0) gcd 10,7 = 𝑎 3 =1=10 𝑥 2 +7 𝑦 2 =10× −2 +7×3
𝑒𝑑=1 𝑚𝑜𝑑 𝑝への適用 (𝑝,𝑒)を拡張ユークリッドの互除法に適用すると 𝑝𝑥+𝑒𝑦=1となる整数 𝑥,𝑦 が求められる これは𝑒𝑦=1 𝑚𝑜𝑑 𝑝となる𝑦である 𝑦>0なら𝑦が答え𝑦<0なら𝑝−𝑦が答えになる
多人数公開鍵暗号
1対𝑛の暗号方式 秘密分散共有法 放送型暗号(ブロードキャスト暗号)
秘密分散共有法 𝑛人のうち,任意の𝑘人が集まると秘密𝑠を復元できるが, どの𝑘−1人が集まっても𝑠を復元できない手法 ディーラ𝐷と𝑛人の参加者 𝑃 𝑖 からなる 𝐷は秘密𝑠を𝑛個のシェア 𝑣 𝑖 に符号化し, 𝑣 𝑖 を 𝑃 𝑖 に与える (分散段階) 𝑛人の参加者のうち𝑘人が集まり𝑠を復元する (再構成段階) (𝑘,𝑛)閾値秘密分散共有法(閾値法)と呼ぶ
(2,𝑛)閾値秘密分散共有法 𝐷は𝑓 𝑥 =𝑎𝑥+𝑠を決める 𝑓 0 =𝑠を秘密情報とする 𝐷は𝑛人の参加者 𝑃 𝑖 に 𝑖,𝑓 𝑥 の点情報を与える 参加者は2人以上の情報 2点 で 𝑓 𝑥 =𝑎𝑥+𝑠を求める 𝑠=𝑓 0 を取り出す
𝑓 𝑥 =𝑠+ 𝑎 1 𝑥+ 𝑎 2 𝑥 2 +…+ 𝑎 𝑘−1 𝑥 𝑘−1 𝑚𝑜𝑑 𝑝を選ぶ (𝑘,𝑛)閾値秘密分散共有法 𝐷は𝑝>max(𝑠,𝑛)となる素数𝑝を決める 𝐷は𝑓 0 =𝑠となる𝐺𝐹 𝑝 上の高々𝑘−1次多項式 𝑓 𝑥 =𝑠+ 𝑎 1 𝑥+ 𝑎 2 𝑥 2 +…+ 𝑎 𝑘−1 𝑥 𝑘−1 𝑚𝑜𝑑 𝑝を選ぶ 𝐷は 𝑣 𝑖 =𝑓 𝑖 𝑚𝑜𝑑 𝑝を計算し,シェア 𝑣 𝑖 を 𝑃 𝑖 に与える (分散段階) 参加者は𝑘人以上の情報 𝑘点 で𝑓 𝑥 を求める 𝑠=𝑓 0 を取り出す (再構成段階)
ラグランジュ補間 𝑘個の点で𝑘−1次多項式を復元する手法 𝑓 𝑥 = 𝜆 1 𝑥 𝑓 𝑖 1 +…+ 𝜆 𝑘 𝑥 𝑓 𝑖 𝑘 𝑚𝑜𝑑 𝑝 𝑓 𝑥 = 𝜆 1 𝑥 𝑓 𝑖 1 +…+ 𝜆 𝑘 𝑥 𝑓 𝑖 𝑘 𝑚𝑜𝑑 𝑝 このとき 𝜆 𝑗 𝑥 = 𝑥− 𝑖 1 ×…×(𝑥− 𝑖 𝑘 ) 𝑖 𝑗 − 𝑖 1 ×…×( 𝑖 𝑗 − 𝑖 𝑘 ) 𝑚𝑜𝑑 𝑝 𝑘≠𝑗 𝑠=𝑓 0 = 𝜆 1 0 𝑓 𝑖 1 +…+ 𝜆 𝑘 0 𝑓 𝑖 𝑘 で𝑠が求まる
ラグランジュ補間を実装してみる 𝑍 23 上の点 0,8 , 1,3 , 5,14 , 8,5 , 11,5 の5点を通る 𝑓 𝑥 = 𝑎 0 𝑥 4 + 𝑎 1 𝑥 3 + 𝑎 2 𝑥 2 + 𝑎 3 𝑥+ 𝑎 4 を求め,𝑓(2)と𝑓(3)の値を求めよ
ラグランジュ補間を実装してみる 𝑓 𝑥 = 9 𝑥 4 +20 𝑥 3 +20 𝑥 2 +15𝑥+8 𝑎 0 =9, 𝑎 1 =20, 𝑎 2 =20, 𝑎 3 =15, 𝑎 4 =8 ※係数はガウスの消去法で求められる ラグランジュ補間を使用すると 𝑓(2)=8 𝑓(3)=7 が得られる
放送型暗号(ブロードキャスト暗号) 送信者が秘密情報𝑠を暗号化したデータの送信 (同報通信)を1度だけ行う 受信者のうち,復号を許可されている 鍵を持っている 受信者𝑛人のみが復号できる このとき,𝑛人の鍵は皆異なるが復号される𝑠は同一になる ※ B-CASのイメージ (厳密にはB-CASは放送型暗号に含まれない)
代数的な方法 準備 素数𝑝と𝐺𝐹 𝑝 の原始元𝑔を選ぶ (𝑝は公開しておく) 送信者は 𝑍 𝑝 上の多項式 𝑓 𝑥 = 𝑎 0 + 𝑎 1 𝑥+ 𝑎 2 𝑥 2 +…+ 𝑎 𝑘 𝑥 𝑘 を選ぶ. 送信者は以下の値を計算する 𝑦 0 = 𝑔 𝑎 0 , 𝑦 1 = 𝑔 𝑎 1 ,…, 𝑦 𝑘 = 𝑔 𝑎 𝑘 受信者 𝑈 𝑖 に𝑓 𝑥 上の点 𝛼 𝑖 ,𝑓 𝛼 𝑖 を安全に配布する 𝛼 𝑖 ,𝑓 𝛼 𝑖 は 𝑈 𝑖 の復号鍵になる
代数的な方法 暗号化 送信者は𝐺𝐹 𝑝 上のメッセージ𝑀を暗号化する鍵 𝑠∈𝐺𝐹 𝑝 を選び,𝑀を𝑠で暗号化する 𝐶=𝐸𝑛𝑐(𝑠,𝑀) 以下のヘッダ𝐻を作成する 𝐻=ℎ 𝑠,𝑟 = 𝑔 𝑟 ,𝑠 𝑦 0 𝑟 , 𝑦 1 𝑟 ,…, 𝑦 𝑘 𝑟 𝑟∈𝐺𝐹 𝑝 はランダムに選ぶ 𝐻と𝐶を送信する
代数的な方法 復号化 受信者𝑖は自身の秘密鍵 𝛼 𝑖 ,𝑓 𝛼 𝑖 を用いて 以下の計算をして𝑠を得る 受信者𝑖は自身の秘密鍵 𝛼 𝑖 ,𝑓 𝛼 𝑖 を用いて 以下の計算をして𝑠を得る 𝑠= 𝑠 𝑦 0 𝑟 × 𝑗=1 𝑘 ( 𝑦 𝑗 𝑟 ) 𝛼 𝑖 𝑗 / ( 𝑔 𝑟 ) 𝑓( 𝛼 𝑖 ) を計算する 𝑠で𝐶を復号化して𝑀を得る
代数的な方法 証明 𝑠 𝑦 0 𝑟 × 𝑗=1 𝑘 ( 𝑦 𝑗 𝑟 ) 𝛼 𝑖 𝑗 / ( 𝑔 𝑟 ) 𝑓( 𝛼 𝑖 ) ={𝑠 𝑦 0 𝑟 ×( 𝑦 1 𝑟 ) 𝛼 𝑖 ×…×( 𝑦 𝑘 𝑟 ) 𝑎 𝑖 𝑘 }/ ( 𝑔 𝑟 ) 𝑓( 𝛼 𝑖 ) = 𝑠 𝑔 𝑎 0 𝑟 × 𝑔 𝑎 1 𝑟 𝛼 𝑖 ×… ×𝑔 𝑎 𝑘 𝑟 𝛼 𝑖 𝑘 /( 𝑔 𝑟 ) 𝑓( 𝛼 𝑖 ) ={𝑠 𝑔 𝑟 𝑎 0 + 𝑎 1 𝛼 𝑖 +…+ 𝑎 𝑘 𝛼 𝑖 𝑘 } /( 𝑔 𝑟 ) 𝑓( 𝛼 𝑖 ) =𝑠 ( 𝑔 𝑟 ) 𝑓( 𝛼 𝑖 ) / ( 𝑔 𝑟 ) 𝑓( 𝛼 𝑖 ) =𝑠
ブロードキャスト暗号の種類 共通鍵ブロードキャスト暗号 公開鍵ブロードキャスト暗号
公開鍵ブロードキャスト暗号 BGW方式 -2005年 AHBE(Ad Hoc Broadcast Encryption)-2010年 全体を管理するセンタが鍵の生成管理を行う AHBE(Ad Hoc Broadcast Encryption)-2010年 送信者受信者ともにシステム全体の人数とそれぞれ の公開鍵を保持する必要がある CBE(Contributory Broadcast Encryption)-2011年 構成員がかわるたびに秘密鍵と公開鍵を更新する必 要がある
IPマルチキャスト暗号の要件 受信できるメッセージは,すべての受信者において同一であ る 受信者は任意のタイミングでグループ参加・離脱を行う グループの構成をリアルタイムにすべて把握できる存在はい ない 受信者同士が信頼できる関係であるとは限らない 送信者指定のグループ以外は,基本的に誰でも送信者になれ るため,送信者認証機能があると望ましい
IPマルチキャスト暗号の定義 マルチキャスト暗号は,鍵生成アルゴリズムGen,暗号化アルゴ リズムEnc, 復号化アルゴリズムDec の多項式時間アルゴリズム の組(Gen,Enc,Dec) によって定義される Gen - 鍵生成アルゴリズム 1 𝜆 (λ はセキュリティパラメータ) を入力とし,受信者𝑖 は,自身の公 開鍵 𝑃𝐾 𝑖 と秘密鍵 𝑆𝐾 𝑖 を出力する Enc - 暗号化アルゴリズム 復号を許可する受信者の公開鍵 𝑃𝐾 𝑖 の集合と平文𝑀を入力とし,暗 号文𝐶 を出力する Dec - 復号アルゴリズム 送信者に復号を許可された任意の受信者𝑖 の公開鍵 𝑃𝐾 𝑖 と秘密鍵 𝑆𝐾 𝑖 と,暗号文𝐶 を入力とし,平文𝑀 あるいは復号不可を表す⊥ を出力 する
IPマルチキャスト暗号(図示) s PK1 SK1 H PK2 M SK2 C PK3 SK3 PKn SKn Sender Rec 1 93ea923 510de92 H 392a18e f8c0152 7d23b59 C PK1 PK2 PK3 PKn SK1 SK2 SK3 SKn Rec 1 Hello How are you? Rec 2 M Rec 3 Rec n
IPマルチキャスト暗号(図示) s PK1 SK1 PK2 M SK2 PK3 SK3 PKn SKn Sender Rec 1 Rec 2 93ea923 510de92 392a18e f8c0152 7d23b59 Rec 1 PK1 SK1 Hello How are you? Rec 2 M PK2 SK2 Rec 3 PK3 SK3 PKn Rec n SKn
IPマルチキャスト暗号(図示) PK1 SK1 s M Rec 1 93ea923 510de92 392a18e f8c0152 7d23b59 s Rec 1 PK1 SK1 Hello How are you? M
プロトタイプ 準備 各受信者を1, 2, …, 𝑛 とする 受信者はそれぞれの秘密鍵 𝑝 𝑖 , 𝑞 𝑖 受信者はそれぞれの秘密鍵 𝑝 𝑖 , 𝑞 𝑖 (𝑖 = 1, 2, …, 𝑛) を大きな素数から選ぶ 公開鍵 𝑃𝐾 𝑖 = 𝑝 𝑖 𝑞 𝑖 𝑖 = 1, 2, …, 𝑛 をそれぞれ計算し,公開する
プロトタイプ 送信 任意の𝑖 𝑖 = 1, 2, …, 𝑛 において𝑠 < 𝑝 𝑖 𝑞 𝑖 となる秘密共通鍵𝑠 を決定する 任意の𝑖 𝑖 = 1, 2, …, 𝑛 において𝑠 < 𝑝 𝑖 𝑞 𝑖 となる秘密共通鍵𝑠 を決定する 暗号鍵𝑒(素数が望ましい) を決定する 𝑐 = 𝑠 𝑒 𝑚𝑜𝑑 𝑖=1 𝑛 𝑃𝐾 𝑖 を計算する 𝑐 と𝑒 をヘッダとして送信する 平文𝑀を𝑠 で暗号化したメッセージを送信する
プロトタイプ 受信 復号する受信者𝑖 を例とする 𝑒𝑑 𝑖 = 1 𝑚𝑜𝑑 𝑝 𝑖 − 1 𝑞 𝑖 − 1 となる復号鍵 𝑑 𝑖 を計算する 𝑒𝑑 𝑖 = 1 𝑚𝑜𝑑 𝑝 𝑖 − 1 𝑞 𝑖 − 1 となる復号鍵 𝑑 𝑖 を計算する 𝑠 = 𝑐 𝑑 𝑖 𝑚𝑜𝑑 𝑝 𝑖 𝑞 𝑖 を計算し,秘密共通鍵𝑠 を得る 𝑠 で暗号文を復号して𝑀を得る
プロトタイプ 補足 𝑒は 𝑖=1 𝑛 𝑝 𝑖 −1 𝑞 𝑖 −1 と互いに素になる 整数値に 𝑒は 𝑖=1 𝑛 𝑝 𝑖 −1 𝑞 𝑖 −1 と互いに素になる 整数値に するべきであるが,送信者も任意の 𝑝 𝑖 , 𝑞 𝑖 を知らない ため,素数値にする 事前に𝑒 を決めておくと,受信者の秘密鍵生成時に 互いに素になる 𝑝 𝑖 , 𝑞 𝑖 を選べ, 𝑑 𝑖 も事前に決定できる 𝑠 で平文𝑀を暗号化するアルゴリズムは本手法と 独立で,既存の共通鍵暗号方式などを用いる
安全性 任意の受信者𝑖 の公開鍵 𝑃𝐾 𝑖 から秘密鍵 𝑝 𝑖 , 𝑞 𝑖 を 導き出すことは,RSA 仮定と同等で困難である グループ内に同じ 𝑝 𝑖 または 𝑞 𝑖 をもつ受信者がい た場合,その存在を確認できる
その他 RSA署名同様に送信者認証が行える 𝑐の法は 𝑖=1 𝑛 𝑃𝐾 𝑖 になるため,ヘッダサイズは 𝑂(𝑛) に従って増大する 𝑐の法は 𝑖=1 𝑛 𝑃𝐾 𝑖 になるため,ヘッダサイズは 𝑂(𝑛) に従って増大する 𝑒の値を調整してサイズ減少も考え中 RSA公開鍵と共用できる
暗号関係のサーベイ 楕円曲線上のペアリング 素因数分解問題 離散対数問題 共通鍵暗号(ブロック暗号)