密钥共享系统、共享密钥生成装置及共享密钥复原装置

摘要

提供一种能防止在加密装置和解密装置之间导出不同的密钥的内容分配系统。加密装置(110d)的随机数生成部(112d)生成随机数，第1函数部(113d)生成随机数的函数值G(s)，根据函数值G(s)生成验证值a和共享密钥K，加密部(114d)使用公开密钥多项式h生成验证值a的第1加密文c1，第2函数部(115d)生成验证值a和第1加密文c1的函数值H(a、c1)，随机数屏蔽部(116d)生成c2＝s xor H(a、c1)。解密装置(120d)使用秘密密钥多项式f对第1加密文进行解密后生成解密验证值，第3函数部(124d)生成验证值a’和第1加密文c1的函数值H(a’、c1)，随机数除去部(125d)生成解密随机数s’＝c2 xor H(a’、c1)，第4函数部(126d)生成解密随机数s’的散列函数值G(s’)，根据函数值G(s’)生成验证值a”和共享密钥K’，比较部(127d)在解密验证值a’和验证值a”相等时，输出共享密钥K’。

说明书

技术领域

本发明涉及作为信息安全技术的密码技术，特别涉及不让第3者知道而配送密钥的技术。

背景技术

过去，为了从发送装置向接收装置秘密发送信息，使用了公开密钥密码方式。

在公开密钥密码方式中，发送装置使用接收装置的公开密钥加密后再发送通信内容，接收装置接收已加密的通信内容，并使用自身的秘密密钥对已接收的通信内容进行解密，得到原来的通信内容。(例如，参照非专利文献1)。

1996年，作为可高速处理的公开密钥密码，提出了NTRU密码(例如，参照非专利文献2)。在NTRU密码中，因使用可进行高速运算的多项式运算进行加密和解密，故若与进行幂乘运算的RSA密码或进行椭圆曲线上点的标量乘积运算的椭圆曲线密码比较，利用软件可以进行比现有的公开密钥密码更高速的处理。

但是，在该NTRU密码中，当使用公开密钥对明码文加密后生产加密文，并使用正规的秘密密钥对加密文解密后生成解密文时，会产生解密文与原来的明码文不同的情况。将该现象称作发生解密错误。再有，作为避免解密错误的方法，公开了一种对明码文添加附加信息后再加密，并和明码文的散列函数值一起发送的方法(例如，参照非专利文献1)。

另一方面，近年来，作为公开密钥密码的新概念，提出了称之为密钥密封机制(Key Encapsulation Mechanisms)的方式(例如，参照非专利文献3)。该密钥密封机制是使用公开密钥密码在发送装置和接收装置之间进行共享密钥配送的算法，发送装置将接收者的公开密钥pk输给加密算法E，再生成加密文C和共享密钥K，并将加密文C传送给接收装置。其次，接收装置将秘密密钥sk和加密文C输给解密算法D，再求出和发送装置相同的共享密钥K。

这样，在使用密钥密封机制使发送装置和接收装置对共享密钥K进行共享之后，发送装置利用公共密钥密码方式并使用共享密钥K对应向接收装置发送的明码文进行加密，生成加密文，并将生成的加密文发送给接收装置。接收装置接收加密文，利用上述公共密钥密码方式并使用共享密钥K对已接收的加密文进行解密，再生成解密文。

密钥密封机制的过去所没有的特征在于，在从发送者向接收者单方向发送信息，但发送者不能有意生成共享密钥，从而限制了发送者的非法行为。

作为这样的密钥密封机制，公开了一种称之为PSEC-KEM的算法(例如，参照非专利文献3和非专利文献4)。下面，说明非专利文献4中记载的PSEC-KEM算法。

(1)PSEC-KEM的系统参数

PSEC-KEM具有以下系统参数。

.椭圆曲线：E

.椭圆曲线上的位数n的点：P

.散列函数：G、H

再有，关于椭圆曲线、位数及散列函数，在非专利文献1中已有详细记载，这里省略其说明。

(2)PSEC-KEM的公开密钥和秘密密钥

.随机选取Zn的要素x，生成W＝x*P。

这里，Zn是由{0，1，---n-1}构成的集合，x*P表示通过将x个椭圆曲线上的点P相加后得到的椭圆曲线上的点。再有，关于椭圆曲线上的点相加的方法，在非专利文献1中已有记述。

.设公开密钥pk为(E.P.W.n)，秘密密钥sk为x。

(3)PSEC-KEM的加密

在加密时，向下述加密算法KemE输入公开密钥pk再输出共享密钥K和加密文C。下面，说明加密算法KemE。

.随机生成和散列函数H的输出位长长度相同的s。

.生成G(s)并分割G(s)生成a和K。a是由G(s)的高位多位构成的位列，K是由剩下的位构成的位列。这里，G(s)＝a||K。‘||’是表示位结合的运算符。即，若a和K结合，则得到G(s)。

.生成R＝a*P，Q＝a*W。

.生成v＝sxor H(R||Q)。这里，xor表示“异”运算。

.输出共享密钥K和加密文C＝(R，v)。

(4)PSEC-KEM的解密

解密时，向下述解密算法KemD输入加密文C＝(R，v)、公开密钥pk和秘密密钥sk再输出共享密钥K。下面，说明解密算法KemD。

.生成Q＝x*R。

.生成s＝v xor H(R||Q)。

.生成G(s)并将G(s)分割成G(s)＝a||K。

.检验R＝a*P是否成立。若成立则输出共享密钥K。

当将该PSEC-KEM算法应用于在发送装置和接收装置之间进行加密通信的密码系统时，首先，发送装置取得通信目的地接收装置的公开密钥pk，并将取得的公开密钥pk输入到前述的加密算法KemE中，再导出共享密钥K和加密文C，再将加密文C发送给接收装置。

其次，接收装置从发送装置接收加密文C，将已接收的加密文C和自身具有的公开密钥pk、秘密密钥sk输入到前述的解密算法KemD，导出和发送装置导出的相同的共享密钥K。

下面，进一步详细说明。

现在，PSEC-KEM算法将散列函数H的输入作为(a*P||a*W)，使H(a*P||a*W)的值作用于在加密算法KemE中随机生成的要素s，生成v。接着，在解密算法KemD中使用秘密密钥sk(＝x)，可以从R＝a*P中求出Q＝x*R＝x*(a*P)＝a*(x*P)＝a*W，所以，使H(a*P||a*W)的值作用于v，可以求出在加密算法KemK中生成的随机要素s。

因此，加密算法KemE和解密算法KemD可以向散列函数G输入相同的s的值，并可以导出相同的共享密钥K。结果，具有秘密密钥sk的接收装置可以导出和发送装置所导出的相同的共享密钥K。

另一方面，不知道秘密密钥sk的其他接收装置即使取得公共密钥pk并接收到加密文C，因不知道秘密密钥sk(＝x)，故不能根据R＝a*P计算出Q＝a*W(＝(ax)*P)，不能导出和发送装置所导出的相同的共享密钥K。

这是因为，不知道秘密密钥sk的其他接收装置只能利用公开密钥pk，在上述计算中利用公开密钥pk去代替秘密密钥sk(＝x)，但是，一般，根据a*P和W＝x*P求Q＝a*W(＝(ax)*P)被称作椭圆曲线上的Diffie-Hellman问题，若不知道a或x的值，则很难进行计算(例如，参照非专利文献5)。

即，在PSEC-KEM算法中，使用不使用秘密密钥而根据a*P计算a*W较为困难的Diffie-Hellman问题，并最终导出共享密钥K，从而若不知道秘密密钥，则不能导出该共享密钥K。

由以上可知，发送装置和接收装置可以共同秘密地拥有共享密钥K，将使用秘密密钥密码从发送装置向接收装置通信的通信内容数据，使用共享密钥K以公共密钥密码的形式对其进行加密。

(专利文献1)

特开2002-252611号公报

(非专利文献1)

冈本龙明、山本博资，“现代密码”，系列/信息科学的数学、产业图书，1997

(非专利文献2)

Jeffery Hoffstein，Jill Pipher and Joseph H.Silverman，“NTRU：A ring based public key cryptosystem”，Lecture Notesin Computer Science，1423，pp.267-288，Springer-Verlag，1988.

(非专利文献3)

Victor Shoup，“A proposal for an ISO standard for publickey encryption(version2.1)”，[online]，2001年12月20日，[2002年9月29日检索]，Internet<URL：http：//shoup.net/papers/iso-2_1.pdf>

(非专利文献4)

Tatsuaki Okamoto，“Generic conversions for constructingIND-CCA2 public-key encryption in the random oracle model”，[online]，The 5th Workshop on Elliptic Curve Cryptography(ECC2001)，2001年10月30日，[2002年9月29日检索]，Internet<URL：http：//www.cacr.math.uwaterloo.ca/conferences/2001/ecc/okamoto.ppt>

(非专利文献5)

Neal Koblitz，“Algebraic Aspects of Cryptography”，Algorithms and Computation in Mathematics Vo1.3，pp.132-133，Springer-Verlag，1998

如上所述，现有的PSEC-KEM算法在散列函数H的输入中使用a*P、a*W，利用不使用秘密密钥而根据a*P计算a*W较为困难的Diffie-Hellman问题，并最终导出共享密钥K，从而若不知道秘密密钥，则不能导出该共享密钥K。

但是，在以NTRU密码为首，不求解Diffie-Hellman问题的其他公开密钥密码中，因没有与Diffie-Hellman问题中的a*P、a*W相当的参数，故不适用于PSEC-KEM算法。即，可进行高速处理的NTRU密码不能使用作为密钥密封机制的PSEC-KEM算法进行共享密钥的配送，因此，存在发送装置和接收装置不能进行从使用了该共享密钥的发送装置向接收装置的加密通信。

发明内容

为了解决上述问题，本发明的目的在于提供一种密钥共享系统、共享密钥生成装置、共享密钥复原装置、共享密钥生成方法、共享密钥复原方法、共享密钥生成程序和共享密钥复原程序，即使使用不求解Diffie-Hellman问题的密码方式，也可以在不让第三者知道的情况下从共享密钥生成装置向共享密钥复原装置配送共享密钥，这时，可以防止在共享密钥生成装置和共享密钥复原装置之间导出不同的共享密钥。

为了达到上述目的，本发明提供一种密钥共享系统，由生成共享密钥的共享密钥生成装置和共享密钥复原装置构成，并生成不让第三者知道的共享密钥，上述共享密钥生成装置具有：生成种子值的种子值生成装置、根据已生成的上述种子值生成验证值和共享密钥的第1共享密钥生成装置、对已生成的上述验证值进行加密再生成第1加密信息的第1加密装置、根据已生成的上述验证值对已生成的上述种子值进行加密再生成第2加密信息的第2加密装置、和发送已生成的上述第1加密信息和第2加密信息的发送装置，上述共享密钥复原装置具有：接收上述第1加密信息和上述第2加密信息的接收装置、将已接收的上述第1加密信息解密后生成第1解密验证值的第1解密装置、根据已生成的上述第1解密验证值将已接收的上述第2加密信息解密后生成解密种子值的第2解密装置、利用和上述第1共享密钥生成装置相同的方法，并根据已生成的上述解密种子值生成第2解密验证值和解密共享密钥的第2共享密钥生成装置、根据已生成的上述第1解密验证值和上述第2解密验证值判断是否输出已生成的上述解密共享密钥的判断装置、和当判断要输出时输出已生成的上述解密共享密钥的输出装置。

若按照该构成，上述共享密钥生成装置根据种子值生成验证值和共享密钥，对上述验证值进行加密生成第1加密信息，根据上述验证值对上述种子值进行加密生成第2加密信息，上述共享密钥复原装置将上述第1加密信息解密后生成第1解密验证值，根据上述第1解密验证值将上述第2加密信息解密后生成解密种子值，和上述第1共享密钥生成装置一样，根据上述解密种子值生成第2解密验证值和解密共享密钥，根据已生成的上述第1解密验证值和上述第2解密验证值判断是否输出已生成的上述解密共享密钥，所以，能够从共享密钥生成装置向共享密钥复原装置配送不让第三者知道的共享密钥，这时，可以防止在共享密钥生成装置和共享密钥复原装置之间导出不同的共享密钥。

这里，上述共享密钥生成装置进而具有：取得内容的取得装置和使用已生成的上述共享密钥对已取得的内容进行加密再生成加密内容的加密装置，上述发送装置进而发送已生成的上述加密内容，上述接收装置进而接收上述加密内容，上述共享密钥复原装置进而具有：使用已输出的上述解密共享密钥对已接收的上述加密内容进行解密再生成解密内容的解密装置、和输出已生成的解密内容的输出装置。

若按照该构成，共享密钥生成装置使用已生成的上述共享密钥对已取得的内容进行加密再生成加密内容，上述共享密钥复原装置使用已输出的上述解密共享密钥对已接收的上述加密内容进行解密再生成解密内容，所以，能够从共享密钥生成装置向共享密钥复原装置发送不让第三者知道的内容。

此外，本发明是不让第三者知道而向对方装置传送共享密钥的共享密钥生成装置，具有：生成种子值的种子值生成装置、根据已生成的上述种子值生成验证值和共享密钥的共享密钥生成装置、对已生成的上述验证值进行加密后再生成第1加密信息的第1加密装置、根据已生成的上述验证值对已生成的上述种子值进行加密再生成第2加密信息的第2加密装置、和发送已生成的上述第1加密信息和第2加密信息的发送装置。

若按照该构成，共享密钥生成装置对上述验证值进行加密生成第1加密信息，根据上述验证值对上述种子值进行加密生成第2加密信息，所以，可以通过双重加密来进一步提高安全性。第三者只要不知道第1和第2加密装置的密码方式，就得不到共享密钥。

这里，上述种子值生成装置生成随机数，通过将生成的随机数作为上述种子值来生成上述种子值。

若按照该构成，共享密钥生成装置生成随机数并将生成的随机数作为上述种子值，所以，在生成种子值、生成验证值和共享密钥、生成第1加密信息和第2加密信息并发送第1加密信息和第2加密信息之后，当生成下一个种子值时，可以生成和最初生成的种子值不同的下一个种子值。因此，由共享密钥生成装置发送的第1加密信息和第2加密信息每一次都不同。所以，即使第三者这时盗听、记录从共享密钥生成装置向对方装置发送的第1加密信息和第2加密信息，也很难根据记录的各第1加密信息和第2加密信息类推出原来的种子值。

这里，上述共享密钥生成装置对上述种子值执行单向函数来生成函数值，并根据已生成的上述函数值生成上述验证值和上述共享密钥。

若按照该构成，对上述种子值执行单向函数来生成上述验证值，所以，即使第三者得知了上述验证值，也很难根据上述验证值求出上述种子值。因此，根据上述验证值求出上述种子值进而求得共享密钥事实上是不可能的。

这里，上述共享密钥生成装置对上述种子值执行作为上述单向函数的散列函数，生成上述函数值。

若按照该构成，上述单向函数是散列函数，所以，其算法大家都熟悉，容易使用。

这里，上述共享密钥生成装置将已生成的上述函数值的一部分作为上述验证值，另一部分作为上述共享密钥，由此，生成上述验证值和上述共享密钥。

若按照该构成，将上述函数值的一部分作为上述验证值，另一部分作为上述共享密钥，所以，容易生成上述验证值和上述共享密钥。

这里，上述共享密钥生成装置对上述种子值执行单向函数再生成函数值，根据已生成的上述函数值生成上述验证值、上述共享密钥和盲值。

若按照该构成，对上述种子值执行单向函数来生成上述验证值，所以，即使第三者得知了上述验证值，也很难根据上述验证值求出上述种子值。因此，根据上述验证值求出种子值进而求得共享密钥事实上是不可能的。

这里，上述第1加密装置包含取得公开密钥的公开密钥取得部、使用取得的上述公开密钥和已生成的上述盲值对上述验证值执行公开密钥加密算法再生成上述第1加密信息的公开密钥加密部。

此外，上述第1加密装置包含取得公开密钥的公开密钥取得部、使用取得的上述公开密钥对上述验证值执行公开密钥加密算法再生成上述第1加密信息的公开密钥加密部。

若按照该构成，第1加密装置使用公开密钥密码方式，所以，与使用共享密钥密码方式的情况相比，容易进行密钥的管理。

这里，上述公开密钥加密算法是NTRU密码方式，上述公开密钥取得部取得利用NTRU密码方式的密钥生成算法生成的公开密钥多项式作为上述公开密钥，上述公开密钥加密部根据上述验证值生成验证值多项式，根据上述盲值生成盲值多项式，利用NTRU密码方式的加密算法，将上述公开密钥多项式作为密钥使用，为了搅乱上述验证值多项式，使用上述盲值多项式加密上述验证值多项式，再生成作为多项式的上述第1加密信息。

此外，上述公开密钥加密算法是NTRU密码方式，上述公开密钥取得部取得利用NTRU密码方式的密钥生成算法生成的公开密钥多项式作为上述公开密钥，上述公开密钥加密部根据上述验证值生成验证值多项式，生成盲值并根据生成的上述盲值生成盲值多项式，利用NTRU密码方式的加密算法，将上述公开密钥多项式作为密钥使用，为了搅乱上述验证值多项式，使用上述盲值多项式加密上述验证值多项式，再生成作为多项式的上述第1加密信息。

若按照该构成，可以采用NTRU密码。

这里，上述第2加密装置对上述验证值执行单向函数再生成函数值，使用生成的上述函数值，对上述种子值执行加密算法，再生成上述第2加密信息。

若按照该构成，使用对上述验证值执行单向函数所得到的函数值，对上述种子值执行加密算法，再生成上述第2加密信息，所以，第三者只要不知道上述单向函数和上述加密算法，就不能从上述第2加密信息中得到上述种子值。

这里，上述第2加密装置通过对已生成的上述函数值和上述种子值执行作为上述加密算法的“异”运算，生成上述第2加密信息。

若按照该构成，因上述加密算法是“异”运算，故容易使用。此外，还可以进行逆运算。

这里，上述第2加密装置通过对已生成的上述函数值和上述种子值执行作为上述加密算法的公共密钥加密算法，生成上述第2加密信息。

若按照该构成，因上述加密算法是众所周知的公共密钥加密算法，故容易使用。此外，还可以进行逆运算。

这里，上述第2加密装置通过对已生成的上述函数值和上述种子值执行作为上述加密算法的加法运算，生成上述第2加密信息。

若按照该构成，因上述加密算法是加法运算，故容易使用。此外，还可以进行逆运算。

这里，上述第2加密装置通过对已生成的上述函数值和上述种子值执行作为上述加密算法的乘法运算，生成上述第2加密信息。

若按照该构成，因上述加密算法是乘法运算，故容易使用。此外，还可以进行逆运算。

这里，上述第2加密装置对上述验证值执行作为上述单向函数的散列函数再生成上述函数值。

若按照该构成，上述单向函数是散列函数，其算法大家都熟悉，所以，容易使用。

这里，上述第2加密装置使用上述验证值对上述种子值执行加密算法，再生成第2加密信息。

若按照该构成，使用上述验证值对上述种子值执行加密算法，因运算简单，故容易使用。

这里，上述第2加密装置使用上述验证值和上述第1加密信息，对上述种子值进行加密。

若按照该构成，使用上述验证值和上述第1加密信息，对上述种子值进行加密，所以，非法的第三者若不知道上述验证值和上述第1加密信息，就得不到种子值，从而提高了安全性。

这里，上述第2加密装置对上述验证值和上述第1加密信息执行单向函数再生成上述函数值，使用已生成的上述函数值对上述种子值执行加密算法，生成上述第2加密信息。

若按照该构成，使用单向函数和加密算法，所以，即使非法的第三者知道第1加密信息和第2加密信息，至少若不知道单向函数和加密算法，也得不到种子值，从而提高了安全性。

这里，上述第2加密装置通过对已生成的上述函数值和上述种子值执行作为上述加密算法的“异”运算，生成上述第2加密信息。

若按照该构成，因上述加密算法是“异”运算，故运算容易。此外，还可以进行逆运算。

这里，上述共享密钥生成装置进而具有：取得内容的取得装置和使用已生成的上述共享密钥对已取得的内容进行加密再生成加密内容的加密装置，上述发送装置进而发送已生成的上述加密内容。

若按照该构成，共享密钥生成装置可以不让第三者知道而向对方装置发送内容。

这里，是不让第三者知道而从共享密钥生成装置接收共享密钥的共享密钥复原装置，上述共享密钥生成装置生成种子值，根据已生成的上述种子值生成验证值和共享密钥，对已生成的上述验证值进行加密生成第1加密信息，根据已生成的上述验证值对已生成的上述种子值进行加密生成第2加密信息，并发送已生成的上述第1加密信息和上述第2加密信息，上述共享密钥复原装置具有：接收上述第1加密信息和上述第2加密信息的接收装置、将已接收的上述第1加密信息解密后生成第1解密验证值的第1解密装置、根据已生成的上述第1解密验证值将已接收的上述第2加密信息解密后生成解密种子值的第2解密装置、利用和上述共享密钥生成装置相同的方法，并根据已生成的上述解密种子值生成第2解密验证值和解密共享密钥的共享密钥生成装置、根据已生成的上述第1解密验证值和上述第2解密验证值判断是否输出已生成的上述解密共享密钥的判断装置、和当判断要输出时输出已生成的上述解密共享密钥的输出装置。

若按照该构成，可以不让第三者知道而从共享密钥生成装置接收共享密钥，这时，还可以防止在共享密钥生成装置和共享密钥复原装置之间导出不同的共享密钥。

这里，上述共享密钥生成装置取得公开密钥，使用已取得的上述公开密钥对上述验证值执行公开密钥加密算法，再生成上述第1加密信息，上述第1解密装置包含：取得与上述公开密钥对应的秘密密钥的秘密密钥取得部、使用取得的上述秘密密钥对已接收的上述第1加密信息执行与上述公开密钥加密算法对应的公开密钥解密算法后再生成上述第1解密验证值的公开密钥解密部。

若按照该构成，第1解密装置使用公开密钥密码方式，所以，与使用共享密钥密码方式的情形相比较，容易进行密钥的管理。

这里，上述公开密钥加密算法和上述公开密钥解密算法使用了NTRU密码方式，上述共享密钥生成装置取得利用NTRU密码方式的密钥生成算法生成的公开密钥多项式作为上述公开密钥，根据上述验证值生成验证值多项式，生成盲值并根据生成的上述盲值生成盲值多项式，利用NTRU密码方式的加密算法，将上述公开密钥多项式作为密钥使用，为了搅乱上述验证值多项式，使用上述盲值多项式加密上述验证值多项式，再生成作为多项式的上述第1加密信息，上述接收装置接收作为多项式的上述第1加密信息，上述秘密密钥取得部取得利用NTRU密码方式的密钥生成算法生成的秘密密钥多项式作为上述秘密密钥，上述公开密钥解密部利用NTRU密码方式的与上述加密算法对应的解密算法，将上述秘密密钥多项式作为密钥使用，对作为多项式的上述第1加密信息进行解密，生成解密验证值多项式，根据已生成的上述解密验证值多项式生成上述第1解密验证值。

若按照该构成，可以采用NTRU密码。

这里，上述共享密钥生成装置对上述验证值执行单向函数再生成函数值，使用生成的上述函数值，对上述种子值执行加密算法，再生成上述第2加密信息，上述第2解密装置对已生成的上述第1解密验证值执行上述单向函数再生成解密函数值，使用已生成的上述解密函数值对已接收的上述第2加密信息执行与上述加密算法对应的解密算法，再生成上述解密种子值。

若按照该构成，第2解密装置采用单向函数和解密算法的两阶段运算方法，所以，即使非法的第三者知道第1加密信息和第2加密信息，至少若不知道单向函数和解密算法，也得不到种子值，从而提高了安全性。

这里，上述公共密钥生成装置通过对已生成的上述函数值和上述种子值执行作为上述加密算法的“异”运算，生成上述第2加密信息，上述第2解密装置通过对已生成的上述解密函数值和上述第2加密信息执行作为上述解密算法的“异”运算，生成上述解密种子值。

若按照该构成，因上述解密算法是“异”运算，故运算容易，此外，它还是上述加密算法的逆运算。

这里，上述共享密钥生成装置通过对已生成的上述函数值和上述种子值执行作为上述加密算法的公共密钥加密算法，生成上述第2加密信息，上述第2解密装置通过对已生成的上述解密函数值和上述第2加密信息执行作为上述解密算法的、与上述公共密钥加密算法对应的公共密钥解密算法，生成上述解密种子值。

若按照该构成，因上述解密算法是众所周知的共享密钥解密算法，故容易使用，此外，它还是上述加密算法的逆运算。

这里，上述公共密钥生成装置通过对已生成的上述函数值和上述种子值执行作为上述加密算法的加法运算，生成上述第2加密信息，上述第2解密装置通过对已生成的上述解密函数值和上述第2加密信息执行作为上述解密算法的减法运算，生成上述解密种子值。

若按照该构成，因上述解密算法是减法运算，故运算容易，此外，它还是上述加密算法的逆运算。

这里，上述共享密钥生成装置通过对已生成的上述函数值和上述种子值执行作为上述加密算法的乘法运算，生成上述第2加密信息，上述第2解密装置通过对已生成的上述解密函数值和上述第2加密信息执行作为上述解密算法的除法运算，生成上述解密种子值。

若按照该构成，因上述解密算法是除法运算，故运算容易，此外，它还是上述加密算法的逆运算。

这里，上述共享密钥生成装置对上述验证值执行作为上述单向函数的散列函数，生成上述函数值，上述第2解密装置对已生成的上述第1解密验证值执行作为上述单向函数的上述散列函数，生成上述解密函数值。

若按照该构成，因上述单向函数是散列函数，是大家都熟悉的算法，故容易使用。

这里，上述共享密钥生成装置使用上述验证值，对上述种子值执行加密算法，生成第2加密信息，上述第2解密装置使用已生成的上述第1解密验证值，对上述第2加密信息执行与上述加密算法对应的解密算法，生成上述解密种子值。

若按照该构成，使用第1解密验证值对第2加密信息进行解密，所以运算容易。

这里，上述共享密钥生成装置使用上述验证值和上述第1加密信息对上述种子值进行加密，上述第2解密装置使用已生成的上述第1解密验证值和已接收的上述第1加密信息，对上述第2加密信息进行解密，生成上述解密种子值。

若按照该构成，使用第1解密验证值和第1加密信息，对第2加密信息进行解密，所以，非法的第三者若不知道上述第1解密验证值和上述第1加密信息，就得不到种子值，从而提高安全性。

这里，上述共享密钥生成装置对上述验证值和上述第1加密信息执行单向函数，生成函数值，并使用已生成的函数值对上述种子值执行加密算法，生成上述第2加密信息，上述第2解密装置对上述第1解密验证值和上述第1加密信息执行上述单向函数，生成解密函数值，使用已生成的上述解密函数值，对上述第2加密信息执行与上述加密算法对应的解密算法，生成上述解密种子值。

若按照该构成，第2解密装置使用单向函数和解密算法的两阶段运算方法，所以，即使非法的第三者知道上述第1加密信息和上述第2加密信息，至少若不知道单向函数和解密算法，也得不到种子值，提高了安全性。

这里，上述共享密钥生成装置通过对已生成的上述函数值和上述种子值执行作为上述加密算法的“异”运算，生成上述第2加密信息，上述第2解密装置通过对上述解密函数值和上述第2加密信息执行作为上述解密算法的“异”运算，生成上述解密种子值。

若按照该构成，因上述解密算法是“异”运算，故运算容易，此外，它还是上述加密算法的逆运算。

这里，上述共享密钥生成装置对上述种子值执行单向函数来生成函数值，并根据已生成的上述函数值生成上述验证值和上述共享密钥，上述共享密钥生成装置对已生成的上述解密种子值执行上述单向函数，生成解密函数值，并根据已生成的上述解密函数值生成上述第2解密验证值和上述解密共享密钥。

若按照该构成，对上述解密种子值执行单向函数来生成上述第2解密验证值，所以，即使第三者得知了上述第2解密验证值，也很难根据上述第2解密验证值求出上述种子值。因此，根据上述第2解密验证值求出上述种子值进而求得共享密钥事实上是不可能的。

这里，上述共享密钥生成装置对上述种子值执行作为上述单向函数的散列函数，生成上述函数值，上述共享密钥生成装置对已生成的上述解密种子值执行作为上述单向函数的上述散列函数，生成上述解密函数值。

若按照该构成，上述单向函数是散列函数，所以，其算法大家都熟悉，容易使用。

这里，上述共享密钥生成装置将已生成的上述函数值的一部分作为上述验证值，另一部分作为上述共享密钥，由此，生成上述验证值和上述共享密钥，上述共享密钥生成装置将已生成的上述解密函数值的一部分作为上述第2解密验证值，另一部分作为上述解密共享密钥，由此，生成上述第2解密验证值和上述解密共享密钥。

若按照该构成，将上述解密函数值的一部分作为上述第2解密验证值，另一部分作为上述解密共享密钥，所以，容易生成上述第2解密验证值和上述解密共享密钥。

这里，上述共享密钥生成装置对上述种子值执行单向函数再生成函数值，根据已生成的上述函数值生成上述验证值、上述共享密钥和盲值，取得公开密钥，使用已取得的上述公开密钥和已生成的上述盲值，对上述验证值执行公开密钥加密算法，生成上述第1加密信息，上述共享密钥生成装置对已生成的上述解密种子值执行上述单向函数，生成解密函数值，并根据已生成的解密函数值生成上述第2解密验证值、上述解密共享密钥和解密盲值。

若按照该构成，对上述解密种子值执行单向函数来生成上述第2解密验证值，所以，即使第三者得知了上述第2解密验证值，也很难根据上述第2解密验证值求出上述种子值。因此，根据上述第2解密验证值求出种子值进而求得共享密钥事实上是不可能的。

这里，上述共享密钥生成部取得公开密钥并使用已取得的上述公开密钥和已生成的上述盲值对上述验证值执行公开密钥加密算法，生成上述第1加密信息，上述判断装置取代基于上述第1解密验证值和第2解密验证值的上述判断，而具有：取得上述公开密钥的公开密钥取得部、使用已取得的上述公开密钥和已生成的上述解密盲值对生成的上述第1解密验证值或上述第2解密验证值执行上述公开密钥加密算法并生成再加密信息的再加密部、根据已接收的上述第1加密信息和已生成的上述再加密信息判断是否输出已生成的上述解密共享密钥的判断部。

若按照该构成，根据已接收的上述第1加密信息和已生成的上述再加密信息判断是否输出已生成的上述解密共享密钥，所以，可以不让第三者知道，而接收从共享密钥生成装置来的共享密钥，这时，还可以防止在共享密钥生成装置和共享密钥接收装置之间导出不同的共享密钥。

这里，上述判断部将上述第1加密信息和上述再加密信息比较，当上述第1加密信息和上述再加密信息一致时，判断输出上述解密共享密钥。此外，上述判断部将上述第1解密验证值和上述第2解密验证值比较，当一致时，判断为输出上述解密共享密钥。

若按照该构成，当第1加密信息和再加密信息一致时，输出解密共享密钥，所以，可以可靠地进行是否输出解密共享密钥的判断。

这里，上述公开密钥加密算法采用NTRU密码方式，上述共享密钥生成装置取得利用NTRU密码方式的密钥生成算法生成的公开密钥多项式作为上述公开密钥，根据上述验证值生成验证值多项式，根据上述盲值生成盲值多项式，利用NTRU密码方式的加密算法，将上述公开密钥多项式作为密钥使用，为了搅乱上述验证值多项式，使用上述盲值多项式加密上述验证值多项式，再生成作为多项式的上述第1加密信息，上述公开密钥取得部取得上述公开密钥多项式，上述再加密部根据上述第2解密验证值生成解密验证值多项式，根据上述解密盲值生成解密盲值多项式，利用NTRU密码方式的加密算法，将上述公开密钥多项式作为密钥使用，为了搅乱上述解密验证值多项式，使用上述盲值多项式加密上述解密验证值多项式，再生成作为多项式的上述再加密信息。

若按照该构成，可以采用NTRU密码。

这里，上述共享密钥生成装置进而取得内容，使用已生成的上述共享密钥对已取得的内容进行加密再生成加密内容，并发送已生成的上述加密内容，上述接收装置进而接收上述加密内容，上述共享密钥复原装置进而具有使用已输出的上述解密共享密钥对已接收的上述加密内容进行解密后再生成解密内容的解密装置、和输出已生成的解密内容的输出装置。

若按照该构成，共享密钥生成装置使用已生成的上述共享密钥对已取得的内容进行加密再生成加密内容，上述共享密钥复原装置使用已输出的上述解密共享密钥对已接收的上述加密内容进行解密再生成解密内容，所以，能够从共享密钥生成装置向共享密钥复原装置发送不让第三者知道的内容。

附图说明

图1是表示内容分配系统10的构成和构成要素之间的连接形态的概念图。

图2是表示加密装置110的构成的方框图。

图3是表示解密装置120的构成的方框图。

图4是表示加密装置110和解密装置120的动作的处理系统图。

图5是表示加密装置110和解密装置120的动作的流程图。

图6是表示加密装置110b的构成的方框图。

图7是表示解密装置120b的构成的方框图。

图8是表示加密装置110b和解密装置120b的动作的处理系统图。

图9是表示加密装置110c的构成的方框图。

图10是表示解密装置120c的构成的方框图。

图11是表示加密装置110c和解密装置120c的动作的处理系统图。

图12是表示加密装置110c和解密装置120c的变形例的动作的处理系统图。

图13是表示加密装置110d的构成的方框图。

图14是表示解密装置120d的构成的方框图。

图15是表示加密装置110d和解密装置120d的动作的流程图。

图16是表示加密装置110d和解密装置120d的动作的处理系统图。

图17是表示加密装置110e的构成的方框图。

图18是表示解密装置120e的构成的方框图。

图19是表示加密装置110e和解密装置120e的动作的处理系统图。

图20是表示加密装置110e和解密装置120e的动作的处理系统图。

具体实施方式

实施形态1

说明作为本发明的1个实施形态的内容分配系统10。内容分配系统10是使用NTRU密码进行密钥密封机制的密钥配送后再进行加密通信的加密通信系统。

1.1NTRU密码方式

对内容分配系统10中使用的NTRU密码方式进行简单的说明。NTRU密码方式是使用多项式运算进行加密和解密的公开密钥密码方式。

再有，对于NTRU密码方式和NTRU密码方式中的公开密钥和秘密密钥的生成方法，非专利文献2中进行了详细的叙述。

(1)NTRU密码方式的系统参数

在NTRU密码方式中，存在整数的系统参数N、p、q，后述的加密装置和解密装置具有这样的系统参数。

在上述文献中，作为系统参数的例子，可以举出(N，p，q)＝(107，3，64)、(N，p，q)＝(167，3，128)、(N，p，q)＝(503，3，256)3个例子。

以后，在本实施形态中，以系统参数N＝167为例进行说明。

(2)NTRU密码方式的多项式运算

NTRU密码方式如上所述，是利用多项式运算进行加密和解密的公开密钥密码方式。

NTRU密码方式处理的多项式是对上述系统参数N的N-1次方以下的多项式。例如，当N＝5时，是X^4+X^3+1等多项式。这里，‘X^a’表示X的a次方。

此外，加密时或解密时使用的公开密钥h、秘密密钥f、明码文m、随机数r、加密文c都可以用N-1次方以下的多项式来表现(以后分别称作公开密钥多项式h、秘密密钥多项式f、明码文多项式m、随机数多项式r、加密文多项式c)。

在多项式运算中，对上述系统参数N，使用关系式X^N＝1，使运算结果运算为始终在N-1次方以下的多项式。

例如，若用×表示多项式和多项式的积，用·表示整数和多项式的积，根据X^5＝1的关系，当N＝5时，多项式X^4+X^2+1和多项式X^3+X的积变成

(X^4+X^2+1)×(X^3+X)

＝X^7+2·X^5+2·X^3+X

＝X^7+2·X^5+2·X^3+X

＝2·X^3+X^2+X+2

这样，在多项式运算中，始终将其运算为N-1次方以下的多项式。

(3)NTRU密码方式的加密

后述的加密装置如下面所示进行NTRU密码方式的加密。

加密时，使用下述随机数多项式r和公开密钥多项式h，对明码文多项式m执行作为多项式运算的加密算法E，生成加密文多项式c＝E(m、r、h)。

这里，E(m、r、h)是对NTRU密码方式的加密算法E输入明码文多项式m、随机数多项式r和公开密钥多项式h所得到的多项式运算结果。对于加密算法E，非专利文献2中有详细叙述，这里省略其说明。

再有，在NTRU密码方式中，预先决定用来生成随机数多项式r的参数d。这样进行选择，使随机数多项式r在构成随机数多项式的各项中，d个项的系数为‘1’，其余d个项的系数为‘-1’，剩下的项的系数为‘0’。

即，随机数多项式r是N-1次方以下的多项式，对从0次方(常数项)到N-1次方的N个项，存在N个系数。随机数多项式r可以这样进行选择，使其在该N个系数中有d个系数是‘1’，有d个系数是‘-1’，有(N-2d)个系数是‘0’。

若按照非专利文献2，当参数N＝167时，d＝18。即，随机数多项式r被选择成18个系数是‘1’，18个系数是‘-1’，131(＝167-36)个系数是‘0’。

(4)NTRU密码方式的解密

后述的解密装置如下面所示进行NTRU密码方式的解密。

解密时，使用秘密密钥多项式f，对加密文多项式c执行作为多项式运算的解密算法E，生成解密文多项式m’＝D(c、f)。

这里，D(c、f)是对NTRU密码方式的解密算法D输入加密文多项式c和秘密密钥多项式f所得到的多项式运算结果。对于解密算法D，非专利文献2中有详细叙述，这里省略其说明。

(5)NTRU密码方式的解密错误

在该NTRU密码方式中，发生已生成的解密文多项式m’与明码文多项式m不同的情况。这时，解密时不能正确地得到明码文多项式m。将该现象称作解密错误。

1.2内容分配系统10的构成

内容分配系统10如图1所示，由内容服务装置140、加密装置110、解密装置120、再生装置150和监视器155构成，内容服务装置140和加密装置110经专用线路20连接，加密装置110和解密装置120经因特网130连接。再生装置150与内装有解密装置120和扬声器的监视器155连接。加密装置110装有存储卡160，解密装置120装有存储卡170。

内容服务装置140经专用线路20将由图像和声音构成的电影等内容发送到解密装置110。

加密装置110和解密装置120分别生成同一共享密钥K和共享密钥K’。其次，加密装置110使用共享密钥K对从内容服务器装置140接收来的内容进行加密，生成加密内容，并发送已生成的加密内容，解密装置120接收加密内容并对接收的加密内容进行解密，生成再生内容，再生装置150根据再生内容生成图像信号和声音信号，监视器155显示图像并输出声音。

1.3内容服务装置140的构成

内容服务装置140是由微处理器、ROM、RAM、硬盘单元、显示单元、通信单元、键盘和鼠标等构成的计算机系统(未图示)。上述RAM或上述硬盘单元上存储了计算机程序。内容服务器140通过使上述微处理器按照上述计算机程序动作来实现其一部分功能。

内容服务装置140预先将上述内容存储起来，上述内容由多个部分内容mi(1≤i≤n)构成。内容服务装置140根据加密装置110的要求，读出部分内容mi，并经专用线路20将读出的部分内容mi发送给加密装置110。

1.4存储卡160和存储卡170的构成

存储卡160是采用闪速存储器作为存储媒体的卡式存储装置，预先存储公开密钥多项式h。

此外，存储卡170是和存储卡160同样的卡式存储装置，预先存储秘密密钥多项式f和公开密钥多项式h。

这里，秘密密钥多项式f和公开密钥多项式h是利用NTRU密码方式生成的多项式，并分别对应。

1.5加密装置110的构成

加密装置110如图2所示，由公开密钥输入部111、随机数生成部112、第1函数部113、加密部114、第1发送部117、公共密钥加密部118和第2发送部119构成。

加密装置110具体地说，是由微处理器、ROM、RAM和通信单元构成的计算机系统。上述RAM中存储了计算机程序。加密装置110通过使上述微处理器按照上述计算机程序动作来实现其功能。

(1)公开密钥输入部111

公开密钥输入部111从存储卡160读出解密装置120的公开密钥多项式h，并将读出的公开密钥多项式h输出给加密部114。

(2)随机数生成部112

随机数生成部112生成随机数s作为用来生成共享密钥K的基础的种子值，并将生成的随机数s输出给第1函数部113和加密部114。

(3)第1函数部113

第1函数部113从随机数生成部112接收随机数s，生成随机数s的函数值G(s)。这里，函数G是输出长度为2k位的散列函数。再有，散列函数是一种单向函数。其次，第1函数部113将函数值G(s)的高位k位作为随机数值u，将G(s)的低位k位作为共享密钥K，由此，根据生成的函数值G(s)生成共享密钥K和随机数值u，向加密部114输出已生成的随机数值u，将生成的共享密钥K向公共密钥加密部118输出。

(4)加密部114

加密部114从公开密钥输入部111接收公开密钥多项式h，从随机数生成部112接收随机数s，从第1函数部113接收随机数值u。其次，像下面那样，通过NTRU密码，并使用公开密钥多项式h和随机数值u生成随机数s的第1加密文c1。这里，随机数值u是盲值，用于使作为加密对象的随机数s不明了。

加密部114生成由随机数值u唯一求出的随机数多项式r，该随机数多项式r对于NTRU密码的参数d，其d个项的系数是‘1’，d个项的系数是‘-1’，剩下的项的系数是‘0’。

例如，加密部114将随机数值u作为模拟随机数系列的初始值(随机数种子)来设定，根据{0、1、......N-1}生成2d个不重复的模拟随机数，设由最初的d个模拟随机数分别表示的d个n次方的项的系数为‘1’，由剩下的d个伪随机数分别表示的d个n次方的项的系数为‘-1’，其余次方的项的系数为‘0’。

其次，加密部114为了使随机数s能够适用于NTRU密码的密码算法E而构成随机数多项式sp，使由二进制表现随机数s时的N位位列的各位的值与随机数多项式sp的各项的系数对应。例如，设随机数s的低位的第b位的值是项X^b的系数。具体地说，当s＝10010(用位表现)时，生成随机数多项式sp＝X^5+X^2。

其次，加密部114使用公开密钥多项式h和随机数多项式r对随机数多项式sp执行上述加密算法E，生成第1加密文c1＝加密文多项式E(sp、r、h)。

其次，加密部114将生成的第1加密文c1输出给第1发送部117。

再有，在图2中，表示加密装置110的各构成部分的各方框通过连接线与其他方框连接。这里，各连接线表示信号或信息的传送路径。此外，在与表示加密部114的方框连接的多根连接线中，连接线上带密钥标记的线表示向加密部114传送密钥信息的路径。对于表示公共密钥加密部118的方框也一样。此外，其他的图也一样。

(5)第1发送部117

第1发送部117从加密部114接收第1加密文c1，经因特网130将第1加密文c1送往解密装置120。

(6)公共密钥加密部118

公共密钥加密部118例如具有像DES密码方式那样的公共密钥加密算法Sym。

一般，在公共密钥加密中，在加密侧的装置中，使用加密密钥K对明码文m执行公共密钥加密算法sym，生成加密文c＝Sym(m、k)。这里，若加密文生成时使用的加密密钥K和解密文生成时使用的加密密钥K相同，则m’＝m。再有，关于公共密钥加密和DES密码方式，因非专利文献1有详细叙述，故省略其说明。

公共密钥加密部118从内容服务装置140接收多个明码文(部分内容)mi(1≤i≤n)，从第1函数部113接收共享密钥K，使用接收的共享密钥K对明码文mi(1≤i≤n)执行公共密钥加密算法Sym，生成公共密钥加密文Ci＝Sym(mi、k)(1≤i≤n)。

其次，公共密钥加密部118将公共密钥加密文Ci(1≤i≤n)送给第2发送部119。

(7)第2发送部119

第2发送部119从公共密钥加密部118接收公共密钥加密文Ci(1≤i≤n)，并经因特网130将接收的公共密钥加密文Ci(1≤i≤n)发送给解密装置120。

1.6解密装置120的构成

解密装置120如图3所示，由秘密密钥输入部121、第1接收部122、解密部123、第2函数部126、比较部127、公共密钥解密部128和第2接收部129构成。

解密装置120是和加密装置110一样的计算机系统。解密装置120通过使微处理器按照计算机程序动作来实现其功能。

(1)秘密密钥输入部121

秘密密钥输入部121从存储卡170读出解密装置120的秘密密钥多项式f和公开密钥多项式h，并将读出的秘密密钥多项式f输出给解密部123，将读出的公开密钥多项式h输出给比较部127。

(2)第1接收部122

第1接收部122经因特网130从加密装置110接收第1加密文c1，将接收的第1加密文c1输出给解密部123。

(3)解密部123

解密部123从秘密密钥输入部121接收秘密密钥多项式f，从第1接收部122接收第1加密文c1，如下面所示，利用NTRU密码并使用秘密密钥多项式f，对第1加密文c1进行解密，生成解密随机数s’。

解密部123使用秘密密钥多项式f对第1加密文c1执行上述解密算法D，生成解密随机数多项式sp’＝D(c1、f)。其次，解密随机数多项式sp’是用多项式表现的NTRU密码的解密文，所以，生成解密随机数s’，使解密随机数多项式sp’的各项的系数与用二进制表现解密随机数s’时的N位位列的各值相对应。例如，解密随机数多项式sp’的b次方的项X^b的系数变成解密随机数s’的低位第b位的值。

具体地说，当解密随机数多项式sp’＝X^5+X^2时，生成解密随机数S’＝10010(用位表现)。

其次，解密部123将接收的第1加密文c1和生成的解密随机数s’输出给比较部127，将生成的解密随机数s’输出给第2函数部126。

(4)第2函数部126

第2函数部126具有和第1函数部113所具有的函数相同的函数G的算法。

第2函数部126从解密部123接收解密随机数s’，和第1函数部113同样，生成解密随机数s’的函数值G(s’)，其次，根据函数值G(s’)生成随机数值u’和共享密钥K’，将生成的随机数值u’和共享密钥K’输出给比较部127。

(5)比较部127

比较部127如图3所示，由加密部127x和比较运算部127y构成。

加密部127x从秘密密钥输入部121接收公开密钥多项式h，从解密部123接收解密随机数s’，从第2函数部126接收随机数值u’。其次，和加密部114同样，使用公开密钥多项式h和随机数值u’，对解密随机数S’进行加密，生成第1再加密文c1’，将生成的第1再加密文c1’输出给比较运算部127y。

比较运算部127y从解密部123接收第1加密文c1，从第2函数部126接收共享密钥K’，从加密部127x接收第1再加密文c1’。其次，将第1加密文c1和第1再加密文c1’进行比较，判断是否一致，当判断是一致时，将接收的共享密钥K’输出给公共密钥解密部128。当判断为不一致时，不输出接收的共享密钥K’。

(6)第2接收部129

第2接收部129经因特网130从加密装置110接收公共密钥加密文Ci(1≤i≤n)，将接收的公共密钥加密文Ci(1≤i≤n)输出给公共密钥解密部128。

(7)公共密钥解密部128

公共密钥解密部128预先具有和公共密钥加密部118所具有的公共密钥加密算法Sym相同的公共密钥加密算法Sym。

公共密钥解密部128从比较部127接收共享密钥K’，从第2接收部129接收公共密钥加密文Ci(1≤i≤n)，对使用接收的共享密钥K’对接收的公共密钥加密文Ci(1≤i≤n)，执行公共密钥加密算法Sym，并生成解密文mi’＝Sym(C、i、K)(1≤i≤n)。

其次，公共密钥解密部128将生成的解密文mi’(1≤i≤n)输出给再生装置150。

1.7再生装置150和监视器155

再生装置150从解密装置120接收解密文mi’(1≤i≤n)，根据接收的解密文mi’(1≤i≤n)生成图像信号和声音信号，将生成图像信号和声音信号输出给监视器155。

监视器155从再生装置150接收图像信号和声音信号，利用接收的图像信号和声音信号显示图像和输出声音。

1.8加密装置110和解密装置120的动作

使用图4所示的处理系统和图5所示的流程图说明加密装置110和解密装置120的动作。

加密装置110的公开密钥输入部111从存储卡160读出解密装置120的公开密钥多项式h，将读出的公开密钥多项式h输出给加密部114(步骤S101)。

其次，随机数生成部112生成随机数s，将生成的随机数s输出给第1函数部113和加密部114(步骤S102)。

其次，第1函数部113从随机数生成部112接收随机数s，生成随机数s的函数值G(s)(步骤S103)，其次，第1函数部113根据函数值G(s)生成随机数值u和共享密钥K，将随机数值u输出给加密部114，将共享密钥K输出给公共密钥加密部118(步骤S104)。

其次，加密部114从公开密钥输入部111接收公开密钥多项式h，从随机数生成部112接收随机数s，从第1函数部113接收随机数值u，使用公开密钥多项式h和随机数值u生成随机数s的第1加密文c1，将第1加密文c1输出给第1发送部117(步骤S105)。

其次，第1发送部117从加密部114接收第1加密文c1，经因特网130将第1加密文c1发送给解密装置120(步骤S106)。

其次，解密装置120的秘密密钥输入部121从存储卡170读出解密装置120的秘密密钥多项式f和公开密钥多项式h，将读出的秘密密钥多项式f输出给解密部123，将读出的公开密钥多项式h输出给比较部127(步骤S151)。

其次，第1接收部122经因特网130从加密装置110接收第1加密文c1，将第1加密文c1输出给解密部123(步骤S106)。

其次，解密部123从秘密密钥输入部121接收秘密密钥多项式f，从第1接收部122接收第1加密文c1，其次，使用秘密密钥多项式f对第1加密文c1进行解密，生成解密随机数s’，将第1加密文c1和解密随机数s’输出给比较部127，将解密随机数s’输出给第2函数部126(步骤S152)。

其次，第2函数部126从解密部123接收解密随机数s’，生成解密随机数s’的函数值G(s’)(步骤S153)，根据函数值G(s’)生成随机数值u’和共享密钥K’，将随机数值u’和共享密钥K’输出给比较部127(步骤S154)。

其次，比较部127从解密部123接收第1加密文c1，从第2函数部126接收随机数值u’和共享密钥K’，生成第1再解密文c1’(步骤S155)，检验第1加密文c1是不是使用了随机数值u’的解密随机数s’的加密文，若第1加密文c1不是解密随机数s’的加密文(步骤S156)，则解密装置120结束处理。

公共密钥加密部118从外部接收多个明码文mi(1≤i≤n)，从第1函数部113接收共享密钥K，使用共享密钥K对明码文mi(1≤i≤n)执行公共密钥加密算法Sym，生成公共密钥加密文Ci＝Sym(mi、K)(1≤i≤n)，将公共密钥加密文Ci(1≤i≤n)输出给第2发送部119(步骤S107)。

其次，第2发送部119从公共密钥加密部118接收公共密钥加密文Ci(1≤i≤n)，经因特网130发送给解密装置120(步骤S108)并结束处理。

若第1加密文c1是解密随机数s’的加密文(步骤S156)，比较部127则向公共密钥解密部128输出共享密钥K’(步骤S156)，比较部127向公共密钥解密部128输出共享密钥K’(步骤S157)。其次，第2接收部129经因特网130从加密装置110接收加密文Ci(1≤i≤n)，并向公共密钥解密部128输出(步骤S108)。

其次，公共密钥解密部128从比较部127接收共享密钥K’，从第2接收部129接收公共密钥加密文Ci(1≤i≤n)，使用共享密钥K’对公共密钥加密文Ci(1≤i≤n)执行公共密钥加密算法Sym，生成解密文mi’＝Sym(Ci、K)(1≤i≤n)，将解密文mi’(1≤i≤n)输出给再生装置150(步骤S158)并结束处理。

1.9内容分配系统的动作检验

下面，说明实施形态1的内容分配系统10的全部动作。

首先，加密装置110将解密装置120的公开密钥多项式h作为输入，生成随机数s，根据函数值G(s)导出随机数值u和共享密钥K。其次，加密装置110使用公开密钥多项式h和随机数值u，并用NTRU密码对随机数s进行加密，生成第1加密文c1，并经因特网130将第1加密文c1发送给解密装置120。

即，该加密装置110进行以下处理，将第1加密文c1发送给解密装置120。

.生成随机数s。

.生成G(s)，根据G(s)生成u、K。

.使用公开密钥多项式h和随机数值u生成随机数s的第1加密文c1。

.输出共享密钥K和第1加密文c1。

其次，加密装置110使用导出的共享密钥K，用公共密钥密码对从外部输入的明码文mi(1≤i≤n)进行加密，生成加密文Ci(1≤i≤n)，并经因特网130发送给解密装置120。

另一方面，解密装置120将解密装置120的秘密密钥多项式f和公开密钥多项式h作为输入，经因特网130从加密装置110接收第1加密文c1，使用秘密密钥多项式f对第1加密文c1进行解密，生成解密随机数s’。其次，根据解密随机数s’的函数值G(s’)导出随机数值u’和共享密钥K’，对解密随机数s’进行加密，生成第1再加密文c1’，若c1’＝c1，则输出共享密钥K’。

即，该解密装置120进行以下处理，并导出共享密钥K’。

.使用秘密密钥多项式f对第1加密文c1进行解密，生成s’。

.生成G(s’)，根据G(s’)生成u’、K’。

.使用公开密钥多项式h和随机数值u’生成s’的第1再加密文c1’。

.检查c1’＝c1是否成立，若成立，则输出共享密钥K’。

这里，若在解密装置120中使用与在加密装置110中使用的公开密钥多项式h对应的正确的秘密密钥多项式f，则第1解密文c1被正确解密，变成解密随机数s’，因此，从G(s’)导出的随机数值u’＝u，共享密钥K’＝K。而且，因s’＝s和u’＝u成立，故c1’＝c1成立，解密装置120可以导出和加密装置110相同的共享密钥K。

其次，解密装置120使用导出的共享密钥K’(＝K)，经因特网从加密装置110对公共密钥加密文Ci(1≤i≤n)，以公共密钥密码进行解密，生成解密文mi’(1≤i≤n)，再向外部输出。这里，因公共密钥加密文生成时使用的密码密钥K和解密文生成时使用的密码密钥K’相同，故解密装置120可以正确地得到mi’＝mi(1≤i≤n)。

再有，当发生解密错误时，因解密随机数s’和随机数s不同，从G(s’)导出的随机数值u’和共享密钥K’分别和u、K不同。但是，这时，因s’、u’分别和s、u不同，故第1再加密文c1’和第1加密文c1不同，所以，解密装置120不输出共享密钥K’。

1.10实施形态1的效果

在现有的RSA-KEM算法中，将若不知道秘密密钥则不能从加密文C导出的要素s输入到散列函数G中，导出共享密钥K。但是，若使用NTRU密码并使用作为密钥密封机制的RSA-KEM算法进行共享密钥配送，因有时会发生解密错误，故即使使用秘密密钥也不能导出要素s，因此，有时会导出不正确的共享密钥K’。

但是，在实施形态1的内容分配系统、加密装置及解密装置中，根据随机数s的散列函数G(s)生成共享密钥和随机数值u，解密装置使用随机数值u和公开密钥多项式h对解密随机数s’进行再加密，生成第1再加密文c1’，只要第1再加密文c1’和第1加密文c是不同的值，就不输出共享密钥K’，所以，当发生解密错误时，可以防止加密装置和解密装置之间导出不同的密钥。

此外，本发明的方式可以利用和非专利文献3记载的证明方法同样的方法，从理论上证明其安全性。

1.11变形例

上述说明的实施形态1是实施本发明的一个例子，本发明不限于该实施形态，在不脱离其主旨的范围内可以实施各种各样的形态。本发明还包括以下情况。

(1)使用的NTRU密码的参数不限于N＝167。参数N也可以取其他的值。

(2)在加密部114和解密部123进行的位列的各个位值和多项式的各个项的系数之间的变换方法不限于上述已说明的方法，也可以是其他变换方法。

例如，从随机数s到随机数多项式sp的变换可以使用使位列的各个位的值和多项式的各个项的系数一一对应的函数进行变换，也可以使用使位列的各个位的值和多项式的各个项的系数一一对应而存储的函数值表进行变换。

此外，从随机数值u到随机数多项式r的变换，只要从u唯一地求出r，并设r的d个次方项的系数为‘1’，d个次方项的系数为‘-1’，其他次方项的系数为‘0’，则其他变换方法也可以，例如，也可以使用使随机数值u和多项式对应的函数，或使用函数值表进行变换。

(3)加密部114和解密部123使用的公开密钥密码方式若是能在加密部114中，使用公开密钥和随机数值u对随机数s进行加密再生成第1加密文c1，在解密部123中，使用秘密密钥对第1加密文c1进行解密，再生成和随机数值s相等的解密随机数s’即可。

因此，加密部114和解密部123使用的公开密钥密码除了NTRU密码之外，可以使用任何公开密钥密码。

例如，若采用E1Gamal密码，可以将h、f分别作为E1Gamal密码的公开密钥、秘密密钥，在加密部114中，使用h和u对随机数s进行加密再生成c1，在解密部123中，使用f对c1进行解密再生成S’。

再有，关于E1Gamal密码，因非专利文献1有详细记载，故这里省略说明。

(4)第1函数部113将函数值G(s)的高位k位作为随机数值u，低位k位作为共享密钥K，此外，只要从函数值G(s)导出随机数值u和共享密钥K，也可以采用其他方法。

例如，可以将函数值G(s)的高位k/2位作为随机数值u，低位k×3/2位作为共享密钥K。此外，也可以在函数值G(s)的2k位中，每隔1位选择k位作为随机数值u，将剩下的k位作为共享密钥K。

(5)随机数值u除了用第1函数部113和第2函数部126生成之外，只要在加密装置110和解密装置120中能得到相同的值，也可以采用其他生成方法。

例如，也可以对任意函数Func，使u＝Func(s)，从而可以使加密装置110和解密装置120中能得到相同的值。即，在加密装置110和解密装置120中，

.生成G(s)，根据G(s)生成K。

.生成Func(s)，使u＝Func(s)。

(6)随机数值u除了用第1函数部113和第2函数部126生成之外，因只要在加密装置110和解密装置120中能得到相同的值即可，故加密装置110也可以向解密装置120b直接发送随机数值u。

即，也可以像以下那样，将第1加密文c1和随机数值u发送给解密装置120。这时，随机数值u也可以加密后发送。

在加密装置110中，

.生成G(s)，根据G(s)生成K。

.通过别的渠道，从加密装置110向解密装置120发送随机数值U。

.接收随机数值u

.代替随机数值u’，使用接收的随机数值u生成第1再加密文c1’。

这时，也可以是加密装置110将随机数值u加密后再发送，解密装置120对加密后的随机数值u进行解密。

(7)随机数值u因只要加密装置110和解密装置120能得到相同的值即可，故也可以使用第1函数部113和第2函数部126生成随机数值u的一部分的部分信息，随机数值u的剩余部分的部分信息直接从加密装置110向解密装置120发送。

例如，也可以如以下那样，加密装置110将第1加密文c1和随机数值u2发送给解密装置120。

在加密装置110中，

(a)生成G(s)，根据G(s)生成K、u1。

(b)生成随机数值u2，通过另外的途径向解密装置120发送。

(c)根据u＝u1 xor u2生成随机数值u。

(d)使用随机数值u生成第1加密文c1。

在解密装置120中，

(e)接收随机数值u2。

(f)生成G(s’)，根据G(s’)生成K’、u1’。

(g)根据u’＝u1’xor u2生成随机数值u’。

(h)使用生成的随机数值u’生成第1再加密文c1’。

这时，也可以是加密装置110加密随机数值u2再发送，解密装置120对加密的随机数值u2进行解密。

此外，也可以在(c)和(g)中，代替“异”xor而进行其他的运算。例如，也可以在(c)和(g)中，分别使用加法运算和减法运算，此外，也可以使用乘法运算和除法运算。

(8)为了防止因发生解密错误而在加密装置110和解密装置120之间导出不同的共享密钥，当第1再解密文c1’和第1加密文c1相同时，不马上输出共享密钥K’，而使加密装置110对任何1个以上的随机数s、随机数值u或共享密钥K生成散列函数值，并将生成的散列函数值发送给解密装置120，通过解密装置120验证该散列函数值来决定是否输出共享密钥K’。例如，作为该散列函数值，也可以对任意的散列函数H生成随机数s的散列函数值H(s)，也可以使随机数s、随机数值u和共享密钥K组合生成散列函数值H(s||u||k)或散列函数值H(u||k)等。

此外，这时，加密装置110的第1函数部113也可以不从函数值G(s)导出随机数值u和共享密钥K，而只从G(s)导出共享密钥K。

下面，叙述其具体例。

内容分配系统10不包含加密装置110和解密装置120，而包含加密装置110b和解密装置120b，加密装置110b如图6所示，由公开密钥输入部111、随机数生成部112、第1函数部113b、加密部114b、第1发送部117b、公共密钥加密部118和第2发送部119构成，解密装置120如图7所示，由秘密密钥输入部121、第1接收部122b、解密部123b、第2函数部126b、比较部127b、公共密钥解密部128和第2接收部129构成。比较部127b包含第3函数部127u和比较运算部127v。

加密装置110b生成随机数s的散列函数值，解密装置120b在验证该散列函数值时，在加密装置110b中，如图8的处理系统图所示，第1函数部113b生成G(s)(步骤S103)，根据G(s)生成K(步骤S104)。

其次，加密部114b生成随机数值u，根据生成的随机数值u生成随机数多项式r，使用随机数多项式r和公开密钥多项式h生成随机数s的第1加密文c1(步骤S105)，生成散列函数值H(s)(步骤S111)。

其次，第1发送部117b发送第1加密文c1(步骤S106)，并发送散列函数值H(s)(步骤S112)。

其次，在解密装置120b中，第1接收部122b接收第1加密文c1(步骤S106)，并接收散列函数值H(s)(步骤S112)

其次，解密部123b使用秘密密钥多项式f解密第1加密文c1再生成s’(步骤S152)。

其次，第2函数部126生成G(s’)(步骤S153)，根据G(s’)生成K’(步骤S154)。

其次，比较部127利用第3函数部127u生成H(s’)(步骤S154)，利用比较运算部127v检验H(s’)＝H(s)是否成立(步骤S162)，若成立则输出共享密钥K’(步骤S157)。

此外，这时，为了进一步提高安全性，也可以使用专利文献1公开的方法，对附加了附加信息的随机数s进行加密，生成第1加密文c1。即，也可以是，在图6中，加密部114b生成附加信息Ra，对s和Ra的位结合s||Ra的值进行加密，生成第1加密文c1，在图7中，解密部123b解密第1加密文c1，生成s’||Ra’，除去Ra’再生成解密随机数s’。

此外，如专利文献1公开的那样，也可以不使用s||Ra的值，而使用s和Ra的可逆变换F(s、Ra)的值。

2.实施形态2

说明作为本发明的另1个实施形态的内容分配系统10c(未图示)。

内容分配系统10c是在内容分配系统10的基础上对其进行变形的系统，和内容分配系统10的不同点在于：根据函数值G(s)，除随机数值u和共享密钥K之外进而还生成验证值a；加密装置不是生成并发送将随机数s加密后的第1加密文c1，而是生成并发送将验证值a加密后的第1加密文c1和根据验证值a将随机数s加密后的第2加密文c2。

下面，以上述不同点为中心详细说明内容分配系统10c。

2.1内容分配系统10c的构成

内容分配系统10c具有和内容分配系统10同样的构成，取代加密装置110和解密装置120，而包含加密装置110c和解密装置120c。其他的构成因和内容分配系统10一样，故省略其说明。

2.2加密装置110c的构成

加密装置110c如图9所示，具有和加密装置110同样的构成，取代随机数生成部112、第1函数部113、加密部114和第1发送部117，而是包含随机数生成部112c、第1函数部113c、加密部114c、随机数屏蔽部116c和第1发送部117c。

这里，说明随机数生成部112c、第1函数部113c、加密部114c、随机数屏蔽部116c和第1发送部117c。

(1)随机数生成部112c

随机数生成部112c生成随机数s作为用来生成共享密钥K的基础的种子值，并将生成的随机数s输出给第1函数部113b和随机数屏蔽部116c。

(2)第1函数部113c

第1函数部113c从随机数生成部112c接收随机数s，生成随机数s的函数值G(s)。其次，根据生成的函数值G(s)生成验证值a、共享密钥K和随机数值u。

这里，函数G是输出长度为3k位的散列函数，第1函数部113c将函数值G(s)的高位k位作为验证值a，将函数值G(s)中间的k位作为共享密钥K，将函数值G(s)的低位k位作为随机数值u。

其次，第1函数部113c向加密部114c输出已生成的验证值a和随机数值u，将生成的共享密钥K向公共密钥加密部118输出。将生成的验证值a向随机数屏蔽部116c输出。

(3)加密部114c

加密部114c从公开密钥输入部111接收公共密钥多项式h，从第1函数部113c接收验证值a和随机数值u。并如下面所示，使用公开密钥多项式h和随机数值u生成验证值a的第1加密文c1。这里，第1加密文c1是NTRU密码的加密文。

加密部114c生成由随机数值u唯一求出的随机数多项式r，该随机数多项式r对于NTRU密码的参数d，其d个项的各系数是‘1’，其余d个项的各系数是‘-1’，剩下的项的各系数是‘0’。具体地说，将随机数值u作为模拟随机数系列的初始值(随机数种子)来设定，从{0、1、......N-1}中选择2d个不重复的模拟随机数，设由最初的d个模拟随机数表示的次方项的系数为‘1’，由剩下的d个模拟随机数分别表示的次方项的系数为‘-1，其余项的系数为‘0’，由此来生成随机数多项式r。

其次，加密部114c为了使接收的验证值a能够适用于NTRU密码的加密算法E而构成验证值多项式ap，使由二进制表现验证值a时的N位位列的各位的值与验证值多项式ap各项的系数对应，并由此将验证值a变换成验证值多项式ap。例如，设验证值a的低位的第b位的值是项X^b的系数的值。具体地说，当验证值a＝10010(用位表现)时，生成验证值多项式ap＝X^5+X^2。

其次，加密部114c使用公开密钥多项式h作为密钥，使用随机数多项式r对验证值多项式ap执行上述加密算法E，生成作为加密文多项式的第1加密文c1＝E(ap、r、h)。

其次，加密部114c将生成的第1加密文c1输出给第1发送部117c。

(4)随机数屏蔽部116c

随机数屏蔽部116c从随机数生成部112c接收随机数s，从第1函数部113c接收验证值a，其次，生成第2加密文c2＝s xor a，并将生成的第2加密文c2输出给第1发送部117c。

这里，xor是表示“异”运算的运算符。

再有，随机数屏蔽部116c也可以不用“异”运算，而用共享密钥加密算法、加法运算或乘法运算。

(5)第1发送部117c

第1发送部117c从加密部114c接收第1加密文c1，从随机数屏蔽部116c接收第2加密文c2，经因特网130将所接收的第1加密文c1和第2加密文c2送往解密装置120c。

2.2解密装置120c的构成

解密装置120c如图10所示，具有和解密装置120同样的构成，取代第1接收部122、解密部123、第2函数部126和比较部127，而包含第1接收部122c、解密部123c、随机数屏蔽除去部125c、第2函数部126c和比较部127c。

这里，说明第1接收部122c、解密部123c、随机数屏蔽除去部125c、第2函数部126c和比较部127c。

(1)第1接收部122c

第1接收部122c经因特网130从加密装置110c接收第1加密文c1和第2加密文c2，将接收的第1加密文c1输出给解密部123c，将接收的第2加密文c2输出给随机数屏蔽除去部125c。

(2)解密部123c

解密部123c从秘密密钥输入部121接收秘密密钥多项式f，从第1接收部122c接收第1加密文c1，如下面所示，使用秘密密钥多项式f，对第1加密文c1进行解密，生成解密验证值a’。这里，解密验证值a’是基于NTRU密码的解密文。

解密部123c使用秘密密钥多项式f作为密钥，对第1加密文c1执行上述解密算法D，生成解密验证值多项式ap’＝D(c1、f)。这里，解密验证值多项式ap’是用多项式表现的NTRU密码的解密文，所以，解密部123c将解密验证值多项式ap’变换成解密验证值a’，使解密验证值多项式ap’各项的系数与用二进制表现的N位位列的解密验证值a’的各位的值对应。例如，解密验证值多项式ap’的b次方项X^b的系数变成解密验证值a’的低位第b位的值。具体地，解密验证值多项式ap’＝X^5+X^2时，转换为解密验证值a’＝10010(用位表现)。

其次，解密部123c将生成的解密验证值a’输出给随机数屏蔽除去部125c，将接收的第1加密文c1输出给比较部127c。

(3)随机数屏蔽除去部125c

随机数屏蔽除去部125c从第1接收部122c接收第2加密文c2，从解密部123c接收解密验证值a’，生成解密随机数s’＝c2 xor a’，并将生成的随机数s’输出给第2函数部126c。

再有，当随机数屏蔽部116c不用“异”运算，而用共享密钥加密算法、加法运算或乘法运算时，随机数屏蔽部125c也可以分别使用与共享密钥加密算法对应的共享密钥解密算法、减法运算或除法运算。

(4)第2函数部126c

第2函数部126c具有和第1函数部113c所具有的函数相同的函数G的算法。

第2函数部126c从随机数屏蔽除去部125c接收解密随机数s’，并生成接收的解密随机数s’的函数值G(s’)。其次，和第1函数部113c同样，根据函数值G(s’)生成验证值a”、共享密钥K’和随机数值u’，将生成的验证值a”、共享密钥K’和随机数值u’输出给比较部127c。

(5)比较部127c

比较部127c如图10所示，由比较运算部127s和加密部127t构成。

加密部127t从秘密密钥输入部121接收公开密钥多项式h，从第2函数部126c接收验证值a”和随机数值u’，和加密部114c一样，使用接收的公开密钥多项式h和随机数值u’，对验证值a”进行加密，生成第1再加密文c1’，并将生成的第1再加密文c1’输出给比较运算部127s。

此外，比较运算部127s从第2函数部126c接收共享密钥K’，从解密部123c接收第1加密文c1，从加密部127t接收第1再加密文c1’，其次，将接收的第1加密文c 1和接收的第1再加密文c1’进行比较，当判断第1加密文c1＝第1再加密文c1’时，将接收的共享密钥K’输出给公共密钥解密部128。

2.3内容分配系统10c的动作

下面，使用图11所示的处理系统图说明实施形态2的内容分配系统10c的全部动作。

加密装置110c接收解密装置120c的公开密钥多项式h(步骤S101)，生成随机数s(步骤S102)，并求出函数值G(s)，根据函数值G(s)导出验证值a、共享密钥K和随机数值u(步骤S 121)。其次，加密装置110c使用公开密钥多项式h和随机数值u，并采用NTRU密码对验证值a进行加密，生成第1加密文c1(步骤S105)，并根据验证值a对随机数s进行加密，生成第2加密文c2＝s xor a(步骤S122)。其次，加密装置110c经因特网130将第1加密文c1和第2加密文c2发送给解密装置120c(步骤S106)。

即，该加密装置110c进行以下处理，将加密文C＝(c1、c2)发送给解密装置120c。

(a)生成随机数s。

(b)生成G(s)，根据G(s)生成a、K、u。

(c)使用公开密钥多项式h和随机数值u生成验证值a的第1加密文c1。

(d)生成c2＝s xor a。

其次，加密装置110c使用导出的共享密钥K，利用公共密钥密码方式对从内容服务装置140接收的明码文mi(1≤i≤n)进行加密，生成加密文Ci(1≤i≤n)，并经因特网130发送给解密装置120c(步骤S108)。

另一方面，解密装置120c接收解密装置120c的秘密密钥多项式f和公开密钥多项式h(步骤S151)，经因特网130从加密装置110c接收第1加密文c1和第2加密文c2(步骤S106)，使用秘密密钥多项式f对第1加密文c1进行解密，生成解密验证值a’(步骤S152)。其次，根据解密验证值a’解密第2加密文c2，生成解密随机数s’＝c2xor a’(步骤S171)。其次，解密装置120c根据解密随机数s’的函数值G(s’)导出验证值a”、随机数值u’和共享密钥K’(步骤S172)。进而，对验证值a”进行加密，生成第1再加密文c1’(步骤S155)，若c1’＝c1(步骤S156)，则输出共享密钥K’(步骤S157)。

即，该解密装置120c进行以下处理，并导出共享密钥K’。

(a)使用秘密密钥多项式f对第1加密文c1进行解密，生成a’。

(b)生成s’＝c2 xor a’。

(c)生成G(s’)，根据G(s’)生成a”、u’、K’。

(d)使用公开密钥多项式h、随机数值u’生成a”的第1再加密文c1’。

(e)检查c1’＝c1是否成立，若成立，则输出共享密钥K’。

这里，若在解密装置120c中使用与在加密装置110c中使用的公开密钥多项式h对应的正确的秘密密钥多项式f，则第1解密文c1被正确解密，解密验证值a’＝a，根据第2加密文c2和a’生成的解密随机数s’＝s。因此，从G(s’)导出的验证值a”＝a，共享密钥K’＝K成立，随机数值u’＝u。这样，因a”＝a和u’＝u成立，故c1’＝c1成立，解密装置120c可以导出和加密装置110c相同的共享密钥K。

其次，解密装置120c经因特网130从加密装置110c接收公共密钥加密文Ci(1≤i≤n)，使用导出的共享密钥K’(＝K)，并利用公共密钥密码方式对接收的公共密钥加密文Ci(1≤i≤n)进行解密，生成解密文mi’(1≤i≤n)，再将解密文mi’(1≤i≤n)输出给再生装置150。

这里，因公共密钥加密文生成时使用的加密密钥K和解密文生成时使用的加密密钥K’相同，故解密装置120c可以得到正确的解密文mi’＝mi(1≤i≤n)。

再有，当发生解密错误时，因解密验证值a’和验证值a不同，故从第2加密文c2得到的解密随机数s’和s不同。因此，从G(s’)导出的随机数值u’和共享密钥K’分别和u、K不同。但是，这时，因a’、u’分别和a、u不同，故第1再加密文c1’和第1加密文c1不同，所以，解密装置120c不输出共享密钥K’。

2.4实施形态2的效果

在现有的RSA-KEM算法中，将若不知道秘密密钥则不能从加密文C导出的要素s输入到散列函数G中，导出共享密钥K。但是，若使用NTRU密码并使用作为密钥密封机制的RSA-KEM算法进行共享密钥的配送，则因有时会发生解密错误，故即使使用秘密密钥也不能导出要素s，因此，有时会导出不正确的共享密钥K’。

但是，在实施形态2的内容分配系统、加密装置及解密装置中，根据随机数s的散列函数G(s)除生成共享密钥之外还生成验证值a和随机数值u，解密装置使用随机数值u和公开密钥多项式h对解密验证值a’进行再加密，生成第1再加密文c1’，只要第1再加密文c1’和第1加密文c是不同的值，就不输出共享密钥K’，所以，当发生解密错误时，可以防止加密装置和解密装置之间导出不同的密钥。

此外，本发明的方式可以利用和非专利文献3记载的证明方法同样的方法，从理论上证明其安全性。

2.5变形例

上述说明的实施形态2是实施本发明的一个例子，本发明不限于该实施形态，在不脱离其主旨的范围内可以实施各种各样的形态。当然可以实施和实施形态1同样的变形例，本发明还包括以下情况。

(1)从验证值a到验证值多项式ap的变换也可以使用其他变换方法，例如，可以使用使位列的各个位的值和多项式的各个项的系数一一对应的函数进行变换，也可以使用使位列的各个位的值和多项式的各个项的系数一一对应而存储的函数值表进行变换。

此外，从随机数值u到随机数多项式r的变换也可以使用其他变换方法，例如，只要从u唯一地求出r，并设d个次方项的系数为‘1’，d个次方项的系数为‘-1’，其他次方项的系数为‘0’，则其他变换方法也可以，例如，也可以使用使随机数值u和多项式对应的函数，或函数值表来进行变换。

(2)加密部114c和解密部123c使用的公开密钥密码若是能在加密部114c中，使用公开密钥和随机数值u对验证值a进行加密再生成第1加密文c1，在解密部123c中，使用秘密密钥对第1加密文c1进行解密，再生成和验证值a相等的解密验证值a’即可。因此，加密部114c和解密部123c使用的公开密钥密码除了NTRU密码之外，只要是使用随机数的公开密钥密码，任何密码都可以。

例如，若采用E1Gamal密码，则可以将h、f分别作为E1Gamal密码的公开密钥、秘密密钥，在加密部114c中，使用h和随机数值u对a进行加密再生成c1，在解密部123c中，使用f对c1进行解密再生成a’。

(3)随机数值u除了用第1函数部113c和第2函数部126c生成之外，只要在加密装置110c和解密装置120c中能得到相同的值，也可以采用其他生成方法。

例如，也可以对任意函数Func，使u＝Func(s)，从而可以使加密装置110c和解密装置120c中能得到相同的值。即，也可以

.生成G(s)，根据G(s)生成a、K。

.生成Func(s)，使u＝Func(s)。

(4)随机数值u除了用第1函数部113c和第2函数部126c生成之外，因只要在加密装置110c和解密装置120c中能得到相同的值即可，故加密装置110c也可以向解密装置120c直接发送随机数值u。

即，也可以像以下那样，加密装置110c将加密文C和随机数值u发送给解密装置120b。此外，随机数值u也可以加密后发送。

.生成G(s)，根据G(s)生成a、K。

.通过别的渠道，从加密装置110c向解密装置120b发送随机数值u。

(5)随机数值u因只要在加密装置110c和解密装置120c能得到相同的值即可，故也可以使用第1函数部113c和第2函数部126c生成随机数值u的一部分的部分信息，随机数值u的剩下的部分信息直接从加密装置110c向解密装置120c发送。

例如，如下所述，加密装置110c可以将加密文C和随机数值u2发送给解密装置120c，此外，加密装置110c也可以将随机数值u2加密后再发送。

.生成G(s)，根据G(s)生成a、K、u1。

.通过别的渠道，从加密装置110c向解密装置120b发送随机数值u2。

.加密装置110c生成随机数值U＝u1 xor u2。

(6)解密装置120c检验第1加密文c1是不是由第2函数部126c得到的验证值a”的加密文，当c1是a”的加密文时，使用共享密钥K’对公共密钥加密文Ci进行解密，但也可以检验第1加密文c1是不是解密验证值a’的加密文。

(7)解密装置120c检验第1加密文c1是不是由第2函数部126c得到的验证值a”的加密文，当c1是a”的加密文时，使用共享密钥K’对公共密钥加密文Ci进行解密，但也可以像图12的处理系统图的步骤S156所示那样，在比较部127c中，检验解密部123c解密后的a’值是否等于由第2函数部126c生成的a”的值。

(8)为了防止因发生解密错误而在加密装置110c和解密装置120c之间导出不同的密钥，也可以检验第1再解密文c1’和第1加密文c1的值是否相同，取代输出共享密钥K’，而使加密装置110c对任何1个以上的随机数s、验证值a、随机数值u或共享密钥K生成散列函数值，并将生成的散列函数值发送给解密装置120c，通过解密装置120c验证该散列函数值来决定是否输出共享密钥K’，为了提高安全性，也可以使用专利文献1公开的方法。即，也可以使用实施形态1的变形例(8)。

3.实施形态1和实施形态2的总结

如以上说明的那样，本发明是输出共享密钥数据和根据预先给出的公开密钥数据将上述共享密钥数据加密后的加密共享密钥数据的共享密钥生成装置，包括：生成秘密数数据的秘密数数据生成部；按照规定的处理将上述秘密数数据变换成随机数数据和上述共享密钥数据的共享密钥导出部；根据上述公开密钥数据和上述随机数数据将上述秘密数数据加密后生成加密共享密钥数据的第1加密部。

此外，本发明是输出共享密钥数据和根据预先给出的公开密钥数据将上述共享密钥数据加密后的加密共享密钥数据的共享密钥生成装置，包括：生成秘密数数据的秘密数数据生成部；按照规定的处理将上述秘密数数据变换成验证值数据、随机数数据和上述共享密钥数据的共享密钥导出部；根据上述公开密钥数据和上述随机数数据将上述验证值数据加密后生成第1加密预备数据的第1加密部；根据上述验证值数据将上述秘密数数据加密后生成第2加密预备数据的第2加密部，上述加密共享密钥数据由上述第1加密预备数据和第2加密预备数据构成。

这里，上述第2加密部可以进行上述秘密数数据和上述验证值数据的“异”运算后再生成上述第2加密预备数据。

这里，上述第2加密部可以使用上述验证值数据作为加密密钥，并利用公共密钥加密方式将上述秘密数数据加密后生成上述第2加密预备数据。

这里，上述第2加密部可以使上述验证值数据和上述秘密数数据相加再生成上述第2加密预备数据。

这里，上述第2加密部可以使上述验证值数据和上述秘密数数据相乘再生成上述第2加密预备数据。

这里，上述加密共享密钥数据可以是上述第1加密预备数据和上述第2加密预备数据的位连接数据。

这里，上述第1加密部可以利用NTRU密码方式加密后再生成上述加密共享密钥数据。

这里，上述第1加密部可以利用NTRU密码方式加密后再生成上述第1加密预备数据。

这里，上述秘密数数据可以是随机生成的随机数。

这里，作为规定的处理，上述公共密钥导出部可以使用单向散列函数。

此外，本发明是根据预先给出的秘密密钥数据和公开密钥数据将加密公共密钥数据解密后输出公共密钥数据的公共密钥复原装置，包括：根据上述秘密密钥数据解密上述加密共享密钥数据后再生成秘密数数据的第1解密部；按照规定的处理将上述秘密数数据变换成随机数数据和上述共享密钥数据的共享密钥导出部；根据上述公开密钥数据和上述随机数数据将上述秘密数数据加密后生成再加密共享密钥数据的第3加密部，当上述加密共享密钥数据和上述再加密共享密钥数据一致时，输出上述共享密钥数据。

此外，本发明是根据预先给出的秘密密钥数据和公开密钥数据将由第1加密预备数据和第2加密预备数据构成的加密共享密钥数据解密后输出共享密钥数据的共享密钥复原装置，包括：根据上述秘密密钥数据解密上述第1加密预备数据后再生成验证值数据的第1解密部；根据上述验证值数据解密上述第2加密预备数据后再生成秘密数数据的第2解密部；按照规定的处理将上述秘密数数据变换成验证值验证数据、随机数数据和上述共享密钥数据的共享密钥导出部；根据上述公开密钥数据和上述随机数数据将上述验证值验证数据加密后生成第3加密预备数据的第3加密部，当上述第1加密预备数据和上述第3加密预备数据一致时，输出上述共享密钥数据。

此外，本发明是根据预先给出的秘密密钥数据和公开密钥数据将由第1加密预备数据和第2加密预备数据构成的加密共享密钥数据解密后输出共享密钥数据的共享密钥复原装置，包括：根据上述秘密密钥数据解密上述第1加密预备数据后再生成验证值数据的第1解密部；根据上述验证值数据解密上述第2加密预备数据后再生成秘密数数据的第2解密部；按照规定的处理将上述秘密数数据变换成验证值验证数据、随机数数据和上述共享密钥数据的共享密钥导出部；根据上述公开密钥数据和上述随机数数据将上述验证值数据加密后生成第3加密预备数据的第3加密部，当上述第1加密预备数据和上述第3加密预备数据一致时，输出上述共享密钥数据。

这里，上述第2解密部可以进行上述第2加密预备数据和上述验证值数据的“异”运算后再生成上述秘密数数据。

这里，上述第2解密部可以使用上述验证值数据作为加密密钥，并利用共享密钥加密方式将上述第2加密预备数据解密后生成上述秘密数数据。

这里，上述第2解密部可以使第2加密预备数据减去上述验证值数据后再生成上述秘密数数据。

这里，上述第2解密部可以采用上述第2加密预备数据除以上述验证值数据后再生成上述秘密数数据。

这里，上述第1解密部可以利用NTRU密码方式解密后再生成上述共享密钥数据。

这里，上述第1解密部可以利用NTRU密码方式解密后再生成上述验证值数据。

这里，作为规定的处理，上述共享密钥导出部可以使用单向散列函数。

此外，本发明是根据预先给出的公开密钥数据生成将明码文数据加密后的加密文数据的加密装置，包括：生成秘密数数据的秘密数数据生成部；按照规定的处理将上述秘密数数据变换成随机数数据和共享密钥数据的共享密钥导出部；根据上述公开密钥数据和上述随机数数据加密上述秘密数数据后再生成第1加密预备数据的第1加密部；根据上述共享密钥数据将上述明码文数据加密后生成第2加密预备数据的第2加密部，上述加密文数据由上述第1加密预备数据和上述第2加密预备数据构成。

此外，本发明是根据预先给出的秘密密钥数据和公开密钥数据将由第1加密预备数据和第2加密预备数据构成的加密文数据解密后输出解密文数据的解密装置，包括：根据上述秘密密钥数据将上述第1加密预备数据解密后生成秘密数数据的第1解密部；按照规定的处理将上述秘密数数据变换成随机数数据和共享密钥数据的共享密钥导出部；根据上述公开密钥数据和上述随机数数据将上述秘密数数据加密后生成第3加密预备数据的第3加密部，还包括解密部，当上述第1加密预备数据和上述第3加密预备数据一致时，根据上述共享密钥将上述第2加密预备数据解密后生成上述解密文数据。

此外，本发明是由根据预先给出的公开密钥数据生成将明码文数据加密后的加密文数据的加密装置和根据预先给出的秘密密钥数据和公开密钥数据将加密文数据解密后输出解密文数据的解密装置构成的密码系统。上述加密装置包括：生成秘密数数据的秘密数数据生成部；按照规定的处理将上述秘密数数据变换成随机数数据和共享密钥数据的共享密钥导出部；根据上述公开密钥数据和上述随机数数据加密上述秘密数数据后再生成第1加密预备数据的第1加密部；根据上述共享密钥数据将上述明码文数据加密后生成第2加密预备数据的第2加密部，上述加密文数据由上述第1加密预备数据和上述第2加密预备数据以及上述第3加密预备数据构成。上述解密装置包括：根据上述秘密密钥数据将上述第1加密预备数据解密后生成秘密数数据的第1解密部；按照规定的处理将上述秘密数数据变换成随机数数据和共享密钥数据的共享密钥导出部；根据上述公开密钥数据和上述随机数数据将上述秘密数数据加密后生成第3加密预备数据的第3加密部，还包括解密部，当上述第1加密预备数据和上述第3加密预备数据一致时，根据上述共享密钥将上述第2加密预备数据解密后生成上述解密文数据。

如以上说明的那样，本发明是鉴于现有系统中的问题而提出的，所以，在密码系统中，通过构成能使用NTRU密码的新的密钥密封机制，可以防止加密装置和解密装置之间导出不同的密钥，并可以可靠地进行从使用了由密钥密封机制导出的密钥的发送装置向接收装置的加密通信。

如上所述，可以提供一种现有技术不能实现的密码系统，具有很大的价值。

4.实施形态3

说明作为本发明的另1个实施形态的内容分配系统10d(未图示)。

再有，内容分配系统10d是将内容分配系统10变形后的系统，这里，以和内容分配系统10d的不同点为中心详细说明内容分配系统10d。

4.1内容分配系统10d的构成

内容分配系统10d具有和内容分配系统10同样的构成，取代加密装置110和解密装置120，而包含加密装置110D和解密装置120d。其他的构成因和内容分配系统10一样，故省略其说明。

内容分配系统10d是通过使用NTRU密码进行密钥密封机制的密钥配送后再进行加密通信的加密通信系统，加密装置110d和解密装置120D经因特网130连接。

4.2加密装置110d的构成

加密装置110d如图13所示，由公开密钥输入部111d、随机数生成部112d、第1函数部113d、加密部114d、第2函数部115d、随机数屏蔽部116d、第1发送部117d、公共密钥加密部118和第2发送部119构成。

加密装置110d是和加密装置110一样的计算机系统，加密装置110d通过使微处理器按照计算机程序动作来实现其功能。

(1)公开密钥输入部111d

公开密钥输入部111d从存储卡160读出解密装置120的公开密钥多项式h，将读出的公开密钥多项式h输出给加密部114d。

(2)随机数生成部112d

随机数生成部112d生成随机数s作为用来生成共享密钥K的基础的种子值，并将生成的随机数s输出给第1函数部113和随机数屏蔽部116。

(3)第1函数部113d

第1函数部113d从随机数生成部112d接收随机数s，生成接收的随机数s的函数值G(s)，根据函数值G(s)生成验证值a和共享密钥K。这里，函数G是作为单向函数的输出长度为2k位的散列函数，第1函数部113d将函数值G(s)的高位k位作为验证值a，将函数值G(s)的低位k位作为共享密钥K。

其次，第1函数部113d向加密部114d和第2函数部115d输出已生成的验证值a，将生成的共享密钥K向共享密钥加密部118输出。

(4)加密部114d

加密部114d从公开密钥输入部111d接收公共密钥多项式h，从第1函数部113d接收验证值a，如下面所示，使用接收的公开密钥多项式h生成验证值a的第1加密文c1。这里，生成的第1加密文c1是NTRU密码的加密文。

加密部114d随机生成随机数多项式r，该随机数多项式r对于NTRU密码的参数d，其d个项的各系数是‘1’，其余d个项的各系数是‘-1’，剩下的项的各系数是‘0’。其次，为了使验证值a能够适用于NTRU密码的加密算法E而生成验证值多项式ap，使由二进制表现验证值a时的N位位列的各位的值与验证值多项式ap的各项的系数对应。例如，设验证值a的低位的第b位的值是验证值多项式ap的项X^b的系数，这样将验证值a变换成验证值多项式ap。具体地说，当验证值a＝10010(用位表现)时，变换成验证值多项式ap＝X^5+X^2。其次，使用公开密钥多项式h，并使用随机数多项式r对验证值多项式ap执行上述加密算法E，生成作为加密文多项式的第1加密文c1＝E(ap、r、h)。

其次，加密部114d将生成的第1加密文c1输出给第2函数部115d和第1发送部117d。

(5)第2函数部115d

第2函数部115d从第1函数部113d接收验证值a，从加密部114d接收第1加密文c1，如下面所示那样，生成验证值a和第1加密文c1的函数值H(a、c1)。

这里，函数H是散列函数，是单向函数的一种。

因第1加密文c1是由多项式表示的NTRU密码的加密文，故第2函数部115d生成第1加密文位列c1’，使第1加密文c1的各项系数与用二进制表现时的N位第1加密文位列c1’的各位的值对应。例如，将第1加密文c1的b次方的项X^b的系数作为第1加密文位列c1’的低位第b位的值。这样，将第1加密文c1变换成第1加密文位列c1’。具体地说，当第1加密文c1＝X^5+X^2时，变换成第1加密文位列c1’＝10010(用位表现)。

其次，第2函数部115d向散列函数H输入验证值a和第1加密文位列c1’的位结合a||c1’，生成函数值H(a、c1)＝H(a||c1’)。这里，‘||’是表示位结合的运算符。

其次，第2函数部115d向随机数屏蔽部116d输出已生成的函数值H(a、c1)。

(6)随机数屏蔽部116d

随机数屏蔽部116d从随机数生成部112d接收随机数s，从第2函数部115d接收函数值H(a、c1)。其次，生成第2加密文c2＝s xorH(a、c1)，并将生成的第2加密文c2输出给第1发送部117d。

再有，随机数屏蔽部116d也可以不用“异”运算，而用共享密钥加密算法、加法运算或乘法运算。

(7)第1发送部117d

第1发送部117d从加密部114d接收第1加密文c1，从随机数屏蔽部116d接收第2加密文c2，经因特网130将接收的第1加密文c1和第2加密文c2送往解密装置120d。

(8)公共密钥加密部118和第2发送部119

公共密钥加密部118和第2发送部119除了以下的点之外，分别和加密装置110中包含的公共密钥加密部118和第2发送部119相同。

公共密钥加密部118从第1函数部113d接收共享密钥K。

4.3解密装置120d的构成

解密装置120d如图14所示，由秘密密钥输入部121d、第1接收部122d、解密部123d、第3函数部124d、随机数屏蔽除去部125d、第4函数部126d、比较部127d、公共密钥解密部128和第2接收部129构成。

解密装置120d是和解密装置120一样的计算机系统，解密装置120d通过使微处理器按照计算机程序动作来实现其功能。

再有，公共密钥解密部128和第2接收部129分别和解密装置120中包含的公共密钥解密部128和第2接收部129相同，这里省略其说明。

(1)秘密密钥输入部121d

秘密密钥输入部121d从存储卡170读出解密装置120d的秘密密钥多项式f，将读出的秘密密钥多项式f输出给解密部123d。

(2)第1接收部122d

第1接收部122d经因特网130从加密装置110d接收第1加密文c1和第2加密文c2，将接收的第1加密文c1输出给解密部123d和第3函数部124d，将接收的第2加密文c2输出给随机数屏蔽除去部125d。

再有，当随机数屏蔽部116d不用“异”运算，而用共享密钥加密算法、加法运算或乘法运算时，随机数屏蔽除去部125d也可以分别使用与共享密钥加密算法对应的共享密钥解密算法、减法运算或除法运算。

(3)解密部123d

解密部123d从秘密密钥输入部121d接收秘密密钥多项式f，从第1接收部122d接收第1加密文c1，如下面所示，使用秘密密钥多项式f，对第1加密文c1进行解密，生成解密验证值a’。这里，解密验证值a’是基于NTRU密码的解密文。

解密部123d使用秘密密钥多项式f，对第1加密文c1执行上述解密算法D，生成解密验证值多项式ap’＝D(c1、f)。其次，解密验证值多项式ap’是用多项式表现的NTRU密码的解密文，所以，解密部123d生成解密验证值a’，使解密验证值多项式ap’的各系数与用二进制表现解密验证值a’时的N位位列的各位的数对应。例如，将解密验证值多项式ap’的b次方的项X^b的系数作为解密验证值a’的低位第b位的值。这样，将解密验证值多项式ap’变换成解密验证值a’。具体地说，当解密验证值多项式ap’＝X^5+X^2时，变换成解密验证值a’＝10010(用位表现)。

其次，解密部123d将生成的解密验证值a’输出给第3函数部124d和比较部127d。

(4)第3函数部124d

第3函数部124d具有和第2函数部115d所具有的函数相同的函数H的算法。

第3函数部124d从第1接收部122d接收第1加密文c1，从解密部123d接收解密验证值a’。其次，和第2函数部115d一样，生成验证值a’和第1加密文c1的函数值H(a’、c1)，将生成的函数值H(a’、c1)输出给随机数屏蔽除去部125d。

(5)随机数屏蔽除去部125d

随机数屏蔽除去部125d从第1接收部122d接收第2加密文c2，从第3函数部124d接收散列函数值H(a’、c1)，其次，生成解密随机数s’＝c2 xor H(a’、c1)，将生成的解密随机数s’输出给第4函数部126d。

(6)第4函数部126d

第4函数部126d具有和第1函数部113d具有的函数相同的函数G的算法。

第4函数部126d从随机数屏蔽除去部125d接收解密随机数s’，生成解密随机数s’的散列函数值G(s’)。其次，和第1函数部113d同样，根据函数值G(s’)生成验证值a”和共享密钥K’，将生成的验证值a”和共享密钥K’输出给比较部127d。

(7)比较部127d

比较部127d从解密部123d接收解密验证值a’，从第4函数部126d接收验证值a”和共享密钥K，其次，检验解密验证值a’和验证值a”是否相等，若解密验证值a’和验证值a”相等，将共享密钥K’输出给公共密钥解密部128。

(8)公共密钥解密部128和第2接收部129

公共密钥解密部128从比较部127d接收共享密钥K’。

公共密钥解密部128在其他的点上和解密装置120包含的公共密钥解密部128相同，故这里省略说明。

此外，第2接收部129和解密装置120包含的第2接收部129相同，故这里省略说明。

4.4内容分配系统10d的动作

使用图15所示的流程图和图16所示的处理系统图说明内容分配系统10d的动作。

公开密钥输入部111d从存储卡160接收解密装置120的公开密钥多项式h，将公开密钥多项式h输出给加密部114d(步骤S201)。

其次，随机数生成部112d生成随机数s，再将随机数s输出给第1函数部113d和随机数屏蔽部116d(步骤S202)。

其次，第1函数部113d从随机数生成部112d接收随机数s，生成随机数s的函数值G(s)(步骤S203)。接着，第1函数部113d根据函数值G(s)生成验证值a和共享密钥K，再将输出验证值a输出给加密部114d和第2函数部115d，将共享密钥K输出给公共密钥加密部118(步骤S204)。

其次，加密部114d从公开密钥输入部111d接收公开密钥多项式h，从第1函数部113d接收验证值a。接着，加密部114d使用公开密钥多项式h生成验证值a的第1加密文c1，并将第1加密文c1输出给第2函数部115d和第1发送部117d(步骤S205)。

其次，第2函数部115d从第1函数部113d接收验证值a，从加密部114d接收第1加密文c1，生成验证值a和第1加密文c1的函数值H(a、c1)，并将函数值H(a、c1)输出给随机数屏蔽部116d(步骤S206)。

其次，随机数屏蔽部116d从随机数生成部112d接收随机数s，从第2函数部115d接收函数值H(a、c1)，随机数屏蔽部116d生成第2加密文c2＝s xor H(a、c1)，并将第2加密文c2输出给第1发送部117d(步骤S207)。

其次，第1发送部117d从加密部114d接收第1加密文c1，从随机数屏蔽部116d接收第2加密文c2，经因特网130将第1加密文c1和第2加密文c2送往解密装置120d(步骤S208)。

其次，公共密钥加密部118从内容服务装置140接收多个明码文mi(1≤i≤n)，从第1函数部113d接收共享密钥K，使用共享密钥K对明码文mi(1≤i≤n)执行共享密钥加密算法Sym，生成共享密钥加密文Ci＝Sym(mi、K)(1≤i≤n)，并将公共密钥加密文Ci(1≤i≤n)输出给第2发送装置119(步骤S209)。

其次，第2发送部119从公共密钥加密部118接收公共密钥加密文Ci(1≤i≤n)，经因特网130发送给解密装置120d(步骤S210)，并结束处理。

另一方面，秘密密钥输入部121d从存储卡170接收解密装置120d的秘密密钥多项式f，将秘密密钥多项式f输出给解密部123(步骤S251)。

其次，第1接收部122d经因特网130从加密装置110d接收第1加密文c1和第2加密文c2，将第1加密文c1输出给解密部123d和第3函数部124d，将接收的第2加密文c2输出给随机数屏蔽除去部125d(步骤S208)。

其次，解密部123d从秘密密钥输入部121接收秘密密钥多项式f，从第1接收部122d接收第1加密文c1，其次，使用秘密密钥多项式f，对第1加密文c1进行解密，生成解密验证值a’，并将解密验证值a’输出给第3函数部124d和比较部127d(步骤S 252)。

其次，第3函数部124d从第1接收部122d接收第1加密文c1，从解密部123d接收解密验证值a’，其次，和第2函数部115d一样，生成验证值a’和第1加密文c1的函数值H(a’、c1)，并将函数值H(a’、c1)输出给随机数屏蔽除去部125d(步骤S253)。

其次，随机数屏蔽除去部125d从第1接收部122d接收第2加密文c2，从第3函数部124d接收散列函数值H(a’、c1)，其次，生成解密随机数s’＝c2 xor H(a’、c1)，并将解密随机数s’输出给第4函数部126d(步骤S254)。

其次，第4函数部126d从随机数屏蔽除去部125接收解密随机数s’，生成解密随机数s’的散列函数值G(s’)(步骤S255)，和第1函数部113d同样，根据函数值G(s’)生成验证值a”和共享密钥K’，将验证值a”和共享密钥K’输出给比较部127d(步骤S256)。

其次，比较部127d从解密部123接收解密验证值a’，从第4函数部126d接收验证值a”和共享密钥K’，检验解密验证值a’和验证值a”是否相等，若不等(步骤S257)，则结束处理。

若解密验证值a’和验证值a”相等(步骤S257)，则比较部127d将共享密钥K’输出给公共密钥解密部128(步骤S258)

其次，第2接收部129经因特网130从加密装置110接收加密文Ci(1≤i≤n)，并输出给公共密钥解密部128(步骤S210)，

其次，公共密钥解密部128从比较部127d接收共享密钥K’，从第2接收部129接收公共密钥加密文Ci(1≤i≤n)，使用共享密钥K’对公共密钥加密文Ci(1≤i≤n)执行公共密钥加密算法Sym，生成解密文mi’＝Sym(Ci、K)(1≤i≤n)，并将解密文mi’(1≤i≤n)向外部输出(步骤S259)，再结束处理。

4.5内容分配系统10d的动作验证

下面，说明内容分配系统10d的全部动作。

加密装置110d接收解密装置120d的公开密钥多项式h，生成随机数s，并根据函数值G(s)导出验证值a和共享密钥K。其次，加密装置110d使用公开密钥多项式h，并用NTRU密码对验证值a进行加密，生成第1加密文c1，并根据验证值a和第1加密文c1生成函数值H(a、c1)，根据随机数s和函数值H(a、c1)生成第2加密文c2＝s xor(a、c1)。其次，加密装置110d经因特网130将第1加密文c1和第2加密文c2发送给解密装置120d。

即，该加密装置110d进行以下处理，将加密文C＝(c1、c2)发送给解密装置120d。

.生成随机数s。

.生成G(s)，根据G(s)生成a、K。

.使用公开密钥多项式h生成验证值a的第1加密文c1。

.生成c2＝s xor H(a、c1)。

.输出共享密钥K和加密文C＝(c1、c2)。

其次，加密装置110d使用导出的共享密钥K，利用公共密钥密码方式对从内容服务装置140输入的明码文mi(1≤i≤n)进行加密，生成加密文Ci(1≤i≤n)，并经因特网130发送给解密装置120d。

另一方面，解密装置120d输入解密装置120d的秘密密钥多项式f，经因特网130从加密装置110d接收第1加密文c1和第2加密文c2，使用秘密密钥多项式f对第1加密文c1进行解密，生成解密验证值a’。根据解密验证值a’和第1加密文c1生成函数值H(a’、c1)，根据第2加密文c2和函数值H(a’、c1)生成解密随机数s’＝c2 xor(a’、c1)。其次，解密装置120d根据解密随机数s’的函数值G(s’)导出验证值a”和共享密钥K’，若验证值a”＝a’，则输出共享密钥K’。

即，该解密装置120d进行以下处理，并导出共享密钥K’。

.使用秘密密钥多项式f对第1加密文c1进行解密，生成a’。

.生成s’＝c2 xor H(a’、c1)。

.生成G(s’)，根据G(s’)生成a”、K’。

.检查a”＝a’是否成立。若成立，则输出共享密钥K’。

这里，若在解密装置120d中使用与在加密装置110d中使用的公开密钥多项式h对应的正确的秘密密钥多项式f，则第1解密文c1被正确解密，解密验证值a’＝a，根据第2加密文c2和H(a’、c1)生成的解密随机数s’＝s。因此，从G(s’)导出的验证值a”＝a，共享密钥K’＝K。而且，因a”＝a成立，故解密装置120d可以导出和加密装置110d相同的共享密钥K。

其次，解密装置120d使用导出的共享密钥K’(＝K)，经因特网130从加密装置110d接收公共密钥加密文Ci(1≤i≤n)，并利用公共密码方式对接收的公共密钥加密文Ci(1≤i≤n)进行解密，生成解密文mi(1≤i≤n)，再输出给再生装置150。

这里，因公共密钥加密文生成时使用的加密密钥K和解密文生成时使用的加密密钥K’相同，故解密装置120d可以正确地得到解密文mi’＝mi(1≤i≤n)。

4.6实施形态3的效果

在现有的PSEC-KEM算法中，使用a*p、a*w作为散列函数H的输入，使用若不采用秘密密钥则难以从a*p计算出a*w的Diffie-Hellman问题，来最终导出共享密钥K，这时，若不知道秘密密钥，则不能导出共享密钥K。因此，以NTRU密码为首的不利用Diffie-Hellman问题的其他公开密钥密码没有与Diffie-Hellman问题的a*p、a*w相当的密码，所以，存在不能使用PSEC-KEM算法的问题。

但是，在本发明的内容分配系统、加密装置及解密装置中，因将散列函数H的输入作为验证值a及其加密文c1，故可以使用PSEC-KEM算法，且可以利用NTRU密码或其他的公开密钥密码。

再有，在NTRU密码中，即使使用公开密钥对明码文进行加密生成加密文，使用正规的秘密密钥对加密文进行解密生成解密文，也会发生解密文和原来的明码文不同的情况(例如，参照非专利文献2)。若发生这样的解密错误，则解密装置得到错误的解密验证值a’，但是，因从G(s’)得到的验证值a”和a’不相等，故不输出共享密钥K’。因此，即使发生解密错误，也可以防止加密装置和解密装置之间共用错误的密钥。

此外，在解密装置中，因不进行生成再加密文的处理，故与现有技术相比，可以减小运算量。

由此，可以使用NTRU密码构成密钥密封机制，使用NTRU密码在加密装置和解密装置之间进行密钥配送。

此外，本发明的方式可以利用和非专利文献3记载的证明方法同样的方法，从理论上证明其安全性。

4.7变形例

上述说明的实施形态是实施本发明的一个例子，本发明不限于该实施形态，在不脱离其主旨的范围内可以实施各种各样的形态。本发明还包括以下情况。

(1)使用的NTRU密码的参数不限于N＝167，参数N也可以取其他的值。

(2)加密部114d、第2函数部115d、解密部123d及第3函数部124d进行的位列和多项式的变换方法并不限于该方法，也可以是其他变换方法。

例如，可以使用使位列和多项式一一对应的函数或函数值的表进行变换。

此外，例如，也可以使用实施形态2的变形例(1)中描述的变换方法进行变换。

(3)加密部114d和解密部123d使用的公开密钥密码方式若是能在加密部114d中，使用公开密钥对验证值a进行加密后再生成第1加密文c1，在解密部123d中，使用秘密密钥对第1加密文c1进行解密，再生成和验证值a相等的解密验证值a’即可。

因此，加密部114d和解密部123d使用的公开密钥密码除了NTRU密码之外，也可以使用任何公开密钥密码。

例如，若采用RSA密码，可以将h、f分别作为RSA密码的公开密钥和秘密密钥，在加密部114d中，使用h加密a并生成c1，在解密部123d中，使用f解密c1并生成a’。

此外，例如，若采用E1Gamal密码，可以将h、f分别作为E1Gamal密码的公开密钥、秘密密钥，在加密部114d中，生成随机数r，使用h和r加密a生成c1，在解密部123d中，使用f对c1进行解密再生成a’。

再有，关于RSA密码和E1Gamal密码，因非专利文献1有详细记载，故这里省略其说明。

(4)第1函数部113d除了将函数值G(s)的高位k位作为验证值a之外，只要是从函数值G(s)导出验证值a和共享密钥K，也可以采用其他方法。

(5)第2函数部115d只要是从验证值a和第1加密文c1导出函数值H(a、c1)，也可以采用其他生成方法。

例如，对任意的2项运算#，也可以将a#c1输入函数H来导出函数值。再有，在NTRU密码中，因第1加密文c1是多项式，故也可以从第1加密文c1变换出第1加密文位列c1’，将a#c1’输入到函数H来导出函数值。

(6)进而，第2函数部115d只要是使用验证值a导出函数值，也可以采用其他方法。

例如，第2函数部115d可以输出H(a)，也可以直接原样输出验证值a。即，在加密装置110d中，可以将第2加密文c2作为

.c2＝s xor H(a)或

.c2＝s xor a导出。

这时，解密装置120d的第3函数部124d分别输出

.H(a’)或

.a’。

(7)若随机数屏蔽部116d能从随机数s和函数值H(a、c1)导出第2加密文c2，随机数屏蔽除去部125d能从第2加密文c2和函数值H(a、c1)导出随机数s，则也可以采用其他方法。

例如，随机数屏蔽部116d也可以将第2加密文c2作为

.c2＝s+H(a、c1)或

.c2＝s·H(a、c1)导出。

5.实施形态4

说明作为本发明的又另1个实施形态的内容分配系统10e(未图示)。

内容分配系统10e是在实施形态3所示的内容分配系统10d的基础上对其进行变形的系统，和内容分配系统10d的不同点在于：加密装置根据函数值G(s)，除验证值a和共享密钥K之外进而还生成随机数值u；使用随机数值u加密验证值a生成第1加密文c1。在解密装置输出共享密钥K时的判断方法这一点上也和内容分配装置10d不同。

这里，以和内容分配系统10d不同点为中心详细说明内容分配系统10e。

5.1内容分配系统10e的构成

内容分配系统10e具有和内容分配系统10d同样的构成，取代加密装置110d和解密装置120d，而包含加密装置110e和解密装置120e。其他的构成因和内容分配系统10D一样，故省略其说明。

内容分配系统10e是使用NTRU进行密钥配送的系统。加密装置110e和解密装置120e经因特网130而连接。

5.2加密装置110e的构成

加密装置110e如图17所示，由公开密钥输入部111d、随机数生成部112d、第1函数部113e、加密部114e、第2函数部115d、随机数屏蔽部116d、第1发送部117d、公共密钥加密部118和第2发送部119构成。

公开密钥输入部111d、随机数生成部112d、第2函数部115d、随机数屏蔽部116d、第1发送部117d、公共密钥加密部118和第2发送部119因和构成加密装置110的构成要素相同，故省略说明，这里，只说明和构成加密装置110d的构成要素不同的第1函数部113e和加密部114e的构成及动作。

(1)第1函数部113e

第1函数部113e从随机数生成部112d接收随机数s，生成接收的随机数s的函数值G(s)。其次，如下面所示那样，根据生成的函数值G(s)生成验证值a、共享密钥K和随机数值u。

这里，函数G是输出长度为3k位的散列函数，第1函数部113e将函数值G(s)的高位k位作为验证值a，将函数值G(s)的中间的k位作为共享密钥K，将函数值G(s)的低位k位作为随机数值u。

其次，第1函数部113e向加密部114e和第2函数部115d输出已生成的验证值a，将生成的共享密钥K向公共密钥加密部118输出，将生成的随机数值u向加密部114e输出。

(2)加密部114e

加密部114e从公开密钥输入部111d接收公开密钥多项式h，从第1函数部113e接收验证值a和随机数值u。其次，如下面所示，使用公开密钥多项式h和随机数值u生成验证值a的第1加密文c1。这里，第1加密文c1是NTRU密码的加密文。随机数值u是盲值，用于使作为加密对象的验证值a不明了。

加密部114e生成由随机数值u唯一求出的随机数多项式r，该随机数多项式r对于NTRU密码的参数d，其d个项的各系数是‘1’，其余d个项的各系数是‘-1’，剩下的项的各系数是‘0’。

具体地说，将随机数值u作为模拟随机数系列的初始值(随机数种子)来设定，从{0、1、......N-1}中选择2d个不重复的模拟随机数，设由最初的d个模拟随机数表示的次方项的系数为‘1’，由剩下的d个模拟随机数分别表示的次方项的系数为‘-1’，其余项的系数为‘0’，由此来生成随机数多项式r。

其次，加密部114e和加密部114d一样，使用随机数多项式r生成第1加密文c1＝E(ap、r、h)。

其次，加密部114e将生成的第1加密文c1输出给第2函数部115d和第1发送部117d。

5.3解密装置120e的构成

解密装置120e如图18所示，由秘密密钥输入部121e、解密部123e、第3函数部124d、随机数屏蔽除去部125d、第4函数部126e、比较部127e、公共密钥解密部128和第2接收部129构成。

这里，因第3函数部124d、随机数屏蔽除去部125d、公共密钥解密部128和第2接收部129与解密装置120d包含的各构成要素相同，故省略说明，说明与解密装置120d包含的各构成要素不同的秘密密钥输入部121e、解密部123e、第4函数部126e和比较部127e的构成及动作。

(1)秘密密钥输入部121e

秘密密钥输入部121e从存储卡170接收解密装置120e的秘密密钥多项式f和公开密钥多项式h，将秘密密钥多项式f输出给解密部123e，将公开密钥多项式h输出给比较部127e。

(2)解密部123e

解密部123e从秘密密钥输入部121e接收秘密密钥多项式f，从第1接收部122d接收第1加密文c1，其次，使用秘密密钥多项式f，对第1加密文c1进行解密，生成解密验证值a’，并将生成的解密验证值a’输出给第3函数部124d，向比较部127e输出接收的第1加密文c1。

(3)第4函数部126e

第4函数部126e具有和第1函数部113e所具有的函数相同的函数G的算法。

第4函数部126e从随机数屏蔽除去部125d接收解密随机数s’，生成接收的解密随机数s’的散列函数值G(s’)。其次，和第1函数部113e同样，根据函数值G(s’)生成验证值a”、共享密钥K’和随机数值u’，将生成的验证值a”、共享密钥K’和随机数值u’输出给比较部127e。

(4)比较部127e

比较部127e如图18所示，由比较运算部127p和加密部127q构成。

加密部127q从秘密密钥输入部121e接收公开密钥多项式h，从第4函数部126e接收验证值a”和随机数值u’。其次，和加密部114d一样，使用接收的公开密钥多项式h和随机数值u’，对接收的验证值a”进行加密，生成第1再加密文c1’，将生成的第1再加密文c1’输出给比较运算部127p。

比较运算部127p从解密部123b接收第1加密文c1，从加密部127q接收第1再加密文c1’。其次，将接收的第1加密文c1和第1再加密文c1’比较，判断是否c1’＝c1。若c1’＝c1，则将接收的共享密钥K’输出给公共密钥解密部128，若不是c1’＝c1，则不输出接收的共享密钥K’。

5.4内容分配系统10e的动作验证

下面，使用图19所示的处理系统图说明内容分配系统10e的全部动作。

加密装置110e接收解密装置120e的公开密钥多项式h(步骤S201)，生成随机数s(步骤S202)，生成函数值G(s)(步骤S203)，根据函数值G(s)导出验证值a、共享密钥K和随机数值u(步骤S204)。其次，加密装置110e使用公开密钥多项式h和随机数值u，并用NTRU密码对验证值a进行加密，生成第1加密文c1(步骤S205)，并根据验证值a和第1加密文c1生成函数值H(a、c1)(步骤S206)，根据随机数s和函数值H(a、c1)生成第2加密文c2＝sxor H(a、c1)(步骤S207)。其次，加密装置110b经因特网130将第1加密文c1和第2加密文c2发送给解密装置120e(步骤S208)。

即，该加密装置110e进行以下处理(a)～(e)，将加密文C＝(c1、c2)发送给解密装置120e。

(a)生成随机数s。

(b)生成G(s)，根据G(s)生成a、K、u。

(c)使用公开密钥多项式h和随机数值u生成验证值a的第1加密文c1。

(d)生成c2＝s xor H(a、c1)a。

其次，加密装置110e使用导出的共享密钥K，利用公共密钥密码对从内容服务装置140输入的明码文mi(1≤i≤n)进行加密，生成加密文Ci(1≤i≤n)(步骤S209)，并经因特网130发送给解密装置120e(步骤S210)。

另一方面，解密装置120e接收解密装置120e的秘密密钥多项式f和公开密钥多项式h(步骤S251、步骤251e)，经因特网130从加密装置110e接收第1加密文c1和第2加密文c2(步骤S208)，使用秘密密钥多项式f对第1加密文c1进行解密，生成解密验证值a’(步骤S252)。其次，根据解密验证值a’和第1加密文c1生成函数值H(a’、c1)(步骤S253)，根据第2加密文c2和函数值H(a’、c1)生成解密随机数s’＝c2 xor H(a’、c1)(步骤S254)。其次，解密装置120e解密随机数s’的函数值G(s’)(步骤S255)，根据生成的函数值G(s’)导出验证值a”、随机数值u’和共享密钥K’(步骤S256e)。其次，对验证值a”进行加密，生成第1再加密文c1’(步骤S261)，若c1’＝c1(步骤S257)，则输出共享密钥K’(步骤S258)。

即，该解密装置120e进行以下处理(a)～(e)，并导出共享密钥K’。

(a)使用秘密密钥多项式f对第1加密文c1进行解密，生成a’。

(b)生成s’＝c2 xor H(a’、c1)。

(c)生成G(s’)，根据G(s’)生成a”、u’、K’。

(d)使用公开密钥多项式h和随机数值u’生成a”的第1再加密文c1’。

(e)检查c1’＝c1是否成立，若成立，则输出共享密钥K’。

这里，若在解密装置120e中使用与在加密装置110e中使用的公开密钥多项式h对应的正确的秘密密钥多项式f，则第1解密文c1被正确解密，解密验证值a’＝a，根据第2加密文c2和H(a’、c1)生成的解密随机数s’＝s。因此，从G(s’)导出的验证值a”＝a，共享密钥K’＝K成立，随机数值u’＝u。这样，因a”＝a和u’＝u成立，故c1’＝c1成立，解密装置120e可以导出和加密装置110e相同的共享密钥K。

其次，解密装置120e经因特网130从加密装置110e接收公共密钥加密文Ci(1≤i≤n)(步骤S210)，利用公共密钥密码对接收的公共密钥加密文Ci(1≤i≤n)进行解密，生成解密文mi’(1≤i≤n)(步骤S259)，再将解密文mi’(1≤i≤n)输出给再生装置150。

这里，因公共密钥加密文生成时使用的加密密钥K和解密文生成时使用的加密密钥K’相同，故解密装置120e可以正确地得到mi’＝mi(1≤i≤n)。

5.5内容分配系统10e的效果

在现有的PSEC-KEM算法中，使用a*p、a*w作为散列函数H的输入，使用若不采用秘密密钥则难以从a*p计算出a*w的Diffie-Hellman问题，来最终导出共享密钥K，这时，若不知道秘密密钥则不能导出该共享密钥K。因此，以NTRU密码为首的不利用Diffie-Hellman问题的其他公开密钥密码没有与Diffie-Hellman问题的a*p、a*w相当的密码，所以，存在不能使用PSEC-KEM算法的问题。

但是，在本发明的内容分配系统、加密装置及解密装置中，因将散列函数H的输入作为验证值a及其加密文c1，故和实施形态3一样，可以利用NTRU密码或其他的公开密钥密码。

再有，若发生解密错误，解密装置得到错误的解密验证值a’，但是，因c1’不等于c1，故不输出共享密钥K’。因此，即使发生解密错误，也可以防止加密装置和解密装置之间共用错误的密钥。

由此，可以使用NTRU密码构成密钥密封机制，使用NTRU密码在加密装置和解密装置之间进行密钥配送。

此外，本发明的方式可以利用和非专利文献3记载的证明方法同样的方法，从理论上证明其安全性。

5.6变形例

上述说明的实施形态是实施本发明的一个例子，本发明不限于该实施形态，在不脱离其主旨的范围内可以实施各种各样的形态。当然可以实施和实施形态3同样的变形例，本发明还包括以下情况。

(1)在加密部114e中进行的从随机数值u到随机数多项式r的变换不限于本方法，若是从u唯一地求得r，则也可以使用其他变换方法，例如，可以使用使随机数值u与多项式对应的函数或函数值表进行变换。

此外，例如，也可以使用在实施形态2的变形例(1)中记述的变换方法来进行变换。

(2)加密部114e和解密部123e使用的公开密钥密码若是能在加密部114e中，使用公开密钥和随机数值u对验证值a进行加密再生成第1加密文c1，在解密部123e中，使用秘密密钥对第1加密文c1进行解密，再生成和验证值a相等的解密验证值a’即可。因此，加密部114e和解密部123e使用的公开密钥密码除了NTRU密码之外，只要是使用随机数的公开密钥密码，任何密码都可以利用。

例如，若采用E1Gamal密码，可以将h、f分别作为E1Gamal密码的公开密钥、秘密密钥，在加密部114e中，使用h和随机数值u对a进行加密再生成c1，在解密部123e中，使用f对c1进行解密再生成a’。

(3)随机数值u除了用第1函数部113e和第4函数部126e生成之外，只要在加密装置110e和解密装置120e中能得到相同的值，也可以采用其他生成方法。

例如，也可以对任意函数Func，作为u＝Func(s)，在加密装置110e和解密装置120e中能得到相同的值。即，.生成G(s)，根据G(s)生成a、K。

.生成Func(s)，使u＝Func(s)。

(4)进而，随机数值u除了用第1函数部113e和第4函数部126e生成之外，困只要在加密装置110e和解密装置120e中能得到相同的值即可，故加密装置110e也可以向解密装置120e直接发送随机数值u。

即，也可以像以下那样，将加密文C和随机数值u发送给解密装置120e。

.生成G(s)，根据G(s)生成a、K。

.通过别的渠道，从加密装置110e向解密装置120e发送随机数值u。

此外，加密装置110e也可以将随机数值u加密后再发送。

(5)进而，随机数值u因只要加密装置110e和解密装置120e能得到相同的值即可，故也可以使用第1函数部113e和第4函数部126e生成由随机数值u的一部分构成的部分信息，随机数值u的剩下的部分信息直接从加密装置110e向解密装置120e发送。

例如，如下所述，也可以将加密文C和随机数值u2发送给解密装置120e。

.生成G(s)，根据G(s)生成a、K、u1。

.通过别的渠道，从加密装置110e向解密装置120e发送随机数值u2。

.利用u＝u1 xor u2生成随机数值u。

此外，加密装置110e也可以将随机数值u2加密后再发送。

(6)解密装置120e检验第1加密文c1是不是由第4函数部126e得到的验证值a”的加密文，当c1是a”的加密文时，使用共享密钥K’对公共密钥加密文Ci进行解密，但也可以利用和实施形态3的解密装置120d相同的检验方法进行。

即，如图20的处理系统所示，也可以和解密装置120d一样，使用解密部123d和比较部127d，像以下那样进行检验。

(a)使用秘密密钥多项式f对第1加密文c1进行加密，再生成a’(步骤S252)。

(b)生成s’＝c2 xor H(a’、c1)(步骤S254)。

(c)生成G(s’)(步骤S255)，根据G(s’)生成a”、K’、u’(步骤S256e)。

(d)检验a”＝a是否成立(步骤S257)，若成立则输出共享密钥K’(步骤S258)

此外，也可以检验第1加密文c1是不是解密验证值a’的加密文。

7.实施形态3和实施形态4的总结

如以上说明的那样，本发明是输出共享密钥数据和根据预先给出的共享密钥数据将上述共享密钥数据加密后的加密共享密钥数据的共享密钥生成装置，包括：生成秘密数数据的秘密数数据生成部；按照规定的处理将上述秘密数数据变换成验证值数据和上述共享密钥数据的共享密钥导出部；根据上述公开密钥数据将上述验证值数据加密后生成第1加密预备数据的第1加密部；按照规定的处理将上述验证值数据变换成变换验证值数据的验证值变换部；根据上述变换验证值数据将上述秘密数数据加密后生成第2加密预备数据的第2加密部，上述加密共享密钥数据由上述第1加密预备数据和第2加密预备数据构成。

此外，本发明是输出共享密钥数据和根据预先给出的公开密钥数据将上述共享密钥数据加密后的加密共享密钥数据的共享密钥生成装置，包括：生成秘密数数据的秘密数数据生成部；按照规定的处理将上述秘密数数据和上述第1加密预备数据变换成验证值数据和上述共享密钥数据的共享密钥导出部；根据上述公开密钥数据将上述验证值数据加密后生成第1加密预备数据的第1加密部；按照规定的处理将上述验证值数据变换成变换验证值数据的验证值变换部；根据上述变换验证值数据将上述秘密数数据加密后生成第2加密预备数据的第2加密部，上述加密共享密钥数据由上述第1加密预备数据和第2加密预备数据构成。

此外，本发明是输出共享密钥数据和根据预先给出的公开密钥数据将上述共享密钥数据加密后的加密共享密钥数据的共享密钥生成装置，包括：生成秘密数数据的秘密数数据生成部；按照规定的处理将上述秘密数数据变换成验证值数据、随机数数据和上述共享密钥数据的共享密钥导出部；根据上述公开密钥数据和上述随机数数据将上述验证值数据加密后生成第1加密预备数据的第1加密部；按照规定的处理将上述验证值数据变换成变换验证值数据的验证值变换部；根据上述变换验证值数据将上述秘密数数据加密后生成第2加密预备数据的第2加密部，上述加密共享密钥数据由上述第1加密预备数据和第2加密预备数据构成。

此外，本发明是输出共享密钥数据和根据预先给出的公开密钥数据将上述共享密钥数据加密后的加密共享密钥数据的共享密钥生成装置，包括：生成秘密数数据的秘密数数据生成部；按照规定的处理将上述秘密数数据变换成验证值数据、随机数数据和上述共享密钥数据的共享密钥导出部；根据上述公开密钥数据和上述随机数数据将上述验证值数据加密后生成第1加密预备数据的第1加密部；按照规定的处理将上述验证值数据和上述第1加密预备数据变换成变换验证值数据的验证值变换部；根据上述变换验证值数据将上述秘密数数据加密后生成第2加密预备数据的第2加密部，上述加密共享密钥数据由上述第1加密预备数据和第2加密预备数据构成。

这里，上述秘密数数据可以是随机生成的随机数。

这里，作为规定的处理，上述共享密钥导出部可以使用单向散列函数。

这里，上述第1加密部可以利用NTRU加密方式加密后生成上述第1加密预备数据。

这里，作为规定的处理，上述验证值变换部可以使用单向散列函数。

这里，上述第2加密部可以进行上述秘密数数据和上述验证值数据的“异”运算再生成上述第2加密预备数据。

这里，上述第2加密部可以将上述变换验证值数据作为加密密钥使用，并利用公共密钥加密方式将上述秘密数数据加密后生成上述第2加密预备数据。

这里，上述第2加密部可以使上述变换验证值数据和上述秘密数数据相加后再生成上述第2加密预备数据。

这里，上述第2加密部可以使上述验证值数据和上述秘密数数据相乘后再生成上述第2加密预备数据。

这里，上述加密共享密钥数据可以是上述第1加密预备数据和上述第2加密预备数据的位连接数据。

此外，本发明是根据预先给出的秘密密钥数据将由第1加密预备数据和第2加密预备数据构成的加密共享密钥数据解密后输出共享密钥数据的共享密钥复原装置，包括：根据上述秘密密钥数据解密上述第1加密预备数据后再生成验证值数据的第1解密部；按照规定的处理将上述验证值数据变换成变换验证值数据的验证值变换部；根据上述变换验证值数据将上述第2加密预备数据解密后生成秘密数数据的第2解密部，按照规定的处理将上述秘密数数据变换成上述共享密钥数据的共享密钥导出部，当上述验证值数据和上述验证值验证数据一致时，输出上述共享密钥数据。

此外，本发明是根据预先给出的秘密密钥数据将由第1加密预备数据和第2加密预备数据构成的加密共享密钥数据解密后输出共享密钥数据的共享密钥复原装置，包括：根据上述秘密密钥数据解密上述第1加密预备数据再生成验证值数据的第1解密部；按照规定的处理将上述验证值数据和上述第1加密预备数据变换成变换验证值数据的验证值变换部；根据上述变换验证值数据将上述第2加密预备数据解密后生成秘密数数据的第2解密部；按照规定的处理将上述秘密数数据变换成上述共享密钥数据的共享密钥导出部，当上述验证值数据和上述验证值验证数据一致时，输出上述共享密钥数据。

此外，本发明是根据预先给出的秘密密钥数据将由第1加密预备数据和第2加密预备数据构成的加密共享密钥数据解密后输出共享密钥数据的共享密钥复原装置，包括：根据上述秘密密钥数据解密上述第1加密预备数据后再生成验证值数据的第1解密部；按照规定的处理将上述验证值数据变换成变换验证值数据的验证值变换部；根据上述变换验证值数据将上述第2加密预备数据解密后生成秘密数数据的第2解密部；按照规定的处理将上述秘密数数据变换成验证值验证数据、随机数数据和上述共享密钥数据的共享密钥导出部，当上述验证值数据和上述验证值验证数据一致时，输出上述共享密钥数据。

此外，本发明是根据预先给出的秘密密钥数据将由第1加密预备数据和第2加密预备数据构成的加密共享密钥数据解密后输出共享密钥数据的共享密钥复原装置，包括：根据上述秘密密钥数据解密上述第1加密预备数据后再生成验证值数据的第1解密部；按照规定的处理将上述验证值数据变换成变换验证值数据的验证值变换部；根据上述变换验证值数据将上述第2加密预备数据解密后生成秘密数数据的第2解密部；按照规定的处理将上述秘密数数据变换成验证值验证数据、随机数数据和上述共享密钥数据的共享密钥导出部，当上述验证值数据和上述验证值验证数据一致时，输出上述共享密钥数据。

此外，本发明是根据预先给出的秘密密钥数据和公开密钥数据将由第1加密预备数据和第2加密预备数据构成的加密共享密钥数据解密后输出共享密钥数据的共享密钥复原装置，包括：根据上述秘密密钥数据解密上述第1加密预备数据后再生成验证值数据的第1解密部；按照规定的处理将上述验证值数据和上述第1加密预备数据变换成变换验证值数据的验证值变换部；根据上述变换验证值数据将上述第2加密预备数据解密后生成秘密数数据的第2解密部；按照规定的处理将上述秘密数数据变换成验证值验证数据、随机数数据和上述共享密钥数据的共享密钥导出部，根据上述公开密钥数据和上述随机数数据加密上述验证值验证数据后生成第3加密预备数据的第3加密部，当上述第1加密预备数据和上述第3加密预备数据一致时，输出上述共享密钥数据。

此外，本发明是根据预先给出的秘密密钥数据和公开密钥数据将由第1加密预备数据和第2加密预备数据构成的加密共享密钥数据解密后输出共享密钥数据的共享密钥复原装置，包括：根据上述秘密密钥数据解密上述第1加密预备数据后再生成验证值数据的第1解密部；按照规定的处理将上述验证值数据变换成变换验证值数据的验证值变换部；根据上述变换验证值数据将上述第2加密预备数据解密后生成秘密数数据的第2解密部；按照规定的处理将上述秘密数数据变换成验证值验证数据、随机数数据和上述共享密钥数据的共享密钥导出部，根据上述公开密钥数据和上述随机数数据加密上述验证值数据后生成第3加密预备数据的第3加密部，当上述第1加密预备数据和上述第3加密预备数据一致时，输出上述共享密钥数据。

此外，本发明是根据预先给出的秘密密钥数据和公开密钥数据将由第1加密预备数据和第2加密预备数据构成的加密共享密钥数据解密后输出共享密钥数据的共享密钥复原装置，包括：根据上述秘密密钥数据解密上述第1加密预备数据后再生成验证值数据的第1解密部；按照规定的处理将上述验证值数据和上述第1加密预备数据变换成变换验证值数据的验证值变换部；根据上述变换验证值数据将上述第2加密预备数据解密后生成秘密数数据的第2解密部；按照规定的处理将上述秘密数数据变换成验证值验证数据、随机数数据和上述共享密钥数据的共享密钥导出部，根据上述公开密钥数据和上述随机数数据加密上述验证值验证数据后生成第3加密预备数据的第3加密部，当上述第1加密预备数据和上述第3加密预备数据一致时，输出上述共享密钥数据。

此外，本发明是根据预先给出的秘密密钥数据和公开密钥数据将由第1加密预备数据和第2加密预备数据构成的加密共享密钥数据解密后输出共享密钥数据的共享密钥复原装置，包括：根据上述秘密密钥数据解密上述第1加密预备数据后再生成验证值数据的第1解密部；按照规定的处理将上述验证值数据和上述第1加密预备数据变换成变换验证值数据的验证值变换部；根据上述变换验证值数据将上述第2加密预备数据解密后生成秘密数数据的第2解密部，按照规定的处理将上述秘密数数据变换成验证值验证数据、随机数数据和上述共享密钥数据的共享密钥导出部；根据上述公开密钥数据和上述随机数数据加密上述验证值数据后生成第3加密预备数据的第3加密部，当上述第1加密预备数据和上述第3加密预备数据一致时，输出上述共享密钥数据。

这里，作为规定的处理，上述共享密钥导出部可以使用单向散列函数。

这里，上述第1解密部可以利用NTRU密码方式解密后再生成验证值数据。

这里，作为规定的处理，上述验证值变换部可以使用单向散列函数。

这里，作为规定的处理，上述验证值变换部可以直接将上述验证值数据原样作为上述变换验证值数据。

这里，上述第2解密部可以进行上述第2加密预备数据和上述验证值数据的“异”运算后再生成上述秘密数数据。

这里，上述第2解密部可以使用上述变换验证值数据作为加密密钥，并利用共享密钥加密方式将上述第2加密预备数据解密后生成上述秘密数数据。

这里，上述第2解密部可以使第2加密预备数据减去上述变换验证值数据后再生成上述秘密数数据。

这里，上述第2解密部可以采用上述第2加密预备数据除以上述变换验证值数据后再生成上述秘密数数据。

此外，本发明是根据预先给出的公开密钥数据生成将明码文数据加密了的加密文数据的加密装置，包括：生成秘密数数据的秘密数数据生成部；按照规定的处理将上述秘密数数据变换成验证值数据和共享密钥数据的共享密钥导出部；根据上述公开密钥数据加密上述验证值数据后再生成第1加密预备数据的第1加密部；按照规定的处理将上述验证值数据变换成变换验证值数据的验证值变换部；根据上述变换验证值数据将上述秘密数数据加密后生成第2加密预备数据的第2加密部；根据上述共享密钥数据加密上述明码文数据后生成第3加密预备数据的第3加密部，上述加密文数据由上述第1加密预备数据、上述第2加密预备数据和上述第3加密预备数据构成。

此外，本发明是根据预先给出的秘密密钥数据将由第1加密预备数据、第2加密预备数据和第3加密预备数据构成的加密文数据解密后输出解密文数据的解密装置，包括：根据上述秘密密钥数据将上述第1加密预备数据解密后生成验证值数据的第1解密部；按照规定的处理将上述验证值数据变换成变换验证值数据的验证值变换部；根据上述变换验证值数据将上述第2加密预备数据解密后生成秘密数数据的第2解密部；以及按照规定的处理将上述秘密数数据变换成验证值验证数据和共享密钥数据的共享密钥导出部，还包括解密部，当上述验证值数据和上述验证值验证数据一致时，根据上述共享密钥将上述第3加密预备数据解密后生成上述解密文数据。

此外，本发明是由根据预先给出的公开密钥数据生成将明码文数据加密后的加密文数据的加密装置和根据预先给出的秘密密钥数据将加密文数据解密后输出解密文数据的解密装置构成的密码系统。上述加密装置包括：生成秘密数数据的秘密数数据生成部；按照规定的处理将上述秘密数数据变换成验证值数据和共享密钥数据的共享密钥导出部；根据上述公开密钥数据将上述验证值数据加密后生成第1加密预备数据的第1加密部；按照规定的处理将上述验证值数据变换成变换验证值数据的验证值变换部；根据上述变换验证值数据将上述秘密数数据加密后生成第2加密预备数据的第2加密部；根据上述共享密钥数据加密上述明码文数据后生成第3加密预备数据的第3加密部，上述加密文数据由上述第1加密预备数据、上述第2加密预备数据和上述第3加密预备数据构成。上述解密装置包括：根据上述秘密密钥数据将上述第1加密预备数据解密后生成上述验证值数据的第1解密部；按照规定的处理将上述验证值数据变换成上述变换验证值数据的验证值变换部；根据上述变换验证值数据将上述第2加密预备数据解密后生成上述秘密数数据的第2解密部；以及按照规定的处理将上述秘密数数据变换成验证值验证数据和共享密钥数据的共享密钥导出部，还包括解密部，当上述验证值数据和上述验证值验证数据一致时，根据上述共享密钥数据将上述第3加密预备数据解密后生成上述解密文数据。

如以上所说明的那样，本发明是鉴于现有系统的问题而提出的，所以，在密码系统中，通过构成能使用NTRU密码的密钥密封机制，可以使用NTRU密码在加密装置和解密装置之间进行密钥配送。

如上所述，可以提供一种现有技术不能实现的密码系统，具有很大的价值。

8.其他变形例

虽然根据上述实施形态说明了本发明，但本发明不限于上述实施形态，以下情况也包含在本发明之内。

(1)加密装置可以不经因特网向解密装置发送各加密文，而向DVD等记录媒体写入各加密文，解密装置从记录媒体中读出各加密文。

(2)本发明使用的NTRU密码除了非专利文献2记载的方式之外，也可以是EESS(Efficient Embedded Security Standard：有效植入安全标准)方式的NTRU密码。关于EESS方式的NTRU密码，在“EESS；Consortium for Efficient Embedded Security，EfficientEmbedded Security Standards#1：Implementation Aspects of NTRUEncrypt and NTRU Sign，Version 2.0，”(available athttp：/ceesstandards.org，May2003)中有详细记载，因此，这里省略其详细说明，以下简单地进行说明。

在EESS方式的NTRU密码中，随机数多项式r是d个系数是1、(N-d)个系数是0的多项式，或是使用多个这样的多项式计算后得到的多项式。因此，在上述实施形态中，当生成随机数多项式r时，若生成这样的多项式，则可以使用EESS方式的密码去代替NTRU密码，可以得到同样的效果。

(3)内容分配系统也可以像下面所示那样构成。

内容分配系统由内容服务装置、加密装置、发送装置、接收装置、解密装置、再生装置和监视器构成。

加密装置和解密装置与内容分配系统10的加密装置110和解密装置120相对应。

内容服务器装置和加密装置经专用线路连接，内容服务器装置经专用线路将由图像和声音构成的电影等内容向加密装置发送。加密装置和发送装置经专用线路连接。加密装置向发送装置传送各加密文，发送装置将各加密文多路复用，并调制在数字广播电波上进行发送。

接收装置和解密装置连接，解密装置和再生装置连接。接收装置接收数字广播电波，从接收的数字广播电波中抽出各加密文，将抽出的各加密文传送给解密装置。解密装置接收各加密文，使用接收的各加密文生成再生内容，将生成的再生内容输出给再生装置。再生装置与内装有扬声器的监视器连接。再生装置接收再生内容，从接收的再生内容中生成图像信号和声音信号，监视器显示图像并输出声音。

(4)内容服务器装置和加密装置也可以由形成一体的装置构成。此外，解密装置和再生装置也可以由形成一体的装置构成。

(5)在上述各实施形态中，存储卡160预先存储公开密钥多项式，存储卡170预先存储秘密密钥多项式f和公开密钥多项式h，加密装置110和解密装置120分别从存储卡160和存储卡170取得公开密钥多项式和秘密密钥多项式，但不限于此。

也可以是加密装置110预先存储公开密钥多项式，解密装置120预先存储公开密钥多项式和秘密密钥多项式。

此外，密钥管理装置也可以生成秘密密钥多项式和公开密钥多项式，将秘密密钥多项式和公开密钥多项式秘密且安全地发送给解密装置120，并将生成的公开密钥多项式发送给加密装置110。

(6)内容分配系统分配的内容不限于由图像和声音构成的电影等内容。也可以是由活动图像、静止图像、声音、音乐、文书、小说和DB软件生成的数据库、由表格计算软件生成的电子表数据、计算机程序或其他计算机用数据等。

此外，上述内容也可以不是上述那样的著作物，而是使用于加密、解密、数字署名和署名验证等的密钥信息。

例如，也可以像上述各实施形态所示那样，加密装置和解密装置共用共享密钥，加密装置使用共享密钥加密内容密钥后生成加密内容密钥，使用内容密钥对内容加密后生成加密内容，并将生成的加密内容密钥和生成的加密内容发送给解密装置。解密装置接收加密内容密钥和加密内容，并使用共享密钥将加密内容密钥解密后生成内容密钥，使用生成的内容密钥将加密内容解密后生成内容。

(7)本发明可以是上面所示的方法。也可以是由计算机实现这些方法的计算机程序，也可以是由上述计算机程序构成的数字信号。

此外，本发明可以是将上述计算机程序或上述数字信号记录在计算机可读取的记录媒体、例如，软盘、硬盘、CD-ROM、MO、DVD、DVD-ROM、DVD-RAM、BD(Blu-ray盘)、半导体存储器等上的技术。此外，也可以是记录在这些记录媒体上的上述计算机程序或上述数字信号。

此外，本发明也可以是经由电气通信线路、无线或有线通信线路、以因特网为代表的网络、数字广播等传送上述计算机程序或上述数字信号的技术。

此外，本发明也可以是具有微处理器和存储器的计算机系统，上述存储器存储计算机程序，上述微处理器按照上述计算机程序动作。

此外，本发明也可以通过将上述程序和上述数字信号记录在上述记录媒体中后再进行移送，或者经由上述网络等移送上述程序或上述数字信号，从而由其他的独立计算机系统来实施。

(8)也可以将上述实施形态和上述变形例分别组合。

以上说明的内容分配系统在从内容供给者对使用者供给音乐、电影、小说等数字化著作物的行业中，可以经营性地、反复地继续使用。此外，构成内容分配系统的加密装置和解密装置在制造电气产品等电气行业中，可以进行制造和贩卖。

特别地，对通过将数字化著作物存储在DVD等记录媒体上后在市场上流通，或经网络流通，或通过广播来提供数字化产品的行业很适用。