Using the RSA Algorithm for Encryption and Digital Signatures:

Can You Encrypt, Decrypt, Sign and Verify without Infringing the RSA Patent?

(http://www.cyberlaw.com)


Patrick J. Flinn and James M. Jordan III


Zusammenfassung des Artikels

von Robert Gehring


In der Fachliteratur zu Kryptographie findet man im jeweiligen Abschnitt zu RSA üblicherweise den Hinweis, daß der RSA-Algorithmus patentiert sei (US Pat. 4.405.829), z.B. auch bei [Schneier 1996], S.541. Damit entsteht der Eindruck, daß zum legalen Einsatz des RSA-Verfahrens eine Lizenz des Lizenzinhabers, in diesem Falle RSADSI (RSA Data Security Inc.) notwendig sei. Die Autoren des Artikels untersuchen das RSA-Patent im Detail und zeigen auf, daß es gute Gründe dafür gibt, anzunehmen, daß

Sie weisen daraufhin, daß es sich um theoretische Überlegungen und persönliche Auffassungen handelt, die nicht als juristischer Rat zu verstehen sind. Daß diese Überlegungen nichtsdestotrotz fundiert sind, läß sich aufgrund der beruflichen Qualifikation der Autoren annehmen: Flinn und Jordan sind praktizierende Anwälte, Jordan insbesondere Patentanwalt.

Hier folgt eine Zusammenfassung ihrer Schlußfolgerungen und Argumente.


RSA-Entschlüsselung stellt keine Patentverletzung dar


Die RSA-Patentanmeldung enthält 40 Patentansprüche (claims), von denen 10 unabhängige Ansprüche und die restlichen 30 abhängige Ansprüche darstellen. Die bloße Operation der Entschlüsselung einer RSA-verschlüsselten[1] Nachricht wird im Patent nicht als unabhängiger Anspruch aufgeführt[2] .

Der grundlegende Anspruch ist Nummer 23, der Patentschutz für folgende Verfahren beansprucht (im Wortlaut):

Die Autoren führen nun folgende Schritte an, die für eine mutmaßliche Patentverletzung (alleged infringement) vollzogen werden müßten (Rohübersetzung):

Der Schritt der Entschlüsselung wird in Anspruch 23 nicht aufgeführt. Insbesondere stellt eine Entschlüsselung (decoding) keine Verschlüsselung (encoding) dar, die Begriffe sind klar unterschieden und haben eine je eigene Bedeutung. Die Entschlüsselung wird in Anspruch 24 aufgeführt:

Nun ist aber Anspruch 24 ein abhängiger Anspruch, der eingeleitet wird mit

Eine Verletzung des abhängigen Anspruches 24 durch bloßes Entschlüsseln einer RSA-verschlüsselten Nachricht ist nach amerikanischem Patentrecht nicht möglich, da der referenzierte, unabhängige Anspruch 23 die Entschlüsselung nicht aufführt. Entschlüsselung kommt ohne die in Anspruch 23 aufgeführten Aktionen aus.

Die Autoren prüften dann noch die anderen unabhängigen Ansprüche des RSA-Patentes und kamen zu dem Schluß, daß die bloße Entschlüsselung einer RSA-verschlüsselten Nachricht keine Patentverletzung darstellen könne. Dies gilt dann auch für die Verifizierung einer digitalen Signatur, die unter Verwendung des RSA-Verfahrens erzeugt wurde.


Erzeugung einer digitalen Signatur mittels RSA muß keine Patentverletzung sein


An dieser Stelle formulieren die Autoren etwas vorsichtiger:

Um eine Nachricht mit RSA zu verschlüsseln, muß man über die Zahlen verfügen, mit denen die Schlüssel zusammenhängen: p, q, n, e und d. Es genügt, darüber zu verfügen. Man muß sie nicht selbst erzeugt haben. Der Prozeß der Schlüsselerzeugung kann unabhängig von dem der Verschlüsselung erfolgen. Dieser Prozeß fällt sicherlich unter den Patentschutz. Man kann aber einmal erzeugte Schlüssel wiederverwenden, selbst in Software die ohne RSA-Lizenz daherkommt.

Die Autoren sind der Auffassung, daß es dem RSA-Patentinhaber schwer fallen würde, nachzuweisen, daß eine Verschlüsselung, die ohne Schlüsselerzeugung auskommt, unter das Patent fällt. Das Verschlüsselungsverfahren mit Exponenten und modularer Arithmetik wurde nämlich bereits von Stephen Pohlig und Martin Hellman in dem nach ihnen benannten Verschlüsselungssystem eingeführt - 1975. Pohlig und Hellman traten damit bereits zwei Jahre vor dem Trio Rivest/Shamir/Adleman auf den Plan. Der einzige Unterschied zwischen RSA und Pohlig-Hellman besteht darin, das erstere das Produkt zweier Primzahlen verwenden, wogegen letztere mit einer Primzahl auskamen.

In einem Vergleich stellen die Autoren das RSA-Verfahren und das Verfahren von Pohlig und Hellman gegenüber.

Wie ersichtlich, unterscheiden sich die Verschlüsselungs- und die Entschlüsselungsoperationen nicht, sie sind identisch. Vorausgesetzt, man verfügte über die beiden Exponenten d und e, könnte man mit einer Software, die das Pohlig-Hellman-Verfahren implementiert, genauso ver- und entschlüsseln, wie mit einer RSA-Software.

Daraus schlußfolgern die Autoren, daß die RSA-Patentanmeldung ohne die aufgeführte Schlüsselerzeugung ungültig gewesen wäre, da das Pohlig-Hellman-Patent dem entgegengestanden hätte.

Anschließend wenden sich die Autoren der Frage der Beihilfe zur Patentverletzung (contributory infringement) zu. Sie weisen auf den entscheidenden Punkt hin, daß es eine Beihilfe zur Patentverletzung per definitionem nur geben kann, wenn es eine direkte Patentverletzung gibt, zu der beigetragen werden kann. Dies muß willentlich und wissentlich geschehen.

Unterstellt, daß dies der Fall wäre, müßte im Detail untersucht werden, wie die Beihilfe ausgestaltet wäre. Würde sie z.B. mit Mitteln vollzogen, die nicht spezifisch dazu dienen, wäre der Nachweis schwer zu führen[3].



Als nächstes wenden sich die Autoren einem "Real World Example" zu und beschreiben das Beispiel SSL-Client. Sie untersuchen die Abläufe des Schlüsselaustausches und der Verschlüsselung und kommen zu dem Schluß, daß ein Nutzer eines SSL-Clients gutgläubig davon ausgehen kann, daß alles seine Richtigkeit hat und er nichts Ungesetzliches tut.



Der letzte wesentliche Punkt in den Betrachtungen der Autoren ist der Gültigkeit des RSA-Patents gewidmet. Bis zu diesem Punkt waren sie in ihren Überlegungen immer davon ausgegangen, daß das Patent gültig ist, d.h. daß der Antrag auf Patentschutz und das Procedere seiner Einbringung mit den Regeln für die Patenterteilung konform waren. Nun untersuchen sie, ob diese Unterstellung gerechtfertigt ist.

Patentierbarkeit von Algorithmen

1972 stellte der US Supreme Court fest, daß ein Algorithmus kein

sei, wie es in Abschnitt 101 des Patentgesetzes (Patent Act) gefordert wird. Ein Algorithmus war im Verständnis des US Supreme Court eine

Diese Definition schloß Algorithmen von der Patentierung aus.

1981 änderte sich die Situation schlagartig, ebenfalls durch eine Entscheidung des US Supreme Court. Im Fall Diamond vs. Dehr wurde um einen verbesserten Prozeß zur Gummiherstellung gestritten. Die Verbesserung wurde im wesentlichen durch einen Algorithmus zur Behandlung von Gummi bei spezifischen Temperaturen repräsentiert. Der Supreme Court entschied nun, daß dadurch, daß ein Algorithmus Bestandteil eines ansonsten patentierbaren Verfahrens sei -und die Herstellung von Gummi ist prinzipiell patentierbar- nicht begründet werden könne, daß das Verfahren keinen Patentschutz nach Abschnitt 101 des Patentgesetzes zu erhalten habe. Dem Richterspruch des Supreme Court folgten weitere Urteile von Appellationsgerichten, die genauer eingrenzten, wann und wie Algorithmen Patentschutz erhalten können.

Zur Feststellung der Patentierbarkeit eines Algorithmus' wurde der sogenannte Freeman-Walter-Abele-Test[4] erarbeitet, der folgendermaßen vorgenommen wird:

Zusammengefaßt kann ein Algorithmus patentiert werden, wenn er eine der folgenden Bedingungen erfüllt:

Das RSA-Verfahren und der Freeman-Walter-Abele-Test

Die Autoren sind der Ansicht, daß die Formulierungen im RSA-Patentantrag den Forderungen der Gerichtsurteile, die im Freeman-Walter-Abele-Test zum Ausdruck kommen, wohl nicht genügen dürften. Als physikalische Geräte werden genannt:

Dies sind die allgemeinsten Formulierungen, die diesbezüglich überhaupt möglich sind. Daß sie ein physikalisches Gerät beschreiben, kann man eigentlich nicht behaupten. Oder was hat man sich unter einem "encoding means" vorzustellen?

Ähnlich ist es mit den Beschreibungen des physikalischen Prozesses. Dieser wird mit

geschildert. [Frage: Was alles ist ein "message word signal"?]

An dieser Stelle erwähnen die Autoren weitere Fälle, in denen des um die Patentierbarkeit von Algorithmen ging und in denen Computer eine Rolle spielten. Die Urteile in diesen Fällen waren von der Natur der Eingabedaten abhängig. Die Entscheidungen fielen zugunsten der Antragsteller aus, wenn es sich um Daten handelte, die Resultat von

waren. In einem Fall scheiterte der Antragsteller. Bei seinen Daten handelte es sich um Gebote von Auktionären, d.h. um das Resultat menschlichen Denkens, oder zumindest Empfindens.

Die Frage nach der Gültigkeit des RSA-Patents läßt sich unter diesen Umständen nicht mehr eindeutig beantworten.

Formalien

Als sei dies noch nicht genug, haben die Autoren noch weitere Fragwürdigkeiten aufgedeckt.

In Abschnitt 112 des Patentgesetzes werden Anforderungen an die Formulierung eines Patentantrages gestellt. Eine davon besagt, der Erfinder möge

Der Grund für diese Forderung ist, daß einem Mißbrauch des Patentschutzes vorgebeugt werden soll. Es handelt sich um eine klare Forderung, die keine Spielräume kennt.

Zurück zum Fall RSA. Es stellte sich heraus, daß Dr. Rivest im Januar 1978, also vor dem Patentantrag, ein Papier veröffenlicht hatte, das mehr Details über die Ausführung des RSA-Verfahrens beschrieb, als später im Patentantrag aufgeführt wurden[5]. Im Patentantrag wurde also nicht der "best mode of carrying out" offengelegt. Dies ist ein klarer Verstoß gegen die Regeln des Abschnitt 112 des Patentgesetzes. Aus diesem Grunde könnte das Patent ungültig sein.

Die Autoren haben noch andere Merkwürdigkeiten aufgedeckt. So vermieden es die Antragsteller, die Verwandtschaft zum Pohlig-Hellman-Verfahren zu erwähnen. Unerwähnt blieb auch eine Arbeit aus dem 19. (!) Jahrhundert zum Thema Einweg-Funktionen und Kryptographie, die bereits das Faktorisierungsproblem, auf dem RSA aufbaut, diskutiert[6].


Fazit


Die Feststellung, daß RSA patentiert sei, ist richtig. Dabei sollte man es aber nicht belassen. Wie die Autoren gezeigt haben, ist das RSA-Patent zumindest äußerst fragwürdig. Da das Patent und die Lizenzierungspolitik der Lizenzinhaber ein großes Hindernis für die Verbreitung von Digitalen Signaturen darstellen, sollte dieser Punkt weiter untersucht werden.

Einige Aktionen des RSA-Verfahrens lassen sich ausführen, ohne das Patent zu verletzen. Gerade die für den Einsatz Digitaler Signaturen so wichtige Verifikation fällt in der Regeln nicht unter das Patent.


Fußnoten

[1] Unter einer RSA-verschlüsselten Nachricht wird an dieser Stelle eine Nachricht verstanden, die entsprechend dem RSA-Algorithmus verschlüsselt wurde.

[2] Das amerikanische Patentrecht kennt unterschiedliche Arten von Patentansprüchen: unabhängige Ansprüche (independent claims) und abhängige Ansprüche (dependent claims). Abhängige Ansprüche heißen so, weil sie einen Anspruch unter Bezugnahme auf einen unabhängigen Anspruch anmelden (incorporate by reference). Eine eventuelle Patentverletzung muß als Verletzung eines unabhängigen Anspruches nachgewiesen werden. Ein abhängiger Patentanspruch kann nicht verletzt werden, wenn der als Bezug dienende unabhängige Anspruch nicht verletzt wurde.

[3] Es ist eine andere Spezialität des amerikanischen Rechtssystems, daß zur Feststellung der Frage, ob ein Mittel (Gerät, Verfahren) als Tatwerkzeug für die Beihilfe zur Tat zu betrachten ist, das Mittel im Ganzen und in Bezug auf die Tat untersucht wird. Stellt sich dabei heraus, daß es genügend andere Zwecke gibt, zu denen das Mittel verwandt werden kann und verwandt wird (substantial use), so wird es nicht als Tatwerkzeug qualifiziert. Beihilfe zur Tat wird dann in der Regel nicht unterstellt. Zum Thema `contributory infringement' siehe auch: [Rosenoer 1997], S.5, 6, 12, 71, 72, 82-84

[4] Der Name leitet sich von den drei entscheidenden Fällen vor Appellationsgerichten ab: In re Walter, In re Freeman und In re Abele.

[5] Insbesondere machte Dr. Rivest detaillierte Ausführungen zur Auswahl der Primzahlen und des Exponenten (e), die in der Patentschrift nicht enthalten sind.

[6] 1870 befaßte sich William S. Jevons damit.