关于密码学警世准则（“算法是公开的”或者“只有密钥是应该保密的”）的思考

密码学的一个警世准则是“密码算法是公开的”。之前一直觉得这句话是感性表述，因为完全可以把密钥设定为 TM 描述，加密解密算法都是 UTM，这样相当于实际的算法是保密的。

不过现在我产生了新的理解：要公开的是密码学算法的 instance 开始之前固定的部分，保密的是 instance 开始之后抽取的随机样本。待会儿论述为什么是这样。如果接受了这个想法，那么上面提到的 UTM 法里面，密钥只能从一个特定的 TM 分布抽取。而这个分布是在开始算法运行之前就固定好的，因此属于需要公开的。

现在来论述为什么是这样：

从实用角度考虑，这个分布必须是多项式时间可抽取分布；因为这个分布在算法开始使用之前已经固定，也属于需要公布的一部分，因此“实际的算法”是什么仍然是要公开的（即使它可能是多个算法和混合）。从实践的角度说，这个抽取密钥的算法需要写在密码学软件里面，或者写在硬件上，所以总是可以反向工程出来——应该看成公开的。

从理论角度考虑，以安全的伪随机数生成器为例，如果 G 是伪随机数生成器，且对任意高效的一位输出算法 D，有

Pr[D(y)=1] - Pr[D(G(x))=1]

是安全参数的可忽略函数（其中 y 取自 G 的到达域，x 取自 G 的定义域，都是均匀分布），则说 G 是 安全的。定义中 D 的量化是在 G 之后的，因此“ D 知道 G ”（虽然有些 D 可能不会利用这一点），如果我们把密码学分析师或黑客想象为 D 的设计者，则他们可以用对 G 的知识设计 D，因为在取 D 的时候 G 已经固定了。“对手”知道 G，也就是“算法是公开的”。

————————

我思考、草稿用的是汉语，然后写博文是英语，最后再把博文的大概内容翻译成汉语，简直要命……

点击这里阅读我的完整思考（英语）

在这篇博文的书写过程中，我建立了一个新的 extension 帮我管理简单的引用。当你点击博文里面的 [AU83] 或者 [WIKI] 的时候，你会被转到最后列出引用的地方，并且那里会出现一个“箭头按钮”，点击之可以返回正文的位置；如果有多个正文的位置引用同一个内容，可以返回正确的位置（一个例子参考这篇博文提到的 6 月 23 日更新内容）。这一切都不需要 JavaScript 即可完成。

————————

参与讨论：

你对 Kerckhoffs 准则有什么想法？
你对我的 blog 有什么想法？

（另外欢迎挑刺找我的文章中的语法 / 拼写 / 数学错误

fucker

2017-06-24 20:40:18 +08:00

@geelaw
品头论足，读音 pǐn tóu lùn zú，指无聊的人随便谈论妇女的容貌，也比喻在小节上多方挑剔。

你觉得我们冒犯到你的 ID 或者域名你很恼怒或者反感，对此我很抱歉。
我想 @momocraft 和我一样都是没有恶意的，可能我俩是无聊的人吧。
我觉得一个在文章末尾表达“欢迎挑刺”的人，应该是能接受一个小小的玩笑的。
然而....
如果这样冒犯到了你，那么，对不起。

不过楼主你既然回复了我们，那么可以展开讨论吗？
不会引起你的不适吗？
会不会显得不礼貌呢？
可是我怕我不回复也是不礼貌。。。
那我回复一下？可以吗？

楼主你回复的语气 /方式显得太正式了，那么我的回复就尽量随性一点吧：）
你用音标来说 “基佬” 和 “ geelaw ” 发音差别是巨大的，那么我们就明人不放暗屁了
内心确实想到这个词了，但是平时很少说这个词，开玩笑的时候还行，
不开玩笑的时候，个人感觉，挺伤人的一个词
但是纯粹讨论发音差别巨大，可能这样的差别对你来说是“巨大的”。
太主观了吧，也没法讨论，我就认为差别蛮小的。
举个例子？
好吧，举个例子。

----

gene 英[dʒi:n] 美[dʒin]
n. <生>基因; 遗传因子;

Lawry
[人名] 劳里

geelaw

2017-06-24 21:06:26 +08:00

@fucker

> 回复语气太正式

实际上是因为表述方式太形式化（“下面四个命题有一个是真的”是经典成语 TFAE 的变体）

> 冒犯

并不算是冒犯，但是一个我觉得不礼貌的行为不是非要引起别人的不适。第一次见这个的人当然没有恶意，我只是对这个感觉 fed up。

> 挺伤人的一个词

取决于用法，这个词（在普通话里）似乎本身还没有太明显的感情色彩

> 区别巨大

主要原因是第一个音节的复印是很不同的（英语 dʒ、汉语拼音 j 和粤语拼音 k 的区别真的很明显），第二个音节的元音的区别也很大

> 例子

这两个例子中，两个语言中发音的差别都很大，因为一个语言里可以存在另一个语言里面没有的音。

> 挑刺

因为我的书写是追求准确的 - - 这并不是玩笑。

dyxsdtc

2017-06-25 01:00:07 +08:00

对于写作的建议：对于 TM，UTM 之类的缩写，应该给出全称，不熟悉 TCS 的人对这类简称反应不过来。事实上，即使是专业向的写作，第一次使用简称的时候一般也会给出全称。

关于你的第一个疑问：在密码学理论中，key generator 也是加密方法定义的一部分（一个定义包含 (K, E, D)三部分，E 和 D 为加密解密算法）。所以如果以你的方法定义，也能从（公开的）定义中得到“真正”的加密解密算法。其实你后面的解释就是这个意思吧。

理论分析的时候，给出的 attack 肯定是要用到 G 的算法。正如你所说，这是暗含在安全性的定义中的。教科书中一般会提到这点，但是数学定义追求简洁，所以没必要特意提出。证明安全性的时候倒是不会假设 D 的行为。

楼主应该是大学生吧，能思考这些问题已经很不错了。如果有机会选一门密码学的课程的话，应该能对密码学理论有更系统的了解。

geelaw

2017-06-25 01:19:21 +08:00

@dyxsdtc 感谢您的回复 :-)

关于缩写，在完整文章里 UTM 和 PRG 在第一次出现的时候都是 abbr 元素，并且有加点线提示，光标移动上去可以看到 tooltip ；并且在打印的时候会转换为 Abbreviation (full text) 的模式。既然 UTM 有了，就懒得写 TM 了。

在翻译之后的版本里我就偷懒了 >_<

并不算是疑问吧，因为我写的时候已经意识到了我之前的想法是不对的，后面的解释确实是这样。And you're right, 我几乎忘记 keygen 也是（或者也可以是）算法的一部分（因为我学的对称加密里面通常 key 就是直接从一个集合的均匀分布里面抽取，所以不需要 keygen ）……感谢提醒。

我个人不做破译密码（ cryptanalysis ）的工作，所以没关心过 attacker 怎么操作的问题；我所学的是各种密码学对象的“语法”定义和安全性定义、知名的密码学对象构造方法以及密码学命题的论证技巧等，顺带了解一些实用算法（的简化版本）。

与其说“暗含”，我更愿意说是“自然地包括”，而且这种用法是数学中 idiomatic 用法：这种现象在计算理论或者微积分里面都有，定义里量词的顺序是表达了含义的。

trcnkq

2017-06-25 02:13:22 +08:00

同意 lz 观点。几个思考也分享下：
1. 被当做密钥的应该是这样的东西：我方为了维持加密不被破解，依赖且唯一依赖的信息。（我方确信密钥泄露则该 instance 失效）而 instantiate 之前就确定的算法则不具有这种条件：如果尝试雪藏，一方面希望不泄露，另一方面不幸泄露也不会导致 instance 失效。尝试雪藏这种信息的问题在于徒增保密成本和系统不确定性。
2. 可以用一段程序代码当做密钥，eval 函数当做加解密算法。但是在密钥只可能被泄露而不会破解的前提下，用[提前确定且公开的简单的加解密算法+无意义随机串做密钥]的方案的性价比可能更高（比如通信数据量）。