一种将多个整数安全相加的计算机系统及方法转让专利
申请号 : CN200580010699.9
文献号 : CN100585670C
文献日 : 2010-01-27
发明人 : 布田裕一 , 山道将人(已故) , 大森基司 , 静谷启树 , 满保雅浩
申请人 : 松下电器产业株式会社
摘要 :
提供了一种计算机系统，其使得难以分析计算的内容。幂运算单元(262)使用输入数据“a”和“b”执行以下运算：ga＝gamod n，gb＝gbmod n。接下来，乘法单元(264)使用ga和gb执行以下计算：gab＝ga×gbmod n。接下来，离散对数计算单元(266)计算满足gab＝gcimod pi(i＝1，2，…，k)的cimod pi-1。接下来，CRT(267)使用中国剩余定理CRT计算满足ci＝c mod pi-1(i＝1，2，…，k)的“c”。
权利要求 :
1、一种用于将两个或者更多个整数相加的计算机系统，包括：转换模块，用于通过使用每个整数在群G中执行幂运算，生成 属于所述群G的元素，运算模块，用于通过使用所有所生成的元素执行除加法之外的基 本运算，生成运算值，以及逆转换模块，用于通过在所述群G中或者所述群G的适当子群 S中对所述运算值执行逆幂运算，生成所述整数的和值，其中，所述群G是整数剩余环的乘法群，所述转换模块对每个 所述整数执行取幂，以及所述运算模块执行所述元素的乘法作为所述 基本运算。
2、如权利要求1所述的计算机系统，其安全可靠地处理目标信 息，其中所述计算机系统还包括安全模块，用于对所述目标信息执行安全 处理；以及所述安全模块使用所述转换模块、所述运算模块和所述逆转换模 块执行加法运算。
3、如权利要求2所述的计算机系统，其中
所述群G是Z/nZ的乘法群，其中乘积n＝p1×p2×...×pk，并且其 中p1，p2，...，pk(k＞1)表示相互不同的素数；以及运算符×表示乘法，Z表示整数环，并且Z/nZ表示由对于模n同 余的值组成的整数剩余环。
4、如权利要求3所述的计算机系统，其中
所述逆转换模块还用于解决在分别使用所述素数p1，p2，...，pk的 Z/Zp1，Z/Zp2，...，Z/Zpk的所述乘法群的每一个中的离散对数问题。
5、如权利要求4所述的计算机系统，其中
所述逆转换模块还用于使用中国剩余定理来解决在分别使用所 述素数p1，p2，...，pk的Z/Zp1，Z/Zp2，...，Z/Zpk的所述乘法群的每一个 中的离散对数问题。
6、如权利要求2所述的计算机系统，其中
所述群G是Z/nZ的乘法群，对于所述Z/nZ的乘法群，N＝pm×q， 其中p和q为素数，m为正整数；
所述转换模块对每个所述整数执行取幂；以及
所述运算模块执行所述元素的乘法。
7、如权利要求6所述的计算机系统，其中
所述子群S为Z/pmZ的乘法群。
8、如权利要求6所述的计算机系统，其中
所述正整数m为2。
9、如权利要求2所述的计算机系统，其中
所述逆转换模块存储多个指数，每一个指数都对应于使用该指数 求幂的值，并且通过搜索该对应关系来找到所述幂运算的逆运算。
10、如权利要求2所述的计算机系统，其中
所述逆转换模块包括归约子模块，用于将属于所述群G的每个 元素约化到属于所述子群S的元素。
11、如权利要求2所述的计算机系统，其基于密钥信息对所述目 标信息进行加密或者解密，其中所述安全模块基于所述密钥信息对所述目标信息进行加密或者 解密，所述加密和解密是使用所述加法模块将所述密钥信息或者从所 述密钥信息中获得的第二密钥信息加到所述目标信息上或者加到从 所述目标信息中获得的第二目标信息上来执行的；以及在所述加法运算中，所述转换模块、所述运算模块和所述逆转换 模块用于将所述密钥信息或者所述第二密钥信息加到所述目标信息 上或者所述第二目标信息上。
12、如权利要求11所述的计算机系统，其中
所述加密是共享密钥加密算法；以及
所述解密是共享密钥解密算法。
13、如权利要求2所述的计算机系统，其基于密钥信息对所述目 标信息执行数字签名或者数字签名验证，其中所述安全模块基于所述密钥信息对所述目标信息执行所述数字 签名或者数字签名验证，其中使用所述加法运算将所述密钥信息或者 从所述密钥信息中获得的第二密钥信息加到所述目标信息上或者加 到从所述目标信息中获得的第二目标信息上；以及在所述加法运算中，所述转换模块、所述运算模块和所述逆转换 模块用于将所述密钥信息或者所述第二密钥信息加到所述目标信息 上或者所述第二目标信息上。
14、如权利要求2所述的计算机系统，其中
所述计算机系统被集成在IC卡上。
15、一种用于将两个或者更多个整数相加的计算机系统，包括：转换模块，用于通过使用每个整数在群G中执行幂运算，生成 属于所述群G的元素，运算模块，用于通过使用所有所生成的元素执行除加法之外的基 本运算，生成运算值，以及逆转换模块，用于通过在所述群G中或者所述群G的适当子群 S中对所述运算值执行逆幂运算，生成所述整数的和值，其中，所述子群S为不规则椭圆曲线群，所述转换模块使用每个 整数执行所述椭圆曲线上的乘法，以及所述运算模块对所述元素执行 所述椭圆曲线上的加法作为所述基本运算。
16、一种用于将两个或者更多个整数相加的计算机系统，包括：转换模块，用于通过使用每个整数在群G中执行幂运算，生成 属于所述群G的元素，运算模块，用于通过使用所有所生成的元素执行除加法之外的基 本运算，生成运算值，以及逆转换模块，用于通过在所述群G中或者所述群G的适当子群 S中对所述运算值执行逆幂运算，生成所述整数的和值，其中，所述群G是两个不规则椭圆曲线群的直积，所述转换模 块使用每个整数执行所述椭圆曲线上的乘法，以及所述运算模块对所 生成的元素执行所述椭圆曲线上的加法作为所述基本运算。
17、一种用于使用包括存储器单元和处理器的计算机系统将两个 或者更多个整数相加的加法方法，所述加法方法包括步骤：转换步骤，其使所述处理器通过使用每个整数在群G中执行幂 运算，生成属于所述群G的元素，运算步骤，其使所述处理器通过使用所有所生成的元素执行除加 法之外的基本运算，生成运算值，以及逆转换步骤，其使所述处理器通过在所述群G中或者所述群G 的适当子群S中对所述运算值执行逆幂运算，生成所述整数的和值，其中，所述群G是整数剩余环的乘法群，所述转换步骤对每个 所述整数执行取幂，以及所述运算步骤执行所述元素的乘法作为所述 基本运算。
说明书 :
发明领域
本发明涉及抗窜改软件技术，其使得分析计算机程序变得困难。
背景技术
近年来，在包含根据计算机程序操作的处理器的计算机系统中使 用加密程序(加密软件)，这在诸如传送秘密信息和认证通信伙伴之 类的应用中变得普通。
在这种应用中，如果包含密钥、加密算法等等的软件以其原始状 态安装在计算机系统，并且所安装的软件被分析，则可能发生未授权 情况。为了解决该问题，专利文献1公开了一种技术，该技术转换运 算和数据域，从而使得推断原始运算和数据变得困难。
例如，假设存在加法程序，其执行输入数据a和b的加法，并输 出结果a+b。
整数k1和k2被预先存储，并被用于将输入数据a和b分别转换 为ta＝k1×a+k2和tb＝k1×b+k2。需要注意的是，“×”是表示乘法的运 算符。
接下来，根据ta和tb计算出tab＝ta+tb。
此外，根据tab计算出c＝(tab-2k2)/k1。
接下来，输出运算结果c。
以上过程给出：
tab＝ta+tb
＝k1×a+k2+k1×b+k2
＝k1×(a+b)+2k2 其给出
(tab-2k2)/k1＝a+b
因此c＝a+b，并且通过加法程序获得a和b的加法的结果。
专利文献1：U.S.专利6594761。
专利文献2：日本专利申请No.3402441。
专利文献3：日本特开平专利申请2760799。
非专利文献1：Tatsuaki OKAMOTO，Hirosuke YAMAMOTO “Gendai Ango”(Modern Cryptography)，Sangyotosho(1997)。
非专利文献2：Henri Cohen，“A Course in Computational Algebraic Number Theory”，GTM 138，Springer-Verlag，1993，pp.19-20。
非专利文献3：I.Blake，G.Seroussi和N.Smart，“Elliptic Curves in Cryptography”，CAMBRIDGE UNIVERSITY PRESS，1999。
非专利文献4：N.Kunihiro和K.Koyama，“Two Discrete Log Algorithms for Super-Anomalous Elliptic Curves”，SCIS’99，1999，pp. 869-874。
在这种应用中，如果包含密钥、加密算法等等的软件以其原始状 态安装在计算机系统，并且所安装的软件被分析，则可能发生未授权 情况。为了解决该问题，专利文献1公开了一种技术，该技术转换运 算和数据域，从而使得推断原始运算和数据变得困难。
例如，假设存在加法程序，其执行输入数据a和b的加法，并输 出结果a+b。
整数k1和k2被预先存储，并被用于将输入数据a和b分别转换 为ta＝k1×a+k2和tb＝k1×b+k2。需要注意的是，“×”是表示乘法的运 算符。
接下来，根据ta和tb计算出tab＝ta+tb。
此外，根据tab计算出c＝(tab-2k2)/k1。
接下来，输出运算结果c。
以上过程给出：
tab＝ta+tb
＝k1×a+k2+k1×b+k2
＝k1×(a+b)+2k2 其给出
(tab-2k2)/k1＝a+b
因此c＝a+b，并且通过加法程序获得a和b的加法的结果。
专利文献1：U.S.专利6594761。
专利文献2：日本专利申请No.3402441。
专利文献3：日本特开平专利申请2760799。
非专利文献1：Tatsuaki OKAMOTO，Hirosuke YAMAMOTO “Gendai Ango”(Modern Cryptography)，Sangyotosho(1997)。
非专利文献2：Henri Cohen，“A Course in Computational Algebraic Number Theory”，GTM 138，Springer-Verlag，1993，pp.19-20。
非专利文献3：I.Blake，G.Seroussi和N.Smart，“Elliptic Curves in Cryptography”，CAMBRIDGE UNIVERSITY PRESS，1999。
非专利文献4：N.Kunihiro和K.Koyama，“Two Discrete Log Algorithms for Super-Anomalous Elliptic Curves”，SCIS’99，1999，pp. 869-874。
发明内容
本发明旨在解决的问题
常规示例的方法的问题在于，存在转换前的运算将会被推断为是 加法的风险。这是因为在转换后的定义域中的运算是加法，并且由此 该运算的类型与转换前的运算相同。因此，如果执行加法的程序段被 试图分析该程序的人发现，则存在的危险是，这些段周围的代码会被 深入分析，以揭示所采用的转换的本质。因此，应该采用加法之外的 运算，以尽可能地确保转换前的运算的真正本质不会被发现。
本发明的一个目的在于提供一种计算机系统、程序、加法方法和 记录介质，其使得分析运算的内容变得更加困难。
解决问题的手段
为了解决上述问题，本发明是用于将两个或者更多个整数相加的 计算机系统，包括：存储器单元，用于存储包括多个指令的程序；以 及处理器，用于依次从所述存储器单元中存储的程序中取回每条指 令，并解码和执行每条所取回的指令，其中所述程序包括转换指令集， 其使所述处理器通过使用每个整数在群G中执行幂运算，生成属于 群G的元素，运算指令集，其使所述处理器通过使用所有生成的元 素执行除加法之外的基本运算，生成运算值，以及逆转换指令集，其 使所述处理器通过在群G中或者群G的适当子群S中对所述运算值 执行逆幂运算，生成所述整数的和值。
本发明的效果
采用该构造，可以隐藏运算本身以及在该运算中所使用的值。
所述计算机系统可以安全并可靠地操作目标信息，所述程序还可 以包括安全指令集，其使所述处理器对所述目标信息执行安全处理， 并且所述安全指令集可以使所述处理器采用所述转换指令集、所述运 算指令集以及所述逆转换指令集来执行加法运算。
在此，群G可以是整数剩余环(integer residue ring)的乘法群， 所述转换指令集可以使所述处理器对每一个所述整数执行取幂，所述 运算指令集使所述处理器执行元素的乘法。
采用该构造，因为所述转换之后执行的运算是乘法而不是加法， 所以可以隐藏所述转换之后执行的运算。
在此，群G可以是Z/nZ的乘法群，对于该乘法群，n＝pm×q， 其中p和q是素数，m为正整数。所述转换指令集可以使所述处理器 对每一个所述整数执行取幂，并且所述运算指令集使所述处理器执行 元素的乘法。
采用该构造，因为所述转换之后执行的运算是乘法而不是加法， 所以可以隐藏所述转换之后执行的运算。
在此，子群S可以是不规则椭圆曲线群，所述转换指令集可以使 所述处理器使用每个整数执行所述椭圆曲线上的乘法，并且所述运算 指令集使所述处理器对所述元素执行所述椭圆曲线上的加法。此外， 群G可以是两个不规则椭圆曲线群的直积，所述转换指令集可以使 所述处理器使用每个整数执行所述椭圆曲线上的乘法，并且所述运算 指令集使所述处理器对所生成的元素执行所述椭圆曲线上的加法。
采用该构造，因为所述转换之后执行的运算是椭圆曲线上的加法 而不是整数加法，所以可以隐藏所述转换之后执行的运算。
在此，所述逆转换指令集可以包括归约(reduction)部分，以使 所述处理器将属于群G的每个元素约化为属于子群S的元素。
采用该构造，可以容易地进行所述逆转换指令集所执行的操作。
所述计算机系统可以基于密钥信息，对目标信息进行加密或解 密。在该情况下，所述安全指令集可以使所述处理基于所述密钥信息， 对所述目标信息进行加密或解密，所述加密和解密是采用所述加法运 算将所述密钥信息或者从所述密钥信息中获得的第二密钥信息加到 所述目标信息上或者加到从所述目标信息中获得的第二目标信息上 来执行的，并且在所述加法运算中，所述转换指令集、所述运算指令 集以及所述逆转换指令集可以用于将所述密钥信息或者所述第二密 钥信息加到所述目标信息上或者所述第二目标信息上。
采用该构造，可以隐藏在涉及加密或解密的加法中所使用的值和 运算。
所述计算机系统可以基于密钥信息对所述目标信息执行数字签 名或者数字签名验证。在此，所述安全指令集可以基于所述密钥信息 对所述目标信息执行数字签名或者数字签名验证，其中采用所述加法 运算以将所述密钥信息或者从所述密钥信息中获得的第二密钥信息 加到所述目标信息上或者加到从所述目标信息中获得的第二目标信 息上，并且在所述加法运算中，所述转换指令集、所述运算指令集以 及所述逆转换指令集可以用于将所述密钥信息或者所述第二密钥信 息加到所述目标信息上或者所述第二目标信息上。
采用该构造，可以隐藏在涉及所述数字签名或者数字签名验证的 加法中所使用的值和运算。
如上所述，本发明的结构是有利的，这是由于其能够隐藏所述运 算本身以及在所述运算中使用的值。
常规示例的方法的问题在于，存在转换前的运算将会被推断为是 加法的风险。这是因为在转换后的定义域中的运算是加法，并且由此 该运算的类型与转换前的运算相同。因此，如果执行加法的程序段被 试图分析该程序的人发现，则存在的危险是，这些段周围的代码会被 深入分析，以揭示所采用的转换的本质。因此，应该采用加法之外的 运算，以尽可能地确保转换前的运算的真正本质不会被发现。
本发明的一个目的在于提供一种计算机系统、程序、加法方法和 记录介质，其使得分析运算的内容变得更加困难。
解决问题的手段
为了解决上述问题，本发明是用于将两个或者更多个整数相加的 计算机系统，包括：存储器单元，用于存储包括多个指令的程序；以 及处理器，用于依次从所述存储器单元中存储的程序中取回每条指 令，并解码和执行每条所取回的指令，其中所述程序包括转换指令集， 其使所述处理器通过使用每个整数在群G中执行幂运算，生成属于 群G的元素，运算指令集，其使所述处理器通过使用所有生成的元 素执行除加法之外的基本运算，生成运算值，以及逆转换指令集，其 使所述处理器通过在群G中或者群G的适当子群S中对所述运算值 执行逆幂运算，生成所述整数的和值。
本发明的效果
采用该构造，可以隐藏运算本身以及在该运算中所使用的值。
所述计算机系统可以安全并可靠地操作目标信息，所述程序还可 以包括安全指令集，其使所述处理器对所述目标信息执行安全处理， 并且所述安全指令集可以使所述处理器采用所述转换指令集、所述运 算指令集以及所述逆转换指令集来执行加法运算。
在此，群G可以是整数剩余环(integer residue ring)的乘法群， 所述转换指令集可以使所述处理器对每一个所述整数执行取幂，所述 运算指令集使所述处理器执行元素的乘法。
采用该构造，因为所述转换之后执行的运算是乘法而不是加法， 所以可以隐藏所述转换之后执行的运算。
在此，群G可以是Z/nZ的乘法群，对于该乘法群，n＝pm×q， 其中p和q是素数，m为正整数。所述转换指令集可以使所述处理器 对每一个所述整数执行取幂，并且所述运算指令集使所述处理器执行 元素的乘法。
采用该构造，因为所述转换之后执行的运算是乘法而不是加法， 所以可以隐藏所述转换之后执行的运算。
在此，子群S可以是不规则椭圆曲线群，所述转换指令集可以使 所述处理器使用每个整数执行所述椭圆曲线上的乘法，并且所述运算 指令集使所述处理器对所述元素执行所述椭圆曲线上的加法。此外， 群G可以是两个不规则椭圆曲线群的直积，所述转换指令集可以使 所述处理器使用每个整数执行所述椭圆曲线上的乘法，并且所述运算 指令集使所述处理器对所生成的元素执行所述椭圆曲线上的加法。
采用该构造，因为所述转换之后执行的运算是椭圆曲线上的加法 而不是整数加法，所以可以隐藏所述转换之后执行的运算。
在此，所述逆转换指令集可以包括归约(reduction)部分，以使 所述处理器将属于群G的每个元素约化为属于子群S的元素。
采用该构造，可以容易地进行所述逆转换指令集所执行的操作。
所述计算机系统可以基于密钥信息，对目标信息进行加密或解 密。在该情况下，所述安全指令集可以使所述处理基于所述密钥信息， 对所述目标信息进行加密或解密，所述加密和解密是采用所述加法运 算将所述密钥信息或者从所述密钥信息中获得的第二密钥信息加到 所述目标信息上或者加到从所述目标信息中获得的第二目标信息上 来执行的，并且在所述加法运算中，所述转换指令集、所述运算指令 集以及所述逆转换指令集可以用于将所述密钥信息或者所述第二密 钥信息加到所述目标信息上或者所述第二目标信息上。
采用该构造，可以隐藏在涉及加密或解密的加法中所使用的值和 运算。
所述计算机系统可以基于密钥信息对所述目标信息执行数字签 名或者数字签名验证。在此，所述安全指令集可以基于所述密钥信息 对所述目标信息执行数字签名或者数字签名验证，其中采用所述加法 运算以将所述密钥信息或者从所述密钥信息中获得的第二密钥信息 加到所述目标信息上或者加到从所述目标信息中获得的第二目标信 息上，并且在所述加法运算中，所述转换指令集、所述运算指令集以 及所述逆转换指令集可以用于将所述密钥信息或者所述第二密钥信 息加到所述目标信息上或者所述第二目标信息上。
采用该构造，可以隐藏在涉及所述数字签名或者数字签名验证的 加法中所使用的值和运算。
如上所述，本发明的结构是有利的，这是由于其能够隐藏所述运 算本身以及在所述运算中使用的值。
附图说明
图1示出了内容发送系统10的构造；
图2是示出内容服务器100的构造的方框图；
图3是描述内容发送程序131的流程图；
图4是描述内容加密程序132的流程图；
图5示出了加密程序133的结构；
图6是描述加密控制模块141(在图7中继续)的流程图；
图7是描述加密控制模块141(续接图6)的流程图；
图8示出了个人计算机200的构造；
图9是描述内容接收程序231的流程图；
图10是描述内容解密程序232的流程图；
图11示出了解密程序234的结构；
图12是描述解密控制模块241的内容的流程图(在图13中继 续)；
图13是描述解密控制模块241的内容的流程图(续接图12)；
图14示出了加法模块243的结构；
图15是描述加法模块243执行的加法运算的流程图；
图16示出了加法模块501的结构；
图17是描述加法模块501执行的加法运算的流程图；
图18示出了加法模块601的结构；和
图19是描述加法模块601执行的加法运算的流程图。
图2是示出内容服务器100的构造的方框图；
图3是描述内容发送程序131的流程图；
图4是描述内容加密程序132的流程图；
图5示出了加密程序133的结构；
图6是描述加密控制模块141(在图7中继续)的流程图；
图7是描述加密控制模块141(续接图6)的流程图；
图8示出了个人计算机200的构造；
图9是描述内容接收程序231的流程图；
图10是描述内容解密程序232的流程图；
图11示出了解密程序234的结构；
图12是描述解密控制模块241的内容的流程图(在图13中继 续)；
图13是描述解密控制模块241的内容的流程图(续接图12)；
图14示出了加法模块243的结构；
图15是描述加法模块243执行的加法运算的流程图；
图16示出了加法模块501的结构；
图17是描述加法模块501执行的加法运算的流程图；
图18示出了加法模块601的结构；和
图19是描述加法模块601执行的加法运算的流程图。
具体实施方式
1.内容发送系统10
以下描述作为本发明的第一实施例的内容发送系统10。
1.1内容发送系统10的构造
内容发送系统10包括内容服务器100、发送服务器300a、广播 设备300b、BD制造设备300c、个人计算机200、数字广播接收器200a 以及BD播放器200b，如图1所示。
内容服务器100存储由视频和音频数据构成的电影内容，根据来 自发送服务器300a的请求，通过对所存储的内容进行加密来生成加 密内容，并将所生成的加密内容发送到通过专用线路21连接的发送 服务器300a。发送服务器300a接收加密内容，并将该加密内容发送 到经由因特网20与发送服务器300a连接的个人计算机200。个人计 算机200接收加密内容，通过对所接收的加密内容进行解密来生成解 密内容，并通过播放所生成的解密内容来输出视频和声音。
类似地，内容服务器100根据来自广播设备300b的请求生成加 密内容，并将所生成的加密内容发送到通过专用线路22连接的广播 设备300b。广播设备300b接收加密内容，在载波电波上广播所接收 的加密内容。数字广播接收器200a接收广播电波，从广播电波中提 取加密内容，通过对所提取的加密内容进行解密来生成解密内容，并 通过播放所生成的解密内容来输出视频和声音。
类似地，内容服务器100根据来自BD制造设备300c的请求生 成加密内容，并将所生成的加密内容发送到通过专用线路23连接的 BD制造设备300c。BD制造设备300c接收加密内容，将所接收的加 密内容写入记录介质400。将其中具有加密内容的记录介质400投入 市场并卖给用户。当用户装载记录介质400时，BD播放器200b从记 录介质400中读出加密内容，并通过对所读出的加密内容进行解密来 生成解密内容，并通过播放所生成的解密内容来输出视频和声音。
1.2内容服务器100
内容服务器100是包括微处理器101、硬盘单元102、存储器单 元103、输入控制单元104、显示控制单元105、通信单元106等等 的计算机系统，如图2所示。输入控制单元104和显示控制单元105 分别连接到键盘107和监视器108。通信单元106分别通过专用线路 21、22和23连接到发送服务器300a、广播设备300b和BD制造设 备300c。
硬盘单元102和存储器单元103中存储了各种程序，内容服务器 100通过根据程序操作的微处理器101实现了其功能的一部分。
(1)硬盘单元102
硬盘单元102存储如图2所示的内容120、内容121、内容122、...、 密钥123、密钥124和密钥125、...，以及没有描述的其他程序。硬 盘单元102具有用于存储加密内容126、加密内容127、加密内容128... 的区域。
内容120、内容121、内容122、...，分别对应于密钥123、密钥 124、密钥125、...，并且还分别对应于加密内容126、加密内容127、 加密内容128、...。
内容120、内容121、内容122、...中的每一个都是包含已经被 高效压缩编码的视频和音频数据的数据。
密钥123、密钥124、密钥125、...是被用来通过对内容120、内 容121、内容122、...应用加密算法而生成加密内容126、加密内容 127、加密内容128的加密密钥。密钥123、密钥124、密钥125中的 每一个的长度都是64比特。加密算法将在以下章节中介绍。
加密内容126、加密内容127、加密内容128、...是通过分别对 内容120、内容121、内容122、...应用加密算法而生成的加密数据。
(2)存储器单元103
存储器单元103存储如图2所示的内容发送程序131、内容加密 程序132、加密程序133和发送程序134，以及未描述的其他程序。 这些程序中的每一个都由机器语言格式的指令编码的组合所组成。机 器语言格式能够被微处理器101解码和执行。
以下是对每个程序的内容的描述。为了确保每个程序的细节能够 容易理解，采用流程图而不是机器语言格式的指令来表示每个程序的 内容。
(a)内容发送程序131
内容发送程序131包括指令代码集S101、S102、S103和S104， 这些指令代码集在内容发送程序131中按照规定顺序排列，如图3所 示。每个指令代码集都包括一个或者多个指令代码。
指令代码集S101包括用于指示从内容服务器100的管理员接收 内容的指定，或者从内容的发送目的地设备接收内容的指定的多个指 令代码。
指令代码集S102包括用于指示接收内容的发送目的地设备的指 定的多个指令代码。
指令代码集S103包括用于指示指定由所接受或所接收的指定所 指示的内容，调用内容加密程序132，然后将由内容加密程序132所 生成的加密内容作为加密内容126写入硬盘单元102的多个指令代 码。
指令代码集S104包括用于指示指定所接收的指定和被生成并被 写入硬盘单元102中的加密内容的发送目的地设备，以及调用发送程 序134的多个指令代码。通过执行指令代码集S104，将所生成的加 密内容发送到所指定的发送目的地设备
(b)内容加密程序132
内容加密程序132包括指令集S111、S112、S113、S114、S115 和S116，这些指令代码集在内容加密程序132中按照规定顺序排列， 如图4所示。每个指令代码集都包括一个或者多个指令代码。
指令代码集S111包括用于指示将“-64”作为初始值而分配给读 出点的多个指令代码。所述读出点表示在指定内容中的比特中的数据 位置。该指令代码集还指示从硬盘单元102读出与指定内容对应的密 钥。具有初始值“-64”的读出点指示该内容之外的位置。将初始值 “-64”分配给该读出点，从而使得当以下所述的指令代码集S112第 一次执行时，该读出点指示在该内容首部的位置。在以下所述的指令 代码集S112第一次执行时，将该读出点加上64比特，然后该读出点 变为“0”，其指示内容首部。
指令代码集S112包括用于指示将该读出点加上64比特，然后读 出从由该最终的读出点所指示的内容中的位置处开始的数据块的多 个指令代码。所述多个指令代码集还指示，如果该读出点所指示的位 置位于内容中，则从该位置处读出该数据块，并且如果该读出点所指 示的位置位于内容之外，则输出用于指示对该块的读出已经结束的结 束代码。在此，一个块是具有64比特长度的数据。
指令代码集S113包括用于指示如果从指令代码集S112输出结束 代码，则结束内容加密程序132的处理的多个指令代码。所述多个指 令代码集还指示，如果没有输出结束代码，则将控制传递到随后的指 令代码集S114。
指令代码集S114包括指示用于利用所读出的密钥和所读出的第 一块调用加密程序133的多个指令代码。
指令代码集S115包括用于指示将加密程序133所生成的单一加 密块作为加密内容126的一部分写入硬盘单元102的多个指令代码。
指令代码集S116包括用于指示将控制传递到指令代码集S112的 指令代码。
(c)加密程序133
加密程序133包括加密控制模块141、扩展密钥生成模块142、 旋转模块A143、旋转模块B144、旋转模块C145以及旋转模块D146， 如图5所示。
每个模块都是包括机器语言形式的指令代码的组合的程序。机器 语言格式能够被微处理器101解码和执行。
扩展密钥生成模块142
扩展密钥生成模块142包括用于从调用程序接收64比特密钥K， 使用所接收的密钥K生成8个扩展密钥K1、K2、K3、...、K8，并 将8个所生成的扩展密钥K1、K2、K3、...、K8输出到调用程序的 多个指令代码。
注意，由于在专利文献3中对用于生成扩展密钥的方法进行了描 述，因此在此省略。
旋转模块A143
旋转模块A143包括用于指示从调用程序接收32比特数据X， 并对于数据X执行运算Rot2(X)+X+1，并将运算结果输出到调用程 序的多个指令代码。
Rot2(X)表示对32-比特数据X的向左2比特循环移位。32比特 数据X的向左2比特循环移位是指，将数据X分割为2个最重要比 特X1和30个最不重要比特X2，将X2移位到数据X的30个最重要 比特，并将X1移位到2个最不重要比特。
旋转模块B144
旋转模块B144包括用于指示从调用程序接收32比特数据X，并 对于数据X执行运算Rot4(X)XOR X，并将运算结果输出到调用程序 的多个指令代码。
Rot4(X)表示数据X的向左4比特循环移位，而XOR表示异或 操作。32比特数据X的向左4比特循环移位是指，将数据X分割为 4个最重要比特X1和28个最不重要比特X2，将X2移位到数据X 的28个最重要比特，并将X1移位到4个最不重要比特。
旋转模块C145
旋转模块C145包括用于指示从调用程序接收32比特数据X，并 对于数据X执行运算Rot8(X)XOR X，并将运算结果输出到调用程序 的多个指令代码。
Rot8(X)表示数据X的向左8比特循环移位。32比特数据X的向 左8比特循环移位是指，将数据X分割为8个最重要比特X1和24 个最不重要比特X2，将X2移位到数据X的24个最重要比特，并将 X1移位到8个最不重要比特上。
旋转模块D146
旋转模块D146包括用于指示从调用程序接收32比特数据X和 32比特数据Y，并对于数据X和数据Y执行运算Rot16(X)+(XAND Y)，并将运算结果输出到调用程序的多个指令代码。
Rot16(X)表示数据X的向左16比特循环移位，而AND表示逻 辑积。32比特数据X的向左16比特循环移位是指，将数据X分割 为16个最重要比特X1和16个最不重要比特X2，将X2移位到数据 X的16个最重要比特，并将X1移位到16个最不重要比特。
加密控制模块141
加密控制模块141包括在加密控制模块141中按照规定顺序排列 的指令集S121到S140，如图6和图7所示。每个指令代码集包括一 个或多个指令代码。
指令代码集S121包括用于指示从调用加密控制模块141的调用 程序接收单一明文块M和密钥K的多个指令代码。注意，一个块是 64比特长的数据。
指令代码集S122包括用于指示利用所接收的密钥K调用扩展密 钥生成模块142的多个指令代码。指令代码集S122的执行导致生成 8个扩展密钥K1、K2、K3、...、K8。
指令代码集S123包括用于定义数据M1的指令代码，和定义数 据M2的指令代码。数据M1是所接收的明文M的32个最重要比特， 数据M2是所接收的明文M的32个最不重要比特。
指令代码集S124包括用于指示对数据M1和数据M2执行XOR 运算，并将结果存储在变量TMP1中的多个指令代码。
TMP1＝M1 XOR M2
指令代码集S125包括用于指示执行变量TMP1与扩展密钥K1 的加法，并将运算结果存储在变量TMP2中的多个指令代码。
TMP2＝TMP1+K1
指令代码集S126包括用于指示利用变量TMP2调用旋转模块 A143，并将运算结果存储在变量TMP3中的多个指令代码。
TMP3＝Rot2(TMP2)+TMP2+1
指令代码集S127包括用于指示利用变量TMP3调用旋转模块 B144，并将结果存储在变量TMP4中的多个指令代码。
TMP4＝Rot4(TMP3)XOR TMP3
指令代码集S128包括用于指示对变量TMP4和数据M1执行 XOR运算，并将结果存储在变量TMP5中的多个指令代码。
TMP5＝TMP4 XOR M1
指令代码集S129包括用于指示对变量TMP5和扩展密钥K2求 和，并将运算结果存储在变量TMP6中的多个指令代码。
TMP6＝TMP5+K2
指令代码集S130包括用于指示利用变量TMP6调用旋转模块 A143，并将运算结果存储在变量TMP7中的多个指令代码。
TMP7＝Rot2(TMP6)+TMP6+1
指令代码集S131包括用于指示利用变量TMP7调用旋转模块 C145，并将运算结果存储在变量TMP8中的多个指令代码。
TMP8＝Rot8(TMP7)XOR TMP7
指令代码集S132包括用于指示将变量TMP8与扩展密钥K3相 加，并将结果存储在变量TMP9中的多个指令代码。
TMP9＝TMP8+K3
指令代码集S 133包括用于指示利用变量TMP9调用旋转模块 A143，并将运算结果存储在变量TMP10中的多个指令代码。
TMP10＝Rot2(TMP9)+TMP9+1
指令代码集S134包括用于指示利用变量TMP7和变量TMP10 调用旋转模块D146，并将运算结果存储在变量TMP11中的多个指令 代码。
TMP11＝Rot16(TMP10)+(TMP10AND TMP7)
指令代码集S135包括用于指示对TMP11和变量TMP1执行XOR 运算，并将运算结果存储在变量TMP12中的多个指令代码。
TMP12＝TMP11 XOR TMP1
指令代码集S136包括用于指示将变量TMP12与扩展密钥K4相 加，并将运算结果存储在变量TMP13中的多个指令代码。
TMP13＝TMP12+K4
指令代码集S137包括用于指示利用变量TMP13调用旋转模块 A143，并将运算结果存储在变量TMP14中的多个指令代码。
TMP14＝Rot2(TMP13)+TMP13+1
指令代码集S138包括用于指示对变量TMP14和变量TMP4执 行XOR运算，并将运算结果存储在变量TMP15中的多个指令代码。
TMP15＝TMP14 XOR TMP4
指令代码集S139包括用于指示对变量TMP15和变量TMP12执 行XOR运算，并将运算结果存储在变量TMP16中的多个指令代码。
TMP16＝TMP15 XOR TMP12
指令代码集S140包括用于指示将以变量TMP15作为其32个最 重要比特并以变量TMP16作为其最不重要比特的64比特整数作为密 文C输出到调用程序的多个指令代码。
(d)发送程序134
发送程序134(未描述)包括按顺序排列的多个指令代码，并包 括用于指示从调用程序接收数据的指定和发送目的地设备的指定，并 控制通信单元106以使得所指定的数据发送到所指定的发送目的地 设备的多个指令代码。
1.3个人计算机200
个人计算机200包括微处理器201、硬盘单元202、存储器单元 203、输入控制单元204、显示控制单元205、通信单元206等，如图 8所示。输入控制单元204和显示控制单元205分别连接到键盘207 和显示器208。此外，通信单元706连接到因特网20。
硬盘单元202和存储器单元203中存储了各种程序，并且个人计 算机200根据微处理器201依照程序进行操作实现其功能的一部分。
注意，数字广播接收器200a和BD播放器200b的描述被省略， 这是由于所述设备具有与个人计算机200中的那些设备类似的构造。
(1)硬盘单元202
硬盘单元202存储密钥222并具有用于存储加密内容221的区 域，如图8所示。加密内容221对应于密钥222。
加密内容221和密钥222分别与在内容服务器100的硬盘单元 102中存储的加密内容126和密钥123相同。
(2)存储器单元203
存储器单元203存储内容接收程序231、内容解密程序232、播 放程序233、解密程序234和加法程序235，如图8所示。此外，存 储器单元203包括解密内容区域236。这些程序中的每一个都是包括 机器语言格式的指令代码的组合的程序。机器语言格式能够被微处理 器201解码和执行。
对加密内容进行解密，并将所生成的解密内容暂时写入解密内容 区域236中。
以下是各种程序的详细描述，为了使各个程序的描述容易理解， 采用了流程图而不是机器语言格式的指令来表示每个程序。
(a)内容接收程序231
内容接收程序231包括按照规定顺序排列的指令代码集S201、 S202、S203和S204，如图9所示。每个指令代码集包括一个或者多 个指令代码。
指令代码集S201包括用于指示从个人计算机200的用户接收内 容的指定的多个指令代码。
指令代码集S202包括用于指示获取用于识别其指定已经被接收 的内容的内容标识符，并经由通信单元206和因特网20将所获取的 内容标识符发送到发送服务器300a的多个指令代码。
指令代码集S203包括用于指示经由因特网20和通信单元206 从发送服务器300a接收加密内容的多个指令代码。注意，所接收的 加密内容是由所述内容标识符所识别的加密内容。
指令代码群S204包括用于指示将所接收到的加密内容作为加密 内容221写入硬盘单元202的多个指令代码。
(b)内容解密程序232
内容解密程序232包括指令代码集S211、S212、S213、S214、 S215、S216、S217和S218，并且这些指令代码集在内容解密程序232 中按照规定顺序排列，如图10所示。每个指令代码集包括一个或者 多个指令代码。
指令代码集S211包括用于指示从个人计算机200的用户接收在 硬盘单元202中存储的加密内容之一的指定的多个指令代码。
指令代码集S212包括用于指示调用在存储器203中存储的播放 程序233的多个指令代码。执行指令代码集212使得并行执行内容解 密程序232和播放程序233。
指令代码集S213包括用于指示将“-64”作为初始值分配给用于 表示所指定的加密内容中的比特中的数据位置的读出点，随后从硬盘 单元202中读出与所指定的加密内容对应的密钥的多个指令代码。
指令代码集S214包括用于指示对所述读出点加上64比特，然后 试图读出从由最终读出点所指示的加密内容中的位置开始的数据块 的多个指令代码。所述多个指令代码还指示，如果所述读出点指示的 位置位于加密内容内，则从该位置处读出数据块，如果所述读出点指 示的位置位于加密内容之外，则输出表示该块读出已经结束的结束代 码。注意，一个块是具有64比特长度的数据。
指令代码集215包括用于指示如果从指令代码集S214输出结束 代码，则结束内容解密程序232的处理，并且如果没有输出结束代码， 则将控制传递到随后的指令代码集216的多个指令代码。
指令代码集S216包括用于指示利用所读出的密钥和所读出的第 一块调用解密程序234的多个指令代码。
指令代码集S217包括用于指示将解密程序234所生成的单一解 密块写入硬盘单元203的解密内容区域236的多个指令代码。
指令代码集S218包括指示将控制传递到指令代码集S214的多个 指令代码。
(c)播放程序233
播放程序233包括指令代码集S218、S219和S220，如图10所 示，这些指令代码集在播放程序233中按规定顺序排列。每个指令代 码集包括一个或者多个指令代码。
指令代码集S218包括用于指示从存储器单元203的解密内容区 域236中读出至少一个解密块的多个指令代码。
指令代码集S219包括用于指示根据所读出的解密块生成视频数 据和音频数据，转换所生成的视频数据和音频数据，并经由显示控制 单元205将最终的视频信号和音频信号输出到监视器208的多个指令 代码。
指令代码集S220包括用于指示将控制传递给指令代码集S218 的下一个步骤的指令代码。
(d)解密程序234
解密程序234包括解密控制模块241，扩展密钥生成模块242、 加法模块243、旋转模块A244、旋转模块B245、旋转模块C246以 及旋转模块D247，如图11所示。
每个模块都是包括机器语言形式的指令代码的组合的程序。机器 语言格式能够被微处理器201解码和执行。
由于扩展密钥生成模块242、旋转模块A244、旋转模块B245、 旋转模块C246以及旋转模块D247分别与图5所示的扩展密钥生成 模块142、旋转模块A143、旋转模块B144、旋转模块C145以及旋 转模块D146相同，因此在此省略了对它们的描述。
解密控制模块241
解密控制模块241包括指令代码集S221到S240，如图12和图 13所示，并且这些指令代码集在解密控制模块241中按照规定顺序 排列。每个指令代码集包括一个或多个指令代码。
指令代码集S221包括用于指示从调用解密控制模块241的调用 程序接收单一密文块M和密钥K的多个指令代码。注意，一个块是 64比特长的数据。
指令代码集S222包括用于指示调用所接收的密钥K和扩展密钥 生成模块242的多个指令代码。执行指令代码集S222导致生成8个 扩展密钥K1、K2、K3、...、K8。
指令代码集S223包括定义数据M1的指令代码，和定义数据M2 的指令代码。数据M1是所接收的密文M的32个最重要比特，数据 M2是所接收的密文M的32个最不重要比特。
指令代码集S224包括用于指示对数据M1和数据M2进行XOR 运算，并将该运算结果存储在变量TMP1中的多个指令代码。TMP1＝ M1 XOR M2
指令代码集S225包括用于指示利用变量TMP1和扩展密钥K1 调用加法模块243，并将运算结果存储在变量TMP2中的多个指令代 码。其结果是，加法模块243计算出TMP2＝TMP1+K1。
指令代码集S226包括用于指示利用变量TMP2调用旋转模块 A244，并将运算结果存储在变量TMP3中的多个指令代码。
TMP3＝Rot2(TMP2)+TMP2+1
指令代码集S227包括指示利用变量TMP3调用旋转模块B245， 并将运算结果存储在变量TMP4中的多个指令代码。
TMP4＝Rot4(TMP3)XOR TMP3
指令代码集S228包括用于指示对变量TMP4和数据M1执行 XOR运算，并将运算结果存储在变量TMP5中的多个指令代码。
TMP5＝TMP4 XOR M1
指令代码集S229包括用于指示利用变量TMP5和扩展密钥K2 调用加法模块243，并将运算结果存储在变量TMP6中的多个指令代 码。其结果是，加法模块243计算出TMP6＝TMP5+K2。
指令代码集S230包括用于指示利用变量TMP6调用旋转模块 A244，并将运算结果存储在变量TMP7中的多个指令代码。
TMP7＝Rot2(TMP6)+TMP6+1
指令代码集S231包括用于指示利用变量TMP7调用旋转模块 C246，并将运算结果存储在变量TMP8中的多个指令代码。
TMP8＝Rot8(TMP7)XOR TMP7
指令代码集S232包括用于指示利用变量TMP8和扩展密钥K3 调用加法模块243，并将运算结果存储在变量TMP9中的多个指令代 码。其结果是，加法模块243计算出TMP9＝TMP8+K3。
指令代码集S233包括用于指示利用变量TMP9调用旋转模块 A244，并将运算结果存储在变量TMP10中的多个指令代码。
TMP10＝Rot2(TMP9)+TMP9+1
指令代码集S234包括用于指示利用变量TMP7和变量TMP10 调用旋转模块D247，并将运算结果存储在变量TMP11中的多个指令 代码。
TMP11＝Rot16(TMP10)+(TMP10 AND TMP7)
指令代码集S235包括用于指示对TMP11和变量TMP1执行XOR 运算，并将运算结果存储在变量TMP12中的多个指令代码。
TMP12＝TMP11 XOR TMP1
指令代码集S236包括用于指示利用变量TMP12和扩展密钥K4 调用加法模块243，并将运算结果存储在变量TMP13中的多个指令 代码。其结果是，加法模块243计算出TMP13＝TMP12+K4。
指令代码集S237包括用于指示利用变量TMP13调用旋转模块 A244，并将运算结果存储在变量TMP14中的多个指令代码。
TMP14＝Rot2(TMP13)+TMP13+1
指令代码集S238包括用于指示对变量TMP14和变量TMP4执 行XOR运算，并将运算结果存储在变量TMP15中的多个指令代码。
TMP15＝TMP14 XOR TMP4
指令代码集S239包括用于指示对变量TMP15和变量TMP12执 行XOR运算，并将运算结果存储在变量TMP16中的多个指令代码。
TMP16＝TMP15 XOR TMP12
指令代码集S240包括用于指示将以变量TMP15作为32个最重 要比特并以变量TMP16作为最不重要比特的64比特整数作为解密文 本M输出到调用程序的多个指令代码。
加法模块243
加法模块243是用于根据输入数据a和b中计算数据a+b，并 输出数据a+b的程序。如图14所示，加法模块包括转换单元251、 主计算单元252和逆转换单元253。转换单元251包括参数存储单元 261和幂运算单元262。主计算单元252包括参数存储单元263和乘 法单元264。逆转换单元253包括参数存储单元265、离散对数计算 单元266和CRT(中国剩余定理(chinese Remainder Theorem))单元 267。
(i)每个参数和符号的定义，以及输入数据条件的描述
以下给出对各种参数和符号的定义，并描述关于加法模块243的 输入数据的条件。
假设pi(i＝1，2，...，k)为相互不同的素数。每个pi(i＝1，2，...，k) 表示小素数，从而假定p1＝3，p2＝5，p3＝7，p4＝13，...以及k＝17。 假设n为这些素数的乘积p1×p2×...×pk，其中符号“×”表示乘法。 乘积n可以是能够用大约64比特表述的数。在该情况下，k＝17，n＝ p1×p2×...×pk＞264。
由逆转换单元253存储pi(i＝1，2，...，k)，并且由转换单元251和 主计算单元252存储n。
加法模块243在由整数模n(integer modulo n)所组成的整数剩 余环(interger residue ring)Z/nZ中执行乘法群运算，假设g为属于 该乘法群的预先分配的值，并且是pi(i＝1，2，...，k)的本原元素 (primitive elemenet)。
假定g为pi(i＝1，2，...，k)的本原元素，这意味着对于每个pi，g 都有值，使得当m为1，2，...中的给定值时，满足gm＝1mod pi的 m的第一个值是pi-1。
假设L＝LCM(p1-1，p2-1，...，pk-1)，其中LCM(p1-1，p2-1，...，pk-1) 表示p1-1，p2-1，...，pk-1的最小公倍数。
输入数据a和b中每个都是小于L/2的非负整数。
(ii)转换单元251的构造
转换单元251包括参数存储单元261和幂运算单元262。
参数存储单元261存储n和g。
幂运算单元262接收输入数据a和b，对于所接收的输入数据a 和b计算
ga＝ga mod n和
gb＝gb mod n，
并将得到的ga和gb输出到主计算单元252。
(iii)主计算单元252的结构
主计算单元252包括参数存储单元263和乘法单元264。
参数存储单元263存储参数n。
乘法单元264从幂运算单元262接收ga和gb，并对于所接收的 ga和gb计算
gab＝ga×gb mod n，
并将得到的gab输出到逆转换单元253。
(iv)逆转换单元253的构造
逆转换单元253包括参数存储单元265，离散对数计算单元266 和CRT单元267。
参数存储单元265存储p1，p2，...，pk。
离散对数计算单元266从乘法单元264接收gab，并相对于底g mod pi计算gab mod pi(i＝1，2，...，k)的离散对数ci mod pi-1。
换句话说，离散对数计算单元266计算满足gab＝gci mod pi-1(i＝ 1，2，...，k)的cimod pi-1(i＝1，2，...，k)，然后将得到的cimod pi-1(i＝ 1，2，...，k)输出到CRT单元267。
对于利用离散对数计算单元266计算ci mod pi-1，存在各种计算 方法。以下是一种这样的方法。
在此，按照规定的顺序将w置为1，2，3，...，以找到满足gw＝ gab mod pi的w。并将由此而找到的w指定为ci。或者，对于每个pi 的计算结果g1，g2，...，g(Pi-2)mod pi可以被存储为表格，并且对表 格进行搜索以找到等于gab mod pi的gw的值。这随后给出w的值来表 示为ci。
CRT单元267从离散对数计算单元266接收ci mod pi-1(i＝1， 2，...，k)，并采用中国剩余定理从所接收的cimod pi-1(i＝1，2，...，k) 中找到相对于底g mod n的gab mod n的离散对数c mod L。换句话说， CRT单元267找到满足ci＝c mod pi-1(i＝1，2，...，k)的c。
为了使用中国剩余定理从离散对数cimod pi-1(i＝1，2，...，k)中 找到c mod L(其中L＝LCM(p1-1，p2-1，...，pk-1))，采用了以下方 法。
为了避免复杂表示，假设mi＝pi-1。
首先，计算：
u2＝m1×(m1 -1mod(m2/GCD(m1，m2)))×(c2-c1)+c1
其中GCD(a，b，c，...)表示a，b，c，...的最大公约数。
接下来，计算
u3＝(m1×m2)×((m1×m2)-1mod(m3/GCD(m1，m2，m3)))×(c3-u2)+u2， 和
u4＝(m1×m2×m3)×((m1×m2×m3)-1mod(m4/GCD(m1，m2，m3，m4))) ×(c4-u3)+u3
类似地，按照该顺序计算u1，u2，...，uk-1，。最后，计算以下：
uk＝(m1×m2×m3×...×mk-1)×((m1×m2×m3×mk-1)-1mod (mk/GCD(m1，m2，m3，m4，...，mk-4)))×(ck-uk-1)+uk-1
接下来，计算c＝uk以获得c。
注意，在非专利文献2中详细描述了采用CRT 267从ci(i＝1，2，...， k)中计算满足c mod pi-1＝ci的c mod L的方法。
接下来，CRT单元267将所获得的c输出到调用加法模块243 的调用程序。
(v)使用加法模块243的加法运算
参考图15所示的流程图描述使用加法模块243的加法运算。
幂运算单元262从调用加法模块243的调用程序接收输入数据a 和b(步骤S301)，并对输入数据a和b计算ga＝gamod n和gb＝gbmod n(步骤S302和S303)。
接下来，乘法单元264针对ga和gb计算gab＝ga×gb mod n(步骤 S304)。
接下来，离散对数计算单元266找到满足gab＝gci mod pi(i＝1， 2，...，k)的ci mod pi-1(i＝1，2，...，k)(步骤S305)。CRT单元267找 到满足ci＝c mod pi-1(i＝1，2，...，k)的c(步骤S306)，并将所获得 的c输出到调用加法模块243的调用程序(步骤S307)。
(vi)加法模块的加法运算的验证
以下验证加法模块243输出对应于输入数据a，b的数据a+b。
在转换单元251中针对输入数据a和b计算ga＝ga mod n和gb＝ gb mod n，并且在主计算单元252中计算gab＝ga×gb mod n。在该阶段， 明显的是，满足gab＝g(a+b) mod n。
逆转换单元253根据g和gab计算满足gab＝gci mod pi(i＝1，2，...， k)的ci，并且计算c mod L以满足c＝ci mod pi-1。在此，c满足gab ＝gc mod n。这是因为a+b＝c mod L给出g(a+b-c)＝1 mod n。因此， 由于c满足g(a+b)mod n＝gc mod n，c还满足a+b＝c mod((p1-1)×(p2 -1)×...×(pk-1))。a＜L/2和b＜L/2给出a+b＜L。因此，加法模块 243将输出数据a+b，其为数据a和数据b的和。
1.4第一实施例的效果
加法模块243转换要相加的值。注意，即使是在难以对转换单元 251和逆转换单元253进行分析时，也存在分析者将发现值ga，gb和 gc，并且发现根据ga和gb计算gab的处理的风险。然而，即使是在发 现值ga，gb和gab的情况下，仍然难以从转换值ga和gb中推断未转换 值a和b。此外，加法模块243在主计算单元252中执行乘法，并且 难以从该乘法运算中推断出加法模块243实际上实现了加法。从而， 第一实施例的效果是可以不仅隐藏加法运算的输入值，而且还可以隐 藏运算本身。
解密控制单元241当将密钥加到其他数据上时使用加法模块 243。从而，难以推断出要加的值，包括密钥的值在内。此外，即使 是分析者知道加密算法，对他们来说也难以推断出密钥加法部分正在 执行涉及密钥的加法。因此，由于发现密钥加法部分困难，即使是分 析者执行攻击来专门发现加密算法的密钥加法部分特征也将具有难 度。因此，本实施例在使得分析者的攻击变得困难时是有效的。
2.第二实施例
可以使用加法模块501取代第一实施例中的加法模块243。以下 描述加法模块501。
2.1加法模块501的构造
加法模块501是用于根据数据a和b计算数据a+b并输出数据 a+b的程序，与加法模块243类似。加法模块501包括转换单元511、 主计算单元512和逆转换单元513，如图16所示。转化单元511包 括参数存储单元521、随机数生成单元522和幂运算单元523。主计 算单元512包括参数存储单元524和乘法单元525。逆转换单元513 包括参数存储单元526、离散对数计算单元527和归约单元528。
2.2每个参数和符号的定义，以及输入数据条件的描述
以下给出在加法模块501中所使用的每个参数和符号的定义，并 描述输入数据条件。
假设p和q为素数，并且假设n＝p2×q。逆转换单元513存储p 和q，转换单元511和主计算单元512存储n。
加法模块501使用由整数模n组成的整数剩余环Z/nZ的乘法群 运算。假设g为属于乘法群的预先分配的值，并且使得g(p-1)mod p2 的阶(order)为p。此外，假设gp被定义为g(p-1)mod p2。
输入数据a和b中每个都为小于p/2的非负数。
2.3转换单元511的构造
转化单元511包括参数存储单元521、随机数生成单元522和幂 运算单元523。
参数存储单元521存储参数n和g。
随机数生成单元522生成随机数R1和R2，两者都不大于n。
幂运算单元523使用由随机数生成单元522计算的随机数R1和 R2，针对输入数据a和b计算：
ga＝g^(a+n×R1)mod n，以及
gb＝g^(b十n×R2)mod n
在该说明书中，符号“^”是表示幂的运算符。例如，a^b＝ab。 在该说明书中，a^b和ab类型的表示的使用不同是为了表示方便。
接下来，幂运算单元523将结果ga和gb输出到主计算单元512。
2.4主计算单元512的构造
主计算单元512包括参数存储单元524和乘法单元525。
参数存储单元524存储n。
乘法单元525从幂运算单元523接收计算结果ga和gb，对所接 收的ga和gb计算gab＝ga×gb，并将结果gab输出到逆转换单元513。
2.5逆转换单元513的构造
逆转换单元513包括参数存储单元526、离散对数计算单元527 和归约单元528。
参数存储单元526存储参数p。
离散对数计算单元527从乘法单元525接收计算结果gab，并使 用存储在参数存储单元526中的参数p对所接收的gab计算：
cp＝gab (p-1)mod p2，
并随后将cp输出到归约单元528。
归约单元528从离散对数计算单元527接收cp，使用所接收到的 cp计算相对于底gp mod p2的cp的离散对数c，并将所获得的离散对数 c输出到调用程序。
在专利文献2中详细描述了在归约单元528中c的计算方法。在 实际中，其包括以下内容。
归约单元为cp找到满足c＝(cp-1)/(gp-1)mod p的c。
2.6加法模块501的加法运算
参考图17所示的流程图描述加法模块501的加法运算。
幂运算单元523从调用程序接收输入数据a和b(步骤S311)， 随机数生成单元522生成随机数R1和R2，并且两者都不大于n(步 骤S312)，并且幂运算单元523计算：
ga＝g^(a+n×R1)mod n，和
gb＝g^(b+n×R2)mod n(步骤S313到S314)。
注意，在本说明书中，符号“^”时表示幂的运算符。例如a^b＝ ab。在本说明书中，“a^b”和“ab”两种类型的表示可以在不同的时 间内使用。
接下来，乘法单元525计算gab＝ga×gb mod n(步骤S315)。
接下来，离散对数计算单元527计算cp＝gab (p-1)mod p2(步骤 S316)，归约单元528找到c，使得c＝(cp-1)/(gp-1)mod p(步骤 S317)，并且随后将c(＝a+b)输出到调用程序(步骤S318)。
2.7加法模块501的加法运算的验证
以下验证加法模块501针对输入数据a和b输出a+b。
在转换单元511中，对于a和b计算：
ga＝g^(a+n×R1)mod n，和
gb＝g^(b+n×R2)mod n。
在主计算单元512中，计算gab＝ga×gb mod n。在此阶段，显然 满足gab＝g^(a+b+n×(R1+R2))mod n。逆转换单元513计算
cp＝gab (p-1)＝gp^(a+b+n×(R1+R2))mod p2，
根据gp p＝1 mod p2，
gp n＝1 mod p2，
得到cp＝gp (a+b)mod p2。
转换单元513找到相对于底gp mod p2的cp的离散对数c。换句 话说，满足cp＝gp c mod p2。因此，c＝a+b mod p。此外，a＜p/2和b ＜p/2给出a+b＜p。因此，加法模块501将输出输入数据a和b的加 法结果。
2.8加法模块501的效果
加法模块501对要相加的值进行转换。假如转换单元511和逆转 换单元513难以分析，则难以从所转换的值中推断出未转换的值。此 外，加法模块501在主计算单元512中执行乘法，难以从乘法运算中 推断出来加法模块501实际上是实现了加法。因此，加法模块501的 效果是不仅可以隐藏加法的输入值，还可以隐藏加法运算本身。
2.9注解(1)
在加法模块501中，转换单元511执行整数剩余环Z/nZ的乘法 群中的幂运算。逆转换单元513解决了整数剩余环Z/p2Z的乘法群中 的离散对数问题，其中整数剩余环Z/p2Z的乘法群是整数剩余环Z/nZ 的乘法群的子群。考虑分析者不知道p和q但是已经能够发现在转换 单元511中正在执行幂运算的情况。在该情况下，仅仅逆转换单元 513难以分析。然而，如果n足够大，以至于难以进行素数因数分解 (1024比特的量级)，则p和q非常难以获得，因为这样做将需要n 的素数因数分解。在不能获得p和q的情况下，整数剩余环Z/nZ的 乘法群中的离散对数问题是困难的。通常当乘法群的大小(元素的数 目)大(例如，1024比特的量级)时，该群中的离散对数问题是困 难的。在加法模块501中，如果已知p，通过逆转换单元243中的逆 转换就容易地解决乘法群Z/p2Z中的离散对数问题。加法模块501与 加法模块243的不同之处在于，加法模块501使用了以下事实：如果 p已知则容易进行逆转换，但是如果p未知则难以进行逆转换。
2.10注解(2)
加法模块501可以包括如下。
假设p和q为素数，并且n＝pm×q，其中m为整数。加法模块 501使用由整数模n组成的整数剩余环的乘法群中的计算。假设g为 预先分配的属于其中g(p-1)mod pm的阶为p的乘法群的数值。此外， 定义gp＝g(p-1)mod pm。
离散对数计算单元527从乘法单元525中接收计算结果gab，并 使用存储在参数存储单元526中的素数p计算：
cp＝gab (p-1)mod pm
并随后将cp输出到归约单元528。
归约单元528从离散对数计算单元527接收cp，并计算相对于 gp模pm的cp的离散对数c，并将所获得的c输出到调用程序。
3.修改(2)
加法模块601可以用于取代第一实施例中的加法模块243。以下 描述加法模块601。加法模块601使用椭圆曲线上的标量乘法。非专 利文献3中详细描述了椭圆曲线。
3.1加法模块601的构造
加法模块601是用于对于输入数据a和b计算并输出数据a+b 的程序，类似于加法模块243。如图18所示，加法模块601包括转 换单元611、主计算单元612和逆转换单元613。转换单元611包括 参数存储单元621和标量乘法单元622。主计算单元612包括参数存 储单元623和椭圆曲线加法单元624，以及逆转换单元613包括参数 存储单元625、归约单元626和离散对数计算单元627。
3.2每个参数和符号的定义，以及输入数据条件
以下描述给出了加法模块601所使用的各种参数和符号的定义， 并描述了输入数据条件。
假设p和q为素数，以及假设n＝p×q。逆转换单元613存储p 和q，并且转换单元611和主计算单元612存储n。
假设椭圆曲线E的等式为
y2＝x3+A×x+B，其中A和B为椭圆曲线E的参数。
假设G＝(xg，yg)mod n为在椭圆曲线E上满足yg 2＝xg 3+A×xg+B mod n的点。
转换单元611、主计算单元612和逆转换单元613存储A、B和 G。
由满足椭圆曲线E的等式的域GF(p)中的点组成的群被表示为 E(GF(p))。类似地，由满足椭圆曲线E的等式的域GF(q)中的点组成 的群被表示为E(GF(q))。
在Z/nZ上的椭圆曲线群被表示为E(GF(p))和E(GF(q))的积，其 为E(GF(p))×E(GF(q))。注意，由于Z/nZ是环而不是域，因此从数学 上讲不能将E(GF(p))×E(GF(q))称为椭圆曲线。然而，为了方便， E(GF(p))×E(GF(q))被称为在Z/nZ上的直积椭圆曲线群。
对于在Z/nZ上的椭圆曲线E(GF(p))×E(GF(q))的点G＝(xg，yg) mod n，该点对应于E(GF(p))中的点Gp＝(xgp，ygp)mod p和对应于 E(GF(q))中的点Gq＝(xgq，ygq)mod q，将xg定义为满足以下的数：
xg mod p＝xgp和
xg mod q＝xgq
并且将yg定义为满足以下的数：
yg mod p＝ygp和
yg mod q＝ygq。
根据该定义，与E(GF(p))×E(GF(q))中的点G＝(xg，yg)对应的 E(GF(p))中的点Gp为：
Gp＝(xgp，ygp)mod p
E(GF(q))中的点Gq为：
Gq＝(xgq，ygq)。
因此，E(GF(p))和E(GF(q))被认为是E(GF(p))×E(GF(q))的子群。
在加法单元601中，椭圆曲线E是其阶(曲线上的点的数量)为 p的模p的椭圆曲线。域GF(p)上的这种椭圆曲线已知为不规则椭圆 曲线。
此外，椭圆曲线E是模q的椭圆曲线。这意味着GF(q)也是不规 则椭圆曲线。
在Z/Zn上的椭圆曲线已知为超不规则椭圆曲线。超不规则椭圆 曲线在非专利文献4中进行了描述。
在Z/Zn上的椭圆曲线群是E(GF(p))×E(GF(q))，这意味着该椭圆 曲线的阶为
n(＝p×q)。
输入数据a和b为小于p/2的非负数。
3.3转换单元611的构造
转换单元611包括参数存储单元621和标量乘法单元622。参数 存储单元621存储参数n、A、B和G。
标量乘法单元622从调用程序接收输入数据a和b，使用存储在 参数存储单元621中的n、A、B和G对所接收的输入数据a和b计 算：
Ga＝a*G mod n
Gb＝b*G mod n。
注意，a*G是通过使用椭圆曲线加法将多个G加在一起而获得的 点。此外，a*Gmodn是对a*G的每个坐标执行模n实现的。
标量乘法单元622将计算结果Ga和Gb输出到主计算单元612。
3.4主计算单元612的构造
主计算单元612包括参数存储单元623和椭圆曲线加法单元624。
椭圆曲线加法单元624从标量乘法单元622接收计算结果Ga和 Gb，使用在参数存储单元623中存储的n、A、B和G对Ga和Gb执 行椭圆曲线加法，以计算
Gab＝Ga+Gb mod n，
并将计算结果Gab输出到逆转换单元613。
3.5逆转换单元613的构造
逆转换单元61包括参数存储单元625、归约单元626和离散对 数计算单元627。
参数存储单元625存储p、A、B和G mod p。
归约单元626从椭圆曲线加法单元624接收计算结果Gab，并对 所接收的Gab，使用在参数存储单元625中存储的p计算
Gabp＝Gab mod p，
并将计算结果输出到离散对数计算单元627。
离散对数计算单元627计算相对于底G mod p的Gabp的离散对数 c mod p。换句话说，离散对数计算单元627找到满足Gabp＝c*G的c。 接下来，离散对数计算单元627将c输出到调用程序。
注意，离散对数计算单元627所找到的c是不规则椭圆曲线上的 离散对数问题的解决方案。在非专利文献3，第88页到91页详细描 述了用于解决不规则椭圆曲线上的离散对数问题的方法，因此这里省 略了对该方法的描述。
3.6加法模块601的运算
参考图19所示的流程图描述加法模块601的运算。
标量乘法单元622从调用程序接收输入数据a和b(步骤S321)， 并且使用在参数存储单元621中存储的n、A、B和G对所接收的输 入数据a和b计算：
Ga＝a*Gmodn和
Gb＝b*Gmodn(步骤S322和S323)。
接下来，椭圆曲线加法单元624计算
Gab＝Ga+Gb mod n(步骤S324)。
接下来，归约单元626计算
Gabp＝Gab mod p(步骤S325)。
离散对数计算单元627计算相对于底G mod p的Gabp的离散对 数c(步骤S326)，并随后将c输出到调用程序(步骤S327)。
3.7加法模块601的运算验证
以下验证加法模块601对于输入数据a和b输出a+b。
在转换单元611中对于a和b计算：
Ga＝a*G mod n和
Gb＝b*G mod n，
并在主计算单元612中计算Gab＝Ga+Gb mod n。
显然，在该点上满足Gab＝(a+b)*G。
转换单元613首先计算
Gabp＝Gab mod p，
然后计算相对于G mod p的Gabp的离散对数c。换句话说，计算 c以满足Gapb＝c*Gmodp。
因此，c＝a+b mod p。此外，a＜p/2和b＜p/2得到a+b＜p。 因此，给定输入数据a和b，加法模块601输出a+b的结果。
3.8加法模块601的效果
加法模块601采用与加法模块243和加法模块501类似的方法对 值进行转换。假如转换单元611和逆转换单元613难以分析，则该转 换使得难以从所转换的值中推断出非转换值。
加法模块601在主计算单元612中执行椭圆曲线加法。难以从椭 圆曲线运算中推断出加法模块601实际上实现了加法。
因此，加法模块601的效果是不仅可以隐藏加法的输入值，还可 以隐藏加法运算本身。
3.9注释
在加法模块601中，转换单元执行通过在Z/nZ上的椭圆曲线形 成的群E(GF(p))×E(GF(q))中的标量乘法，逆转换单元解决了在子群 E(GF(p))中的离散对数问题。
在企图分析该程序的人发现在转换单元中正在执行幂运算但是 不知道p和q的情况下，仅仅逆转换单元难以分析。
然而，如果n足够大，以至于难以进行素数因数分解(例如，1024 比特的量级)，则难以获得p和q，因为这样做将需要n的素数因数 分解。在不能获得p和q的情况下，解决在Z/nZ上的椭圆曲线形成 的群E(GF(p))×E(GF(q))中的离散对数问题就是困难的。
通常，当群的大小(元素数量)很大(例如，1024比特的量级) 时，解决群中的离散对数问题是困难的。在加法模块601的情况下， 如果p已知，通过逆转换单元中的逆转换可以容易解决椭圆曲线群中 的离散对数问题。加法模块601所执行的转换与第一实施例的那些转 换不同之处在于，它们使用了以下事实：如果p已知则容易进行逆转 换，但是如果p未知则难以进行逆转换。
其他示例性修改
尽管已经基于以上实施例描述了本发明，但是本发明并不限于这 些实施例。以下修改也包括在本发明中。
(1)加法模块243、501和601被描述为执行两个非负整数的加 法，但是加法模块还可以执行三个或者更多个非负整数的加法。在该 情况下，讨论中的加法模块的转换单元转换每个非负数。接下来，在 加法模块243和501中的情况下，主计算单元使用转换结果执行乘法。 在加法模块601的情况下，主计算单元使用转换结果执行椭圆曲线加 法。
(2)加法模块243、501和601仅仅描述为在解密控制模块241 的密钥加法部分中使用，但是每个加法模块都可以在解密控制模块的 其他加法部分中使用。
(3)在第一实施例中，加法模块在解密控制模块241中使用， 但是加法模块可以在加密控制模块141中、在另一加密程序中或者在 签名生成程序中使用。本发明能够类似地应用于任何使用加法的信息 处理运算中。
(4)在加法模块243、501和601中，使用了整数剩余环乘法群 和椭圆曲线上的群，但是可以使用其他类型的群。
还要注意的是，尽管在加法模块243和501中通过执行幂运算来 转换整数，并在加法模块601中通过执行椭圆曲线标量乘法来转换整 数，但是可以使用其他与群相关的幂运算来转换整数。
注意，幂运算是指基本群运算，例如在整数剩余环中的乘法或者 椭圆曲线上的群中的椭圆曲线加法，其被重复多次。
因此，整数剩余环中的乘法群是取幂，椭圆曲线上的群中的幂运 算是椭圆曲线标量乘法。
在加法模块501中，在整数剩余环Z/p2Z的乘法群中解决了离散 对数问题，其中整数剩余环Z/p2Z的乘法群是整数剩余环Z/nZ的乘 法群的子群。当使用不同的群时，与加法模块501的转换单元类似的 转换单元可以解决在不同群的子群中的离散对数问题。
(5)在加法模块243中，g是pi(i＝1，2，...，k)中的本原根，但 是g不必是本原根。
当g不是本原根时，对于mi假设L＝m1×m2×...×mk，其中gmi＝ 1mod pi(mi＞0)。
(6)特别是，上述设备是每个都包括微处理器、ROM、RAM、 硬盘单元、显示器单元、键盘、鼠标等等的计算机系统。程序被记录 在RAM中或硬盘单元中。该程序由表示对计算机的指令的指令代码 的组合组成。每个设备通过微处理器根据该程序进行操作来实现其功 能。简而言之，微处理器一次一个地读出程序中的指令代码，对所读 出的指令代码进行解码，并根据该结果进行操作。
(7)一些或者所有构成上述设备的组件可以使用单一系统LSI (大规模集成电路)构建。系统LSI是使用集成在单一芯片上的多个 组件构建的超多功能LSI。特别是，它是被构造为包括微处理器、 ROM、RAM等等的计算机系统。RAM中存储程序。系统LSI通过 微处理器根据该程序进行操作来实现其功能。
(8)一些或者所有构成上述设备的组件可以使用可拆卸的IC卡 或者单元模块构建。IC卡或者模块是由微处理器、ROM、RAM等等 构建的计算机系统。IC卡或者模块可以包括多功能LSI。IC卡或者 模块通过微处理器根据程序进行操作来实现其功能。IC卡或者模块 可以是防窜改的。
(9)本发明可以是上述的方法。此外，本发明可以是使用计算 机实现这些方法的程序，或者是由程序组成的数字信号。
此外，本发明可以具有记录在其上的程序或者数字信号的计算机 可读记录介质，其示例包括软盘、硬盘、CD-ROM、MO、DVD、 DVD-ROM、DVD-RAM、BD(蓝光光盘)以及半导体存储器等等。 或者，本发明可以是记录在这些记录介质中任意一个上的程序或者数 字信号。
此外，本发明还可以是通过网络等等广播或者传送的程序或者数 字信号，其典型的示例包括电话通信线、无线或者电缆通信线以及因 特网。
此外，本发明还可以是具有微处理器和存储器的计算机系统，其 中存储器存储程序，并且微处理器根据该程序操作。
此外，还可以通过转送记录介质上所记录的程序或者数字信号， 或者通过经过网络等等转送程序或者数字信号，来使用独立计算机系 统实现程序或数字信号。
(10)本发明可以是以上实施例和修改的任意组合。
(11)如上所述，本发明不是简单地实现对运算中使用的值的隐 藏，本发明还实现了隐藏运算本身。因此本发明能够被有用地包括在 扰码软件中或者诸如IC卡之类的设备中。
工业适用范围
在所有必须要安全可靠地处理信息的工业中，本发明的设备、方 法和程序能够被有管理地使用，以及重复地使用。构成本发明的设备、 方法和程序能够在生产电子设备的制造工业中被重复制造并销售。
以下描述作为本发明的第一实施例的内容发送系统10。
1.1内容发送系统10的构造
内容发送系统10包括内容服务器100、发送服务器300a、广播 设备300b、BD制造设备300c、个人计算机200、数字广播接收器200a 以及BD播放器200b，如图1所示。
内容服务器100存储由视频和音频数据构成的电影内容，根据来 自发送服务器300a的请求，通过对所存储的内容进行加密来生成加 密内容，并将所生成的加密内容发送到通过专用线路21连接的发送 服务器300a。发送服务器300a接收加密内容，并将该加密内容发送 到经由因特网20与发送服务器300a连接的个人计算机200。个人计 算机200接收加密内容，通过对所接收的加密内容进行解密来生成解 密内容，并通过播放所生成的解密内容来输出视频和声音。
类似地，内容服务器100根据来自广播设备300b的请求生成加 密内容，并将所生成的加密内容发送到通过专用线路22连接的广播 设备300b。广播设备300b接收加密内容，在载波电波上广播所接收 的加密内容。数字广播接收器200a接收广播电波，从广播电波中提 取加密内容，通过对所提取的加密内容进行解密来生成解密内容，并 通过播放所生成的解密内容来输出视频和声音。
类似地，内容服务器100根据来自BD制造设备300c的请求生 成加密内容，并将所生成的加密内容发送到通过专用线路23连接的 BD制造设备300c。BD制造设备300c接收加密内容，将所接收的加 密内容写入记录介质400。将其中具有加密内容的记录介质400投入 市场并卖给用户。当用户装载记录介质400时，BD播放器200b从记 录介质400中读出加密内容，并通过对所读出的加密内容进行解密来 生成解密内容，并通过播放所生成的解密内容来输出视频和声音。
1.2内容服务器100
内容服务器100是包括微处理器101、硬盘单元102、存储器单 元103、输入控制单元104、显示控制单元105、通信单元106等等 的计算机系统，如图2所示。输入控制单元104和显示控制单元105 分别连接到键盘107和监视器108。通信单元106分别通过专用线路 21、22和23连接到发送服务器300a、广播设备300b和BD制造设 备300c。
硬盘单元102和存储器单元103中存储了各种程序，内容服务器 100通过根据程序操作的微处理器101实现了其功能的一部分。
(1)硬盘单元102
硬盘单元102存储如图2所示的内容120、内容121、内容122、...、 密钥123、密钥124和密钥125、...，以及没有描述的其他程序。硬 盘单元102具有用于存储加密内容126、加密内容127、加密内容128... 的区域。
内容120、内容121、内容122、...，分别对应于密钥123、密钥 124、密钥125、...，并且还分别对应于加密内容126、加密内容127、 加密内容128、...。
内容120、内容121、内容122、...中的每一个都是包含已经被 高效压缩编码的视频和音频数据的数据。
密钥123、密钥124、密钥125、...是被用来通过对内容120、内 容121、内容122、...应用加密算法而生成加密内容126、加密内容 127、加密内容128的加密密钥。密钥123、密钥124、密钥125中的 每一个的长度都是64比特。加密算法将在以下章节中介绍。
加密内容126、加密内容127、加密内容128、...是通过分别对 内容120、内容121、内容122、...应用加密算法而生成的加密数据。
(2)存储器单元103
存储器单元103存储如图2所示的内容发送程序131、内容加密 程序132、加密程序133和发送程序134，以及未描述的其他程序。 这些程序中的每一个都由机器语言格式的指令编码的组合所组成。机 器语言格式能够被微处理器101解码和执行。
以下是对每个程序的内容的描述。为了确保每个程序的细节能够 容易理解，采用流程图而不是机器语言格式的指令来表示每个程序的 内容。
(a)内容发送程序131
内容发送程序131包括指令代码集S101、S102、S103和S104， 这些指令代码集在内容发送程序131中按照规定顺序排列，如图3所 示。每个指令代码集都包括一个或者多个指令代码。
指令代码集S101包括用于指示从内容服务器100的管理员接收 内容的指定，或者从内容的发送目的地设备接收内容的指定的多个指 令代码。
指令代码集S102包括用于指示接收内容的发送目的地设备的指 定的多个指令代码。
指令代码集S103包括用于指示指定由所接受或所接收的指定所 指示的内容，调用内容加密程序132，然后将由内容加密程序132所 生成的加密内容作为加密内容126写入硬盘单元102的多个指令代 码。
指令代码集S104包括用于指示指定所接收的指定和被生成并被 写入硬盘单元102中的加密内容的发送目的地设备，以及调用发送程 序134的多个指令代码。通过执行指令代码集S104，将所生成的加 密内容发送到所指定的发送目的地设备
(b)内容加密程序132
内容加密程序132包括指令集S111、S112、S113、S114、S115 和S116，这些指令代码集在内容加密程序132中按照规定顺序排列， 如图4所示。每个指令代码集都包括一个或者多个指令代码。
指令代码集S111包括用于指示将“-64”作为初始值而分配给读 出点的多个指令代码。所述读出点表示在指定内容中的比特中的数据 位置。该指令代码集还指示从硬盘单元102读出与指定内容对应的密 钥。具有初始值“-64”的读出点指示该内容之外的位置。将初始值 “-64”分配给该读出点，从而使得当以下所述的指令代码集S112第 一次执行时，该读出点指示在该内容首部的位置。在以下所述的指令 代码集S112第一次执行时，将该读出点加上64比特，然后该读出点 变为“0”，其指示内容首部。
指令代码集S112包括用于指示将该读出点加上64比特，然后读 出从由该最终的读出点所指示的内容中的位置处开始的数据块的多 个指令代码。所述多个指令代码集还指示，如果该读出点所指示的位 置位于内容中，则从该位置处读出该数据块，并且如果该读出点所指 示的位置位于内容之外，则输出用于指示对该块的读出已经结束的结 束代码。在此，一个块是具有64比特长度的数据。
指令代码集S113包括用于指示如果从指令代码集S112输出结束 代码，则结束内容加密程序132的处理的多个指令代码。所述多个指 令代码集还指示，如果没有输出结束代码，则将控制传递到随后的指 令代码集S114。
指令代码集S114包括指示用于利用所读出的密钥和所读出的第 一块调用加密程序133的多个指令代码。
指令代码集S115包括用于指示将加密程序133所生成的单一加 密块作为加密内容126的一部分写入硬盘单元102的多个指令代码。
指令代码集S116包括用于指示将控制传递到指令代码集S112的 指令代码。
(c)加密程序133
加密程序133包括加密控制模块141、扩展密钥生成模块142、 旋转模块A143、旋转模块B144、旋转模块C145以及旋转模块D146， 如图5所示。
每个模块都是包括机器语言形式的指令代码的组合的程序。机器 语言格式能够被微处理器101解码和执行。
扩展密钥生成模块142
扩展密钥生成模块142包括用于从调用程序接收64比特密钥K， 使用所接收的密钥K生成8个扩展密钥K1、K2、K3、...、K8，并 将8个所生成的扩展密钥K1、K2、K3、...、K8输出到调用程序的 多个指令代码。
注意，由于在专利文献3中对用于生成扩展密钥的方法进行了描 述，因此在此省略。
旋转模块A143
旋转模块A143包括用于指示从调用程序接收32比特数据X， 并对于数据X执行运算Rot2(X)+X+1，并将运算结果输出到调用程 序的多个指令代码。
Rot2(X)表示对32-比特数据X的向左2比特循环移位。32比特 数据X的向左2比特循环移位是指，将数据X分割为2个最重要比 特X1和30个最不重要比特X2，将X2移位到数据X的30个最重要 比特，并将X1移位到2个最不重要比特。
旋转模块B144
旋转模块B144包括用于指示从调用程序接收32比特数据X，并 对于数据X执行运算Rot4(X)XOR X，并将运算结果输出到调用程序 的多个指令代码。
Rot4(X)表示数据X的向左4比特循环移位，而XOR表示异或 操作。32比特数据X的向左4比特循环移位是指，将数据X分割为 4个最重要比特X1和28个最不重要比特X2，将X2移位到数据X 的28个最重要比特，并将X1移位到4个最不重要比特。
旋转模块C145
旋转模块C145包括用于指示从调用程序接收32比特数据X，并 对于数据X执行运算Rot8(X)XOR X，并将运算结果输出到调用程序 的多个指令代码。
Rot8(X)表示数据X的向左8比特循环移位。32比特数据X的向 左8比特循环移位是指，将数据X分割为8个最重要比特X1和24 个最不重要比特X2，将X2移位到数据X的24个最重要比特，并将 X1移位到8个最不重要比特上。
旋转模块D146
旋转模块D146包括用于指示从调用程序接收32比特数据X和 32比特数据Y，并对于数据X和数据Y执行运算Rot16(X)+(XAND Y)，并将运算结果输出到调用程序的多个指令代码。
Rot16(X)表示数据X的向左16比特循环移位，而AND表示逻 辑积。32比特数据X的向左16比特循环移位是指，将数据X分割 为16个最重要比特X1和16个最不重要比特X2，将X2移位到数据 X的16个最重要比特，并将X1移位到16个最不重要比特。
加密控制模块141
加密控制模块141包括在加密控制模块141中按照规定顺序排列 的指令集S121到S140，如图6和图7所示。每个指令代码集包括一 个或多个指令代码。
指令代码集S121包括用于指示从调用加密控制模块141的调用 程序接收单一明文块M和密钥K的多个指令代码。注意，一个块是 64比特长的数据。
指令代码集S122包括用于指示利用所接收的密钥K调用扩展密 钥生成模块142的多个指令代码。指令代码集S122的执行导致生成 8个扩展密钥K1、K2、K3、...、K8。
指令代码集S123包括用于定义数据M1的指令代码，和定义数 据M2的指令代码。数据M1是所接收的明文M的32个最重要比特， 数据M2是所接收的明文M的32个最不重要比特。
指令代码集S124包括用于指示对数据M1和数据M2执行XOR 运算，并将结果存储在变量TMP1中的多个指令代码。
TMP1＝M1 XOR M2
指令代码集S125包括用于指示执行变量TMP1与扩展密钥K1 的加法，并将运算结果存储在变量TMP2中的多个指令代码。
TMP2＝TMP1+K1
指令代码集S126包括用于指示利用变量TMP2调用旋转模块 A143，并将运算结果存储在变量TMP3中的多个指令代码。
TMP3＝Rot2(TMP2)+TMP2+1
指令代码集S127包括用于指示利用变量TMP3调用旋转模块 B144，并将结果存储在变量TMP4中的多个指令代码。
TMP4＝Rot4(TMP3)XOR TMP3
指令代码集S128包括用于指示对变量TMP4和数据M1执行 XOR运算，并将结果存储在变量TMP5中的多个指令代码。
TMP5＝TMP4 XOR M1
指令代码集S129包括用于指示对变量TMP5和扩展密钥K2求 和，并将运算结果存储在变量TMP6中的多个指令代码。
TMP6＝TMP5+K2
指令代码集S130包括用于指示利用变量TMP6调用旋转模块 A143，并将运算结果存储在变量TMP7中的多个指令代码。
TMP7＝Rot2(TMP6)+TMP6+1
指令代码集S131包括用于指示利用变量TMP7调用旋转模块 C145，并将运算结果存储在变量TMP8中的多个指令代码。
TMP8＝Rot8(TMP7)XOR TMP7
指令代码集S132包括用于指示将变量TMP8与扩展密钥K3相 加，并将结果存储在变量TMP9中的多个指令代码。
TMP9＝TMP8+K3
指令代码集S 133包括用于指示利用变量TMP9调用旋转模块 A143，并将运算结果存储在变量TMP10中的多个指令代码。
TMP10＝Rot2(TMP9)+TMP9+1
指令代码集S134包括用于指示利用变量TMP7和变量TMP10 调用旋转模块D146，并将运算结果存储在变量TMP11中的多个指令 代码。
TMP11＝Rot16(TMP10)+(TMP10AND TMP7)
指令代码集S135包括用于指示对TMP11和变量TMP1执行XOR 运算，并将运算结果存储在变量TMP12中的多个指令代码。
TMP12＝TMP11 XOR TMP1
指令代码集S136包括用于指示将变量TMP12与扩展密钥K4相 加，并将运算结果存储在变量TMP13中的多个指令代码。
TMP13＝TMP12+K4
指令代码集S137包括用于指示利用变量TMP13调用旋转模块 A143，并将运算结果存储在变量TMP14中的多个指令代码。
TMP14＝Rot2(TMP13)+TMP13+1
指令代码集S138包括用于指示对变量TMP14和变量TMP4执 行XOR运算，并将运算结果存储在变量TMP15中的多个指令代码。
TMP15＝TMP14 XOR TMP4
指令代码集S139包括用于指示对变量TMP15和变量TMP12执 行XOR运算，并将运算结果存储在变量TMP16中的多个指令代码。
TMP16＝TMP15 XOR TMP12
指令代码集S140包括用于指示将以变量TMP15作为其32个最 重要比特并以变量TMP16作为其最不重要比特的64比特整数作为密 文C输出到调用程序的多个指令代码。
(d)发送程序134
发送程序134(未描述)包括按顺序排列的多个指令代码，并包 括用于指示从调用程序接收数据的指定和发送目的地设备的指定，并 控制通信单元106以使得所指定的数据发送到所指定的发送目的地 设备的多个指令代码。
1.3个人计算机200
个人计算机200包括微处理器201、硬盘单元202、存储器单元 203、输入控制单元204、显示控制单元205、通信单元206等，如图 8所示。输入控制单元204和显示控制单元205分别连接到键盘207 和显示器208。此外，通信单元706连接到因特网20。
硬盘单元202和存储器单元203中存储了各种程序，并且个人计 算机200根据微处理器201依照程序进行操作实现其功能的一部分。
注意，数字广播接收器200a和BD播放器200b的描述被省略， 这是由于所述设备具有与个人计算机200中的那些设备类似的构造。
(1)硬盘单元202
硬盘单元202存储密钥222并具有用于存储加密内容221的区 域，如图8所示。加密内容221对应于密钥222。
加密内容221和密钥222分别与在内容服务器100的硬盘单元 102中存储的加密内容126和密钥123相同。
(2)存储器单元203
存储器单元203存储内容接收程序231、内容解密程序232、播 放程序233、解密程序234和加法程序235，如图8所示。此外，存 储器单元203包括解密内容区域236。这些程序中的每一个都是包括 机器语言格式的指令代码的组合的程序。机器语言格式能够被微处理 器201解码和执行。
对加密内容进行解密，并将所生成的解密内容暂时写入解密内容 区域236中。
以下是各种程序的详细描述，为了使各个程序的描述容易理解， 采用了流程图而不是机器语言格式的指令来表示每个程序。
(a)内容接收程序231
内容接收程序231包括按照规定顺序排列的指令代码集S201、 S202、S203和S204，如图9所示。每个指令代码集包括一个或者多 个指令代码。
指令代码集S201包括用于指示从个人计算机200的用户接收内 容的指定的多个指令代码。
指令代码集S202包括用于指示获取用于识别其指定已经被接收 的内容的内容标识符，并经由通信单元206和因特网20将所获取的 内容标识符发送到发送服务器300a的多个指令代码。
指令代码集S203包括用于指示经由因特网20和通信单元206 从发送服务器300a接收加密内容的多个指令代码。注意，所接收的 加密内容是由所述内容标识符所识别的加密内容。
指令代码群S204包括用于指示将所接收到的加密内容作为加密 内容221写入硬盘单元202的多个指令代码。
(b)内容解密程序232
内容解密程序232包括指令代码集S211、S212、S213、S214、 S215、S216、S217和S218，并且这些指令代码集在内容解密程序232 中按照规定顺序排列，如图10所示。每个指令代码集包括一个或者 多个指令代码。
指令代码集S211包括用于指示从个人计算机200的用户接收在 硬盘单元202中存储的加密内容之一的指定的多个指令代码。
指令代码集S212包括用于指示调用在存储器203中存储的播放 程序233的多个指令代码。执行指令代码集212使得并行执行内容解 密程序232和播放程序233。
指令代码集S213包括用于指示将“-64”作为初始值分配给用于 表示所指定的加密内容中的比特中的数据位置的读出点，随后从硬盘 单元202中读出与所指定的加密内容对应的密钥的多个指令代码。
指令代码集S214包括用于指示对所述读出点加上64比特，然后 试图读出从由最终读出点所指示的加密内容中的位置开始的数据块 的多个指令代码。所述多个指令代码还指示，如果所述读出点指示的 位置位于加密内容内，则从该位置处读出数据块，如果所述读出点指 示的位置位于加密内容之外，则输出表示该块读出已经结束的结束代 码。注意，一个块是具有64比特长度的数据。
指令代码集215包括用于指示如果从指令代码集S214输出结束 代码，则结束内容解密程序232的处理，并且如果没有输出结束代码， 则将控制传递到随后的指令代码集216的多个指令代码。
指令代码集S216包括用于指示利用所读出的密钥和所读出的第 一块调用解密程序234的多个指令代码。
指令代码集S217包括用于指示将解密程序234所生成的单一解 密块写入硬盘单元203的解密内容区域236的多个指令代码。
指令代码集S218包括指示将控制传递到指令代码集S214的多个 指令代码。
(c)播放程序233
播放程序233包括指令代码集S218、S219和S220，如图10所 示，这些指令代码集在播放程序233中按规定顺序排列。每个指令代 码集包括一个或者多个指令代码。
指令代码集S218包括用于指示从存储器单元203的解密内容区 域236中读出至少一个解密块的多个指令代码。
指令代码集S219包括用于指示根据所读出的解密块生成视频数 据和音频数据，转换所生成的视频数据和音频数据，并经由显示控制 单元205将最终的视频信号和音频信号输出到监视器208的多个指令 代码。
指令代码集S220包括用于指示将控制传递给指令代码集S218 的下一个步骤的指令代码。
(d)解密程序234
解密程序234包括解密控制模块241，扩展密钥生成模块242、 加法模块243、旋转模块A244、旋转模块B245、旋转模块C246以 及旋转模块D247，如图11所示。
每个模块都是包括机器语言形式的指令代码的组合的程序。机器 语言格式能够被微处理器201解码和执行。
由于扩展密钥生成模块242、旋转模块A244、旋转模块B245、 旋转模块C246以及旋转模块D247分别与图5所示的扩展密钥生成 模块142、旋转模块A143、旋转模块B144、旋转模块C145以及旋 转模块D146相同，因此在此省略了对它们的描述。
解密控制模块241
解密控制模块241包括指令代码集S221到S240，如图12和图 13所示，并且这些指令代码集在解密控制模块241中按照规定顺序 排列。每个指令代码集包括一个或多个指令代码。
指令代码集S221包括用于指示从调用解密控制模块241的调用 程序接收单一密文块M和密钥K的多个指令代码。注意，一个块是 64比特长的数据。
指令代码集S222包括用于指示调用所接收的密钥K和扩展密钥 生成模块242的多个指令代码。执行指令代码集S222导致生成8个 扩展密钥K1、K2、K3、...、K8。
指令代码集S223包括定义数据M1的指令代码，和定义数据M2 的指令代码。数据M1是所接收的密文M的32个最重要比特，数据 M2是所接收的密文M的32个最不重要比特。
指令代码集S224包括用于指示对数据M1和数据M2进行XOR 运算，并将该运算结果存储在变量TMP1中的多个指令代码。TMP1＝ M1 XOR M2
指令代码集S225包括用于指示利用变量TMP1和扩展密钥K1 调用加法模块243，并将运算结果存储在变量TMP2中的多个指令代 码。其结果是，加法模块243计算出TMP2＝TMP1+K1。
指令代码集S226包括用于指示利用变量TMP2调用旋转模块 A244，并将运算结果存储在变量TMP3中的多个指令代码。
TMP3＝Rot2(TMP2)+TMP2+1
指令代码集S227包括指示利用变量TMP3调用旋转模块B245， 并将运算结果存储在变量TMP4中的多个指令代码。
TMP4＝Rot4(TMP3)XOR TMP3
指令代码集S228包括用于指示对变量TMP4和数据M1执行 XOR运算，并将运算结果存储在变量TMP5中的多个指令代码。
TMP5＝TMP4 XOR M1
指令代码集S229包括用于指示利用变量TMP5和扩展密钥K2 调用加法模块243，并将运算结果存储在变量TMP6中的多个指令代 码。其结果是，加法模块243计算出TMP6＝TMP5+K2。
指令代码集S230包括用于指示利用变量TMP6调用旋转模块 A244，并将运算结果存储在变量TMP7中的多个指令代码。
TMP7＝Rot2(TMP6)+TMP6+1
指令代码集S231包括用于指示利用变量TMP7调用旋转模块 C246，并将运算结果存储在变量TMP8中的多个指令代码。
TMP8＝Rot8(TMP7)XOR TMP7
指令代码集S232包括用于指示利用变量TMP8和扩展密钥K3 调用加法模块243，并将运算结果存储在变量TMP9中的多个指令代 码。其结果是，加法模块243计算出TMP9＝TMP8+K3。
指令代码集S233包括用于指示利用变量TMP9调用旋转模块 A244，并将运算结果存储在变量TMP10中的多个指令代码。
TMP10＝Rot2(TMP9)+TMP9+1
指令代码集S234包括用于指示利用变量TMP7和变量TMP10 调用旋转模块D247，并将运算结果存储在变量TMP11中的多个指令 代码。
TMP11＝Rot16(TMP10)+(TMP10 AND TMP7)
指令代码集S235包括用于指示对TMP11和变量TMP1执行XOR 运算，并将运算结果存储在变量TMP12中的多个指令代码。
TMP12＝TMP11 XOR TMP1
指令代码集S236包括用于指示利用变量TMP12和扩展密钥K4 调用加法模块243，并将运算结果存储在变量TMP13中的多个指令 代码。其结果是，加法模块243计算出TMP13＝TMP12+K4。
指令代码集S237包括用于指示利用变量TMP13调用旋转模块 A244，并将运算结果存储在变量TMP14中的多个指令代码。
TMP14＝Rot2(TMP13)+TMP13+1
指令代码集S238包括用于指示对变量TMP14和变量TMP4执 行XOR运算，并将运算结果存储在变量TMP15中的多个指令代码。
TMP15＝TMP14 XOR TMP4
指令代码集S239包括用于指示对变量TMP15和变量TMP12执 行XOR运算，并将运算结果存储在变量TMP16中的多个指令代码。
TMP16＝TMP15 XOR TMP12
指令代码集S240包括用于指示将以变量TMP15作为32个最重 要比特并以变量TMP16作为最不重要比特的64比特整数作为解密文 本M输出到调用程序的多个指令代码。
加法模块243
加法模块243是用于根据输入数据a和b中计算数据a+b，并 输出数据a+b的程序。如图14所示，加法模块包括转换单元251、 主计算单元252和逆转换单元253。转换单元251包括参数存储单元 261和幂运算单元262。主计算单元252包括参数存储单元263和乘 法单元264。逆转换单元253包括参数存储单元265、离散对数计算 单元266和CRT(中国剩余定理(chinese Remainder Theorem))单元 267。
(i)每个参数和符号的定义，以及输入数据条件的描述
以下给出对各种参数和符号的定义，并描述关于加法模块243的 输入数据的条件。
假设pi(i＝1，2，...，k)为相互不同的素数。每个pi(i＝1，2，...，k) 表示小素数，从而假定p1＝3，p2＝5，p3＝7，p4＝13，...以及k＝17。 假设n为这些素数的乘积p1×p2×...×pk，其中符号“×”表示乘法。 乘积n可以是能够用大约64比特表述的数。在该情况下，k＝17，n＝ p1×p2×...×pk＞264。
由逆转换单元253存储pi(i＝1，2，...，k)，并且由转换单元251和 主计算单元252存储n。
加法模块243在由整数模n(integer modulo n)所组成的整数剩 余环(interger residue ring)Z/nZ中执行乘法群运算，假设g为属于 该乘法群的预先分配的值，并且是pi(i＝1，2，...，k)的本原元素 (primitive elemenet)。
假定g为pi(i＝1，2，...，k)的本原元素，这意味着对于每个pi，g 都有值，使得当m为1，2，...中的给定值时，满足gm＝1mod pi的 m的第一个值是pi-1。
假设L＝LCM(p1-1，p2-1，...，pk-1)，其中LCM(p1-1，p2-1，...，pk-1) 表示p1-1，p2-1，...，pk-1的最小公倍数。
输入数据a和b中每个都是小于L/2的非负整数。
(ii)转换单元251的构造
转换单元251包括参数存储单元261和幂运算单元262。
参数存储单元261存储n和g。
幂运算单元262接收输入数据a和b，对于所接收的输入数据a 和b计算
ga＝ga mod n和
gb＝gb mod n，
并将得到的ga和gb输出到主计算单元252。
(iii)主计算单元252的结构
主计算单元252包括参数存储单元263和乘法单元264。
参数存储单元263存储参数n。
乘法单元264从幂运算单元262接收ga和gb，并对于所接收的 ga和gb计算
gab＝ga×gb mod n，
并将得到的gab输出到逆转换单元253。
(iv)逆转换单元253的构造
逆转换单元253包括参数存储单元265，离散对数计算单元266 和CRT单元267。
参数存储单元265存储p1，p2，...，pk。
离散对数计算单元266从乘法单元264接收gab，并相对于底g mod pi计算gab mod pi(i＝1，2，...，k)的离散对数ci mod pi-1。
换句话说，离散对数计算单元266计算满足gab＝gci mod pi-1(i＝ 1，2，...，k)的cimod pi-1(i＝1，2，...，k)，然后将得到的cimod pi-1(i＝ 1，2，...，k)输出到CRT单元267。
对于利用离散对数计算单元266计算ci mod pi-1，存在各种计算 方法。以下是一种这样的方法。
在此，按照规定的顺序将w置为1，2，3，...，以找到满足gw＝ gab mod pi的w。并将由此而找到的w指定为ci。或者，对于每个pi 的计算结果g1，g2，...，g(Pi-2)mod pi可以被存储为表格，并且对表 格进行搜索以找到等于gab mod pi的gw的值。这随后给出w的值来表 示为ci。
CRT单元267从离散对数计算单元266接收ci mod pi-1(i＝1， 2，...，k)，并采用中国剩余定理从所接收的cimod pi-1(i＝1，2，...，k) 中找到相对于底g mod n的gab mod n的离散对数c mod L。换句话说， CRT单元267找到满足ci＝c mod pi-1(i＝1，2，...，k)的c。
为了使用中国剩余定理从离散对数cimod pi-1(i＝1，2，...，k)中 找到c mod L(其中L＝LCM(p1-1，p2-1，...，pk-1))，采用了以下方 法。
为了避免复杂表示，假设mi＝pi-1。
首先，计算：
u2＝m1×(m1 -1mod(m2/GCD(m1，m2)))×(c2-c1)+c1
其中GCD(a，b，c，...)表示a，b，c，...的最大公约数。
接下来，计算
u3＝(m1×m2)×((m1×m2)-1mod(m3/GCD(m1，m2，m3)))×(c3-u2)+u2， 和
u4＝(m1×m2×m3)×((m1×m2×m3)-1mod(m4/GCD(m1，m2，m3，m4))) ×(c4-u3)+u3
类似地，按照该顺序计算u1，u2，...，uk-1，。最后，计算以下：
uk＝(m1×m2×m3×...×mk-1)×((m1×m2×m3×mk-1)-1mod (mk/GCD(m1，m2，m3，m4，...，mk-4)))×(ck-uk-1)+uk-1
接下来，计算c＝uk以获得c。
注意，在非专利文献2中详细描述了采用CRT 267从ci(i＝1，2，...， k)中计算满足c mod pi-1＝ci的c mod L的方法。
接下来，CRT单元267将所获得的c输出到调用加法模块243 的调用程序。
(v)使用加法模块243的加法运算
参考图15所示的流程图描述使用加法模块243的加法运算。
幂运算单元262从调用加法模块243的调用程序接收输入数据a 和b(步骤S301)，并对输入数据a和b计算ga＝gamod n和gb＝gbmod n(步骤S302和S303)。
接下来，乘法单元264针对ga和gb计算gab＝ga×gb mod n(步骤 S304)。
接下来，离散对数计算单元266找到满足gab＝gci mod pi(i＝1， 2，...，k)的ci mod pi-1(i＝1，2，...，k)(步骤S305)。CRT单元267找 到满足ci＝c mod pi-1(i＝1，2，...，k)的c(步骤S306)，并将所获得 的c输出到调用加法模块243的调用程序(步骤S307)。
(vi)加法模块的加法运算的验证
以下验证加法模块243输出对应于输入数据a，b的数据a+b。
在转换单元251中针对输入数据a和b计算ga＝ga mod n和gb＝ gb mod n，并且在主计算单元252中计算gab＝ga×gb mod n。在该阶段， 明显的是，满足gab＝g(a+b) mod n。
逆转换单元253根据g和gab计算满足gab＝gci mod pi(i＝1，2，...， k)的ci，并且计算c mod L以满足c＝ci mod pi-1。在此，c满足gab ＝gc mod n。这是因为a+b＝c mod L给出g(a+b-c)＝1 mod n。因此， 由于c满足g(a+b)mod n＝gc mod n，c还满足a+b＝c mod((p1-1)×(p2 -1)×...×(pk-1))。a＜L/2和b＜L/2给出a+b＜L。因此，加法模块 243将输出数据a+b，其为数据a和数据b的和。
1.4第一实施例的效果
加法模块243转换要相加的值。注意，即使是在难以对转换单元 251和逆转换单元253进行分析时，也存在分析者将发现值ga，gb和 gc，并且发现根据ga和gb计算gab的处理的风险。然而，即使是在发 现值ga，gb和gab的情况下，仍然难以从转换值ga和gb中推断未转换 值a和b。此外，加法模块243在主计算单元252中执行乘法，并且 难以从该乘法运算中推断出加法模块243实际上实现了加法。从而， 第一实施例的效果是可以不仅隐藏加法运算的输入值，而且还可以隐 藏运算本身。
解密控制单元241当将密钥加到其他数据上时使用加法模块 243。从而，难以推断出要加的值，包括密钥的值在内。此外，即使 是分析者知道加密算法，对他们来说也难以推断出密钥加法部分正在 执行涉及密钥的加法。因此，由于发现密钥加法部分困难，即使是分 析者执行攻击来专门发现加密算法的密钥加法部分特征也将具有难 度。因此，本实施例在使得分析者的攻击变得困难时是有效的。
2.第二实施例
可以使用加法模块501取代第一实施例中的加法模块243。以下 描述加法模块501。
2.1加法模块501的构造
加法模块501是用于根据数据a和b计算数据a+b并输出数据 a+b的程序，与加法模块243类似。加法模块501包括转换单元511、 主计算单元512和逆转换单元513，如图16所示。转化单元511包 括参数存储单元521、随机数生成单元522和幂运算单元523。主计 算单元512包括参数存储单元524和乘法单元525。逆转换单元513 包括参数存储单元526、离散对数计算单元527和归约单元528。
2.2每个参数和符号的定义，以及输入数据条件的描述
以下给出在加法模块501中所使用的每个参数和符号的定义，并 描述输入数据条件。
假设p和q为素数，并且假设n＝p2×q。逆转换单元513存储p 和q，转换单元511和主计算单元512存储n。
加法模块501使用由整数模n组成的整数剩余环Z/nZ的乘法群 运算。假设g为属于乘法群的预先分配的值，并且使得g(p-1)mod p2 的阶(order)为p。此外，假设gp被定义为g(p-1)mod p2。
输入数据a和b中每个都为小于p/2的非负数。
2.3转换单元511的构造
转化单元511包括参数存储单元521、随机数生成单元522和幂 运算单元523。
参数存储单元521存储参数n和g。
随机数生成单元522生成随机数R1和R2，两者都不大于n。
幂运算单元523使用由随机数生成单元522计算的随机数R1和 R2，针对输入数据a和b计算：
ga＝g^(a+n×R1)mod n，以及
gb＝g^(b十n×R2)mod n
在该说明书中，符号“^”是表示幂的运算符。例如，a^b＝ab。 在该说明书中，a^b和ab类型的表示的使用不同是为了表示方便。
接下来，幂运算单元523将结果ga和gb输出到主计算单元512。
2.4主计算单元512的构造
主计算单元512包括参数存储单元524和乘法单元525。
参数存储单元524存储n。
乘法单元525从幂运算单元523接收计算结果ga和gb，对所接 收的ga和gb计算gab＝ga×gb，并将结果gab输出到逆转换单元513。
2.5逆转换单元513的构造
逆转换单元513包括参数存储单元526、离散对数计算单元527 和归约单元528。
参数存储单元526存储参数p。
离散对数计算单元527从乘法单元525接收计算结果gab，并使 用存储在参数存储单元526中的参数p对所接收的gab计算：
cp＝gab (p-1)mod p2，
并随后将cp输出到归约单元528。
归约单元528从离散对数计算单元527接收cp，使用所接收到的 cp计算相对于底gp mod p2的cp的离散对数c，并将所获得的离散对数 c输出到调用程序。
在专利文献2中详细描述了在归约单元528中c的计算方法。在 实际中，其包括以下内容。
归约单元为cp找到满足c＝(cp-1)/(gp-1)mod p的c。
2.6加法模块501的加法运算
参考图17所示的流程图描述加法模块501的加法运算。
幂运算单元523从调用程序接收输入数据a和b(步骤S311)， 随机数生成单元522生成随机数R1和R2，并且两者都不大于n(步 骤S312)，并且幂运算单元523计算：
ga＝g^(a+n×R1)mod n，和
gb＝g^(b+n×R2)mod n(步骤S313到S314)。
注意，在本说明书中，符号“^”时表示幂的运算符。例如a^b＝ ab。在本说明书中，“a^b”和“ab”两种类型的表示可以在不同的时 间内使用。
接下来，乘法单元525计算gab＝ga×gb mod n(步骤S315)。
接下来，离散对数计算单元527计算cp＝gab (p-1)mod p2(步骤 S316)，归约单元528找到c，使得c＝(cp-1)/(gp-1)mod p(步骤 S317)，并且随后将c(＝a+b)输出到调用程序(步骤S318)。
2.7加法模块501的加法运算的验证
以下验证加法模块501针对输入数据a和b输出a+b。
在转换单元511中，对于a和b计算：
ga＝g^(a+n×R1)mod n，和
gb＝g^(b+n×R2)mod n。
在主计算单元512中，计算gab＝ga×gb mod n。在此阶段，显然 满足gab＝g^(a+b+n×(R1+R2))mod n。逆转换单元513计算
cp＝gab (p-1)＝gp^(a+b+n×(R1+R2))mod p2，
根据gp p＝1 mod p2，
gp n＝1 mod p2，
得到cp＝gp (a+b)mod p2。
转换单元513找到相对于底gp mod p2的cp的离散对数c。换句 话说，满足cp＝gp c mod p2。因此，c＝a+b mod p。此外，a＜p/2和b ＜p/2给出a+b＜p。因此，加法模块501将输出输入数据a和b的加 法结果。
2.8加法模块501的效果
加法模块501对要相加的值进行转换。假如转换单元511和逆转 换单元513难以分析，则难以从所转换的值中推断出未转换的值。此 外，加法模块501在主计算单元512中执行乘法，难以从乘法运算中 推断出来加法模块501实际上是实现了加法。因此，加法模块501的 效果是不仅可以隐藏加法的输入值，还可以隐藏加法运算本身。
2.9注解(1)
在加法模块501中，转换单元511执行整数剩余环Z/nZ的乘法 群中的幂运算。逆转换单元513解决了整数剩余环Z/p2Z的乘法群中 的离散对数问题，其中整数剩余环Z/p2Z的乘法群是整数剩余环Z/nZ 的乘法群的子群。考虑分析者不知道p和q但是已经能够发现在转换 单元511中正在执行幂运算的情况。在该情况下，仅仅逆转换单元 513难以分析。然而，如果n足够大，以至于难以进行素数因数分解 (1024比特的量级)，则p和q非常难以获得，因为这样做将需要n 的素数因数分解。在不能获得p和q的情况下，整数剩余环Z/nZ的 乘法群中的离散对数问题是困难的。通常当乘法群的大小(元素的数 目)大(例如，1024比特的量级)时，该群中的离散对数问题是困 难的。在加法模块501中，如果已知p，通过逆转换单元243中的逆 转换就容易地解决乘法群Z/p2Z中的离散对数问题。加法模块501与 加法模块243的不同之处在于，加法模块501使用了以下事实：如果 p已知则容易进行逆转换，但是如果p未知则难以进行逆转换。
2.10注解(2)
加法模块501可以包括如下。
假设p和q为素数，并且n＝pm×q，其中m为整数。加法模块 501使用由整数模n组成的整数剩余环的乘法群中的计算。假设g为 预先分配的属于其中g(p-1)mod pm的阶为p的乘法群的数值。此外， 定义gp＝g(p-1)mod pm。
离散对数计算单元527从乘法单元525中接收计算结果gab，并 使用存储在参数存储单元526中的素数p计算：
cp＝gab (p-1)mod pm
并随后将cp输出到归约单元528。
归约单元528从离散对数计算单元527接收cp，并计算相对于 gp模pm的cp的离散对数c，并将所获得的c输出到调用程序。
3.修改(2)
加法模块601可以用于取代第一实施例中的加法模块243。以下 描述加法模块601。加法模块601使用椭圆曲线上的标量乘法。非专 利文献3中详细描述了椭圆曲线。
3.1加法模块601的构造
加法模块601是用于对于输入数据a和b计算并输出数据a+b 的程序，类似于加法模块243。如图18所示，加法模块601包括转 换单元611、主计算单元612和逆转换单元613。转换单元611包括 参数存储单元621和标量乘法单元622。主计算单元612包括参数存 储单元623和椭圆曲线加法单元624，以及逆转换单元613包括参数 存储单元625、归约单元626和离散对数计算单元627。
3.2每个参数和符号的定义，以及输入数据条件
以下描述给出了加法模块601所使用的各种参数和符号的定义， 并描述了输入数据条件。
假设p和q为素数，以及假设n＝p×q。逆转换单元613存储p 和q，并且转换单元611和主计算单元612存储n。
假设椭圆曲线E的等式为
y2＝x3+A×x+B，其中A和B为椭圆曲线E的参数。
假设G＝(xg，yg)mod n为在椭圆曲线E上满足yg 2＝xg 3+A×xg+B mod n的点。
转换单元611、主计算单元612和逆转换单元613存储A、B和 G。
由满足椭圆曲线E的等式的域GF(p)中的点组成的群被表示为 E(GF(p))。类似地，由满足椭圆曲线E的等式的域GF(q)中的点组成 的群被表示为E(GF(q))。
在Z/nZ上的椭圆曲线群被表示为E(GF(p))和E(GF(q))的积，其 为E(GF(p))×E(GF(q))。注意，由于Z/nZ是环而不是域，因此从数学 上讲不能将E(GF(p))×E(GF(q))称为椭圆曲线。然而，为了方便， E(GF(p))×E(GF(q))被称为在Z/nZ上的直积椭圆曲线群。
对于在Z/nZ上的椭圆曲线E(GF(p))×E(GF(q))的点G＝(xg，yg) mod n，该点对应于E(GF(p))中的点Gp＝(xgp，ygp)mod p和对应于 E(GF(q))中的点Gq＝(xgq，ygq)mod q，将xg定义为满足以下的数：
xg mod p＝xgp和
xg mod q＝xgq
并且将yg定义为满足以下的数：
yg mod p＝ygp和
yg mod q＝ygq。
根据该定义，与E(GF(p))×E(GF(q))中的点G＝(xg，yg)对应的 E(GF(p))中的点Gp为：
Gp＝(xgp，ygp)mod p
E(GF(q))中的点Gq为：
Gq＝(xgq，ygq)。
因此，E(GF(p))和E(GF(q))被认为是E(GF(p))×E(GF(q))的子群。
在加法单元601中，椭圆曲线E是其阶(曲线上的点的数量)为 p的模p的椭圆曲线。域GF(p)上的这种椭圆曲线已知为不规则椭圆 曲线。
此外，椭圆曲线E是模q的椭圆曲线。这意味着GF(q)也是不规 则椭圆曲线。
在Z/Zn上的椭圆曲线已知为超不规则椭圆曲线。超不规则椭圆 曲线在非专利文献4中进行了描述。
在Z/Zn上的椭圆曲线群是E(GF(p))×E(GF(q))，这意味着该椭圆 曲线的阶为
n(＝p×q)。
输入数据a和b为小于p/2的非负数。
3.3转换单元611的构造
转换单元611包括参数存储单元621和标量乘法单元622。参数 存储单元621存储参数n、A、B和G。
标量乘法单元622从调用程序接收输入数据a和b，使用存储在 参数存储单元621中的n、A、B和G对所接收的输入数据a和b计 算：
Ga＝a*G mod n
Gb＝b*G mod n。
注意，a*G是通过使用椭圆曲线加法将多个G加在一起而获得的 点。此外，a*Gmodn是对a*G的每个坐标执行模n实现的。
标量乘法单元622将计算结果Ga和Gb输出到主计算单元612。
3.4主计算单元612的构造
主计算单元612包括参数存储单元623和椭圆曲线加法单元624。
椭圆曲线加法单元624从标量乘法单元622接收计算结果Ga和 Gb，使用在参数存储单元623中存储的n、A、B和G对Ga和Gb执 行椭圆曲线加法，以计算
Gab＝Ga+Gb mod n，
并将计算结果Gab输出到逆转换单元613。
3.5逆转换单元613的构造
逆转换单元61包括参数存储单元625、归约单元626和离散对 数计算单元627。
参数存储单元625存储p、A、B和G mod p。
归约单元626从椭圆曲线加法单元624接收计算结果Gab，并对 所接收的Gab，使用在参数存储单元625中存储的p计算
Gabp＝Gab mod p，
并将计算结果输出到离散对数计算单元627。
离散对数计算单元627计算相对于底G mod p的Gabp的离散对数 c mod p。换句话说，离散对数计算单元627找到满足Gabp＝c*G的c。 接下来，离散对数计算单元627将c输出到调用程序。
注意，离散对数计算单元627所找到的c是不规则椭圆曲线上的 离散对数问题的解决方案。在非专利文献3，第88页到91页详细描 述了用于解决不规则椭圆曲线上的离散对数问题的方法，因此这里省 略了对该方法的描述。
3.6加法模块601的运算
参考图19所示的流程图描述加法模块601的运算。
标量乘法单元622从调用程序接收输入数据a和b(步骤S321)， 并且使用在参数存储单元621中存储的n、A、B和G对所接收的输 入数据a和b计算：
Ga＝a*Gmodn和
Gb＝b*Gmodn(步骤S322和S323)。
接下来，椭圆曲线加法单元624计算
Gab＝Ga+Gb mod n(步骤S324)。
接下来，归约单元626计算
Gabp＝Gab mod p(步骤S325)。
离散对数计算单元627计算相对于底G mod p的Gabp的离散对 数c(步骤S326)，并随后将c输出到调用程序(步骤S327)。
3.7加法模块601的运算验证
以下验证加法模块601对于输入数据a和b输出a+b。
在转换单元611中对于a和b计算：
Ga＝a*G mod n和
Gb＝b*G mod n，
并在主计算单元612中计算Gab＝Ga+Gb mod n。
显然，在该点上满足Gab＝(a+b)*G。
转换单元613首先计算
Gabp＝Gab mod p，
然后计算相对于G mod p的Gabp的离散对数c。换句话说，计算 c以满足Gapb＝c*Gmodp。
因此，c＝a+b mod p。此外，a＜p/2和b＜p/2得到a+b＜p。 因此，给定输入数据a和b，加法模块601输出a+b的结果。
3.8加法模块601的效果
加法模块601采用与加法模块243和加法模块501类似的方法对 值进行转换。假如转换单元611和逆转换单元613难以分析，则该转 换使得难以从所转换的值中推断出非转换值。
加法模块601在主计算单元612中执行椭圆曲线加法。难以从椭 圆曲线运算中推断出加法模块601实际上实现了加法。
因此，加法模块601的效果是不仅可以隐藏加法的输入值，还可 以隐藏加法运算本身。
3.9注释
在加法模块601中，转换单元执行通过在Z/nZ上的椭圆曲线形 成的群E(GF(p))×E(GF(q))中的标量乘法，逆转换单元解决了在子群 E(GF(p))中的离散对数问题。
在企图分析该程序的人发现在转换单元中正在执行幂运算但是 不知道p和q的情况下，仅仅逆转换单元难以分析。
然而，如果n足够大，以至于难以进行素数因数分解(例如，1024 比特的量级)，则难以获得p和q，因为这样做将需要n的素数因数 分解。在不能获得p和q的情况下，解决在Z/nZ上的椭圆曲线形成 的群E(GF(p))×E(GF(q))中的离散对数问题就是困难的。
通常，当群的大小(元素数量)很大(例如，1024比特的量级) 时，解决群中的离散对数问题是困难的。在加法模块601的情况下， 如果p已知，通过逆转换单元中的逆转换可以容易解决椭圆曲线群中 的离散对数问题。加法模块601所执行的转换与第一实施例的那些转 换不同之处在于，它们使用了以下事实：如果p已知则容易进行逆转 换，但是如果p未知则难以进行逆转换。
其他示例性修改
尽管已经基于以上实施例描述了本发明，但是本发明并不限于这 些实施例。以下修改也包括在本发明中。
(1)加法模块243、501和601被描述为执行两个非负整数的加 法，但是加法模块还可以执行三个或者更多个非负整数的加法。在该 情况下，讨论中的加法模块的转换单元转换每个非负数。接下来，在 加法模块243和501中的情况下，主计算单元使用转换结果执行乘法。 在加法模块601的情况下，主计算单元使用转换结果执行椭圆曲线加 法。
(2)加法模块243、501和601仅仅描述为在解密控制模块241 的密钥加法部分中使用，但是每个加法模块都可以在解密控制模块的 其他加法部分中使用。
(3)在第一实施例中，加法模块在解密控制模块241中使用， 但是加法模块可以在加密控制模块141中、在另一加密程序中或者在 签名生成程序中使用。本发明能够类似地应用于任何使用加法的信息 处理运算中。
(4)在加法模块243、501和601中，使用了整数剩余环乘法群 和椭圆曲线上的群，但是可以使用其他类型的群。
还要注意的是，尽管在加法模块243和501中通过执行幂运算来 转换整数，并在加法模块601中通过执行椭圆曲线标量乘法来转换整 数，但是可以使用其他与群相关的幂运算来转换整数。
注意，幂运算是指基本群运算，例如在整数剩余环中的乘法或者 椭圆曲线上的群中的椭圆曲线加法，其被重复多次。
因此，整数剩余环中的乘法群是取幂，椭圆曲线上的群中的幂运 算是椭圆曲线标量乘法。
在加法模块501中，在整数剩余环Z/p2Z的乘法群中解决了离散 对数问题，其中整数剩余环Z/p2Z的乘法群是整数剩余环Z/nZ的乘 法群的子群。当使用不同的群时，与加法模块501的转换单元类似的 转换单元可以解决在不同群的子群中的离散对数问题。
(5)在加法模块243中，g是pi(i＝1，2，...，k)中的本原根，但 是g不必是本原根。
当g不是本原根时，对于mi假设L＝m1×m2×...×mk，其中gmi＝ 1mod pi(mi＞0)。
(6)特别是，上述设备是每个都包括微处理器、ROM、RAM、 硬盘单元、显示器单元、键盘、鼠标等等的计算机系统。程序被记录 在RAM中或硬盘单元中。该程序由表示对计算机的指令的指令代码 的组合组成。每个设备通过微处理器根据该程序进行操作来实现其功 能。简而言之，微处理器一次一个地读出程序中的指令代码，对所读 出的指令代码进行解码，并根据该结果进行操作。
(7)一些或者所有构成上述设备的组件可以使用单一系统LSI (大规模集成电路)构建。系统LSI是使用集成在单一芯片上的多个 组件构建的超多功能LSI。特别是，它是被构造为包括微处理器、 ROM、RAM等等的计算机系统。RAM中存储程序。系统LSI通过 微处理器根据该程序进行操作来实现其功能。
(8)一些或者所有构成上述设备的组件可以使用可拆卸的IC卡 或者单元模块构建。IC卡或者模块是由微处理器、ROM、RAM等等 构建的计算机系统。IC卡或者模块可以包括多功能LSI。IC卡或者 模块通过微处理器根据程序进行操作来实现其功能。IC卡或者模块 可以是防窜改的。
(9)本发明可以是上述的方法。此外，本发明可以是使用计算 机实现这些方法的程序，或者是由程序组成的数字信号。
此外，本发明可以具有记录在其上的程序或者数字信号的计算机 可读记录介质，其示例包括软盘、硬盘、CD-ROM、MO、DVD、 DVD-ROM、DVD-RAM、BD(蓝光光盘)以及半导体存储器等等。 或者，本发明可以是记录在这些记录介质中任意一个上的程序或者数 字信号。
此外，本发明还可以是通过网络等等广播或者传送的程序或者数 字信号，其典型的示例包括电话通信线、无线或者电缆通信线以及因 特网。
此外，本发明还可以是具有微处理器和存储器的计算机系统，其 中存储器存储程序，并且微处理器根据该程序操作。
此外，还可以通过转送记录介质上所记录的程序或者数字信号， 或者通过经过网络等等转送程序或者数字信号，来使用独立计算机系 统实现程序或数字信号。
(10)本发明可以是以上实施例和修改的任意组合。
(11)如上所述，本发明不是简单地实现对运算中使用的值的隐 藏，本发明还实现了隐藏运算本身。因此本发明能够被有用地包括在 扰码软件中或者诸如IC卡之类的设备中。
工业适用范围
在所有必须要安全可靠地处理信息的工业中，本发明的设备、方 法和程序能够被有管理地使用，以及重复地使用。构成本发明的设备、 方法和程序能够在生产电子设备的制造工业中被重复制造并销售。