DHKE 平方和乘法

給定的是一個DHKE算法。模數 𝑝 有 1024 位，𝛼 是子群的生成器，其中 𝑜𝑟𝑑(𝛼)≈2160。

假設已經計算了公鑰，那麼會話密鑰中有多少個模乘和模平方。

使用平方和乘法算法 $ 2^{160} $ :

160 = 10100000 二進制

1 第一個列表編號 2

0 Square 的零呼叫 $ (2){^2} $

1 要求 Square + Multiply $ ((2){^2}){^2} $ * 2

0 Square 的零呼叫 $ (((2){^2}){^2} $ * 2) $ {^2} $

0 Square 的零呼叫 $ ((((2){^2}){^2} $ * 2) $ {^2} $ ) $ {^2} $

0 Square 的零呼叫 $ (((((2){^2}){^2} $ * 2) $ {^2} $ ) $ {^2} $ ) $ {^2} $

0 Square 的零呼叫 $ ((((((2){^2}){^2} $ * 2) $ {^2} $ ) $ {^2} $ ) $ {^2} $ ) $ {^2} $

0 Square 的零呼叫 $ (((((((2){^2}){^2} $ * 2) $ {^2} $ ) $ {^2} $ ) $ {^2} $ ) $ {^2} $ ) $ {^2} $

因此，對於 160 的指數，應該有 7 個平方和 1 個乘法。

類似地，如果我們現在假設 α 是一個如此短的元素（例如，一個 16 位整數）。

使用平方和乘法算法，我們應該得到 16 的指數共有 4 個平方和 0 次乘法。

這是對會話密鑰使用平方和乘法算法的模乘和平方數的正確理解嗎？

標準 DHKE

標準 DHKE 是在乘法組上定義的。Alice 和 Bob 就循環群達成一致 $ G $ 有秩序的 $ n $ 和一個發電機 $ g $ 然後密鑰協商執行如下；

$$ \begin{array}{lcl} \text{Alice} & \text{Transmit} & \text{Bob}\ \hline a \stackrel{R}{\leftarrow} [1,n-1]& & b \stackrel{R}{\leftarrow} [1,n-1]\ \text{calculates } A = g^a & \xrightarrow{A} & \text{calculates } B = g^b\ & \xleftarrow{B} & \text{calculates } s = B^a = (g^a)^b = g^{ab} \ \text{calculates } s = A^b = (g^b)^a = g^{ab} & & \end{array} $$

因此雙方達成一致意見 $ s = g^{ab} $ 和

組選擇

我們可以使用以下 3 個素數類來選擇 $ p $ ;

1. 在表格中選擇一個素數 $ p = kq+1 $ 那些被poncho稱為 DSA prime 。它們的生成成本很低。
2. 選擇形式的素數 $ p = 2qr+1 $ 那些被稱為 Lim-Lee 素數，其中兩者 $ q $ 和 $ r $ 大約一半大小的素數 $ p $ .
3. 選擇形式的素數 $ 2q+1 $ 那些被稱為安全素數和 $ q $ 被稱為索菲熱爾曼素數。

這些組的生成容易性和安全順序是 $ 1<2<3 $

如果你選擇 $ \mathbb{Z}_p $ 那麼乘法順序是 $ p-1 $ 這不是一個素數，該組可能容易受到 Pohlig-Hellman 的攻擊。通過上述方法，我們保證我們有一個大訂單的元素 $ q $ .

模冪

def modular_pow(base, exponent, modulus):
   if modulus == 1:
       return 0
   result = 1
   base = base % modulus
   
   while exponent > 0:
       if (exponent % 2 == 1):
           result = (result * base) % modulus
       exponent = exponent //2
       base = (base * base) % modulus
   return result

計算

讓我們從RFC 7919中獲取 ffdhe2048

• $ p = p = 2^{2048} - 2^{1984} + (\lfloor(2^{1918} \cdot e \rfloor + 560316 ) \cdot 2^{64} - 1 $
• $ g = 2 $
• $ q = 2*p+1 $ ，所以我們有一個安全的素數。
• $ n = q = (p-1)/2 $ ， 和
• 一個 = 160

Exponent =  0
  Squaring   , base   =  4
Exponent =  0
  Squaring   , base   =  16
Exponent =  0
  Squaring   , base   =  256
Exponent =  0
  Squaring   , base   =  65536
Exponent =  0
  Squaring   , base   =  4294967296
Exponent =  1
  Multiplying, result =  4294967296
  Squaring   , base   =  18446744073709551616
Exponent =  0
  Squaring   , base   =  340282366920938463463374607431768211456
Exponent =  1
  Multiplying, result =  1461501637330902918203684832716283019655932542976
  Squaring   , base   =  115792089237316195423570985008687907853269984665640564039457584007913129639936

Result =  1461501637330902918203684832716283019655932542976

註釋 160

指數太小而不安全。當攻擊者看到結果並與

p=

他們只會認為您使用了一個小數字，並會通過蠻力搜尋它。這 $ a $ 必須均勻隨機地選擇為 $ a \stackrel{R}{\leftarrow} [1,n-1] $ .

其實我們不需要 $ a \stackrel{R}{\leftarrow} [1,n-1] $ 為了安全 $ a \stackrel{R}{\leftarrow} [1,2^{224}] $ 根據 NIST（參見keylenght.com） ，在 2019 年到 2030 年之間就足夠了。正如表揚中所說的雨披，這更有效。

表現

現在操作的數量是可數的。我們必須對指數的每一位求平方（ $ 160_{10} = [10100000]_2 $ ) 和當位為 1 時乘法 ( 2 次為 160 正弦 $ 160= 128+32 $ ).

上述函式對於計算模冪運算不是最優的，並且容易受到側通道的影響，因為存在一個取決於指數位的條件。

中間人

標準 DHKE 容易受到MITM 攻擊，而Telegram 也有不同的攻擊。為了減輕 MITM 攻擊，需要數字簽名。

會話密鑰的生成是用私鑰為公鑰供電，其中私鑰為整數 $ < 2^{160}-1 $ ，即 160 位。因此，它需要 159 個方格和 0.5*160 倍數（平均）。

引用自：https://crypto.stackexchange.com/questions/89606