cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...

and

number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777� ...

, TWIRL (The

Weizmann Institute The Weizmann Institute of Science ( he, מכון ויצמן למדע ''Machon Vaitzman LeMada'') is a public research university in Rehovot, Israel, established in 1934, 14 years before the State of Israel. It differs from other Israeli univ ...

Relation Locator) is a hypothetical hardware device designed to speed up the sieving step of the

general number field sieve In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than . Heuristically, its complexity for factoring an integer (consisting of bits) is of the form :\exp\left( ...

integer factorization In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are suf ...

algorithm. During the sieving step, the algorithm searches for numbers with a certain mathematical relationship. In distributed factoring projects, this is the step that is parallelized to a large number of processors. TWIRL is still a hypothetical device — no implementation has been publicly reported. However, its designers, Adi Shamir and

Eran Tromer Eran is an ancient town and archaeological site in the Sagar district of Madhya Pradesh, India. It was one of the ancient mints for Indian dynasties as evidenced by the diverse coins excavated here. The site has 5th and 6th-century Gupta era ...

, estimate that if TWIRL were built, it would be able to factor 1024-bit numbers in one year at the cost of "a few dozen million

US dollar The United States dollar (symbol: $; code: USD; also abbreviated US$ or U.S. Dollar, to distinguish it from other dollar-denominated currencies; referred to as the dollar, U.S. dollar, American dollar, or colloquially buck) is the official ...

s". TWIRL could therefore have enormous repercussions in

and

computer security Computer security, cybersecurity (cyber security), or information technology security (IT security) is the protection of computer systems and networks from attack by malicious actors that may result in unauthorized information disclosure, the ...

— many high-security systems still use 1024-bit RSA keys, which TWIRL would be able to break in a reasonable amount of time and for reasonable costs. The security of some important cryptographic algorithms, notably RSA and the Blum Blum Shub pseudorandom number generator, rests in the difficulty of factorizing large integers. If factorizing large integers becomes easier, users of these algorithms will have to resort to using larger keys (computationally more expensive) or to using different algorithms, whose security rests on some other computationally hard problem (like the

discrete logarithm In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b' ...

problem).

References

{{reflist

External links

"The TWIRL integer factorization device" - homepage
Cryptanalytic devices Weizmann Institute of Science

See also

References

External links