Previous [ 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 (May 2016)


The Attack of the RSA Subgroup Assumption*


JIANG WENG1,2, YUN-QI DOU1,2 AND CHUAN-GUI MA1,2
1State Key Laboratory of Mathematical Engineering and Advanced Computing
2Zhengzhou 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

Full Text () Retrieve PDF document (201605_05.pdf)

Received January 8, 2015; accepted July 1, 2015.
Communicated by Hung-Min Sun.
* This work was supported by the National Natural Science Foundation of China (No. 61309016, 61379150) and Open Project Program of the State Key Laboratory of Mathematical Engineering and Advanced Computing.