SRVB密码系统入门

本文概述

介绍
什么是密码系统？
底层算法-研究SRVB
Santana Rocha-Villas Boas(SRVB)密码系统
与主要公钥密码系统的比较
下一步是什么？
SRVB运动–挑战奖
致谢

介绍

信息安全是一个引人入胜的知识领域, 涉及从理论计算机科学到软件工程的所有内容, 甚至涉及人为错误的心理学。

密码学现在是我们日常生活中众多匿名技术英雄之一。社交网络, 网络银行, 军事情报以及处理敏感信息的任何其他信息系统都严重依赖加密。密码术使我们拥有隐私权, 有人认为这是第十二项人权。

本文将向你介绍公共密钥密码系统背后的原理, 并向你介绍由本文作者和Daniel Santana Rocha教授开发的密码系统Santana Rocha-Villas Boas(SRVB)。在撰写本文时, 算法作者正在酝酿一项活动, 其中包括对设法破解代码的任何人的经济奖励。由于本文将详细介绍算法功能, 因此这是开始寻求奖励的最佳位置。有关更多信息, 请参见SRVB网站。

什么是密码系统？

密码学是任何妨碍消息可解释性的方法, 只要提供了特定的指令(通常称为”密钥”), 它仍然允许一种可行的方式来解释消息。尽管这是一个非常广泛的定义, 甚至包括最早的技术, 但值得一提的是, 这并未涵盖信息安全的所有内容。

预计加密方法和破解方法之间的技术竞赛永远不会获得最终的胜利。预计新一代将提高信息安全和密码分析的标准, 这是系统地解密/破坏加密消息(即绕过安全性或加密)的一组技术。

为了使密码系统(给定的密码技术)被其用户视为安全的, 它必须获得国际专家团体的认可, 因此是众所周知的, 这被称为Kerckhoffs原理。但是, 这种情况使该系统受到了世界密码分析界的审查, 后者将尝试设计系统地破坏加密的方法。

如何使给定的加密过程足够机密, 只有预期的代理才能解密它, 同时又要足够公开, 以使全世界的密码分析社区可以证明其鲁棒性？答案是构成密码学关键要素的一个要素：钥匙。密码系统的密钥是用于加密或解密算法或两者的参数。通过将参数保密而不是算法系列保密, 可以实现两个矛盾的要求。只要参数族足够大(可能是无限的)并且可以证明其每个组成部分都具有适当的属性, 攻击者仅通过检查即可确定参数是不可行的。

最后, 为了使密钥有效地工作, 必须易于制造但几乎无法猜测。凭借当今计算机的计算能力, 计算机解密人为生成的密钥所需的时间比任何人甚至想象不到的时间还要长, 而且无论如何以这种方式生成密钥并不划算。因此, 密钥倾向于由算法生成。

由于通常的使用, 密钥生成算法不得创建可预测/可再现的输出。由于算法执行的过程没有任何智能过程, 因此问题就变成了如何做到这一点。答案是将密钥生成算法转换为映射, 从而将大量真正随机的位转换为密钥。可以从操作系统中获取真正的随机位, 这是由宇宙中的不确定性生成的。根据应用程序的不同, 某些来源可能是鼠标移动, 网络程序包延迟甚至是专用硬件。

公钥密码系统

准备再次感到惊讶, 因为我们现在将引入一个似乎与我们刚才所说的相矛盾的概念：公钥。

到目前为止, 我们已经看到在安全地交换了秘密参数(密钥)之后创建了安全通信, 但是仍然存在通过公共信道交换参数的问题。现在, 我们将介绍一个解决稍微更明显的问题的概念：创建安全通道。

假设爱丽丝(Alice)与鲍勃(Bob)合作, 并且他们想使用加密来保持工作交互的安全性。他们可以通过互相给对方一个USB闪存盘(上面带有密钥)来见面并交换其加密密钥。但是, 如果爱丽丝和鲍勃位于不同的大陆, 该怎么办？如何建立不存在的安全通道？

通过电子邮件发送密钥不是一种选择, 因为其竞争对手夏娃可以拦截交易并随后使用密钥读取所有加密数据。如果他们有任何其他数字通道可以通过其传输此敏感数据, 则首先不需要加密, 因此不需要密钥。通过物理邮件发送密钥仍然可能被拦截, 因为它首先需要交换敏感信息。通过隐藏在其他数据中来发送密写密钥很聪明, 但是除非发送者确定接收者(以及单独的接收者)知道这种消息的存在并知道如何提取它, 否则它是无用的。碰巧的是, 意识到消息的存在以及如何从数据中提取密钥的描述本身就是密钥的一种, 这使我们回到了平方。

解决方案是设计一种加密系统, 其加密参数不足以合理地构造原始消息[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})$。如果我们用整数的$ k $维向量替换$ b $ s和$ w $, 问题至少同样困难。但是, 要解决这个更困难的问题的领域也必须具有带环的同构, 在同一个环上会发生相同问题的更简单的版本, 如下所示。因此, SRVB利用$ k = 2 $的高斯整数内的子集和问题。

在特殊情况下, 通过使用贪心算法可以轻松解决此问题。如果我们对序列比例因子$ v_1, \ cdot \ cdot \ cdot, v_N $进行排序, 其中序列中的每个整数都大于它之前的所有整数的总和($ \ forall i, \ sum_ {j = 1} ^ {i-1} v_j <v_i $), 可以使用贪婪方法在线性时间中找到序列b。具有所描述属性的序列称为超增序列。

这是这种情况下贪婪解决方案的简单描述：

从$ i = N $(当前观察到的因子)开始, 以及$ w’= w $($ w $的余数)开始
如果当前缩放因子太大而无法容纳$ w $的剩余部分, 即$ v_i> w’$, 则设置$ b_i = 0 $并继续下一步。否则, 我们知道比例因子必须在序列中(因为其余因子小于$ v_i $), 并且我们将$ b_i设置为1 $。
$ w’\ Leftarrow w’-v_i * b_i $, $ i \ Leftarrow i-1 $。如果$ i> 0 $, 请返回步骤2。
验证现在$ w’== 0 $, 否则问题已损坏

之所以起作用, 是因为我们知道, 所有小于当前观察值的乘子都不能像当前乘数一样累加全部(子)和。因此, 如果剩余总和大于当前因数, 我们可以肯定地知道, 在没有当前因数的帮助下, 以下所有因数加起来将无法求和。另一方面, 由于所有乘数都是正数, 因此, 如果当前因子$ 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, \ theta)= 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 \换行＆= \左[\ sum_ {i = 1} ^ N b_i * v_i * \ theta \右] \ bmod \ alpha \换行＆= \左[\ sum_ {i = 1} ^ N b_i * v_i \右] * \ theta \ bmod \ alpha \换行符＆= w * \ theta \ bmod \ alpha \ end {align} $

因此, 可以通过将两边都乘以$ \ theta ^ {-1} $并取模数乘以\\ alpha $来恢复简单和$ w $。为此, 必须同时知道$ \ 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 $的想法。由于更多的技术原因, 这种方法导致了对前述沙米尔袭击的抵抗。

他还构思了一个位块, 该位块由硬背包的上述线性组合的许多步骤组成。在它们的每一个中, 将在序列的末尾添加一个新的(高斯)整数(等于一个整数), 该整数比所有先前的整数之和高, 而当前的最小整数将被丢弃。

$ \ 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对点上色。

颜色	等效于…modα
橙子	$1$
绿色	$ i $
蓝色	$ -1-i $
紫色	$ 1-i $

同构$ f $由循环序列$($, 0, 1, 2, \ cdot \ cdot \ cdot, 10, 11, 12, 0, 1, 2, \ cdot的$ i $ th元素的转换定义\ cdot \ cdot)$放入图中的点的循环第$ i $ th个元素, 该元素遵循以下规则：

它从第一行的红点开始；
它遵循水平的向右箭头；除了那个
当遵循箭头将序列引向晶格外部时, 它将到达非黑点之一。它没有跳到该点, 而是跳到了同一正方形内的相同有色点(即, 等价点以\\ alpha $为模)；最后
当该非黑点恰好是红色(在所有其他颜色都通过后发生)时, 序列跳到最上面的红点, 从而重新开始循环；

为了映射至少$ 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 $。

Y. S. Villas Boas注意到需要$ a $和$ b $的共素性。为了保持超增量, 在序列末尾添加的每个新整数$ w $必须超过所有当前整数的和($ w> \ sum_ {i = 1} ^ k v_i $)。他观察到, 要实现这一点, 它们的乘法系数$ b_i $必须至少为1, 因此, 每个位都不能映射到系数0和1。如果系数是0和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 $ elements _- $ 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 srcmini!。首先, 我们根据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 + 32i, 111 + 44i, 244 + 124i)$

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

” pt” $ \ Rightarrow(12-12i, 3 + 16i, 46 + 12i, 73 + 23i, 201 + 49i)$

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

” ！！” $ \ Rightarrow(12-12i, 4 + 54i, 32 + 65i, 63 + 92i, 121 + 247i)$

现在, 对于解密, 我们有$ \ theta ^ {-1} = 60 ^ {-1} = 27 + i $：

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

现在, 出现贪婪算法：

首先, 我们减去每个贡献因子乘以一个, 因为已知它们至少对最后一个贡献了一次, 得出：

第二个字节的第二个半字节：

$ 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)= true \ Rightarrow b_2 = 1; T \ leftarrow(T-1 * 93)= 55 $

$(T \ geq 47)= 55 \ geq 47)= true \ 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；

结果, 我们恢复了包含消息前两个字符” He”的数据块” 01001000 01100101″。不仅如此, 我们还正确检索了私钥超增序列$(1, 2, 4, 8, 16)$。

其他数据块映射以相同的方式进行。

与主要公钥密码系统的比较

SRVB是：

完全免费和公开；
比ECC [7]更简单, 更容易理解和实施。
相对于依赖于质数的RSA, RSA上的密钥数量丰富, 因此实际上是无成本的, 而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矩阵, 并将其与左边的n个矩阵R乘以random [9] n, 定义n乘N矩阵P：

P =右室

这个想法是鲍勃使用P作为他的新公钥。由于R的随机性, 向量

$ Y = PB = RV B = RW $

V的其他行中的噪声掩盖了$ w $的信息。Bob还预先计算并存储满足以下条件的行向量S：

$ R ^ T S ^ T = e_1 $

当Alice将Y发送给Bob时, 他只是找到SY, 因为：

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

(到目前为止仅定义)

$ {e_1} ^ T(V B)= {e_1} ^ T W = w $

(现在, 利用关联性取消Rs)

然后像以前一样继续通过贪心算法从$ w $中提取$ b_i $的向量。

因此, 总之, 线性代数模糊化利用矩阵乘法的关联性(只要我们保留了序列中所有操作数的序列, 我们就可以扩展这些项, 然后以新的顺序操作它们的成分这一事实)线性地加扰然后过滤(分别在加密和解密中)到/从$ w $的噪声。在$ n = 1 $的极限情况下, 系统可以优雅地恢复到Rocha的方法。

SRVB运动–挑战奖

如前所述, 根据Kerckhoffs的原理, 经验表明, 公知的不间断密码系统的上古性是其可靠性的主要来源, 远远超出了其本人的任何理论论证, 除了其他方面外, 因为权威的证明该算法的功效通常不可用。

这是我们将这些概念付诸实践以赚取巨额奖金的绝佳机会：意识到这一事实, 我们发起了上述活动, 这基本上是一次众筹, 目的是将奖金自动奖励给第一个成功打破奖项的人。信息。这笔钱将被转换成给定钱包中的比特币, 其私钥将通过SRVB加密并发布, 这样任何能够解密它的人都可以匿名拿走钱, 而不会提出任何疑问。

致谢

SãoJoãoDel Rei联邦大学的助理教授Charles F. de Barros教授特别对本文以及整个SRVB Crypto项目提供了极大帮助。 Barros教授为我们提供了SRVB密码系统本身的技术综述。我认为有必要在敢于发表之前先提交, 而且我自己做的时间肯定会更长。

另外, 我还要感谢阿德南·阿德莫维奇教授(Adnan Ademovic)作为本文的编辑, 他的独到见解, 专心和耐心地工作。

词汇表

密码学/密码学：一种科学/实践, 如果没有一组特定的指令(在这种情况下, 即所谓的”密钥”), 几乎不可能解释一条消息, 从而使共享这些指令的代理即使被窃听也可以安全地进行通信。第三方；
隐秘术：通过对消息添加明显无害的修改将消息隐藏在另一个消息中的科学/实践；
密钥生成：将(预期)随机输入映射为(作为随机)有效密钥；
加密/编码：通过一个(随机指定的)元素将一个易于解释的消息轻松地计算为难以解释或无法解释的另一个消息, 该消息对应于(根据Kerckhoffs原理)的密钥并经过验证)算法系列；
解密/解码：一种易于计算的映射, 由前一个的倒数组成, 也可以由(再次随机指定, 因此未知且很难被第三方猜测)元素_再次定义, 该元素对应于key_的一类算法(通常是相同的原理), 因此在使用加密算法输入时输出原始消息；
密码系统：编码算法家族, 相应的解密算法家族和密钥生成算法的三元组；
盟友：与之进行通讯的代理, 并应根据协议的规则行事；
敌人/第三方：并非旨在与之通信的代理, 但仍试图窃听通信并绕过加密系统增强的安全性；
安全通道：任何易于使用的通信协议(程序), 同时还可以有效防止第三方切实解释其用户的含义；
不安全通道：顾名思义, 不是安全通道的任何通道(即协议或过程)；
破坏密钥：通过公共信息(例如加密消息或公共密钥)发现密钥的过程, 而不是要发现的密钥本身, 并且该过程不可能允许发现密钥。由于此过程中产生的信息允许对消息进行解密, 因此这是……的一种特殊情况。
破坏/破译消息：仅通过加密消息本身和其他不希望用来推断原始内容的信息来推断加密消息的原始内容的任何方法；
破解密码系统：发现一种系统的方法来可行地破解由该方法在任何参数下加密的任何消息；
Kerckhoffs的Principle / Desideratum / Axiom / Law：以荷兰密码学家Auguste Kerckhoffs的名字命名的密码原理, 根据该原理, 为了使密码系统被认为是安全的, 除其(私钥)外, 所有与之相关的事物都必须是公众知识;
密钥：密码系统的秘密参数化, 使其无法被第三方猜测(并因此而被破坏), 同时还必须由密码分析师团体进行验证(根据Kerckhoffs的原理)；
对称密码系统：在该密码系统上, 用于编码的任何参数都足以轻松推断要解码的参数, 因此, 必须保持私有。可以这样说, 加密和解密参数都等同于密钥。
非对称/公共密钥密码系统：任何一种密码系统中无法表达编码参数的方法, 都无法切实推断出相应的解码参数, 从而无法通过不安全的渠道将其发送给盟友, 甚至公开发布, 从而在没有安全通道的地方创建安全通道；
公钥：非对称密码系统的一个组成部分, 足以对加密进行参数化, 但不足以可行地推导出解密参数, 即…
私钥：非对称密码系统的一个组成部分, 足以对解密进行参数化, 因此必须保密, 通常也足以对加密进行参数化；

[1]请注意, 此处的短语”解密”或”解密”不适用, 因为在对给定的密码系统(包括其所有组件, 包括其密钥)进行良好定义之前, 无法对从加密后的原始消息进行解释的给定方法进行分类。一种作为预期的通信(解密)或攻击(解密)。

[2]尽管有一些技术可以改善这一猜测工作, 但是发现它仍然比相乘要困难得多。

[3]最初的灵感是看tau猜想的树, 这是一个以数字1为根的无限树, 其其他节点由整数组成, 从而导致先前节点之间加, 减或乘的二元运算(可能是一个)节点自行运行。该理论的目标与该树的深度有关, 其中每个整数首先出现在其中。显然很难在低级分支中找到大量数字(即使我们放松了对它的需求), 但是立即检查给定的操作序列是否确实产生了给定的结果。

[4]当然, 这不是最自然的方法, 但是通过采用这种方法, 可以确保此字节填充(称为填充)…

隐藏填充的大小(例如, 不同的密文窃取)并掩盖消息的结尾, 从而使选择明文攻击更加困难；
增强位的分布, 使其尽可能接近均匀；

如果已知每个消息的最后一个块在远非均匀分布的情况下被系统地偏置, 那么攻击者可以利用这一事实进行统计密码分析, 因为任何给定的消息样本在统计上都比其他情况更具代表性。换句话说, 最后一个块在统计上不那么多样化, 它们变成了消息的最弱链接。

[5]没错：这个最大的公约数是高斯, 前一个是实数。

[6]…这不是完美的, 因为它很容易忽略以下事实：最后三个分量与1、2和4成正比。但是, 再次为简单起见, 我们将忽略此细节。

[7]…太复杂了, 以至于有一些臭名昭著的案例, 使基于该协议的协议无法实现和维护。

[8]在这里, 我们不会采用Rocha的多重线性组合块的方法, 这也使我们可以随机地对bis进行置换以使它们更加模糊。

[9]虽然并非完全随机。它的转置必须跨越向量$ e_1 =(1, 0, …, 0)$生成的子空间。

本文概述

介绍