密码学系列之:memory-bound函数

柔情只为你懂 2023-01-23 09:50 136阅读 0赞

### 文章目录 ###

*  简介
 *  内存函数
 *  内存受限函数
 *   *  内存受限函数的使用

# 简介 #

memory-bound函数可以称为内存受限函数，它是指完成给定计算问题的时间主要取决于保存工作数据所需的内存量。和之相对应的就是计算受限compute-bound的函数，在计算受限的函数中，计算所需要的计算步骤是其决定因素。

本文将会介绍一下内存受限函数和它跟内存函数的关系。

# 内存函数 #

内存函数和内存受限函数看名字好像很类似，其实他们的作用是不同的，我们先来看下内存函数。

在学习算法中，有一个非常简单好用的算法叫做递归算法，熟悉递归算法的朋友可能都知道，递归算法虽然好用，但是有个缺点就是会重复计算递归过程中的函数，比如说递归中最经典的斐波拉赫数列：

Recursive_Fibonacci (n)
     {
         if (n == 0)
             return 0
         if (n == 1)
             return 1
    
         return Recursive_Fibonacci (n-1) + Recursive_Fibonacci (n-2)
     }

很简单，但是我们来考虑下计算过程，F(3)=F(2)+F(1), 而F(4)=F(3)+F(2)，在这个过程中需要计算2次F(2)的值。如果计算的N值够大的话，重复计算的值还会更多。

一个解决方法就是将之前计算过的结果使用内存存起来，这种方法就叫做内存函数：

Fibonacci (n)
     {
         for i = 0 to n-1
             results[i] = -1  // -1 means undefined
    
         return Fibonacci_Results (results, n);
     }
    
     Fibonacci_Results (results, n)
     {
         if (results[n] != -1)  // If it has been solved before,
             return results[n]  // look it up.
         if (n == 0)
             val = 0
         else if (n == 1)
             val = 1
         else
             val = Fibonacci_Results(results, n-2 ) + Fibonacci_Results(results, n-1)
         results[n] = val  // Save this result for re-use.
    
         return val
     }

虽然直接递归的逻辑很简单，写起来也很方便，但是它的时间复杂度会更高。

# 内存受限函数 #

内存受限函数主要用来描述一个使用XOR的函数，它由一系列计算组成，其中每一次计算都依赖于前一次计算。

因为这样的内存依赖关系，所以内存受限函数主要用在密码学中，可以防止密码的暴力破解工作。

下面举个内存受限函数在防止垃圾邮件中的使用。

## 内存受限函数的使用 ##

使用内存受限函数来防止垃圾邮件，主要使用的是POW的原理，也就是说，你可以给我发垃圾邮件，但是前提是需要付出一些代价。

当然，最初的防垃圾邮件的原理是使用CPU受限函数。

1992年，IBM的研究科学家Cynthia Dwork和Moni Naor在CRYPTO上发表了一篇题为《通过定价来阻止垃圾邮件》的论文，他们提出了一种利用CPU受限函数的功能来阻止滥用者发送垃圾邮件的可能性。

该方案的原理是：如果滥发邮件的成本很低，那么垃圾邮件就可能横行。如果能够通过以昂贵的CPU计算的形式为发送邮件添加额外的计算成本，就可以减少垃圾邮件。使用CPU受限函数，使得每发一次邮件都需要消耗一定的CPU资源，从而防止在短时间内发送大量的垃圾邮件。

CPU受限函数是一种突破，但是也有其缺点。

因为快CPU的计算速度比慢CPU快得多。此外，高端计算机系统也有复杂的流水线和其他有利于计算的优化功能。因此，拥有高端系统的垃圾邮件发送者几乎不会受到这种CPU受限函数的影响。