主题：如何分摊秘密（一）——从《鹿鼎记》中的四十二章经说起 -- 明日枯荷包
家园 如何分摊秘密（一）——从《鹿鼎记》中的四十二章经说起 （首先声明，这是篇讲数学知识的文章，虽然这么说大概会赶走不少读者……）
这个世界上有很多秘密。所谓的秘密，就是不希望让不该知道的人知道的一些信息。
有些秘密是属于个人的，比方说大伙上西西河的密码，这个密码除了用户本人以外，其他人都不该知道；就算是家中LD也要上西西河，那么让她自己也注册一个账号，她自己有自己的密码也就是秘密，俩人互不相干。这种只属于某个个体的秘密，不在本文谈论的范围之内。本文谈论的是“如何分摊秘密”，只有一个人拥有的秘密谈不上“分摊”。
但是如果家里是个比较厉害的LD，她非要有你的西西河密码，比如说出于某种考虑想看看你的短信息啦什么的。这样你的密码连她都知道了，这算不算“分摊秘密”呢？也可以算，但是还是不属于本文谈论的范围，因为这个秘密其实是你们每个人都单独拥有了，每个人都知道完整的密码，就算只有一个在场，没有另一个，照样可以用密码登录西西河。这属于多个人里每人都独自地完整地掌握了同一个密码的情况。本文也不谈论这种“分摊秘密”，因为这秘密好像没“摊开”。
那我想说的到底是哪种““分摊秘密””呢？金庸的《鹿鼎记》里有个好例子，就是四十二章经中地图的秘密。在《鹿鼎记》第十五回中写道：
陶红英一笑，道：“这个誓倒是很新鲜古怪。我跟你说，满洲鞑子进关之时，并没想到竟能得到大明江山。满洲人很少，兵也不多，他们只盼能长远占住关外之地，便心满意足了，所以进关之后，八旗兵一见金银财宝，放手便抢。这些财宝，他们都运到了关外，收藏起来。当时执掌大权的是顺治皇帝的叔父摄政王。但是满洲八旗，每一旗都各有势力。当时八旗旗主会议，将收藏财物的秘密所在，绘成地图，由八旗旗主各执一幅………”韦小宝站起身来，大声道：“啊，我明白了！”大车一动，他又坐倒，道：“这八幅地图，便藏在那八部四十二章经之中。”陶红英道：“好像也并非就是如此，到底真相如何，只有当时这八旗旗主才明白，别说我们汉人中无人知晓，连满洲的王公大臣，恐怕也极少知道。我师父说，满洲人藏宝的那座山，是他们龙脉的所在。鞑子所以能占我大明江山，登基为皇，全仗这座山的龙脉。”
韦小宝问道：“什么龙脉?”陶红英道：“那是一个风水极好的地方，满洲鞑子的祖先葬在那山里，子孙大发，来到中国做了皇帝。我师父说，咱们若是找到那座宝山，将龙脉截断，再挖了坟，那么满洲鞑子非但做不成皇帝，还得尽数死在关内。这座宝山如此要紧，所以我太师父和师父花尽心血，要找到山脉的所在。这个大秘密，便藏在那八部四十二章经之中。”
小说的后面叙述，藏宝地图被绘在一张羊皮上，然后又被切割成许多碎片，八部四十二章经中所藏的，正是这些羊皮碎片。
对于小说中韦小宝如何费劲心机找全这八本四十二章经等情节，自然是《鹿鼎记》中非常重要和精彩的一部分，但是这里我们对它不感兴趣。我们感兴趣的，是满清贵族分摊这个大宝藏秘密的技术方法。
首先，因为“满洲八旗，每一旗都各有势力”，所以这个秘密不是某个个体的秘密，而是必须由八旗旗主一起来分摊的。
其次，某个单独的八旗旗主是不是就知道完整的秘密？不是的。他只有自己的那本四十二章经，里面是一堆拼不成完整地图的碎羊皮，光有这些碎羊皮，无法知道宝藏在哪里。摄政王多尔衮应该是知道整个秘密的，但是这里我们不把他算成分摊秘密的人。因为当时考虑的是比较长久以后的事，当时开会的人也许都死光了，那时持有这个秘密的人（尽管每人只持有一部分秘密）就只有那时的八旗旗主了。后来出现的比如八旗旗主有些入狱抄家的事，还有韦小宝这种怪胎，当时八旗旗主会议时，自然都没考虑到。
最后，如果八个旗主都决定要揭开这个秘密，掘出宝藏，那么他们就只需将每人所持的地图碎片取出拼成完整地图。
所以，这是一个被多个个体所分摊的秘密。每个个体都不单独掌握秘密，但是在所有个体一起决定要揭开秘密时，他们就能够知道完整的秘密。
下一步我们要看看这个方法的优点和缺点，以及如何改善这个方法，克服其缺点。
喝口水再说……
元宝推荐：老马丁,海天,铁手, 通宝推：隔路山贼,非吾有,铁手,思炎,landlord,柳叶刀,游识猷,
本帖一共被 1 帖 引用 (帖内工具实现)家园 【求助】实际工作中的问题，好像要用到密码学 刚刚看到了楼主的帖子，很受启发，看来我还得花些时间，慢慢消化。
现在我正好有一个工作中的问题，没有太多头绪，我想这个与密码学有联系，想请楼主不吝指教：
现在有十万种商品，都已编码，标准是九位数字：999-99-9999（前三位是部，中间两位是类，后面四位是项， 让我们用英文字母，D-C-I来代表）。
D的取值范围是 002-300，C：00-99 I：0001-9999.
现在，我们要在这十万种商品抽取若干种（1 到 30 种）。我要给这每一种抽法，编一个唯一的代码。要如何入手？
最直观的办法当然是，先排序，然后拼接在一起。但是这样太占空间，意味着代码长度达到9×30=270字节。（如果不足30 种，用0填充）。
有没有一种比较简单的算法，产生唯一的编码，而且长度控制在20字节以内（当然更少就更好）？我们放宽条件：产生的编码可以是串string（字母与数字混合）？
我自己初步设想是，先计算抽取的商品种类数目（比如抽12种，就用12作为编码的一部分），然后再与这12种商品编码的均值拼接，这样11 个字节就够了，但这样，“撞码”的几率较大？
家园 用string就容易些，可以做到5*30=150位编码 可以把产品码当作一个数字，比如最大的一个产品码是300999999，最小的一个产品码是002000001。
制定编码规则如下：把数字0-9，A-Z，a-z依次编码成0-61共62个码，每个数字对应一个字符，比如数字0对应字符0，数字26对应字符a。。。数字61对应字符Z
把产品码300999999除以62，得到整数XXX1和余数YYY1=43，记录YYY1；
继续把XXX1除以62，得到整数XXX2和余数YYY2，记录YYY2=52；
。。。59；
。。。22；
最后直到整数为0，余数小于62，记为YYYn=20
所以把所有余数按倒序排起来，即20，22，59，52，43。按照前面说的编码规则编成5个字符，我偷个懒就不对应了。这就是产品的编码。
解码的时候这么做：
首先把编码字符还原成0-61的数字串20，22，59，52，43。
第一个数字20，乘以62，得到ZZZ1；
第二个数字22+ZZZ1，得数再乘以62，得到ZZZ2；
第三个数字59+ZZZ2，得数再乘以62，得到ZZZ3；
第四个数字52+ZZZ3，得数再乘以62，得到ZZZ4；
第五个数字43+ZZZ4，即可得到原来的产品码300999999。
照此办理，把最小的产品码的编码计算出来。如果你的产品码都是连续的，那么有效抽法编码范围就在最小产品码与最大产品码之间，并且由于编码时是按照ASCII值的顺序，所以可以简单地用字符串比较的方法来验证随意生成的编码是否有效码了。
可惜的是你的产品码I的取值不包括0000，所以不够连续。只能先解码出产品码，再验证是否有效的产品码，如果无效的话就重新产生了。好在I取值0000的机会只有万分之一，所以在最小编码与最大编码之间随意产生的编码的有效率应该是9999/10000，成功率是很高的。考虑到有的产品码没有对应有效的产品（无效的产品码），所以只能解出产品码后再对照产品库的编码，确定这是否有效码了。
连续生成30个有效的5位产品编码，得到5×30个字符的抽取码。
+++++补充++++++
改进一下，编码规则里取消0。即用数字1-9,A-Z,a-z依次编成61个码。以后编码解码的时候都乘以或者除以61。这样产品编码长度仍然是5位，但是当只取12个产品的时候，其余30-12=18个产品码就可以用18个单独的0来表示。所以取12个产品的时候，抽取码长度是5*12+18=78位。
家园 谢谢各位，并汇报一下我最后的解决办法 楼主与你的办法都很有道理。
我发现在问题的实际处理中，我只需要确保同一次运算中，不出现撞码即可，两三千家商店总共只有最多百来种抽法，我编码目的是正确地将商店按抽法分组。所以HASH算法可能就够了。
但是我最终还是采用拼接法，因为它在编程上最简单。我只要将商店码与拼接码写入一个临时数据库的TABLE，就很容易产生分组码了，最多只要三字节。两三千条记录的TABLE对数据库系统是小意思。后面的复杂运算就采用这个三字节码即可。最后，再从临时TABLE调回实际的商品种类。这样也能避免运算过程中，长码造成的资源浪费。
家园 可以用120个字节 很简单，把每个产品码当做一个整数就是了。 最大的是300-99-9999， 完全可表达为一个4字节的整数。
排序好后按你的想法并列一下就是抽样的代码。30个数120个字节。
计算机里最少要64个字节表达30个1--10万的数。算法恐怕就太麻烦了。
家园 ding 恭喜：你意外获得【铢钱】八个
鲜花已成功送出，消耗 铢钱 1 个，可能得宝。可通过工具取消
提示：此次送花为【有效送花赞扬，加乐善、声望、帖得花总数】。
家园 这个要看你的需求了 如果只有10万种商品，但是希望尽量减少编码的字节，那么应该把这种商品编码转换成内部编码，从0到999999编号。如果不愿意做这个转换，那么下面的100000都要换成1000000000。
如果说允许撞码，只是希望撞码可能性小一点，那么这就是希望找一个好的哈希函数（也叫杂凑函数）。象你这样取平均值也是一种哈希函数，但是效果显然不好，因为那些比较大和比较小的编码没有比较中间那些编码容易被取到。我觉得取加起来再除以100000的余数来做编码（再拿抽取的数目拼接也可以），要比平均值好，因为它的“撞码率”均匀。而且这个方法也容易扩张，如果你还想缩短字节数，可以除以10000，如果觉得字节数长一些也没关系，那么就除以更大的数。
如果说不允许撞码，那么代码长度不可能小于log(100000^30/30!)，也就是差不多150-log(30!)，大约是117字节左右。
家园 等楼主解答，圆桌会议 1 5把钥匙，有任意3把就能打开锁
2 5把钥匙，但是其中1把顶2把用（权重2），任意3把能打开锁，
3 对已丢失钥匙的废弃。。。
《应用密码学-算法、协议与源程序》 ^_^
家园 回答第二题 第一题就是（六）讲过的，第三题估计不会讲了这方面的内容了，第二题却很简单也很值得一提。
5把钥匙，但是其中1把顶2把用（权重2），任意3把能打开锁，那么其实那把权重2的钥匙其实就是两把钥匙，只要制作6把钥匙，使得其中任何3把在一起就可以打开锁，把其中的两把给同一个人的话，这个人其实就是有了一把权重2的钥匙。
这在实际中也很有用处的，每个人的重要性不一定都相同。公司的董事长也许一个人就可以决定是否揭开秘密，但是执行董事的话必须有三人以上同意才行，至于一般董事则要10人以上。制作一把顶n把钥匙的方法就可以解决这种问题。
家园 我想这个宝 的分发对作者是最优解。
谢谢：作者意外获得【通宝】一枚
鲜花已成功送出，消耗 铢钱 1 个，可能得宝。可通过工具取消
提示：此次送花为【有效送花赞扬，加乐善、声望、帖得花总数】。
家园 说的是Zero knowledge吧 家园 送花，回帖都是一个技术活，老铁太厉害了 送花 关闭
恭喜：你意外获得【通宝】一枚
鲜花已成功送出，消耗 铢钱 1 个，可能得宝。可通过工具取消
提示：此次送花为【有效送花赞扬，加乐善、声望、帖得花总数】。
送花 关
家园 有宝 谢谢：作者意外获得【通宝】一枚
鲜花已成功送出，消耗 铢钱 1 个，可能得宝。可通过工具取消
提示：此次送花为【有效送花赞扬，加乐善、声望、帖得花总数】。