Xun’s blog

hello from home

ZoundryDocument

1985年，Miller和Koblitz分别独立提出了该想法。

Koblitz的论文见http://links.jstor.org/sici?sici=0025-5718%28198701%2948%3A177%3C203%3AECC%3E2.0.CO%3B2-E

椭圆曲线方程的图像并不是椭圆，取这个名字是因为它的形式和求椭圆弧线长度时用到的积分很像。

ECC因其密钥短加密速度快逐渐成为RSA的热门接替者。根据NSA的数据ECC用313位密钥的获得的安全性和RSA用4096位密钥相当，并且有着更快的性能。

可用于加密的椭圆曲线主要是模p的椭圆曲线，这种曲线上的点有这样一种性质，任意给出椭圆E上的两点P,Q可以很容易的计算出第三点R，反之则很难，并且R也在E上，如果把这种运算定义为加法运算则意味着E上的加法运算时封闭的。

如E：y^2≡x^3+4x+4(mod 5)

该E上的点是有限的，无论x取什么值，模5后都只能等于0，1，2，3，4中之一。代入x解对应的二次剩余方程即可求出对应的y。

但并非对于所有的x取值都有相应的y，当x≡3(mod 5)时，y^2≡43≡3(mod 5)无解。而x≡1(mod 5)时，y^2≡9≡4(mod 5)，解得y=2或3，所以(1,2),(1,3)为椭圆上的点。

椭圆曲线上的明文嵌入。

E：y^2≡x^3+bx+c(mod p)为椭圆曲线。

为了加密明文m（已表示为数字），把m作为x代入椭圆方程，但是因为只有1/2的机率，x^3+bx+c是模p二次剩余，有对应的y。这样的加密成功率是不能接受的，所以m需进行一定的处理，才能使m作为E上一点的X坐标值被嵌入椭圆。

Koblitz的方法是

取k，使（m+1)k<p

x=mk+j(0<=j<k)

对于j的不同取值计算x^3+bx+c是否为模p二次剩余，如果是则以点(x,y)嵌入椭圆曲线成功，如果所有的取值都非模p二次剩余则嵌入失败，但这种可能性只有（1/2)^k。

恢复数据只需要做m=[x/k]，即使m等于x/k的整数部分。

ElGamal加密系统的椭圆曲线实现。

如果A要发消息给B

B选择一条椭圆曲线E(mod p)，并取其上的一点P，和一个随机数a，计算出Q=aP，把（E,P,Q)作为公钥发送给A，保留a为私钥。

A得到B的公钥后，把消息m表示为E上的一点x（可以用Koblitz方法），并取一随机数k，计算y1=kP，y2=x+kQ，把（y1，y2）发送给B。

B通过x=y2-ay1=x+kQ-akP=x+kaP-akP,解密消息。

整个系统的秘密在于P和Q的关系。因为y1和y2是分别通过P和Q计算出来了所以它们之间的关系是P和Q之间的关系的延续，k只是作为这种关系的掩盖，并在解密过程中被消去。

椭圆曲线算法的作用在于确保在不知道a的情况下没有可能通过P和Q计算出他们之间的关系。

研究方向：

1）并非所有的椭圆曲线都适合用于加密，选取一条安全的椭圆曲线确保安全性的第一步，这方面有很多工作可以做。

2）椭圆曲线上的明文嵌入，Koblitz的方法虽然简洁明了，但效率不高，有改进的空间。

3）标量乘法效率优化。

参考的书：

Wade Trappe, Introduction to Cryptography with Coding Theory (SE),第三章 Basic Number Theroy和第十六章 Elliptic curves

ZoundryDocument宿舍通过DHCP服务器动态分配IP
rem ipdom.bat
netsh interface ip set address “本地连接” source=dhcp
netsh interface ip set dns name = “本地连接” source=dhcp

实验室需要指定静态的IP
rem iplab.bat
netsh interface ip set address “本地连接” source=static IP addr=172.1.15.119 mask=255.255.0.0 gateway=172.1.96.10
netsh interface ip add dns name = “本地连接” addr = 172.1.0.1

ZoundryDocument

ZoundryDocumenthttp://releases.ubuntu.com/releases/8.04/下载光盘映像。用虚拟光驱工具加载映像文件后，直接运行就可以在Windows下安装了，但是这样Ubuntu是以文件的形式装到Windows格式的磁盘分区上，就是所谓的wubi安装，不推荐。要想达到光盘安装一样的效果可以参考这篇文章http://www.divbeta.com/blog/article.asp?id=40

补充一下。

拷贝出casper，.disk目录不需要放到C盘，可以是任意盘，find –set-root /Ubuntu-8.04-beta-desktop-i386.iso只是查找Ubuntu-8.04-beta-desktop-i386.iso文件，并把那个盘设为/目录，所以这个Ubuntu-8.04-beta-desktop-i386.iso可以换成任意文件，只要放在casper，.disk的同一盘根目录就行了。

Grub for Dos中只需要grldr文件。

没有必要拷贝出vmlinuz和initrd.gz文件，只要在menu.lst中多加一个路径。

kernel /casper/vmlinuz boot=casper
initrd /casper/initrd.gz

其实这个时候ISO文件都已经没有必要了。安装所需的所有文件都在那两个目录里面了。

安装前最好在windows下先分好区，Windows自带的磁盘管理工具就行了，Ubuntu的分区工具很不好用。分区的话推荐一个100M的/boot,内存1.5倍的Swap分区，其他都留给/了，并且Linux最好装到逻辑分区上，免得分区表不够用。

输入法，打开Synaptic搜索scim-pinyin装上，打开System，Administration,Language Support把那个Input Method下的小框选上就可以了，甚至不用装中文语言包，我比较受不了把Synaptic翻译成新立得这样的中文界面，所以就直接用英文的了，和Windows一样默认设置是Ctrl+Space唤出输入法，只是Scim没有Windows下的Sougou和Google拼音好用。

3D桌面效果。打开System，Appearance，把Visual effects调到最高，这时会提示安装驱动，装完重启。Synaptic搜索compiz manager安装后，System，Preference下多了一个Advanced Effect Setting的选项，就是设置3D桌面效果的，设置一下打开Desktop Cube和Rotate Cube，就可以按下Ctrl+alt并拖拽鼠标感受旋转桌面的效果了。

影音播放，用Synaptic装上mplayer，去http://www.mplayerhq.hu/MPlayer/releases/codecs/下载自己机器对应的解码包，解压到/usr/lib/codecs/目录下（开一个Termina，sudo mkdir /usr/lib/codecs/ ，sudo cp……来完成），不装解码包的话不能播放RM系列格式的影片。mplayer是一个非常强的播放器，如果不习惯他的操作也可以装smplayer，他们用的是一个核心。

ZoundryDocument/boot Linux内核 Grub的安放地
/etc 系统软件配置目录
/var 临时文件夹 synaptic下载的deb安装包都放在/var/cache/apt/archives
/tmp 存放更加临时的文件
/proc 以文件形式表示的进程，贯彻一切都是文件的思想？
/dev 以文件形式表示的硬件设备
/usr 最大的目录，一般用户的配置信息安装的程序都在这里
/usr/src Linux头文件，定义当前内核能够提供的函数

可执行程序的目录 S代表系统级
/bin
/sbin
/usr/bin
/usr/sbin
/usr/local/bin
/usr/local/sbin
/home/用户名 主目录 bash中~表示，cd无需参数直达

Linux文件布局标准

http://www.pathname.com/fhs/pub/fhs-2.3.html

ZoundryDocument一幅图片是由一个个的像素点组成的，作为有色光的三基色，红绿蓝（RGB）可以以一定的比例混合出任何颜色，所以一幅彩色图片的每个像素都可以用RGB三个分量来表现自己，常见的每个分量用8位，这样一个像素需要3×8=24位，而一幅图片就是一个每元素24位的二维数组。但是研究发现人眼对颜色的敏感比不上对亮度的敏感，因此可以将亮度分量从色度分量中提取出来而以较少的位来表示色度信息，从而更加有效的表示彩色空间。

因此与RGB相对，另一种颜色空间为Y:Cr:Cb，这里Y为亮度分类，即一幅彩色图片的黑白版本，由RGB加权平均得出。Cr，Cb是R，B与Y之差，为色差信息，因Cr+Cb+Cg为常数，所以Cg无需传输。

RGB与Y:Cr:Cb转换公式
Y=0.299R+0.587G+0.114B Cb=0.564(B-Y) Cr=0.713(R-Y)
R=Y+1.402Cr G=Y-0.344Cb-0.714Cr B=Y+1.772Cb

利用人眼对亮度敏感的优势，在一幅彩色图片中，我们可以交叉地使一些点只有亮度分量没有色度分量，而不被人眼察觉。

4：2：2采样（YUY2）：对于图像数组每隔一列只采样Y分量。
4：2：0采样（YV12）：每隔一列和一行只采样Y分量。

因此4：2：0采样的图像只有1/4的像素是24位的，其余3/4的像素只有Y分量的8位，即平均每像素1/4×24+3/4×8=12位，这也是为什么它在FOURCC代码中的表示为YV12。

一个视频编码器的主要功能有：
1，滤波。消除视频源中的干扰信号。
2，源模型编码。把视频变换成一种易于压缩的格式。
3，熵编码。无损压缩上一步得到的数据。

最关键的是第二步了。在这里视频编码被分为帧内编码（Intra-frame Coding）和帧间编码（Inter-frame coding），视频无非是一张张连续的图片，帧内编码就相当于压缩一张图片，因为组成一段视频的图片有一定的相似性，据此我们可以只完全编码压缩某一帧图片，该帧称为I帧，其后的帧只保存那一帧与I帧或基于I帧的某种运动预测后的图片的差别，如果是连续的场景，物体的运动预测又足够准确的话，这种差别是很小的，因此我们只需保存很小的数据量就能恢复出原图像。运动预测的一般方法：把当前帧的某个区块向各个方向移动几格，并与下一帧的对应区块进行比较（通过计算两个图像数组的均方差），保留均方差最小的那个方向做为运动矢量，用于解编码。这个过程会用到各种不同的搜索方式和大量的比较运算，是衡量一个编码器好坏的关键。

编码步骤
变换编码。因为一幅图像的各个部分的空间相关性很高，不利于直接压缩。变换编码就是把图像用一种各部分相关性弱的形式表示，这样就可以去掉一些不重要的点，来进行有损压缩。其实质就是一个24位二进制数的二维数组，从一个各值很平均的形式变到另一种各值落差很大的形式，当然这个过程应该是可逆的。通常落差很大意味着有很多值在零值附近，通过量化就可以变成一个有很多零值的稀疏矩阵。
量化过程可以理解为把数组中所有的值除以一个数N，这样小于N的数就变成了0，而那些大数需要被传输的位数也降低了，其恢复过程为整个数组乘以N，那些在除法过程中被舍弃的位数就成了不可恢复的误差了。
常见的变换编码有DCT和小波变换。
熵编码，根据统计信息将频繁出现的符号用较少的比特表示，不经常出现的符号用较多的比特表示，进而达到对数据压缩的目的，而在此之前往往会通过游程编码重新排列数组，以使更多的零排在一起。这些排在一起的零将通过（run，level）编码，用一个符号表示。
显然最直接的熵编码算法是哈夫曼编码，但实际应用中的熵编码会更加复杂。

参考书籍：Iain E.G.Richardson 视频编解码器设计

ZoundryDocumentsudo fdisk -l 查看硬盘的分区情况

Disk /dev/sda: 120.0 GB, 120034123776 bytes
255 heads, 63 sectors/track, 14593 cylinders
Units = cylinders of 16065 * 512 = 8225280 bytes
Disk identifier: 0xed9fed9f

Device Boot Start End Blocks Id System
/dev/sda1 * 1 1275 10241406 7 HPFS/NTFS
/dev/sda2 1276 2580 10482412+ 7 HPFS/NTFS
/dev/sda3 2581 3885 10482412+ 7 HPFS/NTFS
/dev/sda4 3886 14593 86012010 f W95 Ext’d (LBA)
/dev/sda5 3886 3898 104391 83 Linux
/dev/sda6 3899 4090 1542208+ 82 Linux swap / Solaris
/dev/sda7 6497 14593 65039121 7 HPFS/NTFS
/dev/sda8 4091 6496 19326163+ 83 Linux

一般第一个硬盘用sda表示，第二个用sdb表示，sda1-3是主分区，sda4是扩展分区，而sda5-8都是这个扩展分区里的逻辑分区。
在Linux下一切都是文件，所以这些硬盘分区无论用的是Linux文件系统，还是Windows文件系统通通都表示为/dev目录下的一个文件。
但是不能直接访问这些文件，需要用mount把他们挂载到某个普通目录下先（一般为/mnt下某目录），Ubuntu桌面上你点击Places下的Windows分区图标时会自动把其对应的文件挂载到/media下，其效果就相当于手动运行
sudo mkdir /media/g
sudo mount /dev/sda7 /media/g .
但是当对应的Windows文件系统上有一些句柄没有被释放时（如Windows没有正常退出，或处于休眠状态），这个命令往往会失败。
这时需要强制mount，
sudo mount -t ntfs-3g /dev/sda7 /media/g -o force

也可以通过修改/etc/fstab来实现开机自动mount

sudo gedit /etc/fstab
针对每个分区加一行
/dev/sda7 /media/ent ntfs-3g force 0 0

使mount为readonly的分区可写
mount -o remount,rw /mnt/media

ZoundryDocumentsudo mkdir /usr/share/font/yahei
拷贝Windows下的雅黑字体到目录

更改权限
sudo chmod 555 /usr/share/fonts/yahei/*
建立字体缓存信息
cd /usr/share/fonts/yahei/
sudo mkfontscale
sudo mkfontdir
sudo fc-cache -fv

打开System,Preference,Appearance,在Font标签中把所有字体选为Microsoft YaHei, 如果是液晶显示器，在下面的Rendering中选择最后一个Subpixe smoothing（LCDs）。

在我的笔记本上字体显示效果改善非常的明显。

在英文环境下用gedit打开GB2312编码的文件会出现乱码，这时候可以先开一个gedit，然后点打开文件按钮，这时候会有一个Character Coding下拉框，选Add/Remove可以增加GB2312编码。

更新：运行gconf-editor找到gedit-2 在encoding中的auto_autodetected增加一行GB2312并上移置顶。

ZoundryDocument运行级别（runlevel）其实就是把开机运行的程序分一个组，比如规定在runlevel 3运行的程序包括gdm（gnome的桌面管理器），runlevel 2里不包括，这样当以runlevel 3开机会进入图形桌面的，而runlevel 2开机则进入字符终端。
Unbutu弱化了运行级别这个概念。它的2－5级别运行的程序是完全一样的。而且传统linux上的/etc/inittab文件在Ubuntu上也消失了，取代它的是/etc/event.d/，这是Ubuntu上用的服务管理工具upstart的配置文件。
所有类似Windows的服务的程序都在/etc/init.d/下，而/etc/rc*.d里是对应运行级别下的服务，一般都是链向对应/etc/init.d目录下的链接。
通过runlevel命令查看当前运行级别。Ubuntu默认运行级别是2。进入/etc/rc2.d，这些就是当前运行服务了，可以看到有一项S30gdm，S表示运行，换成K表示停止，30是顺序数，gdm是gnome的桌面管理器，所以默认Ubuntu是以图形界面登录的。如果希望以字符界面登录，然后以startx手动开启图形界面，可以通过sudo mv /etc/rc2.d/S30gdm /etc/rc2.d/K88gdm 让gdm不开机自动启动。

sudo telinit 3 切换运行级别到3

xinit是启动图形桌面的主要程序。
startx只是设置一下变量路径后，调用了xinit。
# whereis startx
startx: /usr/bin/startx /usr/share/man/man1/startx.1.gz
# vi /usr/bin/startx
可以看到x的配置文件位置
userclientrc=$HOME/.xinitrc
sysclientrc=/etc/X11/xinit/xinitrc
userserverrc=$HOME/.xserverrc
sysserverrc=/etc/X11/xinit/xserverrc
defaultclient=xterm
defaultserver=/usr/bin/X

在还没启动图形桌面的时候可以通过xinit firefox开一个没有桌面管理支持的firefox,Ctrl+Alt+F1返回。

Ctrl+Alt+F1，F2，……
切换窗口会话
Ctrl+Alt+F7回到图形桌面

Crtl＋Alt+Backspace关闭图形桌面。