遲早要還的債

代數，念密碼學遲早要還的債 :p

不過，當初念了半天不懂的 Normal Subgroup 現在再回頭看就馬上能夠知道他想要做什麼。而看到 Finite Abelian Group 的章節 (Elliptic Curve 剛好就是 Finite Abelian Group XD) 更是抱著書痛哭 XD

希望往後面看都能覺得很開心 XD

arXiv

前陣子突然想到另外一個蠻重要的 paper archive：arXiv.org，其實這裡也放了不少論文。台灣也有 mirror site，tw.arXiv.org，架設在國科會。

Elliptic Curve Cryptosystems

剛睡醒就在 Digg 看到這篇 The Case for Elliptic Curve Cryptography (瞬間清醒不少...)，講 Elliptic Curve Cryptography 被納入 Suite B cryptography recommendations。

這幾年研究的人會比較多，應該是因為 2001 年時 Stanford 的 Boneh 與 Franklin 使用 Elliptic Curve Cryptography 上的 Weil Pairing，解決 Shamir 在 1984 提出來的 ID-based Cryptography 架構。

ePrint

上個禮拜五跟一位剛畢業學長一起 meeting 時，問學長要盯哪些地方，才發現搞 Crypto 的人在有了一些成果後，幾乎都是先投這邊：Cryptology ePrint Archive。

像是前年王小雲女士，先丟出震撼整個密碼學界的 Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD 這篇論文，直接宣布他找到了兩個值的 MD5 是一樣的，也是先把初步的結果丟上這邊，然後再正式發表出來。

所以這邊有蠻多有趣的東西可以看，有 RSS 可以訂。

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;
}