elikaski/ecc_attacksBekannte Angriffe auf die Elliptische-Kurven-Kryptografie
In den letzten Jahren ist die Kryptografie mit elliptischen Kurven aufgrund ihrer hohen Effizienz und starken Sicherheit beliebt geworden. Der Zweck dieses Artikels ist es, dieses Thema auf eine relativ klarere Weise darzustellen, als es heute im Internet existiert.
In diesem Artikel werde ich vorstellen, was elliptische Kurven sind, die grundlegenden Operationen, die auf ihnen ausgeführt werden können, und wie sie im kryptografischen Kontext verwendet werden können. Der Großteil dieses Artikels besteht aus Beispielen bekannter Angriffe auf fehlerhafte Implementierungen oder falsche Verwendungen. Im gesamten Artikel versuche ich, die Erklärung in einen intuitiven und allgemeinen Teil sowie einen mathematischen Teil, der ins Detail geht, zu trennen. Der Leser ist eingeladen, sich auf den Teil zu konzentrieren, der ihn an der jeweiligen Stelle interessiert, und die Teile zu überspringen, die weniger relevant sind.
Viel Spaß beim Lesen!
Im Allgemeinen ist eine elliptische Kurve eine Art gekrümmte Linie. Ein Beispiel dafür ist die Parabel, deren Gleichung die Form $𝑦 = 𝑎𝑥^2 + 𝑏𝑥 + 𝑐$ hat und so aussieht:
Im Kontext der Kryptografie ist es üblich, elliptische Kurven zu verwenden, deren Gleichung die Form
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏$
hat. Beispielsweise sieht eine elliptische Kurve, die zur Gleichung $𝑦^2 = 𝑥^3 − 3𝑥 + 3$ gehört, so aus:
Die Gleichung der Kurve definiert die Beziehung zwischen der 𝑥-Koordinate eines Punktes auf der Kurve und seiner 𝑦-Koordinate. In einem kryptografischen Kontext beschränken wir 𝑥, 𝑦, 𝑎, 𝑏 auf ganze Zahlen und beschränken die Berechnungen auf modulo einer großen Primzahl. Die Gleichung der elliptischen Kurve lautet also:
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏\ \ \ \ (mod\ 𝑝)$.
Das bedeutet, dass wir eine endliche Anzahl von Punkten auf der Kurve haben. In mathematischer Sprache wird die Kurve als über einem endlichen Körper der Ordnung 𝑝 definiert bezeichnet. Daher hat nicht unbedingt jede 𝑥-Koordinate einen entsprechenden Punkt auf der Kurve, weil die zugehörige 𝑦-Koordinate möglicherweise keine ganze Zahl ist.
Die Menge der Punkte auf der Kurve besteht aus Paaren ganzer Zahlen (𝑥, 𝑦), die die Gleichung der Kurve erfüllen. Zusätzlich zu diesen Punkten wird ein weiterer spezieller Punkt namens „Unendlich“ definiert, der mit 𝒪 bezeichnet wird. In mathematischer Sprache ist dieser Punkt das neutrale Element der Menge der Punkte auf der Kurve bezüglich der Additionsoperation, die wir im nächsten Abschnitt definieren werden. Die Anzahl der Punkte auf der Kurve (einschließlich des Punktes 𝒪) wird als „Ordnung der Kurve“ bezeichnet.
Eine weitere Beobachtung ist, dass elliptische Kurven symmetrisch zur X-Achse sind. Das bedeutet, dass wenn der Punkt 𝑃 = (𝑥, 𝑦) auf der Kurve liegt, dann liegt auch der Punkt −𝑃 = (𝑥, −𝑦) auf der Kurve. Tatsächlich werden diese Punkte als „inverse“ zueinander betrachtet (daher die Bezeichnung −𝑃 für den zweiten Punkt), und das Ergebnis der Additionsoperation zwischen ihnen ist als das neutrale Element 𝒪 definiert.
Ein Satz namens Satz von Hasse liefert eine Abschätzung für #𝐸, die Ordnung der Kurve, und ist von der Größenordnung Θ(𝑝). Genauer gilt:
$𝑝 + 1 − 2\sqrt𝑝 ≤ 𝐸 ≤ 𝑝 + 1 + 2\sqrt𝑝$
Wenn zwei Punkte auf der Kurve gegeben sind, kann zwischen ihnen eine Additionsoperation definiert werden, die zu einem dritten Punkt führt, der ebenfalls auf der Kurve liegt. Um diesen Punkt geometrisch zu finden, zeichnen wir eine Linie zwischen den beiden gegebenen Punkten und verlängern sie, bis sie die Kurve in einem dritten Punkt schneidet. Dieser Punkt wird in Bezug auf die 𝑋-Achse gespiegelt, und der resultierende Punkt ist als das Ergebnis der Addition definiert.
Hier ist ein Diagramm, das zeigt, wie bei gegebenen Punkten 𝑃 und 𝑄 der Punkt 𝑃 + 𝑄 gefunden werden kann:
Eine Frage, die sich aus dieser Beschreibung ergeben könnte, ist: Was passiert, wenn die Linie, die zwischen den beiden Punkten gezeichnet wird, die Kurve nicht erneut schneidet? In diesem Fall sagt man, dass die Linie die Kurve im „Unendlichen“ schneidet, und das Ergebnis der Addition ist der Punkt 𝒪. Beachte, dass dieser Fall eintritt, wenn die gezeichnete Linie vertikal ist, das heißt, wir versuchen, einen Punkt 𝑃 mit seinem inversen Punkt −𝑃 zu addieren:
Daraus ergeben sich zwei grundlegende Identitäten. Für jeden Punkt 𝑃 gilt:
𝑃 + 𝒪 = 𝑃
𝑃 + (−𝑃) = 𝒪
Eine weitere Frage, die sich aus der geometrischen Beschreibung ergibt, ist: Wie addieren wir einen Punkt zu sich selbst? Wir haben gesehen, dass wir, um zwei verschiedene Punkte 𝑃 und 𝑄 zu addieren, eine Linie zwischen ihnen zeichnen und den Schnittpunkt ihrer Verlängerung mit der Kurve betrachten. Intuitiv lassen wir 𝑃 konstant und betrachten die Linie, die entsteht, wenn wir 𝑄 „näher und näher“ an 𝑃 heranbewegen, bis 𝑄 mit 𝑃 verschmilzt. Was wir erhalten, ist eine Linie, die immer stärker „tangential“ zur Kurve im Punkt 𝑃 ist, und genau diese Linie betrachten wir, wenn wir 𝑃 zu sich selbst addieren wollen:
