lynxdec.cpp
1 /* 2 Wookie @ 3 http://atariage.com/forums/topic/129030-lynx-encryption/ 4 */ 5 6 #include <stdio.h> 7 #include <stdlib.h> 8 #include <string.h> 9 10 #define CHUNK_LENGTH (51) 11 12 const unsigned char lynx_public_mod[CHUNK_LENGTH] = { 13 0x35, 0xB5, 0xA3, 0x94, 0x28, 0x06, 0xD8, 0xA2, 14 0x26, 0x95, 0xD7, 0x71, 0xB2, 0x3C, 0xFD, 0x56, 15 0x1C, 0x4A, 0x19, 0xB6, 0xA3, 0xB0, 0x26, 0x00, 16 0x36, 0x5A, 0x30, 0x6E, 0x3C, 0x4D, 0x63, 0x38, 17 0x1B, 0xD4, 0x1C, 0x13, 0x64, 0x89, 0x36, 0x4C, 18 0xF2, 0xBA, 0x2A, 0x58, 0xF4, 0xFE, 0xE1, 0xFD, 19 0xAC, 0x7E, 0x79 20 }; 21 22 #define min(x,y) ((x < y) ? x : y) 23 24 /* result = 2 * result */ 25 void double_value(unsigned char *result, const int length) 26 { 27 int i, x; 28 29 x = 0; 30 for (i = length - 1; i >= 0; i--) { 31 x += 2 * result[i]; 32 result[i] = (unsigned char) (x & 0xFF); 33 x >>= 8; 34 } 35 /* shouldn't carry */ 36 } 37 38 /* result -= value */ 39 int minus_equals_value(unsigned char *result, 40 const unsigned char *value, 41 const int length) 42 { 43 int i, x; 44 unsigned char *tmp; 45 46 /* allocate temporary buffer */ 47 tmp = (unsigned char*)calloc(1, length); 48 49 x = 0; 50 for (i = length - 1; i >= 0; i--) { 51 x += result[i] - value[i]; 52 tmp[i] = (unsigned char) (x & 0xFF); 53 x >>= 8; 54 } 55 56 if (x >= 0) { 57 /* move the result back to BB */ 58 memcpy(result, tmp, length); 59 60 /* free the temporary buffer */ 61 free(tmp); 62 63 /* this had a carry */ 64 return 1; 65 } 66 67 /* free the temporary buffer */ 68 free(tmp); 69 70 /* this didn't carry */ 71 return 0; 72 } 73 74 /* result += value */ 75 void plus_equals_value(unsigned char *result, 76 const unsigned char *value, 77 const int length) 78 { 79 int i, tmp; 80 int carry = 0; 81 82 for(i = length - 1; i >= 0; i--) { 83 tmp = result[i] + value[i] + carry; 84 if (tmp >= 256) 85 carry = 1; 86 else 87 carry = 0; 88 result[i] = (unsigned char) (tmp); 89 } 90 } 91 92 /* L = M * N mod modulus */ 93 void lynx_mont(unsigned char *L, /* result */ 94 const unsigned char *M, /* original chunk of encrypted data */ 95 const unsigned char *N, /* copy of encrypted data */ 96 const unsigned char *modulus,/* modulus */ 97 const int length) 98 { 99 int i, j; 100 int carry; 101 unsigned char tmp; 102 unsigned char increment; 103 104 /* L = 0 */ 105 memset(L, 0, length); 106 107 for(i = 0; i < length; i++) { 108 /* get the next byte from N */ 109 tmp = N[i]; 110 111 for(j = 0; j < 8; j++) { 112 /* L = L * 2 */ 113 double_value(L, length); 114 115 /* carry is true if the MSB in tmp is set */ 116 increment = (tmp & 0x80) / 0x80; 117 118 /* shift tmp's bits to the left by one */ 119 tmp <<= 1; 120 121 if(increment != 0) { 122 /* increment the result... */ 123 /* L += M */ 124 plus_equals_value(L, M, length); 125 126 /* do a modulus correction */ 127 /* L -= modulus */ 128 carry = minus_equals_value(L, modulus, length); 129 130 /* if there was a carry, do it again */ 131 /* L -= modulus */ 132 if (carry != 0) 133 minus_equals_value(L, modulus, length); 134 } else { 135 /* instead decrement the result */ 136 137 /* L -= modulus */ 138 minus_equals_value(L, modulus, length); 139 } 140 } 141 } 142 } 143 144 145 /* this decrypts a single block of encrypted data by using the montgomery 146 * multiplication method to do modular exponentiation. 147 */ 148 int decrypt_block(int accumulator, 149 unsigned char * result, 150 const unsigned char * encrypted, 151 const unsigned char * public_exp, 152 const unsigned char * public_mod, 153 const int length) 154 { 155 int i; 156 unsigned char* rptr = result; 157 const unsigned char* eptr = encrypted; 158 unsigned char *A; 159 unsigned char *B; 160 unsigned char *TMP; 161 162 /* allocate the working buffers */ 163 A = (unsigned char*) calloc(1, length); 164 B = (unsigned char*)calloc(1, length); 165 TMP = (unsigned char*)calloc(1, length); 166 167 /* this copies the next length sized block of data from the encrypted 168 * data into our temporary memory buffer in reverse order */ 169 for(i = length - 1; i >= 0; i--) { 170 B[i] = *eptr; 171 eptr++; 172 } 173 174 /* so it took me a while to wrap my head around this because I couldn't 175 * figure out how the exponent was used in the process. RSA is 176 * a ^ b (mod c) and I couldn't figure out how that was being done until 177 * I realized that the public exponent for lynx decryption is just 3. That 178 * means that to decrypt each block, we only have to multiply each 179 * block by itself twice to raise it to the 3rd power: 180 * n^3 == n * n * n 181 */ 182 183 /* TODO: convert this to a loop that calls lynx_mont public_exp number of 184 * times so that we can raise the encrypted block of data to the power of 185 * public_exp and mod it by public_mod. this will make this flexible 186 * enough to be used to encrypt data as well. 187 */ 188 189 /* do Montgomery multiplication: A = B^2 */ 190 lynx_mont(A, B, B, public_mod, length); 191 192 /* copy the result into the temp buffer: TMP = B^2 */ 193 memcpy(TMP, A, length); 194 195 /* do Montgomery multiplication again: A = B^3 */ 196 lynx_mont(A, B, TMP, public_mod, length); 197 198 /* So I'm not sure if this is part of the Montgomery multiplication 199 * algorithm since I don't fully understand how that works. This may be 200 * just another obfuscation step done during the encryption process. 201 * The output of the decryption process has to be accumulated and masked 202 * to get the original bytes. If I had to place a bet, I would bet that 203 * this is not part of Montgomery multiplication and is just an obfuscation 204 * preprocessing step done on the plaintext data before it gets encrypted. 205 */ 206 for(i = length - 1; i > 0; i--) { 207 accumulator += A[i]; 208 accumulator &= 0xFF; 209 (*rptr) = (unsigned char)(accumulator); 210 rptr++; 211 } 212 213 /* free the temporary buffer memory */ 214 free(A); 215 free(B); 216 free(TMP); 217 218 return accumulator; 219 } 220 221 222 /* this function decrypts a single frame of encrypted data. a frame consists of 223 * a single byte block count followed by the count number of blocks of 224 * encrypted data. 225 */ 226 int decrypt_frame(unsigned char * result, 227 const unsigned char * encrypted, 228 const unsigned char * public_exp, 229 const unsigned char * public_mod, 230 const int length) 231 { 232 int i; 233 int blocks; 234 int accumulator; 235 unsigned char* rptr = result; 236 const unsigned char* eptr = encrypted; 237 238 /* reset the accumulator for the modulus step */ 239 accumulator = 0; 240 241 /* calculate how many encrypted blocks there are */ 242 blocks = 256 - *eptr; 243 244 /* move our index to the beginning of the next block */ 245 eptr++; 246 247 for(i = 0; i < blocks; i++) { 248 /* decrypt a single block of encrypted data */ 249 accumulator = decrypt_block(accumulator, rptr, eptr, public_exp, public_mod, length); 250 251 /* move result pointer ahead */ 252 rptr += (length - 1); 253 254 /* move read pointer ahead */ 255 eptr += length; 256 } 257 258 /* return the number of blocks decrypted */ 259 return blocks; 260 } 261 262 /* this is a completely refactored version of what happens in the Lynx at boot 263 * time. the original code was a very rough reverse of the Lynx ROM code, this 264 * is much easier to understand. 265 */ 266 void lynx_decrypt(unsigned char * result, const unsigned char * encrypted, const int length) 267 { 268 /* decrypt the first frame of encrypted data */ 269 decrypt_frame(&result[0], &encrypted[0], /* lynx_public_exp */ 0, lynx_public_mod, length); 270 }