Skip to main content

The Not-So-Easy C

Whenever I get an embedded software engineer's resume, one thing I can guarantee is there will be definitely a line says:

Excellent in C/C++ (or something similar)

Another one I am sure is someone will challenge the C++ skills of the candidate: so let's talk about templates...

I understand why the graduates think they are qualified for C/C++ programming, and I fully agree C++ is way more than inheritance and OOP.

What I don't understand is why people believe C is simple and, relatively, easy.

I've heard a humble interviewee said:

I am not a C++ expert, but I know C very well.

Really?

Let's test ourselves with some quick questions:

  • Based on What C standard did you write your last C program? You might argue that I am showing off by asking this pedantic question. I'm not. If you are not using C99 or later, you will not be able to write inline functions because that is not supported. You will have to put all variable declarations at the top of the start of a compound statement or the compiler will complain about the "declaration may not appear after executable statement in block" error; You cannot define a variable-length array, and you will have to define your own boolean data type - these are not provided in the pre-C99 standards. There are more. This is why you need to understand what standard you are using before touching the keyboard. With the knowledge, you will solve the compilation errors easily by adding an compile option, -std=c99.
  • So I assume you use C99, which I believe is the most popular standard nowadays. What does the C keyword, _restrict_, mean? No it is not _register_, I mean _restrict_. If you have no idea or are not sure about your answer, check it out here. Again one would question the point of this question: it is too esoteric, even more esoteric than the word "esoteric"! Calm down. Think about the applications of C today. There are good chances that you write C code for some embedded systems, which are very sensitive to efficiency and the footprint of the executable image. Proper use of the _restrict _keyword could help the compiler to produce significantly faster executables. If you seldom consider ways to optimize your code, you might have been lucky (or unfortunate, depending on how you look at it) to work on something called embedded but doesn't care too much about memory and efficiency, or, you might not know C very well, as an embedded software engineer.
  • How would you define an integer? A question, instead of an answer is expected. One should ask: "How many bits of the integer we are talking about?" before writing on the whiteboard. And a statement "U32 x;" is better than "int x;", while "uint32_t x;" is even better because that is C standard, defined in stdint.h. "int" is evil in the embedded system industry. The type system of C has been long disputed and it is the embedded software engineers' responsibility to make it right. It is a must, but not virtue, to write clear, safe and portable code in C.

So, do you still think C is easy and you know it very well?

It would be great if you could also share your piece of not-so-easy C in the comment. My gratitude.

外婆

对外婆的记忆大多是在放暑假的时候。

因为爸妈都要上班又不放心我一个小孩在家,妈妈每天上班的时候就会用自行车把我载到驼背的外婆家,下班的时候再接回去。虽然已经是20多年前的事情了,其中的一些画面想起来的时候还清晰如同就在眼前。

外婆家有一前一后两个小的房间,中间隔着一个开放的空地。外婆没有厕所,用的是痰盂。每次我都是坐在痰盂上大大,完事后由外婆弓着腰带着我去倒。外婆通常把痰盂放在空地上,痰盂的旁边就是外婆的铁笼,有时候养鸡,有时候是兔子。我大大的时候通常会偷偷地捡起身边的菜叶子喂笼子里的兔子。看着它们很高兴地吃我喂的叶子,大大的时光很快就过去了。

外婆的邻居家有一个比我大一岁的小男孩。我到外婆家写完寒假或暑假作业后就去找他玩。我们用圆珠笔芯做小水枪,还用健力宝瓶子做大水枪。玩得不亦乐乎。到了中午,外婆就会弓着腰从屋子里走出来,然后用力挺直身子,喊我开饭。又再弓着身子和我一起进房间吃午饭。午饭不记得有什么了,不过我很喜欢外婆专门用来给我盛饭的瓷碗,上面印着火车从远处驶来的生动画面,我记得火车头还冒着浓烟。我们吃饭的旁边是外婆的小柜子,里面有一个小机械闹钟,有一只母鸡带着几只小鸡在地上啄米,母鸡的头会随着秒针的移动而不停在地上啄米。有火车碗和不停啄米的母鸡闹钟,我很喜欢在外婆家吃饭。

外婆把前面的小房间用布帘隔成两个更小的房间,一个是客厅加饭厅,另外一个就是卧室。吃完饭外婆就会喊我睡午觉。我看见隔壁的男孩写作业的时候用的是一只很高级的铅笔,可以一直写不用按按钮也可以出笔芯的那种。中午睡觉的时候就会和外婆说。我记得外婆床上很多被单,不厚,但是都很软很暖。可惜的是已经不记得是怎么睡着又是怎样起来的了。

到了下午晚些时候妈妈就会接我回家。有一次回家的时候,妈妈送给我一只和隔壁男孩一样的高级铅笔,因为外婆告诉她我想要。外婆说是学习用的,要买。可惜那只笔已经不知去向,不然我一定还是很喜欢用它。

之后就很少去外婆家了。每年春节去拜年的时候,外婆总是会从床垫底下拿出红包来给我,然后叮嘱我要好好学习。外婆的红包是用一张大的红纸折的,拿在手上手指会被染红。

后来每年的春节当我在养老院看到外婆时,她大多数时候已经听不清我的话,认不出我的人了。外婆依旧弓着腰,只是必须坐着或者躺着。她已经站不起来走不动了。

前年除了春节,中秋的时候还回去看过一次外婆,那一次她认出了我,也听到了我说的大多数话。我想夏天或者秋天她的精神确实要好一些。

去年回家时间很短,竟然也就没有去看外婆。

前天是母亲节,我和妈妈通了电话。她说外婆身体越来越差了。

昨天下午,我收到妈妈的短信:外婆去世了,当天晚上下葬。下班回到家,我终于还是没能忍住,哭了出来。

我想你,外婆。愿您安息。

Twitter Enabled Printer

Printers are old ugly monsters from the last century. Twitter is about 6 years old and might shop for school pretty soon.

How would you put the two together? In this post twitter is used to access the printer and to request information and services.

The idea is simple. Nowadays printers can easily connected to network. By implementing a twitter connector  in the printer, the machine will understand how to communicate with the twitter server and then becomes 'twitter enabled'. The diagram below depicts the idea.

/galleries/twitter-enabled-printer-1.png

The twitter connector takes care of talking to the twitter server and translate the Tweets/DMs into printer languages.

With the printer's "twittability" enabled, one can register a twitter id as a proxy and connect the id to the printer. Once connected, the proxy will receive and send Tweets/DMs on behalf of the printer. In this way the Twitter enabled printers offer user an easier yet more powerful option to access and control:

  • No extra software installation is required. Any twitter client on any platform, or the twitter webpage, will work.
  • Status report is accessible in tweets even when the printer is offline.
  • Printers post and "read" tweets and direct messages, which can be further customized, acting like human.

Would it be more interesting if you can talk to your printers like this?

/galleries/twitter-enabled-printer-2.jpg

A demo has been built to show how to talk to a twitter enabled printer:

11年记

面对即将来临的而立之年,过去的2011很是紧凑忙碌。日后回忆自己的29岁,想必一定要有意思得多:总结写到现在,唯独这一年,没有遗憾。 这一年里,发生了这么些事:

  • 老婆送了一把剃须刀,我开始享受刮胡子的感觉。
  • 真正读了一些书。Rework, Rules of Simplicity和Being Geek都很有必要再读几次。Introduction to Algorithm依然在读,这根铁杵还得细磨下去。
  • 完成了自己的第一个专利申请。没有太多的物质收入,但能在人生游戏中玩到这么一个关卡,也算是很有意思。
  • 工作到现在,还是没能专精一项技术。这和大部分时间在做救火员有关,同时也要归咎于自己的毅力不足,喜欢东看看西碰碰。明年的目标是加深对内存问题和管理的理解,还有学习基本的网络知识。
  • 学着平衡工作、生活和爱好。在公司就全心投入好好干活,到了家就多陪陪老婆主动帮帮忙,两头打点好了再看看书做些自己喜欢的事情。平衡很重要。
  • 实现了回家两次的愿望。亲人的老去已经是事实,与其在远方不胜唏嘘还不如多陪他们吃顿饭多看会电视。
  • 胜利完成婚姻一五计划。个中酸甜苦辣自知。庆祝过后,抬头看见的是更长更远更有挑战的相伴相随。
  • 开始尽可能每天早上起床后跑步或是一些简单的锻炼。计划是坚持十年,看看不惑的时候会有什么收成。
  • 朋友波波和大米的公司渐入佳境,迅雷哥哥也离开网易创业去了,他们为自己的梦想迈开步子去做也做到了,钦佩他们的勇气,替他们高兴;胡子和志彦分别都成了家,祝福他们一直幸福下去;还有更多的朋友也都分别结婚生子跳槽创业移民毕业。过去的一年井喷出来的是成熟与希望。
  • 一位父亲的挚友因胰腺癌辞世。他一生乐观,健康生活,爱运动,学不怠,是我永远的榜样。他的提早离席,给我留下的不仅仅是难过。
  • 公司再度经历重组动荡,2008年熟悉的场景和对话再次浮现。然而这次感受更多的是,真正的强者总能逆流而上。恶劣的生态往往更能让适应者生存下来,笑到最后。所以,不要怨天尤人,应该做的是提高自己适应环境。
  • 认识了新的世界观。认识到人的渺小,感受到意志的伟大。有点像坐着小船开进了室外桃源:哇,原来世界如此,原来生命如此。

尽力做了该做的事,任性做了想做的事。 久违了充实的感觉,很好。

Keep Your Fingers Away from "ESC"

When editing in Vim the keys that I hate most are "ESC" (Esc, Shift and CapsLock). They interrupt my thoughts when I have to find the keys far, far away from the comfort area of my fingers, not to mention the mistypes like pressing tab when I mean CapsLock.

There are many ways to get rid of these keys, below is my recipe. No guarantee you can throw the "ESC" keys away, but I would say your fingers will stay away from "ESC" for 80% of your typing experience.

In your vim configuration file, .vimrc if you are in Linux, set the mappings as:

"map space to @ (shift-2) for easier use the record buffer map <space> @

"jumping among windows, with the arrow keys nnoremap <silent> <Down> <C-W>j nnoremap <silent> <Up> <C-W>k nnoremap <silent> <Left> <C-W>h nnoremap <silent> <Right> <C-W>l

" not to even think about the <ESC> key imap jj <ESC>

"delete a word in insert mode imap jjd <ESC>diwi

"capitalize the first character of the current word, in Insert mode imap jjc <ESC>b~A

" Swap ; and :, save the Shift key. nnoremap ; : nnoremap : ;

"page down map ,j <C-d> "page up map ,k <C-u>

木婚•五年

一、二、三、四、五。相识七年,婚后五年。 这一年我们经历了最激烈的争吵,这一年我们感受到更暖人的温情。 在各种痒和痛中,我们继续探索婚姻的奥秘:

磨合 我总感叹我们是两个极端,各自有截然不同的喜好习惯乃至追求。 直到有一天一个朋友说:iron sharpens iron. 我才知道你我的结合是上帝费尽心思的安排: 在我脆弱的时候你坚强,在我冲动的时候你冷静,在我想法幼稚且执意某件事情的时候,你提醒我要成熟起来要考虑周全;在你哭泣的时候我给你依靠,在你构思的时候我为你执行, 在你依然不知如何改掉某个习惯的时候,我告诉你慢慢来我会等你一世一生。 能照顾体贴自己的人固然难得,于此同时还可以直击自己短板,反射自己丑态且帮助自己成长的伴侣也许就只有一个。 能做到这样的我,我骄傲;能找到这样的你,我感激。

亲密 不知道5年是不是某种意义上的轮回,我时有感觉新婚这盘久违的菜加了点什么佐料重新被盛了上来。许多刚结婚时的新鲜感转了一圈又再浮现。只是这次添了些默契,多了点依赖。只要两个人都在,家里就时刻被填满。 这一年,我们的亲吻和拥抱超过5年总和的一半。

厨房 不知道这是不是天下皆知的秘密:做饭时的香味远远的就在说这里才是家;备菜的间隙时不时还可以聊聊今天的八卦。就算是争吵、冷战,也会因为到了饭点,两人就不自觉地开始厨房的协作:砧板拿出来炉灶点起来的那一刻,冰雪也开始融化。

加班 换了新工作后加班的频率高了很多。老婆虽有提意见但依然全力支持。 常见的场景是:晚上回到家,第二天的饭菜已经备好,我洗澡后和老婆聊会天,上床看书睡觉。十分简单非常平淡,而要这样持续一年,两年,就变成一件不那么容易的事情。尤其妻子这样需要陪伴的性格,更是需要极大的理解和极大的爱才能做到。 同时,籍着天赐的智慧,我也知道了要在没有工作的时候多多陪她,或看电视或打扫房间,或参考购物或一同旅游。既填充了爱的水池,又放松了自己。

婚姻的智慧我们或许只摸到了冰山的一角,但能有不断的收获我便感激且欣慰。

纪念日那天我们重游五年前登记的城市。熟悉的落叶,亲切的方言,路过的每一条街道,入口的每一件小吃都让人感到温馨和惬意。饭后散步时的闲聊,仿佛就像时空已经错乱,一会五年后,一会五年前。

酒越酿越醇,爱愈提愈香。将来一路走下去,我愿意,和你。

An Improved Version of the Counting Sort Implementation

The "Introduction to Algorithm" provides an pseudo-implementation of counting sort.

COUNTING-SORT(A, B, k)

1  for i  ← 0 to k

2      do C[i] ← 0

3  for j ← 1 to length[A]

4      do  C[A[j]] ← C[A[j]] + 1

5  ► C[i] now contains the number of elements equal to i

6  for i  ← 1 to k

7      do C[i] ← C[i] + C[i -1]

8  ► C[i] now contains the number of elements less than or equal to i

9  for j  ← length[A] downto 1

10    do B[C[A[j]]] ← A[j]

11          C[A[j]] ← C[A[j]] - 1

It works well, but still there is room for improvement. Below is another version that makes counting sort a bit more faster:

COUNTING-SORT-2(A, B, k)

1  for i  ← 0 to k

2      do C[i] ← 0

3  for j ← 1 to length[A]

4      do  C[A[j]] ← C[A[j]] + 1

5  ► C[i] now contains the number of elements equal to i

6  n = 0

7 for i  ← 0 to k

8      for j ← 1 to C[i]

9            do B[n] ← i

10                n ← n + 1

Start from line 6 is where the two implementations differentiate. when no optimization is taken into account.

In COUNTING-SORT line 6 to line 11 takes:

k +  len(A) * 2 assignments, and k + len(A) pluses

In COUNTING-SORT-2 line 6 to line 10 takes:

len(A) * 2 assignments, and len(A) pluses

The two implementations both cost

$$Omega(len(A))$$,

but in the latter the constant k is eliminated.

At the end is a short python test that gives a taste of difference in real performance on my 2.8GHz Win7 laptop:

import time
def time_elapsed(func):
    def wrapper(*arg):
        t1 = time.time()
        res = func(*arg)
        t2 = time.time()
        print("time elapsed in %s: %0.3f ms" % (func.__name__, (t2 - t1) * 1000.0))
        return res
    return wrapper

@time_elapsed
def counting_sort(a, k):
    c = [0] * (k + 1)
    for j in a:
        c[j] = c[j] + 1
    for i in range(1, k + 1):
        c[i] = c[i] + c[i - 1]
    b = a
    for j in a[::-1]:
    b[c[j] - 1] = j
    c[j] = c[j] - 1
    return b

@time_elapsed
def counting_sort_2(a, k):
    c = [0] * (k + 1)
    for j in a:
        c[j] = c[j] + 1
    b = []
    for i in range(k + 1):
        for j in range(c[i]):
            b.append(i)
    return b

Sorting with counting_sort_2:

data = [3,7,2,1,6,4,5,0] * 1000 counting_sort_2(data, 8 )

time elapsed in counting_sort_2: 22.000 ms

While doing the same sort with counting_sort:

data = [3,7,2,1,6,4,5,0] * 1000 counting_sort(data, 8 )

time elapsed in counting_sort: 36.000 ms

程序员老二

老二在他前家很算挺大的公司写了10年程序,最后离开,到了一个学院教书,讲嵌入式设计。

暑假的时候他被临时聘回公司做一个项目,看见以前自己的代码被糟蹋得不成样子。

“很不爽。”我看见了他的脸在说话。

“还是那个样子,老板会对你说出‘别设计了,写代码吧’这样的话。因为制定计划的时候就没有打算要高质量的代码,他们只要最快速度写出能用的东西。”

“然后就开始抓人修bug,1000, 950……巴不得每个小时更新剩下的bug数目。想方设法威逼利诱底下的人加班加点解决问题,然后画一条漂亮的弧线邀功领赏。”

“工程师前期花时间想办法设计好?那你的工作报告就会很难看。老板会接受你的解释,但是考评和奖金会告诉你他的真实想法。你如果想做个好的程序员,就以最快的速度写出能工作的代码,等着测试人员报出一堆低级错误,然后轻松的快速解决掉他们,这样一来无论工作量还是效率你都优秀得无可挑剔。管别人怎么说去,潜在的问题也不是问题,过个一两年说不定你已经不用去和这些代码打交道了:恭喜!升级!”

看得出他的脸开始有点泛红,而老二肤色本来就不是很白。

我递给他一瓶王老吉。

“你呢?”我问。

“我的表现一直平平,进度最慢的是我,解决bug最少的也是我。反正没人会去关心你的设计合不合理,也没人会认为你的bug少是好事。”

“然后我就已经打算离职了,要在一个月内把手头上的项目做完。想也不多想地每天乱码一气,最后写出来的凑合能用,虽然问题一大堆。”

“然后我就接二连三地收到进步奖金、上司的鼓励、上司的上司的表扬……”

“然后我就走了”

老二说完,打开王老吉,看了看我:“现在你知道怎样做个好的程序员了吧?”

Encryption and Decryption - Note of Fundamental Number Theory III

In previous notes we've seen how messages are encrypted/decrypted from the top and middle level. Eventually we come to the very detail about how the helper functions in setRSAKeys(), and processMessage() are implemented.

  • getPrime() in getRSAKeys() returns a prime. It randomly picks an integer and calls isPrime() to test if it is a prime. isPrime() makes use of ModularExponentiation() to perform the pseudo prime test.
int ModularExponentiation(int a, int b, int n)
{
    int c = 0;
    int d = 1;
    int mask = 0x8000;

    /*locate the most significant bit of b*/
    while (0 == mask & b) mask = mask >> 1;

    while (0 != mask)
    {
        c = c * 2;
        d = (d * d) % n;
        if (0 != (mask & b))
        {
            c = c + 1;
            d = (d * a) % n;
        }
        mask = mask >>  1;
    }

    return d;
}

bool isPrime(int n)
{
    /*this function requires function ModularExponentiation(),
     *which assumes the input n is an odd integer greater than 2
     */

    if (0 == n % 2)
    {
        return false;
    }

    if ( 1 == ModularExponentiation(2, n-1, n))
    {
        //This is, possibly, a prime, or to be accurate, a pseudoprime
        if ( 561 == n)
           return false; // the only Carmichael number in [1, 1000]
        else
           return true;
    }
    else
    {
        //This is definitely a composite
        return false;
    }
}

void getPrime(int* prime)
{
    int suspect = 0;

    do
    {
        //pick a random number
        suspect = rand() % 1000;
        //test if it is a prime
        //if yes, return
        //go to the top
    } while (! isPrime(suspect));

    *prime = suspect;
}

The modular exponentiation is to compute \(a^b\) mod \(n\), where \(a\) and \(b\) are nonnegative integers and \(n\) is a positive integer. Here it is used to test if an input number is a prime. The test is also called primality-testing. In this note the so-called repeated squaring method, described as below, is utilized to compute the modular exponentiation:

Let \((b_k, b_{k-1}, ..., b_0)\) representing the binary form of \(b\). \(b_0\) is the least significant bit. ModularExponentiation(int a, int b, int n) computes \(a^c\) mod \(n\) as \(c\) is increased by doublings, from 0 to \(b\).

The function returns false when the input n is a composite, and true, if n is a pseudo-prime, which is very likely to be a prime, with a few exceptions.

The exceptions are called Carmichael numbers. They are composites and are also pseudo-primes, but they are very rare. So rare they are that for integers less than 100,000,000 there are only 255 Carmichael numbers.

In this note we make lives simple and limit the participants less than 1000, in which there is only one Carmichael number, 561.

There are of course other ways to perform perfect prime test. Miller-Rabin randomized primality test, for example, overcomes the "fake prime" problem that we have in the method above. Again to keep this note short we simply use the Modular Exponentiation method.

With a method for primality test, in the code above a random number is picked and tested. But how many numbers should we pick until a prime is found? Is there a way to estimate the density of primes given the integer range? Yes, by the Prime number theorem:

\begin{equation*} lim_{x \to \infty} \frac{ \pi(n)}{n \ln n} = 1 \end{equation*}

the number of primes equal or less than \(n\) is approximately \(\frac{n}{\ln n}\)

So before we can find a 1024-bit long prime, we will need to test about \(\ln 2^{1024} \approx 709\) numbers, and if we skip checking the evens, there are only 354 candidates to test.

Back to our little simple case, we will get a prime, oh, a pseudo-prime, after trying about \(\frac{\ln 2^{9}}{2} \approx 3\) times, not bad ha?

After getting the required primes, two functions, gcd() and Extended_Euclid(), are used in setRSAKeys() to get \(e\) and \(d\).

The functions gcd() produces greatest common divisor of two integers. \(e\), relatively prime to \(\phi(n)\), is generated by this function:

int gcd(int a, int b)
{
   if (b == 0)
      return a;
   else
      return gcd(b, a % b);
}

I was thinking a simple while loop would be more efficient than the recursion version, but comparisons in C doesn't show any benefit...

After playing with some numbers and I realized that: 1. when a = b, the recursion terminates. 2. if a>b or b>a, the number of recursions is still reasonably small.

(and as it proves later in the book:(Lamé's theorem)

for any integer \(k \geq 1\), if \(a > b \geq 1\) and \(b > F_{k+1}\),

then the call Euclid(a, b) makes fewer than k recursive calls.),

where \(F_{k}\) is the Fibonacci numbers.

Exended_Euclid() are based on the Euclid's algorithm and it's extended version:

Given the input of \(a\) and \(b\), returns \(d\), \(x\) and \(y\), where integers \(a\), \(b\), \(d\), \(x\), and \(y\) satisfy:d = gcd(a, b) = ax+by

This function is used here to calculate modular multiplicative inverses, \(d\).

  typedef struct euclid_coefficients
  {
     int d;
     int x;
     int y;
  } euclid_coefficients;
  euclid_coefficients ec;

  euclid_coefficients Extended_Euclid(int a, int b)
  {
     if (b == 0)
     {
        ec.d = a;
        ec.x   = 1;
        ec.y   = 0;
        return ec;
     }
     euclid_coefficients tmp;
     tmp = Extended_Euclid(b, a % b);
     int old_x = tmp.x;
     tmp.x = tmp.y;
     tmp.y = old_x - a/b*tmp.y;
     return tmp;
  }


* The last step is to use the key to encrypt/decrypt the message:

      long powerMod(long x, int n, int y)
      {
        if (1 > n)
        {
            return 1;
        }
        if (x > y)
        {
            x = x % y;
        }

        long tmp = 1;
        while ( n > 2 )
        {
            n -= 2;
            tmp = ((x * x) % y) * tmp;
            tmp %= y;
        };
        if (2 == n)
        {
            tmp = (x % y) * tmp;
        }
        tmp = (x % y) * tmp;
        tmp %= y;

        return tmp;
      }

      void processMessage(long* msg, key key, int len)
      {
          int i;

          for (i = 0; i < len; i++)
          {
              msg[i] = powerMod(msg[i], key._key, key.n);
          }
      }

After all, we've built a simple encryption/decryption tool. Time to have some fun...

~/EncryptionAndDecryption/> test
p = 61, q = 881
n = 53741, phi(n) = 52800
e = 7
d = 7543
the encrypted message:
[~] [] [] [] []
the decrypted message:
[h] [e] [l] [l] [o]

~/EncryptionAndDecryption/>

Encryption and Decryption - Note of Fundamental Number Theory II

The first thing we need to do in the main function is to prepare two groups of keys.

The function setRSAKeys() helps to generate a public/private key pairs:

int setRSAKeys( key* publickey, key* privatekey)
{
    //generate two 512bit primes p and q
    int p, q;
    srand((unsigned)time(0));
    getPrime(&p);
    getPrime(&q);
    //printf("p = %d, q = %d\n", p, q);

    //calculate n and phi(n)
    int n, phi_n;
    n = p * q;
    phi_n = (p - 1) * (q - 1);
    //printf("n = %d, phi(n) = %d\n", n, phi_n);

    //calculate e, a small odd relatively prime to phi_n
    int e = 1;
    do
    {
        e += 2;
    } while (1 != gcd(e, phi_n));
    //printf("e = %d\n", e);

    //calculate d, the multiplicative inverse of e, modulo phi_n
    euclid_coefficients ec ;
    int d;
    ec = Extended_Euclid(e, phi_n);
    d = ec.x;
    if (0 > d)
    {
        d += phi_n;
    }
    //printf("d = %d\n", d);

    //return (n, e) and (n, d)
    publickey->n = n;
    publickey->_key = e;
    privatekey->n = n;
    privatekey->_key = d;

    return 0;
}

In the function above, two primes are picked to compute \(n\), which in reality is a gigantic number because \(p\) and \(q\) are big primes, say 1024 bits each. (again in this note we simplified the case by using small integers)

Then \(e\) and \(d\ =\ \phi(n)\) are obtained to form the primes: \(e\) is a small odd integer and falls into the public key set. \(d\), another big number calculated based on \(n\), is not very easy to guess (or reversed-engineering), and is therefore put as part of the private key set.

Euler's phi function:

\(\phi(n)=n\ \displaystyle\prod_{p|n} \left(1- \frac{1}{p}\right)\)

where \(\phi(n)\) is the size of \(\mathbb{Z}_{n}^*\), \(p\) runs over all the primes dividing \(n\) (including \(n\) itself, if \(n\) is prime, too)

\(\mathbb{Z}_{n}^*\) is the multiplicative group modulo n, or defined as

\(\mathbb{Z}_{n}^* = {[a]_n}\) in \(\mathbb{Z}_{n} : gcd(a,n) = 1\)

where \([a]_{n}\) = \(a'\) mod \(n\), \(a'\) in \({Z}\)

e.g. \(\mathbb{Z}_{15}^*\ =\ \{1, 2, 4, 7, 8, 11, 13, 14\}\), \(\phi( 15 ) = 15 ( 1 - \frac{1}{3} ) ( 1 - \frac{1}{5} ) = 8\)

When we select \(p\) and \(q\), which are primes and \(n\ =\ pq\), The phi function becomes \(\phi(n)\ =\ (p-1)(q-1)\), much easier now =)

At the end of the above function we have set two groups of keys: the public key \(\{e,\ n\}\) and the private key \(\{d,\ n\}\)

With the public and private keys, encrypting and decrypting a message becomes easy. Given a message \(M\), to encrypt \(M\) we do:

\(M^e\ mod\ n\)

the outcome of which, \(S\), is the encrypted message. To decrypt the secret,

\(S^d\ mod\ n\)

will give you the original message.

\(d = e^{-1}\ mod\ \phi(n) = e^{-1}\ mod\ ((p-1)(q-1))\) guarantees for the given \(p\), \(q\) and \(e\) there will be a unique \(d\). Therefore for a given public key \(\{ e,\ n \}\), there will be one and only one private key \(\{ d,\ n \}\). This is exactly what we want!

On the other hand,

\((M^e\ mod\ n)^d\ mod\ n\ =\ M^{ed}\ mod\ n\ =\ M\)

promises the encryption and decryption are irreversible operations.

To be continued...