Analysis of Two Public Key Cryptosystems Based on Randomized Knapsack Sequences

Two knapsack public key cryptosystems based on randomized knapsack sequences were proposed in 2009 and 2011 respectively, where the secret knapsack sequence is transformed by secret modular linear transforms into one or three public randomized knapsack sequences with appropriate density. In this paper, we recover the secret modular linear transforms by simultaneous Diophantine approximation and propose secret key recovery attacks on these two cryptosystems. Practical attack experiments are done within one minute.