T 2318/08 (Koprozessor zur modularen Inversion/GIESECKE & DEVRIENT) of 23.5.2012

Sachverhalt und Anträge

I. Die Beschwerde richtet sich gegen die Entscheidung der Prü fungsabteilung vom 26. Juni 2008, die europäische Patent anmeldung 06013333.7 zurückzuweisen mangels erfin de rischer Tä tig keit, Artikel 56 EPC 1973, im Lichte der fol genden Doku mente:

D1: A. K. Lenstra, "Computational Methods in Public Key Cryptology", 13. August 2001

D2: US 5 961 578.

II. Beschwerde gegen diese Entscheidung ging am 19. August 2008 ein, und die Beschwerdegebühr wurde am selben Tag entrichtet. Eine Beschwerdebegründung ging am 28. Oktober 2008 ein. Es wurde beantragt, die angefochtene Ent scheidung aufzuheben und das Patent auf Basis eines neu en, mit der Beschwerdebegründung vorgelegten Anspruchs satzes zu erteilen.

III. Mit einer Ladung zur mündlichen Verhandlung teilte die Kammer der Beschwerdeführerin ihre vorläufi ge Meinung mit, nach der die Ansprüche mangels ersichtlichen techni schen Effekts nicht er finderisch seien, Artikel 56 EPÜ 1973. Darüber hinaus erhob die Kammer Einwände unter Ar ti kel 84 und Regel 29 (4) EPÜ 1973.

IV. In Erwiderung darauf legte die Beschwerdefüh re rin vier neue Anspruchssätze gemäß einem Hauptantrag und drei Hilfsanträgen vor. Die Kammer teilte der Beschwer de füh re rin mit, dass sie zwar den 1. Hilfsantrag, nicht aber den Hauptantrag für erteilbar hielte, und wies da rauf hin, dass die Beschreibung noch anzupassen sei.

V. Die Beschwerdeführerin zog daraufhin den Hauptantrag zu rück und beantragte die Erteilung eines Patents auf Grundlage der folgenden Unterlagen:

Beschreibung, Seiten

1, 2, 7-11 wie ursprünglich eingereicht

3 eingereicht am 23. April 2012

4-6, 12 eingereicht am 9. Mai 2012

Zeichnungen, Blatt

1/1 wie ursprünglich eingereicht

Ansprüche, Nr.

1-7 gemäß 1. Hilfsantrag vom 23. April 2012.

VI. Aufgrund dieser Änderungen wurde die anberaumte münd li che Verhandlung abgesagt.

VII. Anspruch 1 des einzigen Antrags lautet wie folgt:

"Verfahren zur Verwendung eines Koprozessors (16) zur Bestimmung des modularen Inversen x eines Eingangswertes u bezüglich eines Moduls v, wobei:

- aus dem Eingangswert u derart ein erster erweiterter Wert U mit einer gegenüber dem Eingangswert u vergrößerten Bitlänge bestimmt wird, dass sich in einem Bitabschnitt des ersten erweiterten Werts U die Informationen des Eingangswerts u befinden, wobei das Bestimmen des ersten erweiterten Werts U die Multiplikation des Eingangswertes u mit einem Erweiterungsfaktor f umfasst und wobei f>2v gilt,

- aus dem Modul v derart ein zweiter erweiterter Wert V mit einer gegenüber dem Eingangswert v vergrößerten Bitlänge bestimmt wird, dass sich in einem Bitabschnitt des zweiten erweiterten Werts V die Informationen des Moduls v befinden, wobei das Bestimmen des zweiten erweiterten Werts V die Multiplikation des Moduls v mit dem Erweiterungsfaktor f umfasst,

- der Koprozessor (16) für Ganzzahl-Berechnungen mit zumindest der vergrößerten Bitlänge vorgesehen ist,

- mindestens einer der erweiterten Werte U, V eine Störung an einer Bitposition enthält, die von denjenigen Bitpositionen, an denen sich die Informationen des Eingangswerts u bzw. des Moduls v befinden, beabstandet ist,

- ausgehend von den beiden erweiterten Werten U und V unter Verwendung des Koprozessors (16) Verarbeitungsschritte (34) eines euklidischen Verfahrens ausgeführt werden, solange eine vorgegebene Ausführungsbedingung erfüllt ist, und

- das modulare Inverse x in Abhängigkeit von dem Ergebnis der ausgeführten Verarbeitungsschritte (34) bestimmt wird."

Entscheidungsgründe

1. Die Kammer hat keinen Zweifel daran, dass die vor lie gen den Ansprüche den Erfordernissen des Artikel 84 EPÜ 1973 entsprechend deutlich und knapp gefasst und durch die ge änderte Beschreibung gestützt sind, sowie dass der Gegen stand der geänderten Anmeldung nicht über den Inhalt der Anmeldung in ihrer ursprünglich eingerei chten Fassung hinausgeht, Artikel 123 (2) EPÜ. Der derzeitige Anspruch 1 insbesondere stützt sich auf die ursprüng li chen An sprü che 1, 6, 7 und 12 in Verbindung mit der ursprüng lichen Beschreibung auf Seite 6, Zeile 24 - Seite 7, Zei le 16.

2. Die Erfindung betrifft ein Ver fahren zur Be rechnung des in kryptografischen Verfahren relevanten modularen In ver sen eines Wertes u zu einem Modul v. Die Erfindung geht von einem zur Berechnung des modularen In versen be kannten erweiterten euklidischen Verfahren aus (vgl. ur sprüngliche Beschreibung, Seiten 2 und 3, je 4. Absatz).

2.1 Die Kernidee des Verfahrens besteht da rin, die Ausgangs werte u und v nicht wie gewöhnlich "rechts bün dig" in den niederwertigen Bitpositionen darzu stellen, sondern sie so weit in höherwertige Positionen zu verschieben, dass in den niederwertigen Positionen Raum für die übrigen Parameter des Verfahrens entsteht, in Ver bindung mit der Erkenntnis, dass auf der so geänder ten Dar stellung (im wesentlichen) nur die Rechenschritte des gewöhnlichen euklidischen Verfahrens durchgeführt wer den müssen, um die Ergebnisse des erweiterten Ver fahrens zu er halten. So mit benötigt das neue Verfahren weniger Re chen schritte als das erweiterte euklidische Verfahren, allerdings um den Preis einer größeren Bitlänge der Ein gangswerte (vgl. ursprüngliche Beschreibung, Seite 3, 4. Absatz - Seite 4, 1. Absatz).

2.2 Die praktische Relevanz des Verfahrens ergibt sich aus den folgenden Beobachtungen: In der kryptografischen Praxis wird die modulare Inversion typischerweise mit einem Koprozessor durchgeführt, der für Operationen auf ganzen Zahlen ausgelegt sind, deren Bitlänge sich wiede rum nach der in RSA üblichen Schlüssellänge richtet. Die zu RSA al ter nativen sogenannten EC-Verfahren verwenden wesentliche kürzere Schlüssel, so dass die modulare Inver sion nur für kleinere Zahlen durchgeführt werden muss. Wenn demnach ein für RSA optimierter Koprozessor für EC ein gesetzt wird, bleibt ein Teil seiner Bits systema tisch ungenutzt. Das erfindungsgemäße Verfahren nutzt diese ohnehin vorhandenen überzähligen Bits zur Be schleu ni gung des gewünschten Verfahrens.

3. Aus dem vorliegenden Stand der Technik geht als bekannt hervor, dass es für die in der Kryptografie notwendigen modularen Ganzzahl-Berechnungen dedizierte Koprozessoren gibt (vgl. D2, Spalte 8, Zeilen 50-59), und dass Varian ten des Eukli di schen Verfahren zur Berechnung des modu la ren In ver sen ver wendet werden (vgl. D1, Abschnitt 3.3, Seiten 14-19). Beides wurde schon in der ur sprünglichen Anmeldung als bekannt anerkannt (Seite 1, 3. Absatz, so wie Seite 2, Zeile 18 - Seite 3, Zeile 7) und von der Be schwerdeführerin nicht bestritten. Auch unbe strit ten ist, dass das beanspruchte Verfahren gegenüber den be kannten euklidischen Verfahren neu ist. Neuheit der be an spruchten Erfindung steht somit nicht in Frage.

4. Ebenso wenig steht in Frage, dass die geschickte Ver wen dung eines bekannten Koprozessors zur beschleunigten Imple mentierung eines ebenfalls bekannten Verfahrens eine technische Aufgabe löst und somit grundsätzlich die Er for dernisse des Artikels 56 EPÜ 1973 erfüllen kann.

4.1 Die Prüfungsabteilung begründete ihre Ent schei dung damit, dass dem Gegenstand des unabhängigen An spruchs 1 seinem damaligen Wort laut nach eine Lö sung dieser technischen Aufgabe nicht zugeschrieben werden könne. Dazu fehle es ihm zum einen an der Beschränkung auf einen Kopro zessor, der "für Ganzzahl-Berechnungen mit zumindest der ver größer ten Bitlänge vorgesehen ist", zum anderen an der Angabe, dass die Hilfsvariablen in den niederwer ti gen Bits der ver größer ten Bitlänge mitgeführt würden (vgl. Entscheidung, Punkte 7.2 und 11).

4.2 Der vorliegende Anspruch 1 ist nun in der geforderten Weise beschränkt: Der beanspruchte Koprozessor ist für ei ne Bitlänge "vorgesehen", die größer ist als diejenige, die für die Eingangswerte u und v nötig sind. Anspruchs ge mäß werden die überzähligen Bits genutzt, indem u und v durch Mul ti plikation mit einem Erweiterungsfaktor in hö here "Bit abschnitte" verschoben werden, und in die da mit freiwerdenden, niederwertigen Bitabschnitte "Störun gen" eingebracht werden, die als Ausgangswerte für Hilfs variablen der anschließenden Berechnung dienen.

5. Dass der beanspruchte Gegenstand - soweit er die behaup tete technische Aufgabe löst - gegenüber dem zitierten Stand der Technik naheliegend sei, wird in der stritti gen Entscheidung nicht behauptet. Im Gegenteil beurteilt die Entscheidung in einem obiter dictum einen geeignet beschränkten Anspruch als erfinderisch (vgl. Punkt 11).

5.1 Die Kammer stimmt der Prüfungsabteilung in dieser Bewer tung zu. Daraus, dass zum einen kryptografische Kopro zessoren und zum anderen das Euklidische Verfahren und seine Varianten bekannt sind, ergibt sich nur, dass die Implementierung Euklidischer Verfahren auf krypto gra fi schen Koprozessoren für den Fachmann naheliegen würde.

5.2 Es ergibt sich daraus jedoch kein Hinweis darauf, frei blei bende Bitabschnitte in einem solchen Koprozessor in der bean spruchten Weise zur Beschleunigung des Ver fah rens zu ver wenden.

5.3 Daher ist der beanspruchte Gegenstand erfinderisch gegenüber dem aus D1 und D2 bekannten Stand der Technik, Artikel 56 EPÜ 1973.

ENTSCHEIDUNGSFORMEL

Aus diesen Gründen wird entschieden:

1. Die Beschwerde wird aufgehoben.

2. Die Sache wird an die Prüfungsabteilung zurückverwiesen mit der Anordnung ein Patent auf Grundlage der folgenden Unterlagen zu erteilen:

Beschreibung, Seiten

1, 2, 7-11 wie ursprünglich eingereicht

3 eingereicht am 23. April 2012

4-6, 12 eingereicht am 9. Mai 2012

Zeichnungen, Blatt

1/1 wie ursprünglich eingereicht

Ansprüche, Nr.

1-7 gemäß 1. Hilfsantrag vom 23. April 2012.