Nov 19 2007

关于学习Linux

今天给我们兴趣小组作了简单的讲座，讲了一下自己学习Linux的经验。

Slides可以在<—这里—>下载。希望新来的同学能比我们做得更好！

把下面这句话和大家共勉：

God helps those who help themselves. （自助者天助！）

Nov 18 2007

整数开平方根

今天被问到如何求一个整数的平方根，不知，速查之，得下面一程序：


unsigned int sqrt(unsigned int n){
    unsigned int a;
    for (a=0;n>=(2a)+1;n-=(2a++)+1);
    return a;
}

厄，仔细一看，它的原理其实也很简单，可以用下图表示：
{0,1,1,1,2,2,2,2,2,3,3,3,3,3,3,3,4,4,4……}

Nov 16 2007

喜欢的几首古诗词

今天去参加AMD的笔试，计算机题就不说了，狠简单，连memcpy的也不在话下（谁让咱看过它的汇编实现呢！！直接翻译成C就可以了。）。

最值得一提的是，上面居然还有一道题说让写出你最喜欢的一首诗词。恩，那我就在这里也写写这个话题吧！

说实话，在高中学古诗词的时候，给我感触最深的基本上都是悼念亲人的那些诗词，文章。大概人在最悲痛的时候的感情才是最深刻的吧！在这里面，最琅琅上口的当推苏轼的《江城子》，这首苏东坡悼念亡妻的诗词字字含泪，每每读起仍是心有感动！

十年生死两茫茫，不思量，自难忘。
千里孤坟，无处话凄凉。
纵使相逢应不识，尘满面，鬓如霜。

夜来幽梦忽还乡，小轩窗，正梳妆。
相顾无言，惟有泪千行。
料得年年肠断处，明月夜，短松冈。
苏东坡不仅有高唱“大江东去”的豪迈气概，更有英雄为美人落泪的柔情。不得不佩服的说。

另一个当推韩愈的《祭十二郎文》，里面的一句“一在天之涯，一在地之角，生而影不与吾形相依，死而魂不与吾梦相接”感人至深！是不可多得的佳作！

当然了，另一篇类似的古文当推袁枚的《祭妹文》，里面的“汝死我葬，我死谁埋？汝倘有灵，可能告我？”也是令人悲痛万分的名句！

Nov 14 2007

快毕业了

发一个老大式的感慨，昨天照毕业照，感觉真的快要毕业了。

看着校园里四处走动的大一的小姑娘小伙子们，仿佛又回到了我们的大一时光。哎，那时我们也是这样年轻！

真的快走了，很快就都各奔东西了。真有点儿舍不得这里的老师，同学，朋友。

耳边又响起张艾嘉《爱的代价》里那句歌词：“走吧，走吧，人总要学着自己长大。”

Nov 12 2007

Static -- A Pain From Past

Ken Thompson曾被问道如果他能重新设计UNIX他将做什么修改，他回答说：“我会在creat命令后加上个e。”

—《Unix痛恨者手册》
如果我们用上面类似的话来问Dennis M. Ritchie，他或许会说，“我会重新造个关键字来替换static。” 呵呵，读者不必当真，这个是玩笑的话。但足以反映static的不足了，它的含义和它的字面意思并不那么吻合，可以这么说，它是C语言中的一个小的瑕疵。

让我们一起来看一看static究竟是如何偏离它的字面意思的。谈static，必须要明白scope，duration，linkage这三个概念。

在C语言中，一个变量或函数有三个属性：scope，duration和linkage。

scope是由它的位置来决定的，scope分为四种：file scope，function scope，block scope和function prototype scope。局部变量的scope就是函数体（function scope）或者局部块（block scope），即使它是static storage。函数和全局变量的scope肯定是整个文件（file scope）。

duration是存活时间，它分两种：automatic和static（这个static不是关键字static）。它是由前面的修饰符和位置共同决定。局部变量默认的storage是auto，如果前面什么都没加。register指定的变量的duration和auto其实一样，也是automatic的。函数的duration都是static的。全局变量也是。局部变量加了static/extern关键字的duration才是static。

linkage最复杂，它要视多种情况而定。linkage分三种：external linkage，internal linkage和no linkage。函数形参的linkage一定是none，局部变量的linkage也都是none的，除非加了extern关键字。对于全局变量/函数，加了static关键字就是internal，否则就可能是external。

这里还有更让人困惑的就是定义和声明，no linkage的是变量其声明就是定义。而external的变量或函数可以有多个声明，但只有一个是定义。internal的变量或函数在本文件内也必须只有一个定义。尽管如此，但有这样一条原则不会改变：对于所有东西来说，带有初始化的一定是定义（如果我们把函数体看作是对函数的”初始化”）。

从这里我们可以看出，static关键字影响了两种属性：duration，linkage。虽然说linkage和duration就是有那么点儿关系，可这个static的作用还是些许模糊。再加之和上面提到的其它一些东西混合，使得正确理解static/extern关键字更加困难。

It’s really a pain from past, for C.

Nov 11 2007

用openssl库实现RSA加密

懒得写了，这里只给出密钥和公钥生成的程序。在此基础上完成加密解密就留给你作为课后作业吧！值得一提的是，用valgrind检查这个程序内存泄漏为0，可能的泄漏也为0，很干净利落。;-)

rsa-use-openssl.c

Nov 10 2007

一个正确使用gets的方法

gets太臭名昭著了，因为它是缓冲区溢出的最大祸根之一。连Linux Programmer’s Manual里都说：“Never use gets().”。没错，你几乎就没有能正确使用它的方法，因为它根本就不关心缓冲区到底够不够，只是一股脑地往里写数据。如果你写了带gets的程序，gcc甚至会提示：“ warning: the `gets’ function is dangerous and should not be used.”。

可是，如果我们仔细想想，究竟有没有正确使用gets的时候？答案是肯定的。那怎么才能正确使用gets呢？其实也很简单，我们只要设置保卫页面（guard pages）来对付溢出就可以了。在Linux上，我们可以这么做：

include

int main(void){
int pagesize;
void p;
char buf;
size_t buflen = 4;

pagesize = getpagesize();
p = mmap(NULL, 2*pagesize, PROT_READ, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
if (p == MAP_FAILED) {
    perror("mmap");
    return -1;
}
if (mprotect(p, pagesize, PROT_READ|PROT_WRITE)){
    perror("mprotect");
    munmap(p, 2*pagesize);
    return -1;
}
buf = (char*)p + pagesize - buflen;

ifdef DEBUG

printf("buf=%p, p=%pn", buf, p);

endif

gets(buf);
puts(buf);
munmap(p, 2*pagesize);
return 0;

}

这时，如果写入的数据超出我们的缓冲区，程序就会收到SIGSEGV而退出。

Nov 9 2007

用Python实现RSA加密算法

这学期开了一门网络安全课，应老师要求，最近要做RSA加密算法。前一篇文章中已经提到，我是用Python来实现的整个程序，而且速度上嘛，比用C实现的慢了很多。我还不清楚到底是寻找素数的算法存在问题，还是Python本身的问题。

关于RSA算法的讲解，最好的莫过于wikipedia上的RSA词条。里面已经非常详细地说明了，这里就不再赘述。整个算法中要用到的数学算法有：Extended Euclidean algorithm，Miller-Rabin primality test。当然，你还需要Modulo operation的知识。

整个算法最关键的是找到合适的P，Q，以及求D。前者尤为关键，它几乎决定了整个程序的运行速度。所以，找到一个搜索大素数的好算法是核心问题。关于求D，我并没有使用Extended Euclidean algorithm，而是用了蛮力求解，没关系，这影响不大，关键还是刚才说的那个。

寻找素数的算法我使用了Miller-Rabin primality test，参考了gmp库源代码中nextprime的实现。但速度上仍然远不如C的实现。详细代码如下：

!/usr/bin/env python

import random
import string
import math
import sys

DEBUG = False

def nextprime(n):
i = n + 1 - n%2
while not probably_prime(i):
i+=2
return i

#i = n + 1 - n%2
#m = 2*n
#while i  0):
    r.append(n % 2)
    n = n / 2
return r

def test(a, n):
“””
Returns:

  - True, if n is complex.
  - False, if n is probably prime.
"""
b = toBinary(n - 1)
d = 1
for i in xrange(len(b) - 1, -1, -1):
    x = d
    d = (d * d) % n
    if d == 1 and x != 1 and x != n - 1:
        return True
    if b[i] == 1:
        d = (d * a) % n
if d != 1:
    return True # Complex
return False # Prime

def MillerRabin(n, s = 15):
“””
Returns:

    - True, if n is probably prime.
    - False, if n is complex.
"""
for j in xrange(1, s + 1):
    a = random.randint(1, n - 1)
    if (test(a, n)):
        return False # n is complex
return True # n is prime

def probably_prime(n):
return MillerRabin(n)

def gcd(m, n):
while n:
m, n = n, m % n
return m

def genkey(bits=100):
BIG_NUM = []
P_INT = 0
Q_INT = 0
global P, Q, X, N, D, E

for i in range(bits):
    BIG_NUM.append(random.choice('0123456789'))

P_INT = int(''.join(BIG_NUM))

for i in range(bits):
    BIG_NUM[i] = random.choice('0123456789')

Q_INT = int(''.join(BIG_NUM))

if DEBUG:
    print "p=%d"%P_INT
    print "q=%d"%Q_INT

P = nextprime(P_INT)
Q = nextprime(Q_INT)

if DEBUG:
    print "next prime to p is %d"%P
    print "next prime to q is %d"%Q

N = P*Q
if DEBUG:
    print "n=%d"%N

X = (P-1)*(Q-1)
if DEBUG:
    print "x=%d"%X

while True:
    if gcd(X, E)==1:
        break
    E+=2

if DEBUG:
    print "e=%d"%E

n = 1
while (n*X+1)%E!=0:
    n+=1
D = (n*X+1)/E

if DEBUG:
    print "d=%d"%D

def rsa_encrypt(msg):
enc = []
for c in msg:
enc.append(pow(ord(c), E, N))
return enc

def rsa_decrypt(cmsg):
dec = []
tmp = []
for ec in cmsg:
tmp.append(pow(ec, D, N))
for c in tmp:
dec.append(“%c”%c)
return dec

X = N = D = P = Q = 0
E= 65537

if name==”main“:
DEBUG = True

argc = len(sys.argv)
if argc==1:
    genkey()
elif argc==2:
    genkey(string.atoi(sys.argv[1]))
else:
    sys.exit(-1)

msg = raw_input()
enc = rsa_encrypt(msg)
if DEBUG:
    print enc
dec = rsa_decrypt(enc)
print ''.join(dec)

Nov 8 2007

Benchmarking big number operations: C vs Python

最近在做RSA加密算法，急需要对大数（很大的数，一般来说是十进制500位以上的数字）进行加法和乘法操作。这就需要对如此大的数操作很快才可以。自然而然，我就想到了Python，它天生就支持大数操作。所以我的RSA也是用Python实现的。

简单地搜了一下网上的一些实现，用C的基本上都采用了gmp库，很牛的一个数字计算的库，接口很方便，而且效率也很乐观。下载一个其中一个还算漂亮的实现，速度超快。相比之下，我的Python程序就慢成马了，难以容忍，优化了一下循环，替换了一个判断素数的算法，效率还是低得出奇。无奈之下，向Herbert求救，在他的提示下，对C和Python的大数操作benchmark了一番。

我用的源代码如下：（声明：C代码编写仓促，很是丑陋，勿模仿！）

include

void timediff(struct timeval a,struct timeval b,struct timeval* result)
{
(result)->tv_sec = (a)->tv_sec - (b)->tv_sec;
(result)->tv_usec = (a)->tv_usec - (b)->tv_usec;

if((result)-&gt;tv_usec tv_sec;
    (result)-&gt;tv_usec += 1000000;
}

}

int main(void)
{
int i;
mpz_t p, q, r;
struct timeval before, after, diff;
char p_str[1024] = {‘1’,};
char q_str[1024] = {‘1’,};

mpz_init(p);
mpz_init(q);
mpz_init(r);
srand(time(NULL));

for(i=1;i&lt;1024;i++)
    p_str[i] = (int)(2.0*rand()/(RAND_MAX+1.0)) + 48;

for(i=1;i&lt;1024;i++)
    q_str[i] = (int)(2.0*rand()/(RAND_MAX+1.0)) + 48;
mpz_set_str(p, p_str, 10);
mpz_set_str(q, q_str, 10);

gettimeofday(&amp;before, NULL);
mpz_add(r, p, q);
gettimeofday(&amp;after, NULL);
timediff(&amp;after, &amp;before, &amp;diff);
printf(&quot;add needs time:&quot;);
printf(&quot;n%-15s : %ld&quot;,&quot;Seconds&quot;, diff.tv_sec);
printf(&quot;n%-15s : %ld&quot;,&quot;Microseconds&quot;, diff.tv_usec);
puts(&quot;&quot;);

gettimeofday(&amp;before, NULL);
mpz_mul(r, p ,q);
gettimeofday(&amp;after, NULL);
timediff(&amp;after, &amp;before, &amp;diff);
printf(&quot;multiply needs time:&quot;);
printf(&quot;n%-15s : %ld&quot;,&quot;Seconds&quot;, diff.tv_sec);
printf(&quot;n%-15s : %ld&quot;,&quot;Microseconds&quot;, diff.tv_usec);
puts(&quot;&quot;);

mpz_clear(r);
mpz_clear(q);
mpz_clear(p);
return 0;

}

!/usr/bin/env python

import time
import string
import random

p = q = r = 0
BIG_NUM = []

for i in range(1024):
BIG_NUM.append(random.choice(‘0123456789’))

p = int(‘’.join(BIG_NUM))

for i in range(1024):
BIG_NUM[i] = random.choice(‘0123456789’)

q = int(‘’.join(BIG_NUM))

before = time.time()
r = p+q
after = time.time()

print r

print “Add needs time: %f us”%((after - before)1000.01000.0)

before = time.time()
r = p*q
after = time.time()

print r

print “Multiply needs time: %f us”%((after - before)1000.01000.0)

实验结果如下：
(C version, compiled with gcc -O9)
$ ./bench
add needs time:
Seconds : 0
Microseconds : 5
multiply needs time:
Seconds : 0
Microseconds : 11

(Python version)
$ ./bench.py
Add needs time: 15.020370 us
Multiply needs time: 207.901001 us

-_-b 刚才搞错进制了。。。 1 second=1000*1000 microseconds 这下对了。Python确实比C慢。抑或是真正的问题出在这里？而不在我的算法？

顺便也在这里问一下：有没有什么好的寻找大素数的算法？？
（整个RSA实现会在以后的文章中贴出。）

Nov 6 2007

两个。。。

今天是两个小姑娘的生日，一个是失散多年的郑小鬼，另一个就是王小敏同学了。恩，啥都不说了，总之，祝两位姑娘生日快乐！越长越帅！^_^…

这两位小鬼的生日在同一天也充分证明了数学上的那个生日悖论～！;-)

=============================

看到两个经典的语句，记录一下：

Software is like sex: It’s better when it’s free.

（很NB的比喻～！）

“Never let school get in the way of learning.”
— Mark Twain

（牛人之言不我欺～！谁要再告诉你必须得上大学，你就用这句话砸死他！）

=============================

澄清一下关于偶的两个流言：

1. 听说你用的是自己写的操作系统。

首先，拜托你，先去网上调查写一个可以日常使用的操作系统需要多少人力年。其次，我用的是Linux，它是Linus Torvalds及数千名内核黑客写的。

2. 听说你去了Google。

本人至今仍是无业游民。。。去向未定。。。

A Geek's Page

Archives

关于学习Linux

整数开平方根

喜欢的几首古诗词

快毕业了

Static -- A Pain From Past

用openssl库实现RSA加密

一个正确使用gets的方法

include

include

include

ifdef DEBUG

endif

用Python实现RSA加密算法

!/usr/bin/env python

Benchmarking big number operations: C vs Python

include

include

include

include

include

!/usr/bin/env python

print r

print r

两个。。。