星期二, 12月 27, 2005

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)
網路上都找的到電子檔 (通常學校都有買)。

星期三, 12月 14, 2005

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...

星期一, 11月 28, 2005

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. 先隨機選擇兩個質數 pq,其 bitlength 為 l/2。
    2. 計算 n = pqΦ = (p-1)(q-1)。
    3. 隨機選擇 e 使得 eΦ 互質。
    4. 利用輾轉相除法找到 d,使得 ed ≡ 1 (mod Φ)。
    5. 技巧:medm (mod n)。

星期五, 11月 25, 2005

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

星期四, 11月 24, 2005

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 適合。

星期二, 11月 22, 2005

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。

星期日, 11月 20, 2005

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) 對應起來...