The integer factorization problem used in the RSA cryptosystem, the discrete logarithm problem used in Diffie-Hellman Key Exchange protocol and the Elliptic Curve Discrete Logarithm problem used in Elliptic Curve Cryptography are traditionally considered the difficult problems and used extensively in the design of cryptographic algorithms. We provide a number of other computationally difficult problems in the areas of Cryptography and Cryptanalysis. A class of problems called the Search problems, Group membership problems, and the Discrete Optimization problems are examples of such problems. A number of computationally difficult problems in Cryptanalysis have also been identified including the Cryptanalysis of Block ciphers, Pseudo-Random Number Generators and Hash functions.
TopProblems In Cryptography
In search for more efficient and/or secure alternatives to established cryptographic protocols (such as RSA which is based on the factorization problem), there have been proposals for public key establishment protocols as well as with public key cryptosystems based on hard search problems from combinatorial (semi) group theory. These problems include the conjugacy search problem (Anshel et al.,1999; Ko, 2000), the homomorphism search problem (Grigoriev et al., 2006; Shpilrain, 2006a), the decomposition search problem (Cha et.al, 2001; Ko, 2000; Shpilrain, 2005) and the subgroup membership search problem (Shpilrain, 2006b). All these are problems of the following nature: given a property P and the information that there are objects with the property P, find at least one particular object with the property P from a pool S of objects.
The following problems have been considered difficult problems and used in cryptography.
The RSA Problem: Given a positive integer n that is a product of two distinct odd primes p and q and a positive integer e such that gcd(e,(p-1)(q-1)) =1 and an integer c, find an integer m such that me ≡ c(mod n).
The RSA Problem is that of finding the eth roots modulo a composite integer n. The underlying one-way function f(x) = xe (mod n) (f: Zn →Zn) is called the RSA function. Zn is the set of integers modulo n i.e., Zn = {0, 1, 2, …n-1}. Addition, Subtraction and Multiplication are performed modulo n. The inverse is f(x)-1 = xd (mod n), where d ≡ e-1 (mod 𝜑(n))
The Quadratic Residuosity Problem: Given an odd composite integer n and integer having Jacobi symbol 
, decide whether or not a is a quadratic residue modulo n. The integer a is said to be a quadratic residue if there exists an x such that x2 ≡ a (mod n).
If the prime factorization is 
. then the Jacobi symbol is evaluated as
where
evaluates to 0, 1, or -1 if
a divides
pi or
a is a quadratic residue or if
a is a quadratic non-residue of
pi.
The Square Root Modulo n Problem: Given a composite integer n and a∈ Qn (the set of quadratic residues modulo n), find a square root of a modulo n.