What are the implications of Shamirs TWINKLE device on PGP security?
“TWINKLE” is a theoretical device thought up by Adi Shamir early in ’99 [Sha99]. It stands for The Weizmann Institute Key Locating Engine. TWINKLE is a sieving machine that can be used to break RSA keys and, to a lesser extent, DH/DSS keys. To my knowledge, no TWINKLE machines have yet been implemented, but they are thought to be practical. Rather than inventing a new method of factoring, TWINKLE simply speeds up the implementation of an existing algorithm (NFS). NFS consists of two steps: • Sieving. This step can be distributed among multiple machines. • Solving the Matrix. Currently can only be performed on a single machine. Very memory intensive. Where feasible, the TWINKLE device dramatically speeds up the sieving portion of NFS. A conventional computer is still then required to solve the resulting matrix. Recently, a team broke a 465-bit number using NFS. The sieving portion took 200 computers 4 weeks and solving the matrix took a CRAY supercomputer 4 days and 810Mb of RAM. In con
