Abstract:

Aiming at the problem that the key stream sequence of RC4 algorithm is not highly random, and it is vulnerable to fault introduction attack, distinguishing attack and “armed attack”, an improved RC4 algorithm based on BBS generator and elliptic curve is proposed. The algorithm generates a seed key by using a random bit generator and a random large prime number, and generates a secret integer by using an elliptic curve. After each output, the elements in the S box are re-assigned to generate a highly random key stream sequence. The improved RC4 algorithm can pass the NIST randomness test, in which the frequency test, the run test and the Maurer test ratio are higher than the RC4 algorithm by 0.12918, 0.10739, 0.19764, respectively, which can effectively prevent the generation of invariant weak keys and resist the “armed” attack. The key stream sequence is evenly distributed, without deviation, and it can effectively resist the distinguishing attack. The secret integer guessing based on the elliptic curve is difficult to guess, and the internal state of the S box cannot be known, which can resist the “fault introduction” attack. Theoretical and experimental results show that the randomness and safety of improved RC4 algorithm is higher than RC4 algorithm.

Key words: RC4 algorithm, random bit generator, elliptic curve, secret integer

摘要：

针对RC4算法密钥流序列随机性不高，易受故障引入攻击、区分攻击和“受戒礼攻击”的问题，提出了一种基于BBS产生器和椭圆曲线的RC4改进算法。该算法利用随机比特产生器和随机大素数生成种子密钥Key，利用椭圆曲线产生秘密整数，在每次输出后对S盒中元素重新赋值，生成随机性很高的密钥流序列。改进RC4算法可以通过NIST随机性测试，其中频率检验、游程检验和Maurer检验等比RC4算法分别高出0.129 18，0.107 39，0.197 64，能够有效防止不变性弱密钥的产生，抵抗“受戒礼”攻击；密钥流序列分布均匀，不存在偏差，能够有效抵御区分攻击；基于椭圆曲线产生的秘密整数猜测困难，S盒内部状态不能获知，能够抵抗“故障引入”攻击。理论和实验证明改进RC4算法的随机性和安全性高于RC4算法。

关键词: RC4算法, 随机比特产生器, 椭圆曲线, 秘密整数