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 higherbit sections” by multiplication by an expansion factor, and introducingdisturbancesinto 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

Leave a Reply

Your email address will not be published. Required fields are marked *