格攻击在公钥密码中的应用.pdfVIP

格攻击在公钥密码中的应用 纪家慧赵仁杰 (郑州信息工程大学信息研究系．郑州450002) 摘要：本文介绍了格的概念和若干重要性质，并分别讨论了对低秘密指数RsA和数字签 名标准Dss的两种不同格攻击。 一．前言 Directionsin 1976年Dime和He¨m柚发表了开创性论文New y’首次提出 cr抑tograph 了公开密钥的思想。在此后的二十多年里，公钥密码蓬勃发展，较著名的有RSA体制、E． 1Gmal体制和数字签名标准Dss等。与此同时，密钥分析者也不断对各种公钥体制进行攻 击，相继破译了多种公钥体制。在众多的攻击方法中，格攻击咀其灵活实用等特点占据重 要位置，近来，更被用于攻击RsA体制和数字签名标准Dss。这些格攻击许多是在不同的 附加假设下成功的，获益于coppersmith的破译思想——如何用LLL算法【l】解一元和二元 摸多项式。 本文将讨论格攻击在公钥密码中的麻J{j，结构如F：第二节介绍格的概念及若干重要 性质，第三节讨论对低秘密指数RsA的格攻击．第四节讨论对数字签名标准DsS的格攻 击。 。 二．格的溉念与重要性质 设“】t…·“。是线性无关向鳋，聊≤月．“l，…，“。所有整数线性组合构成的集 台称为由“，，…，“。)生成的格。“l，…，“。称为格的基，脚称为格的维数，如果脚=H， 则称洛是满秩的。F面介蹦格的若干重要性质，更多的参见[2]。 r=l 行刘式等丁以基向量“．t…，“。为行曲成的讲×翻矩阵的行列式。 将产生L的一组新的基(b-…t6。)满足： 1)．防82曼2lK．4二，对所有的l≤fc甜。 223 ————’。’’。●。。’’’。。’1。。。。‘。●。。‘。。’—1。。。。’’’’一 2)．若对所有的f，岛=睇+艺v，巧，碡u对所有的，，hI≤丢。 de“工)”“。 ●：实2．设L为格，岛，…，k是L的LLL·约化基，则1p．0≤2叫2 对格L的基(“。，…．％)-定义“二。=min，p刈。 事实3．设L是由“。．…，”。生成的格·(“，…，虬)是对给定基进行Lu。约化的 ’ de“工)”‘+”。 结果，假设H：：‘n≥1，则l段0≤2卅2 三．对低秘密指数醛A的格攻击 在雕浦公钥体制中，使用小的秘密指数d能获得快速的签名生成。然而遗憾的是win科3] 在1990年证明了如果使用的d(Ⅳ。25(N为礤n中的公开密钥，是两个大素数的积)．则 鼢～体制可被破译．其中用的攻击是连分式攻击。1999年D．Boneh等改进了这一结果[4】， 证明了只要d(Ⅳ“，RsA体制就是不安全的，其中用的就是格攻击。 ． RSA体制中，公开密钥为(N，c)，其中N=pq是两个n位大素数的积．为简单起见， 假设脚1，q．1辟，对应的秘密密钥为d，满足cd；1m。d!婴堕，其中 (1) m(Ⅳ)=Ⅳ一p—g+1，因此存在整数k，使得甜+女(型岩一旦÷里)=l 令』=竿舻一半，酬_删三1(m。∽·记e=肌e和N有相同的数 量级(即eⅣ，lO)，因此口很接近于1．假设秘密密钥dⅣ5，由式子(1)可知 I叫2如／中(^，)≤3如，Ⅳ知“了，类似地可知H2Ⅳ”=拓17“．取口zl(一般 情况如此)并忽略常数，就得到下面的问题；寻找k和s满足七(■+s)}l(mode)，其中