Friday, December 23, 2005

Verisign M-4 factored

Let M be the modulus of VeriSign Class 3 Public Primary Certification Authority public key, valid until the year 2028. While factoring M is expected to be hard, M-4 has a relatively smooth factorization:

M-4 = 3 * 3 * 193 * 331 * 6128405401 * 600270585077 * 740739825201997 * 3767960522848201931 * 1763988934035706139627 * 59813208105314032027291 * 3246151553918103368085998272489 * 276773842952611154114920239220722631 * 26429454638260922608191475868189426039 * 3894223443367528241282778866698497025018177 * 2455048868245492012151874489544364890868369330214795356411

The original number has 309 digits. The largest factor of M-4 has only 58 digits. While "relatively smooth" for 309-digit numbers, it is still not smooth enough to aid in the factorization of M itself. Furthermore, I do not know if the special number field sieve can deal with offsets that are not +1 or -1, (namely -4).

No comments :