Methods and systems for determining the authenticity of a component using elliptic-curve cryptography
Method of determining authenticity of an item using an elliptic curve E defined over a finite field F q , where q is an integer, the method comprising: generating a random integer j, where the random integer j is in the interval of one to the integer q; calculating a point T=j·S, where point S is a point on elliptic curve E(F q ); calculating a binary value k which is equal to the binary random integer j with a bitmask m applied thereto; sending point T and binary value k to the item; and the item iteratively calculating point U=n·S for different values of integer n, where for each iterative calculation integer n takes different values, wherein for each iteration: the bits of binary integer n corresponding to the unmasked bits of bitmask m are the same as the corresponding bits of binary random integer j; and the bits of binary integer n corresponding to the masked bits of bitmask m are varied in each iteration.
1. A method of determining the authenticity of a replaceable toner cartridge in a printing device using an elliptic curve E defined over a finite field F q , where q is an integer, the method comprising:
the printing device generating a random integer j, where the random integer j is in the interval of one to the integer q;
the printing device calculating a point T=j·S, where point S is a point on elliptic curve E(F q );
the printing device calculating a binary value k which is equal to the binary random integer j with a bitmask m applied thereto;
the printing device sending point T and binary value k to the replaceable toner cartridge; and
the replaceable toner cartridge iteratively calculating point U=n·S for different values of integer n, where for each iterative calculation integer n takes different values, wherein for each iteration:
the bits of binary integer n corresponding to the unmasked bits of bitmask m are the same as the corresponding bits of binary random integer j; and
the bits of binary integer n corresponding to the masked bits of bitmask m are varied in each iteration.
2. The method of claim 1 , further comprising:
the printing device requesting a response from the replaceable toner cartridge;
the replaceable toner cartridge responding by returning at least part of the current value of the integer n to the printing device;
the printing device comparing the at least part of the integer n received from the replaceable toner cartridge with the corresponding part of random integer j.
3. The method of claim 2 , wherein upon a determination that the at least part of the integer n received from the replaceable toner cartridge is the same as the corresponding part of random integer j, the replaceable toner cartridge is identified as an authentic component, and wherein upon a determination that the at least part of the integer n received from the replaceable toner cartridge is different from the corresponding part of random integer j, the replaceable toner cartridge is identified as a non-authentic component.
4. The method of claim 2 , wherein the printing device requests the response from the replaceable toner cartridge after a predetermined time has elapsed.
5. The method of claim 1 , wherein the iterative calculation by the replaceable toner cartridge stops when U=T.
6. The method of claim 1 , wherein the bits of binary value k corresponding to the unmasked bits of bitmask m are the same as the corresponding bits of binary random integer j, and wherein the bits of binary value k corresponding to the masked bits of bitmask m are masked bits.
7. The method of claim 1 , wherein in the step of calculating the binary value k the bitmask m masks one or more of the least significant bits of the binary random integer j to give binary value k.
8. The method of claim 7 , wherein in the step of calculating the binary value k the bitmask m masks sixteen of the least significant bits of the binary random integer j to give binary value k.
9. The method of claim 7 , wherein for iteratively calculating point U comprises adding point S to the point U of the previous iteration.
10. The method of claim 1 , wherein bits in the bitmask m with a value of zero are masked bits of bitmask m and bits in the bitmask m with a value of one are unmasked bits of bitmask m, and wherein binary value k=binary random integer j AND bitmask m.
11. The method of claim 10 , wherein for each iterative calculation performed by the replaceable toner cartridge the binary integer n=binary value k OR binary value o, where binary value o AND bitmask m=0.
12. The method of claim 1 , wherein bits in the bitmask m with a value of one are masked bits of bitmask m and bits in the bitmask m with a value of zero are unmasked bits of bitmask m, and wherein binary value k=binary random integer j OR bitmask m.
13. The method of claim 12 , wherein for each iterative calculation performed by the replaceable toner cartridge the binary integer n=binary value k AND binary value o, where binary value o OR bitmask m=binary 1111 . . . 1.
14. The method of claim 1 , comprising the printing device saving at least part of random integer j to memory of the printing device.
15. A printing system comprising:
a printing device; and
a replaceable toner cartridge communicatively connectable to the printing device,
wherein the printing device is configured to determine the authenticity of the replaceable toner cartridge using an elliptic curve E defined over a finite field F q , where q is an integer, by
generating a random integer j, where the random integer j is in the interval of one to the integer q;
calculating a point T=j·S, where point S is a point on elliptic curve E (F q );
calculating a binary value k which is equal to the binary random integer j with a bitmask m applied thereto; and
sending point T and binary value k to the replaceable toner cartridge, and wherein the replaceable toner cartridge is configured to:
iteratively calculate point U=n· S for different values of integer n, where for each iterative calculation integer n takes different values, wherein for each iteration:
the bits of binary integer n corresponding to the unmasked bits of bitmask m are the same as the corresponding bits of binary random integer j; and
the bits of binary integer n corresponding to the masked bits of bitmask m are varied in each iteration.
16. The printing system of claim 15 , wherein the printing device is configured to request a response from the replaceable toner cartridge, wherein the replaceable toner cartridge is configured to respond by returning at least part of the current value of the integer n to the printing device, and wherein the printing device is configured to compare the at least part of the integer n received from the replaceable toner cartridge with the corresponding part of random integer j.
17. The printing system of claim 16 , wherein upon a determination that the at least part of the integer n received from the replaceable toner cartridge is the same as the corresponding part of random integer j, the replaceable toner cartridge is identified as an authentic component, and wherein upon a determination that the at least part of the integer n received from the replaceable toner cartridge is different from the corresponding part of random integer j, the replaceable toner cartridge is identified as a non-authentic component.
18. The printing system of claim 16 , wherein the printing device is configured to request the response from the replaceable toner cartridge after a predetermined time has elapsed.
19. The printing system of claim 15 , wherein the replaceable toner cartridge is configured such that the iterative calculation by the replaceable toner cartridge stops when U=T.
20. The printing system of claim 15 , wherein the bits of binary value k corresponding to the unmasked bits of bitmask m are the same as the corresponding bits of binary random integer j, and wherein the bits of binary value k corresponding to the masked bits of bitmask m are masked bits.