我對這個雜湊問題的回答正確嗎？
問題
在確定雜湊系統的安全性時，密碼分析員會嘗試以下攻擊。
(a) 如果不允許攻擊者修改原始消息，請確定有 50% 的機會生成與原始消息具有相同雜湊的新消息所需的雜湊計算次數。在您的計算中，假設雜湊長度為 8 位。
(b) 推導出雜湊計算次數的表達式， $ n $ ，需要有 30% 的機會生成具有相同雜湊的兩條不同消息。確定近似值 $ n $ .
我的答案
以上是我認為是正確的，如果我錯了，請告訴我，謝謝！
一個）
$ \text{Hashed} = \big(\frac{2^8}{2}\big) $ = $ \big(2\big)^7 $
$ p = 1 - \big(\frac{(2^7-1)}{2^7}\big)^n $
$ n = 88.38 \rightarrow n = 89 $ .
b)
$ \text{Hashed} = \big(2^\frac{8}{2}\big) $ = $ \big(2\big)^4 $ = $ 16 $
$ p(n) = 1 - (\frac{\text{Hashed}!}{\text{hashed}^n(\text{hashed}-n)!}) $ = $ 1 - (\frac{16!}{16^n(16-n)!}) $
$ p(n) = 1 - e^{(-n^2+n/2 \times 16)} $
$ n = 4.57 \rightarrow n = 5 $
生日攻擊
$ q(n) = 1 - \big(\frac{365-1}{365}\big)^n $
應用科學（物理學、密碼學）需要記住的不是一套公式。對於一些研究過的最簡單的公式，它是：公式產生什麼，輸入什麼，輸入和輸出的單位，以及當公式不歸結為以一種可以可以從單位中找到。當一個人無法推導出公式或不知道其單位時，在現實生活中應用它是有風險的¹。
我們有一個例子：問題最初帶有所有正確的公式，但是輸入應該失去，或者輸入錯誤的單位（雜湊數與雜湊長度（以位為單位）），正如簡潔的答案所暗示的那樣。而對於現在添加的公式即圖片 $ q(n)=1-\left(\frac{365-1}{365}\right)^n $ 它失去了公式產生的東西，它與生日攻擊幾乎沒有關係，這與公式的標題相反。
該公式給出了其中的機率 $ n $ 人，至少有一個人出生在某個未指定年份的 7 月 4日²，假設在一年中的 365 天中的每一天中平均重新分配人類的出生日期³，並隨機選擇 $ n $ 人類⁴。
我們如何推導出該機率的公式 $ q(n) $ ? 畫一個房間。讓 $ n $ 是房間裡的人數， $ k=365 $ 一年中的天數。如果房間是空的，那麼房間裡沒有人在 7 月 4日出生。因此 $ q(0)=0 $ . 現在，想像一個一個進入房間的人（沒有人離開），直到有 $ n>0 $ . 當且僅當兩個事件中的至少一個發生時，房間裡的某人在 7 月4日出生：
- 在最後一個進入房間的人之前，已經有一個人在 7 月 4日出生。該事件的機率為 $ q(n-1) $ ，根據我們給出的定義 $ q $ .
- 最後一個進入房間的人出生在 7 月 4日。該事件的機率為 $ 1/k $ 並且獨立於 $ n $ 和之前的事件（在“假設”之後的上述假設下）。
有一個公式可以計算多個獨立事件之一的機率。幫自己一個忙，忘掉它。相反：如果事件的機率不明顯，請嘗試互補事件。這裡的補充事件是：房間裡沒有人在 7 月 4日出生。應該清楚的是，在我們的（非空的）房間裡，沒有人在 7 月 4日出生當且僅當那是在最後一個人進入房間之前舉行的，並且那個人不是在 7 月 4日出生的，這是上述 (2.) 的補充事件。
現在是時候在機率中應用三個必不可少的規則了：
- 獨立事件全部成立的機率是它們機率的乘積。
- 互補事件的機率是 1 減去事件的機率。
- 當去補充事件時，事件的獨立性被保持。
我們得到： $ \forall n>0 $ ， 它擁有 $ 1-q(n)=(1-q(n-1))\times(1-1/k) $ .
通過歸納，或直接將第一條規則應用於房間中的所有人， $ 1-q(n)=(1-1/k)^n $ , 我們可以重寫為 $$ q(n)=1-\left(\frac{k-1}k\right)^n $$ 並獲得問題的公式 $ k=365 $ .
那麼這如何適用於這個問題呢？好吧，在（a）中，我們想要機率 $ n $ 的雜湊 $ b=8 $ 位長度與特定消息的雜湊值具有相同的值。將雜湊想像為一個 8 位值，例如 $ \tt 01100101 $ . 在散列函式（從消息產生散列的事物）表現為隨機函式的標准假設下，散列表現為 $ 2^b=2^8=256 $ . 這與房間里人們的出生日期相似，它表現為隨機值 $ k=365 $ . 因此，我們可以調整我們現有的公式，替換 $ k $ 和 $ 2^b=2^8=256 $ ，並得到 $ q(n)=1-\left(\frac{2^b-1}{2^b}\right)^n $ 或同等的 $ q(n)=1-\left(1-2^{-b}\right)^n $ .
在這裡，我們可以直接應用該公式，因為 $ b=8 $ 是小。但請注意，在密碼學中，我們的雜湊值通常使用更大的值 $ b $ ，例如 $ b=224 $ 現在在某些應用程序中將被視為最低限度。這個公式仍然成立，但我們可以解決它的數值穩定性問題。在這方面使用一盎司的數學並不難。
我真的建議一個學生推導出問題（b）的公式，並且只使用我的生日問題中的那些進行加密雜湊，101來驗證結果，或者在努力之後。
¹ 錯誤地應用公式可能會在工程、化學、醫學和商業中造成重大損失或死亡。在高等教育中，在此類考試中經過深思熟慮的符號應該恕我直言懲罰不正確的答案，而不是沒有答案與正確答案。
² 這也適用於我的生日，或一年中除 2 月 29日以外的任何特定日子。
³ 一個近似模型，主要是因為大多數物種的生殖活動是季節性的，在某種程度上包括人類。
⁴ 這個假設在駕照考試中可能是嚴重錯誤的。