关键词:
有限域
多项式运算
形式化方法
定理证明
Coq
加密
形式化验证
摘要:
有限域GF(2~n)是多种安全关键性算法的基础,它在AES加密算法,椭圆曲线加密,感染函数掩码等领域有重要作用。有限域上的运算因为自身的复杂性而容易出错,这些错误容易导致系统产生问题。基于测试和基于模型检测的验证方法只能在n固定的特定有限域上进行验证,当n很大时,很难取得有效而全面的验证。基于交互式定理证明器的形式化验证为有限域性质的通用验证提供了可能性,而这有助于有限域上运算的验证,但这方面的工作难度比较大。基于定理证明的验证方法的工作过程和数学定理的证明过程类似,首先需要建立一组定义并证明一批引理,之后在这些前置工作的基础证明最终目标,因此首先需要完成相应的数学理论在定理证明器中的形式化,构建相应的形式化的数学理论库。本文的主要目标是建立在对有限域GF(2~n)的一个形式化数学库,包括对有限域相关概念进行构造性定义,并在构造性定义的基础上对域的一些性质进行形式化验证。针对这些问题,本文借助定理证明器Coq,对有限域GF(2~n)上元素及其基本运算进行了形式化定义,并且对一组同有限域有关的基本性质进行了形式化验证,包括有限域加法基本性质验证、有限域乘法部分性质的验证。这项工作为有限域的完整的形式化,以及基于有限域的算法的形式化验证打下了一个基础。本文考虑了多种方法来实现对有限域进行形式化验证,主要的研究成果如下:第一,本文完成了一个特殊的有限域GF(2~8)的形式化定义,并在此基础上进行了完整的形式化验证。这个有限域主要用于AES算法,是AES算法形式化验证中的一个难点。之后本文将所验证的性质进行了扩展,并以此完成了AES算法的形式化验证中有难的列混淆部分的验证。第二,针对前面工作只针对某一特定有限域展开的局限性,本文以一种归纳结构作为有限域GF(2 ~n)上元素的载体,以递归为主要手段在完成了有限域GF(2~n)上运算的形式化定义。这种方式完成的定义适用于任意大小任意结构的有限域GF(2~n)。第三,本文对有限域GF(2~n)的相关性质进行了形式化验证。在加法方面,完成了对加法交换律,结合律,单位元,逆元等基本性质的形式化验证。乘法方面,由于直接验证很困难,本文分成了几个部分来做。目前完成了构成有限域GF(2~n)乘法的多项式乘法相关性质和取模运算部分性质的形式化验证。并在此基础上完成了有限域乘法部分性质的形式化验证。本文主要通过归纳的方法进行验证,验证的性质适用于任意大小任意结构的有限域GF(2~n)。本文研究所形成的形式化数学库也可以为其它研究提供帮助。