DEALING WITH UNCONCEALED KEYS IN RSA CRYPTOSYSTEM

DEALING WITH UNCONCEALED KEYS IN RSA CRYPTOSYSTEM

Rahul Yadav¹, Praveen Kumar Vishnoi², Sohit Kumar Ch.³

^1,2Department of IT, SITE Nathdwara, Rajasthan

³Department of MCA, IET Alwar, Rajasthan

¹yadav.rahul@live.com, ²erpv89@gmail.com,

³sohitt@gmail.com

Abstract: We discuss approaches for the performance and security of public key cryptosystems. In particular we study the RSA public key cryptosystem. We begin with an introduction to the theory of RSA public key cryptosystem and describe the main results to be used throughout the rest of the work. Next we discuss text book versions of existing algorithms suggested and used for the real world implementation of RSA public key cryptosystems in the literature. Then we discuss the pre-assumptions exist in the key generation of RSA, during this phase we will show the concept of un-concealed key values .We go on to analyze the security dimension on the RSA public key cryptosystem which use the concept of unconcealed key values during the key generation steps of RSA. On the next we will see that how we can avoid the generation of unconcealed key values

Key words & Phrases: Key Words and Phrases: Public-key cryptosystems, security, cryptography, unconcealed key(s), Bézout’s identity.

1. Introduction

There exist two main branches of Network Security: cryptography is domain concerning with the writing of messages in ciphers and the creation of cryptographic algorithms, while cryptanalysis is concerned with reading ciphers by breaking secret keys. In Ancient times there exist many examples of cryptography. Around thousand years BC, Egyptian people made use of hieroglyphic transformations to secure messages. Mesopotamian and Babylonian intellectuals applied similar techniques to render cuneiform tablets into garbage or simply Cipher to the uninitiated persons. The Greeks were first to employ cryptography (with the close relation to steganography, which is concerned with concealing the existence of communication rather than content) for army and top secret purposes.

With the advancement of computing and communication networks in the 1970s, securing communication and data in transition over the networks became an important concern in the private sector too, not limited with army. Especially the needs of the banking in particular, for secure digital communication became most urgent. Developments at IBM resulted to the design of Lucifer, one of the first ciphers for digital communications. The National Security Agency (NSA) offered several improvements to Lucifer, and in late 1975 the National Bureau of Standards presented its modified and more secure version as the Data Encryption Standard, or DES. Thus the first standard for encryption began to gain widespread use as a Private Key cryptographic method proceeded by the Diffie Hellman Key exchange to RSA and Digital Signatures and many more up signcryption.

In this paper our main focus will remain over RSA key generation. We begin with an introduction to the theory of RSA public key cryptosystem and describe the main results to be used throughout the rest of the work. Next we discuss text book versions of existing algorithms suggested and used for the real world implementation of RSA public key cryptosystems in the literature. Then we discuss the pre-assumptions exist in the key generation of RSA, during this phase we will show the concept of un-concealed key values.

2. RSA cryptosystem

RSA is the very first algorithm of Public Key Cryptography and most popular yet in modern era of communication. To encrypt a message M with RSA method, using a public key pair (e, n) proceed as follows. (Here e and n is a pair of positive integers.)

  First, represent the message as an integer between 0 and n — 1. (Break a long message into a series of blocks, and represent each block as such an integer.) Use any standard representation. The purpose here is not to encrypt the message but only to get it into the numeric form necessary for encryption, Then, encrypt the message by raising it to the e^th power modulo n. That is, the result (the cipher text C) is the remainder when M^e is divided by n.

    Decryption of the cipher, raise it to another power d, again modulo n. The encryption and decryption algorithms E and D are thus:

C   =   E(M) = M^e   (mod n), for a message M .

M  =  D(C) = C^d    (mod n), for a cipher text C .

     Note that encryption does not increase the size of a message; both the message and the cipher text are integers in the range 0 to n — 1

     Method by which one chooses his or her encryption and decryption keys, if want to use RSA method; First compute n as the product of two large and distinct prime numbers p and q:

n = p *  q .

    These primes are very large, “random” primes. Although one will make n public, the factors p and q will be effectively hidden from everyone else due to the enormous difficulty of factoring n. This enables communicating entity hides the way decryption exponent d can be derived from encryption exponent e.  Then pick the integer d to be a large, random integer which is co-prime to (p — 1) * (q — 1). That is, check that d satisfies:

gcd(d, (p — 1) * (q — 1)) = 1

(“gcd” means “greatest common divisor”).

    

The integer e is finally computed from p, q, and d to be the “multiplicative inverse” of d, modulo (p — 1) • (q — 1) using extended Euclid algorithm. Thus we have

d ≡ e^-1 (mod (p — 1) * (q — 1)).

Or simply,

e * d = 1   (mod (p — 1) * (q — 1)).

     The RSA algorithm should not be badly co-related with the “exponentiation” technique presented in Diffie and Hellman Key Exchange to solve the key distribution. Diffie and Hellman’s technique permits two users to determine a key in common to be used in a normal cryptographic system. It is not based on a trap-door one-way permutation

3. Break through with the foundational algorithms of RSA

Fermat’s and Euler’s Theorems, these are the two theorems that play important role in RSA’s public key cryptosystem. RSA’s implementation is impossible without help of the Extended Euclid Algorithm as two of the key exponents e and d holds the properties of Bézout's identity as

ax + by = gcd (a, b)

or for simplicity

ae + bd = 1

We crack a trick and when calculating decryption exponent d we are known to value e and its gcd (that is 1 for co-primes), and utilize Bézout's identity with Extended Euclid Algorithm to calculate d, and Fermat’s Theorem plays its role during enciphering and deciphering; while a special case of Euler’s Theorem plays role in key generation which is nothing but the Toient function calculated as a value

φ(n) = [(p-1)(q-1)].

It is used in generation of key exponents e and d.

Fermat’s Theorem: Fermat’s theorem states the fallowing: if a is a positive integer not divisible by p, then

a^p-1 = 1 mod p

An alternative form of the theorem is also useful: If p is prime and a is any positive integer, then

a^p = a mod p

Or its simply Rich Schroeppel’s proof of RSA’s underlying mathematics i.e.

M^ed = M mod n (as n is product of primes)

Euler’s Totient Function: Before presenting the Euler’s theorem, we need to introduce an important quantity in number theory, referred to as Euler’s Totient function and written φ(n), where φ(n) is the number of positive integers less than n and relatively prime to n. For a prime number p,

φ(p) = p-1

Now suppose that we have two prime numbers p and q, with p != q. Then, for

n = p*q,

φ(n) = φ(pq) = φ(p) * φ(q) = (p -1) (q -1)

the fallowing relation holds if p and q are relatively prime

φ(n) = φ(pq) = φ(p) * φ(q )

And, for p being prime

φ(P^e)= P^e - P^e-1

Extended Euclidean Algorithm: 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.

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 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

4. Key generation of RSA algorithm in depth

RSA: Un-concealed Key Values: In a simplest textbook example of RSA keys yields;

p=17, q=11

n = p*q = 17*11 = 187

φ(n) = (p-1)*(q-1) = 16*10 = 160

we calculate all the key values and encountered some of the special cases. You may observe the key values for encryption keys e = (31, 49, 79, 81, 111, 129, 159) with respect to n=187, that Decryption keys d for these values by the relation d = (k* φ(n) +1)/e, are respectively identical, i.e.

e = (31, 49, 79, 81, 111, 129, 159).

d = (31, 49, 79, 81, 111, 129, 159).

“In the case, values of e map to some values of d; these key values can be referred as un-concealed keys”.

Now these three numbers are subject to major attention as their distance from Euler’s Totient function of n is fixed:

159 = 160 -1 = φ(n) - 1

(79, 81) = (160/2) +1 = (φ(n)/2) +1

Now notice these values for more large primes:

n = p * q	1517= 37 * 41	1641179 = 1999 * 821	201703 = 401 * 503
φ(n)	1440	1638360	200800
e = φ(n) – 1, (φ(n)/2) +1	1439, 719, 721	1638359, 819179, 819181	200799, 100399, 100401
d =	1439, 719, 721	1638359, 819179, 819181	200799, 100399, 100401

In general, for ease of notation  if we put

φ(n) = g

And for the simplified properties of congruence relation between e and d using Bézout's identity,

As in Bézout's identity

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  

// using Bézout's properties for some integer constant k

Yields

·         (k* φ(n) + 1) / e = d

Since: (1438 * 1440 + 1)/ 1439 = 1439

(359* 1440 + 1)/ 719 = 719

(361 * 1440 + 1)/ 721 = 721

And (1638358 * 1638360 + 1)/ 1638359 = 1638359

(409589* 1638360 + 1)/ 819179 = 819179

(409591* 1638360 + 1)/ 819181 = 819181

And (200798 * 200800 + 1)/ 200799 = 200799

(50199 * 200800 + 1)/ 100399 = 100399

(50201 * 200800 + 1)/ 100401 = 100401

In general, If φ(n) = g

((g-2)*g +1)/ g-1 = g-1                           … (A)

(((g/4)-1)*g +1)/ ((g/2)-1) = (g/2)-1       ... (B)

(((g/4)+1)*g +1)/ ((g/2)+1) = (g/2)+1    ... (C)

So we can say that key values for e = φ(n) – 1, (φ(n)/2) +1 will always be unconcealed. Further this relation can’t be generalized for g/2^w because we will not get the term of the form g/2^w as the midterm in the relation. There will be 4 more unconcealed key values for this kind of finite field, i.e. multiplication modulo field, for which the fallowing relation will be always true including above 3 (i.e. a multiplication modulo field have 7 unconcealed entities excluding 0, 1, and Base(φ(n)):

5. 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 value(s) and then decrement the result by 1, the resulting value (e²-1) will be a multiple of φ(n).

5.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.

5.2. Resolving Un-concealed key values

We found that each unconcealed key value fallows one definite relation which is;

(e² -1) mod g= 0

     There will be two methods to avoid such kind of values,

1.      Modifying the structure of Extended Euclid algorithm

2.      Placing a check for if (e² -1) mod g= then avoid the key, in step of selection of key value, step 4 of RSA key generation.

6. Conclusions

The main results drown from this work are fallowing

1.      Security of the RSA cryptosystem can be enhanced in a public key system by avoiding the unconcealed keys.

2.      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

Dissertations:

[1] G. Durfee; Cryptanalysis of RSA using algebraic and lattice methods Introduction notes; Stanford University, June 2002; Pages 1-3;

[2] R. Yadav; Review: RSA and ABESARM Methods for Performance Enhancement Chapters 3 and 6; Academy of Business & Engineering Sciences, Ghaziabad, Apr 2009; Pages 15-17, 24-28;

Papers:

[3] 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;

[4] R. Schroeppel; contributor author of the underlying mathematics on original RSA papers as per the [2], Massachusetts Institute of Technology, Cambridge; 1978;

[5] R. Yadav, A. Perti, and M. Tausif: Review RSA and ABESARM Methods for Performance Enhancement Proceedings of Conference on Information Technology for Business Transformation, Ajay Kumar Garg Engineering College, Ghaziabad; Apr 2009;

[6] R. Yadav, H. Gupta, and D. Yadav: RSA Operations with Performance Tuning Proceedings of Conference on Issues & Challenges in Networking Intelligence and Computing Technologies, Krishna Institute of Engineering & Technology, Ghaziabad; Sep 2011;

Books:

[7] William Stallings; cryptography and Network Security, Principles and Practice Third edition; Pearson Education (Singapore), Delhi; 2003;

[8] Singh, S. The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. New York: Anchor Books, 1999.

Others:

[9] Wikipedia, the free encyclopedia; Bézout's identity, Modular multiplicative inverse, extended Euclidean algorithm; @ http://en.wikipedia.org/wiki/; Apr 2009, and revised on Nov 2011;

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;