什么是影响计算的随机数，而不是结果？

Question

这是与我以前的问题相同的随机梯算法。它计算f(g，n，r)=n*g或g^n (取决于组表示法)，其中g是组的生成器。假设n=5882353。这可以计算为

((((((((((1*2*2+1)*2+1)*2*2*2+1)*2+1)*2+1)*2*2*2*2*2*2+1)*2+1)*2+1)*2+1)*2+1)*2*2*2*2+1
(((((((1*3*3+2)*2+1)*2+1)*3*3+2)*2+1)*3*2*3*2+1)*2*2+1)*2*2*2*3*2+1
((((((1*3+2)*3*3+2)*2*3+1)*3+2)*2*3*2*3+1)*2*2+1)*3*2*2*2*2+1
((((((((1*3*3+2)*3*3*3+1)*3+2)*3+1)*3+2)*3*3*3+1)*3+2)*3+2)*3+1

还有约215,000种表示n的其他方法，即乘以2或3，加上1或2，取决于r. r是0到1之间的一个数字，以a/b表示，其中b的位数至少是n的78.8%，目的是使Eve在观察侧频道时很难找出n是什么。有r号的名字吗？如果没有，你能推荐一个吗？

Answer 1

使用影响中间值(但不影响最终结果)的辅助输入的技术称为未定义未定义。辅助输入可以称为“盲参数”，或者其他取决于在计算中如何使用的变量，例如，如果在乘法中使用“盲因子”。当盲是按位操作完成时，通常被称为掩蔽。

盲是密码计算中避免侧信道攻击的一种常用技术。盲参数通常是随机的，但并非总是随机的--在某些情况下，确定性盲是有用的(例如，从私钥和签名操作中的消息导出的盲因子)。随机盲只有当侧通道不能在一个跟踪中显示所有秘密数据时才有帮助，但这是一个常见的情况。

(请注意，我不擅长攻击--以下是我作为一名后卫的经验，专家来找我说：“嘿，我们在你的产品中找到了这个侧通道”，我想找个办法消除这条通道。)

在我看来，这里提出的致盲战略看上去不太好。读取一个指数的位数是一个非常著名的边信道，用一个大指数分解成一个可变的乘法序列并不能消除这个边信道。在许多平台上，运行在同一台机器上的代码可以以合理的精度测量单个跟踪中的指数。即使在更好的孤立平台上(例如，远程攻击)，通过观察许多痕迹，对手也可以了解因素的分布，这可能足以用实际可行的跟踪数重建指数。

通常，在计算中添加噪声只是对侧信道攻击的有限防御。它迫使对手观察更多的计算实例，但只有当侧信道受限时，这才是一个很好的防御，因此一个无噪声的计算需要大量的时间来攻击，而噪声导致攻击时间变得不切实际。即使一个计算实例泄露秘密信息，噪声也于事无补。

你在重新发明一个著名的轮子，而你的轮子非常正方形。我强烈建议您浏览有关攻击和指数化实现的文献，并查看现有的密码库是如何做到的。避免定时侧信道的较好方法不是随机化(使定时依赖于秘密输入和辅助秘密的组合)，而是使操作的定时完全独立于秘密输入。

Answer 2

有r号的名字吗？

我用这个词来形容这将是令人眼花缭乱的因素

现在，对于modexp操作，对指数进行盲化的标准方法是Coron盲，也就是说，计算g^x \bmod p的方法是选择一个随机的r并计算：

g^{x + rq} \bmod p

(其中q是子群的大小；如果在有限域上进行幂运算，那么q = p-1)。

如果q的二进制表示法中没有0's和1's的长字符串，那么这在一个适度的k中很好；如果有这么大的字符串，它可以工作，但它更复杂。在任何情况下，您可能想要考虑这一点，或者作为您的技术的替代或补充。

Answer 3

有几种算法“使用”随机数(S)的方式对结果没有显著的影响：

• 在密码盲密码盲中使用了一个致盲因素，结果完全相同，但(希望)阻塞侧通道攻击(其他人已经回答了)。
• 随机密钥被用来对抗散列泛洪攻击 --不管选择什么密钥，这样的键哈希表产生的结果与非键哈希表完全相同，但是如果密钥是保密的，攻击者就不能强制哈希表冲突，这会导致服务器运行得慢得多。
• 随机密钥通常在SSD的内部(当“整个磁盘被擦除”时，只通过物理擦除该随机键来减少磨损)
• 在许多密码系统中，每个消息都使用唯一的(通常是随机的) 纳塞，例如初始化向量，以提供语义安全。
• 前向保密的一些密码系统使用了一个临时密钥(通常是随机密钥)。

在密码学之外，

• 随机值用于随机算法和随机算法，随机方向用于合成随机游动。通常这样的算法“通常”产生接近正确答案的结果，而随机化使得它不太可能产生一个非常糟糕的答案。
• 虽然小可见粒子的布朗运动显然是由更小的亚微观分子的不可预测的随机速度引起的，爱因斯坦和Smoluchowski表明(实际上不依赖于特定的随机速度)这些小粒子的均方位移可以用来测量分子的尺寸。
• 有些机器人偶尔会转向一个随机的角度来避免卡住--特别是早期的机器人吸尘器使用了这样的随机导航。特定的随机值不会影响最终结果--最终整个地板都会被探测到。
• 对植绒行为的模拟有时会产生令人惊讶的逼真、复杂和不可预测的行为，这些行为似乎至少部分是随机的，使用了一个令人惊讶的简单和确定性的"boids“算法。