現代暗号 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 有限群，部分群，巡回群  有限群 𝐺が有限集合のとき，(𝐺,∗)は有限群と呼ばれる部分群加法群(𝐺, +)において，Ｇの部分集合𝐻を考える．このとき 𝐻, + も群であるなら， 𝐻, + を 𝐺, + の部分群という．  巡回群加法群 𝐺, + において，𝑎 ∈ 𝐺に対し， 𝑎 = … , −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