 | This article needs additional citations for verification .(October 2018) |
In mathematics, a strong prime is a prime number with certain special properties. The definitions of strong primes are different in cryptography and number theory.
| | This article needs additional citations for verification .(October 2018) |
In mathematics, a strong prime is a prime number with certain special properties. The definitions of strong primes are different in cryptography and number theory.
In number theory, a strong prime is a prime number that is greater than the arithmetic mean of the nearest prime above and below (in other words, it's closer to the following than to the preceding prime). Or to put it algebraically, writing the sequence of prime numbers as (p1, p2, p3, ...) = (2, 3, 5, ...), pn is a strong prime if pn > pn − 1 + pn + 1/2. For example, 17 is the seventh prime: the sixth and eighth primes, 13 and 19, add up to 32, and half that is 16; 17 is greater than 16, so 17 is a strong prime.
The first few strong primes are
In a twin prime pair (p, p + 2) with p > 5, p is always a strong prime, since 3 must divide p − 2, which cannot be prime.
In cryptography, a prime number p is said to be "strong" if the following conditions are satisfied. [1]
It is possible for a prime to be a strong prime both in the cryptographic sense and the number theoretic sense. For the sake of illustration, 439351292910452432574786963588089477522344331 is a strong prime in the number theoretic sense because the arithmetic mean of its two neighboring primes is 62 less. Without the aid of a computer, this number would be a strong prime in the cryptographic sense because 439351292910452432574786963588089477522344330 has the large prime factor 1747822896920092227343 (and in turn the number one less than that has the large prime factor 1683837087591611009), 439351292910452432574786963588089477522344332 has the large prime factor 864608136454559457049 (and in turn the number one less than that has the large prime factor 105646155480762397). Even using algorithms more advanced than trial division, these numbers would be difficult to factor by hand. For a modern computer algebra system, these numbers can be factored almost instantaneously. A cryptographically strong prime has to be much larger than this example.
Some people suggest that in the key generation process in RSA cryptosystems, the modulus n should be chosen as the product of two strong primes. This makes the factorization of n = pq using Pollard's p − 1 algorithm computationally infeasible. For this reason, strong primes are required by the ANSI X9.31 standard for use in generating RSA keys for digital signatures. However, strong primes do not protect against modulus factorisation using newer algorithms such as Lenstra elliptic curve factorization and Number Field Sieve algorithm. Given the additional cost of generating strong primes RSA Security do not currently recommend their use in key generation. Similar (and more technical) argument is also given by Rivest and Silverman. [1]
It is shown by Stephen Pohlig and Martin Hellman in 1978 that if all the factors of p − 1 are less than logcp, then the problem of solving discrete logarithm modulo p is in P. Therefore, for cryptosystems based on discrete logarithm, such as DSA, it is required that p − 1 have at least one large prime factor.
A computationally large safe prime is likely to be a cryptographically strong prime.
Note that the criteria for determining if a pseudoprime is a strong pseudoprime is by congruences to powers of a base, not by inequality to the arithmetic mean of neighboring pseudoprimes.
When a prime is equal to the mean of its neighboring primes, it's called a balanced prime. When it's less, it's called a weak prime (not to be confused with a weakly prime number).
In cryptography, key size, key length, or key space refer to the number of bits in a key used by a cryptographic algorithm.
In number theory, a Carmichael number is a composite number which satisfies the modular arithmetic congruence relation:
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.
A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.
RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem that is widely used for secure data transmission. It is also one of the oldest. The acronym RSA comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publicly described the algorithm in 1977. An equivalent system was developed secretly, in 1973 at GCHQ, by the English mathematician Clifford Cocks. That system was declassified in 1997.
In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.
Fermat's little theorem states that if p is a prime number, then for any integer a, the number ap − a is an integer multiple of p. In the notation of modular arithmetic, this is expressed as
In number theory, a prime number p is a Sophie Germain prime if 2p + 1 is also prime. The number 2p + 1 associated with a Sophie Germain prime is called a safe prime. For example, 11 is a Sophie Germain prime and 2 × 11 + 1 = 23 is its associated safe prime. Sophie Germain primes are named after French mathematician Sophie Germain, who used them in her investigations of Fermat's Last Theorem. Sophie Germain primes and safe primes have applications in public key cryptography and primality testing. It has been conjectured that there are infinitely many Sophie Germain primes, but this remains unproven.
In arithmetic, an odd composite integer n is called an Euler pseudoprime to base a, if a and n are coprime, and
The Rabin cryptosystem is an asymmetric cryptographic technique, whose security, like that of RSA, is related to the difficulty of integer factorization. However the Rabin cryptosystem has the advantage that it has been mathematically proven to be computationally secure against a chosen-plaintext attack as long as the attacker cannot efficiently factor integers, while there is no such proof known for RSA. It has the disadvantage that each output of the Rabin function can be generated by any of four possible inputs; if each output is a ciphertext, extra complexity is required on decryption to identify which of the four possible inputs was the true plaintext.
In mathematics and computer science, computational number theory, also known as algorithmic number theory, is the study of computational methods for investigating and solving problems in number theory and arithmetic geometry, including algorithms for primality testing and integer factorization, finding solutions to diophantine equations, and explicit methods in arithmetic geometry. Computational number theory has applications to cryptography, including RSA, elliptic curve cryptography and post-quantum cryptography, and is used to investigate conjectures and open problems in number theory, including the Riemann hypothesis, the Birch and Swinnerton-Dyer conjecture, the ABC conjecture, the modularity conjecture, the Sato-Tate conjecture, and explicit aspects of the Langlands program.
Pollard's p − 1 algorithm is a number theoretic integer factorization algorithm, invented by John Pollard in 1974. It is a special-purpose algorithm, meaning that it is only suitable for integers with specific types of factors; it is the simplest example of an algebraic-group factorisation algorithm.
In cryptography and number theory, TWIRL is a hypothetical hardware device designed to speed up the sieving step of the general number field sieve integer factorization 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.
In number theory, an n-smooth (or n-friable) number is an integer whose prime factors are all less than or equal to n. For example, a 7-smooth number is a number whose every prime factor is at most 7, so 49 = 72 and 15750 = 2 × 32 × 53 × 7 are both 7-smooth, while 11 and 702 = 2 × 33 × 13 are not 7-smooth. The term seems to have been coined by Leonard Adleman. Smooth numbers are especially important in cryptography, which relies on factorization of integers. The 2-smooth numbers are just the powers of 2, while 5-smooth numbers are known as regular numbers.
In cryptography, the RSA problem summarizes the task of performing an RSA private-key operation given only the public key. The RSA algorithm raises a message to an exponent, modulo a composite number N whose factors are not known. Thus, the task can be neatly described as finding the eth roots of an arbitrary number, modulo N. For large RSA key sizes, no efficient method for solving this problem is known; if an efficient method is ever developed, it would threaten the current or eventual security of RSA-based cryptosystems—both for public-key encryption and digital signatures.
The Goldwasser–Micali (GM) cryptosystem is an asymmetric key encryption algorithm developed by Shafi Goldwasser and Silvio Micali in 1982. GM has the distinction of being the first probabilistic public-key encryption scheme which is provably secure under standard cryptographic assumptions. However, it is not an efficient cryptosystem, as ciphertexts may be several hundred times larger than the initial plaintext. To prove the security properties of the cryptosystem, Goldwasser and Micali proposed the widely used definition of semantic security.
In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently. It is not known how to prove (unconditional) hardness for essentially any useful problem. Instead, computer scientists rely on reductions to formally relate the hardness of a new or complicated problem to a computational hardness assumption about a problem that is better-understood.
Integer factorization is the process of determining which prime numbers divide a given positive integer. Doing this quickly has applications in cryptography. The difficulty depends on both the size and form of the number and its prime factors; it is currently very difficult to factorize large semiprimes.
In cryptography, Very Smooth Hash (VSH) is a provably secure cryptographic hash function invented in 2005 by Scott Contini, Arjen Lenstra and Ron Steinfeld. Provably secure means that finding collisions is as difficult as some known hard mathematical problem. Unlike other provably secure collision-resistant hashes, VSH is efficient and usable in practice. Asymptotically, it only requires a single multiplication per log(n) message-bits and uses RSA-type arithmetic. Therefore, VSH can be useful in embedded environments where code space is limited.