Bem após analisar as opções apontadas por vocês, implementei a minha solução utilizando **Pbkdf2** que foi a seguinte:

Em C#, segui [este][1] exemplo ficando assim minha implementação:

<!-- language: c# -->

    // este retorna em bytes (byte[])
    public static byte[] PBKDF2(string password, byte[] salt, int iterations, int outputBytes)
    {
        Rfc2898DeriveBytes pbkdf2 = new Rfc2898DeriveBytes(password, salt);
        pbkdf2.IterationCount = iterations;
        return pbkdf2.GetBytes(outputBytes);
    }

    // Esse retorna em Base64 (que é o que uso no fim)
    public static string PBKDF2ToBase64(string password, byte[] salt, int iterations, int outputBytes)
    {
        return Convert.ToBase64String(PBKDF2(password, salt, iterations, outputBytes));
    }

Em Java, segui [este][2] e [este][3] exemplo ficando assim minha implementação:

<!-- language: lang-java -->

	private static final int KEYLENGTH_MULTIPLIER = 8;
    // este retorna em bytes (byte[])
	public static byte[] PBKDF2(String password, byte[] salt, int iterations,
			int outputBytes) throws NoSuchAlgorithmException,
			InvalidKeySpecException {
		KeySpec spec = new PBEKeySpec(password.toCharArray(), salt, iterations,
				outputBytes * KEYLENGTH_MULTIPLIER);
		SecretKeyFactory f = SecretKeyFactory.getInstance("PBKDF2WithHmacSHA1");
		return f.generateSecret(spec).getEncoded();
	}

    // Esse retorna em Base64 (que é o que uso no fim)
	public static String PBKDF2ToBase64(String password, byte[] salt, int iterations,
			int outputBytes){
		try {
			return new String(Base64.encodeBase64(PBKDF2(password, salt, iterations, outputBytes)), "UTF-8");
		} catch (NoSuchAlgorithmException e) {
			e.printStackTrace();
		} catch (InvalidKeySpecException e) {
			e.printStackTrace();
		} catch (UnsupportedEncodingException e) {
			e.printStackTrace();
		}
		return null;
	}

A biblioteca que estou utilizando para converter para Base64 em Java é [essa][4], e no Android o método `encodeBase64String`, não funciona e fiz uma adaptação com o método `encodeBase64` conforme [essa][5] sugestão.

>Aparentemente tudo está funcionando perfeito, tanto em C#, quanto em Java (Android), se observarem alguma melhoria, ela será bem vinda. Obrigado a todos pelo auxilio.

----------

**Explicação de parâmetros:**

>Os parâmetros `salt`, `iterations`, `outputBytes` são parâmetros de configuração do método de Hash, e podem ser utilizados como chaves secretas de sua aplicação.

Onde: 

 1. [`salt`: Ou sal em Português](https://pt.wikipedia.org/wiki/Sal_(criptografia))
 2. `iterations`: Quantidade de iterações para calcular o hash, quanto maior esse valor maior o tempo de processamento do hash;
 3. `outputBytes`: Quantidade de bytes de saída do hash;

--------------------

**Exemplo de utilização:**

**C#:**

<!-- language: c# -->

    private int LengthOutputBytes = 32;
    private byte[] Salt = new byte[] { 0x20, 0x23, 0x65, 0x46, 0x43, 0x24, 0x55, 0x23, 0x31, 0x33, 0x32, 0x34, 0x72, 0x18, 0x67, 0x68 };
    private int HashIterations = 10;
    private string password = "123";

    string hash = PBKDF2ToBase64(password, Salt, HashIterations, LengthOutputBytes);

**Java:**

<!-- language: java -->

    private byte[] SALT = { 0x20, 0x23, 0x65, 0x46, 0x43, 0x24,
			0x55, 0x23, 0x31, 0x33, 0x32, 0x34, 0x72, 0x18, 0x67, 0x68 };
	private int ITERATIONS = 10;
	private int OUTPUTBYTES = 32;
    private String password = "123";

    String hash = PBKDF2ToBase64(password, SALT, ITERATIONS, OUTPUTBYTES);

  [1]: https://codereview.stackexchange.com/questions/32856/secure-password-hashing-in-net-code-review
  [2]: https://stackoverflow.com/questions/2860943/suggestions-for-library-to-hash-passwords-in-java
  [3]: https://gist.github.com/jtan189/3804290
  [4]: http://commons.apache.org/proper/commons-codec/apidocs/org/apache/commons/codec/binary/Base64.html
  [5]: https://stackoverflow.com/questions/2047706/apache-commons-codec-with-android-could-not-find-method