基于分治的子集积问题DNA计算机算法

如何减少DNA计算机在求解大型科学问题中以问题输入纯指数增长的DNA链数,已成为DNA计算机研究的重要内容。本文将分治策略应用于子集积问题的DNA分子计算中,提出一种求解子集积问题的新的DNA计算机算法。该算法由n位数据搜索器和其它五个子算法组成,其DNA链数可达到亚指数的O(2q/2),其中q为子集积问题的维数。与最近文献结论进行的对比分析表明:新算法将求解子集积问题所需的DNA链数从O(2q)减少至O(2q/2),最大链长度减少为原来的1/2。因此,利用新算法在试管级水平上能将可破解的子集积公钥的维数从60提高到120。

基于REESSE1＋公钥密码体制的概率加密

针对确定性公钥密码体制不能抵抗选择明文攻击的弱点,基于REESSE1+公钥密码体制设计2种概率加密方案,使同一明文对应的密文具有不确定性。方案1在明文比特序列的奇数位置插入相同长度的随机比特串,产生新的随机明文序列,并对该序列进行加密;方案2对公钥序列进行重新排列,使用新的公钥序列对明文进行加密。证明2种方案的正确性,并对其安全性和性能进行分析,结果表明,2种方案均可抵抗选择明文攻击,密码强度至少等价于基于离散对数问题的密码方案,同时,其加解密运行时间均少于基于RSA和剩余问题的概率密码方案。