想要做两个大数的乘法，但是这两个数不能输入计算机，怎么做到？

计算机

输入

寄存器

乘法

51 条回复 • 2019-09-20 02:07:10 +08:00

1

toyassb

2019-04-28 10:56:31 +08:00

https://zh.wikipedia.org/wiki/%E6%9C%BA%E6%A2%B0%E8%AE%A1%E7%AE%97%E6%9C%BA

2

fbxshit

OP

2019-04-28 10:58:35 +08:00 via Android

@toyassb 两个大数乘法，可能有数百位。

3

dbw9580

2019-04-28 11:00:55 +08:00 via Android

5

同态加密

4

neon4o4

2019-04-28 11:03:05 +08:00 via Android

把数字截成两半，分别在两个 cpu 上算，算完汇总一下…

5

nutting

2019-04-28 11:04:54 +08:00

什么环境要求这么高，不联网也不行？干脆不能用计算机？树莓派可以吗？装到铁盒子里屏蔽也不行？

6

fbxshit

OP

2019-04-28 11:09:12 +08:00 via Android

@neon4o4 怎么截？如果分两个 cpu 算，第三个 cpu 汇总，我希望第三个 cpu 也无法知道我原来的两个数 a 和 b。

7

yanaraika

2019-04-28 11:11:22 +08:00 via Android

只有同态加密是对的，你的方法一对方直接把 a+c 和 b-c 一减就能得到 a-b，一加得到 a+b 就能恢复出原来的数据

8

Raisu

2019-04-28 11:11:36 +08:00

不能保存到寄存器中，那 CPU 的 ALU 怎么拿到数据？

9

fbxshit

OP

2019-04-28 11:12:00 +08:00 via Android

@nutting 为了从理论上防止一切安全漏洞，就是在完全不告诉计算机我要计算的原始数据的情况下，利用 cpu 的计算能力。

10

yanaraika

2019-04-28 11:12:15 +08:00 via Android

不论如何你总要信任最后得到结果的某个部件，如果不信任 cpu 可以用 tpm 之类的解决方案

11

yanaraika

2019-04-28 11:13:37 +08:00 via Android

@yanaraika 看错了但我非常怀疑这个针对多次运算的密码学强度

12

fbxshit

OP

2019-04-28 11:13:48 +08:00 via Android

@yanaraika 对于加法，你不知道我的随机数 c,你是无法推测出 a 和 b 的。

13

fbxshit

OP

2019-04-28 11:19:54 +08:00 via Android

@yanaraika 我可以信任一个最小化的系统，由这个最小化的系统对数据进行预处理，然后把处理过的数据放入另一个真正进行计算的计算机。最初的那个预处理机器如果叫 x，真正计算的机器叫 y，那么我可以完全不用担心 y 机器的任何安全漏洞，因为就像加密过的数据一样，连要计算什么都是加密过的。

14

fbxshit

OP

2019-04-28 11:22:00 +08:00 via Android

@Raisu 不能让 cpu 拿到我的乘数 a 和 b，但是要给我返回 a 乘 b,假设 a 和 b 是两个极大的素数。

15

fbxshit

OP

2019-04-28 11:29:10 +08:00 via Android

@dbw9580 感谢

16

leo108

2019-04-28 11:39:21 +08:00

『我可以信任一个最小化的系统』，如果有 4 台这样的最小系统，分别计算 a^2 / b^2，然后人肉计算 c=a+b，第三台计算 c^2，第四台计算 (c^2-a^2-b^2)/2

17

lrigi

2019-04-28 11:43:38 +08:00 via iPhone

@dbw9580
@fbxshit
我有个问题
运行同态加密的时候就需要把数据输入计算机才能得出密文
如果数据可以输入计算机那直接算不就行了？
感觉楼主提出了一个不可能事件？

18

lrigi

2019-04-28 11:46:05 +08:00 via iPhone

@leo108
第一台电脑 ab 不就输进去了吗……
第三台电脑里面甚至 c a b 都知道了……

19

leo108

2019-04-28 12:02:19 +08:00

@lrigi 第一台电脑只计算了 a^2，第四台确实一次性计算这些确实不妥，但是可以把这个公式拆分到更多的系统去计算。

这样可以保证没有任何一台电脑能同时拿到 a b 两个的原始值。

20

TomVista

2019-04-28 12:20:37 +08:00

4

也不能保存到 cpu 寄存器中 ??

不用讨论了吧,脱离 cpu 寄存器进行运算,虽然我机组挂科了,但我也知道冯诺依曼和图灵的棺材板都做不到这件事.

21

rrfeng

2019-04-28 12:29:43 +08:00

如果计算机可以知道一个数的话那一台就够了啊

告诉他计算让他计算 a(b+1) - a

22

goodryb

2019-04-28 12:43:11 +08:00

考虑这个问题的前提是，计算机是一个完整的系统，而不是把他拆分成单个组件。

要么你信任这个计算系统，要么你不信任这个系统。

不要局限于太细节的东西，钻了牛角尖，重新审视一下需求。

23

miaomiao0323

2019-04-28 12:44:33 +08:00

多方安全计算问题吧，https://segmentfault.com/a/1190000018485299

24

ruimz

2019-04-28 12:44:54 +08:00 via Android

@TomVista 你不是计组不好，是语文不好。分明说的是 ab 两个数不能进内存和寄存器，可没说运算的过程不能进寄存器

25

keith1126

2019-04-28 13:01:55 +08:00

1

友情提醒各位，这个问题偏学术，是密码学问题

26

watzds

2019-04-28 13:04:20 +08:00 via Android

类似分解后再计算吧，比如 (a1+a2 …) * ( b1+ b2 …) 拆开单独计算 a1 b1

27

cigarzh

2019-04-28 13:09:45 +08:00

基于同态加密的多方保密计算
一堆论文

28

herozhang

2019-04-28 13:22:46 +08:00 via iPhone

换个思路，输入一大堆乘法运算，得到一大堆结果，但是只有输入方知道哪个结果才是真正想要的

29

ZavierXu

2019-04-28 13:31:27 +08:00

不要自作聪明发明算法，密码学没有你想象的这么简单。
楼主讨论的情况我觉得可以尽可能地隐去保密内容后把现有的情况和想要达到的目的说出来，因为我觉得你所描述的方法不一定是解决你的问题的方法

30

babalarf

2019-04-28 13:38:52 +08:00

换成对数，然后就是加减法

31

Fazauw

2019-04-28 13:42:16 +08:00 via Android

ab=(a+c)(b+c)-c(a+b)-c**2

32

TomVista

2019-04-28 14:07:48 +08:00

@ruimz 我可能真的语文不好.小明不吃屎.小明吃饭的时候会吃屎.

33

jie170601

2019-04-28 14:25:18 +08:00

如果加个随机数 c 的这种加法可以接受的话，那乘法为什么不用(a*c)*(b/c),（ c!=0 ），是考虑到整除的问题吗

#26 的方法好像可以，不过分解得做复杂点
如果分解成 a*b = a1*b1+a1*b2+a2*b1+a2*b2 的话，通过方程组可以解出 a，b 的，虽然可能不是唯一解，要是找个方法让分解后的方程组有无穷多解就好了

34

nmdx

2019-04-28 14:25:19 +08:00 via Android

插句题外的。。学语文的作用是为了让人尝试去理解别人的意思。。。而不是为了去杠

35

freeandi

2019-04-28 14:37:25 +08:00

3 月 18 日，数学家 David Harvey 和 Joris van der Hoeven （分别来自新南威尔士大学和巴黎综合理工大学）在 HAL （法国国家科学研究中心机构库）提交了一篇论文，论文描述了一个将两个非常大的数字相乘的新方法，这是迄今为止发现的最快、最高效的乘法算法。

36

hmzt

2019-04-28 14:40:13 +08:00

建议用算盘或者机械计算器呢

37

TomVista

2019-04-28 15:10:22 +08:00

@nmdx 抱歉.

38

TomVista

2019-04-28 15:21:53 +08:00

@nmdx 我收回我的道歉,

突然有点生气.

呕吼.完蛋.我就不应该插入不知道从哪飞过来的纠纷,我就不应该,说什么棺材板.本来开开心心刷个帖子,成了杠精.

我能怎么办?总想搞事情.

39

purplewall

2019-04-28 15:22:36 +08:00

这不可能吧，从文件 io 肯定要内存映射，就算直接把数据写死在数据 section/segment 里面代码也要放在内存上才能运行啊，楼上说用算盘那个比较靠谱，理论上算盘机的计算能力和图灵机是一样的。

40

TomVista

2019-04-28 15:33:25 +08:00

@nmdx 我就不应该说我自己机组挂科,对不对.我不说他就不会反驳我语文不好,对不对,我就不会说小明到底吃不吃屎.

你说对不对?
我脑子有坑,过来找找嘲讽,对不对.

41

ylrshui

2019-04-28 17:03:52 +08:00 via iPhone

ab=((a+b)^2-(a-b)^2)/4
a+b、a-b 已经有方法了

42

jie170601

2019-04-28 17:22:50 +08:00

@ylrshui 输入 a+b,a-b 的结果时还是能推算出 a 和 b 的值

43

akira

2019-04-28 20:50:57 +08:00

a b 分别做二进制展开，然后分别做多项式加法乘法运算

44

skadi

2019-04-28 20:54:36 +08:00

同态加密.我记得密码学上讲过.

45

morethansean

2019-04-28 21:01:24 +08:00 via Android

@TomVista 都不对，你应该好好学习，这样你既不会计组挂科，还能看懂这个帖子到底要讨论啥。

46

geelaw

2019-04-28 21:41:20 +08:00 via iPhone

这个问题只有 a、b 来自两个人的时候才有意义，否则你可以自己计算。（对于一个人自己想要委托别人进行计算的情况，恐怕同态加密并不划算，因为同态加密、解密本身的时间已经远远超过两个数相乘。）

假设两个数的乘积不超过 p （不需要是质数），把所有的运算搬运到 mod p 里面进行，为了计算 ab，先计算 u=a+r, v=b+s, x=-sa+t, y=-rb-t-rs，其中 rst 是随机数，那么 ab=uv+x+y。

给定 ab （乘积），uvx 是三个独立随机数，而 y 是惟一满足方程 uv+x+y=ab 的数，所以这几个数只透露了 ab。

这个方法就是信息论安全的乱码电路，见于论文 How to Garble Arithmetic Circuits。

47

linhua

2019-04-28 23:28:15 +08:00

KaraTsuba 乘法

48

ldm0

2019-05-04 01:58:03 +08:00

一个完美解法：
找到两个随机数 x,y，满足 x*y - 1 > a * b
向计算方提供 x * a, y * b, x * y - 1，
然后计算函数就是 a * b = ((x * a) * (y * b)) mod (x * y - 1)
研究了很久希望能对楼主有帮助

49

fbxshit

OP

2019-05-05 12:22:22 +08:00

@ldm0 如果需要提供 x*y-1，还不如自己本地计算 a*b 了。

如果用随机数做安全处理后再把计算任务交给远程计算机做，前提是这个预处理
消耗的资源要小于本身要计算的任务，否则还不如我自己算 a*b。

50

ldm0

2019-05-05 13:55:48 +08:00

@fbxshit
首先，我觉得可以查表来分解计算压力，首先在本地预先构建一个足够大的 x, y, x*y - 1 表，发布的时候查一下，而且 x 和 y 的值不一定要很复杂，找一些好计算的数值就可以，方便计算 x * a 和 y * b。
第二，其实那个 x * y - 1 是一个 workaround。我第一眼想到的解法是给 a + p 和 b + p （其中 p > a * b)，然后计算机计算相乘，结果返回之后自己模 p。这整个流程就不需要相乘，只是结果不是到手就能用的。

51

b00tyhunt3r

2019-09-20 02:07:10 +08:00 via iPad

分布式就是干这个的啊