Skip to main content

Encryption and Decryption - Note of Fundamental Number Theory I

Reading the number theory has taken me a while. And I guess, possibly, the most useful application of number theories is information encryption/decryption and digital signatures.

This note lists the essence of elementary number theory (well at least I think so), by showing how basic encryption/decryption and digital signatures is done. Here we go...

The public-key cryptosystem is based on the dramatic difference between the ease of finding large prime numbers and the difficulty of factoring the product of two large prime numbers.

Each participant in the system has a public key or/and a secret key. There are many algorithms for the public-key method, the RSA public-key cryptosystem is one of them. In the rest of this note we will only focus on the RSA method.

When applied in an encription/decryption scenario, usage of the keys is depicted as below:

Plain Message ---Public Key---> Encrypted Message

Encrypted Message ---Secret Key---> Plain Message

No one will be able to get the plain message from the encrypted one except for the one who holds the secret key. Everyone who has the public key will be able to send the encrypted message to the secret key holder.

When applied in a digital signature case:

Plain Message ---Secret Key---> Signed Message

Signed Message ---Public Key---> Plain Message

No one will be able to produce a 'fake' message with the same digital signature. Everyone will be able to read the plain message sent with digital signature, as long as they have a public key.

When combining the two above, one can send a signed and encrypted message.

But how to make the keys and how the keys work?

In reality RSA requires playing with very big numbers, something like 1024-bit integers. For the sake of simplicity we are not going to stick with those big fat digits, instead small numbers are used just to show how things work. For serious code, you may find the GMP library interesting.

OK, let's get our hands dirty with some C code. Firstly we build the top main function:

typedef struct key
{
   int n;
   int _key;
} key;

#define MESSAGE_LENGTH 5

int main(void)
{
   /*prepare the keys*/
   key publickey, privatekey;
   setRSAKeys(&publickey, &privatekey);

   /* use long here to hold the encrypted message */
   long message[MESSAGE_LENGTH] = {'h', 'e', 'l', 'l', 'o'};

   /* Encryption - process message with the publickey */
   processMessage(message, publickey);

   printf("the encrypted message:\n");
   printMessage(message);

   printf("the decrypted message:\n");
   processMessage(message, privatekey);

   /* prints the outcome */
   printMessage(message);

   return EXIT_SUCCESS;
}

老二洗碗

老二吃饭后总是第一时间洗干净碗筷。

“为什么不喝喝茶休息一下再去洗?”我有一天忍不住问。

“在最好洗的时候洗,这些东西放久之后却需花更多力气了。”

转眼间他已经在擦手,走了过来,“现在水刚烧开,可以喝茶了,哈哈。”

嗯,太多的时候我们总是会由着所谓的心情或感觉去回避或拖延那些应该马上就该做的事,结果只是一拖再拖。或是等到不能再等的急迫,或是拖到无需再拖的错过。几乎所有的后悔,都因曾经的任性。

嗯,今天开始,吃完饭洗碗,水烧开喝茶。

一零年记

自第一次给自己写年记已经是第七年,中国人有说法“七”是一个带来转变的数字。好像是这样的。

过去的年度总结或是遗憾自己依旧没有进步,或是罗列诸多没有完成的事情。总之就是364天都没好好过,到了最后一天才来后悔。 这回终于可以写些不一样的东西。

10年初重返老东家,回到熟悉的碧波路690号。新的开发模式让每个工程师可以同时在不同的产品的不同阶段工作,不再有项目组的概念;一项功能的描述只有一句话,剩下的自己搞定;现有的代码没有文档,代码就是文档;一个功能没有可以咨询的专家,新来的你就是专家。不知道这是不是所谓的敏捷,但是是我喜欢的方式;组里召回的都是资深行家,最年轻资历最浅的我闭眼挑谁都是师傅,这也是我选择吃回头草的原因。因此能揽多少活就揽多少活,能加几天班就加几天班。若拙只能以勤补,那么以前对自己说过的“期待艳遇的人,就要不断地往女人堆里钻”,我想自己已经在这样做了。

玩也玩了不少。一年里我们爬普陀,钻拱门,冷三番,热赌城,看了朋友,喝了咖啡。实在够了。

第四年的婚姻生活回忆起来全是感激,2010年的收获是全新的婚姻智慧与哲学,我想从此我们便有了近乎无穷的动力去爱对方。这一段说的太多反倒觉得无力,还是用两句话来总结并供日后回味:

Give, and it will be given to you. 出自这一本书

Love is a choice.

Love is something you do for someone else, not something you do for yourself. 出自这本书

父亲因为工作来过上海几次,每次见面都会看到时间在他身上划下新的痕迹。不知道我这次回家看望外婆是不是依然控制不住自己的情绪,但我知道面对渐渐老去的亲人,我们能做的和他们要求的,都只会越来越少。今年春节,希望能在短暂的时间里带给他们哪怕一丁点的快乐和慰籍。

工作和家庭已经占据了我绝大部分的时间,这让2010年的学习项目执行得非常困难。虽然也完成了一些读书计划,但不是小说就是一些温故知新类的书籍。几本大部头的进度显然落后了一大截。而除去读书外想做的事情就更是心有余而力不足。不过有得必有失,凡事不能面面俱到照顾周全。能有哪怕一丝时间可以给我利用,有哪怕一点点的精力让我继续,就可以了。面对面前的一根根粗铁棒,我可以慢慢磨下去。

总之今年做了两件事:应该做的和想做的

忙而不乱,一零年没白过。

老二的诗

老二是我的学长,以往暑假的时候都会借他用过的书来预习下一年的课文。 记得在过去校园风行写诗的时候,曾在老二的课本上看见过:

”一辈子做自己想做的和应该做的然后才有资格笑在那么多哭泣的脸面前离开“

当时觉得这家伙又在课堂上走神强说愁了,一句话随意断句换行就称诗,还不押韵!我告诉他读者的感受,结果是我被威胁以后若再贬低他的创作就再也不要找他借书了。

虽然这样,我还是不停笑他的诗包括情诗,老二也还是在考试结束后就把所有的课本资料自觉地转送给我。

也许是因为他的作品确实太多,我至今仍记得那么几句甚至是某篇。

这首短诗是记得最清楚的,因为时常想起。

”应该做的和想做的“,离开校园也有好几年,有时想想人需要做的不就这两样么。 先做好应该做的,不管想或不想做,这是履行义务;然后做想要做的,无论应该不应该,这是享受权利。 不能贪得无厌的索取,也毋须呕心沥血的付出。 先往左一丿,再往右一㇏,人字写成。于是面对那么多人的不舍,你可以坦然笑着离开。

世道复杂,世理简单。而当我最近开始这样做的时候,才觉得:当时不应该笑话老二的诗的……

丝婚-两个人的结婚酒

戴上戒指后的第四年,左手无名指已经长出一圈浅浅滑滑的凹痕,总会习惯性地不时用拇指去摸它。

每次发现戒指不在了,马上会去找到并戴起来。因为,你的手上戴着另外一只。

第四年对彼此的了解,比两年前杀人游戏的默契多一点,较去年模式化的争吵深一些。

你知道我喜怒无常,说变就变情绪化;你知道我做事丢三落四,尽管你再三叮嘱我还是会转头就忘;你也知道我总是愚孝,父母的话不加分析就言听计从。

我知道你的自尊心很脆弱,每次理亏的时候都不会再说话;我知道你的毅力极差,虎头蛇尾的你总是三分钟热度坚持不下去;我还知道你没有生物钟,睡觉和起床的时候从来不可预测。

深知对方的缺点和短板,你我都想要帮助对方改正,但又都听不进各自的“金玉良言”:你自己还没做好呢,凭什么来说我?

前所未有的默契竟也能带来两个人的战争,各打各的旗帜,各说各的语言。

于是开始有些觉得爱得乏力,于是对对方的要求愈加多于对自己的鼓励。

4年的相处与相待、相爱与相伤,我们的爱加加减减。

如果说是双方的优点吸引了彼此,那么当过了爱屋及乌的时候,就需要更多的婚姻智慧来教我们学会包容对方的缺陷。

值得感激的是在相同的一年里我们找到了新的源泉,因有它,我们获得无穷的动力和能量去给予对方无私的爱。

某日在回家的路上它告诉我,婚前恋爱的热度就是婚后生活中爱的标杆:如果你现在对她没有恋爱时那样重视和珍惜,你就应该检讨你自己。

于是我争取把加班都放在工作日,并在周末张罗三餐饭菜,这样能让你休息的同时还可以体会到其实你在家里操劳家务也确不易。

于是你每天早上都跑市场买新鲜菜肉,这样我就不用再吃冷冻的食物,你也在努力培养规律的作息。

两个人的生活有了新的动力和生机。

而举再多的例子也显乏力。能用新的定义和方式去爱你,我想这是今年最大的收获之一。

丝婚的那天,你和我布置了一桌丰盛的海鲜无米粥火锅——两个人的结婚酒席。

屋外瑟瑟寒风夹杂着乱飘的雨,家里热气腾腾的火锅吃得很暖很晚。

http://farm6.static.flickr.com/5248/5233243744_388651d747.jpg

后记:写完后重新读了一遍,才知道第四年我们的主旋律原来是:吃。

几乎通篇都和吃有关,也真的算是以食为天了……

老二与作业

老二说话言简意赅,有时候很讨厌,但大多数时候却是很讨人喜欢。

于是局里偶有女孩对老二颇有好感,尽管他的儿子都已经可以背出方文山的词了。

有女C约老二喝茶暗示爱意。

老二翻看报纸的时候问:你小时候一定爱抄别人作业吧?

C不知所云,用崇拜的眼神等待男人的下一句。

按原样叠好看过的报纸,老二说:我那儿子就自己写。

C笑而不语。

茶毕,老二买单。

半年后,C和新男友请全局同事外出烧烤,老二不无遗憾的说:我得看儿子写作业……

“重婚”赌城

今年很重要的一个指标就是“重婚”:三年之痒后我们打算再结一次重燃爱火。

于是周末之外又请了一天假,我们杀到赌城,结婚。

按照计划,结婚小分队携款游击Strip上各大赌场,希望有所斩获,得来的横财可以办场盛大的婚礼。

和计划中的一样,我们输光了所有的赌资,高高兴兴地找了家小办事处登记结婚。

同行的杰西同学欣然接受了证婚人的使命,并兼全程即兴摄影师。(感谢感谢……)

简单却庄重的仪式之后,我们“又一次成为了夫妻”~

http://farm5.static.flickr.com/4139/4914691264_3f685f271a.jpghttp://farm5.static.flickr.com/4138/4914087429_c3884c56c6.jpghttp://farm5.static.flickr.com/4076/4914690844_b14d28c3c5.jpghttp://farm5.static.flickr.com/4122/4914690580_e01a2af980.jpg

更多重婚证据见Las Vegas, U.S.A, 2010

Note on a Few Defects

These days I have been working on some coding stuff, and was stuck in some stupid, yet interesting defects.

Here are two of them, that I still remember:

//..
if ( 0x2400 & 0x2000 != 0 ) printf("you know this must be true...\n");
//..

The above is an abstraction from codes of one of my projects.

At the moment of coding I believe I certainly will see the line prints.

After I see nothing I believe there must be something wrong with my eyes.

Then I went to the restroom, took some water, and return to my seat.

Aha! I suddenly realized how mind absent I was:

the operator & is below != in the precedence table, which means 0x2400 & 0x2000 != 0 is actually 0x2400 & ( 0x2000 != 0 ) !

Well, I bet this precedence problem is just a piece of cake for a college student (or even a high school boy).

But when it comes to real life and real code...

Hmmm, I believe, truely, I need reviewing some of the text books.

I can feel the disdain on your face ;-), so here comes a little bit more interesting one: (again it is a make-up model of the real code)

  #define E_NOTIMPL 0x01234567
  //..
  class Base
  {
     public:
        virtual int foo() = 0;
        int newfoo() { return E_NOTIMPL; }
     //..
  }

  class Derived : public virtual Base
  {
     public:
        virtual int foo() {printf("Derived foo\n"); return 0;}
        virtual int newfoo() {printf("Derived newfoo\n"); return 0;}
     //..
  }

  int main()
  {
     Derived d;
     Base* pb = &d;
     pb->foo();
     pb->newfoo();
  }

The problem of the code above is, i can't get the "Derived newfoo" at all. What is even quirky is, in my debugger I see no execution point in the line pb->newfoo();, which means line 24 doesn't even execute!

And again I had some (more) water and returned to the code:

in line 07 the keyword virtual is missing, thus there is no virtual table entry in the Base object, thus Derived::newfoo() can never be invoked...

but why line 24 is not executed?

because the code for an ARM platform has been compiled with specialized optimization and line 24 was skipped!

This is the whole story about bug fixing and, water drinking.

Apparently there is still a long way for me to grow into a competent programmer...

去了三番

一个月前趁着独立日的档期,混到三番乱游了几天。

第一感觉就是乱。

街头上空永远横七竖八排着一堆的电线,唐人街乱摆着夫子庙城隍庙才卖的劣质商品,九曲花街上乱开着各式各样的车,到了晚上还有不少异族在街上乱晃。乱,实在是乱。

但要说一无是处也过分了些。

SFMOMA还是值得一看,美国现代艺术在此可见一斑。在Guardians of the Secret跟前看了很久不知所云,幸而某团导游带队在画前重点解释了一通,才知道内藏玄机,而真正的秘密究竟是什么,还真的不知道什么时候才能被揭晓。

金门桥在我们去的那天还是深锁在雾中,看着觉得也就那样,骑车上了桥才知道西太平洋的风有多大(在荷兰两年都没有见过那么大的风)。站在桥中央目送那些出海的货船,它们就这样慢慢地驶向无边的太平洋,消失在雾里。每次面对大海的时候都会暗自感叹人的渺小,伴随着那么一丁点的恐惧。一来一回骑到了原点,累得不行。

最后还是去了斯坦福。做不了牛人,也要到牛人堆里YY一小会。见到David和William资助的两栋楼时,自然也要拜拜,留个影纪个念:说什么也算是沾亲带故了:)

总体感觉所谓的国际都市都没什么吸引人的,还是小城镇宜人且安居乐业。于是乎当我们回到小土豆城Boise的时候,发现更是爱上这种平淡简单的生活。

http://farm5.static.flickr.com/4098/4784218027_082562c650.jpghttp://farm5.static.flickr.com/4140/4783623040_2917618cfc.jpghttp://farm5.static.flickr.com/4116/4783621998_0e1240ba51.jpghttp://farm5.static.flickr.com/4079/4783623734_e057b2012f.jpghttp://farm5.static.flickr.com/4135/4783628642_cee4351a28.jpghttp://farm5.static.flickr.com/4136/4782996515_a9b14f8d55.jpghttp://farm5.static.flickr.com/4073/4783633414_3a883d0801.jpghttp://farm5.static.flickr.com/4074/4783635774_926d380358.jpghttp://farm5.static.flickr.com/4093/4783639494_0b6663a991.jpg

更多旅途照片见San Francisco, U.S.A, 2010

去了拱门国家公园

趁着Momenrial Day有一天假期,外加周末两天,我们蹭了同事的车一路往南杀到了犹他州的拱门国家公园(Arches National Park)。

Arches实际上是一片海拔比较高的沙漠,大概有1500米。特殊的地理结构,经过长期的风蚀和雨蚀,就变成了世界上拥有最多自然石拱门的地方。

公园里可以行车,但也保留了绝大部分原态的地貌,于是很多景观都需要步行才能看到。整个公园已经预先设计好了可以徒步行走的很多小路(trail),短的半小时就走完了,长的仅仅是单程也需要8小时以上……

没有能够走完全部小路,雯和我只走了最短的Park Avenue和最著名的Delicate Arch。后来雯的脚底也起泡了,我们便在Devil Garden(需要4~5小时完成)入口处一边望洋兴叹一边聊天休息过了一个下午。

面对千百年后形成的石拱门,除了好看,却也没有什么其他的感叹。倒是一路上见到不少父母背着还不会走路的小孩徒步爬山,很是佩服。

没有很深刻的意义,没有很难忘的情节,当然,也没有熟悉的人山人海。只是边走边聊,顺带看看那些在资料里颇为壮观的景色。

嘿嘿,就算是到拱门国家公园一游了。

http://farm5.static.flickr.com/4055/4673215229_0b0402b263.jpghttp://farm5.static.flickr.com/4038/4673215407_228ea3221c_b.jpghttp://farm5.static.flickr.com/4036/4673213433_11b5a6f945_b.jpghttp://farm2.static.flickr.com/1286/4673213835_39120e56d3_b.jpghttp://farm5.static.flickr.com/4049/4673837484_935cbe196a_b.jpghttp://farm5.static.flickr.com/4059/4673213103_51ef0ebe67_b.jpg

更多旅途照片见Utah, U.S.A, 2010