RSA Implementierung in Objective-C

veröffentlicht am : Mo, 04. 11. 2013 geändert am: Di, 16. 05. 2017

Kategorie: Computer --> Programmierung --> Objective-C


Das war schwieriger als gedacht.

Ich hatte ja schon mal einige Erfolgsmeldungen bezüglich meines kleinen Hobbyprojektes hier verkündet, und doch steckt da der Teufel im Detail. Ich habe etliche Stunden in die Implementierung gesteckt – eigentlich ein dämliches Unterfangen, denn es gibt weit bessere. Aber so weit ich das gesehen habe, keine, die rein auf Objective-C basiert. Die Implementierung von iOS kapselt ja alles recht gut und doch funktioniert halt leider nicht alles bzw. ich bin zu blöd, da die richtigen Zertifikate etc anzulegen. Wäre auch ein wenig overkill für das, was ich machen will.

RSA und PKI – Unterschied?

Noch mal ne kurze Erklärung zu den Abkürzungen: RSA steht für Rivest, Shamir und Adleman. Das sind die Namen der Cryptographen, denen dieses Verschlüsselungsverfahren eingefallen ist. Naja… eingefallen klingt so zufällig, sie haben schon daran gearbeitet. Genaueres dazu gibt’s auch hier.

In gleichem Atemzug wird auch meistens PKI erwähnt, das steht für „Public Key Infrastrukture“ und bezeichnet Verfahren, Methoden und Vorgehensweisen, die es möglich machen mit Hilfe von RSA (oder ähnlichen Asymmetrischen Verschlüsselungsverfahren) die Sender zu identifizieren und sicher zu stellen, dass da keine „dazwischenfunkt“, wie man so schön sagt. Und in diesem Fall ist das fast wörtlich zu nehmen (Stichwort „Man in the Middle“).

Allerdings verursacht gerade diese PKI eine unheimliche verkomplizierung der Verschlüsselung: Zertifikate müssen erstellt werden, die von Zertifizierungsinstanzen zertifiziert werden müssen, welche selbst wiederum eine Zertifizierung von einer höheren instanz benötigen. Die Technik dahinter ist gar nicht so kompliziert, komplex wird’s eben durch dieses Drum herum.

Ich willl gleich mal festhalten, dass das alles wichtig und sinnvoll ist! Ohne PKI wäre das internet noch unsicherer, als es jetzt schon ist. Es gäbe kein SSL, kein HBCI und somit auch kein sicheres Online Banking. Also, ich finde das alles sehr sinnvoll…

Und dennoch gibt es fälle, in denen man einfach nur verschlüsseln will, ohne den ganzen Zinober drum rum. Bei Email würd ich mir das wünschen. Ich weiß ja jetzt auch nicht, wer am anderen Ende sitzt. Da versteh ich das ganze Getue nicht wirklich. Und DE-Mail ist ja eh nur – gelinde gesagt – Geldmacherei (um die man über kurz oder lang leider nicht rum kommen wird 🙁 ).

Anyway… ich wollte für mein kleines Hobbyprojekt einfach nur verschlüsselte Nachrichten von einem iPhone auf ein anderes senden. Da steckt der Teufel im Detail.

Die Implementierung

Ich hab ja hier schon ein paar Einblicke in die Implementierung des ganzen gemacht und seit dem ist dann doch ne menge Zeit vergangen. Den dort beschriebenen Ansatz habe ich beibehalten. Die Java-Sourcen von GNU-BigInteger haben mir dabei als Anhaltspunkt gedient.

Allerdings wollte ich, dass der Code sowohl auf OSX als auch auf gängigen iPhones funktioniert – die Java Version sollte eigentlich relativ problemlos auch auf Android gehen (hab ich aber (noch) nicht getestet). Das verursachte ungeahnte Probleme: die wirklich objektorientierte Implementierung mit NSMutableArray und NSNumber war leider viel zu langsam um nutzbar zu sein. Ich musste den code dann noch mal komplett umschreiben um dann mit Integern zu funktionieren. Auch da gab es Fallstricke: int auf iOS != int auf OSX. Die Bitlängen variieren da. Weshalb ich die interne Repräsentation der Daten komplett auf int64_t gebaut habe.

Wie in dem letzten Post schon beschrieben, blieb „nur noch“ die Umwandlung von Datenblöcken (NSData*) in BigInteger-Arrays übrig, die man dann verschlüsseln kann, bzw. umgekehrt entschlüsseln

Das erwies sich als erstaunlich kompliziert! Hier ein paar Anmerkungen:

  • Die Verschlüsselung funktioniert nur mit Zahlen, die kleiner sind als die Schlüsselbreite. Also, wenn ich RSA-1024 Bit habe, muss ich meine Daten auf <1024 Bit splitten.
  • Das Splitten klappt leider nicht immer aufs Byte genau auf die Grenzen von unseren BigIntegers. Deswegen muss man sich geeignete Mechanismen überlegen, um das ganze verlustfrei hin zu bekommen
  • Es müssen auch die Sonderfälle klappen, also 10 Byte 00, oder kein Byte…
  • Und das ganze muss reversibel bleiben, d.h premarin cream. ich muss aus den BigInteger-Objekten auch wieder meine Daten raus kriegen.

All das hat echt ne Menge Zeit gekostet. Ein wenig Code dafür könnt ihr hier sehen:

 

[codesyntax lang=“objc“ lines=“normal“]

- (NSArray *)getIntegersofBitLength:(int)bitLen {
////take the self, chunks of bitsize - 1
//    bitLen -= 32;
    int dataSize = (bitLen - 1) / 32; //bytes for this bitlength allowdd

    int numBis = self.length / dataSize / 4;
    if ((bitLen - 1) % 31 != 0) {
        numBis++;
    }
    int skip = 0;
    if (self.length % (dataSize * 4) != 0) {
        numBis++;
    }

    NSMutableArray *ret = [[NSMutableArray alloc] initWithCapacity:(NSUInteger) numBis];

    char *buffer = malloc(self.length);

    NSRange range = NSMakeRange(0, self.length);

    [self getBytes:buffer range:range];
    //creating numBis integers
    for (int loc = 0; loc < self.length; loc += (dataSize * 4)) {
        int numDatIdx = 0;

        range.location = (NSUInteger) loc;
        if (loc + dataSize * 4 > self.length) {
            range.length = self.length - loc;
            dataSize = range.length / 4;
            if (range.length % 4 != 0) {
                dataSize++;
            }
        } else {
            range.length = (NSUInteger) dataSize * 4;
        }

        int64_t *numDat = [BigInteger allocData:dataSize + 1];

        //prefixing all bis - to make 00000000 possible
        numDat[dataSize] = dataSize * 4; //prefix number of bytes
        numDatIdx = dataSize - 1;

//            NSLog(@"Got buffer %d, %d    %@", range.location, range.length, [[NSData dataWithBytes:(buffer + range.location) length:range.length] hexDump:NO]);

        for (int i = range.location; i < range.location + range.length; i += 4) {
            unsigned char c = (unsigned char) buffer[i];
//                NSLog(@"Processing idx %d-%d", i, i + 4);
            int v = c << 24;
            if (i + 1 >= range.location + range.length) {
                numDat[numDatIdx--] = v;
                skip = 24;
                break;
            }
            c = (unsigned char) buffer[i + 1];
            v |= c << 16;

            if (i + 2 >= range.location + range.length) {
                numDat[numDatIdx--] = v;
                skip = 16;
                break;
            }
            c = (unsigned char) buffer[i + 2];
            v |= c << 8;

            if (i + 3 >= range.location + range.length) {
//                    v=v>>8;
                numDat[numDatIdx--] = v;
                skip = 8;
                break;
            }
            c = (unsigned char) buffer[i + 3];
            v |= c;
            numDat[numDatIdx--] = v;
            skip = 0;
        }

        BigInteger *bi = [[BigInteger alloc] initWithData:numDat iVal:dataSize + 1];
        if (numDatIdx > -1) {
            //need to skip bytes
            numDatIdx += 1;
            int64_t *arr = (int64_t *) [BigInteger allocData:(int) (bi.iVal - numDatIdx)];
            memcpy(arr, bi.data + numDatIdx, bi.iVal - numDatIdx);
            bi.data = arr;
            bi.iVal = bi.iVal - numDatIdx;
        }
//            NSLog(@"Created BigInteger Ints : %@", bi);
//            NSLog(@"  bits: %d, DataSize %d", bi.bitLength,bi.iVal);
        [bi pack];
        [ret addObject:bi];
    }

//    }
    if (skip > 0) {
        BigInteger *bi = [ret lastObject];
        [ret removeLastObject];
        //remove prefix :/
        int64_t len = bi.data[bi.iVal - 1];
        len = len - skip / 8;
        bi.data[bi.iVal - 1] = 0;

        if (![bi isZero]) {
            bi = [bi shiftRight:skip];
//            bi=[bi or:[BigInteger valueOf:last]];
            [bi pack];
            int64_t *dat = [BigInteger allocData:(int) (bi.iVal + 1)];
            dat[bi.iVal] = len;

            for (int i = (int) (bi.iVal - 1); i >= 0; i--) {
                dat[i] = bi.data[i];
            }
            bi.data = dat;
            bi.iVal += 1;

            if (![bi isZero])
                [ret addObject:bi];
        }
    }
    return ret;
}

[/codesyntax]

 

 

da sind zwar noch ein paar Debug-Ausgaben drin, aber die helfen vielleicht beim Verständnis. Der Knackpunkt ist ziemlich am Anfang: Wie kann man die 0000000-Byte-Version abbilden. Ich meine, eine Zahl mit beliebig vielen führenden nullen ist 0. Deswegen habe ich in der Methode zum umwandeln von Bytes in BigIntegers die Länge in Bytes als Präfix mit eingefügt. Dadurch ist auch eine Menge von 00en nicht 0 – sondern z.B. 400000000 oder so… und diese Zahl kann man dann auch verschlüsseln.

Auf die gleiche Art und weise könnte man hier noch – der Sicherheit wegen – eine Prüfsumme einfügen. Wenn man denn will…

Leider geht das nicht als Ersatz für den Präfix „Länge in Byte“, da ich diesen Wert auch beim decodieren wieder benötige.

Im Normallfall klappt ja alles recht einfach, aber was, wenn die Daten eben nicht an den Grenzen zum BigInteger anfangen / aufhören? Dann muss man es am Ende noch mal „zurechtrücken“ damit das selbe raus kommt. Das erkennt man recht gut ab der Zeile „if (skip>0)“ – das ist genau der Fall, bei dem rotiert werden muss. Beispiel:

ich habe die Daten AFFE1 mein BigInteger hat eine ByteLänge von 64Bit, nach obigem Algorithmus käme dann raus: AFFE1000 was natürlich falsch wäre. Allerdings haben wir den Skip-Value, mit dem die Daten dann zurechtrotiert werden können (shiftRight).

Danach passt wieder alles.

[codesyntax lang=“objc“ lines=“normal“]

+ (NSData *)dataFromBigIntArray:(NSArray *)bigInts hasPrefix:(BOOL)prefix {
    char *buffer = malloc(sizeof(char) * 4); //4byte = 1int
    NSMutableData *ret = [[NSMutableData alloc] init];
    for (int i = 0; i < bigInts.count; i++) {
        BigInteger *integer = (BigInteger *) bigInts[i];

//        NSLog(@"processing %@",integer);
        buffer[0] = buffer[1] = buffer[2] = buffer[3] = 0;
        //stepping through integers
        int j = (int) (integer.iVal - (prefix ? 2 : 1));
        int skipBytes = 0;
        if (prefix) {
            //read prefix, add bytes if not enough in BigInteger
            int pr = (int) integer.data[integer.iVal - 1];
            if (pr < (integer.iVal - 1) * 4) {
                //too many 000
                skipBytes = (int) ((integer.iVal - 1) * 4 - pr);
            }
        }
        int skip = skipBytes;
        for (; j >= 0; j--) {
            int64_t v = integer.data[j];
            int idx = 0;
            char val;
            if (skip > 0) {
                skip--;
            } else {
                val= = (char) ((v >> 24) & 0xff);
                buffer[idx++] = val;
            }

            if (skip > 0) {
                skip--;
            } else {
                val = (char) ((v >> 16) & 0xff);
                buffer[idx++] = val;
            }

            if (skip > 0) {
                skip--;
            } else {
                val = (char) ((v >> 8) & 0xff);
                buffer[idx++] = val;
            }

            if (skip > 0) {
                skip--;
            } else {
                buffer[idx++] = val;
                val = (char) ((v) & 0xff);
            }

            if (skipBytes > 4) {
                skipBytes = skipBytes - 4;
            } else {
                [ret appendBytes:buffer length:(NSUInteger) (4 - skipBytes)];
                skipBytes = 0;
            }
        }

    }
    free(buffer);
    return ret;
}

[/codesyntax]

Das Decoden von so einer Liste von BigIntegers geht im Gegenzug wieder recht einfach, obwohl man auch hier wiederum diesen Offset berücksichtigen muss.

 

 

Die Auflösung eines BigInteger ist ja ein int64_t – also 64Bit = 8 Byte. Das Problem was es nun geben kann ist, dass wenn ein Wert < 2^64 abgebildet wird, kämen evtl. zu viele nullen ins Ergebnis. Also beispielsweise die Zahl FF.

Im BitInteger ist die Repräsentation ein int64_t mit dem Wert FF. Und ich muss jetzt wissen – ist das Ergebnis FF, 00FF oder 0000FF oder so; Bytegenauigkeit sollte hier eigentlich genügen, da die ausgangswerte ja auch Bytes sind. Und genau da kommt unser Präfix von oben ins Spiel. Er besagt, wie viele Bytes wirklich benötigt werden. Alle anderen werfe ich quasi weg, bzw. werden einfach übersprungen.

Damit kann man Blöcke von Bytes einfach in BigIntegers umwandeln und zurück. Und somit kann man diese BigInteger auch ver- bzw entschlüsseln.

Weiteres

die RSA Implementierung hab ich versucht als Library zu bauen, die sowohl ein Target für iOS als auch OSX hat. Ich habe auch einige Unit-Tests implementiert, die die Funktionen ziemlich weit abdecken. Das klappt auch so weit, allerdings habe ich es bisher nicht geschafft, ein iOS erfolgreich dagegen zu linken. Er findet immer einige Implementierungen nicht, was ich mir nicht wirklich erklären kann. Da ist also noch was zu tun.

Dann muss das ganze noch um Asynchronität erweitert werden, damit man in der Oberfläche eine Prozentanzeige darstellen kann, währen er ver- oder entschlüsselt.

Eine kleine Test-App mit der man das alles ausprobieren kann, läuft schon damit:

erstellt Stephan Bösebeck (stephan)