搜索

[20813] 2017-07-08_非对称加密：RSA、ECC

文档创建者：s7ckTeam
浏览次数：0
最后更新：2025-01-18
2017-07-08_非对称加密：RSA、ECC 非 对 称 加 密 ： R S A 、 E C C 原 创   l e m o n   L e m o n S e c   2 0 1 7 - 0 7 - 0 8 对 称 加 密 算 法 在 加 密 和 解 密 时 使 用 的 是 同 一 个 秘 钥 ； 而 非 对 称 加 密 算 法 需 要 两 个 密 钥 来 进 行 加 密 和 解 密 ， 这 两 个 秘 钥 是 公 开 密 钥 （ p u b l i c   k e y ， 简 称 公 钥 ） 和 私 有 密 钥 （ p r i v a t e   k e y ， 简 称 私 钥 ） 。 与 对 称 加 密 算 法 不 同 ， 非 对 称 加 密 算 法 需 要 两 个 密 钥 ： 公 开 密 钥 （ p u b l i c k e y ） 和 私 有 密 钥 （ p r i v a t e k e y ） 。 公 开 密 钥 与 私 有 密 钥 是 一 对 ， 如 果 用 公 开 密 钥 对 数 据 进 行 加 密 ， 只 有 用 对 应 的 私 有 密 钥 才 能 解 密 ； 如 果 用 私 有 密 钥 对 数 据 进 行 加 密 ， 那 么 只 有 用 对 应 的 公 开 密 钥 才 能 解 密 。 因 为 加 密 和 解 密 使 用 的 是 两 个 不 同 的 密 钥 ， 所 以 这 种 算 法 叫 作 非 对 称 加 密 算 法 。 非 对 称 加 密 与 对 称 加 密 相 比 ， 其 安 全 性 更 好 ： 对 称 加 密 的 通 信 双 方 使 用 相 同 的 秘 钥 ， 如 果 一 方 的 秘 钥 遭 泄 露 ， 那 么 整 个 通 信 就 会 被 破 解 。 而 非 对 称 加 密 使 用 一 对 秘 钥 ， 一 个 用 来 加 密 ， 一 个 用 来 解 密 ， 而 且 公 钥 是 公 开 的 ， 秘 钥 是 自 己 保 存 的 ， 不 需 要 像 对 称 加 密 那 样 在 通 信 之 前 要 先 同 步 秘 钥 。 非 对 称 加 密 的 缺 点 是 加 密 和 解 密 花 费 时 间 长 、 速 度 慢 ， 只 适 合 对 少 量 数 据 进 行 加 密 。 在 非 对 称 加 密 中 使 用 的 主 要 算 法 有 ： R S A 、 E l g a m a l 、 背 包 算 法 、 R a b i n 、 D - H 、 E C C （ 椭 圆 曲 线 加 密 算 法 ） 等 。 R S A 公 钥 加 密 算 法 是 1 9 7 7 年 由 罗 纳 德 · 李 维 斯 特 （ 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 ） 一 起 提 出 的 。 1 9 8 7 年 首 次 公 布 ， 当 时 他 们 三 人 都 在 麻 省 理 工 学 院 工 作 。 R S A 就 是 他 们 三 人 姓 氏 开 头 字 母 拼 在 一 起 组 成 的 。 R S A 是 目 前 最 有 影 响 力 的 公 钥 加 密 算 法 ， 它 能 够 抵 抗 到 目 前 为 止 已 知 的 绝 大 多 数 密 码 攻 击 ， 已 被 I S O 推 荐 为 公 钥 数 据 加 密 标 准 。 今 天 只 有 短 的 R S A 钥 匙 才 可 能 被 强 力 方 式 解 破 。 到 2 0 0 8 年 为 止 ， 世 界 上 还 没 有 任 何 可 靠 的 攻 击 R S A 算 法 的 方 式 。 只 要 其 钥 匙 的 长 度 足 够 长 ， 用 R S A 加 密 的 信 息 实 际 上 是 不 能 被 解 破 的 。 但 在 分 布 式 计 算 和 量 子 计 算 机 理 论 日 趋 成 熟 的 今 天 ， R S A 加 密 安 全 性 受 到 了 挑 战 。 R S A 算 法 基 于 一 个 十 分 简 单 的 数 论 事 实 ： 将 两 个 大 质 数 相 乘 十 分 容 易 ， 但 是 想 要 对 其 乘 积 进 行 因 式 分 解 却 极 其 困 难 ， 因 此 可 以 将 乘 积 公 开 作 为 加 密 密 钥 。 R S A 算 法 是 一 种 非 对 称 密 码 算 法 ， 所 谓 非 对 称 ， 就 是 指 该 算 法 需 要 一 对 密 钥 ， 使 用 其 中 一 个 加 密 ， 则 需 要 用 另 一 个 才 能 解 密 。 R S A 的 算 法 涉 及 三 个 参 数 ， n 、 e 1 、 e 2 。 其 中 ， n 是 两 个 大 质 数 是 两 个 大 质 数 p 、 、 q 的 积 ， 的 积 ， n 的 二 进 制 表 示 时 所 占 用 的 位 数 ， 就 是 所 谓 的 密 钥 长 度 。 的 二 进 制 表 示 时 所 占 用 的 位 数 ， 就 是 所 谓 的 密 钥 长 度 。 e 1 和 e 2 是 一 对 相 关 的 值 ， e 1 可 以 任 意 取 ， 但 要 求 e 1 与 ( p - 1 ) * ( q - 1 ) 互 质 ； 再 选 择 e 2 ， 要 求 ( e 2 * e 1 ) m o d ( ( p - 1 ) * ( q - 1 ) ) = 1 。 （ n ， e 1 ) , ( n ， e 2 ) 就 是 密 钥 对 。 其 中 ( n ， ， e 1 ) 为 为 公 钥 ， ( n ， ， e 2 ) 为 私 钥 。 为 私 钥 。 [ 1 ]   R S A 加 解 密 的 算 法 完 全 相 同 ， 设 A 为 明 文 ， B 为 密 文 ， 则 ： A = B ^ e 2   m o d   n ； B = A ^ e 1   m o d   n ； （ 公 钥 加 密 体 制 中 ， 一 般 用 公 钥 加 密 ， 私 钥 解 密 ） e 1 和 e 2 可 以 互 换 使 用 ， 即 ： A = B ^ e 1   m o d   n ； B = A ^ e 2   m o d   n ; 运 算 速 度 由 于 进 行 的 都 是 大 数 计 算 ， 使 得 R S A 最 快 的 情 况 也 比 D E S 慢 上 好 几 倍 ， 无 论 是 软 件 还 是 硬 件 实 现 。 速 度 一 直 是 R S A 的 缺 陷 。 一 般 来 说 只 用 于 少 量 数 据 加 密 。 R S A 的 速 度 比 对 应 同 样 安 全 级 别 的 对 称 密 码 算 法 要 慢 1 0 0 0 倍 左 右 。 比 起 D E S 和 其 它 对 称 算 法 来 说 ， R S A 要 慢 得 多 。 实 际 上 B o b 一 般 使 用 一 种 对 称 算 法 来 加 密 他 的 信 息 ， 然 后 用 R S A 来 加 密 他 的
比 较 短 的 对 称 密 码 ， 然 后 将 用 R S A 加 密 的 对 称 密 码 和 用 对 称 算 法 加 密 的 消 息 送 给 A l i c e 。 这 样 一 来 对 随 机 数 的 要 求 就 更 高 了 ， 尤 其 对 产 生 对 称 密 码 的 要 求 非 常 高 ， 因 为 否 则 的 话 可 以 越 过 R S A 来 直 接 攻 击 对 称 密 码 。 E C C ： ： 椭 圆 曲 线 上 简 单 的 加 密 / 解 密 公 开 密 钥 算 法 总 是 要 基 于 一 个 数 学 上 的 难 题 。 比 如 R S A   依 据 的 是 ： 给 定 两 个 素 数 p 、 q   很 容 易 相 乘 得 到 n ， 而 对 n 进 行 因 式 分 解 却 相 对 困 难 。 那 椭 圆 曲 线 上 有 什 么 难 题 呢 ？ 考 虑 如 下 等 式 ： K = k G   [ 其 中   K , G 为 E p ( a , b ) 上 的 点 ， k 为 小 于 n （ n 是 点 G 的 阶 ） 的 整 数 ] 不 难 发 现 ， 给 定 k 和 G ， 根 据 加 法 法 则 ， 计 算 K 很 容 易 ； 但 给 定 K 和 G ， 求 k 就 相 对 困 难 了 。 这 就 是 椭 圆 曲 线 加 密 算 法 采 用 的 难 题 。 我 们 把 点 G 称 为 基 点 （ b a s e   p o i n t ） ， k （ k 现 在 我 们 描 述 一 个 利 用 椭 圆 曲 线 进 行 加 密 通 信 的 过 程 ： 1 、 用 户 A 选 定 一 条 椭 圆 曲 线 E p ( a , b ) ， 并 取 椭 圆 曲 线 上 一 点 ， 作 为 基 点 G 。 2 、 用 户 A 选 择 一 个 私 有 密 钥 k ， 并 生 成 公 开 密 钥 K = k G 。 3 、 用 户 A 将 E p ( a , b ) 和 点 K ， G 传 给 用 户 B 。 4 、 用 户 B 接 到 信 息 后   ， 将 待 传 输 的 明 文 编 码 到 E p ( a , b ) 上 一 点 M （ 编 码 方 法 很 多 ， 这 里 不 作 讨 论 ） ， 并 产 生 一 个 随 机 整 数 r （ r 5 、 用 户 B 计 算 点 C 1 = M + r K ； C 2 = r G 。 6 、 用 户 B 将 C 1 、 C 2 传 给 用 户 A 。 7 、 用 户 A 接 到 信 息 后 ， 计 算 C 1 - k C 2 ， 结 果 就 是 点 M 。 因 为 C 1 - k C 2 = M + r K - k ( r G ) = M + r K - r ( k G ) = M 再 对 点 M 进 行 解 码 就 可 以 得 到 明 文 。 在 这 个 加 密 通 信 中 ， 如 果 有 一 个 偷 窥 者 H   ， 他 只 能 看 到 E p ( a , b ) 、 K 、 G 、 C 1 、 C 2   而 通 过 K 、 G   求 k   或 通 过 C 2 、 G 求 r   都 是 相 对 困 难 的 。 因 此 ， H 无 法 得 到 A 、 B 间 传 送 的 明 文 信 息 。 对 称 加 密 算 法 在 加 密 和 解 密 时 使 用 的 是 同 一 个 秘 钥 ； 而 非 对 称 加 密 算 法 需 要 两 个 密 钥 来 进 行 加 密 和 解 密 ， 这 两 个 秘 钥 是 公 开 密 钥 （ p u b l i c   k e y ， 简 称 公 钥 ） 和 私 有 密 钥 （ p r i v a t e   k e y ， 简 称 私 钥 ） 。 与 对 称 加 密 算 法 不 同 ， 非 对 称 加 密 算 法 需 要 两 个 密 钥 ： 公 开 密 钥 （ p u b l i c k e y ） 和 私 有 密 钥 （ p r i v a t e k e y ） 。 公 开 密 钥 与 私 有 密 钥 是 一 对 ， 如 果 用 公 开 密 钥 对 数 据 进 行 加 密 ， 只 有 用 对 应 的 私 有 密 钥 才 能 解 密 ； 如 果 用 私 有 密 钥 对 数 据 进 行 加 密 ， 那 么 只 有 用 对 应 的 公 开 密 钥 才 能 解 密 。 因 为 加 密 和 解 密 使 用 的 是 两 个 不 同 的 密 钥 ， 所 以 这 种 算 法 叫 作 非 对 称 加 密 算 法 。 非 对 称 加 密 与 对 称 加 密 相 比 ， 其 安 全 性 更 好 ： 对 称 加 密 的 通 信 双 方 使 用 相 同 的 秘 钥 ， 如 果 一 方 的 秘 钥 遭 泄 露 ， 那 么 整 个 通 信 就 会 被 破 解 。 而 非 对 称 加 密 使 用 一 对 秘 钥 ， 一 个 用 来 加 密 ， 一 个 用 来 解 密 ， 而 且 公 钥 是 公 开 的 ， 秘 钥 是 自 己 保 存 的 ， 不 需 要 像 对 称 加 密 那 样 在 通 信 之 前 要 先 同 步 秘 钥 。 非 对 称 加 密 的 缺 点 是 加 密 和 解 密 花 费 时 间 长 、 速 度 慢 ， 只 适 合 对 少 量 数 据 进 行 加 密 。 在 非 对 称 加 密 中 使 用 的 主 要 算 法 有 ： R S A 、 E l g a m a l 、 背 包 算 法 、 R a b i n 、 D - H 、 E C C （ 椭 圆 曲 线 加 密 算 法 ） 等 。 R S A 公 钥 加 密 算 法 是 1 9 7 7 年 由 罗 纳 德 · 李 维 斯 特 （ 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 ） 一 起 提 出 的 。 1 9 8 7 年 首 次 公 布 ， 当 时 他 们 三 人 都 在 麻 省 理 工 学 院 工 作 。 R S A 就 是 他 们 三 人 姓 氏 开 头 字 母 拼 在 一 起 组 成 的 。 R S A 是 目 前 最 有 影 响 力 的 公 钥 加 密 算 法 ， 它 能 够 抵 抗 到 目 前 为 止 已 知 的 绝 大 多 数 密 码 攻 击 ， 已 被 I S O 推 荐 为 公 钥 数 据 加 密 标 准 。 今 天 只 有 短 的 R S A 钥 匙 才 可 能 被 强 力 方 式 解 破 。 到 2 0 0 8 年 为 止 ， 世 界 上 还 没 有 任 何 可 靠 的 攻 击 R S A 算 法 的 方 式 。 只 要 其 钥
匙 的 长 度 足 够 长 ， 用 R S A 加 密 的 信 息 实 际 上 是 不 能 被 解 破 的 。 但 在 分 布 式 计 算 和 量 子 计 算 机 理 论 日 趋 成 熟 的 今 天 ， R S A 加 密 安 全 性 受 到 了 挑 战 。 R S A 算 法 基 于 一 个 十 分 简 单 的 数 论 事 实 ： 将 两 个 大 质 数 相 乘 十 分 容 易 ， 但 是 想 要 对 其 乘 积 进 行 因 式 分 解 却 极 其 困 难 ， 因 此 可 以 将 乘 积 公 开 作 为 加 密 密 钥 。 R S A 算 法 是 一 种 非 对 称 密 码 算 法 ， 所 谓 非 对 称 ， 就 是 指 该 算 法 需 要 一 对 密 钥 ， 使 用 其 中 一 个 加 密 ， 则 需 要 用 另 一 个 才 能 解 密 。 R S A 的 算 法 涉 及 三 个 参 数 ， n 、 e 1 、 e 2 。 其 中 ， n 是 两 个 大 质 数 是 两 个 大 质 数 p 、 、 q 的 积 ， 的 积 ， n 的 二 进 制 表 示 时 所 占 用 的 位 数 ， 就 是 所 谓 的 密 钥 长 度 。 的 二 进 制 表 示 时 所 占 用 的 位 数 ， 就 是 所 谓 的 密 钥 长 度 。 e 1 和 e 2 是 一 对 相 关 的 值 ， e 1 可 以 任 意 取 ， 但 要 求 e 1 与 ( p - 1 ) * ( q - 1 ) 互 质 ； 再 选 择 e 2 ， 要 求 ( e 2 * e 1 ) m o d ( ( p - 1 ) * ( q - 1 ) ) = 1 。 （ n ， e 1 ) , ( n ， e 2 ) 就 是 密 钥 对 。 其 中 ( n ， ， e 1 ) 为 为 公 钥 ， ( n ， ， e 2 ) 为 私 钥 。 为 私 钥 。 [ 1 ]   R S A 加 解 密 的 算 法 完 全 相 同 ， 设 A 为 明 文 ， B 为 密 文 ， 则 ： A = B ^ e 2   m o d   n ； B = A ^ e 1   m o d   n ； （ 公 钥 加 密 体 制 中 ， 一 般 用 公 钥 加 密 ， 私 钥 解 密 ） e 1 和 e 2 可 以 互 换 使 用 ， 即 ： A = B ^ e 1   m o d   n ； B = A ^ e 2   m o d   n ; 运 算 速 度 由 于 进 行 的 都 是 大 数 计 算 ， 使 得 R S A 最 快 的 情 况 也 比 D E S 慢 上 好 几 倍 ， 无 论 是 软 件 还 是 硬 件 实 现 。 速 度 一 直 是 R S A 的 缺 陷 。 一 般 来 说 只 用 于 少 量 数 据 加 密 。 R S A 的 速 度 比 对 应 同 样 安 全 级 别 的 对 称 密 码 算 法 要 慢 1 0 0 0 倍 左 右 。 比 起 D E S 和 其 它 对 称 算 法 来 说 ， R S A 要 慢 得 多 。 实 际 上 B o b 一 般 使 用 一 种 对 称 算 法 来 加 密 他 的 信 息 ， 然 后 用 R S A 来 加 密 他 的 比 较 短 的 对 称 密 码 ， 然 后 将 用 R S A 加 密 的 对 称 密 码 和 用 对 称 算 法 加 密 的 消 息 送 给 A l i c e 。 这 样 一 来 对 随 机 数 的 要 求 就 更 高 了 ， 尤 其 对 产 生 对 称 密 码 的 要 求 非 常 高 ， 因 为 否 则 的 话 可 以 越 过 R S A 来 直 接 攻 击 对 称 密 码 。 E C C ： ： 椭 圆 曲 线 上 简 单 的 加 密 / 解 密 公 开 密 钥 算 法 总 是 要 基 于 一 个 数 学 上 的 难 题 。 比 如 R S A   依 据 的 是 ： 给 定 两 个 素 数 p 、 q   很 容 易 相 乘 得 到 n ， 而 对 n 进 行 因 式 分 解 却 相 对 困 难 。 那 椭 圆 曲 线 上 有 什 么 难 题 呢 ？ 考 虑 如 下 等 式 ： K = k G   [ 其 中   K , G 为 E p ( a , b ) 上 的 点 ， k 为 小 于 n （ n 是 点 G 的 阶 ） 的 整 数 ] 不 难 发 现 ， 给 定 k 和 G ， 根 据 加 法 法 则 ， 计 算 K 很 容 易 ； 但 给 定 K 和 G ， 求 k 就 相 对 困 难 了 。 这 就 是 椭 圆 曲 线 加 密 算 法 采 用 的 难 题 。 我 们 把 点 G 称 为 基 点 （ b a s e   p o i n t ） ， k （ k 现 在 我 们 描 述 一 个 利 用 椭 圆 曲 线 进 行 加 密 通 信 的 过 程 ： 1 、 用 户 A 选 定 一 条 椭 圆 曲 线 E p ( a , b ) ， 并 取 椭 圆 曲 线 上 一 点 ， 作 为 基 点 G 。 2 、 用 户 A 选 择 一 个 私 有 密 钥 k ， 并 生 成 公 开 密 钥 K = k G 。 3 、 用 户 A 将 E p ( a , b ) 和 点 K ， G 传 给 用 户 B 。 4 、 用 户 B 接 到 信 息 后   ， 将 待 传 输 的 明 文 编 码 到 E p ( a , b ) 上 一 点 M （ 编 码 方 法 很 多 ， 这 里 不 作 讨 论 ） ， 并 产 生 一 个 随 机 整 数 r （ r 5 、 用 户 B 计 算 点 C 1 = M + r K ； C 2 = r G 。 6 、 用 户 B 将 C 1 、 C 2 传 给 用 户 A 。 7 、 用 户 A 接 到 信 息 后 ， 计 算 C 1 - k C 2 ， 结 果 就 是 点 M 。 因 为 C 1 - k C 2 = M + r K - k ( r G ) = M + r K - r ( k G ) = M 再 对 点 M 进 行 解 码 就 可 以 得 到 明 文 。
在 这 个 加 密 通 信 中 ， 如 果 有 一 个 偷 窥 者 H   ， 他 只 能 看 到 E p ( a , b ) 、 K 、 G 、 C 1 、 C 2   而 通 过 K 、 G   求 k   或 通 过 C 2 、 G 求 r   都 是 相 对 困 难 的 。 因 此 ， H 无 法 得 到 A 、 B 间 传 送 的 明 文 信 息 。 密 码 学 中 ， 描 述 一 条 F p 上 的 椭 圆 曲 线 ， 常 用 到 六 个 参 量 ： T = ( p , a , b , G , n , h ) 。 （ p   、 a   、 b   用 来 确 定 一 条 椭 圆 曲 线 ， G 为 基 点 ， n 为 点 G 的 阶 ， h   是 椭 圆 曲 线 上 所 有 点 的 个 数 m 与 n 相 除 的 整 数 部 分 ） 查 看 更 多 文 章 ， 关 注 下 方 二 维 码
回复

举报

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

本版积分规则

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

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