一种基于“陷门收缩”原理的公钥算法

邱培呸呸呸

择要：本文主要介绍一种基于“陷门收缩”原理的公钥算法，给出了私有密钥的构造方法，并对密码长度、保密强度进行了分析。

关键词：加密  解密  陷门收缩 算法


1．引言
   计算机网络技术使信息科学得到了飞速发展，同时也带来了一系列数据安全问题，需要有高强度的加密安全措施才能保证其安全。近年来，密码技术有着突飞猛进的发展，密码学的研究十分活跃，出现了众多公钥密码系统。本文设计了一种基于“陷门收缩”原理的一种公开密钥密码算法，给出了私有密钥的构造方法，并对密码长度、保密强度进行了分析。

2．设计思想
   根据Merkle和Hellman提出的经典陷门收缩算法的基本思想，“背包问题”在不知道“陷门信息”的情况下是难以计算求解的，如果知道了“陷门信息”，则求解就变得容易了。
    本文算法的私有密钥(解密密钥)是在数论的“陷门收缩”理论基础上由随机产生加复杂构造而生成，符合“收缩”计算规律，并利用陷门原理，由私有密钥导出公有密钥(加密密钥)。加密时根据公有密钥由明码导出密码；解密时，利用陷门原理，由密码及关键数导出中间密码，并根据私有密钥收缩求出明码。
    本算法的一般数学描述为：
    设X为明码
       为密码
       为中间密码
       为公有密钥 (公开)
       为私有密钥 (保密)
    加密过程：
    解密过程：①
              ②
    在密码分析的攻击中，密钥占有极其重要的地位，由于公开密钥密码体制自身的特点，私有密钥的设计成为该密码体制中的关键技术。本文所述的关键是以“陷门收缩”理论为基础构造产生出符合收缩计算规律的私有密钥。私有密钥的构造产生方法，体现了本算法的特点，使该算法具有较高的保密强度。

3．本算法的原理与方法
3.1  算法中用到的一些变量及私有密钥的构造原理
(1)设要求加密的数据为X(明文)，即
     ,    ∈(0，1)
    (2)关键数据r，t，s满足
      ①(r，t)＝1
      ②r>t
      ③t•s(mod  r)＝1
    (3)设计构造一组私有密钥(解密密钥) 使其满足
      ① ,   =2，3，…，64
      ②r>
    算法中应将r，s，t， 私有保存。
    (4)求一组加密密钥  (公开)，使其满足
           •t(mod  r)
3.2  加密过程
           密文：
3.3  解密过程
       (1)求关键数s，因为
          s•t(mod  r)＝1
          (r，t)＝1
    所以可利用欧几里得算法求得s。
       (2)求中间密码 ，有
           •s(mod  r)
       (3)收缩求解 ，有
            
                  1      当 时   
       即                  
0      其它

                 1      当 时
                                             ( =n-1,n-2,…,3,2,1 )  
0         其它


4.  私有密钥的构造与密码长度分析
4.1  私有密钥的构造
私有密钥的设计构造是本文的目的和重点，也是实现本算法的关键。假设一个明码的长度为64bit，即为  ( 为0或1)，私有密钥 的个数应与明码的长度相等，即i=64。由数论中的收缩理论可知私有密钥  应满足如下公式：
             =2，3，…，64
    因此对私有密钥可进行如下构造：
    (1)产生一组随机整数 ，0≤ ≤64
    (2)构造  ，    1≤n≤65
使 满足   ，为符合收缩计算规律的私有密钥。它是由困难的收缩问题转换为易解的收缩问题，求解明码X的关键所在， 也是算法的核心所在。对于掌握了私有密钥的人来说解密容易，而对于局外人，不知道私有密钥则求解却十分困难，包括解密与求解该私有密钥。

4.2  密码长度分析
    如前所述私有密钥 是由64个随机数  (0≤ ≤64)，根据
              =2，3，…，64
    的理论按照公式   构造产生出来的，即：
           
    由于 ≤64，其最大值为 =64，据此可分析 可能达到的最大值。
因为
    那么取 =64，则
         
    因为r>
    又因为
    所以取r＝
    已知 r-1
         
           
           •(r-1)
           
由此可知密文的最大长度可能达到 ， 因此加密后的密码长度将大于或等于明码长度(64bit)，因此若加密过程中每次从文件中取8个字节长的明码进行加密，那么解密过程中就要每次从加密后的文件中取10个字节长的密文进行解密。

5. 算法的保密强度分析
5.1  密码体制的安全性
    密码体制的安全性在于：一是密钥的管理。包括密钥的产生、选择、传递、改变以及取消等安全措施。二是加密、解密算法的设计。即使已知明文X 和相对应的密文Y，甚至掌握了加、解密算法本身，也很难计算出密钥来， 因而就不可能根据未被破译的密文，得到原来的明文。由此可知，密码体制的保密性应取决于对密钥的保密，而不是算法的保密。这是一个好的密码体制所应该具备的特征。公钥密码体制正具备这样的优点：它公开加密算法和加密密钥，只对解密密钥进行保密。
    密码算法要能够挫败对方的攻击，必须使明文成为密文和密钥的一个足够复杂的数学函数，并使每个密钥成为密文和明文的一个足够复杂的函数。对于公钥密码体制来说，一般保密强度是建立在一种特定的已知问题求解困难这个假设之上的。如RSA公钥密码和背包公钥密码， 前者其密码强度建立在具有大素数因子的合数因子分解困难这个著名的数学难题之上，后者其密码强度建立在著名的古典背包问题的数学难题之上。因此，公钥密码算法本身就应具有较强的保密强度。
对于密钥，由于其在密码分析攻击中占有极其重要的地位，而公钥密码又只对其解密密钥进行保密，因此密钥的设计和保护就成为该加密体制的关键技术。5.2  算法的保密强度分析
    一般来说，对密码的破译方法有两种手段：一是采用频率分析法(即穷举法)，即以借助机器来试验可能的取值；二是采用对密文分析的手段，即找到密文中的一些特殊性，或在掌握了部分明文的基础上对密文进行分析。
     对于本算法采用第一种破译手段是不可行的， 由于该算法明文 的长度为64bit，则可能的X取值有
                  
若对X的每一取值计算 ，并将结果与密文 比较，若相等，则 就是所求。 假如用一台每秒作10亿次运算的处理器，进行上述算法的穷举试验的时间复杂性是Ｏ( )，所花费的机器时间需要约21296天，即大约58年的时间。若用1000个处理器，则需要21天，因此这种破译方法显然不切实际的。
    对于本算法采用第二种破译手段也是无效的。首先该算法即不是“变形”密码也不是“变位”密码，其密文不存在“变形”和“变位”特性：其次通过密码分析获知的信息来得知X成为计算上的不可行。 本算法是基于一种特定的陷门单向函数，利用秘密陷门信息 ，r，s，t，使公开密钥 不能为破译密文提供信息，在不知道 陷门信息的情况下，仅根据已知的 和加密算法，用求逆的方法求解 将会遇到特定的计算难题，在多项式时间内无解，并且至今尚无有效的求解算法。
    对于密钥的攻击，由于该算法的私有密钥(解密密钥)   ( =1，2，…，64) 的最大长度可达 ，因此， 由上述可知用穷举法来求解该算法的私有密钥是不可行的，64个私有密钥穷举其中一个，可能取值就有
      
其次该算法的私有密钥具有随机和构造双重性质，想通过已知的公钥 来推导出 也是不可能的。
       ≡ •t(mod  r)
       是随机产生加构造而确定
               ( 为随机整数)
      最大长度可达 bit，穷举法无效。
    r>
    r>t  ，且(r，t)＝1
且 ，r，t都是保密的，因此无法由 •t(mod  r)求解出 。

6．结束语
本文基于“陷门收缩”原理的公钥算法，是以经典的陷门收缩算法为依据经改进而提出的一种公开密钥密码算法。它除具有公钥密码的一般优点外，还具有以下特点：以坚实的数论理论和密码学理论为基础，具有充分的理论依据和较高的可靠性，私有密钥具有随机性和复杂构造性，从而提高了私有密钥的保密强度和算法的安全性。

参考文献
1．[美] Bruce Schneier.《应用密码学（协议、算法与C源程序）》.机械工业出版社,2000.2
2．卢开澄.《计算机密码学》.清华大学出版社,1999.8