☆情報理論
◆エントロピー
平均情報量
ある文字系A1,A2,…,Anでそれぞれの文字が使われる確率をp1,p2,…,pnとすると、それぞれの文字が持つ情報量は、
-log(2)p1, -log(2)p2, … , -log(2)pn
あるいは H = log(2) (1/p) ビット
平均 E は、
E = p1*(-log(2)p1) + p2*(-log(2)p2) + … +
pn*(-log(2)pn)
これをエントロピーという。確率が全て等しい(1/n)のとき、エントロピーは log(2)n となる。
※物理におけるエントロピー
「ありえる状態数の対数」
（システムの無秩序さの程度を表す）
※確率が１に近い事象の情報量は０に近い
⇒確率が１である事象の情報量は０である。
⇒確率が０に近い事象の情報量は大きい
情報量 I(P = -log(2){P} ビット
◆ランダム現象
◆シャノンの基本定理
文字系による通信に必要な１文字あたりの平均ビット数は、エントロピーより少なくすることはできない。（近づけることはできる。）
ある文字系の各文字を0と1の組み合わせで表すとき、1文字あたりのビット数の期待値Lはその文字系の平均情報量Hより小さくできない。
☆画像数学
◆信号検出
仮説検定の考え方の応用
信号なのか、雑音なのかを判定する問題。
つねに雑音は存在する。
信号とは信号＋雑音であり、雑音は雑音のみのこと
＿◇感度と特異度
※真の陽性
信号を信号であると正しく判定すること
※真の陰性
雑音を雑音であると正しく判定すること
※感度 sensitivity
感度(%)=(真の陽性数/信号数)*100
※特異度 speciality
特異度(%)=(真の陰性数/信号数)*100
※感度、特異度の両方が高い方が良いか、一般に、一方が高くなると他方が下がる
⇒２つの分布は若干の重なりを持つ分布となる
※縦軸に度数、横軸に判定基準につかう値をとったグラフを描くと、雑音と信号の分布は若干の重なりをもった形となる。
⇒横軸のある位置ｋを判断基準の位置とすると
信号であるにもかかわらず雑音と判断される誤り⇒偽陰性
雑音であるにもかかわらず信号であると判定する誤り⇒偽陽性
偽陰性（％）＝100％－感度＝（偽陰性数/信号数)*100
偽陽性（％）＝100％－特異度＝（偽陽性数/信号数)*100
＿◇刺激、反応行列と条件つき確率分布
反応
YES NO
刺激 信号 [真の陽性 偽陰性]
雑音 [偽陽性 真の陰性]
※信号が与えられたときの条件つき確率密度関数
f(x|s)
※雑音が与えられたときの、条件つき確率密度関数
f(x|n)
判断基準位置ｋにより
A=∫[k:∞]f(x|s)dx=P(S|s) 真の陽性の確率
B=∫[-∞:k]f(x|s)dx=P(N|s) 偽陰性の確率
C=∫[k:∞]f(x|n)dx=P(S|n) 偽陽性の確率
D=∫[-∞:k]f(x|n)dx=P(N|n) 真の陰性の確率
P(N|s)=1-P(S|s)
P(N|n)=1-P(S|n)
※基準位置ｋをとる位置によって４つの確立の大きさがかわる
※尤度比
f(x|s)
——=λ(x)
f(x|n)
xにはSまたはNが入る。
⇒ROC曲線の傾き
◆ＲＯＣ
Receiver Operating Characteristic
受信者動作特性
⇒雑音が含まれる信号の中から、ある特定の弱い信号を検出する目的に使われる
☆決定理論
decision theory
☆数理計画法
☆OR
◆在庫モデル
inventory
◆配分
allocation
＿◇線形計画法
＿◇ダイナミックプログラミング
◆順序づけ、経路
sequencing & routing
※巡回セールスマン問題
◆取替え
replacement
◆待ち行列
queuing
◆競合のあるモデル
competition
※ゲーム理論
◆探索モデル
searching
◆シミュレーション
simulation
☆ゲーム理論
◆ミニマックス定理
☆暗号
◆用語
平文（ひらぶん）plaintext
暗号文（あんごうぶん）ciphertext
共通鍵暗号(Symmetric-key Cipher)
暗号化と復号化の鍵が同じ。鍵が送信者と受信者の間で共有されている必要がある。
公開鍵暗号(Public-key Cipher)
非対称鍵暗号。暗号化と復号化に異なる鍵を用いる。閉める鍵（公開鍵,public key)とあける鍵（秘密鍵,secret key)が異なる。
※
8 + 9 ≡ 5 (mod 12)
「８プラス９は、１２を法として５に合同」
＿◇伝統名
暗号を送る人。。。アリス
暗号を受け取る人。。。ボブ
暗号を盗み見る人。。。イヴ
◆暗号の役割
①守秘 情報を秘密に伝える
②認証 相手の身元を確かめる
◆歴史上の暗号
①スキュタレー暗号（前500年ごろ、スパルタ人）
②シーザ暗号(Julius Caesar考案）
c=x+n;
③ドイツのエニグマ暗号
英Turingにより解読されたとの話があるが、実はそうでない？
④日本の紫暗号(97式欧文印字機)
装置が行き渡らなかったために、同じ内容の文を、既に解読されていた前世代の赤暗号でも送っていた。そのため多数のサンプルがあり解読が進んだ。
＿◇文学上
黄金虫暗号。。。エドガー・アラン・ポー
踊る人形暗号。。。コナンドイル
◆Vernam暗号
Shannonにより暗号化に使われる数列を知らなければ絶対に解読できないことが証明されている。
c[i]=x[i]+n[i];
※ワンタイムパッド法
◎ブロック暗号
◆DES (Data Encryption Standard)
1974年に米商務省標準局(NBS)が公募し、ＩＢＭがFeistel設計によるLucifer暗号で応募、1977に正式採用され、1981年にANSI標準となる。
※デスと発音するのが普通
※共通鍵暗号
※歴史上初めて商用利用可能となった画期的な暗号化方式（それ以前は、暗号アルゴリズムを非公開にすることによって安全性が確保されるという考えだった）
※DESのアルゴリズム
①平文8文字=64ビットをブロックとする。
②基本演算は二つ
加算：右32ビットと１段の鍵48ビットからから
Ｓ－ＢＯＸを使って値をつくりこれを
左32ビットにＸＯＲする。
転置：左右32ビットを交換
③上記の基本演算を１６回繰り返す。
④上記の基本演算の前後に桁の入れ替えを行う。
⑤鍵は各段48ビットで計768ビット必要である
これは56ビットから桁を並び替え抽出するビットを
変えることで鍵を生成する。
※2008年の技術レベルではDESの56ビットのキーサイズを解読に必要な時間は２４時間以下。
→トリプルＤＥＳにより実用強度をなんとか保つ
◆複数ブロックの暗号化モード
FIPS PUB-81
SP800-38A
①ECB(Electrnic Code Book)モード
単純に64ビット毎に暗号化。同一平文がつづくと同一暗号文がつづいてしまう。
②CBC(Cipher Block Chaining)モード
最初の平文64ビットに対して初期ベクタ64ビットをＸＯＲしてからＤＥＳをかける。次からは前のブロックのＤＥＳ結果をベクタとして使う。同一平文でも暗号文が異なるが、途中誤りがあると復号できなくなる。
③CFB(Cipher FeedBack)モード
平文を任意のビット数（１～６４）ずつ暗号化する。ＤＥＳはＸＯＲする値を生成するために使われる。初期ベクタを暗号化し、その結果から事前に決めたビット数を平文にＸＯＲして送信する。送った暗号文をさらにベクタにして次の値を作り出す。
④OFB(Output FeedBack)モード
平文を任意のビット数（１～６４）ずつ暗号化する。ＤＥＳはＸＯＲする値を生成するために使われる。初期ベクタを暗号化し、その結果から事前に決めたビット数を平文にＸＯＲして送信する。ＣＦＢとの違いは、送る暗号文はＤＥＳに反映しないので、ビットエラーがあっても次の復号には影響しなくなる点。しかし、暗号文の数が抜けると全て復号ができなくなる。
⑤CTR(Counter)モード
1979年にディフィーとヘルマンによって提案される
ブロック毎の完全並列化処理できる
＿◇CTRモード
カウンタ系列T1,…Tnにより
暗号化：
Oj = Ek(Tj) j=1,…,n
Cj = Pj ^ Oj j=1,…,n
Cn = Pn ^ MSB_u(On)
復号化：
Oj = Ek(Tj) j=1,…,n
Pj = Cj ^ Oj j=1,…,n
Pn = Cn ^ MSB_u(On)
uは最後の平文、暗号文のビット長
※カウンタ系列の生成
mビットのデータ。。。2^m未満の数で表現できる
mビットのｘに対して
(x+1) mod 2^m
を標準インクリメント関数とする
bビットを1ブロックとするブロック暗号に対して、下位m(m<b)を標準インクリメント関数の値とし、残りb-mビットをナンスとする。
ナンス(message nonce)
セッションをユニークにするための一時的なデータ
◆3-DES
DESのままで、鍵のビット数を増やすために、
第１の鍵でDES暗号化
第２の鍵でDES復号化
第１の鍵でDES暗号化
する方法。第１と第２で同じ鍵を使うと前２段が相殺して、単なるDESとなる。
◆AES (Advanced Encryption Standard)
ブロック暗号で、平文は128ビット、鍵は128ビット、192ビット、256ビット。（入力は固定長だが、鍵長は３種類）
NBSの後継NIST（米商務省標準技術協会）が1997年に公募し、2000年10月2日に決定、翌年11月26日に連邦情報処理標準となった。
※NIST FIPS 197
※ベルギーのDaemen(Banksys社)とRijmen（レーベンカトリック大）が設計したRijndaelが元になっているが、入力文のサイズが固定となり、鍵長も３種類限定となった
※共通鍵暗号
＿◇基本構成
入力をばらして、鍵と混ぜ合わせる操作を所定の回数繰り返す。
※入力文のサイズ
１２８ビット固定
※鍵長とラウンド数
１ワードは４バイト
Nk：鍵長
Nr：ラウンド数
Nr=Nk+6
AES-128 Nk=4 Nr=10
AES-192 Nk=6 Nr=12
AES-256 Nk=8 Nr=14
※暗号化部
ラウンド処理－Ｎｒ回繰り返す
①平文を初期処理に入力
初期処理用鍵ＲＫ０
②第１ラウンド処理～第Ｎｒ－１ラウンド処理
第１～第Ｎｒ－１ラウンド鍵ＲＫ１～ＲＫＮｒ－１
③第Ｎｒラウンド処理
第Ｎｒラウンド鍵ＲＫＮｒ
最終ラウンドのみ構成異なる
※鍵拡張部
共通鍵からＲＫ０～ＲＫＮｒを生成する
＿◇暗号化処理
①初期処理
AddRoundKey <- RK0
②第1~Nr-1ラウンド
SubBytes
ShiftRows
MixColumns
AddRoundKey <- RKn
③第Nrラウンド
SubBytes
ShiftRows
AddRoundKey <- RKNr
＿◇復号化処理
①第Nrラウンド
AddRoundKey <- RKNr
InvShiftRows
InvSubBytes
②第1~Nr-1ラウンド
AddRoundKey <- RKn
InvMixColumns
InvShiftRows
InvSubBytes
③最終処理
AddRoundKey <- RK0
◆他のブロック暗号
① MULTI2 日立 BS,CS加入者むけスクランブル
② IDEA (International Data Encrypt Algorithm)
1991 スイスLai, Messey + Ascom
個人利用は無料。PGPでも使われる
③ RC5 Rivest開発, RCシリーズ5番目。柔軟性。
④ MISTY1,2 三菱電機、松井
⑤ KASUMI MISTYの改造版, W-CDMA
⑥ SC2000 富士通
⑦ Hierocrypt-3 東芝
⑧ Camellia NTT+三菱
◎ストリーム暗号
アルゴリズム非公開の軍事分野では古くから使われているが、現代暗号としては研究があまり進んでいない。
RC4 WWWデータの暗号化
A5 GSMの音声秘匿技術（Shamirにより解析される）
KASUMIに代わる
SEAL IBM
MULTI-S01 日立（米国製PANAMA理論）
◎公開鍵暗号
1976 DiffieとHellmanによって発案
Diffie-Hellman Key Exchange
1777 RSA暗号として発明(Rivest, Shamir, Adleman)
1979 Rabin暗号発明さる
1982 Elgamal暗号発明さる
1985 楕円曲線暗号発明さる
公開鍵で暗号化した暗号文は、対応する秘密鍵でしか復号できない。これにより事前に暗号鍵を双方で持ち合う必要が無くなる。
※公開鍵暗号による認証
秘密鍵で暗号化した暗号文は、対応する公開鍵でしか復号できない。これにより送った平文を公開鍵で復号できる相手は秘密鍵を持っていることを認証できる。
※公開鍵暗号の計算量問題
巨大な数の巨大な回数のべき乗、巨大な数を法とするmod計算が頻出するので、素のままでは計算不能。算法を工夫して計算量と桁数を落とすがそれでも計算時間がかかる。
※共通鍵暗号とのハイブリッド方式
共通鍵を公開鍵暗号を使って暗号化しておくり、通信内容は共通鍵暗号による。
※公開鍵の所有者問題
公開鍵と持ち主の対応を信用できるようにCA(Certificate Authority)をもうけ、ここの公開鍵だけを絶対に信用できるような方法で公開することで、後はCA経由で公開鍵を入手することで認証する。
◆RSA暗号
素数どうしの掛け算が容易であるのに、逆の素因数分解が困難であることを利用した公開鍵暗号。
＿◇原理
異なる二つの素数を掛けた数を法(modをとる)とする世界では、数はべき乗されるたびに予想できない数に変化しながらも、あるべき乗数になると突然全ての数が自分自身に戻る。
このべき乗数は、用いる二つの素数P-1，Q-1に対して
(P-1とQ-1の最小公倍数+1)乗
で最初におき、(P-1とQ-1の最小公倍数)を足す度に起きる。
(P-1とQ-1の最小公倍数)*n+1 乗
P*Qを法とする世界で、平文の数値をある適当な回数だけべき乗する。これを暗号化とし、べき乗の回数を公開鍵とする。復号は自分自身に戻るようにさらにべき乗（このべき乗の数が秘密鍵となる）する。
異なる二つの素数を掛けた数を法(modをとる)とする世界では割り算が単純にできないことが、暗号の背景としてある。※暗号化のためには、法とする値P*Qと、公開鍵Eを公開する必要がある。P*Qを公開してもPとQに素因数分解することが困難であることが安全性を担保している。
※現在のＲＳＡ暗号では、P,Qは150~300桁の素数であり、300~600桁のP*Qを使っている。
＿◇別解説
送信者Ａ
受信者Ｂ
①Ｂは２つの大きな素数p, q(p≠q)を用意し、
N = p * q
および
L = lcm(p-1, q-1)
を計算しておく。
※p, q は2008年では512~1024ビット程度の長さ
※lcm(a, b) : least common multiple
さらに
e * d ≡ 1 (mod L)
となるような e, d を選ぶ。
※e * d ≡ 1 (mod L)とは、ed – 1 が L の倍数であることを意味する。
②(e, N)を公開鍵として公開する
N を公開モジュラス
e を公開指数
と呼ぶ
※一方 d を秘密指数 (d, N)を秘密鍵と呼ぶ
③Ａは、１≦Ｍ＜Ｎを満たす整数で表されたメッセージＭを用意し、Ｍを公開鍵(e, N)で暗号化した暗号文Ｃを作って送付する。Ｂは、秘密鍵(d, N)で復号する
C = M^e mod N
M = C^d mod N
※このような計算をべき乗剰余計算という。
※復号処理がうまく行くためには
gcd(M, N) = 1
である必要がある。
※gcd(M, N) : greatest common divisor
数値例）
p = 7, q = 11
N = 7 * 11 = 77
L = lcm(7-1, 11-1) = lcm(6, 10) = 30
公開指数eと秘密指数dとして
e=7, d=13
を選ぶ
7 * 13 – 1 = 91 – 1= 90 = 3 * 30
より、このe, dはLの倍数である。
よって公開鍵は (e, N) = (7, 77)
秘密鍵は(d N) = (13, 77)
メッセージはgcd(M,77)=1を満たす必要あり
M=17とする。
C = M^e mod N
= 17^7 mod 77 = 410338673 mod 77 = 52 … 暗号文
C^d mod N = 52^13 mod 77 = … = 17
※gcd(M,N)=1でなければ復号できないが、Nは巨大な素数の積なので、gcd(M,N)=1とならない確率は非常に小さい。
＿◇モジュラー演算
① a ≡ b (mod m) とは、a – b が m の倍数であること。
② a mod m とは、a を m で割った余り（剰余）のこと
※余りとしては、0以上 m 未満の数を表すとする、と処理しやすい。
※足し算、引き算、掛け算は自由にできる
a ≡ c (mod m)
b ≡ d (mod m)
のとき
M1) a + b ≡ c + d (mod m)
M2) a – b ≡ c – d (mod m)
M3) a * b ≡ c * d (mod m)
※いつでも割り算ができるわけではない
※a の法 m における逆数
a * x ≡ 1 (mod m)
となるようなxがもしあれば、aの法mにおける逆数といい、
a^-1 (mod m)
と書く。
※a が法 m のもとで逆数を持つための必要十分条件は、
gcd(a, m) = 1
※公開指数と秘密指数は
e * d ≡ 1 (mod L)
という関係式であるので、法Ｌのもとで互いに逆数の関係になり得る。したがって、e, dは、
gcd(e, L) = 1
gcd(d, L) = 1
であるものを選ぶ。
＿◇必要な算法
①512ビット、1024ビットといった大きな数の計算
②乱数の生成
③素数p,qの生成
④最大公約数の計算
⑤最小公倍数の計算
⑥公開指数、秘密指数の計算
⑦べき剰余計算
※a,b の最大公約数gcd(a, b)と最小公倍数lcm(a,b)の間の関係
lcm(a, b) = a*b/gcd(a, b)
＿◇ユークリッド互除法
すべて正の整数であるとする。
※アルゴリズム
Input: a, b
Output: gcd(a, b)
[STEP 1]aをbで割った余りをrとし、r≠0である間、以下を繰り返す
[STEP 1-1]a=rとする
[STEP 1-2]aとbを入れ替える
[STEP 2]bを出力して終了する
＿◇バイナリ・ユークリッド互除法
割り算を使わず、偶奇判定とシフトにより同等な処理を行う
①a,b がともに偶数なら、gcd(a,b)=2*gcd(a/2, b/2)
②aだけが偶数で、bが奇数なら gcd(a,b)=gcd(a/2,b)
③a,bがともに奇数のときは、 a-bは偶数になる
※アルゴリズム
Input: a, b
Output: gcd(a, b)
[STEP 1]g=1とおく
[STEP 2]a>0が満たされる間、以下を繰り返し：
[STEP 2-1]aが偶数であり、かつbも偶数であるとき
a=a/2,b=b/2,g=2*gとして[STEP 2]に戻る
[STEP 2-2]aが偶数、かつbは奇数であるとき
a=a/2とし[STEP 2]に戻る
[STEP 2-3]aが奇数、かつbが偶数であるとき
b=b/2とし[STEP 2]に戻る
[STEP 2-4]aが奇数であり、かつbも奇数であるとき、
t=|a – b|/2に対し、
もしa≧bであれば a=t,
もしa＜bであれば b=tとして[STEP 2]に戻る
[STEP 3]g=gbを出力して終了する
aをbで割った余りをrとし、r≠0である間、以下を繰り返す
[STEP 1-1]a=rとする
[STEP 1-2]aとbを入れ替える
＿◇拡張ユークリッド互除法
公開指数 e と秘密指数 d を計算するために用いられる。
e*d ≡ 1 (mod L)
例）p=11,q=7ならば L=lcm(11-1,7-1)=30
より e * d ≡ 1 (mod 30)
となる組は
(e,d)=(7,13),(11,11),(13,7),(17,23),(19,19)
※セキュリティ上はgcd(e,L)=1だけでは十分安全ではない。
d を求めるためには
e*d = 1 + L * k
k:整数
なる不定方程式を解かねば成らない。（不定方程式なので、答えは一つに定まらず、また、無いこともある）
拡張ユークリッド互除法は、ゼロでない２つの整数a, bに対し不定方程式：
a*x + b*y = gcd(a,b)
を満たす整数x,yとa,bの最大公約数gcd(a,b)を同時に求めるアルゴリズムである。
※無限にある組み合わせのうちの一つが求まる
※a,bは正とするが、例えば負のyが得られた場合もz=-yとおいてzで書き直せばよいので、正負は制約とはならない。
e * d + L * k = gcd(e,L) = 1
で、eとLが判明しているとき(a, bに相当）d, k（x, y)を求める。
※アルゴリズム
Input: a, b
Output: x, y, gcd(a, b)
[STEP 1]x0=1, x1=0, y0=0, y1=1, r_0=a, r_1=b, j=0
[STEP 2]r_j+1=0でない間,jを1ずつ増加させつつ、以下を繰り返し:
[STEP 2-1]r_jをr_j+1で割ったときの商をq_j+2,余りをr_j+2とする。
[STEP 2-2]以下を計算する。
x_j+2=x_j – q_j+2 * x_j+1,
y_j+2=y_j – q_j+2 + y_j+1
[STEP 3]gcd(a,b)=rj, x=xj, y=yjを出力して終了
※実際にdを求めるときにはyは不要。gcd(a, b)も1になるような値を選ぶので計算不要。
※ｘが負の数のなった場合は、Ｌの倍数を足して正の値にすればよい。
※指数計算（逆数計算）のアルゴリズム
Input: e, L (L=lcm(p-1,q-1))(gcd(e,L)=1)
Output: d = (e^-1) mod L
[STEP1] d0=1, d1=0, r0=e, r1=L, j=0
[STEP2]r_j+1=0でない間,jを1ずつ増加させつつ、以下を繰り返す
[STEP2-1]r_jをr_j+1で割ったときの商をq_j+2,余りをr_j+2とする
[STEP2-2]d_j+2=d_j-q_j+2*d_j+1を計算する
[STEP3]d=d_j+1を出力して停止。ただし、dが負であればＬの倍数を加えて正の値としてものを出力。
※公開指数として所定の小さな数を使うものがあるが、危険性があり、大きな乱数を使う。その際、gcd(e,L)=1となるように選ばなければならないが、
L=lcm(p-1,q-1)は、偶数となる
ので、eとして奇数をとればよい。
◆素数
＿◇素数の発見方法
①順番に調べる
②素数を生み出し易い式を使う。（必ず素数を生み出す式は無い。）
n^2+n+41
4*n^2+4*n+59
4*n^2+170*n+1877
③適当に浮かんだ数が素数かどうかチェックする。
＿◇素数判定法
①フェルマーの小定理
「ある数nが素数なら、nを法とする世界の全ての数がn-1乗で必ず１になる。」
全ての数について調べるのは現実的ではない。たまたま素数ではないのに、特定の数のn-1乗が１になる擬素数があるが、複数個しらべれば、まずは見破れる。
※カーマイケル数
素数そっくりに多くの数でフェルマーの小定理を満たすもの。例５６１。
②Miller-Rabin法
※2，3，5，7を使って誤判定する250億以下の唯一の数
3215031751
◆素因数分解
素因数分解は難しい（多大な計算時間がかかる）
＿◇RSA factoring challenge
※RSA-640 … 640bitの数
2005/11に解かれたが、一般数体ふるいというアルゴリズムを実装した80個の2.2GHz opteronプロセッサで5ヶ月を要した。
http://mathworld.wolfram.com/news/2005-11-08/rsa-640/
◆一方向関数
one way function
今のところ、一方向関数であると数学的に証明されたものは知られていない。
一方向関数だと信じられているもの
素数どうしの掛け算（容易）
素因数分解（困難）
◆Elgamal暗号
※離散対数問題
素数Ｐを法とする世界には、べき乗すると全ての数に変化できる原始元と呼ぶ数が存在する。（原始元ではべき乗結果とべき乗数が１対１の対応になっている）原始元のべき乗結果から何乗したかを求める問題を離散対数問題と呼ぶ。
双方で、素数Ｐを法とする世界で原始元をそれぞれの秘密鍵をつかってべき乗し、その結果をそれぞれの公開鍵として交換する。それぞれ相手の公開鍵を自分の秘密鍵でべき乗することで共通の鍵とし、送信側は平文に共通の鍵を乗じることで暗号化し、、受信側は共通鍵で割ることで復号する。
◆PKCS (Public-Key Cryptography Standards)
PKCS#1 RSA暗号署名に関する標準
PKCS#3 Diffie-Hellman鍵共有に関する標準
PKCS#5 パスワードベースの暗号標準
PKCS#6 拡張証明書の形式に関する標準
PKCS#7 暗号メッセージの形式に関する標準
PKCS#8 秘密鍵情報の形式に関する標準
PKCS#9 属性タイプに関する標準
PKCS#10 証明書要求(CSR)に関する標準
PKCS#11 暗号トークン（ユーザ認証データ）のインタフェースに関する標準
PKCS#12 個人情報交換の形式に関する標準
PKCS#13 楕円曲線暗号に関する標準
PKCS#15 暗号トークンのフォーマット標準
◆楕円曲線暗号
y^2 = x^3 + αx + β
Weierstrass型の楕円曲線上の点についての、点と点との間の計算に離散対数問題と同様の問題が存在する。従来の離散対数問題より難しい。
◎攻撃法
◆ブロック暗号の攻撃法
＿◇差分解読法
1989年, BihamとShamirが発見。
※しかし、DES設計者は1974年に既に発見し、ＤＥＳに対策を組み込んでいた。
※差分＝排他的論理和
未知の鍵データＫがデータa,bに排他的論理和されたとき
(a ^ K) ^ (b ^ K) = (a ^ b) ^ (K ^ K) = a ^ b
となって、鍵Ｋが消えてしまう。
※暗号文の差分を調べ、これに偏りがあると、それを手がかりにして鍵の候補を絞っていくことができる
＿◇線形解読法
1993年, 三菱電機松井充が発見。1994年に世界初のDES解読に成功した。
◆サイドチャネル攻撃
暗号理論でなく、暗号処理する際の処理時間や消費電力などの情報をつかって行う攻撃
①SPA (Simple Power Analysis)
②DPA (Differential Power Analysis)
ＩＣカードに記録されたＤＥＳ鍵を求める実験に成功
※対策：計算時間や消費電力を一定にしたり、ノイズをのせる。
◎乱数
統計的一様性 出現頻度のかたよりがない
無相関性 ある数が他の数の出現に影響しない
非線形性 数の予測が不可能
長周期性 出現パターンの繰り返しが短くない
真性乱数 truly-random numbers
自然界の揺らぎを利用して作られた乱数。
擬似乱数 pseudo-random numbers
なんらかのシードから順々に作られるもの、初期値が決まれば出力を予測可能。通常、長い周期を持つ周期列。周期が短いと暗号用の乱数としては役に立たない。
※暗号用乱数
出力ビットから続くビット列を計算するには、多大な計算時間がかかるようなものでないと、暗号用乱数として役に立たない。
※数値実験に使う乱数
⇒素性の良さを把握できるとよい
◆一様乱数
＿◇線形合同法
linear congruential method
単純な方法で、全体としては乱数に見えるが、下位ビットの周期が短いので、規則性が簡単にわかってしまう。
⇒出力ビットから続くビット列を簡単に予測できる
Xn = (A*X_n-1 + B) mod C
乗数A, 法(modulus) Cは正整数
加数B 非負整数
⇒
B=0…乗算型合同法
B≠0…混合型合同法
の形の漸化式でビット列を作り出す。
⇒連続する出力を代入して連立方程式を解けば、Ａ，Ｂ，Ｃを求めることができる。
⇒Xnのとりうる値は,0…C-1
⇒周期列となるので、Cには
2^計算機のビット数
2^(計算機のビット数-1)
上記を越えない最大の素数
例）適当な初期値に６９０６９次々と掛け、２進で表したものの下位３２ビットを取る。
※定理
線形合同法が最長周期Cを持つための必要条件
以下全てがみたされること
i) BとCが互いに素
ii)A-1がCの全ての素因数で割り切れる
iii)Cが4の倍数ならばA-1も4の倍数である
※RANDU
⇒昔のポピュラーだったが、悪い例
C=2^31, A=65539, B=0
⇒３次元単位立方体内に点列{(Xn, Xn+1, Xn+2)}をプロットすると、15枚の平行で等間隔の平面
9*x-6y+z=k (K=-5…9)
にのってしまう。
※合同法乱数列の他次元疎結晶構造
s次元空間内に点列をプロットすると、(s!*m)^(1/s)毎のs-1次元超平面の上にのってしまう
※超平面間の間隔(1/νs)を計算することで生成される乱数列のよさを判定する
⇒スペクトル検定
νs:ｓ次元精度
＿◇M系列にもとづく方法
Ｍ系列
Maximum length linearly recurring sequence
０と１からなる周期列。
⇒シフトレジスタ系列
a_n=c1*a_n-1+c2*a_n-2+…+cp*a_n-p (mod 2)
ここで
ci(1≦i≦p-1)は０または１
cp＝１
初期値a0…a_p-1、少なくとも一つが０でない限り任意
ここで周期が最大の2^p – 1 であるものをM系列とよぶ
※通常は
f(x)=1+x^q+x^p (q<p)
⇒pが1000以下で、周期2^p – 1 が素数となるものの例
p q
89 38
127 1,7,15,30,63
521 32,48,158,168
607 105,147,273
1279 216,418
2281 715, 915, 1029
3217 67, 576
4423 271,369, 370, 649, 1393, 1419, 2098
9689 84, 471, 1836, 2444, 4187
◎ハッシュ関数
Hash Function
(Hash 細切れにする）
自由な大きさの数を、ある一定の大きさ以下の数に変換する数式。出力となるハッシュ値は偏らないことが重要。
⇒任意のバイト列を入力として、その入力を代表する固定長の出力を返す関数
一方向性
衝突困難性
①メッセージダイジェストから入力データを推測できない
②衝突するような入力データを容易に作成できない
③衝突が発生する可能性が非常に低い
※衝突 異なるメッセージに対して同一のメッセージダイジェストが発生すること。メッセージダイジェストのサイズよりも大きいデータに対しては必ず衝突が発生する。
衝突が起きるのに必要なサンプル数は、ｍではなく√（ｍ）に比例するので、ハッシュ関数の強度は、メッセージダイジェストのビット数の半分
※２つのデータが同じであるかどうかの検証を高速化する。
例）公開鍵暗号の処理は遅いので
ドキュメント→ハッシュ関数→メッセージダイジェスト
これを公開鍵暗号でドキュメントの署名とする
※ハッシュ関数例
①ＣＢＣ－ＭＡＣ （ブロック暗号のＣＢＣモードを使う）
②ＭＤ５ ＲＳＡ
md5sum
③ＳＨＡ－１ アメリカ標準
④RIPEMD160 ヨーロッパ標準
※メッセージダイジェスト（改ざんを発見するための要約値）として使う。
◆暗号的に安全なハッシュ関数
cryptographically secure hash function
①異なる入力値に対して同じ出力値が返る可能性がとても低い
②似た入力値から似た出力値が返らない
③出力値が均一に分布
④出力値から入力値が推定できない
◆MD2, MD4, MD5
Message Digest 2, 4, 5
リベスト氏考案。
MD5
メッセージダイジェストのサイズ 128ビット
※RFC1320
※２＾６４程度のサンプル数で衝突が起こる可能性がある
◆SHA-1, SHA-256, SHA-384, SHA-512
Secure Hash Algorithm 1, 256, 384, 512
NSA（米国家安全保安局）考案ハッシュ関数
メッセージダイジェスト長
SHA-1 160ビット
SHA-256 256ビット
SHA-384 384ビット
SHA-512 512ビット
※SH-1：衝突を見つけるのに必要なメッセージの数が理想的な場合と比べ約１３万分の１まで減らせるという結果が既に知られている(2005/02)
◎鍵共有法
①公開鍵暗号
②Kerberosセンタによる共通鍵の生成
③Diffie-Hellman鍵共有
参考）Elgamal暗号
④ID-NIKS
ID-based Non-Interactive Key Sharing
あらかじめID（のハッシュ値など）から暗号に使える乱数値を対象行列にしたものを用意し、各対応の１行をそれぞれに配布（秘密）しておく。通信する場合、それぞれの行から特定の相手と通信する場合の値が得られるので事前通信なしでの暗号化が可能になる。
◎認証
◆相手認証
①パスワード
②ワンタイムパスワード
S/Key, OPIE, OTP
親パスワードCと認証できる回数Nを決めておく。センター側は親パスワードCをハッシュ関数hにN回入れた結果だけを覚えておく。認証時には、認証できる残り回数N-1を伝え、認証をうける側はハッシュ関数にN-1回いれた結果を子パスワードとする。センタ側では届いたパスワードを１回ハッシュに通せば記憶した結果と一致することで認証できる。
③ゼロ知識対話証明
パスワードを教えないがパスワードを知っていることを証明できる。
暗証番号M、素数P,Qを生成しておく
法とする数P*Q、暗証番号の二乗M^2を公開しておく
ユーザーは認証時には乱数rを発生し、r^2を送信する。
センタ側はそれについて白か黒かを問う
ユーザーは白ならr,黒ならr*Mを回答する
センタは白のときr^2, 黒の時r^2*M^2になるか検証する。
※Mを知らない偽者は、白か黒か一方に備えると他方に備えられず２分の一の確率でしか質問に正解できず、この対話を２０回も行えば１００万分の１の確率でしか破れない認証ができる。
④チャレンジ＆レスポンス
APOP
センタでは乱数rを発生し、これをユーザに送る。ユーザではパスワードＣにrを加えた値をハッシュに通し、子パスワードとしてセンタへ返す。センタでは、同様にパスワードＣにrを加えてハッシュを通したものとレスポンスを比較して認証する。
◆データ認証
①ハッシュ関数、ＭＡＣ
②ブラインド署名
③デジタル署名
④電子透かし
◎暗号化アプリケーション
◆CSS
content scramble system
DVDの映画タイトルなどを不正コピーから守るための暗号技術
DVD CCA(Copy Control Association)による
Master Key – Disk Key – Title Key の３階層
DVDプレーヤは機種毎に固有のMater Keyを保持する
Master KeyはCCA管理で、DiskKeyはすべてのMaster Keyで暗号化し、Master Key数分のDisk keyセットとしてDiskに格納されている。機種固有のMaster KeyでDisk keyセットからDisk keyをとりだし、そのDisk KeyでTitle Keyを解読し、Title Keyを使って再生する。
◎量子暗号
◆量子ビット（キュービット）
スピンのように２つの状態が可能な系を２状態系という
⇒量子力学の重ね合わせの原理により、２つの状態のどちらか一方ではなく、両方が重なった状態である。
※１量子ビットで０と１を同時にあらわすことができる
◆ショアのアルゴリズム
量子コンピュータを使った素因数分解のアルゴリズム
①素因数分解をしようとする数Ｎより小さい数ｘを選ぶ
②ｘ＾ｒ÷Ｎの余りを探す。余りのリストは繰り返すので、繰り返しの周期ｐを求める
③ｘ＾（p/2)-1、ｘ＾（p/2)＋1を計算する
これらとＮの最大公約数は、高い確率でＮの素因数になる
※②のステップを量子コンピュータで並列計算する。しかし、結果を読み取ろうとすればデコヒーレンスにより１つに収束してしまうので、干渉を使って読み取る
◆量子暗号システム
量子通信で共通鍵を、古典通信でデータを送る
＿◇量子暗号の特徴
①解読できない
②盗聴は検出できる
＿◇光子の偏光をつかう
不確定性関係から両立できない２種の偏光を使う
①アリスはランダムに２種の偏光方式を選び、それぞれの方式で０か１かに判定できる光子を送る
②ボブはランダムに２種の偏光方式を選び、データを解読する。たまたま方式が一致すれば答えは合うが、不一致ならば答えは合ったり、あわなかったりする。
③古典通信を使って、選択した偏光方式を相互に伝える。方式が一致したデータを残して、他は捨てると、アリスとボブは共通鍵を得たことになる。
④共通鍵を使って暗号化したデータを古典通信で送る
※途中でイブが盗聴すると、アリスとボブの方式が一致しているのにイブの方式が違うケースでは、光子の偏光を壊してしまう。⇒結果が一致しない可能性がでてくる。
※共通鍵として残した変更のうち、いくつかについて答え合わせをすると、誰かが盗聴していると分かる