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: