信息安全是一个引人入胜的知识领域，可以涉及从理论计算机科学到软件工程的任何内容, 甚至观察人类犯错的心理.
密码学现在是我们日常生活中众多匿名技术英雄之一. 社交网络, 网络银行, 军事情报, 任何其他处理敏感信息的信息系统都严重依赖于密码学. 密码学让我们拥有隐私，有些人认为 第十二项人权.
本文将向您介绍公钥密码系统背后的原理，并向您介绍 桑塔纳罗查-维拉斯博阿斯(SRVB)这是一种由这篇文章的作者和教授共同开发的密码系统. 丹尼尔·桑塔纳·罗查. 在撰写本文时, 该算法的作者正在策划一场活动，其中包括向任何设法破解密码的人提供经济奖励. 由于本文将涵盖 算法的功能 详细地说，这是开始追求奖项的最佳地点. 更多信息可在 SRVB网站.
密码学是妨碍消息可解释性的任何方法, 同时，只要提供了特定的指令，就仍然允许一种可行的解释方法, 通常所谓的“关键”是什么.“虽然这是一个非常广泛的定义，甚至包括最早的技术, 值得一提的是，这并没有涵盖信息安全的所有内容.
加密方法和破解方法之间的技术竞赛预计永远不会有最终的赢家. 预计每一代新技术都将提高信息安全和密码分析的标准, 哪一套技术可以系统地破译/破解加密信息, i.e.，绕过安全或加密.
为了使用户认为密码系统(给定的密码技术)是安全的, 它必须得到国际专家团体的认可, 从而为公众所知, 这被称为 Kerckhoffs”原则. 然而,, 这种情况使该系统暴露在世界密码分析社区的审查之下, 谁会尝试设计系统地破解加密的方法.
如何使给定的加密过程足够机密，只有预期的代理才能解密它, 同时又足够公开，世界上的密码分析社区可以证明它的稳健性? 答案是一个组件，它是密码学的一个关键元素:密钥. 密码系统的密钥是加密或解密算法或两者的参数. 通过对参数保密, 而不是算法族, 这两种矛盾的要求都可以实现. 前提是参数族足够大(可能是无限的)，并且它的每一个分量都能被证明有足够的性质, 攻击者仅仅通过检查来确定参数是不可行的.
最后, 为了让钥匙有效地工作, 它必须很容易产生，但几乎不可能猜测. 以当今计算机的计算能力, 计算机破译人类生成的密钥所需的时间比任何人想象的都要少, 最重要的是，以这种方式生成密钥并不划算. 正因为如此，密钥往往是由算法生成的.
密钥生成算法不能作为典型使用的结果创建可预测/可重复的输出. 因为算法执行的过程没有任何智能过程, 问题是如何做到这一点. 答案是将密钥生成算法转化为映射，将大量真正随机的比特转换为密钥. 真正的随机比特可以从操作系统中获得, 从宇宙的不确定性中产生它们. 一些来源是你的鼠标移动, 网络包延迟, 甚至是专用硬件, 取决于应用程序.
准备好再次被惊喜吧, 因为我们现在将引入一个似乎与我们刚刚所说的相矛盾的概念:公钥.
到目前为止, 我们已经看到了在安全地交换了秘密参数(密钥)之后安全通信的创建, 但是在公共通道上交换参数的问题仍然存在. 现在, 我们将介绍一个解决稍微明显一些的问题的概念:创建安全通道.
假设Alice和Bob一起工作, 他们希望通过加密来保证工作交互的安全. 他们可以通过给对方一个装有密钥的USB闪存盘来见面并交换加密密钥. 但是如果爱丽丝和鲍勃位于不同的大洲呢. 如何在没有安全通道的情况下建立安全通道?
通过电子邮件发送钥匙是不可能的, 因为他们的竞争对手Eve可以拦截交换并使用他们的密钥读取所有加密数据. 如果他们有其他的数字渠道来传输这些敏感数据, 这样就不需要加密了, 因此是键, 首先. 通过实体邮件发送密钥也可能被截获, 因为它首先需要交换敏感信息. 发送一个 通过隐藏在其他数据中的隐写密钥 很聪明, 但除非寄件人确定收件人, 而接受者本身, 是否知道这样一条信息的存在并知道如何提取它. 碰巧的是, 对消息存在的感知以及如何从数据中提取密钥的描述本身就是一种密钥, 这又让我们回到原点了.
解决方案是设计一个加密参数不足以可行地解释原始消息的密码系统[1]，并保留允许解释该消息的参数. 我们称该参数为私钥. 基于私钥, 可以为加密工具生成一组参数，而不必使这些新参数本身能够显示私钥是什么. 这组参数可以公开共享, 因为谁能加密东西并不重要, 只要只有一个人能解密. 由于加密工具的这组参数可以公开，因此称为公钥.
加密和解密密钥不同的密码学, 而用前者来推导后者是不可行的, 叫做非对称密码学, 而对称密码学是指那些密钥相同的情况, 或者很容易从彼此中推断出来.
Alice把她的公钥发给Bob, 它只能用于加密只有她才能解密的东西(用她的私钥), 她的秘密)和, 相反, 鲍勃把他的公钥发给爱丽丝, 它只能用于加密他自己可以解密的东西(通过他的私钥), 这也是他私下保存的。). 但是，怎么可能发布一个加密算法的参数，而不能从中推导出确切的逆算法呢?
答案就在与编程关系最密切的数学领域——数学 计算复杂性理论. 任何深入研究数学问题的人都听说过变换在某种程度上很容易做到, 但反过来很难. 在微积分, 例如, 找到教科书上的导数通常是一个简单的练习, 在做逆运算的时候(比如解一些不平凡的积分或者课本上的物理运算) 颂歌 or PDE, 例如，需要一个更深入的研究过程，首先假设保证(或至少似是而非)包含解的函数族，并求解逆问题以从这些族中找到解.
中实际使用的例子 RSA密码系统 是把大质数相乘还是在不知道因数的情况下把结果分解. 做乘法很简单，但因式分解需要随机进行[2] 猜猜质因数是多少，质因数有几百位. 该操作的一个重要特性是需要良好的可伸缩性. 在RSA中质数的大小上增加几个数字，就会产生一个需要数千倍的操作才能破解的密钥，而加密过程的复杂性也会略有增加. 粗略地说, 素数的乘积用于加密, 而这对素数因子则用于解密.
了解了所有这些之后，让我们来看看SRVB密码系统是如何工作的.
像任何其他公钥密码系统一样, SRVB依赖于解决一个容易产生的特定问题的难度. 在SRVB的例子中，它是 子集和问题，可描述如下:
给定整数w和v_1, \cdot \cdot \cdot \cdot, v_N \in Z$找到序列$b_1, \cdot \cdot \cdot \cdot, b_N \in {0,1}$, 使得$ \sum_{i = 1}^{N} v_i b_i = w $.
很明显, 这个问题可以通过随机选择N个整数来解决, 随机选择其中的一个子集然后把这个子集加起来，这很简单.
蛮力搜索的复杂度为0 (N * 2^N), 计算$b$s值的每个组合. 提出了一种更有效的方法 霍洛维茨和萨尼在1972年，复杂度为$ O (N * 2 ^ {N / 2}) $. 如果我们用k维的整数向量替换b s和w，这个问题至少是一样难的. 然而，这个更困难的问题所在的领域也必须有一个 同构 与一个 环 我们将在下面看到，同一个问题的一个更简单的版本发生在哪里. 出于这个原因，SRVB利用了内部的子集和问题 高斯整数，其中k = 2.
有一种特殊的情况，这个问题很容易通过使用贪婪算法来计算. 如果我们对序列排序，缩放因子$ v_1, \cdot \cdot \cdot \cdot, v_N $，其中序列中的每个整数都大于它之前的所有整数的和($ \forall i , \sum_{j=1}^{i-1} v_j < v_i $), 我们可以使用贪心方法来查找序列 b 在线性时间内. 具有所描述属性的序列称为 superincreasing序列.
下面是这种情况下贪心解的简单描述:
从$ i = N $(当前观察到的因子)和$w ' = w$ ($w$的剩余部分)开始
如果当前的比例因子太大，无法容纳剩下的$w$, meaning $ v_i > w’$, 设置$b_i = 0$，继续下一步. 否则，我们知道缩放因子需要在序列中(因为其余因子小于$v_i$)，并且我们设置$b_i = 1$.
$ w ' \左列w ' - v_i * b_i$， $i \左列i - 1$. If $i > 0$, return to step 2.
现在验证$w ' == 0$，否则问题已损坏
这是有效的，因为我们知道所有小于当前观察到的乘数都不能像当前乘数那样覆盖(子)和$ w ' $. 如果剩余的和大于当前因子, 我们肯定地知道，如果没有当前因素的帮助，以下所有因素加在一起将无法总结它. 另一方面, 因为所有乘数都是正的, 如果当前因子$ v_i $大于剩余的总和$ w ' $, 加上任何其他因素都会使结果超过$ w ' $.
让我们为本文的其余部分设置一个符号. 我们选择$ v_1, \cdot \cdot \cdot \cdot, V_n $和$w$作为超增长序列的因子和和, $ u_1, \cdot \cdot \cdot \cdot, U_n $和$y$将是提供用于恢复$ b_1的公开可用参数, \cdot \cdot \cdot \cdot, b_n美元.
序列$ u_1, \cdot \cdot \cdot \cdot, 选择U_n $，所以它不是超增长的, 数字y是公开的, 没有公开提供足够的信息来恢复序列$ b_1, \cdot \cdot \cdot \cdot, b_n美元. 然而, 如果有一个超递增序列$ v_1, \cdot \cdot \cdot \cdot, V_n $可以代替序列$ u_1, \cdot \cdot \cdot \cdot, u_n美元, 我们可以使用这个序列用贪心方法来解决这个问题.
下面我们将展示它是如何工作的.
In 1978年，拉尔夫·默克尔和马丁·赫尔曼设计了一种方法来利用这两个背包范式和 线性 在前一节中描述的两个序列之间建立连接——从而构思一个公钥密码系统. 这个想法是为了改变 简单的背包 通过带秘密操作数的线性运算(模数)，(由整数的超增长向量组成的)变成硬向量(缺乏这种性质的向量). 这个变换包括将每个$v_i$乘以$\theta$并将这个乘积的余数乘以$\alpha$, 其中$\alpha \gt \sum_{i=1}^N v_i$和$\gcd(\alpha, \theta) = 1$(这两个约束将很快得到证明). 结果，序列$u_1， \ ldots, u_N$不再是超递增的，并且可以认为是a 艰难的背包.
序列$u_1的随机排列, \ ldots, u_N$将给予想要加密并向我们发送消息的一方. 这样做是为了让第三方更难猜测原始的超增长序列是什么. 消息的位块用作系数$b_1， \ ldots, b_N$. 加密是通过将密钥序列与这个系数序列相乘来完成的, 然后把相乘的结果加起来, 我们把它标记为y. 只有私钥的所有者可以将$y$转换为对应的$w$，如果这些相同的$b_1，将获得$w$, \ ldots, b_N$块将与 简单的整数 (序列$v_1， \ ldots, v_N$). 这是通过y乘以$\ ^{-1}来实现的 乘法逆元 $\theta$模$\alpha$(它的存在依赖于$\gcd(\alpha)的条件, \theta) = 1$). 换句话说，$(\theta * \theta^{-1}) \bmod \alpha = 1$. 之后，我们计算$w = (y * \theta^{-1}) \bmod a$. 这保证有效的原因是 模的线性, i.e.,这 余数的线性组合等于这个线性组合的余数.
如果我们连续应用u的定义, 商环, 以及模算子的线性性质, 我们看到了对应关系:
$ 开始\{对齐} 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 & = \left[\sum_{i=1}^N b_i * v_i \right] * \theta \bmod \alpha \newline & = w * \theta \bmod \alpha 结束\{对齐} $
因此 简单的总和 $w$可以通过两边乘以$\theta^{-1}$并取$\alpha$的模量来恢复. 这样做, 我们必须知道$\alpha$和$\theta$(这样就可以很容易地计算$\theta^{-1}$), 作为私钥的一部分，哪些是要保密的.
一个约束条件, $\alpha \gt \sum_{i=1}^N v_i$, 这是对它的解释:第二行和第三行之间的相等是由两行之间的相等组成的 渣类 的 商环 对$\alpha$取模的整数. 换句话说, 它只表示当除以$\alpha$时其余成员的相等性, 哪个不是成员本身相等的充分条件. 结果是, 包含$b$值的多个向量可以映射到单个$y$, 这可以通过限制最大可能子和(i.e. 对于任意$b$值的组合，所有包裹$v_i$) $w_{max}$的总和小于$\alpha$.
就像日常生活中的其他例子一样, 完全了解所有假设往往是不可能的，也从来不容易. 结果是, 在判断一个密码系统是否可以安全使用时，我们必须依靠数学直觉, 这不能给我们提供实际的保证. 创建六年后，MH密码系统被一个 攻击 by A. 沙密. 又有几次重振MH的尝试，其中许多也失败了.
2016年，经过几次头脑风暴，本文的作者有了不同的灵感[3] 密码系统的可能性, 丹尼尔·桑塔纳·罗查提出了用高斯整数代替$\theta$和$\alpha$的想法. 出于更多的技术原因, 这种方法导致了对上述沙米尔袭击的抵抗.
他还构想了一个位块，由前面描述的a的线性组合的许多步骤组成 艰难的背包. 在每一个里面, 一个新的(高斯)整数, 等于1, 高于所有先前的总和将被添加到序列的末尾, 而目前最小的将被删除.
对于$\alpha$，有一个不同但非常类似的约束, 它现在是一个高斯整数. 我们需要$w_{max} \leq \vert\alpha\vert^2$. 原因很难确定, 但幸运的是，它可以很容易地从一个优雅的描述中直观出来:
想象一个复数平面上的方形格子, 直角三角形的斜边是哪条边 catheti A和b，平行于实轴和虚轴. 下面给出了这种晶格的一个例子. 模$\ α = a + bi$的高斯整数可以用位于这样一个格内的点来表示. 在这样的晶格中有$\vert\alpha\vert^2$个不同的点. 如果我们选择一个足够大的$\alpha$，我们可以拟合所有的简单背包的线性组合.
这是同构$f: Z/n \右箭头Z[i]/(\alpha)$的图形表示, 其中$n = 13$和$\alpha = a + bi = 3 + 2i$(注意$n$和$\alpha$确实满足$n = \vert \alpha \vert ^2 = a^2 + b^2 $的要求). 点代表高斯整数i.e.，复数$a + bi$，其中$a$和$b$是整数. 像往常一样, 横轴表示实部, 纵坐标表示虚部. 因此, 向右或向左移动一个点相当于在其当前值上加上+1或-1, 分别. 同样，向上或向下移动一个点对应于分别添加+i或-i.
红点表示等于$0 \bmod(\alpha)$. 除了这些，我们还为另外4对点上色.
| Color | 等于。对α取模 |
| 橙色 | $1$ |
| 绿色 | $i$ |
| 蓝色的 | $-1-i$ |
| 紫罗兰色的 | $1-i$ |
同构$f$是由循环序列$(0)的$i$th元素的变换定义的,1,2,\ cdot \ cdot \ cdot,10,11,12,0,1,2,\ cdot \ cdot \ cdot)$转换为图中同样循环的圆点序列的$i$th元素, 这符合以下规则:
为了映射至少$Y$个自然整数, 必须取一个面积为$\vert\alpha\vert^2$的正方形(其中$\vert\alpha\vert = \sqrt{a^2 + b^2}$), by 勾股定理(其侧面的测量)至少同样高.
注意，如果从上到下计算行，每次“跳转”都会将行号$r$更改为$r \leftarrow (r + b)(mod a + b)$, 和, 同样, 到$r \leftarrow (r + a)(mod a + b)$如果从下往上算的话. 因此, 每一行(和点)在每个循环中只漫游一次的必要和充分条件是，跳跃的大小与行数是一致的, or, 换句话说, 肾小球囊性肾病美元(,A + b) = gcd(b,a + b) = 1$. 根据最大公约数算子的性质, 这两个都等于肾小球囊性肾病美元(),b) = 1$.
Y. S. 维拉斯·博阿斯注意到$a$和$b$的共同性的需要. 为了保持超增长, each new integer $w$ added at the end 的 sequence needs to surpass the sum of all current ones ($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$的解, where all $v_i$ 和 $b_i$ are k现在n for $1 < i \leq n$. 因为我们也不知道b_1, 我们最终得到一个只有一个方程和两个变量的系统, 这样就只剩下一个自由度了. 为了纠正这个错误, 为了简单起见，我们必须选择一个正值, 1)总是赋值给$b_1$, 这样就消除了歧义. 因此, 因为第一个系数固定为1, 为了在每一步上编码$n$位, 整数序列必须有$n + 1$个元素长.
最后一个需要解决的技术问题是，消息的字节大小不是块大小的倍数. 换句话说, 如何处理最后一个数据块的可能剩余字节，以便, 一旦数据块被恢复, 原始内容的所有字节都被保留, 但也不过如此? 我们通过重复一次消息的最后一个字节来解决这个问题. 这个副本是, 然后, 然后是一个随机序列，每个组件只需要与前一个不同. 因此，当数据块被检索时，最后一个 或者，最坏的情况是，上一个的前一个 在字节的最后重复中被截断.[4]
现在让我们展示一个SRVB密码系统的示例.
我们从参数开始:
$k = 4$;
$m = 4$;
这产生了$ 1 = 4 * 4 = 16的块长度$, 以及一个k + 1 = 5的自然整数的超增数列, 这是操作-i.e., 线性组合, 加上这个线性组合的结果, 并简化到最后的$k + 1$元素- $m = 4$ times;
为简单起见，设以下为$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$, 因为它刚好大到足以容纳一个至少有1590个分量的整数环的同构, 同时也满足肾小球囊性肾病美元(),b)=1$. 此外，我们需要选择一个$\theta$，使肾小球囊性肾病美元(，\theta)=1$[5] 最好不要太低, 那么$(a_1 * \theta) \% \alpha \neq v_1 * \theta$, (也是为了避免泄露信息). $\theta = 60$完成了这项工作，得到:
19-1i美元,1 + 38我3-3i 6-6i 12-12i $[6]
那就让我们动手吧. 接受留言 你好Toptal!. 首先，我们将它映射到一个字节数组中 美国信息交换标准代码 截断数据块的约定:
01001000 01100101
01101100 01101100
01101111 00100000
01010100 01101111
01110000 01110100
01100001 01101100
00100001 00100001
因为我们的数据块是16位= 2字节长, 我们的信息有13个字符, 我们最终得到7个数据块，每个2字节, 其中最后一个包含字符' '的两倍位表示。!’ . 让我们一步一步地加密第一个块. 请密切注意，因为每个字节的位是按其重要性排序的.
$m=01001000 01100101$
这样，我们就得到了映射
“他”$ \ Rightarrow (12-12i 15 + 4我49 + 9,106 - 10 -我,252 - 2 - i)美元
加密消息的其余部分如下所示:
“ll”$ \ Rightarrow (12-12i 21-2i 61 - 3, 185 - 31, 367 - 59 - i)美元
" 0 " $\右行(12-12i,25+33i,65+32i,111+44i,244+124i)$
”到“$ \ Rightarrow (12-12i 9 + 10,我46 + 12,149 + 5,277 + 31 i)美元
“pt”美元\ Rightarrow (12-12i, 3 + 16,我46 + 12,73 + 23,201 + 49我)美元
“al”美元\ Rightarrow (12-12i, 4 + 54我44 + 53我,117 + 193,我231 + 389)美元
”!!" $ \ Rightarrow (12-12i 4 + 54我32 + 65,我63 + 92,我121 + 247)美元
现在，对于解密，我们有$\theta^{-1}=60^{-1}=27+i$:
$(“他”美元\ Rightarrow) $ $ (12-12i 15 + 4我49 + 9,106 - 10,252 - 2 - i) * \θ^{1}\ % \α= 16,93223527美元
接下来是贪心算法:
第一个, 我们减去每个促成因素乘以1, 因为众所周知，他们至少为最后一次做出了贡献, 收益率:
$T \leftarrow (527-233-93-47-16) = 148$
$(T \geq 223) = (148 \geq 223) = false \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) = false \Rightarrow b_4 = 0; T \leftarrow (T - 0 * 16) = 8$
结果:0110;
余数:8(添加到序列的开头作为新的最低元素);
从当前序列的final中删除527;
$T \leftarrow (233-93-47-16-8) = 59$
$(T \geq 93) = (59 \geq 93) = false \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) = false \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) = false \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) = false \Rightarrow b_3 = 0; T \leftarrow (T - 0 * 8) = 2$
$(T \geq 4) = (2 \geq 4) = false \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) = false \Rightarrow b_2 = 0; T \leftarrow (T - 0 * 8) = 1$
$(T \geq 4) = (1 \geq 4) = false \Rightarrow b_3 = 0; T \leftarrow (T - 0 * 4) = 1$
$(T \geq 2) = (1 \geq 4) = false \Rightarrow b_4 = 0; T \leftarrow (T - 0 * 2) = 1$
结果:1000;
余数:1(添加到序列的开头作为新的最低元素);
从当前序列的最后删除47;
结果是, 我们已经恢复了包含前两个字符“He”的数据块“01001000 01100101”。, 我们的信息. 不仅如此, 我们还正确地检索了我们的私钥超增序列$(1),2,4,8,16)$.
其他数据块映射以同样的方式进行.
SRVB是:
我们已经可以总结出最可能的漏洞. 由于SRVB来自MH，因此很容易怀疑它可能容易受到 沙米尔攻击，或者其他打破它的东西. 尽管作者有理由相信情况并非如此, 目前还没有对此进行确认(这在处理密码系统时是非常典型的).
Rocha对将要使用的商环进行了一些推广, 这可能会导致密码分析的复杂性增加. 我们也将调查这些可能性.
碰巧的是, 在SRVB的开发和文档编制过程中, Villas Boas提出了另一种方法来改进背包公钥密码系统的概念，这里不会详细解释, 为了不让这篇文章变得太长太无聊, 但这里有一个略读. 如果你没有成功地抓住它, 别担心, 请继续关注我们下一篇文章的发布, 其中我们将更深入地讨论细节:参见子集和y, 的, 说, $N$商环元素$u_i$(同构对应于超递增序列的正整数$v_i$), 和以前一样)作为这些$u_i$的行向量乘以由0和1组成的列向量$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)美元=乌兰巴托,
其中$b_i \in {0,1}$
现在, 想象一下,, 而不是这个向量$u_i$, 你有, on the left a $n$ by $N$ (with $n < N$) matrix V, 将$v_i$(来自超递增序列的整数)向量作为(不失一般性)其第一行，并将所有其他条目填充为噪声. 请注意,, 现在, 将V乘以相同的位向量B，得到列向量W，它的第一项是W，其他项是噪声. 现在，用这个V矩阵乘以一个随机的[9] n × n矩阵R在左边，定义n × n矩阵P
P = rv
这个想法是Bob使用P作为他的新公钥. 因为向量R的随机性
$ y = pb = rv b = rw $
信息$w$是否被其他行V中的噪声所掩盖. 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 $
(现在，利用 结合性 消去r)
然后像之前一样通过贪心算法从w$中提取向量b_i$.
So, 一句话, 线性代数模糊利用了材料乘法的结合性(我们可以展开项，然后以新的顺序操作它们的分量，前提是我们保留了序列中所有操作数的序列)来“线性”搅乱，然后(分别在加密和解密中)过滤噪声到/从$w$. 在极限情况下n = 1，系统优雅地回到了Rocha的方法.
如前所述, 根据科克霍夫的原则, 经验表明，一个公开的未被破解密码系统的古老性是其可靠性的主要来源, 远远超过了自己作者的任何理论论证, 除此之外, 因为这些算法的有效性通常没有明确的证据.
这是我们将这些概念付诸实践以赚取大笔奖金的好机会:意识到这一事实, 我们推出了前面提到的 运动, 这基本上是一种众筹，奖品自动颁发给第一个成功破解信息的人. 这些钱将被转换成比特币，放在一个给定的钱包里，这个钱包的私钥将被SRVB加密并公布，这样任何能够破译它的人都可以匿名拿走钱, 没有问题.
这篇文章，特别是整个SRVB加密项目，在很大程度上得到了教授的帮助. 查尔斯·F. de Barros他是纽约大学的助理教授
此外，我还要向教授表示深深的感谢 Adnan Ademovic 感谢他作为这篇文章的编辑所做的富有洞察力、细心和耐心的工作.
术语表
[1] 注意这里的短语 解读 or 解密 不适用, 因为在给定的密码系统(及其所有组件)之前, (包括它的键)定义良好, 人们不能将从加密消息中解析原始消息的给定方法归类为预期的通信(解密)或攻击(解密)。.
[2] 尽管有一些技术可以改善这种猜测工作, 发现它们仍然比繁殖它们困难得多.
[3] 第一个灵感来自于 猜想树, 一棵以数字1为根的无限树, 谁的其他节点由整数组成，导致一个二进制运算求和, 减法, 或者前面节点之间的乘法, 可能是一个节点自己操作. 该理论的目标与树中每个整数首次出现的深度有关. 很明显，在低矮的树枝上很难找到大量的数字(即使我们放松对它的需求)。, 但是，检查给定的操作序列是否确实产生给定的结果是立即的吗.
[4] 这当然不是最自然的方法, 但是通过采用这个, 一是确保这个字节填充(称为 填充)…
如果每条信息的最后一个区块都是有系统地偏离均匀分布的, 攻击者可以利用这一事实进行统计密码分析, 因为任何给定的消息样本在统计上都比其他方式更具代表性. 换句话说, 最后一个街区的统计差异较小, 它们变成了它们变成了信息中最薄弱的环节.
[5] 不要搞错:这个最大公约数是高斯的，而前一个是实数.
[6] 这并不完美, 因为它很容易给出最后三个分量与1成正比的事实, 2, 和图4. 但是，为了简单起见，我们将忽略这个细节.
[7] 这是非常复杂的，有几个 臭名昭著的失败案例实现和维护基于它的协议.
[8] 在这里, 我们不会采用Rocha的多重线性组合块的方法, 这也允许我们随机排列他，让他们更加模糊.
[9] 虽然不是完全随机的. 它的转置必须张成由向量$ e_1 =(1,0，…，0)$生成的子空间.
世界级的文章，每周发一次.
世界级的文章，每周发一次.
作者都是各自领域经过审查的专家，并撰写他们有经验的主题. 我们所有的内容都经过同行评审，并由同一领域的Toptal专家验证.