Terminology

影響計算但不影響結果的隨機數叫什麼?

  • October 5, 2022

這與我之前的問題大致相同的隨機梯形算法。它計算 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 有名稱嗎?如果沒有,你能推荐一個嗎?

使用影響中間值但不影響最終結果的輔助輸入的技術稱為***盲法。輔助輸入可以稱為“盲參數”或其他一些變體,這取決於它在計算中的使用方式,例如“盲因子”,如果它用於乘法。當使用按位運算完成致盲時,通常稱為掩蔽***。

盲法是避免密碼計算中的側通道攻擊的常用技術。致盲參數通常是隨機的,但並非總是如此——在某些情況下,確定性致盲是有用的(例如,從私鑰和簽名操作中的消息確定性地派生出致盲因子)。僅當側通道無法在單個跟踪中顯示所有秘密數據時,隨機盲法才有幫助,但這是一種常見情況。


(請注意,我不擅長攻擊——以下內容來自我作為一名防守者的經驗,專家來找我說“嘿,我們在你的產品中發現了這個邊路”,我正在尋找一種方法來消除這一邊渠道。)

這裡提出的致盲策略對我來說並不好看。讀取冪運算的位是一個非常有名的側通道,將大指數的冪運算分解為一系列可變的乘法並不會消除此側通道。在許多平台上,在同一台機器上執行的程式碼可以以合理的精度測量單個跟踪中的指數。即使在更好的隔離平台上(例如,遠端攻擊),通過觀察許多痕跡,對手也可以了解因素的分佈,這可能足以重建具有實際可行數量的痕蹟的指數。

通常,在計算中添加雜訊只是對側通道攻擊的有限防禦。它迫使對手觀察更多的計算實例,但這僅在側通道有限的情況下是一種很好的防禦,因此非雜訊計算需要大量時間來攻擊,而雜訊導致攻擊時間變得不切實際。即使單個計算實例洩露秘密資訊,噪音也無濟於事。

你正在重新發明一個眾所周知的輪子,而你的輪子非常方正。我強烈建議您瀏覽有關攻擊和求冪實現的文獻,並看看現有的密碼庫是如何做到的。避免定時側通道的優選方法不是隨機化(使定時取決於秘密輸入和輔助秘密的組合),而是使操作的時間完全獨立於秘密輸入。

數字 r 有名稱嗎?

我遇到的用來描述這一點的術語將是致盲因素

現在,對於 modexp 操作,對指數進行盲法的標準方法是 Coron 盲法,即計算 $ g^x \bmod p $ 是隨機選擇一個 $ r $ 併計算:

$$ g^{x + rq} \bmod p $$

(在哪裡 $ q $ 是子組的大小;如果您正在對有限域進行求冪,那麼 $ q = p-1 $ )。

如果 $ q $ 在其二進製表示中沒有一長串 0 和 1,那麼這適用於適度的 $ k $ ; 如果有這麼大的字元串,可以解決,但它更複雜。在任何情況下,您都可能需要考慮將其作為您的技術的替代方案或補充。

引用自:https://crypto.stackexchange.com/questions/102099