Two problems:
1) you're not terminating your output string - change:
*output_key = malloc(strlen(input_string) * sizeof(char));
to:
*output_key = malloc(strlen(input_string) + 1);
and make sure you add a '\0'
terminator, e.g. in parseAlphaKey
add a line:
(*output_key)[n] = '\0';
after the loop.
2) you're getting bitten by operator precedence - change, e.g.
*output_key[i] = input_string[i] - 'A';
to:
(*output_key)[i] = input_string[i] - 'A';