METHOD FOR CALCULATING A TRANSITION FROM A BOOLEAN MASKING TO AN ARITHMETIC MASKING

Abstract

A method is provided for re-masking from a Boolean mask to an arithmetic mask with a modulus (2m*p), in which m is an integer greater than or equal to zero, and p has at least one prime divisor unequal to 2, so that a carry is generated. The carry is masked or balanced to protect it against intrusion attacks.

Claims

1.-12. (canceled)

13. A method for intrusion-resistant re-masking of a value x to be kept secret from a first masking to a second masking, by carrying out a plurality of successive calculation steps, wherein the secret value x: exists in the first masking, before the execution of the plurality of calculation arithmetic steps, as a first representation xs masked with a first mask s according to a Boolean masking rule xs=x XOR s mod 2n, where 2n is the modulus of the first masking rule, where n is an integer, and in the second masking, after the execution of the plurality of consecutive calculation steps, exists as a second representation xr masked according to an arithmetic masking rule with a second mask r, wherein: xr=(x+r) mod (2m*p) or xr=(x?r) mod (2m*p), where (2m*p) is the modulus of the second masking rule and m is an integer greater than or equal to zero, where p has at least one prime divisor unequal to 2; and during the re-masking, at least one arithmetic calculation step is carried out, in which a carry c1 is generated over 2n, the carry c1 being protected against intrusion attacks by masking or balancing the carry c1 by means of a random information item pm, and in a subsequent calculation step in which the carry c1 is intended for use, the masked carry C_pm or the balanced car-ry C is used instead of the carry.

14. The method according to claim 13, wherein the carry c1 is masked by means of the random information pm, by processing the carry c1 by means of an XOR operation with the random information pm to c1 pm=c1 XOR pm, and c1pm is used as the masked carry C_pm, or the masked carry C_pm is derived from c1pm.

15. The method according to claim 13, wherein the carry c1 is balanced by means of random information pm, by representing the secret value x in the second masking as either xr=(x+r) mod (2n*p) or xr=(x?r) mod (2n*p), selected at random under the control of the random information pm, where-in the balanced carry c1 is used as the carry C or the carry C can be derived from the balanced carry c1.

16. The method according to claim 14, wherein the carry C_pm or C by means of a random number z_p, 0<=z_p<p, is additively masked and then reduced, wherein an intermediate result sum1zp_p is generated, and wherein in subsequent steps further calculations use the intermediate result sum1zp_p instead of the carry C_pm or C.

17. The method according to claim 16, in conjunction with 3, wherein the second mask r is iteratively calculated according to a procedure comprising the following steps: calculating MAX_p=2n mod p and MAX_p2=2n+2*p?MAX_p once only; selecting a random number z1, 0<=z1<2n, selecting a random number z_p, 0<=z_p<p; selecting a random bit pm, the value of which is randomly controlled as either 0 or 1; performing the following steps: TABLE-US-00005 1. sz1 = z1 XOR s 2. xz1 = xs XOR sz1 3. xsz1 = xs XOR z1 4. If pm == 0: a. add1 = sz1 + 2n b. sub1c= add1 ? z1 else: a. add1 = z1 + 2n b. sub1c= add1 ? sz1 5. c1 = sub1c >> n 6. sub1 = sub1c mod 2n 7. add2 = xsz1 + 2n 8. sub2c = add2 ? xz1 9. c2 = sub2c >> n 10. sub2 = subc2 mod 2n 11. xor1 = sub1 XOR s 12. r_low = xor1 XOR sub2 13. C = c1 XOR c2 14. sum1 = (p ? C*MAX_p) 15. sum1zp = sum1 + z_p 16. sum1zp_p = sum1zp mod p 17. p_z_p = p ? z_p 18. sum2 = r_low + sum1zp_p 19. p_sum2 = MAX_p2 ? sum2 20. If pm == 0: a. xr = xs + z_p b. r = sum2 else: a. xr = xs + p_z_p b. r = p_sum2.

18. The method according to claim 16, in conjunction with 3, wherein the second mask r is iteratively calculated according to a procedure comprising the following steps: calculating MAX_p=2n mod p and MAX_p2=2n+2*p?MAX_p once only; selecting a random number z1, 0<=z1<2n, selecting a random number z_p, 0<=z_p<p; selecting a random bit pm, the value of which is randomly controlled as either 0 or 1; performing the following steps: TABLE-US-00006 1. sz1 = z1 XOR s 2. xz1 = xs XOR sz1 3. xsz1 = xs XOR z1 4. If pm == 0: a. add1 = xz1 + 2n b. sub1c= add1 ? sz1 else: a. add1 = sz1 + 2n b. sub1c= add1 ? xz1 5. c1 = sub1c >> n 6. sub1 = sub1c mod 2n 7. add2 = xsz1 + 2n 8. sub2c = add2 ? z1 9. c2 = sub2c >> n 10. sub2 = subc2 mod 2n 11. xor1 = sub1 XOR xs 12. xr_low = xor1 XOR sub2 13. C = c1 XOR c2 14. sum1 =(p ? C*MAX_p) 15. sum1zp = sum1 + z_p 16. sum1zp_p = sum1zp mod p 17. p_z_p = p ? z_p 18. sum2 = xr_low + sum1zp_p 19. p_sum2 = MAX_p2 ? sum2 20. If pm == 0: a. r = s + p_z_p b. xr = sum2 else: a. r = s + z_p b. xr = p_sum2.

19. The method according to claim 16, in conjunction with 2, wherein the second mask r is iteratively calculated according to a procedure comprising the following steps: calculating MAX_p=2n mod p and MAX_p2=2n+2*p?MAX_p once only; selecting a random number z1, 0<=z1<2n, selecting a random number z_p, 0<=z_p<p; selecting a random bit pm, the value of which is randomly controlled as either 0 or 1; performing the following steps, comprising a step of masking the carry c1, 14.c1pm=c1 XOR pm: TABLE-US-00007 1. sz1 = z1 XOR s 2. xz1 = xs XOR sz1 3. xsz1 = xs XOR z1 4. add1 = sz1 + 2n 5. sub1c = add1 ? z1 6. c1 = sub1c >> n 7. sub1 = sub1c mod 2n 8. add2 = xsz1 + 2n 9. sub2c = add2 ? xz1 10. c2 = sub2c >> n 11. sub2 = subc2 mod 2n 12. xor1 = sub1 XOR s 13. r_low = xor1 XOR sub2 14. c1pm = c1 XOR pm 15. C_pm = c1pm XOR c2 16. sum 1 = (p ? C_pm*MAX_p) 17. sum1zp = sum1 + z_p 18. sum1zp_p = sum1zp mod p 19. p_ sum1zp_p = p ? sum1zp_p 20. p_z_p = p ? z_p 21. r_low_p = r_low + p 22. sum2 = r_low_p ? pm * MAX_p 23. If pm == 0: a. xr = xs + z_p b. r = sum2 + sum1zp_p else: a. xr = xs + p_z_p b. r = sum2 + p_sum1zp_p .

20. The method according to claim 16, in conjunction with 2, wherein the second mask r is iteratively calculated according to a procedure comprising the following steps: calculating MAX_p=2n mod p and MAX_p2=2n+2+p?MAX_p once only; selecting a random number z1, 0<=z1<2n, selecting a random number z_p, 0<=z_p<p; selecting a random bit pm, the value of which is randomly controlled as either 0 or 1; performing the following steps, comprising a step of masking the carry c1, 14.c1pm=c1 XOR pm: TABLE-US-00008 1. sz1 = z1 XOR s 2. xz1 = xs XOR sz1 3. xsz1 = xs XOR z1 4. add1 = xsz1 + 2n 5. sub1c = add1 ? sz1 6. c1 = sub1c >> n 7. sub1 = sub1c mod 2n 8. add2 = xsz1 + 2n 9. sub2c = add2 ? z1 10. c2 = sub2c >> n 11. sub2 = subc2 mod 2n 12. xor1 = sub1 XOR xs 13. xr_low = xor1 XOR sub2 14. c1pm = c1 XOR pm 15. C_pm = c1pm XOR c2 16. sum1 = (p ? C_pm*MAX_p) 17. sum1zp = sum1 + z_p 18. sum1zp_p = sum1zp mod p 19. p_ sum1zp_p = p ? sum1zp_p 20. p_z_p = p ? z_p 21. xr_low_p = xr_low + p 22. sum2 = xr_low_p ? pm * MAX_p 23. If pm == 0: a. r = s + p_z_p b. xr = sum2 + sum1zp_p else: a. r = s + z_p b. xr = sum2 + p_sum1zp_p .

21. The method according to claim 17, comprising the further step 21, or step 24, of performing a modular reduction of the masked value xr and the mask r according to $a.\mathrm{xr\_p}=\mathrm{xr}\mathrm{mod}p$ $b.\mathrm{r\_p}=r\mathrm{mod}p.$

22. A key-derivation method, designed as a DH or ECDH key-derivation method or similar key-derivation method, comprising a method according to claim 13.

23. A machine-readable travel document comprising an integrated circuit, which is configured for a key-derivation method according to claim 22, and an interface for communication with a reader.

24. A reader comprising a reader circuit and an interface for communication with a machine-readable travel document and configured for reading a machine-readable travel document according to claim 23.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0061] In the following the invention is explained in further detail based on exemplary embodiments and by reference to the drawings, in which:

[0062] FIG. 1 shows a system for illustrating the invention.

DETAILED DESCRIPTION OF THE EXEMPLARY EMBODIMENTS

[0063] FIG. 1 shows a machine-readable travel document 1 with an integrated circuit 2 and an interface designed as an antenna 3, which is or can be connected to the integrated circuit 2. The integrated circuit 2 is configured for the PACE protocol. The PACE protocol comprises a key derivation method in which the method according to the invention is integrated. The machine-readable travel document 1 can be read out with a suitably configured reader 4, which has a reader circuit 5 and an interface 6, e.g. a corresponding antenna. Such readers 4 for machine-readable travel documents such as the machine-readable travel document 1 are arranged, for example, at control stations such as airports or border crossings.