I am actually having the same issue.   I do not have the Sign AuthRequest box checked.   The encryption key alias and password are both correct.   Any ideas?   There have been no changes made to the SSO config of ServiceNow since we went live almost 5 months ago.