素数计算装置和方法以及密钥发行系统

[19]中华人民共和国国家知识产权局[51]Int.Cl.

H04L9/08(2006.01)

GO9C1/00(2006.01)

[12]发明专利申请公布说明书

[21]申请号200480038935.3

[43]公开日2007年1月17日[11]公开号CN1898898A

[22]申请日2004.12.21[74]专利代理机构永新专利商标代理有限公司

[21]申请号200480038935.3代理人胡建新

[30]优先权

[32]2003.12.26[33]JP[31]433903/2003

[32]2003.12.26[33]JP[31]433904/2003

[32]2004.1.30[33]JP[31]023796/2004

[86]国际申请PCT/JP2004/0191082004.12.21

[87]国际公布W02005/064843日2005.7.14

[85]进入国家阶段日期2006.6.26

[71]申请人松下电器产业株式会社

地址日本大阪府

[72]发明人布田裕一大森基司

权利要求书8页说明书114页附图46页

[54]发明名称

素数计算装置和方法以及密钥发行系统

[57]摘要

提供一种素数计算装置，在算出素数时，通过

简单的管理，在避免重复的同时算出素数。素数计

算装置存储已知的素数q、和素数利用范围中的唯

一管理信息。素数计算装置读出管理信息，生成依

赖于读出的管理信息的搅乱信息R,并读出素数q,

使用读出的素数q和生成的搅乱信息R,通过公式

N=2X搅乱信息RX素数q+1,算出素数候补

N,并判定算出的素数候补N是否为素数，在判定

为是素数的情况下，将算出的素数候补N作为素数

进行输出。由此，素数计算装置可根据唯一的管理

信息，在避免重复的同时算出素数候补。

200480038935.3权利要求书第"8页

1、一种素数计算装置，算出比已知素数q大的素数候补N,进行素数判

定，其特征在于，具备：

素数存储单元，存储已知的素数q；

5管理信息存储单元，存储素数利用范围中的唯一管理信息；

搅乱信息生成单元，从所述管理信息存储单元中读出所述管理信息，生

成依赖于读出的所述管理信息的搅乱信息R;

候补计算单元，从所述素数存储单元中读出所述素数q,使用读出的所

述素数q和生成的所述搅乱信息R,通过N=2X搅乱信息RX素数q+1,算出素

10数候补N；

素数判定单元，判定算出的素数候补N是否为素数；和

输出单元，在判定为是素数的情况下，将算出的素数候补N作为素数进

行输出。

2、根据权利要求1所述的素数计算装置，其特征在于，

15所述搅乱信息生成单元包含：

读出部，从所述管理信息存储单元中读出所述管理信息；

随机数算出部，算出随机数r；

结合部，结合读出的所述管理信息和生成的随机数门和

运算部，根据所述管理信息和随机数r的结合体，算出搅乱信息R。

203、根据权利要求2所述的素数计算装置，其特征在于，

所述运算部对所述结合体实施单射函数，生成搅乱信息R。

4、根据权利要求3所述的素数计算装置，其特征在于，

所述单射函数是异或，

所述运算部预先存储规定的密钥信息，对所述密钥信息和所述结合体实

25施异或，生成搅乱信息R。

200480038935.3权利要求书第2/8页

5、根据权利要求3所述的素数计算装置，其特征在于，

所述素数计算装置算出具有素数q的2倍位长度的素数候补N,

所述随机数算出部算出位长度为从素数q的位长度中减去所述管理信息

的位长度和1的所述随机数人

56、根据权利要求5所述的素数计算装置，其特征在于，

所述素数判定单元包含：

第1判定部，对所述素数候补N判定是否满足2'T=1modN；和

第2判定部，在由所述第1判定部判定为满足的情况下，再对素数候补N

和搅乱信息R判定是否满足TRXlmodN,在判定为满足的情况下，确定素数

10候补N为素数。

7、根据权利要求5所述的素数计算装置，其特征在于，

所述素数判定单元包含：

第1判定部，对所述素数候补N判定是否满足2*三1modN；和

第2判定部，在由所述第1判定部判定为满足的情况下，再对素数候补N

15和搅乱信息R判定是否满足GCD（2叽1,N）=L在判定为满足的情况下，确定

素数候补N为素数。

8、根据权利要求1所述的素数计算装置，其特征在于，

所述素数计算装置还包含

重复控制单元，对所述搅乱信息生成单元、所述候补计算单元和所述素

20数判定单元进行控制，以重复搅乱信息R的生成、素数候补N的计算和所述判

定，直到由所述素数判定单元判定为是素数为止。

9、根据权利要求8所述的素数计算装置，其特征在于，

所述素数计算装置还包含：

次级随机数计算单元，算出随机数R':

25次级候补计算单元，使用输出的所述素数N和生成的所述随机数R',通

过M=2X随机数R，X素数N+1,算出素数候补N'；

200480038935.3权利要求书第3/8页

次级素数判定单元，判定算出的素数候补N'是否为素数；

次级输出单元，在判定为是素数的情况下，将算出的素数候补N'作为

素数进行输出；和

次级重复控制单元，对所述次级随机数计算单元、所述次级候补计算单

5元和所述次级素数判定单元进行控制，以重复随机数R'的生成、素数候补

N，的计算和所述判定，直到由所述次级素数判定单元判定为是素数为止。

10、根据权利要求8所述的素数计算装置，其特征在于，

所述素数计算装置还包含：

次级信息存储单元，存储规定的验证值；

10次级随机数生成单元，生成随机数r，；和

次级候补计算单元，对所述管理信息乘以生成的所述随机数r',算出

搅乱信息R',并通过『=2X搅乱信息R，X素数N+验证值，算出素数候补

N',

所述素数判定单元还判定算出的素数候补N'是否为素数，

15所述输出单元还在判定为素数候补M为素数的情况下，将算出的素数

候补N，作为素数进行输出。

11、根据权利要求8所述的素数计算装置，其特征在于，

所述素数计算装置是生成RSA加密的公钥和私钥的密钥生成装置，

所述素数计算装置还包含：

20公钥生成单元，使用算出的素数N,生成RSA加密的公钥；和

私钥生成单元，使用生成的公钥，生成RSA加密的私钥。

12、根据权利要求11所述的素数计算装置，其特征在于，

所述公钥生成单元对所述重复控制单元指示重新得到素数N',并使用

所述素数N和重新得到的素数V,通过n=素数NX素数N，,算出数n,生成

25随机数e,

算出的数n和生成的随机数e的组为所述公钥，

200480038935.3权利要求书第4/8页

所述私钥生成单元算出满足eXd=lmodL的d,

L是素数N-1和素数V-1的最小公倍数，

算出的d是所述私钥。

13、根据权利要求11所述的素数计算装置，其特征在于，

5所述素数计算装置是密钥发行服务器装置，对终端装置生成并发行RSA

的私钥和公钥，

所述素数计算装置还包含：

密钥输出单元，对终端装置输出生成的所述私钥；和

公开单元，公开生成的所述公钥。

io14、根据权利要求13所述的素数计算装置，其特征在于，

所述素数计算装置还包含：

标识符取得单元，取得唯一识别所述终端装置的终端装置标识符；

管理信息生成单元，生成包含取得的终端装置标识符的所述管理信息；

和

15写入单元，将生成的所述管理信息写入所述管理信息存储单元中。

15、根据权利要求14所述的素数计算装置，其特征在于，

所述素数计算装置还包含：

服务器标识符存储单元，预先存储唯一识别作为密钥发行服务器装置的

该素数计算装置的服务器标识符，

20所述管理信息生成单元还从所述服务器标识符存储单元中读出所述服

务器标识符，并生成还包含读出的服务器标识符的所述管理信息。

16、一种素数计算装置，算出比已知素数大的素数，其特征在于，具备：

素数计算单元，算出具有已知输入素数的2倍位长度的输出素数；

素数存储单元，存储已知的素数初始值；和

25重复控制单元，对所述素数计算单元进行控制，以重复多次计算，

所述重复控制单元在所述重复中的初次计算中，将存储在所述素数存储

200480038935.3权利要求书第5/8页

单元中的素数初始值作为所述输入素数，提供给所述素数计算单元，

在所述重复的初次计算以外的其它计算中，将前一次计算中的输出素数

作为该其它计算中的所述输入素数，提供给所述素数计算单元，

在所述多次算出的任一计算中，所述素数计算单元包含：

5管理信息保存部，存储素数利用范围中的唯一管理信息；

搅乱信息生成部，从所述管理信息保存部中读出所述管理信息，生成依

赖于读出的所述管理信息的搅乱信息R;

候补算出部，接收所述输入素数q，使用接受的所述输入素数q和生成的

所述搅乱信息R,通过N=2X搅乱信息RX素数q+1,算出素数候补N；

10素数判定部，判定算出的素数候补N是否为素数；

输出部，在判定为是素数的情况下，将算出的素数候补N作为输出素数

进行输出；和

重复控制部，对所述搅乱信息生成部、所述候补算出部和所述素数判定

部进行控制，以重复搅乱信息R的生成、素数候补N的计算与所述判定，直到

15由所述素数判定部判定为是素数为止。

17、根据权利要求16所述的素数计算装置，其特征在于，

在所述多次计算中的最终次计算中，所述素数计算单元包含：

信息保存部，存储规定的验证值；

随机数生成部，生成随机数r'：

20候补算出部，对所述管理信息乘以生成的所述随机数r',算出搅乱信

息R',并通过『二2X搅乱信息R，X前一次算出的输出素数+验证值，算出

素数候补M；

素数判定部，判定算出的素数候补V是否为素数；

输出部，在判定为素数候补N'为素数的情况下，将算出的素数候补V

25作为素数进行输出；和

重复控制部，对所述随机数生成部、所述候补算出部和所述素数判定部

200480038935.3权利要求书第6/8页

进行控制，以重复随机数婷的生成、素数候补N，的计算与所述判定，直到

由所述素数判定部判定为是素数为止。

18、一种密钥发行系统，包括对终端装置生成并发行RSA的私钥和公钥

的密钥发行服务器装置、和所述终端装置，其特征在于，

5密钥发行服务器装置具备：

素数计算单元，算出比已知素数q大的素数N；

公钥生成单元，使用算出的素数N,生成RSA加密的公钥；

私钥生成单元，使用生成的公钥，生成RSA加密的私钥；

密钥输出单元，对终端装置输出生成的所述私钥；和

io公开单元，公开生成的所述公钥，

所述素数计算单元包含：

素数保存部，存储已知的素数q；

管理信息保存部，存储唯一的管理信息；

搅乱信息生成部，从所述管理信息保存部中读出所述管理信息，生成依

15赖于读出的所述管理信息的搅乱信息R；

候补算出部，从所述素数保存部中读出所述素数q，使用读出的所述素

数q和生成的所述搅乱信息R,通过N=2X搅乱信息RX素数q+1,算出素数候

补N；

素数判定部，判定算出的素数候补N是否为素数；

20输出部，在判定为是素数的情况下，将算出的素数候补N作为素数进行

输出；和

重复控制部，对所述搅乱信息生成部、所述候补算出部和所述素数判定

部进行控制，以重复搅乱信息R的生成、素数候补N的计算和所述判定，直到

由所述素数判定部判定为是素数为止，

25所述终端装置具备：

接收单元，接收所述私钥；和

200480038935.3权利要求书第7/8页

密钥存储单元，存储接收到的私钥。

19、根据权利要求18所述的密钥发行系统，其特征在于，

所述密钥发行系统还包含证书发行服务器装置，

所述密钥输出单元向所述证书发行服务器装置输出所述公钥，

5所述证书发行服务器装置具备：

存储单元，存储该证书发行服务器装置的私钥；

取得单元，取得所述公钥；

证书生成单元，使用所述证书发行服务器装置的私钥，对包含所述公钥

的公钥信息实施数字签名，生成签名数据，并生成至少包含所述公钥和生成

10的所述签名数据的公钥证书；和

输出单元，向密钥发行服务器装置输出生成的公钥证书。

20、一种素数计算装置中使用的素数算出方法，该素数计算装置算出比

已知素数q大的素数候补N,来进行素数判定，其特征在于，

所述素数计算装置具备：素数存储单元，存储已知的素数q；和管理信

15息存储单元，存储素数利用范围中的唯一管理信息，

所述素数算出方法包含：

随机数生成步骤，从所述管理信息存储单元中读出所述管理信息，生成

依赖于读出的所述管理信息的搅乱信息R；

候补算出步骤，从所述素数存储单元中读出所述素数q,使用读出的所

20述素数q和生成的所述搅乱信息R,通过N=2X搅乱信息RX素数q+1,算出素

数候补N；

素数判定步骤，判定算出的素数候补N是否为素数；和

输出步骤，在判定为是素数的情况下，将算出的素数候补N作为素数进

行输出。

2521、一种素数计算装置中使用的素数算出用计算机程序，素数计算装置

算出比已知素数q大的素数候补N,来进行素数判定，其特征在于,

200480038935.3权利要求书第8/8页

所述素数计算装置具备：素数存储单元，存储已知的素数q；和管理信

息存储单元，存储素数利用范围中的唯一管理信息，

所述素数算出用计算机程序包含：

随机数生成步骤，从所述管理信息存储单元中读出所述管理信息，生成

5依赖于读出的所述管理信息的搅乱信息R;

候补算出步骤，从所述素数存储单元中读出所述素数q，使用读出的所

述素数q和生成的所述搅乱信息R,通过N=2X搅乱信息、RX素数q+1,算出素

数候补N；

素数判定步骤，判定算出的素数候补N是否为素数；和

10输出步骤，在判定为是素数的情况下，将算出的素数候补N作为素数进

行输出。

22、根据权利要求21所述的计算机程序，其特征在于，

所述计算机程序记录在计算机可读取的记录介质中。

23、根据权利要求21所述的计算机程序，其特征在于，

15搭载于载波上来发送所述计算机程序。

200480038935.3说明书第1/114页

素数计算装置和方法以及密钥发行系统

5技术领域

本发明涉及一种将素因数分解的难易作为安全性的基础来保持信息安

全的技术。

背景技术

10近年来，基于计算机技术和通信技术的数据通信广泛普及，在该数据通

信中，使用保密通信方式或数字签名方式。这里，所谓保密通信方式是指不

向特定通信对方以外的对象泄漏通信内容地进行通信的方式。另外，所谓数

字签名方式是指又向通信对方示出通信内容的合法性、又证明发信者的身份

的通信方式。

151.公钥加密方式

关于这些保密通信方式或数字签名方式，使用被称为公钥加密方式的加

密方式。在使用公钥加密方式的保密通信中，加密密钥与解密密钥不同，虽

然解密密钥保密，但加密密钥则公开。将保密的解密密钥称为私钥，将公开

的加密密钥称为公钥。当通信对方多时，在共同密钥加密下，通信对方之间

20必需具有密钥，而在公钥加密下，通信对方只要具有一个固有密钥就可通信，

所以即便通信对方增加，密钥数量也比共同密钥加密少。这样，公钥加密适

于与多个通信对方进行通信，是不可或缺的基本技术。

在作为公钥加密方式之一的RSA加密方式中，将解决整数的素因数分解

问题在计算量上是困难的情况作为安全性的基础。所谓素因数分解问题是在

25将p、q设为素数，整数n=pXq时，对整数n求出素数p、q的问题。这里，X

200480038935.3说明书第2/114页

是通常的乘法。通常在P、q如1024位的数等大的情况下，素因数分解问题困

难。由此，根据RSA加密方式的公钥求出私钥、或不具有私钥的用户根据加

密文本来求得明码文本变困难。另外，素因数分解问题在非专利文献1的

144-151页中详细记述。

5(应用素因数分解问题的RSA加密方式)

这里，说明应用素因数分解问题的RSA加密方式。

(1)密钥的生成

如下计算公钥和私钥。

.随机选择大的素数P、q，并计算其积n=pXq.

10.计算(pT)和(qT)的最小公倍数L=LCM(p-l,q-1)o

.随机选择与L互质、比L小的自然数e。

lWe<L-l、GCD(e,L)=1

这里，GCD(e,L)表示e与L的最大公约数。

.计算满足eXd=lmodL的d。由于GCD(e,L)=l,所以必然存在这种d。

15这样，得到的整数e和整数n为公钥。另外，整数d为私钥。这里，xmody

表示用y除以x的余数。

(2)加密文本的生成

使用作为公钥的整数e和整数n,对明码文本m实施加密运算，计算加密

文本c。

20c=nfemodn

另外，本说明书中，运算符-表示阶乘。例如，A'x表示当x>0时、乘以x

次A所得的值。

(3)解密文本的生成

使用作为私钥的整数d,对加密文本c实施解密运算，计算解密文本亦。

25m'=c"dmodn

另外，由于

200480038935.3说明书第3/114页

m,=c'dmodn

=(m'e)"dmodn

=m(eXdmodL)modn

=m'1modn

5=mmodn

,所以解密文本m'与明码文本m一致。

另外，关于RSA加密在非专利文献2的110T13页中详细说明。

在应用上述的素因数分解的RSA加密中的公钥生成步骤中，执行素数生

成。素数生成在非专利文献3的145-154页中详细说明。素数生成方法中有概

io率的素数生成法和确定的素数生成方法。由概率的素数生成法生成的素数是

'作为素数的概率高的'数，不限于是100%素数。另一方面，确定的素数生

成方法生成确实是素数的数。在非专利文献2中详细说明了概率的素数生成

方法和确定的素数生成方法。下面说明确定的素数生成方法。

2.现有例1-确定的素数生成方法

15说明基于能确定地生成素数的Maurer法之确定的素数生成方法。这里，

在非专利文献3的152-153页中详细说明了Maurer法。

在所述确定的素数生成方法中，通过重复下面所示的步骤，生成素数。

预先提供位长度为lenq的素数q。

(步骤1)选择(lenq-1)位的随机数R。另外，随机数R的开头位必然为1。

20(步骤2)利用下式计算数N。

N=2XqXR+l

(步骤3)关于数N是否为素数，在下面所示的第1判定和第2判定均成立的

情况下，判定为素数。在其它情况下，判定为不是素数。

(第1判定)2八(N-l)=lmodN

25(第2判定)GCD(2A(2R)-1,N)=l

在判定为是素数的情况下，输出数N,作为素数。在判定为不是素数的

200480038935.3说明书第4/114页

情况下，返回步骤1，重复处理，直到输出素数。

步骤3中描述的判定方法被称为Pocklington的素数判定法，在非专利文

献3的144页中详细描述。在Pocklington的素数判定法中，N=2XqXR+l的q

为素数，若第1判定和第2判定的结果为真，贝4N必然为素数。因此，可确定

5地判定为是素数，可确定地生成素数。

这样，在Maurer法的确定的素数生成方法中，根据长度为lenq的素数q,

生成长度为2Xlenq的素数N。因此，在使用Maurer法的确定的素数生成方法

来生成规定长度的素数的情况下，重复执行所述规定长度以下的素数的生

成。例如，在生成512位长度的素数的情况下，根据预先提供的8位的素数，

10生成16位的素数。之后，根据生成的16位的素数，生成32位的素数。之后，

根据生成的32位的素数，生成64位的素数。下面重复同样的素数生成，生成

512位的素数。

另外，也可将所述第2判定替代为如下判定。

（第3判定）2'（2R）W1modN

15上述第3判定方法在非专利文献4中详细描述。以后使用这些判定方法。

3.具有多个密钥发行服务器的密钥发行系统

在公钥加密的密钥发行系统中，有用户生成密钥的情况、和由密钥发行

服务器向用户发行密钥的情况。在由密钥发行服务器发行密钥的情况下，向

用户发行密钥的服务器多数情况下为一台。但是，为了减轻处理的负荷，密

20钥发行系统具备多台密钥管理服务器，多台密钥管理服务器各自也发行密

钥。

专利文献1：特开2003-5644号公报

非专利文献1：冈本龙明、太田和夫共编,“暗号・口知识问题•数论”，

共立出版，1990

25非专利文献2：冈本龙明、山本博资，“现代暗号”，产业图书（1997

年）

200480038935.3说明书第5/114页

非专利文献3：A.J.Menezes,P.C.vanOorschot,S.A.Vanstone,

"Handbookofappliedcryptography,CRCPress,1997

非专利文献4：冈本荣司，“暗号理论入门”，共立出版，1993,21页

非专利文献5：HenriCohen,"ACourseinComputationalAlgebraic

5NumberTheory”,GTM138,Springer-Verlag,1993

在使用多台密钥发行服务器的密钥发行系统中，第1密钥发行服务器与

第2密钥发行服务器不能彼此检查各自发行的RSA密钥。这是因为若向其它密

钥发行服务器公开发行的RSA密钥，则安全上有问题。因此，偶而第1和第2

密钥发行服务器为第1用户和第2用户生成相同的公钥和相同的私钥。

io因此，在利用加密方式时，存在不能确保安全的问题。

例如，第3用户使用第1用户用的所述公钥，对第1用户生成加密文本并

送达时，第1用户当然可使用自身的私钥对加密文本进行解密，但第2用户也

能使用自身的私钥，对所述加密文本进行解密。

15发明内容

为了解决这种问题，通过两个不同素数的积来计算RSA的公钥，所以只

要使公钥生成中使用的各素数在第1密钥发行服务器和第2密钥发行服务器

中不同即可。

因此，本发明的目的在于提供一种素数计算装置、密钥发行系统、素数

20算出方法和素数算出程序，在算出素数时，通过简单的管理，在避免重复的

同时算出素数。

为了实现上述目的，本发明是一种素数计算装置，算出比已知素数q大

的素数候补N,进行素数判定，其特征在于，具备素数存储单元，存储已知

的素数q；管理信息存储单元，存储素数利用范围中的唯一管理信息：搅乱

25信息生成单元，从所述管理信息存储单元中读出所述管理信息，生成依赖于

读出的所述管理信息的搅乱信息R；候补计算单元，从所述素数存储单元中

200480038935.3说明书第6/114页

读出所述素数q，使用读出的所述素数q和生成的所述搅乱信息R，通过N=2X

搅乱信息RX素数q+1,算出素数候补N；素数判定单元，判定算出的素数候

补N是否为素数；和输出单元，在判定为是素数的情况下，将算出的素数候

补N作为素数进行输出。

5根据上述结构，素数计算装置使用依赖于唯一的管理信息生成的搅乱信

息R,算出素数候补N,所以可在避免重复的同时算出素数候补。所谓素数的

利用范围是以素因数分解的难易性作为安全性的基础来利用素数的范围。

这里，也可以是所述搅乱信息生成单元包含：读出部，从所述管理信息

存储单元中读出所述管理信息；随机数算出部，算出随机数r；结合部，结

10合读出的所述管理信息和生成的随机数r；和运算部，根据所述管理信息和

随机数r的结合体，算出搅乱信息R。

根据该结构，素数计算装置根据管理信息和随机数r的结合体，生成搅

乱信息R,所以可生成兼备基于管理信息的唯一性和基于随机数r的随机性的

搅乱信息。

15这里，也可以是所述运算部对所述结合体实施单射函数，生成搅乱信息

Ro

根据该结构，素数计算装置对结合体实施单射函数，生成搅乱信息R,

所以根据单射函数性质，可生成保持结合体具有的唯一性、并且具备基于从

结合体变换的随机性的搅乱信息。

20这里，也可以是所述单射函数是异或(exclusiveor),所述运算部预

先存储规定的密钥信息，对所述密钥信息和所述结合体实施异或，生成搅乱

信息R。

根据该结构，素数计算装置可根据结合体和规定的密钥信息，实施异或，

生成搅乱信息R。

25这里，也可以是所述素数计算装置算出具有素数q的2倍位长度的素数候

补N,所述随机数算出部算出位长度为从素数q的位长度中减去所述管理信息

200480038935.3说明书第7/114页

的位长度和1的所述随机数入

根据该结构，素数计算装置可算出位长度为从素数q的位长度中减去管

理信息的位长度和1的随机数r,并算出具有素数q的2倍位长度的素数候补N。

这里，也可以是所述素数判定单元包含：第1判定部，对所述素数候补N

5判定是否满足2恒=1modN；和第2判定部，在由所述第1判定部判定为满足

的情况下，再对素数候补N和搅乱信息R判定是否满足22块1modN,在判定

为满足的情况下，确定素数候补N为素数。

根据该结构，素数计算装置使用第1和第2判定部来判断素数候补N是否

为素数，所以第1和第2判定部双方在判定结果为肯定的情况下，可将素数候

io补N判断为素数。

这里，也可以是所述素数判定单元包含：第1判定部，对所述素数候补N

判定是否满足21=1modN；和第2判定部，在由所述第1判定部判定为满足

的情况下，再对素数候补N和搅乱信息R判定是否满足GCD（22R-1、N）=l,在判

定为满足的情况下，确定素数候补N为素数。

15根据该结构，素数计算装置使用第1和第2判定部来判断素数候补N是否

为素数，所以第1和第2判定部双方在判定结果为肯定的情况下，可将素数候

补N判断为素数。

这里，也可以是所述素数计算装置还包含：重复控制单元，对所述搅乱

信息生成单元、所述候补计算单元和所述素数判定单元进行控制，以重复搅

20乱信息R的生成、素数候补N的计算和所述判定，直到由所述素数判定单元判

定为是素数为止。

根据该结构，素数计算装置利用重复控制单元，重复搅乱信息R的生成、

素数候补N的计算、素数的判定，直到判定为生成的素数候补是素数为止，

所以总是能够输出素数。

25这里，也可以是所述素数计算装置还包含：次级随机数计算单元，算出

随机数R'；次级候补计算单元，使用输出的所述素数N和生成的所述随机数

200480038935.3说明书第8/114页

R',通过N'=2X随机数R，X素数N+1,算出素数候补V；次级素数判定

单元，判定算出的素数候补N'是否为素数；次级输出单元，在判定为是素

数的情况下，将算出的素数候补N'作为素数进行输出；和次级重复控制单

元，对所述次级随机数计算单元、所述次级候补计算单元和所述次级素数判

5定单元进行控制，以重复随机数R'的生成、素数候补M的计算和所述判定,

直到由所述次级素数判定单元判定为是素数为止。

根据该结构，素数计算装置使用素数N和生成的随机数R，,算出素数候

补V,判定算出的素数候补M是否为素数，并在是素数的情况下，将算出

的素数候补M作为素数进行输出。

10这里，也可以是所述素数计算装置还包含：次级信息存储单元，存储规

定的验证值；次级随机数生成单元，生成随机数r'；和次级候补计算单元，

对所述管理信息乘以生成的所述随机数r',算出搅乱信息R',并通过

N'=2X搅乱信息R，X素数N+验证值，算出素数候补V,所述素数判定单

元还判定算出的素数候补N'是否为素数，所述输出单元还在判定为素数候

15补V为素数的情况下，将算出的素数候补V作为素数进行输出。

根据该结构，素数计算装置使用验证值、素数N、向管理信息乘以随机

数J的搅乱信息R',算出素数候补V,判断算出的素数候补V是否为素

数，在是素数的情况下，将素数候补W作为素数进行输出。由此，可生成

从素数『中减去验证值的结果被管理信息除尽的素数V。

20这里，也可以是所述素数计算装置是生成RSA加密的公钥和私钥的密钥

生成装置，所述素数计算装置还包含：公钥生成单元，使用算出的素数N,

生成RSA加密的公钥；和私钥生成单元，使用生成的公钥，生成RSA加密的私

钥。

根据该结构，素数计算装置可构成生成RSA加密的公钥和私钥的密钥生

25成装置，素数计算装置使用算出的素数N,生成公钥，并使用生成的公钥，

生成私钥。

200480038935.3说明书第9/114页

这里，也可以是所述公钥生成单元对所述重复控制单元指示重新得到素

数N',并使用所述素数N和重新得到的素数N',通过n=素数NX素数V,

算出数n,生成随机数e,算出的数n和生成的随机数e的组为所述公钥，所述

私钥生成单元算出满足eXd=lmodL的d,L是素数NT和素数V-1的最小公

5倍数，算出的d是所述私钥。

根据该结构，素数计算装置使用素数N和素数N',算出数n,生成随机

数e,从而生成公钥，并根据生成的随机数e、与素数N-1和素数N'T的最小

公倍数，生成私钥。

这里，也可以是所述素数计算装置是密钥发行服务器装置，对终端装置

10生成并发行RSA的私钥和公钥，所述素数计算装置还包含：密钥输出单元，

对终端装置输出生成的所述私钥；和公开单元，公开生成的所述公钥。

根据该结构，素数计算装置对终端装置输出生成的私钥，公开生成的公

钥。

这里，也可以是所述素数计算装置还包含：标识符取得单元，取得唯一

15识别所述终端装置的终端装置标识符；管理信息生成单元，生成包含取得的

终端装置标识符的所述管理信息；和写入单元，将生成的所述管理信息写入

所述管理信息存储单元中。

根据该结构，素数计算装置生成包含终端装置标识符的管理信息，将生

成的管理信息写入管理信息存储单元中，所以可存储唯一的管理信息。

20这里，也可以是所述素数计算装置还包含：服务器标识符存储单元，预

先存储唯一识别作为密钥发行服务器装置的该素数计算装置的服务器标识

符，所述管理信息生成单元还从所述服务器标识符存储单元中读出所述服务

器标识符，并生成还包含读出的服务器标识符的所述管理信息。

根据该结构，素数计算装置还生成包含服务器标识符的管理信息，所以

25可提高管理信息的唯一性。

另外，本发明是一种素数计算装置，算出比已知素数大的素数，其特征

200480038935.3说明书第10/114页

在于，具备：素数计算单元，算出具有已知输入素数的2倍位长度的输出素

数；素数存储单元，存储已知的素数初始值；和重复控制单元，对所述素数

计算单元进行控制，以重复多次计算，所述重复控制单元在所述重复中的初

次计算中，将存储在所述素数存储单元中的素数初始值作为所述输入素数，

5提供给所述素数计算单元，在所述重复的初次计算以外的其它计算中，将前

一次计算中的输出素数作为该其它计算中的所述输入素数，提供给所述素数

计算单元，在所述多次算出的任一计算中，所述素数计算单元包含：管理信

息保存部，存储素数利用范围中的唯一管理信息；搅乱信息生成部，从所述

管理信息保存部中读出所述管理信息，生成依赖于读出的所述管理信息的搅

10乱信息R；候补算出部，接收所述输入素数q,使用接受的所述输入素数q和

生成的所述搅乱信息R,通过N=2X搅乱信息RX素数q+1,算出素数候补N：

素数判定部，判定算出的素数候补N是否为素数：输出部，在判定为是素数

的情况下，将算出的素数候补N作为输出素数进行输出；和重复控制部，对

所述搅乱信息生成部、所述候补算出部和所述素数判定部进行控制，以重复

15搅乱信息R的生成、素数候补N的计算与所述判定，直到由所述素数判定部判

定为是素数为止。

根据该结构，素数计算装置的素数输出单元在多次输出素数的计算之一

的计算中，使用依赖于唯一的管理信息生成的搅乱信息R,算出素数候补N,

所以可边避免重复边算出素数候补。

20这里，也可以是在所述多次计算中的最终次计算中，所述素数计算单元

包含：信息保存部，存储规定的验证值；随机数生成部，生成随机数r，；

候补算出部，对所述管理信息乘以生成的所述随机数r',算出搅乱信息R，,

并通过N'=2X搅乱信息R，X前一次算出的输出素数+验证值，算出素数候

补W；素数判定部，判定算出的素数候补M是否为素数；输出部，在判定

25为素数候补N'为素数的情况下，将算出的素数候补V作为素数进行输出；

和重复控制部，对所述随机数生成部、所述候补算出部和所述素数判定部进

200480038935.3说明书第11/114页

行控制，以重复随机数r’的生成、素数候补V的计算和所述判定，直到由

所述素数判定部判定为是素数为止。

根据该结构，素数计算装置使用验证值、在前一次算出的输出素数、向

管理信息乘以随机数r，的搅乱信息R',算出素数候补V,判断算出的素

5数候补N，是否为素数，在为素数的情况下，将素数候补N'作为素数进行

输出。由此，可生成从素数N'中减去验证值的结果被管理信息除尽的素数

VO

另外，本发明是一种密钥发行系统，具有生成RSA的私钥和公钥后对终

端装置发行的密钥发行服务器装置、和所述终端装置，其特征在于，密钥发

10行服务器装置具备素数计算单元，算出比已知素数q大的素数N；公钥生成单

元，使用算出的素数N,生成RSA加密的公钥：私钥生成单元，使用生成的公

钥，生成RSA加密的私钥；密钥输出单元，对终端装置输出生成的所述私钥；

和公开单元，公开生成的所述公钥，所述素数计算单元包含：素数保存部，

存储已知的素数q；管理信息保存部，存储唯一的管理信息；搅乱信息生成

15部，从所述管理信息保存部中读出所述管理信息，生成依赖于读出的所述管

理信息的搅乱信息R;候补算出部，从所述素数保存部中读出所述素数q,使

用读出的所述素数q和生成的所述搅乱信息R,通过N=2X搅乱信息RX素数

q+1,算出素数候补N；素数判定部，判定算出的素数候补N是否为素数；输

出部，在判定为是素数的情况下，将算出的素数候补N作为素数进行输出；

20和重复控制部，对所述搅乱信息生成部、所述候补算出部和所述素数判定部

进行控制，以重复搅乱信息R的生成、素数候补N的计算与所述判定，直到由

所述素数判定部判定为是素数为止，所述终端装置具备接收单元，接收所述

私钥；和密钥存储单元，存储接收到的私钥。

根据该结构，密钥发行系统的密钥发行服务器装置使用依赖于唯一的管

25理信息生成的搅乱信息R,算出素数候补N,所以可在避免重复的同时算出素

数候补。终端装置从密钥发行服务器装置接收私钥并存储，所以可存储根据

200480038935.3说明书第12/114页

在避免重复的同时生成的素数N来生成的、即在避免重复的同时生成的私钥。

这里，也可以是所述密钥发行系统还包含证书发行服务器装置，所述密

钥输出单元向所述证书发行服务器装置输出所述公钥,所述证书发行服务器

装置具备存储单元，存储该证书发行服务器装置的私钥；取得单元，取得所

5述公钥；证书生成单元，使用所述证书发行服务器装置的私钥，对包含所述

公钥的公钥信息实施数字签名，生成签名数据，并生成至少包含所述公钥和

生成的所述签名数据的公钥证书；和输出单元，向密钥发行服务器装置输出

生成的公钥证书。

根据该结构，密钥发行系统可使用证书发行服务器装置，发行与由密钥

10发行服务器装置发行的公钥对应的公钥证书。

附图说明

图1是表示密钥发行系统1的整体示意图。

图2是表示密钥发行服务器100的结构的框图。

15图3是表示素数生成部116的结构的框图。

图4是表示控制信息表格T100的数据结构一例的图。

图5是表示素数信息生成部133的结构的框图。

图6是表示证书发行服务器200的结构的框图。

图7是表示验证值表格T200的数据结构一例的图。

20图8是表示终端装置300的结构的框图。

图9是表示密钥发行系统1的动作示意流程图。

图10是表示密钥发行系统1中的密钥委托处理动作的流程图。

图11是表示密钥发行系统1中的密钥发行处理动作的流程图。下接图12。

图12是表示密钥发行系统1中的密钥发行处理动作的流程图。上接图11,

25下接图13。

图13是表示密钥发行系统1中的密钥发行处理动作的流程图。上接图12,

200480038935.3说明书第13/114页

下接图14。

图14是表示密钥发行系统1中的密钥发行处理动作的流程图。上接图13。

图15是表示素数生成处理动作的流程图。

图16是表示素数候补生成处理动作的流程图。下接图17。

5图17是表示素数候补生成处理动作的流程图。上接图16。

图18是表示密钥发行系统1中的证书发行处理动作的流程图。

图19是表示素数信息生成部133A的结构的框图。

图20是表示验证值表格T250的数据结构一例的图。

图21是表示素数信息生成部133B的结构的框图。

10图22是表示素数生成部116c的结构的框图。

图23是表示控制信息表格T150的数据结构的一例的图。

图24是表示素数信息生成部133c的结构的框图。

图25是表示素数候补生成处理的动作的流程图。

图26是表示密钥发行系统2的整体示意图。

15图27是表示密钥发行服务器1110的结构的框图。

图28是表示已发行密钥信息表格T1100的数据结构一例的图。

图29是表示密钥发行检查服务器1200的结构的框图。

图30是表示验证值表格T1200的数据结构一例的图。

图31是表示密钥发行时的密钥发行系统2的动作示意流程图。

20图32是表示密钥发行时的密钥发行系统2的动作示意流程图。

图33是表示密钥发行系统2中的证书发行处理的动作的流程图。

图34是表示密钥发行系统2中的密钥信息取得处理动作的流程图。

图35是表示密钥发行系统2中的检查处理的动作的流程图。

图36是表示确认处理的动作的流程图。

25图37是表示根据8位的素数来生成512位素数的动作图。

图38是表示素数生成装置2100的结构的框图。

200480038935.3说明书第14/114页

图39是表示素数生成处理动作的流程图。

图40是表示素数候补生成处理动作的流程图。

图41是表示素数生成装置2200的结构的框图。

图42是表示素数生成装置2300的结构的框图。

5图43是表示素数生成装置2400的结构的框图。

图44是表示素数生成装置2500的结构的框图。

图45是表示在发行标识符信息“IDI”的位串中埋入构成随机数“R1”

的各位的结果一例的图。

图46是表示验证处理动作的流程图。

10附图标记说明

1密钥发行系统

100.101.102密钥发行服务器

110标识符保存部

111私钥保存部

15112公钥保存部

113证书保存部

114控制部

115标识符生成部

116素数生成部

20117密钥判定部

118密钥生成部

119信息取得部

120接收部

121发送部

25130服务器标识符存储区域

131终端信息存储区域

200480038935.3说明书第15/114页

132重复控制部

133素数信息生成部

135重复计数器

136输出计数器

5140信息控制部

141随机数生成部

142素数候补生成部

143第1素数判定部

144第2素数判定部

10200证书发行服务器

210私钥保存部

211发行公钥保存部

212发行标识符信息保存部

213公钥证书保存部

15214发行公钥确认部

215公钥证书生成部

216证书取得部

217接收部

218发送部

20220服务器信息存储区域

221确认信息存储区域

300、301、302、303、304、305、306终端装置

310私钥保存部

311公钥证书保存部

25312控制部

313接收部

200480038935.3说明书第16/114页

314无线部

315基带信号处理部

316扬声器

317麦克风

318显示部

319天线

320终端标识符存储区域

400终端装置

2密钥发行系统

1100、1101、1102密钥发行服务器

1110标识符保存部

1111私钥保存部

1112公钥保存部

1113证书保存部

1114控制部

1115标识符生成部

1116素数生成部

1117密钥判定部

1118密钥生成部

1119信息取得部

1120接收部

1121发送部

1122证书生成部

1123证书用私钥保存部

1124已发行密钥信息保存部

1130服务器标识符存储区域

200480038935.3说明书第17/114页

1131终端信息存储区域

1200密钥发行检查服务器

1210确认信息保存部

1211已发行密钥信息保存部

51212控制部

1213发行公钥确认部

1214受理部

1215检查结果输出部

1216接收部

101217发送部

1220服务器信息存储区域

1250监视器

1300、1301>1302、1303、1304、1305、1306终端装置

1400终端装置

152100素数生成装置

2101受理部

2102受理信息保存部

2103素数种子生成部

2104随机数生成部

202105素数候补生成部

2106素数判定部

2107素数判定部

2200素数生成装置

2201受理部

252202受理信息保存部

2203随机数生成部

200480038935.3说明书第18/114页

2204素数候补生成部

2205素数判定部

2206素数判定部

2300素数生成装置

52301受理部

2302受理信息保存部

2303标识符素数生成部

2304随机数生成部

2305素数候补生成部

102306素数判定部

2307素数判定部

2400素数生成装置

2401受理部

2402