改进的GPS模糊度降相关LLL算法

模糊度降相关技术可以有效提高模糊度求解的效率及成功率,LLL(A.K.Lenstra,H.W.Lenstra,L.Lovasz)算法是新出现的模糊度降相关方法。详细分析LLL算法,针对该算法中存在的缺陷,提出逆整数乔勒斯基、整数高斯算法和升序调整矩阵辅助的改进LLL算法。利用谱条件数及平均相关系数为准则,以300个随机模拟的对称正定矩阵作为模糊度方差-协方差矩阵,对LLL算法和改进的LLL算法进行仿真计算。比较与分析结果表明,改进LLL算法模糊度降相关处理更加彻底,能有效地加速整周模糊度搜索及成功解算。

MIMO系统LLL格基约减检测技术研究

针对LLL格基约减算法应用在MIMO系统检测中计算复杂度高,理论和实验分析了LLL算法中影响列交换条件的参数δ对计算复杂度和正交缺陷的影响,同时结合ZF和VBLAST检测技术实验分析了参数δ在MIMO信号检测系统中对误码率性能的影响。数值结果与分析表明:在MIMO检测系统中LLL算法参数δ=0.75为最佳值。

Lovász条件下LLL算法最简复Givens矩阵形式的研究

为了解决复数域下基于QR分解的LLL(A.K.Lenstra,H.W.Lenstra and L.Lovász)算法中复Givens旋转矩形式不统一的问题,文章从复数域下原始LLL算法中Gram-Schmidt系数与QR分解的上三角矩阵R中元素之间的关系出发,证明了上三角矩阵R的元素与Gram-Schmidt系数以及Lovász条件之间的等价的关系;从复数的指数形式出发,推导出2种适合LLL算法的复Givens旋转矩阵形式,并证明只有其中一种符合Lovász条件下复Givens旋转矩阵形式。仿真结果表明,采用基于QR分解的复数域LLL算法的MIMO系统相比采用基于Gram-Schmidt正交化LLL算法的MIMO系统具有更好的误比特率性能。

基于Gauss和LLL规约的新型格基规约算法

格是多维空间中点的规则排列,基于格的公钥密码体制是密码学中研究的热点。针对传统格基规约算法效率较低、消耗时间较长的问题,分析Gauss和LLL规约算法,在此基础上提出一种新型格基规约算法(Gauss-LLL),对算法进行正确性验证,并给出实现伪码。该算法可对格的任意一组基进行规约,最终获得一组长度较短的规约基。分析结果表明,与LLL算法相比,Gauss-LLL算法得到的规约基较优,规约效率较高。

并行LLL算法研究综述

Lenstra-Lenstra-Lovasz(LLL)格基约化算法自1982年被提出以来,已被成功应用于计算机代数、编码理论、密码分析、算法数论、整数规划等众多领域。经过三十多年的发展,串行LLL算法的理论分析和实际效率都已得到显著改进,但仍不能满足密码分析等领域处理较大规模问题的需要。因此,并行LLL算法研究被寄予厚望。对并行LLL算法的研究现状进行了综述,总结了当前并行LLL算法设计与分析中存在的问题和难点,并对其未来发展趋势进行了展望。

MIMO系统中改进的LLL格基约减算法

针对传统LLL格基约减算法在MIMO系统中的误比特性能较差的问题,提出了一种改进的LLL检测算法。该算法利用后向LLL约减算法和同时对多个初始基进行约减的思想,从问题的多组初始基开始搜索,并对多组初始基进行约减,找到其中最好的一组基,摆脱了传统格基约减算法仅从单组基开始搜索的局限。通过理论分析和计算机仿真,对算法的收敛性及不同收发天线数下不同检测算法的误比特性能进行了对比研究。结果表明,在MIMO系统中本文算法的检测性能比传统的格基约减算法更优,且更接近于ML检测算法。

基于LLL算法的永久散射体差分干涉相位解缠

概述了永久散射体差分干涉相位模型以及基于LLL方法的整数最小二乘解算,并用模拟数据对其进行了检验,证明了LLL方法的正确性和可行性,为进一步研究优化LLL算法奠定了基础。

LLL算法及应用

LLL算法是很多数论算法的重要组成部分,在计算数论领域中起着相当重要的作用。它是由A.K.Lenstra,H.K.Lenstra和L.Lov.asz于1982年提出。介绍了LLL算法的相关定义及LLL约减基的性质,通过一个具体例子来说明LLL算法在计算数论中的重要应用。

RSA及其变体算法的格分析方法研究进展

格分析是一种利用格困难问题的求解算法分析公钥密码安全性的分析方法,是研究RSA类密码算法安全性的有力数学工具之一.格分析的关键在于构造格基,虽然目前已有通用简洁的格基构造策略,然而,这种通用方法无法充分、灵活地利用RSA及其变体的代数结构.近年来, RSA类算法的格分析工作大多在通用策略的基础上引入特殊格基构造技巧.首先介绍了格分析方法以及通用格基构造策略,并总结提炼了几种常用格基构造技巧;其次,回顾了标准RSA算法格分析的主要成果,即模数分解攻击、小解密指数攻击以及部分私钥泄漏攻击;然后,总结了几种主流RSA变体算法的特殊代数结构,及其适用的特殊格基构造技巧;最后,对现有RSA及其变体算法的格分析工作进行了分类总结,并展望了格分析方法的研究与发展方向.

基于遗传策略的格基约化算法

格基约化算法是密码分析的重要工具。该文借鉴遗传算法的基本策略,通过对初始格基的调整变换,提出了一种新的格基约化算法,新算法总能得到给定格中长度更短的向量和质量更高的一组基。利用该算法,针对最短向量问题(SVP)挑战的部分数据进行了测试,新算法的输出结果达到或超过了挑战的公开记录,约化效果良好。

对一种改进RSA算法的密码分析

运用Jochemsz和May寻找多项式小根的技术对RSA改进算法——客户端辅助RSA(CA-RSA)算法进行攻击,可以对CA-RSA算法实现基于LLL格归约算法的密码分析.通过分析含有两个私钥指数的CA-RSA算法的安全性,得到当两个私钥指数小于大数模N的1/12次幂时,CA-RSA算法能在多项时间内被有效破解.

基于中国剩余定理的公钥加密方案同态性

针对现有(全)同态加密方案的整体性能不能达到实用要求的问题,为获得新的性能更好的同态加密思路,对基于中国剩余定理(CRT)的快速公钥加密方案的同态性进行了研究。考察了基于原方案构造加法和乘法同态操作的可能性,指出基于原方案不适于构造加法同态操作和乘法同态操作,并分析了原方案在安全性和效率方面存在的几个问题。。提出了一个改进方案,分析了算法的安全性,尤其是对抗格基规约攻击的性能。研究了基于改进方案构造同态操作的可行性,并对原方案和改进方案的主要性能作了对比。最后对同态性构建过程中的经验进行了总结,提出了构建理想(全)同态加密方案的思路。

采用格基规约算法的空间调制检测方案

空间调制是未来5G蜂窝通信系统的物理层备选技术之一,为研究LLL、嵌入式两种格基规约算法对空间调制技术的影响,设计了两种检测方案,分别为LLL辅助MMSE检测方案和嵌入式检测方案.在不同的调制符号、不同的天线数目下,通过仿真比较两种检测方案的误比特率性能.然后通过矩阵运算理论对两种检测方案的运算复杂度进行分析,为使分析结果更直观,在不同天线数目下,对两种方案的运算复杂度进行了仿真.理论分析和仿真结果表明,嵌入式检测方案在误比特率和运算复杂度两方面均优于LLL辅助MMSE检测方案,它更适用于空间调制技术.

格基归约在密码上的应用

文中详细综述了格基归约在密码学中的应用 ,并从分析与设计两方面进行了论述 .在密码分析方面的应用主要对线性同余截尾序列进行了分析和论述 ,在密码体制设计上主要介绍了NTRU公钥密码体制 ,对其安全性进行了分析 ,并与其他体制进行了比较 .

对一类RSA变体的攻击

讨论RSA公钥密码体制在素因子p满足等式ex+by+c≡0(mod p)条件下的安全性,研究了对其格攻击的方法。利用方程小根求解问题对其进行攻击,攻击结果表明:当参数x,y满足|x||y|<N3β-3+(2β+1)1-β-ε时,通过格攻击方法可以有效的分解N,即满足这样条件的RSA公钥密码体制是不安全的。

基于格的RSA密码分析

格在公钥密码分析领域中有着十分重要的地位.1996年,Coppersmith以多项式方程求小值解的问题为桥梁,把攻击RSA密码体制的问题转换为求格中短向量的问题,开辟了基于格的RSA密码分析的研究,他的工作也在后人的简化完善下逐渐形成了Coppersmith方法.一方面,关于基于格的Coppersmith方法,依次介绍了模多项式方程求小值解的方法、整系数多项式方程求小值解的方法、求解近似公共因子问题的方法,还简单描述了除Coppersmith方法外的一种在低维格中寻找最短非零向量的格方法.另一方面,关于RSA密码分析,回顾了小加密指数攻击、小解密指数攻击、部分私钥泄露攻击、求解私钥d与分解模数N的等价性证明、隐式分解问题的分析、素因子部分比特泄露攻击、共模攻击等,并且以Prime Power RSA,Takagi's RSA,CRT-RSA,Common Prime RSA为例,介绍了格方法在RSA密码变体分析中的应用.

基于格基约减辅助的低复杂度MIMO信号检测算法

在多输入多输出(MIMO)系统中,常规的格基约减辅助信号检测算法由于复杂度高而难以在实际工程中应用。为了解决这一问题,基于Brun算法提出了一种低复杂度的信号检测算法。该算法首先通过奇异值分解(SVD)得到信道矩阵奇异向量和转换矩阵之间的近似整数关系,进而采用Brun算法对信道矩阵的对偶格基进行约减优化,最后将约减后的新对偶格基用于传统线性信号检测。仿真结果表明:该方法的复杂度约为基于常规Lenstra Lenstra Lovasz(LLL)格基约减辅助的MIMO信号检测算法的0.1倍;同时,与线性检测算法相比,检测性能提升非常明显,特别在较高信噪比(SNR)范围内。因此,该算法能够在检测性能与计算复杂度之间取得较好的折衷。

对RSA的部分密钥泄露攻击

记N=pq为n比特RSA模数,e和d分别为加解密指数,v为p和q低位相同的比特数,即p≡qmod2v且p qmod2v+1.考察了基于格基约化理论的对RSA的部分密钥泄露攻击.证明了当v和ed均较小且解密指数d的低n/4比特已知时,存在关于n和2v的多项式时间算法分解N.

对RSA的部分密钥泄露攻击

记N=pq为n比特RSA模数,e和d分别为加解密指数,ν为p和q低位相同的比特数,即p≡qmod2ν且p qmod2ν+1。1998年,Boneh、Durfee和Frankel首先提出对RSA的部分密钥泄露攻击:当ν=1,e较小且d的低n/4比特已知时,存在关于n的多项式时间算法分解N。2001年R.Steinfeld和Y.Zheng指出,当ν较大时,对RSA的部分密钥泄露攻击实际不可行。本文的结论是当ν和e均较小且解密指数d的低n/4比特已知时,存在关于n和2ν的多项式时间算法分解N。

一种新型的RSA密码体制模数分解算法

为了提高RSA密码分析效率,提出了一种新的针对RSA密码体制的大整数分解算法.根据Coppersmith定理,利用LLL算法可以在多项式时间内求解非线性低维度多项式方程的小整数解问题.该算法基于格基规约LLL算法,对参数满足e_ix-y_iφ(n_i)=z_i这一多项式方程的情况进行了研究,其中e为加密指数,n为模数,x,y_i为小整数系数.与传统的数域筛法、Monte Carlo方法和椭圆曲线法相比,该大整数分解方法计算复杂度更低.还利用该密码分析方法进行了大整数模数分解.