密钥生成函数中的安全参数

    这篇文章是对密钥生产函数中的安全参数的一些我个人的思考。

    在密码学应用中，使用密码算法的第一步，通常是使用密钥生成函数来生成之后会被使用的密钥。例如，在RSA算法中，密钥生成算法生成一对公私钥对，其在直观层面上可以表示为。

    在阅读论文时，经常会看到这样的一种形式，即，这里的便是密钥生成函数的安全参数。从直观的角度上来说，该安全参数用于描述敌手想要攻破该算法的困难程度，详细的定义请参照下段说明：

In cryptography, a security parameter is a way of measuring of how "hard" it is for an adversary to break a cryptographic scheme. There are two main types of security parameter: computational and statistical, often denoted by  and , respectively. Roughly speaking, the computational security parameter is a measure for the input size of the computational problem on which the cryptographic scheme is based, which determines its computational complexity, whereas the statistical security parameter is a measure of the probability with which an adversary can break the scheme (whatever that means for the protocol).

    这样说虽然很直观，但是总归少了点具体性。那么从更细节的角度上来看，我们说，在具体到编写程序的时候，我们该怎么处理呢？这里还是以RSA为例子，假如你编写了一个RSA的密钥生成算法，其逻辑应当是：随机选取两个大素数和，计算，随机选取大整数，使得，计算。那么，当你写的密钥生成函数把作为参数传递进去时，你应当保证，的大小为位。在这种情况下，能够保证敌手不可能攻破我们的算法（计算安全）。

    那么现在问题来了，为什么不直接把作为参数传进去而非要把传进去呢？这背后的原理其实是算法实现者与算法分析者之间的观点不同。

    从算法实现者的角度而言，当你的密钥生成算法把作为参数传递时，你其实仅仅关注的是这段字符串的长度（例如，对于一个安全参数，我仅仅在乎该安全参数有8位）而不关注安全参数的形式，即这种字符串的形式。

    但是，从算法分析者的角度而言，这是有区别的，你不能从算法实现者的角度想当然的认为与等价，既然约定俗成表示安全参数有k位。算法分析者通过这种方式来形容安全参数，一个重要的原意是他们希望通过这种方法，来强调一个理念，即他们希望密钥生成算法是高效的，即其渐进时间复杂度是多项式级别的，从而使得随着安全参数的提升，算法的运行时间不会出现明显的增长。

    这篇文章在很大程度上参考了一个StackExchange问答，感兴趣的朋友可以进去看一看。