若不想在 Windows 上灌 Virtual Box 進行 kernel 修改，那麼在 Linux 上面灌 qemu，在上面測試，假設只要測試 kernel 那麼 qemu 在第一次編譯以及在部分檔案重新編譯都只需要兩三分鐘。若 Windows 上用 Virtual Box 灌 Linux，又在 Linux 上面灌 qemu，容易遭遇到記憶體不夠的窘境。

Ubuntu Environment

Ubuntu 環境需要安裝下列插件。

1
2

$ sudo apt-get install qemu-system
$ sudo apt-get install libncurses5-dev

Buildroot

用 busybox 建造一直失敗，轉向學長推薦的 buildroot，用別人打包好的環境替 qemu 建造 file system。

site

1
2
3

$ wget https://buildroot.uclibc.org/downloads/buildroot-2015.11.1.tar.bz2
$ bzip2 -d FileName.bz2
$ tar xvf FileName.tar

Compile Config

Buildroot 提供很多參數給予選擇

1

$ make menuconfig

這次作業設定，由於需要改寫 kernel 版本為 2.6.32.* 左右，因此相關的 gcc 編譯器等設定如下。同時，根據機器架構設定，助教預設在 visual box 上面，通常為 i386，而我們用實驗室 server，編 x86 64。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Target options  --->
    Target Architecture (x86_64)  --->
        x86_64
Toolchain  --->
    C library (glibc)  --->
        glibc
    Kernel Headers (Manually specified Linux version)  --->
        custom 2.6.x
        2.6.32.6
System configuration  --->
    [*] Enable root login with password
    [*] remount root filesystem read-write during boot 
Filesystem images  ---> 
    [*] ext2/3/4 root filesystem
    [*] tar the root filesystem

Compile

make -j8 用 8 個執行緒編譯，如果機器有很多個 core，那麼可以用 make -j20 在非常短的時間內完成。

接著在 buildroot

1
2

$ make -j8
$ cp output/image/rootfs.ext* WORKSPACE_PATH

Linux kernel config

1
2

$ make defconfig
$ make menuconfig

1
2
3
4
5
6
7
8
9
10

[_] Enable loadable module support
File systems  ---> 
    [*] Second extended fs support
        [*] ext2
Device Drivers  --->
    Generic Driver Options  ---> 
        [*] Create a kernel maintained /dev tmpfs (EXPERIMENTAL) 
        [*] Automount devtmpfs at /dev

create arch/x86/boot/bzImage

1

$ make -j20

Test Flow

move test execute file

mnt.sh

1
2
3

sudo mount rootfs.ext2 mnt
sudo cp test_weighted_rr/test_weighted_rr mnt/root/
sudo umount mnt

run.sh

1

qemu-system-x86_64 -M pc -kernel arch/x86/boot/bzImage -hda rootfs-dirty.ext4 -netdev user,id=network0 -device e1000,netdev=network0 -nographic -append "root=/dev/sda console=ttyS0"

How to enlarge the rootfs.ext4

http://stackoverflow.com/questions/3495854/extend-the-size-of-already-existing-ext2-image

1
2
3

$ dd if=/dev/zero of=foo.img count=0 bs=1M seek=2000   # assuming target size is 2000M
# e2fsck -f foo.img
# resize2fs foo.img

Screen Workspace

commond tutorial

執行

1

$ screen

• ctrl+a c
  開啟新的視窗，並同時切換到這個新的視窗
• ctrl+a tab
  切換視窗
• ctrl+a |
  切割垂直視窗，並產生新的視窗。
• ctrl+a k
  關閉此視窗

之所以用 Screen 指令，主要是因為遠端到工作站上操作 qemu，若程序掛掉，很容易遭遇到要重新連線的麻煩事。

Speical Thanks

• 蕭光宏 蕭大帥
• Lab 332 Parallel & Distributed Laboratory

Virtual Box

第一次運行

1
2
3
4
5
6

$ cd /usr/src
$ sudo wget http://newslab.csie.ntu.edu.tw/course/rts2015/projects/linux-2.6.32.60.tar.gz
$ sudo tar -zxvf linux-2.6.32.60.tar.gz
$ cd linux-2.6.32.60
$ sudo make mrproper
$ sudo make menuconfig

1
2

$ scp morris1028@140.112.30.245:~/RTS/linux-2.6.32.60/arch/x86/include/asm/unistd_64.h arch/x86/include/asm/
$ scp morris1028@140.112.30.245:~/RTS/linux-2.6.32.60/kernel/sched_weighted_rr.c kernel/

1
2
3
4

$ sudo make bzImage
$ sudo make modules
$ sudo make modules_install
$ sudo make install

1
2
3
4
5
6

$ sudo vim /etc/default/grub
#Add "#" to comment the following 2 lines
#GRUB_HIDDEN_TIMEOUT=10
#GRUB_HIDDEN_TIMEOUT_QUIET=true
$ sudoupdate-grub2
$ sudoshutdown -r now

Test flow

1
2
3
4
5

$ cd /usr/src/linux-2.6.32.60
$ sudo make bzImage
$ sudo make modules
$ sudo make modules_install
$ sudo make install

Debug by printk

在另一個 terminal 開啟以下代碼，並且等待執行測試 scheduler 得執行檔在 kernel 運行時所打印出的 printk 訊息。

1

$ sudo more /proc/kmsg

目標

安裝 linux kernel 2.6.32.68、練習 pthread 設定 scheduler 相關函數以利後續修改 kernel source code。

設定 scheduler 問題

• 設定 thread 可以在哪些 core 運行，由於要測試執行順序,強制讓 pthread 都在 CPU 0 運行。
  編譯時，增加 #define _GNU_SOURCE 在 #include <pthread> 之前，確定 cpu_set_t 型別存在。

1
2
3
4

cpu_set_t mask;
CPU_ZERO(&mask);
CPU_SET(0, &mask);
sched_setaffinity(0, sizeof(mask), &mask);

• 使用 sched_setscheduler() 時，需查閱 int policy 相關規定去設定 struct sched_param 的 priority 數值。例如 SCHED_FIFO 的 priority 介於 1 到 99 之間,若 priority 錯誤，sched_setscheduler() 會發生錯誤，錯誤訊息可以藉由 printf("Message␣%s\n", mid, strerror(errno)); 查閱。

1
2
3

sched_setaffinity(0, sizeof(mask), &mask);
              int sched_setscheduler(pid_t pid, int policy,
const struct sched_param *param);

• 如果 pid = 0，相當於 caller 的 thread 會被設置對應的 policy 和 sched_param。在 policy 設定 規範中，有兩種 real time scheduler SCHED_FIFO 和 SCHED_RR。當 thread 設置 real time scheduler 時，需要用 root 權限來執行程式，否則會設置失敗。相反地，若使用 non-real time scheduler 則不需要 root 權限，如 SCHED_BATCH。

1
2
3
4
5

struct sched_param param;
printf("Thread %d sched_setscheduler()\n", mid);
param.sched_priority = sched_get_priority_max(SCHED_FIFO);
s = sched_setscheduler(0, SCHED_FIFO, &param);
printf("Thread %d sched after %s\n", mid, strerror(errno));

三種方法設定 pthread

方法一

各自的 pthread_create() 後，再呼叫 sched_setscheduler() 進行設定。這種寫法在本次實驗有順序問題，在 create 之後，無法保證執行 sched_setscheduler() 的順序，無法依靠 main thread 中執行 pthread_create() 的順序決定。幸運地，仍可以使用

1
2
3

pthread_barrier_t barrier; 
pthread_barrier_wait(&barrier);
pthread_barrier_init(&barrier, NULL, MAX_THREAD);

確保每一個 thread 都設置好各自的 sched_setscheduler() 後統一運行，運行順序取決 priority。

方法二

在 main thread 中，呼叫 pthread_attr_setinheritsched(attr, PTHREAD_INHERIT_SCHED); 接下來 create 出來的 pthread 都將繼承 main thread 的 scheduler 設定。這種寫法很方便，如果需要各自設置 priority 會不方便，倒不如直接用第三種寫法。

方法三

在 main thread 中，手動設置每一個 pthread 的 scheduler。

1
2
3
4
5
6
7
8
9
10

pthread_attr_t *attr = new pthread_attr_t;
struct sched_param *param = new struct sched_param;
// increasing order
param->sched_priority = sched_get_priority_max(SCHED_FIFO) - i;
// set scheduler
pthread_attr_setinheritsched(attr, PTHREAD_EXPLICIT_SCHED);
pthread_attr_setschedpolicy(attr, SCHED_FIFO);
pthread_attr_setschedparam(attr, param);
// create thread
pthread_create(&tid[i], attr, running_print, create_arg(i+1, scheduler))

計時設置

為確定每一個 thread 按照設定的 scheduler 運行，方式採用 print() 進行，但有可能輸出之間間隔距離過短，導致順序容易在輸出上發生無法預期的問題，適時地加入一秒間隔完成。

如何準確地停止一秒？不能呼叫 sleep() 因為這類的 system call 會產生 interrupt，此時 thread 將會降低 priority 或者進入隊列尾端。佔據 CPU time 有以下三種

busy work

只要停留的夠久即可，下面是一種簡單的方法

1
2
3

// busy 1 second
double a = 0;
for (int i = 0; i < 10000000; i++)	a += 0.1f;

系統時間

利用 critical section 抓系統時間 int gettimeofday (struct timeval * tv, struct timezone * tz);，這寫法會共用同一份時間，因此需要使用 mutex 完成。仍使用一個迴圈來判定時間是否超過，實際運行時間會超過一秒。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

static double my_clock(void) {
    struct timeval t;
    gettimeofday(&t, NULL);
    return 1e-6 * t.tv_usec + t.tv_sec;
}
pthread_mutex_lock(&outputlock);
{
    double sttime = my_clock();
    while (1) {
        if (my_clock() - sttime > 1)
            break;
    }
}
pthread_mutex_unlock(&outputlock);

執行緒運行時間

事實上 Linux 有提供每一個 thread 各自的 clock，用來計算 thread 的執行時間。使用 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &t)，在舊版本需在編譯參數中加入 -lrt 才能使用。

1
2
3
4
5

static double my_clock(void) {
    struct timespec t;
    assert(clock_gettime(CLOCK_THREAD_CPUTIME_ID, &t) == 0);
    return 1e-9 * t.tv_nsec + t.tv_sec;
}

輸出 console 問題

在 SCHED_FIFO 這類的 real time scheduler 情況下，thread 輸出無法即時顯示在 terminal 上。

從 http://man7.org/linux/man-pages/man7/sched.7.html 可以見到 real-time scheduler 安排工作的比例，由於 print() 之後的顯示處理並不是 real-time process，當 real-time process 完全用盡 95\% 的 CPU time 時，顯示處理可能沒辦法在一秒內完成，可能要用好幾秒中的 5% 來完成。這也就是造成一開始會停頓一陣子，隨後才一次輸出數行結果。(註：並不是每一種裝置都會造成這問題，跟 CPU 時脈有關。)

The value in this file specifies how much of the period time can be used by all real-time and deadline scheduled processes on the system. The value in this file can range from -1 to INT_MAX-1. Specifying -1 makes the runtime the same as the period; that is, no CPU time is set aside for non-real-time processes (which was the Linux behavior before kernel 2.6.25). The default value in this file is 950,000 (0.95 seconds), meaning that 5% of the CPU time is reserved for processes that don’t run under a real-time or deadline scheduling policy.

解決這類的問題，可以從 kernel 設定著手，降低 real-time 最大佔有量，讓 print() 處理能即刻印出。這不是好的解決辦法，但可用於實驗。

1
2
3
4

// default
$ sudo /sbin/sysctl -w kernel.sched_rt_runtime_us=950000
// modify
$ sudo /sbin/sysctl -w kernel.sched_rt_runtime_us=500000

又或者採用拉大間隔，讓每一個 thread 都停止數十秒以上。

特別感謝

蕭光宏學長

Github

https://github.com/morris821028/hw-realtime-system

關於小額付費

另一個名稱為 微支付 (Micropayment)，簡單來說提供顧客 (Consumer) - 銀行 (Broker) - 商家 (Vendor) 三方的交易。小額付費標明在交易金額小，因此交易成本也應該小，否則交易手續的計算能量就超過交易金額，更別說要扣除交易物品的成本。通常要在以下三點最小化

• 計算資源：
  在先前提到的加密算法中，key 的 bit-length 相當長，導致計算的能量消耗大。倘若只消費 1 元，耗電成本就佔了 1% 以上，甚至更多，那麼是划不來的。
• 儲存空間花費：
  計算每一組交易明細所需要的空間要最小，例如記錄金額需要 32-bit，那麼 n 次交易就需要 n 個 32-bit 的空間，在其他細節中還需要紀錄額外的購買來源、 … 等。
• 管理成本：
  第三方 (通常是銀行) 要管理顧客的金額花費、商家是否能取用顧客的錢。銀行要怎麼紀錄顧客的狀態、如何驗證商家真的有跟顧客交易 … 等。

由於交易金額小，即使被破解對雙方的損失也不大。但通常破解手段需要的時間、資源往往超過交易金額，因此不太會有人去破解這個。

應用層面

網路電子報：

一份電子報可能有一些特別的標題內容，若要深入查閱內文，需要讀者付費觀看。這一部分更具有彈性，對於一份具有相當多面向的電子報而言，有些人只看幾個專欄就必須花費購買一整本的金額，有些時候是浪費的。

網路期刊購買、資料庫詢問

網路學術期刊就跟電子報的情況一樣。資料庫詢問比較特別，花費小金額來交換資料庫服務的次數。

廣告

互動式影片、廣告商為了誘拐大眾仔細觀看廣告，由廣告商付錢給觀看者。例如回答問卷回饋、機率性地抽獎回饋 … 等。

網頁閱讀

類似向大眾徵文，鼓勵分享知識。徵求到的文章，由平台供應者支付。

何時用

使用者付費，而非訂閱長時間的垃圾訊息或服務。在大多數的服務商中，會提供時間內無限使用或按照次數計費兩種方案，在大多數的情況下，時間內無限使用是對商家有利，可以預先得到使用者的投資，但使用者在後續時間內可能沒有去使用、或者沒時間去用。

不是 按照次數計費全然好 ，就如 電話費 ，打了多少通電話、講了多久，只有電信商知道，即便告訴花費相當多金額，通話明細也是由他們提供，很難證明到底花了多少，這是對使用者的不利。相較起來，小額付費比較接近投幣式的公共電話，投了多少就打多少，等到快沒有餘額時，再進行補充。

先付款給商家會對使用者不利，有可能取得不好的服務，後付款給商家會對商家不利，因為使用者可能沒有足夠的金額。正因為小額交易，適時地刷新狀態 (再投幣) 就能在之間達到平衡。

數學

由制定 RSA 那伙人 Rivest, Shamir 提供 Payword scheme 的方法。

首先，概念建立在假設不用數字儲存金額 (減少儲存空間、管理花費)，而是用運算次數來知道花費金額 (用簡單運算來完成，防止能源消耗過大)。金額花費是整數，由最小單位 1 元構成，如果是在通貨膨脹的國家，最小單位可能不一樣？

那麼可以建立一個儲值金額 n 元的串列如下。

由使用者拿一個$x_n$ 初始化，接著利用 hash$x_i = h(x_{i+1})$ 得到每一個硬幣$x_i$。用數學表示遞迴公式$x_i = h^{n-i}(x_n)$。

當顧客跟商家交易時，簽一份簽章 (例如用 RSA 或者是 DSA 等方式) 給商家。簽章內容為

其中 $\text{Cert}$ 是由第三方信任銀行簽署給用戶的內容 (類似銀行帳戶的確認)。最後發送給商家資訊為

由商人去驗證 (檢查簽證內容、拿對方的 public key 打開，再去拿銀行的 public key 驗證 $\text{Cert}$ 是否正確) 是否是可信任的顧客或者是顧客是否存在。

接下來交易採用最笨的方案，每一次交易 1 元，交付 i 元時，顧客就告知$x_i$ 值給商家，這裡顧客得到硬幣方法為重新計算$x_i = h^{n-i}(x_n)$，可以不事先用記憶體儲存$[x_0, x_n]$，保留 $n$ 和$x_n$ 即可。

之後商家拿著 i 元$x_i$ 和$\text{Sign}_C(\text{Merchant-ID} || x_0 || \text{Cert})$ 的資訊給銀行，銀行計算 $i$ 次 hash$x_0 = h^i(x_i)$ 查看是否正確，若檢驗沒問題，則銀行從客戶存簿撥款給商家。

為什麼可行

運算過程中使用 hash，hash 提供不可逆的操作，因此商家無法有更多金額的索取，假設從顧客手中得到$x_i$，無法計算出$x_{i+1}$ 究竟是什麼，具有一定安全性。而顧客必須由銀行索取簽證，來表示當前的狀態是合法的，顧客沒辦法竄改自己的狀態，使得自己有更多的金錢，銀行那裏會有最新一組的簽章在？應該是吧，銀行會在商家發送驗證資訊時發生異狀檢查顧客是否竄改。

數學之美。

前言

幾乎是密碼學基礎數論，看來也走到這了。

亂來

隨便寫寫，上課不專心真是抱歉。

1. Given an integer $x$, what is the requirement to let the multiplcative inverse $x^{-1}$ exist when modulo $p$? if $x^{-1} \mod p$ exists, please write down the equation (based on Fermat’s theorem) used to compute $x^{-1} \mod p$. (5%)

   1. condition: $gcd(x, p) = 1$ for multiplcative inverse $x^{-1}$ exist when modulo $p$
   2. Fermat’s theorem : $x^{p-1} = 1 \mod p \Rightarrow x^{p-2} \times x = 1 \mod p$ $x^{-1} = x^{p-2} \mod p$

2. What is the Euler totient function $\phi(n)$? Please answer $\phi(77) = ?$

   $\phi(n)$ 表示 1 到 n 之內的整數，有多少與 n 互質的個數。
   $\phi(77) = 77 \times (1 - 1 / 7) \times (1 - 1 / 11) = 60$

3. Whais the discrete logarithm problem? (5%)
   對於等式 $y = x^a \mod p$，已知三整數 y, x, p，解出 a 的問題。詳見小步大步算法 baby-step-giant-step，複雜度 $O(\sqrt p)$

4. What is a hybrid cryptography? (5%)
   $$\text{hybrid cryptosystem } = \text{ public-key cryptosystem } + \text{ symmetric-key cryptosystem}$$

   • public-key cryptosystem
     提供 key encapsulation，就是 key 的安全性和簽章認證，保護 key 傳輸、保管上的問題。
   • symmetric-key cryptosystem
     提供 data encapsulation，提供高效率的加解密效能。

5. What are the two primary reasons of using a cryptographic hash before signing a signature? (5%)
   cryptographic hash 密碼雜湊函數，通常會計算 $hash(M)$

   • 單向不可逆
     難以給定一個雜湊值，並且逆推得到當初輸入的數值。
     • 提供訊息修改檢查，相同的訊息進行雜湊，高機率會是不同。
       $hash(M1) \neq hash(M2)$，如果 M1 和 M2 差異只有數個 bits 不同。
     • 防止在傳輸過程中被竄改。對於簽章則更難竄改成相同雜湊值且具有 意義 的訊息 $M'$。
   • 容易計算
     將一個長度很大的訊息，壓縮一個固定長度的數值，這數值方便後續算法計算用加密算法的部分。

6. Please write down the RSA public key encryption and decryption process (including public key and private key generation process). (10%)

   1. $N = p \times q$
   2. $\phi(N) = (p-1)(q-1)$
   3. $gcd(\phi(N), e) = 1, \phi(N) > e > 1$
   4. $d = e^{-1}, e \times d = 1 \mod ø(N)$
   5. public $e, N$
   6. private $p, q, d$

7. Please develop a left-to-right binary exponentiation algorithm without “conditional jump” which is usually dangerous to some engineering attack. (10%)
   Montgomery Ladder

   1 2 3 4 5

   R[0] = 1, R[1] = p for i = n-1 to 0, step = -1 R[1-a[i]] = R[0] * R[1] R[a[i]] = R[a[i]] * R[a[i]] return R[0]

8. Below is the DSA signature scheme in which $p$ is a large prime, $q$ is a 160-bit prime factor of (p - 1), $g$ is an integer of order $q$ modulo $p$. Let $x$ be the signer’s private key and $y = g^x \mod p$ be the public key.

   1. How to generate an integer $g$ ? (5%)

   2. Please complete the following nissing steps of the scheme. (10%)

   3. Please describe a trick for speeding up DSA’s on-line signing process. (5%)

      _______________________________________________________________________
      Signing algorithm                 Verification algorithm
      _______________________________________________________________________
      r = (g^k mod p) mod q             w = s^-1 mod q
      k is a random integer             u1 = (SHA(m) * w) mod q
      s = ________________              u2 = (r * w) mod q
      m is the messgae                  v = _________________
      the signature is (s,r)            if v = r then the signature is correct
      

   • $g = h^{(p-1)/q} \mod p$ ，其中隨機亂數 $h$，滿足 $g > 1$ 即可。
     從費馬小定理中，有一個比較特別的計算來得到 order $q$，所謂的 order $q$ 就是在前 $q$ 個 $g^i \mod p$ 下不會出現重複 (循環長度至少為 $q$)，從觀察中得知循環長度 $L$ 滿足 $L | p-1$，也就是說 $L$ 是 $p-1$ 的因數，$q$ 則是要找到一個大循環，讓攻擊者更難找到 $x$，又因為 $L$ 是其因數，由於 $q$ 是 $p-1$ 的其中一個質因數，則保證是一個最小循環節的要求。

   • $s = k(SHA(m) + x \times r)$ $v = g^{u1} y^{u2}$

   • 可以 offline 去預處理隨機亂數 $k$，事先計算一堆的 $r$、$z = k^{-1}x \times r$，那麼計算 $s$ 可以非常的快速，$s = k^{-1} SHA(M) + z \mod p$，假設 hash 計算快速，只動用到一次乘法和加法，相較於 RSA 的簽章方法，少了指數次方運算。

9. Under the following certificate hierarchy, please provide all the details of how end user A checking the correctness of end user C’s public key by verifying a sequence of certificates. Note: User A only knows X’s public key, but does NOT have the root Z’s public key directly. (10%)
   若 A 要確認 C 給的 public key 是否正確，則依循以下步驟來確認

   1. C 拿出 Y<<C>>，拿 Y 的 public key 進行確認 C 的 public key。
   2. 再檢查 Y 的 public key，Y 拿出 Z<<Y>>，拿 Z 的 public key 進行確認 Y 的 public key。
   3. 再檢查 Z 的 public key，Z 拿出 X<<Z>>，拿 X 的 public key 進行確認 Z 的 public key。
   4. 由於我們知道 X 的 public key (藉由實地臨櫃面對面確認 X 的 public key)，最後驗證 C 給的是正確的 public key。

            Z
          ／ ＼          Notation used
         X     Y         X<<A>>:
       ／ ＼    ＼       A's certificate issued by X
      A     B     C
      

10. Pleasewrite down the Diffie-Hellman key exchange protocol (including the public key and private key generation process). (10%) What is the man-in-middle (or the middle person) attack? (5%)

    • 共同決定一個大質數 $p$ 和一個基底 $g$ (全部人都知道)
    • 每個人 A 擁有自己的 private key $x_A$ ($x_A < p - 1$)
    • 每個人 A 計算自己的 public key $y_A$ ($y_A = g^{x_A} \mod p$)

    假設有兩個人 A, B 要通訊，則把自己的 public key 交給對方，共同產生出一把暫時的 key $K_{AB}$ 進行通訊加密。

    • 對於 A 來說會接收到 $y_B$，計算$K_{AB} = (y_B)^{x_A} = g^{x_B \times x_A} \mod p$
    • 對於 B 來說會接收到 $y_A$，計算$K_{AB} = (y_A)^{x_B} = g^{x_A \times x_B} \mod p$
    • 由於離散對數是一個困難問題，很難藉由攔截紀錄來得到對方的 private key $x_A$，因此有一定的安全性。

    假若現在要進行中間人 C 的攻擊，則會在一開始交換 $K_{AB}$ 的時候插入到其中通訊。

    • A 發送 $y_A$ 給 B 時，受到 C 的攔截。
    • C 知道 A 想要跟 B 通訊，則把自己的 $y_C$ 發送給 B，並且也傳一份給 A。
    • B 以為是 A 要進行通訊，實質拿到 $y_C$ 而非 $y_A$。
    • 產生兩把 key$K_{AC}, K_{CB}$，C 就偷偷在中間偷聽，並且作為中繼傳送訊息，需要解密 (拿$K_{AC} \text{ or } K_{CB}$) 之後再進行加密$K_{CB} \text{ or } K_{AC}$ 送給另一方。

    如何防止中間人攻擊，大約有幾種方法，但牽涉到可信任第三方、計算速度。

    • 發送訊息上，計算時間的延遲不得超過一定限制，否則可能存在中間人攻擊。
    • 藉由可信任第三方 CA (Certificate Authority) 來驗證彼此的 public key 歸屬於誰
      由 CA 簽認$Sign_{CA}(\text{public key || owner_id || expiration date || ...})$，如此一來如果存在 C 中間人，則轉交 $y_C$ 給 B 時，B 就會藉由 CA 驗證得到 owner_id 不是通訊對象 A。如果 CA 不可信任，則可以讓 C 簽一個$Sign_{CA}(\text{public key C || owner_A || expiration date || ...})$ 來欺騙 A 和 B，也就是說 CA 和 C 偷偷在私底下做了黑心勾當，那麼中間人攻擊仍是存在的。

11. Both message authentication code (MAC) and digital signature can be used to provide the functionality of message origin and integrity check. Please briefly describe these two techniwues and compare percisely the difference between these two techniques. (10%)
    message authentication code (文件訊息鑑別) 顧名思義就是針對 message 進行驗證，確認發送者身分和資料完整性，相較於 digital signature (數位簽章) 也是做相同的事情，訊息量不同且產生出來的結果也大不相同。通常文件訊息鑑別會破壞儲存資訊，藉由雙方共享的 key 來進行身分認證，可用暫時性的 key，若採用非對稱式則需要額外的數位簽章來輔助驗證發送者。而數位簽章則是提供有效期限內的使用，這把驗證的 public key 必須存在比較長的時間。
    數位簽章簽定時不知道對方怎麼簽，但能驗證是他簽的並且只有他簽得出來，文件訊息鑑別通常知道對方用什麼流程輸出一樣的數值。

問卷設計跟面試方法一樣，如何了解使用者的需求與能力，如何發問、如何誘導都是相當有趣的。對於每一種人格特質，在面對不同問題的問法時，作答的難易度是有影響的，這對面試官也是相當重要的課題，因此需要了解到問題設計的方法。

關於問卷

問卷通常會分成兩種

• 定量分析
  詢問回答者的意見 程度 ，通常採用二值化，在從正到反極劃分數個單位，讓使用者選擇。
• 定性分析
  單純詢問使用者的 看法 ，在不給予任何提示下，讓使用者根據自身的經驗回答問題。

當不知道問題的答案分布，既不是好與壞兩者，那麼定量分析就不能作為評估，採用開放式作答的定性分析，讓使用者回答它們所理解的，通常開放式有一個缺點，會導致過於雜亂的回答，很難得到期望的答案。想必很多人在不理解 問題描述 就會答非所問。定量分析的面向去設計，會得不到意想不到的答案，兩種方法各有優缺。

問卷設計

按照上述的兩種情況分成 選項 跟 申論 兩種。申論題就不必說，留給使用者提出自己的看法，欄位設計就是文字欄位而非選項欄位。

特別介紹一下選項部分，通常會有 是 / 否 、 喜歡 / 不喜歡 ，再複雜一點就是 非常喜歡 - 喜歡 - 沒意見 - 不喜歡 - 非常不喜歡 。如果在量表中只有偶數選項，通常是不存在中立立場，希望每個應答者都給予一個立場去回答，反之在奇數選項中，給予中立立場的應答機會，通常會得到非常多的 沒意見 此時有效問卷的數量相對少。

關於面談

面談通常會分成三種

• 結構化
  封閉式對答，在已知答案中做決策。循序讓使用者回答問題。
• 半結構
  相較於結構化問題，不要求詢問順序性，或者是確切的答案回答。
• 非結構
  問題會隨著應答者回答的方式變化。

通常第三者的非結構面談相當輕鬆，如果變化問題不特別刁難，面談者也會根據應答者的能力詢問相關問題。然而在結構化問題中，相當一板一眼，容易對應答者感到緊張，當問題卡住的時候，接下來的問題就會影響到應答者的狀態。半結構化則介於兩者之間。

團體面談

• 部分應答者很容易被忽略，需要主持人去引導，觀察每個應答者在聽取其他人回答的肢體語言，適時地將每個人的意見引出。
• 很難獲得想要的資訊。
• 回答之間會相互影響。

特別小心主持人不應該讓面談者們 達到共識 ，而是讓他們分享所知。誤導或誘答的情況應該避免，否則有可能會造成馬拉松領先者帶著一群人走錯方向的感覺。感覺不少情況會設下陷阱去讓面談者誤答，在問題描述上不給予明確的規範，在算法問題上也常常會這樣，至於算不算誤答就不曉得，當一個人對問題的背景認知不同時，問題本身就不一樣，能不能 取悅 面試官呢？

歸納問卷

回收問卷後，利用定性方式去得到的答案是最難分析，只能靠觀察去理解，對於定量方式去設計的，將要看採用的數學模型來決策，例如消頭去尾後得到的平均數、眾數、中位數 … 等。不管哪一種方案，要看應答者的文化習慣，是否會造成不願意表態，極端情況是否正常 … 等因素，適時地消去一些實驗數據進行統計。

問卷介面也要有所區別，通常會有數個相似領域的問題，整合在一起，並且給予一個問題大綱有助於對問題的理解，特別注意到問題設計時要確定題目是否能二極化。

各組設計

最奇葩的要來了，針對認知風格進行問卷調查，針對先前設計的遊戲，不同認知風格對遊戲介面的觀感。，各組提出的問卷問題如下：

塔防遊戲

• 遊戲中介面的引導對你有哪些幫助？
• 升級頁面的兵種介紹對你有何影響？
• 過多提示會不會扼殺你對遊戲的興趣？為什麼？
• 你覺得遊戲中哪一個功能最不直觀？為什麼？
• 是否希望一開始就解鎖所有關卡？為什麼？
• 無法順利通關時，你都如何應對？
• 升級頁面的兵種能力數值是否能幫助你理解兵種特性？如果不行，希望如何改善？
• 你覺得遊戲中哪一個功能最不直觀？為什麼？
• 你覺得遊戲中在哪個部分自由度不夠？希望如何改善？
• 你希望遊戲中哪些介面能夠讓你自行調整？

角色扮演

• 你覺得主畫面看起來如何 (例如背景顏色、排版、標題等等)或是其他？
• 你覺得說明文件的詳細度以及對於操作的說明還有排版等恰當嗎，能助你了解遊戲怎麼進行？
• 關卡劇情有沒有讓你覺得充滿故事性、關聯性，讓你進入遊戲中？
• 遊戲的流程、難度、還有系統的圖示資訊你覺得夠完善嗎，能幫助你遊戲順利？
• 你覺得遊戲的音樂選擇跟切換時機有讓你覺得非常合理，並且具有強大代入感嗎？
• 您覺得遊戲難度是否可以自行解決？為什麼

我們組所提出的七個問題如下

• 您覺得遊戲難度是否可以自行解決？為什麼
• 您最喜歡、討厭這遊戲哪一部分，討厭的話，想改成什麼？
• 您覺得遊戲內介面的看法如何？
• 您對於介面的動畫效果的看法如何？
• 您玩完這款遊戲後，對遊戲目標瞭解程度 (例如劇情 …)？
• AI 擬真程度對遊戲操作的感受？
• 原本期望的效果、事物卻沒在遊戲中的是什麼？

解謎遊戲

• 在遊戲進行當中在覺得最困難的部分為何？
• 如果在遊戲中加入選關模式，你有什麼看法？
• 對於遊戲介面，你認為有什麼可以改善的地方？
• 教學關卡對你學習遊戲的操作模式有什麼影響？
• 對於破關後才加入競速模式，你有什麼看法？
• 你認為遊戲劇情有何改善空間？

問卷統計範例

本課程教學極為詭異，應該請全班人一起填，總共才七組來卻只要求自己去找 課程班上 十個人來填問卷，互填對方設計的遊戲問卷難道這麼困難嗎？老師應該要直接請全班來填寫吧，用鼓勵的方式，居然在畢業前一周要大家填問卷，一星期統計好並且報告，明顯地大家都在忙畢業典禮的拍照，問卷也很晚統計回來。

當然十個人的樣本數只能自我安慰，下什麼結論都是不具有信用的，只好按照老師的調調亂扯一通。就算遊戲做得再差，問卷回饋不如預期的對答，也許按照自己的預測方式去報告就行，問卷感覺就是裝飾用的。自己的教授自己靠北？

問卷結果

分別對於兩個版本，非常非常少的實驗數據。

遊戲難度 Holist 認為難度簡單，對遊戲進行不算困難，對於 Serialist 比較有新事物認知上的起手問題。

在遊戲偏好上，大部份的 Holist 看到了整體的光影效果對此深感好奇，而 Serialist 不少指出遊戲說明上的困惑與扣除血量的細節。

在遊戲內介面上，Holist 對於道具切換、使用狀態有強烈的要求，太過簡潔的界面是介意的地方，而在 Serialist 對於顏色要求較為強烈，對於簡介的介面設計滿意。

在遊戲介面動畫上，Holist 比較偏向回答遊戲內部的元素動畫，而 Serislist 則比較在意流血效果和字體閱讀。在這一部分的回答可以說是有點誤導，預期是想要讓他們回應遊戲介面動畫，而非遊戲內的元素動畫。

在遊戲目標上，一致都朝著遊戲通關目標為基準，而非劇情走向，估計是劇情走向對遊戲進行流程不影響，所以沒有必要去注意遊戲劇情內容。

在人工智慧 AI 上，Holist 比較偏向滿意，對有一些與現實邏輯不合的反應介意，對於 Serialist 對於 AI 的反應比較兩極，有好有壞。

對於預測遊戲進行上，Holist 比較想要的是局部性改變，例如效果與道具使用上、遊戲進行邏輯、新的功能利於闖關。而 Serialist 比較喜歡全局性的擴充，如新增關卡、不同類型的通過條件、關卡成就感、角色成長的需求。

課程意見

請不要一堂課的結尾就喊出成績來決定一個學生的價值，若要從認知風格中挑選一種分類，老師的認知風格屬於一種衝動型，部分是需要不斷反思來接受新的資訊。不強求這門課的走向，但從做遊戲方面，可說是此次教學的創舉，既然要我們寫程式，麻煩就以資工系的方式引導，時間跟計劃不是一兩個星期前講就了事，牽涉到設計與構思，不給一個明確的方向，導致各組面向不同種遊戲，類型不同的遊戲設計出來就不能隨意說好與壞，若是要符合你們口味的網路學習，那直接說做益智遊戲即可，有些探討問題也因遊戲類型扯不上關係。

若要用小組程式作業、設計作為不上課的理由實在說不過去，導致這一學期很多次沒上課，起碼可以一個小時上課，後兩個小時討論的方式。而在論文上台報告卻有報告老師的同一篇論文，導致報告內容重複且冗長。上課投影片請不要用講稿模式 (兩攔筆記式，另一半的筆記欄位不知道給誰看的)，可以請助教弄全螢幕的投影片。

由於在選讀論文時，和上課都遇到相關問題，但一直對這 SVD 的實際感觸沒很深，了解數學計算，卻不知道特性一直很困惑我。在這裡收集一下曾經學過的內容，當初在線性代數時沒有學到這一塊，至於 $LU$ 分解有沒有上到過，我自己也深感困惑，不過看一下網路資源勉強還能理解。

至於 SVD 則在線性代數非常重要，在許多領域時常會遇到，如巨量資料 (massive data)？機器學習？影像處理？就我所知理解看看吧！

SVD

定義從一般式

得到縮減過後的相似矩陣

給定 $A$ 矩陣，要變成三個矩陣相乘，可以壓縮儲存空間，一般來說都是拿來得到近似的 $A$ 矩陣，藉由刪除過小的 eigenvalue 來完成，eigenvalue 就是所謂的矩陣特徵值。

在學線性代數時，沒有仔細想過 eigenvalue 的意義所在，每一個 eigenvalue 也會對應一個 eigenvector，這些 eigenvalue 大小對應的分佈的相關性大小，而 eigenvector 則表示新的轉換軸的方向。類似最小平方法得到的結果。

但在巨量資料課程中我們可以知道一件事情，若是稀疏矩陣 $A$，經過 SVD 運作後，得到 $U, V$ 矩陣都是稠密的，因此空間儲存反而划不來，因此會有另外一種解法 CUR，可以上網搜尋 massive data mining coursera 在 這裏 可以知道關於 CUR 的資訊。

從課程中的例子來看，假設在電影評論系統中，則 A 矩陣表示電影對人的喜好度，則 SVD 相當於如下描述 (假想，單純的矩陣概念)

• $A(i, j)$ 電影編號 i 對用戶 j 的好感度
• $U(i, j)$ 電影編號 i 對電影屬性 j 的成分程度
• $\Sigma(i, j)$ 電影屬性 i 跟電影屬性 j 的之間重要性。
• $V(i, j)$ 表示用戶 i 對電影屬性 j 的偏愛程度。

也就是說有一些電影屬性不是很重要，可以移除掉，這樣的表示法得到一個近似的矩陣 $A$。

在巨量資料中一個有趣的運用，可以用在購物推薦系統中，來達到預測相關性，跟某人對其他產品的喜好程度或者是需求性，但是在處理之前會遇到矩陣過大，但又非常稀疏，為了解決紀錄問題，就有奇奇怪怪的 Dimensionality Reduction 來完成，SVD 就是其中一種方法。

其他應用部分，將不重要的特徵值消除，來求得哪些元素是需要的，看到有一篇 文章 在做 PCA 主成份分析。

如此一來就可以知道要保留哪幾個主要資訊。

在虛擬實境論文中也是有這樣的處理，做的是 CT 建模，將模型的每個頂點，要計算 QEM (最小二次誤差) 的重要性，可以將其表示成一個矩陣，利用 SVD 方式得到，來決策要保留前 k 個重要性的節點，再將其他節點移除，來讓新得到節點盡可能地可以貼近真實模型。

之所以會這麼做，是要利用內插法來強迫得到邊緣偵測，但這樣會造成很多新頂點，為了要把過多頂點消除，使用 QEM 作為評價方法，利用 SVD 來完成大規模刪除的操作。

Map-Reduce

都明白 SVD 是一個很繁複的做法，有一個 $O(N^3)$ 的算法來求得所有 eigenvalue，若要用一般電腦跑，光是得到一個大矩陣所有 eigenvalue 複雜度相當高，其複雜程度沒有細讀過。有一種迭代的方法，類似馬可夫過程，每一次迭代可以逼近一個 eigenvalue，為了得到 n 個 eigenvalue，想必要迭代非常多次。運用 Map-Reduce 分散到很多台群落電腦加快矩陣乘法，這種方法的複雜度是可以期待的。

詳細操作 請參考

eigenvalue $\lambda$ 滿足

現在開始迭代 $v$ 讓其等式趨近於穩定

初始化$x_{i} = (1, 1, ..., 1, 1)$ ，其中$|x_{i}| = 1$ 藉由長度為 1 的向量，來求得$\lambda$，之所以要對 $x$ 進行正規化，其一就是要求出$\lambda$，另一個原因是要看何時穩定，當$|x_{i} - x_{i+1}|$ 差距夠小時，則表示進入穩定狀態。

那就可以得到矩陣 $A$ 的其中一個 eigenvalue，為了求得另外一組解，得到新的$A^* = A - \lambda x x^T$，再對$A^*$ 找到 eigenvalue，不斷地迭代下去。

DSA

Digital Signature Standard (DSS) 數位憑證標準，而有一個 DSA 演算法來完成憑證。

每一次憑證傳送三個參數 $(r, s, M)$，利用私用金鑰進行加密。讓對方使用公鑰進行驗證。

• $r = (g^k \mod p) \mod q$
• $s = k^{-1}(SHA(M) + x \times r) \mod q$

give receiver $(r, s, M)$, we have random (one-time) $k$ & private key $x$

每一次簽名時，最好使用隨機亂數 $k$ 作為簽章用途，隨用即棄，若發生重複使用，將會發生被攻擊，被攻擊者拿到私鑰後，攻擊者就能進行偽裝。

Attack

if reused $k$

如果重複使用隨機變數 $k$，可以藉由夾擊的方式得到，雖然不知道加密的隨機亂數 $k$ 究竟是什麼，藉由夾擊可以把 $k$ 消除，利用乘法反元素反求 $x$ 是多少，公式如下所述。

• $k = s1^{-1} (SHA(M1) + x \times r) \mod q$ - (1)
• $k = s2^{-1} (SHA(M2) + x \times r) \mod q$ - (2)

subtract (1) - (2)

• $0 = s1^{-1} SHA(M1) - s2^{-1} SHA(M2) + (s1^{-1} - s2^{-1}) x \times r \mod q$
• $s1^{-1} SHA(M1) - s2^{-1} SHA(M2) = (s2^{-1} - s1^{-1}) x \times r \mod q$
• $x = (s1^{-1} SHA(M1) - s2^{-1} SHA(M2)) \times (s2^{-1} - s1^{-1})^{-1} \times r^{-1} \mod q$

get private key. Dangerous !

Verify

驗證的正確性與否，接收者需要計算以下四個步驟來完成驗證。

• $w = s^{-1} \mod q$
• $u1 = (SHA(M) \times w) \mod q$
• $u2 = r \times w \mod q$
• $v = g^{u1} y^{u2} \mod q$

test $v = r$, why correct ?

理論的正確性可以參考以下證明，把公開的 $y = g^x \mod p$ 拿出來，這個安全性取決於離散對數的算法難度。

• known $y = g^x \mod p$, $x$ is a private key
• because $s = k^{-1}(SHA(M) + x \times r) \mod q$
• then $k = s^{-1}(SHA(M) + x \times r) \mod q$

want $r = (g^k \mod p) \mod q$

• $r = (g^k \mod p) \mod q = g^{s^{-1}(SHA(M) + x \times r)} \mod q$
• $r = g^{s^{-1} SHA(M)} \times g^{x (s^{-1} \times r)} \mod q$
• $r = g^{s^{-1} SHA(M)} \times g^{x^{(s^{-1} \times r)}} \mod q$
• $r = g^{s^{-1} SHA(M)} \times y^{(s^{-1} \times r)} \mod q$

而我們事實上就是在處理指數部分，

離散對數

解決問題 $y = g^x \mod p$，當已知 $y, g, p$，要解出 $x$ 的難度大為提升，不像國高中學的指數計算，可以藉由 log() 運算來完成，離散對數可以的複雜度相當高，當 $p$ 是一個相當大的整數時，通常會取用到 256 bits 以上，複雜度則會在 $O(2^{100})$ 以上。

實際上有一個有趣的算法 body-step, giant-step algorithm，中文翻譯為 小步大步算法 ，在 ACM-ICPC 競賽中也可以找到一些題目來玩玩，算法的時間複雜度為 $O(\sqrt{p})$，空間複雜度也是 $O(\sqrt{p})$。相信除了這個外，還有更好的算法可以完成。

小步大步算法其實很類似塊狀表的算法，分塊處理，每一塊的大小為 $\sqrt{p}$，為了找尋答案計算其中一塊的所有資訊，每一塊就是一小步，接著就是利用數學運算，拉動數線，把這一塊往前推動 (或者反過來把目標搜尋結果相對往塊的地方推動)。因此需要走 $\sqrt{p}$ 大步完成。

虛擬實境這一門課可以讓你體驗有如在上另一門課的虛擬實境，前半段講生物結構，來了解軟硬體需要那些特性、效能，後半段在講視覺建模算法，牽涉到計算幾何、線性代數 … 等課程。

在幾何課程中介紹的 Delaunay triangulation 對於建模算法是相當重要，接著在多重解析度部分牽涉到傳輸跟處理速度，在資料結構的儲存上很有趣。為了加速運算效能、漸進式需求，各種轉換壓縮都會跑出來。

複習

1. (15%)[Definition]
   詳細說明一個虛擬實境 (virtual reality) 系統需要具備那些特性，並說明一個虛擬實境系統要用到哪些軟體技術。

   提供人們能感知的動態環境，視覺、嗅覺、觸覺，並且能與環境互動中得到反饋，得到逼真感覺。需要以下幾個軟體

   1. 影像處理與繪製
   2. 物理引擎
   3. 擷取資料的整合

2. (15%)[Human perception]
   說明人類 1. 單眼立體視覺的原理，2. 雙眼立體視覺的原理；並3. 比較其優缺點。

   1. 單眼立體視覺靠單一眼球調整焦距，將數張影像交給大腦來整合，這必須藉由對物體認知來補足。
   2. 雙眼立體視覺的原理主要靠左右兩個眼球不同的相位差，來計算立體影像的距離差距。
   3. 視野範圍以及反應時間，單眼必須藉由調整焦距來補足，雙眼可以同時獲取不同相位差的影像。

3. (15%)[Hardware]
   說明感應手套 (sensing glove) 與力回饋手套 (force-feedback glove) 的原理，並比較他們在應用上的差別(可舉例說明)。

   感應手套是由操作者的反應傳輸給感測器，藉由手套上感應器之間的變化數據得到操作者給予的狀態。力回饋手套則是將物理特性反饋給使用者，藉由手套上的機械，施予使用者力反饋。

   感應手套為使用者操作，力反饋手套則相反由環境操作。

4. (15%)[Modeling]
   說明五種 3D 模型的表面表示式 (surface representation)，並比較這些表示式的優缺點。

   目前共計主要分成五種表示法：

   • regular square grid meshes (RSG)

   • triangulated regular meshes (TRM)

   • triangulated irregular networks (TINs)

   • polygon meshes

   • parametric patches

     RSG 建造簡單，但會有四點不共平面，影響到貼圖繪製上的問題。TRM 解決四點不共平面問題，但與 RSG 問題無法凸顯邊緣。TINs 解決無法凸顯邊緣問題，但需要經過最佳化算法來得到不規則三角網格，儲存方式必須記錄所有的點座標，由於要經過最佳化算法，處理速度會慢上很多。動態更動座標的效果較差。polygon meshes 建造相對困難，多邊形的最小單位是三角形，頂點儲存量比 TINs 少很多，parametric patches 藉由取樣點套入參數，讓表面接近平滑，針對部分訊息的改造，平滑效果造成的反饋比較逼真。

5. (15%)[Multiresolution modeling]
   說明並比較以小波轉換為基礎的多重解析度模塑 (wavelet-based multiresolution modeling) 技術與 Lindstrom 等人的對稱三角網格 (symmetric triangulated networks) 多重解析度模塑技術的原理及優缺點。

   • wavelet-based multiresolution modeling
     解析度資料量與面積成正比，考慮到與觀察者之間的距離，用另外三張影響轉換到更高解析度，每一次解析度增加兩倍。

   • symmetric triangulated networks
     考慮到地形高地、平坦性對於觀察者的影響，投影到使用者的平面，判斷是否差異過大需要提供更高解析，解析度資料量所需節點數成正比

     相較之下，小波轉換給予的傳輸資料反應會比較慢，同時也會在使用者感受不到差異的地方提供更高解析度，很容易浪費資源，對稱三角網格在資料鏈結會複雜許多，沒有小波轉換的儲存架構來得容易理解，但對稱三角網格反應速度快，支持快速的解析度變換。

6. (15%)[Multiresolution modeling]
   說明漸進網格 (progressive mesh) 多重解析度模塑與二次誤差 (quadric-error-metric) 多重解析度模塑的相同與差異處，並比較兩者的優缺點。

   漸進網格藉由拔點、縮邊，提供不同解析度，依序拔點，考慮四個因素來決策拔點順序，這四個因素分別為影響到其他點之間的距離、縮邊的長度總和、頂點材質的差異、對邊界影響程度。

   考慮的是從精細模型轉換到粗糙模型的差異變化，挑選變成粗糙的影響最小的先拔除，這樣的計算量會比較大，拔除一點後，鄰近的點的誤差值計算也要跟著重新計算。

   二次誤差類似漸進網格的方式進行拔點縮點，但縮邊完的的結果不會只有三種可能，縮到兩端點的其中一個、或者是中點，提供一個數學計算來找到縮到哪一個地方更好。

   二次誤差考慮的是從端點誤差值得相加，並且產生一個新的頂點，有點霍夫曼編碼的意味在。計算從粗糙模型上的點到精細模型平面的距離平方，與之前的模型 (Progressive mesh - Hoppe) 恰恰相反，並不是考慮精細模型上的點到粗糙模型平面的距離平方。因此對於 QEM 的誤差可以累加。問題是粗糙模型上的頂點是無法得知，屬於未知數，用內插法。QEM 誤差精確度只是約略，速度快但品質沒有 Progressive mesh 來得好。

1. (15%)[Multiresolution modeling]
   說明 (a) 動態載入 (dynamic loading) 的意義。(b) 動態載入與多重解析度模塑技術整合會產生什麼問題。(c)解決上述問題的三種方法。

   動態載入為在記憶體不足時，將部分資料存放在磁碟中，當程式運行到需要那些資料進行運算時再從磁碟中讀取，這樣的過程稱為動態載入。

   動態載入對於多重解析度塑模來說，主要是記憶體問題以及所需要的解析度跟數據大小關係，解析度度越高，所需要的資料量越多。但是畫面呈現的解析度不一下，要怎麼進行資料讀取，動態載入的數據結構定義則需要特別設計，例如是要 response time 最小、計算複雜度最低，讀取數量最小 … 等。

   假設需要不同解析度可以靠 Discrete layered multiresolution models，每一種解析度彼此獨立儲存，這樣的方法可以提供基礎的不同解析度，但讀取時間相對長，儲存在磁碟的空間需求大，效果呈現是最快的，但是離散結果會有不連續的解析度變化。

   為了解決解析度連續變化問題，可以使用 progressive mesh 來達到，提供以點、線與解析度呈現線性變化。

   若需要不同解析度，可以利用 hierarchical models 來完成畫面中每一處的解析度不同，這是一種資料結構，當需要更高解析度時，則走訪更深的樹節點來印出所需要的畫面。

   評價效果好壞利用 Delaunay triangulation 計算平滑程度。

2. (15%)[Rendering]
   說明shading的意義，敘述 Gouraud shading 與 Phong shading 的作法，最後比較他們的優缺點。

前言

上次沒有好好地將遊戲內容進行擷取說明，單純對介面設計原則做說明，介面設計會根據裝置操作有所不同吧，那遊戲介面是否又能如此？

要把法則呈現在遊戲中又是另一回事，畢竟遊戲跟網頁又有點差別，當然也有人認為認知風格跟遊戲性不相干，倒不如說會跟遊戲內容有關，遊戲內容決定介面設計方向，若要根據認知風格設計，想必會是一道難題。

遊戲內容的多寡將決定運行的流程、架構，遊戲介面越簡潔越好，最後的演化就是什麼 都沒有最好 ，除非有人喜歡儀表板，那就另當別論。隨著遊戲必要才出現的介面，會導致程式撰寫相當麻煩，要用排除法來防止奇葩的流程走向。

不僅介面擺設需要考量，還要有觸發時間、方法，以及浮現效果，這些會影響到使用者是否知道可以使用，大部分的介面以文字為主，那串接效果影響不大。為了提升使用者體驗，最好是使用圖示為主，但這會造成跟背景融合的一體感，可能會造成無法被使用者察覺可觸發，必須在圖示效果加點功夫。

就像虛擬實境課程內容所提及的漸進式效果會比較好，對於使用者有如虛擬實境，也就是說介面出現的時間跟方法不能太過迅速。關於上虛擬實境課程的那些小事，有如在上影像處理課程的虛擬實境呢。

以上內容，僅本人觀察。

Github

如果圖片看不到，請至 Github 中的 doc 目錄下查閱本篇附圖。

遊戲執行檔和開源代碼都在其中，當然還有遊戲的編輯器。更多的遊戲截圖在裡頭，只支持 windows 平台。

Animate

Info	Demo
Menu Enter/Select
Button Enter
Popup Menu
Menu Focus
Lighting
Fog
Use Props
Caption

Screenshot

Menu Design

選單使用方向鍵和滑鼠點擊操控，同時提供大綱說明。

Info	Demo
How to Play
Story
Test Room
Achievement
Options

Tutorial Design

使用教學關卡，步入遊戲元素與操作。

Info	Demo
Tutorial

Game UI Design

遊戲介面細節設計

Info	Demo
Tip
Control Information
Exit Warning
Props View 1 (Scroll up)
Props View 2 (Scroll down)
Level Complete
Level Fail

Game Element

遊戲元素效果

Info	Demo
Hide
Use
Test Room

Option Design

遊戲配置設計

Info	Demo
Sound
Difficult

Story Design

過場 (eyecatch) 劇情的介面設計

Info	Demo
Story
Story branch 1
Story branch 2

Other Mode

遊戲模式設計

Info	Demo
Time Mode 1 (Time Count)
Time Mode 2 (Time Up)
Time Mode 3 (Time Over)

Feature

考量的設計並沒全部去實作，提供設計參考。

Menu Layout

Info	Demo
Old 1
Old 2
X-Box
Andriod
Hexagon
Overview 1
Overview 2

Game Layout

Info	Demo
Origin
Clear
Icon With props 1
Icon With props 2
Exit Menu

Option Setting

Info	Demo
Keyboard 1
Keyboard 2

Over Layout

Info	Demo
Popup

Game Flow

Info	Demo
With Over
With Eyecatch

Game Caption

Info	Demo
Balloon

筆記錯誤多多，請以僅供參考的角度去質疑

Problem

1. Below is a key distribution protocol.
   (a) Please describe the details of “replay attack” when $N_1$ is removed from the protocol.
   (b) Please modify the protocol to enable party A to confirm that party B already received $K_s$?

2. Please explain link encryption and end-to-end encryption.

3. (a) Please describe details of the Fermat’s theorem (or called Fermat’s little theorem).
   (b) How to compute the multiplicative inverse of an integer $a$ modulo $p$ based on the Fermat’s theorem?
   (c) What is the requirement for $a^{-1}$ to exist?

4. (a) Please describe details of the Euler’s theorem.
   (b) Based on this theorem, please describe the basic idea of the RSA encryption and decryption process.

5. The Miller-Rabin algorithm is used to test whether an odd integer n is a
   prime. Please complete the following missing steps of teh algorithm. (15%)
   (1) Find integers $k, q$ ($k$ > 0, $q$ odd), so that $(n - 1)$ = __________
   (2) Select a random integer $a$, $1 < a < n - 1$
   (3) if (_______) then return (“maybe prime”)
   (4) for $j = 0$ to $k - 1$ do
   (5) if (_________) then return (“maybe prime”)
   (6) return (“composite”)

6. Please describe details of the Chinese remainder theorem for the case of $n = p \times q$ where both $p$ and $q$ are primes. (Your anseer should include how to transform an ordinary domain integer $A$ to the CRT domain, and the CRT formula used to inverse-transform the CRT domain representation back to the ordinary domain integer).

Notes

Part 1

基礎步驟如下

1
2
3
4
5

(1) A -> KDC : IDA || IDB || N1
(2) KDC -> A : E(Ka, [Ks || IDA || IDB || N1]) || E(Kb, [Ks || IDA])
(3) A -> B   : E(Kb, [Ks || IDA])
(4) B -> A   : E(Ks, N2)
(5) A -> B   : E(Ks, f(N2))

如果沒有 $N_1$，紀錄 IDA || IDB、E(Ka, [Ks || IDA || IDB]) || E(Kb, [Ks || IDA])，就能假冒 KDC 讓 A 用固定的 $K_s$ 去跟 B 連線。再藉由已知明文，就能知道雙方的溝通內容，進行竊聽。

為了讓 A 知道 B 擁有 $K_s$ 修改其中兩個步驟

1
2

modify  (3) E(Kb, [Ks || IDA]) || Nx
        (4) E(Ks, N2 || Nx)

Part 2

• link encryption 屬於 router 之間的通訊，屬於低階網路層協定，在每一條連輸線路各自獨立的加解密，會修改訊息 header，可以增加 padding，保護流量偵測。
• end-to-end encryption 屬於原點、目的地之間的加密，它們共同享有一把 shared key，屬於高階網路層協定，用來保護資料安全，訊息 header 保留給傳輸用。

Part 3

Fermat’s theorem :

$$a^{p-1} \equiv 1 (\text{mod } p)$$

為了要求 $x^{-1}$，則利用費馬小定理 $x^{p-2} \times x \equiv 1 (\text{mod } p)$，因此 $x^{-1} \equiv x^{p-2} (\text{mod }p)$，特別小心 $p$ 一定要是質數，且滿足 $gcd(x, p) = 1$。

Part 4

Euler’s theorem

$$a^{\phi(n)} \equiv 1 (\text{mod } n) \text{ , }gcd(a, n) = 1$$

先來複習一下 RSA 算法的產生與加解密

1. select two large primes $p$ and $q$ at random.
2. Let $N = p \times q$, $\phi(N) = (p-1)(q-1)$
3. select (at random or fixed) the encryption key $e$
   where $1 < e < \phi(N)$, $gcd(e,\phi(N))=1$
   so, $e^{-1} \mod \phi(N)$ exists
4. solve following equation to find decryption key $d = e^{-1}$, $e \times d \mod \phi(N)=1$
5. publish public/encryption key:$KP = \left \{ e,N \right \}$
6. keep secret private/decryption key:$KS = \left \{ d, p, q \right \}$

encrypt a message $M$ the sender:

• obtains public key of recipient $KP = \left \{ e,N \right \}$
• computes: $C = M^e \mod N$

decryption a ciphertext $C$

• uses his private key$KS = \left \{ d, p, q \right \}$
• computes: $M = C^d \mod N$

用來加解密，為什麼會是正確的呢？

這裡很神祕，假設 $n = 21$，則 $phi(n) = 12$，根據歐拉公式 $3^{12} \equiv 15 \mod 21$ 違反歐拉定理，但是在 ACM-ICPC 競賽中，有一點明白到，$a^i$ 在 $\mod n$ 下的餘數循環節長度 L，則滿足 $L | phi(n)$，藉由這一點來正確解密，至於到底算不算利用歐拉定理仍是個有趣問題。

Part 5

1
2
3

(1) 2^k q
(3) a^q == 1 mod n
(5) a^(2^j q) == n-1 mod n

Part 6

雖然題目要求得不多，這裡直接拿 RSA 作範例

1. $N = p \times q$

2. 目標計算 $M = C^d \mod N$
   分開計算得到兩個部分，這裡可以利用歐拉定理加快，因此 $d$ 可以先 $\mod \phi(p)$

   $Mp = C^d \mod p$ $Mq = C^d \mod q$

3. 套用中國餘式定理 CRT，簡單的模型如下：

   $a_i = M \mod m_i$ $M = a_1 c_1 + a_2 c_2 + \text{ ... }$ $Mi = m_1 \times m_2 ... \times m_n / m_i$ $c_i = M_i \times (M_i^{-1}) \mod m_i$

4. 因此 RSA 可以預先處理 $c_p = q \times (q^{-1} \mod p)$ 和 $c_q = p \times (p^{-1} \mod q)$，還原的算法則是 $M = Mp \times c_p + Mq \times c_q \mod N$

結論，由於拆分後的 bit length 少一半，乘法速度快 4 倍，快速冪次方快 2 倍 (次方的 bit length 少一半)，但是要算 2 次，最後共計快 4 倍。CPU 的乘法想必不會用快速傅立葉 FFT 來達到乘法速度為 $O(n \log n)$

但是利用 CRT 計算容易受到硬體上攻擊，因為會造成 $p, q$ 在分解過程中獨立出現，當初利用 $N$ 很難被分解的特性來達到資訊安全，但是卻因為加速把 $p, q$ 存放道不同時刻的暫存器中。

其中一種攻擊，計算得到 $M = Mp \times q \times (q^{-1} \mod p) + Mq \times p \times (p^{-1} \mod q) \mod N$ 當擾亂後面的式子 (提供不穩定的計算結果)。得到 $M' = Mp \times q \times (q^{-1} \mod p) + (Mq + \Delta) \times p \times (p^{-1} \mod q) \mod N$

接著 $(M' - M) = (\Delta' \times p) \mod N$，若要求 $p$ 的方法為 $gcd(M' - M, N) = gcd(\Delta' \times p, N) = p$，輾轉相除的概念呼之欲出，原來 $p$ 會被這麼夾出，當得到兩個 $p, q$，RSA 算法就會被破解。