Abstract by anuja a sonalker on Asymmetric Key Distribution

2.4.1 How the RSA keys are computed: 
First, very large primes p, q are randomly generated such that p 
≠
q. After verifying their 
prime nature, the modulus N = p · q is computed and made public. However, p and q are 
never made public. Hiding the value of p and q ensures that e
and d
cannot be computed 
easily. e is selected such that the greatest common divisor of 
φ
(n) and e is 1, where 
φ
(n) = 
(p-1) · (q-1), i.e., they have no common factors between them. 
Thus, e 
∋
gcd (e, 
φ
(n)) = gcd(e, (p-1).(q-1)) = 1 and
d = 1/ e (mod 
φ
(n)) = 1/ e (mod (p-1)(q-1)). 
2.4.2 Why this works 
According to Fermat’s Theorem[11], if M 
≠
0: 
M
p-1
= 1 mod p 
M
φ
(n)
= 1 mod p since p-1 divides 
φ
(n). 
Similarly M
φ
(n)
= 1 mod q since q-1 divides 
φ
(n). (parallel argument as above) 
Therefore, M
φ
(n)
= 1 mod N. 
M
k
φ
(n) 
= 1 mod N, for any k >0 
And M
k
φ
(n)+1 
= M
k
φ
(n)
. M = 1 mod N. M = M mod N , even if M=0. 

---

12 
Since e.d = 1 (mod 
φ
(n)) according to RSA [8]
⇒
e.d = 1 + k
φ
(n), for some k. 
Thus M
e.d
= M mod N. 
And S
e 
mod N = (M
d 
)
e 
mod N = M mod N. 
 
2.5 Distributed Key Structure: 
Distributed key structure, also known as Secret Sharing, refers to the technique of 
splitting the secret key into smaller components and distributing it among a set of peers. 
Since the secret key is now shared between a number of peers, it becomes the task of the 
peers to collectively apply their secret shares to create signature shares of the original 
message. The complete signed certificate is created without assembling the entire key at 
any point of time. The key shares are used to create signature shares of the message and 
the signature shares are combined to create the signed certificate. 
Hence, d
k
= d
1
+ d
2 
+ d
3 
+……..+ d
t 
where there are t shares of the key. 
C
1
= 
ƒ
(M, d
1
), C
2
= 
ƒ
(M, d
2
) , C
3
= 
ƒ
(M, d
3
) ……. C
t
= 
ƒ
(M, d
t
)
C = H { C
1
·C
2
·C
3……….
C
t 
} 
M = D(C) = 
ƒ
(C, e
k
). 
Though the scheme above offers security against easy theft of the single private key by 
dividing it into shares, it opens up another issue, which is the inability of the encryption 
agents to successfully create a signed share if any ONE of them were to fall prey to an 
attacker. This system has zero fault-tolerance, i.e., the inability of a single entity to 
contribute a share can result in the inability of the entire system to create the completely 
signed certificate. To improve the tolerance, we incorporate a small amount of 

---

13 
redundancy in the system by reducing the exact number of required shares to be less than 
the total number of encryption agents present. This minimum number of servers required 
to create the complete signed signature is known as the threshold of the system. For 
example, if out of 5 present systems all five are required to provide legitimate signatures, 
the tolerance of the system is said to be zero. If only 3 of them are required, the system 
has a tolerance of 2 - as long as two or fewer servers are compromised, the system is still 
able to produce a legitimate signature.