The Full Cost of Cryptanalytic Attacks

The Full Cost of Cryptanalytic Attacks
复制标题

密码分析攻击的全部成本

DOI：
--
复制
发表时间：
2004
期刊：
Journal of Cryptology
影响因子：
3
通讯作者：
M. Wiener
M. Wiener
中科院分区：
计算机科学4区
文献类型：
--
作者：
M. Wiener

文献摘要

被引文献

相似文献

摘要人关于渐近性的问题 将许多处理器连接到 使用三个维度进行接线的大记忆 已回答，使用此结果 找到几个的全部费用 在许多情况下，加密攻击。 成本高于公认的复杂性 根据处理器数量的给定算法的 步骤。 确定了加密攻击，包括 小腿计算离散的方法 Prime顺序n的循环群中的对数， 需要N1/2+O（1）处理器步骤，但是， 当考虑所有因素时， N2/3+O（1）。 通过数字字段筛分，通用 对块密码的攻击，双重攻击 和三重加密，并查找哈希碰撞。 在许多情况下，平行碰撞搜索 给出明显的不对称优势 众所周知的通用攻击。
AbstractAn open question about the asymptotic cost of connecting many processors to a large memory using three dimensions for wiring is answered, and this result is used to find the full cost of several cryptanalytic attacks. In many cases this full cost is higher than the accepted complexity of a given algorithm based on the number of processor steps. The full costs of several cryptanalytic attacks are determined, including Shanks’ method for computing discrete logarithms in cyclic groups of prime order n, which requires n1/2+o(1) processor steps, but, when all factors are taken into account, has full cost n2/3+o(1). Other attacks analyzed are factoring with the number field sieve, generic attacks on block ciphers, attacks on double and triple encryption, and finding hash collisions. In many cases parallel collision search gives a significant asymptotic advantage over well-known generic attacks.