PKC Algorithm
PKC Algorithm
PKC Algorithm
RSA
RSA & Diffie-Hellman
RSA - Ron Rivest, Adi Shamir and Len Adleman
at MIT, in 1977.
RSA is a block cipher
The most widely implemented
Diffie-Hellman
Exchange a secret key securely
RSA
best known & widely used public-key scheme
can be used to provide both secrecy & digital
signatures
security due to cost of factoring large numbers
Key Lengths
SKE length PKC length
56 bits 384 bits
64 bits 512 bits
80 bits 768 bits
112 bits 1792 bits
128 bits 2304 bits
Decryption is
M = 1123 mod 187 = 88
RSA Example - Key Setup
Select primes
p=11 & q=3
Compute n
n = pq = 11 x 3 = 33
Compute phi value
ø(n)=(p–1)(q-1)=10 x 2 = 20
Select encryption parameter
gcd(e: gcd(e,20)=1; choose e = 3
Determine decryption paramter
d: de=1 mod 20 and d < 20
Value is d=7 since 7X3=21=20x1+1
Publish public key PU={3,20}
Keep secret private key PR={7,20}
RSA Example - En/Decryption
The sample RSA private/public operations are:
Given message M = 7 (note that 7<33)
Encryption is
C = 73 mod 33
= 343 mod 33
= 13
Decryption is
M = 137 mod 33
= 13(3+3+1) mod 33
= (133 mod 33)(133 mod 33)(13 mod 33)mod 33
= (2197 mod 33)(2197 mod 33)(13)mod 33
= 19.19.13 mod 33 = 4693 mod 33
= 7
Another Example
Consider the text grouping in the groups of three i.e.
ATTACKXATXSEVEN = ATT ACK XAT XSE VEN
Value is d=11787
u 6