本科生毕业论文（设计）

Transcription

1 中 南 大 学 本 科 生 毕 业 论 文 ( 设 计 ) 题 目 大 模 数 的 Rabin 密 码 保 密 通 信 软 件 学 生 姓 名 周 技 锋 指 导 教 师 杜 伟 王 国 才 学 院 信 息 科 学 与 工 程 学 院 专 业 班 级 通 信 工 程 0405 完 成 时 间 2008 年 5 月

2 目 录 摘 要... II ABSTRACT... III 第 一 章 绪 论 网 络 信 息 安 全 现 状 及 研 究 意 义 Rabin 公 钥 密 码 系 统 介 绍 Windows Sockets 网 络 通 信 介 绍 毕 业 设 计 课 题 描 述... 6 第 二 章 Rabin 密 码 系 统 的 设 计 与 实 现 需 求 分 析 与 总 体 设 计 功 能 分 析 方 案 选 择 与 总 体 设 计 功 能 模 块 的 设 计 与 实 现 大 数 的 表 示 方 式 幂 模 运 算 Miller-Rabin 素 性 检 测 的 实 现 扩 展 欧 几 里 德 算 法 的 实 现 Rabin 加 密 解 密 模 块 设 计 第 三 章 winsock 通 信 的 设 计 与 实 现 Winsock 基 本 概 念 Winsock 通 信 原 理 客 户 机 / 服 务 器 模 型 Winsock 控 件 编 程 参 数 使 用 说 明 Winscok 网 络 通 信 应 用 程 序 设 计 服 务 器 程 序 的 开 发 客 户 端 程 序 的 开 发...26 第 四 章 大 模 数 的 Rabin 密 码 保 密 通 信 软 件 的 实 现 功 能 模 块 设 计 界 面 设 计 第 五 章 总 结 全 文 总 结 与 展 望 心 得 体 会...35 致 谢 参 考 文 献 附 录 I

3 摘 要 随 着 计 算 机 科 学 技 术 及 网 络 通 信 技 术 的 飞 速 发 展 和 Internet 的 快 速 普 及, 计 算 机 网 络 的 应 用 已 遍 及 人 类 社 会 的 各 个 领 域 人 们 对 网 络 通 信 的 安 全 提 出 了 更 高 的 要 求 密 码 技 术 在 保 证 数 据 的 完 整 性 私 有 性 和 不 可 否 认 性 方 面 起 着 极 为 重 要 的 作 用, 在 网 络 通 信 安 全 领 域 占 据 特 别 重 要 的 地 位 Rabin 密 码 系 统 是 一 种 不 对 称 密 码 技 术, 它 的 安 全 性 如 RSA 一 样, 均 涉 及 到 因 数 分 解 的 问 题 Rabin 密 码 系 统 可 以 证 明 破 译 的 复 杂 性 等 同 于 因 子 分 解 问 题 本 文 对 Rabin 密 码 保 密 通 信 软 件 进 行 了 研 究 简 单 介 绍 了 信 息 安 全 技 术 现 状 及 研 究 意 义, 讨 论 了 公 钥 密 码 系 统 和 Rabin 密 码 系 统 及 其 涉 及 到 的 算 法, 包 括 大 整 数 的 实 现 蒙 格 马 利 快 速 幂 模 运 算 Miller-Rabin 素 性 检 测 法 扩 展 的 欧 几 里 德 算 法 着 重 讨 论 了 Rabin 密 码 系 统 的 方 案 设 计 以 及 Winsock 通 信 技 术 最 后 讲 解 了 Rabin 密 码 系 统 在 保 密 通 信 中 的 应 用, 初 步 完 成 了 大 模 数 Rabin 密 码 保 密 通 信 软 件 的 设 计 关 键 词 : 公 钥 密 码,Rabin 密 码 系 统,Winsock, 保 密 通 信 II

4 ABSTRACT With the rapid development of Computer Science and the populariza tion of Internet,the applica tions of computer network have come into lots of fields in huma n.society. and the efficiency of it has greatly improved.cryptographic technology pla ys a quite important role to ensure the integrity, confidentia lity and non-repud iation of data. The Rabin cryptosystem is an asymmetric cryptographic technique, whose security, like that of RSA, is related to the difficulty of factorization. However the Rabin cryptosystem has been proved to be as hard as integer factorization. This thesis described a research on safe server/client socket communication software using Rabin Cryptosystem,br iefed the status and significa nce of information technology security,discussed the public key cryptography and Rabin cryptosystem and its related algor ithms,including Montgomer y fast-computing,m iller-rabin prima lity testing,extend- Euclidea n algor ithm.focused on the design of Rabin cryptosystem and Winsock communication technology.fina lly expla ined the applica tion of Rabin cryptography in the confidentia l communications,prelimina ry completed Rabin cryptosystem confidentia l communications software design. KEY WORDS: communication public key cryptography,rabin cryptosystem,winsock,confidentia l III

5 第 一 章 绪 论 第 一 章 绪 论 1.1 网 络 信 息 安 全 现 状 及 研 究 意 义 由 于 电 子 信 息 电 信 等 基 础 科 学 的 突 飞 猛 进, 不 仅 造 就 新 兴 产 业 如 半 导 体 3C 产 业 等, 亦 协 助 了 传 统 产 业 的 改 头 换 面 这 种 以 信 息 技 术 为 中 心 的 技 术 革 命, 对 人 类 的 经 济 社 会 与 文 化 均 产 生 革 命 性 的 影 响 伴 随 着 网 际 网 络 的 蓬 勃 发 展, 建 构 网 络 安 全 环 境 亦 成 为 不 可 轻 忽 的 问 题 自 网 络 兴 起 后, 透 过 网 络 传 输 讯 息 的 行 为 愈 来 愈 频 繁, 因 此, 资 料 安 全 防 护 也 愈 来 愈 重 要 对 目 前 尚 未 进 行 安 全 防 护 机 制 的 网 络 架 构 而 言, 任 何 人 皆 可 以 轻 易 的 拦 截 在 网 络 上 传 输 的 资 料, 一 旦 通 信 过 程 中 的 信 息 被 不 法 使 用 者 窃 取, 轻 则 造 成 金 钱 损 失, 重 则 影 响 商 誉, 甚 至 危 及 国 家 安 全, 因 此, 信 息 安 全 用 于 保 护 网 络 上 流 通 信 息 是 相 当 重 要 的 其 实, 全 世 界 对 于 信 息 安 全 研 究 已 持 续 多 年, 密 码 学 家 莫 不 致 力 于 保 护 重 要 之 机 密 信 息 而 研 发 出 许 多 加 解 密 机 制 何 谓 信 息 安 全 [1]? 狭 义 来 说, 主 要 是 针 对 技 术 面 来 作 探 讨, 其 定 义 为 保 护 机 密 或 敏 感 资 料, 以 防 制 未 授 权 的 揭 露, 并 注 重 资 料 的 机 密 性 其 应 用 范 围 包 括 国 防 军 事 或 外 交 等 政 府 机 构 我 们 生 活 在 一 个 令 人 兴 奋 快 节 奏 的 世 界, 任 何 东 西 的 改 变 都 比 不 上 我 们 处 理 信 息 的 方 法 快 利 用 Internet, 我 们 可 以 利 用 一 些 以 前 想 都 想 不 到 的 方 式 来 访 问 和 使 用 信 息 不 用 去 银 行 或 在 取 款 机 前 排 队 等 候, 我 们 在 家 就 可 以 支 付 账 单 签 发 支 票 和 转 账, 而 且 是 每 周 7 天 每 天 24 小 时 都 可 以 不 用 出 家 门 就 可 以 申 请 和 接 收 贷 款 可 以 在 Internet 上 买 书 食 品 礼 物 以 及 其 他 任 何 东 西 不 用 周 末 去 跳 蚤 市 场, 通 过 网 络 就 可 以 在 任 何 时 间 卖 东 西 我 们 还 可 以 买 卖 股 票, 给 他 人 邮 寄 信 息 随 着 无 线 技 术 的 出 现, 我 们 用 手 机 在 全 球 任 意 地 方 都 可 以 完 成 所 有 以 上 事 情, 甚 至 不 止 这 些 诚 然, 这 些 都 是 令 人 兴 奋 的 事, 但 也 有 不 好 的 一 面 同 样 的 技 术 可 以 使 我 们 的 生 活 更 方 便, 但 若 被 罪 犯 利 用, 就 将 危 及 我 们 的 生 活 例 如, 在 当 今 的 美 国, 窃 取 身 份 证 是 增 长 最 快 的 犯 罪 之 一 它 之 所 以 盛 行, 是 因 为 法 律 惩 罚 没 有 跟 上 犯 罪 的 步 伐, 而 且 这 种 犯 罪 很 容 易 实 施 这 是 因 为 大 多 数 的 个 人 信 息 缺 乏 保 护 要 享 受 新 技 术 给 予 的 好 处, 避 免 陷 阱, 就 必 须 具 有 一 些 保 护 我 们 身 份 和 个 人 信 息 的 方 法 但 是, 任 何 关 于 加 密 法 的 讨 论 都 必 须 从 加 密 学 的 通 用 原 理 开 始, 也 就 是 说, 必 须 假 定 偷 听 者 具 有 加 密 数 据 所 使 用 的 算 法 知 识 这 就 意 味 着, 不 要 以 为 加 密 算 法 是 新 的 或 是 对 外 人 是 未 知 的, 数 据 永 远 都 是 不 安 全 的 只 有 加 密 算 法 的 密 钥 是 安 全 的 数 据 才 是 安 全 的 永 远 不 要 指 望 敌 人 不 明 白 你 的 数 据 的 加 密 原 理 应 总 是 假 定 他 们 1

6 第 一 章 绪 论 知 道 加 密 算 法 的 详 细 细 节 这 就 叫 作 Kerckhoffs 规 律 [2], 这 也 是 佛 兰 德 的 密 码 员 Auguste Kerckhoffs 在 他 19 世 纪 的 著 作 La Crypthographie Militaire 中 所 列 举 的 加 密 系 统 必 具 的 六 条 要 求 之 一 这 六 条 要 求 现 在 仍 认 为 是 所 有 加 密 算 法 的 基 础, 见 文 献 [3] (1) 加 密 系 统 在 实 际 中 应 是 不 可 破 解 的, 尽 管 不 是 理 论 上 不 可 破 解 的 (2) 破 解 加 密 系 统 应 不 会 打 扰 通 信 者 (3) 密 钥 应 无 须 做 记 录 即 可 记 住, 并 容 易 修 改 (4) 密 码 应 能 够 用 电 报 来 传 输 (5) 设 备 或 文 档 应 一 个 人 即 可 携 带 或 操 作 (6) 系 统 应 很 容 易 操 作, 无 须 掌 握 一 长 串 的 规 则 或 进 行 专 门 培 训 全 球 经 济 发 展 正 在 进 入 信 息 经 济 时 代, 知 识 经 济 初 见 端 倪 电 脑 信 息 的 保 密 问 题 显 得 越 来 越 重 要, 无 论 是 个 人 信 息 通 信 还 是 电 子 商 务 发 展, 都 迫 切 需 要 确 保 Internet 上 信 息 传 输 的 安 全, 需 要 确 保 信 息 安 全 信 息 安 全 技 术 是 一 门 综 合 学 科, 他 涉 及 信 息 论 电 脑 科 学 和 密 码 学 等 多 方 面 知 识, 他 的 主 要 任 务 是 研 究 电 脑 系 统 和 通 信 网 络 内 信 息 的 保 护 方 法 以 实 现 系 统 内 信 息 的 安 全 保 密 真 实 和 完 整 其 中, 信 息 安 全 的 核 心 是 密 码 技 术 密 码 技 术 是 集 数 学 电 脑 科 学 电 子 和 通 信 等 诸 多 学 科 于 一 身 的 交 叉 学 科 他 不 但 能 够 确 保 机 密 性 信 息 的 加 密, 而 且 能 够 实 现 数 字 签 名 身 份 验 证 系 统 安 全 等 功 能 是 现 代 化 发 展 的 重 要 科 学 之 一 本 文 将 重 点 介 绍 Rabin 公 开 密 钥 [4] 保 护 系 统 并 设 计 简 单 的 基 于 Rabin 密 码 保 密 通 信 软 件 1.2 Rabin 公 钥 密 码 系 统 介 绍 密 码 技 术 是 信 息 安 全 的 核 心 技 术 如 今, 计 算 机 网 络 环 境 下 信 息 的 保 密 性 完 整 性 可 用 性 和 抗 抵 赖 性, 都 需 要 采 用 密 码 技 术 来 解 决 密 码 体 制 大 体 分 为 对 称 密 码 ( 又 称 为 私 钥 密 码 ) 和 非 对 称 密 码 ( 又 称 为 公 钥 密 码 ) 两 种 公 钥 密 码 在 信 息 安 全 中 担 负 起 密 钥 协 商 数 字 签 名 消 息 认 证 等 重 要 角 色, 已 成 为 最 核 心 的 密 码 当 前, 公 钥 密 码 的 安 全 性 概 念 已 经 被 大 大 扩 展 了 像 著 名 的 RSA 公 钥 密 码 [5] 算 法 Rabin 公 钥 密 码 算 法 和 ElGamal 公 钥 密 码 算 法 都 已 经 得 到 了 广 泛 应 用 但 是, 有 些 公 钥 密 码 算 法 在 理 论 上 是 安 全 的, 可 是 在 具 体 的 实 际 应 用 中 并 非 安 全 因 为 在 实 际 应 用 中 不 仅 需 要 算 法 本 身 在 数 学 证 明 上 是 安 全 的, 同 时 也 需 要 算 法 在 实 际 应 用 中 也 是 安 全 的 比 如, 公 钥 加 密 算 法 根 据 不 同 的 应 用, 需 要 考 虑 选 择 明 文 安 全 非 适 应 性 选 择 密 文 安 全 和 适 应 性 选 择 密 码 安 全 三 类 数 字 签 名 根 据 需 要 也 要 求 考 虑 抵 抗 非 消 息 攻 击 和 选 择 消 息 攻 击 等 因 此, 近 年 来, 公 钥 密 码 学 研 究 中 的 一 个 重 要 内 容 可 证 安 全 密 码 学 正 是 致 力 于 这 方 面 的 研 究 用 抽 象 的 观 点 来 看, 公 钥 密 码 体 制 就 是 一 种 陷 门 单 向 函 数 [6] 我 们 说 一 个 函 数 f 2

7 第 一 章 绪 论 是 单 向 函 数, 若 对 它 的 定 义 域 中 的 任 意 x 都 易 于 计 算 f(x), 而 对 f 的 值 域 中 的 几 乎 所 有 的 y, 即 使 当 f 为 已 知 时 要 计 算 f -1 (y) 在 计 算 上 也 是 不 可 行 的 若 当 给 定 某 些 辅 助 信 息 ( 陷 门 信 息 ) 时 易 于 计 算 f -1 (y), 就 称 单 向 函 数 f 是 一 个 陷 门 单 向 函 数 公 钥 密 码 体 制 就 是 基 于 这 一 原 理 而 设 计 的, 将 辅 助 信 息 ( 陷 门 信 息 ) 作 为 秘 密 密 钥 这 类 密 码 的 安 全 强 度 取 决 于 它 所 依 据 的 问 题 的 计 算 复 杂 性, 见 文 献 [6] 安 全 的 公 开 密 钥 密 码 系 统, 可 以 达 到 下 列 功 能 : (1) 保 护 信 息 机 密 : 任 何 人 均 可 将 明 文 加 密 成 密 文, 此 后 只 有 拥 有 解 密 密 钥 的 人, 才 能 解 密 (2) 简 化 密 钥 分 配 及 管 理 问 题 : 网 络 上 的 每 个 人 只 需 要 一 把 加 密 公 开 ) 密 钥 及 一 把 解 密 ( 私 有 秘 密 ) 密 钥, 这 些 密 钥 只 要 由 接 收 方 自 己 产 生 即 可 除 拥 有 更 高 的 安 全 性 外, 更 大 大 简 化 密 钥 的 分 配 及 管 理 问 题 (3) 可 达 到 不 可 否 认 功 能 : 由 于 只 有 接 收 方 自 己 才 拥 有 解 密 密 钥, 若 他 先 用 解 密 密 钥 将 明 文 加 密 ( 签 名 ) 成 密 文 ( 签 名 文 ), 则 任 何 人 均 能 用 公 开 密 钥 将 密 文 解 密 ( 验 证 ) 成 明 文, 并 与 原 来 明 文 对 照 公 钥 密 码 的 原 理 就 是 基 于 单 向 陷 门 函 数, 加 密 是 容 易 的 方 向, 加 密 指 令 是 公 开 密 钥, 任 何 人 都 能 加 密 信 息 而 解 密 是 难 的 方 向, 它 设 计 得 非 常 困 难, 以 致 于 若 没 有 秘 密 信 息, 使 用 最 快 的 计 算 机 用 几 百 万 年 的 时 间 都 不 能 解 开 加 密 信 息 秘 密 信 息 即 陷 门 就 是 私 钥 假 设 A 和 B 是 通 信 的 双 方,E 是 窃 听 者 以 下 是 A 使 用 公 钥 密 码 发 送 信 息 给 B 的 过 程 (1)A 和 B 选 用 一 个 公 钥 密 码 系 统 (2)B 将 他 的 公 钥 传 送 给 A (3)A 用 B 的 公 钥 加 密 她 的 信 息, 然 后 传 送 给 B (4)B 用 他 的 私 钥 解 密 A 的 信 息 可 以 看 出 公 钥 密 码 是 通 过 密 钥 分 配 来 解 决 传 统 密 码 的 主 要 问 题 对 于 传 统 密 码, A 和 B 不 得 不 选 取 同 一 密 钥 :A 可 能 随 机 选 取 一 个, 但 她 不 得 不 把 选 取 的 密 钥 告 诉 B 她 可 能 事 先 交 给 B, 但 那 样 做 需 要 有 先 见 之 明 她 也 可 能 通 过 挂 号 信 将 它 寄 给 B, 但 那 样 做 要 花 费 时 间 对 公 钥 密 码 则 没 有 这 个 问 题, 不 用 事 先 安 排 A 就 能 把 信 息 安 全 地 发 送 给 B 在 整 个 交 换 中 一 直 在 窃 听 的 E, 虽 有 B 的 公 钥 和 用 公 钥 加 密 的 信 息, 但 却 恢 复 不 出 B 的 私 钥 或 者 是 传 送 的 信 息 更 一 般 地, 网 络 中 的 用 户 约 定 公 钥 密 码, 每 一 用 户 有 自 己 的 公 钥 和 私 钥, 并 且 在 其 他 地 方 的 数 据 库 都 是 公 开 的, 这 样 一 来 使 用 就 更 容 易 : (1) 从 数 据 库 中 得 到 B 的 公 钥 ; (2) 用 B 的 公 钥 加 密 信 息, 然 后 传 给 B; (3)B 用 自 己 的 私 钥 解 密 A 发 送 的 信 息 3

8 第 一 章 绪 论 自 从 1976 年 Diffie 和 Hellman 提 出 公 钥 密 码 的 观 点 之 后, 大 量 的 公 钥 密 码 被 陆 续 提 出 来, 如 RSA 公 钥 密 码 Merke-Hellman 背 包 公 钥 密 码 McEliece 公 钥 密 码 ElGamal 公 钥 密 码 和 椭 圆 曲 线 (EC) 公 钥 密 码 等, 所 有 这 些 公 钥 密 码 的 安 全 性 都 依 赖 于 数 学 问 题 的 难 解 性 公 开 密 钥 密 码 系 统 虽 具 有 许 多 优 点, 但 仍 有 其 缺 点 存 在 其 受 人 批 评 最 多 的 方 而, 即 在 于 加 解 密 运 算 复 杂, 且 速 度 缓 慢 前 面 介 绍 的 公 钥 密 码 共 有 的 性 质 是, 攻 破 它 们 同 解 一 个 公 认 的 计 算 上 难 解 的 问 题 诸 如 整 数 分 解 或 离 散 对 数 问 题 一 样 难 然 而, 就 如 同 RSA 公 钥 密 码 一 样, 虽 然 普 遍 确 信 攻 击 它 同 分 解 模 数 一 样 困 难, 但 两 者 之 间 的 等 价 性 一 直 未 能 得 到 证 明 Rabin 公 钥 加 密 算 法 [4,6] 由 Rabin 在 1979 年 提 出, 是 第 一 个 可 证 明 的 安 全 公 钥 密 码 算 法 继 1978 年 由 Rivest,Shamir 和 Adleman 提 出 RSA 公 钥 密 码 体 制 后,Rabin 对 RSA 提 出 一 种 巧 妙 修 改, 即 取 RSA 中 的 加 密 指 数 e=2 Rabin 密 码 是 建 立 在 求 mod n 平 方 根 算 法 的 理 论 基 础 上 的, 进 一 步 讲, 是 基 于 大 数 n 因 数 分 解 的 困 难 性 现 已 证 明, 破 译 Rabin 密 码 等 价 于 大 数 分 解 对 在 通 信 信 道 上 窃 取 信 息 的 被 动 敌 方 来 说, 要 从 某 个 已 知 的 密 文 中 恢 复 出 明 文, 所 面 临 的 问 题 等 价 于 因 数 分 解 Rabin 密 码 系 统 算 法 描 述 : 密 钥 的 产 生 : 接 收 者 B 任 选 两 大 素 数 p 及 q, 满 足 p,q 3(mod 4) 并 求 出 n=pq 公 钥 :n 秘 钥 :p 及 q 加 密 : 若 A 欲 传 送 明 文 m 给 B,0 m<n, 则 A 首 先 取 得 B 的 公 开 密 钥 n, 并 求 出 密 文 C= m 2 mod n A 将 密 文 C 传 送 给 B 解 密 :B 收 到 密 文 后, 求 出 M=C 1/2 mod n 四 个 平 方 根 m1,m2,m3 及 m4, 则 m 必 为 此 4 个 根 之 一 若 明 文 m 满 足 某 种 格 式 ( 如 增 加 预 指 定 的 冗 余 项 ), 则 由 格 式 可 判 定 此 4 个 根 何 者 为 真 正 明 文 Rabin 密 码 体 制 的 加 密 算 法 的 效 率 非 常 高, 所 以 很 适 合 某 些 特 定 的 应 用, 如 由 便 携 装 置 运 行 的 加 密 网 上 交 易 加 密 连 接 网 上 银 行 身 份 验 证 各 种 信 用 卡 使 用 的 数 字 证 书 智 能 移 动 电 话 和 存 储 卡 的 验 证 功 能 芯 片 等 1.3 Windows Sockets 网 络 通 信 介 绍 个 人 计 算 机 及 微 软 视 窗 已 经 非 常 普 遍, 加 上 利 用 计 算 机 网 络 的 种 种 好 处, 有 不 少 厂 商 在 这 样 的 环 境 下 开 发 一 些 给 使 用 者 使 用 的 软 件 ( 如 Telnet FTP News Mail 等 等 ) 或 是 提 供 网 络 发 展 环 境 给 使 用 者 来 开 发 其 网 络 软 件 但 是 早 期 发 展 时, 由 于 没 有 共 同 的 标 准 界 面, 所 以 各 家 厂 商 均 各 自 发 展 其 环 境 系 统 及 应 用 软 件 ; 使 用 者 在 购 买 了 这 样 的 一 套 系 统 之 后, 不 论 是 使 用 其 应 用 软 件 或 是 在 上 面 开 发 自 己 的 程 序 都 必 须 受 限 于 这 家 厂 商 了, 因 为 彼 此 的 系 统 开 发 工 具 (SDK,System Development Kid) 4

9 第 一 章 绪 论 的 应 用 程 序 界 面 (API, Application Interface) 并 不 相 同, 所 以 开 发 出 来 的 应 用 程 序 也 无 法 在 不 同 厂 商 的 系 统 上 执 行 ; 如 果 该 厂 商 没 有 进 一 步 提 供 技 术 支 援 发 展 新 的 软 件 或 是 连 络 不 便, 甚 或 不 幸 倒 闭 了, 那 将 是 一 件 很 令 人 头 痛 的 事 正 因 为 如 此, 于 是 由 各 公 司 组 成 的 一 群 有 志 之 士 ( 包 括 Microsoft Sun Microsystems HP Informix Novell 3Com 等 等 ) 开 始 着 手 于 整 合 定 义 出 一 套 微 软 视 窗 环 境 下 的 标 准 TCP/IP 网 络 开 发 界 面, 并 利 用 微 软 视 窗 环 境 下 动 态 连 结 程 序 库 (DLL, Dynamic Link Library) 的 特 性, 以 便 让 提 供 网 络 发 展 环 境 的 厂 商 及 开 发 网 络 应 用 程 序 的 公 司 能 够 各 自 分 开 发 展 而 彼 此 不 受 限 ; 换 句 话 说, 也 就 是 若 遵 循 此 一 标 准 界 面 所 开 发 出 来 的 网 络 软 件 应 该 可 以 在 各 家 不 同 的 环 境 上 执 行, 而 发 展 这 些 微 软 视 窗 下 TCP/IP 网 络 环 境 的 厂 商 亦 须 遵 照 此 一 标 准 提 供 符 合 这 些 界 面 的 各 项 函 式 功 能 ; 这 样 使 用 者 就 可 以 不 受 限 地 选 择 不 同 厂 商 的 软 件 或 是 在 不 同 家 的 系 统 环 境 上 执 行 同 一 个 自 己 开 发 的 网 络 软 件 了, 甚 至 不 必 再 经 过 修 改 编 译 等 烦 琐 的 程 序, 真 的 是 给 使 用 者 及 开 发 者 很 大 的 方 便 这 个 标 准 的 微 软 视 窗 TCP/IP 网 络 开 发 界 面 称 之 为 Windows Sockets [7] Windows Sockets 规 范 本 意 在 于 提 供 给 应 用 程 序 开 发 者 一 套 简 单 API(Application Programming Interface 应 用 编 程 接 口 ), 并 让 各 家 网 络 软 件 供 应 商 共 同 遵 守 此 外, 在 一 个 特 定 版 本 Windows 的 基 础 上,Windows Sockets 也 定 义 了 一 个 二 进 制 接 口 (ABI), 以 此 来 保 证 应 用 Windows Sockets API 的 应 用 程 序 能 够 在 任 何 网 络 软 件 供 应 商 的 符 合 Windows Sockets 协 议 的 实 现 上 工 作 因 此 这 份 规 范 定 义 了 应 用 程 序 开 发 者 能 够 使 用, 并 且 网 络 软 件 供 应 商 能 够 实 现 的 一 套 库 函 数 调 用 和 相 关 语 义 从 用 户 的 角 度 来 看, 实 际 上, 套 接 字 是 网 络 通 信 端 点 的 一 种 抽 象 概 念, 一 个 套 接 字 就 是 通 信 的 一 端, 它 为 用 户 提 供 了 一 种 发 送 和 接 收 数 据 的 机 制 其 中 应 用 程 序 告 诉 WinSock 执 行 什 么 任 务,WinSock 先 将 这 些 命 令 翻 译 成 其 与 TCP/IP 协 议 之 间 的 通 信 语 言, 再 和 TCP/IP 协 议 进 行 交 流, 最 终 由 TCP/IP 协 议 将 其 传 送 到 网 络 进 行 网 络 通 信 Windows Sockets 规 范 定 义 并 记 录 了 如 何 使 用 API 与 Internet 协 议 族 (IPS, 通 常 我 们 指 的 是 TCP/IP) 连 接, 尤 其 要 指 出 的 是 所 有 的 Windows Sockets 实 现 都 支 持 面 向 连 接 套 接 字 和 数 据 报 套 接 字 应 用 程 序 调 用 Windows Sockets 的 API 实 现 相 互 之 间 的 通 信 Windows Sockets 又 利 用 下 层 的 网 络 通 信 协 议 功 能 和 操 作 系 统 调 用 实 现 实 际 的 通 信 工 作 它 们 之 间 的 关 系 如 图 5

10 第 一 章 绪 论 图 1.1 应 用 程 序 与 Windows Sockects 关 系 图 1.4 毕 业 设 计 课 题 描 述 题 目 : 大 模 数 的 Rabin 密 码 软 件 要 求 : 设 计 一 个 模 数 达 到 2560 比 特 的 Rabin 密 码 系 统, 能 对 指 定 的 一 段 信 息 进 行 数 据 加 密, 并 能 用 Winsock 通 信 传 输 这 段 加 密 的 信 息 ; 接 收 后 能 够 解 密 (1) 模 数 的 选 择 程 序 ; (2) 加 密 程 序 ; (3) 解 密 程 序 ; (4)Winsock 通 信 本 文 在 第 一 章 绪 论 中 概 况 地 讲 述 了 网 络 信 息 安 全 技 术 的 现 状 及 研 究 的 意 义, 公 钥 密 码 系 统 等 相 关 技 术 的 研 究 现 状 及 其 应 用, 并 对 网 络 通 信 进 行 了 简 单 的 介 绍 第 二 章 详 细 介 绍 了 Rabin 密 码 系 统 加 密 解 密 实 现 过 程, 以 及 计 算 机 中 大 数 的 表 示 蒙 格 马 利 快 速 幂 模 运 算 Miller-Rabin 素 性 检 测 扩 展 欧 几 里 德 算 法 等 第 三 章 则 详 细 介 绍 了 Winsock 通 信 的 实 现, 首 先 Winsock 通 信 的 原 理 和 规 范, 接 着 描 述 了 客 户 端 / 服 务 器 模 型 及 各 编 程 参 数 的 使 用 说 明, 最 后 详 细 介 绍 了 Winsock 通 信 编 程 的 实 现 第 四 章 是 Rabin 密 码 保 密 通 信 软 件 的 实 现, 将 Rabin 密 码 系 统 和 Winsock 通 信 进 行 整 合, 并 对 软 件 界 面 进 行 了 介 绍 和 演 示 下 面 我 们 主 要 围 绕 密 码 学 和 网 络 通 信 两 个 方 面 来 展 开 本 课 题 的 讨 论, 逐 步 实 现 保 密 通 信 系 统 6

11 第 二 章 Rabin 密 码 系 统 的 设 计 与 实 现 第 二 章 Rabin 密 码 系 统 的 设 计 与 实 现 2.1 需 求 分 析 与 总 体 设 计 功 能 分 析 我 们 可 以 将 对 软 件 的 要 求 总 结 如 下 : 1 可 以 按 要 求 的 模 数 生 成 密 钥 与 公 钥 2 可 以 保 存 密 钥 和 装 载 密 钥 3 可 以 用 指 定 密 钥 以 Rabin 算 法 加 密 任 意 信 息 4 可 以 用 指 定 的 密 钥 解 密 密 文 还 原 出 明 文 5 提 示 信 息 完 整 操 作 舒 适 图 形 界 面 雅 观 根 据 以 上 分 析, 一 般 来 说, 需 要 进 行 编 码 的 程 序 有 :1Rabin 密 钥 生 成 2Rabin 加 密 解 密 3 各 环 节 必 要 的 数 据 编 码 转 换 4 图 形 操 作 界 面 方 案 选 择 与 总 体 设 计 1. Rabin 公 钥 加 密 算 法 一 (1) 密 钥 创 建 为 了 生 成 用 户 的 主 要 参 数, 用 户 Alice 执 行 以 下 步 骤 : 1 选 择 两 个 随 机 素 数 p 和 q; 2 计 算 N=pq; 3 随 机 选 择 一 个 整 数 b Z N ; 4 公 开 她 的 公 钥 (N,b), 把 (p,q) 作 为 她 的 私 钥 保 密 (2) 加 密 为 了 发 送 给 Alice 秘 密 消 息 m Z N, 发 送 者 Bob 按 下 面 的 方 式 生 成 密 文 C: C = E(M) = M(M+b) mod N 公 式 (2.1) (3) 解 密 为 了 解 密 密 文 c, Alice 对 m<n 求 解 二 次 方 程 M 2 +Mb-C 0 (mod N) 公 式 (2.2) 2. Rabin 公 钥 加 密 算 法 二 (1) 密 钥 创 建 Alice 如 下 生 成 一 个 公 钥 和 对 应 的 私 钥 : 1 生 成 两 个 大 的 ( 不 同 的 ) 素 数 pq,p 和 q 都 模 4 同 余 3 7

12 第 二 章 Rabin 密 码 系 统 的 设 计 与 实 现 2 计 算 N=pq 3Alice 的 公 钥 是 N, 私 钥 是 (p,q) 假 若 Bob 加 密 信 息 M 给 Alice,Alice 解 密, 则 加 解 密 过 程 如 下 : (2) 加 密 Bob 应 该 执 行 : 1 获 取 Alice 的 公 钥 N; 2 将 信 息 表 示 为 {0,1,,n-1} 的 整 数 m; 3 按 下 面 的 方 式 生 成 密 文 C C = E(M) = M 2 mod N 公 式 (2.3) 4 发 送 密 文 c 给 Alice (3) 解 密 为 从 c 中 恢 复 出 明 文 M, 求 出 M 2 =C mod N 公 式 (2.4) 从 以 上 可 以 看 出, 算 法 二 是 算 法 一 的 一 种 的 特 殊 情 况 (b=0), 很 显 然 算 法 二 的 加 密 解 密 运 算 过 程 要 简 单 在 这 里 我 们 选 用 算 法 二 来 实 现, 见 文 献 [8] 解 密 运 算 包 括 求 模 N 的 平 方 根 运 算, 我 们 知 道 求 平 方 根 问 题 的 困 难 性 等 价 于 分 解 N 的 困 难 性 由 于 只 有 Alice 知 道 N 的 分 解, 所 以 只 有 她 能 够 计 算 解 密 方 程 我 们 注 意 到 如 果 N 是 所 谓 的 Blum 整 数 [6], 即 N=pq, 其 中 P q 3(mnd 4), 则 计 算 模 N 的 平 方 根 就 很 容 易 所 以, 实 际 上 Rabin 密 码 体 制 中 的 公 开 模 数 都 选 用 Blum 整 数 求 解 : M=C 1/2 mod N 解 法 1: 1 利 用 扩 展 的 Euclidean 算 法 [9] 寻 找 整 数 a 和 b 满 足 ap+bq=1 2 计 算 r=c (p+1)/4 mod p 公 式 (2.5) s=c (q+1)/4 mod q 公 式 (2.6) x=(aps+bqr)mod N 公 式 (2.7) y=(aps+bqr)mod N 公 式 (2.8) 3C 模 N 的 四 个 平 方 根 m1,m2,m3,m4 分 别 为 x,-xmod n,y,-ymod n 解 法 2: 基 于 混 合 基 数 转 换 (MRC) 的 Rabin 解 密 算 法 [10] ( p 1)/ 4 ( q 1) / 4 1 计 算 x C mod p, x p, x C mod q, x q ; 1 2 x1 1 2 计 算 t p mod q; 3 计 算 3 4 x3 8

13 第 二 章 Rabin 密 码 系 统 的 设 计 与 实 现 m1 x1 [( x3 x1 ) t mod q] p m2 x1 [( x4 x1 ) t mod q] p 公 式 (2.9) m3 x2 [( x3 x2) t mod q] p m4 x1 [( x4 x2 ) t mod q] p 对 于 合 法 的 接 收 者 而 言, 由 于 p 和 q 是 已 知 的, 因 此 无 论 解 法 1 还 是 解 法 法 2 中 都 可 以 预 先 利 用 扩 展 Euclidean 算 法 计 算 出 尽 管 解 法 2 中 的 步 骤 3 比 解 法 1 的 多 四 次 乘 法 运 算, 但 是 由 于 p, q, t<<n, 使 得 解 法 2 的 步 骤 3 中 乘 法 与 取 模 计 算 量 大 大 减 小, 因 此 解 法 2 在 计 算 速 度 上 还 是 明 显 优 于 解 法 1 的 但 是 现 在 的 计 算 机 的 处 理 速 度 已 经 相 当 快 了, 为 了 便 于 实 现, 减 少 开 发 周 期, 我 们 选 择 解 法 一 来 设 计, 见 文 献 [6] 例 :Rabin 密 码 算 法 实 体 A 选 择 素 数 p=277.q=331 计 算 n=pq=91687,a 的 公 钥 是 n=91687,a 的 私 钥 是 (p=277,q=331) 假 设 在 加 密 之 前 需 要 复 制 原 信 息 的 后 6bit, 为 加 密 10bit 信 息 m= , B 复 制 m 的 后 6bit 得 到 16bit 信 息 M= , 用 十 进 制 数 字 表 示 是 m=40569 B 计 算 c=m 2 mod n= mod91687=62111 并 发 送 给 A 为 解 密 c,a 计 算 c mod n 的 四 个 平 方 根 : M 1 =69654,M 2 =22033,M 3 =40569,M 4 =51118 二 进 制 表 示 为 M 1 = M 2 = M 3 = M 4 = 四 个 数 中 只 有 M 3 有 所 需 的 多 余 度, A 解 密 c 为 M 3, 并 恢 复 出 原 来 的 信 息 m= Rabin 密 码 系 统 流 程 图 如 图 2.1 9

14 第 二 章 Rabin 密 码 系 统 的 设 计 与 实 现 图 2.1 Rabin 密 码 系 统 流 程 图 2.2 功 能 模 块 的 设 计 与 实 现 大 数 的 表 示 方 式 由 于 安 全 需 要, 目 前 主 流 的 Rabin 加 密 算 法 都 是 基 于 2 进 制 的 512 位 或 1024 位 的 大 整 数, 而 目 前 的 主 流 高 级 语 言 编 译 器 最 多 也 只 能 支 持 到 2 进 制 64 位 整 数, 所 以 大 整 数 的 存 储 和 运 算 对 于 Rabin 算 法 的 实 现 都 是 至 关 重 要 的 一 个 最 容 易 理 解 的 方 法 就 是 将 大 数 用 十 进 制 表 示, 并 将 每 一 位 (0 9) 都 做 为 一 个 单 独 的 数 用 数 组 进 行 管 理, 见 文 献 [11] 做 加 减 乘 除 等 运 算 时, 人 工 的 对 其 进 行 进 借 位 然 而 计 算 机 对 于 10 进 制 数 的 处 理 并 不 在 行, 而 且 表 示 非 2 n 进 制 的 数 会 浪 费 很 多 空 间, 所 以 应 该 采 用 8 进 制 16 进 制 32 进 制 64 进 制 的 表 示 法, 使 得 每 一 位 数 字 都 能 占 据 一 个 完 整 的 内 存 空 间 目 前 绝 大 多 数 PC 机 都 是 基 于 32 位 运 算 的, 所 以 采 用 2 32 进 制 表 示 大 数 将 会 很 大 提 高 计 算 机 的 处 理 效 率 现 实 中, 就 使 用 32 位 的 整 数 数 组 进 行 存 储 每 一 位 数, 另 设 一 个 布 尔 值 表 示 正 负 进 行 计 算 时 常 会 遇 到 进 位 借 位 的 情 况, 而 且 常 常 会 超 过 2 32 次 方, 幸 好 目 前 的 编 译 器 都 支 持 64 位 整 数, 可 以 满 足 ( ) * ( ) 以 内 的 运 算, 所 以 使 用 64 位 整 数 作 为 运 算 中 间 量 将 会 是 很 好 的 选 择 10

15 第 二 章 Rabin 密 码 系 统 的 设 计 与 实 现 大 数 除 了 加 减 乘 除 等 基 本 运 算 以 外, 还 有 一 些 如 赋 值 比 较 左 右 移 位 或 与 等, 为 了 方 便 使 用, 我 们 可 以 利 用 面 向 对 象 的 方 法 把 大 数 进 行 封 装, 并 利 用 C++ 的 特 性 进 行 运 算 符 重 载, 使 它 成 为 一 个 整 体 对 象 来 进 行 操 作 这 样 我 们 就 可 像 使 用 int 一 样 来 使 用 它 了 当 然, 大 数 类 的 实 现 并 不 是 一 篇 文 章 就 可 以 叙 述 完 的, 而 且 目 前 有 一 些 很 成 熟 并 且 开 源 的 大 数 类 库, 如 GTK NTL HugeCalc 等, 因 此 在 这 里 就 不 对 具 体 的 算 法 做 进 一 步 阐 释 了 我 们 可 以 定 义 使 用 比 较 成 熟 的 CBigNumber 的 大 数 运 算 类, 可 以 把 CBigNumber 的 头 文 件 和 实 现 函 数 加 入 工 程, 然 后 定 义 该 类 的 实 例, 就 可 以 对 这 些 实 例 进 行 加 减 乘 除 了 最 先 完 成 的 功 能 是 大 数 的 存 储, 存 储 功 能 由 CBigNumber 类 提 供 和 普 通 的 类 型 一 样, 每 一 个 大 数 对 应 一 个 CBigNumber 的 实 例 类 CBigNumber 中, 用 一 个 无 符 号 整 数 指 针 unsigned * a 指 向 一 块 内 存 空 间 的 首 地 址, 这 块 内 存 空 间 用 来 存 储 一 个 大 数, 如 图 2.2 所 以 可 以 说, 大 数 是 被 存 储 在 一 个 以 unsigned 为 单 元 的 线 性 组 中 在 方 法 void reserve( unsigned x ) 中 通 过 C++ 的 new 来 给 a 开 辟 空 间, 当 CBigNumber 的 实 例 中 被 存 入 比 当 前 存 储 的 数 更 大 的 数 时, 就 会 调 用 reserve 来 增 加 存 储 空 间, 但 是 当 CBigNumber 的 实 例 中 被 存 入 比 当 前 存 储 的 数 更 小 的 数 时, 存 储 空 间 并 不 会 自 动 紧 缩, 这 是 为 了 在 运 算 的 时 候 提 高 执 行 效 率 结 合 指 针 a, 有 两 个 重 要 的 无 符 号 整 数 来 控 制 存 储,unsigned z 和 unsigned n,z 是 被 分 配 空 间 的 单 元 数, 随 数 字 变 大 不 断 增 大, 不 会 自 己 紧 缩, 而 n 是 当 前 存 储 的 大 数 所 占 的 单 元 数, 组 成 一 个 大 数 的 各 unsigned 单 元 的 存 入 和 读 出 由 set get 方 法 完 成, 变 量 n 是 只 读 的 类 型 unsigned 在 32 位 机 是 32 位 的, 所 以 对 于 CBigNumber 这 个 大 数 类 来 说, 每 个 大 数 最 大 可 以 达 到 个 字 节 长, 这 已 经 超 过 了 32 位 机 通 常 的 最 大 内 存 容 量, 所 以 是 足 够 进 行 Rabin 所 需 要 的 各 种 运 算 的 图 2.2 CBigNumber 对 大 数 的 管 理 11

16 第 二 章 Rabin 密 码 系 统 的 设 计 与 实 现 幂 模 运 算 幂 模 运 算 是 Rabin 算 法 中 的 关 键, 无 论 是 素 数 测 试, 还 是 加 密 解 密, 都 要 用 到 幂 模 运 算 简 单 的 讲, 幂 模 运 算 就 是 计 算 N R mod D 的 值 但 是 对 于 计 算 机 来 讲, 计 算 R 很 大 的 N R 的 值 时 将 会 非 常 浪 费 存 储 空 间, 并 使 计 算 变 的 非 常 缓 慢 而 难 以 实 现 但 是 我 们 通 过 上 文 讨 论 的 积 模 分 解 公 式, 可 以 发 现 N R mod D 是 可 以 进 行 转 换 的 针 对 快 速 幂 模 运 算 这 一 课 题, 西 方 现 代 数 学 家 提 出 了 很 多 的 解 决 方 案 经 查 阅 相 关 数 学 著 作, 发 现 通 常 都 是 依 据 乘 模 的 性 质 先 将 幂 模 运 算 化 简 为 乘 模 运 算 ( a b) mod n ((a mod n ) (b mod n)) mod n 公 式 (2.10) 常 的 分 解 习 惯 是 指 数 不 断 的 对 半 分, 如 果 指 数 是 奇 数, 就 先 减 去 一 变 成 偶 数, 然 后 再 对 半 分, 例 如 求 D=,E=15, 可 分 解 为 如 下 6 个 乘 模 运 算 C E mod n 比 如 说 计 算 A 13 2 C1 C C mod n C mod n 3 C2 C1 C mod n C mod n C3 C 2 C2 mod n 6 C mod n 7 C4 C3 C mod n C mod n C5 C4 C 4 mod n C C6 C5 C mod n C mod n mod n 时, 如 果 让 A 直 接 进 行 连 乘, 需 要 12 次 运 算 但 是 如 果 把 A * A 的 值 保 存 起 来, 我 们 就 只 需 要 进 行 B=A*A 和 B*B*B*B*B*B*A, 一 共 七 次 运 算, 如 果 我 们 再 把 B*B 的 值 保 存 起 来, 那 我 们 就 只 需 要 进 行 B=A*A C=B*B D=C*C D*C*A, 一 共 五 次 运 算 总 结 这 个 规 律 可 以 发 现, 运 算 过 程 中 如 果 某 次 的 幂 数 为 奇 数 时, 在 乘 方 过 后 还 需 要 乘 以 上 次 保 留 的 积 幂 模 运 算 中 有 一 种 蒙 格 马 利 算 法, 运 算 效 果 相 当 不 错 蒙 格 马 利 算 法 [12] 描 述 计 算 N 的 E 次 方 再 取 D 的 模 N E mod D, 令 R 为 计 算 结 果 R:=1 A:=N B:=E WHILE Z!=0 IF B&1; 判 断 是 否 为 奇 数 12

17 第 二 章 Rabin 密 码 系 统 的 设 计 与 实 现 B:=B-1 R:=R*A X:=X%D ELSE B:=B/2 A:=A*A A:=A%D END IF NEXT 蒙 格 马 利 快 速 幂 模 运 算, 是 目 前 世 界 上 效 率 最 高 的 幂 模 运 算, 很 多 硬 件 芯 片 在 处 理 类 似 算 法 时 都 采 用 的 这 种 方 法 Miller-Rabin 素 性 检 测 的 实 现 首 先 要 说 明 的 是, 事 实 上, 当 今 的 计 算 机 还 不 足 以 聪 明 到 立 刻 计 算 生 成 一 个 很 大 的 随 机 素 数 一 般 来 说, 要 得 到 100% 准 确 的 大 素 数, 都 是 通 过 查 已 经 计 算 好 的 素 数 表 的 方 式 但 是 素 数 表 的 方 式 给 Rabin 的 安 全 性 带 来 隐 患, 因 为 攻 击 者 如 果 得 到 了 密 钥 生 成 时 所 使 用 的 素 数 表, 攻 破 Rabin 加 密 的 难 度 将 会 大 大 降 低 当 前 产 生 确 定 位 数 的 大 素 数 方 法 有 两 种 : (1) 利 用 较 小 的 素 数, 通 过 迭 代 方 法 产 生 ;(2) 先 产 生 一 个 大 随 机 奇 数, 然 后 利 用 随 机 多 项 式 时 间 素 性 测 试 算 法 对 其 进 行 测 试, 通 过 测 试 为 素 数 ; 否 则 重 新 生 成 大 奇 数 再 测 试, 直 到 产 生 素 数 为 止 在 实 际 中 常 采 用 后 一 种 方 法, 而 且 是 利 用 偏 是 的 [13] (Yes-biased) Monte Carlo 素 性 测 试 算 法 进 行 素 性 测 试 所 谓 偏 是 的 Monte Carlo 素 性 测 试 算 法 是 具 有 下 列 性 质 的 概 率 算 法 : 利 用 某 个 随 机 数, 对 于 输 入 的 大 奇 数 N, 仅 输 出 Yes 或 No 两 个 状 态 当 输 出 为 Yes 时, 则 N 必 为 合 数 ; 当 输 出 为 No 时,N 可 能 为 素 数, 也 存 在 将 合 数 N 错 误 地 判 断 为 素 数 的 情 况, 但 出 现 这 种 错 判 的 概 率 至 多 为 ε(ε 是 一 个 小 正 数 ) 常 见 的 Monte Carlo 素 性 测 试 算 法 有 Lehmann 测 试 算 法 和 Miller-Rabin 测 试 算 法 [6,13] 等 Miller-Rabin 算 法 是 典 型 的 验 证 一 个 数 字 是 否 为 素 数 的 方 法 判 断 素 数 的 方 法 是 Miller-Rabin 概 率 测 试, 那 么 他 具 体 的 流 程 是 什 么 呢 假 设 我 们 要 判 断 n 是 不 是 素 数, 首 先 我 们 必 须 保 证 n 是 个 奇 数, 那 么 我 们 就 可 以 把 n 表 示 为 n=(2^r)*s+1, 注 意 s 也 必 须 是 一 个 奇 数 然 后 我 们 就 要 选 择 一 个 随 机 的 整 数 a(1<=a<=n-1), 接 下 来 我 们 就 是 要 判 断 a^s=1(mod n) 或 a^((2^j)*s)=-1(mod n)(0<=j 如 果 任 意 一 式 成 立, 我 们 就 说 n 通 过 了 测 试, 但 是 有 可 能 不 是 素 数 也 能 通 过 测 试 所 以 我 们 通 常 要 做 多 次 这 样 的 测 试, 以 确 保 我 们 得 到 的 是 一 个 素 数 (DDS 的 标 准 是 要 经 过 50 次 测 试 ) 13

18 第 二 章 Rabin 密 码 系 统 的 设 计 与 实 现 Miller-Rabin 算 法 的 理 论 基 础 : 令 n-1=2 s m, 其 中 s 是 非 负 整 数,m 是 正 奇 数 若 b m 1 (mod n) 或 b 2jm -1 (mod n),0 j s-1, 则 称 n 通 过 以 b 为 基 的 米 勒 测 试 定 理 2.1 若 n 是 素 数,b 是 整 数, 且 n 不 能 整 除 b, 则 n 必 然 通 过 以 b 为 基 的 米 勒 测 试 定 理 2.2 若 n 是 奇 合 数, 则 n 通 过 以 b 为 基 的 米 勒 测 试 的 数 目 最 多 为 (n-1)/4,1 b n-1 基 于 上 述 两 个 定 理, 若 n 是 正 整 数, 选 k 个 小 于 n 的 正 整 数, 以 这 k 个 数 作 为 基 进 行 米 勒 测 试 若 n 是 合 数,k 次 测 试 通 过 的 概 率 为 (1/4) k 比 如 k=100,n 是 合 数, 测 试 全 部 通 过 的 概 率 为 (1/4) 100 =6.22*10-61, 几 乎 不 可 能 发 生 米 勒 测 试 思 想 如 下 Miller-Rabin(n,t) 输 入 : 一 个 大 于 3 的 奇 整 数 n 和 一 个 大 于 等 于 1 的 安 全 参 数 t( 用 于 确 定 测 试 轮 数 ) 输 出 : 返 回 n 是 否 是 素 数 ( 概 率 意 义 上 的, 一 般 误 判 概 率 小 于 (1/2) 80 即 可 ) 已 知 n-1=2 s m S1 在 {1,2, n-1} 中 均 匀 的 产 生 一 数 b;jß0, 计 算 zßb m mod n 若 z=1 或 n-1, 则 n 通 过 测 试, 结 束 S2 若 j=s 则 n 非 负 数, 结 束, 否 则 转 S3 S3 jßj+1,zßz 2 mod n 若 z=-1, 则 n 通 过 测 试, 结 束, 否 则 转 S2. 详 细 步 骤 如 下 S1 在 {1,2, n-1} 中 均 匀 的 产 生 一 数 b,2 b<n-1; 计 算 Vßb m mod n S2 若 V=1 则 转 S7 S3 iß1 S4 若 V=n-s 则 转 S7 S5 若 i=s, 则 n 非 素 数, 结 束, S6 VßV 2 mod n,ißi+1, 转 S4 S7 n 通 过 测 试 对 于 任 何 奇 合 数 n,miller-rabin(n,t) 表 明 n 是 素 数 的 概 率 小 于 (1/4) t 扩 展 欧 几 里 德 算 法 的 实 现 1. 欧 几 里 德 算 法 欧 几 里 德 算 法 [12] 是 用 来 计 算 最 大 公 约 数 的 快 速 算 法, 在 我 国 又 称 辗 转 相 除 法, 具 有 悠 久 的 历 史 整 数 a,b 的 最 大 公 约 数 用 gcd(a,b) 表 示 gcd(a,b)=max[c,c a 且 c b] 14

19 第 二 章 Rabin 密 码 系 统 的 设 计 与 实 现 定 理 :gcd(a,b) = gcd(b,a mod b) 证 明 :a 可 以 表 示 成 a=kb+r, 则 r=a mod b, 假 设 d 是 a,b 的 一 个 公 约 数, 则 有 d a, d b, 而 r=a-kb, 因 此 d r, 因 此 d 是 (b,a mod b) 的 公 约 数 假 设 d 是 (b,a mod b) 的 公 约 数, 则 d b,d r, 但 是 a=kb+r, 因 此 d 也 是 (a,b) 的 公 约 数 因 此 (a,b) 和 (b,a mod b) 的 公 约 数 是 一 样 的, 其 最 大 公 约 数 也 必 然 相 等, 得 证 欧 几 里 德 算 法 描 述 : S1 d=a%b S2 如 果 d=0 返 回 b( 即 为 最 大 公 因 数 ) 否 则 a=b;b=d; 返 回 S1 实 现 这 个 算 法 需 要 保 存 每 一 步 带 余 除 法 的 运 算 数 据, 内 存 开 销 比 较 大, 在 编 程 实 现 时 候 并 不 直 接 采 用 这 个 算 法 2. 扩 展 欧 几 里 德 算 法 对 欧 几 里 德 算 法 进 行 扩 展 不 仅 可 以 计 算 gcd(a,b), 如 果 a b 互 素, 还 可 以 求 a 模 b 的 逆 元 算 法 原 理 : 存 在 整 数 p 和 q 使 得 gcd(a,b)=p a+q b=1 (p a+q b)mod b=1 (p a)mod b=1 pa 1 mod b 显 然,p 是 a 模 b 的 一 个 逆 元 扩 展 欧 几 里 德 算 法 描 述 : S1 x0=0,y0=1;x1=1,y0=0,c=a,d=b S2 q<-c/d r<-c%d S3 if r=0 return else E4 S4 x=x0-q*x1 x0=x1;x1=x y=y0-q*y1 y0=y1;y1=y 15

20 第 二 章 Rabin 密 码 系 统 的 设 计 与 实 现 Rabin 加 密 解 密 模 块 设 计 到 现 在,Rabin 算 法 中 所 涉 及 到 的 所 有 算 法 我 们 都 已 经 讨 论 过 了, 下 面 对 Rabin 密 码 系 统 的 设 计 就 变 得 非 常 简 单 了 1. 密 钥 的 生 成 Generate_prime(CBigNumber p,int size) 1 随 机 生 成 一 个 指 定 位 长 的 数 字 p; 2 设 置 最 高 位 和 最 低 位 为 1( 最 高 位 为 1 确 保 素 数 达 到 要 求 的 位 数, 最 低 位 为 1 确 保 它 是 奇 数 ) 3 检 查 确 定 p 不 能 被 小 素 数 {3,5,7,11,13,17,19,23,29,31,37} 整 除 ; 4 对 p 做 5 次 Miller-Rabin 素 性 检 测, 若 不 是 素 数, 返 回 1; 5 检 查 p 是 否 模 4 余 三, 否 则 返 回 1; 6 返 回 p 按 照 上 面 的 方 法, 我 们 可 以 生 成 规 定 位 长 的 私 钥 p 和 q, 计 算 公 钥 N=pq 大 素 数 产 生 主 要 涉 及 三 个 函 数 :1 随 机 数 产 生 ;2. 筛 值 ;3.Miller-Rabin 素 数 检 测, 其 具 体 实 现 参 见 附 录 在 Visual C++6.0 中 编 译 执 行 Rabin 算 法 的 系 统 级 模 型, 可 以 看 到 产 生 大 素 数 的 结 果, 产 生 的 两 个 大 素 数 p 和 q 的 值 ( 模 数 取 1024) 如 下 : p= q= n= Rabin 算 法 的 安 全 性 基 于 大 素 数 难 于 分 解 的 这 个 事 实 的 因 此 在 应 用 Rabin 算 法 进 行 加 密 和 解 密 时 候,p 和 q 应 该 保 密, 在 这 里 为 了 说 明, 把 p 和 q 的 结 果 作 为 输 出 的 一 部 分, 特 在 此 说 明 2. 加 密 算 法 首 先 需 将 明 文 数 字 化, 取 长 度 小 于 log2n 位 的 数 字 作 为 明 文 块, 见 文 献 [14] 对 于 明 文 块 M 加 密 :C=M 2 mod N,Rabin 的 加 密 算 法 很 迅 速 很 简 单 在 这 里 我 们 可 以 在 明 文 M 的 后 面 加 16bit 的 0 作 为 冗 余 信 息, 以 便 在 解 密 的 时 候 能 够 从 四 个 根 中 判 断 出 哪 一 个 才 是 真 正 的 根 16

21 第 二 章 Rabin 密 码 系 统 的 设 计 与 实 现 3. 解 密 算 法 解 密 就 是 对 M=C 1/2 mod N 求 解 M 的 四 个 根 1 利 用 扩 展 的 Euclidean 算 法 寻 找 整 数 a 和 b 满 足 ap+bq=1 公 式 (2.11) 2 利 用 蒙 格 马 利 快 速 幂 模 运 算 计 算 r=c (p+1)/4 mod p 公 式 (2.12) s=c (q+1)/4 mod q 公 式 (2.13) 3 将 所 计 算 的 r 和 s 的 值 代 入 下 面 式 子 中 : x=(aps+bqr)mod N 公 式 (2.14) y=(aps+bqr)mod N 公 式 (2.15) 4C 模 N 的 四 个 平 方 根 m1,m2,m3,m4 分 别 为 x,-xmod n,y,-ymod n 在 这 里 我 们 还 不 能 确 定 哪 个 才 是 真 正 的 根 对 比 4 个 根 的 后 16bit 的 信 息, 找 出 有 冗 余 度 的 根 即 为 真 实 的 根 17

22 第 三 章 Winsock 通 信 的 设 计 与 实 现 第 三 章 winsock 通 信 的 设 计 与 实 现 3.1 Winsock 基 本 概 念 网 络 通 信 是 采 用 网 络 协 议 实 现 计 算 机 之 间 的 数 据 交 换 所 谓 网 络 协 议 是 指 通 信 双 方 约 定 好 的 规 则 集 合, 一 般 使 用 TCP/IP 协 议 Socket [15] 最 初 是 在 80 年 代 初, 美 国 加 利 福 尼 亚 大 学 伯 克 利 分 校 在 美 国 政 府 的 资 助 的 在 UNIX 操 作 系 统 下 实 现 TCP/IP 协 议 这 一 项 目 中, 为 TCP/IP 网 络 通 信 开 发 的 一 个 API, 称 为 Socket 接 口, 今 天,Socket 接 口 是 TCP/IP 网 络 最 为 通 用 的 API, 也 是 在 Internet 上 进 行 应 用 开 发 最 为 通 用 的 API Winsock 通 信 原 理 通 信 的 基 石 是 套 接 字 (Sockets), 一 个 套 接 字 是 通 信 的 一 端 在 这 一 端 上 你 可 以 找 到 与 其 对 应 的 一 个 名 字 一 个 正 在 被 使 用 的 套 接 字 都 有 它 的 类 型 和 与 其 相 关 的 进 程 套 接 字 存 在 于 通 信 域 中 通 信 域 是 为 了 处 理 一 般 的 线 程 通 过 套 接 字 通 信 而 引 进 的 一 种 抽 象 概 念 套 接 字 通 常 和 同 一 个 域 中 的 套 接 字 交 换 数 据 ( 数 据 交 换 也 可 能 穿 越 域 的 界 限, 但 这 时 一 定 要 执 行 某 种 解 释 程 序 ) Windows Sockets 规 范 支 持 单 一 的 通 信 域, 即 Internet 域 各 种 进 程 使 用 这 个 域 互 相 之 间 用 Internet 协 议 族 来 进 行 通 信 (Windows Sockets 1.1 以 上 的 版 本 支 持 其 他 的 域, 例 如 Windows Sockets 2) 套 接 字 是 应 用 程 序 通 信 的 基 石, 是 支 持 TCP/IP 协 议 的 网 络 通 信 应 用 的 基 本 操 作 单 元 可 以 将 套 接 字 看 作 是 不 同 主 机 间 的 进 程 进 行 双 向 通 信 的 端 点 : 网 络 中 两 台 通 信 的 主 机 各 自 在 自 己 机 器 上 建 立 通 信 的 端 点 套 接 字, 然 后 使 用 套 接 字 进 行 数 据 通 信 一 个 套 接 字 是 如 下 描 述 的 一 个 结 构 : { 协 议, 本 地 地 址, 本 地 端 口, 远 程 地 址, 远 程 端 口 } 操 作 系 统 会 为 本 地 建 立 的 套 接 字 分 配 一 个 唯 一 的 套 接 字 标 识 号, 应 用 程 序 按 该 标 识 号 来 使 用 套 接 字 进 行 网 络 通 信 根 据 网 络 通 信 的 特 征, 套 接 字 主 要 分 为 两 类 : 面 向 连 接 套 接 字 和 数 据 报 套 接 字 面 向 连 接 套 接 字 是 面 向 连 接 的, 它 提 供 双 向 的 有 序 的 无 差 错 无 重 复 并 且 无 记 录 边 界 的 数 据 流 服 务, 适 用 于 处 理 大 量 数 据, 提 供 可 靠 的 服 务 数 据 报 套 接 字 是 无 连 接 的, 它 支 持 双 向 的 数 据 传 输, 具 有 开 销 小 数 据 传 输 效 率 高 的 特 点, 但 不 保 证 数 据 传 输 的 可 靠 性 有 序 性 和 无 重 复 性, 适 合 少 量 数 据 传 输 以 及 时 间 敏 感 的 音 视 频 多 媒 体 数 据 传 输 此 外, 还 有 一 种 较 少 使 用 的 套 接 字 叫 原 始 套 接 字 (SOCK_RAW), 可 以 使 用 它 对 底 18

23 第 三 章 Winsock 通 信 的 设 计 与 实 现 层 协 议 如 IP 或 ICMP 直 接 访 问, 在 通 信 与 协 议 开 发 时 有 时 会 用 到 Windows 套 接 字 程 序 执 行 API 函 数 I/O 操 作 时 有 阻 塞 和 非 阻 塞 两 种 模 式 在 阻 塞 模 式 下, 执 行 I/O 操 作 的 Winsock 函 数 ( 如 accept send recv 等 ) 在 I/O 操 作 完 成 前, 会 一 直 等 下 去, 不 会 立 即 返 回 程 序 ( 将 控 制 权 交 还 给 程 序 ); 而 在 非 阻 塞 模 式 下, 调 用 Winsock 函 数 进 行 I/O 操 作 时, 不 管 I/O 有 没 有 完 成 会 立 即 返 回 socket 在 初 始 化 后 默 认 工 作 在 阻 塞 模 式, 可 以 通 过 ioctlsocket() 函 数 改 变 socket 工 作 模 式 客 户 机 / 服 务 器 模 型 一 个 在 建 立 分 布 式 应 用 时 最 常 用 的 范 例 便 是 客 户 机 / 服 务 器 模 型 在 这 种 方 案 中 客 户 应 用 程 序 向 服 务 器 程 序 请 求 服 务 这 种 方 式 隐 含 了 在 建 立 客 户 机 / 服 务 器 间 通 信 时 的 非 对 称 性 客 户 机 / 服 务 器 模 型 工 作 时 要 求 有 一 套 为 客 户 机 和 服 务 器 所 共 识 的 惯 例 来 保 证 服 务 能 够 被 提 供 ( 或 被 接 受 ) 这 一 套 惯 例 包 含 了 一 套 协 议 它 必 须 在 通 信 的 两 头 都 被 实 现 根 据 不 同 的 实 际 情 况, 协 议 可 能 是 对 称 的 或 是 非 对 称 的 在 对 称 的 协 议 中, 每 一 方 都 有 可 能 扮 演 主 从 角 色 ; 在 非 对 称 协 议 中, 一 方 被 不 可 改 变 地 认 为 是 主 机, 而 另 一 方 则 是 从 机 一 个 对 称 协 议 的 例 子 是 Internet 中 用 于 终 端 仿 真 的 TELNET 而 非 对 称 协 议 的 例 子 是 Internet 中 的 FTP 无 论 具 体 的 协 议 是 对 称 的 或 是 非 对 称 的, 当 服 务 被 提 供 时 必 然 存 在 客 户 进 程 和 服 务 进 程 一 个 服 务 程 序 通 常 在 一 个 众 所 周 知 的 地 址 监 听 对 服 务 的 请 求, 也 就 是 说, 服 务 进 程 一 直 处 于 休 眠 状 态, 直 到 一 个 客 户 对 这 个 服 务 的 地 址 提 出 了 连 接 请 求 在 这 个 时 刻, 服 务 程 序 被 惊 醒 并 且 为 客 户 提 供 服 务 - 对 客 户 的 请 求 作 出 适 当 的 反 应 这 一 请 求 / 相 应 的 过 程 可 以 简 单 的 用 图 2-1 表 示 虽 然 基 于 连 接 的 服 务 是 设 计 客 户 机 / 服 务 器 应 用 程 序 时 的 标 准, 但 有 些 服 务 也 是 可 以 通 过 数 据 报 套 接 字 提 供 的 在 TCP/IP 网 络 中 两 个 进 程 间 的 相 互 作 用 的 主 机 模 式 是 客 户 机 / 服 务 器 [16] 模 式 (Client/Server Model) 该 模 式 的 建 立 基 于 以 下 两 点 :1 非 对 等 作 用 ;2 通 信 完 全 是 异 步 的 客 户 机 / 服 务 器 模 式 在 操 作 过 程 中 采 取 的 是 主 动 请 示 方 式 : 首 先 服 务 器 方 要 先 启 动, 并 根 据 请 示 提 供 相 应 服 务 :( 过 程 如 下 ) 1 打 开 一 通 信 通 道 并 告 知 本 地 主 机, 它 愿 意 在 某 一 个 公 认 地 址 上 接 收 客 户 请 求 2 等 待 客 户 请 求 到 达 该 端 口 3 接 收 到 重 复 服 务 请 求, 处 理 该 请 求 并 发 送 应 答 信 号 4 返 回 第 二 步, 等 待 另 一 客 户 请 求 5 关 闭 服 务 器 客 户 方 : 1 打 开 一 通 信 通 道, 并 连 接 到 服 务 器 所 在 主 机 的 特 定 端 口 19

24 第 三 章 Winsock 通 信 的 设 计 与 实 现 2 向 服 务 器 发 送 服 务 请 求 报 文, 等 待 并 接 收 应 答 ; 继 续 提 出 请 求 3 请 求 结 束 后 关 闭 通 信 通 道 并 终 止 1. 面 向 连 接 的 套 接 字 面 向 连 接 套 接 字 定 义 了 一 种 可 靠 的 面 向 连 接 的 服 务, 实 现 了 无 差 错 无 重 复 的 顺 序 数 据 传 输. 数 据 报 套 接 字 定 义 了 一 种 无 连 接 的 服 务, 数 据 通 过 相 互 独 立 的 报 文 进 行 传 输, 是 无 序 的, 并 且 不 保 证 可 靠, 无 差 错. 原 始 套 接 字 允 许 对 低 层 协 议 如 IP 或 ICMP 直 接 访 问, 主 要 用 于 新 的 网 络 协 议 实 现 的 测 试 等 系 统 调 用 时 序 图 如 图 3.1: 图 3.1 面 向 连 接 套 接 字 的 系 统 调 用 时 序 图 2. 无 连 接 套 接 字 基 于 UDP 协 议 无 连 接 服 务 器 一 般 都 是 面 向 事 务 处 理 的, 一 个 请 求 一 个 应 答 就 完 成 了 客 户 程 序 与 服 务 程 序 之 间 的 相 互 作 用 20

25 第 三 章 Winsock 通 信 的 设 计 与 实 现 图 3.2 无 连 接 协 议 的 套 接 字 调 用 时 序 图 UDP 设 计 初 衷 就 是 尽 可 能 快 的 将 数 据 包 发 送 出 去 所 以 UDP 协 议 显 得 非 常 精 简 只 要 建 立 一 个 包, 构 造 一 个 有 目 标 信 息 的 IP 头, 然 后 发 出 去 无 需 连 接 当 然 UDP 也 需 要 通 过 对 方 返 回 命 令 正 确 应 答 也 叫 ACK 包, 来 避 免 数 据 包 丢 失 假 使 一 定 时 间 内, 发 送 方 没 有 收 到 接 收 方 的 应 答, 则 重 新 发 送 数 据 包, 直 到 收 到 "ACK" 确 认 包 Winsock 控 件 编 程 参 数 使 用 说 明 微 软 公 司 开 发 的 Winsock 是 Windows 环 境 网 络 程 序 的 接 口 (API), 也 是 一 种 进 入 TCP/IP 的 较 为 方 便 的 方 法, 但 是 调 用 Winsock 的 过 程 是 很 复 杂 的 VC6.0 提 供 了 Winsock 控 件, 只 需 要 设 置 控 件 中 的 属 性, 调 用 其 方 法 即 可 进 行 数 据 交 换, 减 少 了 开 发 周 期 和 提 高 工 作 效 益 为 了 更 好 说 明 套 接 字 编 程 原 理, 在 这 里 先 列 出 几 个 简 单 函 数 的 功 能 及 参 数, 见 表

26 第 三 章 Winsock 通 信 的 设 计 与 实 现 表 3.1 Winsock 函 数 参 数 说 明 函 数 说 明 功 能 用 于 初 始 化 Winsock int WSAStarup(WORD wversionrequested,lpwsadata 声 明 WSAStartup lpwsadata) 参 数 wversionrequested: 要 求 使 用 Winsock 的 最 低 版 本 号 ; lpwsadata:winsock 的 详 细 资 料 功 能 用 于 生 成 套 接 字 声 明 SOCKET socket(int af,int type,int protocol) socket af: 地 址 家 族 ( 通 常 使 用 :AF_INET); 参 数 type:socket 的 种 类 ; protocol: 所 使 用 的 协 议 功 能 指 定 本 地 IP 地 址 所 使 用 的 端 口 号 int bind ( SOCKET s,const struct sockaddr FAR 声 明 *addr,int namelen ) bind s: 指 向 用 Socket 函 数 生 成 的 Socket Descriptor; 参 数 addr: 指 向 Socket 地 址 的 指 针 ; namelen: 该 地 址 的 长 度 功 能 用 于 与 服 务 器 建 立 连 接, 发 出 连 接 请 求 声 明 int connect (SOCKET s,const struct sockaddr FAR connect *name,int namelen ) s: 指 向 用 Socket 函 数 生 成 的 Socket Descriptor; 参 数 name: 指 向 服 务 器 地 址 的 指 针 ; namelen: 该 地 址 的 长 度 功 能 利 用 Socket 进 行 接 受 数 据 声 明 int recv (SOCKET s,char FAR *buf,int len,int flags ) recv s: 指 向 用 Socket 函 数 生 成 的 Socket Descriptor; 参 数 buf: 接 受 数 据 的 缓 冲 区 ( 数 组 ) 的 指 针 ; len: 缓 冲 区 的 大 小 功 能 利 用 Socket 进 行 发 送 数 据 int send(socket s,const char FAR *buf,int len,int 声 明 flags) send s: 指 向 用 Socket 函 数 生 成 的 Socket Descriptor; 参 数 buf: 发 送 数 据 的 缓 冲 区 ( 数 组 ) 的 指 针 ; len: 缓 冲 区 的 大 小 3.2 Winscok 网 络 通 信 应 用 程 序 设 计 在 方 案 选 择 上 采 用 在 网 络 编 程 中 最 常 用 的 一 种 模 型 客 户 机 / 服 务 器 模 型 这 种 客 户 机 / 服 务 器 模 型 是 一 种 非 对 称 式 编 程 模 式 该 模 式 的 基 本 思 想 是 把 集 中 在 一 起 的 应 用 划 分 成 为 功 能 不 同 的 两 个 部 分, 分 别 在 不 同 的 计 算 机 上 运 行, 通 过 它 们 之 间 的 分 工 合 作 来 实 现 一 个 完 整 的 功 能 对 于 这 种 模 式 而 言 其 中 一 部 分 需 要 作 为 服 务 器, 22

27 第 三 章 Winsock 通 信 的 设 计 与 实 现 用 来 响 应 并 为 客 户 提 供 固 定 的 服 务 ; 另 一 部 分 则 作 为 客 户 机 程 序 用 来 向 服 务 器 提 出 请 求 或 要 求 某 种 服 务 选 取 基 于 TCP/IP 的 客 户 机 / 服 务 器 模 型 和 面 向 连 接 的 流 式 套 接 字 其 通 信 原 理 为 : 服 务 器 端 和 客 户 端 都 必 须 建 立 通 信 套 接 字, 而 且 服 务 器 端 应 先 进 入 监 听 状 态, 然 后 客 户 端 套 接 字 发 出 连 接 请 求, 服 务 器 端 收 到 请 求 后, 建 立 另 一 个 套 接 字 进 行 通 信, 原 来 负 责 监 听 的 套 接 字 仍 进 行 监 听, 如 果 有 其 它 客 户 发 来 连 接 请 求, 则 再 建 立 一 个 套 接 字 默 认 状 态 下 最 多 可 同 时 接 收 5 个 客 户 的 连 接 请 求, 并 与 之 建 立 通 信 关 系 因 此 本 程 序 的 设 计 流 程 应 当 由 服 务 器 首 先 启 动, 然 后 在 某 一 时 刻 启 动 客 户 机 并 使 其 与 服 务 器 建 立 连 接 服 务 器 与 客 户 机 开 始 都 必 须 调 用 Windows Sockets API 函 数 socket() 建 立 一 个 套 接 字 Sockets, 然 后 服 务 器 方 调 用 bind() 将 套 接 字 与 一 个 本 地 网 络 地 址 捆 扎 在 一 起, 再 调 用 listen() 使 套 接 字 处 于 一 种 被 动 的 准 备 接 收 状 态, 同 时 规 定 它 的 请 求 队 列 长 度 在 此 之 后 服 务 器 就 可 以 通 过 调 用 accept() 来 接 收 客 户 机 的 连 接 在 VC 中 进 行 WINSOCK 的 API 编 程 开 发 的 时 候, 需 要 在 项 目 中 使 用 下 面 三 个 文 件, 否 则 会 出 现 编 译 错 误, 见 文 献 [17] (1)WINSOCK.H: 这 是 WINSOCK API 的 头 文 件, 需 要 包 含 在 项 目 中 (2)WSOCK32.LIB: WINSOCK API 连 接 库 文 件 在 使 用 中, 一 定 要 把 它 作 为 项 目 的 非 缺 省 的 连 接 库 包 含 到 项 目 文 件 中 去 (3)WINSOCK.DLL: WINSOCK 的 动 态 连 接 库, 位 于 WINDOWS 的 安 装 目 录 下 服 务 器 程 序 的 开 发 (1) 使 用 WSAStartup() 函 数 将 WinSock 初 始 化 由 于 Winsock 提 供 的 API 服 务 是 以 动 态 链 接 库 WinSock.dll [18] 实 现 的, 所 以 必 须 先 调 用 WSAStartup() 函 数 对 WinSock.dll 进 行 加 载 初 始 化, 协 商 Winsock 的 版 本 支 持, 并 分 配 必 要 的 资 源 如 果 在 调 用 Winsock 函 数 前 没 有 加 载 Winsock 库, 则 会 返 回 SOCKET_ERROR 错 误, 错 误 信 息 是 WSANOTINITIALISED (2) 使 用 sockets() 函 数 创 建 套 接 字, 并 返 回 套 接 字 s 初 始 化 WinSock 的 动 态 连 接 库 后, 需 要 在 服 务 器 端 建 立 一 个 监 听 的 socket, 为 此 可 以 调 用 socket() 函 数 用 来 建 立 这 个 监 听 的 socket, 并 定 义 此 socket 所 使 用 的 通 信 协 议 此 函 数 调 用 成 功 返 回 socket 对 象, 失 败 则 返 回 INVALID_SOCKET( 调 用 WSAGetLastError() 可 得 知 原 因, 所 有 WinSocket 的 函 数 都 可 以 使 用 这 个 函 数 来 获 取 失 败 的 原 因 ) socket 函 数 的 原 型 如 下 : SOCKET socket (int af,int type,int protocol); 23

28 第 三 章 Winsock 通 信 的 设 计 与 实 现 其 中,af 用 于 指 定 网 络 地 址 族, 一 般 取 AF_INET, 表 示 该 套 接 字 在 Internet 域 中 进 行 通 信 参 数 type 用 于 指 定 套 接 字 类 型, 若 取 SOCK_STREAM 表 示 要 创 建 的 套 接 字 是 面 向 连 接 时 使 用 的 流 套 接 字, 若 取 SOCK_DGRAM 则 创 建 无 连 接 时 的 数 据 报 套 接 字 参 数 protocol 则 用 于 当 指 定 地 址 族 和 套 接 字 类 型 有 多 个 条 目 时 用 来 限 定 使 用 特 定 的 网 络 协 议, 一 般 使 用 时 可 取 0, 表 示 默 认 为 TCP/IP 协 议 若 套 接 字 创 建 成 功 则 该 函 数 返 回 所 创 建 的 套 接 字 句 柄 SOCKET, 否 则 产 生 INVALID_SOCKET 错 误 实 现 代 码 举 例 如 下 : if(!initsocket()) return 1; // 初 始 化 Window Sockets DLL, 若 出 错 返 回 1 s=socket( AF_INET,SOCK_STREAM,0); // 创 建 流 式 套 接 字 (3) 使 用 bind() 函 数 把 套 接 字 s 和 本 机 的 IP,TCP 口 绑 定 接 下 来 要 为 服 务 器 端 定 义 的 这 个 监 听 的 Socket 指 定 一 个 地 址 及 端 口 (Port), 这 样 客 户 端 才 知 道 待 会 要 连 接 哪 一 个 地 址 的 哪 个 端 口, 为 此 我 们 要 调 用 bind() 函 数, 该 函 数 调 用 成 功 返 回 0, 否 则 返 回 SOCKET_ERROR bind() 函 数 原 型 如 下 : int bind(socket s,const struct sockaddr FAR * name,int namelen); 其 中, 第 一 个 参 数 s 标 识 一 未 捆 绑 过 的 套 接 字 句 柄, 它 用 来 等 待 客 户 机 的 请 求 ; 第 二 个 参 数 name 是 赋 予 套 接 字 的 地 址, 它 由 struct sockaddr 结 构 表 示 ; 第 三 个 参 数 namelen 为 name 的 长 度 实 现 代 码 举 例 如 下 : ((sockaddr_in*)&addr)->sin_family = AF_INET; //AF_INET: 使 用 Internet 地 址 族 ((sockaddr_in*)&addr)->sin_port = htons(3000); // htons():16 位 端 口 号 3000 的 主 机 字 节 顺 序 转 换 成 网 络 字 节 顺 序 ((sockaddr_in*)&addr)->sin_addr.s_addr = inet_addr(" "); // inet_addr(): 主 机 点 分 十 进 制 字 符 串 IP 地 址 转 换 为 网 络 字 节 顺 序 的 u_long IP 地 址 bind(sock,&addr,sizeof(addr)); // 把 套 接 字 与 地 址 绑 定 如 果 使 用 者 不 在 意 地 址 或 端 口 的 值, 那 么 可 以 设 定 地 址 为 INADDR_ANY, 及 Port 为 0,Windows Sockets 会 自 动 将 其 设 定 适 当 之 地 址 及 Port(1024 到 5000 之 间 的 值 ) 此 后 可 以 调 用 getsockname() 函 数 来 获 知 其 被 设 定 的 值 (4) 使 用 listen() 通 知 TCP 服 务 准 备 好 接 收 连 接 当 服 务 器 端 的 Socket 对 象 绑 定 完 成 之 后, 服 务 器 端 必 须 建 立 一 个 监 听 的 队 列 来 接 收 客 户 端 的 连 接 请 求 listen() 函 数 原 型 如 下 : int listen(socket s, int backlog); 24

29 第 三 章 Winsock 通 信 的 设 计 与 实 现 第 一 个 参 数 指 定 套 接 字 第 二 个 backlog 参 数 指 定 了 正 在 等 待 连 接 的 最 大 队 列 长 度 这 个 参 数 非 常 重 要, 因 为 完 全 可 能 同 时 出 现 几 个 服 务 器 连 接 请 求 例 如, 假 定 backlog 参 数 为 2, 如 果 三 个 客 户 机 同 时 发 出 请 求, 那 么 头 两 个 会 被 放 在 一 个 等 待 处 理 的 队 列 中, 以 便 应 用 程 序 依 次 为 它 们 提 供 服 务 而 第 三 个 连 接 会 造 成 一 个 WSAECONNREFUSED 错 误 listen() 函 数 使 服 务 器 端 的 socket 进 入 监 听 状 态, 并 设 定 可 以 建 立 的 最 大 连 接 数 ( 目 前 最 大 值 限 制 为 5, 最 小 值 为 1) 该 函 数 调 用 成 功 返 回 0, 否 则 返 回 SOCKET_ERROR (5)accept() 接 受 客 户 端 的 连 接 请 求 当 客 户 端 提 出 连 接 请 求 时, 服 务 器 会 收 到 Winsock Stack 送 来 我 们 自 定 义 的 一 个 消 息, 这 时, 我 们 可 以 分 析 lparam, 然 后 调 用 相 关 的 函 数 来 处 理 此 事 件 为 了 使 服 务 器 端 接 受 客 户 端 的 连 接 请 求, 就 要 使 用 accept() 函 数, 该 函 数 新 建 一 socket 与 客 户 端 的 socket 相 通, 原 先 监 听 之 socket 继 续 进 入 监 听 状 态, 等 待 他 人 的 连 接 要 求 该 函 数 调 用 成 功 返 回 一 个 新 产 生 的 socket 对 象, 否 则 返 回 INVALID_SOCKET accept() 函 数 的 原 型 为 : SOCKET accept(socket s,struct sockaddr* addr,int* addrlen); 其 中, 第 一 个 参 数 s 指 定 套 接 字, 它 须 处 在 监 听 模 式 而 第 二 个 参 数 是 一 个 SOCKADDR 结 构 形 式 的 地 址, 第 三 个 参 数 addrlen 为 SOCKADDR 结 构 的 长 度 如 果 客 户 端 有 了 连 接 请 求, 服 务 器 通 过 使 用 accept() 函 数 来 接 受 客 户 端 的 请 求 accept() 函 数 返 回 后,addr 结 构 中 会 包 含 发 出 连 接 请 求 的 那 个 客 户 机 的 IP 地 址 信 息, 而 addrlen 参 数 则 指 出 该 结 构 的 长 度 此 外,accept() 会 返 回 一 个 新 的 套 接 字 描 述 符, 它 对 应 于 已 经 接 受 的 那 个 客 户 机 连 接 对 于 该 客 户 机 后 续 的 所 有 操 作, 都 应 使 用 这 个 新 套 接 字 至 于 原 来 那 个 监 听 套 接 字, 它 仍 然 用 于 接 受 其 他 客 户 机 连 接, 而 且 仍 处 于 监 听 模 式 实 现 代 码 举 例 如 下 : listen(sock,1); // 设 置 服 务 器 监 听 方 式,1-- 允 许 等 待 队 列 的 长 度 len=sizeof(addr); sersock=accept(sock,&addr,&len ); // 阻 塞, 等 待 客 户 连 接 进 来, 从 等 待 队 列 中 检 取 客 户 // 接 受 客 户 连 接, 生 成 新 套 接 字 sersock 对 应 该 连 接 ; 而 原 监 听 Socket 继 续 等 待 其 它 客 户 连 接 请 求 (6) 使 用 recv()/send() 函 数 来 接 收 / 发 送 资 料 基 于 TCP/IP 连 接 协 议 套 接 字 的 服 务 是 设 计 客 户 机 / 服 务 器 应 用 程 序 时 的 主 流 标 准 面 向 连 接 套 接 字 提 供 双 向 可 靠 有 次 序 不 重 复 的 资 料 传 送 一 般 情 况 下 TCP Socket 的 数 据 发 送 和 接 收 是 调 用 send() 及 recv() 这 两 个 函 数 25

30 第 三 章 Winsock 通 信 的 设 计 与 实 现 来 达 成 send() 函 数 的 原 型 为 : int send(socket s,const char FAR * buf,int len,int flags); 其 中, 参 数 s 是 已 建 立 连 接 的 套 接 字, 将 在 这 个 套 接 字 上 发 送 数 据 第 二 个 参 数 buf, 则 是 字 符 缓 冲 区, 区 内 包 含 即 将 发 送 的 数 据 第 三 个 参 数 len, 指 定 即 将 发 送 的 缓 冲 区 内 的 字 符 数 最 后,flags 一 般 可 设 为 0 send() 函 数 调 用 后, 返 回 实 际 发 送 的 字 节 数 ; 若 发 生 错 误, 就 返 回 SOCKET_ERROR send() 实 现 代 码 举 例 如 下 : send(sock,msg,strlen(msg)+1,0); // 发 送 数 据 recv() 函 数 的 原 型 为 : int recv(socket s,char FAR * buf,int len,int flags); 其 中, 参 数 s 是 准 备 接 收 数 据 的 那 个 套 接 字 第 二 个 参 数 buf, 是 即 将 收 到 数 据 的 字 符 缓 冲, 而 len 则 是 准 备 接 收 的 字 节 数 或 buf 缓 冲 的 长 度 最 后,flags 参 数 一 般 可 设 为 0 该 函 数 调 用 后 返 回 读 入 数 据 的 字 节 数 recv() 实 现 代 码 举 例 如 下 : len=recv(sersock,msg,200,0 ); // 接 收 数 据 (7) 使 用 closesockt() 关 闭 套 接 字 结 束 服 务 器 和 客 户 端 的 通 信 连 接 是 很 简 单 的, 这 一 过 程 可 以 由 服 务 器 或 客 户 机 的 任 一 端 启 动, 只 要 调 用 closesocket() 就 可 以 了, 而 要 关 闭 Server 端 监 听 状 态 的 socket, 同 样 也 是 利 用 此 函 数 另 外, 与 程 序 启 动 时 调 用 WSAStartup() 憨 数 相 对 应, 程 式 结 束 前, 需 要 调 用 WSACleanup() 来 通 知 Winsock Stack 释 放 Socket 所 占 用 的 资 源 这 两 个 函 数 都 是 调 用 成 功 返 回 0, 否 则 返 回 SOCKET_ERROR 客 户 端 程 序 的 开 发 (1) 使 用 WSAStartup() 函 数 将 WinSock 初 始 化 (2) 使 用 sockets() 函 数 创 建 套 接 字 与 服 务 器 端 的 socket 不 同 的 是, 客 户 端 的 socket 可 以 调 用 bind() 函 数, 由 自 己 来 指 定 IP 地 址 及 port 号 码 ; 但 是 也 可 以 不 调 用 bind(), 而 由 Winsock 来 自 动 设 定 IP 地 址 及 port 号 码 (3) 使 用 connect() 函 数 将 客 户 端 客 户 端 的 socket 使 用 connect() 函 数 来 提 出 与 服 务 器 端 的 socket 建 立 连 接 的 申 请, 函 数 调 用 成 功 返 回 0, 否 则 返 回 SOCKET_ERROR connect() 函 数 原 型 为 : int connect(socket s,const struct sockaddr FAR* name,int namelen); 26

31 第 三 章 Winsock 通 信 的 设 计 与 实 现 其 中, 参 数 s 指 定 套 接 字 ;name 是 对 方 服 务 器 SOCKADDR 结 构 形 式 的 地 址 ;namelen 则 是 地 址 参 数 的 长 度 如 果 连 接 的 服 务 器 没 有 监 听 指 定 端 口,connect 调 用 就 会 失 败, 发 生 错 误 WSAECONNREFUSED 实 现 代 码 举 例 如 下 : ((sockaddr_in*)&addr)->sin_family =AF_INET; //AF_INET 地 址 族 gets(msg); // 输 入 点 分 十 进 制 形 式 的 服 务 器 地 址 gets(msg); // 输 入 想 连 接 到 的 服 务 器 端 口 号 portno=atoi(msg); // 字 符 串 形 式 端 口 号 转 换 为 整 型 ((sockaddr_in*)&addr)->sin_port=htons(portno); // 端 口 号 转 网 络 字 节 顺 序 其 中, 参 数 s 指 定 套 接 字 ;name 是 对 方 服 务 器 SOCKADDR 结 构 形 式 的 地 址 ;namelen 则 是 地 址 参 数 的 长 度 如 果 连 接 的 服 务 器 没 有 监 听 指 定 端 口,connect 调 用 就 会 失 败, 发 生 错 误 WSAECONNREFUSED (4) 使 用 send()/recv() 函 数 来 发 送 / 接 收 资 料 ( 同 服 务 器 ) (5) 使 用 使 用 closesockt() 关 闭 套 接 字 ( 同 服 务 器 ) 为 了 简 化 WinSock 网 络 编 程, 使 用 户 专 注 于 应 用 程 序 算 法 的 设 计,Microsoft 的 基 本 类 库 (Microsoft Foundation Class,MFC) 提 供 了 两 种 利 用 Windows Sockets 进 行 网 络 通 信 的 编 程 模 式, 这 两 种 模 式 即 为 用 CAsyncSocket 类 和 派 生 于 CAsyncSocket 的 CSocket 类 来 编 程 这 两 个 类 在 不 同 程 度 上 对 WinSock API 的 函 数 进 行 了 封 装, 在 编 程 时 使 用 经 过 封 装 的 MFC WinSock 类 使 编 程 工 作 大 大 简 化, 而 且, 这 两 个 类 都 提 供 了 事 件 处 理 函 数, 通 过 对 事 件 处 理 函 数 进 行 重 载, 用 户 可 以 在 应 用 程 序 中 很 方 便 地 对 套 接 字 发 送 接 收 数 据 等 事 件 进 行 处 理 CAsyncSocket 类 封 装 了 Windows Sockets API 函 数, 提 供 了 较 低 层 的 与 Windows Sockets 对 话 接 口, 一 般 适 合 于 有 相 当 水 平 的 网 络 编 程 基 础 者 使 用, 可 方 便 地 进 行 底 层 的 网 络 事 件 通 知 及 信 息 回 叫 控 制 等 操 作 CSocket 派 生 于 CAsyncSocket, 它 继 承 了 父 类 中 一 些 常 用 易 懂 的 Windows Sockets API 函 数, 并 对 CAsyncSocket 中 底 层 的 较 难 控 制 的 一 些 API 函 数 或 成 员 函 数 进 行 了 处 理, 同 时 它 支 持 模 块 化 的 后 台 信 息 处 理, 解 决 了 CAsyncSocket 中 较 难 克 服 的 多 线 程 处 理 正 是 基 于 Csocket 类 的 这 些 优 点, 程 序 中 采 用 Csocket 类 来 实 现 数 据 的 传 输 27

32 第 四 章 大 模 数 的 rabin 密 码 保 密 通 信 软 件 的 实 现 第 四 章 大 模 数 的 Rabin 密 码 保 密 通 信 软 件 的 实 现 4.1 功 能 模 块 设 计 在 公 钥 密 码 系 统 中, 加 密 和 解 密 使 用 的 是 不 同 的 密 钥 ( 相 对 于 对 称 密 钥, 人 们 把 他 叫 做 非 对 称 密 钥 ), 这 两 个 密 钥 之 间 存 在 着 相 互 依 存 关 系 : 即 用 其 中 任 一 个 密 钥 加 密 的 信 息 只 能 用 另 一 个 密 钥 进 行 解 密 这 使 得 通 信 双 方 无 需 事 先 交 换 密 钥 就 可 进 行 保 密 通 信 其 中 加 密 密 钥 和 算 法 是 对 外 公 开 的, 人 人 都 能 够 通 过 这 个 密 钥 加 密 文 档 然 后 发 给 收 信 者, 这 个 加 密 密 钥 又 称 为 公 钥 ; 而 收 信 者 收 到 加 密 文 档 后, 他 能 够 使 用 他 的 解 密 密 钥 解 密, 这 个 密 钥 是 由 他 自 己 私 人 掌 管 的, 并 无 需 分 发, 因 此 又 成 称 为 私 钥, 这 就 解 决 了 密 钥 分 发 的 问 题 为 了 说 明 这 一 思 想, 我 们 能 够 考 虑 如 下 的 类 比 : 两 个 在 不 安 全 信 道 中 通 信 的 人, 假 设 为 Alice( 收 信 者 ) 和 Bob( 发 信 者 ), 他 们 希 望 能 够 安 全 的 通 信 而 不 被 他 们 的 敌 手 Oscar 破 坏 Alice 想 到 了 一 种 办 法, 她 使 用 了 一 种 锁 ( 相 当 于 公 钥 ), 这 种 锁 任 何 人 只 要 轻 轻 一 按 就 能 够 锁 上, 但 是 只 有 Alice 的 钥 匙 ( 相 当 于 私 钥 ) 才 能 够 打 开 然 后 Alice 对 外 发 送 无 数 把 这 样 的 锁, 任 何 人 比 如 Bob 想 给 她 寄 信 时, 只 需 找 到 一 个 箱 子, 然 后 用 一 把 Alice 的 锁 将 其 锁 上 再 寄 给 Alice, 这 时 候 任 何 人 ( 包 括 Bob 自 己 ) 除 了 拥 有 钥 匙 的 Alice, 都 不 能 再 打 开 箱 子, 这 样 即 使 Oscar 能 找 到 Alice 的 锁, 即 使 Oscar 能 在 通 信 过 程 中 截 获 这 个 箱 子, 没 有 Alice 的 钥 匙 他 也 不 可 能 打 开 箱 子, 而 Alice 的 钥 匙 并 无 需 分 发, 这 样 Oscar 也 就 无 法 得 到 这 把 私 人 密 钥, 见 文 献 [19] 从 以 上 的 介 绍 能 够 看 出, 公 钥 密 码 体 制 的 思 想 并 不 复 杂, 而 实 现 他 的 关 键 问 题 是 如 何 确 定 公 钥 和 私 钥 及 加 / 解 密 的 算 法, 也 就 是 说 如 何 找 到 Alice 的 锁 和 钥 匙 的 问 题 我 们 假 设 在 这 种 体 制 中, PK 是 公 开 信 息, 用 作 加 密 密 钥, 而 SK 需 要 由 用 户 自 己 保 密, 用 作 解 密 密 钥 图 4.1 是 公 钥 密 码 体 制 的 框 图, 我 们 可 以 看 出, 公 开 密 钥 技 术 进 行 安 全 通 信, 有 以 下 优 点 : (1) 通 信 双 方 事 先 不 需 要 通 过 保 密 信 道 交 换 密 钥 (2) 密 钥 持 有 量 大 大 减 少 在 n 个 用 户 的 团 体 中 进 行 通 信, 每 一 用 户 只 需 要 持 有 自 己 的 私 钥, 而 公 钥 可 放 置 在 公 共 数 据 库 上, 供 其 它 用 户 取 用 28

33 第 四 章 大 模 数 的 rabin 密 码 保 密 通 信 软 件 的 实 现 图 4.1 公 钥 密 码 体 制 框 图 从 上 述 条 件 可 看 出, 公 开 密 钥 密 码 体 制 下, 加 密 密 钥 不 等 于 解 密 密 钥 加 密 密 钥 可 对 外 公 开, 使 任 何 用 户 都 可 将 传 送 给 此 用 户 的 信 息 用 公 开 密 钥 加 密 发 送, 而 该 用 户 唯 一 保 存 的 私 人 密 钥 是 保 密 的, 也 只 有 他 能 将 密 文 复 原 解 密 虽 然 解 密 密 钥 理 论 上 可 由 加 密 密 钥 推 算 出 来, 但 这 种 算 法 设 计 在 实 际 上 是 不 可 能 的, 或 虽 然 能 够 推 算 出, 但 要 花 费 很 长 的 时 间 而 成 为 不 可 行 的 所 以 将 加 密 密 钥 公 开 也 不 会 危 害 密 钥 的 安 全, 见 文 献 [20] A,B 两 用 户 在 Rabin 公 开 密 钥 密 码 体 制 下 进 行 保 密 通 信 的 过 程 为 : 1 用 户 A 要 与 用 户 B 通 信, 通 信 前 A 产 生 一 对 密 钥 (Kpk,Ksk),Kpk 为 公 开 的 加 密 密 钥,Ksk 为 保 密 的 解 加 密 密 钥 ; 2 用 户 A 将 Kpk 送 到 用 户 B; 3 用 户 B 产 生 一 会 话 S, 用 Kpk 加 密 后 送 给 用 户 A,A 收 到 后 用 Ksk 解 密, 得 到 S; 4Kpk,Ksk 被 撤 消 ; 5 用 户 A, B 间 使 用 会 话 S 进 行 保 密 通 信 ; 6 通 信 完 毕, 密 钥 Ks 被 撤 消 图 4.2 是 Rabin 保 密 通 信 软 件 模 块 结 构 图, 结 构 图 中 读 者 可 以 清 楚 地 看 到, 此 系 统 共 有 三 个 大 的 结 构 组 成,Rabin 密 码 部 分,Winsock 通 信 部 分 和 用 户 界 面 设 计 部 分 图 4.2 Rabin 保 密 通 信 软 件 模 块 结 构 图 Rabin 密 码 部 分 部 分 又 细 分 为 两 个 小 的 结 构, 即 加 密 部 分 和 解 密 部 分 ;Winsock 通 信 部 分 也 有 服 务 器 端 和 客 户 端 两 部 分 组 成 ; 用 户 界 面 设 计 部 分 的 作 用 主 要 是 增 加 29

34 第 四 章 大 模 数 的 rabin 密 码 保 密 通 信 软 件 的 实 现 系 统 的 美 观 性 和 易 操 作 性, 提 供 人 机 对 话 接 口 图 4.3 是 保 密 通 信 的 流 程 图, 服 务 器 启 动 后, 等 待 客 户 端 的 连 接 请 求, 然 后 进 行 公 钥 交 换, 使 用 公 钥 进 行 信 息 加 密, 达 到 保 密 通 信 的 目 的 图 4.3 保 密 通 信 流 程 图 4.2 界 面 设 计 完 成 了 Rabin 和 Winsock 算 法 的 编 程 后, 我 们 就 可 以 用 VisualC++ 结 合 算 法 源 代 码 做 一 个 可 视 化 界 面. 这 个 界 面 具 有 : 产 生 素 数 加 密 解 密 通 信 等 功 能 通 过 此 界 面, 一 般 的 用 户 都 能 轻 轻 松 松 地 完 成 保 密 通 信 在 这 里 我 们 使 用 MFC 和 向 导 (Wizards) 来 编 写 应 用 程 序 制 作 可 视 化 界 面 1. 客 户 端 界 面 设 计 运 行 客 户 端 程 序, 我 们 可 以 看 到 友 好 的 人 机 界 面 要 实 现 客 户 端 的 功 能, 首 先 必 须 对 各 参 数 进 行 设 置 图 中 模 数 一 栏 输 入 Rabin 密 码 系 统 模 数 [21] 的 位 长, 为 了 安 全 起 见, 该 数 值 要 大 于 512 比 特, 即 32 字 长 输 入 服 务 器 的 地 址 和 端 口 号, 由 于 条 件 的 限 制, 我 们 在 同 一 台 计 算 机 上 演 示, 输 入 IP 为 设 置 完 毕 后, 点 击 30

35 第 四 章 大 模 数 的 rabin 密 码 保 密 通 信 软 件 的 实 现 连 接 按 钮 启 动 随 机 数 生 成 器, 如 图 4.4 注 意 若 此 时 服 务 器 没 有 启 动 将 无 法 连 接 图 4.4 随 机 数 生 成 器 图 4.5 客 户 端 密 钥 生 成 界 面 我 们 等 待 其 生 成 密 钥, 密 钥 生 成 成 功 后, 将 公 钥 发 送 给 服 务 器, 并 接 收 对 方 公 钥, 如 图 4.5 所 示 服 务 器 使 用 客 户 端 公 钥 对 消 息 进 行 加 密, 将 加 密 后 的 消 息 通 过 Winsock 传 送 到 客 户 端 客 户 端 收 到 加 密 消 息 后, 调 用 私 钥 (p,q) 进 行 解 密, 得 到 明 文 消 息, 如 图 4.6 为 了 操 作 方 便, 使 界 面 更 简 洁, 在 这 里 我 们 不 显 示 密 文 消 息 31

36 第 四 章 大 模 数 的 rabin 密 码 保 密 通 信 软 件 的 实 现 图 4.6 客 户 端 聊 天 界 面 2. 服 务 器 界 面 设 计 打 开 服 务 器 程 序, 点 开 密 钥 生 成 标 签, 生 成 私 钥 (p,q) 和 公 钥 n, 如 图 4.7 等 待 客 户 端 连 接 并 交 换 公 钥, 一 切 就 绪 后, 我 们 在 明 文 区 输 入 您 好, 欢 迎!, 点 击 发 送 按 钮 即 可 对 消 息 进 行 加 密 并 发 送 消 息 客 户 端 调 用 私 钥 即 可 进 行 解 密 并 显 示 出 明 文 这 里 我 们 可 以 设 置 最 大 连 接 数, 进 行 多 人 对 话 如 图 4.8 图 4.7 服 务 器 端 密 钥 生 成 界 面 32

37 第 四 章 大 模 数 的 rabin 密 码 保 密 通 信 软 件 的 实 现 图 4.8 服 务 器 聊 天 界 面 将 以 上 客 户 端 和 服 务 器 端 各 自 的 实 现 情 况 结 合 在 一 起 作 为 一 个 整 体 观 察, 即 可 看 出 这 就 是 一 次 完 整 和 成 功 地 具 有 消 息 保 密 功 能 的 网 络 通 信 过 程 至 此, 本 次 毕 业 设 计 系 统 实 现 部 分 的 任 务 圆 满 完 成 33

38 第 五 章 结 束 语 第 五 章 总 结 5.1 全 文 总 结 与 展 望 本 文 在 概 况 地 讲 述 了 网 络 信 息 安 全 技 术 的 现 状 及 研 究 的 意 义, 公 钥 密 码 系 统 等 相 关 技 术 的 研 究 现 状 及 其 应 用, 并 对 网 络 通 信 进 行 了 简 单 的 介 绍 详 细 介 绍 了 Rabin 密 码 系 统 加 密 解 密 实 现 过 程, 以 及 计 算 机 中 大 数 的 表 示 蒙 格 马 利 快 速 幂 模 运 算 Miller-Rabin 素 性 检 测 扩 展 欧 几 里 德 算 法 等 接 着 详 细 介 绍 了 Winsock 通 信 的 实 现, 首 先 Winsock 通 信 的 原 理 和 规 范, 然 后 描 述 了 客 户 端 / 服 务 器 模 型 及 各 编 程 参 数 的 使 用 说 明, 详 细 介 绍 了 Winsock 通 信 编 程 的 方 法 最 后 是 Rabin 密 码 保 密 通 信 软 件 的 实 现, 将 Rabin 密 码 系 统 和 Winsock 通 信 进 行 整 合, 并 对 软 件 界 面 进 行 了 介 绍 和 演 示 在 分 析 和 验 证 的 成 功 的 基 础 上, 使 用 C++ 编 写 了 Rabin 公 钥 密 码 体 制 的 软 件 界 面 操 作, 通 过 该 界 面 可 对 信 息 进 行 加 密 和 解 密 不 足 之 处 是, 该 程 序 对 公 钥 的 分 配 和 管 理 方 面 还 欠 完 善 Rabin 算 法 研 制 的 最 初 理 念 和 目 标 是 努 力 使 互 连 网 安 全 可 靠, 旨 在 解 决 DES 算 法 秘 密 密 钥 的 利 用 公 开 信 道 传 输 分 发 的 难 题 而 实 际 结 果 不 但 很 好 地 解 决 了 这 个 难 题 ; 还 可 利 用 Rabin 来 完 成 对 电 文 的 数 字 签 名 以 抗 对 电 文 的 否 认 和 抵 赖 ; 同 时 还 能 够 利 用 数 字 签 名 较 容 易 地 发 现 攻 击 者 对 电 文 的 非 法 篡 改, 以 保 护 数 据 信 息 的 完 整 性 现 在 为 止, 部 分 加 密 技 术 采 用 了 Rabin 算 法, 该 算 法 也 已 在 互 连 网 的 许 多 方 面 得 以 比 较 广 泛 应 用 此 外,Rabin 加 密 系 统 还 可 应 用 于 智 能 IC 卡 和 网 络 安 全 产 品 现 在, 日 益 激 增 的 电 子 商 务 和 其 他 因 特 网 应 用 需 求 使 公 钥 体 系 得 以 普 及, 这 些 需 求 量 主 要 包 括 对 服 务 器 资 源 的 访 问 控 制 和 对 电 子 商 务 交 易 的 保 护, 连 同 权 利 保 护 个 人 隐 私 无 线 交 易 和 内 容 完 整 性 ( 如 确 保 新 闻 报 道 或 股 票 行 情 的 真 实 性 ) 等 方 面 公 钥 技 术 发 展 到 今 天, 在 市 场 上 明 显 的 发 展 趋 势 就 是 PKI 和 操 作 系 统 的 集 成,PKI 是 Public Key Infrastructure 的 缩 写, 意 为 公 钥 基 础 设 施 公 钥 体 制 广 泛 地 用 于 CA 认 证 数 字 签 名 和 密 钥 交 换 等 领 域 即 使 如 此,Rabin 加 密 系 统 仍 然 动 摇 不 了 RSA 的 地 位, 且 新 的 密 码 方 案 层 出 不 穷 RSA 将 被 取 而 代 之 的 是 基 于 椭 圆 曲 线 的 密 码 方 案 (ECC 算 法 ) ECC 的 特 性 更 适 合 当 今 电 子 商 务 需 要 快 速 反 应 的 发 展 潮 流 此 外, 一 种 全 新 的 量 子 密 码 也 正 在 发 展 中 至 于 在 实 际 应 用 中 应 该 采 用 何 种 加 密 算 法 则 要 结 合 具 体 应 用 环 境 和 系 统, 不 能 简 单 地 根 据 其 加 密 强 度 来 做 出 判 断 因 为 除 了 加 密 算 法 本 身 之 外, 密 钥 合 理 分 配 加 密 效 率 和 现 有 系 统 的 结 合 性 连 同 投 入 产 出 分 析 都 应 在 实 际 环 境 中 具 体 考 虑 加 密 34

39 第 五 章 结 束 语 技 术 随 着 网 络 的 发 展 更 新, 将 有 更 安 全 更 易 于 实 现 的 算 法 不 断 产 生, 为 信 息 安 全 提 供 更 有 力 的 保 障 今 后, 加 密 技 术 会 何 去 何 从, 我 们 将 拭 目 以 待 5.2 心 得 体 会 刚 开 始 接 触 到 密 码 学 真 的 是 一 头 雾 水, 而 且 也 不 知 道 该 从 何 下 手, 最 基 本 的 方 法 还 是 查 找 资 料 吧! 所 以 一 伙 人 就 去 图 书 馆 找 自 需 要 的 书 籍, 我 们 互 相 讨 论, 彼 此 给 予 建 议 在 学 习 新 事 物 的 过 程, 从 茫 然 疑 惑 寻 找 推 测 失 望 努 力 成 就 心 得, 每 一 个 步 骤 都 是 一 种 学 习 在 导 师 的 督 促 下, 同 学 彼 此 间 都 能 感 到 互 相 往 前 进 的 压 迫 感, 互 相 勉 励 激 励, 无 形 的 驱 策 自 己 要 多 用 心 多 用 时 间 把 毕 业 设 计 完 成 好, 为 使 自 己 的 大 学 生 活 划 上 一 个 完 美 的 句 号 在 设 计 过 程 中, 我 通 过 查 阅 大 量 有 关 资 料, 与 同 学 交 流 经 验 和 自 学, 并 向 老 师 请 教 等 方 式, 使 自 己 学 到 了 不 少 知 识, 也 经 历 了 不 少 艰 辛, 但 收 获 同 样 巨 大 在 整 个 设 计 中 我 懂 得 了 许 多 东 西, 也 培 养 了 我 独 立 工 作 的 能 力, 树 立 了 对 自 己 工 作 能 力 的 信 心, 相 信 会 对 今 后 的 学 习 工 作 生 活 有 非 常 重 要 的 影 响 而 且 大 大 提 高 了 动 手 的 能 力, 使 我 充 分 体 会 到 了 在 创 造 过 程 中 探 索 的 艰 难 和 成 功 时 的 喜 悦 毕 业 设 计 不 仅 是 对 前 面 所 学 知 识 的 一 种 检 验, 而 且 也 是 对 自 己 能 力 的 一 种 提 高 通 过 这 次 毕 业 设 计 使 我 明 白 了 自 己 原 来 知 识 还 比 较 欠 缺 自 己 要 学 习 的 东 西 还 太 多 通 过 这 次 毕 业 设 计, 我 才 明 白 学 习 是 一 个 长 期 积 累 的 过 程, 在 以 后 的 工 作 生 活 中 都 应 该 不 断 的 学 习, 努 力 提 高 自 己 知 识 和 综 合 素 质 35

40 致 谢 在 我 的 学 生 生 活 即 将 结 束 之 际, 进 校 之 时 的 情 景 历 历 在 目 经 过 四 年 的 学 习 生 活, 身 边 的 老 师 同 学 都 成 为 了 我 的 良 师 益 友 这 四 年 的 快 乐 的 学 习 生 活 使 我 终 生 难 忘! 首 先 诚 挚 的 感 谢 导 师 杜 伟 老 师 和 王 国 才 老 师, 他 们 的 工 作 热 情 及 忘 我 的 严 谨 的 工 作 态 度 深 深 地 打 动 着 我 他 们 丰 富 的 专 业 知 识 和 工 作 经 验 给 我 提 供 良 好 的 学 习 资 源, 从 导 师 那 里 总 是 能 得 到 满 意 的 答 案 在 学 习 上 无 私 的 给 予 我 谆 谆 的 教 诲 和 鼓 励 另 外, 我 也 非 常 感 杨 政 宇 老 师 一 直 以 来 对 我 的 毕 业 设 计 的 指 导, 使 我 的 论 文 得 以 进 一 步 完 善 其 次 要 感 谢 吴 水 清 和 杨 健 两 位 师 兄 给 予 我 的 很 多 建 议 和 帮 助 在 资 料 缺 少 的 情 况 下, 帮 我 收 集 了 国 内 外 相 关 领 域 的 一 些 资 料 对 我 的 系 统 设 计 外 文 翻 译 等 提 出 了 修 改 意 见 第 三 要 感 谢 同 组 同 学, 因 为 有 你 们 的 帮 助, 我 的 论 文 得 以 顺 利 完 成 感 谢 你 们, 大 学 四 年 给 我 了 那 么 多 的 帮 助 与 鼓 励 36

41 参 考 文 献 [1] 汤 惟. 密 码 学 与 网 络 安 全 技 术 基 础. 北 京 : 机 械 工 业 出 版 社,2004 [2] 冯 登 国, 裴 定 一. 密 码 学 导 引 [M]. 北 京 : 科 学 出 版 社, 1999 [3][ 美 ] 斯 廷 森 D R. 密 码 学 原 理 与 实 践 [M]. 冯 登 国 译, 北 京 : 电 子 工 业 出 版 社, 2003 [4] 卢 开 澄. 计 算 机 密 码 学 [M]. 北 京 : 清 华 大 学 出 版 社, [5] 卿 斯 汉. 密 码 学 与 计 算 机 网 络 安 全 [M]. 北 京 : 清 华 大 学 出 版 社, 2001 [6] 周 玉 洁, 冯 登 国. 公 开 密 钥 密 码 算 法 及 其 快 速 实 现 [M]. 北 京 : 国 防 工 业 出 版 社, 2002 [7] 蒋 东 兴. Windows Sockets 网 络 程 序 设 计 大 全 [M ]. 北 京 : 清 华 大 学 出 版 社, 1999 [8]Menezes,A.J.,Van Oorschor,P. And Vanstone,S.,Ha ndbook of Applied Cryptography[M]. CRC Press,1996 [9] 赖 溪 松, 韩 亮, 张 真 诚. 计 算 机 密 码 学 及 其 应 用 [M]. 北 京 : 国 防 工 业 出 版 社 [10]L.Harn and T. Kiseler. Improved Rabin s scheme with high efficiency[j]. Electron. Lett, 25 may 1989 [11] 凌 捷, 刘 少 涛. 数 据 加 密 算 法 与 大 素 数 的 生 成 及 运 算. 广 东 工 业 大 学 学 报,2001,18(4):25-27 [12] 潘 承 洞, 潘 承 彪. 初 等 数 论 [M]. 北 京 : 北 京 大 学 出 版 社, 2003 [13] 秦 晓 东, 辛 运 帏, 卢 桂 章.Miller-Rabin 算 法 研 究 与 优 化 实 现 [J] 计 算 机 工 程, : [14] 贺 毅 朝, 沈 春 璞 等. Rabin 密 码 系 统 的 分 析 与 实 现 [J]. 河 北 省 科 学 院 学 报, 2002 [15] 王 晓 鹏,CP/IP 下 的 Socket 及 Winsock 通 信 机 制 [J]. 航 空 计 算 技 术,2004,6:126 [16] 刘 东 华. 网 络 与 通 信 安 全 技 术. 北 京 : 人 民 邮 电 出 版 社, [17] 徐 佑 军, 吴 元 保. 基 于 WinSock 的 网 络 实 时 通 信 程 序 的 设 计 [J]. 计 算 机 工 程,1999,25(11): [18]C.E.Sha nnon.communica tion theor y of secrecy systems[j].be j]system Technica l Journal,1949,28(4): [19]Schneier, B.,Applied Cryptography, Protocols, Algorithms and Source Code in C[M]. John Wiley and Sons, 1996 [20]Dr. Cetin K. Koc.ECE 575 Data Security and Cryptography[EB/OL]. ject/,2002. [21] 颜 篙 铭. 因 子 分 解 之 现 况 与 展 望 密 码 长 度 之 选 取, 信 息 安 全 通 信 [J]. 台 湾 : 台 湾 信 息 学 会,1995.1,3,