高校生のための暗号論入門

@Author　MASASI.Sanae　　@Version　1.04;2003.1.22

０．はじめに

　インターネットの普及に伴って，ネット上における情報の機密保持，改ざん防止の方法として公開鍵暗号方式が注目を集めている。公開鍵方式の中でも最も普及しているのがRSA暗号と呼ばれるものである。
　この理論には基本的でかつ魅力的な数学の整数に関する理論が用いられている。高校数学レベルでも理解できる数学をもとに，暗号論の魅力を少しでも知っていただきたいと思う。

1．素数

1_1　素数・合成数

　整数a(a≠1)が1とa以外に約数をもたないときaを素数という。また素数でない整数を合成数という。（素数一覧参照）

（例）7，11は素数。　12=2²･3は合成数。

1_2　素数判定アルゴリズム

　素数を完全に定義する式が存在することは証明されていないし，また存在しないともわかっていない。
　与えられた奇数 n が素数であるかどうかを厳密に判定することは， n の桁数が増えるとかなり難しい。そのため，厳密に素数であるか否かを判定するより，『確率的に素数である』ことを判定する方法がよく用いられる。代表的なものとしてRabin判定法（誤り確率1/4）がある。
　判定をクリアしたとき（ほぼ素数であろうと考えて間違いがないと判定されたとき）その数を疑似素数という。

1_3　素因数分解の困難性

　数値を素数の積で表すを素因数分解という。
　素因数分解は小さな素数から順に2， 3， 5， 7… と次々に割り算していけばよいが，このような方法では大きな数の場合計算量が指数関数的に増えて大変である。現在では大きな数の素因数分解のアルゴリズムとして，1974年にPollardによって発表されたp-1法や1980年代から提案された方法として2次ふるい法や数体ふるい法がある。特に大きな数に対しては数体ふるい法が最も高速であると言われている。

2．法

2_1　剰余定理

　任意の整数a，b(b≠0)に対し，a=bq+r (0≦r＜|b|)となるようなq(商)とr(剰余)が一意に存在する。

2_2　法と合同

　整数nで整数a，bで割った余りが等しいとき，aとbとはnを法として合同といいa≡b(mod n)で表す。

（例）17÷5=3...2，32÷5=6...2　　∴17≡32(mod 5)

2_3　法に関する演算

a≡b，c≡d (mod n)　⇒　a±c≡b±d，ac≡bd (mod n)
ca≡cb (mod n）　⇒　a≡b (mod n/(c，n))　　（(c，n)はcとnの最大公約数）

3．最大公約数・最小公倍数

3_1　最大公約数

　2つの整数a，bのそれぞれの公約数のうちで最大の整数をa，bの最大公約数といい，GCD(a，b)または(a，b)であらわす。

（例）(10，6)=2，　(24，36)=12

2つの数の最大公約数を求めるスクリプト

3_2　互いに素

　2つの整数a，bが(a，b)=1の関係にあるとき，aとbは互いに素であるという。

（例）3，5は互いに素。　(4，6)=2より4，6は互いに素ではない。

3_3　ユークリッドの互除法

　b≠0 のとき，a を b で割った余りを r とおくと (a，b) = (b，r) が成り立つ。

　次のアルゴリズムにより最大公約数が求まる：

a₀= a，a₁= b
a_n=mod(a_n-2，a_n-1） (n=2, 3,…)
a_n=0 となるとき (a，b)=a_n-1

（例）5916と1716の最大公約数12を求める。

i a_i 計算

0 a₀=5916 　

1 a₁=1716 5916÷1716=3...768

2 a₂=768 1716÷768=2...180

3 a₃=180 768÷180=4...48

4 a₄=48 180÷48=3...36

5 a₅=36 48÷36=1...12

6 a₆=12 36÷12=0

3_4　最小公倍数

　2つの整数a，bのそれぞれの公倍数のうちで最小の整数をa，bの最小公倍数といい，LCM(a，b)であらわす。
　a，bの最小公倍数をL=LCM(a，b)，最大公約数をG=GCD(a，b)とするときL=a*b/Gが成り立つ。

（例）a=12，b=20のとき，G＝4。　∴L=12*20/4=60

3_5　RSA暗号の基本定理

　異なる素数p，qに対してn=pq，L=LCM(p-1，q-1)とする。任意の正の整数xに対して
　　　　x^mL+1≡x　(mod n)　　（mは整数）

（注）多くの文献，Webサイトでオイラー関数φ(N)=φ(p×q)=φ(p)×φ(q)=(p-1)×(q-1)を用いて再出現する旨の記述があるが，これでは不十分であろうと思われる。

（例）

p=2，q=5，n=10，L=LCM(2-1，5-1)=4

	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
2	4	8	6	2	4	8	6	2	4	8	6	2	4	8	6	2	4	8	6	2	4	8	6	2
3	9	7	1	3	9	7	1	3	9	7	1	3	9	7	1	3	9	7	1	3	9	7	1	3
4	6	4	6	4	6	4	6	4	6	4	6	4	6	4	6	4	6	4	6	4	6	4	6	4
5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5
6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6
7	9	3	1	7	9	3	1	7	9	3	1	7	9	3	1	7	9	3	1	7	9	3	1	7
8	4	2	6	8	4	2	6	8	4	2	6	8	4	2	6	8	4	2	6	8	4	2	6	8
9	1	9	1	9	1	9	1	9	1	9	1	9	1	9	1	9	1	9	1	9	1	9	1	9

p=3，q=7，n=21，L=LCM(3-1，7-1)=6

	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
2	4	8	16	11	1	2	4	8	16	11	1	2	4	8	16	11	1	2	4	8	16	11	1	2
3	9	6	18	12	15	3	9	6	18	12	15	3	9	6	18	12	15	3	9	6	18	12	15	3
4	16	1	4	16	1	4	16	1	4	16	1	4	16	1	4	16	1	4	16	1	4	16	1	4
5	4	20	16	17	1	5	4	20	16	17	1	5	4	20	16	17	1	5	4	20	16	17	1	5
6	15	6	15	6	15	6	15	6	15	6	15	6	15	6	15	6	15	6	15	6	15	6	15	6
7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7
8	1	8	1	8	1	8	1	8	1	8	1	8	1	8	1	8	1	8	1	8	1	8	1	8
9	18	15	9	18	15	9	18	15	9	18	15	9	18	15	9	18	15	9	18	15	9	18	15	9

4．逆元

4_1　記数法

10進数で表された数値nの各桁の数字をd_ｎ，d_ｎ-1，・・・，d₂，d₁，d₀としたとき，
　　　n＝d_ｎ×10^ｎ+d_n-1×10^n-1+・・・+d₂×10²+d₁×10¹+d₀
ｒ進数で表された数値nの各桁の数字をd_ｎ，d_ｎ-1，・・・，d₂，d₁，d₀としたとき，n=d_ｎd_ｎ-1・・・d₂d₁d₀_(r)と表し，
　　　n＝d_ｎ×r^ｎ+d_n-1×r^n-1+・・・+d₂×r²+d₁×r¹+d₀
10進数からｒ進数への変換は，ｒでわった時の余りがそれぞれの桁の係数となる。
　　　d_ｎd_ｎ-1・・・d₂d₁d₀_(r)=d_ｎ×r^ｎ+d_n-1×r^n-1+・・・+d₂×r²+d₁×r¹+d₀=(d_ｎ×r^ｎ-1+d_n-1×r^n-2+・・・+d₂×r¹+d₁)×r+d₀

(例)

27=2⁴×1+2³×1+2¹×1+1=11011₍₂₎
1201₍₃₎=3³×1+3²×2+1=27+18+1=46

4_2　繰り返し2乗法

　ｎを法とするa^eを効率よく計算する方法。

（例）325³⁰(mod 23)の計算。

30を2進数表示　　　30=11110₍₂₎

325²，325⁴，325⁸，325¹⁶を計算

325²	＝105625	≡9
325⁴	≡9²	＝81	≡12
325⁸	≡12²	＝144	≡6
325¹⁶	≡6²	＝36	≡13

325³⁰を計算

325³⁰	＝325¹⁶×325⁸×325⁴×325²
	≡13×6×12×9
	＝78×108
	≡9×16
	＝144
	≡6

a^e mod n を求めるスクリプト

4_3　乗法逆元

　ax≡1(mod n)となるxをaの乗法に関する逆元という。　(a，n)=1のときnを法とするaの逆元が必ず存在する。

（例）

n=13のとき，5×8=40≡1より5の逆元は8。
n=6のとき，3×0≡0，3×1≡3，3×2≡0，3×3≡3，3×4≡0，3×5≡3。　∴ 6を法とする3の逆元は存在しない。

4_4　拡張ユークリッドの互除法

　aとb が互いに素ならばax+by=1を満たす整数x，yが次のアルゴリズムによって求まる。

a₀=a，a₁=b
x₀= 1，x₁=0
y₀= 0，y₁=1
q_ｎ=a_n-1をa_nで割った商
a_n = a_n-2-q_n-1*a_n-1 （=a_n-2をr_n-1で割った余り）
x_n = x_n-2-q_n-1*x_n-1
y_n = y_n-2-q_n-1*y_n-1 （n=2,3,…）
a_n=0 となるnで
a_n-1＞0 のとき (a，b)=a_n-1，x=x_n-1，y=y_n-1
a_n-1＜0 のとき (a，b)=-a_n-1，x=-x_n-1，y=-y_n-1

4_5　逆元の存在

　整数aが法nと互いに素であるとき，ax≡1(mod n) を満たす整数xが拡張ユークリッドの互除法によって求まる。
　ax+ny=(a，n)=1を満たす整数x，yが求まるが，このときax=1-ny≡1 (mod n)より明らか。

（例）2184を法としたときの1241の逆元を求める。

i a_i qi xi 計算

0 a₀=1241 　 x₀=1 　

1 a₁=2184 q₁=0 x₁=0 1241÷2184=0...2141

2 a₂=1241 q₂=1 x₂=x₀-q₁・x₁=1 2184÷1241=1...943

3 a₃=943 q₃=1 x₃=x₁-q₂・x₂=-1 1241÷943=1...298

4 a₄=298 q₄=3 x₄=x₂-q₃・x₃=2 943÷298=3...49

5 a₅=49 q₅=6 x₅=x₃-q₄・x₄=-7 298÷49=6...4

6 a₆=4 q₆=12 x₆=x₄-q₃・x₃=44 49÷4=12...1

7 a₇=1 q₇=4 x₇=x₅-q₄・x₄=-535 4÷1=4...0

　∴　2184-535=1649が1241の逆元。　　（1241×1649=2046409≡1(mod 2184)　より確かめられる。）

nを法とするeの逆元を求めるスクリプト

5．暗号

5_1　暗号の定義

　元のデータを送信者と受信者以外の人には解読不可能なデータに変換する，または元に戻すための技法。

平文　・・・元のデータ
暗号文　・・・第三者に解読不可能な形式に変換されたデータ
暗号化　・・・平文を暗号文に変換する処理
複号化　・・・暗号文を平文に変換する処理

（例）

平文暗号化暗号文複合化平文

"apple" → "dssoh" → "apple"

5_2　暗号方式と鍵

　平文をアルファベット順にxづつずらして暗号文を作成するとする。このときの「アルファベット順にずらす」を暗号方式（アルゴリズム），「x」を鍵という。

（例1）

平文：　"I am a boy"
暗号方式：　a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,0,1,2,3,4,5,6,7,8,9,(space)
　　鍵x分だけ右にずらす（はみ出た場合は先頭aに戻る）
鍵：　5
暗号文：　"nefrefegt3"

（例2）

平文：　"I am a boy"

暗号方式：　a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,0,1,2,3,4,5,6,7,8,9,(space)
　　平文の文字一字一字に鍵を当てはめ，その数だけ右にずらす（はみ出た場合は先頭aに戻る）

I		a	m		a		b	o	y
7	3	2	4	7	3	2	4	7	3

鍵：　7324　　（注：このとき鍵の“長さ”は「4」であるという）
暗号文：　"pccqgdbfv2"

5_3　暗号方式

共通鍵暗号方式
あらかじめ送信者と受信者だけが取り決めて，互いに第三者に知らせないで運用する方式。ひとつの鍵で送信者が暗号化し，受信者は同じ鍵を使って複号化する。この方式で最も有名なものはDES (Data Encription Standard) と呼ばれる暗号方式で，1977年に規格化されている。56 ビットが一般的で，米国の銀行など世界で使われている。またIDEAは128ビットの鍵を使用する暗号で1990年に公開された。暗号化プログラムPGPで使われている。
公開鍵暗号方式
2つの鍵が使われる。一方の鍵で閉じたら，その鍵では開けることができない。開くときには別の鍵が必要となる。片方を「秘密鍵」（自分だけが持っている鍵），もう一方を「公開鍵」（誰でも使えるところに公開する鍵）という。閉じる鍵と開く鍵が違うこと，片方が公開されているということから，従来の鍵に比べてとても柔軟に使え，かつ安全な暗号化を行うことができる。この方式の最も有名なものはRSA（Rivest， Shamir， Adlemanの3人の発明者の頭文字をとったもの）である。暗号化は「素因数分解」の困難性をもとに作られている。
共通鍵と公開鍵の併用

（例：共通鍵暗号方式）

A氏："apple"を暗号化→"dssoh"を送信。
B氏："dssoh"を受信→複合化→"apple"を取得。

"apple"をアルファベット順に3つずつずらして"dssoh"に暗号化。このときの「アルファベット順にずらす」が暗号化の規則（アルゴリズム）で，「3」が鍵となる。受信者以外に鍵を知られないことで秘匿性が守られる。

（例：公開鍵暗号化方式）

A氏："apple"をB氏の公開鍵で暗号化→送信。
Bさん：受信→Bさんの秘密鍵で復号化→"apple"を取得。

B氏の「公開鍵」で暗号化された情報はB氏の「秘密鍵」でしか復号化できない。逆にB氏の「秘密鍵」で暗号化された情報はB氏の「公開鍵」でしか復号化できない。

6．メッセージの数値化

6_1　メッセージの数値化

　現代暗号では文字を事前に決められた複数の文字ずつを単位として，いったん数値に変換した上で暗号化する。

（例）

平文：　"cap"
暗号方式：　アルファベット　a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z
　　aから順に0から25の数字を当てはめる。"cap"→2,0,15
　　これを26進法表示だと考え，10進法表示に変換する
　　　　2・26²+0・26+15=2・676+0・26+15=1367
変換された数値：　"1367"

6_2　ASCIIコード

　ASCIIコードでは0から127までの数値に次の表のような文字と数値を対応させる。

上位３ビット 0 1 2 3 4 5 6 7

下位３ビット

0 NUL DLE SP 0 @ P ` p

1 SOH DC1 ! 1 A Q a q

2 STX DC2 " 2 B R b r

3 ETX DC3 # 3 C S c s

4 EOT DC4 $ 4 D T d t

5 ENQ NAC % 5 E U e u

6 ACK SYN & 6 F V f v

7 BEL ETB ' 7 G W g w

8 BS CAN ( 8 H X h x

9 HT EM ) 9 I Y i y

A LF/NL SUB * : J Z j z

B VT ESC + ; K [ k {

C FF FS , < L \ l |

D CR GS - = M ] m }

E SO RS . > N ^ n ~

F SI US / ? O _ o DEL

6_3　暗号化ソフト

　米国のPhilip Zimmermann氏が開発した暗号ソフト「PGP(Pretty Good Privacy)」が有名。

7．ＲＳＡ暗号

7_1　RSA暗号の概要
　平文をM，暗号文をCとすると，M＜nのとき
　　　C≡M^e　(mod n)　　　（暗号化）
　　　M≡C^d　(mod n)　　　（複合化）
　ここでe，nが公開鍵，dが秘密の鍵になる。

（例：暗号化）　M=21をn=437，e=17で暗号化する。C=21¹⁷を最小2乗法を用いて計算。

17を2進数表示　　17=10001₍₂₎

21²，21⁴，21⁸，21¹⁶を計算

21²	＝441	≡4
21⁴	≡4²	＝16
21⁸	≡16²	＝256
21¹⁶	≡256²	＝65536	≡423

21¹⁷を計算

21¹⁷ ＝21¹⁶×21

≡423×21

＝8883

≡143

∴　C=21¹⁷≡143　(mod 437)

（例：複合化）　d=35で複合化する。上と同様に最小2乗法を用いて計算。

M'=143³⁵≡21　(mod 437)　

7_2　鍵の作成の仕方①　公開鍵nとe

2つの素数p，qを選ぶ（これは秘密の鍵となる）。
p，qを元にn=pqとL=LCM(p-1，q-1)を計算する。
Lと素な整数eを選択する。

（例）

p=19，q=23
n=19*23=437，L=LCM(19-1，23-1)=198
e=17　　　（これは(17，198)=1より確かめられる）

7_3　鍵の作成の仕方②　秘密鍵d

Lを法とするeの逆元を計算する。

（例）L=198を法とするe=17の逆元dを拡張ユークリッドの互除法で計算する。

i a_i qi xi 計算

0 a₀=17 　 x₀=1 　

1 a₁=198 q₁=0 x₁=0 17÷198=0...17

2 a₂=17 q₂=11 x₂=x₀-q₁・x₁=1 198÷17=11...11

3 a₃=11 q₃=1 x₃=x₁-q₂・x₂=-11 17÷11=1...6

4 a₄=6 q₄=1 x₄=x₂-q₃・x₃=12 11÷6=1...5

5 a₅=5 q₅=1 x₅=x₃-q₄・x₄=-23 6÷5=1...1

6 a₆=1 q₆=1 x₅=x₃-q₄・x₄=35 5÷1=5...0

7_4　RSA暗号の安全性

　素因数分解の困難性に基づく。まだ誰もその破り方を発見していない。

≪参考資料≫

RSA暗号体験入門（CyberSyndrom）　http://www8.big.or.jp/~000/CyberSyndrome/rsa/
サルにも分かるＲＳＡ暗号（まいとう情報通信研究会）　http://www.maitou.gr.jp/rsa/
暗号について（大坪家の書庫，大坪五郎の部）　http://member.nifty.ne.jp/GOtsubo/contents/encrypt/encrypt00.htm
ＲＳＡ暗号と初等整数論アルゴリズム（計算機実験 II（塩田・森教官）平成７年度教材）　http://lupus.is.kochi-u.ac.jp/~shiota/kj95/

☆HOME☆　☆数学のいずみ☆

i	a_i	計算
0	a₀=5916
1	a₁=1716	5916÷1716=3...768
2	a₂=768	1716÷768=2...180
3	a₃=180	768÷180=4...48
4	a₄=48	180÷48=3...36
5	a₅=36	48÷36=1...12
6	a₆=12	36÷12=0

	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
2	4	8	6	2	4	8	6	2	4	8	6	2	4	8	6	2	4	8	6	2	4	8	6	2
3	9	7	1	3	9	7	1	3	9	7	1	3	9	7	1	3	9	7	1	3	9	7	1	3
4	6	4	6	4	6	4	6	4	6	4	6	4	6	4	6	4	6	4	6	4	6	4	6	4
5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5
6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6
7	9	3	1	7	9	3	1	7	9	3	1	7	9	3	1	7	9	3	1	7	9	3	1	7
8	4	2	6	8	4	2	6	8	4	2	6	8	4	2	6	8	4	2	6	8	4	2	6	8
9	1	9	1	9	1	9	1	9	1	9	1	9	1	9	1	9	1	9	1	9	1	9	1	9

	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
2	4	8	16	11	1	2	4	8	16	11	1	2	4	8	16	11	1	2	4	8	16	11	1	2
3	9	6	18	12	15	3	9	6	18	12	15	3	9	6	18	12	15	3	9	6	18	12	15	3
4	16	1	4	16	1	4	16	1	4	16	1	4	16	1	4	16	1	4	16	1	4	16	1	4
5	4	20	16	17	1	5	4	20	16	17	1	5	4	20	16	17	1	5	4	20	16	17	1	5
6	15	6	15	6	15	6	15	6	15	6	15	6	15	6	15	6	15	6	15	6	15	6	15	6
7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7
8	1	8	1	8	1	8	1	8	1	8	1	8	1	8	1	8	1	8	1	8	1	8	1	8
9	18	15	9	18	15	9	18	15	9	18	15	9	18	15	9	18	15	9	18	15	9	18	15	9

i	a_i	qi	xi	計算
0	a₀=1241		x₀=1
1	a₁=2184	q₁=0	x₁=0	1241÷2184=0...2141
2	a₂=1241	q₂=1	x₂=x₀-q₁・x₁=1	2184÷1241=1...943
3	a₃=943	q₃=1	x₃=x₁-q₂・x₂=-1	1241÷943=1...298
4	a₄=298	q₄=3	x₄=x₂-q₃・x₃=2	943÷298=3...49
5	a₅=49	q₅=6	x₅=x₃-q₄・x₄=-7	298÷49=6...4
6	a₆=4	q₆=12	x₆=x₄-q₃・x₃=44	49÷4=12...1
7	a₇=1	q₇=4	x₇=x₅-q₄・x₄=-535	4÷1=4...0

平文	暗号化	暗号文	複合化	平文
"apple"	→	"dssoh"	→	"apple"

上位３ビット	0	1	2	3	4	5	6	7
下位３ビット	0	1	2	3	4	5	6	7
0	NUL	DLE	SP	0	@	P	`	p
1	SOH	DC1	!	1	A	Q	a	q
2	STX	DC2	"	2	B	R	b	r
3	ETX	DC3	#	3	C	S	c	s
4	EOT	DC4	$	4	D	T	d	t
5	ENQ	NAC	%	5	E	U	e	u
6	ACK	SYN	&	6	F	V	f	v
7	BEL	ETB	'	7	G	W	g	w
8	BS	CAN	(	8	H	X	h	x
9	HT	EM	)	9	I	Y	i	y
A	LF/NL	SUB	*	:	J	Z	j	z
B	VT	ESC	+	;	K	[	k	{
C	FF	FS	,	<	L	\	l	\|
D	CR	GS	-	=	M	]	m	}
E	SO	RS	.	>	N	^	n	~
F	SI	US	/	?	O	_	o	DEL

i	a_i	qi	xi	計算
0	a₀=17		x₀=1
1	a₁=198	q₁=0	x₁=0	17÷198=0...17
2	a₂=17	q₂=11	x₂=x₀-q₁・x₁=1	198÷17=11...11
3	a₃=11	q₃=1	x₃=x₁-q₂・x₂=-11	17÷11=1...6
4	a₄=6	q₄=1	x₄=x₂-q₃・x₃=12	11÷6=1...5
5	a₅=5	q₅=1	x₅=x₃-q₄・x₄=-23	6÷5=1...1
6	a₆=1	q₆=1	x₅=x₃-q₄・x₄=35	5÷1=5...0

21¹⁷	＝21¹⁶×21
	≡423×21
	＝8883
	≡143

	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
2	4	8	6	2	4	8	6	2	4	8	6	2	4	8	6	2	4	8	6	2	4	8	6	2
3	9	7	1	3	9	7	1	3	9	7	1	3	9	7	1	3	9	7	1	3	9	7	1	3
4	6	4	6	4	6	4	6	4	6	4	6	4	6	4	6	4	6	4	6	4	6	4	6	4
5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5
6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6	6
7	9	3	1	7	9	3	1	7	9	3	1	7	9	3	1	7	9	3	1	7	9	3	1	7
8	4	2	6	8	4	2	6	8	4	2	6	8	4	2	6	8	4	2	6	8	4	2	6	8
9	1	9	1	9	1	9	1	9	1	9	1	9	1	9	1	9	1	9	1	9	1	9	1	9

	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
2	4	8	16	11	1	2	4	8	16	11	1	2	4	8	16	11	1	2	4	8	16	11	1	2
3	9	6	18	12	15	3	9	6	18	12	15	3	9	6	18	12	15	3	9	6	18	12	15	3
4	16	1	4	16	1	4	16	1	4	16	1	4	16	1	4	16	1	4	16	1	4	16	1	4
5	4	20	16	17	1	5	4	20	16	17	1	5	4	20	16	17	1	5	4	20	16	17	1	5
6	15	6	15	6	15	6	15	6	15	6	15	6	15	6	15	6	15	6	15	6	15	6	15	6
7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7
8	1	8	1	8	1	8	1	8	1	8	1	8	1	8	1	8	1	8	1	8	1	8	1	8
9	18	15	9	18	15	9	18	15	9	18	15	9	18	15	9	18	15	9	18	15	9	18	15	9