数字签名和鉴别

数 字 签 名 和 鉴 别 � � � ! ∀ # ∃ % &∋ 译 者 说 明 数字签名是一种验证文件可信性的技术 , 目前在几个发达的资本主义国家 中以商业交易文件为主要对象进行着基础性的研究 , 其目的和手书签名一样 , 是为防止对文件的抵赖、 伪造、 涂改和冒充 , 其优点是易于输入到 电子计算机 中处理和存储 。 它目前主要引用的是密码技术 , 但用法和作通信保密不完全相 同 。 这种密码技术在社会主义国家中是否有用 , 是否可以推广到在其他方面使 用 , 尚需探讨 。 摘 要 由 一 个 数 据处理系统连接起来的许 多用户对参加交易 , 采用的书确保每 个用户防备另一方或第三者的有害行为 , 并为解决争端提供了根据 。 要预防的威胁 包括( ) &∗ 抵赖 , )++∗ 伪 造 , ) ++ +∗ 修改 , ) &,∗ 冒充。 本文系统地阐述对交 易进行核实的检验 , 并考查近期提出 的解决办法。 + 、 绪 言 我们假定有用户对之间的下述形式的 交易 ( 用户�对经纪人 − ( 购买我的账户⋯ ⋯ . /0股份有限公司的股份 , 不超过⋯⋯ 美元 。 银行�对银行 − ( 账户 1 2 3 + 3 4 赊账总 数+ , 5 5 5美元。 在正常商业交易中 , 采用了协议书 , 译者注 ( 本文是 6− 7 高级工程师 � 。 。 ! ∀ # ∃ % &∋ 在北京的讲稿 。 � � � ! ∀ # ∃ % &∋ 主要从事概率论方 面的工作 , 但也搞过密 码 , 曾参加过 8 9 : 的算法设计 。 以确保每个用户防备他方或第三者的有害 行为 ; 如果发生了争论 , 协议书中拟定的 关于解决这些争端的调解程序是协议各方 一致同意的。 我们正在朝着一个 电子数字 通信的时代迅速前进 , 在那个时代 , 关于 一切货物和设施的交易 , 都可以由远距程 序控制线路把所有用户连接起来的数据处 理系统来完成 。 专用通信的常用部件一物 理的 , 光学的 , 音频的都可 以不用了 。 电 子消息是容易被伪造或修改的。示交易 ( 银行 �对银行− ( 账户 1 2 3 + 3 4 赊账总 数6 , 5 5 5美元 的这个消息中的 < 、 + 序列容易被纂改 , 以致于 + , 5 5 5美元改成了+ , 5 5 5 , 5 5 5美元或 者账户号1 2 3 + 3 4被改换成了= > 2 2 4 + 。 正常 交易中的那些协议书 , 对于由一个数据处 理系统所管理的交易来说 , 是必须详细规 定的。 协议书通过检验和合理的理解 , 可 以预防或阻止产生错误 。 在本文中 , 我们 系统地阐述对交易检验系统的具体要求 , 同时考查某些人所提出的解决这个间题的 办法。 ? 。 威 胁 办理从发起人 ) 用户 � ∗ 到 接 收者 ) 用户 − ∗ 的一笔交易就是把数据给这些 用户的某种传送过程 。 数据可以表示银行 同业之间的资金转移 , 自动化买卖或者高 度 机密材料的电子邮寄 , 存货的销售 。 所 有交易参加者要求预防的各种有害行为包 括 ( 抵赖 发起人随后否认有任何交易是属于 自己的。 伪造 接收者随便捏造一笔交易 。 修改 接收者改换一笔先前有效的交易 。 胃充 一个用户企图伪装成另一个用户 。 3 。 交易检验有什么要求 ≅ 为 了验证从用户 �到用户 − 的数据 , 协议书应当包含下面几个要点 ( ) + ∗ 发起人 )用户 � ∗ 必须与数 据合为一体构成一个数字签名。 签名就是 一种可加密信息 , 它依赖于这数据 、 交易 的接收者和只有该发起人才知道的秘密信 息 ! Α 。 : 6 Β! 人 , 8 � Χ � , Δ Ε ∀ Φ − Γ表示 由 用 户� 给用户−的数据签名。 ) ? ∗ 给用户 − 的一个正确的数据 签名 : 6 健! 人 , 8 � Χ � , Δ Ε % Φ − Γ , 在没 有 ! � 的 情况下 , 一定是事实上不可能构 造的。 ) 3 ∗ 用户 − 必须能够验证 :6 福! � , 8 � Χ � , Δ Ε% Φ − Γ是由用户 � 签 署 的一个正确的数据签名 。 ) 4 ∗ 检验过程必须包含 “时间” 相关性 , 以防止重新用时间上失效了的消 息 。 讨论 ( 的数据加密 。 在变换 Δ Ε % Φ − , 8 � Χ � 一, : 6 Β! 人 , 8 � Χ � , Δ Ε% Φ − Γ 中的秘密元素 ! � 称为密钥。 在任何 密码体制的实际系统中 , ! 、属于 一 个称之 为密钥空间的有 限集 ! , 密钥空间是由一 系列字母一数字符号的有 限序列组成的。 集合! 和变换 8 � Χ � , Δ Ε % Φ − , : 6 遥! ; , 8 � Χ � , Δ Ε % Φ − Γ 的函数形式是公开信息 。 秘密是 由用 户 �所选取的!的特殊元素 ! � 。 由于 ! 是 有限的 , 所以全部密钥的穷举试验就给出 了相应的变换对 ( 8 � Χ � ; , Δ Ε% Φ − ( , 、 : 6 义! , , 8 � Χ � ; , Δ Ε % Φ − ; Γ 通常可以由对手推导出一个确定 的 ! 人 。 如果! 的基底充分大且设 ! Α 是 随 机选取 的 , 则密钥的穷举试验是不切实际的 。 那 么 , 可以说 , 在没有密钥的情况下 , 要构 造一个有效的签名 , 事实上是不可能的 。 这意味着 , 没有! 人时 , : 6 丈! � , 8 � Χ � , Δ Ε % Φ − Γ 的确定 , 在计算上 , 等价于密钥 试验 。 + 。 一笔签字交易就是采用密码变换 ? > ? 。 在信息处理系统中 , 设备 、 程 序和存贮器的存取 , 通常是由通行字控制 的 。签名是通行字的变形 , 其函数形式依赖 于交易的发起人 、 接收者和交易的内容 , 3 � 为了检验一笔新的交易 , 每笔 交易的签名都必须不同 , 以便防止重新用 以前的签名 。 数字签名和手写签名是不同 的 。 手写签名常常是时间和数据两者是独 立的 。 数字签名和手写签名的相似之处在 于 ( 两者都是从物主所特有的特征中产生 出来的 。 4 。 虽然接收者不能构造一个有效 的签名 , 但接收者必须能够检验一个签名 是否正确 。 在许多流行的商业交易中一例 如 , 纽约州货物的出售一一个受托的无关 的第三者 ) 公证人 ∗ 起着这种作用 。 4 。 鉴别 根据 Η %ΙΕ ϑ % Φ 词典 , 鉴别就是一种 程序 , 通信中的每个用户利用这种程序来 检验另一用户的身份 。 鉴别程序中隐含的 成份就是某种保密的元素 , 该通信中的参 与者凭借这种信息对另一用户进行识别 , 判认是他或她本人 。 在许多日常活动中 , 我们鉴别 自己使用签名的情况 ( · 验证时的签名或者司机的执照 , · 过国境时的一张护照的相片 , 以便让发起人能被一个数据处理系统中的 接收者鉴别。 ) + ∗ 发起人 ) 用户� ∗ 必须提供 识别消息 � Δ Χ Κ Β! � , Δ Ε % Φ − Γ给接收者 ) 用户 − ∗ , 消息� Δ Χ Κ Β! � , Δ Ε % Φ − Γ依 赖于只有用户�知道 的秘密信息 ! � 。 ) ? ∗ 由用户 � 给用户 − 的有效识 别消息 � Δ Χ Κ 笼! � , Δ Ε% Φ − Γ , 当没有密 钥 ! � 时 , 必 须是 事实上不能构造的。 ) 3 ∗ 用户 − 为 了验 证 识别消息 � Δ Χ Κ Β! Λ , Δ Ε % Φ − Γ确实发自用户 � , 必 须有一个专门程序 。 ) 4 ∗ 鉴别程序必须有 “时间” 概 念 , 以便防止使用以前的识别消息 。 我们指出 , 鉴别和交易检验都包含了 类似的环节 ; 一个数字签名就是带有附加 条件的识别消息 , 附加条件取决 于交易的 内容。 2 。 密码预备知识 设 0 二 二 笼< , + , ��� , ∋ 一 + Γ表示∋ 个字母的字母表 。 Μ 二 , 。 表示字母的 # 一 字 母组全体的集合 Ν Ο ) Ν 。 , Ν ( , Ν ( , ⋯ , Ν 。 , + ∗ Ν ( 任0 。 0 二上的密码变换Χ 是一族一一映射 , Χ Ο 笼Χ ‘”’( + 三 # Π 二 Γ Χ )# ∗ ( 0 二 , 。 , 0 二 , 。 Θ 映射 Χ )# ∗ ( Ν Ο ) Ν 。, Ν Ρ , ⋯ , Ν 二 , . ∗ ‘ Χ )# ∗ ) Ν ∗ Ο / Ο ) / 。 , / ; , ⋯ , / 。一 ∗ 把明文# 一字母组 . 加密成密文 # 一字母组 / 。 一种密 码 体 制 就是 一 密 码变 换族 Χ Ο Β Χ ! ( ! 〔! Γ, 这种密码变换由取值于密钥空间! 的密钥 ! 作标记 。 我们并不强求不同 的密钥对应于不同的变换 。 用8 9 : 表示的数据加密标准是用! 二 0 ( , 。 � 对字母表 0 ( 。 � Ο 0 ( , � ‘定义的一种密码 体制。 我们令 / Ο 8 9 :王! , Ν Γ 表示用有密钥! 的 8 9 :对 Ν 加密的密文。 8 9 : 可 以扩展 , 以便对长为Σ的二进位组的明 文加密 , 当Σ全 1 ) 但无需 1 的倍数 ∗ 时 , 可用链式循环法进行明文的加密。 设 ? = ) Ν ∗ Ο ) Ν )∀ ∗ , Ν ) + , , ⋯ , Ν ), 一 ’∗ ∗ ) / Τ Υ ∗ 表示链接明文块 ΒΝ ‘, ’( 。三 &Π 丫 Γ的明文 Π . ∗ , 前丫 一 Υ块是每块长为 1 的二进 位 明 文信息组 , 最后 一块 Ν ‘丫一 ‘’) 若存在 ∗ 属于长为ς 的二进位明文信息组 , <兰ς Π 1 。 用 具有密钥! 和初始循环值 6Ω Ξ 〔0 ( , � ‘的8 9 :对Ν 加密的密文是用 8 9 :ΩΚ 福! , 6Ψ , , ) Ν Τ Γ 二 Π / Τ Ο ) / , 。 , / )’ 、, ⋯ , / ), 一 ‘∗ ∗ 兰‘” Ο 8 9 : Β! , 兰“ , �竺‘一 ‘’卜 �‘ ! ∀ 一 #, 兰‘一 ” “ ∃ % & ∋ ( , ) 二 ∗ ‘丫) + , − ./ ,〔0 − 1 23 , ∋ ( 了一 ‘)卜〕 定义的 , 其中+ 表示交叉或 ( 矢量空间加法 ) , , − . / , 455 ·〕表示〔⋯〕的二进位组最左 , 位 。 当我们把长度 6七 7 ( 二进位 ) 的明文 ∗ 的密文写为0 − 12 3 , ∗ 8的时候 , 我们正 是指按照0 − 19 : 将 0 − 1 扩展 , 在此扩展中 , ∃ 9 &是未被详细说明的。 密码分析的基本间题是 ; ( < ) 从密文恢复明文和 =或密钥 , 或者 ( > ) 从对应的明文和密文恢复密钥 。 任何密码体制可以通过下述方法的综合进行分析 。 ( < ) 密钥试探一把密钥空间中的所有密钥作穷举试验 , 直到获得可读明文 , ( > ) 频率分析一列出明文和密文字母出现的频率表 , ( ? ) 变换 2/ 3 8的分析一弋/ 3 8揭示出明文 ∗ 、 密文 ∋ 和密钥3之间的关系 。 0 − 1编码中的明文字母是扩充的二进制编码的十进制交换码 ( − ≅ 4 Α Β Χ Α Χ Δ Β “∀ Ε 9 Φ Χ Α Χ 0 Α 9 Γ Η # ∃ Β 4 Α ∀ Α Ι Η Β ϑ Α 9 。 Χ Α ) 的 7 一字母组 , 事实上 , 不可能出现大约 Κ ≅ <Λ ’压 个 ( 可印刷的 ) 7 一字母组的频率表。 已经发现并且公开了; 从对应明文 、 密文中 恢复 密钥的那些明文 、 密文和密钥之间互相独立 。 密钥量超过密钥空间 3 恰含有的 > “ “种密 钥的争论 已有所考虑 。 虽然可以构造 ( 花大量代价 ) 一种特殊用途的信息处理机 , 以便 对密钥作穷举试验 , 但是用0 − 1的第二个ΜΝ 位密钥对密文再加密就可以使这个机器无用 , 因 此作这样的机器是不必要的。 Ν 。 签名的两个例子 例 Ν 5 < ; 链式签名 设 ( 0 Ο / Ο , Π ; Α , 6 、 。 。 ) Θ ( ∗ “ , ∗ ( ” , 用具有链锁作用的0 − 1对 ( 0 Ο / Ο , Π ‘ 。 , 6 5 Γ 。 0 − 123 , ( 0 Ο / Ο , Π ; 。 , 6 ; 二 。 ) 8 二 ( ∋ ‘“’, ∋ “’二 0 − 1 23 , ∗ ‘, ) + ∋ “ 一 ’) 8 Φ三 ! 6 ∋ 。 Θ 0 − 123 , ∗ 。 ’+ ∃ 9 Ρ 8 >7 二 ‘ , ∗ (6 一 < ) ) 进行加密 ; ∋ ‘’) , ⋯ , ∋ (卜一 # ) 并定义: 6 Β! , 8 � Χ � , Δ 。 % , Σ 。 , 。Γ Ο / ‘Σ 一 ‘’ 从? ? , 。‘Σ 到0 。 ‘的映射:王! , 一 Γ就是从 ? � 毛‘Σ 一 ”到 + 的映射 例 > � ? ( 采用压缩编码的签名 对于 ) 8 � Χ � , Δ ‘。 , Σ 。 。 。 ∗ 如上所述 , 定义 ) / )∀ ∗ , / )’∗ , ⋯ , / )Σ 一 Υ ∗ ∗ / “ ’Ο 8 9 : ) / )‘一 ” , Ν “ ’∗ ∀ 三 &Π Σ / 一 ’ 二 ! 并把具有密钥! 的数据签名定义为 2 6 Β! , 8 � Χ � , Δ ‘ 。 ( Σ � 。 %卜 / )Σ 一 , ∗ 压缩编码就是密钥上的链锁 。 = � + 雷宾 ) Ζ 。 , 6 # ∗ 的解 数字签名的第一个例子是Η &Ψ ∃ Ρ% Υ Ζ Ρ Ι &# 给出的〔Ζ � 6〕。 每一对交易参加者都涉及 到一个示于图= 。 + 。 +的 :7 � 标准消息 用户 � : 6 Β! Λ , 。 , :7 , Δ � 。 , −卜 2 6 Β! 人 , , , :7 , Δ , 。 ( − Γ :6 Β! Λ , Χ 一 ( , :7 , Δ � 。 , − Γ [ 。 。 。 ( ·‘ · , 用户 − 2 6 Β! , , 。 , :7 , Δ � 。 , � Γ 2 6 Β! 。 , ( , :7 , Δ 。 。 , � 卜 2 6 Β! 。 , Χ 一 ( , :7 , Δ � 。 , � Γ ∋ ∀ # Ρ % ∃ % ∋ − % ∴ % # 图= 。+ 。 + ) 用户�一用户− ∗ 合同 用户� 用密钥! � 给用户− 的数据签名 :6 Β! � , 8 � Χ � , Δ , 。 ( − Γ 是用具有密钥! � 的密码系统把 ) 8 � Χ � , Δ , % ( − ∗ 加密成某种密码 。雷宾提出的压 缩编码 ) 如例 > � ? ∗ 可用来得出这个签名 , 但链式密文 ) 如例> � + ∗ ) 或它的一 种 变 形 ∗ 似乎有更称心的特性 。 每对用户独立地选择Χ 个密钥并用每 个密钥加密标准消息 , 这 0 Χ 个密码被记 录在用户双方签 了名的)用户 �一用户− ∗ 合同中。用户 � 、用户 − 和一个称作公证人 的受托的第三者接收该合同的一个付本 。 = � ? 。交易 从用户 � 到用户 − 的一笔交易包括下 述一些步骤 ( 步 骤 + ( 对于第 &项交易 , 发起人 )用户 � ∗ 把数据发送给接收者 )用户 − ∗ , 并 附有 ?+ 种签名 。 8 � Χ � , : 6 Β! � , ( ( , , 8 � Χ � , Δ ( 。 ,−卜, ⋯ , 8 � Χ � , ΕΥ% Β! � , ( ( ; ] ? 。 , 8 Χ � � , Δ , 。 , − Γ 是由第 & 密钥块 ! � , ( + + ! Λ , ( 一 &十 ⊥ ! Λ , ( ( Ε十 ( ∀ 构成的 。 步骤 ? ( 现在 , 用户−要求用户 � 揭示 ?+ 种密钥中的 +5 种 ( ! 人 , ( ( & 十 ! � , ? + , 十 了 ! � , ? ? + � , 。 <三丫 。Π 丫 ; Π ⋯ Π / 。Π ? + / 。 , / , , 一 , 丫。的选择是由用户−指定的 。 步骤 3 ( 若密钥 ( ! � , ? , ‘( 。 , ⋯ , ! 人 , Μ Φ Α] ( 。 Υ � 一致的 , 是和合同中第 &密钥块中的结构 以及 如果它们是和 +5 个签名 2 6 Β! “ , ? ( ( ] ( 。 , 8 � Χ � , Δ : · − Γ <丛 :Π _ 一致的 , 则用户−现在可以进行检验。 步骤 4 ( 合同要求从用户 − 到用户 � 有一 个认可 ( � Ω ! 8 � Χ � ( 我承认收到关 于 ) 日 期 ∗ ⋯的如在步骤 + 一 3 中用用户 � ) 原 文误为用户− ∗ 的第 &密钥块签名的数据 。 一种密钥只用于一笔交易 。 = � 3 � 设想 若签名是如例> � +或例 > � ?中那样定义 的 , 要求出下述问题中的任意解 ( 问题 + ( 已知 ( ) 8 � Χ � 、, Δ ‘ 。 ( − Α ∗ 和: 6 灌! Α , 8 � Χ � ⎯ , Δ , 。 ( − 』Γ 二 / ; 求 ! Λ 。 或者 问题 ? ( 已知 ( 3 心 ) 8 � Χ � ; , Δ ( 3 、 ∗ 和 : 6 Β ! Α , 8 � Χ � & , Δ , 。 ( − & Γ 二 / , &“ 5 , + , 求证 ( : 6 笼! � , 8 � Χ � , Δ 。 。 ( − Γ当8 � Χ � 睡笼8 � Χ � , Γ时等价于密钥试验 。 = � 4 � 争论 各种各样的争论都可能发生 , Ζ 接收者认为发起人没有遵守合同 。 < 发起人认为接收者投有遵守合 同 。 如果产生了下述问题 ( +� 发起人抵赖 , &( � 发起人或接收者伪造 ; ++ + � 第三者冒充 。 则争论 Ζ 可能发生 。 如果已有下述问题存在 ( + � 接收者抵赖 , && · 发起人或接收者伪造 ; ++ + � 第三者冒充。 则争论 < 可能发生 。 如在某些其他问题中那样 , 在 Ζ Ρ Ι加 提出的解中 , 解决争论是由公证人完成的 。 任何签名中的参加者都必须同意遵守 该制度的准则并接受公证人的裁决 。 我们认为只解决了一种争论 。 = � 2 建立一种争论 争论 Ζ 接收者 ) 用户− ∗ 把数据 , ?+ 个签名 ( 2 6 Β! 人 , ( , Α , 8 � Χ � , Δ 二 , − Γ , : 6 长! Α , ( ; 、十 ( 。 , 8 � Χ � , Δ ( 、, −卜 和+5 种密钥 ( ! � , ( ? + ] , ∀ ! ‘ , ( ( ‘] , Μ ! Λ , Μ ( ;不, 。 提供给公证人 。 公证人要求发起人 ) 用户 � ∗ 提供第 & 密 钥块 ( ! � Ε ( ? + ! � , ( 一Α十 Υ ! � , ( + +十 ( ∀ 并进行验算 。 如果 + � 用户 � 的第 &密钥块和合同结构 2 6 Β! � , ( , ; ] , , :7 , Δ ( 。 丫− Γ 心三 ϑΠ ?+ 是一致的 ; ++ � 用户−提供 的?+ 个签名 ( : 6 Β! � , ( + ; 十 ϑ , 8 � Χ � , Δ � 。 , − 卜 。三 ϑ Π ? + 是正确的。 则公证人对用户−作出裁决 。 如果 &。 用户 � 提供的密钥 义! � , ? ; ; 十 ϑ Γ 和合同结构之间有矛盾 ; 或者 修改或者伪造能成功吗 ≅ 要修改或者 伪造 一笔正确的已经签名的交易 , 需要有 能力从被认为是难 以加工的签名: 6 Β! � , 8 � Χ � , Δ Ε 。 ( − Γ 中找出数据的正确签名 ++ � 有 ++ 个或更多的签名是正确的 , 则争论 < 对于争论 Ζ 而言是双重的 , 而且 可以通过交换用户 � 、 用户 − 、 数据和认 可 ) � Ω! 8 � Χ � ∗ 的作用而得到解决。 讨论 发起人能够成功地赖账吗 ≅ 如果抵 赖是成功的 , 则?+ 个签名中正确的签名不 会超过 +5 个。 因为究竞要选哪 +5 个密钥 ) 步骤 + ∗ 是根据检验的要求 , 由接收者 指定的 , 发起人的抵赖不会逃脱接收者的 发觉 , 接收者能发现发起人进行抵赖的概 率是 ( + α α , , � , 。 � , 。 , � Θ , 。 。 , 。 一 。止犷二 + + Φ+ 5 里β ? + Φ、 2 . Υ∀一 若认为+ 5 一 ”的概率太小了 , 则可把总数?+ )步骤 ? ∗ 增加到 ? 2 ] + ; :个签名是由 接收者 ) 步骤 3 ∗ 要求的 。 并且 , 若 : ] + 或更多的签名是正确的 , 则争论的解决会 有利于接收者 。 1 。 0 χ δ 上 的幂映射 定理1 � + 当ε 和ε是不同的素数时 , 设 # Ο ε δ 。 若 . 是和ε 、 δ互素的 , 则 . 甲)# ∗三 Υ ) ∋ ∀ φ # ∗ 其中甲 ) # ∗ 二 ) ε 一 + ∗ ) δ 一 + ∗是 # 的 欧拉极性函数 ) 9 γ Υ% Φ ϑ。Α &% # ϑ ∗ 。 推论 1 � ? 当ε , δ是不同的素数时 , 设 # 二 ε δ 。 若 %和甲 ) # ∗ 互素且有逆元 φ , % φ 二 + ) ∋ ∀ φ 甲 ) # ∗ ∗ 则映射 ( 9 , ( Ν 一Ν , ) ∋ ∀ φ # ∗ 是 0 。上的一一映射且有逆9 φ , 。 。 证明 ( 若Ν 是和 ε 、 δ 互素的 , 则 军题月 Ν % φ Ο Ν Υ 十 η甲 )几 ∗ Ο Ν 一Ν η )ε 一 工∗)δ 一 & ∗ 二 Ν ) ∋ ∀ φ # ∗ 因为 , 据费尔马定理有 ( Ν ε 一 ’ Ο + ) ∋ ∀ φ ε ∗ , Ν 万一 + Ο Υ ) ∋ ∀ φ δ ∗ 如果 当 Υ三 ι Π δ Π ε 时 , Ν Ο ε ι, 则 Ν Υ ] η甲 )� ∗ 一 Ν 显然能被ε除尽。 由于 . 不能被 δ 整除, 故 Ν 6 ‘ η甲 )” ∗ 一 Ν 二 Ν 以Ν )δ 一 ’∗∗η )ε 一 + ∗ 一 + 〕 根据费尔马定理 , 括号中的数模δ 同余零。 于是 Ν ∀ φ 一 Ν 三 < ) ∋ ∀ φ # ∗ 附注 ( 整数 Σ可写作 Σ 二 Ω ∀ ] Ω , # ] Ω ( # 0 ] ⋯ <三Ω &Π 。 ⎯ΟΟ 5 , Υ , ? , 在集合谧< , Υ , 一 Γ上用 9 。 , 。 ( Σ , ) 9 。 , 。Σ ∗ Ο )9 ‘ , 。Ω 。 ∗ ] # ) 9 。 , 。Ω , ∗ ] # 么 ) 9 Α , # Ω 0 ∗ ] ⋯ 定义的映射9 。 , 。是集合提< , Υ , ⋯ Γ上映 到它本身的一一映射 。 _ � + 吕屋斯特 一 萨 米 尔一 埃德 勒 曼 ) Ζ &, % Ε ϑ一:∃ Ρ∋ &Φ一 � φ Υ% ∋ Ρ # ∗ ) 略 称 Ζ :�一译者注 ∗ 签名制度〔Ζ Υ〕 φ ε , δ 保密 % # “ χδ 公开 附注( + 。 因式分解# 可得甲)# ∗ 二 )χ 一 +∗ ) δ 一 Υ ∗ ; 由印)# ∗和 %可得φ 。 ? , 由 % 和 φ可得 甲)#∗ 的一倍数 ; 由 甲)# ∗的倍数可给出# 的一个因式分解。 公公 开 密 钥 手 册册 用用 户户 公 开 密 钥钥 9 % 人 , # � Θ 一 ) % � , # Λ ∗ 9 % 。 , # −一Θ ) % − , # − ∗ 用户� 通过发送 9 % − , # − Β9 φ � , # 人笼8 � Χ � ΓΓ 对用户−进行数据签名 。 9 % − , # 。笼9 φ Α , # � 魂8 � Χ � Γ Γ使用的是用 户 � 的 秘 密映射 9 φ Α , # � , 用户−的公开映射 9 % − , # 。 。 用户 − 能够阅读这笔签了名的交易 ; 首先使用用户−的秘密映射9 φ − , # − , 以便 得到 9 φ � , # � Β 8 � Χ � Γ “ 9 φ − , # Ρ Β 9 % 。 , # − Β9 φ , , 。人 Β8 � Χ � ΓΓΓ 而后 , 为了得到 8 � Χ � 一 9 % � , # Λ Β9 φ � , # � Β8 � Χ � ΓΓ 使用用户� 的公开映射 9 ∀ � , # � 。 这好比求9 % � , # � 的逆 9 φ � , # 、 。 我们 需要的是# Α 二 ε 、 δ 、 的因数 。 已知最快的 +算法需要运算。 ) % ’。二 人 ’‘ , 、· 人 , 一牙 ∗ 步 。 +5 � 平方剩余 定义 +5 � + ( 若二次方程 ι 0 二 Ρ ) ϑ# ∀ φ # ∗ 在0 。 α上有解ι , 则Ρ是模# 的一个平方剩余。 附注 ( 下面关于平方剩余的论据是 一般的 �− �一一— 一” 数论定理 )〔ς 9 〕。 在下文中 , ε是一个奇_ � ? 交易 素数 ∗ + 。 ι 0 三 Ρ ) ∋ ∀ φ ε ∗ 或者有 5 解 , 或者有两个解 , ? 。 对所有的. 〔 Μ χ , Ν) , 一 ’ ∗β ? 二 + 或 一 Υ , 3 。 存在 χ 一 + β ? 个模χ的平方剩余 ( ⊥ ⊥ , · 一 ⊥ 一 ⊥ · ⊥ 。 一 。 了χ 一 + 、 ? � Δ � Δ 〔犷 ϕ Ο 悦& ‘ , 乙 ’ , ’ ‘” 气一万一 β 气 ∋ < [ ε 少 尹 4 。 若且仅若 . )ε 一 ‘∗β ?二 + ) ∋ ∀ φ ε ∗ 则Ν 任[Δ � 8 〔χ〕 2 。 试验Ν 〔Μ χ是否是一个平方剩余 , 是复杂性为 5 ) Υ∀ ∴ ε ∗ 的计算 。 + + 。 ι “二 。 ) ∋ ∀ φ ε ∗ 的− % Φ Υ% η Ρ ∋ ε解〔−9 〕 假设 Ρ 是模 ε的一个平方剩余 , 使得方程式 κ ) ι ∗ 二 ι “ 一 Ρ 二 5 ) ∋ ∀ φ χ ∗ 有一个解 。 求ι就是确定二次多项式κ ) ι ∗ “ ι 又 一 Ρ 的线性因子 ( κ ) ι ∗ Ο ) / 一 日∗ ) / ] ε ∗ 扫, 一 ε 任0 , 一 α −% ( +比盈功ε的方法是用/ ‘ 0代替多项式的未定元/ , / 一 0表示由κ ( )ι》得到的多项 式 ( κ ( ) / ∗ 二 ) / 一 0 一 日 ∗ ) / 一 0 ] 日 ∗ 设 ( ) ι ∗ Ο ∴ % φ 蓬κΜ ) ι ∗ , ι χ 一 ‘β ? 一 & Γ 有四种情况 ( ( ) ι ∗ 情况 + ( ) 0 ] 日∗ 〔[Δ � 8 〔χ〕 ) 0 一 日∗ 〔[Δ � 8 〔χ〕 κ ( ) ι ∗ 情况 ? ( ) 0 ] 日∗ 破[Δ � 8 〔χ〕 ) 0 一 日∗ 磋[Δ �8 〔χ〕 Υ 情况 3 Ρ ( ) 0 ] 日∗ 〔[Δ � 8 〔ε〕 ) 0 一日∗ 诺[Δ � 8 〔χ〕 / 一 0 一 日 情况 Ε Ι ( ) 0 ] 日∗ 任[Δ � 8 〔χ〕 ) 0 一 日∗ 〔[Δ � 8 〔χ〕 / 一 0 ] 日 我们在 3 Ρ和 3 Ι两种情况中确定 κ )ι ∗ 二 。 的一个根 , 粉清况 + 和 ? 中 , 用独立地新选的 0值反复试验。 我们如何能经常成功地求得一个根呢 ≅ 设0 是均匀分布在 0 。上的一个随机变量 , 计 算κ Μ )ι∗ 的值 ( α 若κ ( )∀ ∗ 二 < ) ∋ ∀ φ ε ∗ 则0 Ο ε , 若 κ ( )< ∗粉 < ) ∋ ∀ φ ε ∗ , 计算出 Μ )ι ∗ 。 什么时 候我们会成功呢 ≅ 用 Η ( 0 ε 一 Β日Γ一0 。 一 Β Υ Γ Η ( 0 , Η ) 0 ∗ 二 0 ] ε β 0 一 ε 定义映射Η 二 Η ) Μ ∗ 。 关于0 , 一 Β ε 卜中的那些值的一半 ) +5 节附注 3 ∗ , Μ ε一 Β 日Γ在映射Η 下的象是 χ的 平方剩余。 于是 χ , Β)0 ] 日 ∗ β ) 0 一 ε ∗ 诺[Δ � 8 〔χ〕β 0 午 ε Γ。 通⊥ 其次 , 我们利用一个重要的事实 ) +5 节附注 4 ∗ , 即 若且仅若0 ] 日 和 0 一 ε 或 两 者 都是模 χ 的平方剩余 , 或两者都不是模 χ 的平方剩余 , 则 ) Μ ] 日 ∗八 Μ Θ ε ∗是 模 χ的一个平方剩余 。 最后得到下面的定理 ( 定理 + + � + 若 Ρ 是模 χ 的一个平方剩余 , 则用 − % Φ Υ% η Ρ ∋ ε 的方法求得方程 κ )ι ∗ 二 ι 0 一 Ρ 主 < ) Φ# ∀ φ ε ∗ 的一个解具有概率 、 含。 求得一个解所期 望的实验数近似等于 ? 。 + ? 。 ι “ 一 Ρ 二 < ) ∋ ∀ φ # ∗ 的解 。 # Ο ε δ ⊥ ε 和 δ是 已知素数。 若 ι 0 一 Ρ 二 < ) ∋ ∀ φ ε δ ∗ 有解 , 则了“ ι Υ Ο ι ( 也是一对同余式 ( Μ 0 � Υ ι ( 么 一 Ρ 兰 5 ) ∋ ∀ φ ε ∗ + ? � ? ι ? ? 一 Ρ 二 < ) ∋ ∀ φ δ ∗ 的解 。 反之 , 中国剩余定理 ) 即孙子定理一 译者注 ∗ 〔ς 9 〕给我们指出了如何求联立 方程 ) ? ? � + ∗ 一 ) +? � ? ∗ 的解 )ι ( , ι ( ∗ , 从而得到方程 ι 0 一 Ρ 二 < ) ∋ ∀ φ χδ ∗ 的解 。 我们指出 ( 若已知 # 的两个因数ε和δ , 则可求出当 # ” ε δ 以及Ρ 〔[Δ � 8 〔# 〕时的 方程 ι 0 一 仪二 < ) ∋ ∀ φ # ∗ 的解 。 + 3 � + Ζ ΡΙ &# 的等价定理 Ζ Ε� 数字签名方式的强度 , 部份依赖 于因式分解 # 二 ε δ的难度 。 在ε , δ是大素 数 (( 的假定条件下 , 破开Ζ :�方式的密码 问题是否就是等价于因式分解 # 二 ε δ , 尚 未可知。 % 二 ? 的特殊情况 已由Ζ ΡΙ &# 解 决 了。 (( 在密码学中, 术语 “大素数” 是关于 大概率素数的同义语 。 根据这个说法 , 我 们指定一个数目 # , 它 满 足 2 5+ 。 , “ι 和 : ϑ ( Ρ Ε Ε % # 〔2 5 〕概率算法的足够实验次数 , 为了验证 # 是否是一个素数 , 需要选择一 个均匀分布在集合 Β + , ? , ⋯ , # 一 + Γ中 的Ρ 并验算下式是否成立 ( ★ _ % φ ΒΡ , # 卜 Υ和 ϕ ) Ρ , # ∗ 二 Ρ 一 ‘β ? ) ∋ ∀ φ 。 ∗ 其中ϕ ) Ρ , 。 ∗ 是由下式 + ϕ) Ρ β ? , # ∗ )一 + ∗‘妞 一 ‘, β 3 ϕ ) # )∋ ∀ φ Ρ ∗ , # ∗ ) 一 Υ ∗’ 一 , 、‘Φ 一 , β 4 若 二 二 + 若 Ρ是偶数 若 Ρ Τ + 且是奇数 产‘�λ卫、�λ言�+、 一一、夕# , Ρ了、甲�ϕ 定义的雅可比符号 。 若# 是素数 , 则Α 会成立 。若Ρ 是 一个 合数 , 则★成立的概率 二 一盖一 。 若我们重复 试验 Σ次 , 且每次★都被满足 , 则我们确 信# 是一个素数的概率 二 ? 一 Σ 。 定理+ 3 � + ( 〔Ζ � 0 〕解方程 ) + 3 � ? ∗ ι 兰。二 。) ∋ ∀ φ ε δ ∗ 的问题等价于 # 二 ε δ的因子分解 。 证明 ( 若我们有 # 二 ε δ 的一个因子分解 , 则− % Φ Υ% η Ρ∋ ε方法和孙子定理能帮助我们 解方程 ) + 3 � + ∗ 。 为了证明相反的结论 , 我们首先注意 到二次方程 ι “ 一 Ρ 丢 。 ) ∋ ∀ φ # ∗ 一般有四个解。 这四个解可以用 丫 , 日, # 一 / , # 一 日 表示 , 日磋Β丫 , # 一 丫Γ。 由于 丫? 一 Ρ 二 ∀ )∋ ∀ φ # ∗日? 一 。二∀ )∋ ∀ φ # ∗ 满足 丫 ? 一 日? 二 ) 丫 ] ε ∗ ) 丫 一 ε ∗ 二 ∀ ) ∋ ∀ φ # ∗ 故素数ε和δ不能都除尽 丫 十 ε或丫 一 日, 使得或者 Υ ∗ ε是 ) 丫 一 ε ∗ 的一个因数 , δ是 ) 丫 ] 日 ∗ 的一个因数 , 或者 ? ∗ δ是 ) 丫 一 日∗ 的一个因数 , ε是 / ] 日的一个因数。 不管哪种情况发生 , # 和 / 一 日的最大公约数给出 # 的一个因数 , 使得ι 0 一 Ρ 二 。 ) ∋ ∀ φ 。 ∗ 的两个独立解给出# 的因式分解。 假设� ς 是下述情况 中的某种算法 ( 已知 ( # 和 # 的一个平方剩余仪 还原 ( ι 0 一 Ρ 二 ∀ )。∀ φ # ∗ 的一个解/ 二 �ς ) # , Ρ ∗ 选 ε使得 + Π 日Π # 以及 ∴ % 迁笼ε , # Γ Ο + , 则 。 二 日? ) ∋ ∀ φ # ∗ 是一个平方剩余 ⊥ � ς ) # , Ρ ∗ 是 ι “二 Ρ ) ∋ ∀ φ # ∗ 的一个解。 的条件下 , 作因式分解是可能的。 若� ς 重复该实验 , 成功所期望的数是 ? 。 在概率 Ο 音 , � ς ) # , Ρ ∗ 磋灌ε , # 一 日Γ ) # , Ρ ∗ 〔Β 日, # 一 日Γ , 则用 ε的一个新的值 + 3 � ? 平方剩余签名方式 等价定理可以作为数字签名的基础 。 设 ε和 δ是大素数 , # 二 ε δ , 数据被表 示成下述形式 ( 数据 ( )Ν 。 , Ν ( , ⋯ , Ν ( 一 , ∗〔? ? , Σ 为了对数据签名 , 需要 + ∗ 随机产生一序列 Ζ ( ) / 。 , / ( , ⋯ , / 7 一 + ∗ 〔? ? , 7 ? ∗ 把接连起来的序列 )Ν 。 , Ν ; , ⋯ , Ν Σ 一 , , / 。 , / ; , ⋯ , / 7 一 ; ∗ 〔 0 ( , Σ 十 7 映射成0 。 ) # Ο ε δ ∗ 中的一个整数 ( )Ν 。 , Ν 一 , ⋯ , Ν Σ 一 + , / 。 , / , , ⋯ , / 7 一 , ∗ 一 Ρ ∀三 Ρ Π # 例如 , 压缩编码 )Ν 。 , Ν ( , ⋯ , Ν Σ 一 , , / 。 , / ; , ⋯ , / 7 一 ( ∗ 以及简化模 # 的这个结果 。 3 ∗ 若 Ρ 是模# 的一个平方剩余 ( ι 0 匀 Ρ ) ∋ ∀ φ # ∗ 则数据的签名就是 ( ) 丫。 , 丫 ; , ⋯ , 丫7 一 ; ∗ 日 4 ∗ 通过把 Ρ 升幂到ε 一 +β ?和 δ 一 +β ? ) 或用 ϕΡ Ψ ∀ Ι& 符 号 ∗ 来对 Ρ 进行检验 。 若 Ρ 不是模# 的一个平方剩余 , 则重复该过 程 , 产生一个新的 Ζ 值 , 重复步骤 + ∗ 到 3 ∗ ∀ 讨论 ( 若映射 8 � Χ � , Ζ Θ Ρ 是个好的映射 , 则选择一 Ζ , 相对于 Ζ 伴 生的Ρ 是模#的一个平方剩余的概率、 十 。 + 4 � + 委托凭据 将要讨论的验证交易的最后方法是用 特殊硬件连接的8 9 :算法 。 这种想法就是 要用 Ξ 9 Ζ 6κ/ ) 一种微处理器 ∗ , 它只对 范围很窄的指令集起反应 。 固 有 运算 和 , 9 Ζ6 κ/的中间结果不能从该系统得到 。 我们作下述假设 ( 假设 + ( 从相应的明文和8 9 :密文对 中恢 复密钥的任何方法等价于密钥试验 。 假设 ? ( ·为了正确地用密钥! � 签署数据 , 使用相应的数据 、 签名对 ( 8 � Χ � ; : 6 Β! � , 8 � Χ � 、Γ 当8 � Χ � 堪Β 8 � Χ � Α Γ时 , 在没有密 钥 ! � 的 情况下 , 这种方法等价于密钥试 验 。 系统有许多基本的检验密钥 ! Κ , , 每 个用户有一专门的检验密钥 ( �一、! 人 − , , ! − Ω , 、 ! Ψ 假设 3 ( 没有用户有机会接触密钥! Κ , , 用户 � 只把密钥 ! �告诉公证人 。 交易检验系统制作两个供使用的表; 一 表存在处理器内 , 第二个 表 ) 脱离主 机的 ∗ 由公证人掌握 。 ⋯汗 一 ’ 一 ’⋯ 一表一 ! Λ Α Ο 8 9 : Β! Κ , , )Δ � 。 , � , ! � ∗ Γ � , 、 ! 人 , , ! � Α − Θ 、! − , 一! − Α Ω Θ 一! Ψ , 一! Ψ Α 公证人的表 8 � Χ � 二 ) Ν ” + , Ν ‘、 , ⋯ , Ν 州 一 Υ∗ .) ‘∗( 1 位二进制数据块 。 8 9 : Β! � , 8 � Χ � Γ Ο ) ι ” ’, ι ‘” , ⋯ , 丫“ 一 , , ∗ ) 数据的链式密码 ∗ ι ‘Σ 一 ’ ( 用户 �的数据签名 。 在? ? , 。‘ Σ上 , 映射 8 � Χ � , : 6 笼! 人 , 8 � Χ � Γ 是 ? “ “ Σ 一 ”映射到 Υ 。 + 4 � ? 硬件设想 + � 每个终端配一个 8 9 :加密箱 。 ? � 每个终端有时钟或计数器 。 3 � , 9 Ζ 6κ / 是在 Ω χΔ 的实际保 护之下 , 它有基本的检验密钥 ! Κι , 系统 库不提供检验设备的中间计算结果 。 + 4 � 3 交易 从发起人 )用户� ∗到接收者 )用户− ∗ 的一笔交易由以下步骤组成 ( 步骤 + ( 用户�和用户−建立一条通信线 , 用户 − 把 一 个 计数器 ) 或时钟 ∗ 值 Ω Χ Φ % 。 发送用户� 。 步骤 ? ( 用 户 � 作 数据签名 : 6 笼! � , 8 � Χ � Γ且将数据、 签名对 8 � Χ � : 6 王! Λ , 8 � Χ � 卜 发送给用户 − 。 我们假定在数据前头标上 ( ) + ∗ 交易 日期 ) ? ∗ 用户� 的终端中现行计数器 值Ω Χ ∀Φ &和从用户 − 终端接 收到的计数器值Ω Χ Φ ∀ Ω 。 8 � Χ � ( Υ β + + β 1 5 , Ω Χ ∀ Φ &, Ω Χ Φ % %一买 ⋯ + 5 5份 步骤 3 ( 用户−接收数据 、 签名) Ν , / ∗ , 其中Ν , /假定等于 ( Ν 二 8 � Χ � / Ο : 6 谧! � , 8 � Χ � 卜 若且仅若 ) + ∗ 日期信息是现行的 ; ) ? ∗ 首标中的计数器值是 Ω Χ Φ % Ψ 。 则检验继续进行 。 用户− 不能检验关系 ( / Ο 2 6 Β! Λ , Ν Γ 因为! � 是不被用户−知道的 , Ν 和 / 之间 正常关系的检验将由Ξ 9 Ζ 6κ/来完成。 用 户−用密钥 ! −把互有联系的事项 ) # , Ν , / , Δ Ε % Φ � , Δ Ε % Φ − ∗ 加密。 # Ο Ν )二进位 ∗ 的长度 Δ Ο 8 9 : Β! − , ) # , Ν , / , Δ Ε % Φ � ⊥ Δ Ε ∀ Φ − ∗ Γ 把Δ 发送给 Ξ 9 Ζ 6κ /并请求Ξ 9 Ζ 6κ / 检验 / 是否是用户� 对Ν 的正确签名 , 用户−还 用明文把发起人 ) 用户 � ∗ 和接收者 ) 用 户 − ∗ 的名字发送 Ξ 9 Ζ 6κ/ 。 步骤 4 ( Ξ 9 Ζ 6κ / 包含 , 一 表中的 ! 、 Α , ! − Α 。 ) Υ ∗ ! � Α Ο 8 9 : Β! Κ , , ! Λ Γ ) ? ∗ ! 。 Α 二 8 9 : Β! ∀ , , ! 。Γ 并计算出! 人和! − )Δ Ε% Φ� , ! 人 ∗ Ο 8 9 :一 ‘Β ! Κ , , ! Λ Α 卜 )Δ Ε% Φ − , ! ( ∗ Ο 8 9 :一 ’王! 。 , , ! 。 Α 卜 借助密钥! ( 破译密码Δ 。 Δ Ο 8 9 :一 ’Β! − , Δ Γ 设定 ) + ∗ Δ ; Ο Δ ) + , ) ? ∗ Δ ( Ο Δ 〔∋ ] ∗) Δ 的 Υ 到二位二进位组 ∗ ∋ ] Ρ 〕)Δ的∋ ] + 到∋ ] # 位二进位组 ) 3 ∗ 三3 “ 竺〔# ] ∋ ] + , # ] ∋ ] 1 〕) Δ 的# ] ∋ ] Υ 到# ] ∋ ] 1 位二进位组 ∗ ) 4 ∗竺4 Ο 旦〔# ] ∋ ] _ , # ] ∋ ] + >〕) Δ 的# ] ∋ ] _ 到# ] ∋ ] +> 位二进位组 ∗ ) 2 ∗竺2 Ο 卫〔# ] ∋ ] += , # ] ∋ ] ? 4〕) Δ 的 # ] ∋ ] + =到 # ] ∋ ] ? 4位二进位组 ∗ 在一个有效的检验序列中 竺; “咨 + , ∋ 〕( # ) 数据的长度 ∗ Δ ( Ο Δ 〔∋ ] Υ , ∋ ] #〕( 数据 Δ 3 二 Δ 〔∋ ] # ] Υ , ∋ ] # ] 1 〕( 签名: 6 灌! Α , 8 � Χ � Γ Δ ‘ 二 Δ 〔∋ ] # ] _ , ∋ ] # ] + >〕( 用户 � Δ > 二 Δ 〔# ] ∋ ] + = , # ] ∋ ] ? 4 ∗ ( 用户 − 若且仅若下面的条件成立 , 则检验过程不 应继续 ) 表示发送给用户− ∗ ( ) Υ ∗ 明文中发起人 的 名 字 和卫 〔∋ ] # ] _ , # ] ∋ ] + > 〕不 同 ; ) ? ∗ 明文中接收 者 的 名 字 禾坦 〔∋ ] # ] += , # ] ∋ ] ? 4〕不 同 ; ) 3 �∗ 8 9 : 一 ‘Β! Κ , , ! � Α Γ中的首 标和Δ 〔∋ ] # ] _ , # ] ∋ ] + >〕不同, ) 4 ∗ 8 9 :一 ’Β ! Κ , , ! 。 Α Γ中的首 标和Δ 〔∋ ] # ] + = , # ] ∋ ] ? 4〕不同 , 然后 , , 9 Ζ 6κ/用密钥 ! � 计算出竺( 的签名 : 6 Β! Α , Δ ( 卜 并把, 9 Ζ 6κ/推出的签名和丛比较 ( ) Υ ∗ Ω Ο + 若有相同 ) ? ∗ Ω Ο < 其他情况 ) + ∗ 若 Ω Ο + , Ξ 9 Ζ 6κ/ 会导出 8 9 :用密钥 ! , 加密人卫的签名并把 , 一 : 6 Β! , , 、Δ Γ送还给用户− ∀ ) ? ∗ 若 Ω 二 5 , , 9 Ζ 6κ/会导出卫 的签名 Ξ Ο : 6 笼! 。 。 Δ Γ 并把 Ξ 还给用户 − 。 步骤 2 ( 用户− 计算出 2 6 Β! − , 、 )# , Ν , / , Δ Ε % Φ � , Δ Ε% Φ − ∗ Γ 并把它和从 Ξ 9 Ζ 6κ/ 接收到的答 复 Ξ 比 较 。 步骤 > ( 若而且仅若 ) Υ ∗ Ν 中的日期信息是现在的 , ) ? ∗ Ν 中的计数器值和所存贮的 计数器值一致以及 ) 3 ∗ 检验是有根据的 Ξ 二 : 6 Β ! 。 , ‘ ) # , Ν , / ⊥ Δ Ε % Φ� , Δ Ε % Φ − ∗Γ 则用户 − 承认这笔交易。 在这笔交易的检验系统中流通的数据 是 ( 信息 来自 去到 Ω Χ Φ % Ψ 用户� 用户 − # , Ν , / 用户� 用户 − 8 9 :Β! − , ) # , Ν , / , Δ Ε % Φ � , Δ ∀ % Φ − ∗ 子, Δ Ε% Φ � , Δ Ε % Φ − 用户− Ξ 9 Ζ 6κ/ Ξ Ξ 9 Ζ 6κ/ 用户 − + 4 � 4 迹象分析 在争论Ζ 中一用户−声称用户 �不遵守一笔数字签名合同 Ν 二 8 � Χ � / 二 : 6 Β! 人 , 8 � Χ � 手 公证人将验证 /是否是用! 、加密的Ν 的数 字签名并在这种情况下对 用 户 − 作 出裁 决 。 用 Ν 二 8 � Χ � / 专 : 6 义! � , 8 � Χ � Γ 能给用户− 验验证一笔交易 ) Ν , / ∗ 吗 ≅ 假定用户 − 已经收到 了 ) Ν , / ∗ 并认 为用户�必定是信源 。 实际上 , ) Ν , / ∗ 是 由用户Ω发送的 )或因此用户 � 可以抵 赖 ∗ , 使得 ( /寺 : 6 笼! � , 8 � Χ � Γ 根据假定 + 和 ? , 用户 Ω 不可能有效地签 署数据一也就是 没有 ! � , 用户Ω 不能导出 签名: 6 Β! � , 8 � Χ � Γ。 对用户 Ω 来讲 , 可能的策略是 ( + 。 从用户 −到Ξ 9 Ζ 仆/ , 用消息 Δ , , 用户� , , 用户− , 来替换消息 Δ , 用户� , 用户− 这会引起 Ξ 9 Ζ 6κ/把验证用户 − 的这笔交 易的正确复信 Ξ Ο 2 6 笼! ( , 、Δ Γ 送还给用户− 。 或者 ? 。 从Ξ 9 Ζ 6κ/到用户 − , 用会导致 用户−承认这笔交易的签名 2 6 Β! − , 、Δ Γ 代替消息 Ξ( Ξ 二 2 6 笼! 。 , Δ Γ 因消息 Ξ 会警告用户 − , /不是由用户�正 确签署的. 。 根据有 “时间一标志 ” 的交易计数器值 , 可以防止重新用以前验证过的交易。 我们 假定计数器的周期充分大 。 假设 Υ 和 ? 暗中指 出 , 在没有! 。时 , 用户Ω 不可能有效地算出 Δ , 二 8 9 : 笼! ; , ) # , Ν , / , Δ Ε % Φ � ‘ , Δ Ε % Φ− ‘ ∗ Γ 以便用没有! � ‘和! 。的 / 二 :6 Β ! 、 ‘ , 8 � Χ � Γ 来破坏 + 或者用没 有 ! 8 的 :6 咬! 。 , 、Δ Γ来破坏 ? 用户 Ω能够把消息 Δ , 用户 � , 用户 − 中的明文用户 �改为用户Ω , 使得/ Ο : 6 Β ! Ψ , 8 � Χ � Γ是由用户 Ω对 Ν 的一个正确 签名 。 当Ξ 9 Ζ 6κ/接收到消息 Δ , 用户Ω , 用户− Δ Ο 8 9 : Β! 。 , ) # , Ν , / , Δ Ε % Φ � , Δ Ε% Φ − ∗ Γ 时 , Ξ 9 Ζ 6κ/不会验证这笔交易 , 因为明 文名字用户Ω 和 Δ ; 不一致。 假设从用户 − 到 Ξ 9 Ζ 6κ/ 的正确消息 Δ 或者从 Ξ 9 Ζ 6κ/到用户 − 的正确检验复 信: 6 笼! − , 、 Δ Γ始终是可以收到的 。 那 么 , 我们认为 , 链锁变换 的特性 , 表明了 用随机抽样法成功的概率大约是 ? 一 。 3 这 个量级 。 最后 , 机内, 一表可能被企图伪装的用 户 Ω更换 ;例如 , 用 ! Ω Α 来代替输入 ! 二 Α 。 再者 , , 9 Ζ 6κ/ 在识破这假想的 ! 人 Α 以 及把8 9 :一 ‘灌! , ( , , ! � Α Γ8 9 :一 ‘ Β ! Κ 、 , ! − Α 卜的首标和8 9 : Β ! − , ) # , Ν , / , Δ Ε。Φ