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 perfeita, tanto em C#, quanto em Java (Android), se observarem alguma melhoria, ela será bem vinda. Obrigado a todos pelo auxilio.


  [1]: http://codereview.stackexchange.com/questions/32856/secure-password-hashing-in-net-code-review
  [2]: http://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]: http://stackoverflow.com/questions/2047706/apache-commons-codec-with-android-could-not-find-method