×
Usamos cookies para ayudar a mejorar LingQ. Al visitar este sitio, aceptas nuestras
politicas de cookie .
李永乐老师 Youtube, 姚期智百万富翁问题:大数据时代,如何保护个人隐私?
姚期智 百万富翁 问题 :大 数据 时代 ,如何 保护 个人隐私?
各位 同学 大家 好 我 是 李永乐 老师
各位 同学 大家 好 我 是 李永乐 老师
在 上 一回 咱们 讲 零 知识 证明 的 时候
留 了 一个 思考题
说 有 两个 百万富翁 想 比较 彼此 的 财富 谁 多 谁 少
但是 谁 都 不想 公开 自己 的 真实 财产
有没有 什么 办法 呢
今天 我们 来讲 一讲 这个 问题
这个 问题 是 一个 计算机科学 的 问题
我们 称之为 百万富翁 问题
这个 百万富翁 问题 呢
在 现在 的 生活 中 已经 越来越 有用 了
我们 来讲 一讲 这个 问题
它 是 谁 提出 的 呢
它 是 在 这个 1982 年 的 时候
由 著名 的 计算机 科学家 姚期智 提出 的
大家 听说 过 姚期智 的 名字 吗
如果 你 没听说过 的话
有没有 听说 过 清华大学 姚班 呢
就是 以 姚期智 的 名字 命名 的
姚期智 1946 年 的 时候 出 生于 上海
后来 在 台湾大学 物理系 获得 了 学士学位
到 美国 的 哈佛大学 获得 了 物理学 的 博士学位
再 后来 在 MIT 斯坦福
还有 UC 伯克利 教 计算机
在 2000 年 的 时候
由于 姚期智 在 计算机 方面 的 贡献 而 获得 了
图灵奖
图灵奖 我们 讲过
是 这个 计算机 界 的 诺贝尔奖
我们 国家 就 只有 一个 人 获得 过 图灵奖
那 就是 姚期智
姚期智 也 是 美国科学院 台湾 中央研究院
还有 中国科学院 的 院士
好 那么 姚期智 在 1982 年 这篇 论文 里面
就 提出 这样 一个 问题
他 说 有 A B 两个 富翁
这个 A 和 B 两个 富翁
他们 的 资产 都 可以 近似 为 一个 整数
说 A 他 的 资产 是 i 亿元 这个 i 是 一个 整数
然后 这个 B 他 的 资产 是 这 j 亿元
j 亿元 j 也 是 个 整数
i 和 j 都 介于 0 到 10 之间
是 一个 0 到 10 之间 的 整数
然后 他们 两个 就 说 我们 两个 想 比较 一下
谁 钱 多 谁 钱 少
但是 我们 都 不想 让 对方 知道 我们 自己 的 钱
有没有 什么 办法 呢
这 姚期智 就 提出 了 一种 办法
我们 先 用 一个 例子 来 打个比方
说明 一下 姚期智 的 这个 思路 是 什么
说 这 两个 百万富翁 他们 商量 好
说 我们 要 通过 一个 规则 比较 彼此 的 财富
谁 也 不许 作假
但 在 这个 过程 中
我们 每个 人 都 不 告诉 对方 我们 有 多少钱
怎么办 呢
我们 可以 这样 看
首先 我们 先 拿 10 个 箱子 这 10 个 箱子 带锁
我 先画 10 个 箱子
好 了 10 个 箱子 画 完 了
这 10 个 箱子 都 是 带锁 的
这个 A
就 我们 刚才 说 的 那个 资产 为 i 亿 的 这个 人
他 是 有 钥匙 的
所以 他 可以 锁上 这个 箱子
也 可以 把 这个 箱子 给 打开
而 B 这个 百万富翁 这个 B 他 没有 钥匙
但是 他 可以 锁上
那个 锁头 你 一扣 不 就 锁上 了 吗
所以 他 虽然 没有 钥匙 他 还是 可以 锁上 的
好 现在 这 两个 人 就 开始 做 这个 事 了
怎么 做 呢
首先 这个 A 他 不是 资产 是 i 亿元 嘛
他 先 找到 第 i 个 箱子
比如说 这个 吧 这个 就是 第 i 个 箱子
然后 他 就 把 i 个 箱子 之前
所有 的 箱子 里面 放 一个 纸条 写 的 0
所有 的 箱子 都 写 0
到 了 第 i 个 箱子 开始 他 就 写 1
写 1 1 1 1 放个 纸条
然后 把 箱子 全都 锁上
全都 锁上 了 之后 他 就 出来 跟 B 说
说 你 过去 吧 你 去 看吧
这个 B 进来 之后 面对 10 个 箱子
10 个 箱子 全是 锁上 的
B 一个 也 打不开 对 不 对
所以 B 根本 不 知道 里边 写 的 是 什么
他 如果 打开 的话 一看
前面 是 0 后面 是 1 他 就 明白 了
你 的 资产 就 应该 是 这个 是不是
1 2 3 4 5 6 你 应该 就是 6 亿元
现在 我 打不开 我 就 不 知道 那 怎么办 呢
B 说 这样
我 也 找 我 自己 的 资产
比如说 我 的 资产 是 4 亿元 是 j 是 吧
我 第 4 个 j 等于 4 是不是
刚才 说 这个 i 等于 6
如果 我 的 资产 是 4 亿元
那 这样 我 就 把 这 第 4 个 箱子 给 拿 出来
我 把 它 拿 出来 给 A
我 打不开 但 我 可以 拿 出来
剩下 这些 个 箱子 我 全都 烧掉 我 全都 烧掉
你 也 不要 管 我 拿 的 是 第几个 箱子
反正 我 都 烧掉 了
都 烧掉 了 之后
A 面对 这个 B 拿 出来 的 箱子
A 根本 不 知道 这 拿 出来 是 第几个 箱子
但是 A 有 钥匙 A 可以 把 它 打开
所以 A 就 把 它 打开 了
打开 了 之后 就 面临 两种 可能
第一种 可能 是 什么 呢
第一种 可能 是 这个 箱子 里面 是 0
箱子 里边 是 0
这 说明 了 什么
这 不 就 说明 这个 j 它 是 小于 i 的 吗 是不是
也 就是 第一个 富翁 他 比较 有钱
第二个 富翁 比较 没 钱 对 不 对
但是 也 有 可能 打开 之后 里边 字条 是 1
如果 里边 字条 是 1 说明 什么
说明 这个 j 它 出现 在 这些 个 部位 对 不 对
所以 就 说明 什么 说明 j 是 大于 等于 i 的
所以 第二个 富翁 可能 更 有钱 一些 或者 是 相等
通过 这种 办法 他 就 可以 比较 彼此 财富 的 多少
而且 A 不 知道 拿 的 是 第几个 箱子
所以 A 不 知道 B 的 财富
而 B 拿出 箱子 之后
他 也 不 知道 后面 第几个 才 变成 1 的
所以 他 也 不 知道 A 的 财富 对 不 对
就 实现 了 姚期智 当时 说 的 这种 方法
那 这 里面 只是 一个 比方
它 这里 边 的 锁 就是 这个 箱子 是 带锁 的
锁 是 什么 呢 锁 在 密码学 中叫 公钥
就是 公开 的 这个 密码 就是 公开 的 钥匙
任何人 都 可以 对 数据 用公钥 进行 加密
而 这个 钥匙 是 什么 呢
钥匙 密码学 中 称之为 私钥
就是说 只有 那个 拥有者 用 私钥
才 能够 把 锁 打开
才能 看到 里边 的 数据 是 什么 才 能够 解密
这种 非对称 的 加密 方式
以前 我们 讲过 叫 RSA 加密
这是 一种 典型 的 非对称 加密
好 那么 这是 一个 例子
我们 来讲 一讲 具体 的 过程 是 怎么样 的
我们 来看 整个 的 这个 具体 的 操作 的 方案
我们 还是 说 A B 两个 人
用 更加 数学 化 的 方法 把 这个 问题 解释 出来
首先 我们 先说 B 第一步 我们 看 B 的 操作
B 怎么 操作 呢 我们 知道 B 他 是 没有 私钥 的
也 就是 他 是 没有 办法 解密 的
就 跟 刚才 这个 B 一样 他 没有 钥匙 对 不 对
但是 他 有 公钥 因为 公钥 是 公开 的
谁 都 可以 有 他 可以 进行 加密
所以 他 不能 解密 他 只能 加密
于是 B 按照 下面 的 方法 进行 操作
第一步 B 先 选出 一个 大数 选出 一个 大数 x
这 大数 x 他 不要 告诉 A 他 选出 大数 来
然后 用公钥 对 这个 大数 x 进行 加密
加密 我们 用 字母 E 来 表示 E(x)
加密 完 了 之后 不是 有个 结果 吗
这个 结果 我们 令 它 等于 k
大家 注意 加密 之后 的 结果 就是 k
那 我 问 你 解密 之后 的 结果 是 什么
解密 我用 字母 D 来 表示
D(k) 它 就 应该 等于 x 对 不 对
这 就是 个 解密 过程
但是 问题 是 解密 这个 步骤 B 是 完成 不了 的
因为 他 只是 有公钥 可以 进行 加密
但是 他 没有 私钥 所以 他 没有 办法 进行 解密
这 就是 非对称 加密 的 一个 特点
下 一步 这个 B 就 再 计算 一个 数
计算 一个 什么 数 呢 计算 一个 k-j+1
大家 注意
k 是 他 刚才 通过 加密算法 算 出来 的 一个 数
这个 j 是 什么 j 就是 B 的 财富 值
他 就 把 这个 自己 的 财富 值
融入 到 这个 算式 当中 去 了
最后 又 加 了 1 这个 数据 我们 管它 叫 m
B 就算 出 一个 m 来
然后 B 就 通过 一定 的 方法
把 这个 m 公开 给 A 他 就 告诉 A 了
他 说 你 看 我 现在 算 出 一个 m 来
而且 我 还 可以 告诉 你
这个 m 里边 就 有 我 的 财富 值 j
但是 因为 你 不 知道 我 的 k 是 多少
所以 你 根本 也 没有 办法 算出 j 来 对 不 对
B 告诉 一个 数据 m 给 A
但 A 也 不 知道 B 有 多少钱
好 B 的 操作 暂时 先放 这
然后 我们 再 来看 A A 的 特点 是 什么 呢
A 比 B 多有 一个 东西 A 是 有 公钥 有公钥
也 就是 那个 锁头 同时 还有 私钥
说 A 为什么 有 私钥 呢 因为 最 开始 生成 的 时候
就是 这个 A 自己 生成 了 一对 公钥 和 私钥
然后 他 把 这公钥 发给 B 的
所以 说 B 是 没有 私钥 的
但是 A 有 有公钥 也 有 私钥
既 可以 进行 加密 也 可以 进行 解密
A 拿到 B 传过来 的 数据 m
也 就是 k-j+1 之后
A 要 做 这么 几个 操作
首先 A 要 计算 一系列 的 数据 哪些 数据 呢
第一个 数据 就是 k-j+1 这个 不用 算了
A 还要 算 第二个 数 叫 k-j+2
k-j+3 往 下 一直 写
最后 写 到 多少 呢 写到 k-j+10
一共 有 10 个 数据
这 10 个 数据 中 必然 有 一项 是 什么
是 k-j+j 为什么 呢
因为 我们 说 过 i 和 j 都 是 在 0 到 10 之间 对 不 对
而 k-j+j 等于 多少
不 就 等于 k 吗
所以 说 这个 k 是 隐藏 在 这 十个 数 中间 的
这是 一个 自然数 的 数列
好 计算出来 这件 事 之后
你 看 A 不是 有 私钥 吗
那 可以 解密
所以 A 就 会 对 这些 个 数据 进行 解密
就 加密 的 逆运算 叫 解密
解密 的 结果 我们 写成 是 y
第 u 个 解密 数据 叫做 D(k-j+u)
我 把 它 解密 出来
解密 出来 了 之后 就 会 获得 十个 数据 叫做 y₁
这个 y₁ 就是 对 这个 数据 进行 解密 得到 的
然后 y₂ 就是 对 这个 数据 解密 得到 的
y₃ 一直 到 中间 有 一个 yⱼ
这个 yⱼ 就是 对 它 解密 得到 的
然后 再 往 最后 叫做 y₁₀
好 解密 出来 了
咱们 来看 一看 这个 yⱼ 是 什么
这个 yⱼ 是 对 k-j+j 进行 解密 得到 的 对 不 对
也 就是 对 k 进行 解密 得到 的
于是 我们 说 这个 yⱼ 它 其实 是 等于 D(k)
大家 看 一下 x 加密 之后 的 结果 是 k
而 k 解密 之后 的 结果 不 就是 x 吗
所以 这 一项
它 其实 就 等于 最 开始 A 所选 的 那个 数据
因此 它 解密 之后 的 这些 数据
大家 注意 看 它 已经 不再 是 自然 数列 了
因为 我 经过 了 一次 解密
它 不是 自然 数列 了 是 乱七八糟 的
但是 中间 隐藏 了 一个 数
就是 刚才 B 选出 的 那个 大数 x
只不过 A 不 知道 为什么 呢
因为 B 也 没有 告诉 它 哪个 数是 我 大数 x
对 不 对 你 要 知道 哪个 数是 的话
A 就 会 知道 B 的 财富 了 A 不 知道
但是 确实 有 那么 一个 数是 x
好 解密 完 了 之后
下 一步 的 操作 叫做 求模
什么 叫模 呢
这是 一个 比较 数学 化 的 语言
大概 的 意思 就是 取 余数
就是 我们 算 一个 数列 zᵤ 它 等于 什么 呢
等于 每 一个 数 yᵤ 再模 一个 P
这个 P 是 一个 质数
什么 意思 呢
就是 除以 一个 质数 取 余数
举个 例子 来讲
我们 这个 质数 取 3
如果 y₁ 是 100 的话 那 100 除以 3 余几
是不是 余 1
那 z₁ 就是 1
如果 第二个 数是 10 10 除以 3 还余 1
那 z₂ 也 是 1
如果 第三个 数是 5 5 除以 3 它 是 余 2
所以 第三个 数 就是 2
就是 我们 找 一个 质数
然后 让 刚才 的 y₁ 到 y₁₀ 这 十个 数
全都 除以 这个 质数
除 完 了 这个 质数 之后 取出 余数 来
这 就 叫做 求模 求模
求 完 了 模 之后 你 又 得到 了 一组 数据 叫 z₁
它 就是 y₁ 除以 P 余数
z₂ 那 就是 第二个 数 除以 P 的 余数
z₃ 一直 到 有 一个 zⱼ 对 吧
再 往后 叫 z₁₀ 取 了 十个 余数
好 下 一步 A 的 操作 就是
要 把 自己 的 财富 融到 这些 数据 里边
A 的 财富 是 多少
是 i 亿美元 它 怎么 融 进去
我们 看 它 的 操作 是 这样 的
就是 z₁ z₂ ... zᵢ
这些 个 数据 它 都 不变 它 都 不变
然后 在 zᵢ₊₁ zᵢ₊₂ ... z₁₀
这 不 还有 一大堆 数据 吗
我 都 让 它 加上 1
也就是说 刚才 你 获得 一大堆 数据
比如说 这个 z₃ 就是 zᵢ
那 你 前面 几个 数据 它 就 不变 它 就 不变
完 了 后面 的 这些 数据
你 就 把 它 都 加上 1 都 加上 1
中间 那个 分界线 是 什么
就是 第 i 个 数据
这个 i 就 表示 的 是 A 的 财富 值 了 是不是
好 我 获得 了 这些 数据 之后 再 干什么 呢
再 把 这些 数据 把 它 传给 B
好 传给 B 最后 一步 就是 B 的 检验 了
B 进行 检验
那么 B 拿到 这个 数据 之后 关注 什么 呢
它 只会 关注 第 j 个 数据 zⱼ
它 为什么 关注 zⱼ 呢
因为 你 看 zⱼ 它 是 什么
它 实际上 是 yⱼ 取 P 的 这个 模 得到 的
就是 yⱼ 除以 P 取 余数 得到 的 yⱼ 是 什么
yⱼ 不 就是 x 吗
x 是 我 自己 想 的 所以 我 知道 对 不 对
所以 我 就 检查一下
如果说 我们 用 x 我们 取模 除以 P 取 余数
取完 了 余数 之后 它 正好 等于 zⱼ
这 说明 了 什么
说明 这个 zⱼ
没有 经过 +1 这个 步骤
因为 你 不 +1
我 这么 一除
你 最后 发现 它 是 相等 的 对 不 对
所以 没有 经过 +1 这个 步骤 说明 什么
说明 zⱼ 是 落到 了 i 之前 的 这个 空间
因此 j 就 小于 等于 i 对 吗
我 再说 一遍
就是说 你 是 对 x 然后 除以 P 取个 余数
因为 x 就 等于 yⱼ
yⱼ 对 P 的 余数 就是 zⱼ
如果 它 正好 相等 的话
就 说明 这个 zⱼ 是 没有 +1 的
没有 经过 最后 这 一步
那么 为什么 没有 +1 呢
因为 这个 A 它 只 对 前 i 个 数据 加 了 1 了
后面 的 数据 它 没有 加 对 不 对
所以 说 你 如果 没有 +1
就 表示 zⱼ 是 落 在 i 之前 的
那 于是 j 就 小于 等于 i 对 不 对
反过来说
如果 这个 x 它模 了 P 之后
它 不 等于 zⱼ
你 把 你 自己 的 那个 数 除以 P 取 余数
取完 了 之后 不 相等
不 相等 的 原因 是 什么
那 因为 就是 zⱼ+1 了 呗
加完 了 1 之后
它 就 不再 是 x 除以 P 的 余数 了 对 不 对
所以 才 会 不 相等
那 就 说明 这个 zⱼ 它 是 在 i 之后 的
因此 j 就 大于 i
于是乎 A 也 不 知道 B 的 财富
B 也 不 知道 A 的 财富
但是 他们 却 可以 比较 谁 钱 多 谁 钱 少 对 吧
好 这样 就 解决 了 百万富翁 问题
在 我 上 一回 提 这个 思考题 的 时候
有 小朋友 给 我 留言
说 很 简单
两个 富翁 把 自己 的 钱装 袋子 里
放在 一个 天平 上
看 谁 重
谁 重 谁 的 钱 就 多
这种 方法 实现 的 前提
是 要 有 一架 公正 的 天平
这个 公正 的 天平 就是 一个 客观 的 第三方
但是 如果 你 在 互联网 的 世界 上
你 没有 这个 客观 的 第三方
又 如何 去 解释 这个 问题 呢
那么 姚期智 先生 提出 的 这种 方法
就是 用来 应对 这种 问题 的
那 这种 问题 被 称之为 多方 安全 计算 问题
现在 我们 是 一个 互联网 大 数据 的 时代
我们 有 许多 数据安全 的 问题 要 处理
举个 例子 来讲
比如说 我 想 找到 跟 我 兴趣爱好 相同 的 人
但是 我 又 不想 向 别人 透露
我 的 兴趣爱好 到底 是 什么
我该 怎么 做 呢
再 比如说 有 一些 学校 机关 和 医院
他们 有 一大堆 的 数据 要 进行 处理
但是 他们 又 不敢 把 这个 数据 给 一些 私人 公司
怕 他们 把 这个 数据 泄露
此时 他 该 怎么办 呢
姚期智 先生 提出 的 这种 方法
就 可以 解决 这个 问题
我 把 加密 之后 的 数据 给 你
然后 你 进行 处理 再 返 给 我
但 在 这个 过程 中 你 其实 什么 都 没有 获得
姚期智 先生 提出 的 这个 问题
在 计算机 安全 领域 具有 开拓性 的 意义
他 获得 了 图灵奖 也 是 实至名归
那么 这节 课 再 给 大家 留 一个 思考题
说 你 在 一个 公司 里面 上班 上 了 很多年 之后
找到 老板 说 老板 我要 加薪
我 这么 努力
但是 我 的 工资 却 没有 达到
咱们 公司员工 的 平均水平
老板 说 每 一个 人 的 工资 都 是 保密 的
你 是 怎么 知道 公司员工 的 平均工资 的 呢
你 就 非常 生气
把 这个 事 跟 小伙伴 们 一 说
小伙伴 们 也 纷纷表示
希望 算 出 公司 的 平均工资
但是 每 一个 小伙伴
又 不 愿意 告诉 别人 自己 的 工资 到底 是 多少
那么 我们 有没有 一种 办法
能够 算 出 所有 员工 的 平均工资
但是 又 不 透露 出 每个 员工 的 工资 到底 是 多少 呢
我 提示 一下
第一步 依然 是 要 寻找 一个 大数
大家 如果 知道 这个 问题 的 答案
可以 在 评论 区里 留言
大家 如果 喜欢 我 的 视频
可以 在 YouTube 的 账号 李永乐 老师 里 订阅 我
点击 小 铃铛 可以 第一 时间 获得 更新 信息
姚期智 百万富翁 问题 :大 数据 时代 ,如何 保护 个人隐私?
Yao Qizhi's millionaire question: How to protect personal privacy in the era of big data?
Yao Zhizhi Millionaire Pregunta: ¿Cómo proteger la privacidad personal en la era de los grandes datos?
各位 同学 大家 好 我 是 李永乐 老师
各位 同学 大家 好 我 是 李永乐 老师
在 上 一回 咱们 讲 零 知识 证明 的 时候
When we talked about zero-knowledge proof last time
留 了 一个 思考题
Left a question
说 有 两个 百万富翁 想 比较 彼此 的 财富 谁 多 谁 少
但是 谁 都 不想 公开 自己 的 真实 财产
有没有 什么 办法 呢
今天 我们 来讲 一讲 这个 问题
这个 问题 是 一个 计算机科学 的 问题
我们 称之为 百万富翁 问题
这个 百万富翁 问题 呢
在 现在 的 生活 中 已经 越来越 有用 了
我们 来讲 一讲 这个 问题
它 是 谁 提出 的 呢
它 是 在 这个 1982 年 的 时候
由 著名 的 计算机 科学家 姚期智 提出 的
大家 听说 过 姚期智 的 名字 吗
如果 你 没听说过 的话
有没有 听说 过 清华大学 姚班 呢
就是 以 姚期智 的 名字 命名 的
姚期智 1946 年 的 时候 出 生于 上海
后来 在 台湾大学 物理系 获得 了 学士学位
到 美国 的 哈佛大学 获得 了 物理学 的 博士学位
再 后来 在 MIT 斯坦福
还有 UC 伯克利 教 计算机
在 2000 年 的 时候
由于 姚期智 在 计算机 方面 的 贡献 而 获得 了
Due to Yao Qizhi’s contribution to computers
图灵奖
图灵奖 我们 讲过
是 这个 计算机 界 的 诺贝尔奖
我们 国家 就 只有 一个 人 获得 过 图灵奖
那 就是 姚期智
姚期智 也 是 美国科学院 台湾 中央研究院
Yao Qizhi is also the National Academy of Sciences Taiwan
还有 中国科学院 的 院士
好 那么 姚期智 在 1982 年 这篇 论文 里面
就 提出 这样 一个 问题
他 说 有 A B 两个 富翁
这个 A 和 B 两个 富翁
他们 的 资产 都 可以 近似 为 一个 整数
说 A 他 的 资产 是 i 亿元 这个 i 是 一个 整数
然后 这个 B 他 的 资产 是 这 j 亿元
j 亿元 j 也 是 个 整数
i 和 j 都 介于 0 到 10 之间
是 一个 0 到 10 之间 的 整数
然后 他们 两个 就 说 我们 两个 想 比较 一下
谁 钱 多 谁 钱 少
但是 我们 都 不想 让 对方 知道 我们 自己 的 钱
有没有 什么 办法 呢
这 姚期智 就 提出 了 一种 办法
我们 先 用 一个 例子 来 打个比方
说明 一下 姚期智 的 这个 思路 是 什么
说 这 两个 百万富翁 他们 商量 好
说 我们 要 通过 一个 规则 比较 彼此 的 财富
谁 也 不许 作假
No one is allowed to cheat
但 在 这个 过程 中
我们 每个 人 都 不 告诉 对方 我们 有 多少钱
怎么办 呢
我们 可以 这样 看
首先 我们 先 拿 10 个 箱子 这 10 个 箱子 带锁
我 先画 10 个 箱子
好 了 10 个 箱子 画 完 了
这 10 个 箱子 都 是 带锁 的
这个 A
就 我们 刚才 说 的 那个 资产 为 i 亿 的 这个 人
他 是 有 钥匙 的
所以 他 可以 锁上 这个 箱子
也 可以 把 这个 箱子 给 打开
而 B 这个 百万富翁 这个 B 他 没有 钥匙
但是 他 可以 锁上
那个 锁头 你 一扣 不 就 锁上 了 吗
Can't you lock the lock as soon as you click it?
所以 他 虽然 没有 钥匙 他 还是 可以 锁上 的
好 现在 这 两个 人 就 开始 做 这个 事 了
怎么 做 呢
首先 这个 A 他 不是 资产 是 i 亿元 嘛
他 先 找到 第 i 个 箱子
比如说 这个 吧 这个 就是 第 i 个 箱子
然后 他 就 把 i 个 箱子 之前
所有 的 箱子 里面 放 一个 纸条 写 的 0
所有 的 箱子 都 写 0
到 了 第 i 个 箱子 开始 他 就 写 1
写 1 1 1 1 放个 纸条
然后 把 箱子 全都 锁上
全都 锁上 了 之后 他 就 出来 跟 B 说
说 你 过去 吧 你 去 看吧
这个 B 进来 之后 面对 10 个 箱子
10 个 箱子 全是 锁上 的
B 一个 也 打不开 对 不 对
所以 B 根本 不 知道 里边 写 的 是 什么
他 如果 打开 的话 一看
前面 是 0 后面 是 1 他 就 明白 了
你 的 资产 就 应该 是 这个 是不是
1 2 3 4 5 6 你 应该 就是 6 亿元
现在 我 打不开 我 就 不 知道 那 怎么办 呢
B 说 这样
我 也 找 我 自己 的 资产
比如说 我 的 资产 是 4 亿元 是 j 是 吧
我 第 4 个 j 等于 4 是不是
刚才 说 这个 i 等于 6
如果 我 的 资产 是 4 亿元
那 这样 我 就 把 这 第 4 个 箱子 给 拿 出来
我 把 它 拿 出来 给 A
我 打不开 但 我 可以 拿 出来
剩下 这些 个 箱子 我 全都 烧掉 我 全都 烧掉
你 也 不要 管 我 拿 的 是 第几个 箱子
反正 我 都 烧掉 了
都 烧掉 了 之后
A 面对 这个 B 拿 出来 的 箱子
A 根本 不 知道 这 拿 出来 是 第几个 箱子
但是 A 有 钥匙 A 可以 把 它 打开
所以 A 就 把 它 打开 了
打开 了 之后 就 面临 两种 可能
第一种 可能 是 什么 呢
第一种 可能 是 这个 箱子 里面 是 0
箱子 里边 是 0
这 说明 了 什么
这 不 就 说明 这个 j 它 是 小于 i 的 吗 是不是
也 就是 第一个 富翁 他 比较 有钱
第二个 富翁 比较 没 钱 对 不 对
但是 也 有 可能 打开 之后 里边 字条 是 1
如果 里边 字条 是 1 说明 什么
说明 这个 j 它 出现 在 这些 个 部位 对 不 对
所以 就 说明 什么 说明 j 是 大于 等于 i 的
所以 第二个 富翁 可能 更 有钱 一些 或者 是 相等
通过 这种 办法 他 就 可以 比较 彼此 财富 的 多少
而且 A 不 知道 拿 的 是 第几个 箱子
所以 A 不 知道 B 的 财富
而 B 拿出 箱子 之后
他 也 不 知道 后面 第几个 才 变成 1 的
所以 他 也 不 知道 A 的 财富 对 不 对
就 实现 了 姚期智 当时 说 的 这种 方法
那 这 里面 只是 一个 比方
它 这里 边 的 锁 就是 这个 箱子 是 带锁 的
锁 是 什么 呢 锁 在 密码学 中叫 公钥
就是 公开 的 这个 密码 就是 公开 的 钥匙
任何人 都 可以 对 数据 用公钥 进行 加密
而 这个 钥匙 是 什么 呢
钥匙 密码学 中 称之为 私钥
就是说 只有 那个 拥有者 用 私钥
才 能够 把 锁 打开
才能 看到 里边 的 数据 是 什么 才 能够 解密
这种 非对称 的 加密 方式
以前 我们 讲过 叫 RSA 加密
这是 一种 典型 的 非对称 加密
好 那么 这是 一个 例子
我们 来讲 一讲 具体 的 过程 是 怎么样 的
我们 来看 整个 的 这个 具体 的 操作 的 方案
我们 还是 说 A B 两个 人
用 更加 数学 化 的 方法 把 这个 问题 解释 出来
首先 我们 先说 B 第一步 我们 看 B 的 操作
B 怎么 操作 呢 我们 知道 B 他 是 没有 私钥 的
也 就是 他 是 没有 办法 解密 的
就 跟 刚才 这个 B 一样 他 没有 钥匙 对 不 对
但是 他 有 公钥 因为 公钥 是 公开 的
谁 都 可以 有 他 可以 进行 加密
所以 他 不能 解密 他 只能 加密
于是 B 按照 下面 的 方法 进行 操作
第一步 B 先 选出 一个 大数 选出 一个 大数 x
这 大数 x 他 不要 告诉 A 他 选出 大数 来
然后 用公钥 对 这个 大数 x 进行 加密
加密 我们 用 字母 E 来 表示 E(x)
加密 完 了 之后 不是 有个 结果 吗
这个 结果 我们 令 它 等于 k
大家 注意 加密 之后 的 结果 就是 k
那 我 问 你 解密 之后 的 结果 是 什么
解密 我用 字母 D 来 表示
D(k) 它 就 应该 等于 x 对 不 对
这 就是 个 解密 过程
但是 问题 是 解密 这个 步骤 B 是 完成 不了 的
因为 他 只是 有公钥 可以 进行 加密
但是 他 没有 私钥 所以 他 没有 办法 进行 解密
这 就是 非对称 加密 的 一个 特点
下 一步 这个 B 就 再 计算 一个 数
计算 一个 什么 数 呢 计算 一个 k-j+1
大家 注意
k 是 他 刚才 通过 加密算法 算 出来 的 一个 数
这个 j 是 什么 j 就是 B 的 财富 值
他 就 把 这个 自己 的 财富 值
融入 到 这个 算式 当中 去 了
最后 又 加 了 1 这个 数据 我们 管它 叫 m
B 就算 出 一个 m 来
然后 B 就 通过 一定 的 方法
把 这个 m 公开 给 A 他 就 告诉 A 了
他 说 你 看 我 现在 算 出 一个 m 来
而且 我 还 可以 告诉 你
这个 m 里边 就 有 我 的 财富 值 j
但是 因为 你 不 知道 我 的 k 是 多少
所以 你 根本 也 没有 办法 算出 j 来 对 不 对
B 告诉 一个 数据 m 给 A
但 A 也 不 知道 B 有 多少钱
好 B 的 操作 暂时 先放 这
然后 我们 再 来看 A A 的 特点 是 什么 呢
A 比 B 多有 一个 东西 A 是 有 公钥 有公钥
也 就是 那个 锁头 同时 还有 私钥
说 A 为什么 有 私钥 呢 因为 最 开始 生成 的 时候
就是 这个 A 自己 生成 了 一对 公钥 和 私钥
然后 他 把 这公钥 发给 B 的
所以 说 B 是 没有 私钥 的
但是 A 有 有公钥 也 有 私钥
既 可以 进行 加密 也 可以 进行 解密
A 拿到 B 传过来 的 数据 m
也 就是 k-j+1 之后
A 要 做 这么 几个 操作
首先 A 要 计算 一系列 的 数据 哪些 数据 呢
第一个 数据 就是 k-j+1 这个 不用 算了
A 还要 算 第二个 数 叫 k-j+2
k-j+3 往 下 一直 写
最后 写 到 多少 呢 写到 k-j+10
一共 有 10 个 数据
这 10 个 数据 中 必然 有 一项 是 什么
是 k-j+j 为什么 呢
因为 我们 说 过 i 和 j 都 是 在 0 到 10 之间 对 不 对
而 k-j+j 等于 多少
不 就 等于 k 吗
所以 说 这个 k 是 隐藏 在 这 十个 数 中间 的
这是 一个 自然数 的 数列
好 计算出来 这件 事 之后
你 看 A 不是 有 私钥 吗
那 可以 解密
所以 A 就 会 对 这些 个 数据 进行 解密
就 加密 的 逆运算 叫 解密
解密 的 结果 我们 写成 是 y
第 u 个 解密 数据 叫做 D(k-j+u)
我 把 它 解密 出来
解密 出来 了 之后 就 会 获得 十个 数据 叫做 y₁
这个 y₁ 就是 对 这个 数据 进行 解密 得到 的
然后 y₂ 就是 对 这个 数据 解密 得到 的
y₃ 一直 到 中间 有 一个 yⱼ
这个 yⱼ 就是 对 它 解密 得到 的
然后 再 往 最后 叫做 y₁₀
好 解密 出来 了
咱们 来看 一看 这个 yⱼ 是 什么
这个 yⱼ 是 对 k-j+j 进行 解密 得到 的 对 不 对
也 就是 对 k 进行 解密 得到 的
于是 我们 说 这个 yⱼ 它 其实 是 等于 D(k)
大家 看 一下 x 加密 之后 的 结果 是 k
而 k 解密 之后 的 结果 不 就是 x 吗
所以 这 一项
它 其实 就 等于 最 开始 A 所选 的 那个 数据
因此 它 解密 之后 的 这些 数据
大家 注意 看 它 已经 不再 是 自然 数列 了
因为 我 经过 了 一次 解密
它 不是 自然 数列 了 是 乱七八糟 的
但是 中间 隐藏 了 一个 数
就是 刚才 B 选出 的 那个 大数 x
只不过 A 不 知道 为什么 呢
因为 B 也 没有 告诉 它 哪个 数是 我 大数 x
对 不 对 你 要 知道 哪个 数是 的话
A 就 会 知道 B 的 财富 了 A 不 知道
但是 确实 有 那么 一个 数是 x
好 解密 完 了 之后
下 一步 的 操作 叫做 求模
什么 叫模 呢
这是 一个 比较 数学 化 的 语言
大概 的 意思 就是 取 余数
就是 我们 算 一个 数列 zᵤ 它 等于 什么 呢
等于 每 一个 数 yᵤ 再模 一个 P
Equal to every number yᵤ modulo a P
这个 P 是 一个 质数
什么 意思 呢
就是 除以 一个 质数 取 余数
举个 例子 来讲
我们 这个 质数 取 3
如果 y₁ 是 100 的话 那 100 除以 3 余几
是不是 余 1
那 z₁ 就是 1
如果 第二个 数是 10 10 除以 3 还余 1
那 z₂ 也 是 1
如果 第三个 数是 5 5 除以 3 它 是 余 2
所以 第三个 数 就是 2
就是 我们 找 一个 质数
然后 让 刚才 的 y₁ 到 y₁₀ 这 十个 数
全都 除以 这个 质数
除 完 了 这个 质数 之后 取出 余数 来
这 就 叫做 求模 求模
求 完 了 模 之后 你 又 得到 了 一组 数据 叫 z₁
它 就是 y₁ 除以 P 余数
z₂ 那 就是 第二个 数 除以 P 的 余数
z₃ 一直 到 有 一个 zⱼ 对 吧
再 往后 叫 z₁₀ 取 了 十个 余数
好 下 一步 A 的 操作 就是
要 把 自己 的 财富 融到 这些 数据 里边
A 的 财富 是 多少
是 i 亿美元 它 怎么 融 进去
我们 看 它 的 操作 是 这样 的
就是 z₁ z₂ ... zᵢ
这些 个 数据 它 都 不变 它 都 不变
然后 在 zᵢ₊₁ zᵢ₊₂ ... z₁₀
这 不 还有 一大堆 数据 吗
我 都 让 它 加上 1
也就是说 刚才 你 获得 一大堆 数据
比如说 这个 z₃ 就是 zᵢ
那 你 前面 几个 数据 它 就 不变 它 就 不变
完 了 后面 的 这些 数据
你 就 把 它 都 加上 1 都 加上 1
中间 那个 分界线 是 什么
就是 第 i 个 数据
这个 i 就 表示 的 是 A 的 财富 值 了 是不是
好 我 获得 了 这些 数据 之后 再 干什么 呢
再 把 这些 数据 把 它 传给 B
好 传给 B 最后 一步 就是 B 的 检验 了
B 进行 检验
那么 B 拿到 这个 数据 之后 关注 什么 呢
它 只会 关注 第 j 个 数据 zⱼ
它 为什么 关注 zⱼ 呢
因为 你 看 zⱼ 它 是 什么
它 实际上 是 yⱼ 取 P 的 这个 模 得到 的
就是 yⱼ 除以 P 取 余数 得到 的 yⱼ 是 什么
yⱼ 不 就是 x 吗
x 是 我 自己 想 的 所以 我 知道 对 不 对
所以 我 就 检查一下
如果说 我们 用 x 我们 取模 除以 P 取 余数
取完 了 余数 之后 它 正好 等于 zⱼ
这 说明 了 什么
说明 这个 zⱼ
没有 经过 +1 这个 步骤
因为 你 不 +1
我 这么 一除
I divide like this
你 最后 发现 它 是 相等 的 对 不 对
所以 没有 经过 +1 这个 步骤 说明 什么
说明 zⱼ 是 落到 了 i 之前 的 这个 空间
因此 j 就 小于 等于 i 对 吗
我 再说 一遍
就是说 你 是 对 x 然后 除以 P 取个 余数
因为 x 就 等于 yⱼ
yⱼ 对 P 的 余数 就是 zⱼ
如果 它 正好 相等 的话
就 说明 这个 zⱼ 是 没有 +1 的
没有 经过 最后 这 一步
那么 为什么 没有 +1 呢
因为 这个 A 它 只 对 前 i 个 数据 加 了 1 了
后面 的 数据 它 没有 加 对 不 对
所以 说 你 如果 没有 +1
就 表示 zⱼ 是 落 在 i 之前 的
那 于是 j 就 小于 等于 i 对 不 对
反过来说
如果 这个 x 它模 了 P 之后
它 不 等于 zⱼ
你 把 你 自己 的 那个 数 除以 P 取 余数
取完 了 之后 不 相等
不 相等 的 原因 是 什么
那 因为 就是 zⱼ+1 了 呗
加完 了 1 之后
它 就 不再 是 x 除以 P 的 余数 了 对 不 对
所以 才 会 不 相等
那 就 说明 这个 zⱼ 它 是 在 i 之后 的
因此 j 就 大于 i
于是乎 A 也 不 知道 B 的 财富
B 也 不 知道 A 的 财富
但是 他们 却 可以 比较 谁 钱 多 谁 钱 少 对 吧
好 这样 就 解决 了 百万富翁 问题
在 我 上 一回 提 这个 思考题 的 时候
有 小朋友 给 我 留言
说 很 简单
两个 富翁 把 自己 的 钱装 袋子 里
放在 一个 天平 上
看 谁 重
谁 重 谁 的 钱 就 多
这种 方法 实现 的 前提
是 要 有 一架 公正 的 天平
这个 公正 的 天平 就是 一个 客观 的 第三方
但是 如果 你 在 互联网 的 世界 上
你 没有 这个 客观 的 第三方
又 如何 去 解释 这个 问题 呢
那么 姚期智 先生 提出 的 这种 方法
就是 用来 应对 这种 问题 的
那 这种 问题 被 称之为 多方 安全 计算 问题
现在 我们 是 一个 互联网 大 数据 的 时代
我们 有 许多 数据安全 的 问题 要 处理
举个 例子 来讲
比如说 我 想 找到 跟 我 兴趣爱好 相同 的 人
但是 我 又 不想 向 别人 透露
我 的 兴趣爱好 到底 是 什么
我该 怎么 做 呢
再 比如说 有 一些 学校 机关 和 医院
他们 有 一大堆 的 数据 要 进行 处理
但是 他们 又 不敢 把 这个 数据 给 一些 私人 公司
怕 他们 把 这个 数据 泄露
此时 他 该 怎么办 呢
姚期智 先生 提出 的 这种 方法
就 可以 解决 这个 问题
我 把 加密 之后 的 数据 给 你
然后 你 进行 处理 再 返 给 我
但 在 这个 过程 中 你 其实 什么 都 没有 获得
姚期智 先生 提出 的 这个 问题
在 计算机 安全 领域 具有 开拓性 的 意义
他 获得 了 图灵奖 也 是 实至名归
那么 这节 课 再 给 大家 留 一个 思考题
说 你 在 一个 公司 里面 上班 上 了 很多年 之后
找到 老板 说 老板 我要 加薪
我 这么 努力
但是 我 的 工资 却 没有 达到
咱们 公司员工 的 平均水平
老板 说 每 一个 人 的 工资 都 是 保密 的
你 是 怎么 知道 公司员工 的 平均工资 的 呢
你 就 非常 生气
把 这个 事 跟 小伙伴 们 一 说
小伙伴 们 也 纷纷表示
希望 算 出 公司 的 平均工资
但是 每 一个 小伙伴
又 不 愿意 告诉 别人 自己 的 工资 到底 是 多少
那么 我们 有没有 一种 办法
能够 算 出 所有 员工 的 平均工资
但是 又 不 透露 出 每个 员工 的 工资 到底 是 多少 呢
我 提示 一下
第一步 依然 是 要 寻找 一个 大数
大家 如果 知道 这个 问题 的 答案
可以 在 评论 区里 留言
大家 如果 喜欢 我 的 视频
可以 在 YouTube 的 账号 李永乐 老师 里 订阅 我
点击 小 铃铛 可以 第一 时间 获得 更新 信息