In
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
Adi Shamir ( he, עדי שמיר; born July 6, 1952) is an Israeli cryptographer. He is a co-inventor of the Rivest–Shamir–Adleman (RSA) algorithm (along with Ron Rivest and Len Adleman), a co-inventor of the Feige–Fiat–Shamir identificat ...
and
Eran Tromer, 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
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
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
Blum Blum Shub (B.B.S.) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub that is derived from Michael O. Rabin's one-way function.
__TOC__
Blum Blum Shub takes the form
:x_ = x_n^2 \bmod M,
where ...
pseudorandom number generator
A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generate ...
, 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).
See also
*
Custom hardware attack
In cryptography, a custom hardware attack uses specifically designed application-specific integrated circuits (ASIC) to decipher encrypted messages.
Mounting a cryptographic brute force attack requires a large number of similar computations: ...
*
TWINKLE
Twinkle may refer to:
* Twinkling, the variation of brightness of distant objects
People
* Twinkle (singer) (1948–2015), born Lynn Annette Ripley, English singer-songwriter
* Twinkle Khanna, Indian movie actress
* Twinkle Bajpai, female conte ...
References
{{reflist
External links
"The TWIRL integer factorization device" - homepage
Cryptanalytic devices
Weizmann Institute of Science