Mathematik, Informatik und Arithmetik

Wir haben früher bemerkt, dass die tatsächliche Durchführung von Kryptographie das Kombinieren von Mathematik und Informatik erfordert. In diesem Kapitel beschreiben wir mehrere Algorithmen und Rechentricks, die es ermöglichen, die diskrete Mathematik, die Kryptographie ist, auf Computern durchzuführen, die nicht unbedingt darauf ausgelegt sind, robuste Unterstützung für diskrete Mathematik zu bieten. Dieses Kapitel behandelt einige dieser Tricks und Algorithmen, die notwendig sind, um zu verstehen, wie man tatsächlich Kryptographie in der realen Welt durchführen könnte. Die erste Reihe von Tricks wurde ausgiebig beim Testen von Ganzzahlen auf Primzahleigenschaft verwendet, wobei die Bitmuster der Ganzzahlen verwendet wurden, um die Notwendigkeit einer Modulreduktion zu eliminieren. Multipräzise Arithmetik ist für einen Großteil der modernen Kryptographie erforderlich, wobei die Modulreduktion und Multiplikation die Kosten der Arithmetik dominieren. Die Multiplikation selbst wird mit schnellen Methoden wie der FFT durchgeführt, die wir hier behandeln, und die Reduktion kann mit der Montgomery-Multiplikation behandelt werden, die im Wesentlichen den Mersenne-Primzahltrick auf alle Ganzzahlmoduli erweitert.