搜索

[24211] 2015-08-20_秀尔算法：破解RSA加密的“不灭神话”

文档创建者：s7ckTeam
浏览次数：2
最后更新：2025-01-18
2015-08-20_秀尔算法：破解RSA加密的“不灭神话” 秀 尔 算 法 ： 破 解 R S A 加 密 的 “ 不 灭 神 话 ” L i n u x 中 国   2 0 1 5 - 0 8 - 2 0 R S A 加 密 曾 被 视 为 最 可 靠 的 加 密 算 法 ， 直 到 秀 尔 算 法 出 现 ， 打 破 了 R S A 的 不 灭 神 话 。 R S A 加 密   V S   秀 尔 算 法 作 为 R S A 加 密 技 术 的 终 结 者 — — “ 太 多 运 算 ， 无 法 读 取 ” 的 秀 尔 算 法 （ S h o r ’ s   a l g o r i t h m ） 不 是 通 过 暴 力 破 解 的 方 式 找 到 最 终 密 码 的 ， 而 是 利 用 量 子 计 算 的 并 行 性 ， 可 以 快 速 分 解 出 公 约 数 ， 从 而 打 破 了 R S A 算 法 的 基 础 （ 即 假 设 我 们 不 能 很 有 效 的 分 解 一 个 已 知 的 整 数 ） 。 同 时 ， 秀 尔 算 法 展 示 了 因 数 分 解 这 问 题 在 量 子 计 算 机 上 可 以 很 有 效 率 的 解 决 ， 所 以 一 个 足 够 大 的 量 子 计 算 机 可 以 破 解 R S A 。 R S A 加 密 “ 曾 经 ” 之 所 以 强 大 ， 是 因 为 它 对 极 大 整 数 做 因 数 分 解 的 难 度 决 定 了 R S A 算 法 的 可 靠 性 。 将 两 个 质 数 相 乘 是 件 很 容 易 的 事 情 ， 但 要 找 到 一 个 庞 大 数 字 的 质 因 子 却 非 常 困 难 。 这 便 是 大 量 现 代 科 技 的 依 靠 之 处 ， R S A 加 密 就 是 凭 借 其 简 洁 性 迅 速 风 靡 。 然 而 ， 有 一 种 技 术 可 以 让 R S A 加 密 无 用 武 之 地 。 秀 尔 算 法 可 以 破 解 R S A ， 但 是 怎 样 才 能 让 它 真 正 见 效 呢 ？ 我 们 这 里 并 非 建 议 你 同 时 尝 试 所 有 可 能 的 质 因 子 。 而 是 使 用 （ 相 对 ） 简 洁 的 语 句 ： 如 果 我 们 快 速 找 到 下 面 这 个 周 期 函 数 的 周 期 ，   f ( x )   =   m ^ x   ( m o d   N ) 我 们 便 可 以 破 解 R S A 加 密 。 秀 尔 五 步 走 那 么 ， 秀 尔 算 法 究 竟 是 怎 样 工 作 的 呢 ？ 在 秀 尔 五 步 法 中 ， 只 有 一 步 需 要 是 需 要 用 到 量 子 计 算 机 的 ， 其 他 的 步 骤 则 都 可 以 采 用 传 统 方 法 解 决 。
第 一 步 ： 使 用 传 统 最 大 公 约 数 分 解 （ g c d ） 算 法 ， 也 就 是 辗 转 相 除 法 。 N 是 你 需 要 尝 试 的 因 子 ， m 则 是 一 个 小 于 N 的 随 机 正 整 数 。 如 果 g c d （ m ， N ） = 1 ， 则 继 续 。 一 旦 你 使 用 g c d 找 到 一 个 因 子 ， 你 便 能 获 得 一 个 非 凡 因 子 ， 然 后 结 束 。 第 二 步 ： 找 到 周 期   P m   m o d   N ,   m ^ 2   m o d   N ,   m ^ 3   m o d   N 这 是 使 用 量 子 计 算 的 一 步 。 第 三 步 ： 如 果 周 期 P 是 奇 数 ， 回 到 第 一 步 ， 选 择 另 一 个 随 机 整 数 。 如 果 不 是 ， 继 续 下 一 步 。 第 四 步 ： 检 验 如 果 成 立 ， 则 继 续 第 五 步 ； 反 之 ， 回 到 第 一 步 。 第 五 步 ： 解 解 得 一 个 非 凡 素 因 数 N 的 值 ， 然 后 你 便 能 破 解 R S A 加 密 了 。 第 二 步 是 怎 样 实 现 的 ？ 然 而 ， 量 子 计 算 机 是 如 何 找 到 函 数 周 期 的 ？ 这 又 为 什 么 如 此 重 要 ？ 我 们 来 看 一 下 周 期   P   ： m   m o d   N ,   m ^ 2   m o d   N ,   m ^ 3   m o d   N ( 由 于 这 是 一 个 指 数 函 数 ， 我 们 可 以 将 一 个 复 杂 的 质 数 转 换 成 双 曲 正 弦 、 余 弦 然 后 得 到 周 期 ) 这 个 发 现 周 期 的 过 程 需 要 依 赖 量 子 计 算 机 同 时 计 算 许 多 状 态 的 能 力 ， 也 就 是 状 态 的 “ 叠 加 ” ， 因 此 我 们 能 找 到 方 程 的 周 期 。 我 们 需 要 这 么 做 ： 1 .   应 用 H a d a m a r d   g a t e 来 创 建 一 个 量 子 叠 加 态 2 .   量 子 转 换 使 方 程 生 效 3 .   执 行 量 子 傅 立 叶 变 换 与 传 统 情 况 类 似 ， 在 这 些 转 化 之 后 ， 一 个 测 量 值 将 会 产 生 一 个 近 似 方 程 周 期 的 值 （ 你 可 以 获 得 “ 波 峰 ” ， 就 像 傅 立 叶 变 换 中 的 ， 而 准 确 性 会 更
原 文 ： h t t p : / / w w w . f r e e b u f . c o m / n e w s / 7 5 3 4 6 . h t m l 作 者 ：   空 白 高 一 点 ） 。 使 用 量 子 傅 立 叶 变 换 ， 我 们 能 够 解 决 排 序 和 因 数 问 题 ， 这 二 者 相 同 。 量 子 傅 立 叶 变 换 可 以 让 一 台 量 子 计 算 机 进 行 相 位 估 计 （ 酉 算 子 特 征 值 的 近 似 值 ） 。 当 你 完 成 量 子 部 分 （ 第 二 步 ） 的 时 候 ， 你 可 以 检 查 一 下 周 期 的 有 效 性 ， 然 后 使 用 另 一 个 传 统 的 最 大 公 约 数 算 法 得 到 密 钥 的 质 因 素 。 有 趣 的 是 ， 由 于 这 项 技 术 并 不 是 在 于 找 到 所 有 潜 在 质 因 数 ， 而 是 找 到 潜 在 周 期 ， 你 就 不 必 尝 试 很 多 随 机 数 直 到 找 到 一 个 成 功 的 质 因 数 N 。 如 果 P 是 奇 数 ， 那 你 不 得 不 回 到 第 一 步 ， 这 里 K 是 一 个 不 同 于 N 的 质 因 素 。 因 此 ， 即 使 你 加 倍 密 钥 长 度 （ N ） ， 寻 找 质 因 数 也 不 会 出 现 放 缓 的 情 况 。 R S A 是 不 安 全 的 ， 同 样 加 倍 密 钥 长 度 也 不 能 帮 你 抵 御 量 子 计 算 的 汹 涌 来 袭 ， 而 保 障 安 全 。 “ 破 解 R S A - 2 0 4 8 （ 2 0 4 8 - b i t ） 的 密 钥 可 能 需 要 耗 费 传 统 电 脑 1 0 亿 年 的 时 间 ， 而 量 子 计 算 机 只 需 要 1 0 0 秒 就 可 以 完 成 。 ” — — D r .   K r y s t a   S v o r e ,   微 软 研 究 院 量 子 傅 立 叶 变 换 被 用 于 建 立 量 子 线 路 ， 使 得 秀 尔 算 法 的 物 理 实 现 成 了 量 子 计 算 机 最 为 轻 松 的 任 务 之 一 。 量 子 傅 立 叶 变 换 ： 青 出 于 蓝 秀 尔 算 法 的 核 心 是 发 现 顺 序 ， 这 样 便 可 以 减 少 阿 贝 尔 的 隐 子 群 问 题 ， 使 用 量 子 傅 立 叶 变 换 便 可 以 解 决 。 — — N I S T   量 子 世 界 量 子 傅 立 叶 变 换 是 许 多 量 子 算 法 的 关 键 所 在 。 它 并 不 加 速 寻 找 传 统 傅 立 叶 转 变 ， 但 是 能 够 在 一 个 量 子 振 幅 内 执 行 一 个 傅 立 叶 变 换 。 在 一 台 量 子 计 算 机 上 可 以 指 数 增 长 般 快 速 处 理 量 子 傅 立 叶 变 换 。 虽 然 超 过 了 直 接 映 射 经 典 傅 立 叶 变 换 的 范 畴 ， 量 子 计 算 机 也 可 以 做 其 他 的 事 。 例 如 ， 解 决 隐 子 群 问 题 ( 也 就 是 解 决 离 散 对 数 问 题 ) ， 或 是 计 数 问 题 ( 解 决 了 这 个 问 题 就 可 以 解 决 现 代 密 码 学 中 很 多 其 他 形 式 的 密 码 ) 。 更 重 要 的 是 ， 量 子 傅 立 叶 变 换 可 以 应 用 到 机 器 学 习 、 化 学 、 材 料 科 学 或 者 模 拟 量 子 系 统 。 秀 尔 算 法 中 只 有 一 个 步 骤 是 需 要 在 量 子 计 算 机 上 完 成 的 ， 其 他 的 都 可 以 在 普 通 的 超 级 计 算 机 上 完 成 。 量 子 计 算 机 运 行 完 子 程 序 后 就 会 将 结 果 返 回 给 超 级 计 算 机 让 它 继 续 完 成 计 算 过 程 。 量 子 计 算 机 可 能 永 远 不 会 是 单 独 存 在 的 ， 而 是 一 直 和 超 级 计 算 机 配 合 执 行 任 务 ， 经 过 这 样 的 配 合 它 们 就 可 以 破 解 R S A 密 钥 。 因 为 篇 幅 有 限 ， 很 多 数 学 细 节 和 证 明 过 程 就 不 再 赘 述 了 ， 如 果 你 对 这 些 数 学 解 释 感 兴 趣 ， 如 果 你 具 备 线 性 代 数 、 群 论 、 高 等 数 学 的 知 识 ， 你 可 以 看 看 这 些 ： Q u a n t u m   C o m p u t e r   S c i e n c e Q u a n t u m   I n f o r m a t i o n   a n d   Q u a n t u m   C o m p u t a t i o n N I S T   Q u a n t u m   Z o o     —   一 个 所 有 量 子 算 法 的 列 表 * 参 考 来 源 ： m e d i u m ， v u l t u r e 对 本 文 有 贡 献 ，
阅 读 原 文
回复

举报

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

本版积分规则

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

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