【主讲人】樊海宁 副研究员

    樊海宁，清华大学计算机科学与技术系博士，加拿大University of Waterloo 博士后，清华大学软件学院副研究员。

【时  间】2008年4月3日 14:00-16:00

【地  点】软件学院217教室

【主  题】算法设计的两条基本原则（平衡和分治）在GF(2^n)密码芯片设计中的应用

【摘  要】平衡和分治是算法设计的两条基本原则。本讲座分两部分来加深大家对这两条原则的印象，同时将提出几个问题供大家思考。

    第一部分介绍经典的分治算法——Karatsuba算法（1962），就是那个首次突破O(n^2)界的整数乘法算法。讨论将不以整数乘法为背景，而以GF(2)[x]中两个多项式相乘为背景（即系数为0或1，系数间的加法和乘法运算均模2的两个多项式相乘），介绍Karatsuba算法背后的一般原则——孙子定理。对于GF(2)[x]中的乘法，将提出两个问题供大家考虑。例如：如何找出所有只使用6次乘法计算(ax^2 + bx + c)(dx^2 + ex + f)的公式?

    第二部分介绍平衡原则的一个典型应用：GF(2^n) VLSI 乘法器设计。简单讲，GF(2^n)乘法定义为GF(2)[x]中两个n-1次多项式乘积模一个GF(2)[x]中n次不可约多项式后所得的剩余。系数间的加法和乘法分别对应异或门（XOR）和与门（AND）。而GF(2^n)乘法器设计就是只用2输入异或门和与门来实现GF(2^n)乘法。同样，也将提出问题供大家考虑。

【背景介绍】

    有限域GF(2^n)在密码和信道编码等领域有着广泛的用途。实际应用中的信道编码算法大多在GF(2^n)上构造。密码体制可分为对称密钥密码体制和非对称密钥密码体制，前者的典型代表是美国在2001 年选定的AES（Advanced Encryption Standard），AES 的基本操作是基于有限域GF(2^8)；而作为目前的主流非对称密钥密码体制，椭圆曲线密码体制可同时在GF(p)和GF(2^n)这两类有限域上构造，GF(p)就是大家熟知的整数模素数p所得的域。为满足安全性的要求，通常p 和n 分别满足 p>2^100 和n>100。在相近的参数条件下，即p≈2^n，GF(p)和GF(2^n)上的椭圆曲线密码系统具有相近的安全性，但因为GF(2^n)上加法和平方运算更加简单(比整数加简单)，所以GF(2^n)密码芯片的电路门数量和门延时均小于对应的GF(p) 密码芯片。以上特点使GF(2^n)密码芯片得到较GF(p)芯片更广泛的应用，特别是在计算资源有限的应用系统中，例如智能卡和PDA（Personal Digital Assistant）等。

联系人：   刘旸，liu_yang06@mails.tsinghua.edu.cn