搜索

[11565] 2017-07-19_如何利用密码学以及数论基础攻击一个“宣称安全”的密码系统

文档创建者：s7ckTeam
浏览次数：20
最后更新：2025-01-18
2017-07-19_如何利用密码学以及数论基础攻击一个“宣称安全”的密码系统 如 何 利 用 密 码 学 以 及 数 论 基 础 攻 击 一 个 “ 宣 称 安 全 ” 的 密 码 系 统 T e d Z h a n g   F r e e B u f   2 0 1 7 - 0 7 - 1 9 最 近 在 对 基 于 区 块 链 构 建 的 信 任 社 会 （ 未 来 社 会 形 态 ） 非 常 感 兴 趣 ， 区 块 技 术 去 中 心 化 的 特 性 ， 让 没 有 金 融 机 最 近 在 对 基 于 区 块 链 构 建 的 信 任 社 会 （ 未 来 社 会 形 态 ） 非 常 感 兴 趣 ， 区 块 技 术 去 中 心 化 的 特 性 ， 让 没 有 金 融 机 构 成 为 了 可 能 （ 包 括 央 行 ， 以 及 各 种 商 业 银 行 ） 。 构 成 为 了 可 能 （ 包 括 央 行 ， 以 及 各 种 商 业 银 行 ） 。 除 了 在 数 字 货 币 领 域 大 放 异 彩 外 ， 在 包 括 供 应 链 ， 网 络 购 物 ， 公 平 合 约 等 方 面 的 应 用 也 非 常 广 泛 。 其 中 智 能 合 约 的 特 性 十 分 的 吸 引 我 。 不 过 我 今 天 并 不 想 讨 论 区 块 技 术 ， 因 为 区 块 技 术 建 立 在 密 码 学 的 技 术 之 上 ， 今 天 我 们 讨 论 如 何 利 用 密 码 学 以 及 数 论 基 础 攻 击 一 个 宣 称 安 全 的 密 码 系 统 。 在 密 码 学 中 ， 算 法 ， 秘 钥 以 及 协 议 构 成 了 一 个 完 整 的 密 码 系 统 。 算 法 是 密 码 系 统 的 基 础 ， 它 是 将 一 组 或 多 组 输 入 信 息 转 化 成 一 组 或 多 组 输 出 信 息 的 数 学 方 法 ， 算 法 的 输 出 会 被 秘 钥 影 响 ， 秘 钥 不 同 ， 输 出 也 不 同 。 因 此 ， 加 密 同 样 的 信 息 ， A 用 秘 钥 K a 加 密 与 B 用 秘 钥 K b 加 密 输 出 的 信 息 是 完 全 不 同 的 。
秘 钥 是 密 码 系 统 的 核 心 ， 奥 秘 在 于 算 法 存 在 一 个 最 优 解 （ 最 优 解 有 很 多 种 解 释 ， 例 如 超 递 增 序 列 ， 因 式 分 解 两 素 数 之 和 等 ） ， 这 个 秘 密 就 是 秘 钥 。 如 果 一 个 人 想 要 解 密 别 人 的 密 文 ， 在 不 知 道 秘 钥 的 情 况 下 ， 他 只 能 尝 试 解 数 学 难 题 ， 这 对 于 普 通 人 拥 有 的 资 源 来 说 ， 直 到 宇 宙 毁 灭 也 无 法 得 出 答 案 。 有 了 算 法 和 秘 钥 ， 没 有 协 议 就 不 是 一 个 密 码 系 统 。 协 议 是 指 由 多 方 参 与 的 ， 确 定 要 去 完 成 一 些 事 情 。 如 果 没 有 多 方 参 与 ， 或 者 没 有 去 完 成 一 些 目 标 就 不 叫 协 议 。 协 议 有 很 多 种 ， 最 明 显 比 如 秘 钥 交 换 协 议 （ 例 如 A 和 B 要 在 一 个 加 密 的 通 道 中 传 递 信 息 ， 在 这 之 前 A 和 B 要 协 商 一 个 秘 钥 并 交 换 ， 使 得 A 可 以 加 密 消 息 发 送 给 B 并 确 保 B 可 以 解 密 信 息 ） 。 密 钥 交 换 协 议 密 钥 交 换 协 议 在 一 个 安 全 的 密 码 系 统 中 ， 必 须 是 算 法 ， 秘 钥 ， 协 议 都 安 全 ， 如 果 其 中 一 个 是 不 安 全 的 ， 那 么 整 个 系 统 就 是 不 在 一 个 安 全 的 密 码 系 统 中 ， 必 须 是 算 法 ， 秘 钥 ， 协 议 都 安 全 ， 如 果 其 中 一 个 是 不 安 全 的 ， 那 么 整 个 系 统 就 是 不 安 全 的 。 安 全 的 。 大 多 数 流 行 的 公 开 算 法 ， 已 经 被 广 泛 的 证 明 是 安 全 的 ， 它 们 经 历 过 很 多 理 论 数 学 家 的 分 析 。 秘 钥 的 安 全 性 由 秘 钥 长
度 ， 以 及 你 是 否 妥 当 的 保 管 你 的 秘 钥 来 决 定 。 如 果 你 做 的 不 错 ， 那 么 秘 钥 也 是 安 全 的 。 协 议 却 不 是 如 此 了 ， 协 议 很 脆 弱 。 举 个 例 子 ， A 将 重 要 的 信 息 加 密 发 送 给 B ， 只 有 B 有 秘 钥 可 以 解 密 这 些 信 息 ， C 在 网 路 上 监 听 到 了 A 发 送 给 B 的 秘 密 ， 但 是 C 没 有 秘 钥 无 法 解 密 信 息 ， 怎 么 办 。 上 面 说 过 ， 秘 钥 是 这 个 数 学 难 题 的 最 优 解 ， 如 果 没 有 秘 钥 ， C 就 只 能 尝 试 解 数 学 难 题 ， 恐 怕 C 这 一 生 都 无 法 解 开 ， 但 是 C 的 老 板 要 求 他 必 须 在 7 2 小 时 内 解 密 信 息 ， 不 然 C 所 在 的 公 司 就 要 遭 受 重 大 损 失 。 于 是 C 决 定 铤 而 走 险 ， 他 绑 架 了 B ， 并 对 B 进 行 严 刑 拷 打 ， B 扛 不 住 ， 交 出 了 他 的 秘 钥 ， C 拿 着 B 的 秘 钥 解 密 了 秘 密 ， 并 干 掉 了 B 。 上 面 的 例 子 说 明 了 协 议 在 整 个 密 码 系 统 中 是 一 个 易 攻 击 的 薄 弱 环 节 ， 这 样 的 攻 击 类 型 很 多 （ 贿 赂 ， 美 色 诱 惑 ， 威 胁 等 ） 。 我 们 来 尝 试 把 这 种 攻 击 带 入 到 软 件 破 解 上 来 ， 同 样 的 结 论 也 是 攻 击 协 议 ， 而 非 攻 击 算 法 和 秘 钥 。 同 样 来 举 个 例 子 ， 软 件 D 采 用 R S A 公 开 秘 钥 算 法 来 对 用 户 的 信 息 以 及 软 件 产 品 序 列 号 摘 要 进 行 加 密 ， 并 发 送 给 软 件 D 公 司 的 注 册 服 务 器 ， 软 件 公 司 D 的 计 算 机 收 到 用 户 A 发 送 给 它 的 加 密 信 息 ， 用 自 己 的 私 钥 解 密 并 把 用 户 信 息 与 数 据 库 中 的 信 息 进 行 对 比 ， 如 果 序 列 号 不 在 D 公 司 的 数 据 库 中 说 明 这 个 产 品 的 不 是 D 公 司 销 售 的 产 品 ， 如 果 序 列 号 在 D 公 司 的 数 据 库 中 ， 并 且 A 用 户 信 息 不 在 数 据 库 中 ， 那 么 A 是 第 一 次 注 册 ， 将 A 的 信 息 与 序 列 号 绑 定 在 一 起 保 存 在 数 据 库 中 ， 此 序 列 号 将 不 能 再 给 其 他 人 使 用 。 如 果 序 列 号 和 A 都 在 数 据 库 中 ， 并 且 序 列 号 与 A 绑 定 ， 那 么 D 公 司 用 私 钥 加 密 一 段 许 可 信 息 发 送 给 A ， A 每 次 使 用 D 软 件 的 时 候 验 证 这 段 信 息 ， 如 果 是 D 公 司 发 送 的 许 可 信 息 允 许 使 用 ， 如 果 不 是 不 允 许 登 陆 。 看 起 来 很 不 错 ， R S A 是 安 全 的 公 开 密 钥 算 法 ， 并 且 秘 钥 被 D 公 司 保 存 起 来 ， 除 非 你 能 贿 赂 D 公 司 的 员 工 获 得 秘 钥 ， 或 者 攻 破 D 公 司 的 网 路 ， 否 则 秘 钥 也 是 安 全 的 。 因 此 攻 击 算 法 和 秘 钥 是 不 现 实 的 。 那 么 ， 我 们 可 以 从 协 议 的 角 度 入 手 ， 看 看 有 没 有 弱 点 。 先 简 单 说 一 下 R S A 算 法 ： 1 .   选 择 两 个 大 素 数   p   和   q ， 假 设   p = 3 ， q = 1 1 2 .   计 算   n   =   p   ×   q   =   3   ×   1 1   =   3 3 3 .   计 算   ∅ ( n )   =   ( p   –   1 )   ×   ( q   –   1 )   =   2   ×   1 0   =   2 0 4 .   选 择   e   且   1   <   e   <   ∅ ( n )   ,   e   与   n   互 为 素 数 .   假 设   e   =   7 5 .   计 算   d ， 使   ( d   ×   e )   %   ∅ ( n )   =   1 .   假 设   d   =   3 ， 且   d   =   ( 3   ×   7 )   %   2 0   =   1 ， 满 足 条 件 6 .   公 开   e ,   n   = >   ( 7 ,   3 3 ) 7 .   保 密   d   = >   3 8 .   加 密 公 式   C   =   M e   %   n 9 .   解 密 公 式   M   =   C d   %   n
用 上 面 的 公 式 加 密 ， 假 如 消 息 是 2 ， C   =   2 7   %   3 3   =   2 9 ， 密 文 就 是 2 9 。 解 密 的 话 就 是 M   =   2 9 3   %   3 3   =   2 。 回 到 刚 才 的 软 件 破 解 问 题 上 ， 软 件 产 品 中 有 e 和 n ， 如 果 能 够 分 解 n 我 们 就 能 够 构 造 d ， 也 就 知 道 了 D 公 司 的 秘 钥 ， 由 于 分 解 n 是 一 个 数 学 难 题 ， 我 们 不 知 道 最 优 解 很 难 解 出 答 案 。 我 们 采 用 另 一 种 方 法 ， 破 坏 协 议 ， 首 先 我 们 自 己 选 择 2 个 大 素 数 ， 构 造 另 一 个 n ， 并 分 别 求 出 对 应 的 e 和 d 。 然 后 我 们 架 设 一 个 服 务 器 ， 用 来 模 仿 D 公 司 的 验 证 服 务 器 。 我 们 侵 入 D 公 司 的 软 件 ， 用 我 们 自 己 的 n 和 e 替 换 D 公 司 的 n 和 e ， 这 时 软 件 D 会 用 我 们 的 公 开 秘 钥 加 密 用 户 信 息 以 及 序 列 号 ， 这 段 信 息 是 无 法 送 给 D 公 司 验 证 的 ， 因 为 D 公 司 没 有 我 们 的 保 密 秘 钥 ， 无 法 解 密 信 息 ， 因 此 这 样 还 无 法 完 成 软 件 的 验 证 。 下 一 步 ， 我 们 使 软 件 D 将 加 密 好 的 信 息 发 送 给 我 们 刚 才 架 设 的 模 仿 D 公 司 的 服 务 器 ， 这 台 机 器 拥 有 我 们 的 保 密 秘 钥 ， 它 成 功 的 解 密 信 息 ， 并 直 接 构 造 一 个 验 证 通 过 的 数 据 块 ， 并 用 保 密 秘 钥 加 密 发 送 给 D 软 件 。 D 软 件 用 我 们 的 公 开 秘 钥 解 密 信 息 ， 验 证 一 切 正 常 ， 并 将 这 段 信 息 保 存 到 计 算 机 中 。 每 次 D 软 件 启 动 时 ， 重 新 检 查 是 否 存 在 验 证 通 过 信 息 块 ， 并 用 我 们 设 给 它 的 公 开 秘 钥 解 密 ， 解 密 成 功 后 通 过 验 证 ， 启 动 D 软 件 。 只 要 通 过 一 次 验 证 ， D 软 件 就 无 需 再 次 与 D 公 司 服 务 器 进 行 交 互 ， 因 此 完 成 了 破 解 。 再 次 说 明 ， 算 法 ， 秘 钥 ， 协 议 是 一 个 密 码 系 统 的 组 成 部 分 ， 任 何 一 个 方 面 不 安 全 ， 整 个 系 统 就 是 不 安 全 的 。 当 下 ， 很 多 厂 商 对 算 法 和 秘 钥 很 关 注 ， 在 算 法 的 选 择 与 秘 钥 的 长 度 上 下 足 了 功 夫 。 但 他 们 的 系 统 并 不 像 他 们 想 象 的 那 么 安 全 ， 因 为 他 们 忽 视 了 协 议 。 P S .   本 文 仅 仅 是 基 于 理 论 方 面 的 讨 论 ， 真 正 的 软 件 破 解 过 程 比 本 文 描 述 的 要 复 杂 的 多 ， 在 r e a l   w o r l d 中 尝 试 发 现 n 和 e 可 能 要 困 难 的 多 。 至 于 P a t c h 程 序 代 码 ， 改 变 程 序 运 行 流 程 来 达 到 破 解 目 的 与 本 文 讨 论 的 主 题 无 关 。
* 本 文 作 者 ： T e d Z h a n g ， 转 载 请 注 明 F r e e B u f . C O M 阅 读 原 文
回复

举报

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

本版积分规则

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