《无间道》中的“盲签字”

科学松鼠会 @ 2010-5-5 17:49

电影《无间道》里，梁朝伟饰演的角色陈永仁很尴尬，警校没毕业就被派到黑社会做卧底，到斗争最激烈的时候，他的身份证明被黑帮打入警局的刘建明（刘德华饰）彻底删除了，与陈永仁单线联系的黄督察（黄秋生饰）也死了，陈永仁再也没法证明自己是警察了，他成了一个黑人。剧情安排他被杀了，这是没办法的事，否则他完成任务之后，如何再回到警局去上班呢？谁又能帮他证明警察身份呢？

如果我是他，出于自保的目的，会在当卧底之前把各种可能性都考虑清楚，首先我会要求警局把我的电脑卧底资料加密，密码由我一人掌握，以防刘建明之流从中获取我的信息。但这还不够，因为刘建明之流虽然看不到我的具体信息，但他有可能找到卧底人信息的加密文件，他一鼓脑都删除了，那我也会同样地悲剧了。

命运要掌握在我自己手里，根据这个原则，我按与黄督察约定好的条款写了一份卧底证明，即我的掩护名为“阿仁”，韩琛帮覆灭后就回警局工作，升两级且获奖金50万元，并要求黄督察签字盖章。但是，我不能让他看到这份证明，因为黄督察有可能事后变节，把“阿仁”是卧底的情况泄露给黑帮。

我把证明打印好后，把文字部分遮挡住，只留下空白处让黄督察签字盖章。但是黄督察不干，因为他对我写的证明内容没信心，他认为我可能写的是“卧底1个月即退休，退休金2000万”。

如何才能让黄督察既看不到我写的证明内容，又让他确信他已经知道了我的证明内容呢？这看似不可能，但这却是信息安全理论中已经解决了的“盲签字”内容。

我设计了以下的签字流程：


1、我写了10份掩护名不同的证明，有的叫“阿仁”，有的叫“阿德”等等，其它内容都完全一致，用同一种加密方法进行加密，得到十份不同的密文。特别的是，这种加密方法对明文的变化很敏感，即使两份证明中仅有“仁”“德”两个字不同，那密文也显得毫无关系的样子，这叫作雪崩效应，即一丁点的扰动就会引起结果巨大的差别。

2、我找黄督察签字盖章，他随机挑出9份，让我当场解密，他看到解密后的明文与我们的约定相同，只是掩护名不同而矣。于是，黄督察放心地在第10张密文上签了字盖了章，他当然不知道我的掩护名是什么，现在我放心了。


3、我把这份签字盖章的证明妥善保管起来，以备将来回警局时使用，只是掩护名是10个我起好中的随机的一个了，这有点令我不爽，本来是想叫“阿德”的，但黄督察恰好把“阿仁”这份留下来了。

这里面还有3个问题：

1、我为什么选择了有雪崩效应的加密算法呢？

如果没有这种特性，那我加密后的十份密文会非常相似，只有个别位置不相同，黄督察当然会知道不相同之处就是掩护名的密文，他获得了十份掩护名的密文及一一对应的九份掩护名的明文，会很容易地根据这些规律推导出他签字盖章的那份证明的掩护名的明文。而有了雪崩效应，他就找不出掩护名所对应的密文是哪个了，我也就安全了。

2、如果对同一个密文有两种不同的解法，一种可解成不捣鬼的，一种解成捣鬼的，那我当着黄督察的面用前一种解密算法忽悠他签了字，下个月我拿他签字盖章的证明密文找他要钱，使用后一种捣鬼算法，那他不就傻了吗？

这其中涉及到了单向函数问题，什么是单向函数呢？给定了被除数和除数，余数就很容易确定了，例如被除数4除以除数3，余数是1，但给定了除数3和余数1，被除数会有无穷多个。正向推很容易得到确定解，反向推就难以得到确定解了，这就是一种单向函数。黄督察规定我必须使用单向函数加密，这就保证了我不可能有第二种解法，否则我就当知名数学家了，还做卧底这苦差干吗？

3、黄督察为什么也会放心呢？
因为我捣鬼了1份以上(不含)的证明，当场解开9份后一定会被发现,我只捣鬼了1张，而黄督察恰巧没抽到的概率只占1/10,这是我欺骗成功的唯一机会。为了避免欺骗的发生，他事先跟我约定了一个严重的欺诈惩罚条例，只要发现我作弊就开除甚至法办我，如果他还不放心，可以要求我搞100份或更多的证明来，直到他认定我不会傻到为了这么小的可能性而去冒这么大的风险。

在“盲签字”运用中，10个样本是极少的，实际中的样本量可能有几百万个之多，几百万分之一的可能性才能获益，而在绝大多数的情况下会受到严重惩戒的事，但凡有一点理智的人都是不会干的。正是基于这样的考虑，“盲签字”就成为了一种很可靠的安全协议，跟上两篇《阿里巴巴的零知识证明》和《象棋大师的身份欺诈》一样，这种安全协议最不怕的就是惟利是图的人，他们对自己获利的小算盘打得越精，就越能牵着他们的鼻子走。

本文来自科学松鼠会http://songshuhui.net，转载请注明出处。科学松鼠会 @ 2010-5-5 17:49

电影《无间道》里，梁朝伟饰演的角色陈永仁很尴尬，警校没毕业就被派到黑社会做卧底，到斗争最激烈的时候，他的身份证明被黑帮打入警局的刘建明（刘德华饰）彻底删除了，与陈永仁单线联系的黄督察（黄秋生饰）也死了，陈永仁再也没法证明自己是警察了，他成了一个黑人。剧情安排他被杀了，这是没办法的事，否则他完成任务之后，如何再回到警局去上班呢？谁又能帮他证明警察身份呢？

如果我是他，出于自保的目的，会在当卧底之前把各种可能性都考虑清楚，首先我会要求警局把我的电脑卧底资料加密，密码由我一人掌握，以防刘建明之流从中获取我的信息。但这还不够，因为刘建明之流虽然看不到我的具体信息，但他有可能找到卧底人信息的加密文件，他一鼓脑都删除了，那我也会同样地悲剧了。

命运要掌握在我自己手里，根据这个原则，我按与黄督察约定好的条款写了一份卧底证明，即我的掩护名为“阿仁”，韩琛帮覆灭后就回警局工作，升两级且获奖金50万元，并要求黄督察签字盖章。但是，我不能让他看到这份证明，因为黄督察有可能事后变节，把“阿仁”是卧底的情况泄露给黑帮。

我把证明打印好后，把文字部分遮挡住，只留下空白处让黄督察签字盖章。但是黄督察不干，因为他对我写的证明内容没信心，他认为我可能写的是“卧底1个月即退休，退休金2000万”。

如何才能让黄督察既看不到我写的证明内容，又让他确信他已经知道了我的证明内容呢？这看似不可能，但这却是信息安全理论中已经解决了的“盲签字”内容。

我设计了以下的签字流程：


1、我写了10份掩护名不同的证明，有的叫“阿仁”，有的叫“阿德”等等，其它内容都完全一致，用同一种加密方法进行加密，得到十份不同的密文。特别的是，这种加密方法对明文的变化很敏感，即使两份证明中仅有“仁”“德”两个字不同，那密文也显得毫无关系的样子，这叫作雪崩效应，即一丁点的扰动就会引起结果巨大的差别。

2、我找黄督察签字盖章，他随机挑出9份，让我当场解密，他看到解密后的明文与我们的约定相同，只是掩护名不同而矣。于是，黄督察放心地在第10张密文上签了字盖了章，他当然不知道我的掩护名是什么，现在我放心了。


3、我把这份签字盖章的证明妥善保管起来，以备将来回警局时使用，只是掩护名是10个我起好中的随机的一个了，这有点令我不爽，本来是想叫“阿德”的，但黄督察恰好把“阿仁”这份留下来了。

这里面还有3个问题：

1、我为什么选择了有雪崩效应的加密算法呢？

如果没有这种特性，那我加密后的十份密文会非常相似，只有个别位置不相同，黄督察当然会知道不相同之处就是掩护名的密文，他获得了十份掩护名的密文及一一对应的九份掩护名的明文，会很容易地根据这些规律推导出他签字盖章的那份证明的掩护名的明文。而有了雪崩效应，他就找不出掩护名所对应的密文是哪个了，我也就安全了。

2、如果对同一个密文有两种不同的解法，一种可解成不捣鬼的，一种解成捣鬼的，那我当着黄督察的面用前一种解密算法忽悠他签了字，下个月我拿他签字盖章的证明密文找他要钱，使用后一种捣鬼算法，那他不就傻了吗？

这其中涉及到了单向函数问题，什么是单向函数呢？给定了被除数和除数，余数就很容易确定了，例如被除数4除以除数3，余数是1，但给定了除数3和余数1，被除数会有无穷多个。正向推很容易得到确定解，反向推就难以得到确定解了，这就是一种单向函数。黄督察规定我必须使用单向函数加密，这就保证了我不可能有第二种解法，否则我就当知名数学家了，还做卧底这苦差干吗？

3、黄督察为什么也会放心呢？
因为我捣鬼了1份以上(不含)的证明，当场解开9份后一定会被发现,我只捣鬼了1张，而黄督察恰巧没抽到的概率只占1/10,这是我欺骗成功的唯一机会。为了避免欺骗的发生，他事先跟我约定了一个严重的欺诈惩罚条例，只要发现我作弊就开除甚至法办我，如果他还不放心，可以要求我搞100份或更多的证明来，直到他认定我不会傻到为了这么小的可能性而去冒这么大的风险。

在“盲签字”运用中，10个样本是极少的，实际中的样本量可能有几百万个之多，几百万分之一的可能性才能获益，而在绝大多数的情况下会受到严重惩戒的事，但凡有一点理智的人都是不会干的。正是基于这样的考虑，“盲签字”就成为了一种很可靠的安全协议，跟上两篇《阿里巴巴的零知识证明》和《象棋大师的身份欺诈》一样，这种安全协议最不怕的就是惟利是图的人，他们对自己获利的小算盘打得越精，就越能牵着他们的鼻子走。

本文来自科学松鼠会http://songshuhui.net，转载请注明出处。