Große Exponentiale und 8-Bit-PIC-Prozessoren

Wie crasic in den Kommentaren betonte, müssen Sie das tatsächliche Exponential nicht wirklich berechnen. Sie können modulare Arithmetik verwenden, um den maximalen Wert zu reduzieren, den Sie speichern müssen:

Für$(a b)~\textrm{mod}~m$, der Höchstwert, den Sie jemals speichern müssen, ist$(m-1)^2$, was m=23bedeutet, dass Sie 484 speichern können müssen. Dies liegt außerhalb des Bereichs von 8-Bit-Zahlen, passt aber in 16-Bit. Wie Olin jedoch betonte, können einige 8-Bit-Mikros 16-Bit-Werte effizient manipulieren, sodass dies kein großes Problem darstellt.

Eine allgemeine Implementierung in C könnte wie folgt aussehen:

uint16_t exp_mod(uint16_t base, uint16_t power, uint16_t m)
{
    uint16_t res = 1;
    while(power)
    {
        if(power & 1)
        {
            res = (res * base) % m;
        }
        res = (res*res) % m;
        power >>= 1;
    }
    return  res;
}

Wenn Ihr uC über einen effizienten Modulo-Befehl verfügt, ist dies normalerweise gut genug. Wenn Sie dies jedoch nicht wissen und wissen, dass n immer ein bestimmter Wert sein wird, gibt es eine effiziente Implementierung der Division (und damit Modulo) von T. Granlun und PL Montomery . Agner Fog hat auch eine Beschreibung, wie das funktioniert .

Hier ist eine gehackte Implementierung für m=23.

uint16_t mod23(uint16_t m)
{
    // note: I didn't actually figure out what n and the error correction term is suppose
    // to be, I just guessed a value for n which produces a simple function
    // only checked to be correct for m <= 484
    // 
    // n = 11
    uint16_t res = a - 23*((m*89)>>11);
    return (res == 23) ? 0 : res;
}

Die einzigen erforderlichen 16-Bit-Operationen sind dann:

• Addition Subtraktion
• Multiplikation
• bitweises Verschieben
• bitweise und
• Gleichberechtigung Vergleich

Ich bin mit dem PIC-Befehlssatz nicht vertraut, aber hier ist ungefähr die Anzahl der Anweisungen für den schlimmsten Fall:

• 4*log2(power)Vergleiche
• 4*log2(power)springt
• 2*log2(power)Subtraktionen
• 3*log2(power)bitweise Verschiebung
• 6*log2(power)Multiplikationen

Für power=15sind dies ungefähr 76 Anweisungen. Beachten Sie, dass dies nachlassen kann, wenn Sie Zugriff auf Multiplizier-Addier-Anweisungen oder andere spezielle Anweisungen haben. Das fände ich durchaus vernünftig.

Hinweis: Diese Implementierung hat variable Timings dafür, wie lange exp_mod abhängig vom Eingabeparameter dauert, und ist daher anfällig für Timing-basierte Cracks (obwohl für einen 16-Bit-Schlüssel auch nur Brute-Force-Cracking möglich ist). Es ist relativ einfach, diesen Code so zu ändern, dass er dagegen widerstandsfähig ist, indem Dummy-Anweisungen eingefügt werden, die theoretisch nur die durchschnittliche Leistung beeinträchtigen sollten und die Leistung im schlimmsten Fall unverändert bleibt.

Jede Mathematik kann auf jedem Prozessor durchgeführt werden. Die Frage ist nur, wie viele Operationen und damit wie viel Zeit es dauern wird.

5 ¹⁵ = 2 ^34,8 , erfordert also mindestens 35 Bits zum Ausdrücken. Bits kommen in Bytes von jeweils 8 auf einem PIC 18, also würden Sie 40 Bits oder 5 Bytes verwenden, um diesen Wert darzustellen.

Alles, was Sie also schreiben müssen, ist eine Routine, die eine 1-Byte-Zahl mit einer 5-Byte-Zahl in die 5-Byte-Zahl multipliziert. Dies ist eigentlich ziemlich einfach, da der PIC 18 einen Hardware-8x8-in-16-Bit-Multiplikator hat. Grundsätzlich multiplizieren Sie das eine Eingabebyte mit jedem der breiten Zahlenbytes separat und addieren die Ergebnisse. Ich würde dies wahrscheinlich als ungerollte Schleife schreiben, also wären die Eingeweide 5 Sätze einer Multiplikation und zwei Additionen oder 15 Anweisungen.

Hinzugefügt

Wie Dan D in einem Kommentar zu Recht darauf hingewiesen hat, habe ich vergessen, den Modulo-Teil anzusprechen. Das ist deutlich komplizierter als Rechnen 5 ¹⁵ . Grundsätzlich teilst du durch 23 und behältst nur den Rest. Vielleicht kannst du dir ein paar Anweisungen sparen, weil du den Quotienten am Ende nicht brauchst, aber meistens musst du immer noch einen 5-Byte-geteilt durch 1-Byte-mit-1-Byte-Rest-Algorithmus schreiben.

Auch dies kann alles auf einem PIC 18 oder anderen kleinen Prozessoren durchgeführt werden, erfordert jedoch viel mehr Anweisungen als auf einem Prozessor, der 40-Bit-Zahlen nativ manipulieren kann.

Haftungsausschluss: Wenn Sie es zu Bildungszwecken tun möchten, machen Sie weiter. Wenn Sie es verwenden möchten, um die Kommunikation tatsächlich zu schützen, besorgen Sie sich eine Kopie des "Handbook of Applied Cryptography".

Wie bereits erwähnt, ist das Problem nicht die Potenzierung, sondern die Modulo-Operation (wenn sie naiv gemacht wird). Die Montgomery-Multiplikation ist ein effizienter Weg, dies zu lösen. Kurz gesagt, das Problem wird auf eine andere Gruppe abgebildet, die die Eigenschaft hat, dass die Modulo-Operation durch Bitverschiebung (und/oder Speicherkopie) ersetzt werden kann.

Ich weiß nichts über DH-Implementierungen auf 8-Bit-Chips, aber ich weiß mit Sicherheit, dass es RSA-Implementierungen für 8-Bit-Mikroprozessoren gibt.