Monthly Archives: April 2011

当年做的蛮开心的一个小程序


回顾了一下,发现自己这么久以来做了很多的项目,参与到了很多的项目,也有上10万行代码的项目,但发现自己做的最开心的其实是一个数独游戏,在那个游戏也不是去增加程序的功能的快乐,而是去提高算法效率上收获了很多,之后又尝试去做象棋,体会到为了提高效率的辛苦,甚至后来为了参加比赛而写代码,在读取写入文件榨取那么几毫秒的时间。再后来养成了一定的习惯,无论写完什么,之后总是前后考虑对效率的影响,是否已经发挥到了极限,是否还可以继续提高效率,减小内存的开支,有的时候走在路上,睡觉前,上课走神的时候甚至都会考虑一下,也许这就是代码的乐趣吧!

如今想来,刚开始其实不懂,很多的时候是为了项目而做项目,于是做了一个又一个网站,但如今看来那些算什么呢,感触最深的是自己用了什么什么框架写了多少多少行代码,窃窃自喜,但突然发现大牛写了一个框架去给别人使用的时候发现了自己多么的愚蠢。

回想这个数独游戏,是在2010年初写的,界面操作模仿数独博士,现在看来也还算很不错的,当时花了很长的时间去提高它的效率,记得有一道题目,是专门针对普通算法的题,普通的穷举基本卡死,要4、5秒钟,后来我降到1秒,降到200ms,降到50ms,最后降到了5ms,这其中的乐趣不是能描述出来的。界面也花了很大的功夫,很多时候为了一个小控件的使用方法,自定义控件,图片的颜色,GDI+,windows消息机制,google了好久,此后的好久我再写MFC程序的时候都要翻翻这个小程序找到一些用法。程序中使用了3个customer control,自己定义样式,属性,事件,其实很多人抱怨MFC控件少,老,陈旧,都是片面的,现在的桌面程序还没有几个完全是.NET写的,当自己创建一个控件,然后使用,会发现MFC的健壮性,扩展性直到如今都是那么值得称赞。

但是后来又没有完成所有功能,好像是累了,懒了,不愿写了,功能都是重复的,就是填代码了,缺少了刚开始的兴奋,所以就没写完。但也可以玩一玩,还是蛮有趣的。

现在我就把它开源出来,给那些MFC的初学者一个小例子,希望能够帮助到一些人,环境是VS2008 SP1

项目地址:http://code.google.com/p/sudoku-xiu/

原创文章,转载请注明: 转载自yongxiu

本文链接地址: https://yongxiu.net/201104/13205.html

浅谈公钥密码

前篇文章谈到一个非对称密钥加密系统,觉得很是神奇,一直想找一个实例,最近查阅了一些资料,google了一下,找到一些,分享一下。

它的用途有很多,数字证书啊,https啊,我感触最深的就是那个ssl加密,感觉很神奇,试想你和网站中间的路由一直在监听你们的传输数据,甚至从发送证书开始,只要通过ssl加密,它就不能窃取了(当然没那么绝对)。

首先看左图,有一个RSA看到了吧,他是很关键的一个密码加密系统,gmail网站有一个公钥,它是对所有人公开的,任何访问它的人都可以得到,用它可以进行加密;然后它还有一个密钥,通过密钥就可以对加密内容解密,gmail的任务是保管好密钥,任何人都不能得到。

大家可能会在网上搜到两个大素数的积分解困难等关键字,却不太明白具体的原理,我在这儿举个例子,例子是在一本叫《公钥密码学》上看到的,很简单,能让我们懂得基本原理。

参数生成:

(1) 选取两个大素数p和q (保密)

(2) 计算n=pq(公开的系统参数),γ=(p-1)(q-1)(保密)

(3) 随机选取整数e(公开的加密密钥),使得gcd(e, γ)=1

(4) 计算d(保密,私人密钥),使得ed≡1(mod γ),即d=e-1(mod γ)

(5) 加密:c=me mod n

(6) 解密:m=cd mod n

举一个实际的例子:

p = 11, q = 23,则 n = pq = 253

γ=(p-1)(q-1) = 220

选取加密密钥 e = 3,显然gcd(3, 220) = 1,求得 d = 147。

对于明文 m = 165,有密文 c ≡ 165 * 165 * 165 mod 253 ≡ 110

对于密文 c = 110,有明文 m ≡ 110^147 mod 253 ≡ 165

看,上述就是一个简单加密,解密的例子,你可能会说p, q岂不是很容易猜出来,请记住“两个素数的积分解困难”,很大的!

完成这步之后,客户端浏览器按照服务器的只是生成128位的RC4对称密钥,你可能会问,这个时候为什么不用非对称的?因为效率!非对称虽然有很多的好处,但是有效率限制,再说双方通过RC4传输,通过刚才的非对称加密已经保证这个RC4密钥的安全性了,为什么还要再用非对称呢。

当然这个RC4不是绝对的,服务器也可能要求使用别的加密方法,例如微软的live用的是128位的AES,QQ邮箱用了256位的AES,但他们都是对称密钥加密。

顺便再提一嘴MD5,本来和密码没什么关系,但是学习的过程中,仿佛在说不可能有两个MD5一样的不同文件。我就一直在想,如果通过一个128位的字符串就能表示几G的电影,岂不是说任何文件都能压缩到128个字节,或者说128位字符串能表示所有文件?

其实是我的理解错误,MD5的算法网上有很多,大家看一下就会发现,确实文件之修改一点点都会造成MD5的值发生变化。

它的要求是:
对任何给定的码h,寻找x使得H(x)=h在计算上,是不可行的,称为单项性;
对任何给定的分组x,寻找不等于x的y,使得H(y)=H(x)在计算上是不可行的。称为弱抗冲突;
寻找对任何的(x,y)对,使得H(y)=H(x)在计算上是不可行的,称为强抗冲突;

看,上述的都是强调在计算上,上网搜一下MD5碰撞,你就会发现存在两个不同文件MD5值相同。

好,今天到这里,文章可能有疏漏,请指正!

原创文章,转载请注明: 转载自yongxiu

本文链接地址: https://yongxiu.net/201104/12198.html