diff -urw a/libopendkim/dkim.c b/libopendkim/dkim.c
--- a/libopendkim/dkim.c	2016-07-07 14:20:38.038000000 -0400
+++ b/libopendkim/dkim.c	2016-07-07 15:02:10.513000000 -0400
@@ -5301,6 +5301,7 @@
 	size_t diglen = 0;
 #ifdef USE_GNUTLS
 	gnutls_datum_t key;
+	gnutls_sign_algorithm_t sign_algo;
 #else /* USE_GNUTLS */
 	BIO *key;
 #endif /* USE_GNUTLS */
@@ -5413,6 +5414,8 @@
 		rsa->rsa_digest.data = digest;
 		rsa->rsa_digest.size = diglen;
 
+		sign_algo = gnutls_pk_to_sign(GNUTLS_PK_RSA, (dkim->dkim_signalg != DKIM_SIGN_RSASHA1 ? GNUTLS_DIG_SHA256 : GNUTLS_DIG_SHA1));
+
 		status = gnutls_pubkey_init(&rsa->rsa_pubkey);
 		if (status != GNUTLS_E_SUCCESS)
 		{
@@ -5442,7 +5445,8 @@
 			return DKIM_STAT_OK;
 		}
 
-		rsastat = gnutls_pubkey_verify_hash(rsa->rsa_pubkey, 0,
+		rsastat = gnutls_pubkey_verify_hash2(rsa->rsa_pubkey,
+		                                    sign_algo, 0,
 		                                    &rsa->rsa_digest,
 		                                    &rsa->rsa_sig);
 		if (rsastat < 0)