diff --git a/build.gradle b/build.gradle
index 4c05a77..fe75e9a 100644
--- a/build.gradle
+++ b/build.gradle
@@ -22,6 +22,7 @@
     implementation 'com.google.protobuf:protobuf-javalite:3.8.0'
     testImplementation 'junit:junit:4.13'
     testImplementation 'org.bouncycastle:bcprov-jdk15on:1.68'
+    testImplementation 'org.conscrypt:conscrypt-openjdk-uber:2.5.1'
 }
 
 protobuf {
diff --git a/src/main/java/com/android/apksig/Constants.java b/src/main/java/com/android/apksig/Constants.java
index 680c5c3..32c7375 100644
--- a/src/main/java/com/android/apksig/Constants.java
+++ b/src/main/java/com/android/apksig/Constants.java
@@ -47,4 +47,6 @@
             SourceStampConstants.V1_SOURCE_STAMP_BLOCK_ID;
     public static final int V2_SOURCE_STAMP_BLOCK_ID =
             SourceStampConstants.V2_SOURCE_STAMP_BLOCK_ID;
+
+    public static final String OID_RSA_ENCRYPTION = "1.2.840.113549.1.1.1";
 }
diff --git a/src/main/java/com/android/apksig/internal/apk/ApkSigningBlockUtils.java b/src/main/java/com/android/apksig/internal/apk/ApkSigningBlockUtils.java
index 61b7b00..5b34849 100644
--- a/src/main/java/com/android/apksig/internal/apk/ApkSigningBlockUtils.java
+++ b/src/main/java/com/android/apksig/internal/apk/ApkSigningBlockUtils.java
@@ -16,6 +16,7 @@
 
 package com.android.apksig.internal.apk;
 
+import static com.android.apksig.Constants.OID_RSA_ENCRYPTION;
 import static com.android.apksig.internal.apk.ContentDigestAlgorithm.CHUNKED_SHA256;
 import static com.android.apksig.internal.apk.ContentDigestAlgorithm.CHUNKED_SHA512;
 import static com.android.apksig.internal.apk.ContentDigestAlgorithm.VERITY_CHUNKED_SHA256;
@@ -666,7 +667,8 @@
         if ("X.509".equals(publicKey.getFormat())) {
             encodedPublicKey = publicKey.getEncoded();
             // if the key is an RSA key check for a negative modulus
-            if ("RSA".equals(publicKey.getAlgorithm())) {
+            String keyAlgorithm = publicKey.getAlgorithm();
+            if ("RSA".equals(keyAlgorithm) || OID_RSA_ENCRYPTION.equals(keyAlgorithm)) {
                 try {
                     // Parse the encoded public key into the separate elements of the
                     // SubjectPublicKeyInfo to obtain the SubjectPublicKey.
diff --git a/src/main/java/com/android/apksig/internal/apk/v1/V1SchemeSigner.java b/src/main/java/com/android/apksig/internal/apk/v1/V1SchemeSigner.java
index 85301ca..ee3c9d8 100644
--- a/src/main/java/com/android/apksig/internal/apk/v1/V1SchemeSigner.java
+++ b/src/main/java/com/android/apksig/internal/apk/v1/V1SchemeSigner.java
@@ -16,6 +16,7 @@
 
 package com.android.apksig.internal.apk.v1;
 
+import static com.android.apksig.Constants.OID_RSA_ENCRYPTION;
 import static com.android.apksig.internal.pkcs7.AlgorithmIdentifier.getSignerInfoDigestAlgorithmOid;
 import static com.android.apksig.internal.pkcs7.AlgorithmIdentifier.getSignerInfoSignatureAlgorithm;
 
@@ -111,7 +112,7 @@
     public static DigestAlgorithm getSuggestedSignatureDigestAlgorithm(
             PublicKey signingKey, int minSdkVersion) throws InvalidKeyException {
         String keyAlgorithm = signingKey.getAlgorithm();
-        if ("RSA".equalsIgnoreCase(keyAlgorithm)) {
+        if ("RSA".equalsIgnoreCase(keyAlgorithm) || OID_RSA_ENCRYPTION.equals((keyAlgorithm))) {
             // Prior to API Level 18, only SHA-1 can be used with RSA.
             if (minSdkVersion < 18) {
                 return DigestAlgorithm.SHA1;
diff --git a/src/main/java/com/android/apksig/internal/apk/v1/V1SchemeVerifier.java b/src/main/java/com/android/apksig/internal/apk/v1/V1SchemeVerifier.java
index 6d7e997..0ebef0e 100644
--- a/src/main/java/com/android/apksig/internal/apk/v1/V1SchemeVerifier.java
+++ b/src/main/java/com/android/apksig/internal/apk/v1/V1SchemeVerifier.java
@@ -26,6 +26,7 @@
 import com.android.apksig.ApkVerifier.IssueWithParams;
 import com.android.apksig.apk.ApkFormatException;
 import com.android.apksig.apk.ApkUtils;
+import com.android.apksig.internal.apk.ApkSigningBlockUtils;
 import com.android.apksig.internal.asn1.Asn1BerParser;
 import com.android.apksig.internal.asn1.Asn1Class;
 import com.android.apksig.internal.asn1.Asn1DecodingException;
@@ -54,13 +55,17 @@
 import java.io.IOException;
 import java.nio.ByteBuffer;
 import java.security.InvalidKeyException;
+import java.security.KeyFactory;
 import java.security.MessageDigest;
 import java.security.NoSuchAlgorithmException;
 import java.security.Principal;
+import java.security.PublicKey;
 import java.security.Signature;
 import java.security.SignatureException;
 import java.security.cert.CertificateException;
 import java.security.cert.X509Certificate;
+import java.security.spec.InvalidKeySpecException;
+import java.security.spec.X509EncodedKeySpec;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Base64;
@@ -677,7 +682,27 @@
             String jcaSignatureAlgorithm =
                     getJcaSignatureAlgorithm(digestAlgorithmOid, signatureAlgorithmOid);
             Signature s = Signature.getInstance(jcaSignatureAlgorithm);
-            s.initVerify(signingCertificate.getPublicKey());
+            PublicKey publicKey = signingCertificate.getPublicKey();
+            try {
+                s.initVerify(publicKey);
+            } catch (InvalidKeyException e) {
+                // An InvalidKeyException could be caught if the PublicKey in the certificate is not
+                // properly encoded; attempt to resolve any encoding errors, generate a new public
+                // key, and reattempt the initVerify with the newly encoded key.
+                try {
+                    byte[] encodedPublicKey = ApkSigningBlockUtils.encodePublicKey(publicKey);
+                    publicKey = KeyFactory.getInstance(publicKey.getAlgorithm()).generatePublic(
+                            new X509EncodedKeySpec(encodedPublicKey));
+                } catch (InvalidKeySpecException ikse) {
+                    // If an InvalidKeySpecException is caught then throw the original Exception
+                    // since the key couldn't be properly re-encoded, and the original Exception
+                    // will have more useful debugging info.
+                    throw e;
+                }
+                s = Signature.getInstance(jcaSignatureAlgorithm);
+                s.initVerify(publicKey);
+            }
+
             if (signerInfo.signedAttrs != null) {
                 // Signed attributes present -- verify signature against the ASN.1 DER encoded form
                 // of signed attributes. This verifies integrity of the signature file because
diff --git a/src/main/java/com/android/apksig/internal/pkcs7/AlgorithmIdentifier.java b/src/main/java/com/android/apksig/internal/pkcs7/AlgorithmIdentifier.java
index 4185dbc..9712767 100644
--- a/src/main/java/com/android/apksig/internal/pkcs7/AlgorithmIdentifier.java
+++ b/src/main/java/com/android/apksig/internal/pkcs7/AlgorithmIdentifier.java
@@ -16,6 +16,7 @@
 
 package com.android.apksig.internal.pkcs7;
 
+import static com.android.apksig.Constants.OID_RSA_ENCRYPTION;
 import static com.android.apksig.internal.asn1.Asn1DerEncoder.ASN1_DER_NULL;
 import static com.android.apksig.internal.oid.OidConstants.OID_DIGEST_SHA1;
 import static com.android.apksig.internal.oid.OidConstants.OID_DIGEST_SHA256;
@@ -92,7 +93,7 @@
                 throw new IllegalArgumentException(
                         "Unexpected digest algorithm: " + digestAlgorithm);
         }
-        if ("RSA".equalsIgnoreCase(keyAlgorithm)) {
+        if ("RSA".equalsIgnoreCase(keyAlgorithm) || OID_RSA_ENCRYPTION.equals(keyAlgorithm)) {
             return Pair.of(
                     jcaDigestPrefixForSigAlg + "withRSA",
                     new AlgorithmIdentifier(OID_SIG_RSA, ASN1_DER_NULL));
diff --git a/src/test/java/com/android/apksig/ApkVerifierTest.java b/src/test/java/com/android/apksig/ApkVerifierTest.java
index 9e1a75e..5a7c64d 100644
--- a/src/test/java/com/android/apksig/ApkVerifierTest.java
+++ b/src/test/java/com/android/apksig/ApkVerifierTest.java
@@ -30,6 +30,7 @@
 import com.android.apksig.internal.util.Resources;
 import com.android.apksig.util.DataSources;
 
+import java.security.Provider;
 import org.junit.Assume;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -1330,6 +1331,23 @@
         }
     }
 
+    @Test
+    public void verifySignature_negativeModulusConscryptProvider() throws Exception {
+        Provider conscryptProvider = null;
+        try {
+            conscryptProvider = new org.conscrypt.OpenSSLProvider();
+            Security.insertProviderAt(conscryptProvider, 1);
+            assertVerified(verify("v1v2v3-rsa-2048-negmod-in-cert.apk"));
+        } catch (UnsatisfiedLinkError e) {
+            // If the library for conscrypt is not available then skip this test.
+            return;
+        } finally {
+            if (conscryptProvider != null) {
+                Security.removeProvider(conscryptProvider.getName());
+            }
+        }
+    }
+
     private ApkVerifier.Result verify(String apkFilenameInResources)
             throws IOException, ApkFormatException, NoSuchAlgorithmException {
         return verify(apkFilenameInResources, null, null);
diff --git a/src/test/resources/com/android/apksig/v1v2v3-rsa-2048-negmod-in-cert.apk b/src/test/resources/com/android/apksig/v1v2v3-rsa-2048-negmod-in-cert.apk
new file mode 100644
index 0000000..6f73b92
--- /dev/null
+++ b/src/test/resources/com/android/apksig/v1v2v3-rsa-2048-negmod-in-cert.apk
Binary files differ