[go: up one dir, main page]

CN1592196A - 数据共享方法、委托处理方法及装置 - Google Patents

数据共享方法、委托处理方法及装置 Download PDF

Info

Publication number
CN1592196A
CN1592196A CNA2004100686309A CN200410068630A CN1592196A CN 1592196 A CN1592196 A CN 1592196A CN A2004100686309 A CNA2004100686309 A CN A2004100686309A CN 200410068630 A CN200410068630 A CN 200410068630A CN 1592196 A CN1592196 A CN 1592196A
Authority
CN
China
Prior art keywords
data
calculation
trust
init
calculate
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
CNA2004100686309A
Other languages
English (en)
Other versions
CN100546243C (zh
Inventor
大石和臣
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Canon Inc
Original Assignee
Canon Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Canon Inc filed Critical Canon Inc
Publication of CN1592196A publication Critical patent/CN1592196A/zh
Application granted granted Critical
Publication of CN100546243C publication Critical patent/CN100546243C/zh
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/0816—Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
    • H04L9/0838—Key agreement, i.e. key establishment technique in which a shared key is derived by parties as a function of information contributed by, or associated with, each of these
    • H04L9/0841—Key agreement, i.e. key establishment technique in which a shared key is derived by parties as a function of information contributed by, or associated with, each of these involving Diffie-Hellman or related key agreement protocols
    • H04L9/0844—Key agreement, i.e. key establishment technique in which a shared key is derived by parties as a function of information contributed by, or associated with, each of these involving Diffie-Hellman or related key agreement protocols with user authentication or key authentication, e.g. ElGamal, MTI, MQV-Menezes-Qu-Vanstone protocol or Diffie-Hellman protocols using implicitly-certified keys
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • H04L9/3006—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters
    • H04L9/3013—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • H04L9/3066—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
    • H04L2209/76—Proxy, i.e. using intermediary entity to perform cryptographic operations

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Computing Systems (AREA)
  • Physics & Mathematics (AREA)
  • Algebra (AREA)
  • General Physics & Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Mathematical Physics (AREA)
  • Pure & Applied Mathematics (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Computer And Data Communications (AREA)

Abstract

数据共享装置与通信对方共享第1数据。数据共享装置使用委托计算从第3数据求出第2数据，通信对方从第2数据和第5数据生成用于求出第1数据的第4数据。然后，数据共享装置使用委托计算从由第3数据和第7数据生成的第6数据求出与通信对方共享的第1数据。

Description

数据共享方法、委托处理方法及装置
技术领域
本发明涉及与通信对方共享数据的共享方法、处理计算委托的处理方法及装置。
背景技术
由于Ipv6的问世，已考虑了现在没有考虑与网络连接的装置与网络连接的情况。例如面向能与因特网直接连接的最终用户的数字摄像机。
考虑用Ipv6进行通信的装置使用Ipsec进行加密通信。
Ipsec是因特网上的2个装置共享其它人谁也不知道的保密数据，并根据该保密数据进行加密和认证的协议，在通信时有必要安全地共享保密数据和双方的Ipv6地址等。保密数据和双方的Ipv6地址等数据被称为SA(保密关联)。安全地共享SA的协议叫做IKE(Internetkey Exchange：因特网密钥交换)，并在RFC2409“Internet keyExchange(IKE)”中被规定。此处，安全地共享SA的意思是只与希望的对方可靠地共享SA的意思，必须可靠地确认对方。在IKE中作为共享保密数据的方法使用Diffie-Hellman公开密钥发送方式(以下，记作DH)。并规定4个认证方法。
在IKE的执行中所进行的处理中负荷最大的是DH的处理，即使在DH的处理中，大的整数(例如，如果是1990年前后是512位，最近理想的是1024位左右)的幂乘余数计算的负荷特别大。所谓幂乘余数计算是从B和C求出满足A＝B^{C}mod D的A，即用D除B的C次方的余数A的计算。此外，在使用K位大小的整数计算幂乘余数计算的情况下，必须进行K+(用2进制表达指数B时的1的个数)-1次的乘法余数计算。在K是512的情况下，平均是767(＝512+256-1)次。
在用Ipv6进行通信的装置中，如面向所述的最终用户的数字摄像机那样也有计算能力不一定大的装置。那样的装置如果执行IKE，则往往需要几分钟的处理时间，缩短该处理时间就成为课题。此外，不限于IKE，由于DH或RSA密码系统、EIGamaI密码方式、EIGamaI署名方式等许多公开密钥密码需要幂乘余数计算，因此有效地执行幂乘余数计算这一点在利用公开密钥密码方面是有用的。
此外，与该幂乘余数计算相反的计算，即在某系数和基数的基础上求出某个值的指数的计算被称为离散对数问题，在系数大的情况下的离散对数问题在现实中无法解答，但已成为上述的公开密钥密码的安全性的根据(的一部分)。另外，作为用于实现DH的数学构造，能够使用有限域上的乘法群(multiplicative group)、或者有限域上的椭圆曲线。以下以上述的乘法群为例进行说明，但本发明在使用椭圆曲线的情况下也有效。
可是，正在研究和开发在作为计算能力小的装置向计算能力大的装置委托计算的方式下，在计算中一边隐藏必要的保密信息一边进行委托的方法(以下，记作委托计算)(IC卡片不泄露秘密而使用终端进行计算，参照松本勉、加藤光几、今井秀树编著的“第10届信息理论及其应用论文集(1987)”，以及Tsutomu MATSUMOTO KokiKATO，Hideki IMAI，“speeding up secret computations with insecureauxiliary devices，”Advances in Cryptology-CRYPTO’88.PP.497506，Springer-Verlag(1988))。
作为那样的方法的具体例子，RSA密码的加密变换(解密或生成署名)是最典型的。这是计算能力小的装置(客户端)具有密钥，不公开该密钥而向计算能力大的装置(服务器)委托将密钥作为指数的幂乘余数计算的方法。有以下的不同点，即在RSA密码的加密变换的情况下，系数是合成数，在DH的情况下系数是素数，但无论哪一个都是将密钥作为指数的幂乘余数计算。
在它们当中，提案出多种委托计算RSA密码的加密变换的方法，包含在DH的幂乘余数计算中能应用的方法。它们中的某一种方法(后述的RSA-S1)在离散对数问题不能解答的前提下，根据用全部不符合的情况下的全部符合次数评价它的安全性。在决定其参数使得全部符合次数变成10^20左右时，RSA-S1需要20次乘法余数计算。
另外，也提案出委托计算RSA密码的加密变换的方法(参照USP5046094)。
在它们当中，有也能应用于DH的幂乘余数计算中的方法。这些方法是通过并行地执行客户端进行的计算和服务器进行的计算，即使在计算能力的差别和通信线路的速度不同的情况下也能最佳地缩短总的处理时间的方法，是客户端也进行幂乘余数计算的方法。因此，如果将在全部不符合的情况下的全部符合次数设定为10^20左右(＝大约2^67)，则客户端必须自己计算使用67位左右的指数的幂乘余数计算，乘法余数计算的次数平均约100次，比所述的MATSUMOTO等人的方法(RSA-S1)多。
另外，也提出了委托计算RSA密码的加密交换的方法，也能够适用于DH中(参照USP5369708)。
这些方法主要着眼于完全不泄露加密交换所需要的保密信息，并且是与同样的现有技术相比提高了处理效率的方法。但是，在512比特的情况下，由于记载了客户端执行的乘法余数计算在100次以上，所以比所述的MATSUMOTO等人的方法(RSA-S1)多。
在委托计算1次的幂乘余数计算的情况下能使用以上的委托计算方法。
可是，在DH中，如以下那样重复进行2次幂乘余数计算。
一边参照图4一边说明在实体A和实体B将素数p、生成元g作为共同参数使用并执行DH时的协议。
在步骤S401A中，实体A生成保密信息x_A。在步骤401B中生成保密信息x_B。
在步骤S402A中，实体A计算y_A＝g^(x_A)mod p，在步骤S403A中实体A将y_A发送到实体B。
在步骤S402B中，实体B计算y_B＝g^(x_B)mod p，在步骤S403B中实体B将y_B发送到实体A。
在步骤S404A中，实体A计算y_AB＝(y_B)^(x_A)mod p，在步骤S404B中，实体B计算y_BA＝(y_A)^(x_B)mod p。
此处，由于y_AB＝(g^(x_B))^(x_A)mod p＝(x_A*x_B)mod p＝(g^(x_A))^(x_B)mod p＝y_BA，因此将该y_AB＝y_BA作为共同的加密数据使用，并生成加密密钥等。
这样，在利用委托计算执行DH的情况下，有必要进行使用相同的加密信息(x_A或x_B)的2次的幂乘乘法计算的委托计算。如果考虑这一点，则在DH中应用了上述的委托计算的情况下，对于以下说明的攻击有变得脆弱的可能性。
考虑着眼于实体A，实体A作为客户端执行委托计算协议的情况。作为具体的委托计算方法，采用上述的MATSUMOTO等人的论文的Protocol RSA-S1进行说明。客户端具有整数x、d、n，并想求出y＝x^d mod n。d是客户端的秘密，n是公开的。将n的CarmichaelFunction记作λ(n)。一边参照图5一边进行说明。
在步骤S501中，客户端随机地生成成为d＝f_1*d_1+f_2*d_2+...f_M*d_M(modλ(n))那样的整数矢量D＝[d_1、d_2、...、d_M]和二进制矢量F＝[f_1、f_2、...、f_M]。但是，设M和L为某个整数，d_i是1以上n以下，F的加权(在F的要素f_1、f_2、...、f_M中，值是1的要素的个数)是L以下。此外，上述的式子表示用λ(n)除d的余数和用λ(n)除计算了f_1*d_1+f_2*d_2+...+f_M*d_M的值的余数是相等的。
在步骤S502中，客户端将n、D、x发送到服务器。
在步骤S503中，服务器计算成为z_i＝x^(d_i)mod n的Z＝[z_1、z_2、...、z_M]。在步骤S504中，服务器将Z发送给客户端。
在步骤S505中，客户端如以下那样计算y＝y_M。即，设定y_0＝1，对于i＝1、2、...、M，如果f_i＝1，则y_i＝y(i-1)*z_i mod n，如果f_i＝0，则y_i＝y_(i-1)。将它从i＝1到i＝M，反复进行。即，依次求出y_1、y_2...，将它反复进行，求出y_M。
在将该协议的系数n设定为素数p时，变成λ(n)＝λ(p)＝p-1，并能在DH中应用。因此，客户端2次执行保密的指数值d＝x_A的幂乘余数计算的委托计算协议。第1次是用于求出y_A＝g^(x_A)modp，第2次是用于求出y_AB＝(y_B)^(x_A)mod p的委托计算协议。此处，由于对于在因特网上执行的IKE，y_A是被发送到实体B的值，因此应考虑到攻击者(因特网上的第三者或委托计算的服务器)能够得到y_A的值。于是，那样的攻击者能够在原理上从D和Z通过全部符合求出与y_A的值一致那样的F。为了成为在现实的时间中无法被求出那样的全部符合的次数而设定参数M和L，但只要判明y_A的值，在原理上就能求出F(至少规定1个成为y_A的组合)。
此处，考虑根据某些技巧，用全部不符合有效的攻击方法实现第1次委托计算协议的情况。例如，由于在IKE中被使用的p和g_被标准化，因此也许发现对于多个不同的i，因特网上的多台计算机分别生成事前计算了g^i mod p的表，它们同时并行并有效地执行全部符合的新的分散算法。在实现这样的攻击的情况下，只要使用相同的指数值和相同的F，就能够利用D和攻击第1次的委托计算协议而判明的F，直接求出第2次的委托计算协议的结果(y_AB)，因此就会破坏DH。此外，由于在第2次的委托计算协议中基数(y_B)的值每次不同，因此上述那样的全部符合攻击对于单独的第2次委托计算协议不成立。
另外，对于上述USP5046094的方法，客户端使用只有客户端知道的加密的指数值自己进行幂乘余数计算，但如已经指出的那样，在将对于全部符合的安全性变成了与RSA-S1相同程度的情况下，计算量比RSA-S1多。因此，在适用于进行2次的委托计算的DH中的情况下，计算量也变成2倍，没有满足最初的目的(计算能力小的装置自己没有进行负荷大的计算而求出幂乘余数计算结果)。
另外，上述USP5369708在完全没有泄露指数值的意义上是最安全的，但计算量增大。因此，在适用于进行2次的委托计算的DH中的情况下，计算量也变成2倍，没有满足最初的目的(计算能力小的装置自己不进行负荷大的计算，而求出幂乘余数计算结果)。
发明内容
即，本发明想要解决的课题就是，自己进行的计算量少的委托计算安全性低，安全性高的委托计算自己进行的计算量多。
本发明的目的在于：使自己进行的计算量和安全性并存。
为解决上述课题，涉及本申请的第1发明生成参数使得在第1次委托计算中使用的参数和在第2次委托计算中使用的参数独立。
在通过所述第1发明执行2次的委托计算的情况下，能够提高上述那样的对全部符合的攻击的耐受性。
为解决上述课题，涉及本申请的第2发明在用于求出第2共享数据的第1次委托计算中使用用于求出第1共享数据的第1次委托计算的结果。
通过所述第2发明，即使自己不计算在用于求出第2共享数据的第1次委托计算中使用的参数也可以。
通过所述第2发明，对于用于求出第2共享数据的第1次委托计算的全部符合攻击的耐受性变成对于用于求出第1共享数据的第1次委托计算的全部符合攻击的耐受性和对于用于求出第2共享数据的第1次委托计算的全部符合攻击的耐受性的积。
本发明的其它目的从以下的实施例的说明将会明确。
附图说明
图1是委托计算协议的图。
图2是以太(R)局域网的模式图。
图3是节点的构成图。
图4是Diffie-Hellman Public-key发布方案的图。
图5是Protocol RSA-S1的图。
图6是抽象化IKE协议(主模式)图。
图7是统一IKE协议(应答方兼作委托计算服务器的情况)的图。
图8是统一IKE协议(网闫兼作委托计算服务器的情况)的图。
图9是IKE-Proxy协议图。
图10是采用使用了pre-shared key的认证方式的主模式的协议图。
图11是采用了已使用数字署名的认证方式的主模式的协议图。
具体实施方式
在本实施例中，说明当某个节点(设定为节点A)使用IKE与其它节点(设定为节点B)进行IPsec通信时，通过与委托计算服务器(设定为节点S)执行委托计算协议而执行DH的实施例。
图2是模式地表示本实施例的连接环境的图。图2表示被连接到LAN的主机204、205、206经由缺省网关202访问因特网201的环境。在本实施例中，假定各主装置用链路207连接，具体地说假定是因特网(R)。所谓链路是与它连接的装置经由它能够进行通信的设备或者媒体，它连接到IP层的下侧。在链路中，除因特网(R)外，还有PPP链路、X.25、帧中继、ATM网络。与链路连接的Ipv6对应装置叫做节点。
在图3中示出了节点的内部构成的典型例子。在节点中，有路由器和主机，路由器转送不是发送给自己的信息包，而主机不转送。如从图3知道的那样，节点是具有CPU303、ROM304、RAM305、HD(硬盘)306、电源307、键盘/定点设备的接口308、监视器的接口309、网络接口301、302等的计算机，路由器具有多个网络接口，与此相对，主机在许多情况下具有1个网络接口。根据节点也有不具有HD的。
此外，作为装置或程序实现以下的处理内容(程序)，由具有该装置的节点执行，或者由存储在ROM305或HD306中的节点执行。例如，在作为程序被实现的情况下，CPU303读入该程序，根据需要进行以下动作：一边将RAM305作为用于计算的空间利用，一边经由总线310对对象数据施行加密的计算并计算密码正文。
图3的节点如以后详细地说明的那样，是用于与通信对方共享第1数据y_AB的数据共享装置。
一边参照图1一边说明本实施例的协议。在以下的说明中，例如，节点A是主机204，结点B是主机209。节点S是能够经由主节点206或者缺省网关202或者因特网201进行通信的主机(未图示)。
图1表示客户端和服务器在执行DH时所进行的(2次的委托计算)协议。客户端(节点A，例如图2的主机204)具有保密信息x_A，并设想用委托计算协议求出在与进行IPsec通信的通信对方(节点B，例如图2的主机209)之间最终共享的y_AB＝(y_B)^(x_A)mod p和为求出该y_AB在中途必要的y_A＝g^(x_A)mod p。x_A是客户端的保密信息，g和p是公开的。将p的Carmichael Function记作λ(p)。客户端已知道服务器(节点S，例如主机206)的IP地址。
在步骤S101中，客户端(主机204)准备随机数r_init和y_init＝g^(r_init)mod p。r_init是1以上未满p的整数。在以前执行了图1中说明的协议的情况下，将上次计算出的r和g^r mod p作为r_init和y_init＝g^(r_init)mod p利用。，在以前执行了图1中说明的协议的情况下，将上次计算出的r和g^r mod p预先存储在RAM305和HD306中。
另外，在初次执行协议的情况下，假定客户端在以下这样的状态下出厂，即，例如在制造时生成随机数r_init，并已经将计算出的y_init＝g^(r_init)mod p记录在ROM304或HD306中。或者，在其他的实施例中，在待机状态(不执行委托计算协议的状态)下生成r_init并计算y_init＝g^(r_init)mod p，将该结果预先记录在RAM305或HD306中。或者在其它的实施例中，在用于IKE的委托计算(在图6中说明的协议)之前与服务器执行在后述的信息量上的安全的委托计算协议。
在步骤S102中，客户端随机地生成作为r_1st＝f_1*d_1+f_2*d_2+...+f_M*d_M(modλ(p))那样的整数矢量D＝[d_1、d_2、...、d_M]和二进制向量F＝[f_1、f_2、...、f_M]。其中，设M和L为某个整数，d-i在1以上而不满p，F的加权(在F的要素f_1、f_2、...、f_M中，值是1的要素的个数)是L以下。此外，上述的式子表示用λ(n)除d的余数和用λ(n)除计算了f_1*d_1+f_2*d_2+...+f_M*d_M的值的余数相等。
在步骤S103中，客户端向服务器发送p、D、g。
在步骤S104中，服务器计算成为z_i＝g^(d_i)mod p的Z＝[z_1、z_2、...z_M]。在步骤S105中，服务器将Z发送给客户端。
在步骤S106中，客户端如以下那样计算y_M。即，假定y_0＝1，对于i＝1、2、...、M，如果f_i＝1，则y_i＝y_(i-1)*(z-i)mod p，如果f_i＝0，则y_i＝y_(i-1)。从i＝1到i＝M反复进行。即，依次求出y_1、y_2、...，并反复进行该计算，求出y_M。将y_M设定为y_1st。
然后，客户端将r_1st和y_1st(＝g^(r_1st)mod p)记录到RAM305，作为y_A＝y_init*y_1st mod p求出y_A。已记录在该RAM305中的r_1st和y_1st在下次作为r_init和y_init使用。
此外，由于客户端(节点A，例如图2的主机204)与节点B执行(例如，图2的主机209)IKE，因此将y_A发送到节点B，另一方面，从节点B接收y_B(未图示)。此外，节点B可以如在图4的步骤S401B中已说明的那样计算y_B，但可以用与图1的步骤S101～S106相同的程序求出y_B。
在步骤S107中，客户端随机地生成作为r_init+r_1st＝f_1’*d_1’+f_2’*d_2’+...+f_M’*d_M’(mod(λ(p))那样的整数矢量D’＝[d_1’、d_2’、...、d_M’]和二进制矢量F’＝[f_1’、f_2’、...、f_M’]。其中，M和L为某个整数，d_i’是1以上不满p，F’的加权(在F’的要素f_1’、f_2’、...、f_M’中，值是1的要素的个数)为L以下。
在步骤S108中，客户端将p、D’和y_B发送到服务器。
在步骤S109中，服务器计算成为z_i’＝(y_B)^(d_i’)mod p的Z’＝[z_1’、z_2’、...、z_M’]。在步骤S110中，服务器将Z’发送给客户端。
在步骤S111中，客户端如以下那样计算y_M’。即，假定y_0’＝1，对于i＝1、2、...、M，如果f_i’＝1，则y_i’＝y_(i-1)’*(z_i’)mod p，如果f_i’＝0，则y_i’＝y(i-1)’。将它从i＝1到i＝M，反复进行。即，依次求出y_1’、y_2’、...，将它反复进行，求出y_M’。将y_M’设为y_2nd。将已求出的y_2nd设为y_AB(y_AB:＝y_2nd)。
通过2次执行以上委托计算协议，执行1次DH。接着在执行DH时，这次作为随机数r_init和y_init＝g^(r_init)mod p进行计算，并使用存储在RAM305中的r_1st和y_1st＝g^(r_1st)mod p。
如以上那样，图1表示用于CPU303执行用于与通信对方(节点B)共享第1数据y_AB的数据共享方法的程序。
即，如上述说明的那样，在图1中通过委托计算，根据第3数据r_1st求出第2数据y_1st，通信对方根据第2数据y_1st和第5数据y_init生成用于求出第1数据y_AB的第4数据y_A(步骤S102、S106)。另外，通过委托计算，根据由第3数据r_1st和第7数据r_init被生成的第6数据(r_init+r_1st)求出与通信对方共享的第1数据y_AB(步骤S107、S111)。
详细地说，在用于根据第3数据r_1st求出第2数据y_1st的委托计算中(步骤S106、S107)，根据通过第1变换(使用了上述的数据F的分解)从第3数据r_1st得到的第8数据D得到第9数据Z，使用与第1变换对应的第2变换(使用了上述的数据F的合成)根据第9数据Z生成第2数据y_1st。另外，在用于根据第6数据(r_init+r_1st)求出第1数据y_AB的委托计算中(步骤S107、S111)，根据通过第3变换(使用了上述的数据F’)从第6数据(r_init+r_1st)得到的第10数据D’得到第11数据Z’，通过与第3变换对应的第4变换(使用了上述的数据F’的合成)根据第11数据Z’生成第1数据y_AB。
更详细地说，第2数据y_1st是用p除g的第3数据r_1st次方的余数，第1数据y_AB是用p除第12数据y_B的第6数据(r_init+r_1st)次方的余数。另外，第4数据y_A是用p除第2数据y_1st和第5数据y_init的相乘计算结果的余数，第6数据(r_init+r_1st)是第3数据r_1st和第7数据r_init的相加计算结果(步骤S107)。第5数据y_init是用p除g的第7数据r_init的余数。
在本实施例中，还将用于求出第1共享数据y_AB的第2数据y_1st和第3数据r_1st作为用于求出第2共享数据的第5数据y_ini和第7数据r_init使用。
另外，根据第1数据y_AB生成在与通信对方的通信中使用的加密密钥。
在图3中，CPU303作为生成第3数据r_1st，使用网络接口301，通过委托计算根据第3数据r_1st求出第2数据y_1st的委托计算装置进行动作。
另外，CPU303作为使用由委托计算求出的第2数据y_1st和存储在RAM305中的第5数据y_init，并从第2数据y_1st和第5数据y_init生成用于通信对方求出第1数据y_AB的第4数据y_A的生成装置进行动作。
作为委托计算装置进行动作的CPU303使用事先已生成的第3数据r_1st、已被存储在RAM305中的第7数据r_init，从由第3数据r_1st和第7数据r_init生成的第6数据(r_init+r_1st)，通过委托计算求出与通信对方共享的第1数据y_AB。
在以上的2次委托计算协议中，第1次的委托计算协议的矢量D和F以及第2次的委托计算协议的矢量D’和F’是独立的。就是说，第1次的委托计算协议是将r_1st作为保密信息的委托计算，第2次的委托计算协议是将(r_init+r_1st(mod(λ(p))作为保密信息的委托计算。此外，该式表示用λ(p)除计算了r_init+r_1st的值，或者计算了r_init+r_1st的值的余数。由于客户端的保密数据r_init和y_init＝g^(r_init)mod p是除了客户端以外不知道的随机数，因此如果从第三者的立场看，则这2种委托计算协议作为独立的、不同的委托计算协议被观测。
另外，即使想要通过全部符合从y_A和D求出r_1st(即F)，由于有随机数r_init，因此不能够唯一地决定。从而，作为课题举出的攻击，即利用攻击并判明了D和第1次的委托计算协议的F求出第2次的委托计算协议的结果(y_AB)并破解DH的攻击不成立。
第2次的委托计算协议是将r_init+r_1st mod(λ(p))作为指数值的幂乘余数计算的委托计算。r_init是保密的值，由于用来唯一地确定它的信息y_init是保密的，因此不能从第2次的委托计算协议确定r_init。
接着，考虑第2次的DH执行时。在变量中附加了‘～{n}’的记号表示第n次的DH执行时的变量。
在执行第1次的DH时，由于由服务器计算在第2次的DH中使用的y_init～{2}＝g^(r_init～{2})]mod p，因此客户端不重新计算y_1st～{1}＝g^(r_1st～{1})mod p就可以。
接着，考虑对第2次的DH执行时的第1次委托计算协议的全部符合攻击的耐受性。与第1次的DH执行时不同，在第2次的DH执行是使用的r_init～{2}和y_init～{2}＝g^(r_init～{2})mod p是在第1次的DH执行时被计算的值。就是说，在第2次的DH执行时使用的r_init～{2}＝r_1st～{1}和y_init～{2}＝y_1st～{1}＝(g^(r_1st～{1})mod p)是从第1次的DH执行时的D～{1}和Z～{1}的要素组合求出的值。
而且，可以认为由于对由y_init～{2}＝y_1st～{1}＝(g^(r_1st～{1})mod p)和在第2次的DH执行时被使用的D～{2}和Z～{2}的要素组合而求出的值y_1st～{2}进行乘法余数计算的结果(y_init～{2}*y_1st～{2}mod p)作为y_A～{2}经由因特网被发送到通信对方，因此攻击者可能取得y_A～{2}。
另一方面，y_1st～{2}的值由客户端局部地进行计算，但在因特网上不被通信，因此攻击者无法得到。
因此，在考虑通过全部符合求出y_A～{2}的指数值r_init～{2}+r_1st～{2}mod pλ(p)的攻击时，必须同时使以全部符合求出y_init～{2}＝y_1st～{1}＝(g^(r_1st～{1})mod p)的指数值的攻击和以全部符合求出y_1st～{2}(＝g^(r_1st～{2})mod p)的指数值的攻击的双方都成功。就是说，对第2次DH执行时的第1次委托计算协议的全部符合攻击的耐受性变成对第1次DH执行时的第1次委托计算协议的全部符合攻击的耐受性和对第2次DH执行时的第1次委托计算协议的全部符合攻击的耐受性的积。
因此，变成通过上述那样的全部符合攻击2次破解幂乘余数计算的委托计算协议的工作量。在用于1次破解的时间需要10^20次的全部符合的情况下，需要10^20*10^20＝10^40次的全部符合，因此能够增强上述那样的全部符合攻击的耐受性。
同样的关系在第k次DH执行和第k+1次DH执行之间成立。因此，在用于求出DH执行的最初的委托计算的指数值的工作量需要10^20次全部符合的情况下，在任意的连续2次的DH执行(第k次的DH执行和第k+1次的DH执行)中，用于求出第k+1次DH执行的最初的委托计算的指数值r_1st～{k+1}的工作量需要10^20*10^20＝10^40次的全部符合。
另一方面，如果着眼于第1次和第3次的DH执行，则在y_init～{1}＝(g^(r_init～{1})mod p、y_1st～{1}＝(g^(r_1st～{1})mod p、y_init～{3}＝y_1st～{2}＝g^(r_1st～{2})mod p、y_1st～{3}＝g^(r_1st～{3})mod p中没有使用共同的变量，因此第1次和第3次的DH执行是独立的。于是，作为在第3次DH执行中被使用的y_init～{3}，如果使用y_init～{3}＝y_init～{1}*y_1st～{2}mod p，则攻击者不清楚y_init～{1}(即，r_init～{1})，因此不能从第3次DH执行时的y_A～{3}＝y_init～{3}*y_1st～{3}＝y_init～{1}*y_1st～{2}*y_1st～{3}＝g^(r_init～{1})*g^(r_1st～{2})*g^(r_1st～{3})(mod p)唯一地求出r_1st～{3}。
考虑第4次以后也反复进行同样的处理。就是说，考虑这样的情况，即作为在第4次的DH执行时所使用的y_init～{4}，使用y_init～{4}＝y_init～{1}*y_1st～{3}mod p、作为在第5次的DH执行时所使用的y_init～{5}，使用y_init～{5}＝y_init～{1}*y_1st～{4}mod p、...作为在第k次的DH执行时所使用的y_init～{k}，使用y_init～{k}＝y_init～{1}*y_1st～{k-1}mod p。
在第k＝4次以后的DH执行中，是y_init～{k}＝y_init～{1}*y_1st～{k-1}＝g^(r_init～{1})*g^(r_1st～{k-1}}(mod p)，由于攻击者不知道y_init～{1}和r_init～{1}，因此不能从D～{k}和Z～{k}唯一地确定y_1st～{k-1}＝g^(r_1st～{k-1})mod p的值，不能够通过全部符合的攻击求出r_1st～{k-1}的值。因此，在第n＝3以后的DH的执行中，作为课题举出的攻击，就是说利用D～{n}和攻击第1次的委托计算协议而判明的F～{n}求出第2次委托计算协议的结果(y_AB～{n})并破解DH的攻击不成立。
归纳起来，如果设定为y_init～{n}＝y_init～{1}*y_1st～{n-1}mod p，则作为课题举出的攻击在第n次以后(其中，n是3以上)的DH执行时变成不成立。
由以上可知，在第2次的DH执行时，有用10^40的全部符合被破解的可能性。为使该攻击无效(攻击变成不成立)，可以设置只客户端知道的r_init2和y_init2＝g^(r_init 2)mod p，并作为y_init～{2}＝y_init2*y_1st～{1}mod p进行计算。就是说，最初预先准备2个随机数r_init和r_init2、它们的指数计算值y_init＝g^(r_init)modp和y_init 2＝g^(r_init2)mod p，如果设定为y_init～{2}＝y_init2*y_1st～{1}mod p、y_init～{n}＝y_init～{1}*y_1st～{n-1}mod p(其中，n＝3、4、...)，则作为课题举出的攻击变成不成立。
[在信息量方面安全的委托计算协议]
说明为得到在图1中使用的y_init(＝g^(r_init)mod p)而进行的委托计算协议。
这是在信息量方面具有委托计算服务器或第三者不可能确定客户端的保密信息x的特征的委托计算协议。将保密信息x(为K位的整数)的2进制表达设定为x_(K-1)|x_(K-2)|...x_2|x_1|x_0(‘|’是明确地分离各位的记号，各位数是x_i。(其中，x_i的值是0或1的任何一个)。
(1)客户端将系数p、生成元g、k发送到服务器。
(2)服务器计算z_i＝g^(b_i)mod p(其中b_i＝2^i(i＝O、1、...、k-1))，并将Z＝[z_0、z_1、z_2、...z_(k-1)]发送给客户端。
(3)客户端如以下那样计算g^x mod p＝y_K。即，设定y_0＝1，对于i＝0、1、...、K-1，如果x_i＝0，则y_(i+1)＝y_i mod p，如果x_i＝1，则y_(i+1)＝y_i*z_i mod p。将它从i＝1到i＝K-1，反复进行。即，依次求出y_1、y_2、...，将它反复进行，求出y_K。
在图1的协议中，将该保密信息x作为r_init，将y_K作为y_init(＝g^(r_init)mod p)使用。
[信息量方面安全的委托计算协议结束]
在以上的实施例说明中，说明了使离散对数问题变成困难那样的乘法群及将该乘法群的随机数作为指数的幂乘余数计算的实施例，但也能够使用使离散对数问题变成困难那样的椭圆曲线及椭圆曲线上的点和随机数的乘法。
在使用了上述的乘法群的实施例中，作为加密密钥使用了整数x、作为参数使用了素数p和GF(p)的生成元g、作为公开密钥使用了y＝g^{x}mod p，但在使用椭圆曲线的实施例中，作为加密密钥使用整数x、作为参数使用某个椭圆曲线及该椭圆曲线上的点P、作为公开密钥使用y＝x*P。
图4的协议变成以下那样。实体A生成加密密钥x_A，计算y_A＝x_A*P，将y_A发送到实体B，实体B生成加密密钥x_B，计算y_B＝x_B*P，将y_B发送到实体A。然后，实体A接收y_B，计算y_AB＝x_A*y_B，实体B接收y_A，计算y_BA＝x_B*y_A。
在使用了椭圆曲线的实施例中，乘法群上的某个要素(整数)与椭圆曲线上的点(具有x坐标和y坐标)对应，乘法群的乘法在椭圆曲线中与点和点的加法对应。乘法群的指数计算相当于在椭圆曲线中将相同的点进行多次加法，因此与点和整数的乘法对应。
因此，在乘法群的幂乘余数计算中所使用的指数(整数)r_init+r_1st(图1的步骤S107)，即使椭圆曲线的情况下，也是r_init+r_1st，乘法群的y_A＝y_init*y_1st mod p(图1的步骤S106)在椭圆曲线的情况下是y_A＝y_init*y_1st。但是，椭圆曲线上的点和点的加法(用+表示的计算)、乘法(用*表示的计算)如上述的定义那样。
在图1的协议中，第2数据y_1st是第3数据r_1st和椭圆曲线上的点P的相乘计算结果，第4数据y_A是椭圆曲线上的第2数据y_1st和椭圆曲线上的第5数据y_init的相加计算结果。另外，第1数据y_AB是第6数据(r_1st+r_init)和椭圆曲线上的第12数据y_B的相乘计算结果，第6数据(r_init+r_1st)是第3数据r_1st和第7数据r_init的相加计算结果。第5数据y_init是第7数据r_init和椭圆曲线上的点P的相乘计算结果。
此外，在图1的步骤S103中，将定义椭圆曲线的参数(包含P)和D发送到服务器，在步骤S108中将D’和y_B发送到服务器。
在以下的实施例中，能够使用使离散对数问题变成困难那样的椭圆曲线及其椭圆曲线上的点和随机数的乘法代替使离散对数问题变成困难那样的乘法群及将该乘法群的随机数作为指数的幂乘余数计算。
此外，委托计算协议的服务器作为单独节点，例如图2的主机206被设置在LAN上，该LAN上的其它Ipv6装置(主机204)能够向委托计算服务器委托DH的计算。或者，例如在办公室或家庭的LAN上设置计算能力大的PC，例如图2的主机205，并作为委托计算服务器使其动作，当LAN上的其它Ipv6装置，例如计算能力小的数码摄像机(主机204)与因特网201上的其它Ipv6装置(主机209)进行IKE的Ipsec通信时，通过在服务器(主机205)中进行委托计算，能够进行IKE。
此外，以上根据理想的实施例说明了本发明，但本发明并不只限于上述实施例构成，在权利要求的范围内，能进行各种变形，例如，也能在因特网上设置委托计算协议的服务器。
接着，作为将上述的委托计算协议(图1)与IKE统一的协议，说明进行IKE的节点兼作委托计算协议的服务器的情况。
例如，将因特网上的Web站点的服务器作为委托计算服务器动作，当因特网上的其它Ipv6装置，例如计算能力小的便携式终端访问该Web站点并进行IKE的Ipsec通信时，一边与服务器执行IKE一边同时在服务器中进行委托计算那样的情况。
本实施例是在图1的实施例中，在向通信对方委托用于从第3数据r_1st求出第2数据y_1st的委托计算，以及从第6数据(r_init+r_1st)求出第1数据y_AB的委托计算的例子。最初，简单地说明IKE，IKE的详细情况被记载在RFC2409“The Inernet Key Exchange(IKE)”中。
IKE由阶段1和阶段2组成，在阶段1中确立ISAKMP SA，在阶段2中确立IPsec SA。在阶段1中主模式(6次数据发送接收)和主动模式(3次数据发送接收)的任何一个与4种认证方式组合并被执行，因此仅在阶段1中就存在8种组合。在各模式的各自的组合中，被发送接收的数据不一样。在4种认证方式中，对于使用公开密钥密码的2种加密，DH的数据被加密。另一方面，阶段2只是快速模式，DH是任选。但是，IKE的本质是与SA配合的DH的执行。如果不对与它们相关的数据发送接收进行加密，则能直接应用上述的委托计算协议(图1)。
如果依据RFC2409，则采用了pre-shared key的认证方式的主模式是图10那样的协议(数据的详细情况后述)。
此外，图10的HDR表示ISAKMP标题，在其右边记载的数据表示有效负荷。例如，“HDR、SA”表示ISAKMP信息包的负荷是SA。HDR*表示对该信息包的负荷进行加密。KE是在Diffie-He1lman中被交换的信息，Ni和Nr是Nonce(随机数)，IDii和IDir是identificationpayload，HASH_I和HASH_R是由在以前已交换的数据生成的HASH值。最后的2个加密数据使用根据用Diffie-Hellman共享的保密信息生成的加密密钥被加密。
另一方面，采用了使用数字署名的认证方法的主模式是如图11那样的协议。
根据SIG_I、SIG_R分别是对HASH_I、HASH_R应用了数字署名的结果这一事实，如比较上述2个协议所明确的那样，上述2个协议在本质上是相同的。
因此，以下，一边参照图6一边说明将在安装IKE的情况下必须支持的主模式作为对象，抽出了在主模式中使用了pre-shared key的认证方法和使用了数字署名的认证方法的本质的协议(称为抽象化IKE协议(主模式))。
[抽象化IKE协议(主模式)]
在步骤S601中，IKE的发起方将SA的建议(1个以上的保密关联)发送给应答方。
在步骤S602中，应答方从建议中选择保密关联(一个)，并发送给发起方(如果确定保密关联，则p和g被确定)。
在步骤S603中，发起方将y_i(＝g^(x_i)mod p)和Nonce Ni发送给应答方(x_i是发起方的保密信息)。
在步骤S604中，应答方将y_r(＝g^(x_r)mod p)和Nonce Nr发送给发起方(x_r是应答方的保密信息)。
在步骤S605中，发起方根据从应答方接收到的y_r＝g^(x_r)modp和自己的保密信息x_i计算并求出(g^(x_r))^(x_i)mod p，根据它生成加密的密钥，并使用该密钥将加密了identification payload IDii和HASH_I的数据发送给应答方(根据记载在RFC2409中的方法生成加密的密钥和HASH_I)。
在步骤S606中，应答方根据从发起方接收到的y_i＝g^(x_i)modp和自己的保密信息x_r计算并求出(g^(x_i))^(x_r)mod p，根据它生成加密的密钥，并使用该密钥将加密了identification payload IDii和HASH_R的数据发送给发起方(根据记载在RFC2409中的方法生成加密的密钥和HASH_R)。
一边参照图7一边说明在以上的抽象化IKE协议(主模式)中应用图1的委托计算协议，进行IKE的节点(应答方)兼作委托计算协议的服务器的情况。图7是统一了图1的委托计算协议和图6的抽象化IKE协议(主模式)的协议。应答方对用于求出发起方(通信装置)与应答方(通信对方)共享的y_ir(第1数据)的计算委托进行处理。根据存储在ROM304或HD306中的程序执行该处理。在图7中，记载了在1次的数据传送中包含IKE的数据和委托计算的数据的双方，但即使同时并列地执行2个协议也能得到同样的效果，因此在1次的数据传送中可以不包含双方的数据。此外，发起方和应答方具有图3的构成。应答方的网络接口301(连接链路207的接口)是接收来自发起方(通信装置)的委托的接收装置，是将计算结果发送到发起方(通信装置)的发送装置。另外，应答方的CPU303是进行被委托的计算的计算装置。
假定发起方知道应答方是委托计算服务器并且是用IKE进行IPsec通信的对方，进行了其地址和委托计算服务器的设定。
在步骤S701中，发起方与图1的步骤S101、S102相同，决定随机数r(＝r_1st)、委托计算的参数D和F，并将SA的建议和D发送给应答方。应答方接收用于根据r_1st(第3数据)求出y_1st(第2数据)的D(第一委托)。
在步骤S702中，应答方从建议中选择所使用的保密关联(一个)。由于p和g被确定，因此从它们和D计算Z(其中z_i＝g^(d_i)mod p)，并将选择的保密关联和Z发送给发起方。即，应答方根据D(第一委托)进行第一计算，求出Z(第一计算结果)，并将Z(第一计算结果)发送给发起方。
在步骤S703中，与图1的步骤S106相同，发起者从(F和)Z求出y_1st，再计算y_i。该y_i与图1的步骤S106的y_A(＝y_init*y_1stmod p)相同。y_init与图1相同，被预先准备。另外，与图1的步骤S107相同，根据r_init+r决定委托计算的参数D’和F’。r_init与图1相同，被预先准备。然后，将y_i和Nonce Ni以及D’发送给应答方。应答方接收根据由r_1st(第3数据)和r_init(第7数据)生成的r_init+r_1st(第6数据)求出y_ir(第1数据)的委托D’(第二委托)。
在步骤S704中，应答方决定y_r。与图4的y_A、y_B相同地能够计算该y_r。另外，应答方从y_r和D’计算Z’(其中z_i’＝(y_r)^(d_i’)mod p)。将y_r、Nonce Nr和Z’发送给发起方。即，应答方根据D’(第二委托)计算使用了y_r(第12数据)的第二计算，求出Z’(第二计算结果)，并将Z’(第二计算结果)发送给发起方。
在步骤S705中，发起方从(F’和)Z’求出y_ir。与图1的步骤S111的y_AB相同地能够求出该y_ir。另外，发起方根据y_ir生成加密的密钥，并求出HASH_I(根据记载在RFC2409中的方法生成加密的密钥和HASH_I)。将加密了identification payload IDii和HASH_I的数据发送给应答方。
另一方面，在步骤S706中，应答方求出y_ri。与图4的步骤S404A、S404B相同地能够求出该y_ri。根据y_ri生成加密的密钥，求出HASH_R。将加密了identification payload IDii和HASH_R的数据送给发起方。
通过以上的协议，计算能力小的Ipv6装置和计算能力大的Ipv6装置在进行IKE时，能一边分散负荷一边安全地执行IKE。
此外，在步骤S703中，发起方送送给应答方的D’也能够在步骤S701中传送。
在本实施例中，说明作为将图1中已说明的委托计算协议与IKE统一的协议，委托计算协议的服务器例如在家庭LAN的网关上进行动作的情况。
例如，在从外出的因特网咖啡馆使用PC或便携式终端，或使用工作单位PC，经由因特网访问家庭LAN内部的Ipv6终端时，相当于用IKE进行IPsec通信的情况。这时，家庭LAN内部的Ipv6终端作为IKE的应答方进行动作，但网关(图2的网关202)位于发起方(例如，图2的主机209)和应答方(图2的主机204)之间，对IKE的信息包进行中继，因此能一边使IKE的协议和委托计算的协议相互重合一边提供委托计算服务。网关的网络接口301(连接链路207的接口)是接收来自应答方(通信装置)的委托的接收装置，是将计算结果发送到应答方(通信装置)的发送装置。另外，网关的CPU303是进行被委托的计算的计算装置。
本实施例是在图1的实施例中，向存在于与通信对方之间的服务器委托用于从第3数据r_1st求出第2数据y_1st的委托计算，以及用于从第6数据(r_init+r_1st)求出第1数据y_AB的委托计算的例子。
一边参照图8一边进行说明。网关(服务器)202处理用于求出应答方(通信装置)与发起方(通信对方)共享的y_ri(第1数据)的计算委托。根据被存储在ROM304或HD306中的程序执行该处理。在图8中，记载了在1次的数据传送中包含IKE的数据和委托计算的数据的双方，但即使同时一边使2个协议同步一边执行也能得到同样的效果，因此在1次的数据传送中可以不包含双方的数据。
应答方(例如，图2的主机204)将网关(服务器)202设定为缺省网关并兼作委托计算服务器。假定发起方(例如，图2的主机209)已知道应答方的地址。
在步骤S801中，发起方将SA的建议(1个以上的保密关联)发送给应答方。
在步骤S802中，网关将SA的建议(1个以上的保密关联)从发起方中继到应答方。
在步骤S803中，应答方决定r_1st，求出(r_init+r_1st)，从r_1st决定委托计算的参数D和F，从(r_init+r_1st)决定委托计算的参数D’和F’。此外，r_init与图1相同，被预先准备。然后，从建议中选择使用的保密关联(一个)，将它经由网关发送给发起方，并将它、D和D’发送给网关。
在步骤S804中，网关从选择出的保密关联(p和g被确定)和D计算Z(z_r＝g^(d_r)mod p)。即，网关接收应答方(通信装置)用于从r_1st(第3数据)求出y_1st(第2数据)的D(第一委托)，以及从由r_1st(第3数据)和r_init(第7数据)生成的r_init+r_1st(第6数据)求出y_ri(第1数据)的D’(第二委托)，根据D(第一委托)，进行第一计算，并求出Z(第一计算结果)。
在步骤S805中，网关将选择出的保密关联中继到发起方。此外，步骤S804和步骤S805可以不必按该顺序执行。
在步骤S806中，发起方经由网关将y_i(＝g^(x_i)mod p)和NonceNi发送到应答方(x_i是发起方的保密信息)。
在步骤S807中，网关(为了中继到应答方)根据从发起方接收到的y_i和D’计算Z’(z_r)’＝(y_i)^(d_r’)mod p，即，网关从发起方(通信对方)接收y_i(第12数据)，根据D’(第二委托)，进行使用了y_i(第12数据)的第二计算，求出Z’(第二计算结果)。
在步骤S808中，网关将y_i和Ni中继到应答方，将Z和Z’(第一计算结果和第二计算结果)发送到应答方。
在步骤S809中，应答方与图1的步骤S106相同，从(F和)Z求出y_1st，再计算y_r。该y_r与图1的步骤S106的y_A(＝y_init*y_1st mod p)相同。此外，y_init与图1相同，被预先准备。
在步骤S810中，应答方将y_r和Nonce Nr发送到发起方。
在步骤S810和步骤S814之间应答方从(F’和)Z’计算y_ri，根据y_ri生成加密的密钥，求出HASH_R。与图1的步骤S111的y_AB相同地能够求出该y_ri。
在步骤S811中，网关将y_r和Nonce Nr中继到发起方。
在步骤S812中，发起方根据从发起方接收到的y_r和自己的保密信息x_i求出y_ir(＝(y_r)^(x_i)mod p)，根据y_ir生成加密的密钥，求出HASH_I，将加密了identification payload IDii和HASH_I的数据发送到应答方。
在步骤S813中，网关将加密了identification payload IDii和HASH_I的数据发送到应答方。
在步骤S814中，应答方将加密了identification payload IDir和HASH_R的数据发送到发起方。在该加密中，使用根据y_ri生成的密钥。
在步骤S815中，网关将加密了identification payload IDir和HASH_R的数据中断到发起方。
通过以上的协议，计算能力小的Ipv6装置能一边将网关作为委托计算服务器利用，一边安全地执行IKE。
在本实施例中，说明作为使第1实施例的委托计算协议与IKE组合的协议，将委托计算协议的服务器作为专门提供委托计算的节点设置在因特网上，而且该节点像代理那样进行动作的情况。
例如，因特网上的2个Ipv6装置在进行IKE的Ipsec通信时，作为2个装置共同在该委托计算服务器中进行委托计算并进行IKE的情况，相当于IKE的信息包必定经由该委托计算服务器的情况。在该情况下，委托计算服务器可以看作作为IKE代理进行动作。
本实施例是在图1的实施例中，委托存在于与通信对方之间的服务器进行用于从第3数据r_1st求出第2数据y_1st的委托计算，以及从第6数据(r_init+r_1st)求出第1数据y_AB的委托计算的例子。
此外，本实施例也能够看作是将图7的协议和图8的协议组合起来的协议。就是说，委托计算服务器位于发起方和应答方之间，一边对IKE信息包进行中继一边向发起方和应答方的双方提供委托计算服务。一边参照图9一边进行说明。IKE代理处理用于求出发起方(通信装置)与应答方(通信对方)共享的y_ir(第1数据)的计算委托。另外，IKE代理处理用于求出应答方与发起方共享的y_ri的计算委托。根据被存储在ROM304或HD306中的程序执行该处理。
发起方、应答方以及IKE代理具有图3那样的构成。IKE代理的网络接口301、302是接收来自发起方(通信装置)和应答方的委托的接收装置，是将计算结果发送到发起方(通信装置)和应答方的发送装置。另外，IKE代理的CPU303是进行被委托的计算的计算装置。
在图9中，记载了在1次的数据传送中包含IKE的数据和委托计算的数据的双方，但即使同时一边使2个协议同步一边执行也能得到同样的效果，因此可以在1次的数据传送中不包含双方的数据。
发起方和应答方将IKE-Proxy(服务器)设定为兼作委托计算服务器。假定发起方知道应答方的地址。
在步骤S901中，发起方决定委托计算的参数D_i、F_i、D_i’和F_i’，将SA的建议经由IKE-Proxy发送到应答方。另外，将D_i、D_i’发送到IKE-Proxy。IKE-Proxy接收D_i(第一委托)以及D_i’(第二委托)。此外，与图1相同，D_i(第一委托)是用于从r_1st(第3数据)求出y_1st(第二数据)的委托，D_i’(第二委托)是用于从由r_1st(第3数据)和r_init(第7数据)生成的r_init+r_1st(第6数据)求出y_ri(第1数据)的委托。
在步骤S902中，IKE-Proxy将SA的建议(1个以上的保密关联)从发起方中继到应答方。
在步骤S903中，应答方决定委托计算的参数D_r、F_r、D_r’和F_r’。另外，从建议中选择使用的保密关联(一个)，将保密关联经由IKE-Proxy发送到发起方。另外，将D_r和D_r’发送到IKE-Proxy。
在步骤S904中，IKE-Proxy与图1的步骤S104相同，使用选择出的保密关联(确定了p和g)，从D_i(第一委托)计算Z_i，从D_r计算Z_r。即，IKE-Proxy根据D_i(第一委托)，进行第一计算，并求出Z_i(第一计算结果)。
在步骤S905中，IKE-Proxy将所选择的保密关联和Z_i(第一计算结果)发送到发起方。在步骤S906中，发起方从(F_i和)z_i计算y_i。该y_i相当于图1的步骤S106的y_A(＝y_init*y_1st mod p)。
在步骤S907中，发起方将y_i和Nonce Ni经由IKE-Proxy发送到应答方。
在步骤S908中，IKE-Proxy与图1的步骤S109相同，从由发起方(用于中继到应答方)接收到的y_i和D_r’计算z_r’(z_r’＝(y_i)^(d_r’)mod p)。
在步骤S909中，IKE-Proxy将y_i和Ni中继到应答方，将z_r和z_r’发送到应答方。
在步骤S910中，应答方从(F_r和)Z_r计算y_r。该y_r相当于图1的步骤S106的y_A(＝y_init*y_1st mod p)。
在步骤S911中，应答方将y_r和Nonce Nr经由IKE-Proxy发送到发起方。
在步骤S911和步骤S917之间，应答方从(F_r’和)z_r’计算y_ri，根据y_ri生成加密的密钥，并求出HASH_R。与图1的步骤S111的y_AB相同地能求出该y_ri。
在步骤S912中，IKE-Proxy从由应答方(为了中继到发起方)接收到的y_r和D_i’计算Z_i’(z_i’＝(y_r)^(d_i’)mod p)。即，IKE-Proxy从应答方(通信对方)接收y_r(第12数据)，根据D_i’(第二委托)进行使用了y_r(第12数据)的第二计算，求出Z_i’(第二计算结果)。
在步骤S913中，IKE-Proxy将y_r和Nonce Nr中继到发起方，并将Z_i’(第二计算结果)发送到发起方。
在步骤S914中，发起方根据Z_i’求出y_ir。能够与图1的步骤S111的y_AB同样地求出该y_ir。根据y_ir生成加密的密钥，求出HASH_I。在步骤S915中，发起方用已生成的密钥将加密了identification payload IDii和HASH_I的数据经由IKE-Proxy发送到应答方。
在步骤S916中，IKE-Proxy将加密了identification payload IDii和HASH_I的数据中继到应答方。
在步骤S917中，应答方用根据y_ri生成的密钥将加密了identification payload IDir和HASH_R的数据发送到发起方。
在步骤S918中，IKE-Proxy将加密了identification payload IDir和HASH_R的数据中继到发起方。
通过以上的协议，2台计算能力小的Ipv6装置能一边将IKE-Proxy作为委托计算服务器利用一边安全地执行IKE。此外，即使IKE-Proxy想要执行man-in-the-middle-attack，通过用IKE中所执行的(根据pre-shared key或数字署名的)认证方法检测其攻击，攻击也不会成功。

Claims (20)

1.一种数据共享方法，用于与通信对方共享第1数据，其特征在于：
使用委托计算从第3数据求出第2数据，
通信对方从第2数据和第5数据生成用于求出第1数据的第4数据，
使用委托计算从由第3数据和第7数据生成的第6数据求出与通信对方共享的第1数据。
2.根据权利要求1记载的方法，其特征在于：
在使用委托计算从第3数据求出第2数据的步骤中，根据通过第1变换从第3数据得到的第8数据，使用委托计算求出第9数据，并使用与第1变换对应的第2变换从第9数据生成第2数据，
在使用委托计算从第6数据求出第1数据的步骤中，根据通过第3变换从第6数据得到的第10数据，使用委托计算求出第11数据，使用与第3变换对应的第4变换从第11数据生成第1数据。
3.根据权利要求1记载的方法，其特征在于：
第2数据是用p除g的第3数据次方的余数，
第4数据是用p除第2数据和第5数据的相乘计算结果的余数，
第1数据是用p除第12数据的第6数据次方的余数，
第6数据是第3数据和第7数据的相加计算结果，
第5数据是用p除g的第7数据次方的余数。
4.根据权利要求1记载的方法，其特征在于：
第2数据是第3数据和椭圆曲线上的点P的相乘计算结果，
第4数据是椭圆曲线上的第2数据和椭圆曲线上的第5数据的相加计算结果，
第1数据是第6数据和椭圆曲线上的第12数据的相乘计算结果，
第6数据是第3数据和第7数据的相加计算结果，
第5数据是第7数据和椭圆曲线上的点P的相乘计算结果。
5.根据权利要求1记载的方法，其特征在于：
将用于求出第1共享数据的第2数据和第3数据作为用于求出第2共享数据的第5数据和第7数据使用。
6.根据权利要求1记载的方法，其特征在于：
向通信对方委托用于从第3数据求出第2数据的委托计算以及用于从第6数据求出第1数据的委托计算。
7.根据权利要求1记载的方法，其特征在于：
向存在于与通信对方之间的服务器，委托用于从第3数据求出第2数据的委托计算以及用于从第6数据求出第1数据的委托计算。
8.根据权利要求1记载的方法，其特征在于：
根据第1数据生成在与通信对方的通信中使用的加密密钥。
9.一种数据共享装置，用于与通信对方共享第1数据，其特征在于包括：
使用委托计算从第3数据求出第2数据的委托计算装置；以及
从第2数据和第5数据生成用于通信对方求出第1数据的第4数据的生成装置，其中
所述委托计算装置使用委托计算从由第3数据和第7数据生成的第6数据求出与通信对方共享的第1数据。
10.根据权利要求9记载的装置，其特征在于：
所述委托计算装置在使用委托计算从第3数据求出第2数据的情况下，根据通过第1变换从第3数据得到的第8数据，使用委托计算求出第9数据，使用与第1变换对应的第2变换从第9数据生成第2数据，并在使用委托计算从第6数据求出第1数据的情况下，根据通过第3变换从第6数据得到的第10数据，使用委托计算求出第11数据，并使用与第3变换对应的第4变换从第11数据生成第1数据。
11.根据权利要求9记载的装置，其特征在于：
第2数据是用p除g的第3数据次方的余数，
第4数据是用p除第2数据和第5数据的相乘计算结果的余数，
第1数据是用p除第12数据的第6数据次方的余数，
第6数据是第3数据和第7数据的相加计算结果，
第5数据是用p除g的第7数据次方的余数。
12.根据权利要求9记载的装置，其特征在于：
第2数据是第3数据和椭圆曲线上的点P的相乘计算结果，
第4数据是椭圆曲线上的第2数据和椭圆曲线上的第5数据的相加计算结果，
第1数据是第6数据和椭圆曲线上的第12数据的相乘计算结果，
第6数据是第3数据和第7数据的相加计算结果，
第5数据是第7数据和椭圆曲线上的点P的相乘计算结果。
13.根据权利要求9记载的装置，其特征在于：
将用于求出第1共享数据的第2数据和第3数据作为用于求出第2共享数据的第5数据和第7数据使用。
14.根据权利要求9记载的装置，其特征在于：
根据第1数据生成在与通信对方的通信中使用的加密密钥。
15.一种处理方法，对用于求出通信装置与通信对方共享的第1数据的计算委托进行处理，其特征在于：
通信装置接收用于从第3数据求出第2数据的第一委托以及从由第3数据和第7数据生成的第6数据求出第1数据的第二委托，
根据第一委托进行第一计算，
根据第二委托，进行使用了第12数据的第二计算，
将第一计算结果和第二计算结果发送到通信装置。
16.根据利要求15记载的方法，其特征在于还包括：
从通信对方接收第12数据的接收步骤。
17.根据利要求15记载的方法，其特征在于：
在所述发送步骤中，将第12数据发送到通信装置。
18.一种处理装置，处理用于求出通信装置与通信对方共享的第1数据的计算委托，其特征在于包括：
通信装置接收从第3数据求出第2数据的第一委托以及用于从由第3数据和第7数据生成的第6数据求出第1数据的第二委托的接收装置；
根据第一委托进行第一计算，根据第二委托进行使用了第12数据的第二计算的计算装置；以及
将第一计算结果和第二计算结果发送到通信装置的发送装置。
19.根据权利要求18记载的装置，其特征在于：
所述接收装置从通信对方接收第12数据。
20.根据权利要求18记载的装置，其特征在于：
所述发送装置将第12数据发送到通信装置。
CNB2004100686309A 2003-09-05 2004-09-03 数据共享方法、委托处理方法及装置 Expired - Fee Related CN100546243C (zh)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP314000/2003 2003-09-05
JP2003314000A JP3854954B2 (ja) 2003-09-05 2003-09-05 データ共有装置

Publications (2)

Publication Number Publication Date
CN1592196A true CN1592196A (zh) 2005-03-09
CN100546243C CN100546243C (zh) 2009-09-30

Family

ID=34131899

Family Applications (1)

Application Number Title Priority Date Filing Date
CNB2004100686309A Expired - Fee Related CN100546243C (zh) 2003-09-05 2004-09-03 数据共享方法、委托处理方法及装置

Country Status (4)

Country Link
US (1) US7370070B2 (zh)
EP (1) EP1513286A1 (zh)
JP (1) JP3854954B2 (zh)
CN (1) CN100546243C (zh)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN107707518A (zh) * 2016-08-09 2018-02-16 联想（新加坡）私人有限公司 用于基于事务的消息安全性的设备及方法
CN111492614A (zh) * 2017-12-19 2020-08-04 国际商业机器公司 多因素认证

Families Citing this family (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP5068176B2 (ja) * 2005-01-18 2012-11-07 サーティコム コーポレーション デジタル署名と公開鍵の促進された検証
JP4757591B2 (ja) * 2005-09-29 2011-08-24 株式会社エヌ・ティ・ティ・データ パスワード認証鍵交換装置、システム、方法、及びコンピュータプログラム
US20070211674A1 (en) * 2006-03-09 2007-09-13 Ragnar Karlberg Lars J Auto continuation/discontinuation of data download and upload when entering/leaving a network
US20080137863A1 (en) * 2006-12-06 2008-06-12 Motorola, Inc. Method and system for using a key management facility to negotiate a security association via an internet key exchange on behalf of another device
US8100755B2 (en) 2009-05-11 2012-01-24 Multimedia Games, Inc. Method, apparatus, and program product for distributing random number generation on a gaming network
FR2988942B1 (fr) * 2012-03-27 2015-08-28 Commissariat Energie Atomique Methode et systeme d'etablissement d'une cle de session
DE102012213449A1 (de) * 2012-07-31 2014-02-27 Bundesdruckerei Gmbh Authentifizierung eines Dokuments gegenüber einem Lesegerät
CN110120907B (zh) * 2019-04-25 2021-05-25 北京奇安信科技有限公司 一种基于提议组的IPSec VPN隧道的通信方法及装置

Family Cites Families (30)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5046094A (en) * 1989-02-02 1991-09-03 Kabushiki Kaisha Toshiba Server-aided computation method and distributed information processing unit
US5369708A (en) * 1992-03-31 1994-11-29 Kabushiki Kaisha Toshiba Fast server-aided computation system and method for modular exponentiation without revealing client's secret to auxiliary device
US5491749A (en) * 1993-12-30 1996-02-13 International Business Machines Corporation Method and apparatus for entity authentication and key distribution secure against off-line adversarial attacks
US5657390A (en) * 1995-08-25 1997-08-12 Netscape Communications Corporation Secure socket layer application program apparatus and method
JPH09247416A (ja) * 1996-03-13 1997-09-19 Canon Inc データ通信方法
JPH09284272A (ja) * 1996-04-19 1997-10-31 Canon Inc エンティティの属性情報に基づく暗号化方式、署名方式、鍵共有方式、身元確認方式およびこれらの方式用装置
US6154841A (en) * 1996-04-26 2000-11-28 Canon Kabushiki Kaisha Digital signature method and communication system
JPH09321748A (ja) * 1996-05-27 1997-12-12 Trans Kosumosu Kk 共有暗号鍵による通信システム、同システム用サーバ装置、同システム用クライアント装置、及び通信システムにおける暗号鍵の共有方法
US5987131A (en) * 1997-08-18 1999-11-16 Picturetel Corporation Cryptographic key exchange using pre-computation
US6151395A (en) * 1997-12-04 2000-11-21 Cisco Technology, Inc. System and method for regenerating secret keys in diffie-hellman communication sessions
US6298153B1 (en) * 1998-01-16 2001-10-02 Canon Kabushiki Kaisha Digital signature method and information communication system and apparatus using such method
US6226750B1 (en) * 1998-01-20 2001-05-01 Proact Technologies Corp. Secure session tracking method and system for client-server environment
US6829356B1 (en) * 1999-06-29 2004-12-07 Verisign, Inc. Server-assisted regeneration of a strong secret from a weak secret
US6944762B1 (en) * 1999-09-03 2005-09-13 Harbor Payments Corporation System and method for encrypting data messages
US7359507B2 (en) * 2000-03-10 2008-04-15 Rsa Security Inc. Server-assisted regeneration of a strong secret from a weak secret
US7047408B1 (en) * 2000-03-17 2006-05-16 Lucent Technologies Inc. Secure mutual network authentication and key exchange protocol
US6766453B1 (en) * 2000-04-28 2004-07-20 3Com Corporation Authenticated diffie-hellman key agreement protocol where the communicating parties share a secret key with a third party
WO2001095545A2 (en) * 2000-06-05 2001-12-13 Phoenix Technologies Ltd. Systems, methods and software for remote password authentication using multiple servers
US6990468B1 (en) * 2000-06-19 2006-01-24 Xerox Corporation System, method and article of manufacture for cryptoserver-based auction
US7051199B1 (en) * 2000-06-19 2006-05-23 Xerox Corporation System, method and article of manufacture for providing cryptographic services utilizing a network
JP3918448B2 (ja) * 2001-04-02 2007-05-23 日本ビクター株式会社 エージェントシステムにおける認証方法
US7076656B2 (en) * 2001-04-05 2006-07-11 Lucent Technologies Inc. Methods and apparatus for providing efficient password-authenticated key exchange
US7243366B2 (en) * 2001-11-15 2007-07-10 General Instrument Corporation Key management protocol and authentication system for secure internet protocol rights management architecture
GB2401293B (en) * 2002-01-17 2004-12-22 Toshiba Res Europ Ltd Data transmission links
US7376745B2 (en) * 2002-05-15 2008-05-20 Canon Kabushiki Kaisha Network address generating system, network address generating apparatus and method, program and storage medium
US7565537B2 (en) * 2002-06-10 2009-07-21 Microsoft Corporation Secure key exchange with mutual authentication
CA2502134A1 (en) * 2002-06-19 2004-03-04 Secured Communications, Inc. Inter-authentication method and device
US7039247B2 (en) * 2003-01-31 2006-05-02 Sony Corporation Graphic codec for network transmission
US7480384B2 (en) * 2003-02-10 2009-01-20 International Business Machines Corporation Method for distributing and authenticating public keys using random numbers and Diffie-Hellman public keys
US20050005114A1 (en) * 2003-07-05 2005-01-06 General Instrument Corporation Ticket-based secure time delivery in digital networks

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN107707518A (zh) * 2016-08-09 2018-02-16 联想（新加坡）私人有限公司 用于基于事务的消息安全性的设备及方法
CN107707518B (zh) * 2016-08-09 2020-12-08 联想（新加坡）私人有限公司 用于基于事务的消息安全性的设备及方法
CN111492614A (zh) * 2017-12-19 2020-08-04 国际商业机器公司 多因素认证
CN111492614B (zh) * 2017-12-19 2023-09-01 国际商业机器公司 多因素认证

Also Published As

Publication number Publication date
JP2005086330A (ja) 2005-03-31
EP1513286A1 (en) 2005-03-09
US7370070B2 (en) 2008-05-06
US20050102516A1 (en) 2005-05-12
CN100546243C (zh) 2009-09-30
JP3854954B2 (ja) 2006-12-06

Similar Documents

Publication Publication Date Title
CN1679271A (zh) 基于认证的加密和公共密钥基础结构
JP5349619B2 (ja) アイデンティティベースの認証鍵共有プロトコル
CN1251715A (zh) 有限域离散对数密码系统的割圆多项式结构
CN1773905B (zh) 在安全通信系统中生成匿名公钥的方法、设备和系统
CN1104118C (zh) 计算机支持的在两个计算机之间的密码交换方法
CN1310464C (zh) 一种基于公开密钥体系的数据安全传输的方法及其装置
CN1969501A (zh) 安全地产生共享密钥的系统和方法
CN1457170A (zh) 公钥证明书发行装置
CN1906883A (zh) 实现基于无状态服务器的预共享私密
CN1870499A (zh) 产生新的多变量公钥密码系统的方法
CN1751533A (zh) 在移动无线电系统中形成和分配加密密钥的方法和移动无线电系统
CN1411202A (zh) 一种安全的数字签名系统及其数字签名方法
CN1701573A (zh) 远程访问虚拟专用网络中介方法和中介装置
CN1871810A (zh) 认证系统和远隔分散保存系统
CN1452356A (zh) 公开密钥证书提供装置
CN101079701A (zh) 高安全性的椭圆曲线加解密方法和装置
JP5047638B2 (ja) 暗号文復号権委譲システム
CN1921384A (zh) 一种公钥基础设施系统、局部安全设备及运行方法
Chen Cryptography standards in quantum time: new wine in old wineskin?
CN1921387A (zh) 认证处理方法以及认证处理装置
CN1592196A (zh) 数据共享方法、委托处理方法及装置
CN1650570A (zh) 加密通信系统、其密钥分发服务器、终端设备和密钥共亨方法
JP5457848B2 (ja) Ｉｄベース認証鍵交換システム、認証鍵交換方法、認証鍵交換装置及びそのプログラムと記録媒体
CN1645792A (zh) 通信装置、数字签名发行方法、装置及签名发送方法
CN1905438A (zh) 一种基于标识的组合密钥管理方法和系统

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
C14 Grant of patent or utility model
GR01 Patent grant
CF01 Termination of patent right due to non-payment of annual fee

Granted publication date: 20090930

Termination date: 20160903

CF01 Termination of patent right due to non-payment of annual fee