HKUST Institutional Repository

Transcription

1

2 (19) 中 华 人 民 共 和 国 国 家 知 识 产 权 局 (12) 发 明 专 利 *CN B* (21) 申 请 号 (22) 申 请 日 (30) 优 先 权 数 据 61/129, US (73) 专 利 权 人 香 港 科 技 大 学 地 址 中 国 香 港 九 龙 清 水 湾 (10) 授 权 公 告 号 CN B (45) 授 权 公 告 日 算 法 的 实 现. 计 算 机 工 程 与 应 用.2001,( 第 9 期 ), 林 小 竹 等. 一 种 改 进 的 LZW 压 缩 算 法. 计 算 机 工 程.2005, 第 31 卷 ( 第 14 期 ), 审 查 员 黄 捷 (72) 发 明 人 区 子 廉 周 建 涛 (74) 专 利 代 理 机 构 北 京 天 昊 联 合 知 识 产 权 代 理 有 限 公 司 代 理 人 陈 源 张 天 舒 (51)Int.Cl. H03M 7/30 ( ) H03M 7/00 ( ) G06F 9/44 ( ) (56) 对 比 文 件 CN A, , 全 文. US B1, , 全 文. CN A, , 全 文. 袁 占 亭 等. 数 据 通 信 中 文 本 元 件 无 损 压 缩 权 利 要 求 书 2 页 页 页 附 附 图 图 5 页 5 页 (54) 发 明 名 称 基 于 具 有 安 全 特 性 的 压 缩 技 术 来 编 码 数 据 的 系 统 和 方 法 (57) 摘 要 本 文 描 述 的 是 一 种 有 效 的 加 密 方 法 和 系 统, 该 方 法 和 系 统 具 有 改 进 的 基 于 随 机 性 的 安 全 特 性 该 方 法 和 系 统 采 用 随 机 字 典 插 入 和 随 机 字 典 排 列 以 及 由 流 密 码 器 所 产 生 的 密 钥 流 安 全 性 分 析 结 果 显 示, 与 现 有 的 编 码 方 法 相 比, 该 方 法 和 系 统 提 供 了 更 高 级 别 的 安 全 性, 而 没 有 引 入 任 何 编 码 效 率 的 损 失 CN B

3 权 利 要 求 书 1/2 页 1. 一 种 采 用 基 于 字 典 的 压 缩 技 术 对 数 据 进 行 编 码 的 方 法, 该 方 法 包 括 : 接 收 源 符 号 序 列 ; 根 据 随 机 插 入 采 用 源 字 符 表 对 所 述 字 典 进 行 初 始 化 ; 以 及 根 据 基 于 字 典 的 压 缩 技 术 对 所 述 源 符 号 序 列 进 行 编 码, 其 中 根 据 编 码 过 程 中 的 随 机 插 入 和 随 机 排 列 更 新 字 典 2. 根 据 权 利 要 求 1 所 述 的 方 法, 其 中 所 述 源 字 符 表 包 括 多 个 字 符, 所 述 字 典 包 括 多 个 条 目, 对 所 述 字 典 进 行 初 始 化 的 步 骤 还 包 括 将 所 述 多 个 字 符 中 的 每 一 个 随 机 地 分 配 给 所 述 多 个 条 目 中 的 一 个 3. 根 据 权 利 要 求 1 所 述 的 方 法, 其 中 所 述 源 符 号 序 列 至 少 包 括 第 一 字 符, 对 源 符 号 序 列 进 行 编 码 的 步 骤 还 包 括 : 将 所 述 第 一 符 号 添 加 到 字 符 串 ; 以 及 在 字 典 中 搜 索 具 有 所 述 第 一 符 号 的 字 符 串 4. 根 据 权 利 要 求 3 所 述 的 方 法, 所 述 源 符 号 序 列 还 包 括 第 二 符 号, 对 所 述 源 符 号 序 列 进 行 编 码 的 步 骤 还 包 括 : 确 定 字 典 中 存 在 对 具 有 第 一 符 号 的 字 符 串 的 匹 配 ; 以 及 将 第 二 符 号 添 加 到 具 有 第 一 符 号 的 字 符 串 5. 根 据 权 利 要 求 3 所 述 的 方 法, 对 所 述 源 符 号 序 列 进 行 编 码 的 步 骤 还 包 括 : 确 定 字 典 中 不 存 在 对 具 有 第 一 符 号 的 字 符 串 的 匹 配 ; 确 定 不 具 有 第 一 符 号 的 字 符 串 的 字 典 索 引 ; 在 字 典 中 随 机 选 择 一 个 空 条 目, 用 来 存 储 具 有 第 一 符 号 的 字 符 串 ; 以 及 将 所 述 字 符 串 初 始 化 为 第 一 符 号 6. 根 据 权 利 要 求 5 所 述 的 方 法, 在 字 典 中 随 机 选 择 一 个 空 条 目 来 存 储 具 有 第 一 符 号 的 字 符 串 的 步 骤 还 包 括 : 基 于 具 有 私 有 密 钥 的 键 控 散 列 函 数 来 选 择 所 述 空 条 目 7. 根 据 权 利 要 求 1 所 述 的 方 法, 还 包 括 : 将 字 典 布 置 成 具 有 多 个 列 和 多 个 行 的 二 维 矩 阵 ; 对 所 述 的 多 个 列 执 行 列 排 列 ; 以 及 对 所 述 的 多 个 行 执 行 行 排 列 8. 根 据 权 利 要 求 7 所 述 的 方 法, 还 包 括 对 所 述 多 个 列 中 的 每 一 列 进 行 循 环 移 位 9. 根 据 权 利 要 求 8 所 述 的 方 法, 其 中 用 第 一 随 机 偏 移 量 对 每 一 个 偶 数 列 进 行 循 环 移 位, 并 用 第 二 随 机 偏 移 量 对 每 一 个 奇 数 列 进 行 循 环 移 位 10. 根 据 权 利 要 求 7 所 述 的 方 法, 还 包 括 对 所 述 多 个 行 中 的 每 一 行 进 行 循 环 移 位 11. 根 据 权 利 要 求 8 所 述 的 方 法, 其 中 用 第 三 随 机 偏 移 量 对 每 一 个 偶 数 行 进 行 循 环 移 位, 并 用 第 四 随 机 偏 移 量 对 每 一 个 奇 数 行 进 行 循 环 移 位 12. 根 据 权 利 要 求 1 所 述 的 方 法, 还 包 括 通 过 组 合 已 编 码 的 源 符 号 序 列 与 流 密 码 器 所 产 生 的 密 钥 流, 来 产 生 编 码 数 据 流 13. 根 据 权 利 要 求 1 所 述 的 方 法, 其 中 所 述 压 缩 技 术 是 Lempel-Ziv-Welch 压 缩 Lempel-Ziv-Storer-Szymanski 压 缩 和 Lempel-Ziv-Ross 压 缩 中 的 一 种 2

4 权 利 要 求 书 2/2 页 14. 一 种 用 于 采 用 具 有 多 个 条 目 的 字 典 来 对 源 符 号 序 列 进 行 编 码 的 方 法, 所 述 源 符 号 序 列 包 括 多 个 符 号, 该 方 法 包 括 执 行 下 列 步 骤, 直 到 源 符 号 序 列 被 用 尽 为 止 : 将 字 符 串 初 始 化 为 源 符 号 序 列 的 一 个 符 号 ; 在 字 典 中 搜 索 与 所 述 字 符 串 匹 配 的 最 长 条 目 ; 执 行 (a)-(b) 直 到 在 所 述 字 典 中 不 能 找 到 对 该 字 符 串 的 匹 配 : (a) 确 定 字 典 具 有 与 该 字 符 串 相 匹 配 的 最 长 条 目 和 与 所 述 字 符 串 相 匹 配 的 最 长 条 目 的 字 典 索 引, (b) 将 来 自 源 符 号 序 列 的 另 一 个 符 号 添 加 到 该 字 符 串 ; 存 储 所 述 字 典 索 引 ; 随 机 地 选 择 字 典 中 的 条 目 来 存 储 不 具 有 所 述 另 一 个 符 号 的 字 符 串 ; 以 及 执 行 随 机 字 典 排 列 15. 根 据 权 利 要 求 14 所 述 的 方 法, 其 中 执 行 所 述 随 机 字 典 排 列 还 包 括 : 将 字 典 布 置 成 具 有 多 个 列 和 多 个 行 的 二 维 矩 阵 ; 以 及 对 所 述 的 多 个 列 和 所 述 的 多 个 行 执 行 随 机 字 典 排 列 16. 根 据 权 利 要 求 15 所 述 的 方 法, 还 包 括 : 用 第 一 随 机 偏 移 量 对 所 述 的 多 个 列 的 至 少 一 个 奇 数 列 进 行 循 环 移 位 ; 以 及 用 第 二 随 机 偏 移 量 对 所 述 的 多 个 列 的 至 少 一 个 偶 数 列 进 行 循 环 移 位 17. 根 据 权 利 要 求 16 所 述 的 方 法, 还 包 括 : 用 第 三 随 机 偏 移 量 对 所 述 多 个 行 的 至 少 一 个 奇 数 行 进 行 循 环 移 位 ; 以 及 用 第 四 随 机 偏 移 量 对 所 述 多 个 行 的 至 少 一 个 偶 数 行 进 行 循 环 移 位 18. 根 据 权 利 要 求 14 所 述 的 方 法, 还 包 括 : 产 生 用 于 随 机 插 入 和 随 机 字 典 排 列 的 密 钥 流 19. 根 据 权 利 要 求 18 所 述 的 方 法, 其 中, 基 于 具 有 与 密 钥 流 的 一 部 分 相 关 联 的 秘 密 密 钥 的 散 列 函 数 来 选 择 用 于 存 储 不 具 有 另 一 个 符 号 的 字 符 串 的 条 目 20. 根 据 权 利 要 求 14 所 述 的 方 法, 其 中 所 述 字 典 索 引 包 括 一 个 或 多 个 二 进 制 位, 所 述 方 法 还 包 括 : 产 生 表 示 源 符 号 序 列 的 字 典 索 引 流, 通 过 根 据 异 或 运 算 将 字 典 索 引 流 与 密 钥 流 进 行 组 合, 来 产 生 编 码 数 据 流 ; 以 及 输 出 编 码 数 据 流 3

5 1/10 页 基 于 具 有 安 全 特 性 的 压 缩 技 术 来 编 码 数 据 的 系 统 和 方 法 [0001] 对 相 关 申 请 的 交 叉 引 用 [0002] 本 专 利 申 请 要 求 于 2008 年 6 月 17 日 提 交 的 美 国 临 时 专 利 申 请 [0003] No.61/129,298 的 优 先 权, 通 过 引 用 将 其 整 体 并 入 本 文 技 术 领 域 [0004] 本 发 明 通 常 涉 及 数 据 编 码 和 加 密, 尤 其 是 涉 及 Lempel-Ziv-Welch 数 据 压 缩 背 景 技 术 [0005] Ziv 和 Lempel 在 1977 和 1978 年 的 他 们 的 具 有 里 程 碑 意 义 的 分 别 被 称 为 LZ77 和 LZ78 的 论 文 中 提 出 了 两 种 通 用 的 无 损 数 据 压 缩 算 法 从 那 以 后, 已 经 提 出 了 很 多 的 变 型, 例 如 Lempel-Ziv-Welch(LZW) Lempel-Ziv-Storer-Szymanski(LZSS) 以 及 Lempel-Ziv-Ross(LZR) 在 最 初 的 LZ78 的 这 些 变 型 中,Welch 于 1984 年 所 设 计 的 LZW 可 能 是 最 著 名 和 最 流 行 的 变 型 已 经 采 用 了 这 种 变 型 用 于 很 多 系 统 和 标 准 中, 并 作 为 一 种 选 择 用 于 TIFF 图 像 和 PDF 格 式 文 档 中, 这 些 系 统 和 标 准 包 括 UNIX 系 统 图 形 互 换 格 式 (GIF) 标 准 V.42 位 调 制 解 调 器 标 准 [0006] 一 种 保 护 由 LZW 算 法 所 产 生 的 位 流 的 简 单 方 法 是 采 用 流 密 码 对 其 进 行 加 密, 即, 对 LZW 位 流 和 密 钥 流 进 行 异 或 (XOR) 运 算 但 是, [0007] 这 种 机 制 极 易 受 到 选 择 明 文 攻 击 特 别 地, 攻 击 者 可 以 对 源 符 号 序 列 S 进 行 编 码 并 获 得 压 缩 的 和 加 密 的 位 流 Y 由 于 LZW 算 法 是 公 知 的, 攻 击 者 可 以 很 容 易 地 确 定 LZW 编 码 器 所 产 生 的 中 间 位 流 X 因 此, 通 过 进 行 运 算 ( 其 中 是 XOR 运 算 符 ), 可 以 容 易 地 恢 复 密 钥 流 可 替 换 地, 可 以 采 用 诸 如 在 高 级 加 密 标 准 (AES) 中 定 义 的 密 码 之 类 的 分 组 密 码 对 由 LZW 算 法 所 产 生 的 位 流 进 行 加 密 实 际 上, 这 种 加 密 机 制 提 供 了 非 常 高 的 安 全 性 能 但 是, 分 组 密 码 的 一 个 重 要 缺 陷 是, 由 于 分 组 密 码 通 常 涉 及 几 个 查 表 操 作 的 循 环 XOR 操 作 以 及 混 合 操 作, 与 流 密 码 相 比, 它 是 复 杂 的 且 计 算 速 度 缓 慢 另 外, 由 于 在 大 多 数 多 媒 体 应 用 中, 所 需 要 的 安 全 级 别 远 低 于 军 事 应 用 中 的 安 全 级 别, 不 需 要 采 用 AES 以 较 低 的 运 算 速 度 为 代 价 来 实 现 这 么 高 的 安 全 性 [0008] 有 一 些 利 用 LZW 算 法 其 自 身 来 实 现 高 安 全 性 能 的 现 存 系 统 和 方 法 例 如,Xie et al. Secure Lempel Ziv Compression with EmbeddedEncryption, Proc.SPIE,vol.5681, pp ,2005 描 述 了 一 种 基 于 LZ78 方 法 的 加 密 机 制 其 基 本 思 想 是 用 不 同 的 条 目 顺 序 建 立 多 个 字 典, 并 接 着 在 每 个 压 缩 步 骤 中 选 择 随 机 字 典 但 是, 这 些 现 有 的 方 法 仍 然 容 易 受 到 大 量 的 攻 击 ( 如 选 择 明 码 攻 击 ) 发 明 内 容 [0009] 本 文 描 述 的 是 在 多 媒 体 应 用 中 基 于 数 据 压 缩 技 术 进 行 数 据 加 密 的 系 统 和 方 法, 具 有 三 个 要 求 :(1) 没 有 编 码 效 率 损 失 ;(2) 高 安 全 性 ;(3) 加 密 成 本 应 当 大 致 等 于 采 用 其 后 接 流 密 码 器 的 标 准 LZW 的 方 案 的 加 密 成 本 4

6 2/10 页 [0010] 根 据 一 些 实 施 例, 该 系 统 包 括 低 成 本 的 改 进 的 LZW 模 块 和 流 密 码 器, 所 述 LZW 模 块 采 用 随 机 字 典 插 入 和 随 机 字 典 排 列 这 种 低 成 本 的 改 进 的 LZW 的 一 个 非 常 期 望 的 属 性 是 可 以 很 容 易 地 将 随 机 字 典 插 入 与 散 列 算 法 合 并 在 一 起, 这 种 散 列 算 法 已 经 广 泛 地 用 于 实 际 LZW 实 现 中 来 加 速 字 典 中 的 字 符 串 比 较 密 码 分 析 结 果 显 示, 在 不 影 响 编 码 效 率 的 情 况 下, 该 系 统 可 以 提 供 令 人 满 意 的 安 全 级 别 [0011] 根 据 其 他 的 一 些 实 施 例, 提 供 了 一 种 用 于 采 用 基 于 字 典 的 压 缩 技 术 对 数 据 进 行 编 码 的 方 法 这 种 方 法 包 括 :(1) 接 收 源 符 号 序 列,(2) 根 据 随 机 插 入 采 用 源 字 符 表 对 字 典 进 行 初 始 化, 以 及 (3) 根 据 基 于 字 典 的 压 缩 技 术 对 源 符 号 序 列 进 行 编 码 所 述 源 符 号 表 包 括 多 个 字 符 且 所 述 字 典 具 有 多 个 条 目 所 述 源 符 号 序 列 包 括 至 少 第 一 和 第 二 符 号 [0012] 在 字 典 的 初 始 化 过 程 中, 多 个 字 符 中 的 每 一 个 均 被 分 配 至 多 个 条 目 中 的 一 个 [0013] 在 编 码 过 程 中, 根 据 随 机 插 入 和 随 机 排 列 对 字 典 进 一 步 更 新 [0014] 对 源 符 号 序 列 进 行 编 码 的 步 骤 还 包 括 将 第 一 字 符 添 加 到 一 个 字 符 串, 并 在 字 典 中 搜 索 具 有 第 一 符 号 的 该 字 符 串 另 外, 编 码 步 骤 还 包 括 确 定 该 字 典 具 有 对 具 有 第 一 符 号 的 字 符 串 的 匹 配, 并 将 第 二 符 号 添 加 到 具 有 第 一 符 号 的 字 符 串 [0015] 可 替 换 地, 如 果 该 字 典 不 具 有 对 具 有 第 一 符 号 的 字 符 串 的 匹 配, 该 方 法 还 包 括 确 定 没 有 第 一 符 号 的 字 符 串 的 字 典 索 引, 在 字 典 中 随 机 地 选 择 一 个 空 条 目 来 存 储 具 有 第 一 符 号 的 字 符 串, 并 将 字 符 串 初 始 化 为 第 一 符 号 基 于 具 有 私 有 密 钥 的 键 控 散 列 函 数 来 选 择 空 条 目 [0016] 在 另 一 个 实 施 例 中, 该 编 码 步 骤 包 括 将 字 典 布 置 成 具 有 多 个 列 和 多 个 行 的 二 维 矩 阵, 在 所 述 多 个 列 上 执 行 列 排 列, 并 在 所 述 多 个 行 上 执 行 行 排 列 行 排 列 包 括 对 多 个 列 中 的 每 一 个 以 及 多 个 行 中 的 每 一 个 进 行 循 环 移 位 特 别 地, 用 第 一 随 机 偏 移 量 对 每 一 个 偶 数 列 进 行 循 环 移 位, 用 第 二 随 机 偏 移 量 对 每 一 个 奇 数 列 进 行 循 环 移 位, 用 第 三 随 机 偏 移 量 对 每 一 个 偶 数 行 进 行 循 环 移 位, 用 第 四 随 机 偏 移 量 对 每 一 个 奇 数 行 进 行 循 环 移 位 [0017] 在 又 一 个 实 施 例 中, 该 方 法 包 括 通 过 组 合 已 编 码 的 符 号 序 列 和 流 密 码 器 所 产 生 的 密 钥 流 来 产 生 编 码 数 据 流 [0018] 在 另 外 一 些 实 施 例 中, 压 缩 技 术 是 Lempel-Ziv-Welch 压 缩 Lempel-Ziv-Storer-Szymanski 压 缩 和 Lempel-Ziv-Ross 压 缩 中 的 一 种 [0019] 根 据 其 他 一 些 实 施 例, 提 供 了 一 种 计 算 机 可 读 媒 介, 其 上 具 有 存 储 的 计 算 机 代 码 该 计 算 机 代 码 包 括 计 算 机 可 执 行 指 令, 当 这 些 可 执 行 指 令 被 一 个 或 多 个 数 字 处 理 器 执 行 时, 提 供 采 用 基 于 字 典 的 压 缩 技 术 的 数 据 编 码 该 计 算 机 代 码 包 括 接 收 源 符 号 序 列 的 指 令 根 据 随 机 插 入 采 用 源 字 符 表 初 始 化 字 典 的 指 令 根 据 压 缩 技 术 对 该 源 符 号 序 列 进 行 编 码 的 指 令 以 及 在 编 码 过 程 中 根 据 随 机 插 入 和 随 机 字 典 排 列 对 字 典 进 行 更 新 的 指 令 [0020] 在 另 一 个 实 施 例 中, 源 符 号 序 列 包 括 多 个 符 号 而 且 计 算 机 代 码 还 包 括 将 第 一 符 号 添 加 到 字 符 串 的 指 令 确 定 字 典 不 具 有 与 具 有 第 一 符 号 的 字 符 串 相 匹 配 的 条 目 确 定 不 具 有 第 一 符 号 的 字 符 串 的 字 典 索 引 的 指 令 在 字 典 中 随 机 选 择 空 条 目 来 存 储 具 有 第 一 符 号 的 字 符 串 的 指 令 以 及 将 字 符 串 初 始 化 为 第 一 符 号 的 指 令 [0021] 根 据 本 发 明 的 其 他 一 些 实 施 例, 提 供 了 一 种 用 来 采 用 具 有 多 个 条 目 的 字 典 对 源 符 号 序 列 进 行 编 码 的 方 法 该 源 符 号 序 列 包 括 多 个 符 号 该 方 法 包 括 执 行 下 列 步 骤, 直 到 该 源 符 号 序 列 被 用 尽 为 止 :(1) 将 字 符 串 初 始 化 为 源 符 号 序 列 的 一 个 符 号,(2) 在 字 典 中 搜 5

7 3/10 页 索 与 该 字 符 串 匹 配 的 最 长 条 目,(3) 执 行 (a)-(b), 直 到 在 字 典 中 不 能 找 到 对 该 字 符 串 的 匹 配 :(a) 确 定 字 典 具 有 与 字 符 串 相 匹 配 的 最 长 条 目 和 与 字 符 串 相 匹 配 的 最 长 条 目 的 字 典 索 引,(b) 将 来 自 源 符 号 序 列 的 另 一 个 符 号 插 入 字 符 串 该 方 法 还 包 括 存 储 该 字 典 索 引 随 机 地 选 择 字 典 中 的 条 目 来 存 储 不 具 有 另 一 个 符 号 的 字 符 串 以 及 执 行 随 机 字 典 排 列 [0022] 在 一 个 实 施 例 中, 执 行 随 机 字 典 排 列 的 步 骤 还 包 括 将 字 典 布 置 成 具 有 多 个 列 和 多 个 行 的 二 维 矩 阵, 并 对 所 述 的 多 个 列 和 多 个 行 执 行 随 机 字 典 排 列 特 别 地, 该 方 法 包 括 : 用 第 一 随 机 偏 移 量 对 所 述 多 个 列 的 至 少 一 个 奇 数 列 进 行 循 环 移 位, 用 第 二 随 机 偏 移 量 对 所 述 多 个 列 的 至 少 一 个 偶 数 列 进 行 循 环 移 位, 用 第 三 随 机 偏 移 量 对 所 述 多 个 行 的 至 少 一 个 奇 数 行 进 行 循 环 移 位, 用 第 四 随 机 偏 移 量 对 所 述 多 个 行 的 至 少 一 个 偶 数 行 进 行 循 环 移 位 [0023] 在 另 一 个 实 施 例 中, 该 方 法 还 包 括 产 生 用 于 随 机 插 入 和 随 机 字 典 排 列 的 密 钥 流 基 于 具 有 与 该 密 钥 流 的 一 部 分 相 关 联 的 秘 密 密 钥 的 散 列 函 数, 选 择 用 于 存 储 不 具 有 另 一 个 符 号 的 字 符 串 的 条 目 [0024] 在 又 一 个 实 施 例 中, 该 方 法 还 包 括 产 生 表 示 源 符 号 序 列 的 字 典 索 引 流 按 照 异 或 运 算 将 字 典 索 引 流 与 密 钥 流 组 合 起 来, 产 生 编 码 数 据 流, 并 输 出 已 编 码 的 数 据 流 附 图 说 明 [0025] 图 1 是 我 们 所 提 出 的 机 制 的 示 意 图 ; [0026] 图 2 是 (a) 在 排 列 之 前 (b) 在 列 排 列 之 后 以 及 (c) 在 列 和 行 排 列 之 后 的 字 典 排 列 的 示 例 ; [0027] 图 3 是 用 以 实 现 图 1 中 的 编 码 方 法 和 系 统 的 计 算 系 统 的 视 图 ; [0028] 图 4 描 述 了 具 有 用 于 实 现 所 述 编 码 方 法 的 多 个 部 件 的 计 算 装 置 的 示 意 图 ; [0029] 图 5 描 述 了 采 用 基 于 字 典 的 压 缩 技 术 对 符 号 序 列 进 行 编 码 的 方 法 的 一 个 实 施 例 的 示 意 图 ; [0030] 图 6(a) 示 出 了 明 文 形 式 的 源 符 号 序 列 的 一 个 示 例, 且 图 6(b) 示 出 了 采 用 标 准 LZW 技 术 对 源 符 号 序 列 进 行 解 码 的 结 果, 所 述 源 符 号 序 列 是 基 于 本 文 所 述 的 方 法 进 行 编 码 的 具 体 实 施 方 式 [0031] 根 据 一 些 实 施 例, 在 图 1 中 示 出 了 用 于 采 用 压 缩 技 术 执 行 数 据 加 密 的 系 统 100 的 示 意 图 该 压 缩 技 术 可 以 是 任 何 采 用 字 典 的 技 术, 如 Lempel-Ziv-Welch(LZW) 压 缩 Lempel -Ziv-Storer-Szymanski(LZSS) 压 缩 以 及 Lempel-Ziv-Ross(LZR) 压 缩 为 了 便 于 讨 论, 在 图 中 示 出 了 改 进 的 LZW 压 缩 但 是, 本 文 所 描 述 的 发 明 不 局 限 于 LZW 压 缩, 且 本 领 域 技 术 人 员 在 阅 读 本 之 后, 可 以 将 本 发 明 修 改 为 采 用 字 典 的 其 他 压 缩 方 法 [0032] 根 据 图 1 中 所 示 的 实 施 例, 改 进 的 LZW 压 缩 具 有 一 些 安 全 特 性, 将 在 下 文 进 一 步 描 述 特 别 地, 系 统 100 包 括 两 个 基 本 部 件 : 用 于 产 生 密 码 流 的 密 钥 调 度 器 102, 以 及 用 于 执 行 LZW 编 码 的 改 进 的 LZW 模 块 104 在 另 外 一 些 实 施 例 中, 该 系 统 可 以 包 括 如 图 1 中 所 示 的 XOR 运 算 符 106, 用 于 基 于 密 钥 调 度 器 102 所 产 生 的 密 钥 流, 采 用 流 密 码 对 LZW 数 据 流 进 行 进 一 步 加 密 [0033] 与 现 有 的 基 于 LZW 的 编 码 技 术 不 同, 本 文 所 述 的 LZW 压 缩 采 用 随 机 字 典 插 入 以 及 随 机 字 典 排 列 来 获 得 改 进 的 针 对 各 种 攻 击 类 型 ( 如 纯 密 文 攻 击 已 知 明 文 攻 击 选 择 明 文 6

8 4/10 页 攻 击 和 选 择 密 文 攻 击 ) 的 安 全 性 如 图 1 所 示, 改 进 的 LZW 模 块 104 采 用 密 钥 调 度 器 102 所 产 生 的 密 钥 流 的 部 分 来 对 源 符 号 序 列 S 执 行 安 全 压 缩 接 着 由 XOR 运 算 符 106 对 改 进 的 LZW 模 块 104 所 产 生 的 位 流 X 和 密 钥 调 度 器 102 所 产 生 的 保 留 密 钥 流 执 行 XOR 运 算, 来 形 成 最 后 的 加 密 输 出 B 下 文 将 描 述 基 于 改 进 的 LZW 压 缩 而 提 供 数 据 加 密 的 系 统 和 方 法 的 细 b 节 在 下 文 的 描 述 中, 假 定 i 表 示 正 整 数, 且 (i) 2 表 示 具 有 长 度 b 的 i 的 二 进 制 表 示 [0034] 具 有 随 机 插 入 和 随 机 字 典 排 列 的 改 进 的 LZW [0035] 假 定 源 字 符 表 为 A = {a 1,a 2,...,a N }, 其 中 N 是 源 字 符 表 A 的 字 符 数 假 定 要 被 编 码 的 输 入 源 符 号 序 列 是 S = {s 1,s 2,...s M }, 其 中 M 是 源 序 列 S 中 的 符 号 数 为 了 便 于 讨 论, 采 用 b = 12 的 位 数 来 表 示 每 个 字 典 索 引, 即, 字 典 的 大 小 为 2 b = 4096 当 然, 在 阅 读 本 之 后,b 的 其 他 选 择 对 于 本 领 域 技 术 人 员 也 是 可 行 并 显 而 易 见 的 下 文 将 说 明 该 编 码 过 程 [0036] 根 据 图 4 所 示 的 实 施 例, 在 接 收 到 要 被 编 码 的 输 入 符 号 序 列 S 之 后 ( 步 骤 402), 采 用 源 字 符 表 对 字 典 进 行 初 始 化 ( 步 骤 404) 特 别 地, 构 建 具 有 2 b 个 空 条 目 的 字 典, 从 其 中 随 机 地 选 择 N 个 条 目 来 存 储 源 字 符 表 A 的 字 符 a i (1 i N) 换 句 话 说, 源 字 符 表 A 的 每 个 字 符 a i 随 机 插 入 或 填 充 在 字 典 中 [0037] 这 个 过 程 与 传 统 的 LZW 压 缩 不 同, 在 传 统 LZW 压 缩 中, 源 字 符 表 A 的 字 符 a i (1 i N) 被 分 配 给 该 字 典 的 第 一 个 N 个 条 目 传 统 LZW 方 法 的 一 个 缺 点 是 第 一 个 b-[log 2 N] 个 位 被 固 定 为 零 攻 击 者 可 以 采 用 这 个 信 息 来 恢 复 密 钥 流 的 部 分, 从 而 使 编 码 的 数 据 特 别 容 易 受 到 攻 击 相 反, 根 据 本 文 所 描 述 的 实 施 例, 由 于 是 基 于 随 机 插 入 对 字 典 进 行 初 始 化, 攻 击 者 很 难 恢 复 密 钥 流 [0038] 在 对 字 典 进 行 初 始 化 之 后, 采 用 改 进 的 LZW 方 法 来 对 源 符 号 序 列 S 进 行 编 码 ( 步 骤 406), 其 中 根 据 每 个 迭 代 中 的 随 机 插 入 对 LZW 机 制 的 字 典 进 行 更 新 特 别 地, 来 自 符 号 序 列 S 的 源 符 号 s j (1 j M) 被 输 入, 并 在 字 符 串 I 中 一 个 接 一 个 地 累 加 在 每 个 字 符 被 输 入 并 被 连 结 到 字 符 串 I 之 后, 对 字 典 进 行 搜 索 来 查 找 字 符 串 I 的 匹 配 只 要 在 字 典 中 找 到 字 符 串 I 的 匹 配, 就 继 续 连 结 和 搜 索 过 程 [0039] 在 某 一 点, 将 来 自 符 号 序 列 S 的 下 一 个 符 号 x 添 加 到 字 符 串 I, 使 得 搜 索 第 一 次 失 败, 即, 在 添 加 符 号 x 之 前 找 到 对 字 符 串 I 的 匹 配, 而 在 添 加 符 号 x 之 后 没 有 找 到 对 字 符 串 Ix 的 匹 配 接 着 执 行 后 续 的 步 骤 特 别 地, 确 定 指 向 添 加 x 之 前 的 字 符 串 I 的 匹 配 的 字 典 索 引 如 上 文 所 述, 该 字 典 索 引 由 b 个 二 进 制 位 所 表 示 接 着, 从 字 典 中 随 机 选 择 一 个 空 条 目 来 存 储 添 加 x 之 后 的 字 符 串 Ix 的 副 本 基 于 以 字 符 串 Ix 为 输 入 的 密 钥 散 列 函 数, 对 空 条 目 进 行 随 机 选 择 在 将 字 符 串 Ix 的 副 本 存 入 字 典 之 后, 将 字 符 串 I 初 始 化 为 符 号 x [0040] 根 据 一 个 实 施 例, 根 据 字 符 串 自 身 采 用 公 共 散 列 函 数 所 形 成 的 地 址, 将 新 字 符 串 Ix 存 储 在 字 典 中 的 位 置 中 这 种 策 略 极 大 地 提 升 了 字 典 搜 索 的 速 度 可 替 换 地, 采 用 具 有 秘 密 密 钥 的 私 有 散 列 函 数 来 确 定 用 于 存 储 字 符 串 Ix 的 地 址 换 句 话 说, 用 秘 密 密 钥 来 取 代 该 散 列 函 数 的 一 些 参 数, 使 得 在 没 有 这 些 秘 密 密 钥 的 情 况 下, 该 散 列 函 数 的 输 出 是 不 可 预 知 的 [0041] 根 据 本 发 明 的 另 一 个 实 施 例, 在 将 字 符 串 Ix 存 储 到 字 典 中 之 后, 如 下 对 更 新 的 字 典 执 行 随 机 排 列 [0042] 首 先, 将 字 典 布 置 成 具 有 2 b/2 个 列 和 2 b/2 个 行 的 二 维 矩 阵 两 个 索 引 集 合 被 定 义 7

9 5/10 页 为 G 1 = {1,3,...,2 b/2-1} 和 G 2 = {2,4,...,2 b/2 } 因 此, 首 先 对 这 个 二 维 矩 阵 执 行 循 环 的 列 排 列, 用 偏 移 量 c 1 对 那 些 具 有 索 引 m G 1 的 列 进 行 循 环 移 位, 其 中 c 1 是 一 个 随 机 数 且 0 c 1 2 b/2-1 用 偏 移 量 c 2 对 那 些 具 有 索 引 m G 2 的 列 进 行 循 环 移 位, 其 中 c 2 是 另 一 个 随 机 数 且 0 c 2 2 b/2-1 类 似 地, 分 别 用 偏 移 量 r 1 和 r 2 对 二 维 矩 阵 的 奇 数 行 和 偶 数 行 采 用 循 环 的 行 排 列 图 2 描 述 了 用 参 数 b = 4,c 1 = 2,c 2 = 3,r 1 = 1 和 r 2 = 2 进 行 随 机 字 典 排 列 的 示 例 图 2(a) 示 出 了 排 列 之 前 的 二 维 字 典, 图 2(b) 示 出 了 列 排 列 之 后 的 二 维 字 典, 且 图 2(c) 示 出 了 列 和 行 排 列 之 后 的 二 维 字 典 [0043] 重 复 上 述 的 搜 索 存 储 初 始 化 和 排 列 步 骤, 直 到 源 符 号 序 列 S 中 的 所 有 符 号 都 被 编 码 [0044] 根 据 一 些 实 施 例, 在 不 采 用 随 机 字 典 排 列 的 情 况 下 可 以 执 行 上 述 的 基 于 改 进 的 LZW 压 缩 的 数 据 编 码 和 加 密 方 法 [0045] 根 据 如 图 5 所 示 的 另 一 个 实 施 例, 提 供 了 方 法 500, 用 来 采 用 具 有 多 个 与 上 述 条 目 相 似 的 条 目 的 字 典 来 对 源 符 号 序 列 进 行 编 码, 其 中 该 源 符 号 序 列 包 括 多 个 符 号 如 图 5 所 示, 方 法 500 包 括 下 列 步 骤 在 步 骤 502, 将 一 个 字 符 串 初 始 化 为 来 自 符 号 序 列 的 多 个 符 号 中 的 一 个 在 步 骤 504 和 508, 方 法 500 执 行 字 典 搜 索 来 确 定 是 否 存 在 具 有 最 长 长 度 的 匹 配 字 符 串 的 条 目 如 果 发 现 了 这 种 匹 配, 方 法 500 接 着 前 进 到 确 定 匹 配 字 符 串 的 最 长 条 目 的 字 典 索 引 ( 步 骤 510), 并 将 来 自 源 符 号 序 列 的 另 一 个 符 号 添 加 到 该 字 符 串 ( 步 骤 506) 执 行 步 骤 , 直 到 没 有 该 字 符 串 的 匹 配 被 发 现 方 法 500 接 着 前 进 到 存 储 在 步 骤 510 中 所 确 定 的 最 近 的 字 典 索 引 ( 步 骤 512), 随 机 地 选 择 字 典 中 的 条 目 来 存 储 最 近 的 字 符 串 ( 步 骤 514), 并 对 更 新 的 字 典 执 行 随 机 的 字 典 排 列 ( 步 骤 516) 如 果 方 法 500 确 定 源 符 号 序 列 中 的 所 有 符 号 都 已 经 被 编 码 ( 步 骤 518), 那 么, 其 接 着 前 进 到 输 出 编 码 的 符 号 序 列 根 据 上 述 的 各 个 实 施 例, 编 码 的 符 号 序 列 包 括 一 系 列 的 字 典 索 引 [0046] 密 钥 调 度 器 [0047] 密 钥 调 度 器 102 的 作 用 是 产 生 用 于 改 进 的 LZW 和 XOR 运 算 的 必 要 的 密 钥 流 根 据 一 个 实 施 例, 流 密 码 ( 如 本 领 域 所 公 知 的 RC4) 用 于 这 个 目 的 RC4 密 码 的 一 个 优 点 是 在 密 钥 流 产 生 中 所 涉 及 的 软 件 和 硬 件 的 复 杂 度 非 常 低 可 替 换 地, 在 阅 读 本 之 后 本 领 域 技 术 人 员 很 容 易 理 解, 还 可 以 采 用 如 密 码 块 链 接 模 式 (Cipher BlockChaining mode) 中 的 数 据 加 密 标 准 密 码 (Data Encryption Standardcipher) 和 高 效 替 代 转 换 密 码 (Very Efficient SubstitutionTransposition) 之 类 的 其 他 流 密 码 [0048] 实 现 该 数 据 加 密 方 法 的 计 算 机 系 统 [0049] 图 3 示 出 了 其 中 可 以 实 现 本 发 明 的 合 适 的 硬 件 系 统 300 的 示 例 该 硬 件 系 统 300 只 是 合 适 的 操 作 环 境 的 一 个 示 例, 并 不 意 味 着 对 本 发 明 的 使 用 范 围 或 功 能 的 任 何 限 制 适 于 与 本 发 明 一 起 使 用 的 其 他 已 知 的 计 算 系 统 环 境 和 / 或 配 置 包 括 但 不 限 于 个 人 计 算 机 服 务 器 手 持 或 膝 上 装 置 多 处 理 器 系 统 基 于 微 处 理 器 的 系 统 可 编 程 电 子 器 件 网 络 PC 小 型 计 算 机 大 型 计 算 机 包 括 任 何 上 述 系 统 或 装 置 的 分 布 式 计 算 环 境 等 [0050] 参 照 图 3, 用 于 实 现 本 发 明 的 示 例 系 统 300 包 括 计 算 装 置 ( 如 装 置 110) 在 其 最 基 本 的 配 置 中, 装 置 110 通 常 包 括 处 理 单 元 120 和 系 统 存 储 器 130 根 据 计 算 装 置 的 精 确 配 置 和 类 型, 系 统 存 储 器 130 可 包 括 易 失 性 存 储 器 ( 例 如 RAM 132) 非 易 失 性 存 储 器 ( 例 如 ROM 131) 或 二 者 的 组 合 另 外, 系 统 300 还 可 以 具 有 海 量 存 储 单 元, 该 海 量 存 储 单 元 包 8

10 6/10 页 括 不 可 拆 除 的 存 储 器 141( 如 硬 盘 ) 和 / 或 可 拆 除 存 储 器 ( 如 通 常 的 软 盘 152 或 光 盘 (CD/ DVD)156 或 闪 存 存 储 器 装 置 ) 类 似 地, 系 统 100 还 可 以 具 有 输 入 装 置 ( 如 鼠 标 161 键 盘 162), 和 / 或 输 出 装 置 ( 如 显 示 单 元 191 打 印 机 196 和 扬 声 器 197) 系 统 100 的 其 他 方 面 还 包 括 采 用 有 线 或 无 线 媒 介 到 其 他 装 置 计 算 机 网 络 服 务 器 等 的 网 络 连 接 例 如, 系 统 100 还 可 以 包 括 用 于 通 过 广 域 网 (WAN)173 和 / 或 局 域 网 (LAN)171 与 远 程 计 算 机 180 进 行 通 信 的 调 制 解 调 器 172 和 网 络 接 口 170 另 外, 装 置 110 还 包 括 系 统 总 线 121, 该 系 统 总 线 121 电 学 上 连 接 至 处 理 单 元 120 各 种 存 储 器 模 块 输 入 / 输 出 装 置 以 及 上 述 的 其 他 功 能 部 件 因 此, 处 理 单 元 120 可 以 从 / 向 系 统 存 储 器 130 直 接 读 取 / 写 入 数 据 它 还 可 以 通 过 各 种 接 口 ( 如 存 储 器 接 口 140 和 150 用 户 输 入 接 口 160 网 络 接 口 170 视 频 接 口 190 以 及 输 出 外 围 接 口 195) 与 各 种 输 入 / 输 出 装 置 以 及 网 络 装 置 交 换 数 据 所 有 这 些 装 置 都 是 本 领 域 公 知 的 装 置, 在 这 里 不 需 要 对 其 进 行 长 篇 讨 论 [0051] 可 以 将 上 述 的 编 码 方 法 实 现 为 在 类 似 于 装 置 110 的 通 用 数 字 处 理 器 上 运 行 的 软 件 程 序 特 别 地, 用 于 实 现 该 编 码 方 法 的 软 件 程 序 可 以 包 括 用 于 指 示 装 置 110 的 各 个 部 件 执 行 上 述 方 法 步 骤 的 程 序 代 码 例 如, 这 些 程 序 代 码 可 以 包 括 提 供 密 钥 调 度 器 102 改 进 的 LZW 模 块 104 以 及 XOR 运 算 符 106 的 功 能 的 功 能 模 块 可 替 换 地, 该 软 件 程 序 可 以 包 括 分 离 的 程 序, 单 独 地 执 行 每 一 个 程 序 用 于 提 供 密 钥 调 度 器 102 改 进 的 LZW104 和 XOR 运 算 符 106 的 功 能 无 论 该 软 件 程 序 的 结 构 如 何, 这 些 程 序 代 码 通 常 包 括 用 于 接 收 包 括 源 符 号 序 列 和 其 他 编 码 参 数 的 输 入 数 据 的 指 令 用 于 初 始 化 字 典 的 指 令 用 于 根 据 上 述 改 进 的 LZW 对 符 号 序 列 进 行 编 码 的 指 令 更 具 体 地, 用 于 指 示 装 置 110 执 行 改 进 的 LZW 的 程 序 代 码 还 包 括 用 于 对 字 典 进 行 搜 索 来 查 找 字 符 串 I 的 匹 配 的 指 令 通 过 随 机 插 入 和 随 机 排 列 的 方 式 更 新 字 典 的 指 令 以 及 确 定 字 符 串 I 的 字 典 索 引 的 指 令 [0052] 采 用 标 准 编 程 语 言 ( 如 C/C++ C# Java 以 及 Basic) 可 以 实 现 该 软 件 程 序 可 替 换 地, 可 以 在 商 业 计 算 机 平 台 ( 如 Matlab) 中 实 现 该 软 件 程 序 可 以 是 独 立 于 装 置 110 上 运 行 的 其 他 程 序 的 可 以 由 装 置 110 所 执 行 的 独 立 的 程 序, 或 者 它 还 可 以 是 嵌 入 在 其 他 程 序 中 或 操 作 系 统 中 用 来 提 供 数 据 编 码 和 加 密 的 程 序 例 如, 它 可 以 嵌 入 到 UNIX 操 作 系 统 或 Adobe 文 档 处 理 程 序 中, 来 提 供 其 中 的 数 据 压 缩 和 加 密 用 以 实 现 编 码 系 统 100 的 软 件 程 序 可 以 位 于 不 可 拆 除 的 存 储 器 141 或 可 拆 除 存 储 器 ( 如 软 盘 152 或 CD/DVD 156) 上 一 旦 启 动 系 统 300 或 者 通 过 鼠 标 161 或 键 盘 162 接 收 用 于 执 行 该 软 件 程 序 的 输 入 时, 可 以 将 该 程 序 代 码 加 载 到 与 系 统 存 储 器 130 中 的 应 用 程 序 相 关 的 存 储 器 空 间 135 中 [0053] 另 一 方 面, 装 置 110 可 通 过 各 种 装 置 接 收 要 被 编 码 的 数 据 ( 如 图 1 中 的 源 符 号 序 列 S) 例 如, 可 以 将 数 据 存 储 到 不 可 拆 除 的 存 储 器 141 中, 并 加 载 到 与 系 统 存 储 器 130 中 的 程 序 数 据 相 关 的 存 储 器 空 间 137 中 可 替 换 地, 可 以 将 要 被 编 码 的 数 据 存 储 在 软 盘 152 或 CD/DVD 156 上, 并 通 过 存 储 器 接 口 150 和 盘 阅 读 器 151 或 155 将 其 读 入 存 储 器 空 间 137 还 可 替 换 地, 用 户 通 过 键 盘 162 或 通 过 网 络 接 口 170 从 远 程 计 算 机 180 输 入 要 被 编 码 的 数 据 根 据 另 一 个 实 施 例, 可 以 由 各 种 格 式 的 输 入 数 据 产 生 源 符 号 序 列 S 例 如, 输 入 数 据 可 以 是 ASCII 文 本 格 式 Microsoft Word 格 式 HTML 格 式 XML 格 式 PDF 格 式 或 其 它 合 适 的 专 用 格 式 [0054] 当 接 收 到 用 以 执 行 编 码 过 程 的 另 一 个 指 令 时, 从 存 储 器 空 间 135 中 读 出 并 由 处 理 单 元 120 解 释 包 括 这 些 指 令 的 程 序 代 码 这 些 程 序 代 码 可 以 指 示 处 理 单 元 120 来 加 载 以 之 9

11 7/10 页 前 接 收 并 存 储 在 存 储 空 间 137 中 的 数 据, 并 根 据 本 文 所 述 的 方 法 对 这 些 数 据 进 行 处 理 在 编 码 过 程 中, 可 以 将 中 间 数 据 和 包 括 密 钥 流 位 流 X 和 字 典 的 编 码 参 数 存 储 在 与 程 序 数 据 相 关 的 存 储 器 空 间 137 中, 或 者 存 储 在 处 理 单 元 120 的 内 部 寄 存 器 中 当 完 成 编 码 时, 可 将 已 编 码 的 数 据 流 B 存 储 在 存 储 空 间 137 中, 用 于 后 续 的 处 理, 或 者 被 其 他 的 程 序 所 利 用 可 替 换 地, 可 以 将 已 编 码 的 数 据 流 B 输 出 到 不 可 拆 除 的 存 储 器 141 或 可 拆 除 的 存 储 器 ( 包 括 软 盘 152 和 CD/DVD 156) 中 来 进 行 存 储 还 可 以 通 过 LAN171 上 的 网 络 接 口 170 或 WAN 173 上 的 调 制 解 调 器 172 将 其 发 送 到 远 程 计 算 机 180 上 还 可 替 换 地, 可 以 在 现 实 装 置 191 上 显 示 已 编 码 的 数 据 流 B 可 以 将 其 嵌 入 到 其 他 未 编 码 的 数 据 中, 以 使 已 编 码 的 数 据 流 B 与 内 容 已 被 编 码 且 访 问 这 些 内 容 需 要 得 到 授 权 的 表 示 一 起 被 显 示 为 无 意 义 的 文 本 [0055] 根 据 其 他 一 些 实 施 例, 还 可 以 在 形 式 为 插 入 到 通 用 计 算 机 系 统 中 的 计 算 机 卡 的 专 有 软 件 / 硬 件 系 统 上 实 现 本 文 所 述 的 编 码 方 法 和 系 统 可 替 换 地, 可 以 在 现 场 可 编 程 门 阵 列 (FPGA) 或 专 用 集 成 电 路 (ASIC) 中 实 现 [0056] 根 据 如 图 4 所 示 的 一 些 实 施 例, 提 供 计 算 装 置 400 来 执 行 上 文 所 述 的 编 码 方 法 的 各 种 实 施 例 特 别 地, 如 图 4 所 示, 计 算 装 置 400 包 括 用 以 接 收 输 入 的 源 符 号 序 列 的 接 收 模 块 402 用 于 对 编 码 过 程 中 所 采 用 的 字 典 进 行 初 始 化 的 字 典 初 始 化 装 置 404 以 及 用 来 基 于 该 字 典 对 输 入 的 符 号 序 列 进 行 编 码 的 编 码 器 406 [0057] 根 据 另 外 一 些 实 施 例, 接 收 模 块 402 可 以 包 括 图 1 所 示 的 各 种 接 口 和 存 储 器 装 置, 例 如 不 可 拆 除 的 存 储 器 接 口 140 与 存 储 器 141 可 拆 除 存 储 器 接 口 150 与 软 盘 152 和 CD/DVD 156 用 户 输 入 接 口 160 与 键 盘 162 和 调 制 解 调 器 172 以 及 网 络 接 口 170 接 收 模 块 402 还 可 以 包 括 其 中 存 储 了 用 于 后 续 编 码 的 源 符 号 序 列 的 系 统 存 储 器 130 例 如, 可 以 将 符 号 序 列 存 储 在 与 程 序 数 据 相 关 的 存 储 空 间 137 中, 之 后 可 以 将 所 述 程 序 数 据 读 取 并 加 载 到 处 理 单 元 120 中 [0058] 参 照 图 4, 通 过 采 用 用 于 执 行 初 始 化 过 程 的 程 序 代 码, 可 以 在 数 字 处 理 器 上 实 现 用 于 对 字 典 进 行 初 始 化 的 字 典 初 始 化 装 置 404 例 如, 可 以 采 用 处 理 单 元 120 来 执 行 一 组 用 于 执 行 字 典 的 初 始 化 过 程 的 程 序 代 码 特 别 地, 可 以 将 这 组 程 序 代 码 存 储 在 与 应 用 程 序 相 关 的 存 储 空 间 135 中, 并 读 入 存 储 单 元 120 用 于 执 行 [0059] 对 于 图 4 所 示 的 编 码 器 406, 还 可 以 在 与 实 现 了 初 始 化 装 置 404 的 处 理 器 不 同 的 数 字 处 理 器 上 或 在 如 处 理 单 元 120 同 一 个 数 字 处 理 器 上 实 现 特 别 地, 用 于 执 行 编 码 器 406 的 程 序 代 码 组 可 以 被 读 入 并 存 储 在 存 储 空 间 135 中, 接 着 由 处 理 单 元 120 连 续 地 读 取 并 加 载 用 于 对 源 符 号 序 列 进 行 编 码 [0060] 可 以 从 系 统 存 储 器 中 逐 个 读 出 要 被 编 码 的 源 符 号 序 列 的 符 号, 并 将 其 存 储 在 处 理 单 元 120 的 内 部 寄 存 器 中 另 外, 还 可 以 将 字 典 存 储 在 存 储 空 间 137 中, 并 将 其 加 载 到 处 理 单 元 120 中 以 用 于 执 行 编 码 步 骤 ( 例 如 字 典 搜 索 随 机 插 入 和 字 典 排 列 ) 可 以 将 在 每 个 编 码 迭 代 更 新 后 的 字 典 重 新 存 回 到 存 储 器 空 间 137 中 或 存 储 在 处 理 单 元 120 的 内 部 寄 存 器 中 此 外, 处 理 单 元 120 可 以 根 据 用 于 执 行 编 码 的 程 序 代 码 来 执 行 对 字 典 的 附 加 操 作 例 如, 处 理 单 元 120 可 以 采 用 内 部 指 针 或 存 储 器 地 址 对 字 典 中 的 每 个 条 目 进 行 检 索 可 以 安 排 这 些 指 针 和 存 储 器 地 址, 使 得 由 具 有 多 个 行 和 多 个 列 的 二 维 矩 阵 来 表 示 字 典 处 理 单 元 120 还 可 以 根 据 程 序 代 码 的 指 令 来 识 别 每 个 偶 数 或 奇 数 列 以 及 每 个 偶 数 或 奇 数 行, 接 着 如 根 据 该 编 码 方 法 的 各 种 实 施 例 的 描 述, 对 这 些 行 和 列 的 每 一 个 执 行 循 环 移 位 10

12 8/10 页 [0061] 安 全 分 析 [0062] 在 一 些 已 知 攻 击 的 情 况 下, 分 析 由 上 述 各 种 实 施 例 所 提 供 的 安 全 性, 并 将 显 示 这 些 实 施 例 比 基 于 传 统 的 LZW 压 缩 的 编 码 策 略 能 更 安 全 地 对 抗 这 些 攻 击 根 据 攻 击 者 可 以 访 问 的 信 息, 通 常 将 攻 击 分 成 几 种 类 型, 包 括 :(1) 纯 密 文 攻 击,(2) 已 知 明 文 攻 击,(3) 选 择 明 文 攻 击 和 (4) 选 择 密 文 攻 击 对 于 攻 击 模 式 (4), 攻 击 通 常 依 赖 于 安 全 性 分 析, 所 述 安 全 性 分 析 高 度 依 赖 于 解 码 器 中 的 误 差 纠 正 在 选 择 密 文 攻 击 的 情 况 下, 攻 击 者 不 能 访 问 本 文 所 述 的 编 码 机 制 的 信 息 因 此, 本 文 所 述 的 加 密 和 编 码 机 制 在 选 择 密 文 攻 击 下 是 安 全 的 关 于 攻 击 模 式 (2)( 已 知 明 文 攻 击 ), 对 于 本 领 域 技 术 人 员 而 言, 很 明 显 它 是 攻 击 模 式 (3)( 选 择 明 文 攻 击 ) 的 弱 化 版 本 因 此, 为 了 防 止 已 知 明 文 攻 击, 系 统 在 选 择 明 文 攻 击 下 是 足 够 安 全 的 出 于 这 些 原 因, 本 领 域 技 术 人 员 将 意 识 到, 在 分 析 上 述 方 法 和 系 统 的 安 全 性 能 时, 讨 论 攻 击 模 式 (1) 和 (3) 就 足 够 了 [0063] 纯 密 文 攻 击 [0064] 在 这 种 攻 击 情 形 下, 攻 击 者 只 能 访 问 加 密 位 流, 并 希 望 找 到 系 统 中 所 采 用 的 密 钥 由 于 攻 击 者 可 用 的 信 息 非 常 有 限, 非 常 普 通 的 攻 击 是 复 杂 性 涉 及 到 密 钥 空 间 的 强 力 攻 击 [0065] 根 据 上 述 实 施 例, 只 有 私 有 信 息 是 密 钥 调 度 器 102 中 所 采 用 的 密 钥, 该 密 钥 的 长 度 是 128 位 因 此, 密 钥 空 间 是 2 128, 这 保 证 了 令 人 满 意 的 安 全 级 别 [0066] 可 替 换 地, 攻 击 者 可 能 希 望 恢 复 在 改 进 的 LZW 104 和 OXR 运 算 符 106 中 所 采 用 的 密 钥 流 但 是, 可 以 显 示 出 这 个 任 务 甚 至 比 仅 采 用 强 力 攻 击 来 找 到 密 钥 调 度 器 102 中 的 密 钥 更 加 困 难 为 了 便 于 讨 论, 只 考 虑 随 机 字 典 插 入 由 于 可 以 将 字 符 a i (1 i N) 分 配 给 2 b 大 小 的 字 典 中 的 任 意 条 目, 随 机 字 典 初 始 化 和 随 机 字 典 插 入 的 密 钥 空 间 将 是 2 b! 在 b = 12 的 情 况 下, 密 钥 空 间 将 是 4096! 级 别 的, 这 是 难 以 置 信 地 大, 且 即 使 采 用 当 今 的 计 算 能 力 进 行 攻 击 也 是 极 度 困 难 的 因 此, 攻 击 者 宁 愿 采 用 具 有 复 杂 度 为 的 强 力 攻 击 来 找 到 密 钥 调 度 器 中 所 采 用 的 密 钥, 这 已 经 被 证 实 是 极 度 困 难 的 [0067] 因 此, 针 对 纯 密 文 攻 击 本 文 所 述 的 数 据 编 码 方 法 是 安 全 的 [0068] 选 择 明 文 攻 击 [0069] 在 这 种 攻 击 情 形 下, 允 许 攻 击 者 向 编 码 器 输 入 几 个 源 符 号 序 列, 并 得 到 相 应 的 位 流 [0070] 如 上 所 述, 在 不 采 用 随 机 字 典 排 列 的 情 况 下, 可 以 执 行 基 于 改 进 的 LZW 压 缩 的 数 据 编 码 和 加 密 方 法 但 是, 如 下 文 所 示, 这 并 是 一 个 容 易 受 到 选 择 明 文 攻 击 的 非 优 选 的 实 施 例 [0071] 特 别 地, 对 于 输 入 源 符 号 序 列 S = {s 1,s 2,...s M }, 给 定 对 应 的 位 流 为 B = B 1 B 2...B L, 其 中 B i 的 长 度 为 b 位, 且 L 是 由 改 进 的 LZW 所 产 生 的 索 引 的 数 量 假 定 与 初 始 字 典 中 的 符 号 s 1 相 关 的 索 引 是 i 1, 那 么 [0072] [0073] 其 中 K 1 是 XOR 运 算 符 106 中 所 采 用 的 密 钥 流 中 的 第 一 个 b 个 位 [0074] 如 果 攻 击 者 采 用 强 力 攻 击 来 破 解 具 有 2 b = 4096 复 杂 度 的 K 1, 那 么 攻 击 者 可 以 对 一 系 列 的 源 符 号 序 列 X j = {s j,x 2,...x M }(1 j N) 进 行 编 码, 其 中 x m A(2 m M) 是 任 意 符 号 由 于 K 1 是 通 过 强 力 攻 击 已 知 的, 攻 击 者 可 以 接 着 确 定 与 初 始 字 典 中 的 符 号 s j 相 关 的 所 有 索 引 应 当 注 意 的 是, 在 不 进 行 随 机 字 典 排 列 的 情 况 下, 由 于 新 的 字 符 串 Ix 的 11

13 9/10 页 随 机 插 入 将 不 会 影 响 已 经 填 充 进 字 典 的 条 目, 与 符 号 s j 相 关 的 索 引 不 会 随 时 间 改 变 因 此, 为 了 恢 复 K 2, 攻 击 者 可 以 类 似 地 对 另 一 个 符 号 序 列 X = {s j,s j,x 3,..x L } 进 行 编 码 假 定 s j 的 索 引 是 i j, 那 么, [0075] [0076] 由 于 采 用 强 力 攻 击 已 经 知 道 了 (i j ) 2 b, 而 且 B 2 是 公 知 的, 攻 击 者 可 以 唯 一 地 确 定 K 2 类 似 地, 攻 击 者 可 以 恢 复 所 有 后 续 的 K m 在 确 定 XOR 运 算 符 106 中 所 采 用 的 整 体 密 钥 流 K 之 后, 恢 复 改 进 的 LZW104 中 所 采 用 的 密 钥 流 就 很 简 单 了 因 此, 针 对 这 个 没 有 采 用 随 机 字 典 排 列 的 实 施 例 的 攻 击 的 复 杂 度 是 2 b = 4096 量 级 的, 在 当 今 的 计 算 能 力 下 这 是 完 全 可 以 接 受 的 [0077] 因 此, 采 用 随 机 字 典 插 入 和 随 机 字 典 排 列 的 编 码 是 一 种 更 优 选 的 实 施 例 如 下 文 所 示, 该 实 施 例 提 供 了 一 种 比 没 有 采 用 随 机 字 典 排 列 情 况 下 在 选 择 明 文 攻 击 下 更 加 严 密 的 安 全 性 [0078] 特 别 地, 在 对 采 用 了 随 机 字 典 插 入 和 随 机 字 典 排 列 的 实 施 例 的 攻 击 尝 试 中, 攻 击 者 还 可 以 采 用 等 式 (1) 所 示 的 关 系 和 强 力 攻 击 来 找 到 K 1 但 是, 与 上 文 一 些 实 施 例 中 所 述 相 同, 在 每 个 编 码 步 骤 之 后, 通 过 将 每 个 条 目 移 动 到 随 机 位 置 的 循 环 的 列 排 列 和 行 排 列 来 进 一 步 更 新 该 字 典 如 果 对 符 号 序 列 X = {s j,s j,x 3,...x L } 进 行 编 码, 并 将 随 机 排 列 应 用 于 该 字 典, 那 么, [0079] [0080] 其 中 i j 是 s j 在 行 和 列 排 列 后 的 新 索 引 且 K 2 是 K 的 第 二 个 b 个 位 由 于 排 列 偏 移 量 是 随 机 数, 因 此 攻 击 者 对 解 方 程 (3) 为 之 因 此, 攻 击 者 不 得 不 采 用 强 力 攻 击 来 确 定 K 2 或 i j 由 于 行 排 列 偏 移 量 和 列 排 列 偏 移 量 均 位 于 [0,2 b/2-1] 范 围 内, 采 用 强 力 攻 击 找 到 i j 的 复 杂 度 是 2 2b, 其 中 奇 数 列 和 偶 数 列 的 偏 移 量 是 不 同 的, 且 奇 数 行 和 偶 数 行 的 偏 移 量 也 是 不 同 的 由 于 破 解 K 2 的 复 杂 度 是 2 b, 比 2 2b 小, 攻 击 者 愿 意 瞄 准 K 2 应 该 注 意, 在 这 个 实 施 例 中 对 奇 数 和 偶 数 列 以 及 奇 数 和 偶 数 行 进 行 不 同 的 处 理, 因 为 这 有 助 于 破 坏 条 目 的 局 部 依 赖 性 换 句 话 说, 在 几 次 循 环 排 列 之 后, 彼 此 接 近 的 两 个 条 目 被 迅 速 地 隔 离 远 离 彼 此 这 使 得 攻 击 者 难 以 利 用 条 目 的 相 对 位 置 信 息 来 设 计 潜 在 的 攻 击 [0081] 如 上 所 述, 攻 击 者 不 得 不 采 用 强 力 攻 击 来 找 到 K 的 随 后 发 生 的 位 在 确 定 K 之 后, 恢 复 随 机 插 入 中 所 采 用 的 随 机 数 以 及 字 典 排 列 中 所 采 用 的 排 列 偏 移 量 是 很 简 单 的 因 此, 这 种 选 择 明 文 攻 击 的 复 杂 度 是 2 bl 量 级 的, 其 中 L 是 由 改 进 的 LZW 104 所 产 生 的 索 引 数 当 L 比 很 大 时, 攻 击 者 将 宁 愿 采 用 强 力 攻 击 来 找 到 密 钥 调 度 器 102 中 所 采 用 的 密 钥, 已 经 示 出 其 具 有 2 b! 的 复 杂 度, 并 因 此 难 以 攻 击 因 此, 采 用 随 机 插 入 和 随 机 排 列 的 实 施 例 确 保 了 相 应 编 码 的 数 据 针 对 选 择 明 文 攻 击 是 安 全 的 [0082] 编 码 效 率 [0083] 由 于 采 用 固 定 的 b 个 位 对 每 个 字 典 索 引 进 行 编 码, 最 终 压 缩 和 加 密 的 文 件 的 大 小 等 于 bl, 其 中 L 是 索 引 数 量 可 以 很 容 易 地 看 出, 随 机 插 入 和 随 机 字 典 排 列 只 改 变 了 索 引 的 分 布, 但 是 没 有 影 响 索 引 的 数 量 当 然,XOR 运 算 符 106 不 会 增 大 最 终 位 流 的 长 度 因 此, 可 以 发 现 最 终 的 位 流 与 由 标 准 LZW 所 产 生 的 位 流 具 有 相 同 的 大 小 换 句 话 说, 没 有 编 码 效 率 的 损 失 [0084] 实 验 结 果 12

14 10/10 页 [0085] 下 文 所 描 述 的 是 说 明 该 编 码 方 法 和 系 统 的 有 效 性 的 示 例 采 用 作 为 最 常 用 的 软 件 流 密 码 的 流 密 码 RC4 来 实 现 密 钥 调 度 器 位 16 进 制 密 钥 是 9F7AC6DC 改 进 的 LZW 104 采 用 了 由 RC4 所 产 生 的 密 钥 流 来 在 字 典 上 执 行 随 机 插 入 和 随 机 字 典 排 列 由 RC4 密 码 所 产 生 的 密 钥 流 还 可 以 用 于 XOR 级 106, 通 过 对 来 自 改 进 的 LZW 104 的 位 流 进 行 编 码 来 产 生 最 终 的 位 流 [0086] 图 6(a) 示 出 了 要 被 编 码 和 加 密 的 一 段 ASCII 字 符 当 然, 如 果 将 图 1 所 示 的 系 统 100 所 产 生 的 位 流 B 输 入 到 授 权 的 采 用 具 有 正 确 密 钥 的 适 当 编 码 策 略 的 解 码 器, 已 解 码 的 符 号 序 列 与 图 6(a) 所 示 的 原 始 序 列 完 全 相 同 但 是, 如 果 将 系 统 100 所 编 码 的 位 流 B 输 入 到 标 准 的 LZW 解 码 器, 解 码 的 符 号 序 列 如 图 6(b) 所 示, 是 完 全 无 意 义 的 序 列 应 该 注 意, 标 准 LZW 解 码 器 由 于 不 同 的 实 现 而 有 一 些 差 异 例 如, 考 虑 ASCII 字 符 表, 如 果 第 一 个 索 引 大 于 255, 一 些 实 现 只 是 声 明 一 个 严 重 错 误, 而 不 输 出 任 何 的 符 号 序 列 根 据 一 些 实 施 例, 在 这 种 情 况 下 解 码 器 仍 然 继 续 解 码 可 以 注 意 到, 在 采 用 标 准 LZW 解 码 的 符 号 序 列 中, 有 很 多 的 重 复 符 号 这 是 因 为 在 标 准 LZW 中 如 果 索 引 所 指 的 条 目 为 空, 该 解 码 器 将 输 出 与 第 一 符 号 连 接 的 最 后 的 解 码 符 号 串 M.Nelson, LZW Data Compression, us/1989/10/01/lzw-datacompression/ 有 关 于 标 准 LZW 的 更 多 细 节 [0087] 虽 然 在 本 文 中 公 开 了 发 明 的 注 入 - 增 强 注 入 - 锁 定 分 频 器 的 一 些 示 例 实 施 例, 这 不 意 味 着 对 本 发 明 范 围 的 必 然 限 制 因 此, 不 脱 离 权 利 要 求 的 原 理 或 范 围 的 简 单 改 进 或 变 型 仍 然 处 于 本 发 明 的 范 围 内 [0088] 所 有 本 文 引 用 的 参 考, 包 括 出 版 物 专 利 申 请 以 及 专 利, 均 通 过 引 用 合 并 到 与 单 独 地 且 专 门 地 将 每 个 参 考 通 过 引 用 合 并 而 且 在 这 里 以 全 文 阐 述 的 相 同 的 范 围 [0089] 在 描 述 本 发 明 的 上 下 文 中 ( 特 别 是 如 下 权 利 要 求 的 上 下 文 中 ) 将 所 采 用 的 术 语 一 个 一 种 和 这 种 以 及 类 似 的 指 示 对 象 解 释 为 涵 盖 单 数 和 复 数, 除 非 在 本 文 中 另 行 说 明 或 与 上 下 文 的 内 容 明 确 地 出 现 了 抵 触 将 术 语 包 含 具 有 包 括 以 及 含 有 解 释 为 开 放 性 术 语 ( 如 意 思 是 包 括 但 不 限 于 ), 除 非 另 行 说 明 本 文 所 述 的 值 的 范 围 仅 仅 用 来 作 为 对 落 在 范 围 内 的 每 个 分 离 值 单 独 引 用 的 速 记 方 法, 除 非 在 文 中 另 行 说 明, 且 如 果 每 个 分 离 值 在 本 文 中 被 单 独 引 用, 将 该 值 均 合 并 到 本 中 可 以 以 任 何 合 适 的 顺 序 执 行 本 文 所 述 的 所 有 方 法, 除 非 在 文 中 另 行 说 明, 或 者 与 上 下 文 的 内 容 明 确 地 出 现 了 抵 触 本 文 提 供 的 所 采 用 的 任 何 示 例 和 所 有 示 例 或 示 例 语 言 ( 例 如 如 ) 仅 仅 是 为 了 更 好 地 说 明 本 发 明, 而 不 是 要 对 本 发 明 的 范 围 提 出 限 制, 除 非 另 行 声 明 中 的 任 何 语 言 都 不 解 释 为 表 示 本 发 明 的 实 践 要 素 的 任 何 非 声 明 元 素 [0090] 本 文 对 本 发 明 的 优 选 实 施 例 进 行 了 说 明, 包 括 发 明 人 所 知 的 用 于 执 行 本 发 明 的 最 佳 模 式 本 领 域 技 术 人 员 在 阅 读 前 述 之 后, 各 种 优 选 实 施 例 的 变 型 将 变 得 很 明 显 发 明 人 希 望 技 术 人 员 以 合 适 的 方 式 采 用 这 些 变 型, 且 发 明 人 希 望 可 以 以 本 中 没 有 明 确 说 明 的 方 式 来 实 践 本 发 明 因 此, 本 发 明 包 括 所 附 的 权 利 要 求 所 列 举 的 主 题 的 所 有 变 型 和 等 价, 这 是 适 用 的 法 律 所 允 许 的 此 外, 本 发 明 包 含 上 述 元 素 所 有 可 能 的 变 型 的 任 何 组 合, 除 非 在 文 中 另 行 说 明, 或 者 与 上 下 文 的 内 容 明 确 地 出 现 了 抵 触 13

15 附 图 1/5 页 图 1 图 2 14

16 附 图 2/5 页 图 3 15

17 附 图 3/5 页 图 4 16

18 附 图 4/5 页 图 5 17

19 附 图 5/5 页 图 6 18