Tamper-resistant encryption using individual key
(19) AUSTRALIAN PATENT OFFICE (54) Title Tamper-resistant encryption using individual key (51)6 International Patent Classification(s) H04L 009/10 G09C ooi/oo (21) Application No: 2003304629 (22) Application Date: 2003.07.22 (87) WIPONo: WO05/008955 (43) Publication Date : 2005.02.04 (43) Publication Journal Date : 2005.08.18 (71) Applicant(s) Fujitsu Limited (72) Inventor(s) Izu, Tetsuya; Takenaka, Masahiko; Torii, Naoya; Itoh, Kouichi7 (H) Application NoAU 2003304629 A1 (19) AUSTRALIAN PATENT OFFICE (54) Title Tamper-resistant encryption using individual key (51)6 International Patent Classification(s) H04L 009/10 G09C ooi/oo (21) Application No: 2003304629 (22) Application Date: 2003.07.22 (87) WIPONo: WO05/008955 (43) Publication Date : 2005.02.04 (43) Publication Journal Date : 2005.08.18 (71) Applicant(s) Fujitsu Limited (72) Inventor(s) Izu, Tetsuya; Takenaka, Masahiko; Torii, Naoya; Itoh, Kouichi7 An encryption device (10) for performing elliptic encryption processing with a private key, includes: randomizing means (16) for setting, into an initial elliptic point V 0 , an elliptic point R on an elliptic curve that is generated in accordance with a random value; operation means (20) for performing a first operation of summing the initial elliptic point V 0 and a scalar multiple of a particular input elliptic point A on the elliptic curve, V 1 = V 0 + dA, in accordance with a bit sequence of a particular scalar value d for the elliptic encryption processing; de-randomizing means (22) for performing a second operation of subtracting the initial elliptic point V 0 from the sum V 1 determined by the first operation, V = V 1 - V 0 ; and means (24) for providing, as an output, the elliptic point V determined by the de-randomization unit. An encryption device for performing elliptic encryption processing with a private key, comprising:
a randomizing unit for setting, into an initial elliptic point V0, an elliptic point R on an elliptic curve that is generated in accordance with a random value; an operation unit for performing a first operation of summing the initial elliptic point V0 and a scalar multiple of a particular input elliptic point A on the elliptic curve, V1 = V0 + dA, in accordance with a bit sequence of a particular scalar value d for said elliptic encryption processing; a de-randomizing unit for performing a second operation of subtracting the initial elliptic point V0 from the sum V1 determined by said first operation, V = V1 - V0; and a unit for providing, as an output, the elliptic point V determined by said de-randomization unit. An encryption device according to claim 1, wherein said operation unit repeatedly performs the operations of:
- elliptic point addition V[1] :=V[0] + V[2], - elliptic point doubling V[2] :=2V[2], and - substitution V[0] := V[d[i]], An encryption device according to claim 1, wherein said randomizing unit generates a coordinate X of the elliptic point R on the elliptic curve, then generates a coordinate Y of the elliptic point R in accordance with the coordinate X, and then sets, as the initial elliptic point V0, the generated coordinates (X, Y) expressing the elliptic point R. An encryption device according to claim 1, wherein said randomizing unit generates a random value s, then determines a base elliptic point G multiplied by s, and then sets the determined sG as the elliptic point R into the initial elliptic point V0. An encryption device according to claim 4, wherein for the determination of the sG, said randomizing unit sets the infinite elliptic point O as an initial value into the work variable V[0], then sets the G as an initial value into the work variable V[2], and then repeatedly performs the operations of:
- elliptic point addition V[1] := V[0] + V[2], - elliptic point doubling V[2] := 2V[2], and - substitution V[0] := V[d[i]], An encryption device according to claim 4, wherein for the determination of the sG, said randomizing unit sets a random value s as the scalar value d, then sets the input elliptic point A as the base elliptic point G, and then sets the infinite elliptic point O as the elliptic point R, so as to determine sG = O + sG based on said first operation of V1 = V0 + dA. An encryption device according to claim 1, wherein an elliptic point R0 on the elliptic curve generated at first at random is set as the elliptic point R, and thereafter an elliptic point Rn on the elliptic curve expressed by a function Rn = f(Rn-1, c) is used as the elliptic point R, where Rn denotes the n-th time of the elliptic encryption processing, and c indicates a constant. An encryption device according to claim 7, wherein when a previous elliptic point Rn-1 on the elliptic curve is expressed by an elliptic point (RX, RY, RZ) in projective coordinates, a current elliptic point Rn on the elliptic curve is expressed by an elliptic point (c × RX, c × RY, c × RZ) in the projective coordinates. An encryption device according to claim 7, wherein when a previous elliptic point Rn-1 on the elliptic curve is expressed by an elliptic point (RX, RY, RZ) in Jacobian coordinates, a present elliptic point Rn on the elliptic curve is expressed by an elliptic point (c2 × RX, c3 × RY, c × RZ) in the Jacobian coordinates. An encryption device according to claim 2, wherein said elliptic encryption processing is the operation using Jacobian coordinates for elliptic curve parameters over a prime field, where P = V[2] = (Xi, Yi, Zi) = 2iA, wherein
for i = 0, Ri is determined by sequentially performing the operations of Ri := Z02, Ri = Ri2, and Ri := aRi;
for i ≥ 1, Ri is determined by performing the operation of Ri := RiTi-1, where Ti-1 denotes intermediate data for i - 1; and
P = (Xi+1, Yi+1, Zi+1) = 2i+1A is determined by performing, in accordance with the determined Ri, the operations of Mi := 3Xi + Ri, Qi := Yi2, Si := 4XiQi, Ti := 8Qi2, Zi+1 := 2YiZi, Xi+1 := Mi2 - 2Si, and Yi+1 := Mi(Si - Xi) - Ti, in this order or in a different order, and then is outputted as V[2]. An encryption device for performing modular exponentiation encryption processing with a private key, comprising:
a randomizing unit for setting, into an initial value V0, an integer r generated in accordance with a random value; an operation unit for performing a first operation of modular exponentiation V1 = V0ad (mod n) = r × ad (mod n) for the initial value V0 and a particular input value a in accordance with a bit sequence of a particular value d for said modular exponentiation encryption processing; a de-randomizing unit for performing a second operation of modular multiplication V = V1 × r-1 (mod n) on the value V1 determined by said first operation and an inverse element r-1 (mod n) of r (mod n); and a unit for providing, as an output, the value V determined by said de-randomizing unit. An encryption device according to claim 11, wherein said operation unit repeatedly performs the operations of:
- multiplication V[1] := V[0] × V[2] (mod n) - squaring V[2]2 (mod n), and - substitution V[0] := V[d[i]], A program recorded on a recording medium for use in an information processing device and for performing elliptic encryption processing with a private key, said program being operable to effect the steps of:
generating an elliptic point R on an elliptic curve at random that is generated in accordance with a random value; setting the elliptic point R into an initial elliptic point V0; performing a first operation of summing the initial elliptic point V0 and a scalar multiple of a particular input elliptic point A on the elliptic curve, V1 = V0 + dA, in accordance with a bit sequence of a particular scalar value d for said elliptic encryption processing; performing a second operation of subtracting the initial elliptic point V0 from the sum V1 determined by said first operation, V = V1 - V0; and providing, as an output, the elliptic point V determined by said de-randomization unit. A program recorded on a recording medium for use in an information processing device and for performing modular exponentiation encryption processing with a private key,
setting, into an initial value V0, an integer r generated in accordance with a random value;
performing a first operation of modular exponentiation V1 = V0ad (mod n) = r × ad (mod n) for the initial value V0 and a particular input value a in accordance with a bit sequence of a particular value d for said modular exponentiation encryption processing;
performing a second operation of modular multiplication V = V1 × r-1 (mod n) on the value V1 determined by said first operation and an inverse element r-1 (mod n) of r (mod n); and
providing, as an output, the value V determined by said de-randomizing unit. A method for use in an information processing device and for performing elliptic encryption processing with a private key, said method comprising the steps of:
generating an elliptic point R on an elliptic curve at random that is generated in accordance with a random value; setting the elliptic point R into an initial elliptic point V0; performing a first operation of summing the initial elliptic point V0 and a scalar multiple of a particular input elliptic point A on the elliptic curve, V1 = V0 + dA, in accordance with a bit sequence of a particular scalar value d for said elliptic encryption processing; performing a second operation of subtracting the initial elliptic point V0 from the sum V1 determined by said first operation, V = V1 - V0; and providing, as an output, the elliptic point V determined by said de-randomization unit. A method for use in an information processing device and for performing modular exponentiation encryption processing with a private key, said method comprising the steps of:
setting, into an initial value V0, an integer r generated in accordance with a random value; performing a first operation of modular exponentiation V1 = V0ad (mod n) = r × ad (mod n) for the initial value V0 and a particular input value a in accordance with a bit sequence of a particular value d for said modular exponentiation encryption processing; performing a second operation of modular multiplication V = V1 × r-1 (mod n) on the value V1 determined by said first operation and an inverse element r-1 (mod n) of r (mod n); and providing, as an output, the value V determined by said de-randomizing unit.