T 1326/06 – Tales From The ‘Crypt

Claims 1, 9 and 10 of the international application as filed read:

1. A method for calculating the modular inverse (R) of a value (E) in relation to a module (M), in particular for cryptographic applications, with the steps:

a) determining (10) a breakdown of the module (M) into at least two factors (M1, M2),

b) calculating (12,14) a respective auxiliary value (R1, R2) for each of the factors (M1, M2) determined in step a), wherein each auxiliary value (R1, R2) is the modular inverse of the value (E) in relation to the respective factor (M1, M2) as module, and

c) calculating (16) the modular inverse (R) of the value (E) in relation to the module (M) at least using the auxiliary values (R1, R2) calculated in step b).

9. A computer program product which has program commands to cause a processor to carry out a method having the features of one of claims 1 to 8.

10. A portable data carrier, in particular a chip card or chip module, set up to carry out a method having the features of one of claims 1 to 8.

The EPO acting as ISA declared that it would not establish a search report because the claims referred to a mathematical theory.

This objection was confirmed by the Examining Division (ED) after the application had entered the European phase: claims 1 to 8 were excluded from patentability under A 52(2)(a) because they were directed at an abstract mathematical method. The computer program product of claim 9 had only effects in domains excluded from patentability and, therefore, was not patentable under A 52(2)(c) and A 52(3) either. The known portable data carrier did not solve a technical problem and, as a consequence, was not inventive.

The applicant filed an appeal against the decision to refuse the application.

Claim 1 on file before the Board read:

1. A computer implemented method for determining of key pairs for an RSA encryption or signature method by

calculating the modular inverse (R) of a value (E) in relation to a module (M) by means of the following steps:

a) determining (10) a breakdown of the module (M) into at least two factors P-1 and Q-1, wherein P and Q are the prime numbers that are defined by RSA,

b) calculating (12,14) a respective auxiliary value (R1, R2) for each of the factors (P-1,Q-1) determined in step a), wherein each auxiliary value (R1, R2) is the modular inverse of the value (E) in relation to the respective factor (P-1, Q-1) as module, and

c) calculating (16) the modular inverse (R) of the value (E) in relation to the module (M) at least using the auxiliary values (R1, R2) calculated in step b).

The Board finds the request to comply with A 123(2) and A 83 and then goes on:

*** Translated from the German ***

A 52(2) and (3)

[5] According to the established case law, the subject-matter of all of the claims has technical character and, therefore, complies with A 52(2) and (3) because the claims are directed at a computer implemented method (cf. T 258/03 [headnote 1] and G 3/08 [10.7]).

[5.1] This dispels the only objection that has been directly raised against the original method claims. There are no more claims directed at a computer program product and a portable data carrier.

[5.2] However, the ED was of the opinion that the computer program product as originally claimed had only effects in domains excluded from patentability. The Board presumes that the ED would have been of the same opinion in regard of the method claims if they had been said to be “computer implemented”.

[5.3] Therefore, a direct remittal to the first instance is likely to lead to another refusal based on the same arguments but invoking A 56 rather than A 52(2) and (3).

[5.4] Therefore, the Board considers it to be appropriate to examine, within the powers conferred to it by A 111(1), whether the methods according to claims 1 to 4 have a technical effect that goes beyond its computer implementation.

Technical nature

[6] RSA is an asymmetric encryption system that can be used both for encryption and for digital signatures. It uses key pairs consisting in a private key, which is used for decrypting or signing data, and a public key, which is used for encrypting and examining signatures. The private key is kept secret and can only be calculated from the public key with extremely high effort, if at all.

[6.1] Keys and messages are represented as figures and both the determination of the key pairs and the en/decryption or the signature of messages are described in terms of mathematical operations: the choice of two big prime numbers P and Q and the calculation of N=P*Q and M=(P-1)*(Q-1), the choice of a number E, where E and M are relatively prime, and the determination of the modular inverse of E in relation to module M (for the determination of the key pair), as well as the exponentiation modulo N (for en/decrypting and signing, respectively). Moreover, the fact that the private key is kept secret is based on the founded mathematical assumption that prime factorization is, as a rule, a difficult problem and that, in particular, the factorization of N in its prime factors P and Q is practically impossible. Therefore, to a great extent, RSA appears to be a purely mathematical method.

[6.2] On the other hand, asymmetric cryptography deals with the concrete problem of how to safely exchange electronic messages and at the same time facilitate the exchange of keys and secrecy. In contrast to symmetric cryptography, when asymmetric cryptography is used, each user of the system only has to keep his own private key secret.

[6.3] The Board is of the opinion that the safe exchange of electronic messages is a technical effect and the problem to achieve this effect has to be considered to be a technical problem.

[6.4] RSA solves this problem by using mathematical means. RSA allowed a breakthrough in the development of cryptography. It is held that RSA is the first viable, concretely implemented asymmetric cryptography system and nowadays it is a central component in many cryptographic security systems. The underlying mathematics, therefore, directly serves the solution of a concrete technical problem.

[6.5] Therefore, the Board is of the opinion that methods for de/encrypting or signing electronic messages by means of RSA have to be considered to be technical methods even though they are essentially based on mathematical methods.

[7.1] This assessment of the Board is consistent with decisions T 953/04 and T 27/97.

In T 953/04 [3.3] it was stated that

• “The use of cryptographic methods in the technical context of electronic data processing and communication has certainly technical character.”,

and T 27/97 [3] comes to the conclusion that

“a method for encrypting or decrypting a message in the form of a digital word by means of algorithms using a public key of the RSA type […], intended to be used in electronic systems, is not excluded from patentability under A 52(2) and (3), even if the invention is based on an abstract algorithm or a mathematical method”.

[7.2] The preamble of claim 1 is directed at a computer implemented method for determining key pairs for an RSA encryption or signature method.

The Board is of this opinion that this wording results in claim 1 going beyond claiming the mere suitability of the determination of key pairs for RSA. Rather, it defines, in a limitative manner, that the key pair determination is in fact embedded in a encryption or signature method using RSA and that it is functionally related to it. Therefore, this limitation contributes to the technical character of the claimed subject-matter.

The wording leaves open how the RSA encryption or signature method is implemented and how the relevant method steps are distributed between different programmes, data carriers or computers.

[8] The claimed calculation steps exclusively refer to the determination of key pairs, wherein the keys that are calculated in this way are exactly the known keys, as defined by RSA. Therefore, the claimed way of calculating the results (Rechenweg) has no impact on the RSA encryption or signature method in a narrow sense.

[8.1] This being said, the calculation of the key pairs undoubtedly constitutes an essential component of the RSA encryption system: as explained above, asymmetric cryptography is unthinkable without keys having the relevant mathematical properties.

[8.2] Therefore, the Board is of the opinion that the claimed calculation of the RSA key pair including all the calculation steps contributes to the technical character of the invention according to claim 1.

[9] According to the established case law of the Boards of appeal, the features which contribute to the technical character of the invention have to be taken into account when the inventive step of an invention is assessed (cf. T 641/00 [headnote 1] and G 3/08 [12.2.1-2]).

[9.1] The calculation of the modular inverse according to claim 1 is not carried out with one of the conventional calculation methods mentioned in the description, which are based on the Euclidean algorithm […].

[9.2] The Board has no indication justifying the assumption that the claimed method is notoriously known or indisputably forms part of the common general knowledge (cf. T 1242/04 [9.2]).

[9.3] As a consequence, it is not possible to decide on novelty and inventive step without the documents of the prior art, so that the file is remitted in order for the announced additional research to be carried out and the examination to be pursued.

NB: The decision also comprises a take-away headnote:

“Methods for encrypting/decrypting or signing electronic messages have to be considered to be technical methods, even if they are essentially based on mathematical methods.”

Should you wish to download the whole document (in German), just click here.

To have a look at the file wrapper, click here.