WO/2018/171627 | METHOD FOR SEGMENTING TRANSMISSION BLOCK, AND WIRELESS COMMUNICATION DEVICE AND CHIP |
WO/2017/185377 | POLAR CODE ENCODING METHOD AND APPARATUS |
WO/2003/071688 | OBTAINING CYCLIC REDUNDANCY CODE |
ANONYMOUS: ""RSA-Kryptosystem" - Versionsunterschied - Wikipedia", 15 September 2015 (2015-09-15), pages 1 - 14, XP055307752, Retrieved from the Internet
WITTEN H., SCHULZ, R.-H.: "RSA & Co. in der Schule - Moderne Kryptologie, alte Mathematik, raffinierte Protokolle. Neue Folge - Teil 2: RSA für grosse Zahlen", LOG IN, vol. 26, no. 143, 2006, pages 50 - 58, XP009192000
ANONYMOUS: ""Hill-Chiffre" - Wikipedia", 7 June 2015 (2015-06-07), XP055308196, Retrieved from the Internet
Patentansprüche Verfahren zum rechnergestützten Erstellen einer asymmetrischen Prüfsumme durch einen ersten Kommunikationspart¬ ner (200), bei dem ein Prozessor (211) die folgenden Verfahrensschritte ausführt: Berechnen (105) einer abgebildeten Prüfsumme (c') mit¬ tels einer bijektiven Abbildung (G) aus einer ersten Prüfsumme ( c i ) , wobei die erste Prüfsumme ( ci ) aus der Menge aller mögli¬ chen Prüfsummen (C) mittels einer ersten Funktion ( Fi ) jeweils einer Nachricht (m) aus einer Menge aller möglichen Nachrichten (M) zugeordnet wird, die erste Prüfsumme ( ci ) insbesondere durch eine Abbildung der Menge aller möglichen Prüfsummen (C) durch eine zweite Funktion (F2) auf eine erste Men¬ ge (CA) aufbereitet wird; Verteilen (110) von einer Information, welche eine Umkehrfunktion (G-1) zu der bijektiven Abbildung (G) definiert, an mindestens einen zweiten Kommunikationspartner (300), wobei mittels der Umkehrfunktion (G-1) die erste Prüfsumme ( c i ) aus der abgebildeten Prüfsumme ( c ' ) be¬ rechnet wird; und Übermitteln (115) der abgebildeten Prüfsumme (c') und der Nachricht (m) an den mindestens einen zweiten Kommu¬ nikationspartner (300). Verfahren nach Anspruch 1, wobei zusätzlich zur Nachricht (m) und der abgebildeten Prüfsumme (c'), die erste Prüfsumme ( c i ) an den zweiten Kommunikationspartner (300) gesendet wird. Verfahren nach Anspruch 1 oder 2, wobei das Berechnen der abgebildeten Prüfsumme (c') ein Geheimnis bildet, das dem ersten Kommunikationspartner (200) bekannt ist. 4. Verfahren nach einem der vorhergehenden Ansprüche, wobei das Aufbereiten der erste Prüfsumme ( c i ) mit der zweiten Funktion (F2) in einem ersten Vorverarbeitungsschritt vor dem Berechnen der abgebildeten Prüfsumme (c') durchgeführt wird, und die bijektiven Abbildung (G) insbesondere eine Abbildung der ersten Menge (CA) auf sich selbst ist. Verfahren zum rechnergestützten Prüfen einer asymmetrischen Prüfsumme durch einen zweiten Kommunikationspart¬ ner (300), bei dem ein Prozessor (321) zum Ausführen der folgenden Schritte programmiert ist: Empfangen (150) einer Information, welche eine Umkehrfunktion (G-1) zu einer bijektiven Abbildung (G) definiert, von einem ersten Kommunikationspartner (200); Empfangen (155) einer abgebildeten Prüfsumme (c') und einer Nachricht (m) von einem ersten Kommunikationspart¬ ner (200); Berechnen (160) einer zweiten Prüfsumme (c2) mittels der Umkehrfunktion (G-1) unter Verwendung der abgebildeten Prüfsumme (c ' ) ; Berechnen (165) einer dritten Prüfsumme (C3) über die Nachricht (m) , wobei die dritte Prüfsumme (C3) aus der Menger aller mög¬ lichen Prüfsummen (C) mittels einer ersten Funktion ( Fi ) jeweils einer Nachricht (m) aus einer Menge aller möglichen Nachrichten (M) zugeordnet wird, die dritte Prüfsumme (C3) insbesondere durch eine Abbildung der Menge aller möglichen Prüfsummen (C) durch eine zweite Funktion (F2) auf eine erste Men¬ ge (CA) aufbereitet wird; und Feststellen (170) einer Korrektheit der Nachricht (m) , falls die zweite Prüfsumme (c2) mit der dritten Prüfsum¬ me (C3) eine ausreichende Übereinstimmung aufweist. Verfahren nach Anspruch 5, wobei zusätzlich zur Nachricht (m) und der abgebildeten Prüfsumme (c'), eine ers¬ te Prüfsumme ( c i ) vom ersten Kommunikationspartner empfangen wird, wobei die erste Prüfsumme ( c i ) vorzugsweise zusätzlich mit der zweiten Prüfsumme (c2) und/oder der dritten Prüfsumme (C3) verglichen wird, und wobei die Korrektheit der Nachricht (m) festgestellt wird, falls die erste Prüfsumme (ci) mit der zweiten Prüfsumme (c2) und/oder der dritten Prüfsumme (C3) eine ausreichende Übereinstimmung aufweist. Verfahren nach einem der vorhergehenden Ansprüche, wobei das Aufbereiten der dritten Prüfsumme (C3) mit der zwei¬ ten Funktion (F2) in einem zweiten Vorverarbeitungsschritt vor dem Feststellen der Korrektheit der Nachricht (m) durchgeführt wird, die bijektiven Abbildung (G) insbesondere eine Abbildung der ersten Menge (CA) auf sich selbst ist. Verfahren nach Anspruch 7, wobei die zweite Prüfsumme (c2) der ersten Prüfsumme (ci) ent¬ spricht, die jeweils von der zweiten Funktion (F2) auf¬ bereitet wurde, und die erste Prüfsumme (ci) und die dritte Prüfsumme (C3) insbesondere jeweils ein Element der ersten Menge (CA) sind . Verfahren nach einem der vorhergehenden Ansprüche, wobei die zweite Funktion (F2) eine 64-Bit Prüfsumme auf eine 32-Bit Prüfsumme abbildet oder die Identität ist. Verfahren nach einem der vorhergehenden Ansprüche, wobei die erste Menge (CA) oder die Menge aller möglichen Prüfsummen (C) ein Monoid ist, das Monoid als neutrales Element das Einselement umfasst und für das Monoid eine Operation einer Verknüpfung definiert ist, der erste Kommunikationspartner (200) ein invertierbares Element (a) des Monoids auswählt; der erste Kommunikationspartner (200) ein invertiertes Element ( ainv ) zu dem invertierbaren Element (a) berech¬ net; die abgebildete Prüfsumme (c') mittels der bijektiven Abbildung (G) in Form der Verknüpfung der ersten Prüfsumme ( c i ) mit dem invertierbaren Element (a) gebildet wird, die Information das invertierte Element (ainv) umfasst; und die Verknüpfung insbesondere von dem invertierbaren Element (a) und der abgebildeten Prüfsumme (c') das Einselement ergibt. Verfahren nach Anspruch 10, wobei die zweite Prüfsumme (c2) mittels der Umkehrfunktion (G-1) in Form der Verknüpfung des invertierten Elements (ainv) mit der abge¬ bildeten Prüfsumme (c') berechnet wird. Verfahren nach einem der Ansprüche 1 - 9, wobei die erste Menge (CA) oder die Menge aller möglichen Prüfsummen (C) ein Vektorraum ist; der erste Kommunikationspartner (200) eine invertierbare Matrix (A) aus dem Vektorraum bildet; der erste Kommunikationspartner (200) eine invertierte Matrix (A-1) aus der invertierbaren Matrix (A) bildet; die Information die invertierte Matrix (A-1) umfasst; und die abgebildete Prüfsumme (c') mittels der bijektiven Abbildung (G) in Form der Matrixmultiplikation der ersten Prüfsumme ( c i ) mit der Matrix (A) gebildet wird. Verfahren nach Anspruch 12, wobei die zweite Prüfsumme (c2) mittels der Umkehrfunktion (G-1) in Form der Matrix¬ multiplikation berechnet wird, indem die invertierte Matrix (A-1) mit der abgebildete Prüfsumme (c') multi¬ pliziert wird. Verfahren nach einem der Ansprüche 1 - 9, wobei der erste Kommunikationspartner (200) eine erste Tabelle bildet, in der zu allen möglichen Prüfsummen (C) jeweils eine abgebildete Prüfsumme (c') zugeordnet wird; der erste Kommunikationspartner (200) eine zweite Tabel¬ le bildet, in der jeweils einer abgebildeten Prüfsumme (c') eine Prüfsumme zugeordnet wird; die erste Tabelle die bijektive Abbildung (G) ist und die zweite Tabelle die Umkehrfunktion (G-1) der bijektiven Abbildung ist; und die Information über eine Umkehrfunktion die zweite Tabelle umfasst. Verfahren nach Anspruch 14, wobei die zweite Prüfsumme (c2) mittels der Umkehrfunktion (G-1) in Form der zweiten Tabelle berechnet wird. Verfahren nach Anspruch 14 oder 15, wobei die abgebildete Prüfsumme (c') als eine Ziffer oder als ein alphanu¬ merischer Wert implementiert wird. Erster Kommunikationspartner (200) zum Erzeugen einer asymmetrischen Prüfsumme, aufweisend: eine erste Berechnungseinrichtung, die mit einem Prozessor (211) eine abgebildete Prüfsumme (c') mittels einer bijektiven Abbildung (G) aus einer ersten Prüfsumme ( c i ) berechnet, wobei die erste Prüfsumme ( ci ) aus der Menge aller mögli¬ chen Prüfsummen (C) mittels einer ersten Funktion ( Fi ) jeweils einer Nachricht (m) aus einer Menge aller möglichen Nachrichten (M) zugeordnet wird, die erste Prüfsumme ( ci ) insbesondere durch eine Abbildung der Menge aller möglichen Prüfsummen (C) durch eine zweite Funktion (F2) auf eine erste Men¬ ge (CA) aufbereitet wird; eine Sendeeinrichtung (220), die eine Information, welche eine Umkehrfunktion (G-1) zu der bijektiven Abbildung (G) definiert, an mindestens einen zweiten Kommunikationspartner (300) verteilt, wobei mittels der Umkehrfunktion (G-1) die erste Prüfsumme ( ci ) aus der abgebildeten Prüfsumme (c') berechnet wird; und die abgebildete Prüfsumme (c') und die Nachricht (m) an den mindestens einen zweiten Kommunikations¬ partner (300) übermittelt. Erster Kommunikationspartner (200) nach Anspruch 17, wobei der erste Kommunikationspartner (200) ein virtualisiertes erstes Kommunikationsgerät ist. Zweiter Kommunikationspartner (300) zum Prüfen einer asymmetrischen Prüfsumme, aufweisend: eine Empfangseinrichtung (310), die eine Information, welche eine Umkehrfunktion (G-1) zu einer bijektiven Abbildung (G) definiert, von einem ersten Kommunikationspartner empfängt; eine abgebildete Prüfsumme (c') und eine Nachricht von dem ersten Kommunikationspartner empfängt; eine zweite Berechnungseinrichtung (320), die mit einem Prozessor (321) eine zweite Prüfsumme (c2) mittels der Umkehrfunk¬ tion (G-1) unter Verwendung der abgebildeten Prüfsumme (c') berechnet; eine dritte Prüfsumme (C3) über die Nachricht (m) berechnet, wobei die dritte Prüfsumme (C3) aus der Menger aller möglichen Prüfsummen (C) mittels einer ersten Funktion ( Fi ) jeweils einer Nachricht (m) aus einer Menge aller möglichen Nachrichten (M) zugeordnet wird, die dritte Prüfsumme (C3) insbesondere durch eine Abbildung der Menge aller möglichen Prüfsummen (C) durch eine zweite Funktion (F2) auf eine erste Menge (CA) aufbereitet wird; und eine Korrektheit der Nachricht (m) feststellt, falls die zweite Prüfsumme (c2) mit der dritten Prüfsumme (C3) eine ausreichende Übereinstimmung aufweist . 20. Zweiter Kommunikationspartner (300) nach Anspruch 19, wobei der zweite Kommunikationspartner (300) ein virtualisiertes zweites Kommunikationsgerät ist. 21. Computersystem (500), aufweisend ein erstes Kommunikationsgerät (200) nach Anspruch 17 oder 18, und ein zweites Kommunikationsgerät (300) nach Anspruch 19 oder 20. 22. Integrierter Schaltkreis, der mit Konfigurationsschrit¬ ten zur Durchführung des Verfahrens nach einem der Ansprüche 1-16 ausgerüstet wird oder mit Konfigurationsschritten derart konfiguriert ist, dass der integrierte Schaltkreis die Merk- male des ersten Kommunikationsgerätes nach Anspruch 17 oder 18, oder des zweiten Kommunikationsgerätes nach Anspruch 19 oder 20 aufweist. 23. Computerprogrammprodukt mit Programmbefehlen zur Durch- führung des Verfahrens nach einem der Ansprüche 1-16. 24. Bereitstellungsvorrichtung für das Computerprogrammprodukt nach Anspruch 23, wobei die Bereitstellungsvorrichtung das Computerprogrammprodukt speichert und/oder bereitstellt. |
Vorrichtung und Verfahren zum Erstellen einer asymmetrischen Prüfsumme
Die Erfindung bezieht sich auf ein Verfahren und Geräte zur Bildung einer asymmetrischen Prüfsumme und zur Prüfung der asymmetrischen Prüfsumme.
Bei der Übertragung von Daten treten gelegentlich Fehler auf, die die übertragenen Daten verändern. Um dies zu verhindern, wird häufig eine sogenannte Prüfsumme der Daten berechnet und zusammen mit diesen übertragen oder gespeichert. Beim Empfang oder Auslesen der Daten wird wiederum die Prüfsumme berechnet und mit der mit übertragenen Prüfsumme verglichen. Sind die beiden Checksummen gleich, so wird davon ausgegangen, dass mit hoher Wahrscheinlichkeit kein Fehler aufgetreten ist. Die Höhe dieser Wahrscheinlichkeit lässt sich prinzipiell aus den Eigenschaften des Berechnungsverfahrens ( PrüfSummenfunktion) und dem angenommenen Fehlermodell berechnen oder abschätzen.
Meist besteht für konkrete Anwendungen die Anforderung, dass sich die PrüfSummenfunktion effizient berechnen lässt. Beispiele für solche PrüfSummenfunktionen sind CRC16 (cyclic redundancy check 16) oder CRC32 (cyclic redundancy check 32) . Bei sicherheitsrelevanten Geräten werden oft durch Kunden oder Regularien bestimmte Sicherheitsintegritätslevel, wie beispielsweise in der Sicherheitsnorm EN 61508 festgelegt, gefordert. Dafür ist eine Gefährdungsbeurteilung erforderlich, in deren Rahmen auch die eingesetzten Prüfsummenfunkti- onen überprüft werden. Hierbei ist beispielsweise der Nach ¬ weis zu erbringen, dass nicht durch einen Fehler im Programmablauf trotz tatsächlich fehlerhafter Prüfsumme diese fälschlicherweise als richtig erkannt wird.
Dabei besteht das grundsätzliche Problem, dass nach dem Stand der Technik der Algorithmus zur Überprüfung der Prüfsumme auch den Algorithmus zur Berechnung der Prüfsumme enthält. Ein Empfänger einer Nachricht muss prinzipiell die Prüfsumme selbst berechnen, wobei der Empfänger nachfolgend auch als Verifizierer oder Verifizierergerät bezeichnet wird. Bei ei ¬ ner Fehlfunktion des Verifizierergerätes wird grundsätzlich davon ausgegangen, dass das Verifizierergerät die Prüfsumme über die verfälschten Daten versehentlich selbst nochmal berechnet und das Ergebnis der beiden eigenen Berechnungen ver gleicht, was die Funktion der Prüfsumme aushebelt, so dass keine Fehler mehr erkannt werden können. Sollte der
Verifizierer die Daten mit der verfälschten Prüfsumme weiter leiten, würden auch anderen Verifizierer keine Fehler mehr erkennen können.
Die Aufgabe der vorliegenden Erfindung ist es ein Verfahren und Geräte zur Berechnung und Prüfung einer asymmetrischen Prüfsumme bereitzustellen.
Die Aufgabe wird durch die in den unabhängigen Ansprüchen an gegebenen Merkmalen gelöst. In den Unteransprüchen sind vorteilhafte Weiterbildungen der Erfindung dargestellt.
Gemäß einem ersten Aspekt betrifft die Erfindung ein Verfahren zum rechnergestützten Erstellen einer asymmetrischen Prüfsumme durch einen ersten Kommunikationspartner, bei dem ein Prozessor zum Ausführen der Verfahrensschritte programmiert ist. Das Verfahren umfasst einen Verfahrensschritt zum Berechnen einer abgebildeten Prüfsumme mittels einer
bijektiven Abbildung aus einer ersten Prüfsumme, wobei die erste Prüfsumme aus der Menge aller möglichen Prüfsummen mit tels einer ersten Funktion jeweils einer Nachricht aus einer Menge aller möglichen Nachrichten zugeordnet wird, wobei die erste Prüfsumme insbesondere durch eine Abbildung der Menge aller möglichen Prüfsummen durch eine zweite Funktion auf ei ne erste Menge aufbereitet wird. Das Verfahren umfasst einen weiteren Verfahrensschritt zum Verteilen von einer Informati on, welche eine Umkehrfunktion zu der bijektiven Abbildung definiert, an mindestens einen zweiten Kommunikationspartner wobei mittels der Umkehrfunktion die erste Prüfsumme aus der abgebildeten Prüfsumme berechnet wird. Das Verfahren umfasst einen weiteren Verfahrensschritt zum Übermitteln der abgebildeten Prüfsumme und der Nachricht an den mindestens einen zweiten Kommunikationspartner.
Insbesondere wird das Aufbereiten der ersten Prüfsumme durch die Abbildung der Menge aller möglichen Prüfsummen durch die zweite Funktion auf die erste Menge durchgeführt, bevor die bijektiven Abbildung berechnet wird .
Mit dem Verfahren wird sichergestellt, dass der zweite Kommu ¬ nikationspartner, ebenfalls als Empfänger, Verifizierer oder Verifizierergerät bezeichnet, nicht fälschlicherweise die richtige Prüfsumme berechnet, obwohl die zu prüfende Nach ¬ richt fehlerhaft ist. Es kann beispielsweise durch einen Feh ¬ ler im Programmablauf vorkommen, dass trotz tatsächlich fehlerhafter Nachricht oder Prüfsumme diese fälschlicherweise als richtig erkannt wird.
Mit dem Verfahren wird außerdem sichergestellt, dass der zweite Kommunikationspartner nicht im Besitz der Information ist, um die abgebildete Prüfsumme versehentlich zu berechnen. Zur Verifikation der Prüfsumme genügt die Information, welche die Umkehrfunktion definiert. Durch den asymmetrischen Aufbau des der PrüfSummenerzeugung und der PrüfSummenverifizierung enthält somit der Verifizieralgorithmus nicht mehr den Algo ¬ rithmus zur Prüfsummenerzeugung .
Das Verfahren verwendet vorzugsweise zur Berechnung einer asymmetrischen Prüfsumme nicht-kryptographische asymmetrische Verfahren, damit die asymmetrische Prüfsumme möglichst schnell berechnet werden kann. Damit das Verfahren möglichst effizient ist, können beispielsweise Schlüssellängen der eingesetzten Verfahren sehr kurz gewählt werden. Diese können somit viel kürzer gewählt werden, als es für sicherheitskritische Anwendungen erforderlich wäre. Das Aufbereiten der Menge aller möglichen Prüfsummen durch die zweite Funktion auf die erste Menge, kann dazu dienen die Prüfsummen zunächst in ein Format zu bringen, mit dem eine bijektive Abbildung erst möglich ist oder mit der eine bijektive Abbildung besonders einfach zu berechnen ist. Bei einer konkreten Implementierung bereitet beispielsweise die zweite Funktion die erste Prüfsumme auf, bevor die bijektive Abbildung berechnet wird.
Bei einer ersten Ausführungsform des Verfahrens wird zusätzlich zur Nachricht und der abgebildeten Prüfsumme, die erste Prüfsumme an den zweiten Kommunikationspartner gesendet.
Durch das Senden der ersten Prüfsumme an den zweiten Kommunikationspartner, wird die Prüfung der Korrektheit der Nachricht noch weiter verbessert. Dies wird dadurch erreicht, dass die erste Prüfsumme zusätzlich mit der Prüfsumme vergli ¬ chen wird, die durch den zweiten Kommunikationspartner berechnet wird.
Bei weiteren Ausführungsformen des Verfahrens bildet das Be ¬ rechnen der abgebildeten Prüfsumme ein Geheimnis, das dem ersten Kommunikationspartner bekannt ist.
Dadurch, dass nur dem ersten Kommunikationspartner bekannt ist, wie die abgebildete Prüfsumme berechnet wird, ist es extrem unwahrscheinlich, dass durch einen Programmierfehler für eine fehlerhafte Nachricht fälschlicherweise eine korre te Prüfsumme berechnet wird.
Bei weiteren Ausführungsformen des Verfahrens wird das Aufbe- reiten der erste Prüfsumme mit der zweiten Funktion in einem ersten Vorverarbeitungsschritt vor dem Berechnen der abgebil- deten Prüfsumme durchgeführt, obei die bijektiven Abbildung insbesondere eine Abbildung de ersten Menge auf sich selbst ist . Gemäß einem weiteren Aspekt betrifft die Erfindung ein Verfahren zum rechnergestützten Prüfen einer asymmetrischen Prüfsumme durch einen zweiten Kommunikationspartner, bei dem ein Prozessor zum Ausführen der Verfahrensschritte programmiert ist. Das Verfahren umfasst einen Verfahrensschritt zum Empfangen einer Information, welche eine Umkehrfunktion zu einer bijektiven Abbildung definiert, von einem ersten Kommunikationspartner. Das Verfahren umfasst einen weiteren Verfahrensschritt zum Empfangen einer abgebildeten Prüfsumme und einer Nachricht von einem ersten Kommunikationspartner. Das Verfahren umfasst einen weiteren Verfahrensschritt zum Berechnen einer zweiten Prüfsumme mittels der Umkehrfunktion unter Verwendung der abgebildeten Prüfsumme, wobei die zweite Prüfsumme aus der Menger aller möglichen Prüfsummen mittels einer ersten Funktion jeweils einer Nachricht aus einer Menge aller möglichen Nachrichten zugeordnet wird, wobei die Menge aller möglichen Prüfsummen mit einer zweiten Funktion auf eine erste Menge abgebildet werden, wobei die bijektiven Abbil ¬ dung eine Abbildung der ersten Menge auf sich selbst ist. Das Verfahren umfasst einen weiteren Verfahrensschritt zum Be ¬ rechnen einer dritten Prüfsumme über die Nachricht. Das Verfahren umfasst einen weiteren Verfahrensschritt zum Feststel ¬ len einer Korrektheit der Nachricht, falls die zweite Prüf ¬ summe mit der dritten Prüfsumme eine ausreichende Überein ¬ stimmung aufweist.
Bei einer ersten Ausführungsform des Verfahrens wird zusätzlich zur Nachricht und der abgebildeten Prüfsumme, eine erste Prüfsumme vom ersten Kommunikationspartner empfangen, wobei die erste Prüfsumme vorzugsweise zusätzlich mit der zweiten Prüfsumme und/oder der dritten Prüfsumme verglichen wird, und wobei die Korrektheit der Nachricht festgestellt wird, falls die erste Prüfsumme mit der zweiten Prüfsumme und/oder der dritten Prüfsumme eine ausreichende Übereinstimmung aufweist.
Durch das Empfangen der ersten Prüfsumme vom ersten Kommunikationspartner, wird die Prüfung der Korrektheit der Nachricht noch weiter verbessert. Dies wird dadurch erreicht, dass die erste Prüfsumme zusätzlich mit der Prüfsumme vergli ¬ chen wird, die durch den zweiten Kommunikationspartner berechnet wird. Bei weiteren Ausführungsformen des Verfahrens wird das Aufbe ¬ reiten der dritten Prüfsumme mit der zweiten Funktion in einem zweiten Vorverarbeitungsschritt vor dem Feststellen der Korrektheit der Nachricht durchgeführt wird, wobei die bijektiven Abbildung insbesondere eine Abbildung der ersten Menge auf sich selbst ist.
Allgemein kann durch die Aufbereitung einer Prüfsumme durch die zweite Funktion beispielsweise die Prüfsumme in eine Form gebracht werden, mit der entweder erst eine bijektive Abbil- dung möglich ist, die bijektive Abbildung leichter berechenbar ist oder die bijektive Abbildung bestimmte vordefiniere Eigenschaften, beispielsweise mathematische Bedingungen, erfüllt. Die Informationen über die zweite Funktion können dem zweiten Kommunikationspartner separat übermittelt werden oder in den Informationen über die Umkehrfunktion enthalten sein.
Bei weiteren Ausführungsformen des Verfahrens bildet die zweite Funktion eine 64-Bit Prüfsumme auf eine 32-Bit Prüf ¬ summe ab oder die zweite Funktion ist die Identität.
Das Abbilden lässt sich sehr effizient durch einen Prozessor auf unterschiedlichen Rechnerarchitekturen berechnen. Insofern eignet sich deren Verwendung als zweite Funktion besonders gut, da diese schnell durch einfaches Abschneiden der überzähligen Bits berechenbar ist.
Die Identität kann beispielsweise für Anwendungsfälle verwen ¬ det werden, bei denen die Menger aller möglichen Prüfsummen bzw. die erste Prüfsumme nicht durch die zweite Funktion ver- ändert werden soll.
Bei weiteren Ausführungsformen des Verfahrens ist die erste Menge oder die Menge aller möglichen Prüfsummen ein Monoid, wobei das Monoid als neutrales Element das Einselement um- fasst und für das Monoid eine Operation einer Verknüpfung definiert ist, wobei der erste Kommunikationspartner ein invertierbares Element des Monoids auswählt, wobei der erste Kommunikationspartner ein invertiertes Element zu dem
invertierbaren Element berechnet, wobei die abgebildete Prüf ¬ summe mittels der bijektiven Abbildung in Form der Verknüpfung der ersten Prüfsumme mit dem invertierbaren Element gebildet wird, wobei die Information das invertierte Element umfasst, wobei die Verknüpfung insbesondere von dem
invertierbaren Element und der abgebildeten Prüfsumme das Einselement ergibt.
Eine Implementierung des Verfahrens auf Basis eines Monoids bietet den Vorteil, dass das Verfahren sehr effizient imple ¬ mentiert werden kann. Es ist beispielsweise auf Systemen mit begrenzter Rechenkapazität, wie beispielsweise Chipkarten einsetzbar, sodass die Chipkarte die asymmetrische Prüfsumme erzeugen kann.
Bei weiteren Ausführungsformen des Verfahrens wird die zweite Prüfsumme mittels der Umkehrfunktion in Form der Verknüpfung des invertierten Elements mit der abgebildete Prüfsumme be ¬ rechnet .
Eine Implementierung des Verfahrens auf Basis eines Monoids bietet den Vorteil, dass das Verfahren sehr effizient imple ¬ mentiert werden kann. Es ist beispielsweise auf Systemen mit begrenzter Rechenkapazität, wie beispielsweise Chipkarten einsetzbar, sodass die Chipkarte die asymmetrische Prüfsumme prüfen kann.
Bei weiteren Ausführungsformen des Verfahrens ist die erste Menge oder die Menge aller möglichen Prüfsummen ein Vektorraum, wobei der erste Kommunikationspartner eine
invertierbare Matrix aus dem Vektorraum bildet, wobei der erste Kommunikationspartner eine invertierte Matrix aus der invertierbaren Matrix bildet, wobei die Information die in- vertierte Matrix umfasst, wobei die abgebildete Prüfsumme mittels der bijektiven Abbildung in Form der Matrixmultiplikation der ersten Prüfsumme mit der Matrix gebildet wird. Eine Implementierung des Verfahrens auf Basis von Matrizen und einer Matrixmultiplikation bietet den Vorteil, dass das Verfahren extrem schnell auf Rechnerarchitekturen berechnet werden kann, die hinsichtlich Vektor und Matrizenberechnungen optimiert sind. Dies können beispielsweise Vektorrechner sein oder aber auch Grafikkarten.
Bei weiteren Ausführungsformen des Verfahrens wird die zweite Prüfsumme mittels der Umkehrfunktion in Form der Matrixmulti ¬ plikation berechnet, indem die invertierte Matrix mit der ab- gebildete Prüfsumme multipliziert wird.
Eine Implementierung des Verfahrens auf Basis von Matrizen und einer Matrixmultiplikation bietet den Vorteil, dass das Verfahren extrem schnell auf Rechnerarchitekturen berechnet werden kann, die hinsichtlich Vektor- und Matrizenberechnungen optimiert sind. Dies können beispielsweise Vektorrechner sein oder aber auch Grafikkarten.
Bei weiteren Ausführungsformen des Verfahrens bildet der ers- te Kommunikationspartner eine erste Tabelle, in der zu allen möglichen Prüfsummen jeweils eine abgebildete Prüfsumme zuge ¬ ordnet wird, wobei der erste Kommunikationspartner eine zwei ¬ te Tabelle bildet, in der jeweils einer abgebildete Prüfsumme eine Prüfsumme zugeordnet wird, wobei die erste Tabelle die bijektive Abbildung ist und die zweite Tabelle die Umkehr ¬ funktion der bijektiven Abbildung ist, wobei die Informationen über eine Umkehrfunktion die zweite Tabelle umfasst.
Eine Implementierung des Verfahrens auf Basis von Tabellen erlaubt eine Ausführung des Verfahrens auf extrem rechen ¬ schwachen Systemen, wie beispielsweise RFID Chips. Die Tabel ¬ len können jeweils als Lookup-Tabellen (LUT) bzw. Umsetzungstabellen implementiert werden. Die Verwendung von Tabellen hat insbesondere den Vorteil, dass eine Berechnung einer gebildeten Prüfsumme zur Laufzeit nicht notwendig ist.
Bei weiteren Ausführungsformen des Verfahrens wird die zweite Prüfsumme mittels der Umkehrfunktion in Form der zweiten Tabelle berechnet.
Eine Implementierung des Verfahrens auf Basis von Tabellen erlaubt eine Ausführung des Verfahrens auf extrem rechen ¬ schwachen Systemen, wie beispielsweise RFID Chips. Die Tabel ¬ len können jeweils als Lookup-Tabellen (LUT) bzw. Umsetzungstabellen implementiert werden. Die Verwendung von Tabellen hat insbesondere den Vorteil, dass eine Berechnung der zwei ¬ ten Prüfsumme zur Laufzeit nicht notwendig ist.
Bei weiteren Ausführungsformen des Verfahrens wird eine abge ¬ bildete Prüfsumme als eine Ziffer oder als ein alphanumeri ¬ scher Wert implementiert.
Durch die Darstellung der abgebildeten Prüfsumme als Ziffer oder als alphanumerischer Wert, lassen sich die Tabellen auf besonders einfache Weise erzeugen.
Gemäß einem weiteren Aspekt betrifft die Erfindung einen ersten Kommunikationspartner zum Erzeugen einer asymmetrischen Prüfsumme. Der erste Kommunikationspartner weist eine erste Berechnungseinrichtung und eine Sendeeinrichtung auf. Die erste Berechnungseinrichtung berechnet mit einem Prozessor eine abgebildeten Prüfsumme mittels einer bijektiven Abbildung aus einer ersten Prüfsumme, wobei die erste Prüfsumme aus der Menge aller möglichen Prüfsummen mittels einer ersten Funktion jeweils einer Nachricht aus einer Menge aller mögli ¬ chen Nachrichten zugeordnet wird, wobei die erste Prüfsumme wahlweise insbesondere durch eine Abbildung der Menge aller möglichen Prüfsummen durch eine zweite Funktion auf eine erste Menge aufbereitet wird. Die Sendeeinrichtung sendet eine Information, welche eine Umkehrfunktion zu der bijektiven Abbildung definiert, an mindestens einen zweiten Kommunikati- onspartner verteilt, wobei mittels der Umkehrfunktion die erste Prüfsumme aus der abgebildeten Prüfsumme berechnet wird und die Sendeeinrichtung die abgebildete Prüfsumme und die Nachricht an den mindestens einen zweiten Kommunikationspart- ner übermittelt.
Bei einer ersten Ausführungsform des ersten Kommunikationsgerätes ist das erste Kommunikationsgerät ein virtualisiertes erstes Kommunikationsgerät.
Ein virtualisiertes erstes Kommunikationsgerät hat den Vor ¬ teil, dass es sich kostengünstig in einem virtualisierten Rechnersystem einsetzten lässt und auf teure Hardware verzichtet .
Gemäß einem weiteren Aspekt betrifft die Erfindung einen zweiten Kommunikationspartner zum Prüfen einer asymmetrischen Prüfsumme, der eine Empfangseinrichtung und eine zweite Be ¬ rechnungseinrichtung aufweist. Die Empfangseinrichtung emp- fängt eine Information, welche eine Umkehrfunktion zu einer bijektiven Abbildung definiert, von einem ersten Kommunikationspartner und die Empfangseinrichtung empfängt eine abgebildete Prüfsumme und eine Nachricht von dem ersten Kommunikati ¬ onspartner. Die zweite Berechnungseinrichtung berechnet mit einem Prozessor eine zweite Prüfsumme mittels der Umkehrfunk ¬ tion unter Verwendung der abgebildeten Prüfsumme. Die zweite Berechnungseinrichtung berechnet mit dem Prozessor eine dritte Prüfsumme über die Nachricht, wobei die dritte Prüfsumme aus der Menger aller möglichen Prüfsummen mittels einer ers- ten Funktion jeweils einer Nachricht aus einer Menge aller möglichen Nachrichten zugeordnet wird, wobei die dritte Prüf ¬ summe insbesondere durch eine Abbildung der Menge aller mög ¬ lichen Prüfsummen durch eine zweite Funktion auf eine erste Menge aufbereitet wird. Die zweite Berechnungseinrichtung stellt eine Korrektheit der Nachricht fest, falls die zweite Prüfsumme mit der dritten Prüfsumme eine ausreichende Über ¬ einstimmung aufweist. Bei einer ersten Ausführungsform des zweiten Kommunikationsgerätes ist das zweite Kommunikationsgerät ein
virtualisiertes zweites Kommunikationsgerät. Ein virtualisiertes zweites Kommunikationsgerät hat den Vor ¬ teil, dass es sich kostengünstig in einem virtualisierten Rechnersystem einsetzten lässt und auf teure Hardware verzichtet . Desweiteren wird ein integrierter Schaltkreis, beispielsweise ein FPGA oder ein ASIC, mit den genannten erfindungsgemäßen Merkmalen beansprucht. Zusätzlich wird ein integrierter
Schaltkreis beansprucht, der mit Konfigurationsschritten zur Ausführung des genannten erfindungsgemäßen Verfahrens ausge- rüstet wird oder mit Konfigurationsschritten derart konfigu ¬ riert ist, dass der integrierter Schaltkreis die erfindungs ¬ gemäßen Merkmale des ersten Kommunikationsgerätes oder des zweiten Kommunikationsgerätes aufweisen. Desweiteren wird ein Computerprogrammprodukt mit Programmbe ¬ fehlen zur Durchführung des genannten erfindungsgemäßen Verfahrens beansprucht. Zusätzlich wird eine Bereitstellungsvorrichtung zum Speichern und/oder Breitstellen einer Datenstruktur, die das Computerprogrammprodukt umfasst, bean- sprucht . Die Bereitstellungsvorrichtung ist beispielsweise ein Datenträger, der das Computerprogrammprodukt speichert und/oder bereitstellt. Alternativ ist die Bereitstellungsvorrichtung beispielsweise ein Computersystem, ein Serversystem, ein Netzwerk, ein cloudbasiertes Rechnersystem und/oder vir- tuellen Rechnersystem, welches das Computerprogrammprodukt speichert und/oder bereitstellt. Diese Bereitstellung erfolgt vorzugsweise als Download des vollständigen Computerprogrammprodukts, kann aber beispielsweise auch als partieller Download erfolgen, der aus mehreren Teilen besteht und insbeson- dere über ein Peer-to-Peer Netzwerk heruntergeladen wird. Ein solches Computerprogrammprodukt wird beispielsweise unter Verwendung der Bereitstellungsvorrichtung in Form des Datenträgers in einem System eingelesen und führt die Programmbe- fehle aus, sodass das erfindungsgemäße Verfahren auf einem Computer zur Ausführung gebracht wird.
Die oben beschriebenen Eigenschaften, Merkmale und Vorteile dieser Erfindung sowie die Art und Weise, wie diese erreicht werden, werden klarer und deutlicher verständlich im Zusammenhang mit der folgenden Beschreibung der Ausführungsbeispiele, die im Zusammenhang mit den Figuren näher erläutert werden. Dabei zeigen:
Fig. 1 ein Ablaufdiagramm eines Ausführungsbeispiels zur
Erzeugung einer asymmetrischen Prüfsumme;
Fig. 2 ein Ablaufdiagramm eines Ausführungsbeispiels zum
Prüfen einer asymmetrischen Prüfsumme;
Fig. 3 eine schematische Darstellung eines Ausführungsbei ¬ spiels eines ersten Kommunikationspartners; Fig. 4 eine schematische Darstellung eines Ausführungsbei ¬ spiels eines zweiten Kommunikationspartners; und
Fig. 5 eine schematische Darstellung eines Ausführungsbei ¬ spiels eines Computersystems mit einem ersten Kom- munikationspartner und einem zweiten Kommunikationspartner .
In den Figuren sind funktionsgleiche Elemente mit denselben Bezugszeichen versehen, sofern nichts anderes angegeben ist.
Fig. 1 ist ein Ablaufdiagramm eines Ausführungsbeispiels zur Erzeugung einer asymmetrischen Prüfsumme.
Um eine asymmetrische Prüfsumme, die auch als abgebildete Prüfsumme c' bezeichnet wird, für eine Nachricht m zu berech ¬ nen, ist zunächst mittels einer ersten Funktion Fi , bei ¬ spielsweise einer PrüfSummenfunktion, jeder einzelnen Nach- rieht aus der Menge aller Nachrichten M eine Prüfsumme c aus der Menge aller Prüfsummen C zuordenbar:
Fi: M -> C (Formel 1)
Für eine Nachricht m wird somit zunächst eine erste Prüfsumme Ci mittels der ersten Funktion berechnet.
Eine zweite Funktion F 2 bereitet in einem ersten Vorverarbei- tungsschritt die erste Prüfsumme C \ auf. Dieser Vorverarbei ¬ tungsschritt ist optional, also nicht zwangsläufig notwendig, hat aber den Vorteil, dass die erste Prüfsumme ci beispiels ¬ weise damit in eine Darstellung gebracht wird, für die eine bijektive Abbildung erst möglich ist. Auch kann eine Darstel- lung gewählt werden, bei der die bijektive Abbildung leichter berechenbar ist oder die bijektive Abbildung bestimmte vorde ¬ finiere Eigenschaften, beispielsweise mathematische Bedingun ¬ gen, erfüllt. Diese Berechnungen können dann vorzugsweise durch den zweiten Kommunikationspartner ebenfalls ausgeführt werden, damit dieser die übermittelte abgebildete Prüfsumme c' prüfen kann. Einzelheiten hierzu werden in dem entsprechenden Ausführungsbeispiels der Fig. 2 erläutert.
Allgemeiner ausgedrückt wird die zweite Funktion F 2 verwen- det, um die Menge aller möglichen Prüfsummen C auf eine erste Menge C abzubilden, wobei hierdurch auch die erste Prüfsumme Ci abgebildet wird. Folglich ist die erste Prüfsumme Ci vor dem ersten Vorverarbeitungsschritt ein Element der Menge al ¬ ler möglichen Prüfsummen C und nach Anwendung der zweite Funktion F 2 ist somit die erste Prüfsumme ein Element der ersten Menge C. Die erste Prüfsumme C \ kann nach diesem ers ¬ ten Vorverarbeitungsschritt auch als eine aufbereitete erste Prüfsumme bezeichnet werden.
F 2 : C -> C (Formel 2) In einer Variante ist die zweite Funktion F 2 eine Funktion, die eine 64-Bit Prüfsumme durch das Abschneiden von Bits auf eine 32-Bit Prüfsumme abbildet.
5 In einer weiteren Variante ist die zweite Funktion F 2 eine
Funktion welche die Menge aller möglichen Prüfsummen C unverändert auf die erste Menge C abbildet. Dies kann beispiels ¬ weise sinnvoll sein, um die Menge aller möglichen Prüfsummen C unverändert für weitere Berechnungen zur Verfügung zu stel ¬ lt) len.
Mit anderen Worten ist es beispielsweise auch möglich die zweite Funktion F 2 immer auf die die erste Prüfsumme C \ anzu ¬ wenden. In Anwendungsszenarien in denen die erste Prüfsumme
15 Ci bzw. die Menge aller möglichen Prüfsummen C unverändert bzw. unaufbereitet für weitere Berechnungsschritte bereitge ¬ stellt werden soll, kann für die zweite Funktion F 2 bei ¬ spielsweise eine Identitätsfunktion bzw. eine identische Ab ¬ bildung der Menge aller möglichen Prüfsummen C auf die ersten
20 Menge C gewählt werden.
Um für eine Nachricht m die abgebildete Prüfsumme c' in einem ersten Verfahrensschritt 105 durch einen ersten Kommunikati ¬ onspartner zu berechnen, wird eine bijektive Abbildung G der
25 ersten Menge C oder der Menge aller möglichen Prüfsummen auf sich selbst verwendet. Mit anderen Worten handelt es sich bei der bijektiven Abbildung G um eine Funktion, die eine Permutation der abgebildeten Prüfsummen c' durchführt, wobei die erste Prüfsumme C \ ein Eingabeparameter für die bijektive Ab-
30 bildung G ist.
Damit lässt sich die abgebildete Prüfsumme c' für die erste Prüfsumme C \ leicht berechnen.
35 c ' = G(ci) (Formel 3)
Mit Hilfe einer Umkehrfunktion G -1 zur bijektiven Abbildung lässt sich die erste Prüfsumme Ci, die durch die zweite Funk- tion F2 aufbereitet worden sein kann bzw. die aufbereitete erste Prüfsumme, wieder aus der abgebildeten Prüfsumme c' be ¬ rechnen .
Ci = G "1 (c' ) (Formel 4)
Durch die bijektive Abbildung G bzw. der asymmetrischen Prüfsumme c', wird verhindert, dass die bijektive Abbildung G dasselbe Ergebnis erzeugt wie die Umkehrfunktion G -1 oder die Umkehrfunktion G -1 dasselbe Ergebnis erzeugt wie die
bijektive Abbildung G. Insbesondere ist für die bijektive Ab ¬ bildung G und die Umkehrfunktion G -1 eine Involution ausgeschlossen. Mit anderen Worten wird hierdurch ausgeschlossen, dass die bijektive Abbildung G und die Umkehrfunktion G -1 übereinstimmen. Ein Beispiel für eine solche Involution wäre eine Exklusive-Oder Verknüpfung der ersten Prüfsumme C \ mit einer Konstanten a.
G(ci) = Ci xor a (Formel 5)
Je nach Rechenmodell oder Rechnerarchitektur sind für bestimmte Varianten zur Berechnung von der bijektiven Abbildung ausgeschlossen. Insbesondere sind Berechnungen der nachfolgenden Art ausgeschlossen:
G(ci) = Ci + a mod 2 32 (Formel 6) wobei mod die Modulo-Operation ist. Eine solche Berechnung der abgebildeten Prüfsumme ist deshalb problematisch, da die Umkehrfunktion G -1 zur Formel 6
G _1 (c') = c' - a mod 2 32 (Formel 7) eine Subtraktion aufweist. Dies ist insofern problematisch, da sich die Subtraktion in den meisten Rechenwerken nur durch ein Bit, also einen einfachen Schalter, von der Addition unterscheidet . Mit anderen Worten ist für die bijektive Abbildung G und die Umkehrfunktion G -1 vorzugsweise eine Involution ausgeschlos ¬ sen. Die bijektive Abbildung G und die Umkehrfunktion G -1 erfüllen darüber hinaus vorzugsweise die Bedingung, dass je- weils die Berechnung der bijektive Abbildung G und der Umkehrfunktion G -1 derart unterschiedlich ist, dass triviale Bitfehler kein identisches Ergebnis für die beiden Funktionen liefern. Dies trifft insbesondere auf die Additionsoperation und die Subtraktionsoperation zu.
Damit ein zweiter Kommunikationspartner die abgebildete Prüfsumme c' verifizieren kann, wird diesem eine Information in einem zweiten Verfahrensschritt 110 bereitgestellt, welche die Umkehrfunktion G -1 definiert. Dieses Bereitstellen kann beispielsweise zu einem früheren Zeitpunkt geschehen, sodass diese Information für viele abgebildete Prüfsummen verwendet werden kann.
In einem dritten Verfahrensschritt 115 wird dem zweiten Kom- munikationspartner nun die abgebildete Prüfsumme c' und die Nachricht m übermittelt.
Fig. 2 ist ein Ablaufdiagramm eines Ausführungsbeispiels zum Prüfen einer asymmetrischen Prüfsumme. Die Berechnungsvor- Schriften und die mathematischen Bedingungen, die bereits in der Beschreibung zur Fig. 1 erläutert wurden, sollen auch für die nachfolgende Erläuterungen zu den Fig. 2 - 5 gelten.
Um die asymmetrische Prüfsumme durch einen zweiten Kommunika- tionspartner zu prüfen, wird in einem vierten Verfahrensschritt 150 die Information, welche die Umkehrfunktion G -1 zu der bijektiven Abbildung G definiert, von dem ersten Kommunikationspartner empfangen. In einem fünften Verfahrensschritt 155 wird dann die abgebil ¬ dete Prüfsumme c' und die Nachricht m von dem ersten Kommuni ¬ kationspartner empfangen. In einem sechsten Verfahrensschritt 160 wird eine zweite Prüfsumme C2 mittels der Umkehrfunktion G -1 unter Verwendung der abgebildeten Prüfsumme c' und unter Nutzung beispielswei ¬ se eines Prozessors berechnet. Die zweite Prüfsumme C2 ent- spricht dabei der ersten Prüfsumme Ci, die von der zweiten Funktion F 2 aufbereitet worden sein kann. Falls die zweite Funktion F 2 die ersten Prüfsumme C \ aufbereitet hat, so ist dem zweiten Kommunikationspartner vorzugsweise die zweite Funktion F 2 bekannt.
In einem siebten Verfahrensschritt 165 wird dann eine dritte Prüfsumme C 3 über die Nachricht m berechnet. Hierzu wird vor ¬ zugsweise die erste Funktion Fi verwendet, damit für die PrüfSummenberechnung jeweils über die Nachricht m der gleiche Algorithmus verwendet wird. Zusätzlich wird die zweite Funk ¬ tion F 2 in einem zweiten Vorverarbeitungsschritt auf die dritte Prüfsumme C 3 angewendet, analog zur Anwendung der zweiten Funktion F 2 auf die erste Prüfsumme Ci. Der zweite Vorverarbeitungsschritt wird jedoch nur ausgeführt, wenn die- ser tatsächlich notwendig ist, also der erste Vorverarbei ¬ tungsschritt bei der Erzeugung der abgebildeten Prüfsumme c' ausgeführt wurde. Die dritte Prüfsumme kann nach Anwendung der zweiten Funktion F 2 auch als dritte aufbereitete Prüfsum ¬ me bezeichnet werden.
In einem achten Verfahrensschritt 170 wird die Korrektheit der Nachricht m festgestellt, falls die zweite Prüfsumme C2 mit der dritten Prüfsumme C 3 eine ausreichende Übereinstim ¬ mung aufweist.
Für die Berechnungen bzw. für die erste Funktion Fi der ersten Prüfsumme C \ und der dritten Prüfsumme C 3 wird die glei ¬ che PrüfSummenfunktion verwendet. Ebenfalls wird für die zweite Funktion F 2 jeweils ebenfalls der gleiche Algorithmus verwendet, sofern der erste Vorverarbeitungsschritt bei der Erzeugung der abgebildeten Prüfsumme c' durchgeführt wurde. Die zweite Prüfsumme C2 entspricht dabei der ersten Prüfsumme
Cl . Die Informationen über die erste Funktion Fi und zweite Funktion F2 können allgemein bekannt sein, über eine separate Nachricht zwischen den Kommunikationspartnern ausgetauscht werden, durch einen Administrator konfiguriert werden
und/oder in der Information über die Umkehrfunktion G -1 enthalten sein.
Der prinzipielle Ablauf des Verfahrens zwischen dem ersten Kommunikationspartner und dem zweiten Kommunikationspartner wird nachfolgend erläutert.
Auf der Seite des ersten Kommunikationspartners ist die Be ¬ rechnungsvorschrift zur Bildung der bijektiven Abbildung G implementiert. Auf der Seite des zweiten Kommunikationspart ¬ ners ist die Berechnungsvorschrift für die Umkehrfunktion G -1 implementiert. Der erste Kommunikationspartner berechnet die erste Prüfsumme ci über die Nachricht m, bereitet die erste Prüfsumme C \ mit der zweiten Funktion F2 auf und bildet dann die zugehörige abgebildete Prüfsumme c' . Zusätzlich zur ers ¬ ten Prüfsumme C \ oder anstelle der ersten Prüfsumme C \ wird dann die abgebildete Prüfsumme c' übermittelt.
Beim zweiten Kommunikationspartner kommt die Nachricht m und die zusätzliche die abgebildete Prüfsumme c' an. Der zweite Kommunikationspartner berechnet nun die dritte Prüfsumme C 3 und wendet dann die zweite Funktion F2 auf dritte Prüfsumme C 3 an. Außerdem berechnet er die zweite Prüfsumme c 2 , und vergleicht das Ergebnis mit der dritten Prüfsumme C 3 . Falls keine Übertragungsfehler aufgetreten sind, sind die zweite Prüfsumme C2 und die dritte Prüfsumme C 3 identisch. Ist zu ¬ sätzlich die erste Prüfsumme C \ mit übertragen worden, stimmt auch die erste Prüfsumme C \ mit der zweiten Prüfsumme C2 überein, sofern die abgebildete Prüfsumme c' fehlerfrei über- tragen wurde. Falls ein Übertragungsfehler aufgetreten ist, sind die zweite Prüfsumme C2 und die dritte Prüfsumme C 3 mit hoher Wahr ¬ scheinlichkeit nicht gleich. Da dem zweiten Kommunikationspartner die bijektive Abbildung G nicht bekannt ist, kann der zweite Kommunikationspartner die erste Prüfsumme C \ nicht berechnen, und deshalb nicht versehentlich eine falsche Prüfsumme verwenden (oder sogar weiterverschicken) , ohne dass das später bemerkt wird.
Anders als bei kryptographischen Verfahren ist es dabei für den genannten Anwendungszweck unerheblich, ob die bijektive Abbildung G aus der Umkehrfunktion G -1 effizient berechnet werden kann. Es reicht aus, dass die Berechnung von der bijektiven Abbildung G aus der Umkehrfunktion G -1 hinreichend nichttrivial ist, beispielsweise einen Algorithmus benötigt, der auf Seite des zweiten Kommunikationspartners nicht imple ¬ mentiert ist, so dass diese Berechnung nicht „versehentlich" durchgeführt werden kann.
In einer Variante der beschriebenen Ausführungsbeispiele wird die bijektive Abbildung G und die Umkehrfunktion G -1 mittels einer Monoid-Verknüpfung implementiert. Die erste Menge C' ist dabei ein Monoid, also eine Halbgruppe mit neutralem Element 1 und Verknüpfung „*". Falls die zweite Funktion F 2 nicht auf die Menge aller Prüfsummen C angewendet wurde, ist das Monoid die Menge aller Prüfsummen C. Der erste Kommunikationspartner wählt ein invertierbares Ele ¬ ment a des Monoids, wobei gilt a * a iriv = 1 (Formel 8) wobei ai nv das invertierte Element zu dem invertierbaren Ele ¬ ment a ist. Der erste Kommunikationspartner verteilt das invertierte Element ai nv an den zweiten Kommunikationspartner, und behält das invertierbare Element a. Die bijektive Abbildung ist dann gegeben durch
G (ci) = Ci * a (Formel 9)
Und die Umkehrfunktion G ist gegeben durch
G _i (c ' ) = c (Formel 10) Nachfolgend wird eine mögliche Implementierung mittels eines Monoids im Einzelnen erläutert.
Im Folgenden sei das Monoid gegeben durch die Menge {0x0, 0x1, 0x2, Oxffffffff} zusammen mit der Multiplikation mo- dulo 0x100000000. Diese modulare Multiplikation lässt sich sehr effizient implementieren, da vom Resultat der normalen Multiplikation einfach die niederwertigsten 32 Bit verwendet werden . In diesem Monoid ist jede ungerade Zahl invertierbar. Sei al ¬ so beispielsweise das invertierbare Element a = 0xc0cl7487, dann ist das invertierte Element ai nv = 0xa4751137. Dies kann beispielsweise mit Hilfe des Euklidschen Algorithmus berech ¬ net werden. Das Produkt des invertierbaren Elements a und des invertierten Elements ai nv ist a · a± inv = 0x7bd4140700000001
= 1 mod 0x100000000 (Formel 11) wobei die Multiplikation ganzer Zahlen ist.
Weiter sei die erste Funktion Fi eine PrüfSummenfunktion, beispielsweise die CRC32 Funktion. Hier ist es möglich als zweite Funktion F2 die identische Abbildung zu wählen, weil die Bildmenge von CRC32 mit dem Monoid übereinstimmt.
Sei nun beispielsweise die erste Prüfsumme Ci = 0x82441710 die CRC32-Prüfsumme einer geeigneten Nachricht m, auf die zu- sätzlich die zweite Funktion F 2 angewendet wurde, so ist die abgebildete Prüfsumme c' definiert durch c' = c * a = 0xef6b6970 (Formel 12)
Diese Zahl wird an den zweiten Kommunikationspartner zusammen mit der Nachricht m übermittelt.
Der Zweite Kommunikationspartner berechnet nun die dritte Prüfsumme C 3 mit Hilfe der CRC 32 Funktion über die Nachricht m und wendet anschließend die zweite Funktion F 2 auf diese an. Zusätzlich wird die zweite Prüfsumme C2 berechnet: c 2 = c' * a iriv = 0x82441710 (Formel 13)
Stimmen die zweite Prüfsumme C2 und die dritte Prüfsumme C 3 überein, wird die Nachricht m als fehlerfrei angesehen. Die abgebildete Prüfsumme c' könnte der zweite Kommunikations ¬ partner jedoch nicht selbst berechnen, weil er das invertier- bare Element a nicht kennt, und der Euklidsche Algorithmus nicht implementiert ist.
Neben der oben beschriebenen Multiplikation modulo einer Potenz von 2 zur Konstruktion des Monoid wäre beispielsweise auch eine Multiplikation modulo einer Primzahl p denkbar. Das sich ergebende Monoid ist dann eine Gruppe, sofern die 0 aus ¬ geschlossen wird. Daraus folgt, dass jedes Element invertier ¬ bar ist. Die Berechnung des Inversen erfolgt wieder mit Hilfe des Euklidschen Algorithmus. Da die Primzahl p eine Konstante ist, lässt sich die modulare Multiplikation effizient imple ¬ mentieren, beispielsweise durch Vorberechnung von 1/p in hinreichender Genauigkeit, wodurch die Division sich zu einer Multiplikation vereinfacht. In einer Variante der beschriebenen Ausführungsbeispiele wird die bijektive Abbildung G und die Umkehrfunktion G -1 mittels Matrizen und der Matrixmultiplikation implementiert. Die erste Menge C oder die Menge aller Prüfsummen C ist ein Vektorraum und der erste Kommunikationspartner bildet eine invertierbare Matrix A aus dem Vektorraum. A = C * C (Formel 14)
Der erste Kommunikationspartner berechnet eine invertierte Matrix A -1 zu der invertierbaren Matrix A und verteilt diese an den zweiten Kommunikationspartner.
Die bijektive Abbildung ist dann gegeben durch
G(ci) = A * ci (Formel 15) wobei „*" die Matrixmultiplikation ist.
Und die Umkehrfunktion G -1 ist gegeben durch
G _1 (c') = A "1 * c' (Formel 16)
In einer weiteren Variante der beschriebenen Ausführungsbeispiele wird die bijektive Abbildung G und die Umkehrfunktion G -1 mittels Tabellen implementiert. Die bijektive Abbildung G bzw. die abgebildete Prüfsumme c' wird hierbei durch eine erste Tabelle gebildet, in der zu je ¬ der Prüfsumme c ein passender Wert zu seiner bijektiven Abbildung G bzw. G(c) gespeichert ist. Auch hier können die Prüfsummen durch die zweite Funktion F2 aufbereitet worden sein, bevor diese weiterverarbeitet werden. Die erste Prüf ¬ summe Ci wird als ein Eingangswert beispielsweise für eine Umsetzungstabelle verwendet, um die abgebildete Prüfsumme c' zu berechnen. Die Umkehrfunktion G -1 bzw. die zweite Prüfsumme C2 wird durch eine zweite Tabelle berechnet, die zu jeder abgebildeten Prüfsumme die passende Prüfsumme enthält. Mit anderen Worten wird die abgebildete Prüfsumme c' als Ein ¬ gangswert für die zweite Tabelle verwendet, um die zweite Prüfsumme C2 zu erhalten. Fig. 3 ist eine schematische Darstellung eines Ausführungs ¬ beispiels eines ersten Kommunikationspartners 200, der auch als Erzeugungsgerät oder Sender bezeichnet wird. Das Erzeu- gungsgerät weist eine erste Berechnungseinrichtung 210 und eine Sendeeinrichtung 220 auf, die über einen Bus 230 kommu ¬ nikativ miteinander verbunden sind.
Die erste Berechnungseinrichtung 210 berechnet mit einem Pro- zessor 211 eine abgebildete Prüfsumme mittels einer
bijektiven Abbildung aus einer ersten Prüfsumme, wobei die erste Prüfsumme aus der Menge aller möglichen Prüfsummen mittels einer ersten Funktion jeweils einer Nachricht aus einer Menge aller möglichen Nachrichten zugeordnet wird, wobei die erste Prüfsumme insbesondere durch eine Abbildung der Menge aller möglichen Prüfsummen durch eine zweite Funktion auf eine erste Menge aufbereitet wird.
Die Sendeeinrichtung 220, verteilt eine Information, welche eine Umkehrfunktion zu der bijektiven Abbildung definiert, an mindestens einen zweiten Kommunikationspartner, der auch als Verifizierer oder Verifizierergerät bezeichnet wird, wobei mittels der Umkehrfunktion die erste Prüfsumme aus der abge ¬ bildeten Prüfsumme berechnet wird. Die Sendeeinrichtung 220 übermittelt zusätzlich die abgebildete Prüfsumme und die
Nachricht an den mindestens einen zweiten Kommunikationspart ¬ ner .
Fig. 4 ist eine schematische Darstellung eines Ausführungs- beispiels eines zweiten Kommunikationspartners 300, der auch als Sender, Verifizierer oder Verifizierergerät bezeichnet wird. Das Verifizierergerät weist eine Empfangseinrichtung 310 und eine zweite Berechnungseinrichtung 320 auf, die über einen Bus 350 kommunikativ miteinander verbunden sind.
Die Empfangseinrichtung 310, empfängt eine Information, welche eine Umkehrfunktion zu einer bijektiven Abbildung definiert, von einem ersten Kommunikationspartner, der auch als Erzeugungsgerät bezeichnet wird. Zusätzlich empfängt die Emp ¬ fangseinrichtung 310 eine abgebildete Prüfsumme und eine Nachricht von dem ersten Kommunikationspartner. Die zweite Berechnungseinrichtung 320 berechnet mit einem
Prozessor 321 eine zweite Prüfsumme mittels der Umkehrfunkti ¬ on unter Verwendung der abgebildeten Prüfsumme.
Die zweite Berechnungseinrichtung 320 berechnet zusätzlich vorzugsweise mit dem Prozessor 321 eine dritte Prüfsumme über die Nachricht, wobei die dritte Prüfsumme aus der Menger al ¬ ler möglichen Prüfsummen mittels einer ersten Funktion jeweils einer Nachricht aus einer Menge aller möglichen Nachrichten zugeordnet wird, wobei die dritte Prüfsumme insbeson- dere durch eine Abbildung der Menge aller möglichen Prüfsummen durch eine zweite Funktion auf eine erste Menge aufberei ¬ tet wird.
Darüber hinaus stellt die zweite Berechnungseinrichtung 320 eine Korrektheit der Nachricht fest, falls die zweite Prüf ¬ summe mit der dritten Prüfsumme eine ausreichende Überein ¬ stimmung aufweist.
Fig. 5 ist eine schematische Darstellung eines Ausführungs- beispiels eines Computersystems 500.
Das Computersystem 500 umfasst einen ersten Kommunikations ¬ partner 200 entsprechend der Beschreibung zu Fig. 3 beispielsweise in Form eines ersten Computers, beispielsweise ein IBM-kompatibler Personal Computer mit einem Linux- Betriebssystem. Der erste Kommunikationspartner 200 ist über ein Netzwerk, beispielsweise ein Ethernet Netzwerk oder ein Tokenring Netzwerk, mit einem zweiten Kommunikationspartner 300 entsprechend der Beschreibung zu Fig. 4 in Form eines zweiten Computers, beispielsweise einen Apple iMac®, verbun ¬ den . Der erste Kommunikationspartner 200 und der zweite Kommunika ¬ tionspartner 300 umfassen beispielsweise jeweils marktübliche Hardwarekomponenten, wie ein Anzeigegerät vorzugsweise in Form eines TFT Monitors, insbesondere mindestens ein Eingabe- gerät vorzugsweise in Form einer Computermaus und/oder einer Tastatur, mindestens einen Datenträger vorzugsweise in Form einer Solid-State Festplatte und/oder eines DVD-Lese- und/oder Schreiblaufwerkes, einen Prozessor, vorzugsweise ei ¬ nen Intel x86 kompatiblen Prozessor, eine Netzwerkschnitt- stelle, vorzugsweise eine Ethernet-Schnittstelle, Arbeits ¬ speicher, vorzugsweise DDR SDRAM (Double Data Rate
Synchronous Dynamic Random Access Memory), und/oder weitere dem Fachmann bekannten Hardware oder Peripheriegeräten. Die Hardwarekomponenten des ersten Kommunikationspartners 200 sind beispielsweise über eine Hauptplatine und einen Datenbus miteinander kommunikativ verbunden. Die Hardwarekomponenten des zweiten Kommunikationspartners 300 sind ebenfalls bei ¬ spielsweise über eine Hauptplatine und einen Datenbus mitei- nander kommunikativ verbunden. Die jeweiligen Hauptplatinen des ersten Kommunikationspartners 200 und des zweiten Kommu ¬ nikationspartners 300 verfügt vorzugsweise über mindestens einen Steckplatz oder andere Schnittstellen, beispielsweise eine Universal Serial Bus (USB) oder eine FireWire Schnitt- stelle, zur Verbindung von einem Peripheriegerät über den
Datenbus mit dem Prozessor. Der Steckplatz ist vorzugsweise als Peripheral Component Interconnect Express Bus (PCIe) aus ¬ gebildet . Das Verfahren, das in der Beschreibung zu Fig. 2 und Fig. 3 erläutert wurde, wird beispielsweise durch eine Vorrichtung oder mehrere Vorrichtungen implementiert, die als Steckkarte oder USB Gerät ausgebildet sind. Diese Steckkarte ist bei ¬ spielsweise in den Steckplatz eingesetzt und weist somit eine kommunikative Verbindung mit den Hardwarekomponenten und/oder weiterer Peripherie auf. In einer Variante wird das Verfahren durch Programmcode im ¬ plementiert, der durch den Prozessor ausgeführt wird.
In einer weiteren Variante führt beispielsweise der erste Kommunikationspartner 200 mindestens einen virtualisierten Computer aus, der eine virtualisierte Steckkarte aufweist, die das Verfahren implementiert, oder das Verfahren durch Programmcode implementiert, der durch den virtualisierten Prozessor ausgeführt wird.
In einer weiteren Variante wird das Verfahren beispielsweise durch einen Terminalserver mittels einer Steckkarte oder Programmcode implementiert, wobei der Terminalserver ebenfalls ein virtualisierter Terminalserver sein kann. Der Terminal- Server bedient dann einen Terminalclient, sodass ein Nutzer oder ein anderes Programm das Verfahren ausführen kann.
In einer weiteren Variante ist der erste Kommunikationspart ¬ ner ein erster Prozess oder ein erstes Programm und der zwei- te Kommunikationspartner ist ein zweiter Prozess oder ein zweites Programm, das auf einem Computer ausgeführt wird.
In einer weiteren Variante ist ein integrierter Schaltkreis, beispielsweise ein FPGA oder ein ASIC, mittels Programmbefeh- len in einen Zustand versetzt, in einen Zustand bringbar, um das erfindungsgemäße Verfahren auszuführen.
Obwohl die Erfindung im Detail durch die Ausführungsbeispiele näher illustriert und beschrieben wurde, so ist die Erfindung nicht durch die offenbarten Beispiele eingeschränkt und ande ¬ re Variationen können vom Fachmann hieraus abgeleitet werden, ohne den Schutzumfang der Erfindung zu verlassen.