DEALING WITH
UNCONCEALED KEYS IN RSA CRYPTOSYSTEM
Rahul Yadav1, Praveen
Kumar Vishnoi2, Sohit Kumar Ch.3
1,2Department of IT, SITE Nathdwara,
Rajasthan
3Department of MCA, IET Alwar,
Rajasthan
1yadav.rahul@live.com, 2erpv89@gmail.com,
3sohitt@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 eth
power modulo n. That is, the result (the cipher text C) is the
remainder when Me 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) = Me (mod n), for a message M .
M = D(C)
= Cd (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
ap-1 = 1 mod p
An alternative form of the theorem is also useful: If p is
prime and a is any positive integer, then
ap = a mod p
Or its simply Rich Schroeppel’s proof of RSA’s underlying
mathematics i.e.
Med = 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
φ(Pe)=
Pe - Pe-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/2w
because we will not get the term of the form g/2w 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 (e2-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;
(e2 -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 (e2 -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;
