Category: object is technical – yes

Masking a private key/CERTICOM – T 0556/ 14 – 28 July 2016

In this decision in a patent a method of masking a privat key is claimed. It is considered not to be a mathematical method as such, because storing on a smartcard (hardware) was claimed. The claimed method achieves some protection against power analysis attacks and thus have a technical effect. An inventive step is acknowledged if, having regard to the state of the art, the invention is not obvious to a person skilled in the art. It is not necessary that the invention is a technical improvement over the prior art. The claimed method is an alternative approach compared to the closest prior art and is not suggested.

Object of the Invention:

  • the invention relates to a method for masking a private key used in cryptographic operations on a security token such as a smartcard against power analysis attacks
  • the security of cryptographic systems relies on a particular piece of information being kept secret, and power analysis attacks try to extract information about the secret by statistically analysing the power consumption of the security token when carrying out the cryptographic operation
  • the attacker of the power analysis attack considers the security token “to be a black box which contains a known algorithm and an unknown key” and in order to obtain the required statistical information, repeatedly executes the algorithm with varying parameters under his control
  • masking is, roughly speaking, a technique of randomising the calculations carried out in each instance of the cryptographic algorithms, so that their result remains the same but no relevant statistical information about the key can be gathered by repeated execution
  • first a private key d, which in elliptic curve cryptography is multiplied with a point P to derive a public key Q = dP, is “divided” into a plurality of parts
  • specifically disclosed is a division into two parts b1 and b2 such that d = b1 + b2
  • then a random number π is generated and the values of the parts are updated as b1 = b1 + π mod n and b2 = b2 – π mod n, where n is the number of points on the elliptic curve used
  • the cryptographic operation, in which the private key is “used”, is then carried out by “utilizing” the individual and modified “new parts”

Board I (Art. 52 (2) and (3) EPC):

  • due to the express reference in claim 1 to a smart card on which the key parts and also the new parts are stored, the claimed method of masking is not a mathematical method as such (Claim 1: A method […] storing the new parts on the smart card […])
  • due to the reference to the smart card and in view of the description the skilled person would understand the claimed masking operation to be an automated one to be carried out on the smart card

Board II (technical effect of masking)

  • central to any masking method is the modification of a mathematical method in such a way that its repeated execution is less prone to a statistical analysis revealing the properties of a secret
  • since the result of the computation must not change, this means that masking, in essence, relies on replacing one mathematical method by another which has an equivalent result
  • however, the modified computation is meant to be better protected against power analysis (or other sidechannel) attacks when carried out on hardware
  • as such, the idea of masking is well-established in the art as a protection against such attacks
  • the board accepts as a technical problem the protection of a cryptographic computation against power analysis attacks – if, and only if, the computation is actually carried out on hardware and thus open to such attacks
  • claim 1 specifies a masking method carried out on hardware
  • even though claim 1 literally specifies only the storage of the key parts on a smart card, in the board’s view the skilled person can only understand the method of claim 1 as a fully computer-implemented method
  • the claimed randomisation steps, namely the calculation of two randomised key parts and the computation of Q = b1P + b2P instead of Q = dP, does achieve some protection against power analysis attacks and thus have a technical effect
  • à mathematical steps contribute to the technical character of claim 1

Board III (inventive step)

  • the differences between the claimed matter and D2 (closest prior art) are
    • that D2 relates to RSA (Rivest-Shamir-Adleman = public-key cryptosystem) whereas claim 1 relates to elliptic curve cryptography (ECC), and
    • the masking of the secret by randomised splitting
  • the problem solved by the invention over D2 can therefore be considered as adapting the masking method of D2 to other cryptographic operations particular side channel attacks

Respondent I (inventive step)

  • the randomised splitting steps do not make the claimed method more efficient than the one according to D2
  • on the contrary, in fact: while the method of D2 masks the given calculation by the addition of one multiplication and one addition, the claimed method would be adding two multiplications and one addition and thus be less efficient

Board IV (inventive step)

  • the disadvantage of a method may be outweighed by an advantage it may also have
  • for instance, a slower method might have a statistically significant protective advantage against particular side channel attacks
  • the board hastens to add that the patent contains no detail whatsoever that might allow a judgement or even a sophisticated guess as to the relative security of the proposed measure against any particular power analysis attack
  • however, the board considers that the comparison between the claimed method and that of D2 cannot be reduced to the number of additions and multiplications
  • inventive step is acknowledged if, having regard to the state of the art, the invention is not obvious to a person skilled in the art
  • it is not necessary that the invention is a technical improvement over the prior art
  • the claimed randomized splitting and the adding of an “effective zero” according to D2 are alternative approaches and that the change from the latter to the former is not suggested by the change from ECC to RSA
  • the respondent has also not put forward any fundamental mathematical considerations which would, to the board’s satisfaction, suggest this change
  • the respondent was not able to convince the board that the skilled person starting from D2 would be led, in an obvious way, to the randomized split according to the invention
  • –> the claimed method shows the required inventive step over D2

Conclusion:

There are all necessary elements which are necessary that the mathematical method is considered for inventive step at the EPO:

  • a mathematical method
  • a use: computer implementation of the mathematical method on a smartcard
  • the use is technical: because it contributes to a technical effect, namely the protection of a cryptographic computation against power analysis attacks – if, and only if, the computation is actually carried out on hardware and thus open to such attacks

Koprozessor zur modularen Inversion/GIESECKE & DEVRIENT – T 2318/08 – 23. Mai 2012

This decision provides a known cryptographic coprocessor and a known Euclidean method. However, it is not known how to use free bit sections in the coprocessor to speed up the method. Therefore, the clever use of a known coprocessor to speed up the implementation of an equally known method solves a technical problem.

Object of the Invention:

  • the invention relates to a method for calculating the modular inverse of a value u to a modulus v, which is relevant in cryptographic methods
  • the invention is based on a known extended Euclidean method for calculating the modular inverse
  • the core idea of the method is not to represent the output values u and v “right-aligned” in the low-order bit positions as usual, but to shift them to higher-order positions to such an extent that space is created in the low-order positions for the other parameters of the method
  • only the calculation steps of the standard Euclidean method need to be carried out on the modified representation in order to obtain the results of the extended method
  • the new method therefore requires fewer calculation steps than the extended Euclidean method, but at the cost of a longer bit length for the input values
  • the practical relevance of the method results from the following observations:
    • in cryptographic practice, modular inversion is typically performed with a coprocessor designed for operations on integers, whose bit length in turn depends on the usual key length in RSA (= Rivest-Shamir-Adleman = public-key cryptosystem)
    • the so-called EC methods (= Elliptic Curve), which are an alternative to RSA, use significantly shorter keys so that modular inversion only has to be carried out for smaller numbers
    • accordingly, if a coprocessor optimised for RSA is used for EC, a part of its bit system remains unused
    • the method according to the invention utilises these already existing surplus bits to accelerate the desired method

Board:

  • the skilful use of a known coprocessor to accelerate the implementation of an equally known method solves a technical problem and can therefore in principle fulfil the requirements of Article 56 EPC
  • the examining division based its rejection on the fact that the subject-matter of independent claim 1 could not, according to its wording at the time, be said to provide a solution to this technical problem
  • to this end, it lacked, on the one hand, the limitation to a coprocessor “intended for integer calculations with at least the increased bit length” and, on the other hand, the indication that the auxiliary variables were carried in the low-order bits of the increased bit length
  • the present claim 1 is now limited as claimed:
    • the claimed coprocessor is “provided” for a bit length greater than that required for the input values u and v
    • according to the claim, the surplus bits are utilised by shifting u and v into higher “bit sections” by multiplication by an expansion factor, and introducing “disturbances” into the low-order bit sections thus freed up, which serve as output values for auxiliary variables of the subsequent calculation
  • from the fact that, on the one hand, cryptographic coprocessors and, on the other hand, the Euclidean method and its variants are known, it only follows that the implementation of Euclidean methods on cryptographic coprocessors would be obvious to the skilled person
  • however, this does not indicate that free bit sections in such a coprocessor can be used in the claimed manner to accelerate the method
  • –> inventive

Edge Detection – T 0165/ 12 – 6 July 2017

In this decision, the Board found that the description of the main request did not support the claim, as the description disclosed only one specific example of a merely general feature (“first phase congruency component”). In an auxiliary request, the appellant overcame this rejection, but the claimed subject-matter is still considered not to be inventive (but technical), since the choice of one out of the 3 straightforward possibilities – mentioned in the decision – for increasing the number of edge pixels does not involve an inventive step.

Object of the Invention:

  • method for edge detection of an image
  • the method categorises pixels in the image as edge pixels or non-edge pixels

Board I (support by the description – main request):

  • in the application itself, no different way to determine the phase congruency at a pixel is disclosed than to calculate the ratio between the local energy at the pixel and the sum of Fourier components
  • also in the statement of grounds the appellant provided no additional example and, thus, failed to support its view that a different phase congruency component could be used
  • hence, it is a mere allegation that other “first phase congruency components” could be used
  • according to the established jurisprudence of the boards of appeal, the requirement of 84 EPC means that the subject-matter of the claim must be taken from the description and it is not admissible to claim something that is not described
  • in decision T 94/05, in particular, the board pointed out that the requirement for the claims to be supported by the description was intended to ensure that the extent of protection as defined by the patent claims corresponds to the technical contribution of the disclosed invention to the art
  • therefore the claims must reflect the actual contribution to the art in such a way that the skilled person is able to perform the invention in the entire range claimed
  • the skilled person, at least after reading the patent specification, taking account of his common general knowledge, and possibly also after carrying out normal experiments, must actually be provided with at least a plurality of different embodiment variants
  • in the present case, the use of the term “first phase congruence component” leaves it open, what other embodiments besides the “local energy” are envisaged
  • –> there is not enough support in the description for using the broad term “first phase congruency component” in the independent claims instead of the only embodiment disclosed in the specification, i.e. the “local energy”

Board II (inventive step – auxiliary request):

  • technical effect disclosed in the application is: “This allows for pixels that fail the phase congruency test, to be counted as edge pixels if their local energy satisfies the phase congruency component criteria.“
  • a person skilled in the art recognizing that a first method for edge detection does not result in an expected number of edge pixels evidently has three straightforward possibilities to increase the number of edge pixels:
    1. by using another – better – method for edge detection
    2. by adapting the first method for edge detection (for instance by reducing a respective threshold that distinguishes between non-edge pixels and edge pixels)
    3. by using a further known method for edge detection, which provides different results (i.e. additional edge pixels) than the first method and combining the results of both methods
  • for instance, an example for an algorithm using different methods for detecting different kind of edges is disclosed in D3
  • choosing one out of these straightforward possibilities does not involve an inventive step
  • the Board does not see an inventive step in using the local energy method for finding additional edge pixels that were missed by the first method (as claimed) as compared to rejecting edge pixels by using the local energy method that were found by the first method, but should not be considered as edge pixels (as disclosed in D1)
  • this is considered a mere implementation detail, depending on the choice of criteria of the first method, which might cause too many or not enough edge pixels

Character Recognition – T 135/92 – 15 May 1992

This decision concerns a method for image data. The competent chamber considers the object and solution to be technical.

Object of the Invention:

  • automatic scanning and identification of unknown characters (of image data)
  • in a first stage, different sets of logic tests are used for the identification of characters; were a character not to be identified by the said logic tests, the character would be tested in the second stage by logic tests which are discrete from the tests of the first stage

Board:

  • problem to be solved is to identify characters that could not be identified by the known system
  • this problem is clearly technical
  • solution is also of a technical character, as the addition of additional stages to a first stage clearly represents a technical measure