当前位置：文档之家 › Why You Cannot Even Hope to Use Grobner Bases in Public-Key Cryptography An Open Letter to

Why You Cannot Even Hope to Use Grobner Bases in Public-Key Cryptography An Open Letter to

  • 格式：pdf
  • 大小：114.33 KB
  • 文档页数：7

WhyYouCannotEvenHopetoUseGr¨obnerBasesinPublic-KeyCryptography?AnOpenLettertoaScientistWhoFailedandaChallengetoThoseWhoHaveNotYetFailed

[PublishedinJournalofSymbolicComputations18(6):497–501,1994.]BooBarkee,DehCacCan⋆,JuliaEcks,TheoMoriarty,andR.F.ReeProf.B.Barkee⋆⋆MathematicalScienceInstitute,CornellUniversity,IthacaNY14853100142.3240@compuserve.com

InthemagicalartofSteganography,thereisnothingfrivolous,norcontrarytotheGospelsandtheCatholicfaith;norhavewetaughtsuperstitiousbeliefs.Everythingisbasedonnatural,lawfulandhonestprinciples;themysterywhichveilsthepreceptsofthisartandthenamesofthespirits,requiresacultivatedreader;tohidethesecretsofthisart,whichcouldbeharmfulifmadeknowntowickedmen,weavailourselvesoftheservicesofthespirits.

JohannesTrithemius,Steganographia

Theairisinfluencedbyastralemanations.Soonecan,naturallyandwithoutspiritualhelp,communicatehisthoughtstoanotherman,how-everlargethedistancebetweenthem.ThisIhaveseendone,IdidmyselfandwasdonebyTrithemius...Inthesameway,onecanbroadcastintheairanyimage,howeverfar,bymeansofmirrors...Theimagewillbe,throughlargedistances,seenbyaconsciousreaderinthelunardisc;thisartificewasusedbyPythagoras.

H.C.Agrippa,DeOccultaPhilosophia

It’sbettertohavelovedandlostthantohavelikedandtiedforsecond.

Anonymous

DearDeludedAuthor,YouareproposingtousethefactthatGr¨obnerbasesarehardtocomputetodeviseapubickeycryptographyscheme.Wearefirmlyconvinced,instead,thatnoschemeusingGr¨obnerbaseswilleverwork.Thefollowingnotesareanattempttoexplainwhy.2BooBarkee,DehCacCan,JuliaEcks,TheoMoriarty,andR.F.ReeLetusstartbyrecallingthebasicfactsrelatedtoGr¨obnerbases(cf.[B],[BWK]).OnehasanidealI⊂k[X1,...,Xn](wherekisafield)andawell-orderingcompatiblewithproductonthesemigroupTofterms(monicmono-mials)ink[X1,...,Xn].Thisorderingallowstorepresentuniquelyeachf∈k[X1,...,Xn]asanorderedlinearcombinationofelementsofT:

f=r󰀂i=1citici∈k\{0},ti∈T,t1>···>tr

sotoeachnon-zeroelementf∈k[X1,...,Xn],wecanassociateT(f):=t1,themaximaltermoff;itscoefficientc1iscalledtheleadingcoefficientoffanddenotedlc(f).Moreover,theorderingallowstoassociatetotheidealIthesemigroupidealT(I):={T(f)∈T:f∈I\{0}}⊂T,anditscomplement,theorderidealO(I):=T\T(I).Themostimportantfactwhichcanbederivedbythissettingisthefollowing:

Fact11)k[X1,...,Xn]=I⊕Spank(O(I)).2)Thereisak-vectorspaceisomorphismbetweenk[X1,...,Xn]/IandSpank(O(I)).3)Foreachf∈k[X1,...,Xn]thereisauniqueg:=Can(f,I)∈Spank(O(I))s.t.f−g∈I.Moreover:

a)Can(f,I)=Can(g,I)ifandonlyiff−g∈I.b)Can(f,I)=0ifandonlyiff∈I.

Remarkimmediatelyaveryimportantpoint,whichisobscuredinmostpre-sentationsofGr¨obnerbases:thecanonicalformofanelementisdefinedjustintermsoftheidealandoftheordering;conceptuallythenotionofaGr¨obnerbasisisnotneededtodefinecanonicalforms.Infact,wehavenotyetdefinedGr¨obnerbases:wearegoingtodoitnow.AGr¨obnerbasisofIisasetofgeneratorsG:={g1,...,gs}⊂Is.t.T(G):={T(g1),...,T(gs)}generatesT(I).IfaGr¨obnerbasisGofIisknown,givenf∈k[X1,...,Xn],Can(f,I)canbecomputedbythefollowingalgorithm(BuchbergerReduction):

Red(f,G)h:=0Whilef=0IfT(f)∈T(G)thenchooseg∈Gs.t.T(f)=tT(g)f:=f−lc(f)lc(g)−1tgelseh:=h+lc(f)T(f),f=f−lc(f)T(f)Can(f,I):=hGr¨obnerBasesinPublic-KeyCryptography3whichisaprocedureanalogoustoGaussianreductioninvectorspacesandwhosecostisthereforequadraticinthesizeoftheinputpolynomialf,i.e.,inadenserepresentation,inthenumberoftermswhicharenotgreaterthanT(f).Iftheorderingiscompatiblewithdegree,i.e.deg(t1)numberisO(dn)whered=deg(f).Ontheotherside,BuchbergerAlgorithmtocomputeaGr¨obnerbasisofanidealI,knowingabasis{f1,...,ft}ofI,hasaworst-casecomplexityd2O(n),whered=maxdeg(fi).Notwithstandingthecomplexityresultabove,thebasicassumptionofyourpaper,i.e.thatGr¨obnerbasesarehardtocompute,isbasedonamisunder-standing.ItistruethatthereareidealswhoseGr¨obnerbaseshaveelementswhosedegreeisdoublyexponentialinthedegreesoftheinputbasis;butsuchexam-plesarerare,withbadalgebraicproperties,andabsolutelynotrandom,whilerandomnessmustobviouslybesomehowpartofyourscheme.InfactinoneofthetwopaperswhichatleastpartiallysettledthecomplexityofBuchbergeralgorithm([G]),thefollowingisproved:

Theorem1.“Most”oftheidealsgeneratedbyspolynomialsinnvariablesofdegreeboundedbydaresuchthattheirGr¨obnerbaseshavedegreeboundedby(n+1)d−n.

Mostheremeansthatcoefficientsarerandomlychosenandthattheresultholdsexceptforasetofmeasurezerointhespaceparametrizingthecoefficients.ThemajormisunderstandingofyourpaperishoweverconfusingtheproblemofdecidingidealmembershipwiththeproblemofcomputingGr¨obnerbases;asolutiontothesecondproblemgivesasolutiontothefirstone,butaneasiersolutiontothefirstproblemcouldbeathand.ItisthiseasiersolutionwhichallowstobreakaGr¨obnercryptographicscheme.

合集下载

ctf rsa 佩尔方程

ctf rsa 佩尔方程

ctf rsa 佩尔方程CTF RSA 佩尔方程引言RSA加密算法是一种非对称密码体制，它是以三位数质数为基础的公开密钥加密系统。

RSA算法的安全性基于大质数分解问题，即将一个大的合数分解成两个质数的乘积。

但是，随着计算机技术的发展和量子计算机的出现，RSA算法所依赖的大质数分解问题已经变得越来越容易被攻破。

人们开始寻找新的加密算法来替代RSA。

佩尔方程佩尔方程（Pell's equation）是指形如x² - Dy² = 1的二次不定方程。

其中，D为正整数且不为完全平方数。

佩尔方程最早由英国学者John Pell在17世纪提出，并被广泛应用于密码学中。

在密码学中，我们可以利用佩尔方程来构造一种新的非对称加密算法——Pell加密算法。

Pell加密算法主要思路是将明文转化为二次不定方程x² - Dy² = m（m为整数），然后将其转化为另一个二次不定方程x′² - Dy′² = 1，并利用其解来进行加密和解密操作。

Pell加密算法实现步骤1.选择两个大质数p和q，计算N = pq。

2.选择一个整数D，使得D不是N的平方因子且D不是完全平方数。

3.选择一个整数m，使得m与N互质。

4.解出满足x² - Dy² = m的最小正整数解(x,y)。

5.将明文转化为二次不定方程x² - Dy² = m，并求其最小正整数解(x0,y0)。

6.将x0和y0转化为二进制形式，并将它们拼接起来得到密文C。

7.解密时，将密文C拆分为两部分x′和y′，然后解出满足x′² - Dy′² = 1的最小正整数解(x,y)。

明文即为二次不定方程x² - Dy² = m的最小正整数解。

Pell加密算法的优点1.与RSA加密算法相比，Pell加密算法更难被攻破。

由于佩尔方程的求解过程较为困难，因此攻击者很难通过分解大质数来破解Pell加密算法。

格密码学研究--王小云

格密码学研究--王小云


王小云 等:格密码学研究综述
15
有 界 距 离 解 码 问 题 (Bounded Distance Decoding, BDD- ): 给 定 一 个 格 L , 目 标 向 量 t 满 足
dist t , L 1 L , 找一个非零格向量 v , 满足对任意非零向量 u L, v t u t .
Abstract: Lattice-based cryptography is widely believed to resist quantum computer attacks, which involves many cryptographic mathematical problems and belongs to interdisciplinary study. The development of lattice-based cryptography follows two main lines: One is to study the computational complexity and searching algorithms for solving hard problems in high dimensional lattices based on the research of classical lattice problems. The other is to analyze the security of non-lattice-based public-key cryptosystems using the algorithms solving hard lattice problems, and further to design the lattice-based cryptosystems. This paper gives a survey of the main progress on lattice-based cryptography in recent 30 years, which covers the following concerns: computational complexity and searching algorithms relating to hard lattice problems, design and cryptanalysis of lattice-based cryptosystems. The paper tries to reflect the relationship of these four areas. In addition, some classical lattice problems and relative important results are described.
椭圆曲线加密分析：FLEXLM ECC问答

椭圆曲线加密分析：FLEXLM ECC问答

标题:【原创】椭圆曲线加密分析：FLEXLM ECC问答[7月16日更新到第7部分]作者:readyu时间: 2012-06-25,19:00:18链接: /showthread.php?t=152615说明：我曾经写过ECCTool用于学习和研究椭圆曲线加密在软件上的应用。

椭圆曲线密码学工具 ECCTooL v1.04原帖年代久远不再更新。

v1.05版本我放在本帖3#。

FLexLM ECC是椭圆曲线签名的一个典型应用，不可不察。

我整理了一下FLEXLM ECC方面的研究心得，准备把它完全写出来。

后面会有算法描述的例子代码。

FLEXLM ECC问答 (1)readyu 2012.61. FLEXLM是个虾米东西？FLEXlm是应用广泛的License管理工具。

宣称数千家EDA工具采用它管理授权。

FLEXlm对厂商来说，它的优点是证书管理功能强大，支持平台众多。

对最终用户来说，它的缺点是不够友好，比如Windows下，经常由于某些原因，flexlm服务启动错误。

对于破解者来说，它有着为数众多的教本。

维基百科上的条目为：/wiki/FLEXlmFLEXLM本来属于GLOBEtrotter。

Macrovision曾经收购GLOBEtrotter。

2006年的时候，FLEXLM原来的开发组跑路，另起灶头，产品叫RLM。

/index.php2008年Macrovision把FLEXLM卖了。

现在叫FlexNet Publisher。

/products/flexnet-publisher.htm2. FLexLM 的ECC（椭圆曲线加密）怎么来的？早期的flexlm采用的常规加密，不安全，能被做出lic。

这样的教程是很多的。

flexlm的安全性完全得不到保障，所以，自 v8(大约2001-2002)版本引入了公钥加密算法：椭圆曲线加密。

从此，它一直是flexlm的金钟罩。

包括v9(2003-) , v10(2004-) , v11(2007-), 到最新的版本 v11.10 (2012) 。

ZUC-256流密码算法

ZUC-256流密码算法

ZUC-256流密码算法ZUC算法研制组【期刊名称】《密码学报》【年(卷),期】2018(5)2【摘要】为了应对5G 通信与后量子密码时代的来临,本文提出 ZUC-256流密码.ZUC-256流密码是3GPP 机密性与完整性算法128-EEA3和128-EIA3中采用的 ZUC-128流密码的256比特密钥升级版本,与 ZUC-128流密码高度兼容.ZUC-256流密码的设计目标是提供5G 应用环境下的256比特安全性;其认证部分在初始向量不可复用的条件下支持多种标签长度.%To be well adapted to the 5G communications and the post-quantum cryptography era,we propose the ZUC-256 stream cipher in this paper, a successor of the previous ZUC-128 stream cipher used in the 3GPP confidentiality and integrity algorithms 128-EEA3 and 128-EIA3 which is highly compatible with the ZUC-128 stream cipher. The aim is a new stream cipher that offers the 256-bit security for the upcoming applications in 5G. For the authentication, various tag sizes are supported with the IV-respecting restriction.【总页数】13页(P167-179)【作者】ZUC算法研制组【作者单位】【正文语种】中文【中图分类】TP309.7【相关文献】1.一种面向RFID的超轻量级流密码算法 [J], 夏文涛; 潘森杉; 王良民2.ZUC-256流密码的猜测决定攻击 [J], 王梓宇; 毛明; 张艳硕3.基于拉丁方的流密码算法设计与仿真 [J], 李熙;田传俊4.基于拉丁方与时变符号混沌系统的流密码算法设计 [J], 唐文君;田传俊5.流密码算法、架构与硬件实现研究 [J], 赵石磊;刘玲;黄海;徐江;刘志伟;于斌因版权原因，仅展示原文概要，查看原文内容请购买。