Printer Friendly

RSA-type algebra structures.

1. Introduction

The RSA cryptosystem, named after its inventors Ron Rivest, Adi Shamir, and Len Adleman, was introduced in 1978 and has been widely used for ensuring the privacy and authenticity of digital data. Since then, there has been concentration on two trends considering the RSA cryptosystem: (i) point out vulnerabilities of the cryptosystem, and (ii) develop its variants. Although there have been many variants of the RSA, cryptanalysis on those has not attracted many researchers as compared to the original RSA. We recall some remarkable results in cryptanalysing on low private exponent RSA in Section 2 after recalling the original RSA cryptosystem. In Section 3, we give an answer for the question why RSA variants are built on platform other than [Z.sub.n]. Section IV devotes for an algebraic structure of RSA, we also show in this Section all known RSA cryptosystems having this algebraic structure. The usefulness of the structure is then made clear in Section V, where we recall the construction of Bergman ring based RSA. A slight comparison between known RSAs in Section 4 can help answer the question why the original RSA is preferred over its variants.

2. RSA and cryptanalysis on the RSA cryptosystem

2.1. The original RSA cryptosystem

For the convenience of the reader, we briefly describe the original RSA cryptosystem in the form of a theorem. The proof of this theorem and its working can be found in [1].

Theorem 2.1 Given p and q as two distinct primes. Let n = p q, [phi] (n) = (p - 1) (q - 1), and e,d be two integers such that ed [equivalent to] 1 (mod [phi] (n)). Then, for all m [member of] [Z.sub.n], we have [m.sup.ed] [equivalent to] m (mod n).

This theorem ensures the encryption and decryption phases in the RSA cryptosystem as follows: a plaintext is encrypted by computing and is in turn decrypted by calculating [c.sup.d] [equivalent to] m (mod n).

2.2. Attacks on RSA

Although there has been no polynomial time algorithm for factoring an integer n into product of primes so far, there have been many attacks on the original RSA scheme. By considering the continued fraction expansion of e/n, Wiener showed in [2] that one can recover d for the case when d < [1/3] [n.sup.1/4]. A better result was considered by Boneh and Durfee [3] for the case when d < [n.sup.0.292]. In such a case, by solving the small inverse problem, can be recovered. Lattice reduced algorithms, such as Gaussian or LLL algorithms can also be applied to recover in some cases of low exponent private key [4]. However, so far, no devastating attack has ever been found.

A common attack on RSA is factoring the modulus n. Knowing n = pq, an attacker can calculate [phi](n) = (p - 1) (q - 1) and then find the private key d = [e.sup.-1] (mod [phi](n)). Factoring modulus n in the case p, q being weak primes was considered by A. Nitaj and T. Rachidi [5]. Currently, the fastest algorithm for the factoring a whole number n is the General Number Field Sieve algorithm [6], which has a complexity of exp (( 3[square root of (64/9)] + O(1)) [(ln n).sup.1/3] [(ln ln n).sup.2/3]).

3. RSA variants

If is a positive integer and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [p.sub.1], [p.sub.2], ..., [p.sub.k] are distinct prime numbers and [r.sub.i] [member of] Z (i = 1, 2, ..., k), then we denote rad (n) = [p.sub.1][p.sub.2] ... [p.sub.k]. Apparently, the original RSA scheme still holds when n = rad (n)[7]. We first prove that is the only form of n under that an RSA encryption scheme can be applied to all messages belonging to [Z.sub.n].

Proposition 3.1 Suppose that there exists a natural number k [not equal to] 1 such that the map

F: [Z.sub.n] [right arrow] [Z.sub.n] x [??] [x.sup.k]

is a bijection. Then, n = rad (n).

Proof.

Suppose that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [p.sub.1], [p.sub.2], ..., [p.sub.k] are distinct prime numbers and assume the contrary that n [not equal to] rad (n), then at least one of [r.sub.1], [r.sub.2], ..., [r.sub.k] is larger than 1. Without loss of generality, we can assume [r.sub.1] > 1. Considering [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], it is obvious that x [not equal to] 0. Since k [greater than or equal to] 2, then k([r.sub.1] - 1). It follows that F(x) = [x.sup.k] = 0, which contradicts the bijection of F.

Proposition 3.1 explains the reason for the two trends in developing RSA variants. For the first trend, the RSA cryptosystems are developed on the ring [Z.sub.n]. For RSA cryptosystems where the modulus is the product of distinct primes, some additional algorithms are applied to speed up the decryption or encryption process in the cryptosystem. The Batch RSA [8], Multi Prime RSA [7], DRSA [9] are examples of such cryptosystems. For RSA cryptosystems where the modulus is not a product of distinct primes, the space of plaintexts must be reduced to a subset of [Z.sub.n] instead of the entire [Z.sub.n]. For example, in the MultiPower RSA cryptosystem [10], the modulus n has the form n = [p.sup.k]q with k [member of] Z, k [greater than or equal to] 2, where p, q are distinct primes and the space of plaintexts is the reduced residue group modulo n. This RSA variant was then combined with DRSA to increase the encryption verification performance [11-12]. Attacking to these RSA variants has been concerned by many authors, we refer the reader to [13-14] for cryptanalysing on MultiPower RSA.

In the second trend, platforms other than [Z.sub.n] should be chosen for plaintexts. So far, there have been many variants of RSA constructed in this manner: In 1985, Varadharajan and Odoni constructed an extension of RSA to matrix rings [15]; In 1993, Demytko, proposed an elliptic curve-based RSA variant at EUROCRYPT [16]; In 2004, El-Kassar, Hatary, and Awad developed a modified RSA in the domains of Gaussian integers and polynomials over finite fields [17]. The critical equality [m.sup.ed] = m in those cryptosystems was obtained using different methods depending on the platforms. Here, we concentrate on an abstract model by proposing a semigroup platform together with conditions that ensure equality and then show that the model will cover all mentioned RSA cryptosystems.

From now on, if * is a binary operation on a set X, k is a positive integer, and x [member of] X, then we denote [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by ([*.sub.k])x.

4. Generic RSA scheme

4.1 A generic model for RSA

Let Y be a nonempty set and * be a binary operation on Y such that (Y, *) is a semigroup, and suppose that X [subset] Y is a set of plaintexts. The equation [m.sup.ed] = m for all m [member of] X is a basic equation in RSA cryptosystems. We propose some conditions for establishing this equation as follows.

Proposition 4.1 Let Y, U, V be multiplicative semigroups, X be a nonempty subset of Y, and [mu]: Y [right arrow] U, [eta]: Y [right arrow] V be two homomorphisms. Suppose that

(i) There exist groups [U.sub.1] [subset] U, [U.sub.2] [subset] U and [V.sub.1] [subset] V, [V.sub.2] [subset] V such that [mu](X) [subset] ([U.sub.1] [union] [U.sub.2]) and [eta](X) [subset] ([V.sub.1] [union] [V.sub.2]).

(ii) The map [theta]: Y [right arrow] U x V defined by [theta](x) = ([mu](x), [eta](x)) is an injective.

Let [N.sub.i], [absolute value of [U.sub.i]], [M.sub.i] = [absolute value of ([V.sub.i])] (i = 1,2) L = lcm ([N.sub.1], [N.sub.2], [M.sub.1], [M.sub.2]) and 3, d be two chosen integers such that cd (e, L) = 1 and ed [equivalent to] 1 (mod L). Then, we have [x.sup.ed] = x for all x [member of] X.

Proof. Assume that x [member of] X.

For x [member of] X, since [mu](X) [subset] ([U.sub.1] [union] [U.sub.2]) and [U.sub.1], [U.sub.2] are groups, then [([mu] (x)).sup.i] = [mu](x) for all integers i satisfying i [equivalent to] 1 (mod lcm ([N.sub.1], [N.sub.2])). This implies that [([mu] (x)).sup.ed] = [mu] (x). As [mu] is a homomorphism, [mu]([x.sup.ed]) = [(u(x)).sup.ed] = [mu](x).

Similarly, we have [([eta] (x)).sup.ed] = [eta] (x).

Since [mu]([x.sup.ed]) = [mu](x) and [eta]([x.sup.ed]), then [theta]([x.sup.ed]) = [theta](x). Therefore, [x.sup.ed] = x as [theta] is an injective.

Using the symbols and hypothesis as in the above theorem, we propose a generic model for an RSA cryptosystem as follows.

The generic RSA cryptosystem

Key creation

--Choose e satisfying 1 < e <L and gcd (e, L) = 1.

--Find d = [e.sup.-1] (mod L).

--Publish e as public key and keep d as private key.

Encryption

--A plaintext m [member of] X is encrypted by calculating c = [m.sup.e].

Decryption

--Ciphertext c is then decrypted by calculating [c.sup.d] = m.

From now on, if Y is a ring and x [member of] Y, we write <x> for the ideal of Y generated by x and write Y/<x> for the quotient ring of Y by <x>. Next, we show that our proposed model can cover all known RSA variants.

4.2 The original RSA

Consider the ring Y = [Z.sub.n], where pq is the product of two distinct primes p, q and X = Y. Since the ring isomorphism [Z.sub.n] [congruent to] [Z.sub.p] x [Z.sub.q], the projectors [mu], [eta] from Y to U = [Z.sub.p] and V = [Z.sub.q] satisfy the hypothesis in Proposition 4.1. Therefore, the equation [m.sub.ed] = m holds for all m [member of] X = [Z.sub.n], where e, d are integers that satisfy ed [equivalent to] 1 (mod L). In this case, we choose

[U.sub.1] = {0}, [U.sub.2] = [Z.sub.p]\{0}, [V.sub.1] = {0}, [V.sub.2] = [Z.sub.q]\{0},

then

[N.sub.1] = [absolute value of [U.sub.1]] = 1, [N.sub.2] = [absolute value of [U.sub.2]] = p - 1,

[M.sub.1] = [absolute value of [V.sub.1]], [M.sub.2] = [absolute value of [V.sub.2]] = q - 1,

L = lcm (p - 1, q - 1).

We achieve the original RSA cryptosystem.

4.3 The RSA on the quotient rings of polynomials

The ring of polynomials [Z.sub.p][x] is considered in this instance, where p is a prime number. Similar to the original RSA, let g(x), h(x) [member of] [Z.sub.p][x] be irreducible polynomials having degree r, s and f (x) = g(x). h(x) Consequently, the number of invertible elements in [Z.sub.p][x]/ <g(x)>, [Z.sub.p][x]/ <h(x)> and [Z.sub.p][x]/<f(x)> is [p.sup.r] - 1, [p.sup.s] - 1 and L = ([p.sup.r] - 1)([p.sup.s] - 1), respectively. Therefore, m[(x).sup.ed] = m(x) holds for all m(x) [member of] [Z.sub.p][x]/<f(x)>, where e,d are integers chosen such that gcd(e, L) = 1 and ed [equivalent to] 1(mod L.). The equation m[(x).sup.ed] = m(x) ensures the encryption c(x) = [(m(x)).sup.e] and decryption [(c(x)).sup.d] = m(x). The RSA on the quotient rings of polynomials can be regarded as an instance of the proposed model mentioned in Section 4.1 where

Y = X = [Z.sub.p][x] I <f (x)>,

U = [Z.sub.p][x] /<g(x)>, V = [Z.sub.p][x] / <h (x)>,

[U.sub.1] = {0}, [U.sub.2] = U\[U.sub.1], [V.sub.1] = {0}, [V.sub.2] = V\[V.sub.1].

[N.sub.1] = [absolute value of [U.sub.1]] = 1, [N.sub.2] = [absolute value of [U.sub.2]] = [p.sup.r] - 1,

[M.sub.1] = [absolute value of [V.sub.1]] = 1, [M.sub.2] = [absolute value of [V.sub.2]] = [p.sup.s] - 1,

and [mu]. [eta] are projectors from [Z.sub.p][x]/<f(x)> onto [Z.sub.p][x]/<g(x)>, [Z.sub.p][x]/<h(x)> respectively.

4.4 The RSA on the quotient ring of Gaussian integers

The Gaussian ring is defined by Z[i] = {a + bi: a, b [member of] Z} with common addition and multiplication. The norm on Z[i] is given by [delta](a + bi) = [a.sup.2] + [b.sup.2]. Euclidean division is valid on Z[i]; hence, Z[i] is an Euclidean ring. All units in Z[i] are 1, -1, i, -i. Euclidean division gives rise to the concept of primes in Z[i]. A number x [member of] L[i] is prime in Z[i] if and only if x is a unit multiplied by one of the following:

(i) 1 + i,

(ii) a prime number p [member of] L, where p [equivalent to] 3 (mod 4), or

(iii) u + vi [member of] Z[i], where q = [u.sup.2] + [v.sup.2] is a prime in Z with q [equivalent to] 1 (mod 4).

A prime x [member of] Z[i] is called type [alpha], type p, or type [pi] corresponding to cases (i), (ii), and (iii), respectively.

The Euler's Phi function [PHI]: Z[i] \ {0} [right arrow] N is a function in which for all x [member of] Z[i] \ {0}, [PHI](x) is the number of invertible elements in the quotient ring Z[i] / <x>. Then, for prime element x [member of] Z[i], we have [PHI](x) = [delta](x) [18].

Let [beta], [gamma] be two prime elements in Z[i] and [eta] = [beta].[gamma], then [PHI]([eta]) = [PHI]([beta]). [PHI]([gamma]). The equation [m.sup.ed] = m holds for all m [member of] Z[i]/<[eta]>, where e,d are integers chosen such that gcd (e, [PHI], ([eta])) = 1 and ed [equivalent to] 1 (mod [PHI]([eta])). This ensures the encryption c = [m.sup.e] and decryption [c.sup.d] = m for all plaintext m [member of] Z[i]/<[eta]>.

The RSA on the quotient ring of Gaussian integers can be regarded as an instance of the proposed model described in Section 4.1 where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and [mu], [eta] are projectors from Y = Z[i]/<[eta]> to U = Z[i]/<[beta]> and V = Z[i]/<[gamma]>, respectively.

4.5 The RSA on the ring of matrices

Let p, q be two prime numbers, n = pq, and l be a positive integer. Let [M.sub.l](p), [M.sub.l](q), and [M.sub.l](n) denote the multiplicative groups of all non-singular l X l matrices having elements in [Z.sub.p], [Z.sub.q], and [Z.sub.n], respectively. The orders [N.sub.p], [N.sub.q], and [N.sub.n] of these groups can be shown by

[N.sub.p] = ([p.sup.l] - 1)([p.sup.l] - p) ... ([p.sup.l] - [p.sup.l-1]), (1)

[N.sub.q] = ([q.sup.l] - 1)([q.sup.l] - q) ... ([q.sup.l] - [q.sup.l-1]), (2)

and

[N.sub.n] = [N.sub.p][N.sub.q], (3)

respectively.

Choose two positive integers e, d satisfying gcd (e, [N.sub.n]) = 1 and ed [equivalent to] 1 (mod [N.sub.n]). The Lagrange theorem in group theorem implies that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [I.sub.n] denotes the unit matrix in [M.sub.l](n); hence, [m.sup.ed] = m for all m [member of] [M.sub.l] (n). This ensures the encryption c = [m.sup.e] and decryption [c.sup.d] = m for all plaintext m [member of] [M.sub.l](n). Since [M.sub.l](n) [equivalent to] [M.sub.l](p) X [M.sub.l](q), the RSA variant on the ring of matrices is an instance of the model described in Section 3.1 where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and [mu], [eta] are projectors from [M.sub.l](n) to [M.sub.l](p) and [M.sub.l](q), respectively.

4.6 The RSA on the elliptic curve group

Let p > 3 be a prime, and let a, b be integers chosen such that 4 [a.sup.3] + 27 [b.sup.2] [not equivalent to] 0 (mod p). The elliptic curve group modulo p, denoted by [E.sub.p] (a, b), is a set of all pairs (x, y) [member of] [Z.sub.p] x [Z.sub.p] satisfying [y.sup.2] = [x.sup.3] + ax + b on [Z.sub.p], together with an element denoted [infinity]. The operation + on [E.sub.p](a, b) is defined such that [infinity] is the identity element and for two points P([x.sub.1], [y.sub.1]), Q([x.sub.2], [y.sub.2]) [member of] [E.sub.p] (a, b), the result R([x.sub.3], [y.sub.3]) = P + Q is determined as follows:

--If Q = [infinity], then P + Q = Q + P = P.

--If [x.sub.1] = [x.sub.2] and [y.sub.1] = -[y.sub.2], then P + Q = [infinity].

--Otherwise, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

A complementary elliptic curve group, denoted by [bar.[E.sub.p] (a, b)], is a set of all pairs (x,y) [member of] [Z.sub.p] x [Z.sub.p] satisfying [y.sup.2] + [x.sup.3] + ax + b, together with an element denoted [infinity]; however, y is of the form y = u[square root of (v)], where u, v [member of] [Z.sub.p] and v is a fixed quadratic non-residue. The operation + on [bar. [E.sub.p](a,b)] is identically defined to that on [E.sub.p](a, b). The orders of [E.sub.p](a,b) and [bar.[E.sub.p](a,b)] are denoted by [absolute value of ([E.sub.p](a,b))] and [absolute value of ([bar.[E.sub.p] (a,b)])], respectively. These numbers can be found by some polynomial time algorithms, for example, the algorithm considered in [19].

For RSA on the elliptic group, we choose two distinct primes p,q and let n = pq. Select two integers a,b such that gcd (4[a.sup.3] + 27[b.sup.2], n) = 1. Denote [N.sub.1] = [absolute value of ([E.sub.p](a,b))], [N.sub.2] = [absolute value of ([bar.[E.sub.p](a,b)])], [M.sub.1] = [absolute value of ([E.sub.q](a,b))], [M.sub.2] = [absolute value of ([bar.[E.sup.q](a,b)])], and L = [N.sub.1][N.sub.2][M.sub.1][M.sub.2].

Choose two integers e, d such that ed [equivalent to] 1 (mod L), then the equation ([+.sub.ed]) (x, y) = (x, y) holds for all x [member of] [Z.sub.n] and y = [square root of ([x.sup.3] + ax + b)]. This equation ensures the encryption and decryption as in the original RSA.

We can apply the proposed model to this instance of RSA. Indeed, suppose that [v.sub.p] and [v.sub.q] are generators of multiplicative groups [Z.sup.*.sub.p] and [Z.sup.*.sub.q], respectively. Then, [bar.[E.sub.p] (a, b)] = {u[square root of ([v.sub.p])]: u [member of] [Z.sub.p]} and [bar.[E.sub.q](a, b)] {u[square root of ([v.sub.q]))] u [member of] [Z.sub.q]} are complementary elliptic groups of [E.sub.p](a, b) and [E.sub.q](a,b), respectively. Denote by [w.sub.1], [w.sub.2] and [w.sub.3] elements in [Z.sub.n] such that

[w.sub.1] [equivalent to] 1 (mod p), [w.sub.1] [equivalent to] [v.sub.q](mod q),

[w.sub.2] [equivalent to] [v.sub.p](mod p), [w.sub.1] [equivalent to] 1(mod q),

and

[w.sub.3] [equivalent to] [v.sub.p](mod p), [w.sub.1] [equivalent to] [v.sub.q](mod q).

Then, for each x [member of] [Z.sub.n], one and only one of the following cases occurs:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Therefore, if we define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

then for each x [member of] [Z.sub.n], there exists exactly one of the above sets containing an element with the first coordinate x.

It is well known that we can define a operation + on [E.sub.n](a, b) = [E.sup.11.sub.n] and [E.sub.n] (a, b) [congruent to] [E.sub.p] (a, b) x [E.sub.q](a, b). Therefore, two projectors [mu]: [E.sup.11.sub.n] [right arrow] [E.sub.p](a, b) and [eta]: [E.sup.11.sub.n] [right arrow] [E.sub.q] (a,b) are homomorphisms. Proposition 3.2 ensures that ([+.sub.ed])(x, y) = (x, y) for all (x, y) [member of] [E.sup.11.sub.n], where e, d are integers satisfying ed [equivalent to] 1 (mod [L.sub.11]) with [L.sub.11] = lcm ([N.sub.1], [M.sub.1]).

Similar to the operation + on [E.sub.n] (a, b) = [E.sup.11.sub.n], we can define a binary operations + on [E.sup.12.sub.n], [E.sup.21.sub.n], and [E.sup.22.sub.n] such that these sets become groups and

[E.sup.12.sub.n] [congruent to] [E.sub.p] (a, b) x [bar.[E.sub.q](a,b)],

[E.sup.21.sub.n] [congruent to] [bar.[E.sub.p]] (a, b) x [E.sub.q](a,b),

[E.sup.22.sub.n] [congruent to] [bar.[E.sub.p]] (a, b) x [bar.[E.sub.q](a,b)],

Proposition 4.1 ensures the equation ([+.sub.ed]) (x, y) = (x, y) for all (x, y) [member of] [E.sup.ij.sub.n] (i, j = 1, 2) if e, d satisfy ed [equivalent to] 1(mod [L.sub.ij]) with [L.sub.ij] = lcm([N.sub.i], [M.sub.j]). In other words, the proposed model is applied to each group [E.sup.ij.sub.n](i, j = 1, 2) separately.

Because the operators + on [E.sup.ij.sub.n] (i, j = 1, 2) are defined in a similar way, the first coordinates [x.sub.k] in the equation ([x.sub.k], [y.sub.k]) = ([+.sub.k])(x, y) are the same, and they do not depend on i, j, where (x, y) [member of] [E.sup.ij.sub.n]. Demytko [16] gave a formula for [x.sub.k] by setting [x.sub.i] = [X.sub.i]/[Z.sub.i], y = [Y.sup.i]/[Z.sub.i] in homogenous coordinates:

[X.sub.2i] = [([X.sup.2.sub.i] - a[Z.sup.2.sub.i]).sup.2] - 8b[X.sub.i][Z.sup.3.sub.i](mod n), (4)

[Z.sub.2i] = 4[Z.sub.i]([X.sup.3.sub.i] + a[X.sub.i][Z.sup.2.sub.i] + b[Z.sup.3.sub.i]) (mod n), (5)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (6)

[Z.sub.2i+1] = Z[([X.sub.i][Z.sub.i+1] - [X.sub.i+1] [Z.sub.i]).sup.2] (mod n), (7)

[x.sub.i] = [x.sub.i]/[z.sub.i]. (8)

4.7 Comparison

Since there are many time polynomial algorithms (e.g., Berlekamp [20], Ben-Or [21], and Cantor-Zassenhaus [22]) for factoring a polynomial f (x) [member of] [Z.sub.p][x] into the product of irreducible polynomials, the RSA cryptosystem on the quotient ring of polynomials can be easily broken using these algorithms.

We compare the security among RSAs by evaluating the complexity of the brute-force algorithm for factoring the modulus n. For simplicity, we assume that the length of each plaintext is 1024 bits.

Table 1 shows the lengths of modulus as well as the number of operations involved in encryption processes in original RSA and those in its variants, where e is the public key.

For the original RSA cryptosystem, because a plaintext m [member of] [Z.sub.n] has a length of bits, the modulus n must have the same length as m. Therefore, the algorithm for factoring n is applied for a 1024-bit number.

For the RSA cryptosystem on the quotient ring of Gaussian integers, a plaintext m = a + bi has a length of bits, and therefore, both a and b have a length of bits 512. Thus, the length of the value [delta](m) = [a.sup.2] + [b.sup.2] does not exceed 1025 bits. Because m [member of] Z[i]/ <[eta]>, [delta]([eta]) must have a length less than 1 0 2 5 bits. Hence, the length of modulus [eta] is 512 bits. Factoring a 512-bit number [eta] may be simpler than the case for the original RSA.

For the RSA on the ring of matrix, one can determine by factoring. Hence, we calculate [N.sub.p], [N.sub.q] by (1), (2), respectively, and then [N.sub.n] by (3). Then, the private key d can be calculated from these values. Suppose that l [greater than or equal to] 2, then a plaintext m [member of] [M.sub.l](n) is a matrix having at least four elements. Because m has a length of 1024 bits, each of its four elements must be 256 bits. Since each element belongs to [Z.sub.n], must be bits. Factoring in this case is simpler than that in the original RSA.

In both the original RSA and the RSA on the elliptic curve group, each plaintext element x [member of] [Z.sub.n] has the same bit length as modulus n. However, the encryption and decryption in RSA on the elliptic curve group requires more operations than those in the original RSA. In the original RSA, encrypting c [equivalent to] [m.sup.e](mod n) requires 2[log.sub.2]e multiplications using a fast power algorithm. The numbers of operations in (4), (5), (6), and (7) are 11, 12, 21, and 5, respectively. Therefore, for the RSA on the elliptic curve group, the number of operations for encrypting a plaintext to cipher text using the equation ([+.sub.e])(x,y) = (s,t) requires at least 5[log.sub.2]e multiplications.

In our cryptosystem mentioned in the next Section, a plaintext m is a matrix having four elements. Because m has a length of 1024 bits, each of its four elements must be 2 5 6 bits. Since each element belongs to [Z.sub.n], n must be 256 bits. Factoring n in this case is simpler than that in the original RSA.

The above argument shows that, for the same length of the modulus, the lengths of plaintexts and cipher texts in original RSA cryptosystems are shorter than those in its variants. This partially explains why the original RSA cryptosystem is more widely used compared to other RSA variants.

5. A new variant of RSA: probability RSA

Based on the proposed scheme, we developed a Bergman ring based cryptosystem analogue of RSA. We briefly describe this cryptosystem as follows.

Bergman [23] established that End [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a semilocal ring with [p.sup.5] elements, where p is a prime. Climent et al. [24] identified the elements of this ring as 2x2 matrices that form the ring

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The multiplication and addition operations on this ring are defined as follows:

if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now, let p, q be two distinct primes and n = pq. We denote

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

It is easy to verify that the multiplication defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is a binary operation on [E.sub.n].

We define the maps [mu]: [E.sub.n] [right arrow] [E.sub.p] and [eta]: [E.sub.n] [right arrow] [E.sub.q] as follows.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and

[d.sub.p] [equivalent to] d (mod [p.sup.2]), [d.sub.q] [equivalent to] d(mod [q.sup.2]) .

Then, we can prove the following propositions.

Proposition 5.1 [mu] and [eta] are homomorphisms and the map [theta]: [E.sub.n] [right arrow] [E.sub.p] x [E.sub.q] defined by [theta](x) = ([mu] (x), [eta] (x)) is an injective.

We denote by [E.sup.*.sub.p] and [E.sup.*.sub.q] the set of all invertible elements in [E.sub.p] and [E.sub.q], respectively. Further, [E.sup.*.sub.p] and [E.sup.*.sub.p] are multiplicative groups with orders [p.sup.3][(p - 1).sup.2] and [q.sup.3][(q - 1).sup.2], respectively [24]. Applying the model proposed in Section 3.1 where

Y = [E.sub.n], U = [E.sub.p], V = [E.sub.q],

X = {x [member of] Y: [mu](x) [member of] [E.sup.*.sub.p] and [eta](x) [member of] [E.sup.*.sub.q]}, and

[U.sub.1] = [U.sub.2] = [E.sup.*.sub.p], [V.sub.1] = [V.sub.2] = [E.sup.*.sub.q],

the equality [m.sup.ed] = m holds for all m [member of] X if e, d satisfy ed [equivalent to] 1(mod L) with L = lcm ([p.sup.3][(p-1).sup.2]), [q.sup.3][(q - 1).sup.2]). Therefore, we can construct the cryptosystem analogue of RSA. The details and the cryptanalysis of this cryptosystem were discussed in [25].

6. Conclusions

The equality [m.sup.ed] = m plays an important role in a RSA cryptosystem, it ensures encryption and decryption phases in the cryptosystem. The paper has proposed a algebraic structure, or a scheme, for constructing a RSA cryptosystem by proposing conditions which ensure that equality on a semigroup. Applying this scheme, the equalities in known RSAs are then established by unischeme, despite of the RSA platforms being quotient rings or groups. The usefulness of the proposed scheme is proved when constructing Bergman ring based RSA, which follows the proposed scheme and has some advantages compared to the original RSA. One may ask whether the proposed scheme will be applied for a future RSA variant. The answer is yes if that RSA variant built on a commutative group; we will look more closely at the answer in another article.

This work was supported by the Funding VNU-HCMC, Vietnam (B2012-18-02TD, Design and Implementation of FPGA-cryptography IP Cores). This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2012R1A1A2007014)

http://dx.doi.org/ 10.3837/tils.2016.06.021

References

[1] R.L.Rivest, A.Shamir, and L.M.Adleman, "A method for obtaining digital signatures and public key cryptosystems," Communications of the ACM 21 (1978), no 2, 120-126. Article (CrossRef Link)

[2] M.Wiener, "Cryptanalysis of short RSA secret exponents," IEEE Transactions on Information Theory, 36:553-558, 1990. Article (CrossRef Link)

[3] D. Boneh and G. Durfee, Cryptanalysis of RSA with private key less than , Eurocrypt'99. Article (CrossRef Link)

[4] C.Coupe, P.Nguyen, and J.Stern, "The effectiveness of lattice attacks against low-exponent RSA," Public Key Cryptography '99. Article (CrossRef Link)

[5] A. Nitaj and T. Rachidi, "Factoring RSA moduli with weak prime Factors, Codes," in Proc. of Cryptology and Information Security Conference, C2SI 2015, LNCS 9084, pp. 361-374, 2015. Article (CrossRef Link)

[6] A.K. Lenstra and J.H.W.Lenstra, "The development of the number field sieve," Lecture Notes in Mathematics, vol. 1554, Springer-Verlag, Berlin, 1993. Article (CrossRef Link)

[7] T. Collins, D. Hopkins, S. Langford, and M. Sabin, "Public Key Cryptographic Apparatus and Method," US Patent 5, 848, 159. Jan.1997.

[8] A. Fiat, "Batch RSA," Advances in Cryptology, Crypto'89, Vol. 435, pp. 175-185, 1989. Article (CrossRef Link)

[9] D. Pointcheval, "New public key cryptosystem based on the dependent RSA problem," Eurocrypt'99 LNCS Springer-Verlag, vol. 1592, pp. 239-254, 1999. Article (CrossRef Link)

[10] T. Takagi, "Fast RSA - Type Cryptosystem Modulo ," Crypto'98, 1462 of LNCS, 1998, pp. 318-326, 1998. Article (CrossRef Link)

[11] Garg D. and Verma S., "Improvement over Public key Cryptographic Algorithm," in Proc. of Advance Computing Conference, 2009, IACC 2009, IEEE International Conference, March 2009, pp. 734-739. Article (CrossRef Link)

[12] Garg D. and Verma S., "Improvement in RSA Cryptosystem," Journal of Advances in Information Technology, vol. 2, no. 3, August 2011. Article (CrossRef Link)

[13] M.F. Esgin, M.S. Kiraz, and O. Uzunkol, "A new partial key exposure attack on MultiPower RSA," in Proc. of 6th International Conference on Algebraic Information (CAI 2015). Article (CrossRef Link)

[14] A. Nitaj and T. Rachidi, "New attacks on RSA with moduli ," C2SI 2015, LNCS 9084, pp. 352-360, 2015. Article (CrossRef Link)

[15] Varadharajan V. and Odoni R., "Extension of RSA cryptosystems to matrix rings," Cryptologia, 9:2, 140-153, 1985. Article (CrossRef Link)

[16] N. Demytko, "A new elliptic curve based analogue of RSA," EUROCRYPT'93, LNCS 765 40-49 (1993). Article (CrossRef Link)

[17] El-Kassar, A.N., R. Hatary and Y. Awad, "Modified RSA in the domains of Gaussian integers and polynomials over finite fields," in Proc. of Intl. Conf. Computer Science, Software Engineering, Information Technology, e-Business and Applications (CSITeA'04), Cairo, Egypt.

[18] James.T. Cross, "The Euler -function in the Gaussian integers," The American Mathematical Monthly, vol. 90, no. 8, pp. 518-528, Oct., 1983. Article (CrossRef Link)

[19] R.Schoof, Elliptic curves over finite fields and the computation of square roots mod p,Mathematics of Computation, vol. 44, no. 170, pp 483-494. Article (CrossRef Link)

[20] Lindsay N. Childs, "A concrete introduction to higher algebra," Third Edition, Springer Science + Business Media LLC, pp. 543-552, 2009. Article (CrossRef Link)

[21] M. Ben-Or, "Probabilistic algorithms in finite fields," in Proc. of 22nd Annual Symposium on Foundations of Computer Science, 394-398, 1981. Article (CrossRef Link)

[22] Victor Shoup, "A computational introduction to number theory and algebra," Cambridge University Press, pp.530-538, 2008.

[23] Bergman G.M., Examples in PI ring theory, Israel J. Math. 18, 257-277, 1974. Article (CrossRef Link)

[24] Joan-Josep Climent, Pedro R. Navarro, and Leandro Tortosa, "On the arithmetic of the endomorphisms ring ," AAECC, 2011. Article (CrossRef Link)

[25] Long T.D., Thu D.T. and Thuc D.N., "A Bergman ring based cryptosystem analogue of RSA," ICITCS 2013 eBook, Macau, Dec., 2013, pp. 377-380. Article (CrossRef Link)

Dr. TRAN Dinh Long is lecturer at Hue University. His research focus on Cryptography and Applied Mathematics.

Dan-Thu Tran is Dean of the Faculty of Information Technology, University of Science, Vietnam National University - Ho Chi Minh city, Vietnam. His research focus on Combinatorics, Algebra and Cryptography. He obtained his Ph.D. in computer science from National Polytechnical Institute of Toulouse, France in 2001.

Deokjai Choi, Ph. D is a professor of School of Electronics and Computer Engineering, Chonnam National University, Korea. He got PhD degree in Computer Science and Telecommunication Program, University of Missouri-Kansas City, USA in 1995. His research interests are context awareness, sensor network, future Internet, SDN.

Dr. NGUYEN Dinh Thuc is professor at School of Information Technology, University of Science, Vietnam National University of Ho Chi Minh City. His research focus on Applied Cryptography, Information Security and Database Security.

Long D. Tran (1), Thu D. Tran (2), Deokjai Choi (3) and Thuc D. Nguyen (2)

(1) Hue University of Science 77 Nguyen Hue, Hue, Vietnam [email: trandinhlong1963@yahoo.com.vn]

(2) University of Science 227 Nguyen Van Cu, District 5, HCMC, Vietnam [email: tdthu@fit.hcmus.edu.vn,ndthuc@fit.hcmus.edu.vn]

(3) School of Electrical and Computer Engineering, Chonnam National University 77 Yongbong-ro, Buk-gu, Gwangju 500-757, Korea [e-mail: dchoi@jnu.ac.kr]

* Corresponding author: Deokjai Choi

Received April 23, 2015; revised July 17, 2015; re-vised January 16, 2016; accepted April 7, 2016; published June 30, 2016
Table 1. Lengths of modulus and number of operations involved in
RSAs cryptosystem

                                 Length of     Least number
                                 the modulus   of operations

Original RSA                        1024        [log.sub.2]e
RSA on the quotient ring of          512       6[log.sub/2]e
  Gauss integers
RSA on the group of matrix           256       12[log.sub.2]e
RSAon the elliptic curve group      1024       5[log.sub.2]e
Bergman ring based RSA               256       12[log.sub.2]e
COPYRIGHT 2016 KSII, the Korean Society for Internet Information
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Tran, Long D.; Tran, Thu D.; Choi, Deokjai; Nguyen, Thuc D.
Publication:KSII Transactions on Internet and Information Systems
Article Type:Report
Date:Jun 1, 2016
Words:6127
Previous Article:Reversible data hiding in block truncation coding compressed images using quantization level swapping and shifting.
Next Article:A scalable data integrity mechanism based on provable data possession and JARs.
Topics:

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |