Ensure that the certificate you're using for signing the SAML request is correctly configured. The error suggests that the KeyInfo in the SAML request does not match any valid certificate on Azure AD's side. Double-check the certificate thumbprint or details in your Azure AD app configuration to make sure they match the certificate used for signing.
In your Azure AD app registration for the SP, make sure you have configured the correct certificate for SAML signing. Go to the Azure portal, navigate to your app registration, and check the "Certificates & secrets" section to ensure the certificate is uploaded and correctly associated with the app.
Ensure that the "Issuer" in your SAML request (saml:Issuer) matches the configured Issuer URI in your Azure AD app registration. They should be identical.