It provides a brief implementation, although it is simple, but it is quite interesting, because after all, it is a method of attacking the RSA of the decomposition factor. It can be seen that under certain conditions, the program can be obtained by the public key N, B.
Specific ideas, proof and pseudo code, please refer to Douglas R.stinson's "Cryptography" and practice ", this book has a Chinese translation, and the title is" password principle and practice ", translated by Feng Deguo.
C implementation of the low decryption index attack on the RSA password, C implementation #include #include using namespace std; const n = 10000; Static Long Q [N], M, PRIKEY, P, Q; STATIC INT flag = 0; int EUC (long A, long b) // Euclidean algorithm {long r [n]; r [0] = a; r [1] = b; m = 1; while (r [m]! = 0) {q [m] = r [M-1] / R [m]; r [m 1] = r [m-1] -Q [m] * r [m]; m ;} M- -; RETURN R [M];} void Wiener (long n, long b) // Wiener attack {long c [n], d [n], j; double ndot, test, test1; double temp, mid, de, Delte, PP, QQ; C [0] = 1; C [1] = Q [1]; D [0] = 0; D [1] = 1; j = 1; While (j <= m) {TEMP = double (c [j]) * (b); ndot = (TEMP-1) / double (d [j]); test = long (ndot); if (test == ndot) {mid = double (n) -ndot 1.0; de = mid * mid-4.0 * double (n); delte = SQRT (DE); QQ = (mid-delte) / 2.0; pp = (MID DELTE) / 2.0; test = long (PP ); Test1 = long (QQ); if (test == pp && test1 == qq && de> = 0) {// COUT << "P =" << PP << ", q =" << qq << Endl; P = PP; Q = QQ; FLAG = 1;}}} J ; C [J] = Q [J] * C [J-1] C [J-2]; D [J] = Q [J] * D [J-1] D [J-2];} if (! flag) cout << ". .attack failed "<< Endl;} int GCD (int A, int b, int & x, int & y) // Ask the same equation {if (! b) {x = 1; y = 0; return a;} else {INT R = GCD (B, A% B, X, Y); INT T = x; x = y; y =
