現代暗号 volume2 t-matsu 暗号アルゴリズムの高速化素数判定

現代暗号 VOLUME2
t-matsu
暗号アルゴリズムの
高速化
素数判定
暗号の世界では素数が重要である
素数の探し方として以下がある



試し割り
エラトステネスのふるい
フェルマーテスト


𝑎𝑛−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 を取り出す
(𝑘, 𝑛)閾値秘密分散共有法
𝐷は𝑝 > max(𝑠, 𝑛)となる素数𝑝を決める
 𝐷は𝑓 0 = 𝑠となる𝐺𝐹 𝑝 上の高々𝑘 − 1次多項式
𝑓 𝑥 = 𝑠 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + ⋯ + 𝑎𝑘−1 𝑥 𝑘−1 𝑚𝑜𝑑 𝑝を選ぶ
 𝐷は𝑣𝑖 = 𝑓 𝑖 𝑚𝑜𝑑 𝑝を計算し，シェア𝑣𝑖 を𝑃𝑖
に与える
(分散段階)
 参加者は𝑘人以上の情報 𝑘点で𝑓 𝑥 を求める
 𝑠 = 𝑓 0 を取り出す
(再構成段階)

ラグランジュ補間
𝑘個の点で𝑘 − 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年
 送信者受信者ともにシステム全体の人数とそれぞれ
の公開鍵を保持する必要がある

CBE(Contributory Broadcast Encryption)-2011年
 構成員がかわるたびに秘密鍵と公開鍵を更新する必
要がある
IPマルチキャスト暗号の要件





受信できるメッセージは，すべての受信者において同一であ
る
受信者は任意のタイミングでグループ参加・離脱を行う
グループの構成をリアルタイムにすべて把握できる存在はい
ない
受信者同士が信頼できる関係であるとは限らない
送信者指定のグループ以外は，基本的に誰でも送信者になれ
るため，送信者認証機能があると望ましい
IPマルチキャスト暗号の定義
マルチキャスト暗号は，鍵生成アルゴリズムGen,暗号化アルゴ
リズムEnc, 復号化アルゴリズムDec の多項式時間アルゴリズム
の組(Gen,Enc,Dec) によって定義される

Gen - 鍵生成アルゴリズム


Enc - 暗号化アルゴリズム


1𝜆 (λ はセキュリティパラメータ) を入力とし，受信者𝑖 は，自身の公
開鍵𝑃𝐾𝑖 と秘密鍵𝑆𝐾𝑖 を出力する
復号を許可する受信者の公開鍵𝑃𝐾𝑖 の集合と平文𝑀を入力とし，暗
号文𝐶 を出力する
Dec - 復号アルゴリズム

送信者に復号を許可された任意の受信者𝑖 の公開鍵𝑃𝐾𝑖 と秘密鍵𝑆𝐾𝑖
と，暗号文𝐶 を入力とし，平文𝑀 あるいは復号不可を表す⊥ を出力
する
IPマルチキャスト暗号(図示)
Sender
Hello
How are
you?
M
s
93ea92
3
510de9
2
392a18
e
f8c0152
7d23b5
9
PK1
Rec 1
SK1
H
PK2
C
PK3
Rec 2
SK2
Rec 3
SK3
PKn
Rec n
SKn
IPマルチキャスト暗号(図示)
Sender
Hello
How are
you?
s
93ea92
3
510de9
2
392a18
e
f8c0152
7d23b5
9
PK1
PK2
M
PK3
Rec 1
SK1
Rec 2
SK2
Rec 3
SK3
PKn
Rec n
SKn
IPマルチキャスト暗号(図示)
93ea92
3
510de9
2
392a18
e
f8c0152
7d23b5
9
PK1
s
Rec 1
SK1
Hello
How are
you?
M
プロトタイプ



準備
各受信者を1, 2, … , 𝑛 とする
受信者はそれぞれの秘密鍵 𝑝𝑖 , 𝑞𝑖
(𝑖 = 1, 2, … , 𝑛) を大きな素数から選ぶ
公開鍵𝑃𝐾𝑖 = 𝑝𝑖 𝑞𝑖 𝑖 = 1, 2, … , 𝑛
をそれぞれ計算し，公開する
プロトタイプ
送信

任意の𝑖 𝑖 = 1, 2, … , 𝑛 において𝑠 < 𝑝𝑖 𝑞𝑖
となる秘密共通鍵𝑠 を決定する
暗号鍵𝑒(素数が望ましい) を決定する

𝑐 = 𝑠 𝑒 𝑚𝑜𝑑

𝑐 と𝑒 をヘッダとして送信する

平文𝑀を𝑠 で暗号化したメッセージを送信する

𝑛
𝑖=1 𝑃𝐾𝑖
を計算する
プロトタイプ




受信
復号する受信者𝑖 を例とする
𝑒𝑑𝑖 = 1 𝑚𝑜𝑑 𝑝𝑖 − 1 𝑞𝑖 − 1
となる復号鍵𝑑𝑖 を計算する
𝑠 = 𝑐 𝑑𝑖 𝑚𝑜𝑑 𝑝𝑖 𝑞𝑖
を計算し，秘密共通鍵𝑠 を得る
𝑠 で暗号文を復号して𝑀を得る
プロトタイプ
補足
𝑛
 𝑒は
𝑖=1 𝑝𝑖 − 1 𝑞𝑖 − 1 と互いに素になる整数値に
するべきであるが，送信者も任意の𝑝𝑖 , 𝑞𝑖 を知らない
ため，素数値にする
事前に𝑒 を決めておくと，受信者の秘密鍵生成時に
互いに素になる𝑝𝑖 , 𝑞𝑖 を選べ，𝑑𝑖 も事前に決定できる

𝑠 で平文𝑀を暗号化するアルゴリズムは本手法と
独立で，既存の共通鍵暗号方式などを用いる

安全性



任意の受信者𝑖 の公開鍵𝑃𝐾𝑖 から秘密鍵𝑝𝑖 , 𝑞𝑖 を
導き出すことは，RSA 仮定と同等で困難である
𝑠 を使用した暗号文を少なくとも𝑒 個以上集め
た場合，RSA の同一平文問題同様，中国の剰余
定理を用いた方法で𝑠を解読できる
グループ内に同じ𝑝𝑖 または𝑞𝑖 をもつ受信者がい
た場合，その存在を確認できる
その他


RSA署名同様に送信者認証が行える
𝑐の法は 𝑛𝑖=1 𝑃𝐾𝑖 になるため，ヘッダサイズは
𝑂(𝑛) に従って増大する
 𝑒の値を調整してサイズ減少も考え中

RSA公開鍵と共用できる
暗号関係のサーベイ




楕円曲線上のペアリング
素因数分解問題
離散対数問題
共通鍵暗号(ブロック暗号)

Download Report