搜索

[2376] 2015-10-19_知识｜RSA算法是如何诞生的

文档创建者：s7ckTeam
浏览次数：2
最后更新：2025-01-16
2015-10-19_知识｜RSA算法是如何诞生的 知 识 ｜ R S A   算 法 是 如 何 诞 生 的 8 0 8 0   E 安 全   2 0 1 5 - 1 0 - 1 9 欢 迎 E 安 全 微 信 公 众 号 ： E A Q a p p 最 近 为 了 研 究 某 个 极 其 无 聊 的 问 题 ， 读 了 一 些 公 钥 加 密 的 历 史 ， 意 外 地 发 现 这 段 历 史 竟 然 非 常 有 趣 。 尤 其 是 R S A 算 法 的 诞 生 过 程 ， 被 很 多 书 写 得 非 常 励 志 ， 看 得 人 热 血 澎 湃 。 果 然 比 起 算 法 本 身 ， 这 些 背 后 的 故 事 更 能 吸 引 我 的 兴 趣 。 R S A 算 法 具 体 是 怎 么 回 事 ， 我 就 不 在 这 瞎 说 了 。 简 介 可 以 看 W i k i p e d i a ， 如 果 想 形 象 一 点 理 解 算 法 本 身 ， 这 儿 有 个 不 错 的 视 频 ， 可 以 通 过 它 了 解 R S A 的 基 本 思 想 。 我 就 直 接 从 R S A 这 三 个 人 说 起 了 。 参 考 的 书 籍 资 料 列 在 文 末 。 R S A   背 后 的 三 个 小 伙 背 后 的 三 个 小 伙 R S A 是 由 三 个 提 出 者 R o n   R i v e s t 、 A d i   S h a m i r   和   L e o n a r d   A d l e m a n 的 姓 氏 首 字 母 组 成 的 。 这 三 个 人 风 格 迥 异 ， 组 成 了 一 个 技 能 互 补 的 完 美 团 队 。 R o n   R i v e s t ， R S A   中 的 R 。 他 在 耶 鲁 读 数 学 系 ， 随 后 跑 到 斯 坦 福 读 计 算 机 科 学 系 研 究 人 工 智 能 。 他 所 研 究 的 课 题 — — 让 机 器 人 在 没 有 人 干 预 的 情 况 下 在 停 车 场 散 步 ， 在 那 个 计 算 机 科 学 系 仅 成 立 四 年 的 年 代 明 显 太 过 乐 观 ， 但 他 依 然 乐 此 不 疲 。 毕 业 后 他 接 受 M I T 任 教 的 工 作 机 会 。 也 许 是 因 为 多 年 积 累 的 科 研 氛 围 ， 他 对 新 技 术 非 常 兴 奋 ， 大 量 阅 读 前 沿 文 献 。 与 此 同 时 ， 他 认 为 迷 人 的 理 论 应 该 与 现 实 世 界 相 结 合 ， 才 能 散 发 魅 力 ， 对 世 界 有 所 改 变 ， 这 也 是 他 的 理 想 。 A d i   S h a m i r ， R S A 中 的 S 。 他 是 以 色 列 人 ， 和 R i v e s t 一 样 ， 学 数 学 后 转 计 算 机 科 学 进 一 步 深 造 ， 毕 业 后 以 访 问 学 者 的 身 份 来 到 M I T 。 他 很 聪 明 ， 学 习 能 力 超 强 。 虽 然 他 在 数 学 上 的 造 诣 颇 深 ， 但 起 初 他 在 算 法 方 面 的 知 识 十 分 匮 乏 ， 当 他 接 到 R i v e s t 关 于 算 法 高 级 课 程 讲 授 的 邀 请 信 时 连 连 叫 苦 ， 教 算 法 已 经 够 呛 了 ， 还 什 么 高 级 课 程 ？ 给 博 士 生 讲 的 么 ？ 虽 然 如 此 ， 他 还 是 硬 着 头 皮 前 往 M I T ， 之 后 很 快 投 入 到 学 习 中 ， 整 天 泡 在 图 书 馆 ， 读 了 一 书 架 关 于 算 法 的 书 籍 ， 最 终 仅 用 两 周 便 掌 握 了 所 需 的 知 识 。 L e o n a r d   A d l e m a n ， R S A 中 的 A 。 自 幼 胸 无 大 志 ， 从 未 想 过 做 什 么 数 学 家 。 读 大 学 时 受 各 方 面 影 响 ， 甚 至 包 括 电 视 节 目 的 影 响 ， 在 专 业 选 择 上 犹 豫 不 决 ， 最 终 因 为 学 数 学 会 有 大 量 时 间 做 别 的 而 选 择 就 读 数 学 系 。 毕 业 后 在 美 国 银 行 做 程 序 员 ， 之 后 想 去 学 医 ， 被 录 取 了 却 又 改 变 主 意 想 研 究 物 理 ， 上 了 几 堂 课 又 觉 得 没 意 思 。 最 后 他 怕 挂 科 对 找 工 作 有 影 响 ， 跑 去 图 书 馆 借 了 本 计 算 机 科 学 的 书 ， 一 直 没 还 ， 学 校 就 会 因 此 扣 留 成 绩 单 。 辗 转 几 次 后 ， 他 最 终 选 择 读 计 算 机 科 学 P h D 。 毕 业 后 同 样 在 M I T 任 教 。 这 三 人 当 时 都 非 常 年 轻 ， 二 十 多 、 三 十 出 头 的 样 子 。 他 们 的 办 公 室 距 离 很 近 ， 可 以 经 常 串 门 。 于 是 故 事 就 从 一 次 A d l e m a n 的 串 门 开 始 了 。 自 左 至 右 ： A d i   S h a m i r ,   R o n   R i v e s t ,   L e o n a r d   A d l e m a n   ( v i a )
4 2 次 的 失 败 次 的 失 败 1 9 7 6 年 底 的 某 天 ， A d l e m a n 无 意 推 开 R i v e s t 的 房 门 。 热 爱 新 技 术 的 R i v e s t 果 不 其 然 正 拿 着 份 楼 上 的 W h i t f i e l d   D i f f i e   与   M a r t i n H e l l m a n 合 作 发 表 的 新 论 文 研 究 。 自 认 为 对 前 沿 理 念 无 所 不 晓 的 R i v e s t ， 没 料 到 这 篇 文 章 提 出 了 一 个 前 所 未 有 的 思 路 ， 这 让 他 兴 奋 不 已 。 正 琢 磨 着 ， A d l e m a n 推 门 进 来 了 ， R i v e s t 便 忘 我 地 向 A d l e m a n 讲 解 了 这 篇 论 文 中 所 述 的 思 想 ， 在 A d l e m a n 听 起 来 大 约 是 这 样 的 ： 公 钥 密 码 b l a h   b l a h   b l a h … 不 对 称 密 码 b l a h   b l a h   b l a h … 单 向 函 数 b l a h   b l a h   b l a h … 但 是 符 合 条 件 的 单 向 函 数 目 前 没 找 到 。 我 有 信 心 找 到 这 样 的 单 向 函 数 ， 你 看 你 要 不 要 和 我 一 起 试 试 ？ 这 些 显 然 不 足 以 让 早 已 下 决 心 走 纯 理 论 路 线 的 A d l e m a n 动 心 ， 对 此 他 只 是 报 以 一 个 “ 礼 貌 的 哈 欠 ” 。 想 当 初 选 择 读 计 算 机 科 学 ， 除 了 方 便 找 工 作 ， A d l e m a n 还 深 受 马 丁 加 德 纳 专 栏 的 影 响 。 专 栏 中 写 到 的 哥 德 尔 定 理 让 他 感 到 惊 艳 ， 深 深 体 会 到 数 学 之 美 ， 如 今 只 有 高 斯 之 流 方 能 入 他 的 眼 ， 眼 下 R i v e s t 滔 滔 不 绝 的 什 么 加 密 解 密 ， 在 他 看 来 既 不 高 级 也 不 好 玩 。 好 在 R i v e s t 拉 到 了 另 一 个 同 盟 ， 也 就 是 隔 壁 的 S h a m i r 。 S h a m i r 一 听 说 这 篇 文 章 就 立 刻 意 识 到 它 的 价 值 ， 二 人 一 拍 即 合 ， 开 始 了 他 们 昼 夜 不 休 的 单 向 函 数 寻 找 之 旅 。 因 为 两 人 都 头 脑 灵 活 ， 很 快 就 想 到 了 一 些 方 案 。 尽 管 A d l e m a n 不 情 愿 参 与 其 中 ， 他 们 还 是 会 把 结 果 拿 给 A d l e m a n ， A d l e m a n 的 角 色 就 是 逐 个 击 破 这 些 方 案 ， 找 出 各 种 漏 洞 ， 给 那 两 个 头 脑 发 热 的 人 泼 点 冷 水 ， 免 得 他 们 走 弯 路 。 三 人 走 火 入 魔 一 般 ， 吃 饭 聊 、 喝 酒 聊 ， 甚 至 去 滑 雪 度 假 也 不 忘 讨 论 这 件 事 。 S h a m i r 就 在 滑 雪 的 时 候 想 到 了 一 个 绝 妙 的 点 子 ， 以 至 于 把 滑 雪 板 都 落 在 了 身 后 。 当 他 意 识 到 这 一 点 回 头 去 取 时 ， 却 又 不 幸 忘 记 了 那 个 一 闪 而 过 的 点 子 。 相 对 来 说 给 他 们 启 发 的 D i f f i e 要 幸 运 一 些 ， 他 在 下 楼 买 可 乐 的 时 候 同 样 让 灵 感 溜 走 ， 好 在 上 楼 的 过 程 中 他 又 想 起 来 了 ， 这 个 差 点 溜 走 的 灵 感 正 是 R i v e s t 那 天 手 中 所 拿 论 文 的 核 心 思 想 ， 为 R S A 算 法 奠 定 了 基 础 。 起 初 R i v e s t 和 S h a m i r 构 造 出 来 的 算 法 很 快 就 能 被 A d l e m a n 破 解 ， 二 人 受 到 强 烈 的 打 击 ， 以 至 于 有 一 阶 段 他 们 走 向 了 另 一 个 极 端 ， 试 图 证 明 D i f f i e 他 们 的 想 法 根 本 就 是 不 靠 谱 的 。 但 慢 慢 的 ， 破 解 变 得 没 那 么 容 易 ， 特 别 是 他 们 的 第 3 2 号 方 案 ， A d l e m a n 用 了 一 晚 上 才 找 出 漏 洞 ， 这 让 他 们 感 觉 胜 利 就 在 眼 前 。 就 这 样 ， R i v e s t 和 S h a m i r 先 后 抛 出 了 4 2 个 方 案 ， 虽 然 这 4 2 个 全 部 被 A d l e m a n 击 破 ， 不 过 他 们 的 努 力 并 不 算 白 费 ， 至 少 指 出 了 4 2 条 错 误 的 路 线 。 算 法 的 诞 生 与 命 名 算 法 的 诞 生 与 命 名 1 9 7 7 年 四 月 ， R i v e s t 和 其 余 两 人 参 加 了 犹 太 逾 越 节 的 P a r t y ， 喝 了 些 酒 。 到 家 后 R i v e s t 睡 不 着 ， 随 手 翻 了 翻 数 学 书 ， 随 后 一 个 灵 感 逐 渐 清 晰 起 来 。 他 大 气 不 敢 出 一 口 ， 冷 静 下 来 连 夜 整 理 自 己 的 思 路 ， 一 气 呵 成 写 就 了 一 篇 论 文 。 次 日 ， R i v e s t 把 论 文 拿 给 A d l e m a n ， 做 好 再 一 次 徒 劳 的 心 理 准 备 ， 但 这 一 次 A d l e m a n 认 输 了 ， 认 为 这 个 方 案 应 该 是 可 行 的 。 按 照 惯 例 ， R i v e s t 按 姓 氏 字 母 序 将 三 人 的 名 字 署 在 论 文 上 ， 也 就 是 A d l e m a n 、 R i v e s t 、 S h a m i r ， 但 A d l e m a n 总 觉 得 自 己 贡 献 微 乎 其 微 ， 不 过 是 泼 泼 冷 水 ， 不 至 于 还 要 署 个 名 ， 便 要 求 R i v e s t 拿 掉 自 己 的 名 字 。 在 R i v e s t 的 坚 持 下 ， 他 最 终 要 求 至 少 把 自 己 的 名 字 放 到 最 后 。 也 正 因 为 如 此 ， R S A 叫 做 R S A 没 有 被 叫 做 A R S 。 虽 然 A d l e m a n 一 开 始 认 为 这 注 定 是 他 诸 多 论 文 中 最 不 起 眼 的 一 篇 ， R S A 走 红 后 他 还 是 调 侃 说 ， 越 来 越 觉 得 A R S 更 顺 口 了 。 之 后 之 后 之 后 的 历 史 我 们 就 非 常 熟 悉 了 ， 他 们 的 论 文 受 到 各 方 赞 赏 。 R i v e s t 还 把 论 文 发 给 马 丁 加 德 纳 一 份 ， 加 德 纳 非 常 感 兴 趣 ， 把 R i v e s t 请 到 家 里 面 谈 ， 进 一 步 了 解 R S A 算 法 。 当 然 此 前 ， 加 德 纳 还 不 忘 先 表 演 一 个 扑 克 魔 术 。 这 次 会 面 也 促 成 后 来 马 丁 加 德 纳 在 他 著 名 的 专 栏 刊 登 R S A 算 法 及 破 解 奖 金 的 故 事 。 至 于 R 、 S 、 A 这 三 人 ， 依 然 保 持 着 友 谊 ， 还 成 立 了 R S A 公 司 ， 赚 了 一
大 笔 钱 。 最 后 ， 既 然 R S A 是 根 据 提 出 者 命 名 的 ， 必 然 也 逃 不 出 S t i g l e r ’ s   l a w 的 魔 爪 。 的 确 从 时 间 上 来 说 ， R S A 这 三 人 并 非 最 早 提 出 这 个 算 法 的 人 。 事 实 上 早 于 这 三 人 四 年 时 间 ， R S A 算 法 的 思 想 就 被 英 国 学 者 构 造 出 来 了 。 早 在 1 9 6 9 年 ， 英 国 密 码 学 家 J a m e s   E l l i s 就 想 到 了 公 钥 密 码 的 概 念 ， 但 同 样 卡 在 寻 找 单 向 函 数 这 个 问 题 上 。 1 9 7 3 年 9 月 ， 年 仅 2 6 岁 的 数 学 家 C l i f f o r d   C o c k s 听 说 这 个 思 想 后 ， 在 完 全 不 了 解 状 况 的 心 理 状 态 下 花 不 到 半 小 时 就 找 到 了 R i v e s t 他 们 苦 思 冥 想 的 方 案 。 但 是 ， 他 们 效 力 于 政 府 ， 这 个 绝 妙 的 想 法 立 刻 被 相 关 机 构 封 锁 ， 变 为 机 密 ， 谁 也 不 能 对 外 公 开 自 己 的 发 现 ， 于 是 他 们 眼 睁 睁 地 看 着 D i f f i e 及 R S A 等 人 重 现 了 他 们 当 时 的 研 究 并 享 有 盛 誉 。 直 到 1 9 9 7 年 底 ， 时 隔 二 十 余 年 ， 这 件 事 情 才 被 公 之 于 众 。 遗 憾 的 是 那 时 候 E l l i s 已 经 过 世 一 个 月 ， 直 至 逝 世 都 是 一 个 无 名 英 雄 。 阅 读 原 文
回复

举报

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

使用Markdown编辑器编辑 使用富文本编辑器编辑

Archiver| 手机版| 小黑屋|
Powered by Discuz! X3.4 Copyright © 2001-2020, Tencent Cloud. 商业源码建议获取授权，如侵犯您的权益，请联系客服处理