O operador de módulo (%) fornece um resultado diferente para diferentes versões do .NET em C #

89

Estou criptografando a entrada do usuário para gerar uma string para senha. Mas uma linha de código fornece resultados diferentes em diferentes versões da estrutura. Código parcial com valor da tecla pressionada pelo usuário:

Tecla pressionada: 1. A variável asciié 49. Valor de 'e' e 'n' após alguns cálculos:

e = 103, 
n = 143,

Math.Pow(ascii, e) % n

Resultado do código acima:

  • Em .NET 3.5 (C #)

    Math.Pow(ascii, e) % n

    9.0.

  • Em .NET 4 (C #)

    Math.Pow(ascii, e) % n

    77.0.

Math.Pow() fornece o (mesmo) resultado correto em ambas as versões.

Qual é a causa e existe uma solução?

Rajiv
fonte
12
Claro, ambas as respostas da pergunta estão erradas. O fato de você não parecer se importar com isso é, bem, preocupante.
David Heffernan
34
Você precisa voltar várias etapas. "Estou criptografando a entrada do usuário para gerar uma string para senha" esta parte já é duvidosa. O que você realmente quer fazer? Você deseja armazenar uma senha em formato criptografado ou hash? Você quer usar isso como entropia para gerar um valor aleatório? Quais são seus objetivos de segurança?
CodesInChaos
49
Embora esta pergunta ilustre um problema interessante com aritmética de ponto flutuante, se o objetivo do OP for "criptografar a entrada do usuário para gerar uma string para senha", não acho que lançar sua própria criptografia seja uma boa ideia, então não recomendaria realmente implementando qualquer uma das respostas.
Harrison Paine
18
Bela demonstração de por que outras linguagens proíbem o uso de %com números de ponto flutuante.
Ben Voigt
5
Embora as respostas sejam boas, nenhum deles responde à pergunta sobre o que mudou entre o .NET 3.5 e 4 que está causando o comportamento diferente.
msell

Respostas:

160

Math.Powfunciona em números de ponto flutuante de precisão dupla; portanto, você não deve esperar que mais do que os primeiros 15 a 17 dígitos do resultado sejam precisos:

Todos os números de ponto flutuante também têm um número limitado de dígitos significativos, o que também determina a precisão com que um valor de ponto flutuante se aproxima de um número real. Um Doublevalor tem até 15 dígitos decimais de precisão, embora um máximo de 17 dígitos seja mantido internamente.

No entanto, o módulo aritmético requer que todos os dígitos sejam precisos. No seu caso, você está computando 49 103 , cujo resultado consiste em 175 dígitos, tornando a operação do módulo sem sentido em ambas as suas respostas.

Para calcular o valor correto, você deve usar aritmética de precisão arbitrária, conforme fornecida pela BigIntegerclasse (introduzida no .NET 4.0).

int val = (int)(BigInteger.Pow(49, 103) % 143);   // gives 114

Edit : Conforme apontado por Mark Peters nos comentários abaixo, você deve usar o BigInteger.ModPowmétodo, que se destina especificamente a este tipo de operação:

int val = (int)BigInteger.ModPow(49, 103, 143);   // gives 114
Douglas
fonte
20
+1 para apontar o problema real, ou seja, que o código em questão está totalmente errado
David Heffernan
36
É importante notar que BigInteger fornece um método ModPow () que executa (em meu teste rápido agora) cerca de 5 vezes mais rápido para esta operação.
Mark Peters
8
1 com a edição. O ModPow não é apenas rápido, é numericamente estável!
Ray
2
@maker Não, a resposta não tem sentido , não é inválida .
Cody Gray
3
@ makerofthings7: Concordo com você em princípio. No entanto, a imprecisão é inerente à aritmética de ponto flutuante, e é considerado mais prático esperar que os desenvolvedores estejam cientes dos riscos do que impor restrições às operações em geral. Se alguém quisesse estar realmente "seguro", a linguagem também precisaria proibir comparações de igualdade de ponto flutuante, para evitar resultados inesperados, como 1.0 - 0.9 - 0.1 == 0.0avaliar para false.
Douglas
72

Além do fato de que sua função de hashing não é muito boa * , o maior problema com seu código não é que ele retorna um número diferente dependendo da versão do .NET, mas que em ambos os casos ele retorna um número totalmente sem sentido: a resposta correta para o problema é

49 103 mod 143 = é 114. ( link para Wolfram Alpha )

Você pode usar este código para calcular esta resposta:

private static int PowMod(int a, int b, int mod) {
    if (b == 0) {
        return 1;
    }
    var tmp = PowMod(a, b/2, mod);
    tmp *= tmp;
    if (b%2 != 0) {
        tmp *= a;
    }
    return tmp%mod;
}

A razão pela qual seu cálculo produz um resultado diferente é que, para produzir uma resposta, você usa um valor intermediário que elimina a maioria dos dígitos significativos do número 49 103 : apenas os primeiros 16 de seus 175 dígitos estão corretos!

1230824813134842807283798520430636310264067713738977819859474030746648511411697029659004340261471771152928833391663821316264359104254030819694748088798262075483562075061997649

Os 159 dígitos restantes estão todos errados. A operação mod, no entanto, busca um resultado que exija que cada dígito esteja correto, incluindo os últimos. Portanto, mesmo a menor melhoria na precisão do Math.Powque pode ter sido implementado no .NET 4, resultaria em uma diferença drástica do seu cálculo, o que essencialmente produz um resultado arbitrário.

* Uma vez que esta questão fala sobre elevar inteiros a altas potências no contexto de hashing de senha, pode ser uma boa ideia ler este link de resposta antes de decidir se sua abordagem atual deve ser alterada por uma potencialmente melhor.

dasblinkenlight
fonte
20
Boa resposta. O ponto real é que esta é uma função hash terrível. OP precisa repensar a solução e usar um algoritmo mais apropriado.
david.pfx
1
Isaac Newton: É possível que a lua seja atraída para a terra da mesma forma que a maçã é atraída para a terra? @david.pfx: A questão real é que esta é uma maneira terrível de colher maçãs. Newton precisa repensar a solução e talvez contratar um homem com uma escada.
jwg
2
O comentário de @jwg David teve tantos votos positivos por um motivo. A pergunta original deixava claro que o algoritmo estava sendo usado para hash de senhas, e é de fato um algoritmo terrível para esse propósito - é extremamente provável que haja falha entre as versões do framework .NET, como já foi demonstrado. Qualquer resposta que não mencione que o OP precisa substituir seu algoritmo em vez de "consertá-lo" está prestando um péssimo serviço a ele.
Chris
@Chris Obrigado pelo comentário, editei para incluir a sugestão de David. Eu não falei tão fortemente quanto você, porque o sistema de OP pode ser um brinquedo ou um pedaço de código descartável que ele constrói para sua própria diversão. Obrigado!
dasblinkenlight
27

O que você vê é um erro de arredondamento em dobro. Math.Powtrabalha com double e a diferença é a seguinte:

.NET 2.0 e 3.5 => var powerResult = Math.Pow(ascii, e);retorna:

1.2308248131348429E+174

.NET 4.0 e 4.5 => var powerResult = Math.Pow(ascii, e);retorna:

1.2308248131348427E+174

Observe o último dígito anterior Ee isso está causando a diferença no resultado. Não é o operador de módulo (%) .

Habib
fonte
3
Caramba, esta é a ÚNICA resposta para a pergunta dos OPs? Eu li toda a meta "blá, blá, pergunta errada sobre segurança, eu sei mais do que você n00b" e ainda me pergunto "por que a discrepância consistente entre 3,5 e 4,0? Você já bateu com o dedo do pé em uma rocha enquanto olhava para a lua e perguntou" que tipo de rocha é isso? "Apenas para ouvir" Seu verdadeiro problema é não olhar para os pés "ou" O que você espera ao usar sandálias caseiras à noite? !!! "OBRIGADO!
Michael Paulukonis
1
@MichaelPaulukonis: Essa é uma falsa analogia. O estudo das rochas é uma busca legítima; executar aritmética de precisão arbitrária usando tipos de dados de precisão fixa é simplesmente errado. Eu compararia isso a um recrutador de software perguntando por que cães são piores do que gatos para escrever C #. Se você é um zoólogo, a pergunta pode ter algum mérito; para todos os outros, é inútil.
Douglas
24

A precisão do ponto flutuante pode variar de máquina para máquina e até mesmo na mesma máquina .

Porém, o .NET faz uma máquina virtual para seus aplicativos ... mas há mudanças de versão para versão.

Portanto, você não deve confiar nele para produzir resultados consistentes. Para criptografia, use as classes que o Framework fornece, em vez de criar suas próprias classes.

Joe
fonte
10

Há muitas respostas sobre como o código é ruim. No entanto, por que o resultado é diferente ...

As FPUs da Intel usam o formato de 80 bits internamente para obter mais precisão para resultados intermediários. Portanto, se um valor está no registro do processador, ele obtém 80 bits, mas quando é escrito na pilha, ele é armazenado em 64 bits .

Espero que a versão mais recente do .NET tenha um otimizador melhor em sua compilação Just in Time (JIT), portanto, ela mantém um valor em um registro em vez de gravá-lo na pilha e depois lê-lo de volta da pilha.

Pode ser que o JIT agora possa retornar um valor em um registro em vez de na pilha. Ou passe o valor para a função MOD em um registro.

Consulte também a pergunta sobre Stack Overflow Quais são os aplicativos / benefícios de um tipo de dados de precisão estendida de 80 bits?

Outros processadores, por exemplo, o ARM, darão resultados diferentes para este código.

Ian Ringrose
fonte
6

Talvez seja melhor calculá-lo sozinho usando apenas aritmética de inteiros. Algo como:

int n = 143;
int e = 103;
int result = 1;
int ascii = (int) 'a';

for (i = 0; i < e; ++i) 
    result = result * ascii % n;

Você pode comparar o desempenho com o desempenho da solução BigInteger postado nas outras respostas.

Ronald
fonte
7
Isso exigiria 103 multiplicações e reduções de módulo. Pode-se fazer melhor calculando e2 = e * e% n, e4 = e2 * e2% n, e8 = e4 * e4% n, etc. e, em seguida, resultado = e * e2% n * e4% n * e32% n * e64% n. Um total de 11 multiplicações e reduções de módulo. Dado o tamanho dos números envolvidos, pode-se eliminar mais algumas reduções de módulo, mas isso seria menor em comparação com a redução de 103 operações para 11.
supercat
2
@supercat Boa matemática, mas na prática relevante apenas se você estiver executando em uma torradeira.
alextgordon
7
@alextgordon: Ou se alguém está planejando usar valores de expoentes maiores. Expandir o valor do expoente para, por exemplo, 65521 levaria cerca de 28 multiplicações e reduções de módulo se alguém usar a redução de força, contra 65.520 se não usar.
supercat
+1 para fornecer uma solução acessível onde fica claro exatamente como o cálculo é feito.
jwg
2
@Supercat: você está absolutamente certo. É fácil melhorar o algoritmo, o que é relevante se for calculado com muita frequência ou se os expoentes forem grandes. Mas a mensagem principal é que ele pode e deve ser calculado usando aritmética de inteiros.
Ronald