As mentioned earlier in the thread, we now know how the checksum is obsfuscated, thanks to Jalada and nicholas on IRC. (That is, by xoring it with 0x4a3b2c1d.)
By looking for the magic number 0x4a3b2c1d, i was able to find where in the ROM the encryption takes place, and to pinpoint the encryption algorithm. I'm sure you will not be surprised to learn that it uses yet another LCG, which i'm naming the GRNG, for "GTS Random Number Generator". (Terrible, i know. Also it sounds a bit like "grunge".)
Ladies and Gentlemen, the GRNG:
GRNG[n+1] = (GRNG[n] * 0x45 + 0x1111) & 0x7fffffff
The data is encrypted by xoring each byte with the low byte of the high word of the corresponding GRNG value, like so:
ciphertext[n] = plaintext[n] ^ ((GRNG[n] >> 16) & 0xff)
The checksum is used to seed the GRNG:
GRNG = checksum | (checksum << 16)
(Oh, and for anyone interested, the routine for seeding the GRNG is at 0x02211E60 in Diamond, and the routine for advancing it is at 0x02211E70. These routines are found in overlay 79.)
So there you have it. I guess the floodgates are open. And now that i've figured out both the challenge-response hash and the data encryption, i'm kind of done with this GTS stuff. Honestly though, i'm a little worried about the SSL connection that takes place. Since we don't know much about it, and aren't even close to being able to spoof it, that means that when Nintendo eventually shuts down the official GTS server, all the fan servers will go with it. Enjoy it while it lasts.
And, as a parting note, i'm interested in seeing where the Wonder Card spoofing research goes.