--- a/mobile/android/debug_sign_tool.py
+++ b/mobile/android/debug_sign_tool.py
@@ -91,33 +91,33 @@ class DebugKeystore:
 
         args = [ self.keytool,
                  '-genkeypair',
                  '-keystore', self.keystore,
                  '-storepass', 'android',
                  '-alias', self.alias,
                  '-keypass', 'android',
                  '-dname', 'CN=Android Debug,O=Android,C=US',
-                 '-keyalg', 'RSA',
+                 '-keyalg', 'DSA',
                  '-validity', '365',
                ]
         if self.verbose:
             args.append('-v')
         self._check(args)
         if self.verbose:
             log.info('Created alias %s in keystore %s' %
                      (self.alias, self.keystore))
 
     def sign(self, apk):
         if not self.keystore_contains_alias():
             self.create_alias_in_keystore()
 
         args = [ self.jarsigner,
                  '-digestalg', 'SHA1',
-                 '-sigalg', 'MD5withRSA',
+                 '-sigalg', 'SHA1withDSA',
                  '-keystore', self.keystore,
                  '-storepass', 'android',
                  apk,
                  self.alias,
                ]
         if self.verbose:
             args.append('-verbose')
         self._check(args)

--- a/testing/mozharness/mozharness/base/signing.py
+++ b/testing/mozharness/mozharness/base/signing.py
@@ -112,16 +112,18 @@ class AndroidSigningMixin(object):
         # This needs to run silently, so no run_command() or
         # get_output_from_command() (though I could add a
         # suppress_command_echo=True or something?)
         self.log("(signing %s)" % apk, level=log_level)
         try:
             p = subprocess.Popen([jarsigner, "-keystore", keystore,
                                  "-storepass", storepass,
                                  "-keypass", keypass,
+                                 "-digestalg", "SHA1",
+                                 "-sigalg", "SHA1withDSA",
                                  apk, key_alias],
                                  stdout=subprocess.PIPE,
                                  stderr=subprocess.STDOUT)
         except OSError:
             self.exception("Error while signing %s (missing %s?):" % (apk, jarsigner))
             return -2
         except ValueError:
             self.exception("Popen called with invalid arguments during signing?")