共通鍵方式をささえる数体
このページはマス旅の一部です。
今回は初期の暗号である「共通鍵方式」について探ってみよう。
１．ウォーミングアップ
＜暗号の基本＞
# 平文：暗号化する前の文のことです。
暗号化した文はもちろん「暗号文」といいますね。
# 鍵：平文を「暗号化」したり、暗号文を平文に戻す「復号」のための情報や技術です。
# ネットワークの通信路にある危険の代表：盗聴・改ざん・なりすまし
# 共通鍵方式：昔からあるやり方ですね。
送信者と受信者が秘密鍵を事前に共有しておくことが必要になります。
＜GF(2^8）の基本＞
前回は符号の多項式表現を作りましたね。
そのときに活躍したのがGF(2)とGF(2^8)でしたね。
#GF(2)：2要素ガロア体（GaussField）の略です。
X={0,1}の加法群をベースにしています。
加法の0+0=0,1+0=1以外に1+1=0であることから、
mod 2とか排他的論理和と呼びましたね。
ただの和ではないから、x⊕yともかきました。
GF(2)では、積が0*0=0,1*1=1,1*0=0とふつうのかけ算と同じになりますが、
x⊗yとかくこともあります。
#GF(2^8)：8ビットつまり１バイトの符号語の各ビットを
次数8-1＝７の多項式の係数に対応させたものです。
巡回符号のときに次数下げをするための法になる生成多項式Gを考えましたが、
暗号でも、法となる多項式を設定することがあります。
たとえば、p(X)＝X^8+x^4+x^3+x+1を法にすると、係数がGF(2)だから、
x^8をx^4+x^3+x+1に置き換えることができますね。
２．共通鍵暗号をざっくり見渡そう
暗号と言えば、共通鍵。
というほど、共通鍵暗号は昔からありました。
#シーザー暗号
アルファベットを３巡回シフトする暗号です。
JAPAN⇒MDSDQ
単文字置き換え暗号の代表ですね。
#転置暗号
きまった長さで文字を区切って、区切りの中で置換規則で入れ替えます。
たとえば、5文字ずつ逆順にソートする例です。
JAPAN WORLD ⇒NAPAJ DLROW
＜ストリーム暗号＞
シーザー暗号も転置暗号も1文字やn文字など細かな長さで暗号化しましたね。
ストリーム暗号はビット、バイト、ワードなどの小単位で暗号化のことです。
コツコツ暗号化するので、逐次暗号といも言いますね。
でも、これまでのストリーム暗号はどうも、努力すれば見破れそうですね。
それは、言語を作るアルファベットの情報源には
マルコフ性（出現が直前の情報に依存する規則性・確率分布がある）が強くあります。
だから、条件付き確率の計算まですれば、どの文字がどの文字の置き換えなのかが推論しやすくなるからです。
ストリーム暗号なのに「無条件に安全な暗号」というものがあります。
それが「バーナム暗号」です。
F：アルファベットのAからZの26文字を０から25の数字に置き換えます。
F（JAPAN）＝[9,0,15,0,13]
G：それに使い捨て鍵(ワンタイムパッド）としての乱数列をそれぞれの文字にたします。
Keys=[19,3,22,8,10]
G（F（JAPAN））＝F（JAPAN）+Keys
=[9,0,15,0,13] ＋[19,3,22,8,10]
＝[28,3,37,8,23]
H:これを(mod 26)の剰余にします。
H（G（F（JAPAN）））＝H（[28,3,37,8,23]）
＝[28,3,37,8,23]（mod 26）
＝[28（mod 26）,3（mod 26）,37（mod 26）,8（mod 26）,23（mod 26）]
≡[2,3,11,8,23]
F^-1:Fの逆です。０から25の数字をアルファベットのAからZに置き換えます。
F^-1（[2,3,11,8,23])＝CDLIX
このプロセスを平文JAPANの「P」を使って何が起きてるかを追跡しましょう。
F：P（0番スタートでアルファベット表参照）⇒15、
G：15（＋22）⇒37、
H：37(mod 26) ⇒11、
F：11（0番スタートでアルファベット表参照の逆）⇒L
これから、(FGHF^(-1))：P⇒L
(FGHF^(-1))： JAPAN⇒CDLIX
この操作を逆にやる、つまり、(FGHF^(-1))を逆順に逆のことをやれば
もとの平文に戻せます。
でも、Gのワンタイムパッド（使い捨て鍵）の加算が曲者ですね。
JAPANからCDLIXへは何の規則性もありません。
Keysを入手しないかぎりは復号不可能ですね。
それに、平文と同じ長さのデータを鍵として渡す必要があるので効率が悪いです。
とは言え、効率よりも秘匿性が高い通信、
たとえば、大統領どうしの通信内容とかには使われることがあるようですね。
実際にバーナム暗号を使うときは、多少の工夫をすれば使いやすくなります。
アルファベット表を手元において数えるのもめんどうですから、文字を文字コードに変換しましょう。
文字コード変換、逆変換の関数はたいていの言語には用意されているでしょう。
アルファベットを文字コードにして、さらに2進数にしても
バーナム暗号は実現できますね。
平文も暗号文も01による符号だとします。
平文がa=[10010110]、
ストリーム暗号がp=[11110000]のとき、
暗号文は平文aと鍵pの排他的論理和
c=a⊕p=[01100110]
のように計算します。
mod 26 よりも排他的論理和の方が計算しやすいです。
もし、関数が用意されてなければ、桁ごとの和にmod2をすれば大丈夫です。
復号は、これらの逆順に逆操作をするだけでできますね。
もちろん、鍵ｐのデータが手元のないと復号できません。
ここでも、鍵の長さが問題になります。
ストリーム暗号は、シャノンによると「鍵の長さが平文の長さ以上でないといけない」のです。
それは難しいので、実際は固定長（128ビットなど）の鍵を疑似乱数生成器で平文以上の長さに引きのばすことで対応するそうです。
＜ブロック暗号＞
1977年から2004年までアメリカの標準局が採用したことで
世界標準になったブロック暗号方式があります。
DES(Data Encryption Standard)暗号です。
平文を64ビットのブロックに区切って暗号化する方式です。
どんな暗号化をするかというと、次のようになります。
ブロックごとに転置暗号化（ビットの入れ替え）、
S-Box(乱数テーブルでの単文字置き換え暗号化)、
XOR(秘密鍵の値との排他的論理和）などの定型処理をするのです。
このブロック単位の1回の定型処理が１ラウンドです。これを16回繰り返します。
1つの鍵は64ビットのうち8ビットが誤り検出用なので、
事実上64-8=56ビットを使います。
すると、鍵の種類は2^56≒7.2×10^16 種類あります。
総当たりで試したとして、１つの鍵をためすのに10^(-6)秒かかったとすると全部で2283年ほどかかりますが、コンピュータを連結したり高速コンピュータを使えば１年を切るかもしれません。
＜AES＞
DESの進化版が
AES（advanced encryption standard)です。
現在のアメリカの標準暗号ですね。
AESのブロック長はDESより大きいです。128、192、256（ビット）の3種類があり、
ビットによって回すラウンド数が違うようです。
128ビットは10、192ビットは12、256ビットは14ラウンドです。
たとえば、128ビットの10ラウンドは次のように実行します。
128ビットの秘密鍵を11個作ります。
平文の方は、128ビットを1バイト（8ビット）ごとに16個に分割して、それを4×4の行列とみなします。
１つのラウンドは４つ操作があります。
SubBytes（各バイトをS-boxで置き換える),
ShiftRows(４つの行の巡回シフトでビット入れ替え）,
MixColumns（列ごとに行列積して置き換える）,
AddRoundKey(鍵とのXOR)です。
11個の鍵のうち1個目の鍵はAddRoundKeyだけやります。
残り10個の鍵で10ラウンド回します。
ただし、最終ラウンドだけはMixColumnsをやりません。
どんだけ、かき混ぜるんだよ！
という複雑化をします。
エントロピー上がりまくりですね。
でも、このほとんど跡形もないような暗号化をしても
復号できなければ、何の役にもたちません。
その「複雑化をもとに戻す代数の基盤」がガウス体GF(2^8)です。
次にそのようすを具体的に見ていきましょう。
３．AESの実装を探ろう
平文の方128ビット＝1バイト（8ビット）×16個を１ステート（4×4の行列）とします。
目まぐるしく状態がかわるから、ステートなんでしょうね。
４つの操作のかたまりをまとめて、ラウンド関数と呼びましょう。
SubBytes（各バイトをS-boxで置き換える),
ShiftRows(４つの行の巡回シフトでビット入れ替え）,
MixColumns（列ごとに行列積して置き換える）,
AddRoundKey(鍵とのXOR)です。
「鍵とのXOR」はバーナム暗号のところで暗号化、復号化をかいたので飛ばします。
１つめはSubBytesです。
＜SubBytes＞
１バイトを思い出そう。
1バイト（8ビット）は2^8=(2^4)^2なので、2個の16進数の並びです。
00からffの256通りありますね。
たてによこに0からfまでが並ぶ16×16のテーブルを「S-Box」といいます。
０行目は[63,7c,77,7b,f2,6b,6f,c6,30,01,67,2b,fe,d7,ab,76]
１行目は[ca,82,c9,7d,fa,59,47,f0,ad,d4,a2,af,9c,a4,72,c0]
.......................
ｆ行目は[8c,a1,89,0d,bf,e6,42,68,41,99,2d,0f,b0,54,bb,16]
のようになっています。
表の一番上の行は列目名です。左から順に、
列目名は[x0,x1,x2,x3,x4,x5,x6,x7,x8,x9,xa,xb,xc,xd,xe,xf]
表の一番左の列は行目名です。上から順に、
行目名も[x0,x1,x2,x3,x4,x5,x6,x7,x8,x9,xa,xb,xc,xd,xe,xf]
このテーブルを参照すると、1バイトを別の1バイトに置換できますね。
まあ、アルファベット表をかきまぜる表を参照するようなものです。
やっていることはアナログ的に考えると単純ですが、デジタルでみると変なことをやってます。たてにたどっても、よこにたどっても規則性がないのです。
デジタル的な単純さがないので、非線形置換（変換）とも言われてます。
そうはいっても、これは乱数ではないし、鍵でもなく、ただの1対1対応ですから、
可逆です。つまり、これは復号できますね。
（最近のS-boxは、GF(2^8)での逆元を求めた８ビットベクトルに、8×8行列をかけてから定数0x63をXORすることで作られているそうです。逆元にしただけで、非線形なのに手が込んでますね。）
＜ShiftRows＞
ステート（４×４行列）を行ベクトル４つとみましょう。
行ごとに巡回シフトします。シフト量は決まっています。
０行目は０、1行目は１、2行目は２、３行目は３です。
たとえば、シフト方向は左なので、次のように変わります。
[00,01,02,03]⇒[00,01,02,03]
[10,11,12,13]⇒[11,12,13,10]
[20,21,22,23]⇒[22,23,20,21]
[30,31,32,33]⇒[33,30,31,32]
これも可逆な変化ですから、復号できますね。
＜MixColumns＞
ステートを列ごとに別の行列をかけて置き換えます。
ステートの要素はそれぞれ1バイト（2けたの16進数）です。
[00,01,02,03]
[10,11,12,13]
[20,21,22,23]
[30,31,32,33]
今、みなさんはステートの世界、1バイト単位の世界にいることを
再確認してくださいね。
たとえば、
２行２列目は「11」ですが、これは10進数の10×1+1=11ではなく、
2けたの16進数なので、10進数の「16×1+1=17」を表しているとします。
さあ、いよいよ、MixColumnsの処理を始めます。
たとえば、2列目ｘ＝[x1,x2,x3,x4]^t=[01,11,21,31]^tがありますね。
これを次の行列Mにかけます。
[02,03,02,01]
[01,02,03,01]
[01,01,02,03]
[03,01,01,02]
つまり、
積Mｘの値である列ベクトルy＝[y1,y2,y3,y4]^tを同じ2列目にします。
y＝Mx
の計算がポイントです。
たとえば、このベクトルｙの第1要素は内積で求められます。
y1=M(1,1)x1+M(1,2)x2+M(1,3)x3+M(1,4)x4
=02×01+03×11＋02×21＋01×31
かけ算が４つありますが、2×1、3×11、2×21、1×31を10進数でやったらアウト！
今、1バイトの世界にいることを思い出しましょう。
１バイトの世界は、2進数の8けた、多項式では7次式の世界でした。
GF(2^8)の登場です。
各積は「２けたの16進数」の積ですね。
これを2ビット×8ビットの2進数の積にし、
さらに、2進数を係数とする多項式の積を計算します。
そして、ウォーミングアップで触れたp(X)＝X^8+x^4+x^3+x+1を法にした余りにします。
2進数を多項式に直すときは、左はしが最高位とし右はしは定数項です。
16進数積：02×01 ,03×11 ,02×21 ,01×31
２進数積：10×00000001 ,11×00010001 ,10×00100001 ,01×00110001
多項式積：ｘ×１＝ｘ ,(x+1)(x^4+1) ,x ×(x^5+1) , 1×(x^5+x^4+1)
剰余；ｘ(mod p)≡x ,x^5+x^4+x+1 ,x^6 +x , x^5+x^4 +1
ふつうの多項式の和は、
x＋ (x^5+x^4+x+1) ＋(x^6 +x) ＋ (x^5+x^4 +1)
=x^6 + 2x^5 +2x^4+ 3x+2
≡x^6 + x (mod 2)
これを2進数にすると1000010です。
下から４けたで区切ることで２けたの16進数42にできます。
y1=42と決まりました。
これをプログラミングすれば、
y=[y1,y2,y3,y4]が決定できますね。
ということは、今のは2列目だけでしたが、それを1列目から4列目まで実行すると、
ステートから新ステートが計算できますね。
１つ１つの計算だけ近視眼的にみると、
復元できそうもありませんね。
どうしましょう？？
でも、そういうときは、俯瞰してみましょう。
やっていることは、「y=Mx」というよくある行列×ベクトルですね。
xにもどすにはMの逆行列をかければよいですね。
逆行列はMの行列式がゼロでなければ存在します。
行列式は行列要素の積に符号をつけて合計しているだけだし、固定行列であれば、
前もってM^(-1)は用意できるでしょう。
GF(2^8)の数体で逆行列を計算すればよいわけです。
このように４つの操作ごとに逆関数が可能だということがわかった。
2≡0(mod 2)のため、同じものをもう一度たすと元に戻るので、
AddRoundKeyの逆関数はAddRoundKey自身です。
SubBytesにはInvSubBytes,
ShiftRowsにはInvShiftRows,
MixColumnsにはInvMixColumnsという逆関数ツールを
暗号化と逆順に同じラウンドだけ繰り返せば、
復号できるイメージがわきましたね。
４．振り返り
暗号が進化すれば解読技術が上がり、それがさらに堅牢な暗号を生む。
このいたちごっこが暗号史の原動力です。
また、AESのようなブロック暗号（128ビット単位）で長い文章を暗号化するには、
暗号化モード（ECB, CBC, CTRなど）を使います。
同じ平文ブロックでも暗号結果が変わるように初期化ベクトル（IV）やカウンターを組み合わせる工夫がなされています。
一方、AESのような「可逆（復号可能）」な暗号とは対照的に、
「不可逆（二度と元に戻せない）」な性質を極限まで高めたのが
「ハッシュ関数（SHA-256など）」です。
1文字変わっただけで結果がカオスのように激変（雪崩効果）し、
逆算が不可能であるため、
パスワードの保存やデータの改ざん検出（同一性保証）に不可欠な技術となっています。
暗号化と復号で同じ鍵を使う「共通鍵方式（対称鍵方式）」の仕組み、
その背後にある代数構造の美しさを実感していただけたでしょうか。
課題：MixColumnsをGF(2^8)のコマンドがないgeogebraで実現できますか。
できます。
先ほどやったようにステートの2列目ｘだけを行列Mをかけた積ｙのy1だけを求めましょう。
タイトルは「AES暗号のMixColumnsロジックを多項式剰余とGF(2)で実装しよう」
#M(1,1)からM(1,4)は01,02,03のどれかだから、多項式は1,x,x+1になる。
Times={1,x,x+1}
#x1,x2,x3,x4を設定します。
a="01"
b="11"
c="21"
d="31"
#16進数として読み取り10進化してから2進表示にして、01の数値列にしたのがB1～B4
text1=ToBase(FromBase(a,16),2)
text2=ToBase(FromBase(b,16),2)
text3=ToBase(FromBase(c,16),2)
text4=ToBase(FromBase(d,16),2)
La=Length(text1)
Lb=Length(text2)
Lc=Length(text3)
Ld=Length(text4)
B1=Sequence(If(Element(text1,k)=="1",1,0),k,1,La)
B2=Sequence(If(Element(text2,k)=="1",1,0),k,1,Lb)
B3=Sequence(If(Element(text3,k)=="1",1,0),k,1,Lc)
B4=Sequence(If(Element(text4,k)=="1",1,0),k,1,Ld)
# B1からB4の01を係数とした多項式P1s～P4sを作ります。
P1=Sequnece(Element(B1,k) x^(La-k),k,1,La)
P2=Sequnece(Element(B2,k) x^(Lb-k),k,1,Lb)P3=Sequnece(Element(B3,k) x^(Lc-k),k,1,Lc)P4=Sequnece(Element(B4,k) x^(Ld-k),k,1,Ld)
P1s(x)=Simplify(Sum(P1))
P2s(x)=Simplify(Sum(P2))
P3s(x)=Simplify(Sum(P3))
P4s(x)=Simplify(Sum(P4))
y1x1(x)=Times(2,x) P1s(x)
y1x2(x)=Times(3,x) P2s(x)
y1x3(x)=Times(2,x) P3s(x)
y1x4(x)=Times(1,x) P4s(x)
r(x)=Mod(y1x1,P)+ Mod(y1x2,P)+Mod(y1x3,P)+ Mod(y1x4,P)
s(x)=Simplify(r)
Coffs=Coefficients(s)
#多項式の係数を取り出すと、y1の係数がでますが、2以上もあり得ます。
XOR=Zip(if(Mod(k,2)==0,0,1),k,Coffs) #mod2にしたy1の係数
lx=Length(XOR)
y1=Sequence(Element(XOR,k) x^(lx-k),k,1,lx)
#最終的にGF(2^8)でのy1の多項式
f(x)=Simplify(Sum(y1))
e=f(2)
#最終的なy1の16進表示の文字列
text5=ToBase(e,16)
#入力ボックスの挿入
見出しをx1にして、コントロールをa
見出しをx2にして、コントロールをb
見出しをx3にして、コントロールをc
見出しをx4にして、コントロールをdにすると、
画面から、x1、x2、x3、x4を変更できます。
その結果を見るために
"y1 = " + text5 + ""
を貼り付けましょう。
グラフの曲線が大量に表示されますが、ｆとy1を表示して見比べるとおもしろいかもしれません。