背包公钥论文：背包公钥 非超递增序列 逆向构造算法 新型密码体制.doc

背包公钥论文：背包公钥 非超递增序列 逆向构造算法 新型密码体制【中文摘要】网络和信息安全正在成为一个国家政治、军事、经济以及社会生活正常运行的基础,它将是一个国家综合实力的重要体现。而密码学是信息安全的核心。公钥密码又是将加密、解密密钥甚至加密、解密函数分开,用户只保留解密密钥,而将加密密钥和加密函数一起公之于众,是密码学的重要组成部分。背包公钥和RSA一样是著名的公钥体制之一,特别是背包公钥的安全基础是背包问题,这是一个NP难问题。虽然在提出不久就遭到破解,但是在提出的背包公钥系统的改进方案中依然有几个被证明是安全的。背包公钥是首个把NP问题用于公钥密码的密码体制,而其他现阶段应用的公钥密码体制都是基于因式分解或离散对数问题的,他们都不是NP问题构造的,因此背包公钥体制的研究是十分有意义的。本文从背包体制的常用攻击方法入手,寻找被破解的原因,并针对这些原因提出了新的构造思路,利用非超递增序列构造背包体制。利用非超递增序列构造背包公钥有2个必须解决的问题是加密结果的不唯一性和解密的困难性。本文对一种同余多模背包序列进行分析,并利用得出的性质构造一种新的L序列,并证明了L序列能解决以上2个问题,并提出了利用L序列构造背包公钥体制的方案。为了加快加解密速度,还提出了模M和W-1的逆向构造算法。然后给出了非超递增背包公钥体制的模拟实现。【英文摘要】Network and information security is becoming a countrys political,military, economic and social life of the normal operation of the foundation. It will be a comprehensive national strength of the important embodiment. And cryptography is the core of information security. Public key cryptography is to separate the encryption key and the decryption key or encryption function and the decryption function. Users retain only decryption key,while encryption keys and encryption function together made public. Public key cryptography is an important part of cryptography.The knapsack public-key like the RSA is one of the well-known public key system. In particular the knapsack public-key is based on the knapsack problem. It is a NP-hard problem. Although the break was mode soon,in the improve of knapsack public-key system there are some which is proven to be safe. The knapsack problem is the first cryptography system which use the NP problem to the public-key cryptography. And the others at the application of public-key cryptography are based on factorization or discrete number issues. They are not the structural problems of the NP. So the research of knapsack public-key system is very meaningful.From the commonly used knapsack attacking method ,finds the reasons for the break,proposes new thought against the break,and makes use of non-super-increasing knapsack sequence construct the knapsack system. There are two prominent problems of using non-super-increasing sequence to construct knapsack scheme: encryption result is not unique and the difficulty of decipher. This article analysis one of the congruence multi-mode knapsack sequence,use it to construct a knapsack scheme, proves that the L sequence can solve the above two problems and propose a plan to use the L sequence to construct a new knapsack public-key system. To speed up the encryption and decryption speed,The article also propose the reverse construction algorithm of m and w-1. Finally this article give the stimulant implementation of non-super-increasing knapsack scheme.【关键词】背包公钥 非超递增序列 逆向构造算法 新型密码体制【英文关键词】Knapsack public-key non-super-increasing sequence reverse construction algorithm new cryptosystem【目录】新型背包公钥体制研究摘要4-5Abstract5第一章 绪论8-111.1 课题研究背景及意义8-91.2 本文所做工作9-101.3 论文的研究成果101.4 论文的安排10-11第二章 公钥密码11-252.1 公钥密码的原理11-122.2 公钥密码的数学基础12-162.2.1 数论基础知识13-142.2.2 陷门单向函数142.2.3 大整数分解问题FAC（Factorization Problem）14-152.2.4 离散对数问题DLP（Discrete Logarithem Problem）152.2.5 丢番图方程问题（Diophantine Equation problem）15-162.2.6 背包问题（Knapsack Problem）162.3 公钥密码的的应用和优缺点16-242.3.1 密钥管理16-202.3.2 公钥密码的优缺点20-212.3.3 认证和数字签名21-242.4 本章小结24-25第三章 背包密码体制25-353.1 背包公钥密码体制的发展253.2 部分典型的背包公钥密码体制25-303.2.1 Merkle-Hellman 背包密码体制26-273.2.2 多次迭代MH 背包体制273.2.3 基于加法实现的背包体制27-283.2.4 基于孙子定理的背包体制28-293.2.5 拆分型背包体制29-303.3 背包系统的分析和攻击30-343.3.1 加密方案攻击30-313.3.2 Shamir 对MH 背包体制攻击31-323.3.3 LLL 格规约基算法32-343.3.4 低密度攻击343.4 小结34-35第四章 新型的背包公钥体制35-454.1 新型背包公钥体制的基本思路35-364.2 多模编码序列及其性质36-394.3 一种非超递增背包体制39-404.4 背包公钥模M 与逆元W-1的逆向构造40-414.5 利用L 序列来构造背包公钥密码体制41-434.5.1 密钥的生成41-424.5.2 加密过程424.5.3 解密过程42-434.6 安全性初步分析43-444.6.1 低密度子集和攻击434.6.2 解密速度43-444.6.3 可证明安全性讨论444.7 小结44-45第五章 系统的实现和调试45-575.1 实现的界面说明45-475.2 关键部分的流程和代码47-555.2.1 大数运算47-495.