[求助]两个人各持有一个[1,5]之间的整数，如何在不泄露各自持有数字的情况下，比较持有的数字是否相等-密码应用-看雪-安全社区|安全招聘|kanxue.com

[求助]两个人各持有一个[1,5]之间的整数，如何在不泄露各自持有数字的情况下，比较持有的数字是否相等

2018-8-31 14:40 5527

[求助]两个人各持有一个[1,5]之间的整数，如何在不泄露各自持有数字的情况下，比较持有的数字是否相等

cejay

活跃值

2018-8-31 14:40

5527

两个人各持有一个[1,5]之间的整数，如何在不泄露各自持有数字的情况下，比较持有的数字是否相等。

一个类似的问题是“姚氏百万富翁问题”，但是这个问题解决的是如何在不公开的情况下判断两个人持有数字的大小。在我这里只是判断持有的数字是否相等，即使连大小都不能被猜出来

求熟悉相关问题的同志给点思路，或者现成的算法，感激不尽！！！

[培训]《安卓高级研修班(网课)》月薪三万计划，掌握调试、分析还原ollvm、vmp的方法，定制art虚拟机自动化脱壳的方法

收藏・3

点赞・0

打赏

分享

最新回复 (13)
bambooqj 雪币： 781 活跃值： (1071) 能力值： ( LV5，RANK：78 ) 在线值：发帖 31 回帖 348 粉丝 36 关注私信	bambooqj 2018-8-31 15:10 2 楼 0 数学问题不懂..有个思路不知道对不对.. 持有数字 1 - 5 已知随机数不随机 . 大部分编程语言随机数算法基本相同比如 srand(0) rand 第一次必为38.当然这个随机数算法你可以自己去实现. 我以1为随机数种子循环X次这个X可以用时间戳计算最好不要太大. 得到结果 X=666 结果=26740 发送 666.26740 到你那边带入 1-5 进行查询对比.比较笨主要好写 2333 资源耗费也比较大..不过我这种小学毕业的只能这个程度了. 数学算法的话应该用圆周法或者方程模式吧..反正我就是水个经验.说的不对别打我. 最后于 2018-8-31 15:13 被bambooqj编辑，原因：
yeyeshun 雪币： 205 活跃值： (2659) 能力值： ( LV7，RANK：140 ) 在线值：发帖 12 回帖 394 粉丝 13 关注私信	yeyeshun 2 2018-8-31 15:31 3 楼 0 加入一个相同的第三方数据，增加复杂度，然后求出一个HASH，对比HASH是否相等就知道了。如果比大小的话不行，但是只判断是否相等是足够的
bambooqj 雪币： 781 活跃值： (1071) 能力值： ( LV5，RANK：78 ) 在线值：发帖 31 回帖 348 粉丝 36 关注私信	bambooqj 2018-8-31 15:34 4 楼 0 yeyeshun 加入一个相同的第三方数据，增加复杂度，然后求出一个HASH，对比HASH是否相等就知道了。如果比大小的话不行，但是只判断是否相等是足够的还是岳父大人懂.
cejay 雪币： 19 活跃值： (40) 能力值： ( LV3，RANK：20 ) 在线值：发帖 3 回帖 19 粉丝 2 关注私信	cejay 2018-8-31 15:34 5 楼 0 谢谢回复，此方法最终需要每个数带入对比，如果数字不相同，也是应该会导致知道对方持有的数字的吧
cejay 雪币： 19 活跃值： (40) 能力值： ( LV3，RANK：20 ) 在线值：发帖 3 回帖 19 粉丝 2 关注私信	cejay 2018-8-31 15:44 6 楼 0 yeyeshun 加入一个相同的第三方数据，增加复杂度，然后求出一个HASH，对比HASH是否相等就知道了。如果比大小的话不行，但是只判断是否相等是足够的谢谢回复，您的方案如果加入了相同的第三方数据，会导致可以根据对方hash，通过自己的遍历得到对方原始值得（因为就5个数，挨个数算下hash就知道了）
bambooqj 雪币： 781 活跃值： (1071) 能力值： ( LV5，RANK：78 ) 在线值：发帖 31 回帖 348 粉丝 36 关注私信	bambooqj 2018-8-31 15:48 7 楼 0 cejay 谢谢回复，此方法最终需要每个数带入对比，如果数字不相同，也是应该会导致知道对方持有的数字的吧算法在你自己手里啊...就算我用圆周法我也是要带数做差啊.
cejay 雪币： 19 活跃值： (40) 能力值： ( LV3，RANK：20 ) 在线值：发帖 3 回帖 19 粉丝 2 关注私信	cejay 2018-8-31 15:59 8 楼 0 感谢回复，但是您的方案会导致手中持有的数字会泄露的
轩辕之风雪币： 2290 活跃值： (908) 能力值： ( LV8，RANK：130 ) 在线值：发帖 34 回帖 298 粉丝 62 关注私信	轩辕之风 1 2018-8-31 17:17 9 楼 0 cejay 谢谢回复，您的方案如果加入了相同的第三方数据，会导致可以根据对方hash，通过自己的遍历得到对方原始值得（因为就5个数，挨个数算下hash就知道了）根据这个思路扩展一下，如果这个第三方数据是个不可预测的数呢？比如引入一个执行时动态获取时间毫秒数，你不就不能根据HASH值去反推了吗
cejay 雪币： 19 活跃值： (40) 能力值： ( LV3，RANK：20 ) 在线值：发帖 3 回帖 19 粉丝 2 关注私信	cejay 2018-8-31 17:22 10 楼 0 轩辕之风根据这个思路扩展一下，如果这个第三方数据是个不可预测的数呢？比如引入一个执行时动态获取时间毫秒数，你不就不能根据HASH值去反推了吗感谢回复，两个互不信任的人即使同时引入不可预测的数据，也是可以遍历反推的，你想想看
arab 雪币： 7582 活跃值： (3249) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 82 粉丝 1 关注私信	arab 2018-9-3 16:10 11 楼 0 抽象一下, 楼主的需求是在指定的区间[a,b]内, 求算法F, 使得在不泄露x1, x2的情况下, 能通过F(x1), F(x2)的值比较x1, x2的大小或是否相同. 那么这就有个问题了, 谁来比较 F(x1), F(x2)? 如果不引入双方可信的第三方的话, 在[a,b]范围很小的情况下, 无论用什么算法F, 双方都可以使用遍历的方式穷举出所有数x对应的F(x), 从而由F(x)得到对方的数据x.
jmpcall 雪币： 2327 活跃值： (10043) 能力值： ( LV9，RANK：230 ) 在线值：发帖 32 回帖 192 粉丝 50 关注私信	jmpcall 3 2018-9-3 18:02 12 楼 0 数字是几，就拿几克的砝码，天平中间用东西隔开。
cejay 雪币： 19 活跃值： (40) 能力值： ( LV3，RANK：20 ) 在线值：发帖 3 回帖 19 粉丝 2 关注私信	cejay 2018-9-4 17:00 13 楼 0 arab 抽象一下, 楼主的需求是在指定的区间[a,b]内, 求算法F, 使得在不泄露x1, x2的情况下, 能通过F(x1), F(x2)的值比较x1, x2的大小或是否相同. 那么这就有个问题了, 谁来比 ... 你说的对，需要规避可穷举的问题。
wawal哇雪币： 20 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 8 粉丝 0 关注私信	wawal哇 2018-9-28 17:17 14 楼 0 用姚教授的安全两方计算没问题啊，判断相等这个命题是可以转换成门电路的。具体的，设两方为A、B; A为证明方，B是验证方；GC阶段A为A1至A5和B1至B5分配随机数标识r1-r10，kdf得出所有密钥，k1=(r1,r6)...k25=(r5,r10)，A模拟所有执行结果，相同标1，不同标0，用k的哈希对执行结果加密，计算y1=enc(h(k1),1)....y25=enc(h(k25),1); 把Y数组顺序置乱发给B;同时，A将自己选的数的标签ra(r1-r5中的一个)发给B. B的视角：25个密文(y1-y25，乱序), A的标签ra，如果B能拿到A对自己选的数打的标签rb，就可以计算kdf(ra,rb)=k,进而计算25次dec(y,k)，其中只有一次能正确解密，解密后得到1代表相同，0代表不同。如果A将B的五个标签都发给B，B就可以通过解密穷举出A的数，但A也不能直接问B你选的哪个数。这里B需要用到OT(oblivious transfer)协议来得到rb，里面有rsa的交互，具体不展开了，OT达到的目的是：A拥有r6-r10五个标签，B确定自己选的数，直到协议完成，A不知道B选的是哪个，B能获得与所选数对应的rb，但不能获得其他四个r。
	游客登录 \| 注册方可回帖　回帖　表情雪币赚取及消费高级回复

返回

cejay

发帖

回帖

RANK

关注

他的文章

[求助]两个人各持有一个[1,5]之间的整数，如何在不泄露各自持有数字的情况下，比较持有的数字是否相等

[原创]逆向360加固等dex被隐藏的APK

[求助]android中C程序如何调用JAVA方法

看雪公众号

专注于PC、移动、智能设备安全研究及逆向工程的开发者社区