現代暗号

現代暗号
t-matsu
シーザー暗号



H -> I
A -> B
L -> M
暗号アルゴリズム
 文字をnずらす
鍵
 1文字
現代暗号

暗号化アルゴリズムと鍵を明確に分ける

暗号化アルゴリズムは公開する

鍵は秘密にする
現代暗号の利点

暗号強度を公開の場で議論できる

暗号化アルゴリズムを標準化できる

鍵を変えることで暗号通信が実用可能になる
ケルフホフスの原理
秘密鍵s以外の全てを敵が知ったとしてもなお
安全であるべきである



現代暗号の原点
暗号方式の安全性の議論が可能
標準化が可能
共通鍵暗号と公開鍵暗号

共通鍵暗号
秘密の共通鍵sを共有する
 sで暗号化したものはsで復号化できる
 比較的高速


公開鍵暗号
暗号鍵PKと復号鍵SKを使う
 暗号鍵PKを公開してしまう
 PKからSKを求めることが困難である必要がある
 低速であることが多い

暗号方式の記述




平文集合M
鍵の集合K
暗号化アルゴリズムEnc
復号化アルゴリズムDec
𝑘 ∈ 𝐾, 𝑚 ∈ 𝑀とする.
暗号化
復号化
𝑐 = 𝐸𝑛𝑐𝑘 (𝑚)
𝑚 = 𝐷𝑒𝑐𝑘 (𝑐)
が成り立つ.
共通鍵暗号

ブロック暗号
 DES
 TDEA
 AES

ストリーム暗号
 OFB
 CFB
 RC4
数学的準備
合同式
整数𝑎, 𝑏の差 𝑎 − 𝑏が0,または正整数𝑁の倍数であると
き,
𝑎 = 𝑏 𝑚𝑜𝑑 𝑁
と書き,𝑎と𝑏とは𝑁を法として合同であるという.
特に𝑁 = 0 𝑚𝑜𝑑 𝑁なので,
−𝑥 = 0 − 𝑥 = 𝑁 − 𝑥 𝑚𝑜𝑑 𝑁
0, … , 𝑁 − 1 の整数の集合を𝑍𝑁 で表す.すなわち
𝑍𝑁 = {0,1,2, … , 𝑁 − 1}
また,𝑍𝑁 のうち,𝑁との最大公約数が1 (𝑁と互いに素)で
ある
整数の集合を𝑍𝑁∗ と表す.
𝑍𝑁∗ = {𝑥|1 ≦ 𝑥 ≦ 𝑁 − 1, gcd 𝑥, 𝑁 = 1}
合同式の例






4 = 1 𝑚𝑜𝑑 3
−2 = 1 𝑚𝑜𝑑 3
𝑍6 = 0,1,2,3,4,5
𝑍7 = 0,1,2,3,4,5,6
𝑍6∗ = 1,5
𝑍7∗ = {1,2,3,4,5,6}
群
代数系
任意の𝑎, 𝑏が正整数のとき,𝑎 + 𝑏も正整数になる.
このとき正整数は, + について閉じているという

群
整数の集合𝑍は, + について閉じているのみならず,以下の性質を満たす
•
結合律𝑎 + 𝑏 + 𝑐 = 𝑎 + 𝑏 + 𝑐が成り立つ
•
任意の𝑎 ∈ 𝑍に対し,𝑎 + 0 = 0 + 𝑎となる単位元0 ∈ 𝑍が存在する
•
任意の𝑎 ∈ 𝑍に対し,𝑎 + −𝑎 = −𝑎 + 𝑎となる逆元 − 𝑎 ∈ 𝑍が存在する
このようなとき 𝑍, + は群をなす.

一般に 𝐺,∗ が結合律を満たし,
単位元と逆元が存在するとき, 𝐺,∗ を群という.
さらに交換律𝑎 ∗ 𝑏 = 𝑏 ∗ 𝑎が成り立つ群 𝐺,∗ を可換群という.
加法群と乗法群

加法群
 単位元は0
 逆元は

−𝑥
乗法群
 単位元は1
 逆元は𝑥
−1
有限群,部分群,巡回群

有限群
𝐺が有限集合のとき,(𝐺,∗)は有限群と呼ばれる
部分群
加法群(𝐺, +)において,Gの部分集合𝐻を考える.
このとき 𝐻, + も群であるなら, 𝐻, + を 𝐺, + の部分群という.

巡回群
加法群 𝐺, + において,𝑎 ∈ 𝐺に対し, 𝑎 = … , −2𝑎, −𝑎, 0, 𝑎, 2𝑎, …

は, 𝑎 , + は 𝐺, + の部分群になる.
また,ある𝑎 ∈ 𝐺に対しG = 𝑎 となるとき, 𝐺, + は巡回群と呼ばれ,
𝑎は𝐺の生成元と呼ばれる.
∗
𝑍𝑝
𝑝を任意の素数とすると𝑍𝑝∗ = {1,2, … 𝑝 − 1}は,




𝑝 − 1個の要素を持つ
有限群である
巡回群である
生成元𝑔が存在する
有限体𝐺𝐹(𝑝)
𝑝を任意の素数とした𝑍𝑝∗ = 1,2, … 𝑝 − 1 の世界は,
1
𝑎
任意の𝑎 ∈ 𝑍𝑝∗ において 𝑚𝑜𝑑 𝑝が存在する.
𝑚𝑜𝑑 𝑝の世界では,加算,減算,乗算,除算が自由に行える.
四則演算が自由に行える世界を体と呼ぶ.
要素数が有限の体を有限体またはガロア体と呼ぶ.
これを要素数𝑄を用いて𝐺𝐹 𝑄 と書く.
ガロア体には0も含まれる
※ 𝐺𝐹 = 𝐺𝑎𝑙𝑜𝑖𝑠 𝐹𝑖𝑒𝑙𝑑
有限体の例
𝑝 = 11とした𝐺𝐹(11)を考える
 𝐺𝐹(11) = {0,1,2,3,4,5,6,7,8,9,10}
 3 + 5 = 8 , 9 + 4 = 2, 5 × 3 = 4, 3 ÷ 2 = 7
 生成元 𝑔 = 2
21 = 2, 22 = 4, 23 = 8, 24 = 5, 55 = 10,
26 = 9,27 = 7, 28 = 3, 29 = 6, 210 = 1,
フェルマーの小定理
𝑝を任意の素数とした𝑍𝑝∗ = 1,2, … 𝑝 − 1 に対し,
任意の𝑎 ∈ 𝑍𝑝∗ において,
𝑎𝑝−1 = 1 𝑚𝑜𝑑 𝑝
が成り立つ.
オイラーの定理
正の整数𝑛,𝑎を𝑛と互いに素な正の整数としたとき,
𝑎𝜑(𝑛) = 1 𝑚𝑜𝑑 𝑛
が成立する.ここで𝜑(𝑛)はオイラーの関数である.
𝑟
𝑟
𝑟
𝑟
ここで𝜑 𝑛 は,𝑛 = 𝑝11 𝑝22 … 𝑝𝑑𝑑 = 𝑑𝑖=1 𝑝𝑖 𝑖 とすると,
𝑟 −1
𝑟 −1
𝑟 −1
𝜑 𝑛 = 𝑝11 𝑝1 − 1 𝑝22 𝑝2 − 1 … 𝑝𝑑𝑑 (𝑝𝑑 − 1)
となる.
※ ここで
𝑛 = 𝑝(𝑝は素数)の場合𝜑(𝑛) = 𝑝 − 1
𝑛 = 𝑝 ∗ 𝑞(𝑝と𝑞は互いに素の素数)の場合𝜑(𝑛) = (𝑝 − 1)(𝑞 − 1)
になることに注意する.
暗号を解読してみよう
ElGamal暗号


𝐺𝐹 𝑝 の𝑝と生成元𝑔を選ぶ.
∗ からランダムに選ぶ.
𝑥を𝑍𝑝

ℎ = 𝑔 𝑥 とする.
𝑝, 𝑔, ℎ を公開し𝑥を秘密鍵とする.
平文𝑚 ∈ 𝑍𝑝∗ において,𝑟 ∈ 𝑍𝑝∗ とし,暗号文𝑐1 と𝑐2 を

𝑐1 = 𝑔𝑟 , 𝑐2 = 𝑚 × ℎ𝑟 と計算する
暗号文𝑐1 , 𝑐2 ∈ 𝑍𝑝∗ において暗号文𝑚を


𝑚 = 𝑐2 × (𝑐1𝑥 )−1
と計算する
ElGamal暗号の安全性




DL問題
𝐺を素数位数𝑝の巡回群, 𝑔を𝐺の生成元, ℎを𝐺の元とする.
𝐺, 𝑝, 𝑔, ℎ が与えられたときに𝑔 𝑥 = ℎ 𝑚𝑜𝑑 𝑝となる𝑥を求める問題
DL仮定
DL問題を解く効率的なアルゴリズムは存在しないという仮定
CDH問題
𝐺を素数位数𝑝の巡回群, 𝑔を𝐺の生成元, 𝑥, 𝑦 ∈ 𝑍𝑝∗ とする.
𝐺, 𝑝, 𝑔, 𝑔 𝑥 , 𝑔 𝑦 が与えられたときに𝑔 𝑥𝑦 (𝑚𝑜𝑑 𝑝)を求める問題
CDH仮定
CDH問題を解く効率的なアルゴリズムは存在しないという仮定
ElGamal暗号を解読してみよう





𝑝 = 71887, 𝑔 = 323
𝑥 = 3322とする.
𝑐1 = 38073
𝑐2 [] = {49456,14883,15327,2297,1853,41831}
𝑚[] = {? , ? , ? , ? , ? , ? }
※オーバーフローに注意
ポーリック・ヘルマン暗号






素数𝑝を選ぶ
gcd(𝑒, 𝑝 − 1) = 1となる𝑒を選ぶ
𝑒𝑑 = 1 𝑚𝑜𝑑 𝑝 − 1となる𝑑を選ぶ
秘密鍵を(𝑝, 𝑒, 𝑑)とする
平文𝑚 ∈ 𝑍𝑝∗ において暗号文𝑐を
𝑐 = 𝑚𝑒 𝑚𝑜𝑑 𝑝 と計算する
暗号文𝑐 ∈ 𝑍𝑝∗ において暗号文𝑚を
𝑚 = 𝑐 𝑑 𝑚𝑜𝑑 𝑝 と計算する
ポーリック・ヘルマン暗号


秘密鍵 𝑝, 𝑒, 𝑑 のうち(𝑝, 𝑒)を公開しても良さそうである
𝑝, 𝑒 から𝑑を計算できるため,公開すると暗号にならな
い

𝑝 − 1と𝑒から𝑑を導き出せる
RSA暗号






素数𝑝と𝑞を選ぶ, 𝑛 = 𝑝 ∗ 𝑞とする(𝑝と𝑞は互いに素である
)
gcd(𝑒, (𝑝 − 1)(𝑞 − 1)) = 1となる𝑒を選ぶ
𝑒𝑑 = 1 𝑚𝑜𝑑 (𝑝 − 1)(𝑞 − 1)となる𝑑を選ぶ
𝑛, 𝑒 を公開鍵とする
平文𝑚 ∈ 𝑍𝑝∗ において暗号文𝑐を
𝑐 = 𝑚𝑒 𝑚𝑜𝑑 𝑛 と計算する
暗号文𝑐 ∈ 𝑍𝑝∗ において暗号文𝑚を
𝑚 = 𝑐 𝑑 𝑚𝑜𝑑 𝑛 と計算する
RSA暗号



𝑛, 𝑒 を公開しても良い
𝑛から(𝑝 − 1)(𝑞 − 1)を求めるのは困難である
(𝑝 − 1)(𝑞 − 1)がわからなければ,
𝑒𝑑 = 1 𝑚𝑜𝑑 𝑝 − 1 𝑞 − 1
を求めることはできない
これをRSA仮定と呼ぶ
RSA暗号を解読してみよう




𝑝 = 3343, 𝑞 = 233とする
𝑒 = 216 + 1 = 65537とする.
𝑐[] = {488868,341908,351702,341908,682283,
105258,682283,472843,608335}
𝑚[] = {? , ? , ? , ? , ? , ? , ? , ? , ? }
※型のある言語の人はオーバーフローに注意
Attack RSA
𝑒 = 3のときを考える
同じ𝑒と平文𝑚を使用した暗号文を少なくとも𝑒個集める



𝑐1 = 𝑚3 𝑚𝑜𝑑 𝑛1
𝑐2 = 𝑚3 𝑚𝑜𝑑 𝑛2
𝑐3 = 𝑚3 𝑚𝑜𝑑 𝑛3
この3つから
𝑐 = 𝑚3 𝑚𝑜𝑑 𝑛1 𝑛2 𝑛3
となる𝑐を求める 𝑚3 < 𝑛1 𝑛2 𝑛3 が明らかなので,
この𝑐の3乗根を求めることで𝑚が求まる
Attack RSA
𝑛2 𝑛3 𝑥1 = 1 𝑚𝑜𝑑 𝑛1
𝑛1 𝑛3 𝑥2 = 1 𝑚𝑜𝑑 𝑛2
𝑛1 𝑛2 𝑥3 = 1 𝑚𝑜𝑑 𝑛3
となる𝑥𝑖 を求め,
𝑐1 𝑛2 𝑛3 𝑥1 + 𝑐2 𝑛1 𝑛3 𝑥2 + 𝑐3 𝑛1 𝑛2 𝑥3 = 𝑚3 𝑚𝑜𝑑𝑛1 𝑛2 𝑛3
を計算する
Attack RSA
実際にやってみる
𝑒 = 3, 𝑚 = 10 , 𝑛1 = 17, 𝑛2 = 11, 𝑛3 = 19 とする.
𝑐1 = 14, 𝑐2 = 10, 𝑐3 = 12
𝑥1 = 7, 𝑥2 = 3, 𝑥3 = 6 となる.
14 ∗ 11 ∗ 19 ∗ 7 + 10 ∗ 17 ∗ 19 ∗ 3 + 12 ∗ 17 ∗ 11 ∗ 6 𝑚𝑜𝑑 3553
= 1000 𝑚𝑜𝑑 3553
3
1000 = 10