簡單加密 - 在C哈希值的總和

Question

我試圖證明概念的一個簡單證明相對於一個脆弱性在遊戲中的一段代碼用C寫的

比方說，我們要驗證字符登錄。登錄由用戶從圖形菜單中選擇n項目（現在讓我們假設n=5）處理。這些項目都是中世紀主題：

如：

_______________________________ 
|   |   |  | 
| Bow  | Sword  | Staff | 
|-----------|-----------|-------| 
| Shield | Potion | Gold | 
|___________|___________|_______| 

用戶必須點擊每個項目，然後選擇每個項目的編號。

驗證算法然後執行下列操作：

1. 其中被選定的項目確定
2. 降價每個字符串爲小寫（即：Bow變得bow等）
3. 計算一個簡單的字符串的散列每個字符串（即：`弓=> b = 2，O = 15，W = 23，總和=（2 + 15 + 23 = 40）
4. 乘以散列由所述值選擇相應的項目的用戶;該新值被稱爲key
個
5. 和的一起keys爲每個所選項目;這是最後的驗證哈希
6. 重要提示：驗證會接受這個散列，與它的非零倍數沿（即：如果最終散列等於1111，然後2222，3333，8888等也有效）。

因此，舉例來說，假設我選擇：

Bow (1) 
Sword (2) 
Staff (10) 
Shield (1) 
Potion (6) 

算法降低這些字符串爲小寫，計算出它們的字符串哈希值，乘以選定每串哈希通過號碼，然後將這些鍵彙總在一起。

如：

Final_Validation_Hash = 1*HASH(Bow) + 2*HASH(Sword) + 10*HASH(Staff) + 1*HASH(Shield) + 6*HASH(Potion)

歐拉方法的應用，我打算證明這些哈希值是不是唯一的，要制定一個簡單的應用程序來證明這一點。

在我的情況

，用於5個項目，我就基本上可以嘗試計算：

(B)(y) = (A_1)(x_1) + (A_2)(x_2) + (A_3)(x_3) + (A_4)(x_4) + (A_5)(x_5)

其中：

B is arbitrary 
A_j are the selected coefficients/values for each string/category 
x_j are the hash values for each string/category 
y is the final validation hash (eg: 1111 above) 
B,y,A_j,x_j are all discrete-valued, positive, and non-zero (ie: natural numbers) 

能有人要麼幫助我解決這個問題，或者點我到一個類似的例子（即：代碼，計算方程等）？我只需要解決最後一步（即：（B）（Y）= ...）。

---

最後，我寫了一個遞歸算法，去n層次深，然後把手遞增，測試等，所有剩餘的可能的組合。效率不高，但效果顯着。我可以根據要求提供它（太大而無法在此發佈）。

Answer 1

在我看來，大多數用戶會選擇相當小的數字爲每個項目（畢竟「2」比他們更容易記住「438483」）。

鑑於這種限制，蠻力實際上可能是合理的。

簡單地爲5個符號加上一個數字，例如1..99範圍內的所有可能的輸入值，計算結果散列，並計數（例如使用字典）計算產生給定散列的不同組合的數量應該給出對最可能的輸入值散列分佈的經驗性理解。

從那裏我會看看有多少個不同的哈希值實際上是生成的（如果哈希是一個Int32，則有2^32個可能的哈希值），以及查找以特定頻率生成的哈希值（在字典中有很高的計數）。

Answer 2

那麼它可能會或可能不會取決於菜單x_j，係數A_j，和驗證哈希y，並且選擇的項目n數量上的項目是唯一的。

例如，如果您的驗證散列是1會發生什麼？然後，一切都會驗證。

另一方面，如果你有n是項目的總數，那麼只有一個可能的散列是唯一的。

當然這些都是極端的例子，但它們說明了這一點。這取決於你的參數。除了暴力外，沒有一種簡單的通用方法來檢測哈希是否是唯一的。

Answer 3

這是非常平凡的，因爲算法接受非零倍數。如果你乘以二所有輸入你就會有一個矛盾：

Bow (1) 
Sword (2) 
Staff (10) 
Shield (1) 
Potion (6) 

y = (A_1)(x_1) + (A_2)(x_2) + (A_3)(x_3) + (A_4)(x_4) + (A_5)(x_5) 

2再乘以他們：

Bow (2) 
Sword (4) 
Staff (20) 
Shield (2) 
Potion (12) 

2(A_1)(x_1) + 2(A_2)(x_2) + 2(A_3)(x_3) + 2(A_4)(x_4) + 2(A_5)(x_5) 
= 2((A_1)(x_1) + (A_2)(x_2) + (A_3)(x_3) + (A_4)(x_4) + (A_5)(x_5)) 
= 2y 

Answer 4

雖然這不是一個正式的證明，但我有一個想法。

讓不同的字符串的哈希值是h_1，h_2，...，h_n線性和將

y = h_1 + h_2 + ... + h_n

一旦我們有y，我們總能找到h_1'，h_2'，... ，h_n'，使得該系列中的至少一對i和jh_i != h_j'。

所以我們可以重複h值來得到最後的總和。

再次，因爲每個h值從一些整數（字符的代表值），因此一個特定的h值可以由不同的線性和來實現的線性和產生的，也就是不同的字符串。

乘數值可以調整。而且，即使乘數值是恆定的，即重複哈希生成器也不能選擇它，與乘數相乘的值可以被修改，使得相乘的鍵的總和保持不變。

因此，我們可以從許多字符串中生成一個散列。

Answer 5

設置所有，但最後的係數爲1，那麼你得到的形式的東西的* XN = R（MOD Y），然後使用擴展歐幾里德算法來找到解決的辦法，請參閱Wikipedia