作为一个密码学学渣，这个问题引起了我极大的兴趣，想从相对专业一点的角度聊一聊。答案较长，分为以下几个部分：第一部分介绍一些基本概念和讨论的大前提，第二部分分析目前知友们提出的方案，第三部分基于一位知友的答案进行改进，第四部分讨论几何均值的情况，第五部分总结。
[h1]一、介绍[/h1]在一个有信息需要保密的过程中，我们应该如何考虑消息的安全性？主要分为两个方面：
第一是消息的保密性。也就是说，要尽量保证不该知道这个消息的人不能知道与消息相关的信息（注意是信息而非内容。内容是指完整地掌握所有的信息，而信息则是与之相关的东西，比如最后一个比特，二进制中 1 的个数等等。这些信息的泄露也是需要避免的）。
第二是消息的可靠性。也就是说，A 收到了 B 发出的消息，他应该有办法验证这条消息确实是 B 发出的，而不是中间人掉包后的消息。
在研究一个协议的安全性时，我们经常构造一个“游戏（game）”，游戏中有两方：敌手和挑战者。挑战者进行保密通信，而敌手则需要窃取秘密或破坏通信。根据不同的假设，我们给予敌手一些能力，同时对通信中消息的保密性和可靠性做一些要求。最后，我们考虑在面对有这种能力的敌手时，需要的保密性和可靠性是否能够达到要求。
具体到这个问题中，我们先讨论一些大前提，再讨论其他知友给出的方案的安全性，构造一些攻击，最后提出一个相对来说安全性较高的方案。为了一般性，我们直接讨论 n 个人的情况。大前提1：所有的节点必须是诚实的。也就是说，每个人提供自己的工资信息时不能撒谎。 大前提2：最坏的情况下只有 n-2 个节点进行合谋，攻击其余两个节点。
[h1]二、方案分析[/h1]下面我们分析一些知友提出的方案的安全性。
1. 扑克牌/麻将/大富翁钞票
在这些知友的方案中，每个人通过扑克牌等将自己的工资信息拆分，之后混在一起加起来求平均。由于这些牌是扣起来混合的，因此不可能知道其他人的工资。
分析：这个方法在大多数情况下可以保证自己的工资不被其他人所知，但一定会有信息泄露。比如说我们用红桃代表千位，你看到翻开后的牌里有一个红桃九，而你自己的工资只有一千多，矛盾是不是就产生了？但是如果是理想情况，你只能知道最后的平均工资，而不能知道每一个人工资的任何信息。
由于这个方案泄露了大家工资的信息，因此不可靠。
2.第一个人加上一个随机数，最后减掉（这个答案）
这样的方式是符合最基本的安全要求的。也就是说，如果每个人都只知道自己的工资和传来的数字，没有人可以知道其他人的工资。
分析：这个方案几乎没有直接泄露的信息，但少数人合谋可以对某个人的工资数进行攻击。如果第一个人知道了第三个人收到的数字，他就可以知道第二个人的工资；2 号知道了 4 号收到的数字，就知道 3 号的工资……对于任意一个 n ，只需要知道前后的数字就可以算出一个人的工资，这个协议还是比较脆弱的。
3.每个人拆分自己的工资并发给其他人（这个答案）
在这种情况下，任意 n-2 个人合谋也只能得到其余两人的平均工资，无法获得更多的信息。这是目前最好的方案。
但是注意，这个方案我们进行了一些假设：每个人发给其他人的信息不会被这 n 个人之外的敌手窃听，也不会被篡改。但实际中并不是这样。我们的方案应该能防止这些事情的发生。
下面，我们提出这个问题中的敌手能力和安全性要求，并对方案 3 做出改进来满足我们提出的要求。
三、方案改进
现在我们假设这 n 个人不在一起，彼此之间只能通过计算机发送信息。而通信的信道是不可靠的，也就是说我们不能验证这条消息是不是对方发来的、没有被篡改过的，传输的信息也会被敌手得到。
而我们的要求包括两方面。第一，这 n 个人中即使有 n-2 个人合谋，也只能知道剩下 2 人的平均工资，不能获得更多的信息；第二，敌手即使可以获得所有的通信消息，也可以进行篡改。在这种情况下，敌手不能获得关于工资的任何信息，也不能篡改通信内容而不被发现。
在这里我们还要再做两点补充。第一是敌手的计算能力是有限的，这允许我们进行公钥加密和签名（这两个概念马上会具体介绍）；第二是公开信息是可靠的，也就是说，我可以公开一个字符串作为我的一个“公钥”，这个公钥没有保密性，任何人都可以看到。而这种情况下这个字符串是无法伪造的，也就是所有人都可以确定我确实公开的是这段字符串。
下面我们分别介绍公钥加密和数字签名。在传输中的消息是会被敌手看到的，所以要对消息进行加密。但如果使用传统的加密方式，需要加密者和解密者拥有共同的密钥，在这种情况下是做不到的（不考虑密钥交换……这个过程还是用公钥思想实现的）。因此我们需要使用另一种加密方式：加密密钥是公开的，每个人都可以看到并使用；但解密密钥是保密的，只有消息的接受者持有。这样，当 Alice 想给 Bob 发送一条保密消息时，他只需要使用 Bob 的公钥对消息进行加密再发给 Bob ，Bob 使用解密密钥进行解密即可。
这种加密方式需要一个困难问题，大家把困难问题理解为一个敌手和挑战者都无法进行的计算问题即可。比如说离散对数问题：在一个群 G 中， ![]()
，给出群 G 和 ![]()
的值，求 ![]()
。这里的对数和我们之前讨论的不同，是在群中的。实数中的对数是容易计算的，而一般情况下，群里的离散对数是难以计算的。
另外，我们还要做一个假设（CDH 假设）：在群 G 中，给出 ![]()
，计算 ![]()
是困难的。
这样，我们就可以构造一个公钥加密体制，也就是著名的 ELGamal ：1.Bob 找一个群（比如 ![]()
）和一个生成元 ![]()
,私钥为 ![]()
，公开 ![]()
，保密 ![]()
.2.Alice 先随机选择一个数 ![]()
，然后分别计算 ![]()
和 ![]()
,将其发送给 Bob.3.Bob 计算 ![]()
，可以验证其等于 ![]()
,解密成功。（这里的描述不是很严谨，大家理解意思即可）
类似地，ELGamal 同样可以进行签名的构造。比如 Alice 要对消息 m 进行签名：sAlice 随机选择 k 计算 ![]()
和 ![]()
dsis
Bob 验证 ![]()
（公式显示不出来的话可自行搜索相关内容）
好了，下面我们完整地过一遍：
1.每个人的工资分别记为 ![]()
2.每个人将工资随机地分解为 n 个数之和，记为 ![]()
等等
3.每个人在自己分解的 n 个数随机排序，将第 ![]()
个数用第 ![]()
个人的公钥加密（如果是给自己的则省略），用自己的私钥对加密后的消息进行签名，然后将消息与加密结果一起发送给第 ![]()
个人
4.每个人验证签名后用自的私钥解密其余 n-1 条消息，将其与自己留下的一个数共 n 个数求和
5.把求和结果用其余 n-1 个人的公钥分别加密，并对结果签名，将加密后的消息与对应的签名发送给对应的人
6.每个人验证签名后解密所有消息，计算平均值即可
四、几何均值
在第三部分最后，我们已经给出了所有人算术平均值的方案，可以证明在加密算法和签名算法安全的情况下，这种方案也是足够安全的。下面我们讨论求几何均值的情况。
如果用类似的方法，我们需要把每个数分解为若干个数的乘积，这是很难做到的。一方面，对整数进行素因子分解本身就不是一件容易的事情；另一方面，有些整数没有足够的素因子，将 1 作为因数之一并不是一个好办法。
看来只有另寻出路了。注意到 ELGamal 加密算法中的消息是作为一个因子的，这给了我们一个提示。构造这样的算法：
1. 其中任何一个人公开一个群 ![]()
和一个生成元 ![]()
，每个人选取一个私钥 ![]()
和一个随机数 ![]()
,公开所有 ![]()
2. 第一个人计算 ![]()
,传给第二个人
3.第二个人计算 ![]()
，以此类推，直到第 ![]()
个人计算完毕，将结果 ![]()
交给第一个人
4.第一个人计算 ![]()
,交给第二个人
5.第二个人计算 ![]()
，交给第三个人，以此类推，直到第 ![]()
个人计算完毕。公布结果，即为所有人工资的乘积
6.别忘了这里的乘积是对 ![]()
取模的，因此要得到最终答案还需要一点数学技巧：选取 ![]()
个不同的大素数 ![]()
，重复上述过程，我们就得到了 ![]()
个数的乘积对不同的 ![]()
取模的值。用中国剩余定理，我们可以算出这个乘积对所有的 ![]()
乘积的模值。注意到后者大于前者，因此取模并不影响，该数字就是这 ![]()
个数的乘积，开 ![]()
次方即为答案。
关于可靠性只需要再加一个签名即可，不再赘述。
五、总结
这个看起来很简单的问题，深究起来竟然涉及如此多的密码学知识，连我都有些惊讶。这也是我们思考问题的方式：假设每个环节都有泄密或被篡改的可能，然后逐个去排除，让协议更加安全可靠。
第二部分第三个方案是一个很不错的方案，不仅泄露的信息最少，而且很容易类比到任意人数的情况。因此很容易想到在此基础上进行修正。而第四部分纯粹是我突然想到的，画蛇添足了。
事实上，问题本身是一个最简单的安全多方计算问题，有兴趣的朋友可以顺着这个关键词查阅相关的资料。
最后我想说，密码学真的很好玩~
|
转播
