搜索

[12432] 2018-03-06_从小白变RSA大神，附常用工具使用方法及CTF中RSA典型例题

文档创建者：s7ckTeam
浏览次数：5
最后更新：2025-01-18
2018-03-06_从小白变RSA大神，附常用工具使用方法及CTF中RSA典型例题 从 小 白 变 R S A 大 神 ， 附 常 用 工 具 使 用 方 法 及 C T F 中 R S A 典 型 例 题 原 创   婷 儿 小 跟 班 ✧   F r e e B u f   2 0 1 8 - 0 3 - 0 6 * 本 文 作 者 ： 婷 儿 小 跟 班 ✧ ， 本 文 属   F r e e B u f   原 创 奖 励 计 划 ， 未 经 许 可 禁 止 转 载 。 前 言 前 言 R S A 加 解 密 类 题 型 是 加 解 密 类 题 型 是 c t f 题 中 常 见 题 型 ， 考 点 比 较 广 泛 ， 涉 及 各 种 攻 击 手 法 ， 以 前 在 这 栽 了 不 少 跟 头 ， 这 里 好 好 题 中 常 见 题 型 ， 考 点 比 较 广 泛 ， 涉 及 各 种 攻 击 手 法 ， 以 前 在 这 栽 了 不 少 跟 头 ， 这 里 好 好 总 结 一 下 。 包 括 总 结 一 下 。 包 括 R S A 加 密 原 理 ， 加 密 原 理 ， R S A 常 用 工 具 使 用 方 法 及 下 载 地 址 ， 常 用 工 具 使 用 方 法 及 下 载 地 址 ， R S A 典 型 例 题 。 典 型 例 题 。 R S A 加 密 基 本 原 理 加 密 基 本 原 理 加 密 过 程 加 密 过 程 选 择 两 个 大 素 数 p 和 q ， 计 算 出 模 数 N   =   p   *   q 计 算 φ   =   ( p − 1 )   *   ( q − 1 )   即 N 的 欧 拉 函 数 ， 然 后 选 择 一 个 e   ( 1 < e < φ ) ， 且 e 和 φ 互 质 取 e 的 模 反 数 为 d ， 计 算 方 法 :   e   *   d   ≡   1   ( m o d   φ ) 对 明 文 A 进 行 加 密 ： ， 得 到 的 B 即 为 密 文 对 密 文 B 进 行 解 密 ， ， 得 到 的 A 即 为 明 文 p   和   q   ： 大 整 数 N 的 两 个 因 子 （ f a c t o r ） N ： 大 整 数 N ， 我 们 称 之 为 模 数 （ m o d u l u s ） e   和   d ： 互 为 模 反 数 的 两 个 指 数 （ e x p o n e n t ） c   和   m ： 分 别 是 密 文 和 明 文 ， 这 里 一 般 指 的 是 一 个 十 进 制 的 数 一 般 有 如 下 称 呼 ： （ N ， e ） ： 公 钥 （ N ， d ） ： 私 钥 加 密 分 析 加 密 分 析 R S A 算 法 是 一 种 非 对 称 密 码 算 法 ， 所 谓 非 对 称 ， 就 是 指 该 算 法 需 要 一 对 密 钥 ， 使 用 其 中 一 个 加 密 ， 则 需 要 用 另 一 个 才 能 解 密 。 R S A 的 算 法 涉 及 三 个 参 数 ， n 、 e 、 d 。 其 中 ， n 是 两 个 大 质 数 p 、 q 的 积 ， n 以 二 进 制 表 示 时 所 占 用 的 位 数 ， 就 是 所 谓 的 密 钥 长 度 。 e 和 d 是 一 对 相 关 的 值 ， e 可 以 任 意 取 ， 但 要 求 e 与 ( p - 1 ) ( q - 1 ) 互 质 ； 再 选 择 d ， 要 求 。 令 φ   =   ( p - 1 ) ( q - 1 )   上 式 即     即 （ n ， e ) , ( n ， d ) 就 是 密 钥 对 。 其 中 ( n ， e ) 为 公 钥 ， ( n ， d ) 为 私 钥 。 R S A 加 解 密 的 算 法 完 全 相 同 ， 设 A 为 明 文 ， B 为 密 文 ， B ≡ A ^ e   ( m o d   n )   或   B   =   p o w ( A , e , n ) A ≡ B ^ d (   m o d   n )   或   A   =   p o w ( B , d , n ) ( e d )   ≡   1 ( m o d ( p - 1 ) × ( q - 1 ) ) d * e   =   1   m o d   φ ： ( d * e   -   1 ) %   φ   =   0
则 ： A ≡ B ^ d (   m o d   n ) ； B ≡ A ^ e   ( m o d   n ) ； （ 公 钥 加 密 体 制 中 ， 一 般 用 公 钥 加 密 ， 私 钥 解 密 ） e 和 d 可 以 互 换 使 用 ， 即 ： A ≡ B ^ e   ( m o d   n ) ； B ≡ A ^ d (   m o d   n ) ; 附 加 解 释 附 加 解 释 同 余 符 号   “   ≡   ” 数 论 中 的 重 要 概 念 。 给 定 一 个 正 整 数 m ， 如 果 两 个 整 数 a 和 b 满 足 （ a - b ） 能 够 被 m 整 除 ， 即 （ a - b ） / m 得 到 一 个 整 数 ， 那 么 就 称 整 数 a 与 b 对 模 m 同 余 ， 记 作 a ≡ b ( m o d   m ) 。 对 模 m 同 余 是 整 数 的 一 个 等 价 关 系 比 如 2 6 ≡ 1 4 ( m o d   1 2 ) 互 质 公 约 数 只 有 1 的 两 个 数 ， 称 为 互 质 p y t h o n   p o w ( )   函 数 R S A 工 具 工 具 R S A - T o o l   2 使 用 方 法 使 用 方 法 软 件 参 数 软 件 参 数 P =   第 一 个 大 素 数 Q =   第 二 个 大 素 数   ( P 和 Q 的 长 度 不 能 相 差 太 大 ！ ) E =   公 钥   ( 一 个 随 机 数 ， 必 须 满 足 ： G C D ( E , ( P - 1 ) * ( Q - 1 ) ) = = 1 ) ( 译 者 注 ： 即 E 和 ( p - 1 ) ( Q - 1 ) 互 素 ) N =   公 用 模 数 ， 由 P 和 Q 生 成 ： N = P * Q D =   私 钥 ： D = E ^ ( - 1 )   m o d   ( ( P - 1 ) * ( Q - 1 ) ) 参 数 N 和 E 是 公 开 的 但 是 D 是 私 有 的 并 且 绝 不 能 公 开 ！ P 和 Q 在 生 成 密 钥 后 便 不 再 需 要 了 ， 但 是 必 须 销 毁 。 为 了 从 公 钥 ( N , E ) 得 到 D , 需 要 试 图 分 解 N 为 它 的 两 个 素 数 因 子 。 对 于 一 个 很 大 的 模 数 N （ 5 1 2 位 或 更 大 ） 要 想 分 解 出 它 的 P 和 Q 是 件 非 常 困 难 的 事 。 生 成 一 组 生 成 一 组 R S A 密 钥 对 密 钥 对 按 下 ’ S t a r t ’ 按 钮 ， 通 过 移 动 你 的 鼠 标 指 针 来 收 集 一 些 随 机 数 据 . 这 必 须 一 次 完 成 ， 因 为 收 集 的 数 据 会 被 保 存 在 你 的 R S A - T o o l 文 件 夹 里 面 的 一 个 文 件 中 。   选 择 要 创 建 的 密 钥 的 长 度 ( 等 于 N 的 长 度 ) 。 最 大 为 4 0 9 6 位 .   选 择 你 的 公 钥 ( E ) 并 把 它 输 入 到 相 应 的 编 辑 框 作 为 十 进 制 数 。 常 用 的 E 有 （ 考 虑 到 计 算 速 度 的 原 因 ) : 3 , 1 7 , 2 5 7 和 6 5 5 3 7 ( 十 进 制 ) .   按 下 ’ G e n e r a t e ’ ， 等 到 密 钥 生 成 完 成 。 注 意 ， 生 成 很 大 的 数 需 要 一 些 时 间 ， 取 决 于 你 的 C P U 的 计 算 能 力 。 特 别 说 明 ： 你 可 以 常 按 ’ G e n e r a t e ’ . 做 为 密 钥 生 成 过 程 的 一 个 组 成 部 分 的 内 置 随 机 数 生 成 系 统 会 在 运 行 的 时 候 重 新 进 行 初 始 化 。 这 是 故 意 这 么 做 的 ， 这 样 可 使 那 些 滥 用 这 个 工 具 做 其 它 事 情 变 得 更 困 难 … 　 　   注 意 两 次 或 两 次 以 上 生 成 相 同
的 密 钥 对 是 不 可 能 的 。 分 解 一 个 数 分 解 一 个 数 选 择 正 确 的 进 制   在 M o d u l e s ( N ) 编 辑 框 中 输 入 或 复 制 这 个 数 。 这 会 激 活 ’ F a c t o r ’ 按 钮 。   然 后 按 F a c t o r 按 钮 . 注 意 分 解 大 于 2 4 0 位 的 数 会 花 很 大 的 内 存 和 时 间 ！ 甚 至 很 小 的 数 也 会 需 要 几 个 小 时 。 如 果 用 M u l t i p l e   P o l y n o m i a l   Q u a d r a t i c   S i e v e ( M P Q S ) 算 法 来 分 解 整 数 , 需 要 大 量 的 内 存 . 原 因 是 这 个 算 法 的 设 计 , 而 不 是 编 码 风 格 。 例 如 ： 分 解 一 个 给 定 大 小 的 N 的 内 存 使 用 情 况 ( 使 用 M P Q S 算 法 ) … 2 5 6 位 ~ 8 9 M B ,   2 8 0   位 ~ 1 4 0 M B ,   2 9 6 位 ~ 1 8 5 M B 等 等 . 由 素 数 因 子 由 素 数 因 子 P 和 和 Q 计 算 私 钥 计 算 私 钥 D 选 择 参 数 P 和 Q 的 正 确 进 制 ， 在 相 应 的 文 本 区 域 中 输 入 或 粘 贴 P 和 Q   按 下 ’ C a l c . D ’ ， 得 到 整 数 的 精 确 位 长 度 为 你 要 进 行 检 查 的 数 选 择 正 确 的 进 制   在 M o d u l e s ( N ) 文 本 框 中 输 入 或 粘 贴 整 数   按 小 的 ’ E x a c t   s i z e ’ 按 钮 . 会 显 示 出 这 个 数 使 用 的 精 确 的 位 数 m s i e v e 使 用 方 法 使 用 方 法 m s i e v e 是 一 个 大 数 分 解 工 具   下 载 地 址 m s i e v e . e x e   — h e l p   查 看 帮 助   l   f i l e n a m e   保 存 日 志 到 f i l e n a m e 文 件 中 ， 默 认 为 m s i e v e . l o g   i   f i l e n a m e   从 f i l e n a m e 文 件 中 读 取 数 字 ， 默 认 w o r k t o d o . i n i   o n e _ n u m b e r :   待 分 解 数 字 ， 0 开 头 代 表 8 进 制 ， 0 x 开 头 代 表 1 6 进 制 ， 否 则 为 1 0 进 制 。 如 不 填 ， 则 从 w o r k t o d o . i n i 中 读 取 数 字 。   - v   意 思 打 印 具 体 分 解 的 情 况   - q   仅 仅 打 印 能 找 到 的 因 子 各 自 运 行 结 果 如 下 ：
注 ： p r p 3 9   即 是 分 解 出 来 的 p , q 注 意 前 面 加 上 相 应 进 制 。 八 进 制 0   十 六 进 制 0 x   十 进 制 什 么 也 不 加 。 o p e n s s l 生 成 私 钥 ， 并 导 出 公 钥 生 成 2 0 4 8   b i t 的 P E M 格 式 的 R S A   K e y ： K e y . p e m
从 私 钥 导 出 公 钥 ： K e y _ p u b l i c . p e m 准 备 测 试 数 据 准 备 测 试 数 据 为 了 简 便 起 见 ， 这 里 将 字 符 串 ” h e l l o   r s a ” 存 放 到 文 件 m s g . t x t 作 为 测 试 数 据 ： 公 钥 加 密 公 钥 加 密 使 用 公 钥 k e y _ p u b l i c . p e m 对 测 试 数 据 m s g . t x t 进 行 加 密 生 成 m s g . t x t . e n c ， 并 查 看 加 密 后 的 数 据 ： 这 里 使 用 ： - i n   选 项 指 定 原 始 数 据 文 件 m s g . b i n   - o u t   选 项 指 定 加 密 后 的 输 出 文 件 m s g . b i n . e n c   - i n k e y   选 项 指 定 用 于 加 密 的 公 钥 K e y _ p u b . p e m ， 由 于 输 入 是 公 钥 ， 所 以 需 要 使 用 选 项 - p u b i n 来 指 出   - e n c r y p t   选 项 表 明 这 里 是 进 行 加 密 操 作   - p k c s   选 项 指 定 加 密 处 理 过 程 中 数 据 的 填 充 方 式 ， 对 于 填 充 ， 可 选 项 有 ： - p k c s ,   - o a e p ,   - s s l ,   - r a w ， 默 认 是 - p k c s ， 即 按 照 P K C S # 1   v 1 . 5 规 范 进 行 填 充 私 钥 解 密 私 钥 解 密 使 用 私 钥 k e y . p e m 对 加 密 后 的 数 据 m s g . t x t . e n c 进 行 解 密 ， 并 将 结 果 存 放 到 m s g . t x t . d e c 文 件 中 ： 这 里 使 用 ：
- i n   选 项 指 定 待 解 密 的 数 据 文 件 m s g . b i n . e n c   - o u t   选 项 指 定 解 密 后 的 输 出 文 件 m s g . b i n . d e c   - i n k e y   选 项 指 定 用 于 解 密 的 私 钥 K e y . p e m ， 由 于 输 入 是 私 钥 ， 所 以 不 再 需 要 使 用 选 项 - p u b i n   - d e c r y p t   选 项 表 明 这 里 是 进 行 解 密 操 作 - p k c s   选 项 指 定 解 密 处 理 过 程 中 数 据 的 填 充 方 式 ， 对 于 填 充 ， 可 选 项 有 ： - p k c s ,   - o a e p ,   - s s l ,   - r a w ， 默 认 是 - p k c s ， 即 按 照 P K C S # 1   v 1 . 5 规 范 进 行 填 充 y a f u 主 要 用 来 分 解 N ， 命 令 为 f a c t o r ( N ) 先 运 行 文 件 夹 下 的 y a f u - x 6 4 . e x e 进 入 命 令 行 执 行 f a c t o r ( N ) 执 行 过 程 ： （ 也 可 以 像 下 面 这 样 后 面 直 接 加 上 f a c t o r ( N ) ） m i s m a t c h e d   p a r e n s 报 错 这 是 因 为 N 的 位 数 过 长 ， 命 令 行 不 支 持 。 把 N 值 保 存 到 文 件 中 ， 如 r s a . t x t   ， 然 后 执 行 执 行 后 r s a . t x t 就 会 被 自 动 删 除 。 执 行 过 程 如 下 ：
e o f ;   d o n e   p r o c e s s i n g   b a t c h f i l e 报 错 r s a . t x t 用 n o t e p a d + + 打 开 ， 最 后 加 上 换 行 即 可 。 R S A 题 型 分 析 题 型 分 析 实 验 吧 实 验 吧 R S A 题 目 链 接 ： h t t p : / / w w w . s h i y a n b a r . c o m / c t f / 1 7 7 2 o p e n s s l 分 析 公 钥 ， 得 到 N , E 运 行 结 果
M o d u l u s   是 n 的 值 ， E x p o n e n t 是 E 的 值 。 m s i e v e 分 解 N 的 值 运 行 结 果
知 道 p ， q ， e 的 值 ， p y t h o n 脚 本 生 成 私 钥
注 ： 生 成 的 私 钥 会 默 认 b a s e 6 4 加 密 。 密 钥 解 密 密 文 R S A   r o l l 题 目 给 出 一 个 t x t 文 件 ， 内 容 如 下 ：
回复

举报

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

本版积分规则

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

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