这篇文章是对密钥生产函数中的安全参数的一些我个人的思考。
在密码学应用中,使用密码算法的第一步,通常是使用密钥生成函数来生成之后会被使用的密钥。例如,在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问答,感兴趣的朋友可以进去看一看。