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

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

  •  
  •   fbxshit · 230 天前 via Android · 3875 次点击
    这是一个创建于 230 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

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

    这样可以保证没有任何一台电脑能同时拿到 a b 两个的原始值。
        20
    TomVista   230 天前   ♥ 3
    也不能保存到 cpu 寄存器中 ??

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

    告诉他计算 让他计算 a(b+1) - a
        22
    goodryb   230 天前
    考虑这个问题的前提是,计算机是一个完整的系统,而不是把他拆分成单个组件。

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

    不要局限于太细节的东西,钻了牛角尖,重新审视一下需求。
        23
    miaomiao0323   230 天前
    多方安全计算问题吧,https://segmentfault.com/a/1190000018485299
        24
    ruimz   230 天前 via Android
    @TomVista 你不是计组不好,是语文不好。分明说的是 ab 两个数不能进内存和寄存器,可没说运算的过程不能进寄存器
        25
    keith1126   230 天前
    友情提醒各位,这个问题偏学术,是密码学问题
        26
    watzds   230 天前 via Android
    类似分解后再计算吧,比如 (a1+a2 …) * ( b1+ b2 …) 拆开单独计算 a1 b1
        27
    cigarzh   230 天前
    基于同态加密的多方保密计算
    一堆论文
        28
    herozhang   230 天前 via iPhone
    换个思路,输入一大堆乘法运算,得到一大堆结果,但是只有输入方知道哪个结果才是真正想要的
        29
    ZavierXu   230 天前
    不要自作聪明发明算法,密码学没有你想象的这么简单。
    楼主讨论的情况我觉得可以尽可能地隐去保密内容后把现有的情况和想要达到的目的说出来,因为我觉得你所描述的方法不一定是解决你的问题的方法
        30
    babalarf   230 天前
    换成对数,然后就是加减法
        31
    Fazauw   230 天前 via Android
    ab=(a+c)(b+c)-c(a+b)-c**2
        32
    TomVista   230 天前
    @ruimz 我可能真的语文不好.小明不吃屎.小明吃饭的时候会吃屎.
        33
    jie170601   230 天前
    如果加个随机数 c 的这种加法可以接受的话,那乘法为什么不用(a*c)*(b/c),( c!=0 ),是考虑到整除的问题吗

    #26 的方法好像可以,不过分解得做复杂点
    如果分解成 a*b = a1*b1+a1*b2+a2*b1+a2*b2 的话,通过方程组可以解出 a,b 的,虽然可能不是唯一解,要是找个方法让分解后的方程组有无穷多解就好了
        34
    nmdx   230 天前 via Android
    插句题外的。。学语文的作用是为了让人尝试去理解别人的意思。。。而不是为了去杠
        35
    freeandi   230 天前
    3 月 18 日,数学家 David Harvey 和 Joris van der Hoeven (分别来自新南威尔士大学和巴黎综合理工大学)在 HAL (法国国家科学研究中心机构库)提交了一篇论文,论文描述了一个将两个非常大的数字相乘的新方法,这是迄今为止发现的最快、最高效的乘法算法。
        36
    hmzt   230 天前
    建议用算盘或者机械计算器呢
        37
    TomVista   230 天前
    @nmdx 抱歉.
        38
    TomVista   230 天前
    @nmdx 我收回我的道歉,

    突然有点生气.

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

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

    你说对不对?
    我脑子有坑,过来找找嘲讽,对不对.
        41
    ylrshui   230 天前 via iPhone
    ab=((a+b)^2-(a-b)^2)/4
    a+b、a-b 已经有方法了
        42
    jie170601   230 天前
    @ylrshui 输入 a+b,a-b 的结果时还是能推算出 a 和 b 的值
        43
    akira   230 天前
    a b 分别做二进制展开,然后分别做多项式加法 乘法运算
        44
    skadi   230 天前
    同态加密.我记得密码学上讲过.
        45
    morethansean   230 天前 via Android
    @TomVista 都不对,你应该好好学习,这样你既不会计组挂科,还能看懂这个帖子到底要讨论啥。
        46
    geelaw   230 天前 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   230 天前
    KaraTsuba 乘法
        48
    ldm0   224 天前
    一个完美解法:
    找到两个随机数 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   223 天前
    @ldm0 如果需要提供 x*y-1,还不如自己本地计算 a*b 了。

    如果用随机数做安全处理后再把计算任务交给远程计算机做,前提是这个预处理
    消耗的资源要小于本身要计算的任务,否则还不如我自己算 a*b。
        50
    ldm0   223 天前
    @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   85 天前 via iPad
    分布式就是干这个的啊
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1913 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 33ms · UTC 16:16 · PVG 00:16 · LAX 08:16 · JFK 11:16
    ♥ Do have faith in what you're doing.