基于背包问题的单向壳核函数的研究

作     者：于洁 

作者单位：吉林大学 

学位级别：硕士

导师姓名：赵永哲

授予年度：2018年

学科分类：08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：背包问题 单向壳核函数 半陷门单向壳核函数 公钥密码 半超递增背包向量 

摘      要：在即将到来的量子时代,由于量子计算机具有高速的并行计算能力和强大的模拟能力,目前所使用的多数公钥密码日益受到量子计算机的威胁,一旦量子计算机研制成功,这些密码将很快被破解。2017年5月3号,由中国科学技术大学潘建伟教授带头研发的光量子计算机的诞生,标志着中国正式进入了量子计算机发展的行列。所以,研究出抗量子计算的密码成为当务之急。众所周知,量子计算机不大擅长计算NPC问题,因此基于NPC问题来构造密码方案成为后量子密码研究的主流。而背包问题就是典型的NPC问题。纵观所有的背包密码方案,可发现它们都是基于陷门单向函数来实现的,但由于陷门性和单向性的固有矛盾,使得基于陷门单向函数的公钥密码存在安全隐患。为此本文引入单向壳核函数的概念,即采用“一壳一核的构造手段来进行伪装。单向壳核函数有效地解决了陷门单向函数存在的边界泄露问题,增强陷门的安全性,所以基于单向壳核函数的公钥密码安全性更高。但目前对于单向壳核函数的研究都偏向于硬件实现,为了探索纯数学的实现方案并使其公钥密码能抵御量子攻击,本文在背包问题的基础上进行单向壳核函数的构造。本文将研究重点放在基于背包问题构造单向壳核函数上,利用单向壳核函数实现非对称的密钥交换,从而可得到一种新的公钥密码构造方法,即基于单向壳核函数的公钥密码。基于背包问题的困难性,对单向壳核函数以及相应的非对称密钥交换进行设计实现,由此可得到新的背包密码方案。本文的主要工作以及研究成果如下:1.根据相关资料文献,对密码学发展历程以及背包密码的国内外研究进展进行了系统的阐释,同时对背包密码相关定义、定理、安全性进行分析证明。2.分析单向壳核函数实现密钥交换的多种方案,给出最优的密钥交换方案,即KEP-SC。KEP-SC是可剥壳的壳核函数和不可剥壳的壳核函数的有效结合。此方案可以约定会话密钥,并能有效地隐藏函数边界,让攻击者无从下手。3.基于背包问题构造单向壳核函数,并给出KEP-SC的具体实现方案。随后针对方案存在的缺陷,提出优化、改进的密钥交换方案。4.在KEP-SC方案的基础上,利用“半陷门单向函数,对原方案中壳函数进行重构,得到新的密钥交换方案Half-KEPC。基于“半超递增背包向量,构造出半陷门单向壳核函数,进而得到Half-KEPC的一个具体实现方案。