情報セキュリティ
第５回
ＥｌＧａｍａｌ暗号
脅威と暗号技術
セキュリティに対する脅威
盗聴
（秘密が漏れる）
脅かされる特性
暗号技術
共通鍵暗号
機密性
公開鍵暗号
改竄
（情報が書き換えられる）
正真性
一方向ハッシュ関数
なりすまし
（正しい送信者のふりをする）
認証
メッセージ認証コード
否認
（後から私じゃないと言う）
否認不可能性
デジタル署名
公開鍵暗号系
公開鍵暗号系
受信者
送信者
非対称暗号系とも呼ぶ。
平
公開鍵と秘密鍵がある。
鍵配送問題を解決する。
文
入力サイズ（ビット数）が大きいと解く
m
のが困難な問題を利用する
離散対数問題（ElGamal暗号）
素因数分解問題（RSA暗号）
公開する
ナップサック問題
暗
号
化
復
号
暗号文c
敵
秘密鍵SＫ
公開鍵PＫ
３っのアルゴリズム
鍵生成アルゴリズムG
公開鍵PKと秘密鍵SKを生
成する。
暗号化アルゴリズムE
暗号文cを生成する。
c=EPk(m)
復元アルゴリズムD
暗号文cを復号する。
m=DSk(c)
平
文
m
鍵生成アルゴリズムG
平文
m
暗号化アルゴリズムE
公開鍵PＫ
秘密鍵SＫ
暗号文
c
公開鍵PＫ
暗号文
c
復元アルゴリズムD
秘密鍵SＫ
平文
m
合同式
合同式： a≡b (mod N)
整数aとbの差（a－b）が正整数N
の倍数であるとき、a≡b (mod N)
と書く。
(a mod N)=(b mod N)
⇔ a≡b (mod N)
a=qN+r ⇔ a≡r (mod N)
例: 5≡2 (mod 3)
例：9x13≡2x6 (mod 7)
確認1（差が７の倍数か？）
9x13－2x6=117－12=105
(a－b) mod N = 0 105÷7=15余り0
確認2（それぞれ７で割った余りが
一致するか？）
9x13÷7=16余り5。従って、
(a mod N)
9x13≡5 (mod 7)
= (b mod N)
2x6÷7=1余り5。従って、
2x6≡5 (mod 7)
同一の法を有する合同式
は、＋、－、×に限り、等
式（＝）と同様に計算出来
る。
a≡a’ (mod N)かつb≡b’ (mod N)
⇒ (a±b)≡(a’±b’) (mod N)、
(ab)≡(a’b’) (mod N)
例１:
9≡2 (mod 7), 13≡6 (mod 7)
⇒ 9+13≡2+6 (mod7)
9x13≡2x6 (mod7)
例２: 2250 (mod7) を求め
よ。
2250≡(9+13)50≡(2+6)50≡150 ≡1
2250を計算しない!!
(2+6) mod 7 = 1
mod Nの集合（ZN）
mod Nの集合（Nで割った余りの
集合）
xとNは互いに素
Z*N={x|1≦x≦N－1, gcd(x,N)=1}
ZN={0,..,N-1}
例： Z6={0,1,2,3,4,5}
a≡b (mod N)かつa∈ZN
⇒ a=(b mod N)
例： 2=(8 mod 6)
－xとはx+(－x)≡0 (mod N) を満
たす数。
1+6≡0 (mod 7)より
6≡－1 (mod 7)
1≡－6 (mod 7)
N－x≡－x (mod N)
減算a－bは、
a+(－b)と考える
gcd(1,6)=1
gcd(2,6)=2
gcd(3,6)=3
gcd(4,6)=2
gcd(5,6)=1
ZNはZ*Nを含む
Z*N⊂ZN
gcdとは、最大公約数
例1： gcd(8,12)=4
8の約数： 8,4,2,1
12の約数：12,6,4,3,2,1
8と12の公約数：4,2,1
8と12の最大公約数 gcd(8,12)=4
例2
Z*6 ={1,5}
Z*7 ={1,2,3,4,5,6}
gcd(1,7)=1, gcd(2,7)=1
gcd(3,7)=1, gcd(4,7)=1
gcd(5,7)=1, gcd(6,7)=1
素数
素数pとは：
原始元（生成元）
1とp以外に約数を持たない2
素数pに対し、ordp(g)=p－1となる
以上の整数pを素数と呼ぶ。
gをZ*pの原始元という。
例： 2,3,5,7,11,13,..
定理5.3
pが素数 ⇒ Z*p={1,2,..,p－1}
pは素数、 gはZ*pの原始元とする。
フェルマーの定理
ai=(gi mod p)、 i=0,..,p－2と置くと、
{a0,a1,..,ap-2}={1,2,..,p－1}
pが素数の時、任意のa∈Z*p
p－1
に対してa ≡1 (mod p)が成
立つ。
mod 5の場合
素数p=5の場合の確認
Z5={0,1,2,3,4}, Z*5={1,2,3,4}
24≡16≡1 (mod 5)
位数ord5(4)=2
定理5.3
4
3 ≡81≡1 (mod 5)
20≡1 (mod 5), 30≡1 (mod 5), 40≡1 (mod 5)
44≡256≡1 (mod 5)
21≡2 (mod 5), 31≡3 (mod 5), 41≡4 (mod 5)
位数ordp(a)
22≡4 (mod 5), 32≡4 (mod 5), 42≡1 (mod 5)
素数p、a∈Z*pに対し、ax≡1
(mod p)となる最小の正整数x
23≡3 (mod 5), 33≡2 (mod 5), 43≡4 (mod 5)
を位数ordp(a)と言う。
24≡1 (mod 5), 34≡1 (mod 5), 44≡1 (mod 5)
フェルマーの定理より、
1≦ordp(a)≦p－1
3はZ*5の原始元
2はZ*5の原始元
例： ord5(4)=2
フェルマーの定理
離散対数問題
離散対数問題とは：
定理5.3
素数pが大きいと解くの
に膨大な時間がかかる
素数p、 Z*pの原始元g、 a∈Z*pに対し、
a=(gx mod p)
を満たすx∈{0,1,..,p－2}を求めよ。
離散対数xは必ず存在する。
離散対数仮説とは：
p,g,a
x
整数だけを考えるから離散
次の式を満たす離散対数x∈{0,1,2,3}
を求めよ。
離散対数問題を多項式時間で解ける
アルゴリズムはない。
多項式の例：5x20+13x3
素数pが大きいと解けない。 指数関数の例：20x
解の候補数（pは1024ビット）
離散対数問題を解く
アルゴリズム
原始元g=2の場合
答 x=0
答 x=1
答 x=3
答 x=2
1=(2x mod 5)
2=(2x mod 5)
3=(2x mod 5)
4=(2x mod 5)
|Zp-1|≒21024≒(103)102=10306
原始元でない4の場合
1GHzマシンが1クロックで集合Zp-1内の1つ候補
が解かどうかチェック出来るとする。全部チェック
する時間は10306/109x60x60x24x365=10290年。
1=(4x mod 5)
2=(4x mod 5)
3=(4x mod 5)
4=(4x mod 5)
答 x=0,2
答 存在しない
答 存在しない
答 x=1,3
答えが複数ある
ＥｌＧａｍａｌ暗号
鍵生成
素数p、Z*pの原始元gを選ぶ。
秘密鍵x∈Zp-1をランダムに選び、
y=(gx mod p)を計算する。
Pk=(p,g,y)を公開鍵する。
暗号化
公開鍵Pk=(p,g,y)と平文m∈Zpから
次のように暗号文C=(c1,c2)を求め
る：
r∈Zp-1をランダムに選び、
c1=(gr mod p), c2=(myr mod p)
復号
秘密鍵Sk=xと暗号文C=(c1,c2)か
ら次のように平文mを復号する：
m=(c2c1p-1-x mod p)
復号の証明
c2c1p-1-x≡myrgr(p-1-x) ≡mgrxgr(p-1-x)
≡mgr(p-1) (mod p)
フェルマーの定理より、gp-1≡1(mod p)
従って、 c2c1p-1-x≡m (mod p)
受信者
素数p、原始元g、離散対数x
からy=gx mod pを計算
鍵生成アルゴリズムG
PKを公開
Pk=(p,g,y)
Sk=x
送信者
平文m
暗号化アル
ゴリズムE
暗号文
C=(c1,c2)
Pk=(p,g,y)
受信者
暗号文
C=(c1,c2)
復元アル
ゴリズムD
Sk=x
平文m
パラメータ選択
素数pの選択
pが大きい程、離散対数問題は難しくなる。
p≧1024ビットであることが望ましい。
p－1は大きな素数を少なくとも一つ持つようにする。
p－1が小さな素数の積の場合、離散対数問題が
解けてしまう。
乱数ｒの選択
rはメッセージ毎に変える。
rを同じにすると、二つの平文m1とm2に対する暗号文
C1=(gr,m1yr)とC2=(gr,m2yr)から、m1yr/m2yr≡m1/m2
(mod p)が得られる。
m1が解るとm2が解る
1回目小テスト（理解度確認試験）
について
実施日：第６回講義の日
成績評価に関係する。
持ち込み可
教科書、パワーポイント参照可。
試験内容
条件付確率と順列の基礎
第１回～５回講義内容
共通鍵、公開鍵暗号系
ブロック暗号の利用モード、排他的論理和
ランダム置換族、ランダム関数族、擬似ランダム置換族
合同式、位数、離散対数
© Copyright 2024 ExpyDoc
