Encryption operating apparatus and method having side-channel attack resistance

An encryption operating apparatus having side-channel attack resistance, comprising:

• a ciphertext input part for inputting ciphertext X that can be decrypted with secret keys p, q and d;
• a constant storing part for storing a constant C having relationships C>p and C>q with respect to the secret keys p and q;
• a correction value storing part for storing correction values C−dp and C−dq (dp=d mod (p−1), dq=d mod (q−1)) calculated based on the constant;
• a constant multiplying part for multiplying the ciphertext X by the constant C stored in the constant storing part;
• a multiplication result storing part for storing an operation result by the multiplication;
• a remainder operating part for conducting a remainder operation represented by Expression 104 using the secret key p or q as a remainder value with respect to the operation result by the multiplication stored in the multiplication result storing part;
• Xp′=X*C mod p
• Xq′=X*C mod q (104)
• a remainder operation result storing part for storing operation results Xp′ and Xq′ by the remainder operation;
• a Chinese remainder RSA processing part for conducting a modular exponentiation operation based on a Chinese remainder theorem represented by Expression 105 with respect to the operation results Xp′ and Xq′ by the remainder operation stored in the remainder operation result storing part;
• Yp=Xp′dp mod p
• Yq=Xq′dq mod q (105)
• a modular exponentiation operation result storing part for storing operation results Yp and Yq by the modular exponentiation operation;
• a correction processing part for conducting a correction operation represented by Expression 106 by using the correction value C−dp or C−dq stored in the correction value storing part with respect to the operation results Yp and Yq by the modular exponentiation operation stored in the modular exponentiation operation result storing part;
• Yp′=Yp*C−dp mod p
• Yq′=Yq*C−dq mod q (106)
• a correction result storing part for storing operation results Yp′ and Yq′ by the correction operation;
• and
• a plaintext output part for calculating plaintext Y before being encrypted as expressed by Expression 107 based on the operation results Yp′ and Yq′ by the correction operation stored in the correction result storing part,
• Y=(a(Yq′−Yp′)mod q)p+Yp′ (107)
• where a=p−1 mod q
• wherein, even in a case where any of the ciphertext X is input, the secret keys p and q cannot be revealed.

An encryption operating apparatus having side-channel attack resistance, comprising:

• a ciphertext input part for inputting ciphertext X that can be decrypted with secret keys p, q and d;
• a constant storing part for storing constants Cp and Cq having relationships Cp>p and Cq>q with respect to the secret keys p and q;
• a correction value storing part for storing correction values Cp−dp and Cq−dq (dp=d mod (p−1), dq=d mod (q−1)) calculated based on the constants;
• a constant multiplying part for multiplying the ciphertext X by the constants Cp and Cq stored in the constant storing part;
• a multiplication result storing part for storing an operation result by the multiplication;
• a remainder operating part for conducting a remainder operation represented by Expression 108 using the secret key p or q as a remainder value with respect to the operation result by the multiplication stored in the multiplication result storing part;
• Xp′=X*Cp mod p
• Xq′=X*Cq mod q (108)
• a remainder operation result storing part for storing operation results Xp′ and Xq′ by the remainder operation;
• a Chinese remainder RSA processing part for conducting a modular exponentiation operation based on a Chinese remainder theorem represented by Expression 109 with respect to the operation results Xp′ and Xq′ by the remainder operation stored in the remainder operation result storing part;
• Yp=Xp′dp mod p
• Yq=Xq′dq mod q (109)
• a modular exponentiation operation result storing part for storing operation results Yp and Yq by the modular exponentiation operation;
• a correction processing part for conducting a correction operation represented by Expression 110 by using the correction value Cp−dp or Cq−dq stored in the correction value storing part with respect to the operation results Yp and Yq by the modular exponentiation operation stored in the modular exponentiation operation result storing part;
• Yp′=Yp*Cp−dp mod p
• Yq′=Yq*Cq−dq mod q (110)
• a correction result storing part for storing operation results Yp′ and Yq′ by the correction operation;
• and
• a plaintext output part for calculating plaintext Y before being encrypted as expressed by Expression 111 based on the operation results Yp′ and Yq′ by the correction operation stored in the correction result storing part,
• Y=(a(Yq′−Yp′)mod q)p+Yp′(111)
• where a=p−1 mod q
• wherein, even in a case where any of the ciphertext X is input, the secret keys p and q cannot be revealed.

An encryption operating apparatus having side-channel attack resistance, wherein, in a case where a function MONT_EXP for executing a Montgomery modular exponentiation operation is defined by Expression 112:

• R>p
• MONT_EXP(X,d,R,p)=(X*R−1)d mod p (112)
• the apparatus comprising:
• a ciphertext input part for inputting ciphertext X that can be decrypted with secret keys p, q and d;
• a Montgomery parameter multiplying part for multiplying the ciphertext X by a Montgomery parameter R;
• a multiplication result storing part for storing an operation result by the multiplication;
• a remainder operating part for conducting a remainder operation represented by Expression 113 using the secret key p or q as a remainder value with respect to the operation result by the multiplication stored in the multiplication result storing part;
• Xp′=X*R mod p
• Xq′=X*R mod q (113)
• a remainder operation result storing part for storing operation results Xp′ and Xq′ by the remainder operation;
• a Montgomery modular exponentiation operating part for conducting a Montgomery modular exponentiation operation represented by Expression 114 with respect to the operation results Xp′ and Xq′ by the remainder operation stored in the remainder operation result storing part;
• Yp=MONT_EXP(Xp′,dp,R,p)
• Yq=MONT_EXP(Xq′,dq,R,q) (114)
• where dp=d mod(p−1), dq=d mod(q−1)
• a Montgomery modular exponentiation operation result storing part for storing operation results Yp and Yq by the Montgomery modular exponentiation operation;
• and
• a plaintext output part for calculating plaintext Y before being encrypted as expressed by Expression 115 based on the operation results Yp and Yq by the Montgomery modular exponentiation operation stored in the Montgomery modular exponentiation operation result storing part,
• Y=(a(Yq−Yp)mod q)p+Yp (115)
• where a=p−1 mod q
• wherein, even in a case where any of the ciphertext X is input, the secret keys p and q cannot be revealed.

An encryption operating apparatus having side-channel attack resistance, wherein, in a case where a function MONT_EXP for executing a Montgomery modular exponentiation operation is defined by Expression 116:

• R>p
• MONT_EXP(X,d,R,p)=(X*R−1)d mod p (116)
• the apparatus comprising:
• a ciphertext input part for inputting ciphertext X that can be decrypted with secret keys p, q and d;
• a Montgomery parameter multiplying part for multiplying the ciphertext X by a Montgomery parameter Rp or Rq having relationships Rp>p and Rq>q with respect to the secret keys p and q;
• a multiplication result storing part for storing an operation result by the multiplication;
• a remainder operating part for conducting a remainder operation represented by Expression 117 using the secret key p or q as a remainder value with respect to the operation result by the multiplication stored in the multiplication result storing part;
• Xp′=X*Rp mod p
• Xq′=X*Rq mod q (117)
• a remainder operation result storing part for storing operation results Xp′ and Xq′ by the remainder operation;
• a Montgomery modular exponentiation operating part for conducting a Montgomery modular exponentiation operation represented by Expression 118 with respect to the operation results Xp′ and Xq′ by the remainder operation stored in the remainder operation result storing part;
• Yp=MONT_EXP(Xp′,dp,Rp,p)
• Yq=MONT_EXP(Xq′,dq,Rq,q) (118)
• where dp=d mod(p−1), dq=d mod(q−1)
• a Montgomery modular exponentiation operation result storing part for storing operation results Yp and Yq by the Montgomery modular exponentiation operation;
• and
• a plaintext output part for calculating plaintext Y before being encrypted as expressed by Expression 119 based on the operation results Yp and Yq by the Montgomery modular exponentiation operation stored in the Montgomery modular exponentiation operation result storing part,
• Y=(a(Yq−Yp)mod q)p+Yp (119)
• where a=p−1 mod q
• wherein, even in a case where any of the ciphertext X is input, the secret keys p and q cannot be revealed.

An encryption operating apparatus having side-channel attack resistance, wherein, in a case where a function MONT_EXP for executing a Montgomery modular exponentiation operation is defined by Expression 120:

• R>p
• MONT_EXP(X,d,R,p)=(X*R−1)d mod p (120)
• the apparatus comprising:
• a ciphertext input part for inputting ciphertext X that can be decrypted with secret keys p, q and d;
• a Montgomery parameter remainder operation result storing part for storing a result obtained by conducting a remainder operation to a remainder value p or q as represented by Expression 121 with respect to a Montgomery parameter R;
• Rp′=R mod p
• Rq′=R mod q (121)
• a remainder value multiplying part for multiplying the input ciphertext X by an operation result Rp′ or Rq′ by the remainder operation stored in the Montgomery parameter remainder operation result storing part as represented by Expression 122;
• Xp′=X*Rp′
• Xq′=X*Rq′ (122)
• a multiplication result storing part for storing operation results Xp′ and Xq′ by the multiplication;
• a remainder operating part for successively conducting a remainder operation represented by Expression 123 using the secret keys p and q as remainder values with respect to the operation results Xp′ and Xq′ by the multiplication stored in the multiplication result storing part;
• Xp=Xp′mod p
• Xq=Xq′mod q (123)
• a remainder operation result storing part for storing operation results Xp and Xq by the remainder operation;
• a Montgomery modular exponentiation operating part for conducting a Montgomery modular exponentiation operation represented by Expression 124 with respect to the operation results Xp and Xq by the remainder operation stored in the remainder operation result storing part;
• Yp=MONT_EXP(Xp,dp,R,p)
• Yq=MONT_EXP(Xq,dq,R,q) (124)
• where dp=d mod(p−1), dq=d mod(q−1)
• a Montgomery modular exponentiation operation result storing part for storing operation results Yp and Yq by the Montgomery modular exponentiation operation;
• and
• a plaintext output part for calculating plaintext Y before being encrypted as expressed by Expression 125 based on the operation results Yp and Yq by the Montgomery modular exponentiation operation stored in the Montgomery modular exponentiation operation result storing part,
• Y=(a(Yq−Yp)mod q)p+Yp (125)
• where a=p−1 mod q
• wherein, even in a case where any of the ciphertext X is input, the secret keys p and q cannot be revealed.

An encryption operating apparatus having side-channel attack resistance, wherein, in a case where a function MONT_EXP for executing a Montgomery modular exponentiation operation is defined by Expression 127:

• R>p
• MONT_EXP(X,d,R,p)=(X*R−1)d mod p (127)
• the apparatus comprising:
• a ciphertext input part for inputting ciphertext X that can be decrypted with secret keys p, q and d;
• a Montgomery parameter remainder operation result storing part for storing a result obtained by conducting a remainder operation to a remainder value p or q as represented by Expression 128 with respect to a Montgomery parameter Rp or Rq having relationships Rp>p and Rq>q with respect to the secret keys p and q;
• Rp′=Rp mod p
• Rq′=Rq mod q (128)
• a remainder value multiplying part for multiplying the input ciphertext X by an operation result Rp′ or Rq′ by the remainder operation stored in the Montgomery parameter remainder operation result storing part as represented by Expression 129;
• Xp′=X*Rp′
• Xq′=X*Rq′ (129)
• a multiplication result storing part for storing operation results Xp′ and Xq′ by the multiplication;
• a remainder operating part for successively conducting a remainder operation represented by Expression 130 using the secret keys p and q as remainder values with respect to the operation results Xp′ and Xq′ by the multiplication stored in the multiplication result storing part;
• Xp=Xp′mod p
• Xq=Xq′mod q (130)
• a remainder operation result storing part for storing operation results Xp and Xq by the remainder operation;
• a Montgomery modular exponentiation operating part for conducting a Montgomery modular exponentiation operation represented by Expression 131 with respect to the operation results Xp and Xq by the remainder operation stored in the remainder operation result storing part;
• Yp=MONT_EXP(Xp,dp,Rp,p)
• Yq=MONT_EXP(Xq,dq,Rq,q) (131)
• where dp=d mod(p−1), dq=d mod(q−1)
• a Montgomery modular exponentiation operation result storing part for storing operation results Yp and Yq by the Montgomery modular exponentiation operation;
• and
• a plaintext output part for calculating plaintext Y before being encrypted as expressed by Expression 132 based on the operation results Yp and Yq by the Montgomery modular exponentiation operation stored in the Montgomery modular exponentiation operation result storing part,
• Y=(a(Yq−Yp)mod q)p+Yp (132)
• where a=p−1 mod q
• wherein, even in a case where any of the ciphertext X is input, the secret keys p and q cannot be revealed.

An encryption operating method having side-channel attack resistance, comprising:

• inputting ciphertext X that can be decrypted with secret keys p, q and d;
• storing a constant C having relationships C>p and C>q with respect to the secret keys p and q;
• storing correction values C−dP and C−dq (dp=d mod (p−1), dq=d mod (q−1)) calculated based on the constant;
• multiplying the ciphertext X by the stored constant C;
• storing an operation result by the multiplication;
• conducting a remainder operation represented by Expression 134 using the secret key p or q as a remainder value with respect to the stored operation result by the multiplication;
• Xp′=X*C mod p
• Xq′=X*C mod q (134)
• storing operation results Xp′ and Xq′ by the remainder operation;
• conducting a modular exponentiation operation based on a Chinese remainder theorem represented by Expression 135 with respect to the stored operation results Xp′ and Xq′ by the remainder operation;
• Yp=Xp′dp mod p
• Yq=Xq′dq mod q (135)
• storing operation results Yp and Yq by the modular exponentiation operation;
• conducting a correction operation represented by Expression 136 by using the stored correction value C−dp or C−dq with respect to the stored operation results Yp and Yq by the modular exponentiation operation;
• Yp′=Yp*C−dp mod p
• Yq′=Yq*C−dq mod q (136)
• storing operation results Yp′ and Yq′ by the correction operation;
• and
• calculating plaintext Y before being encrypted as expressed by Expression 137 based on the stored operation results Yp′ and Yq′ by the correction operation,
• Y=(a(Yq′−Yp′)mod q)p+Yp′ (137)
• where a=p−1 mod q
• wherein, even in a case where any of the ciphertext X is input, the secret keys p and q cannot be revealed.

An encryption operating method having side-channel attack resistance, comprising:

• inputting ciphertext X that can be decrypted with secret keys p, q and d;
• storing constants Cp and Cq having relationships Cp>p and Cq>q with respect to the secret keys p and q;
• storing correction values Cp−dp and Cq−dq (dp=d mod (p−1), dq=d mod (q−1)) calculated based on the constants;
• multiplying the ciphertext X by the stored constant Cp or Cq;
• storing an operation result by the multiplication;
• conducting a remainder operation represented by Expression 138 using the secret key p or q as a remainder value with respect to the stored operation result by the multiplication;
• Xp′=X*Cp mod p
• Xq′=X*Cq mod q (138)
• storing operation results Xp′ and Xq′ by the remainder operation;
• conducting a modular exponentiation operation based on a Chinese remainder theorem represented by Expression 139 with respect to the stored operation results Xp′ and Xq′ by the remainder operation;
• Yp=Xp′dp mod p
• Yq=Xq′dq mod q (139)
• storing operation results Yp and Yq by the modular exponentiation operation;
• conducting a correction operation represented by Expression 140 by using the stored correction value Cp−dp or Cq−dq with respect to the stored operation results Yp and Yq by the modular exponentiation operation;
• Yp′=Yp*Cp−dp mod p
• Yq′=Yq*Cq−dq mod q (140)
• storing operation results Yp′ and Yq′ by the correction operation;
• and
• calculating plaintext Y before being encrypted as expressed by Expression 141 based on the stored operation results Yp′ and Yq′ by the correction operation,
• Y=(a(Yq′−Yp′)mod q)p+Yp′ (141)
• where a=p−1 mod q
• wherein, even in a case where any of the ciphertext X is input, the secret keys p and q cannot be revealed.

An encryption operating method having side-channel attack resistance, wherein, in a case where a function MONT_EXP for executing a Montgomery modular exponentiation operation is defined by Expression 142:

• R>p
• MONT_EXP(X,d,R,p)=(X*R−1)d mod p (142)
• the method comprising:
• inputting ciphertext X that can be decrypted with secret keys p, q and d;
• multiplying the ciphertext X by a Montgomery parameter R;
• storing an operation result by the multiplication;
• conducting a remainder operation represented by Expression 143 using the secret key p or q as a remainder value with respect to the stored operation result by the multiplication;
• Xp′=X*R mod p
• Xq′=X*R mod q (143)
• storing operation results Xp′ and Xq′ by the remainder operation;
• conducting a Montgomery modular exponentiation operation represented by Expression 144 with respect to the stored operation results Xp′ and Xq′ by the remainder operation;
• Yp=MONT_EXP(Xp′,dp,R,p)
• Yq=MONT_EXP(Xq′,dq,R,q) (144)
• where dp=d mod(p−1), dq=d mod(q−1)
• storing operation results Yp and Yq by the Montgomery modular exponentiation operation;
• and
• calculating plaintext Y before being encrypted as expressed by Expression 145 based on the stored operation results Yp and Yq by the Montgomery modular exponentiation operation,
• Y=(a(Yq−Yp)mod q)p+Yp (145)
• where a=p−1 mod q
• wherein, even in a case where any of the ciphertext X is input, the secret keys p and q cannot be revealed.

An encryption operating method having side-channel attack resistance, wherein, in a case where a function MONT_EXP for executing a Montgomery modular exponentiation operation is defined by Expression 146:

• R>p
• MONT_EXP(X,d,R,p)=(X*R−1)d mod p (146)
• the method comprising:
• inputting ciphertext X that can be decrypted with secret keys p, q and d;
• multiplying the ciphertext X by a Montgomery parameter Rp or Rq having relationships Rp>p and Rq>q with respect to the secret keys p and q;
• storing an operation result by the multiplication;
• conducting a remainder operation represented by Expression 147 using the secret key p or q as a remainder value with respect to the stored operation result by the multiplication;
• Xp′=X*Rp mod p
• Xq′=X*Rq mod q (147)
• storing operation results Xp′ and Xq′ by the remainder operation;
• conducting a Montgomery modular exponentiation operation represented by Expression 148 with respect to the stored operation results Xp′ and Xq′ by the remainder operation;
• Yp=MONT_EXP(Xp′,dp,Rp,p)
• Yq=MONT_EXP(Xq′,dq,Rq,q) (148)
• where dp=d mod(p−1), dq=d mod(q−1)
• storing operation results Yp and Yq by the Montgomery modular exponentiation operation;
• and
• calculating plaintext Y before being encrypted as expressed by Expression 149 based on the stored operation results Yp and Yq by the Montgomery modular exponentiation operation,
• Y=(a(Yq−Yp)mod q)p+Yp (149)
• where a=p−1 mod q
• wherein, even in a case where any of the ciphertext X is input, the secret keys p and q cannot be revealed.

An encryption operating method having side-channel attack resistance, wherein, in a case where a function MONT_EXP for executing a Montgomery modular exponentiation operation is defined by Expression 150:

• R>p
• MONT_EXP(X,d,R,p)=(X*R−1)d mod p (150)
• the method comprising:
• inputting ciphertext X that can be decrypted with secret keys p, q and d;
• storing a result obtained by conducting a remainder operation to a remainder value p or q as represented by Expression 151 with respect to a Montgomery parameter R;
• Rp′=R mod p
• Rq′=R mod q (151)
• multiplying the input ciphertext X by a stored operation result Rp′ or Rq′ by the remainder operation as represented by Expression 152;
• Xp′=X*Rp′
• Xq′=X*Rq′ (152)
• storing operation results Xp′ and Xq′ by the multiplication;
• successively conducting a remainder operation represented by Expression 153 using the secret keys p and q as remainder values with respect to the stored operation results Xp′ and Xq′ by the multiplication;
• Xp=Xp′mod p
• Xq=Xq′mod q (153)
• storing operation results Xp and Xq by the remainder operation;
• conducting a Montgomery modular exponentiation operation represented by Expression 154 with respect to the stored operation results Xp and Xq by the remainder operation;
• Yp=MONT_EXP(Xp,dp,R,p)
• Yq=MONT_EXP(Xq,dq,R,q) (154)
• where dp=d mod(p−1), dq=d mod(q−1)
• storing operation results Yp and Yq by the Montgomery modular exponentiation operation;
• and
• calculating plaintext Y before being encrypted as expressed by Expression 155 based on the stored operation results Yp and Yq by the Montgomery modular exponentiation operation,
• Y=(a(Yq−Yp)mod q)p+Yp (155)
• where a=p−1 mod q
• wherein, even in a case where any of the ciphertext X is input, the secret keys p and q cannot be revealed.

An encryption operating method having side-channel attack resistance, wherein, in a case where a function MONT_EXP for executing a Montgomery modular exponentiation operation is defined by Expression 156:

• R>p
• MONT_EXP(X,d,R,p)=(X*R−1)d mod p (156)
• the method comprising:
• inputting ciphertext X that can be decrypted with secret keys p, q and d;
• storing a result obtained by conducting a remainder operation to the remainder value p or q as represented by Expression 157 with respect to a Montgomery parameter Rp or Rq having relationships Rp>p and Rq>q with respect to the secret keys p and q;
• Rp′=Rp mod p
• Rq′=Rq mod q (157)
• multiplying the input ciphertext X by a stored operation result Rp′ or Rq′ by the remainder operation as represented by Expression 158;
• Xp′=X*Rp′
• Xq′=X*Rq′ (158)
• storing operation results Xp′ and Xq′ by the multiplication;
• successively conducting a remainder operation represented by Expression 159 using the secret keys p and q as remainder values with respect to the stored operation results Xp′ and Xq′ by the multiplication;
• Xp=Xp′mod p
• Xq=Xq′mod q (159)
• storing operation results Xp and Xq by the remainder operation;
• conducting a Montgomery modular exponentiation operation represented by Expression 160 with respect to the stored operation results Xp and Xq by the remainder operation;
• Yp=MONT_EXP(Xp,dp,Rp,p)
• Yq=MONT_EXP(Xq,dq,Rq,q) (160)
• where dp=d mod(p−1), dq=d mod(q−1)
• storing operation results Yp and Yq by the Montgomery modular exponentiation operation;
• and
• calculating plaintext Y before being encrypted as expressed by Expression 161 based on the stored operation results Yp and Yq by the Montgomery modular exponentiation operation,
• Y=(a(Yq−Yp)mod q)p+Yp (161)
• where a=p−1 mod q
• wherein, even in a case where any of the ciphertext X is input, the secret keys p and q cannot be revealed.

A recording medium storing a computer-executable program for implementing an encryption operating method having side-channel attack resistance, the program comprising:

• inputting ciphertext X that can be decrypted with secret keys p, q and d;
• storing a constant C having relationships C>p and C>q with respect to the secret keys p and q;
• storing correction values C−dp and C−dq (dp=d mod (p−1), dq=d mod (q−1)) calculated based on the constant;
• multiplying the ciphertext X by the stored constant C;
• storing an operation result by the multiplication;
• conducting a remainder operation represented by Expression 162 using the secret key p or q as a remainder value with respect to the stored operation result by the multiplication;
• Xp′=X*C mod p
• Xq′=X*C mod q (162)
• storing operation results Xp′ and Xq′ by the remainder operation;
• conducting a modular exponentiation operation based on a Chinese remainder theorem represented by Expression 163 with respect to the stored operation results Xp′ and Xq′ by the remainder operation;
• Yp=Xp′dp mod p
• Yq=Xq′dq mod q (163)
• storing operation results Yp and Yq by the modular exponentiation operation;
• conducting a correction operation represented by Expression 164 by using the stored correction value C−dp or C−dq with respect to the stored operation results Yp and Yq by the modular exponentiation operation;
• Yp′=Yp*C−dp mod p
• Yq′=Yq*C−dq mod q (164)
• storing operation results Yp′ and Yq′ by the correction operation;
• and
• calculating plaintext Y before being encrypted as expressed by Expression 165 based on the stored operation results Yp′ and Yq′ by the correction operation,
• Y=(a(Yq′−Yp′)mod q)p+Yp′ (165)
• where a=p−1 mod q
• wherein, even in a case where any of the ciphertext X is input, the secret keys p and q cannot be revealed.

A recording medium storing a computer-executable program for implementing an encryption operating method having side-channel attack resistance, the program comprising:

• inputting ciphertext X that can be decrypted with secret keys p, q and d;
• storing constants Cp and Cq having relationships Cp>p and Cq>q with respect to the secret keys p and q;
• storing correction values Cp−dp and Cq−dq (dp=d mod (p−1), dq=d mod (q−1)) calculated based on the constants;
• multiplying the ciphertext X by the stored constant Cp or Cq;
• storing an operation result by the multiplication;
• conducting a remainder operation represented by Expression 166 using the secret key p or q as a remainder value with respect to the stored operation result by the multiplication;
• Xp′=X*Cp mod p
• Xq′=X*Cq mod q (166)
• storing operation results Xp′ and Xq′ by the remainder operation;
• conducting a modular exponentiation operation based on a Chinese remainder theorem represented by Expression 167 with respect to the stored operation results Xp′ and Xq′ by the remainder operation;
• Yp=Xp′dp mod p
• Yq=Xq′dq mod q (167)
• storing operation results Yp and Yq by the modular exponentiation operation;
• conducting a correction operation represented by Expression 168 by using the stored correction value Cp−dp or Cq−dq with respect to the stored operation results Yp and Yq by the modular exponentiation operation;
• Yp′=Yp*Cp−dp mod p
• Yq′=Yq*Cp−dq mod q (168)
• storing operation results Yp′ and Yq′ by the correction operation;
• and
• calculating plaintext Y before being encrypted as expressed by Expression 169 based on the stored operation results Yp′ and Yq′ by the correction operation,
• Y=(a(Yq′−Yp′)mod q)p+Yp′ (169)
• where a=p−1 mod q
• wherein, even in a case where any of the ciphertext X is input, the secret keys p and q cannot be revealed.

A recording medium storing a computer-executable program for implementing an encryption operating method having side-channel attack resistance, wherein, in a case where a function MONT_EXP for executing a Montgomery modular exponentiation operation is defined by Expression 170:

• R>p
• MONT_EXP(X,d,R,p)=(X*R−1)d mod p (170)
• the program comprising:
• inputting ciphertext X that can be decrypted with secret keys p, q and d;
• multiplying the ciphertext X by a Montgomery parameter R;
• storing an operation result by the multiplication;
• conducting a remainder operation represented by Expression 171 using the secret key p or q as a remainder value with respect to the stored operation result by the multiplication;
• Xp′=X*R mod p
• Xq′=X*R mod q (171)
• storing operation results Xp′ and Xq′ by the remainder operation;
• conducting a Montgomery modular exponentiation operation represented by Expression 172 with respect to the stored operation results Xp′ and Xq′ by the remainder operation;
• Yp=MONT_EXP(Xp′,dp,R,p)
• Yq=MONT_EXP(Xq′,dq,R,q) (172)
• where dp=d mod(p−1), dq=d mod(q−1)
• storing operation results Yp and Yq by the Montgomery modular exponentiation operation;
• and
• calculating plaintext Y before being encrypted as expressed by Expression 173 based on the stored operation results Yp and Yq by the Montgomery modular exponentiation operation,
• Y=(a(Yq′−Yp′)mod q)p+Yp′ (173)
• where a=p−1 mod q
• wherein, even in a case where any of the ciphertext X is input, the secret keys p and q cannot be revealed.

A recording medium storing a computer-executable program for implementing an encryption operating method having side-channel attack resistance, wherein, in a case where a function MONT_EXP for executing a Montgomery modular exponentiation operation is defined by Expression 174:

• R>p
• MONT_EXP(X,d,R,p)=(X*R−1)d mod p (174)
• the program comprising:
• inputting ciphertext X that can be decrypted with secret keys p, q and d;
• multiplying the ciphertext X by a Montgomery parameter Rp or Rq having relationships Rp>p and Rq>q with respect to the secret keys p and q;
• storing an operation result by the multiplication;
• conducting a remainder operation represented by Expression 175 using the secret key p or q as a remainder value with respect to the stored operation result by the multiplication;
• Xp′=X*Rp mod p
• Xq′=X*Rq mod q (175)
• storing operation results Xp′ and Xq′ by the remainder operation;
• conducting a Montgomery modular exponentiation operation represented by Expression 176 with respect to the stored operation results Xp′ and Xq′ by the remainder operation;
• Yp=MONT_EXP(Xp′,dp,Rp,p)
• Yq=MONT_EXP(Xq′,dq,Rq,q) (176)
• where dp=d mod(p−1), dq=d mod(q−1)
• storing operation results Yp and Yq by the Montgomery modular exponentiation operation;
• and
• calculating plaintext Y before being encrypted as expressed by Expression 177 based on the stored operation results Yp and Yq by the Montgomery modular exponentiation operation,
• Y=(a(Yq′−Yp′)mod q)p+Yp′ (177)
• where a=p−1 mod q
• wherein, even in a case where any of the ciphertext X is input, the secret keys p and q cannot be revealed.

A recording medium storing a computer-executable program for implementing an encryption operating method having side-channel attack resistance, wherein, in a case where a function MONT_EXP for executing a Montgomery modular exponentiation operation is defined by Expression 178:

• R>p
• MONT_EXP(X,d,R,p)=(X*R−1)d mod p (178)
• the program comprising:
• inputting ciphertext X that can be decrypted with secret keys p, q and d;
• storing a result obtained by conducting a remainder operation to a remainder value p or q as represented by Expression 179 with respect to a Montgomery parameter R;
• Rp′=R mod p
• Rq′=R mod q (179)
• multiplying the input ciphertext X by a stored operation result Rp′ or Rq′ by the remainder operation as represented by Expression 180;
• Xp′=X*Rp′
• Xq′=X*Rq′ (180)
• storing operation results Xp′ and Xq′ by the multiplication;
• successively conducting a remainder operation represented by Expression 181 using the secret keys p and q as remainder values with respect to the stored operation results Xp′ and Xq′ by the multiplication;
• Xp=Xp′mod p
• Xq=Xq′mod q (181)
• storing operation results Xp and Xq by the remainder operation;
• conducting a Montgomery modular exponentiation operation represented by Expression 182 with respect to the stored operation results Xp and Xq by the remainder operation;
• Yp=MONT_EXP(Xp,dp,R,p)
• Yq=MONT_EXP(Xq,dq,R,q) (182)
• where dp=d mod(p−1), dq=d mod(q−1)
• storing operation results Yp and Yq by the Montgomery modular exponentiation operation;
• and
• calculating plaintext Y before being encrypted as expressed by Expression 183 based on the stored operation results Yp and Yq by the Montgomery modular exponentiation operation,
• Y=(a(Yq−Yp)mod q)p+Yp (183)
• where a=p−1 mod q
• wherein, even in a case where any of the ciphertext X is input, the secret keys p and q cannot be revealed.

A recording medium storing a computer-executable program for implementing an encryption operating method having side-channel attack resistance, wherein, in a case where a function MONT_EXP for executing a Montgomery modular exponentiation operation is defined by Expression 184:

• R>p
• MONT_EXP(X,d,R,p)=(X*R−1)d mod p (184)
• the program comprising:
• inputting ciphertext X that can be decrypted with secret keys p, q and d;
• storing a result obtained by conducting a remainder operation to the remainder value p or q as represented by Expression 185 with respect to a Montgomery parameter Rp or Rq having relationships Rp>p and Rq>q with respect to the secret keys p and q;
• Rp′=Rp mod p
• Rq′=Rq mod q (185)
• multiplying the input ciphertext X by a stored operation result Rp′ or Rq′ by the remainder operation as represented by Expression 186;
• Xp′=X*Rp′
• Xq′=X*Rq′ (186)
• storing operation results Xp′ and Xq′ by the multiplication;
• successively conducting a remainder operation represented by Expression 187 using the secret keys p and q as remainder values with respect to the stored operation results Xp′ and Xq′ by the multiplication;
• Xp=Xp′mod p
• Xq=Xq′mod q (187)
• storing operation results Xp and Xq by the remainder operation;
• conducting a Montgomery modular exponentiation operation represented by Expression 188 with respect to the stored operation results Xp and Xq by the remainder operation;
• Yp=MONT_EXP(Xp,dp,Rp,p)
• Yq=MONT_EXP(Xq,dq,Rq,q) (188)
• where dp=d mod(p−1), dq=d mod(q−1)
• storing operation results Yp and Yq by the Montgomery modular exponentiation operation;
• and
• calculating plaintext Y before being encrypted as expressed by Expression 189 based on the stored operation results Yp and Yq by the Montgomery modular exponentiation operation,
• Y=(a(Yq−Yp)mod q)p+Yp (189)
• where a=p−1 mod q
• wherein, even in a case where any of the ciphertext X is input, the secret keys p and q cannot be revealed.