理解伪随机函数与伪随机 permutation：加密安全模型与 CBC 模式分析

本文档主要探讨了密码学中的两个核心概念——伪随机函数（PRF）和伪随机 permutation（PRP），以及它们在块密码体制中的应用，特别是与加密安全模型和两种常见模式（Cipher Block Chaining, CBC 和 Counter Mode）的关系。首先，我们了解了什么是PRFs和PRPs，它们之间的区别和联系。 PRFs是一种定义在密钥空间K、输入空间X和输出空间Y上的函数，具有以下特点： 1. 存在一个高效算法可以评估F(k, x)，即给定密钥k和输入x，可以容易地计算其输出。 2. PRPs是特殊的PRFs，它们是将密钥空间映射到自身空间的一一对应关系，即输入X和输出X相同，并且存在一个高效的逆运算算法D(k, x)。 以AES-128、DES和3DES为例，它们都是PRPs，因为它们满足上述条件，同时由于它们的可逆性，也被认为是PRFs。AES-128和DES/3DES分别在128位和64位输入上进行操作，其中密钥长度分别为128位和56/168位。 文档接着讨论了如何确保PRFs的安全性。一个安全的PRF要求，其行为类似于从X到Y的随机函数集合Funs[X,Y]中任意一个随机函数，即使知道它是由PRF F(k, *)生成的，也无法轻易区分。这里的安全性可以通过比较函数集合SF（由所有可能的PRF F(k, *)组成）与Funs[X,Y]的大小来衡量，其中SF的大小取决于密钥空间的大小|K|，而Funs[X,Y]的大小则由输入空间X和输出空间Y的大小决定。 最后，文档提到了两种常用的块加密模式——CBC（Cipher Block Chaining）和Counter（CTR）模式，这些模式在实际应用中用于实现加密过程，但在此处并未详述它们的实现细节和安全性分析。通常，CBC模式通过链接每个区块的加密结果来增强安全性，而CTR模式则利用计数器模式生成密钥流，与明文逐位进行异或操作，以达到加密目的。 总结来说，这份文档深入讲解了密码学中的抽象块密码，特别是PRPs和PRFs的概念，以及它们在设计和评估加密系统时的重要作用。此外，它还介绍了如何确保PRFs的安全性，并简要提及了CBC和CTR这两种常见的加密模式，这些都是理解现代信息安全技术的基础知识。