问为什么代数证明适用于密码学？

EN

在计算机上实现的整数运算与整数的理论定义是同构的。否则，操作将不能给出正确的结果。

考虑到你问题中的术语，我怀疑当你想到计算机上的整数运算时，你想到的是机器单词上的操作。密码学使用不适合机器单词的数字:任何在整数上工作的密码代码(通常来说是非对称密码)都必须包括一个bignum图书馆 (或者依赖第三方密码)。

二的补语是表示负整数的一种方法。它与密码学无关，因为密码学几乎从不使用负整数:只有非负整数($\mathbb{N}$，或使用其代表存储在范围$$中的整数调制$n$ )。

您可以在许多地方找到Peano算法和二进制表示算法之间等价的形式证明，例如在BitNatCoq模块中。

就获得正确的结果而言，实现整数操作是一个没有问题的问题，但它确实会对安全性产生影响。如果实现不小心，侧通道 (例如定时和内存访问模式)可能泄露机密数据，如果对手找不到有关中间值的任何信息，该协议的安全性就会受到损害。

我们知道，整数的数论模型并不总是为计算机实现的整数的行为提供一个完善的甚至实际适用的模型。应用密码学必须考虑到

• 机器字的可能溢出(很少大于64位，比非对称密码中使用的要小得多)。这是相对容易的部分，并由"bignum“库(内置于某些语言)进行处理。
• 通常用于特定编译器和硬件的实现错误(示例)非常罕见和模糊:当DIV/DIVW指令被中断并在执行第一个ISR的IRET指令期间生成第二个中断时，就会发生此错误。
• 依赖于数据的时间依赖: bignum库和一些硬件或/和编译器往往会花费可变的时间，这取决于机器使用的单词数和被操纵的值，这可能导致密钥或明文泄漏。一篇基础论文是PaulC.Kocher Diffie-Hellman、RSA、DSS和其他系统实现的定时攻击 (在密码1996年的议事程序中)。这是针对定制的bignum库的特殊实现，要么在固定时间内操作，要么很难从剩余时间变化中收集可利用的信息。一个重要的特例是比较(memcmp库函数，有时甚至是相等的操作符==)，它是定时攻击的一个常见且容易的目标。
• 其他方面的渠道，如电力消耗。一篇基础论文是PaulC.Kocher，Joshua，Benjamin Jun 差分功率分析 (在密码1999年议事录中)。
• 缺陷:攻击者经常会强迫实现发生错误(在智能卡的IC上使用激光)并从所得到的不正确结果中推断出信息。一个基本的例子是所谓的Bellcore攻击: Dan，Richard . DeMillo和RichardJ.Lipton 关于对密码协议进行故障检测的重要性 (在密码学杂志，2001年年中，最初在1997年年欧洲地窖的诉讼程序中)。这里是对实用性的(过时的)介绍。

在理论上，忽略了上述问题，对于通常的无符号二进制算法，整数模$2^k$和$k$-bit计算机字之间有精确的对应(同构)。数学双操作数算子$+$、$-$、$\cdot$ (乘法)、$/$ (这里理解为欧氏除法的商数)和$\bmod$ (欧几里德除法的余数)与C语言中的+、-、*、/和% (以及可用的硬件指令)精确地对应于任何unsigned类型的变量，但除除法和右运算值为零的余数(在数学中是禁止的，但导致计算机算术中未定义的行为或例外)外。

对于$k$-bit 2-补中的有符号整数，当实现忽略溢出时，类似的对应关系适用于加法、减法和乘法。范围$[0，2^{k-1}]$中的整数表示为无符号二进制算术，整数$x\in[-2^{k-1},0)$具有$x+2^k$在无符号二进制算术中的机器表示形式。剩余类模$2^k$的代表位于间隔$[-2^{k-1}，2^{k-1}]$而不是$[0,2^k)$。商数和余数没有明确的对应关系( (-1)%2可能是-1或1 )。