T 0083/09 (Ausspähungsgeschützte modulare Inversion/GIESECKE & DEVRIENT) of 25.7.2012

Sachverhalt und Anträge

I. Die Beschwerde richtet sich gegen die Entscheidung der Prüfungsabteilung, die Anmeldung 03 735 380.2 zurückzu wei sen. In der Entscheidung werden u. a. die folgenden Do ku mente zitiert:

D1: US 2001/0002486 A1

D4: WO 01/31436 A1

D5: Akkar M.-L. et al., "An Implementation of DES and AES, Secure against Some Attacks", CHES 2001, LNCS 2162, 2001, Seiten 309-318,

und es wird argumentiert, dass der beanspruchte Gegen stand (gemäß einer Alternative) gegenüber D4 in Verbin dung mit D5 nicht erfinderisch sei, Artikel 56 EPÜ 1973. In einem obiter dictum wird weiter argumentiert, dass die andere beanspruchte Alternative nicht erfinderisch sei gegenüber D4 in Kombination mit D1, dass beide Al ter nativen gemäß Anspruch 1 nicht einheitlich mitein an der seien, Artikel 82 EPÜ 1973, und dass Ansprüche 7 und 8 gegen Artikel 83 EPÜ 1973 verstießen.

II. Beschwerde gegen diese Entscheidung ging am 25. Juli 2008 ein, und die Beschwerdegebühr wurde am selben Tag entrichtet. Eine Beschwerdebegründung wurde am 17. November 2008 eingereicht.

III. Mit einer Ladung zur mündlichen Verhandlung erhob die Kammer Einwände unter Artikel 83 und 84 EPÜ 1973, aber teilte der Beschwerdeführerin auch ihre vorläufige Mei nung mit, nach der geeignet geänderte Ansprüche die er for derliche erfinderische Tätigkeit aufwiesen.

IV. In Erwiderung auf die Ladung legte die Beschwerdefüh re rin geänderte Ansprüche und Beschreibungsseiten vor und beantragte, die Entscheidung aufzuheben und ein Patent auf der Grundlage der folgenden Unterlagen zu erteilen.

Beschreibung, Seiten

1, 2, 8, 9 veröffentlichte Fassung

3-7, 10 eingereicht mit Schreiben vom 25. Juni 2012

Zeichnungen, Blatt

1 veröffentlichte Fassung

Ansprüche, Nr.

1-3 eingereicht mit Schreiben vom 25. Juni 2012

V. Die Kammer sagte daraufhin die anberaumte mündliche Ver handlung ab.

VI. Anspruch 1 lautet wie folgt:

"Verfahren zum ausspähungsgeschützten Bestimmen des modularen Inversen b eines Wertes a zum Modul n in einer kryptographischen Anwendung, bei der es sich um eine Schlüsselpaarbestimmung bei einem RSA-Codierverfahren oder einem RSA-Signaturverfahren handelt, wobei das Verfahren auf einem Prozessor ausgeführt wird und die folgenden Schritte umfasst:

a) Bestimmen (10) eines Hilfswerts beta und eines dazu teilerfremden Hilfsmoduls delta zumindest in Abhängigkeit von dem Wert a, dem Modul n sowie mindestens einem Maskierungsparameter r und mindestens einem Hilfsparameter s derart, daß sich der Hilfswert beta von dem Wert a und/oder der Hilfsmodul delta von dem Modul n unterscheiden/unterscheidet, wobei der mindestens eine Maskierungsparameter r zufällig gewählt wird und/oder die Größenordnung des Moduls n aufweist und wobei der mindestens eine Hilfsparameter s zufällig gewählt wird und/oder die Größenordnung des Moduls n aufweist,

b) Bestimmen (20) eines Hilfsinversen beta' als modulares Inverses des Hilfswertes beta zum Hilfsmodul delta, und

c) Bestimmen (24) des modularen Inversen b zumindest in Abhängigkeit von den folgenden Werten:

- dem Hilfsinversen beta',

- dem mindestens einen Maskierungsparameter r, und

- dem Hilfswert beta und/oder dem Hilfsmodul delta, wobei der Hilfsparameter s nicht unmittelbar in die Bestimmung des modularen Inversen b einfließt,

wobei in Schritt a) der Hilfswert beta und der Hilfsmodul delta gemäß den Gleichungen ra=alphan+beta und sn=gammaa+delta mit 0<=beta<n und 0<=delta<a bestimmt werden und in Schritt c) das modulare Inverse b durch Auswerten der Gleichung b=beta'r+delta'gamma mod n mit delta'=(betabeta'-1)/delta bestimmt wird oder

wobei in Schritt a) der Hilfswert beta und der Hilfsmodul delta gemäß den Gleichungen ra=alphan+delta und sn=gammaa+beta mit 0<=delta<n und 0<=beta<a bestimmt werden und in Schritt c) das modulare Inverse b durch Auswerten der Gleichung b=-(delta'r+beta'gamma) mod n mit delta'=(betabeta'-1)/delta bestimmt wird."

Entscheidungsgründe

1. Die Erfindung bezieht sich auf das Gebiet der Krypto gra fie und betrifft die insbesondere bei der Schlüssel paar berechung im RSA-Verfahren benötigte Berechnung des mo dularen Inversen b eines Wertes a zum Modul n.

1.1. Um die Parameter dieses Verfahrens, wenn es auf einem Pro zessor ausgeführt wird, gegen Ausspähung durch Messung "physischer Parameter" zu schützen, etwa durch Analyse der Laufzeit oder des Stromver brauchs, schlägt die Er fin dung eine "maskierte" Berechnung vor: Die Ein gangs werte a und n wer den dabei mit Hilfe soge nann ter Mas kie rungs parameter in "Hilfswerte" transformiert, das mo du lare Inverse als "Hilfsinverses" für diese Hilfs werte be stimmt, und das Hilfsinverse in das gewün schte modu lare Inverse der Ein gangs werte rück trans for miert.

1.2. Spezifisch schlägt die Er findung vor, einen Maskie rungs wert r und einen Hilfsparameter s zu wählen und den Hilfs wert beta bzw. den Hilfsmodul delta als die Reste der (ganz zahligen) Division von ra bzw. sn durch n bzw. a (oder umgekehrt) zu bestimmen. Die Glei chungen, die zur Bestimmung von beta und delta sowie des ur sprünglich gesuchten modularen Inversen b zu lösen sind, nämlich

ra = alphan + beta mit 0 <= beta < n,

sn = gammaa + delta mit 0 <= delta < a, und

b = (beta'r + delta'gamma) mod n mit delta' = (betabeta'-1)/delta, bzw.

ra = alphan + delta mit 0 <= delta < n

sn = gammaa + beta mit 0 <= beta < a, und

b = -(delta'r + beta'gamma) mod n mit delta' = (betabeta'-1)/delta,

werden nun, als Alterna tiven, obligatorisch beansprucht.

1.3. Darüber hinaus spezifiziert die beanspruchte Erfindung (vgl. Anspruch 1, Schritt a) bevorzugte, aber optionale Kriterien, nach denen r und s zu wählen sind.

Artikel 123 (2) EPÜ, sowie Artikel 83 und 84 EPÜ 1973

2. Die Änderungen gehen nicht über den Inhalt der Anmeldung in der ursprünglichen Fassung hinaus und entsprechen so mit den Erfordernissen von Artikel 123 (2) EPÜ: Die ge nannten Gleichungen sind in den Ansprüchen 6-10 und auf Seiten 6, 9 und 10 (jeweils 2. Abs.), und die Kri te rien gemäß Schritt a) des Anspruchs 1 in den ur sprüng lichen Ansprüchen 2 und 4 sowie auf Seite 5 (ebenfalls 2. Abs.) der ursprüng lichen Anmeldung offenbart. RSA ist im ur sprüng lichen Anspruch 11 sowie an verschiedenen Stellen der Beschreibung offenbart, darunter auf Seite 1, die Ausführung des Verfahrens auf einem Prozessor ist etwa im ursprünglichen Anspruch 12 offenbart. Die Änderungen an der Beschreibung beschränken sich auf solche, die not wendig sind, die Beschreibung in Einklang mit den ge än derten Ansprüchen zu bringen (Artikel 84 EPÜ 1973).

3. Die im Ladungszusatz erhobenen Einwände unter Artikel 83 und 84 EPÜ 1973 hatte die Kammer mit ihrer Einschätzung begründet, dass die Anmeldung genau eine mathematische Lösung des genannten Problems offenbare und dem Fachmann auch keinen Hinweis gebe, wie er alternative Lösungen fin den könne, ohne erfinderisch tätig zu wer den. Durch die Be schrän kung der Ansprüche auf diese eine, offen bar te Lö sung haben sich diese Einwände erübrigt.

4. Die Entscheidung erhebt in einem obiter dictum den Ein wand unter Artikel 83 EPÜ 1973, die Formeln gemäß (da mals anhängigen) An sprüchen 7 und 8 würden unter der An nahme alpha=gamma=0 "nicht ... zur korrekten Inversen des Wer tes a führen". Die nun beanspruchten Gleichungen und Neben be dingungen haben, wie sich der Fachmann leicht über zeugt, unter der Annahme alpha=gamma=0 keine Lösung. Die Kammer ist somit der Ansicht, dass der Fachmann diese nicht ausdrücklich beanspruchte Nebenbedingung ohne Weiteres ergänzen würde, so dass ihr Fehlen keinen Offenbarungs mangel im Sinne von Artikel 83 EPÜ darstellt.

Artikel 56 EPÜ 1973

5. Die Entscheidung der Prüfungsabteilung (Punkt B.1.1) geht in ihrer Analyse von Dokument D4 aus, das bei spiel haft die "ungeschützte direkte Inversions be rech nung ... zur Berechnung eines geheimen RSA-Schlüssels" offenbart. Die Kammer folgt dieser Wahl.

6. Über die Unterschiede zwischen Anspruch 1 und D4 und de ren technische Wirkung eines Ausspähungsschutzes besteht Einigkeit zwischen der Entscheidung und der Beschwerde füh rerin (vgl. Entschei dung, Punkt B.1.1; Beschwerde be gründung, S. 1).

6.1. Die Entscheidung argumentiert weiter, dass D5 die bean spruchte Lösung nahelegen würde. D5 befasse sich mit dem Ausspähungsschutz kryptografischer Algorithmen und offen bare ein Verfahren, demgemäß insbesondere eine mul tiplikative Inversion durch Maskierung geschützt würde. Von diesem sei das beanspruchte Maskie rungs ver fah ren nur geringfügig und nicht erfinderisch unter schie den (Punkt B.1.2). Die Tat sache, dass es sich in D5 mit AES um ein symme tri sches und nicht, wie gemäß der Anmeldung mit RSA um ein asymmetrisches Ver schlüs se lungsverfahren handele, sei unerheblich angesichts der Tatsache, dass die multi pli kative Inversion in beiden Fällen eine "modulare" sei (Punkt B.1.2.1).

6.2. Der Beschwerdeführer bringt demgegenüber vor, dass die mo dulare Inversion bei symmetrischen Algorithmen wie AES keine Rolle spiele und dass sich daher der Fachmann, der sich mit asymmetrischer Kryptografie beschäftige, nicht auf dem Gebiet der symmetrischen Krypto gra fie nach Prob lem lösungen umsehen würde. Der Fachmann wür de somit D4 und D5 nicht kombinieren (vgl. Beschwer debegründung, S. 2, insbes. Abs. 2 und 6). Darüber hi naus habe die mul ti plikative Inversion "an sich" nichts mit der in der asymmetrischen Kryptografie verwendeten modularen Inver sion zu tun, und die Entscheidung würde nicht im Einzel nen darlegen, in welcher Weise D5 die fehlenden Merkmale nach Anspruch 1 offenbaren würde (Beschwerde begründung, S. 3, Abs. 2 und 3) und wie die Ent schei dung zur Auf fassung gelangt sei, dass Aij**(-1)ein modulares Inverses sei, ob gleich dieser Begriff in D5 gar nicht erwähnt würde.

7. Die Kammer ist der Ansicht, dass dem mit Krypto grafie be fassten Fachmann symmetrische und asymmetrische Ver fahren gleichermaßen geläufig sind, und dass er daher rou tinemäßig in Betracht ziehen würde, Verbesserungen bei den einen für die anderen verfügbar zu machen.

7.1. Die Kammer stimmt der Beschwerdeführerin aber darin zu, dass sich der Fachmann auch der Unterschiede beider Ver fahren (z. B. mathematischer Art) bewusst wäre und somit erkennen würde, dass sich manche Lösungen in ei nem Ge biet nicht - oder nicht ohne Weiteres - auf das an dere über tragen lassen.

7.2. Zwischen der multiplikativen Inversion aus D5 und der mo du laren Inversion nach Anspruch 1 bestehen Ähnlich keiten und Unterschiede.

7.3. Gemäß D5 ist die multiplikative Inversion in GF(2**(8)) zu be stimmen. GF(2**(8)) ist der Raum der Polynome höchstens 7. Grades mit Addition (+) und Multiplikation (*) von Poly no men wie üblich bis auf Reduktion der Koeffizien ten mo dulo 2 und, was die Multiplikation angeht, Reduk tion mo dulo eines irreduziblen Polynoms f vom Grad 8. In AES ist dieses Polynom konkret festgelegt (vgl. D5, S. 314, vorletzte Zeile). Das mul ti plikative Inverse eines Poly noms a zum Modul f ist dann ein Polynom b, so dass a (*) b = 1 (mod f), also ein "modular Inverses" zum Modul f.

7.4. Andererseits ist die Kammer der Ansicht, dass die mul ti pli ka tive Inversion aus D5 (über GF(2**(8))) und die mo dulare Inversion (über einem Ring ganzer Zahlen mo dulo n), wie sie für RSA benötigt wird, wegen der zugrunde lie gen den Addition und Multiplikation soweit verschieden sind, dass eine Mas kierung der einen Operation sich nicht in offen sicht licher, geschweige denn unmittelbarer Weise auf eine Mas kierung der anderen Operation übertragen lässt.

7.5. Die Kammer stimmt somit der Beschwerdeführerin darin zu, dass der Fachmann ausgehend von D4 und auf der Suche nach einer Maskierung der für RSA benötigten modularen In version nicht in D5 nach einer Lösung suchen würde. Aber selbst eine hypothetische Kombination von D4 mit D5 würde den Fachmann nicht zur beanspruchten Erfindung füh ren, da in der D5 die nun spezifisch beanspruchten Gleichungen weder offenbart noch nahegelegt werden.

7.6. Was D1 angeht, so folgt die Kammer der Ansicht der Be schwer de führerin, dass der Fachmann zur Bestimmung eines ausspähungssicheren Verfahrens zur Bestimmung des modu lar Inversen für RSA nicht auf D1 zurückgreifen würde (vgl. Eingabe vom 26. Mai 2008, S.3, letzter Abs.). Da die vorliegenden Ansprüche nun auf RSA beschränkt sind, erübrigt sich somit eine detaillierte Analyse von D1.

7.7. Insgesamt kommt die Kammer zu dem Ergebnis, dass die vorliegenden Ansprüche 1-3 den erforder lichen erfin derischen Schritt gegenüber D4, D5 und D1 aufweisen, Artikel 56 EPÜ 1973.

Artikel 82 EPÜ 1973

8. Die in Schritt c) von Anspruch 1 beanspruchten Al ter na tiven sind durch analoge Gleichungssysteme definiert (vgl. Punkt 1.2), deren erfinderische Tätigkeit gegen über D1, D4 und D5 sich in gleicher Weise aus den vor an stehenden Betrachtungen ergibt. Diese Gleichungen müssen damit als besondere technische Merk male im Sinne der Re gel 30 (1) EPÜ 1973 gelten, und stellen so mit Einheit lichkeit der Erfindung gemäß Ar ti kel 82 EPÜ 1973 inner halb des Anspruchs 1 her, vgl. Re gel 30 (2) EPÜ 1973.

ENTSCHEIDUNGSFORMEL

Aus diesen Gründen wird entschieden:

1. Die Entscheidung wird aufgehoben.

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

Beschreibung, Seiten

1, 2, 8, 9 veröffentlichte Fassung

3-7, 10 eingereicht mit Schreiben vom 25. Juni 2012

Zeichnungen, Blatt

1 veröffentlichte Fassung

Ansprüche, Nr.

1-3 eingereicht mit Schreiben vom 25. Juni 2012