在C#中,模运算符(%)在不同的.NET版本中会产生不同的结果。

88

我正在加密用户输入,以生成密码字符串。但一行代码在不同版本的框架中会产生不同的结果。以下是一部分代码和用户按键值:

用户按下的键:1。变量ascii的值为49。经过某些计算后,“e”和“n”的值如下:

e = 103, 
n = 143,

Math.Pow(ascii, e) % n

以上代码的结果:

  • In .NET 3.5 (C#)

    Math.Pow(ascii, e) % n
    

    gives 9.0.

  • In .NET 4 (C#)

    Math.Pow(ascii, e) % n
    

    gives 77.0.

Math.Pow()在两个版本中都会给出正确(相同)的结果。

是什么原因导致这种情况发生,是否有解决方法?


12
当然,问题中的两个答案都是错误的。你似乎并不关心这一点,这让人有些担忧。 - David Heffernan
34
你需要回退几步。 "我正在加密用户的输入以生成密码字符串" 这部分已经很可疑了。你实际想做什么?你想以加密或哈希形式存储密码吗?你想将其用作生成随机值的熵吗?你的安全目标是什么? - CodesInChaos
49
虽然这个问题展示了浮点数运算中的有趣问题,但如果提问者的目标是“加密用户输入以生成密码字符串”,我认为自行编写加密算法不是一个好主意,因此我不建议实际实现任何答案。 - Harrison Paine
18
其他语言为什么禁止在浮点数中使用“%”号,这是一个很好的例子。 - Ben Voigt
5
这些回答虽然不错,但都没有回答.NET 3.5和4之间发生了什么变化,导致了不同的行为。 - msell
显示剩余17条评论
6个回答

159

Math.Pow 适用于双精度浮点数;因此,您不应该期望结果超过 前15-17个数字 的准确性:

所有浮点数字也都有有限的有效数字位数,这也决定了浮点值近似实数的准确度。 Double 值具有最多15位十进制数字的精度,但在内部维护最大为17位数字。

然而,模算术要求所有数字都是准确的。在您的情况下,您正在计算 49 的 103 次方,其结果由 175 位数字组成,使模运算在您的两个答案中都没有意义。

要计算出正确的值,您应该使用任意精度算术,如 .NET 4.0 中提供的 BigInteger 类。

int val = (int)(BigInteger.Pow(49, 103) % 143);   // gives 114
编辑:正如Mark Peters在下面的评论中指出的那样,您应该使用BigInteger.ModPow方法,该方法专门用于此类操作。
int val = (int)BigInteger.ModPow(49, 103, 143);   // gives 114

20
感谢指出真正的问题,即问题中的代码是错误的。+1 - David Heffernan
36
值得注意的是,BigInteger 提供了一个 ModPow() 方法,用于执行(在我刚刚进行的快速测试中)比这种操作快约 5 倍的运算。 - Mark Peters
8
同意修改。ModPow 不仅快速,而且数值稳定! - Ray
2
@maker 不,答案是“无意义的”,而不是“无效的”。 - Cody Gray
3
@makerofthings7:我原则上同意你的观点。然而,由于浮点运算本质上存在不确定性,因此预计开发人员了解风险比一般情况下强制实施限制更为实用。如果想要真正“安全”,那么语言也需要禁止浮点数相等比较,以避免出现意外结果,例如 1.0 - 0.9 - 0.1 == 0.0 的计算结果为 false - Douglas
显示剩余6条评论

71
除了您的哈希函数不是很好用*,您代码中最大的问题不是根据.NET版本返回不同的数字,而是无论哪种情况下,它都返回一个完全没有意义的数字:问题的正确答案是49的103次方对143取模等于114(链接到Wolfram Alpha)。您可以使用以下代码计算此答案:
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;
}

你的计算产生不同结果的原因是,为了得出答案,你使用了一个中间值,丢失了49的103次方数的大部分有效数字:只有它的175位数字中的前16位是正确的!
1230824813134842807283798520430636310264067713738977819859474030746648511411697029659004340261471771152928833391663821316264359104254030819694748088798262075483562075061997649

剩下的159个数字全部都是错误的。然而,取模运算需要每一个数字都正确,包括最后一位。因此,即使在.NET 4中可能已经实现了对Math.Pow精度的微小改进,也会导致计算结果的巨大差异,从而产生任意结果。 *由于这个问题涉及到将整数提高到高次幂以进行密码哈希,在决定是否更换当前方法以寻求更好方法之前,阅读this answerlink可能是一个非常好的主意。

20
好的答案。实际关键在于这是一个糟糕的哈希函数。楼主需要重新考虑解决方案并使用更合适的算法。 - david.pfx
1
艾萨克·牛顿:月亮是否会像苹果一样被地球所吸引?@david.pfx:真正的问题是这是一个摘苹果的可怕方式。牛顿需要重新思考解决方案,或许雇佣一个有梯子的人。 - jwg
2
@jwg David的评论之所以得到那么多赞同,是有原因的。原始问题明确表示该算法正在用于散列密码,而事实上这是一个非常糟糕的用途 - 它很有可能在.NET框架的不同版本中发生问题,这已经被证明过了。任何没有提到OP需要替换算法而不是"修复"它的答案都对他造成了伤害。 - Chris
@Chris 感谢您的评论,我进行了编辑以包含David的建议。我没有像您那样表达得那么强烈,因为OP的系统可能是一个玩具或者一段他为自己娱乐而构建的临时代码。谢谢! - Sergey Kalinichenko

26

你看到的是双精度浮点数的舍入误差,Math.Pow 使用双精度浮点数进行计算,其差异如下:

.NET 2.0 和 3.5 => var powerResult = Math.Pow(ascii, e); 的返回结果为:

1.2308248131348429E+174

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

1.2308248131348427E+174

注意在 E 前面的最后一位数字导致了结果的差异。这并不是取模运算符 (%) 的原因。


3
这是回答原帖问题的唯一答案吗?我看了所有的"废话安全性错误问题我比你懂n00b",但仍然想知道为什么3.5和4.0之间存在持续的差异?你曾经在看月亮时被石头绊倒并问“这是什么石头?”只听到“你的真正问题不在于你没有看脚”或者“晚上穿自制凉鞋还期待什么呢!!!”感谢! - Michael Paulukonis
1
@MichaelPaulukonis:这是一个错误的比喻。研究岩石是一项合法的追求;使用固定精度数据类型执行任意精度算术是完全错误的。我会把它比作软件招聘人员询问为什么狗比猫更不擅长编写C#。如果你是一名动物学家,这个问题可能有一些价值;对于其他人来说,这是无意义的。 - Douglas

23

浮点精度在不同机器上甚至同一台机器上也可能会有所不同(甚至在同一台机器上)

然而,.NET为您的应用程序提供了虚拟机...但是版本之间可能会有变化。

因此,您不应该依赖它来产生一致的结果。对于加密,请使用框架提供的类而不是自己编写。


10

关于代码为什么会出现不同结果,有很多答案。然而,造成结果不同的原因是…

因特尔的浮点数单元在内部使用80位格式来获取中间结果的更高精度。所以,如果一个值在处理器寄存器中,它将获得80位,但当它被写入堆栈时,它将被存储在64位

我预期较新版本的.NET在其即时(JIT)编译器中有更好的优化程序,因此它将一个值保留在寄存器中,而不是将其写入堆栈,然后从堆栈中读取它。

可能是JIT现在可以返回一个值到寄存器而不是堆栈,或者将该值作为参数传递给MOD函数。

另请参阅Stack Overflow问题“80位扩展精度数据类型有哪些应用/好处?”

其他处理器,例如ARM,将对此代码产生不同的结果。


5
也许最好使用整数算术自己计算。例如:
int n = 143;
int e = 103;
int result = 1;
int ascii = (int) 'a';

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

您可以将其性能与其他答案中发布的BigInteger解决方案的性能进行比较。

7
这将需要103次乘法和模数减法。 通过计算e2 = e * e%n,e4 = e2 * e2%n,e8 = e4 * e4%n等等,可以更好地完成任务,然后结果 = e * e2%n * e4%n * e32%n * e64%n。总共有11个乘法和模数减法。考虑到所涉及的数字大小,可以消除更多的模数减法,但相比将103次操作减少到11次,这只是微不足道的。 - supercat
2
@supercat 数学很好,但实际上只有在你在烤面包机上运行此代码时才相关。 - alextgordon
7
如果有人计划使用更大的指数值,采用强度降低技术将指数扩展到例如65521需要约28次乘法和模数减少操作,而不使用该技术则需要65520次。 - supercat
如果提供一个易于理解的解决方案,并清楚地说明计算过程,那么就可以得到+1分。 - jwg
2
@Supercat:你说得完全正确。如果算法经常被计算或指数很大,那么改进算法是很容易的。但主要的信息是,它可以并且应该使用整数算术来计算。 - Ronald

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接