Please refer to the SAML Binding Specification which can be found here:
https://docs.oasis-open.org/security/saml/v2.0/saml-bindings-2.0-os.pdf

Lines 620-623 on page 18 states:

"Further, note that URL-encoding is not canonical; that is, there are multiple legal encodings
for a given value. The relying party MUST therefore perform the verification step using the
original URL-encoded values it received on the query string. It is not sufficient to re-encode
the parameters after they have been processed by software because the resulting encoding
may not match the signer's encoding."

Unfortunately in the method verifyRedirectSignature() (located in services/src/main/java/org/keycloak/protocol/saml/SamlProtocolUtils.java) this is what is occurring, it decodes and then re-encodes the query values prior to signature verification, this occurs in this code block:

        UriBuilder builder = UriBuilder.fromPath("/")
                .queryParam(paramKey, request);
        if (encodedParams.containsKey(GeneralConstants.RELAY_STATE)) {
            builder.queryParam(GeneralConstants.RELAY_STATE, encodedParams.getFirst(GeneralConstants.RELAY_STATE));
        }
        builder.queryParam(GeneralConstants.SAML_SIG_ALG_REQUEST_KEY, algorithm);
        String rawQuery = builder.build().getRawQuery();

The problem is UriBuilder encodes the values, this is in the javadoc for the UriBuilder class:

"Builder methods perform contextual encoding of characters not permitted in the
corresponding URI component following the rules of the application/x-www-form-urlencoded
media type for query parameters and RFC 3986 for all other components."

So even when getRawQuery() is called you're being returned a value which has been re-encoded.

This is easy to see in this little test code snippet:

String relayState = "https%3A%2F%2Fjdennis-test.example.com%2Fsaml-test%2Ftest(test).txt";		

System.out.println("raw:   RelayState=" + relayState);

UriBuilder builder = UriBuilder.fromPath("/");
builder.queryParam("RelayState", relayState);
String rawQuery = builder.build().getRawQuery();
System.out.println("built: " + rawQuery);

Which outputs:

raw:   RelayState=https%3A%2F%2Fjdennis-test.example.com%2Fsaml-test%2Ftest(test).txt
built: RelayState=https%3A%2F%2Fjdennis-test.example.com%2Fsaml-test%2Ftest%28test%29.txt

You can see the parens have been percent-encoded.

As a consequence the signature validation will fail even though the signature is correct. It fails because the signature was computed from a string that contained the parenthesis but was validated against a string that has the parenthesis replaced with percent-encoding.

FWIW, the parenthesis does not need to be percent encoded in a query component, it's legal to percent-encode them, but it's not required.

This is an example of the problem the binding specification warns about (cited above) when performing a signature validation.

The purpose of the UriBuilder code block is construct a string with the query parameters in the correct order as noted in lines 616-619 in the SAML Binding specification. This is better done with Java string operations instead of with a class that tries to interpret the meaning of the strings.

I have a proposed patch that replaces UriBuilder with string concatenation. I have not tested the patch, it might need a tweak or two.