V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
fbxshit
V2EX  ›  问与答

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

  •  
  •   fbxshit · 2019-04-28 10:53:14 +08:00 via Android · 5283 次点击
    这是一个创建于 1797 天前的主题,其中的信息可能已经有所发展或是发生改变。

    为了安全性,这两个数不能存到内存中,也不能保存到 cpu 寄存器中。

    对于两数 a 和 b 加法,我能想到的是,取一个随机数 c,把 a 加 c 的结果输入计算机,然后把 b 减 c 的结果输入计算机。

    那么对于 a 乘 b,如何做到让计算机得出答案,但是没有办法推测出 a 和 b?

    51 条回复    2019-09-20 02:07:10 +08:00
    fbxshit
        2
    fbxshit  
    OP
       2019-04-28 10:58:35 +08:00 via Android
    @toyassb 两个大数乘法,可能有数百位。
    dbw9580
        3
    dbw9580  
       2019-04-28 11:00:55 +08:00 via Android   ❤️ 5
    同态加密
    neon4o4
        4
    neon4o4  
       2019-04-28 11:03:05 +08:00 via Android
    把数字截成两半,分别在两个 cpu 上算,算完汇总一下…
    nutting
        5
    nutting  
       2019-04-28 11:04:54 +08:00
    什么环境要求这么高,不联网也不行?干脆不能用计算机?树莓派可以吗?装到铁盒子里屏蔽也不行?
    fbxshit
        6
    fbxshit  
    OP
       2019-04-28 11:09:12 +08:00 via Android
    @neon4o4 怎么截?如果分两个 cpu 算,第三个 cpu 汇总,我希望第三个 cpu 也无法知道我原来的两个数 a 和 b。
    yanaraika
        7
    yanaraika  
       2019-04-28 11:11:22 +08:00 via Android
    只有同态加密是对的,你的方法一对方直接把 a+c 和 b-c 一减就能得到 a-b,一加得到 a+b 就能恢复出原来的数据
    Raisu
        8
    Raisu  
       2019-04-28 11:11:36 +08:00
    不能保存到寄存器中,那 CPU 的 ALU 怎么拿到数据?
    fbxshit
        9
    fbxshit  
    OP
       2019-04-28 11:12:00 +08:00 via Android
    @nutting 为了从理论上防止一切安全漏洞,就是在完全不告诉计算机我要计算的原始数据的情况下,利用 cpu 的计算能力。
    yanaraika
        10
    yanaraika  
       2019-04-28 11:12:15 +08:00 via Android
    不论如何你总要信任最后得到结果的某个部件,如果不信任 cpu 可以用 tpm 之类的解决方案
    yanaraika
        11
    yanaraika  
       2019-04-28 11:13:37 +08:00 via Android
    @yanaraika 看错了 但我非常怀疑这个针对多次运算的密码学强度
    fbxshit
        12
    fbxshit  
    OP
       2019-04-28 11:13:48 +08:00 via Android
    @yanaraika 对于加法,你不知道我的随机数 c,你是无法推测出 a 和 b 的。
    fbxshit
        13
    fbxshit  
    OP
       2019-04-28 11:19:54 +08:00 via Android
    @yanaraika 我可以信任一个最小化的系统,由这个最小化的系统对数据进行预处理,然后把处理过的数据放入另一个真正进行计算的计算机。最初的那个预处理机器如果叫 x,真正计算的机器叫 y,那么我可以完全不用担心 y 机器的任何安全漏洞,因为就像加密过的数据一样,连要计算什么都是加密过的。
    fbxshit
        14
    fbxshit  
    OP
       2019-04-28 11:22:00 +08:00 via Android
    @Raisu 不能让 cpu 拿到我的乘数 a 和 b,但是要给我返回 a 乘 b,假设 a 和 b 是两个极大的素数。
    fbxshit
        15
    fbxshit  
    OP
       2019-04-28 11:29:10 +08:00 via Android
    @dbw9580 感谢
    leo108
        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
    lrigi
        17
    lrigi  
       2019-04-28 11:43:38 +08:00 via iPhone
    @dbw9580
    @fbxshit
    我有个问题
    运行同态加密的时候就需要把数据输入计算机才能得出密文
    如果数据可以输入计算机 那直接算不就行了?
    感觉楼主提出了一个不可能事件?
    lrigi
        18
    lrigi  
       2019-04-28 11:46:05 +08:00 via iPhone
    @leo108
    第一台电脑 ab 不就输进去了吗……
    第三台电脑里面甚至 c a b 都知道了……
    leo108
        19
    leo108  
       2019-04-28 12:02:19 +08:00
    @lrigi 第一台电脑只计算了 a^2,第四台确实一次性计算这些确实不妥,但是可以把这个公式拆分到更多的系统去计算。

    这样可以保证没有任何一台电脑能同时拿到 a b 两个的原始值。
    TomVista
        20
    TomVista  
       2019-04-28 12:20:37 +08:00   ❤️ 4
    也不能保存到 cpu 寄存器中 ??

    不用讨论了吧,脱离 cpu 寄存器进行运算,虽然我机组挂科了,但我也知道冯诺依曼和图灵的棺材板都做不到这件事.
    rrfeng
        21
    rrfeng  
       2019-04-28 12:29:43 +08:00
    如果计算机可以知道一个数的话那一台就够了啊

    告诉他计算 让他计算 a(b+1) - a
    goodryb
        22
    goodryb  
       2019-04-28 12:43:11 +08:00
    考虑这个问题的前提是,计算机是一个完整的系统,而不是把他拆分成单个组件。

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

    不要局限于太细节的东西,钻了牛角尖,重新审视一下需求。
    miaomiao0323
        23
    miaomiao0323  
       2019-04-28 12:44:33 +08:00
    多方安全计算问题吧,https://segmentfault.com/a/1190000018485299
    ruimz
        24
    ruimz  
       2019-04-28 12:44:54 +08:00 via Android
    @TomVista 你不是计组不好,是语文不好。分明说的是 ab 两个数不能进内存和寄存器,可没说运算的过程不能进寄存器
    keith1126
        25
    keith1126  
       2019-04-28 13:01:55 +08:00   ❤️ 1
    友情提醒各位,这个问题偏学术,是密码学问题
    watzds
        26
    watzds  
       2019-04-28 13:04:20 +08:00 via Android
    类似分解后再计算吧,比如 (a1+a2 …) * ( b1+ b2 …) 拆开单独计算 a1 b1
    cigarzh
        27
    cigarzh  
       2019-04-28 13:09:45 +08:00
    基于同态加密的多方保密计算
    一堆论文
    herozhang
        28
    herozhang  
       2019-04-28 13:22:46 +08:00 via iPhone
    换个思路,输入一大堆乘法运算,得到一大堆结果,但是只有输入方知道哪个结果才是真正想要的
    ZavierXu
        29
    ZavierXu  
       2019-04-28 13:31:27 +08:00
    不要自作聪明发明算法,密码学没有你想象的这么简单。
    楼主讨论的情况我觉得可以尽可能地隐去保密内容后把现有的情况和想要达到的目的说出来,因为我觉得你所描述的方法不一定是解决你的问题的方法
    babalarf
        30
    babalarf  
       2019-04-28 13:38:52 +08:00
    换成对数,然后就是加减法
    Fazauw
        31
    Fazauw  
       2019-04-28 13:42:16 +08:00 via Android
    ab=(a+c)(b+c)-c(a+b)-c**2
    TomVista
        32
    TomVista  
       2019-04-28 14:07:48 +08:00
    @ruimz 我可能真的语文不好.小明不吃屎.小明吃饭的时候会吃屎.
    jie170601
        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 的,虽然可能不是唯一解,要是找个方法让分解后的方程组有无穷多解就好了
    nmdx
        34
    nmdx  
       2019-04-28 14:25:19 +08:00 via Android
    插句题外的。。学语文的作用是为了让人尝试去理解别人的意思。。。而不是为了去杠
    freeandi
        35
    freeandi  
       2019-04-28 14:37:25 +08:00
    3 月 18 日,数学家 David Harvey 和 Joris van der Hoeven (分别来自新南威尔士大学和巴黎综合理工大学)在 HAL (法国国家科学研究中心机构库)提交了一篇论文,论文描述了一个将两个非常大的数字相乘的新方法,这是迄今为止发现的最快、最高效的乘法算法。
    hmzt
        36
    hmzt  
       2019-04-28 14:40:13 +08:00
    建议用算盘或者机械计算器呢
    TomVista
        37
    TomVista  
       2019-04-28 15:10:22 +08:00
    @nmdx 抱歉.
    TomVista
        38
    TomVista  
       2019-04-28 15:21:53 +08:00
    @nmdx 我收回我的道歉,

    突然有点生气.

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

    我能怎么办?总想搞事情.
    purplewall
        39
    purplewall  
       2019-04-28 15:22:36 +08:00
    这不可能吧,从文件 io 肯定要内存映射,就算直接把数据写死在数据 section/segment 里面代码也要放在内存上才能运行啊,楼上说用算盘那个比较靠谱,理论上算盘机的计算能力和图灵机是一样的。
    TomVista
        40
    TomVista  
       2019-04-28 15:33:25 +08:00
    @nmdx 我就不应该说我自己机组挂科,对不对.我不说他就不会反驳我语文不好,对不对,我就不会说小明到底吃不吃屎.

    你说对不对?
    我脑子有坑,过来找找嘲讽,对不对.
    ylrshui
        41
    ylrshui  
       2019-04-28 17:03:52 +08:00 via iPhone
    ab=((a+b)^2-(a-b)^2)/4
    a+b、a-b 已经有方法了
    jie170601
        42
    jie170601  
       2019-04-28 17:22:50 +08:00
    @ylrshui 输入 a+b,a-b 的结果时还是能推算出 a 和 b 的值
    akira
        43
    akira  
       2019-04-28 20:50:57 +08:00
    a b 分别做二进制展开,然后分别做多项式加法 乘法运算
    skadi
        44
    skadi  
       2019-04-28 20:54:36 +08:00
    同态加密.我记得密码学上讲过.
    morethansean
        45
    morethansean  
       2019-04-28 21:01:24 +08:00 via Android
    @TomVista 都不对,你应该好好学习,这样你既不会计组挂科,还能看懂这个帖子到底要讨论啥。
    geelaw
        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。
    linhua
        47
    linhua  
       2019-04-28 23:28:15 +08:00
    KaraTsuba 乘法
    ldm0
        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)
    研究了很久希望能对楼主有帮助
    fbxshit
        49
    fbxshit  
    OP
       2019-05-05 12:22:22 +08:00
    @ldm0 如果需要提供 x*y-1,还不如自己本地计算 a*b 了。

    如果用随机数做安全处理后再把计算任务交给远程计算机做,前提是这个预处理
    消耗的资源要小于本身要计算的任务,否则还不如我自己算 a*b。
    ldm0
        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。这整个流程就不需要相乘,只是结果不是到手就能用的。
    b00tyhunt3r
        51
    b00tyhunt3r  
       2019-09-20 02:07:10 +08:00 via iPad
    分布式就是干这个的啊
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5255 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 44ms · UTC 09:15 · PVG 17:15 · LAX 02:15 · JFK 05:15
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.