JISE

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16]

Journal of Information Science and Engineering, Vol. 32 No. 3, pp. 597-610

The Attack of the RSA Subgroup Assumption

JIANG WENG^1,2, YUN-QI DOU^1,2 AND CHUAN-GUI MA^1,2
¹State Key Laboratory of Mathematical Engineering and Advanced Computing
²Zhengzhou Information Science and Technology Institute
Zhengzhou, 450001 P.R. China
E-mail: {wengjiang858}@163.com

In TCC 2005, Groth proposed the cryptographic usefulness of a small subgroup G of Z^*_N of hidden order. So far, the best attack of previous method for a subgroup of Z^*_Nhad a complexity about O(p'). In this paper, we propose the interval and the double walks method to speed up the computation of the semi-smooth RSA subgroup problem. Our new algorithm reduces the complexity to O(p/2) rather than O(p'). Besides the theoretical analysis, we also compare the performances of our new algorithm with the previous algorithm in experiments, and the efficiency of our new algorithm is approach to 50% faster than the previous.

Keywords: RSA moduli, hidden order, subgroup, cryptanalysis, semi-smooth RSA

Retrieve PDF document (JISE_201603_05.pdf)