A trapdoor function is a function that is easy to compute in one direction, yet believed to be difficult to compute in the opposite direction (finding its inverse) without special information, called the "trapdoor". The Mathematical concept of a function expresses dependence between two quantities one of which is given (the independent variable, argument of the function In Mathematics, if &fnof is a function from A to B then an inverse function for &fnof is a function in the opposite direction from B Trapdoor functions are widely used in cryptography. Cryptography (or cryptology; from Greek grc κρυπτός kryptos, "hidden secret" and grc γράφω gráphō, "I write"
In mathematical terms, if f is a trapdoor function there exists some secret information y, such that given f(x) and y it is easy to compute x. Consider taking an engine apart. It would not be very easy to put it together again unless of course you had the assembly instructions. These instructions would be the trapdoor that allow you to return the engine to its original state. A mathematical example would be the multiplication of two large prime numbers. In Mathematics, a prime number (or a prime) is a Natural number which has exactly two distinct natural number Divisors 1 Finding and verifying two large primes is easy, as is their multiplication. But factoring the resultant product can be very difficult.
Trapdoor functions came to prominence in cryptography in the mid-1970s with the publication of asymmetric encryption techniques by Diffie, Hellman, and Merkle. This article is about the Decade 1970-1979 For the Year 1970 see 1970. Public-key cryptography, also known as asymmetric cryptography, is a form of Cryptography in which the key used to encrypt a message differs from the key Bailey Whitfield 'Whit' Diffie (born June 5 1944) is a US Cryptographer and one of the pioneers of Public-key cryptography. Martin Edward Hellman (born October 2, 1945) is a cryptologist, famous for his invention of Public key cryptography in cooperation with Ralph C Merkle (born February 2, 1952) is a pioneer in Public key cryptography, and more recently a researcher and speaker on Molecular nanotechnology Indeed, Diffie and Hellman first coined the term (Diffie and Hellman, 1976). Several function classes have been proposed, and it soon became obvious that trapdoor functions are harder to find than was initially thought. For example, an early suggestion was to use schemes based on the subset sum problem. In Computer science, the subset sum problem is an important problem in complexity theory and Cryptography. This turned out -- rather quickly -- to be unsuitable.
As of 2004, the best known trapdoor function (family) candidates are the RSA and Rabin families of functions. "MMIV" redirects here For the Modest Mouse album see " Baron von Bullshit Rides Again " In Cryptography, RSA is an Algorithm for Public-key cryptography. The Rabin cryptosystem is an asymmetric Cryptographic technique whose security like that of RSA, is related to the difficulty of Factorization. Both are written as exponentiation modulo a composite number, and both are related to the problem of prime factorisation.
Functions related to the hardness of the discrete logarithm problem (either modulo a prime or in a group defined over an elliptic curve) are not known to be trapdoor functions, because there is no known "trapdoor" information about the group that enables the efficient computation of discrete logs. In Mathematics, specifically in Abstract algebra and its applications discrete logarithms are group-theoretic analogues of ordinary Logarithms Elliptic curve cryptography (ECC is an approach to Public-key cryptography based on the algebraic structure of Elliptic curves over Finite fields The use However, the discrete logarithm problem can be used as the basis for a trapdoor when the related problems called the computational Diffie-Hellman problem (CDH) and/or its decisional variant are used. The Diffie-Hellman problem (DHP is the name of a specific problem in Cryptography which was first proposed by Whitfield Diffie and Martin Hellman. The semantically secure version of the ElGamal Cryptosystem relies on the Decision Diffie-Hellman problem (DDH). In Cryptography, the ElGamal encryption system is an Asymmetric key encryption algorithm for Public-key cryptography which is based on the Diffie-Hellman The Diffie-Hellman problem (DHP is the name of a specific problem in Cryptography which was first proposed by Whitfield Diffie and Martin Hellman. The Digital Signature Algorithm is based on CDH in a prime order subgroup. The Digital Signature Algorithm (DSA is a United States Federal Government standard or FIPS for Digital signatures It was proposed by the
A trapdoor in cryptography has the very specific aforementioned meaning and is not to be confused with a backdoor (these are frequently used interchangeably and this is incorrect). A backdoor in a Computer system (or Cryptosystem or Algorithm) is a method of bypassing normal Authentication, securing remote access to a computer A backdoor is a deliberate mechanism that is added to a cryptographic algorithm (e. g. , a key pair generation algorithm, digital signing algorithm, etc. ) or operating system, for example, that permits one or more unauthorized parties to bypass or subvert the security of the system in some fashion.
See also
References
- W. A one-way function is a function that is easy to compute but "hard to invert" (in the sense defined below Diffie and M. Hellman. New Directions in Cryptography. IEEE Trans. Info. Theory 22(6), pp644–654 (1976). PDF version of the paper
Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic