現代暗号 volume2 t-matsu.

Presentation on theme: "現代暗号 volume2 t-matsu."— Presentation transcript:

1 現代暗号 volume2 t-matsu

2 暗号アルゴリズムの 高速化

3 素数判定 暗号の世界では素数が重要である 素数の探し方として以下がある 試し割り エラトステネスのふるい フェルマーテスト AKS素数判定法
𝑎 𝑛−1 ≠1 𝑚𝑜𝑑 𝑛 の場合𝑛は合成数と判定 AKS素数判定法 (𝑋+𝑎) 𝑛 ≠ 𝑋 𝑛 +𝑎 𝑚𝑜𝑑 𝑛 の場合𝑛は合成数と判定

4 ユークリッドの互除法 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

5 拡張ユークリッドの互除法 整数 𝑚, 𝑛 の最大を gcd 𝑚,𝑛 と表すときに， 拡張ユークリッドの互除法を用いて， 𝑎𝑚 + 𝑏𝑛 = gcd⁡(𝑚, 𝑛) の解となる整数 𝑎, 𝑏 の組を見つけることができる 特に、𝑚, 𝑛 が互いに素 最大公約数が 1 である場合， 𝑎𝑚 + 𝑏𝑛 = 𝑐 は任意の整数 𝑐 に対して整数解 (𝑎, 𝑏) をもつ

6 拡張ユークリッドの互除法 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

7 𝑒𝑑=1 𝑚𝑜𝑑 𝑝への適用 (𝑝,𝑒)を拡張ユークリッドの互除法に適用すると 𝑝𝑥+𝑒𝑦=1となる整数 𝑥,𝑦 が求められる これは𝑒𝑦=1 𝑚𝑜𝑑 𝑝となる𝑦である 𝑦>0なら𝑦が答え𝑦<0なら𝑝−𝑦が答えになる

8 多人数公開鍵暗号

9 1対𝑛の暗号方式 秘密分散共有法 放送型暗号(ブロードキャスト暗号)

10 秘密分散共有法 𝑛人のうち，任意の𝑘人が集まると秘密𝑠を復元できるが， どの𝑘−1人が集まっても𝑠を復元できない手法
ディーラ𝐷と𝑛人の参加者 𝑃 𝑖 からなる 𝐷は秘密𝑠を𝑛個のシェア 𝑣 𝑖 に符号化し， 𝑣 𝑖 を 𝑃 𝑖 に与える (分散段階) 𝑛人の参加者のうち𝑘人が集まり𝑠を復元する (再構成段階) (𝑘,𝑛)閾値秘密分散共有法(閾値法)と呼ぶ

11 (2,𝑛)閾値秘密分散共有法 𝐷は𝑓 𝑥 =𝑎𝑥+𝑠を決める 𝑓 0 =𝑠を秘密情報とする
𝐷は𝑛人の参加者 𝑃 𝑖 に 𝑖,𝑓 𝑥 の点情報を与える 参加者は2人以上の情報 2点 で 𝑓 𝑥 =𝑎𝑥+𝑠を求める 𝑠=𝑓 0 を取り出す

12 𝑓 𝑥 =𝑠+ 𝑎 1 𝑥+ 𝑎 2 𝑥 2 +…+ 𝑎 𝑘−1 𝑥 𝑘−1 𝑚𝑜𝑑 𝑝を選ぶ
(𝑘,𝑛)閾値秘密分散共有法 𝐷は𝑝>max⁡(𝑠,𝑛)となる素数𝑝を決める 𝐷は𝑓 0 =𝑠となる𝐺𝐹 𝑝 上の高々𝑘−1次多項式 𝑓 𝑥 =𝑠+ 𝑎 1 𝑥+ 𝑎 2 𝑥 2 +…+ 𝑎 𝑘−1 𝑥 𝑘−1 𝑚𝑜𝑑 𝑝を選ぶ 𝐷は 𝑣 𝑖 =𝑓 𝑖 𝑚𝑜𝑑 𝑝を計算し，シェア 𝑣 𝑖 を 𝑃 𝑖 に与える (分散段階) 参加者は𝑘人以上の情報 𝑘点 で𝑓 𝑥 を求める 𝑠=𝑓 0 を取り出す (再構成段階)

13 ラグランジュ補間 𝑘個の点で𝑘−1次多項式を復元する手法 𝑓 𝑥 = 𝜆 1 𝑥 𝑓 𝑖 1 +…+ 𝜆 𝑘 𝑥 𝑓 𝑖 𝑘 𝑚𝑜𝑑 𝑝
𝑓 𝑥 = 𝜆 1 𝑥 𝑓 𝑖 1 +…+ 𝜆 𝑘 𝑥 𝑓 𝑖 𝑘 𝑚𝑜𝑑 𝑝 このとき 𝜆 𝑗 𝑥 = 𝑥− 𝑖 1 ×…×(𝑥− 𝑖 𝑘 ) 𝑖 𝑗 − 𝑖 1 ×…×( 𝑖 𝑗 − 𝑖 𝑘 ) 𝑚𝑜𝑑 𝑝 𝑘≠𝑗 𝑠=𝑓 0 = 𝜆 1 0 𝑓 𝑖 1 +…+ 𝜆 𝑘 0 𝑓 𝑖 𝑘 で𝑠が求まる

14 ラグランジュ補間を実装してみる 𝑍 23 上の点 0,8 , 1,3 , 5,14 , 8,5 , 11,5 の5点を通る 𝑓 𝑥 = 𝑎 0 𝑥 4 + 𝑎 1 𝑥 3 + 𝑎 2 𝑥 2 + 𝑎 3 𝑥+ 𝑎 4 を求め，𝑓(2)と𝑓(3)の値を求めよ

15 ラグランジュ補間を実装してみる 𝑓 𝑥 = 9 𝑥 𝑥 𝑥 2 +15𝑥+8 𝑎 0 =9, 𝑎 1 =20, 𝑎 2 =20, 𝑎 3 =15, 𝑎 4 =8 ※係数はガウスの消去法で求められる ラグランジュ補間を使用すると 𝑓(2)=8 𝑓(3)=7 が得られる

16 放送型暗号(ブロードキャスト暗号) 送信者が秘密情報𝑠を暗号化したデータの送信 (同報通信)を1度だけ行う
受信者のうち，復号を許可されている 鍵を持っている 受信者𝑛人のみが復号できる このとき，𝑛人の鍵は皆異なるが復号される𝑠は同一になる ※ B-CASのイメージ （厳密にはB-CASは放送型暗号に含まれない)

17 代数的な方法 準備 素数𝑝と𝐺𝐹 𝑝 の原始元𝑔を選ぶ (𝑝は公開しておく) 送信者は 𝑍 𝑝 上の多項式
𝑓 𝑥 = 𝑎 0 + 𝑎 1 𝑥+ 𝑎 2 𝑥 2 +…+ 𝑎 𝑘 𝑥 𝑘 を選ぶ． 送信者は以下の値を計算する 𝑦 0 = 𝑔 𝑎 0 , 𝑦 1 = 𝑔 𝑎 1 ,…, 𝑦 𝑘 = 𝑔 𝑎 𝑘 受信者 𝑈 𝑖 に𝑓 𝑥 上の点 𝛼 𝑖 ,𝑓 𝛼 𝑖 を安全に配布する 𝛼 𝑖 ,𝑓 𝛼 𝑖 は 𝑈 𝑖 の復号鍵になる

18 代数的な方法 暗号化 送信者は𝐺𝐹 𝑝 上のメッセージ𝑀を暗号化する鍵 𝑠∈𝐺𝐹 𝑝 を選び，𝑀を𝑠で暗号化する 𝐶=𝐸𝑛𝑐(𝑠,𝑀)
以下のヘッダ𝐻を作成する 𝐻=ℎ 𝑠,𝑟 = 𝑔 𝑟 ,𝑠 𝑦 0 𝑟 , 𝑦 1 𝑟 ,…, 𝑦 𝑘 𝑟 𝑟∈𝐺𝐹 𝑝 はランダムに選ぶ 𝐻と𝐶を送信する

19 代数的な方法 復号化 受信者𝑖は自身の秘密鍵 𝛼 𝑖 ,𝑓 𝛼 𝑖 を用いて 以下の計算をして𝑠を得る
受信者𝑖は自身の秘密鍵 𝛼 𝑖 ,𝑓 𝛼 𝑖 を用いて 以下の計算をして𝑠を得る 𝑠= 𝑠 𝑦 0 𝑟 × 𝑗=1 𝑘 ( 𝑦 𝑗 𝑟 ) 𝛼 𝑖 𝑗 / ( 𝑔 𝑟 ) 𝑓( 𝛼 𝑖 ) を計算する 𝑠で𝐶を復号化して𝑀を得る

20 代数的な方法 証明 𝑠 𝑦 0 𝑟 × 𝑗=1 𝑘 ( 𝑦 𝑗 𝑟 ) 𝛼 𝑖 𝑗 / ( 𝑔 𝑟 ) 𝑓( 𝛼 𝑖 ) ={𝑠 𝑦 0 𝑟 ×( 𝑦 1 𝑟 ) 𝛼 𝑖 ×…×( 𝑦 𝑘 𝑟 ) 𝑎 𝑖 𝑘 }/ ( 𝑔 𝑟 ) 𝑓( 𝛼 𝑖 ) = 𝑠 𝑔 𝑎 0 𝑟 × 𝑔 𝑎 1 𝑟 𝛼 𝑖 ×… ×𝑔 𝑎 𝑘 𝑟 𝛼 𝑖 𝑘 /( 𝑔 𝑟 ) 𝑓( 𝛼 𝑖 ) ={𝑠 𝑔 𝑟 𝑎 0 + 𝑎 1 𝛼 𝑖 +…+ 𝑎 𝑘 𝛼 𝑖 𝑘 } /( 𝑔 𝑟 ) 𝑓( 𝛼 𝑖 ) =𝑠 ( 𝑔 𝑟 ) 𝑓( 𝛼 𝑖 ) / ( 𝑔 𝑟 ) 𝑓( 𝛼 𝑖 ) =𝑠

21 ブロードキャスト暗号の種類 共通鍵ブロードキャスト暗号 公開鍵ブロードキャスト暗号

22 公開鍵ブロードキャスト暗号 BGW方式 -2005年 AHBE(Ad Hoc Broadcast Encryption)-2010年
全体を管理するセンタが鍵の生成管理を行う AHBE(Ad Hoc Broadcast Encryption)-2010年 送信者受信者ともにシステム全体の人数とそれぞれ の公開鍵を保持する必要がある CBE(Contributory Broadcast Encryption)-2011年 構成員がかわるたびに秘密鍵と公開鍵を更新する必 要がある

23 IPマルチキャスト暗号の要件 受信できるメッセージは，すべての受信者において同一であ る 受信者は任意のタイミングでグループ参加・離脱を行う
グループの構成をリアルタイムにすべて把握できる存在はい ない 受信者同士が信頼できる関係であるとは限らない 送信者指定のグループ以外は，基本的に誰でも送信者になれ るため，送信者認証機能があると望ましい

24 IPマルチキャスト暗号の定義 マルチキャスト暗号は，鍵生成アルゴリズムGen,暗号化アルゴ リズムEnc, 復号化アルゴリズムDec の多項式時間アルゴリズム の組(Gen,Enc,Dec) によって定義される Gen - 鍵生成アルゴリズム 1 𝜆 (λ はセキュリティパラメータ) を入力とし，受信者𝑖 は，自身の公 開鍵 𝑃𝐾 𝑖 と秘密鍵 𝑆𝐾 𝑖 を出力する Enc - 暗号化アルゴリズム 復号を許可する受信者の公開鍵 𝑃𝐾 𝑖 の集合と平文𝑀を入力とし，暗 号文𝐶 を出力する Dec - 復号アルゴリズム 送信者に復号を許可された任意の受信者𝑖 の公開鍵 𝑃𝐾 𝑖 と秘密鍵 𝑆𝐾 𝑖 と，暗号文𝐶 を入力とし，平文𝑀 あるいは復号不可を表す⊥ を出力 する

25 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

26 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

27 IPマルチキャスト暗号(図示) PK1 SK1 s M Rec 1 93ea923 510de92 392a18e f8c0152
7d23b59 s Rec 1 PK1 SK1 Hello How are you? M

28 プロトタイプ 準備 各受信者を1, 2, …, 𝑛 とする 受信者はそれぞれの秘密鍵 𝑝 𝑖 , 𝑞 𝑖
受信者はそれぞれの秘密鍵 𝑝 𝑖 , 𝑞 𝑖 (𝑖 = 1, 2, …, 𝑛) を大きな素数から選ぶ 公開鍵 𝑃𝐾 𝑖 = 𝑝 𝑖 𝑞 𝑖 𝑖 = 1, 2, …, 𝑛 をそれぞれ計算し，公開する

29 プロトタイプ 送信 任意の𝑖 𝑖 = 1, 2, …, 𝑛 において𝑠 < 𝑝 𝑖 𝑞 𝑖 となる秘密共通鍵𝑠 を決定する
任意の𝑖 𝑖 = 1, 2, …, 𝑛 において𝑠 < 𝑝 𝑖 𝑞 𝑖 となる秘密共通鍵𝑠 を決定する 暗号鍵𝑒(素数が望ましい) を決定する 𝑐 = 𝑠 𝑒 𝑚𝑜𝑑 𝑖=1 𝑛 𝑃𝐾 𝑖 を計算する 𝑐 と𝑒 をヘッダとして送信する 平文𝑀を𝑠 で暗号化したメッセージを送信する

30 プロトタイプ 受信 復号する受信者𝑖 を例とする 𝑒𝑑 𝑖 = 1 𝑚𝑜𝑑 𝑝 𝑖 − 1 𝑞 𝑖 − 1 となる復号鍵 𝑑 𝑖 を計算する
𝑒𝑑 𝑖 = 1 𝑚𝑜𝑑 𝑝 𝑖 − 1 𝑞 𝑖 − 1 となる復号鍵 𝑑 𝑖 を計算する 𝑠 = 𝑐 𝑑 𝑖 𝑚𝑜𝑑 𝑝 𝑖 𝑞 𝑖 を計算し，秘密共通鍵𝑠 を得る 𝑠 で暗号文を復号して𝑀を得る

31 プロトタイプ 補足 𝑒は 𝑖=1 𝑛 𝑝 𝑖 −1 𝑞 𝑖 −1 と互いに素になる 整数値に
𝑒は 𝑖=1 𝑛 𝑝 𝑖 −1 𝑞 𝑖 −1 と互いに素になる 整数値に するべきであるが，送信者も任意の 𝑝 𝑖 , 𝑞 𝑖 を知らない ため，素数値にする 事前に𝑒 を決めておくと，受信者の秘密鍵生成時に 互いに素になる 𝑝 𝑖 , 𝑞 𝑖 を選べ， 𝑑 𝑖 も事前に決定できる 𝑠 で平文𝑀を暗号化するアルゴリズムは本手法と 独立で，既存の共通鍵暗号方式などを用いる

32 安全性 任意の受信者𝑖 の公開鍵 𝑃𝐾 𝑖 から秘密鍵 𝑝 𝑖 , 𝑞 𝑖 を 導き出すことは，RSA 仮定と同等で困難である
グループ内に同じ 𝑝 𝑖 または 𝑞 𝑖 をもつ受信者がい た場合，その存在を確認できる

33 その他 RSA署名同様に送信者認証が行える 𝑐の法は 𝑖=1 𝑛 𝑃𝐾 𝑖 になるため，ヘッダサイズは 𝑂(𝑛) に従って増大する
𝑐の法は 𝑖=1 𝑛 𝑃𝐾 𝑖 になるため，ヘッダサイズは 𝑂(𝑛) に従って増大する 𝑒の値を調整してサイズ減少も考え中 RSA公開鍵と共用できる

34 暗号関係のサーベイ 楕円曲線上のペアリング 素因数分解問題 離散対数問題 共通鍵暗号(ブロック暗号)