RSA AND ABES-ARM METHODS FOR PERFORMANCE ENHANCEMENT

Formatted Text:

REVIEW: RSA AND ABES-ARM METHODS FOR PERFORMANCE
ENHANCEMENT
Rahul Yadav Ashwin Perti
Department of Information Technology, Department of Information Technology,
Academy of Business and Engineering Sciences, Academy of Business and Engineering Sciences,
Ghaziabad, India; Ghaziabad, India;
E-mail: rexingrahul@gmail.com E-mail: ashwinperti@abes.ac.in
Mohammad Tausif
Department of Indesign RnD
Thomson Digital Press
Noida, India
E-mail: mohdtausif20@gmail.com
Abstract: An encryption method and modifications to
the existing algorithms are presented in order to
enhance the performance and security of the RSA
cryptosystem. The method presented here is capable
and efficient for each such block value of a message
where bit count of message and publish divisor are
same, and the numerical value of message is greater
than publish divisor, this have following important
consequence: enciphering and deciphering of each
block of message require a number of exhaustive
operations, so we proposed solution to those
considerations.
A message M is encrypted into a cipher pair by
representing it in two numbers by using number theory
(not in two sub-blocks), different operations are
performed over each number.
Modifications proposed for the key generation
ensures maximum key space, rapid key generation and
enhances security from a new dimension of discovered
threat.
Key Words and Phrases: Public-key cryptosystems,
cryptography, unconcealed key(s), ambiguity, Bézout's
identity.
I. Introduction
In the history of cryptology up to 1975, all
cryptosystems required the sender and the receiver to
agree beforehand on the same key, a key that had to be
rigorously protected from exposure to an adversary. In
1976, Martin Hellman, a professor at Stanford
University and Whitfield Diffie, a graduate student,
introduced the concept of public key cryptography. In
August 1977 the RSA public key cryptosystem [1] was
introduced in Martin Gardner’s column on
Mathematical Games in Scientific American. The RSA
cryptosystem has survived over thirty one years of
study by cryptanalysts in the public sector, but there are
also dimensions in the basic concepts of RSA
cryptosystem which are yet to be disclosed in order to
make RSA more efficient and secure in implementation
prospective.
In subsequent text we will discuss some of the problems
and limitations associated with RSA cryptosystem, but
first let’s have a brief of the RSA cryptosystem. There
are three stages of RSA operations named Key
Generation, Encryption and Decryption Process. In the
Key Generation step we first choose two distinct large
prime numbers namely p and q, multiplying both the
numbers gives publish divisor n, another value φ(n)
known as Eulars totient function of n is calculated as
φ(n) = (p - 1) * (q - 1). Then we choose public exponent
e, such number which is relatively prime to φ(n).
Private exponent d is calculated by using the
congruence modulo relation which is notated as
[e * d = 1 mod φ(n)],
and d is said to be multiplicative inverse of e in the ring
of positive integers Zφ(n). To encrypt lengthy SSL data
we first divide that data into small size of blocks
depends on the size of publish divisor n. A block value
M (Integer representation of data block), is encrypted
into cipher C as
C = Me mod n
and for the purpose of decryption
Cd mod n gives M.
II. Limitations and problems associated with
RSA cryptosystem
Here we are going to discuss the main limitations and
problems which are often encounters while
implementation of RSA cryptosystem and these are just
ignored by taking an alternative patch over the whole
system. The solutions of given list will be discussed in
subsequent sections.
2.1 RSA cryptosystem do not give any method to
encrypt the message block M where M>n, except
dividing M into sub-blocks of size and value less than
n, this result into increased time and space complexity.
For example if we are using a 1024-bit RSA key whose
initials (Hex value) are given as 00:ca:fa:79:98… (an
example sited in Netscape site) now for a 1024-bit M,
whose initials (Hex value) are given as
2a:5b:57:4d:26…, The message M is of the same size as
n, but due to the fact that M>n, and RSA cryptosystem
is not applicable for M>n, we need to divide M into two
sub-blocks which doubles the complexity, and half the
performance of the system in the case.
2.2 A huge key space of RSA cryptosystem gone in
vain due to absence of absolute solution for the
multiplicative inverse problem for the ring of positive
integers. This is due to fact that most widely used
solution for the multiplicative inverse problem,
Extended Euclid algorithm is efficient for the integers
and not for the positive integers. The algorithm returns
the smallest possible integer as multiplicative inverse.
Our observations show in more than 49% cases
algorithm returns a negative integer, which are not
desired. The most accurate method to find
multiplicative inverse, which is given as:
e * d mod φ(n) = 1
or d = (k * φ(n) +1)/e | for some integer value of k
This approach have unnecessory time complexity,
we encounter the value of k lies between 1 to (φ(n) – 2)
for the different values of e and k is maximum (φ(n) –
2) for (e = φ(n) -1). Due to this fact we have to use long
lasting key pairs which is not recommended due to
security resions.
2.3 In some cases we observed exact mapping between
the key pair e and d, saying e = = d, this is not desired
for a public key environment. So we need to find out
the cases where such conditions encounter and its
solution.
III. Extended Euclidean Algorithm
Before heading towards the solutions for the problems
and limitaions discussed in above section let’s have a
breaf look over Extended Euclid algorithm which is
going to be a subject of major discussion in subsequent
sections. The extended Euclidean algorithm is an
extension to the Euclidean algorithm for finding the
greatest common divisor (GCD) of integers a and b: it
also finds the integers x and y in Bézout's identity [4]
ax + by = gcd (a, b)
(Typically either x or y is negative).
The extended Euclidean algorithm is particularly useful
when a and b are coprime, since x is the modular
multiplicative inverse of a modulo b. Here we present
the Iterative textbook version of Extended Euclid
algorithm [3] to find the value
d = b-1 mod m
Extended Euclid [m, b] // m>b
1. (A1, A2, A3) = (1, 0, m); (B1, B2, B3) = (0, 1,
b);
2. if B3 = 0 return A3 = gcd(m, b); no
multiplicative inverse
3. if B3 = 1 return B3 = gcd(m, b); B2 = b-1 mod
m
4. Q = floor(A3 / B3)
5. (T1, T2, T3) = (A1 – QB1, A2 – QB2, A3 –
QB3)
6. (A1, A2, A3) = (B1, B2, B3)
7. (B1, B2, B3) = (T1, T2, T3)
8. goto 2
IV. ABES-ARM variant of RSA for M>n
As in the traditional method of encryption and
decryption using RSA it is considered that RSA
algorithm is efficient for the message M, where 0<M<n,
this is due to the closure property of the Ring of
Integers Zn under the operations multiplication and
residue modulo. Here we have a variant of RSA, which
is capable of encrypting and decrypting the value M,
which lies outside the Zn.
The concept is the simple which preserves the
security of the RSA, and let it retain same as it is with
the message size and value M<n, as the key values
remains same, and we used the value C2 to record the
message variance from the n, and this value C2= floor
(M / n) is only dependent on the value of n, and the
residue r lies in Zn which will be encrypted using
conventional RSA relations, so it cause no security
compromises. The method presented here is capable for
the M>n and it is efficient where size of M is of the
same order as n, for example the method is capable of
encryption and decryption for the values as (n= 187,
M=1 to 999), we will not go further with this approach
for the entire plaintext as it cause the disclosure of the
MSB of plaintext message M when C2 is multiplied by
n. The number of disclosed MSB digits will be same
with count of more digits in M than n. Yet we can apply
the method for the cases as illustrated in section 2.2.
4.1 Encryption Process:
To encrypt M > n, from public key (e, n)
r = M mod n
C1 = re mod n
C2 = (M – r) / n or C2 = floor (M / n)
4.2 Decryption Process:
To decrypt cipher pair (C1, C2), from private key (d, n),
for the message M
M = (C1
d
mod n) + (C2 * n)
4.3 Proof: the underlying Mathematics:
We now prove that equations (1) (2) in subsequent text
hold (that is, that deciphering works correctly if e and d
are chosen as described in section II and will be more
efficient and secure if the concepts on section V and VI
are implemented). Now
D(E(M))
= (C1)d mod n + (C2 * n)
= (re)d mod n + ((M-r)/n) * n
= red mod n + M – r (1)
Now let r is the value of the plaintext used for RSA
cryptosystem encrypted by the public key e and
decrypted by the private key d.
D(E(r)) ≡ (E(r))d ≡ (re)d (mod n) = red (mod n)
E(D(r)) ≡ (D(r))e ≡ (rd)e (mod n) = red (mod n)
And as per the Rich Schroeppel [2] proof of RSA, E
and D are inverse permutations. This yields when the D
is applied on the output value of E, and vise-versa the
resulting value is red (mod n). now when two inverse
permutations E and D are applied on the value r, this
will always result into r, this is equally saying that when
RSA cryptosystem’s operations E and D are applied on
a value r this will result into red (mod n) or r, as it
happens in RSA cryptosystem. This is equally saying
that
red (mod n) = r (2)
now placing the result (2) into (1)
D(E(M))
= (C1)d mod n + (C2 * n)
= (re)d mod n + ((M-r)/n) * n
= red mod n + M – r
= r + M – r
= M
V. Ambiguity in RSA Key generation
5.1. Analysis of the relation d ≡ e-1 mod φ(n)
If we proceed with the congruence relation with the d
and e-1 we may derive the fallowing relations
Given;
d ≡ e-1 mod φ(n)
Implications;
 d ≡ (1/e) mod φ(n)
 d*e ≡ 1 mod φ(n)
 d*e mod φ(n) = 1
 d*e -1 mod φ(n) = 0
 (d*e -1)/ φ(n) = k //for some integer constant k
 d = (k* φ(n) +1)/e (3)
Now both possibilities are there, k may be either
positive or negative. For the positive values of k only,
we can generate decryption key of RSA cryptosystem.
For the negative values again we can generate such
entities which do satisfy the multiplicative inverse
criteria, but we can not use them as the key values for
RSA decryption. Here we encounter the fact that there
exists ambiguity in RSA key generation. This was
clearer when we were able to transform the
multiplicative inverse relation in the form of Bézout's
identity [4].
5.2. Proof of ambiguity:
As in Bézout's identity [4]
ax + by = gcd (a, b)
(Typically either x or y is negative).
A Bézout's identity is the representation of the elements
of a finite field under the multiplicative modulo
operation. We can transform the modular multiplicative
inverse relation used in RSA into Bézout's identity, as:
d ≡ e-1 mod φ(n)
Implications;
 d ≡ (1/e) mod φ(n)
 d*e ≡ 1 mod φ(n)
 d*e mod φ(n) = 1
 d*e -1 mod φ(n) = 0
 (d*e -1)/ φ(n) = k //for some integer constant k
 de = k* φ(n) + 1
 -k* φ(n) + de = 1
now 1 = gcd (φ(n), e)
 -k* φ(n) + de = gcd(φ(n), e) (4)
the above relation (4) is of the form Bézout's identity,
so for positive values of k, d will be negative. A
snapshot of the results of extended euclidean values is
given, as
5.3. Avoiding the ambiguity in RSA key generation
As in the subsequent sections we will discuss method
how to avoid the ambiguity in RSA key generation by
the use of Theory of multiple multiplicative inverses
resides outside the finite field, and will try to find out
the relation between these values, and how they will be
incorporated in Extended Euclid Algorithm so that it
always return a correct positive value. The main
advantage of using only the Extended Euclid algorithm
instead of relation (3), which is given as
d = (k* φ(n) +1)/e
It needlessly requires so long calculation depends on
the values of k, its highest value φ(n)-2 is dependent on
the value of φ(n), and this one is not the case for
Extended Euclid algorithm.
5.4. Resolving Ambiguity by modifying Extended
Euclid algorithm’s return value
5.4.1. Theory of multiple multiplicative inverses resides
outside the ring
As the solution of such kind of ambiguity we have
found a hypothesis and the arithmetic proof of it as
illustrated below;
“For a given value of e and φ(n) we can calculate
multiple values of d such as
1. We get one of it value falls between 2 to φ(n)
which is often used in RSA implementations by the
relation,
d = k* φ(n) +1 (5)
2. For the some cases when we use Euclidean method
to find multiplicative inverse we get a minimal negative
value (d0), for the cases of the negative Euclidean
values if we calculate Least Positive Multiplicative
Inverse value using the relation d = k* φ(n) +1,
We found a relation of the form
d= d0 + φ(n) (6)
We generalized the case and have practical proof as
di+1= di + φ(n) (7)
We will use these results to avoid the ambiguity of RSA
cryptosystem.
5.4.2. Proposed modification in Extended Euclid
algorithm for resolving ambiguity and best suited for
ARM key calculation.
ARM_Euclid(x,y)
{
A1=0, A2=x;
B1=1, B2=y;
while(1)
{
if B2 = 0 then return NO_INVERSE;
if B2 = 1 then
{
return(B1);
}
q=(A3/B3)/1;
T1=A1-(q*B1); if T1<0 then T1=T1+x;
T2=A2-(q*B2); if T2<0 then T2=T2+x;
A1=B1; A2=B2;
B1=T1; B2=T2;
}
}
VI. Unconcealed Keys
In the ring of positive integers less than φ(n) = (p-1) (q-
1) for primes p and q under the operations
multiplication modulo, if we derive a relation between
two integers said (e, d) of the form (the multiplicative
inverse relation).
d ≡ e-1 mod φ(n)
We find a mapping (d= =e) for the exactly seven
values of e, now if we sort these values these will lie in
the ring in fallowing sequence:
1. φ(n)/4 – v
2. φ(n)/4 + v
3. φ(n)/2 -1
4. φ(n)/2 +1
5. 3 *φ(n)/4 – v
6. 3 *φ(n)/4 + v
7. φ(n) -1
(For a fixed number v, randomly dependent on φ(n)).
If we square these values (e) and then decrement the
result by 1, the resulting value (e2-1) will be a multiple
of φ(n), no matter how long φ(n) is, developers can
check the unconcealed results for the long as well as
short values of φ(n).
Example unconcealed keys
n
φ(n)
187
160
209
180
Unconcealed 1 e01 31 19
Unconcealed 2 e02 49 71
Unconcealed 3 e11 79 89
Unconcealed 4 e12 81 91
Unconcealed 5 e21 111 109
Unconcealed 6 e22 129 161
Unconcealed 7 e00 159 179
6.1 Security violence due to uses of unconcealed
keys:
By using the unconcealed keys in Public key
cryptosystem disclosing public key is equivalent to
disclosing the private key, so one should strictly avoid
uses of these kinds of entities. For the cryptanalysts it
will be good practice to try to decrypt the message first
by the known entity that is public key.
6.2. Resolving Un-concealed key values
We have found that each unconcealed key value fallows
one definite relation (8) which is;
(e2 -1) mod g= 0 ……………….(8)
Here we have replaced φ(n) by an alternative notation
by g, saying φ(n) = g;
There will be two methods to avoid such kind of
values,
1. Modifying the structure of Extended Euclid
algorithm
2. Placing a check for (e2 -1) mod g= 0 in step of
selection of key value, step 4 of RSA key generation.
Case1. There are few advantages and disadvantages of
both of above methods. If we go for such a check in the
calculation of multiplicative inverse we have to only
place a single check of the form
If (e == d) then return unconcealed and loop back to
step 4 of RSA key generation … (9)
I.e. choose the next value as e so that previous one is
un-concealed.
Case2. If we go for check in the selection of the key in
step 4, the check structure will be of the form;
(e2 -1) mod g= 0 then declare unconcealed and loop
back to step 4 ……………… (10)
In the case 1 it seems to be lengthier task as compared
to case 1, because we have to loop back after the
execution of whole steps of Extended Euclid algorithm,
but in the case 2 we have a check before the Extended
Euclid structure so it don’t required lengthier loop back.
But if we analyze the complexity of checks, then we
found the time and space complexity of (9) is high in a
great deal than one in (10), and we have to apply check
on each e value. We will found the loop back after the
execution of Extended Euclid structure only in the 7
cases, since there are only 7 unconcealed key values for
φ(n) = (p-1) * (q-1) where p, q prime so this is the case
for only those values but the performance penalty of
relation structure (10) is more high which is the case for
all the e in finite ring. It is better practice to check the
unconcealed values during the calculation of modular
multiplicative inverse e; i.e. case (1).
Case1. Proposed modification in Extended Euclid
algorithm for avoiding unconcealed values
ARM_Euclid(x,y)
{
A1=0, A2=x;
B1=1, B2=y;
while(1)
{
if B2 = 0 then return NO_INVERSE;
if B2 = 1 then
{
if(inverse == e) then return unconcealed;
else
return(B1);
}
q=(A3/B3)/1;
T1=A1-(q*B1); if T1<0 then T1=T1+x;
T2=A2-(q*B2); if T2<0 then T2=T2+x;
A1=B1; A2=B2;
B1=T1; B2=T2;
}
}
Case2. Proposed modification in selection of e to avoid
unconcealed keys
1. Select prime integers p, q
2. Calculate n=p*q
3. Calculate φ(n)=(p-1)*(q-1)
4. Choose e, so that GCD(e, φ(n))=1 && s (e2 -1)
mod φ(n) != 0
5. Calculate d, so that d ≡ e-1 mod φ(n)
VII. A Symmetric RSA scheme
The symmetric RSA scheme can presented by using the
unconcealeds as the key elements for the purpose, as we
have seen in above section that there are seven
unconcealeds while calculating the multiplicative
inverse of a totient function used in asymmetric RSA,
which remains untransformed in the process. The steps
of calculating the private key elements are as fallows:
1. Select prime integers p, q
2. Calculate n=p*q
3. Calculate φ(n)=(p-1)*(q-1)
4. Choose e, so that GCD(e, φ(n))=1 && (e2 -1) mod
φ(n) = = 0
Encryption:
For message M
C = Me mod n
Decryption:
M = Ce mod n
VIII. Conclusions
The main results drown from this work are fallowing
1. ABES-ARM variant to encrypt efficiently the M >
n of the same order
2. Extended key space can be achieved by adoption of
the proposed modifications in extended Euclid
algorithm.
3. Security of the RSA cryptosystem can be enhanced
in a public key system by avoiding the unconcealed
keys.
4. We can use the RSA scheme in a symmetric
manner by using unconcealed keys, the most easy
calculated symmetric keys are given as φ(n)-1 and
φ(n)/2 + 1.
References
[1] R.L. Rivest, A. Shamir, and L. Adleman; A Method
for Obtaining Digital Signatures and Public-Key
Cryptosystems Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge;
1978; original RSA papers @
http://people.csail.mit.edu/rivest/Rsapaper.pdf; p 6-8;
[2] R. Schroeppel; contributor author of the underlying
mathematics on original RSA papers as per the [1],
Massachusetts Institute of Technology, Cambridge;
1978;
[3] William Stallings; Cryptography and Network
Security, Principles and Practice Third edition; Pearson
Education (Singapore), Delhi; 2003;
[4] Wikipedia, the encyclopedia; Bézout's identity,
Modular multiplicative inverse, extended Euclidean
algorithm; @ http://en.wikipedia.org/wiki/; Nov 2008;