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) $.