反垃圾邮件技术中的密码学方法

维普资讯

第２４卷第１１期

２００７年１ １月

计算机应用与软件

Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ ａｎｄ Ｓｏｆｔｗａｒｅ

Ｖｏ１．２４ Ｎｏ．１ １

ＮＯＶ．２００７

反垃圾邮件技术中的密码学方法

杨春福 宋韬

（上海市计算技术研究所上海２０００４０）

摘 要 主要介绍了反垃圾邮件技术中的计算性挑战体制和公钥密码方法这两类采用密码学思想方法的技术，比较了几种技术

的优缺点，分析了他们各自的适用场合，为进一步的研究和反垃圾邮件方案的具体实施提供参考。

关键词 垃圾邮件 计算性挑战 哈希钱 存储受限函数 域名密钥 Ｓ／ＭＩＭＥ ＩＩＭ

ＣＲＹＰＴｏＧＲＡＰＨＩＣ ＭＥＴＨｏＤＳ ＩＮ ＡＮＴＩ．ＳＰＡＭ ＴＥＣＨＮｏＬｏＧＹ

Ｙａｎｇ Ｃｈｕｎｆｕ Ｓｏｎｇ Ｔａｏ

（Ｓｈａｎｇｈａｉ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｃｏｍｐｕｔｉｎｇ Ｔｅｃｈｎｏｌｏｇｙ，Ｓｈａｎｇｈａｉ ２０００４０，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ Ｉｎ ｔｈｅ ｒｅｓｅａｒｃｈ ｆｉｅｌｄ ｏｆ ａｎｔｉ—ｓｐａｍ，ｍａｎｙ ｓｃｈｅｍｅｓ ｈａｖｅ ｂｅｅｎ ｐｒｏｐｏｓｅｄ．Ｍｅｔｈｏｄｓ ｕｓｉｎｇ ｃｒｙｐｔｏｇｒａｐｈｉｃ ｉｄｅａ ａｒｅ ｉｎｔｒａｄｕｃｅｄ ｗｉｔｈ ｔｈｅｉｒ

ａｄｖａｎｔａｇｅｓ ａｎｄ ｄｉｓａｄｖａｎｔａｇｅｓ ｃｏｍｐａｒｅｄ．Ｔｈｅｉｒ ｓｕｉｔａｂｌｅ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｓｉｔｕａｔｉｏｎｓ ａｒｅ ａｎａｌｙｚｅｄ ＳＯ ａｓ ｔｏ ｇｉｖｅ ｏｕｔ ｓｏｍｅ ｒｅｆｅｒｅｎｃｅ ｋｎｏｗｌｅｄｇｅ ｆｏｒ

ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ａｎｄ ｆｕｒｔｈｅｒ ｒｅｓｅａｒｃｈ ｏｎ ａｎｔｉ—ｓｐａｍ ｓｃｈｅｍｅｓ．

Ｋｅｙｗｏｒｄｓ Ｓｐａｍ Ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｈａｌｌｅｎｇｅ Ｈａｓｈｅａｓｈ Ｍｅｍｏ￣一ｂｏｕｎｄ ｆｕｎｃｔｉｏｎ ＤｏｍａｉｎＫｅｙｓ Ｓ／ＭＩＭＥ ＩＩＭ

１），其中Ｓ表示要求发送者的令牌是

０简介

专为这个ｓｅ￣ｅｒ制作的，Ｗ参数化希

望发送者完成的工作量。邮件的发

送者（称他为ｃｌｉｅｎｔ）以Ｃ为参数使用 垃圾邮件问题正在发展成为一个为浪费大量网络带宽，转

移人们的注意力从而使工作效率低下，甚至破坏公司网络和数

据安全的重大安全问题。 ｅｒ交互的令牌。然后ｓｅｒｖｅｒ使用一

学术界和产业界已经提出了大量的反垃圾邮件方案，但是

ＭＩＮＴ（）函数来制造一个用于与ｓｅｒｖ—

个评估函数ＶＡＬＵＥ（）来检查这个令

图１

真正可行的不多。本文主要对使用密码学方法的反垃圾邮件体

制进行分析研究和比较，以为反垃圾邮件系统的实施和进一步

的研究提供参考。

牌，只有评估通过，才继续跟ｃｌｉｅｎｔ交互。

１．２哈希钱

Ａｄａｍ Ｂａｃｋ在１９９７年提出使用寻找部分碰撞ｈａｓｈ函数值

的运算作为费用函数的方法，是为哈希钱体制。首先引入几个

１计算性挑战体制

垃圾邮件发送者（以下称之为ｓｐａｍｍｅｒ）使用程序制造并发

符号：对于位串Ｓ ｛０，１｝ ，我们定义［ｓ］ 为偏移ｉ处的位，

［ｓ Ｊ为从位置ｉ开始到 结束的字串，定义左比较操作符＠

为 ＠ ｙ表示Ｖｉ＝１…ｂ，［ ］ ＝［ｙ］

协议交互过程如图１，其中三个主要算法描述如下：

ＣＨＡＬ（ ，Ｗ）：选择ｃ∈Ｒ｛０，１｝ ，令ｃ （ ，Ｗ，ｃ）

ＭＩＮＴ（Ｃ）：找到 ∈｛０，１｝ 使得Ｈ（ ｌ ｌＣ ｌ ）＠ ０ ，令Ｔ （Ｓ，ｌ ）

ＶＡＬＵＥ（Ｔ）：判断Ｈ（ ｌ｝Ｃ ｆ ）＠ ０ 是否成立，令Ｖ为ＴＲＵＥ或 １

ＦＡＬＳＥ

送大量垃圾邮件。计算性挑战体制的基本思想是：如果你想给

我发一封ｅ—ｍａｉｌ，你必须向我证明你为了专门给我发这封ｅ—ｍａｉｌ

付出了一些努力，比如说花费了一些你的计算机的ＣＰＵ计算时

间。这种方法利用了密码学中非对称运算的思想，可以提高垃

圾邮件的制造成本，以此达到反垃圾邮件的目的。这里主要介

绍两种体制，哈希钱（Ｈａｓｈｅａｓｈ）和基于内存访问限制函数的方

法。

其中的Ｈ是一个抗碰撞的哈希函数。可以看出，哈希钱费

１．１基本概念

Ｄｗｏｒｋ和 ａｒ在１９９２年密码年会（Ｃｒｙｐｔｏ９２）上提出使用

用函数的原理是找到哈希函数的部分碰撞，并以找到的碰撞位

数为指标控制发送方的工作量。攻击抗碰撞的哈希函数最快的

算法是暴力攻击。对于工作量Ｗ，邮件发送者制作一个令牌得

运算时间期望值是Ｏ（２ ）。

收稿日期：２００５一Ｏ７—１１。杨春福，硕士生，主研领域：计算机软件

与理论。

ＣＰＵ估价函数来反垃圾邮件的建议…，这个估价函数后来发展

成了费用函数（ｃｏｓｔ—ｆｕｎｃｔｉｏｎ）的概念。

邮件发送者（ｃｌｉｅｎｔ）先向邮件接收者（ｓｅｒｖｅｒ）发送一个“发

送邮件请求，ｓｅ￣ｅｒ用ＣＨＡＩ （Ｓ，Ｗ）函数来生成一个挑战ｃ（见图