Single character signing scheme (minimal security)

Question

Note: I originally posted this to Information Security, but I'm starting to think it might be more relevant here as it's really about determining what I should do with a request rather than securing information.

Situation

System A:

I have a system A that serves requests to users. This server does something, and then redirects the user to system B. During that redirect, server A can give the user a 32-character alphanumeric string of information to pass along to system B. 31 characters of that information are needed, but one can be used as a checksum. This string can more or less be thought of as a request ID.

System B:

When system B receives a request from the user, it can verify that the request (and the ID-like string) are valid by parsing the 31-character string, querying a database, and talking to system A. This system can verify with absolute certainty that the request is valid and has not been tampered with, but it's very computationally expensive.

Attackers:

It is likely that this system will see many attempts to spoof the ID. This is filtered by later checks so I'm not worried about a single character perfectly signing the ID, but I do want to avoid spending any more resources on handling these requests than is needed.

What I Need

I am looking for a checksum/signing scheme that can, with a single character, give me a good idea of whether the request should continue to the verification process or if it should be immediately discarded as invalid. If a message is discarded, I need to be 100% sure that it isn't valid, but it's okay if I keep messages that are invalid. I believe an ideal solution would mean 1/62 invalid requests are kept (attacker has to guess the check character), but as a minimal solution discarding half of all invalid requests would be sufficient.

What I've Tried

I have looked at using the Luhn algorithm (same one that's used for credit cards), but I would like to be able to use a key to generate the character to make it more difficult for an attacker to spoof the checksum.

As a first attempt at creating a signing scheme, I am bitwise xor-ing the 31-byte id with a 31-byte key, summing the resulting bytes, converting to decimal and adding the digits together until it's less than 62, then mapping it to a character in the set [a-bA-Z0-9] (pseudocode below). The problem is that although I'm pretty sure this won't discard any valid requests, I'm not sure how to determine how often this will let through invalid IDs or if the key can be retrieved using the final value.

Set alphabet to (byte[]) "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
Set keystring to "aLaklj14sdLK87kxcvalskj7asfrq01";

Create empty byte[] key;
FOR each letter in keystring
  Push (index of letter in alphabet) to key;

Create empty byte[] step1;

FOR each (r, k) in (request, key)
  Push r XOR s to step1;

Set step2 to 0;
FOR each b in step1
  Add (int) b to step2;

WHILE step2 > 62
  Copy step2 to step3;
  Set step2 to 0;
  Convert step3 to String;
  Split step3 between characters;
  FOR each digit in step3
    Add (int) digit to step2;
END WHILE

RETURN alphabet[step2]

Stated Formally

A deterministic hash function where, given a private key and an input 31 bytes long, yields an output in the set {x | x ∈ ℕ, x < 62}, where guessing the output would be more efficient than calculating the private key. (Bonus points for variable-length input)

This will eventually be implemented in NodeJS/JavaScript but isn't really language-dependent.

---

Disclaimer: I apologize if this question is too vague and theoretical. Please comment for clarification if it's needed. There are, obviously, ways I could work around this problem, but in this case, I am looking for as direct a solution as possible.

Answer 1

If you want a "deterministic hash function" with a private key, then I believe you can just use sha256 (or any other hash function in your crypto library) with the key appended to the input:

sha256(input+key).toString('hex');

Afterwards, take the last few bits of the hash value, convert it from hex string to integer, divide the integer by 62, get the remainder, and determine the character based on the remainder.

This won't give you perfect 1/62 distribution probability (the hex string should have a uniform distribution for each value but not the remainders after dividing by 62) for each character but should be very close.