Cryptosystem Papers

幾篇 Public Key Cryptosystems 與 Identity-based Cryptosystems 開頭的 Paper：

1. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (Rivest，Shamir，Adleman，1978)
2. Identity-based cryptosystems and signature schemes (Shamir，1985)
3. Use of Elliptic Curves in Cryptography (Miller，1986)
   
4. Elliptic curve cryptosystems (Koblitz，1987)
5. Identity-Based Encryption from the Weil Pairing (Boneh，Franklin，2001)

網路上都找的到電子檔 (通常學校都有買)。

Elliptic Curve Cryptosystems

前陣子看 Neal Koblitz 的 Elliptic Curve Public Key Cryptosystems，看了老半天看不懂，後來跑去找他在 1987 年發的論文 (Elliptic Curve Cryptosystems: Mathematics of Computation, Volume 48, Number 177, January 1987, Page 203-209) 果然清楚多了，而且也把每個細節的來龍去脈講得很清楚。

不過這篇論文後半部都在搞機率統計的東西，gosh...

gethost* on FreeBSD

前陣子在我個人板上有寫，FreeBSD 6.0 的 gethost*() 已經 Thread-safe 了：

1. gethostbyname manpage on FreeBSD 6.0
2. gethostbyname manpage on FreeBSD 5.4

在最下面 BUGS 的地方寫的還蠻清楚的，所以我就寫了個小程式測試，在不同的 Thread 裡面不斷的呼叫 gethostbyname()，看傳回來的位置是什麼：

#include <netdb.h>
#include <pthread.h>
#include <stdio.h>

#define THREAD_NUM      (3)

void *thread_start()
{
   const pthread_t tid = pthread_self();

   int i;
   for (i = 0; i < 5; i++) {
       struct hostent *p = gethostbyname("ccca.nctu.edu.tw");
       printf("tid = %d, gethostbyname() = %p\n", tid, p);
       sleep(1);
   }

   return;
}

int main(void)
{
   pthread_t tid[THREAD_NUM];

   int i;
   for (i = 0; i < THREAD_NUM; i++)
       pthread_create(tid + i, NULL, thread_start, NULL);

   sleep(10);
}

Guide to Elliptic Curve Cryptography - 2005/11/28

Public-key cryptography 常用的方法：

1. Integer Factorization Problem (ex：RSA)
   
2. Discrete Logarithm Problem (ex：ElGamal、DSA)
   
3. Elliptic Curve Discrete Logarithm Problem
   

RSA：(在這本書上寫 "It has been proven that the problem of determining the private key d from the public key (n,e) is computatuinally equivalent to the problem of determining the factors p and q of n; the latter is the integer factorization problem (IFP)"，但並沒有引用文獻，需要再去查)

• Key 的產生：輸入 Security parameter l，輸出 public key (n,e) 與 private key d。
1. 先隨機選擇兩個質數 p 與 q，其 bitlength 為 l/2。
2. 計算 n = pq 與 Φ = (p-1)(q-1)。
3. 隨機選擇 e 使得 e 與 Φ 互質。
4. 利用輾轉相除法找到 d，使得 ed ≡ 1 (mod Φ)。
5. 技巧：m^ed ≡ m (mod n)。

Network Programming Using Libevent - (III)

這次要談的跟 Network Programming 沒有直接的關係。

在寫 Nonblocking Network Program 通常要處理 Buffering 的問題，但並不好寫，主要是因為 read() 或 recv() 不保證可以一次讀到一行的份量進來。

在 libevent 裡面提供相當不錯的 Buffer Library 可以用，完整的說明在 man event 的時候可以看到，最常用的應該就是以 evbuffer_add()、evbuffer_readline() 這兩個 Function，其他的知道存在就可以了，需要的時候再去看詳細的用法。

下面直接提供 libevent-buff.c 當作範例，編譯後看執行結果，再回頭來看 source code 應該就有感覺了：

#include <sys/time.h>
#include <event.h>
#include <stdio.h>

void printbuf(struct evbuffer *evbuf)
{
    for (;;) {
        char *buf = evbuffer_readline(evbuf);
        printf("* buf = %p, the string = \"\e[1;33m%s\e[m\"\n", buf, buf);
        if (buf == NULL)
            break;
        free(buf);
    }
}

int main(void)
{
    struct evbuffer *evbuf;

    evbuf = evbuffer_new();
    if (evbuf == NULL) {
        fprintf(stderr, "%s(): evbuffer_new() failed.\n", __func__);
        exit(1);
    }

    /* Add "gslin" into buffer. */
    u_char *buf1 = "gslin";
    printf("* Add \"\e[1;33m%s\e[m\".\n", buf1);
    evbuffer_add(evbuf, buf1, strlen(buf1));
    printbuf(evbuf);

    u_char *buf2 = " is reading.\nAnd he is at home.\nLast.";
    printf("* Add \"\e[1;33m%s\e[m\".\n", buf2);
    evbuffer_add(evbuf, buf2, strlen(buf2));
    printbuf(evbuf);

    evbuffer_free(evbuf);
}

Network Programming Using Libevent - (II)

接下來要談的是 libevent 要如何使用，不過為了方便起見，我們直接寫一個很簡單的 Time Server 來當作例子：當你連上去以後 Server 端直接提供時間，然後結束連線。

在這些例子裡面我以 FreeBSD 6.0 當作測試的平台，另外使用 libevent 1.1a 當作 Event-based Library，Compile 時請使用 gcc -I/usr/local/include -o timeserver timeserver.c -L/usr/local/lib -levent (如果 libevent 的 Header 與 Library 放在 /usr/include 與 /usr/lib 下的話可以省略這兩個參數)。

原始程式碼在文章的最後頭。

event_init() 表示初始化 libevent 所使用到的變數。

event_set(&ev, s, EV_READ | EV_PERSIST, connection_accept, &ev) 把 s 這個 File Description 放入 ev (第一個參數與第二個參數)，並且告知當事件 (第三個參數的 EV_READ) 發生時要呼叫 connection_accept() (第四個參數)，呼叫時要把 ev 當作參數丟進去 (第五個參數)。

其中的 EV_PERSIST 表示當呼叫進去的時候不要把這個 event 拿掉 (繼續保留在 Event Queue 裡面)，這點可以跟 connection_accept() 內在註冊 connection_time() 的程式碼做比較。

而 event_add(&ev, NULL) 就是把 ev 註冊到 event queue 裡面，第二個參數指定的是 Timeout 時間，設定成 NULL 表示忽略這項設定。

最後的 event_dispatch() 表示進入 event loop，當 Queue 裡面的任何一個 File Description 發生事件的時候就會進入 callback function 執行。

這隻程式非常粗糙，有很多地方沒有注意到 Blocking 的問題，這點我們就先不管了。當跑起來以後你就可以連到 port 7000，就會出現類似下面的結果：gslin@netnews [~] [3:14/W5] t 0 7000


gslin@netnews [~/work/C] [3:15/W3] t 0 7000
Trying 0.0.0.0...
Connected to 0.
Escape character is '^]'.
Fri Nov 25 03:15:10 2005
Connection closed by foreign host.


最基本的使用就是這樣了，你可以 man event 看到完整的說明。

這是 timeserver.c：

#include <netinet/in.h>
#include <sys/socket.h>
#include <sys/types.h>
#include <event.h>
#include <stdio.h>
#include <time.h>

void connection_time(int fd, short event, struct event *arg)
{
    char buf[32];
    struct tm t;
    time_t now;

    time(&now);
    localtime_r(&now, &t);
    asctime_r(&t, buf);

    write(fd, buf, strlen(buf));
    shutdown(fd, SHUT_RDWR);

    free(arg);
}

void connection_accept(int fd, short event, void *arg)
{
    /* for debugging */
    fprintf(stderr, "%s(): fd = %d, event = %d.\n", __func__, fd, event);

    /* Accept a new connection. */
    struct sockaddr_in s_in;
    socklen_t len = sizeof(s_in);
    int ns = accept(fd, (struct sockaddr *) &s_in, &len);
    if (ns < 0) {
        perror("accept");
        return;
    }

    /* Install time server. */
    struct event *ev = malloc(sizeof(struct event));
    event_set(ev, ns, EV_WRITE, (void *) connection_time, ev);
    event_add(ev, NULL);
}

int main(void)
{
    /* Request socket. */
    int s = socket(PF_INET, SOCK_STREAM, 0);
    if (s < 0) {
        perror("socket");
        exit(1);
    }

    /* bind() */
    struct sockaddr_in s_in;
    bzero(&s_in, sizeof(s_in));
    s_in.sin_family = AF_INET;
    s_in.sin_port = htons(7000);
    s_in.sin_addr.s_addr = INADDR_ANY;
    if (bind(s, (struct sockaddr *) &s_in, sizeof(s_in)) < 0) {
        perror("bind");
        exit(1);
    }

    /* listen() */
    if (listen(s, 5) < 0) {
        perror("listen");
        exit(1);
    }

    /* Initial libevent. */
    event_init();

    /* Create event. */
    struct event ev;
    event_set(&ev, s, EV_READ | EV_PERSIST, connection_accept, &ev);

    /* Add event. */
    event_add(&ev, NULL);

    event_dispatch();

    return 0;
}

Network Programming Using Libevent - (I)

在課堂上學過 Unix Network Programming 後，我們知道在處理多 User 時會有幾種方法解決：

1. 一個新的 Connection 進來，用 fork() 產生一個 Process 處理。
2. 一個新的 Connection 進來，用 pthread_create() 產生一個 Thread 處理。
3. 一個新的 Connection 進來，丟入 Event-based Array，由 Main Process 以 Nonblocking 的方式處理所有的 I/O。
   

這三種方法當然也都有各自的缺點：

1. 用 fork() 的問題在於每一個 Connection 進來時的成本太高。
2. 用 Multi-thread 的問題在於 Thread-safe 與 Deadlock 問題難以解決，另外有 Memory-leak 的問題要處理。
3. 用 Event-based 的方式在於實做上不好寫，尤其是要注意到事件產生時必須 Nonblocking，於是會需要實做 Buffering 的問題，而 Multi-thread 所會遇到的 Memory-leak 問題在這邊會更嚴重。而在多 CPU 的系統上沒有辦法使用到所有的 CPU resource。
   

當然，針對前面兩項有各自的解法：

1. 以 Poll 的方式解決：當一個 Process 處理完一個 Connection 後，不直接死掉，而繼續回到 accept() 的狀態繼續處理，但這樣會遇到 Memory-leak 的問題，於是採用這種方式的人通常會再加上「處理過 N 個 Connection 後死掉，由 Parent Process 再 fork() 一隻新的」。最有名的例子是 Apache 1.3。
2. Thread-safe 的問題可以透過自己撰寫，或是尋找其他 Thread-safe Library 直接使用。Memory-leak 的問題可以試著透過 Garbage Collection Library 分析出來。Apache 2.0 的 Thread MPM 就是使用這個模式。
   

然而，目前高效率的 Server 都偏好採用 Event-based，一方面是沒有 Create Process/Thread 所造成的 Overhead，另外一方面是不需要透過 Shared Memory 或是 Mutex 在不同的 Process/Thread 之間交換資料。

然而，Event-based 在實做上的幾個複雜的地方在於：

1. select() 與 poll() 的效率過慢，造成每次要判斷「有哪些 Event 發生」這件事情的成本很高，這在 BSD 支援 kqueue()、Linux 支援 epoll()、Solaris 支援 /dev/poll 後就解決了，但這兩組 Function 都不是 Standard，於是在不同的平台上就必須再改一次。
   
2. 因為 Nonblocking，所以在 write() 或是 send() 時滿了需要自己 Buffering。
3. 因為 Nonblocking，所以不能使用 fgets() 或是其他類似的 function，於是需要自己刻一個 Nonblocking 的 fgets()。但是使用者所丟過來的資料又不能保證在一次 read() 或 recv() 就有一行，於是要自己做 Buffering。

實際上這三件事情在 libevent 都有 Library 處理掉了。

另外值得注意的一點在於 libevent 使用的是 3-clause BSD license 而非 GPL，所以在不想公開程式碼 (像是商業用途) 的情況下會比其他的 Library 適合。

Algebra Definition

幾個重要的定義：

1. SemiGroup (結合律)
2. Monoid (多了單位元素)
   
3. Group (多了封閉性、反元素)
4. Abelian Group (Communtative，即交換律)
   
5. Ring (加法成一個 Abelian Group，乘法只保證封閉性、結合律，另外有分配律)
   
6. Integral Domain (兩元素相乘為零，則必有一元素為零) 及 Division Ring (保證反元素的存在)
   
7. Field (== Commutative Division Ring)
   

在接觸到的 Cryptography 常常用到 Finite Field，又稱 Galois Field，所以常寫成 GF(n) 表示元素個數有 n 個的 Finite Field。

Basic Algebra - P.M. Cohn

把 gslin.blogspot.com 給清掉，這邊只放跟課程有關的東西，第一篇就講最近在念的 Algebra (代數) 吧。

會重新去念 Algebra 主要是因為研究 Elliptic Curves 的關係，當初代數用的那本 Abstract Algebra (I.N. Herstein) 那本雖然有留著，但是 peace 跟我說那本講的太少了。即使如此，我當初在學的時候就一直沒有弄懂 Quotient 與 Sylow Theorem。(後者根本已經忘記內容是什麼了)

不管怎樣，現在要用到的是 Finite field (Galois field)，在 Herstein 的 Abstract Algebra 裡面講的太少了，所以我就在網路上找了一些文章，看到台大數學系有專門對某些學科開書單：代數參考書目及評論。

其中 Herstein 另外一本 Topics on Algebra 雖然我有買，但是我放在台北家裡了，但是有陣子沒回去了，就決定在新竹買另外一本，等有空回家的時候再把它帶下來。

在評論裡面其中有一本 Basic Algebra (Nathan Jacobson) 被標為「經典佳作」，於是我就跑到交大的愛因斯坦書局去翻，結果翻到另外一本 Basic Algebra (P.M. Cohn)。當時沒有注意到作者不一樣，翻了翻書裡面的內容覺得也還不錯，就買下來了。結果後來才發現不是同一本 :)

P.M. Cohn 這本書在網路上的資料不多，查了 Amazon 也沒看到 Review，不過在台大數學系曾經用過這本當作 88 學年代數通論 (下) 的 Textbook，所以應該也還可以用吧？

這本書感覺的出來走的非常快，光是第一章的東西之多就令人咋舌。

我記得在六年前修集合論的時候用了不少時間給出 Axiom of Choice、Zorn's Lemma、Well Ordered Principle 三者的等價證明，這本書只用了一個 Section 1.2 就寫完了。當然也有可能是當時大一老師為了讓大家熟悉而放慢速度就是了...

以前面幾章來說，拿來自修的話應該還是不錯的書。

2005/11/20 Update：

把第一章看過去以後覺得不太習慣，有些地方沒講清楚。像是這個定理：

If function f: A -> B is injection and g: B -> A is injection too, then there is a bijection function h: A -> B.

在證明的過程中他把一般常用的 f(a) 寫成 af，於是我就在那邊看半天才想起來這個定理證明的過程，才把這個 af 符號跟 f(a) 對應起來...