#import "template.typ": *

#show: project.with(
  title: "KUE-CHIPを用いた公開伴暗号通信の実装(1)",
  author: "<NAME>",
  year: "2024",
)


#outline(indent: auto, fill: box(width: 1fr, repeat[．]))

// start page number
#set page(numbering: "1", number-align: center)
#counter(page).update(1)

= 実験内課題

== 予習問題(前期の復習)

下の手順を参考に2つの整数 x, n に対し Modular(剰余)Mod[x, n] を
求めるアセンブリ語プログラムを作成し,命令毎の動作を説明せよ.

このプログラムでは以下のような入出力を想定する.

*入力*
```
180: (X)**H (自然数: 1バイト)
182: (N)**H (自然数: 1バイト)
```

*出力*
```
ACC: Mod[X, N]
```


与えられた問題を解くプログラムは以下のようになった.
```
00: 65    LD ACC, (80)
01: 80
02: 6D    LD IX,  (82)
03: 82
04: A1    SUB ACC, IX
05: 32    BZP 02
06: 02
07: B1    ADD ACC, IX
08: 0F
```

*プログラムの説明*

プログラムの手順としては、Xからnを引いていき、それが負数になったら、nを足すことによって剰余を求めるというものである.
Xからnを引く際に、繰り返す回数は自然数であるから、Xは $(n times (text("自然数")) + text("整数"))$ という形で表せる.
最後にnを足す理由は、剰余は$n$より小さく、かつ非負である必要があるからである.



== 課題01
$op("Mod") [a x]$ を求めるプログラムを作成し、KUECHIPで実行せよ.

このプログラムでは以下のような入出力を想定する.

*入力*
```
180: (X)**H (乗数)
182: (N)**H
1B0: (A)**H *(被乗数)
```

*出力*
```
ACC: Mod[AX,N]
```

与えられた問題を解くプログラムは以下のようになった.

```
00: C0    EOR ACC, ACC
01: C9    EOR IX,  IX
02: B5    ADD ACC, (80)
03: 80
04: A5    SUB ACC, (82)
05: 82
06: 32    BZP 04
07: 04
08: B5    ADD ACC, (82)
09: 82
0A: BA    ADD IX,  1
0B: 01
0C: FD    CMP IX,  (B0)
0D: B0
0E: 3A    BN 02
0F: 02
10: 0F    HLT
```

*プログラムの説明*

このプログラムでは、Mod演算が足し算に対して不変であることを利用する. @experiment すなわち、
$
s_0 = 0, s_(i+1) = op("Mod") [s_i + x,n]
$
としたとき
$
op("Mod") [a x, n] &= s_a
$
を利用する.

よって、期待する出力であるMod[AX,N]を得るためには、$s_i$の$i$が$A$となるまで
$
s_(i+1) = op("Mod") [s_i + x,n]
$
を計算していけば良い.
このプログラムではIXで$s_i$の$i$をカウントし、ACCに$s_i$を格納して計算を行っている.
ここで、予習問題にて作成したMod[x,n]を求めるプログラムを利用し、$op("Mod") [s_i + x,n]$を求めている.


== 課題02
3つの整数$x, k, n$に対し、$op("Mod") [x^k, n]$を計算するプログラムを実装せよ.

このプログラムでは以下のような入出力と作業領域を想定する.

*入力*
```
180: (X)
181: (K)
182: (N)
```

*作業領域*
```
1B0: (W1)**H (作業領域1: 途中経過 A=Mod[X^p,N], 被乗数)
1C0: (W2)**H (作業領域2: Xの乗算を実行した回数p)
```

*出力*
```
ACC: Mod[X^K, N]
```

与えられた問題を解くプログラムは以下のようになった.

```
00: 65    LD ACC, (80)
01: 80
02: 6A    LD IX,  1
03: 01
04: 7D    ST IX,  (C0)
05: C0
06: 75    ST ACC, (B0)
07: B0
08: C0    EOR ACC, ACC 
09: C9    EOR IX,  IX  
0A: B5    ADD ACC, (80)
0B: 80
0C: A5    SUB ACC, (82)
0D: 82
0E: 32    BZP 0C
0F: 0C
10: B5    ADD ACC, (82)
11: 82
12: BA    ADD IX,  1   
13: 01
14: FD    CMP IX,  (B0)
15: B0
16: 3A    BN 0A        
17: 0A
18: 6D    LD IX,  (C0)
19: C0
1A: BA    ADD IX, 1
1B: 01
1C: FD    CMP IX, (81)
1D: 81
1E: 3A    BN 04
1F: 04
20: 0F    HLT
```

*プログラムの説明*

このプログラムでは、Mod演算が乗算に対して不変であることを利用する.すなわち、
$
r_0 = 0, r_(i+1) = op("Mod") [r_i x,n]
$
としたとき
$
op("Mod") [x^k, n] &= r_k
$
を利用する.

よって、期待する出力であるMod[X^K,N]を得るためには、$r_i$の$i$が$K$となるまで
$
r_(i+1) = op("Mod") [r_i x,n]
$
を計算していけば良い.

このプログラムにおいて、課題01において作成したMod[ax,n]を利用し、$r_(i+1) = op("Mod") [r_i x,n]$
を求めている.
また、このプログラムではIX, ACCをMod[AX,N]の計算を行う上で必要となるため、$r_i$の$i$は作業領域1C0に格納しておき、$r_i$は作業領域1B0に格納しておく.
この作業領域1C0に格納している$i$の値が$K$になるまで処理を繰り返すことで$r_k$を求めることができる.


== 課題03
課題02をプログラム領域のアドレス080H以下に実装し、分岐命令BAを使い、ルーチンとして２つの数値を連続して暗号化し、メモリに保存するプログラムを作成せよ.

このプログラムでは以下のような入出力と作業領域を想定する.

*入力*
```
170: (D) 02H 0FH (データ)
181: (K) 05H     (公開鍵)
182: (N) 5BH     (共通鍵)
```

*作業領域*
```
150: (LN)**H (作業領域: 残り繰り返し回数)
180: (X)**H  (作業領域: 暗号化するデータの一時保存)
```

*出力*
```
190: (EN) 20H 47H (暗号化データ)
```

与えられた問題を解くプログラムは以下のようになった.

```
00: 6A    LD IX, 1
01: 01
02: 7D    ST IX, (50)
03: 50
04: 67    LD ACC, (IX+70)
05: 70
06: 75    ST ACC, (80)
07: 80
08: 30    BA 80
09: 80
0A: 6D    LD IX, (50)
0B: 50
0C: 77    ST ACC, (IX+90)
0D: 90
0E: AA    SUB IX, 1
0F: 01
10: 32    BZP 02
11: 02
12: 0F    HLT


# Subroutine
80: 65    LD ACC, (80)
81: 80
82: 6A    LD IX,  1
83: 01
84: 7D    ST IX,  (C0)
85: C0
86: 75    ST ACC, (B0)
87: B0
88: C0    EOR ACC, ACC 
89: C9    EOR IX,  IX  
8A: B5    ADD ACC, (80)
8B: 80
8C: A5    SUB ACC, (82)
8D: 82
8E: 32    BZP 8C
8F: 8C
90: B5    ADD ACC, (82)
91: 82
92: BA    ADD IX,  1   
93: 01
94: FD    CMP IX,  (B0)
95: B0
96: 3A    BN 8A        
97: 8A
98: 6D    LD IX,  (C0)
99: C0
9A: BA    ADD IX, 1
9B: 01
9C: FD    CMP IX, (81)
9D: 81
9E: 3A    BN 84
9F: 84
A0: 30    BA 0A
A1: 0A
```

*プログラムの説明*

課題02で作成した000Hからのプログラム領域に格納したプログラムを080H以下に格納し、サブルーチンとして実装しておく.
これにより、適切なデータ領域(180H)に引数が与えられれば、その引数(180Hに格納されたデータ)を暗号化するような関数として動作する.
この関数を2回呼び出すことによって、データ領域の連続した値(170H, 171H)を暗号化して、連続したデータ領域(190H, 191H)に出力することができる.

このプログラムにおいてまず、IXに1を格納し、171H(170H+IX)のデータから読みこみ、180H領域に引数としてセットし、関数を呼び出し、1つ目のデータを暗号化し191H(190H+IX)に格納する.その後、IXの値をデクリメントし、170H(170H+IX)のデータに対しても同様の処理を行うことで、暗号化したデータを190H(190H+IX)に格納する.

= 考察

== 考察課題01
予習問題, 課題01,課題02 で実装したプログラムの計算量を評価せよ.命令回数を a, x, k, n 等を用いて定量的に評価すること(例えば,
$op("O") (a x^2 k n)$ 等のように表す).

=== 考察

==== 予習問題
まず最初に予習問題のプログラムの計算量について考える.
このプログラムでは、$x$ から $n$ を負になるまで繰り返し引いていくので、繰り返しの回数は
$
floor(x / n) + 1
$
となる.ここで、$x$ が $n$ で割り切れる場合もこの回数分繰り返しが行われることに注意する.
よって、このプログラムの計算量は $op("O") (x / n)$ となる.

==== 課題01
次に課題01のプログラムの計算量について考える.
このプログラムでは、
$
s_(i+1) = op("Mod") [s_i + x,n]
$
を$s_a$を得るまで繰り返す.よって、$op("Mod") [s_i + x,n]$を$a$回繰り返す.
ここで、$op("Mod") [s_i + x,n]$の計算について、$0 <= s_i < n$であるから、
$0 <= s_i / n < 1$ となる.
よって、
$
op("O") ((s_i + x) / n) = op("O") (s_i / n + x / n) = op("O") (x / n)
$ 
よって、課題01のプログラムの計算量は $op("O") ((a x) / n)$ となる.


==== 課題02
最後に課題02のプログラムの計算量について考える.
このプログラムでは、

$
r_(i+1) = op("Mod") [r_i x,n]
$
を$r_k$を得るまで繰り返す.よって、$op("Mod") [r_i x,n]$ を $k$ 回繰り返す.
ここで、$0 <= r_i < n$ であるから $ 0<= r_i / n < 1$ である.よって、$op("Mod") [r_i x,n]$ の計算量は
$
op("O") ((r_i x) / n) = op("O") (r_i / n dot x) = op("O") (x)
$
よって、課題02の計算量は $op("O") (k x)$ となる.


== 考察課題02
課題01において,$op("Mod") [a x, N]$の値を,まず$a x$の計算を行った後,Nによる剰余を求めることにより計算した場合,課題1の方法で計算したときとどのような違いがあるか考察せよ.

=== 考察
$op("Mod") [a x, N]$の値を求める際に、先に $a x$ の乗算を行った後に $a x$ の$N$による剰余を求める場合、$a x$
の計算結果がオーバーフローしてしまい、その後の $N$ による剰余の計算において正常な出力ができなくなってしまう可能性がある.
そこで、課題01のように
$
s_(i+1) = op("Mod") [s_i + x,n]
$
を繰り返し求めることで、$s_a$ を求める方法では、各$s_i$を計算したとき、$s_i$は常に$0$ 以上 $n -1$以下となるので、次に計算すべき$s_(i+1)$の計算において、$s_i + x$ がオーバーフローする可能性を小さくすることができる.

#[
  #set text(lang: "en")
  #bibliography(title: "参考文献", style:"ieee", "bib.yaml")
]
