需要一个非常快的一对一算法，可能加密 [英] Need a very fast one-to-one algorithm, possibly encryption

问题描述

我需要一个非常，非常快的一对一算法。该算法不需要是不可破解的。合理的坚强是足够的，但它必须闪电快。我将在硬件中实现它。区域也是一个问题，所以它不应该使用太多的逻辑。

它应该是一个函数f_N（x），其输入是一个N位数，其输出是N位数。 N是常数，可能在20-70之间。该函数必须是一对一。 （即可逆的，意味着解密是可能的。解密速度是无关紧要的。）

我需要在3ns以内加密，这是每秒大约333M的输入。例如，DES每秒大约50Mbits。我每秒需要333M 输入。

到目前为止，我已经使用了大约6轮的Feistel密码。

更多记录

p>

有一些问题，我会解释。我需要把密钥放入哈希表。标准方法是对输入密钥进行散列，并将结果用作表中的索引。表中的每一行都必须存储原始密钥。 信息理论告诉我们，表格的行实际上不需要与输入键，而是与输入键少一样宽，表中地址的位数。例如：

• 输入：x（N位）


• hash：x％128位）


• 验证者：floor（x / 128）（N-8位）

对于整数通常是相同的宽度，但是我用硬件来做的，这将是愚蠢的。

x％128是一个容易的哈希。事实上，如果输入键仅在前几位不同，您将在事故时破坏散列。我想要一个哈希，不会被打破事故，甚至可能很难打破目的。我也尝试过 LFSR 。 LFSR是快速的，但是两个相等长度的LFSR生成线性相关的散列结果。 （如果f（x）和g（x）对两个不同的多项式给出相同的散列，f（x + 1）和g（x + 1）很容易相关。）

因此，我需要一个具有N位输入和V位，H位输出（V + H = N）的函数，其中很难找到长度为N的两个输入，使得两个输入都输出相同的H.加密适合账单，因为它使输出与输入长度相同，并且很难反转。加密以外的东西也可以工作，尽管它看起来像我想要的几乎是加密的定义。

很抱歉，没有解释所有这一切。希望这澄清的事情。

解决方案

当你说快你只关心吞吐量，最高重要性？

如果延迟不如吞吐量那么重要，是否有任何理由不能使用标准 Feistel密码，在每个回合之间粘一个寄存器，以便管道加密算法？它本质上将需要相同数量的硬件（稍微多一些来为寄存器添加一些触发器）作为已知的安全加密算法，但是传播延迟将只是Feistel网络的一个循环+传播延迟触发器。

I need a very, very fast one-to-one algorithm. The algorithm doesn't need to be unbreakable. Reasonably strong is enough but it must be lightning fast. I will be implementing it in hardware. Area is a concern, too, so it shouldn't use too much logic.

It should be a function f_N(x) whose input is an N-bit number and whose output is an N-bit number. N is a constant, probably between 20-70. The function must be one-to-one. (ie invertible, meaning that decryption is possible. Decryption speed is irrelevant.)

I need to encrypt in under 3ns, which is about 333M inputs per second. DES, for example, does about 50Mbits per second. I need 333M inputs per second.

So far I've been using a Feistel cipher with about 6 rounds. That seems to take about 3ns.

Suggestions?

More notes

There have been some questions so I'll explain. I need to put keys into a hash table. The standard method is to hash the input key and use the result as an index into a table. Each row in the table must store the original key. Information theory tells us that the rows of the table don't actually need to be as wide as the input key, but rather as wide as the input key less the number of bits in the address of the table. For example:

• input: x (N bits)
• hash: x%128 (8 bits)
• verifier: floor(x/128) (N-8 bits)

It would be silly on a CPU where integers are usually the same width but I'm doing it in hardware.

x%128 is an easy hash to break. In fact, if the input keys only differ in the first few bits, you will have broken the hash on accident. I want a hash that won't be broken on accident and might even be difficult to break on purpose. I also tried an LFSR. LFSRs are fast but two LFSRs of equal length generate hash results that are correlated linearly. (If f(x) and g(x) give the same hash for two different polynomials, f(x+1) and g(x+1) are easily correlated.)

So, I need a function with N-bit input and V-bit,H-bit output (V+H=N) where it is difficult to find two inputs of length N such that both will output the same H. Encryption fits the bill in that it leaves the output the same length as the input and it is difficult to reverse. Something other than encryption might work, too, though it seems like what I want is almost the very definition of encryption.

Sorry about not explaining all this up-front. Hope that this clarifies things.

解决方案

When you say "fast" do you care only about throughput, or is latency itself of the highest importance?

If latency is not quite as important as throughput, is there any reason why you can't use a standard Feistel cipher that is known to be secure, and instead of having the full number of rounds (e.g. like 16 in Blowfish) output from combinational logic, stick a register in between each round, so that you pipeline the encryption algorithm? It would essentially require the same amount of hardware (a little bit more to add some flip-flops for registers) as a known secure encryption algorithm, but the propagation delay would only be that of one round of the Feistel network + the propagation delay of the flip-flops.

这篇关于需要一个非常快的一对一算法，可能加密的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！