SRVB 密碼系統入門

介紹

信息安全是一個引人入勝的知識領域，可以涉及從理論計算機科學到軟件工程的任何內容，甚至可以觀察人為錯誤的心理。

密碼學現在是我們日常生活中眾多匿名的技術英雄之一。 社交網絡、網上銀行、軍事情報和任何其他處理敏感信息的信息系統都嚴重依賴密碼學。 密碼學讓我們擁有隱私，有些人認為這是第 12 項人權。

本文將向您介紹公鑰密碼系統背後的原理，並向您介紹由本文作者和 Daniel Santana Rocha 教授開發的密碼系統 Santana Rocha-Villas Boas (SRVB)。 在撰寫本文時，算法作者正在策劃一項活動，其中包括對任何設法破解密碼的人進行經濟獎勵。 由於本文將詳細介紹算法功能，因此這是開始追求獎品的最佳場所。 更多信息可在 SRVB 網站上找到。

什麼是密碼系統？

密碼學是阻礙消息可解釋性的任何方法，同時只要提供特定指令（通常是所謂的“密鑰”），仍然允許一種可行的方法來解釋它。 雖然這是一個非常廣泛的定義，甚至包含了最早的技術，但值得一提的是，這並沒有涵蓋信息安全的所有內容。

加密方法和破解方法之間的技術競賽預計永遠不會有最終的贏家。 每一代都有望提高信息安全和密碼分析的標準，這是一套系統地破譯/破解加密信息的技術，即繞過安全或加密。

為了讓用戶認為密碼系統（給定的密碼學技術）是安全的，它必須得到國際專家社區的認可，從而為公眾所知，這就是眾所周知的 Kerckhoffs 原則。 然而，正是這種情況將系統暴露在世界密碼分析界的審查之下，他們將試圖設計系統地破解加密的方法。

如何讓一個給定的加密過程足夠保密，只有預期的代理才能解密它，同時又足夠公開，讓世界密碼分析界可以證明它的穩健性？ 答案是一個組件，它是密碼學的關鍵元素：密鑰。 密碼系統的密鑰是加密或解密算法或兩者的參數。 通過對參數保密，而不是對算法族保密，可以實現這兩個矛盾的要求。 假設參數族足夠大（可能是無限的）並且可以證明其每個組件具有足夠的屬性，那麼攻擊者僅通過檢查來確定參數是不可行的。

最後，為了使密鑰有效工作，它必須易於生成，但幾乎不可能被猜到。 憑藉當今計算機的計算能力，計算機破譯人類生成的密鑰所需的時間比任何人想像的要少，而且以這種方式生成密鑰並不具有成本效益。 因此，密鑰往往由算法生成。

作為典型使用的結果，密鑰生成算法不得創建可預測/可重現的輸出。 由於算法在沒有任何智能過程的情況下執行程序，問題就變成瞭如何做到這一點。 答案是將密鑰生成算法轉換為將大量真正隨機位轉換為密鑰的映射。 真正的隨機位可以從操作系統中獲取，操作系統是從宇宙中的不確定性中生成它們的。 某些來源可能是您的鼠標移動、網絡包延遲，甚至是專用硬件，具體取決於應用程序。

公鑰密碼系統

準備好再次感到驚訝，因為我們現在要介紹一個與我們剛才所說的似乎相矛盾的概念：公鑰。

到目前為止，我們已經看到在安全交換秘密參數（密鑰）之後創建了安全通信，但是通過公共渠道交換參數的問題仍然存在。 現在，我們將介紹一個解決一個稍微明顯的問題的概念：創建安全通道。

假設 Alice 與 Bob 一起工作，他們希望使用加密來保證工作交互的安全。 他們可以通過給對方一個帶有密鑰的 USB 閃存驅動器來見面並交換他們的加密密鑰。 但是如果愛麗絲和鮑勃位於不同的大陸呢？ 如何在不存在的情況下建立安全通道？

通過電子郵件發送密鑰不是一種選擇，因為他們的競爭對手 Eve 可以攔截交換並在之後使用他們的密鑰讀取所有加密數據。 如果他們有任何其他數字渠道可以傳輸這些敏感數據，那麼他們首先就不需要加密，因此也不需要密鑰。 通過物理郵件發送密鑰也可能被截獲，因為它首先需要交換敏感信息。 通過隱藏在其他數據中來發送隱寫密鑰會很聰明，但沒有用，除非發送者確定接收者，並且只有接收者知道這樣的消息的存在並且知道如何提取它。 碰巧的是，對消息存在的認識以及如何從數據中提取密鑰的描述本身就是一種密鑰，這使我們回到了原點。

解決方案是設計一個密碼系統，其加密參數不足以合理地解釋原始消息^[1] ，並將允許解釋消息的參數保留給自己。 我們稱該參數為私鑰。 基於私鑰，人們可以為加密工俱生成一組參數，而無需讓這些新參數本身能夠揭示私鑰是什麼。 這組參數可以公開共享，因為誰可以加密東西並不重要，只要只有一個人可以解密它。 由於加密工具的這組參數可以公開，因此稱為公鑰。

加密和解密密鑰不同的密碼學，前者不能用於推斷後者，稱為非對稱密碼學，而對稱密碼學是當這些密鑰相同或容易相互推斷時我們所擁有的。

愛麗絲向鮑勃發送她的公鑰，該公鑰只能用於加密只有她才能解密的東西（使用她的私鑰，她保密），相反，鮑勃向愛麗絲發送他的公鑰，它只能用於加密東西他一個人可以解密（通過他的私鑰，他也私下保存）。 但是，怎麼可能發布一個加密算法的參數，而不能從中推斷出精確的逆算法呢？

答案在於與編程最密切相關的數學領域，即計算複雜性理論。 任何深入研究數學問題的人都聽說過以一種方式很容易做到但反過來很難做到的變換。 例如，在微積分中，找到教科書的導數通常是一項簡單的練習，而進行逆運算（例如求解任何稍微不平凡的積分或教科書的物理 ODE 或 PDE）則需要一個更具調查性的過程，即首先假設函數族保證（或至少是合理的）包含解決方案並解決逆問題以從這些家庭中找到解決方案。

在 RSA 密碼系統中實際使用的一個示例是在不知道因子的情況下將大素數相乘與分解結果乘積。 做乘法是微不足道的，但因式分解需要你隨機^[2]猜測具有數百位數字的質因數。 該操作的一個重要特性是它需要很好地擴展。 在 RSA 中的素數大小上添加幾位數字將導緻密鑰需要數千倍的操作才能破解，同時會略微增加加密過程的複雜性。 非常粗略地說，質數的乘積用於加密，而質數對用於解密。

考慮到所有這些，讓我們來看看 SRVB 密碼系統是如何工作的。

底層算法 - 研究 SRVB

子集和問題

與任何其他公鑰密碼系統一樣，SRVB 依賴於解決易於產生的特定問題的難度。 在 SRVB 的情況下，它是子集和問題，可以描述如下：

給定整數 $w$ 和 $v_1，\cdot \cdot \cdot, v_N \in Z$ 求序列 $b_1, \cdot \cdot \cdot, b_N \in {0,1}$，使得 $ \sum_ {i = 1}^{N} v_i b_i = w $。

顯然，這個問題可以通過隨機選擇 N 個整數，隨機選擇其中的一個子集並將這個子集相加來產生 - 這是微不足道的。

蠻力搜索的複雜度為 $ O( N * 2^N ) $，計算 $b$s 的每個值組合。 Horowitz 和 Sahni 在 1972 年給出了一種更有效的方法，其複雜度為 $ O ( N * 2 ^ {N / 2} ) $。 如果我們將 $b$s 和 $w$ 替換為 $k$ 維的整數向量，問題至少同樣困難。 然而，要解決這個更困難的問題的領域也必須有一個帶環的同構，在該環中發生相同問題的更簡單版本，如下所示。 出於這個原因，SRVB 利用了高斯整數中的子集和問題，其中 $ k = 2 $。

有一種特殊情況，通過使用貪心算法可以很容易地計算這個問題。 如果我們對序列縮放因子 $ v_1, \cdot \cdot \cdot, v_N $ 排序，其中序列中的每個整數都大於它之前的所有整數的總和（$ \forall i , \sum_{j= 1}^{i-1} v_j < v_i $)，可以使用貪心方法在線性時間內找到序列b 。 具有上述性質的序列稱為超增序列。

下面簡單描述一下這種情況下的貪心解法：

1. 從當前觀察到的因子 $ i = N $ 和 $ w' = w $ 開始， $w$ 的其餘部分

2. 如果當前的縮放因子太大而無法適應 $w$ 的剩餘部分，即 $v_i > w'$，則設置 $b_i = 0$ 並繼續下一步。 否則我們知道縮放因子需要在序列中（因為其餘因子小於$v_i$）並且我們設置$b_i = 1$。

3. $ w' \Leftarrow w' - v_i * b_i$, $i \Leftarrow i - 1$。 如果$i > 0$，返回步驟2。

4. 現在驗證 $w' == 0$，否則問題已損壞

這是有效的，因為我們知道所有比當前觀察到的乘數更小的乘數不能像當前乘數那樣共同覆蓋盡可能多的（子）總和 $ w' $。 因此，如果剩餘的總和大於當前因子，我們肯定知道，如果沒有當前因子的幫助，所有後續因子加起來將無法相加。 另一方面，由於所有乘數都是正數，如果當前因子 $v_i $ 大於剩餘總和 $w'$，則添加任何其他因子會使結果超過 $w'$。

讓我們為文章的其餘部分設置一個符號。 我們選擇 $ v_1, \cdot \cdot \cdot, v_n $ 和 $w$ 作為超增序列的因子和和，而 $ u_1, \cdot \cdot \cdot, u_n $ 和 $y$ 將是公開的為恢復 $ b_1, \cdot \cdot \cdot, b_n $ 提供的可用參數。

使用序列 $ u_1, \cdot \cdot \cdot, u_n $ 選擇它不會超增，並且數字 $y$ 是公開可用的，公開提供的信息不足以恢復序列 $ b_1, \cdot \cdot \cdot , b_n $。 然而，如果有一個超增序列 $ v_1, \cdot \cdot \cdot, v_n $ 可以代替序列 $ u_1, \cdot \cdot \cdot, u_n $，則可以使用這個序列來解決問題一種貪婪的方法。

下面我們將展示它是如何工作的。

在以前的密碼系統中使用子集和

1978 年，Ralph Merkle 和 Martin Helman 設計了一種方法來利用這兩個背包範式和模運算的線性來建立上一節中描述的兩個序列之間的連接 - 從而構想了一個公鑰密碼系統。 這個想法是通過帶有秘密操作數的線性運算（模數）將簡單的背包（由整數的超增向量組成的）轉換為困難的（缺少此屬性的）。 轉換包括將每個 $v_i$ 乘以 $\theta$ 並將該乘積的其餘部分乘以 $\alpha$，其中 $\alpha \gt \sum_{i=1}^N v_i$ 和 $\gcd (\alpha, \theta) = 1$（兩個約束很快就會被證明是合理的）。 結果，序列 $u_1, \ldots, u_N$ 不再超增，可以認為是一個硬背包。

序列 $u_1、\ldots、u_N$ 的隨機排列將提供給想要加密並向我們發送消息的一方。 完成排列後，第三方很難猜出原始的超增序列是什麼。 消息的位塊用作係數$b_1、\ldots、b_N$。 加密是通過將密鑰序列與這個係數序列相乘來完成的，並將乘法相加成一個結果，我們將標記為 $y$。 只有私鑰的所有者才能將 $y$ 轉換為相應的 $w$，如果這些相同的 $b_1、\ldots、b_N$ 塊與簡單整數相乘（序列 $v_1、\ldots , v_N$)。 這是通過將 $y$ 乘以 $\theta^{-1}$ 來完成的，$\theta$ 模數 $\alpha$ 的乘法逆元（其存在取決於 $\gcd(\alpha, \ θ) = 1$)。 換句話說，$(\theta * \theta^{-1}) \bmod \alpha = 1$。 之後，我們計算 $w = (y * \theta^{-1}) \bmod a$。 這保證工作的原因是模數的線性，即餘數的線性組合等於線性組合的餘數。

如果我們連續應用 $u$ 的定義、商環和模算子的線性性質，我們會看到對應關係：

$ \begin{align} y & = \sum_{i=1}^N b_iu_i \newline & = \sum_{i=1}^N b_i (v_i * \theta \bmod \alpha) \newline & = \sum_{ i=1}^N b_i * v_i * \theta \bmod \alpha \newline & = \left[ \sum_{i=1}^N b_i * v_i * \theta \right] \bmod \alpha \newline & = \左[ \sum_{i=1}^N b_i * v_i \right] * \theta \bmod \alpha \newline & = w * \theta \bmod \alpha \end{align} $

因此，簡單的總和$w$ 可以通過將兩邊乘以 $\theta^{-1}$ 並用 $\alpha$ 取模來恢復。 為此，必須知道 $\alpha$ 和 $\theta$（這使得人們可以輕鬆計算 $\theta^{-1}$），它們將作為私鑰的一部分保密。

一個單一的約束 $\alpha \gt \sum_{i=1}^N v_i$ 是不合理的，這裡有一個解釋：第二行和第三行之間的相等性包括商的剩餘類之間的相等性模 $\alpha$ 的整數環。 換句話說，它只說明了其餘成員除以$\alpha$時是否相等，這不是成員本身相等的充分條件。 結果，可以將多個 $b$ 值的向量映射到單個 $y$，這是通過將最大可能子和（即所有地塊 $v_i$ 的總和）$w_{max}$ 限制為來防止的對於 $b$ 值的任何組合，都小於 $\alpha$。

就像日常生活中的任何其他實例一樣，完全了解所有假設通常是不可能的，也絕非易事。 因此，在判斷密碼系統是否可以安全使用時，我們必須依靠數學直覺，這無法為我們提供任何實際保證。 MH 密碼系統創建六年後，因 A. Shamir 的攻擊而被破解。 還有幾次嘗試重振MH，其中許多也失敗了。

Santana Rocha - Villas Boas (SRVB) 密碼系統

2016 年，在與本文作者就密碼系統的不同啟發^[3]可能性進行了幾次頭腦風暴後，Daniel Santana Rocha 有了用高斯整數替換 $\theta$ 和 $\alpha$ 的想法。 出於更多技術原因，這種方法會導致對上述 Shamir 攻擊的抵抗。

他還構思了一個由前面描述的硬背包線性組合的許多步驟組成的位塊。 在每一個中，一個新的（高斯）整數，等於一，高於所有先前的總和，將被添加到序列的末尾，而當前最小的將被丟棄。

一個不同但優雅相似的約束適用於 $\alpha$，它現在是一個高斯整數。 我們需要 $w_{max} \leq \vert\alpha\vert^2$。 原因很難形式化，但幸運的是，從優雅的描述中可以很容易地理解：

想像一個複數平面中的方格，其邊是直角三角形 a 和 b 的斜邊，平行於實軸和虛軸。 下面給出了這種格子的一個例子。 高斯整數模 $\alpha = a + bi$ 可以由位於這種格內的點表示。 在這樣的格子中有 $\vert\alpha\vert^2$ 個不同的點。 如果我們選擇一個足夠大的$\alpha$，我們可以擬合簡易背包的所有線性組合。

這是同構 $f 的圖形表示：Z/n \rightarrow Z[i]/(\alpha)$，其中 $n = 13$ 和 $\alpha = a + bi = 3 + 2i$（注意 $ n$ 和 $\alpha$ 確實滿足 $n = \vert \alpha \vert ^ 2 = a^2 + b^2 $ 的要求）。 點代表高斯整數，即復數$a + bi$，其中$a$ 和$b$ 是整數。 像往常一樣，橫軸代表實部，而縱軸代表虛部。 因此，向右或向左移動一個點相當於分別為其當前值添加 +1 或 -1。 同樣，向上或向下移動一個點分別對應於添加 +i 或 -i。

紅點是 $0 \bmod(\alpha)$ 的等價物。 除此之外，我們還為另外 4 對點著色。

同構 $f$ 由循環序列 $(0,1,2,\cdot\cdot\cdot,10,11,12,0,1,2,\cdot \cdot\cdot)$ 到圖中同樣循環的點序列的第 $i$ 個元素中，遵循以下規則：

1. 從第一行的紅點開始；
2. 它遵循水平右箭頭； 除了那個
3. 當跟隨箭頭將序列引出晶格時，它將到達非黑點之一。 它不是去那個點，而是跳到同一個正方形內的相同顏色的點（即模$\alpha$的等效點）； 最後
4. 當這個非黑點恰好是紅色時（發生在所有其他顏色都通過之後），序列跳到最上面的紅點，從而重新開始循環；

為了映射至少 $Y$ 個自然整數，必須取一個面積為 $\vert\alpha\vert^2$ 的正方形（其中 $\vert\alpha\vert = \sqrt{a^2 + b^2} $ 是，根據勾股定理，它的邊的度量）至少一樣高。

請注意，如果從上到下計算行數，則每次“跳轉”都會將行號 $r$ 更改為 $r \leftarrow (r + b)(mod a + b)$，並且等效地更改為 $r \leftarrow (r + a)(mod a + b)$ 如果從下往上計算。 因此，每行（和點）在每個循環中恰好漫遊一次的充分必要條件是跳躍的大小與行數互質，或者換句話說，$gcd(a,a + b) = gcd(b,a + b) = 1$。 由於最大公約數運算符的性質，這兩者都等價於 $gcd(a,b) = 1$。

YS Villas Boas 注意到 $a$ 和 $b$ 的互質性的必要性。 為了保持超增性，在序列末尾添加的每個新整數 $w$ 都需要超過所有當前整數的總和（$w > \sum_{i=1}^k v_i$）。 他觀察到，為了實現這一點，它們的乘法係數 $b_i$ 必須至少為 1，因此，每個位都不能映射到係數 0 和 1。如果係數是 0 和 1，則只有塊僅由 1 組成將滿足超增性。 因此，位 0 和 1 然後分別映射到乘法係數 1 和 2。

最後，更重要的是：在解碼的每一步中，要找到一個新整數 $v_1$ 作為方程 $b_1 v_1 = v_{n+1} - \sum_{i = 2}^{n} 的解b_i v_i$，其中所有 $v_i$ 和 $b_i$ 都是已知的 $1 < i \leq n$。 由於我們也不知道 $b_1$，因此我們最終得到了一個具有一個方程和兩個變量的系統，這給我們留下了一個自由度。 為了糾正這個問題，我們必須仲裁一個正值（為簡單起見，1）始終分配給 $b_1$，從而消除歧義。 因此，由於第一個係數固定為 1，為了在每一步編碼 $n$ 位，我們的整數序列必須是 $n + 1$ 個元素長。

最後一個要解決的技術問題是消息的字節大小不是塊大小的倍數的情況。 換句話說，如何處理最後一個數據塊可能剩餘的字節，以便一旦數據塊被恢復，原始內容的所有字節都被保留，但僅此而已？ 我們通過重複消息的最後一個字節一次來解決這個問題。 然後，該副本之後是一個隨機序列，其中每個組件只需要與前一個組件不同。 因此，當檢索數據塊時，它們中的最後一個，或者在最壞的情況下，在最後一個字節重複中截斷最後一個之前的那個。 ^[4]

現在讓我們展示一個 SRVB 密碼系統的例子。

我們從參數開始：

$k = 4$;

$m = 4$;

它產生$l = 4 * 4 = 16$的塊長度和$k + 1 = 5$自然整數的超增序列，它被操作——即線性組合，附加這個線性組合的結果，並且減少到最後的 $k + 1$ 個元素—$m = 4$ 次；

為簡單起見，令以下為 $v_i$ 的（超增）向量：

$(1,2,4,8,16)$

實際上，2 的前五個冪的序列，因為這是具有五個元素和最小的嚴格正可能值的超增序列（因此避免了公鑰中的 0，這會輕易地洩露對應的 0 對應的）。

正如我們之前所說，對於$\alpha = a + bi$，整數$a$ 和$b$ 必須互質，根據我們提到的新約束，我們必須要求$a^2 + b^2 = \vert\alpha\vert^2 \geq W$。 快速計算得出 $W = 1590$。 由於 $\sqrt{1590} \simeq 39.8$，一個非常方便的 $\alpha$ 可以被選擇為 $\alpha = 39 + 40i$，因為它剛好足夠容納一個帶有 at 的整數環的同構最少 1590 個組件，同時滿足 $gcd(a,b)=1$。 另外，我們需要選擇一個 $\theta$ 使得 $gcd(a,\theta)=1$ ^[5]並且最好不要太低，這樣 $(a_1 * \theta) \% \alpha \neq v_1 * \theta$, （也是為了避免洩露信息）。 $\theta = 60$ 完成這項工作，產生：

$-19-1i,1+38i,3-3i,6-6i,12-12i$ ^[6]

那就讓我們動手吧。 接受消息Hello Toptal! . 首先，我們根據 ASCII 和我們截斷數據塊的約定將其映射到一個字節數組中：

 01001000 01100101 01101100 01101100 01101111 00100000 01010100 01101111 01110000 01110100 01100001 01101100 00100001 00100001

由於我們的數據塊是 16 位 = 2 字節長，並且我們的消息有 13 個字符，所以我們最終得到 7 個數據塊，每個 2 字節，其中最後一個包含兩倍於字符“！”的位表示。 . 讓我們逐步加密第一個塊。 請密切注意，因為每個字節的位是按其重要性順序排列的。

$m=01001000 01100101$

• 第一個字節的第一個半字節：$(0,0,0,1)\rightarrow(1,1,1,1,2)\cdot(-19-1i,1+38i,3-3i,6-6i,12 -12i)=15+4i$
• 第一個字節的第二個半字節：$(0,0,1,0)\rightarrow(1,1,1,2,1)\cdot(1+38i,3-3i,6-6i,12-12i,15+ 4)=49+9i$
• 第二個字節的第一個半字節：$(0,1,0,0)\rightarrow(1,1,2,1,2)\cdot(3-3i,6-6i,12-12i,15+4i,49+ 9i)=106-10i$
• 第二個字節的第二個半字節：$(0,1,1,0)\rightarrow(1,1,2,2,1)\cdot(6-6i,12-12i,15+4i,49+9i,106- 10i)=252-2i$

因此，我們剛剛映射了

“他”$\Rightarrow(12-12i,15+4i,49+9i,106-10i,252-2i)$

其餘加密消息如下：

“ll”$\Rightarrow(12-12i,21-2i,61-3i,185-31i,367-59i)$

“o” $\Rightarrow(12-12i,25+33i,65+32​​i,111+44i,244+124i)$

“到”$\Rightarrow(12-12i,9+10i,46+12i,149+5i,277+31i)$

“點”$\右箭頭（12-12i,3+16i,46+12i,73+23i,201+49i）$

“人”$\Rightarrow(12-12i,4+54i,44+53i,117+193i,231+389i)$

“！！” $\右箭頭(12-12i,4+54i,32+65i,63+92i,121+247i)$

現在，對於解密，我們有 $\theta^{-1}=60^{-1}=27+i$：

$($“他” $\Rightarrow)$ $(12-12i,15+4i,49+9i,106-10i,252-2i)*\theta^{-1}\%\alpha=(16,47 ,93,223,527)$

現在，貪心算法來了：

首先，我們將每個貢獻因素減去乘以 1，因為已知它們至少貢獻了最後一次，得出：

• 第二個字節的第二個半字節：

$T \leftarrow (527-233-93-47-16) = 148$

$(T \geq 223) = (148 \geq 223) = 假 \Rightarrow b_1=0 ; T \leftarrow (T - 0 * 223) = 148$

$(T \geq 93) = (148 \geq 93) = 真 \Rightarrow b_2 = 1; T \leftarrow (T - 1 * 93) = 55$

$(T \geq 47) = 55 \geq 47) = 真 \Rightarrow b_3 = 1; T \leftarrow (T - 1 * 47) = 8$

$(T \geq 16) = 8 \geq 16) = 假 \Rightarrow b_4 = 0; T \leftarrow (T - 0 * 16) = 8$

結果：0110；

餘數：8（作為新的最低元素添加到序列的開頭）；

從當前序列的最後刪除 527；

• 第二個字節的第一個半字節：

$T \leftarrow (233-93-47-16-8) = 59$

$(T \geq 93) = (59 \geq 93) = 假 \Rightarrow b_1 = 0; T \leftarrow(T - 0 * 93) = 59$

$(T \geq 47) = (59 \geq 47) = true \Rightarrow b_2 = 1; T \leftarrow (T - 1 * 47) = 12$

$(T \geq 16) = (12 \geq 16) = 假 \Rightarrow b_3 = 0; T \leftarrow (T - 0 8 16) = 12$

$(T \geq 8) = (12 \geq 8) = true \Rightarrow b_4 = 1; T \leftarrow (T - 0 * 12) = 4$

結果：0101；

餘數：4（作為新的最低元素添加到序列的開頭）；

從當前序列的最後刪除 233；

• 第一個字節的第二個半字節：

$T \leftarrow (93 - 47 - 16 - 8 - 4) = 18$

$(T \geq 47) = (18 \geq 47) = 假 \Rightarrow b_1 = 0; T \leftarrow (T - 0 * 47) = 18$

$(T \geq 16) = (18 \geq 16) = true \Rightarrow b_2 = 1; T \leftarrow (T - 1 * 16) = 2$

$(T \geq 8) = (2 \geq 8) = 假 \Rightarrow b_3 = 0; T \leftarrow (T - 0 * 8) = 2$

$(T \geq 4) = (2 \geq 4) = 假 \Rightarrow b_4 = 0; T \leftarrow (T - 0 * 4) = 2$

結果：0100；

餘數：2（作為新的最低元素添加到序列的開頭）；

從當前序列的最後刪除 93；

• 第一個字節的第一個半字節：

$T \leftarrow (47-16-8-4-2) = 17$

$(T \geq 16) = (17 \geq 16) = true \Rightarrow b_1 = 1; T \leftarrow (T - 1 * 16) = 1$

$(T \geq 8) = (1 \geq 8) = 假 \Rightarrow b_2 = 0; T \leftarrow (T - 0 * 8) = 1$

$(T \geq 4) = (1 \geq 4) = 假 \Rightarrow b_3 = 0; T \leftarrow (T - 0 * 4) = 1$

$(T \geq 2) = (1 \geq 4) = 假 \Rightarrow b_4 = 0; T \leftarrow (T - 0 * 2) = 1$

結果：1000；

餘數：1（作為新的最低元素添加到序列的開頭）；

從當前序列的最後刪除 47；

結果，我們恢復了數據塊：“01001000 01100101”，其中包含我們消息的前兩個字符“He”。 不僅如此，我們還正確地檢索到了我們的私鑰超增序列$(1,2,4,8,16)$。

其他數據塊映射以相同的方式進行。

與主要公鑰密碼系統的比較

SRVB 是：

1. 完全免費和公開；

2. 比 ECC ^[7]更簡單、更容易理解和實施；

3. 密鑰豐富，因此幾乎沒有成本，例如 RSA，它依賴於昂貴的素數。

我們已經可以總結出最可能的漏洞。 由於 SRVB 源自 MH，因此很容易懷疑它容易受到 Shamir 攻擊的泛化或其他破壞它的攻擊。 儘管作者有理由相信情況並非如此，但尚未對其進行確認（這在處理密碼系統時非常典型）。

下一步是什麼？

Rocha 觀察到要使用的商環的一些概括，這可能會導緻密碼分析的複雜性增加。 我們還將研究這些可能性。

線性代數模糊

碰巧的是，在 SRVB 的開發和文檔編制過程中，Villas Boas 提出了另一種改進背包式公鑰密碼系統概念的方法，本文將不再詳細解釋，以免本文變得太長並且令人厭煩，但這裡只是略讀一下。 如果您沒有成功掌握它，請不要擔心，請繼續關注我們下一篇文章的發布，其中我們將更深入地探討細節：請參閱子集和 $y$，例如， $N$ 商環元素 $u_i$（同構對應於超遞增序列的正整數 $v_i$，如前所述）作為這些 $u_i$ 的行向量乘以列向量 $B$ (對於二進制）的零和一^[8] 。

$y = \sum_{i=1}^n u_i b_i = (u_1,\cdot\cdot\cdot,u_n)^T\cdot(b_1,\cdot\cdot\cdot,b_n)$=UB,

其中 $b_i \in {0,1}$

現在，想像一下，除了 $u_i$ 的向量，你在左邊有一個 $n$ x $N$（$n < N$）矩陣 V，它有 $v_i$（來自超增的整數序列）向量（不失一般性）它的第一行和所有其他條目都充滿了噪聲。 請注意，現在，將 V 乘以相同的位向量 B 會得到​​一個列向量 W，其中 $w$ 作為其第一個條目，而其他條目則為噪聲。 現在，取這個 V 矩陣並將其乘以左側的隨機^[9] n × n 矩陣 R，定義 n × N 矩陣 P：

P = 房車

這個想法是 Bob 使用 P 作為他的新公鑰。 由於 R 的隨機性，向量

$Y = PB = RV B = RW$

有信息 $w$ 被 V 的其他行中的噪聲所掩蓋。 Bob 也提前計算並存儲滿足以下條件的行向量 S：

$R^TS^T = e_1$

當 Alice 將 Y 發送給 Bob 時，他只是找到了 SY，因為：

$SY=S(PB)=S((RV)B)=SRVB= {e_1}^TR^{-1}((RV)B)=$

（到目前為止只有定義）

${e_1}^T (VB)={e_1}^TW = w$

（現在，利用關聯性來取消 Rs）

然後像以前一樣通過貪心算法從$w$中提取$b_i$的向量。

So, in one word, the Linear Algebraic Obscuring exploits the associativity of matricial multiplication (the fact that we could expand the terms and then operate their components in a new order provided we that preserved the sequence of all the operands in the sequence) to 'linearly' scramble and then filter (in the encryption and in the decryption respectively) noise to/from $w$. And in limit case $n = 1$, the system elegantly goes back to original to Rocha's approach.

The SRVB Campaign – a prize challenge

As explained before, in accordance to Kerckhoffs' principle, experience shows that antiquity of a publicly known unbroken cryptosystem is the main source of reliability of it, far more than any theoretical argumentation by the own authors, apart from anything else, because definitive proof of efficacy of the algorithms usually are not available.

And here it is our great chance to put these concepts to practice to earn a big money prize: Aware of this fact, we launched the aforementioned campaign, which is basically a crowdfunding for a prize automatically awarded to the first one that manages to break a message. The money is going to be converted to bitcoins in a given wallet whose private key will be SRVB encrypted and published so that anyone able to decipher it can simply take the money anonymously, no questions asked.

致謝

This article in particular and the whole SRVB Crypto project in general have been greatly helped by Prof. Charles F. de Barros, assistant professor at the Federal University of Sao Joao Del Rei. Prof. Barros provided us a technical review of the SRVB cryptosystem itself. I judged it necessary to submit to before daring to publish, and that I would certainly take much longer to do by myself.

In addition, I also would like to extend my deep gratitude to professor Adnan Ademovic for his extraordinarily insightful, attentive, and patient work as the editor of this article.

詞彙表

1. Cryptology/Cryptography: The science/practice of making a message nearly impossible to interpret without a specific set of instructions (in this context, the so-called "key"), thus allowing agents who share these instructions to communicate securely even if tapped by third parties;
2. Steganography: The science/practice of hiding a message within another by means of adding apparently innocuous modifications to the latter;
3. Key generation: the mapping of (expectedly) random inputs into (as random) valid keys;
4. Encryption/Encoding: The easily computable mapping of an easily interpretable message into another that is either hard or impossible to construe, by means of an (as randomly specified) element the one correspondent to the key of a (by Kerckhoffs' principle, publicly known and validated) family of algorithms;
5. Decryption/Decoding: The easily computable mapping that consists of the inverse of the previous, also being definable by an (as randomly specified, and therefore, unknown and hard to be guessed by third parties) element _again, the one correspondent to the key_ of a (by the same principle, usually known) family of algorithms, that thus outputs the original message when input with the encrypted one;
6. Cryptosystem: A triad of the family of encoding algorithms, the family of corresponding decrypting algorithms, and a key generating algorithm;
7. Allies: The agents with whom the communication is intended, and who are expected to act according to the protocol's rules;
8. Enemies/Third Parties: The agents with whom the communication is not intended, but try, nevertheless, to eavesdrop the communication and bypass the security enhanced by the cryptosystem;
9. Secure Channel: Any protocol (procedure) for communication that is easy to use while also effectively preventing third parties to feasibly construe what is meant by its users;
10. Insecure Channel: any channel (ie, protocol or procedure) that, as the name suggests, is not a secure channel;
11. Breaking a Key: The process of discovering a key by means of public pieces of information (like an encrypted message or public key) other than the key itself to be discovered and that was not expected to feasibly allow the discovery of the key. Since the information that results from this process grants the decryption of the messages, this is a particular case of…
12. Breaking/Deciphering a message: Any way to deduce the original content of an encrypted message only by means of the encrypted message itself and other pieces of information that were not expected to suffice for the deduction of the original content;
13. Breaking a Cryptosystem: Discovery of a systematic way to feasibly break whatever message is encrypted by this method under whatever parameter;
14. Kerckhoffs' Principle/Desideratum/Axiom/Law: A cryptologic principle named after the dutch cryptographer Auguste Kerckhoffs, according to which, in order for a cryptosystem to be deemed secure, everything about it except by its (private) keys must be of public knowledge;
15. Key: Secret parametrization of a cryptosystem allowing it to be infeasible to be guessed (and consequently broken) by third parties while also being validated by the community of cryptanalysts (in accordance to Kerckhoffs' principle);
16. Symmetric Cryptosystem: Any cryptosystem on which any parameter for the encoding suffices for easily deducing the parameter for decoding, and, for this reason, must be kept private. One can rephrase it by saying that the encryption and decryption parameters are both equivalent to the key;
17. Asymmetric/Public Key Cryptosystem: Any cryptosystem for which there is a way to express the parameters for the encoding that does not suffice to feasibly deduce the correspondent parameter for decoding, allowing it to be sent to allies through an insecure channel, or even made public, and thus creating a secure channel where there was none;
18. Public Key: A component of an asymmetric cryptosystem that suffices for parameterizing the encryption but does not suffice for feasibly deducing the decryption parameter, ie, the…
19. Private Key: A component of an asymmetric cryptosystem that suffices for parameterizing the decryption and thus must be kept privately and usually also suffices for parameterizing the encryption;

^[1] Note that, here, the phrases decipher or decrypt do not apply, because before a given cryptosystem (with all its components, including its keys) is well defined, one cannot classify a given method of construing the original message from the encrypted one as the intended communication (decryption) or an attack (deciphering).

^[2] Though there are techniques to improve this guessing work, it still remains far more difficult discovering than multiplying them.

^[3] The first inspiration was to look at the tree of the tau conjecture, an infinite tree rooted in the number 1, whose other nodes consist of integers resulting in one binary operation of sum, subtraction, or multiplication between previous nodes, possibly one node operated with itself. The theory's goal relates to the depth, in this tree, in which each integer first appears. It is apparently hard to find large numbers in low branches (even if we relax the need for it), but is it immediate to check if a given sequence of operations indeed produces a given result.

^[4] This is surely not the most natural approach, but by adopting this, one ensures that this byte filling (called padding)…

1. Conceals the size of the padding (differently, for example of ciphertext stealing) and obscures the end of the message, thus rendering chosen-plaintext attacks more difficult;
2. Enhances a distribution of bits as close to uniform as possible;

If the last blocks of every message were known to be systematically biased in a far from uniform distribution, an attacker could exploit this fact to do a statistical cryptanalysis, for any given sample of messages would be statistically more representative than otherwise. In other words, the last blocks being statistically less diverse, they become they become the weakest links of the message.

^[5] Make no mistake: this greatest common divisor is Gaussian, while the previous is real.

^[6] …which is not perfect, because it easily gives away the fact that the last three components are proportional to 1, 2, and 4. But, again, for the sake of simplicity, we will ignore this detail.

^[7] …which is so complex that there are a few notorious cases of failure to implement and maintain protocols based on it.

^[8] Here, we will not adopt Rocha's approach of a multiple linear combinations block, which also allows us to randomly permute the bis to obscure them even more.

^[9] Though not totally random. Its transpose must span the subspace generated by the vector $ e_1 = (1,0,…,0) $.